|
October 2000 Programmer's Challenge
What Bills did they Pay?
Mail solutions to:
progchallenge@mactech.com
Extended Due Date: 11:59pm ET, Sunday, 8 October 2000
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:
#include "OSUtils.h"
typedef struct Invoice {
DateTimeRec invoiceDate; /* date on which customer was invoiced */
long invoiceAmount; /* amount customer was invoiced */
long invoiceNumber; /* reference invoice number */
} Invoice;
typedef struct Payment {
DateTimeRec paymentDate; /* date payment was submitted */
long paymentAmount; /* amount of payment */
long paymentNumber; /* reference payment number */
} Payment;
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 */
} Reconciliation;
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 /* 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.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
| 
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
