Oct 00 Challenge
Volume Number: 16
Issue Number: 10
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
What Bills did they Pay?
This month we are helping the accounting department of a small business with a
problem. Our little business is a daily newspaper that survives on its advertising
revenue. Each day they print a newspaper, and each newspaper contains a number of
ads. Whenever the accounting staff can find the time, they send out invoices to their
advertising customers. Sometimes they bill daily, sometimes weekly, sometimes
irregularly during a week or longer period. Most of the customers pay promptly, and
most of them reference the invoice being paid along with their Payment. That's good,
because our little newspaper has only a small accounting staff with no time to
reconcile Payments.
The problem is with a couple of the newspaper's larger customers. These customers
don't always pay promptly, and some of them don't reference the invoice when they
pay. To make things worse, they sometimes pay part of an invoice, or pay multiple
invoices with a simple payment.
Your job is to help sort this all out. The prototype for the code you should write is:
DateTimeRec invoiceDate; [TOKEN:12074] date on which customer was
invoiced */
long invoiceAmount; /* amount customer was
invoiced */
long invoiceNumber; /* reference invoice
number */
DateTimeRec paymentDate; [TOKEN:12074] date payment was submitted
*/
long paymentAmount; /* amount of payment */
long paymentNumber; /* reference payment
number */
typedef struct Reconciliation {
long paymentNumber;
/* reference number of payment being applied */
long invoiceNumber;
/* reference number of invoice to which payment is applied,
zero if duplicate */
long appliedAmount;
/* amount of referenced payment being applied to this
invoice */
long /* number of reconciliation records returned */ ReconcilePayments
(
const Invoice theInvoices[],
/* invoices to reconcile, sorted by increasing date */
const Payment thePayments[],
/* payments to reconcile, sorted by increasing date */
Reconciliation theReconciliation[],
/* return reconciliation here */
long numberOfReconciliationRecords,
/* number of theReconciliation records preallocated */
long *lateDollarDays [TOKEN:12074] see problem description */
);
The objective of this Challenge is to determine which of the Invoices sent to a
problematic customer have been settled by a sequence of Payments. Your
ReconcilePayments routine needs to examine theInvoices and thePayments input
arrays and produce an array of Reconciliation records. Each Reconciliation record
must contain the paymentNumber of the Payment being matched, the invoiceNumber of
the Invoice being matched, and the amount of the Payment being applied to the Invoice.
A given paymentNumber may appear in multiple Reconciliation records, if the
Payment reimbursed more than one Invoice. A given invoiceNumber may also appear
in multiple Reconciliation records, if partial payment was provided by more than one
Payment record.
There are a few things that you can rely on during your reconciliation. Customers
never pay in advance - the payment date is never earlier than the date(s) of the
Invoice(s) being paid. Customers might make a partial payment, but when they do so
they never combine the partial payment with payment for any other Invoice.
Payments might be matched to Invoices in a number of ways, so more than one solution
might exist. We have some constraints, however, that reduce the amount of ambiguity.
Since we are going to use your results to charge interest to our problem customer, and
we want to be as fair as possible, you must apply Payments to the earliest applicable
Invoice. If the Payment matches a single Invoice exactly, or matches the sum of a
number of Invoices exactly, you must apply the Payment to that (those) Invoice(s). If
a Payment exactly matches the balance of an Invoice that has been partially paid by a
previous Payment, you must apply the Payment to the balance of that Invoice, unless
some other rule applies (e.g., an earlier Invoice that is exactly paid by this Payment).
To support assessing an interest charge for our problematic customers, you need to
help the accounting department by calculating how much this customer is in arrears.
Specifically, you need to calculate the number of dollar-days the customer is overdue.
This is the sum, for each unpaid or partially unpaid Invoice, of the unpaid balance of
the Invoice times the number of days the Payment is late. The unpaid amount is simply
the amount remaining after your Reconciliation calculations, and the number of days
late is the difference between the date of the most recent Payment and the date of the
relevant Invoice. The sum of the dollar-days these Payments are late must be returned
in the lateDollarDays parameter of the ReconcilePayments call.
Remember that you cannot apply a Payment to more than one Invoice unless the
Payment exactly totals the original amount of those Invoices - you cannot simply apply
partial Payments to the oldest Invoices to minimize the lateDollarDays value.
The winner will be the solution that correctly calculates the lowest lateDollarDays
result. Among tie values, the entry with the lowest execution time will be the winner.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal.
This Challenge was suggested by Ernst Munter, who adds two Challenge points to his
lead for the suggestion. Thanks, Ernst!
One final point. I've received some letters from people who would like to participate in
the Challenge, but who find the problems too difficult (despite my best efforts to
simplify them), or who find our veteran contestants to be too dominating. I'd really
like to find a way that new contestants could feel comfortable playing, so I'm
considering ways to revise the prize structure or the points system to make that
possible, while still being fair to our regular contestants. If you have any thoughts
along this line, please drop me a suggestion at progchallenge@mactech.com.
Three Months Ago Winner
Congratulations to ... - oops, there is no one whom we can congratulate for winning the
July RAID 5+ Challenge. The problem, you might recall, was to design a disk
input-output system that would survive the loss of two disks in the array. A number of
folks wrote to say that the problem was impossible, which must come as a surprise to
the vendors who marketed solutions to this problem. In any case, this is one of those
rare months when no one submitted a solution.
Is the problem impossible? Imagine a sequence of disks A, B, C, D, and E. Further,
imagine that those disks are striped as follows:
A0 B0 C0 D0 E0
A1 B1 C1 D1 E1
A2 B2 C2 D2 E2
A3 B3 C3 D3 E3
A4 B4 C4 D4 E4
Now, according to the problem statement, the actual data capacity of our array only
requires N-2 of the available N disks. So, to implement protection against the loss of
one disk, we can imagine calculating parity for block (stripe) n across disks A, B, C,
D, and E. Call those parity blocks P1, P2, ..., Then imagine calculating another parity
block, one for each disk. Call those parity blocks PA, PB, ... PE. Then lay those parity
blocks out something like this:
PB B0 C0 D0 P0
A1 B1 C1 P1 PA
A2 B2 P2 PE E2
A3 P3 PD D3 E3
P4 PC C4 D4 E4
Notice that the parity blocks are rotated across the available disks, but that the parity
requires the capacity of only two disks. Note also that there is the equivalent of 3 disks
of information distributed across the 5 physical disks. So what happens when two disks
fail? How do we recover a block? Let's say that disks A and B fail, and that we want to
recover block A1. (Failing these two disks actually represents a worst case, since the
parity block PB for the failed disk B is on the other failed disk.) We have ten missing
blocks of information (6 data blocks and 4 parity blocks), and we have the following
parity equations, with the known elements bolded:
1: B0 + C0 + D0 + P0 = 0
2: A1 + B1 + C1 + P1 = 0
3: A2 + B2 + E2 + P2 = 0
4: A3 + D3 + E3 + P3 = 0
5: C4 + D4 + E4 + P4 = 0
6: A1 + A2 + A3 + PA = 0
7: B0 + B1 + B2 + PB = 0
8: C0 + C1 + C4 + PC = 0
9: D0 + D3 + D4 + PD = 0
10: E2 + E3 + E4 + PE = 0
The first equation allows one to determine B0, the second A1+B1, the third A2+B2,
the fourth A3+P3, the fifth P4, and the eighth PC. The final two equations are all
known quantities and do not help. This leaves us with the following:
1: B0 + C0 + D0 + P0 = 0
2: A1 + B1 + C1 + P1 = 0 (A1 + B1 known)
3: A2 + B2 + E2 + P2 = 0 (A2 + B2 known)
4: A3 + D3 + E3 + P3 = 0 (A3 + P3 known)
5: C4 + D4 + E4 + P4 = 0
6: A1 + A2 + A3 + PA = 0 (A1 + A2 + A3 known)
7: B0 + B1 + B2 + PB = 0 (B1 + B2 + PB known)
8: C0 + C1 + C4 + PC = 0
9: D0 + D3 + D4 + PD = 0
10: E2 + E3 + E4 + PE = 0
This gives us 5 remaining equations and 7 unknowns (A1, A2, A3, B1, B3, P3, and
PB). So, it looks like we are short a couple of equations to arrive at a unique solution.
But we've ignored an additional constraint imposed by parity, that x+x=0. By
enumerating all possible values of these seven remaining unknowns, and determining
which constraints are satisfied by each combination, it turns out that only one
combination of values satisfies all constraints. So it seems to me that a solution ought
to be possible. If you think I've missed something, please let me know and I'll continue
the discussion!
There is also a fair amount of literature on RAID schemes beyond RAID 5. If you're
interested, you might start out at <http://www.pdl.cs.cmu.edu/RAID/RAID.html> and
take it from there.
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 243
2. Saxton, Tom 106
3. Maurer, Sebastian 78
4. Rieken, Willeke 65
5. Boring, Randy 50
6. Shearer, Rob 47
7. Taylor, Jonathan 26
8. Brown, Pat 20
9. Downs, Andrew 12
10. Jones, Dennis 12
11. Day, Mark 10
12. Duga, Brady 10
13. Fazekas, Miklos 10
14. Murphy, ACC 10
15. Selengut, Jared 10
16. Strout, Joe 10
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points