2010 Online qualifications, first problem

Let's see how we can solve the first problem with factor. We will use the generic vocabulary that handles gcj problems described in a earlier post.

Here's where you can read the problem description : http://code.google.com/codejam/contest/dashboard?c=433101#

What we have to do is implement the solve-case method on a new problem-class. Let's import a few vocabularies and declare our new problem-class

USING: math kernel gcj.common sequences io ;
IN: gcj.qual.A

SINGLETON: gcj.qual.A

Let's now we read the input file:

: read-case ( -- n k )
read-ints first2 ;

Now, given the input parameters, let's solve the problem. If you think carefully, you'll see that this problem is equivalent to calculating if k+1 is a multiple of 2**n. Here's the word that does just that :

: multiple-of-2**n-1? ( k n -- ? )
[ 1 + ] [ 2^ ] bi* mod zero? ;

All we have to do now is write the correct answer ("ON" or "OFF") :

: do-case ( n k -- )
swap multiple-of-2**n-1? "ON" "OFF" ? write ;
M: gcj.snapper solve-case
drop read-case do-case ;

This solves the small and large input sets of the first problem of the google codejam 2010 online qualification round.

Here's the complete source file :

! Copyright (C) 2010 Jon Harper.
! See http://factorcode.org/license.txt for BSD license.
USING: math kernel gcj.common sequences io ;
IN: gcj.qual.A

SINGLETON: gcj.snapper
: k2**n-1? ( a n -- ? )
[ 1 + ] [ 2^ ] bi* mod zero? ;

: read-case ( -- n k )
 read-ints first2 ;
: do-case ( n k -- )
 swap k2**n-1? "ON" "OFF" ? write ;
M: gcj.snapper solve-case
 drop read-case do-case ;