Google code jam. Qualification Round 2010.

Решил вчера поучаствовать в отборочном раунде code jam. Раунд состоял из трех достаточно простых задач, мне хватило терпения только на первые две, хотя как решать третью я тоже понял :)

Первая задача, snaper chain – самая простая, достаточно понять, что состояние snapper-ов в цепочке после K щелчков, будет эквивалентно двоичному представлению числа K. Вот мое решение на F#:

open System
open System.IO

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()

let inputSeq:seq<int*int> = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let lst = line.Split(' ')
        yield int lst.[0], int lst.[1]
    }

// write the output file
let snapperState n k =
    let l = 2 <<< n - 1
    let m = k % l
    match l - 1 = m with
    | true  -> "ON"
    | false -> "OFF"

let mutable caseIx = 1
for n, k in inputSeq do
    let line = sprintf "Case #%d: %s" caseIx <| snapperState n k
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Вторая задача, fair warning – намного сложнее. Суть задачи – в следующем, у нас есть набор чисел – t1, t2,.. tn. Нужно найти такое значение y, для которого справедливо условие – (Y + ti) mod T = 0, для любого i < n. Причем, T – должно быть максимально возможным. Помимо этого, исходные данные могут содержать большие числа, так и написано:

64 bits will not save you. You have been warned.

Я использовал следующий алгоритм – сначала массив чисел ti сортируется, затем – нормализуется (из каждого элемента вычитается значение минимального элемента); далее, вычисляется наибольший общий делитель элементов массива(функция gcdv), в результате чего мы получаем значение T, после чего достаточно легко рассчитать значение Y. Вот мое решение:

open System
open System.IO
open System.Numerics

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()
printfn "N: %d" testsNum

let inputSeq = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let strlst = line.Split(' ').[1..]
        let intlst = Array.map (fun x -> BigInteger.Parse(x)) strlst
        yield intlst
    }

let gcd a b = BigInteger.GreatestCommonDivisor(a, b)

let gcdv vals = Array.reduce gcd vals
            
let getDiff events = 
    if Array.length events < 2 then
        failwith "error in getDiff, events array is to small"
    Array.sortInPlace events
    let min = events.[0]
    min, Array.map (fun x -> x - min) events.[1..]

let (|Length|) arr = Array.length arr

let mutable caseIx = 1

for events in inputSeq do

    let result =
        match events with
        | Length 0
        | Length 1 -> 0I
        | _ -> 
            let min, diff = getDiff events 
            let factor = gcdv diff
            if min % factor = 0I then 0I
            else factor - (min % factor)

    let line = sprintf "Case #%d: %s" caseIx <| result.ToString()
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Кстати, сразу после начала раунда я обнаружил что на моем домашнем компьютере нет ни Visual Studio, ни интерпретатора python-a, даже несчастного с++ компиялтора нет. Вышел из положения скачав F# CTP, код набирал в vim. F# interpreter – очень удобная штука, я его использовал в интерактивном режиме, в качестве REPL, а так-же для запуска своей писанины :)

F# и циклические зависимости.

Предметом разговора сегодня будет язык программирования F#, который вызвал у меня неслабую зависимость. Я не буду пока рассказывать чем именно, всему свое время. Вместо этого, я хочу обсудить некоторые “недостатки”.

Главный “недостаток” этого языка программирования, если конечно судить по записям в блогах и сообщениям на форумах – довольно странный для .NET разработчиков механизм компиляции. В C# или VB.NET, порядок компиляции не имеет значения, программист вообще не имеет возможности на него влиять. Мало того, эти языки позволяют с легкостью делать подобное:

class Foo
{  
  private Bar bar;  
  ...
}
class Bar
{  
  private Foo foo;
  ...
}

То есть, определять классы, которые зависят друг от друга (являются взаимно рекурсивными).  Классы Foo и Bar могут быть в разных файлах, это не имеет значения, компилятор C# во всем прекрасно разберется.

В случае F#, все не так просто. Во первых, файлы проекта компилируются в строго определенном порядке. И от этого порядка зависит – будет ли проект скомпилирован, или нет. Во вторых, этот порядок определяется программистом. В каком порядке следуют файлы в проекте, в том они и будут компилироваться, в этом порядке и будет работать вывод типов. Если класс Bar зависит от класса Foo, то файл, в котором определен класс Foo должен компилироваться раньше чем файл, в котором определен класс Bar. Предыдущий пример, на F# будет выглядеть так:

type Foo =
    val bar : Bar
    ...
and Bar =
    val foo : Foo
    ...

обратите внимание на ключевое слово and – с его помощью в F# определяются взаимно рекурсивные типы. При этом, оба класса должны находится в одном файле.

Естественно, это вызывает бурю гневных постов в блогах и на форумах, так-как очень далеко от подхода, используемого в C# и VB.NET.

Так вот, на самом деле – это очень круто! Круто, потому-что нам пришлось явным образом указать – какие классы являются взаимно рекурсивными. Это означает, что внести в код циклическую зависимость можно только специально.

Явный порядок компиляции – одна из моих любимых особенностей F#, так как она заставляет программиста заранее продумать архитектуру проекта. Допустим у нас есть большой проект, мы условно разделили его на два слоя – представление и бизнес логику. Классы из presentation слоя – используют классы из business layer-a, а тот в свою очередь – никак не зависит от представления. Если все это добро находится в одной сборке, то нам ничто не мешает использовать код из presentation слоя в бизнес логике. Это будет ошибкой проектирования, тем не менее, многие языки программирования позволяют с легкостью это сделать. С F# этот номер не пройдет, так как файлы слоя представления будут компилироваться позже файлов, содержащих бизнес логику.

Другое преимущество этого подхода состоит в том, что алгоритм вывода типов становится намного проще, а следовательно работает очень быстро. В частности, благодаря этому, подсказки и сообщения об ошибках в IDE появляются практически мгновенно, что не может не радовать :)