Google Codejam 2015 Qualification Round : Part 2: A small/large

[Part 1]

My compiler

The other language I initially intended to use in codejam was an old compiler thing I coded in 2013. It was a school assignment that took me a couple of days to implement. It's just a C clone that doesn't even have arrays. But hey, at least it has integers. And can actually read. Although it can only read one integer, and write one integer. It doesn't have division either. But it compiles to 64 bits asm code which can be compiled to binary, so speed isn't a big issue.

Problem A - The one with shyness - Standing Ovation

I had to pick a good problem for this. But all seemed unsuitable. My first idea for problem A - Standing OvationWas to just bruteforce for the number of additional members. There's no reason to bring audience members who are shy, so their shyness should be 0. The maximum result is equal to Smax. For each candidate number of additional members, we can just simulate the process and check if everyone claps. So we can do this in an `O(S_(max) N)` loop quite easily.

For the large version, and also to solve using a language that has no arrays. We can use an on-line algorithm. We initially have `x` audience members with 0 shyness. We know those will be clapping. So we should worry about the rest. We encounter that there are `s_1` audience members with shyness 1. If `1 > x`, we need to invite one more audience member: `1 - x`. In fact, we can repeat this, now we know there are `max(1,x) + s_1` audience members that are clapping. We find that there are `s_2` members with shyness 2. And so and so.

The problem was that I needed to have a way to turn the neat input file into something my language can read. Then turn the language's output into something that looks like "Case #1: xxx". DISASTER, I actually learned that my asm code only does syscalls for reading bytes and then converts to integer and is not quite the same as a scanf or cin>>x... In fact, the whole thing really fails at reading files. Even ignored the format issues. I had to learn how to automatize having a terminal send keystrokes to my program for it to work. Apparently this is usually a thing that people need as there is a family of programs called expect that do this. Fortunately, after learning how to use expect I found that python has a pexpect module. This allowed me to create this nifty glue python program:

import pexpect
import sys

# call the solver program, return the result
def call_solver(smax, shy):
    try:
        child = pexpect.spawn ('./A')
        child.sendline('%d' % smax)
        child.expect( '.*' )
        for ch in shy:
            child.sendline ('%s' % ch)
            child.expect( '.*' )
        child.expect(pexpect.EOF)
        return int(child.before.split('\r\n')[-2])
    except:
        print "ERROR"
        return -1


T = int(raw_input() )
for i in range(1, T+1):
    s = raw_input()
    (smax, shy) = s.split(' ')
    smax = int(smax)
    print "Case #%d: %d" % (i, call_solver(smax, shy) )  
    sys.stdout.flush()

So now I am free to make my program using my language...

program Codejam2015A
{
    int n, a, s, i, cost;

    read n;
    read s;
    
    i = 1;
    cost = 0;
    //initial clappers (shyness = 0)
    while (i <= n) {
        read a;
        if (a >= 1) {
            if (i > s) {
                // must invite i - s
                cost = cost + (i - s);
                s = i;
            }
        }
        s += a;
        i = i + 1;
    }
    print cost;
    
    
}

Anyway, you can find the complete source code in the codejam score boards...

I submitted A-small, had a failure because it was slower than I thought, I tried to check if there was something wrong. It seems expect is slow in sending things.

I should have known that the reason it was slow would only get worse in A-Large, in fact, when I tried A.large, it turned out that it could barely solve one case per minute, even tho the program was, the glue stuff using expect was very slow, specially when there are 100000 line enters to send to the fake terminal... Failed A-large because of a time out.