Google Codejam 2015 Qualification Round : Part 4: C small

Part 1: Problem D in Emily

Part 2: Problem A in unnamed language

Part 3: Problem B in Julia

C small

Problem statement

Unlike the other Small problems I didn't really think of a solution of this right away. I had to take a day to do it.

The trick to the problem is that we can find in `O(n)` the product of the `x` first left-most numbers (for all `x`). And the same for the right-most numbers. So imagine if we had a substring `[a,b]`. If left[a-1] is equal to `i` and right[b+1] is `k` then all that we need to learn is if the substring is equal to `j`. If we can answer that question in `O(n^2)`, we have the whole problem solved. And we totally can answer that question! We just need to start with an `a`, then `b = a` and calculate the product for `b = a`, then it is easy to calculate the product when `b = a + 1`, just multiply one more number. And so and so for `b = a + 2`, etc.

The only extra complication is doing the multiplication with `i`, `j`, `k` and the signs... Well, really there are 8 distinct numbers, and we can easily index them and make a table, multiplying this index with this other index yields this other index...

So I tried free pascal. I used to code in Pascal, and I hated it. Now I don't really remember much. So I guess it counts? I had to relearn Pascal a bit. But I reached a solution... which failed. And then it failed again and again... I really thought the problem was in that big hardcoded matrix, and spent hours trying to think of a mistake there. Turns out that free Pascal's Strings are limited to 255 characters (What the hell, free pascal?). You have to use AnsiString for limitless strings.

program C;

function solution(s : AnsiString): String;
const
   CONST_I = 2;
   CONST_J = 4;
   CONST_K = 6;
var
   i, j, n, left, curr : Integer;
   right : Array[0..100000] of Integer;
   t : Array[0..7,0..7] of Integer = (
       (0,1,2,3,4,5,6,7),
       (1,0,3,2,5,4,7,6),
       (2,3,1,0,6,7,5,4),
       (3,2,0,1,7,6,4,5),
       (4,5,7,6,1,0,2,3),
       (5,4,6,7,0,1,3,2),
       (6,7,4,5,3,2,1,0),
       (7,6,5,4,2,3,0,1)
   );
   inputInts: Array[0..99999] of Integer;
   
    function ch2index(ch: Char): Integer;
    begin
        ch2index := CONST_K;
        if ch = 'i' then ch2index := CONST_I;
        if ch = 'j' then ch2index := CONST_J;        
    end;

begin
    
    n := Length(s);
    solution := 'NO';
    for i:=1 to n do begin
        inputInts[i - 1] := ch2index(s[i]);
    end;
    right[n] := 0;
    for i := n - 1 downto 0 do begin
        right[i] := t[inputInts[i]][right[i+1]];
    end;
    left := 0;
    for i := 0 to n-1 do begin
        curr := 0;
        for j := i to n-1 do begin
            curr := t[curr][inputInts[j]];
            if (left = CONST_I) and (curr = CONST_J) and (right[j+1] = CONST_K) then begin
                solution := 'YES';
            end;
        end;
        left := t[left][inputInts[i]];
    end;
end;


var
   X, L : Integer;
   w : AnsiString;
   ww : AnsiString;
   T : Integer;
   i,j : Integer;
begin
    readln(T);
    for i := 1 to T do begin
        Readln(L,X);
        Readln(w);
        ww := '';
        for j := 1 to X do begin
            ww := ww + w;
        end;
        //writeln(ww);
        writeln('Case #',i,': ', solution(ww) );
    end
end.

The end

I qualified! This was a lot more fun and far more stressful than usual.

Google Codejam 2015 Qualification Round : Part 1: D small in Emily

It's another google codejam qualification round and honestly, these rounds are getting old. We are supposed to spend a whole day solving problems, between the too easy Small inputs and the impossible Large inputs. And what for? Once you get enough points for the cut-off it's not worth it. Unless you planned to be connected at 19:00 and try to solve the problems as fast as possible, then your rank might actually mean something...

One time I had position 29 at a qualification round. Impressive! Except it's all fake. I didn't even qualify to the third round that year.

