Google Codejam 2015 Qualification Round : Part 3: B small in Julia

(Part 1: Problem D) (Part 2: Problem A)

After the disaster solving A-large, it became clear that I needed to do more than 2 problems to get an advancing score. But also both B and C seemed likely to be impossible in the languages I wanted. But I still didn't want to use my normal languages. I mean at least B-small seemed quite obvious. A typical problem we can solve with memoization. If we set the state to be equal to an array of 9 elements containing the number of eaters that have 1, 2, ... 9 pancakes. We need to notice that it never makes sense to create a plate that has more pancakes than the original plate from which we took the pancakes. Otherwise each minute just shifts the array...

Anyway, I decided to look for a new language to learn. But something a bit more usable than the other two. I tried Julia. It actually felt like cheating, because it turns out this is a pretty good language. There's a couple of things I don't like, like the 1-indexing. But it was overall a nice experience. Similar to python but with some differences. And apparently benchmarks say it is a bit faster. You can also make it less dynamically typed if needed. Anyway:

function solve(P)
    mem = Dict()

    function f(seq)
        if haskey(mem, seq)
            return mem[seq]
        end
        #println(seq)
        res = 1000000000
        if count(x -> (x != 0), seq) == 0
            # all zeros, base case
            res = 0
        else
            # let one minute go:
            a = [ seq[i] for i = [2:9] ]
            push!(a, 0)
            res = 1 + f(a)
            
            # move something:
            for i = [2:9]
                if seq[i] > 0
                    for j = [1:i-1]
                        #if j != div(i , 2)
                        #    continue
                        #end
                        for k = [1 : i - j - 1]
                            if seq[k] > 0
                                b = [x for x = seq]
                                b[k] -= 1
                                b[k + j] += 1
                                b[i] -= 1
                                b[i - j] += 1
                                res = min(res, 1 + f(b) )
                            end
                        end
                        # move to empty plate
                        if i - j < i
                            b = [x for x = seq]
                            b[j] += 1
                            b[i - j] += 1
                            b[i] -= 1
                            res = min(res, 1 + f(b) )
                        end
                    end
                end
            end
        end
        mem[seq] = res
        #print (seq)
        #print (" = ")
        #println(res)
        return res
    end
    
    seq = [ count(x -> x==i, P) for i = [1:9] ]
    
    return f(seq)
end

s = int(readline(STDIN))
for i = [1: s]
    n = int(readline(STDIN))
    q = split(readline(STDIN), " " )
    P = map( x -> int(x) , q)
    @printf "Case #%d: %d\n" i solve(P)
end

Coding this was easy except for googling how to do things. The logic I learned when learning python really helped.