General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 11 – Largest Product in a Grid
My workflow:
Answer: 70600674
Last Week's Favourite Solution:
Seeing all the different adaptations from the problem 7 macros was great! However, @gawa not only provided two solution, but also explained a shortcut to finding prime number. By considering numbers which follow the formula 6N + or - 1, we can rule out so many non-prime numbers, without even needing to test them. If you want to see the explanation behind this formula, look back at the first page of last weeks solutions, or click here.
Definitions:
- Commutativity – This is a mathematical property where changing the order of an operation does not change the result. i.e
Multiplication is commutative as 4 x 5 = 5 x 4
Division is NOT commutative as 5/4 != 4/5
Mathematical Theory:
This is another problem with less theory than most so far; however, we have still tried to explain our thought process.
Whenever I see a problem like this, I picture it as a coordinate grid. On that grid, we can place straight lines going in 4 different directions.
- Horizontal
- Vertical
- Diagonal (Top Left to Bottom Right)
- Diagonal (Bottom Left to Top Right)
Viewing the problem like this allows us to consider the equations for these types of lines, which in turn helps with the groupings.
For example, with the horizontal lines, we know that only the “x” value, or in this case, the “Column ID” changes. We can therefore isolate a particular row by grouping on the “Row ID”. But how do we turn these into groups of 4?
Like states, in this example, we already know that only the column ID changes, so let's focus on that. We know that each number can at most appear in 4 different groups upon a particular line. I.e. the number 97 in the below extract can be in the following groups:
Extract: 08 02 22 97 38 15 00
Groups:
- 08 02 22 97
- 02 22 97 38
- 22 97 38 15
- 97 38 15 00
We could choose to label these groups based on the position of their final number.
Groups:
- 08 02 22 97 ( Group 4, as 97 is the 4th number in the extract)
- 02 22 97 38 ( Group 5, as 38 is the 5th number in the extract)
- 22 97 38 15 (Group 6)
- 97 38 15 00 (Group 7)
For the number 97, its position in the extract will always stay the same (it’s the 4th number, so it has a Column ID of 4); however, its position within the groups changes. It could be the 1st, 2nd, 3rd or 4th number in the group.
What if we sum both the position in the extract and the position in the group? In the case of 97 we get:
- 4 + 1 = 5
- 4 + 2 = 6
- 4 + 3 = 7
- 4 + 4 = 8
Subtracting one from each of these, we end up with 4, 5, 6, 7. Hopefully, this looks familiar, as these are our group numbers from earlier.
If we apply this same logic to all the numbers in our extract, they will appear in the following groups:
- 08 – Groups: 1, 2, 3, 4
- 02 – Groups: 2, 3, 4, 5
- 22 – Groups: 3, 4, 5, 6
- 97 – Groups: 4, 5, 6, 7
- 38 – Groups: 5, 6, 7, 8
- 15 – Groups: 6, 7, 8, 9
- 00 – Groups: 7, 8, 9, 10
From this point, we can simply find the product for each group (and count the number of digits to make sure they are of length 4 and not less).
The same process as above can be easily adapted for the vertical lines. But there is one small tweak when looking at the diagonals. In the case of diagonals, we can still find a “group number” but we will need to consider both the Row ID and Column ID.
For the Bottom Left to Top Right diagonals, we need to add the “group positions” to both the Row ID and Column ID.
For the Top Left to Bottom Right diagonals, we need to add the “group position” to the Column ID but subtract it from the Row ID. Together, these values then form our groups. You can either leave them in separate cells or combine both numbers into the same cell. (We created a 4 digit group number with the Column ID as the first and second digit and the Row ID as the third and fourth digit).
Method:
1) As I visualised this problem like a coordinate grid, the first thing I did was split everything into Rows and Columns so there was one number per cell.
2) Then we pivoted the data so we had all numbers in one column, with the coordinates alongside them.
3) Next, we created 4 separate records for each number - one for each “group position” it could take. (The screenshot is from the horizontal lines).
4) Now for the tricky part. Here, we created the groups for each of the 4 lines we mentioned earlier.
5) For each of the 4 lines, we then found the product per group, and filtered to those groups with 4 values. (As multiplication is commutative, we didn’t need to worry about the order, we could just group by and multiply)
6) After that, it's simply a case of unioning the records back together, sorting the results, and sampling the top answer.
7) Submit your answer to the Project Euler Website!
Summary:
Beginning with creating the coordinate grid, then taking each of the 4 lines individually, we were able to quickly group numbers together correctly, helping us arrive at a solution.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
