2
\$\begingroup\$

Question:

Given a 20x20 Grid of integers, find the greatest product of four adjacent numbers. (up, down, diagonal, reverse diagonal).

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

Example, above 87 x 97 x 94 x 89 = 70600674 

I wrote a procedural approach to solve the problem. It solved the problem and gave out the correct answer, just that I was not very satisfied with the clumsiness of the code. My intention was to make this piece of code more dynamic so that 1) grids of various sizes (e.g. 30x30), and length of the candidates (e.g. instead of 4, make it product of 5 adjacent numbers) can be solved by this code.

1) So first thing you will notice is I write loops like this:

width = data[0].length       # length of first row of array
height = data.length         # length of array (height)
length = 4                   # 4 adjacent numbers

(0..height-1).each do |i|
    (0..width-length).each do |j|
        numbers_array = []
        (0..length-1).each do |l|
            # # Do things here
        end
     end
end

which I personally think is pretty unreadable. I wish there is a way so I don't have to write all these loops.


2) For the strategies, I came up with the following code which I think is pretty neat, but since there are four different strategies (i.e. up, down, diagonal /, and diagonal ). I had to write this code four times, which violates the DRY principle. So I wonder how I can improve this logic by using a more elegant approach

numbers_array << data[i][j+l].to_i # i, j, l are iterations, where l represent the length of the adjacent numbers, while i, j are positions in the grid.
product = numbers_array.inject(:*)

numbers_array << data[i+l][j].to_i # vertical
numbers_array << data[i+l][j+l].to_i # diagonal \
numbers_array << data[i-l][j+l].to_i # diagaonal /

May be I should encapsulate the four strategies in a def and call it accordingly. Any thoughts?


Below is the complete code for reference. :)

def load_data
    data = []
    File.readlines('11-resource').each_with_index do |line|
        data << line.delete("\n").split(/ /)
    end
    data
end

data = load_data
width = data[0].length
height = data.length
length = 4
max_product = [0,0,0,'']

# Horizontal
(0..height-1).each do |i|
    (0..width-length).each do |j|
        numbers_array = []
        (0..length-1).each do |l|
            numbers_array << data[i][j+l].to_i
        end
        product = numbers_array.inject(:*)
        puts "Horizontal:[#{i}, #{j}] - #{numbers_array * " x "} = #{product}"
        max_product[1] = product > max_product[0] ? i : max_product[1]
        max_product[2] = product > max_product[0] ? j : max_product[2]
        max_product[3] = product > max_product[0] ? 'Horizontal' : max_product[3]
        max_product[0] = product > max_product[0] ? product : max_product[0]
    end
end

# Vertical
(0..height-length).each do |i|
    (0..width-1).each do |j|
        numbers_array = []
        (0..length-1).each do |l|
            numbers_array << data[i+l][j].to_i # want to make this into a def but since data[i][j] is complicated to put into a def.
        end
        product = numbers_array.inject(:*)
        puts "Vertical:[#{i}, #{j}] - #{numbers_array * " x "} = #{product}"
        max_product[1] = product > max_product[0] ? i : max_product[1]
        max_product[2] = product > max_product[0] ? j : max_product[2]
        max_product[3] = product > max_product[0] ? 'Vertical' : max_product[3]
        max_product[0] = product > max_product[0] ? product : max_product[0]
    end
end

# Diagonal \
(0..height-length).each do |i|
    (0..width-length).each do |j|
        numbers_array = []
        (0..length-1).each do |l|
            numbers_array << data[i+l][j+l].to_i
        end
        product = numbers_array.inject(:*)
        puts "Diagonal \:[#{i}, #{j}] - #{numbers_array * " x "} = #{product}"
        max_product[1] = product > max_product[0] ? i : max_product[1]
        max_product[2] = product > max_product[0] ? j : max_product[2]
        max_product[3] = product > max_product[0] ? 'Diagonal \\' : max_product[3]
        max_product[0] = product > max_product[0] ? product : max_product[0]
    end
end

# Diagonal /
(length-1..height-1).each do |i|
    (0..width-length).each do |j|
        numbers_array = []
        (0..length-1).each do |l|
            numbers_array << data[i-l][j+l].to_i
        end
        product = numbers_array.inject(:*)
        puts "Diagonal \:[#{i}, #{j}] - #{numbers_array * " x "} = #{product}"
        max_product[1] = product > max_product[0] ? i : max_product[1]
        max_product[1] = product > max_product[0] ? i : max_product[1]
        max_product[2] = product > max_product[0] ? j : max_product[2]
        max_product[3] = product > max_product[0] ? 'Diagonal /' : max_product[3]
        max_product[0] = product > max_product[0] ? product : max_product[0]
    end 
