2010 Online qualifications, second problem

We already solved the first problem of the 2010 google codejam Online qualifications. Let's see how the second problem can be solved with factor.

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

Remember, to use the generic solver, all 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

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

Let's define a word to calculate T. If you think about it carefully, T is actually the greatest common divisor of all the differences between two event times:

: all-differences ( seq -- diff )
  dup 2array [ first2 - ] product-map ;
: sgcd ( seq -- gcd )
  [ ] [ gcd nip ] map-reduce ;

: T ( seq -- T )
  all-differences sgcd ;

Now that we have T, we only need to take one of the times, and find out in how much time T divides it :

: next-multiple ( n T -- diff )
  2dup [ 1 - ] dip /i 1 + * swap - ;

All that's left is to read the input parameters and call our solution :

: read-case ( -- seq )
   read-ints rest ;
: do-case ( seq -- )
   [ first ] [ T ] bi next-multiple number>string write ;
M: gcj.qual.B solve-case
   drop read-case do-case ;

Here's the complete source file:

! Copyright (C) 2010 Jon Harper.
! See http://factorcode.org/license.txt for BSD license.
USING: gcj.common kernel sequences.product sequences
math.functions arrays math math.parser io ;
IN: gcj.qual.B
SINGLETON: gcj.qual.B
: all-differences ( seq -- diff )
dup 2array [ first2 - ] product-map ;
: sgcd ( seq -- gcd )
[ ] [ gcd nip ] map-reduce ;

: T ( seq -- T )
all-differences sgcd ;
: next-multiple ( n T -- diff )
2dup [ 1 - ] dip /i 1 + * swap - ;
: read-case ( -- seq )
read-ints rest ;
: do-case ( seq -- )
[ first ] [ T ] bi next-multiple number>string write ;
M: gcj.qual.B solve-case
drop read-case do-case ;

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 ;

Factoring the google codejam

This post will be about this year's (2010) google codejam.
May 8th was the online qualification round. Let's see how factor deals with the problems.

First of all, all google codejam problems so far have had the same structure:
give a file describing N instances of the problem, output the file giving the N solutions to these instances.
The input file starts with a line containing the value of N, and then the description of N problems.
The output file must contain exactly N lines, each line looking like this :
Case #X: SOLUTION,
where X goes from 1 to N and SOLUTION is the solution to this instance of the problem.

Let's create a vocabulary that automates all this.

First, we load the vocabularies that we need.

USING: formatting io io.encodings.utf8 io.files math.parser
math.ranges sequences splitting kernel ;
IN: gcj.common

Then, declare a generic word that has to read the description of a problem and print it's solution:

 GENERIC: solve-case ( problem-class -- )

We often have to read integers from files, so here are two useful words for reading 1 or many integers from a line:

: read-int ( -- n )
readln 10 base> ;
: read-ints ( -- ints )
readln " " split [ string>number ] map ;

We then need to be able to read the first line containing the number of cases, and for each case print the Case #X: SOLUTION line.

: solve-cases ( problem-class -- )
read-int [1,b]
[ "Case #%d: " printf solve-case nl ] with each ;

We also need a function to generate a new filename to which we write the solution : the solution to X.in will be stored in X.out :

: out-file ( in-file -- out-file )
"." split but-last ".out" suffix concat ;

Now, all we have to do is open the input file for reading, the output file for writting, and solve each case !

: solve-file ( problem-class file -- )
dup out-file utf8 [ utf8 [ solve-cases ] with-file-reader ] with-file-writer ;

Then if one wants to use this generic solver for the gcj, all one has to do is create a new problem-class, and implement the solve-case method.
In another file :

SINGLETON: gcj.anamefortheproblem
M: gcj.anamefortheproblem solve-case
! implement your case here
;

and call the generic part like this :

gcj.anamefortheproblem "path/to/input/file" solve-file

Here's the complete source file:

! Copyright (C) 2010 Jon Harper.
! See http://factorcode.org/license.txt for BSD license.
USING: formatting io io.encodings.utf8 io.files math.parser
math.ranges sequences splitting kernel ;
IN: gcj.common
GENERIC: solve-case ( problem-class -- )

: read-int ( -- n )
readln 10 base> ;
: read-ints ( -- ints )
readln " " split [ string>number ] map ;
: solve-cases ( problem-class -- )
read-int [1,b]
[ "Case #%d: " printf solve-case nl ] with each ;
: out-file ( in-file -- out-file )
"." split but-last ".out" suffix concat ;
: solve-file ( problem-class file -- )
dup out-file utf8 [ utf8 [ solve-cases ] with-file-reader ] with-file-writer ;