Qapla'!

I finally got things in sync with van Laarhoven's module, and the output is correct. (Just to make sure, I went back to the Code Jam site and submitted the output. I think that being up until nearly 3:00 a.m. caused my initial reaction to

Judge's response for last submission: Correct.

to be "Oh, [expletive]! The judge says I need to correct my last submission!" Then I realized it was an adjective, not a command, and relaxed.)

I'm a little bummed at using someone else's code for a nontrivial portion of the problem, but OTOH, I did learn more Haskell, which is one of my real goals.

But back to the results: the best time output is

real    0m0.361s
user    0m0.336s
sys     0m0.024s

and the worst is

real    0m0.377s
user    0m0.364s
sys     0m0.008s

Both are less than the 0.4 seconds I saw for the C++ solution I tried.

[We pause here to do a victory dance.]

Where are our cost centers, and how about that memory usage?

COST CENTRE            MODULE                %time %alloc

solve                  Main                   37.7   54.0
digitsIn.digitsIn'     Main                   11.5    7.6
nDigitYs               Main                    9.5    8.3
fromList.(...)         SemilatticeSearchTree   6.8    8.8
tenToThe               Main                    6.2    0.0
justOnes               Main                    4.6    6.2
justOnes.pair          Main                    3.3    3.0
satisfy                SemilatticeSearchTree   2.0    0.0
choices                Main                    1.8    2.8
floorSqrt.floorSqrt'.y Main                    1.8    1.8
fromList               SemilatticeSearchTree   1.8    0.2
yTree                  Main                    1.5    1.4
floorSqrt              Main                    1.1    0.3
digitsIn               Main                    1.1    0.1
meet                   SemilatticeSearchTree   1.1    1.1
mkBranch               SemilatticeSearchTree   1.1    1.0
findFirst              SemilatticeSearchTree   1.1    0.0

Aside from solve and digitsIn.digitsIn', the time distribution is a lot flatter. Now it's even more astonishing just how much time and allocation solve, which just reads the file, calls the function, and prints out the results, takes! Any serious improvement is going to have to come from there.

We are definitely trading space for time. Previous graphs of memory usage peaked at around four megabytes, but this version just about doubles that.

UPDATE: ...and you know, we did tack those ordinal positions on with each Y value and added the tree structure and the upper bound info, so doubling sounds plausible.