Python 3.3 vs. MSDOS Basic

[Ian Kelly]

On Mon, Feb 18, 2013 at 3:01 PM, Chris Angelico <rosuav at gmail.com> wrote:
> On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>> Well, I don't see anything that looks especially slow in that code,
>> but the algorithm that you're using is not very efficient.  I rewrote
>> it using dynamic programming (details left as an exercise), which got
>> the runtime down to about 4 seconds.
>
> Did it involve a dictionary, mapping a value to its count, so that any
> time you hit a value you've seen, you can short-cut it? That was my
> first optimization consideration, though I didn't implement it in any
> version, so as to keep the timings comparable.

Ayup.