Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

TL/DR: Any way to work out if known numbers between a known start and ending figure should be positive or negative numbers?

I am developing an application in PHP which can import and read PDFs. The PDFs are financial ones such as bank statements with records of transactions in and out of a bank account. I only have PDFs to work with, no other formats such as CSV unfortunately.

I convert the PDF to HTML using pdftohtml and start parsing the data, the intended end result is an array of transactions. So far I have it working smoothly collecting dates, descriptions and balance. Converting the XML instead doesn't help.

There are other pieces of transcriptional data such as debit or credit amounts. In the PDF, the credit amount is in one column and the debit amount is in another column so it is quite clear in the PDF. However, when converted to HTML, the formatting is lost and therefor I don't know if the amount was a credit or debit amount.

So, my question is, given a starting balance and an ending balance and several known figures in between, is it possible for a programme to work out if those known figures in between are credit or debit amounts?

I imagine there could potentially be several combinations of those known values to reach the ending balance so I'd like to apply a formula to return the correct credit/debit sequence only if its the only possible solution. If there are several ways of adding/subtracting the known values to reach the end balance, I can ask the user to look at it manually but I'd like to keep this to a minimum if possible.

Possible to do, do you think? Thank you in advance for any help.

share|improve this question
    
I believe you are looking for a variation on the subset sum problem. –  MichaelT Dec 20 '12 at 14:45
    
You might consider changing your approach here, and using OCR instead of converting to html. Then you can define regions on the page, and extract the columns individually. –  GrandmasterB Dec 20 '12 at 16:50

2 Answers 2

up vote 2 down vote accepted

If there are only a few values between the starting and the ending figure, you could use a brute force algorithm (try out all the combinations of pluses and minuses). I doubt there's a much more efficient way of doing this, since it's not enough to just find one solution - you need to check if it's the only solution. You could probably use some tricks to make the whole process a bit faster, but that still won't help you if you have a lot of numbers in between.

That solution, however, seems inelegant... Maybe you should concentrate on finding a way of preserving the debit/credit information when converting data from PDF to HTML. What do your output files look like? Isn't there a pattern (like "debit values are in odd positions and credit values are in even positions" or something similar)?

share|improve this answer
    
Here is a sample of what I am working with .. 3295.60<br> 01 Jan 2002 {text description}<br> 800.00<br> {text description}<br> 1440.00<br> {text description}<br> 600.00<br> {text description}<br> 610.00<br> 5525.60<br> .. In this case, the starting balance is 3295.60, the ending balance is 5525.60 In between there are values of 800.00, 1440.00, 600.00 and 610.00 In this case I can tell that the values should be +800, +1440, +600 and -610 to arrive at the final figure. –  Gortron Dec 20 '12 at 11:15
    
Sorry I can't format the above sample a little better in a comment. I think you are correct, I will see if there is any way to convert from PDF to HTML/XML that might give me more structure or information to work with. –  Gortron Dec 20 '12 at 11:17
    
Wait, are positive values always followed by negative values or is it just a coincidence in your example? –  iCanLearn Dec 20 '12 at 11:23
    
Maybe I'm missing something here... but surely it's relatively easy to implement this? If you have all the numbers inbetween the two amounts and they can only be debits or credits (+/-), simply parse all combinations possible until you arrive at the end amount. Even with a fairly large amount of numbers inbetween the two amounts it shouldn't take too long to compute given that there are only two states for each number (+/-)? –  Anonymous Dec 20 '12 at 11:23
    
@iCanLearn Nope, thats just a coincidence here. –  Gortron Dec 20 '12 at 11:25

I can't see how that would be possible. Consider this:

Starting balance $100
$10 credit
$5 debit
$5 debit
Closing balance $100

And this:

Starting balance $100
$10 debit
$5 credit
$5 credit
Closing balance $100

How could you distinguish between those two cases?

share|improve this answer
    
Hi, Yes this situation could arise. It hasn't in the last 3 years but I can't rule it out. What I'm hoping for is, for a formula to tell me the credit/debit values only if it is the only way the numbers can be used to arrive at the final value. If there are other combinations or there is no clear solution, I'll flag that to the application user to manage manually. –  Gortron Dec 20 '12 at 10:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.