An abomination

projecteuler
#1

This is an abomination, but as a proof of concept it gives a result. Now I just need to refine this code and confirm the result.

Given,

x = "\
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".split(" ")

Iterate over 289, 4X4 grids and find the largest sum of 10 in all. Cache the iterator variables, the row number of the highest value in the temporary list (0-9), and the sum.

u = []
for j in range(17):
  for i in range(0, 340, 20):
    y = []
    y.append([int(z) for z in x[i+j:i+j+4]])
    y.append([int(z) for z in x[i+j+20:i+j+24]])
    y.append([int(z) for z in x[i+j+40:i+j+44]])
    y.append([int(z) for z in x[i+j+60:i+j+64]])
    ten = []
    ten.append(sum(y[0]))
    ten.append(sum(y[1]))
    ten.append(sum(y[2]))
    ten.append(sum(y[3]))
    ten.append(y[0][0] + y[0][1] + y[0][2] + y[0][3])
    ten.append(y[1][0] + y[1][1] + y[1][2] + y[1][3])
    ten.append(y[2][0] + y[2][1] + y[2][2] + y[2][3])
    ten.append(y[3][0] + y[3][1] + y[3][2] + y[3][3])
    ten.append(y[0][0] + y[1][1] + y[2][2] + y[3][3])
    ten.append(y[3][0] + y[2][1] + y[1][2] + y[0][3])
    m = max(ten)
    n = ten.index(m)
    u.append((i,j,n,m))

iterate over list of top sums and find the largest sum

v = []
for k in u:
    v.append(k[3])
    
w = max(v)
r = v.index(w)
i,j,k,a = u[r]
print (i,j,k,a)

Depending the position of largest sum of 10 in all, one of four algorithms is selected

if k < 4:
    p = int(x[i+j+0]) + int(x[i+j+1]) + int(x[i+j+2]) + int(x[i+j+3])
    q = int(x[i+j+0]) * int(x[i+j+1]) * int(x[i+j+2]) * int(x[i+j+3])
elif k < 8:
    p = int(x[i+j+0]) + int(x[i+j+20]) + int(x[i+j+40]) + int(x[i+j+60])
    q = int(x[i+j+0]) * int(x[i+j+20]) * int(x[i+j+40]) * int(x[i+j+60])
elif k == 8:
    p = int(x[i+j+0]) + int(x[i+j+21]) + int(x[i+j+42]) + int(x[i+j+63])
    q = int(x[i+j+0]) * int(x[i+j+21]) * int(x[i+j+42]) * int(x[i+j+63])
elif k == 9:
    p = int(x[i+j+60]) + int(x[i+j+41]) + int(x[i+j+22]) + int(x[i+j+3])
    q = int(x[i+j+60]) * int(x[i+j+41]) * int(x[i+j+22]) * int(x[i+j+3])

print (p,q)
"""
240 3 9 367
367 70600674
"""

Looking for ways to bring about a more logical approach and open to any discussion.

#2

I have no idea... But how long did this take you?!

#3

I did it this afternoon. 2-3 hours. I puzzled over the grid for a few moments each day over the last week or so. I finally got my eureka moment (10 in 4x4) last night and dug into the coding today.

This is what I came up with in hour 1.

u = []
for i in range(0, 340, 20):
    print (x[i]),
    y = []
    y.append([int(z) for z in x[i:i+4]])
    y.append([int(z) for z in x[i+20:i+24]])
    y.append([int(z) for z in x[i+40:i+44]])
    y.append([int(z) for z in x[i+60:i+64]])
    ten = []
    ten.append(sum(y[0]))
    ten.append(sum(y[1]))
    ten.append(sum(y[2]))
    ten.append(sum(y[3]))
    ten.append(y[0][0] + y[0][1] + y[0][2] + y[0][3])
    ten.append(y[1][0] + y[1][1] + y[1][2] + y[1][3])
    ten.append(y[2][0] + y[2][1] + y[2][2] + y[2][3])
    ten.append(y[3][0] + y[3][1] + y[3][2] + y[3][3])
    ten.append(y[0][0] + y[1][1] + y[2][2] + y[3][3])
    ten.append(y[3][0] + y[2][1] + y[1][2] + y[0][3])
    m = max(ten)
    n = ten.index(m)
    u.append((i,m,n))

    #break

v = []
for k in u:
    v.append(k[1])
    
w = max(v)
k = v.index(w)
a,b,c = u[k]
print (a,b,c)
p = int(x[a+60]) + int(x[a+41]) + int(x[a+22]) + int(x[a+3])
print (p)
q = int(x[a+60]) * int(x[a+41]) * int(x[a+22]) * int(x[a+3])
print (q)

