Climbing Mount Euler

Foreword

This post presents my BQN solutions to some of the problems in Project Euler. It is discouraged to share them, but I very much dislike writing throw-away code, and that's why they are here1. First I will solve problems in order, and then I will probably pick the ones that I find interesting. This is my profile, if you want to see my progress:

My Project Euler Profile

Let's start by defining some utilities that will be shared by several problems: 

utils ← {
  Sieve ⇐ 2⊸↓{
    L ← {↕∘⌈⌾((𝕨ט⊸+𝕨×⊢)⁼)∘≠⊸{0¨⌾(𝕨⊸⊏)𝕩}𝕩}
    S ← ⊢>ט∘⊣⊸⥊⟜0»≠∘⊢⥊↑⟜1
    𝔽/(𝕩⥊1)≤⟜640◶L‿S⍟⊑´⌽𝔽↕⌈√𝕩
  }
  Rosser ⇐ ⌈⋆⁼{𝔽∘𝔽⊸+⟜𝔽⊸×}
  Tau ⇐ {2+´(2⊸×-⊢×⊣=·⌊÷˜⟜𝕩)⟜(0=|⟜𝕩)2↓↕1+⌊√𝕩}
}
parsing ← {
  Split ⇐ (¬-˜⊢×·+`»⊸>)∘≠⊔⊢
}

Problem 1

E1 ← +´(∨´0=5‿3|<)⊸/

Problem 2

Estimate the upper bound with Binet's formula. 

E2 ← {+´(¬2⊸|)⊸/{⊑¨+`∘⌽⍟(↕𝕩)↕2}(⌈0.5+𝕩⊸×÷○(⋆⁼)2÷˜1⊸+)√5}

Problem 3

A brute force attempt, in which I got lucky. We create a primes table, and then check: 

p ← ¬∘∊⟜(⥊×⌜˜)⊸/2↓↕1e4
{𝕩=×´f←p/˜0=p|<𝕩 ? ⌈´f; @}600851475143

Provided the size of the input, a much reasonable approach is trial division. We can achieve this with the following tacit function: 

E3 ← ⊢´(0=|)◶⟨+⟜2⊸⋈, ⊣⋈÷˜⟩´•_while_(ט⊸<´)

Explanation: since the number is odd, we can start with 3. While the current divisor is less than the square root of the current number, we check if it divides the number. If it does, we divide the number by the divisor. If it doesn't, we increment the divisor by 2 (to consider only odd factors). This works because a composite number must have a prime factor less than or equal to its square root.

Problem 4

Anything other than brute force here? A little tacit function: 

E4 ← ⌈´·(⌽⊸≡•Fmt)¨⊸/·⥊×⌜˜

This runs in 5 ms with the optimization of searching only in the 900's.

Problem 5

That felt almost trivial. 

E5 ← •math.LCM´

Problem 6

Yeah well, what can I say, I love this identity: 

E6 ← ט⊸(+´×-⊣)

In fact, I was terribly stupid. There are closed form solutions for the sum of the first \(n\) integers and its squares (remember induction?). So after squaring the former, subtracting the latter and simplifying we get this constant time solution: 

12÷˜×´⟨⊢, -⟜1, +⟜1, 2+3⊸×⟩{𝕎𝕩}¨100

Quite a few characters more, though.

Problem 7

The idea here is to use Eratosthenes' sieve with a correct upper bound, which we get thanks to Rosser's theorem: 

E7 ← -⟜1⊑utils{𝕗.Sieve𝕗.Rosser}

The sieve uses heuristics to decide which operation to perform when marking the multiples, either zeroing the indices for large argument or creating a mask and multiplying by the current array in the fold. As a bonus, here is a comparison of Eratosthenes' sieves implementations: 

