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.
I downloaded your workflow to learn your smart method but I faced the issue in version 2023.2
I think you use Record ID tool to assign number 'X', probably with grouping option on 'Y'.
But that option is not available in 2023.2 then it just created a single sequence of numbers.
I used Tile tool as a workaround and found your approach is smart!
String Coding for the win! (+ Tool Golf)
Again, the MVT (Most Valuable Tool) is the Generate Rows Tool! Our string parameters include the Row/Column of the current cell, and then the maximum of the four directional products (Right, Down, Up+Right, Down+Right). There is a slight help from the GetPart() function, because if the index is greater than the number of delimited parts, this function returns null, which converts to 0 for the product. Negative indices require more complex logic to account for, but it's not too bad. GetPart() is a very powerful function for this use case, as it allows us to precisely isolate each of the four elements for each group for each direction starting from a given cell.
Fun problem with a very satisfying solution. This is very reminiscent of last year's AoC problem. I love seeing other's solutions.
It's a lot of copying and pasting, but here is the formula tool with the abacus functions.
This reminded me very much of AoC (Advent of Code). For past AoC challenges, I would try to work with the coordinates, like (4,4) to indicate it's the 4th row, 4th column. What I've learned with AoC is to try to work with a unique ID, so (4,4) would be something like 34 if it's 4th row, 4th column. That makes it easier for tracking without having to worry about (4,4)
I did a macro to find adjacent groups of 4 as rows, columns, diagonals one way, diagonals the other way. I tried to make it dynamic so I could specify groups of x, instead of just 4, but eventually left it as just 4 and will figure the dynamic bit out later (ideally before Dec)
From there, I just found the values within each group of 4 and did some maths. Workflow ran in 0.4 seconds
Macro:
