Skip to content

Instantly share code, notes, and snippets.

@cacycleworks
Last active December 12, 2015 05:58
Show Gist options
  • Save cacycleworks/4725534 to your computer and use it in GitHub Desktop.
Save cacycleworks/4725534 to your computer and use it in GitHub Desktop.
Recursive function in php to reconcile credit card batches to an array of charges where the sum of a subset of charges matches the batch amount. Absurdly easy to "see" and do with your mind, getting it programmed was not easy at all.
<?
$charges=Array(
'2863996511' => 154.00 ,'2863879671' => 10.88
,'2863992361' => 762.20 ,'2863858891' => 209.00
,'2863898975' => 49.00 ,'2863856334' => 148.00
,'2863894564' => 5.44 ,'2863367273' => -25.01
); print_r($charges);
$targets=Array(1302.63, 1327.64, 1322.20 );
foreach( $targets as $batch ) {
printf( "We seek combination of transId's to = $%-7.2f\n", $batch);
$answer=reconcile( $batch, $charges );
if( is_array($answer) )
echo eval( "return ".implode("+",$answer).";" )."\nWIN!\n";
else
echo "Bust!\n";
}
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
// recursive reconcile to find if a subset of a charges array matches our batch
function reconcile( $target, $arr ){
if( count($arr) < 2 )
return FALSE;
$sum = eval( "return ".implode("+",$arr).";" ); // 154.00 + 10.88 + 762.20 + 209.00 + 49.00 + 148.00
if($sum < $target) {
$negatives=0;
// add up the negatives and see if it's even possible to meet the target
foreach( $arr as $id=>$amt )
if( $amt < 0 )
$negatives+=$amt;
if($sum < ($target+$negatvies)) {
// echo "Impossible for input array of charges ($$sum) to add up to $$target, bailing. (line: ". __LINE__ .")\n";
return FALSE;
}
}
foreach( $arr as $id=>$amt ){
if( abs($sum-$target-$amt) < .01 ) {
echo ". omit $id : ".$arr[$id]."\n";
unset($arr[$id]);
return $arr; // return the array of the matched subset
}
}
foreach( $arr as $id=>$amt ){
$tmp=$arr; // make copy of input array
unset($tmp[$id]); // get rid of this iteration's charge amount
// call ourself to see if a subset of this subset matches
$rtn = reconcile( $target, $tmp );
if( is_array($rtn) ) {
echo ".. omit $id : ".$arr[$id]."\n";
return $rtn; // return our subset of subset
}
}
return FALSE; // never found a match, sorry!
}
/*
We seek combination of transId's to = $1302.63
. omit 2863879671 : 10.88
1302.63
WIN!
We seek combination of transId's to = $1327.64
. omit 2863367273 : -25.01
.. omit 2863879671 : 10.88
1327.64
WIN!
We seek combination of transId's to = $1322.20
. omit 2863367273 : -25.01
.. omit 2863879671 : 10.88
.. omit 2863894564 : 5.44
1322.2
WIN!
*/
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment