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 ;