I actually might have some rants to make about the formats used in our competitions. Did you know that google found winning programming competitions is correlated with bad work performance? It's SCIENCE. (Supposedly). Although us fans of these contests might like to think there is some sort of mistake in this result of Google's data mining. We cannot just really say it's not true, without doing any actual analysis of the data used and how the conclusion was made.

Anyway, so I want to qualify to round 1, but I was bored of qualifications rounds. So I decided to make them interesting by doing something different to my routine of using c++ and trying to get a perfect score. Instead, I wanted to make special language choices. Use only languages that I designed myself or that I didn't actually learn before the day of the round.

Emily

Once I decided to use special languages. I knew that one of the languages to use today was Emily. It's a relatively new languages, so that's a bonus. Also because o> f luck I've been seeing many previews of its development and finding them interesting. Honestly tho I kind of made this decision without thinking a lot...

The day of the round I noticed I should start learning this language. I figured out a couple of issues. Emily doesn't seem to have a way to read input. Fortunately, it does have the ability to write things. Unfortunately, only strings that you cannot process or floats. For some reason, Emily in its 0.1 version only has floating point numbers. That was going to be a bit of a problem.

My initial plan was to only use Emily and the language I will mention next; and hope to advance using only them. *After* getting an advancing score, I could actually try to use other languages just for fun. When I opened the problems, this seemed difficult. All problems seemed to need arrays, or actual string manipulation or 2D arrays, which are worse to do in Emily. Eventually I noticed Problem D.

Problem D: Ominus Omino - (The one with n-ominos)

statement

When I read this problem, it seemed that the small input can be solved with a bunch of conditionals. And the results are just one of two strings. Conditionals are good news because at least they can be implemented in Emily. And we can print fixed strings. I would only need to use my text editor's regexes to turn input files into code that calls my Emily solution.

To solve this problem (The small version) you can just try all variations of R and C, and just try by yourself, is it possible to pick an n-omino that stops the other player from winning?

This is how my notebook looked after this:

The rest was just implementing everything on Emily. It was HARD. So many conditions. The interesting thing about Emily is everything is an unary function. And I mean EVERYTHING. This includes objects and numbers. Unfortunately, I couldn't think of a good way to think advantage of this in this problem.

\version 0.1

# Hi, I am using a language called Emily, it is in version 0.1 :/
# https://bitbucket.org/runhello/emily/wiki/Home


ALWAYSAWAY = "GABRIEL"
CANMAKELOSE  = "RICHARD"

min = ^a ^b (
    (a < b) ? a : b
)
max = ^a ^b (
    (a > b) ? a : b
)

case4 = ^R ^C (
    ( (max R C) == 4 && ( (min R C) >= 3 ) ) ? ALWAYSAWAY : CANMAKELOSE
)

case3 = ^R ^C (
    a = max R C
    b = min R C
    
    maxIs4 = ( (b == 3) ? ALWAYSAWAY : CANMAKELOSE )
    maxIs3 = ( ((b == 3) || (b == 2) ) ? ALWAYSAWAY : CANMAKELOSE )
    
    (a == 4) ? maxIs4 : (  (a == 3) ? maxIs3 : CANMAKELOSE )
    
)

even = ^X (
    ( (X == 0) || (X == 2) || (X == 4) )
)

case2 = ^R ^C (
    ( (even R) || (even C) ) ? ALWAYSAWAY : CANMAKELOSE
)

# woops, here was my mistake
case1 = ^R ^C (
    ALWAYSAWAY
)


mode = ^X(
   ( X==1? case1: X==2? case2: X==3? case3: X==4? case4: null ) 
]

solution = ^X ^R ^C (
    ( mode(X) ) R C
)


# Examples
println: solution 2 2 2
println: solution 2 1 3
println: solution 4 4 1
println: solution 3 2 3

I couldn't help but get carried away with the functional programming here. Case4 is a function that solves the case for tetraominoes, Case3 for tetraominoes, etc. mode is a function that picks which function to use according to X. I wanted this to just be an array, but apparently that's currently a bit difficult to do.