Next post Previous post

Combinatorial invoices redux

October 3, 2017 at 8:53 PM by Dr. Drang

A few months ago, I wrote a short script to handle a combinatorial problem at work. A client with several outstanding invoices made a direct deposit payment to our bank account without any accompanying information on which invoices were being paid. The payment amount didn’t match any individual invoice, nor did it match the total of all the outstanding invoices, so I wrote a short Python script using the itertools library to figure out which combination of invoices matched the payment.

The script was written to handle a one-off problem; it wasn’t intended to solve the general situation or be reused. The payment and invoice amounts were coded directly into the script, and I had skirted the problem of comparing floating point numbers by entering all the amounts as integer cents instead of dollars and cents, e.g. 773212 instead of 7732.12. This was a reasonable choice to make when I had only one problem to solve, but when the same thing happened a few weeks later, I decided it was worth putting in the effort to create a more general script.

The script I came up with, called payments, works this way: It prompts me first for the payment amount, which I enter in decimal form, with or without a thousands separator and leading dollar sign. It then asks for the set of invoice amounts that the payment may apply to, separated by spaces. These amounts, too, can optionally include a thousands separator and dollar sign. The output is the combination (or combinations) of invoices that match the payment amount. In the Terminal, it looks like this:

Payments command in Terminal

Here’s the source code for payments:

python:
 1:  #!/usr/bin/env python
 2:  
 3:  from itertools import combinations
 4:  from decimal import Decimal
 5:  
 6:  pstr = raw_input("\x1B[1mPayment: \x1B[22m")
 7:  istr = raw_input("\x1B[1mSpace-separated invoices: \x1B[22m")
 8:  
 9:  payment = Decimal(pstr.replace(',', '').replace('$', ''))
10:  invoices = [ Decimal(x.replace(',', '').replace('$', '')) for x in istr.split() ]
11:  
12:  for n in range(len(invoices)):
13:    for c in combinations(invoices, n+1):
14:      if sum(c) == payment:
15:        print
16:        print "".join('{:11,.2f}'.format(x) for x in c)

The raw_input prompt strings in Lines 6 and 7 include escape codes to turn bolding on and off. The \x1B part is the ASCII code for escape in hexadecimal, the [1m turns bolding on, and the [22m turns bolding off. As you can see in the screenshot, the prompts are bold but the responses I type aren’t.

Lines 9 and 10 convert the response strings into Decimal numbers, which don’t have the rounding problem that floats can have. When you compare a Decimal value to a sum of Decimal values, you get the answer you expect, something that’s not always true when doing comparisons of floating point numbers. The payment amount is put into the payment variable, and the invoice amounts are put into the invoices list.

Lines 9 and 10 also handle the possibility of commas and dollar signs in the input through the replace method. I can enter 7732.12, 7,732.12, $7732.12, or $7,732.12 and they’ll all be accepted as the same number. I wouldn’t normally type in commas or dollar signs, because that’s a waste of time, but I might be pasting in values copied from a source that includes commas or dollar signs.

Line 12 then starts the search for a sum that matches. There are len(invoices) invoices, and we need to look at their combinations one at a time,1 two at a time, three at a time, etc. For each subset size, Line 13 starts the iteration through all the combinations of that number of invoices. Line 14 checks whether the sum of the current combination of invoices matches the payment, and if it does, Lines 15–16 print out the matching invoices.

Line 15 prints a blank line before the matching invoices to put some whitespace between the answer and the second input line. Not having this blank line makes it harder to read the answer. Also, there can be more than one combination that matches—if so, blank lines will separate all the answers.

The invoice amounts in the answer line are printed with thousands separators to make them easier to read. I’ve chosen a field width of in Line 16 because that gives two spaces between amounts for five-figure invoices. My company has never sent out a six-figure invoice in the 20+ years we’ve been in business, and I don’t expect that to happen before I retire.

I had forgotten I’d generalized the payments script until I saw this very nice tweet from Ricky Mondello linking to the post from July. I figured an update post was in order.

I love this blog post by @drdrang where he describes how he wrote some code to solve a real-world invoicing problem. leancrew.com/all-this/2017/…
— Ricky Mondello (@rmondello) Oct 1 2017 3:14 PM

I’ve been following Ricky for almost as long as I’ve been on Twitter, and he’s been a good investment—always interesting and thoughtful. Nine years ago, he was a bright college kid; now he’s a Safari developer at Apple. A good investment for Apple, too.

  1. OK, one at a time isn’t really necessary, because if the payment matched a single invoice I’d know it. But it doesn’t hurt to include it. ↩

Next post Previous post