Began work on script to reconcile bank accounts.

The goal here is to take as input an account, a monthly balance amount
that appears on a bank statement, and the date of that bank statement and
output the list of transactions that likely weren't cleared properly as of
that date that caused the balance in the accounts to fail to match the
balance that appeared on the statement.

Note that determining this answer requires solving the known NP-Complete
problem called the subset sum problem.  There is a known pseudo-polynomial
dynamic programming solution to this problem, but it's still exponential
in the size of the numbers you have to balance.

So, if you have *big* account balances, this will make take quite a while
to run.  For smaller accounts, the pseudo-polynomial solution might be
helpful.  (BTW, the wikipedia entry on the subset sum problem isn't, at
the time of this commit, particularly good, but it's "good enough" to give
you a sense of what the subset sum problem is:
    http://en.wikipedia.org/wiki/Subset_sum_problem

)

I originally wrote the subset sum problem solution implementation here:
  https://gitorious.org/bkuhn/small-hacks/commit/2dca069d810b61cdfad46e00abcb1a3edaf56d1b

The code is just cut and pasted in here with some minor modifications.

This rest of this first commit just has that aforementioned paste, plus the
beginnings of the CLI and query to run to get the proper entries.

1 files changed, 122 insertions, 0 deletions

diff --git a/contrib/non-profit-audit-reports/bank-reconcilation.plx b/contrib/non-profit-audit-reports/bank-reconcilation.plx
new file mode 100755
index 00000000..7201ef1f
--- /dev/null
+++ b/contrib/non-profit-audit-reports/bank-reconcilation.plx
@@ -0,0 +1,122 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigFloat;
+use Date::Manip;
+
+Math::BigFloat->precision(-2);
+my $ZERO =  Math::BigFloat->new("0.00");
+
+my $VERBOSE = 0;
+my $DEBUG = 0;
+
+my $LEDGER_BIN = "/usr/local/bin/ledger";
+
+######################################################################
+sub SubSetSumSolver ($$$) {
+  my($numberList, $totalSought, $extractNumber) = @_;
+
+  my($P, $N) = (0, 0);
+  foreach my $ii (@{$numberList}) {
+    if ($ii < $ZERO) {
+      $N += $ii;
+    } else {
+      $P += $ii;
+    }
+  }
+  my $size = scalar(@{$numberList});
+  my %Q;
+  my(@L) =
+     map { { val => &$extractNumber($_), obj => $_ } } @{$numberList};
+
+  for (my $ii = 0 ; $ii <= $size ; $ii++ ) {
+    $Q{$ii}{0}{value} = 1;
+    $Q{$ii}{0}{list} = [];
+  }
+  for (my $jj = $N; $jj <= $P ; $jj++) {
+    $Q{0}{$jj}{value} = ($L[0]{val} == $jj);
+    $Q{0}{$jj}{list} = $Q{0}{$jj}{value} ? [ $L[0]{obj} ] : [];
+  }
+  for (my $ii = 1; $ii <= $size ; $ii++ ) {
+    for (my $jj = $N; $jj <= $P ; $jj++) {
+      if ($Q{$ii-1}{$jj}{value}) {
+        $Q{$ii}{$jj}{value} = 1;
+
+        $Q{$ii}{$jj}{list} = [] unless defined $Q{$ii}{$jj}{list};
+        push(@{$Q{$ii}{$jj}{list}}, @{$Q{$ii-1}{$jj}{list}});
+
+      } elsif ($L[$ii]{val} == $jj) {
+        $Q{$ii}{$jj}{value} = 1;
+
+        $Q{$ii}{$jj}{list} = [] unless defined $Q{$ii}{$jj}{list};
+        push(@{$Q{$ii}{$jj}{list}}, $jj);
+      } elsif ($Q{$ii-1}{$jj - $L[$ii]{val}}{value}) {
+        $Q{$ii}{$jj}{value} = 1;
+        $Q{$ii}{$jj}{list} = [] unless defined $Q{$ii}{$jj}{list};
+        push(@{$Q{$ii}{$jj}{list}}, $L[$ii]{obj}, @{$Q{$ii-1}{$jj - $L[$ii]{val}}{list}});
+      } else {
+        $Q{$ii}{$jj}{value} = 0;
+        $Q{$ii}{$jj}{list} = [];
+      }
+    }
+  }
+  foreach (my $ii = 0; $ii <= $size; $ii++) {
+    foreach (my $jj = $N; $jj <= $P; $jj++) {
+      print "Q($ii, $jj) == $Q{$ii}{$jj}{value} with List of ", join(", ", @{$Q{$ii}{$jj}{list}}), "\n";
+    }
+  }
+  return [ $Q{$size}{$totalSought}{value}, \@{$Q{$size}{$totalSought}{list}}];
+}
+######################################################################
+sub Commify ($) {
+    my $text = reverse $_[0];
+    $text =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/g;
+    return scalar reverse $text;
+}
+######################################################################
+sub ParseNumber($) {
+  $_[0] =~ s/,//g;
+  return Math::BigFloat->new($_[0]);
+}
+if (@ARGV < 4) {
+  print STDERR "usage: $0 <ACCOUNT_REGEX> <END_DATE> <BANK_STATEMENT_BALANCE> <LEDGER_OPTIONS>\n";
+  exit 1;
+}
+######################################################################
+my($account, $endDate, $balanceSought, @mainLedgerOptions) = @ARGV;
+
+$balanceSought = ParseNumber($balanceSought);
+
+my $err;
+my $startDate = UnixDate(DateCalc(ParseDate($endDate), ParseDateDelta("- 1 month"), \$err), "%Y/%m/%d");
+die "Date calculation error on $endDate" if ($err);
+
+my(@fullCommand) = ($LEDGER_BIN, @mainLedgerOptions, '-V', '-X', '$',
+                    '-b', $startDate, '-e', $endDate,
+                    '-F', '"%(date)","%C","%P","%t"\n',
+                    'reg', "/$account/");
+
+  open(FILE, "-|", @fullCommand)
+    or die "unable to run command ledger command: @fullCommand: $!";
+
+my @entries;
+
+foreach my $line (<FILE>) {
+  die "Unable to parse output line from: $line"
+    unless $line =~ /^\s*"([^"]*)","([^"]*)","([^"]*)","([^"]*)"\s*$/;
+  my($date, $checkNum, $payee, $amount) = ($1, $2, $3, $4);
+  die "$amount is not a valid amount"
+    unless $amount =~ s/\s*\$\s*([\-\d\.\,]+)\s*$/$1/;
+  $amount = ParseNumber($amount);
+
+  print "$date, $checkNum, $payee, $amount\n";
+  push(@entries, { date => $date, checkNum => $checkNum, amount => $amount });
+}
+
+###############################################################################
+#
+# Local variables:
+# compile-command: "perl -c bank-reconcilation.plx"
+# End: