TweetFollow Us on Twitter

Oct 00 Challenge

Volume Number: 16 (2000)
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:

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

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
 
AAPL
$102.47
Apple Inc.
+2.71
MSFT
$44.88
Microsoft Corpora
+0.80
GOOG
$526.54
Google Inc.
+5.70

MacTech Search:
Community Search:

Software Updates via MacUpdate

RapidWeaver 6.0 - Create template-based...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
NTFS 12.0.39 - Provides full read and wr...
Paragon NTFS breaks down the barriers between Windows and OS X. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS, providing full read and write access to... Read more
RestoreMeNot 2.0.3 - Disable window rest...
RestoreMeNot provides a simple way to disable the window restoration for individual applications so that you can fine-tune this behavior to suit your needs. Please note that RestoreMeNot is designed... Read more
Macgo Blu-ray Player 2.10.9.1750 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple iOS 8.1 - The latest version of Ap...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PDFKey Pro 4.0.2 - Edit and print passwo...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Yasu 2.9.1 - System maintenance app; per...
Yasu was originally created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks... Read more
Hazel 3.3 - Create rules for organizing...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a... Read more
Autopano Giga 3.7 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more

Latest Forum Discussions

See All

Fiete – A Day on a Farm Review
Fiete – A Day on a Farm Review By Amy Solomon on October 21st, 2014 Our Rating: :: A MEMORABLE EXPERIENCEUniversal App - Designed for iPhone and iPad Fiete – A day on a farm in an interactive app for young children full of... | Read more »
Tilt to Live: Gauntlet’s Revenge is Almo...
Tilt to Live: Gauntlet’s Revenge is Almost Here Posted by Jessica Fisher on October 21st, 2014 [ permalink ] One Man Left has announced the official release date of Tilt to Live: Gauntlet’s Re | Read more »
Sago Mini Monsters Celebrates Halloween...
Sago Mini Monsters Celebrates Halloween with Fun Costumes and Special Treats. Posted by Jessica Fisher on October 21st, 2014 [ permal | Read more »
Inferno 2 Review
Inferno 2 Review By Andrew Fisher on October 21st, 2014 Our Rating: :: TWIN STICK GOODNESSUniversal App - Designed for iPhone and iPad With tight controls and awesome, stark visuals, Inferno 2 is loads of fun.   | Read more »
Clips Review
Clips Review By Jennifer Allen on October 21st, 2014 Our Rating: :: CONVENIENT PASTINGUniversal App - Designed for iPhone and iPad Making copying and pasting more powerful than usual, Clips is a great way to move stuff around.   | Read more »
MonSense Review
MonSense Review By Jennifer Allen on October 21st, 2014 Our Rating: :: ORGANIZED FINANCESiPhone App - Designed for the iPhone, compatible with the iPad Organize your finances with the quick and easy to use, MonSense.   | Read more »
This Week at 148Apps: October 13-17, 201...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Angry Birds Transformers Review
Angry Birds Transformers Review By Jennifer Allen on October 20th, 2014 Our Rating: :: TRANSFORMED BIRDSUniversal App - Designed for iPhone and iPad Transformed in a way you wouldn’t expect, Angry Birds Transformers is a quite... | Read more »
GAMEVIL Announces the Upcoming Launch of...
GAMEVIL Announces the Upcoming Launch of Mark of the Dragon Posted by Jessica Fisher on October 20th, 2014 [ permalink ] Mark of the Dragon, by GAMEVIL, put | Read more »
Interview With the Angry Birds Transform...
Angry Birds Transformers recently transformed and rolled out worldwide. This run-and-gun title is a hit with young Transformers fans, but the ample references to classic Transformers fandom has also earned it a place in the hearts of long-time... | Read more »

Price Scanner via MacPrices.net

Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Strong iPhone, Mac And App Store Sales Drive...
Apple on Monday announced financial results for its fiscal 2014 fourth quarter ended September 27, 2014. The Company posted quarterly revenue of $42.1 billion and quarterly net profit of $8.5 billion... Read more
Apple Posts How-To For OS X Recovery
OS X 10.7 Lion and later include OS X Recovery. This feature includes all of the tools you need to reinstall OS X, repair your disk, and even restore from a Time Machine backup. OS X Recovery... Read more
Mac OS X Versions (Builds) Supported By Vario...
Apple Support has posted a handy resource explaining which Mac OS X versions (builds) originally shipped with or are available for your computer via retail discs, downloads, or Software Update. Apple... Read more
Deals on 2011 13-inch MacBook Airs, from $649
Daily Steals has the Mid-2011 13″ 1.7GHz i5 MacBook Air (4GB/128GB) available for $699 with a 90 day warranty. The Mid-2011 13″ 1.7GHz i5 MacBook Air (4GB/128GB SSD) is available for $649 at Other... Read more
2013 15-inch 2.0GHz Retina MacBook Pro availa...
B&H Photo has leftover previous-generation 15″ 2.0GHz Retina MacBook Pros now available for $1599 including free shipping plus NY sales tax only. Their price is $400 off original MSRP. B&H... Read more
Updated iPad Prices
We’ve updated our iPad Air Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers, including the new iPad Air 2 and the... Read more
Apple Pay Available to Millions of Visa Cardh...
Visa Inc. brings secure, convenient payments to iPad Air 2 and iPad mini 3as well as iPhone 6 and 6 Plus. Starting October 20th, eligible Visa cardholders in the U.S. will be able to use Apple Pay,... Read more
Textkraft Pocket – the missing TextEdit for i...
infovole GmbH has announced the release and immediate availability of Textkraft Pocket 1.0, a professional text editor and note taking app for Apple’s iPhone. In March 2014 rumors were all about... Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.