## Saturday, April 11, 2015

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

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)
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