S0 ← 2⊸↓{𝔽/(𝕩⥊1)⊑◶⊢‿{↕∘⌈⌾((𝕨ט⊸+𝕨×⊢)⁼)∘≠⊸{0¨⌾(𝕨⊸⊏)𝕩}𝕩}´⌽𝔽↕⌈√𝕩}
S1 ← 2⊸↓{𝔽/(𝕩⥊1){↕∘⌈⌾((𝕨ט⊸+𝕨×⊢)⁼)∘≠⊸{0¨⌾(𝕨⊸⊏)𝕩}𝕩}⍟⊑´⌽𝔽↕⌈√𝕩}
S2 ← 2⊸↓{𝔽/(𝕩⥊1){𝕩>(≠𝕩)↑/⁼↕∘⌈⌾((𝕨ט⊸+𝕨×⊢)⁼)≠𝕩}⍟⊑´⌽𝔽↕⌈√𝕩}
S3 ← 2⊸↓{𝔽/(𝕩⥊1)(⊢>ט∘⊣⊸⥊⟜0»≠∘⊢⥊↑⟜1)⍟⊑´⌽𝔽↕⌈√𝕩}
S4 ← {
  L ← {↕∘⌈⌾((𝕨ט⊸+𝕨×⊢)⁼)∘≠⊸{0¨⌾(𝕨⊸⊏)𝕩}𝕩}
  S ← ⊢>ט∘⊣⊸⥊⟜0»≠∘⊢⥊↑⟜1
  2↓/(𝕩⥊1)≤⟜640◶L‿S⍟⊑´⌽2↓↕⌈√𝕩
}
•Show 1=≠∘⍷ S0‿S1‿S2‿S3‿S4 {𝕎𝕩}¨< 1e4
S0‿S1‿S2‿S3‿S4 {𝕏•_timed𝕨}⌜˜ 10⋆3‿5‿7‿8‿9

1
┌─                                                                                                      
╵          8.5813e¯5          8.4411e¯5             8.5593e¯5           3.958e¯6 3.6970000000000003e¯6  
         0.001241902        0.001077388 0.0009073750000000001          7.2879e¯5             7.0424e¯5  
         0.144439973        0.139676776           0.120608139        0.049470815           0.029924439  
  3.5437995570000003 2.0786221950000003    3.6722926040000003 3.5986206610000004           0.985192575  
  28.261043074000003 27.725597807000003     92.62981303100001  98.58912269400001    17.110364360000002  
                                                                                                       ┘

Problem 8

A simple windowed reduction: 

E8 ← ⌈´·(×´⊢-@+48˙)˘13⊸↕

Problem 9

A stupid brute force does the trick: 

{⊑(××+⌾(ט))´¨1+/○⥊⟜(↕≢)(<⌜˜↕≠𝕩)×(1e3=+++⌾(ט))⌜˜𝕩} 1+↕1e3

But I hate it and it is painfully slow. The correct way of doing it is using Euclid's formula. 

E9 ← {⋆⟜4{2×××𝔽˜-𝔽}´¨1+/○⥊⟜(↕≢)⌊⊸=𝕩÷˜(⊢×+)⌜○(1+↕)˜⌈√𝕩}

Here we have used the fact that the sum of the triplet expressed with Euclid's formula must be \(km(m+n)=500\), with \(m>n>1\) coprime and one of them odd. It suffices to loop until √500 because \(m\) cannot be larger than it, as \(n\) is positive.

Problem 10

The sieve again: 

E10 ← +´utils.Sieve

Problem 11

This has to be brute force. First, I will parse the grid: 

inp11 ← ∘‿20⥊•ParseFloat¨' 'parsing.Split"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

Then we have this hideous thing: 

E11 ← {⌈´∾(×˝˘4⊸↕)¨(4≤≠)¨⊸/((⌽++´∘≢)⊸∾·+⌜´↕¨∘≢)⊸⊔⟜(∾˜)𝕩}⌈(⌈´∘⥊·×˝˘4⊸↕){𝔽⌈𝔽∘⍉}

It computes the answer in 300μs.

Problem 12

Here I tried to use an awesome array solution for the number of divisors 1+´0=↕⊸|, which unfortunately does not scale. So I use trial division for computing the divisor function, and also exploit the fact that since \(\text{GCD}(n, n+1)=1\), the divisor function is the product of the divisor functions of the two numbers, dividing by 2 the one that is even: 

E12 ← (2÷˜-⟜1⊸×)·⊢´{𝕊:
  (𝕩+1)⋈˜×´utils.Tau¨(2⊸|)◶⟨÷⟜2⋈1⊸+, ⊢⋈2÷˜1⊸+⟩𝕩
}´•_while_(500≥⊑)

Problem 13

Shall we play lottery with floating point addition? Put the input in a file and have fun: 

10↑·'.'⊸≠⊸/∘•Fmt·+´•ParseFloat¨∘•FLines

There, a tacit function for the sake of it, that works only by accident. We can always implement the high school sum algorithm though (check it out with Python or whatever): 

