Final Notes on the Telephone Number -> Words Programming Challenge.
I have to say that at first I couldn't fully enjoy this puzzle because of some time constraints. However, looking at it now, and taking an extra two hours to refine the code, I'm having some fun. I went ahead and made some really cool changes this morning which are fully documented at the top of the code. Basically:
- The algorithm I use is recursive. This means that the same substrings may get passed back into the function multiple times. In order to eliminate this feature I've added an intern table. The results are that when running the program, if a specific substring has already been processed, it won't be processed again and the cached results will get returned. This tripled the speed of the program.
- Since part of the algorithms 200 ms was loading the dictionary, I modified the input to allow you to process multiple numbers. If we chose to use this algorithm commercially and cared about the performance, we'd really want to process large amounts of numbers at a time and the pre-cached dictionary would buy us quite a bit.
- Since multiple numbers share common substrings, the intern table now stores all of the results for those substrings. So after processing say 10-20 numbers, the algorithm actually starts getting faster (while consuming a little bit of extra memory).
Having a good look at the remaining code, the only additional optimization I can think of is getting rid of the large number of ArrayList objects and replacing them with something strongly typed. That would probably speed the application up quite a bit. There are a couple of smaller optimizations as well, that I would make if say this challenge added performance rules.
Solutions currently available for the challenge: Solutions to the Phraser programming challenge
My latest and greatest solution: Trying my hand at the old Phone number to Words teaser project!