It is just the first 'column'. I used addition in the elimination phase since it would (seems to me) be quicker to add than multiply. Once I have the max values of the 289 'boxes' it just gets boiled down from there.

The rest of the code came together pretty easily in hour 2.

#4

I've been on holiday in Mexico for 1 week so my brain can't even begin to understand anything you're saying :smile:

#5

Examine the grid. There are 17 columns that can be the first column in a 4 by 4 overlay grid. Likewise, there are 17 rows that can be the first row. 17 squared is 289. Once I had that number, I knew that we would be iterating over 289 mini-grids. This is one way to be sure that all the diagonals have been examined.

Today, armed with having slept on the problem one more night, the code pretty much flowed out, bit by bit. Testing was fairly easy since I could predict what should result.

It's still not done, but it can be a model to build from. There is a lot of overlap with regard to the the columns.

[  ] [  ] [  ] [  ]
[  ] [  ] [  ] [  ]
[  ] [  ] [  ] [  ]
[  ] [  ] [  ] [  ]

     [  ] [  ] [  ] [  ]
     [  ] [  ] [  ] [  ]
     [  ] [  ] [  ] [  ]
     [  ] [  ] [  ] [  ]

The trick now will be to cache three of the four column sums so they don't have to added repeatedly 16 more times than necessary.

This is the segment that sums the columns of the mini-grid.

    ten.append(y[0][0] + y[0][1] + y[0][2] + y[0][3])
    ten.append(y[1][0] + y[1][1] + y[1][2] + y[1][3])
    ten.append(y[2][0] + y[2][1] + y[2][2] + y[2][3])
    ten.append(y[3][0] + y[3][1] + y[3][2] + y[3][3])
#6

A small efficiency boost...

x = [int(k) for k in x]

289 calls to int() instead of 2300.

    y.append([z for z in x[i+j:i+j+4]])
    y.append([z for z in x[i+j+20:i+j+24]])
    y.append([z for z in x[i+j+40:i+j+44]])
    y.append([z for z in x[i+j+60:i+j+64]])

if k < 4:
    p = x[i+j+0] + x[i+j+1] + x[i+j+2] + x[i+j+3]
    q = x[i+j+0] * x[i+j+1] * x[i+j+2] * x[i+j+3]
elif k < 8:
    p = x[i+j+0] + x[i+j+20] + x[i+j+40] + x[i+j+60]
    q = x[i+j+0] * x[i+j+20] * x[i+j+40] * x[i+j+60]
elif k == 8:
    p = x[i+j+0] + x[i+j+21] + x[i+j+42] + x[i+j+63]
    q = x[i+j+0] * x[i+j+21] * x[i+j+42] * x[i+j+63]
elif k == 9:
    p = x[i+j+60] + x[i+j+41] + x[i+j+22] + x[i+j+3]
    q = x[i+j+60] * x[i+j+41] * x[i+j+22] * x[i+j+3]
#7

Euler #11?

A bit of quick math says it's just brute force, so I loop through every position and grab 4 numbers from each direction, don't care about duplicates.

(289 positions, 8 directions each, 4 numbers each => order of 10k iterations)
Execution time is linear to the amount of numbers in the grid, a smarter algorithm wouldn't make a significant improvement as long as the grid has to be read into memory each time.

Usage:
$ ./euler11.py < grid.txt
(or just paste the grid in since it reads from stdin)

#!/usr/bin/env python3

"""
Brute-force solution to project euler #11
"""

import sys
from itertools import product
from functools import reduce
from operator import mul

# read grid from stdin
GRID = [[int(n) for n in line.split(' ')]
        for line in map(str.strip, sys.stdin.readlines()) if line]


def get_number_groups(num_nums):
    """
    Get each group of numbers.
    """
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1),
                  (1, 0), (1, 1)]
    # iterate through each location on the GRID
    for start_x, start_y in product(range(len(GRID[0])), range(len(GRID))):
        # iterate through directions (up, down, left, right, diagonals)
        for xdir, ydir in directions:
            # make sure that direction stays within the board
            if start_x + xdir * (num_nums-1) not in range(len(GRID[0])) \
               or start_y + ydir * (num_nums-1) not in range(len(GRID)):
                continue

            yield [GRID[start_x + xdir * offset][start_y + ydir * offset]
                   for offset in range(num_nums)]


def score(nums):
    """
    Compute product of an iterable.
    """
    return reduce(mul, nums)


