Forum Discussion
Utilizing Excel's turing capabilities to create Conway's 'Game of Life'
This is a stab at a solution!
StepHydroλ
= LAMBDA(board, days,
LET(
m, ROWS(board),
n, COLUMNS(board),
// Initial uniform precipitation
initial, SEQUENCE(n, m, 1, 0),
iteration, SEQUENCE(days),
// Increment until precipitation is balanced against outflow from region
solution, REDUCE(initial, iteration,
LAMBDA(step_k, k,
MAKEARRAY(m, n,
LAMBDA(r, c,
IF(AND(r>1, r<m, c>1, c<n), //ignore border regions
LET(
// Calculate water movement day by day
mask, SIGN(TAKE(DROP(board, r-2, c-2), 3, 3) = patch),
neighbourhood, TAKE(DROP(step_k, r-2, c-2), 3, 3),
1 + SUM(mask * neighbourhood)
),
1
)
)
)
)
),
solution - initial
)
);
This function is inspired by the spatial analysis tools provided by ArcGIS. I saw some screen captures and it looked interesting. The demo I've built shows the directional arrows with the help of conditional formatting while the cells contain the integers (e.g. 1, 2, 4, 8, etc.).
// --- Workbook module ---
//Direction vector
direction = {32,64,128,1,2,4,8,16};
//Directional offsets
x = {-1,-1,-1,0,1,1,1,0};
y = {-1,0,1,1,1,0,-1,-1};
//Matrix flow accumulation
Flow.Accumulateλ = LAMBDA(flow_matrix,
LET(
//Create mesh grid coordinates for flow matrix.
r, MGridλ(flow_matrix),
c, MGridλ(flow_matrix, 1),
//Obtain the directional offsets for each cell: Where is the cell pointing?
i, XLOOKUP(flow_matrix, direction, x,0),
j, XLOOKUP(flow_matrix, direction, y,0),
//Obtain the address of these cells - row and col joined with pipe
cells_with_precedents, TOCOL(i + r) & "|" &
TOCOL(j + c),
//Convert row and col matrix to vector - row and col joined with pipe
cells, TOCOL(r) & "|" & TOCOL(c),
//If the cell contains no direction integer, return 1, else check coordinates
//to see if any cells are pointing to it. Count those cells and count
//the cells pointing to those cells, etc.
CountPrecedentsλ, LAMBDA(r₁, c₁,
LET(
active,INDEX(flow_matrix,r₁,c₁),
no_direction,NOT(XOR(active=direction)),
p, IF(no_direction,1,Treeλ(
r₁ & "|" & c₁,
cells_with_precedents,
cells
)),
ROWS(p) - 1
)
),
return, MAP(r, c, CountPrecedentsλ),
return
)
);
//Create a mesh grid for a matrix.
MGridλ =
LAMBDA(matrix,[omit_for_rows_include_for_cols],
LET(
h,ROWS(matrix),
w,COLUMNS(matrix),
i,SEQUENCE(h)*SEQUENCE(,w,1,0),
j,TRANSPOSE(i),
IF(ISOMITTED(omit_for_rows_include_for_cols),i,j)));
//Create a rudimentary 'tree' vector through recursion
//Stack limit: 2,340
Treeλ =
LAMBDA(root,lookup_arr,return_arr,
LET(
next,CHOOSECOLS(root,COLUMNS(root)),
check,IF(XMATCH(lookup_arr,next),return_arr,NA()),
halt,AND(ISNA(next)),
IF(halt,TOCOL(root,2),Treeλ(HSTACK(root,check),lookup_arr,return_arr))))
;The challenge with performance has been with the 18x18 board when Flow.Accumulateλ must contend with an exciting input matrix:
The result:
The results are accurate but the calculation speed is typically 2-5 seconds (Much, much more with the "lazy river" input matrix!).
PeterBartholomew1- It's impressive you arrived a solution based on a picture with no written direction provided. I'm wondering if your solution can be used with this workbook.
I've spent a good amount of time trying variations of the recursive Treeλ but the calculation results are either roughly the same or much worse (Recursive FILTER 'n stack is much slower).
Yes. You seem to have hit on a class of problem (might include map navigation shortest distance puzzles as well as flood fill etc.) with closely related solutions that exploit 2D grid thinking.
Something that I ought to pay attention to is the fact that your descriptions of methods I have implemented are usually better than mine! I guess that's telling me something.
Thank you for sharing this solution! I enjoy stepping through the calculations and incrementing the days to see it at work. This is a good example of taking a larger problem, making it a smaller problem, and solving it elegantly. There are some similarities in this solution with your latest Conway solution. I think matrix flow accumulation is a bit more difficult than Conway because of the directional arrows and needing to be potentially 'aware' of much more than the immediate Moore neighborhood. From what I see you've simplified this by setting up the directional arrows in a way in which they'd point into a given cell and then comparing this against the 8 neighbors. The function works its way through the board with each day.
I can see this approach being used with Flood Fill and other space filling algorithms.
This is what I got from your dataset. The 8 days wasn't how long the program took! The display was chosen to suggest that the 8 iterations might represent the time that rainfall might take to be carried away from the region.