Defeated by Ugly Numbers
Now I am out of Code Jam 2008.
Though I did the Text Messaging Outrage quite easily I've bet my solution to the use of the 'bc' command as a helper in Ugly Numbers for computing strings like "12123+324234+232342-234234". For these numbers it does not seem to be any need, but to be able to solve the large data set of the same problem arbitrary (or at least 40 digits) precision was a requirement. 'bc' can work with these, but unfortunately the computing speed I've got was not up to the task.
I was piping each line to 'bc' and reading the proper answer. Unfortunately it took more than half an hour on my laptop to finish calculation. I run out of time and I failed both small and large datasets.
Later on, once the contest was over and the problems were in practice mode I uploaded my solution file for the small problem and it was Correct! (too late). Still my routing for checking ugly numbers was only dealing with Java longs (n<2^63) so it was not good for the large data set.
Now I've changed the guts of my problem to use BigInteger class (that proved to be as slow as bc was). I'm waiting for the computing to finish with the large problem set but for 40 digits long numbers it's taking forever. This makes me think that it has to be a better way (so it's time to dig on the code submitted by others).
Ok, I've just did and I can tell you now: Mine was not a good idea! In fact I guess the universe will be long frozen before I can obtain an answer using the above depicted method.
Though I did the Text Messaging Outrage quite easily I've bet my solution to the use of the 'bc' command as a helper in Ugly Numbers for computing strings like "12123+324234+232342-234234". For these numbers it does not seem to be any need, but to be able to solve the large data set of the same problem arbitrary (or at least 40 digits) precision was a requirement. 'bc' can work with these, but unfortunately the computing speed I've got was not up to the task.
I was piping each line to 'bc' and reading the proper answer. Unfortunately it took more than half an hour on my laptop to finish calculation. I run out of time and I failed both small and large datasets.
Later on, once the contest was over and the problems were in practice mode I uploaded my solution file for the small problem and it was Correct! (too late). Still my routing for checking ugly numbers was only dealing with Java longs (n<2^63) so it was not good for the large data set.
Now I've changed the guts of my problem to use BigInteger class (that proved to be as slow as bc was). I'm waiting for the computing to finish with the large problem set but for 40 digits long numbers it's taking forever. This makes me think that it has to be a better way (so it's time to dig on the code submitted by others).
Ok, I've just did and I can tell you now: Mine was not a good idea! In fact I guess the universe will be long frozen before I can obtain an answer using the above depicted method.
Comments
It took me almost 12 minutes to solve the small data set.
However a bit of number theory is still missing on my side, as I do not see how the code above does not care about addition or subtraction when processing the string and still gives the correct answer.