end

puts max_product.inspect

So you can easily calculate additional answers by simply changing the length now~

  • For length 5, max product is: Diagonal :[15, 3] - 87 x 97 x 94 x 89 x 47 = 3318231678
  • For length 6, max product is: Horizontal:[17, 10] - 99 x 69 x 82 x 67 x 59 x 85 = 188210512710

  • For length 7, max product is: Horizontal:[17, 10] - 99 x 69 x 82 x 67 x 59 x 85 x 74 = 13927577940540 ...etc

\$\endgroup\$
  • \$\begingroup\$ One minor improvement I saw now is to use 0...height instead of 0..height-1 \$\endgroup\$ – Chris Yeung Apr 4 '15 at 13:45
2
\$\begingroup\$

Firstly, to load the data, I'd do this:

grid = File.readlines("some-file").map do |line|
  line.chomp.split.map(&:to_i)
end

that gets you a grid of integers with minimum hassle.

For the horizontal products there's each_cons (each consecutive), reduce (aka inject), and max to help you (all part of the Enumerable module). Using them, finding the maximum horizontal product is simple:

max_horizontal = grid.map do |row|
  row.each_cons(4).map { |group| group.reduce(&:*) }.max
end.max

Now, to find the vertical maximum, we only need to transpose the grid and do the exact same thing. Thankfully, there's Array#transpose which does exactly what it says on the tin. So we can wrap the above in a method, and call it once with the plain grid, and once with the transposed grid to get the horizontal and vertical maxima:

def max_linear_product(grid)
  grid.map do |row|
    row.each_cons(4).map { |group| group.reduce(&:*) }.max
  end.max
end

max_horizontal = max_linear_product(grid)
max_vertical = max_linear_product(grid.transpose)

You can of course add an extra argument to the method instead of the hard-coded 4.

The diagonals require a bit more fiddling. But again, we can use one method, and just feed it two different versions of the grid to find the two different diagonal maxima.

Now, we know we can skip a few rows and columns, since we need 4 numbers for each product. So we won't gain anything by starting our diagonal grouping in the last 3 rows, or in the last three columns of each row.

I came up with a method like this (which isn't too pretty):

def max_diagonal_product(grid)
  grid[0..-4].each_with_index.flat_map do |row, y|
    row[0..-4].each_with_index.map do |_, x|
      4.times.reduce(1) { |product, i| product * grid[y + i][x + i] }
    end
  end.max
end

(Again, the hard-coded 4 can be replaced with an argument.)

To find the top-left to bottom-right diagonal maximum, we just feed the plain grid to that method:

max_diagonal = max_diagonal_product(grid)

To find the reverse diagonal's maximum, we just need to feed it the grid with each row reversed:

max_reverse_diagonal = max_diagonal_product(grid.map(&:reverse))

Finally, to find the maximum of all of those, you can of course just do:

[max_horizontal, max_vertical, max_diagonal, max_reverse_diagonal].max

All together:

def max_linear_product(grid)
  grid.map do |row|
    row.each_cons(4).map { |group| group.reduce(&:*) }.max
  end.max
end

def max_diagonal_product(grid)
  grid[0..-4].each_with_index.flat_map do |row, y|
    row[0..-4].each_with_index.map do |_, x|
      4.times.reduce(1) { |product, i| product * grid[y + i][x + i] }
    end
  end.max
end

grid = File.readlines("some-file").map do |line|
  line.chomp.split.map(&:to_i)
end

max_horizontal = max_linear_product(grid)
max_vertical = max_linear_product(grid.transpose)
max_diagonal = max_diagonal_product(grid)
max_reverse_diagonal = max_diagonal_product(grid.map(&:reverse))

solution = [max_horizontal, max_vertical, max_diagonal, max_reverse_diagonal].max

At least, that's one way to do it.

Another, more low-level way, could be to run through the grid once, getting horizontal, vertical and diagonal groups all in one go:

groups = grid.each_with_index.flat_map do |row, y|
  row[0..-4].each_with_index.flat_map do |_, x|
    groups = []
    groups << 4.times.map { |i| grid[y][x + i] } # horizontal
    if y <= grid.count - 4
      groups << 4.times.map { |i| grid[y + i][x] } # vertical
      groups << 4.times.map { |i| grid[y + i][x + i] } # diagonal top-left/bottom-right
      groups << 4.times.map { |i| grid[y + i][x + 3 - i] } # opposite diagonal
    end
    groups
  end
end

maximum = groups.map { |group| group.reduce(&:*) }.max
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.