Forum Discussion

Patrick2788's avatar
Patrick2788
Silver Contributor
Apr 10, 2025

This is a good example of how thunks can be efficient.  The timings are roughly each 250 generations = 2.5 seconds. This is impressive considering how much is involved in the calculations.

My only regret with my solution is the reliance on INDEX (and subsequently, FILTER).  The performance is decent but I'd rather not have to deal with discarding 0s so INDEX doesn't go haywire.

One of things I've been experimenting with is a function that can selectively traverse a matrix. The idea is the function would be deployed while mapping or using MAKEARRAY on a matrix.  For each given element in the matrix, the function would traverse up, down, right, left, etc.  This is all part of a larger project in attempting to solve Matrix Flow Accumulation - something Excel probably has no business in doing because there are programs that do it, but it is certainly interesting!

PeterBartholomew1's avatar
PeterBartholomew1
Silver Contributor
Apr 10, 2025

If I was allowed to write a Fast Fourier Transform algorithm in Excel, I don't see why you shouldn't play with Matrix Flow!

  • Patrick2788's avatar
    Patrick2788
    Silver Contributor
    Apr 20, 2025

    I've been working on Matrix Flow Accumulation on and off and have a rough draft solution.  The most difficult part was correctly identifying the type of problem it presents and developing a function to trace the flow for a given cell in the grid.  The second challenge is finding legitimate examples as some of the grids I've encountered contain mistakes in the Flow direction matrix (Making the Flow accumulation totals incorrect). On to testing and refinement!

     

    • PeterBartholomew1's avatar
      PeterBartholomew1
      Silver Contributor
      Apr 22, 2025

      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
    )
);

       

      • Patrick2788's avatar
        Patrick2788
        Silver Contributor
        Apr 24, 2025

        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). 

Resources