8 - Largest product in series

Problem

The four adjacent digits in the $1000$-digit number that have the greatest product are $9 \times 9 \times 8 \times 9 = 5832$. 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the $1000$-digit number that have the greatest product. What is the value of this product?

Foundations

Windows

In many programming languages, there is an operation that gives you an enumerator over multiple elements of an array or a string. Look at the following examples and see if you can spot how this is useful to this problem.

Ruby

nums = "123456789"
enumerator = nums.chars.each_cons 2
enumerator.next
=> ["1", "2"]
enumerator.next
=> ["2", "3"]
enumerator.next
=> ["3", "4"]

Rust

fn main() {
    let nums = "123456789";
    let chars = nums.chars().collect::<Vec<char>>();
    for window in chars.windows(4) {
        println!("{:?}", window);
    }
}

❯ cargo run
['1', '2', '3', '4']
['2', '3', '4', '5']
['3', '4', '5', '6']
['4', '5', '6', '7']
['5', '6', '7', '8']
['6', '7', '8', '9']

Uiua's Stencil

To get windows of an array in Uiua, use stencil.

Stencil is clever and can sometimes adjust the window size to the number of arguments a function requires. For example, add needs two arguments.

    ⧈+ [0 1 2 1 6]
[1 3 3 7]

Otherwise, you can supply a function to stencil and state the window size. I like subscripts.

    st,13id"Shiver me timbers"
    ⧈₁₃∘"Shiver me timbers"
 ╭─
╷ "Shiver me tim"
  "hiver me timb"
  "iver me timbe"
  "ver me timber"
  "er me timbers"
                  ╯

Towards a solution

We know that we want to look at 13 digits at a time. This should be possible for us to do with windows, using stencil. We just need to acquire a digit array.

Digits from base 10

Let's imagine for a moment that we have to solve this for a 4-digit product inside a 10 digit number. Maybe, $7281965729$ or something.

So, what we need is to change the number into an array of digits.

    Wizardry 7281965729
[7 2 8 1 9 6 5 7 2 9]

One way we could do this is with base,10. That will give us the number as an array, but in reverse. Just to make reading easier, I'll apply rev.

    rev base,10
    ⇌ ⊥₁₀7281965729
[7 2 8 1 9 6 5 7 2 9]

Next we apply a stencil with a window size 4. Let's supply the function id just to see what is happening.

    ⧈₄∘ ⇌ ⊥₁₀ 7281965729
╭─
╷ 7 2 8 1
  2 8 1 9
  8 1 9 6
  1 9 6 5
  9 6 5 7
  6 5 7 2
  5 7 2 9
          ╯

Great. That looks correct. Let's replace id with reduce mul to get the digit products.

    ⧈₄/× ⇌ ⊥₁₀ 7281965729
[112 144 432 270 1890 420 630]

Alright. $9 \times 6 \times 5 \times 7 = 1890$ is a clear winner.

Now we just have to acquire the maximum with reduce max

    /↥ ⧈₄/× ⇌ ⊥₁₀ 7281965729
1890

Alright. Let's crunch the 1000 digit number.

    /↥ ⧈₁₃/× ⇌ ⊥₁₀731..<truncated>..3450
    /↥ ⧈₁₃/× ⇌ ⊥₁₀inf
"Error: Cannot take base of ∞"

Oh yeah. Our number is too big. It just gets changed into inf. Uiua doesn't have BigInt.

Digits from string

Let's then see what we can do with a string of digits instead. Using the previous example number, how do we acquire digits?

As before, we want something like this.

    Wizardry "7281965729"
[7 2 8 1 9 6 5 7 2 9]

Well, think about a string. What is its shape?

    △ "1234"
[4]

Isn't this the same shape as an array?

    △ [1 2 3 4]
[4]

Usually, when we operate on a straightforward array in Uiua, we know to use either a pervasive function or rows if we want something to apply to each element. Let's try rows parse on the string.

    ≡⋕ "7281965729"
[7 2 8 1 9 6 5 7 2 9]

Nice. Now we can do the same thing as before.

    /↥ ⧈₄/× ≡⋕ "7281965729"
1890

Excellent. Now we can apply the same set of jargon to the 1000-digit number.

    /↥ ⧈₁₃/× ≡⋕ "731..<truncated>..3450"
23514624000

Extra credit - Getting digits pervasively

Thanks to Tyz for the feedback.

Here it is again. Oh boy.

If it's rows

it is slows

If you are interested in speed, then we might want to consider a pervasive action on the string instead. In Uiua, when we subtract a character from a string, it results in an array of differences. These differences are between the ordinal values or the numerical representations of a character. For example.

    -@A "ABCDEFG"
[0 1 2 3 4 5 6]

These distances climb as we go along in sequence. Luckily, the characters for all digits, 0-9, are in sequence in the ASCII table; from 48 to 57.

    -@0 "0123456789"
[0 1 2 3 4 5 6 7 8 9]

Things inside the string don't have to be in sequence though. We still obtain the distance of each character from the character '0', namely the digit itself.

    -@0 "812932842"
[8 1 2 9 3 2 8 4 2]

This gives us the corresponding digit array.

Let's apply this to the 1000 digit number.

    /↥ ⧈₁₃/× -@0 "731..<truncated>..3450"
23514624000

How fast?

The pervasive solution runs very fast.

    ⊙◌⍜now(/↥ ⧈₁₃/× -@0 "731..<truncated>..3450")
0.00003886222839355469

vs parse rows.

    ⊙◌⍜now(/↥ ⧈₁₃/× ≡⋕ "731..<truncated>..3450")
0.00030612945556640625

So, if 3000 microseconds is not your jam and you really want 300 microseconds instead, be pervasive.