Paperless and clueless

Most of my company’s clients still pay us by check. This works out well, because most accounting software prints out additional information—most importantly, our invoice number—on either the check or the stub that comes with it. That helps us figure out which invoice(s) the check should be applied to in our accounting software.

Business check form

Image from ANS Systems

But in our brave new paperless world, more clients are directly depositing their payments in our bank account. This is convenient for them, I suppose, but it usually isn’t for us. What generally happens is a deposit gets made in our account without all that helpful extra information. Typically, we see the payer, the amount, and the date and that’s it. Sometimes that’s enough to work out which invoice got paid, but not always.

Today we got notice of a direct deposit payment of $16,604.10 from a client who had eight outstanding invoices spread out over several projects. No individual invoice was for that amount, nor was the total of all eight, so I had to figure out which combination of invoices had been paid.1

Turns out™ this was pretty easy. Python’s itertools library has a combinations function that generates all the combinations of a given length from a given list. For example,

python:
for i in itertools.combinations([1, 2, 3, 4, 5], 3):
  print i

prints

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

All I needed to do was make a list of the eight outstanding invoice amounts, generate all the combinations of length 2 through 7 (remember, I knew the payment didn’t match the total of all eight), and print out the one(s) that added up to $16,604.10. The only thing that worried me was using an equality check on a sum of floating point numbers. I could have used the decimal module, but I figured it was easier to just use integers and express all the values in cents.

Here’s the code:

python:
 1:  #!/usr/bin/env python
 2:  
 3:  from itertools import combinations
 4:  
 5:  payment = 1660410
 6:  invoices = [46500, 105250, 539439, 827471, 223750, 23250, 773212, 15500]
 7:  
 8:  for n in range(2, len(invoices)):
 9:    print "Testing combinations of {} invoices...".format(n)
10:    for c in combinations(invoices, n):
11:      if sum(c) == payment:
12:        print c

The output was

Testing combinations of 2 invoices...
Testing combinations of 3 invoices...
Testing combinations of 4 invoices...
Testing combinations of 5 invoices...
(46500, 539439, 827471, 223750, 23250)
Testing combinations of 6 invoices...
Testing combinations of 7 invoices...

which meant the invoices that had been paid were the ones for $465.00, $5,394.39, $8,274.71, $2,237.50, and $232.50.

I suppose I could’ve figured this out without Python. After all, I knew immediately that two of the paid invoices had to be $5,394.39 and $8,274.71 because the total ended with 10 cents. Similarly, I knew $7,732.12 couldn’t be part of the total. That would’ve left me with the simpler problem of finding some combination of the five remaining invoices that added to $2,935.00.

But using itertools was more fun, and it gave me a general tool I’ll be able to use in the future.


  1. Couldn’t I just call the client and ask? No, because “the client” was really several branches of a corporate parent. Our project contacts don’t work together. They submit our invoices up the corporate ladder, but they have no idea when they get approved or paid. And working my way through an accounts payable department would’ve taken longer than writing this little script.