Algorithm challenge

Post Reply New Topic

I had to solve this recently--enjoy!

You have a number of outstanding checks, some for identical amounts and find out your balance has gone down less than the sum of your checks. You will be given the target amount and a list of check amounts (with a multiplier if more than one).

In this example, the top line is the sum of a various items beneath it including four checks for $32.53.

Are you asking us to do your homework for you?

Riiiiiight ...

After reading the target amount off the first line, the script builds a table with the candidate amounts, multipliers, and a try that is initially zero. Items w/o a multiplier are given 1, but 1 will be added to each multiplier before stored in the table. How ever many times an item can appear, it can also appear not at all or zero times.

When all items have been stored in a table, the product of all multipliers is found and will be the terminal count for the next loop.

For each iteration in the next loop, each will have a "do until" loop where carry is zero. One is added to the "try" of the first item and, if it is equal to the multiplier for that item, try is zeroed, carry=1, and a subscript is incremented to go through the loop on the next column. Still in that loop, the sum of each item times its "try" is found.

A second table is built containing the absolute value of the difference between that sum and the target, its sign, and a text field describing what was done.

Coming back from a sort, the first few lines are displayed and the tries with the smallest differences between that sum and the target are displayed first.

My solution is here. Change all dollar signs to less than, all percents to greater than, then save it as a file ending in .html.