E13 ← {∾•Fmt¨{c∾˜𝕩10{𝕩-𝕗×c↩⌊𝕗÷˜𝕩+↩c}¨˜c←0}⌾⌽+˝•ParseFloat∘⋈⚇0>•FLines𝕩}

Problem 14

Memoization, so we don't wait an eternity: 

E14 ← {
  c ← •HashMap˜⋈1
  ⊑⍒2⊸|◶⟨÷⟜2, 1+3⊸×⟩{
    c.Has𝕩 ? c.Get𝕩;
    𝕩(⊢⊣c.Set)1+𝕊𝔽𝕩
  }¨1+↕𝕩
}

Problem 15

First generate the input array: 

inp15 ← 1⌾⊑21‿21⥊0

Then we can propagate all routes and get the final count: 

E15 ← ⊢´∘⥊(»+»˘)⍟(2-˜+´∘≢)

The repetition count is the number of diagonals minus one, your answer. This is unfortunately a slow \(O(mn)\) algorithm, for the optimal solution do this: 

2⊸×⊸•math.Comb

Problem 16

For this problem one is better off using a language with native support for big integers, which makes it trivial. No fancy math either. BQN has integers up to 2⋆53, so we need to roll our own algorithm. Let's first generate an array that will contain the digits of the result, using an estimation for the length: 

inp16 ← 1∾0⥊˜⌊10⋆⁼2⋆1000

Then we have the following tacit function, which I will dare say is beautiful: 

E16 ← +´10⊸(|+⟜»·⌊÷˜)•_while_(∨´≥⟜10)∘(2⊸×)⍟1000

This implementation of arbitrary precision arithmetic is way more elegant than the one I used in the related Problem 13, although it performs more (but vectorized) operations.

Problem 17

Nothing special here, store the lengths of the ones', teens' and tens' names (with padding), pass it in a modifier because a variable would be ugly, and pattern match: 

E17 ← (|⋈˜·⌊÷˜) {
   𝔽 _𝕣_ 𝕘 1000: 11;
   𝕩<100 ? (⊑10‿20⊸>⊐1˙)◶⟨0⊸⋈⊑𝔾, 𝕘⊑˜1⋈-⟜10, +´·⊑⟜𝕘2‿0⋈¨10⊸𝔽⟩𝕩;
   (7+0⊸⋈⊑𝔾)⊸+⟜(××3+𝕊)´100𝔽𝕩
} [0‿3‿3‿5‿4‿4‿3‿5‿5‿4, 3‿6‿6‿8‿8‿7‿7‿9‿8‿8, 0‿0‿6‿6‿5‿5‿5‿7‿6‿6]

The magic numbers 11, 7, and 3 are for one thousand, hundred and and respectively.

Problems 18 and 67

First we do some parsing, the lame padding to make it look like a proper low triangular matrix: 

inp18 ← >(⊢↑¨˜·≠⊢´)•ParseFloat⚇1' '⊸parsing.Split¨•FLines "../../supp/pe/18.inp"

┌─                                              
╵ 75  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
  95 64  0  0  0  0  0  0  0  0  0  0  0  0  0  
  17 47 82  0  0  0  0  0  0  0  0  0  0  0  0  
  18 35 87 10  0  0  0  0  0  0  0  0  0  0  0  
  20  4 82 47 65  0  0  0  0  0  0  0  0  0  0  
  19  1 23 75  3 34  0  0  0  0  0  0  0  0  0  
  88  2 77 73  7 63 67  0  0  0  0  0  0  0  0  
  99 65  4 28  6 16 70 92  0  0  0  0  0  0  0  
  41 41 26 56 83 40 80 70 33  0  0  0  0  0  0  
  41 48 72 33 47 32 37 16 94 29  0  0  0  0  0  
  53 71 44 65 25 43 91 52 97 51 14  0  0  0  0  
  70 11 33 28 77 73 17 78 39 68 17 57  0  0  0  
  91 71 52 38 17 14 91 43 58 50 27 29 48  0  0  
  63 66  4 68 89 53 67 30 73 16 69 87 40 31  0  
   4 62 98 27 23  9 70 98 73 93 38 53 60  4 23  
                                               ┘

Then, what a beautiful array dynamic programming solution! 

E18 ← ⊑+⟜(⌈⟜«)˝

This solution also works for Problem 67, which has only larger input. You get the answer in microseconds.

Footnotes:

1

If I make it that far, I will follow the rule of not sharing solutions to problems over 100. In that case, I will probably encrypt them with org-crypt, using the value of the solution as the key.