print(max(map(score, get_number_groups(4))))
#8

Cool solution. Would've taken me forever to come up with it.

My first thought was along these lines. Admittedly spent too much time fretting over duplicates. Now I see it wouldn't matter. There is only one maximum product. Was bent on knowing the position of the top left corner of the mini-grid where the maximum product is located..

#9

By happy accident, de-duping my solution can be accomplished by removing half the directions from the list of directions, as for each 4-numbers-group there is another starting at the other end-point going in the opposite direction. The number of operations would be roughly cut in half as well.

Can you explain what yours is doing? I can't quite follow along in it and there's something arcane with sums going on.

Mine's doing nothing fancy whatsoever. It just collects all possible 4 numbers, then finds the largest product. It's as straight-forward as it gets. I'm toying around a bit with stuff like map, reduce, product but they all have very plain imperative counter-parts.

I think you're mostly just hard-coding far too many values and behaviour that can be described as data (directions)

I had solved this before, 5 years ago or so, probably in C#. I searched for occurrences of euler but couldn't find it. Would have been interesting to see how I did it back then.

#10

You're.. selecting each 4x4, and checking each horizontal, vertical and diagonal? That's a bit of duplication due to overlap, should add up to roughly one duplicate of each group, same as what I have.

What are the sums for? Same as finding the locations of the 4x4's and considering a 4x4 grid a thing at all?

#11

Exactly. It was a finite solution I could wrap my tired old head around.

The sums are my way of verifying the final result. Now that it's running, they can be removed.

Inside the scanning phase I used sums and max() for what I deemed would be a faster algo than multiplying. The largest sum is going to have the largest product. I definitely knew going in that this was a clunky approach. My initial goal was to create a road map. Now I can focus on logic.

x = [int(k) for k in x]
u = []
for j in range(17):
  for i in range(0, 340, 20):
    y = []
    ten = []
    for k in range(0, 80, 20):
        y.append([z for z in x[i+j+k:i+j+k+4]])
    for k in range(4):
        ten.append(sum(y[k]))
    for k in range(4):
        s = 0
        for z in range(4):
            s += y[k][z]
        ten.append(s)
    ten.append(y[0][0] + y[1][1] + y[2][2] + y[3][3])
    ten.append(y[3][0] + y[2][1] + y[1][2] + y[0][3])
    m = max(ten)
    n = ten.index(m)
    u.append((i,j,n,m))
    
v = []
for k in u:
    v.append(k[3])
    
w = max(v)
r = v.index(w)
i,j,k,a = u[r]
print (i,j,k,a)
if k < 4:
    q = x[i+j+0] * x[i+j+1] * x[i+j+2] * x[i+j+3]
elif k < 8:
    q = x[i+j+0] * x[i+j+20] * x[i+j+40] * x[i+j+60]
elif k == 8:
    q = x[i+j+0] * x[i+j+21] * x[i+j+42] * x[i+j+63]
elif k == 9:
    q = x[i+j+60] * x[i+j+41] * x[i+j+22] * x[i+j+3]

print (q)
#12

That isn't true for all cases

00 00 00 05 sum 5, product 0
01 01 01 01 sum 4, product 1

Even if it was, it would definitely be a premature optimization

#13

Darn zero! And there are some in the data. Thanks for pointing that out. Back to the drawing board.

    #product of rows
    for k in range(4):
        p = 1
        for z in range(4):
            p *= y[k][z]
        ten.append(p)
    #product of columns
    for k in range(4):
        p = 0
        for z in range(4):
            p *= y[z][k]
        ten.append(p)
    ten.append(y[0][0] * y[1][1] * y[2][2] * y[3][3])
    ten.append(y[3][0] * y[2][1] * y[1][2] * y[0][3])
#14

Zero doesn't need to be involved!

01 01 01 99 sum 102, product 99
10 10 10 10 sum 40, product 10000

If you really are going back to the drawing board, then avoid all those hard-coded values and one-letter names, you had well over ten of them, can't keep track of them all.

#15

Holy cow. Amazing how anal my brain is becoming. I got stuck on that idea and rolled with it, willy-nilly. Sure glad I asked for criticism. Thanks for pitching in!

#16

So the four directions you would keep...

directions = [(-1, -1), (0, 1), (1, 0), (1, 1)]

?

Is offset a built-in? I don't see where that variable is defined.

#17

I multiply the direction to get the nth number in that direction. The name isn't super accurate, distance would be more so, and distance * direction would be the offset from the starting point.

#18

Man do I need new glasses. Right there for all to see.