Project Euler: problem 8

Question

n = # some ridiculously large number, omitted
N = [int(i) for i in str(n)]
maxProduct = 0
for i in range(0,len(N)-4):
    newProduct = 1
    is_cons = 0
    for j in range(i,i+4):
        if N[j] == N[j+1] - 1:
        is_cons += 1
    if is_cons == 5:
        for j in range(i,i+5):
            newProduct *= N[j]
        if newProduct > maxProduct:
            maxProduct = newProduct
print maxProduct

I've been working on this problem for hours now and I can't get this to work. I've tried doing this algorithm on paper and it works just fine.. Could you give me hints what's wrong ?

Answer 1

10&#. 5 {.(}.~ I.@(= >./)@(5&(*/))) 10#.^:_1 number

is a J solution where number is the very long number as an extended integer.

It executes more or less from right to left, and parenthesis are used for two things - they pass along right arguments so that they can be used in more than one place, so that you don't have to create named intermediate variables, and to prioritize execution (of course, when an argument is passed in, it is clear that what is inside the parenthesis has to execute last, as opposed to first. J is a very interesting language, parenthesis mean both execute first and execute later. But in general, execution is right to left. The number is cracked into digits, and the sum product of each overlapping group of five digits is taken. The greatest sum-product is found and compared back against that vector to create a boolean vector, where the index of the comparison is found. The head of the original vector is then dropped, up to the index that was found. Then a five digit hunk of that is extracted, and those five digits are glued back together.

I think that problems as low as 8 are really designed just go get you going in Euler - they are simple, most of them are one liners in J.

I am not sure whether I did this as a one liner first time around I may have with an intermediate named variable - but since I have done a few of these problems, I believe I know J a lot better than I did, and I can put a phrase together like this without much problem, I know where to put the parenthesis. In that, doing the euler exercises has been successful.

Answer 2

Here is my solution:

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

print max([reduce(lambda accum, x : accum * x, [int(x) for x in number[i:i+5]]) for i in range(len(number) - 5)])

Answer 3

I think you've misunderstood the problem. Where it says "5 consecutive digits", that only means 5 digits that come one right after another - you're not supposed to check that the values of the digits are consecutive (i.e. each one greater than the last). So throw away all the is_cons logic and just check the product of each 5-digit chunk.

Answer 4

I agree with @tokeland, you probably need to rethink the algo. Also, as @delnan said, range(i,i+4) will give only 4 values. Here's a code that ought to do it

 n = str([whatever number])
 maximum = 0
 for i in range(0,len(n)):
     substr = n[i:i+5]
     product = 1
     for digit in substr:
         product *= int(digit)
         if product > maximum:
              maximum = product
 return maximum

Answer 5

I had worked out a solution that is inline with @tokland's post.

from itertools import islice
from operator import mul

def max_product(num, length=5):
    num_list = map(int, str(num))
    num_slices = (islice(num_list, x, x+length) for x in xrange(0, len(num_list)-length))
    return max(reduce(mul, y) for y in num_slices)

Itertool madness.

from itertools import izip, islice, imap, tee
from operator import mul

def max_product(num, length=5):
    num_lists = enumerate(tee(imap(int, str(num)), length))
    digit_slices = izip(*[islice(num_list, ord, None) for ord, num_list in num_lists])
    return max(reduce(mul, y) for y in digit_slices)

Answer 6

Marijus, I'd recommend you to re-think the algorithm, that's a very weird way of solving the problem. It's much simpler, use the function max, a single iteration (a generator expression, for example), and try to do it without temporal variables. It can be elegantly solved in just 2/3 lines (in fact, you could do it with a single line, but the abstraction of the product function, for example, would be advisable, as you will use it in other Euler problems)

Answer 7

One thing that looks wrong: range(n, m) gives you the numbers from n inclusive to m exclusive, i.e. range(N, N+4) gives you the four next indices (the problem wants five consecutive digits).