This year’s qualification problems were all straightforward puzzles. None of them needed sophisticated implementation techniques, or advanced algorithms, or complex data structures. They just needed patient analysis and careful coding. That’s nice from one perspective, but unfortunately it’s hard to make a good comparison of programming languages when every problem can be solved with just loops and arrays. Still, I succeeded in my goal of producing every output with a different (sometimes terrible) language.
Here’s my code and commentary on the problems. Warning: spoilers ahead. If you haven’t looked at the problems yet, go do that first.
A: Counting Sheep
There’s only one trick to this problem: detecting infinite loops. Otherwise it’s just a matter of implementing the counting process as specified.
Small
Language: Bash
There’s a special place in hell for people who write real programs in Bash and then expect their colleagues to maintain them. The Bourne Again Shell has grown features like a tumour – this code is %100 Bash builtins. It keeps track of digits simply by iterating over the string representations of numbers and storing the digits in an associative array.
#!/bin/bash
set -e
read
CASE_NUM=1
while read N
do
if [[ "$N" = 0 ]]
then
ANS=INSOMNIA
else
declare -A SEEN
I=1
while [[ ${#SEEN[@]} -lt 10 ]]
do
CUR=$(($I * $N))
for (( J=0; J<${#CUR}; J++ ))
do
SEEN[${CUR:$J:1}]=yes
done
((I++))
done
unset -v SEEN
ANS=${CUR}
fi
echo "Case #${CASE_NUM}: ${ANS}"
((CASE_NUM++))
doneLarge
Language: dc
Wikipedia says most of it:
dc is a cross-platform reverse-polish desk calculator which supports arbitrary-precision arithmetic. It is one of the oldest Unix utilities, predating even the invention of the C programming language. Like other utilities of that vintage, it has a powerful set of features but an extremely terse syntax.
The code says the rest:
#!/usr/bin/dc
[L@s0q]sB[q]sQ[lc1+scd1r:h]sF[d0=Q10~d;h0=Fs0lRx]sR[lc10=Qln+dlRxs0lKx]sK[l@10=B0l@:hl@1+s@lZx]sZ[[INSOMNIA]Pq]sI[?dsn0=I0S@lZx0sc0lKxn]sS[lTl@>B[Case #]Pl@n[: ]PlSx10anl@1+s@lCx]sC?sT1s@lCx
Next time you hear someone brag about how much their favourite programming language can do with one line of code, ask if they’ve tried dc. They might like it.
This code extracts digits by repeatedly taking the remainder after dividing by 10, and keeps track of them in an array of flags.
B: Revenge of the Pancakes
The small case can be brute forced, and the official analysis suggests using BFS. Because there’s no need to flip a stack of pancakes more than once (because flipping is commutative and two flips cancel out) you can also solve it by just asking “Do I flip this stack?” for each possible stack of pancakes, and brute forcing all possible combinations to find the best one that works. For a total stack size of , a good way to implement that is to loop from to and use the numbers as a binary encoding of whether to flip each stack.
I didn’t do that. My solution is equivalent to the one in the analysis for the large case, but maybe a little easier to explain. The key insight is that if the bottom pancake needs flipping, there’s only one way to do it: flip the whole stack. So we can simply look at the bottom pancake and decide whether or not to flip the entire stack, and then we never consider flipping the whole stack again. Then we look at the pancake that’s second from the bottom. The only remaining possible way to flip this pancake (if we need to) is to flip all the pancakes from this one up. If we keep working up the pancake stack this way, we can figure out exactly when to flip and when to not flip.
You can implement this by simulating the whole flipping process with an array of “pancakes”, which results in an solution that’s fast enough ( is 100 at maximum). You can avoid doing a full simulation by only keeping track of how many times you’ve flipped, or (because two flips is the same as no flips as far as the higher pancakes are concerned) just whether you’ve flipped an even or odd number of times. This results in an solution, and it’s what I used because it’s easy to implement.
Small
Language: Lua
Lua’s designed as a powerful but fast and lightweight embeddable scripting language, and generally it’s not bad at being that. It has the usual variables and basic data types (including “tables” – associative arrays), as well as modules, first-class functions, closures and iterators. The standard library is deliberately minimal so that you can add only what you need (unlike Python).
It does have a few quirks like all variables being global by default.
#!/usr/bin/lua
function solve(data)
local ret = 0
local parity = '+'
for j = data:len(),1,-1 do
if data:sub(j,j) ~= parity then
ret = ret + 1
if parity == '+' then
parity = '-'
else
parity = '+'
end
end
end
return ret
end
function cases(f)
f:read('*line')
local read_case = function(_, case_num)
local data = f:read('*line')
if data == nil then return end
return case_num+1, data
end
return read_case, 0, 0
end
io.stdout:setvbuf('line')
for case_num, data in cases(io.stdin) do
answer = solve(data)
io.write(string.format('Case #%d: %d\n', case_num, answer))
endLarge
Language: Awk
When I first learned Awk, I thought it was pretty cool, tried it for a few things, then practically never used it
again. It’s like a next step up from basic *nix text-processing commands such as sed and tr – it
adds all kinds of nice things like functions and variables. The trouble is, if you need those things you might as well
use a full-blown scripting language. About the only thing I use the awk command for in practice is as a better cut, which is kind of like buying one of those all-in-one, automatic food
processor machines and using it as a nifty blender.
This Awk code is an almost literal translation of the Lua code.
#!/usr/bin/awk -f
function solve()
{
ret = 0
parity = "+"
split($0, pancakes, "")
for (j=length($0); j>=1; j--)
{
if (pancakes[j] != parity)
{
ret++;
if (parity == "+")
{
parity = "-"
}
else
{
parity = "+"
}
}
}
return ret
}
/^[+-]+$/ {
printf "Case #%d: %d\n", NR-1, solve()
fflush()
}C: Coin Jam
For this problem it was really helpful to get away from a computer screen and do some pen-and-paper analysis. First I wrote down what “evaluating a string in base ” meant in algebraic terms.
where the variables represent the digits of the string. We need to multiply two numbers to get a coin (i.e., a number where the variables have a certain pattern of 1 and 0 values). Simply trying a factor (I chose ) and resolving the constraints gives a set of solutions. This had the side effect that was a suitable “proof” divisor for every coin I generated, so my code output that same list every time.
The problem statement helpfully points out that you can do preprocessing because you know the inputs beforehand. Preprocessing isn’t actually needed if you can calculate the coins directly, but I did do some postprocessing. I.e., I wrote a quick script that parsed the output and verified that it met all the requirements. That way I was pretty confident when I submitted.
Small
Language: Ruby
Ruby is a new language for me, but because this blog is built with Jekyll, I’m using more of it nowadays. My impression so far is that it’s a lot like Python but with a heavier emphasis on map/reduce/filter-style programming (which I like). One the negative side, it has a lot of unnecessary complexity. The Zen of Python says there should be one obvious way to do things. It doesn’t work out that way, but at least Guido has tried. Ruby’s motto could be “Let’s add another way to do it!” Compare map and collect for example.
Because this problem is more about the analysis than the coding, Ruby feels kind of overpowered for the job compared to the other languages I used, but I wanted to use it at least once in this competition.
#!/usr/bin/ruby
CaseData = Struct.new(:n, :j)
def cases(in_file)
Enumerator.new do |enum|
in_file.readline
while not in_file.eof?
n, j = *in_file.readline.split.map(&:to_i).to_a
enum.yield CaseData.new n, j
end
end
end
def bits(v, len)
ret = []
for j in 0...len do
ret << (v & 1)
v >>= 1
end
ret
end
def solve(data)
num_free_bits = (data.n - 3) / 2
divisor_string = (3..11).map(&:to_s).join(' ')
for v in 0...data.j do
coin_factor = 1
bits(v, num_free_bits).each do |bit|
coin_factor <<= 2
coin_factor += bit
end
coin_factor <<= 2
coin_factor += 1
print (coin_factor * 3).to_s(2), ' ', divisor_string, "\n"
end
end
cases($stdin).with_index(1) do |data, case_num|
puts "Case ##{case_num}:"
solve data
$stdout.flush
endLarge
Language: Haskell
Kind of like Ruby, Haskell is overpowered for this job, but I wanted to use it anyway. I’m a pretty casual user of Haskell. Haskell programming requires a completely different approach from any other language I use (even Lisp), so I try it out every now and then to broaden my horizons.
Haskell’s lists are good enough for getting the “Correct” reponse from the judge, but Haskell doesn’t really become Haskell until you use its abstractions (yes, like the infamous monads).
import Control.Monad
import Control.Monad.State
import Data.Bits
import Data.List
import Debug.Trace
import System.IO
import Text.Printf
type Case = (Int, Integer)
type Parser a = State [String] a
parseString :: Parser String
parseString = state $ \(x:xs) -> (x, xs)
parse :: Read a => Parser a
parse = parseString >>= return . read
parseNOf p n = sequence $ replicate n p
parseCases = parse >>= parseNOf parseCase
parseCase :: Parser Case
parseCase = liftM2 (,) parse parse
div_string :: String
div_string = unwords $ map show [3..11]
caseLabel :: Integer -> String
caseLabel = printf "Case #%d: "
gcj :: String -> String
gcj input = let cases = evalState parseCases (words input)
solutions = map solve cases
lSolutions = map (uncurry (:)) $ zip (map caseLabel [1..]) solutions
in unlines $ concat lSolutions
main = hSetBuffering stdout LineBuffering >> interact gcj
solve :: Case -> [String]
solve (n, j) = map (genCoin n) [0..j-1]
binaryExpansion :: Integer -> [Integer]
binaryExpansion n = n .&. 1 : binaryExpansion (shift n (-1))
binaryEvaluation :: [Integer] -> Integer
binaryEvaluation [] = 0
binaryEvaluation (b:bs) = b .|. (shift (binaryEvaluation bs) 1)
showBin = printf "%b"
genCoin :: Int -> Integer -> String
genCoin n v = let num_free_bits = div (n - 3) 2
free_bits = take num_free_bits $ binaryExpansion v
bits = [1, 0] ++ (concat [[b, 0] | b <- free_bits]) ++ [1]
factor = binaryEvaluation bits
in (showBin $ 3 * factor) ++ " " ++ div_stringD: Fractiles
The final problem in a Code Jam qualification round usually takes some special insight or creative approach, but this one just required patient analysis. If you treat the original tile pattern as a system input, and the result as a system output, it’s just about figuring out which output tiles depend on which input tiles, and then choosing a set of output tiles that covers the whole input.
The problem statement uses 1-based indexing, but I used 0-based indexing internally for simpler implementation.
After I’d thought through how the system worked, the overall solution was simple. If the original pattern has, say, 5 tiles, then I need to select output tiles to cover (0-based) input positions 0, 1, 2, 3, and 4. If the transformation has complexity 3, it turns out each output depends on up to 3 inputs, so I pick an output that depends on inputs 0, 1 and 2, and then an output that depends on inputs 3 and 4, and then I’m done.
Small
Language: Forth
Forth feels a bit like a glorified assembly language for a stack machine. It can be implemented extremely efficiently, so it’s historically been very popular for embedded systems.
( gforth ans.fs -e codejam )
65536 constant line-buffer-size
create line-buffer line-buffer-size chars allot
variable cover-me
create positions 128 cells allot
: parse-line ( -- n* )
line-buffer line-buffer-size chars stdin read-line drop drop
line-buffer swap evaluate
;
: generate { origin-len complexity -- pos }
0
complexity 0 u+do
origin-len *
cover-me @ dup 1+ cover-me ! origin-len 1- min +
loop
1+
;
: fill-positions { origin-len complexity grads -- num-positions }
0
begin
dup cells positions +
origin-len complexity generate
swap !
1+
dup grads >=
cover-me @ origin-len >=
or
until
;
: solve { orig-len complexity grads -- }
0 cover-me !
orig-len complexity grads fill-positions
cover-me @ orig-len < if
S" IMPOSSIBLE" type
else
0 u+do
i cells positions + @ .
loop
then
;
: read-case ( -- origin-len complexity grads )
parse-line
;
: case-output ( i -- )
S" Case #" type 1 .r S" : " type
;
: codejam ( -- )
parse-line
1+ 1 u+do
read-case
i case-output
solve
cr
loop
bye
;
Large
Language: Pascal
Pascal used to be extremely popular, so there must be heaps of legacy Pascal around. The first time I got paid to write code, I was working on a legacy Pascal system. Maybe it’s just me, but it’s not a language that seems to get talked about much. I guess there’s nothing cool or exciting about it, but at the same time it’s no COBOL. The syntax feels a bit like BASIC, but it has pointers so it’s closer to C in terms of power.
The problem statement allows several possible solutions, but I deliberately made my two implementations generate
exactly the same output for the same input, so I could do smoke testing using generated data and diff. I expected the Forth code to break if anything, but actually it was
the Pascal code I messed up. I’d misremembered that the LongInt type was 64b on 64b machines, but actually it’s only 32b with
Free Pascal, so I got integer overflows.
program CodeJam;
Uses math;
var
K : Int64;
C : Int64;
S : Int64;
CaseNum : Integer;
NumCases : Integer;
procedure ReadCase();
begin
read(K);
read(C);
read(S);
end;
procedure Solve();
var
CoverMe : Int64;
Positions : Array[1..100] of Int64;
I : Integer;
J : Integer;
CurPos : Int64;
Generation : Integer;
begin
CoverMe := 0;
I := 1;
while (I <= S) and (CoverMe < K) do
begin
CurPos := 0;
for Generation := 1 to C do
begin
CurPos := CurPos * K + Min(CoverMe, K-1);
CoverMe := CoverMe + 1;
end;
Positions[I] := CurPos + 1;
I := I + 1;
end;
if CoverMe < K then
write(' IMPOSSIBLE')
else
for J := 1 to I-1 do
begin
write(' ', Positions[J]);
end;
writeln();
end;
begin
read (NumCases);
for CaseNum := 1 to NumCases do
begin
ReadCase();
write('Case #', CaseNum, ':');
Solve();
end;
end.
Onwards!
I’ll be much more conservative in the next rounds. I’m likely to use more than one language, but I’ll stick to ones I’m comfortable using under time pressure, and I won’t care if I reuse languages. Also, unfortunately, I didn’t plan my schedule too well. There’s only one Round 1 slot before I leave for DConf, and if I don’t mess that up, I’ll still be on the road for Round 2. But, even if things don’t work out so well this year, at least I’ve met my personal challenge for the qualification round, and there’s always next year. On another note, if you’re going to DConf, too, say hi!
If you missed out on entering the 2016 Code Jam qualification, I really recommend giving it a try next year. The puzzles are creative, and it’s a good way to sharpen your programming skills. The online judge is available throughout the year for practice.