Forum Discussion

Patrick2788's avatar
Patrick2788
Silver Contributor
Mar 22, 2024

djclements 

Your solution is very economical and elegant at the same. It performs very well up to a little over $200 million before it reaches recursion limits.  I think it definitely takes after the greedy algorithim approach and could probably be used to solve similar problems which have multiple solutions.

 

I'll have to check the GROUPBY part later on my home computer. At work I'm without insider so no GROUPBY/PIVOTBY/PERCENTOF for me.

djclements's avatar
djclements
Bronze Contributor
Mar 22, 2024

Patrick2788 Yes, I didn't take into account extremely large amounts, which will hit the recursion limits. To overcome this, and to reduce the number of iterations down to a bare minimum, the formula can be modified to take the maximum number of the maximum denominations each time around:

 

CHANGEDUE:
=LAMBDA(amount_due,denominations,[change_due],
    LET(
        v, IF(ISOMITTED(change_due), LET(m, MAX((denominations<=amount_due)*denominations),
            IF(SEQUENCE(IFERROR(INT(amount_due/m), 1)), m)), change_due),
        a, ROUND(amount_due-SUM(v), 2),
        IF(a>0, LET(m, MAX((denominations<=a)*denominations),
            CHANGEDUE(amount_due, denominations, VSTACK(v, IF(SEQUENCE(INT(a/m)), m)))), v)
    )
)

 

This will work up to the maximum number of rows allowed by SEQUENCE (1,048,576), so it will accept an amount due of up to 100 Billion. 🙂

 

EDIT: after posting the modified formula above, a lightbulb went off as I realized the same logic can simply be applied to the REDUCE function:

 

=LET(
    a, Amt_Due,
    d, SORT(denominations,, -1),
    m, MAX((d<=a)*d),
    IF(m=0, 0, REDUCE(IF(SEQUENCE(INT(a/m)), m), d, LAMBDA(v,n, LET(
        b, a-SUM(v),
        IF(n<=b, VSTACK(v, IF(SEQUENCE(INT(b/n)), n)), v)))))
)

 

So, to generate the final output for the workbook with the images:

 

=LET(
    a, Amt_Due,
    d, SORT(denominations,, -1),
    m, MAX((d<=a)*d),
    due, IF(m=0, 0, REDUCE(IF(SEQUENCE(INT(a/m)), m), d, LAMBDA(v,n, LET(
        b, a-SUM(v),
        IF(n<=b, VSTACK(v, IF(SEQUENCE(INT(b/n)), n)), v))))),
    total, SUM(due),
    IFNA(VSTACK(HSTACK("Amount tendered:", total, IF(total=a, "☑", "X")), WRAPROWS(XLOOKUP(due, denominations, BillPix, ""), 4)), "")
)

 

Cheers!

  • Patrick2788's avatar
    Patrick2788
    Silver Contributor
    Mar 23, 2024

    djclements 

    The greedy algorithm is good for solving this problem because currency denominations tend to be 1/5/10/20/50/100, etc.  The flaws in the greedy are exposed when trying to solve similar problems with more diverse sets of integers.

     

    For example,

    Greedy makes the local optimal choice but the overall optimal choice is 30/30 for the 60 target.  I modified my original Lambda to run a 2nd check where the highest integer is discarded from the matrix.

    =LET(
    keep, XMATCH(target, integers, -1),
    int_vector, SORT(TAKE(integers, keep), , -1),
    largest, MAX(int_vector),
    c, MAX(5, ROUNDUP(target / largest, 0)),
    MatrixA, int_vector * SEQUENCE(, c, 1, 0),
    discard, IF(ROWS(MatrixA) = 1, 0, 1),
    MatrixB, DROP(MatrixA, discard),
    GetInt, LAMBDA(acc, v,
        LET(stack, VSTACK(acc, v), IF(SUM(stack) > target, DROP(stack, -1), stack))
    ),
    a, REDUCE(, MatrixA, GetInt),
    b, REDUCE(, MatrixB, GetInt),
    IF(AND(SUM(b) = target, COUNT(b) < COUNTA(a)), b, a)
)

    I may need to test more target values, but it's held up so far.

    • djclements's avatar
      djclements
      Bronze Contributor
      Mar 23, 2024

      Patrick2788 Good stuff. There was a video shared by Diarmuid Early on YouTube a few months ago called "Recursive LAMBDAs to traverse a tree", where he walked through solving the Peg Game Excel challenge. Seems like the same logic could be applied here... in any case, you might find it interesting.

       

      Just for fun, here's another "Greedy" LAMBDA function based on my previous reply, but with additional options that can output 4 different layouts. The generic syntax is:

       

      =MAKECHANGE(amount, denoms, [images], [list_mode])

       

      • amount - The amount due
      • denoms - The range containing the denomination values
      • images - [optional] The range containing the denomination images (if omitted, the function will return the denomination values by default)
      • list_mode - [optional] 0 or FALSE = summary report grouped by denomination (default); 1 or TRUE = complete list of all denominations

       

      This function is highly efficient and can handle amounts greater that 1 trillion with ease (summary report). When list_mode is set to TRUE, it can only handle amounts up to 100 billion, due to the row limitations of TOCOL. The complete definition is:

       

      MAKECHANGE:
=LAMBDA(amount,denoms,[images],[list_mode],
    LET(
        d, SORT(denoms,, -1),
        m, MAX((d<=amount)*d),
        r, IF(m=0, 0, REDUCE(HSTACK(m, INT(amount/m)), d, LAMBDA(v,n,
            LET(a, ROUND(amount-SUMPRODUCT(TAKE(v,, 1)*TAKE(v,,-1)), 2),
                IF(a<n, v, VSTACK(v, HSTACK(n, INT(a/n)))))))),
        x, TAKE(r,, 1),
        y, TAKE(r,,-1),
        t, SUMPRODUCT(x*y),
        h, EXPAND(HSTACK("Amount Tendered:", t, IF(ROUND(amount-t, 2), "⮽", "☑")), 2,, ""),
        IF(
            list_mode,
            LET(z, IFERROR(TOCOL(IFS(y>=SEQUENCE(, MAX(y)), x), 2), 0), IFNA(VSTACK(h, "Denominations:",
                WRAPROWS(IF(ISOMITTED(images), z, XLOOKUP(z, denoms, images, "")), 4)), "")),
            VSTACK(h, HSTACK("Denominations", "Quantity", "Amount"),
                HSTACK(IF(ISOMITTED(images), x, XLOOKUP(x, denoms, images, "")), y, x*y))
        )
    )
)

       

      Enjoy!

Resources