Learning To Code

Join me as I take the plunge!

Saturday Morning Ruby

I’ve been immersed in Rails for a few weeks now. It’s been great, but it has come at the expense of pushing ahead and learning more about Ruby. I decided to go back and do another Project Euler problem this week, but it was a bit too easy. Today I took on a more challenging problem, and spent all morning getting it to work.

Project Euler Problem 11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

In the 2020 grid below, four numbers along a diagonal line have been marked in red.

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
The product of these numbers is 26  63  78  14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 2020 grid?

1. Take grid and turn it into an array

I obviously needed to be able to access each value, and was pretty sure they had to be integers as I had plans to perform mathematical operations on them later on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

grid = "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"

grid = grid.split(' ').collect { |string| string.to_i }

2. Figure out mathematical plan

Rereading the instructions I determined there were four ways (horizontal, vertical, diagonal-right and diagonal-left) that combinations of numbers would be possible. Instead of trying to do this all at once and make one huge class with lots of sub methods, I decided that I would try each method one-by-one and if it produced the correct answer, I would stop.

3. Horizontal Combinations

This was the easiest, so I did it first.

First I tried to find the product of the first 4 numbers.

1
2

sum = grid[0..3].reduce{ |product, n| product * n }
puts sum

Once I was able to do this for the first 4 numbers, I tried to see if I could do this for any adjacent combiantion of 4 numbers in the first row

1
2
3
4
5
6
7
8
9

start = 0
finish = 3

until finish > 19 do
  sum = grid[start..finish].reduce{ |product, n| product * n }
  puts sum
  start += 1
  finish += 1
end

Then I figured out which product of all of these combinations was the greatest in value. As I went further down the rabbit hole I realized it would be helpful to encapsulate this logic into a method, which I did.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def find_largest_product(array)
  start = 0
  finish = 3
  greatest = 0

  until finish > 19 || finish > array.size do
  # I added the '|| finish > array.size' on the line above once I got to the diagonal lines and had to deal with arrays of varying size.
    sum = array[start..finish].reduce{ |product, n| product * n }
    greatest = sum if sum > greatest
    start += 1
    finish += 1
  end
  greatest
end

At this point I decided to split my array into nested arrays, with each nested array containing a row of 20 numbers.

1
2
3
4

until grid[0].is_a? Array
  row = grid.shift(20)
  grid << row
end

Once I had a nested array and a method to find the largest product, I then put the largest product of each row into a new array called answer, and then called the max method on that array to produce (what I hoped would be) the answer to the problem.

1
2
3
4
5

answer = []
  grid.each do |array|
    answer << find_largest_product(array)
  end
puts answer.max

Unfortunately, this was not the answer, and I had to move on and see if the solution would be a vertical combination.

4. Vertical Combinations

I now needed to make arrays of the columns from my origonal grid. I realized that I could just ‘shift’ off the first element of each of the row arrays I had previously made, and combine them into a new nested array which contained all the columns of data.

1
2
3
4
5
6
7
8
9

vertical = []
20.times do
  column = []
  grid.each do |row|
    item = row.shift
    column << item
  end
  vertical << column
end

Once I had this new array, I then see what the largest product of 4 adjacet vertical numbers were. I essentially reused the code I did when I did this for the rows of data, just replacing what array I was using. Looking back I could have put this into it’s own method too.

1
2
3
4
5

  answers = []
    vertical.each do |array|
      answers << find_largest_product(array)
    end
   puts answers.max

As with the horizontal combinations, this did not produce the correct answer. I knew that I was now venturing into more difficult territory with diagonals, but I was so invested in figuring out this problem that I was actually pretty excited.

5. Diagonal-Right Combinations

I tried to figure out what I needed to do in my head, but it wasn’t working. I went into excel and started visualizing it all, which was tremendously helpful.

I ended up determing that what I would do is make arrays of all the diagonals that went down and to the right. The green diagonals on the bottom-left and top-right represent the first and last array, since arrays beyond them would be less than 4 numbers in size. I figured if I started at the bottom-left most array and worked my way up to the top right most array, I would get all the diagonals in one fell swoop.

After some trial-and-error I was able to come up with a way to get all the numbers from a single diagonal line into an array, and then enapsulated it in a method called make_diagonal_array

1
2
3
4
5
6
7
8
9

def make_diagonal_array(horizontal_array, vertical, horizontal)
  diagonal_array = []
  until vertical > 19 || horizontal > 19 do
    diagonal_array << horizontal_array[vertical][horizontal]
    vertical += 1
    horizontal += 1
  end
  diagonal_array
end

Now that I could get a single diagonal array, I had to get all of them. I made a new array called diagonal, and shoveled each diagonal line onto it, again going from the bottom left most diagonal line to the top right most diagonal line. I used some of the same local varaible names that I used in the make_diagonal_array, which I call in the until loop. While this is a bit confusing, it was the least confusing way I could come up with at the time.

1
2
3
4
5
6
7
8
9
10
11
12

diagonal = []
vertical = 16
horizontal = 0

until vertical == 0 && horizontal > 16 do
  diagonal << make_diagonal_array(grid, vertical, horizontal)
  if vertical > 0
    vertical -= 1
  else
    horizontal += 1
  end
end

Hoping this would finally yield me the correct answer, I used the same code as I had done in the last two attempts.

1
2
3
4
5

answer = []
  diagonal.each do |array|
    answer << find_largest_product(array)
  end
puts answer.max

I suppose this was just my lucky day, since this did not produce the right answer. I then went on to try to final set of combiations: diagonal-left.

6. Diagonal-Left

For this step all I had to do was modify the code I made for diagonal-right. This time I would start at the top-left most diagonal and go down to the bottom-right most diagonal. This was suprisingly hard to wrap my head around, but I eventually did with enough fiddling.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def make_diagonal_array(horizontal_array, vertical, horizontal)
  diagonal_array = []
  until vertical > 19 || horizontal < 0 do
    diagonal_array << horizontal_array[vertical][horizontal]
    vertical += 1
    horizontal -= 1
  end
  diagonal_array
end

diagonal = []
vertical = 0
horizontal = 3

until vertical > 16 && horizontal == 19 do
diagonal << make_diagonal_array(grid, vertical, horizontal)
  if horizontal <= 18
    horizontal += 1
  else
    vertical += 1
  end
end

answer = []
  diagonal.each do |array|
    answer << find_largest_product(array)
  end
puts answer.max

FINALLY!! I got the answer (it’s 70,600,674). This was quite a lot of work, but well worth it. If I were to do some serious refactoring, I could put this all into a class, further encapsulate these methods, and make it all work nicely as one program instead of 4 separate attempts. Perhaps another time though - I need to enjoy the rest of my Saturday!