Project Euler Problem 8 Solution

Question

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

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

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

Go

package main

import "fmt"
import "strings"

func main() {
    digits := `
    73167176531330624919225119674426574742355349194934
    96983520312774506326239578318016984801869478851843
    85861560789112949495459501737958331952853208805511
    12540698747158523863050715693290963295227443043557
    66896648950445244523161731856403098711121722383113
    62229893423380308135336276614282806444486645238749
    30358907296290491560440772390713810515859307960866
    70172427121883998797908792274921901699720888093776
    65727333001053367881220235421809751254540594752243
    52584907711670556013604839586446706324415722155397
    53697817977846174064955149290862569321978468622482
    83972241375657056057490261407972968652414535100474
    82166370484403199890008895243450658541227588666881
    16427171479924442928230863465674813919123162824586
    17866458359124566529476545682848912883142607690042
    24219022671055626321111109370544217506941658960408
    07198403850962455444362981230987879927244284909188
    84580156166097919133875499200524063689912560717606
    05886116467109405077541002256983155200055935729725
    71636269561882670428252483600823257530420752963450
    `
    digits = strings.Replace(digits, "\n", "", -1)
    digits = strings.Replace(digits, "\t", "", -1)

    max := 0
    for i, l := 0, len(digits); i < l-13; i++ {
        slice := digits[i : i+13]
        product := 1
        for _, c := range slice {
            product *= int(c - '0')
        }
        if product > max {
            max = product
        }
    }
    fmt.Println(max)
}
$ go build -o adjacent-product adjacent-product.go
$ time ./adjacent-product
real   0m0.001s
user   0m0.000s
sys    0m0.000s

Haskell

parse :: String -> [Int]
parse = map (read . return) . concat . lines

chunks :: Int -> [a] -> [[a]]
chunks n l | length chunk < n = []
           | otherwise = chunk : chunks n (tail l)
           where chunk = take n l

largestProduct :: [[Int]] -> Int
largestProduct = maximum . map product

main :: IO ()
main = do
        str <- readFile "/home/zach/code/euler/008/numbers.txt"
        print $ largestProduct $ chunks 13 $ parse str
$ ghc -O2 -o great-prod great-prod.hs
$ time ./great-prod
real   0m0.004s
user   0m0.000s
sys    0m0.000s

JavaScript

const runs = `
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
`.trim().split("\n").join("").split(/[01]+/)
const x = 13
let max = 0
runs.forEach((run) => {
  if (run.length < x) {
    return
  }
  for (let i = 0, l = run.length; i <= l - x; i++) {
    const digits = run.substring(i, i + x).split("")
    const product = digits.reduce((prod, c) => prod * parseInt(c), 1)
    if (product > max) max = product
  }
})
console.log(max)
$ time node --use-strict --harmony-destructuring largest-product.js
real   0m0.088s
user   0m0.088s
sys    0m0.000s

Python

#!/usr/bin/python
numbers = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
'''
numstring = numbers.strip().replace('\n', '')
greatest_product = 0

for i in range(len(numstring)):
    product = 1
    substring = numstring[i:i+13]
    for digit in substring:
        product *= int(digit)
    if product > greatest_product:
        greatest_product = product

print(greatest_product)
$ time python3 great_prod.py
real   0m0.025s
user   0m0.024s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
numbers = <<EOS
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
EOS
numbers = numbers.split.join('')
max = 0
numbers.split('').each_with_index do |char, i|
  product = numbers[i...i+13].each_char.inject(1) {|acc, digit| acc * digit.to_i}
  if product > max
    max = product
  end
end
puts max
$ time ruby great_prod.rb
real   0m0.031s
user   0m0.028s
sys    0m0.000s

Questions? Comments? Send me an email: [email protected]