GCJ 2014 QR submission

README.md

This is my submission to Google Code Jam 2014 Qualification Round, using Rust programming language. The full description of problems is available at Google.

I've solved all 4 problems over the course of 5 1/2 hours (2014-04-13T05:10+09:00 through T10:40+09:00), which were longer than I've expected (possibly because I was sleepy at that time), but I've got the full credit (90 out of 90) anyway, so I guess it was not so bad move.

I tried to write the idiomatic Rust as much as possible, but not always mostly due to the time constraints. In particular, all program shares same boilerplates for the general structure and I/O which I really don't like. On the other hands there are several handy tricks (newtype structs, for example) to reduce the mistakes. To the end, every program is tested to some degree with Rust's built-in testing facility.

a.rs

use std::io;

enum Ret {
    Single(uint),
    Impossible,
    Multiple,
}

fn solve(tab1: &[uint], chosen1: uint,
         tab2: &[uint], chosen2: uint) -> Ret {
    assert_eq!(tab1.len(), 16);
    assert_eq!(tab2.len(), 16);
    let possible1 = tab1.slice(chosen1 * 4, chosen1 * 4 + 4);
    let possible2 = tab2.slice(chosen2 * 4, chosen2 * 4 + 4);
    let mut possible = Vec::new();
    for &i in possible1.iter() {
        for &j in possible2.iter() {
            if i == j { possible.push(i); break; }
        }
    }
    if possible.is_empty() {
        Impossible
    } else if possible.len() == 1 {
        Single(possible.as_slice()[0])
    } else {
        Multiple
    }
}

fn read_line(r: &mut Buffer) -> ~str {
    r.read_line().unwrap().trim().to_owned()
}

fn case(r: &mut Buffer) -> ~str {
    let chosen1: uint = from_str(read_line(r)).unwrap();
    let mut tab1 = Vec::new();
    for _ in range(0, 4) {
        tab1.extend(read_line(r).words().map(|s| from_str::<uint>(s).unwrap()));
    }
    let chosen2: uint = from_str(read_line(r)).unwrap();
    let mut tab2 = Vec::new();
    for _ in range(0, 4) {
        tab2.extend(read_line(r).words().map(|s| from_str::<uint>(s).unwrap()));
    }

    match solve(tab1.as_slice(), chosen1 - 1, tab2.as_slice(), chosen2 - 1) {
        Single(v) => format!("{}", v),
        Impossible => ~"Volunteer cheated!",
        Multiple => ~"Bad magician!",
    }
}

#[cfg(test)]
fn case_str(r: &str) -> ~str {
    let mut r_ = io::BufReader::new(r.as_bytes());
    case(&mut r_)
}
    
#[test]
fn test_sample() {
    assert_eq!(case_str("\
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
        "), ~"7");

    assert_eq!(case_str("\
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
        "), ~"Bad magician!");

    assert_eq!(case_str("\
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
        "), ~"Volunteer cheated!");
}

pub fn main() {
    let mut r = io::BufferedReader::new(io::stdin());
    let t: uint = from_str(read_line(&mut r)).unwrap();
    for i in range(1, t + 1) {
        println!(r"Case \#{}: {}", i, case(&mut r));
    }
}

b.rs

use std::io;
use std::f64;

static C_PER_SEC: f64 = 2.0;

// the basic strategy boils down to
// 1. buy n farms as soon as it hits c_to_f and
// 2. wait until target
//
// the total time to hit target
// = sum f=0..n-1 (c_to_f / (c_per_sec + c_per_f * f)) + target / (c_per_sec + c_per_f * f)

struct CperF(f64);
struct CtoF(f64);

fn next_time_to_farm(nfs: uint, CperF(c_per_f): CperF, CtoF(c_to_f): CtoF) -> f64 {
    c_to_f / (C_PER_SEC + c_per_f * nfs as f64)
}

fn next_time_to_target(nfs: uint, CperF(c_per_f): CperF, target: f64) -> f64 {
    target / (C_PER_SEC + c_per_f * nfs as f64)
}

fn time_to_target(nfs: uint, c_to_f: CtoF, c_per_f: CperF, target: f64) -> f64 {
    let mut time = 0.0;
    for f in range(0, nfs) { time += next_time_to_farm(f, c_per_f, c_to_f); }
    time += next_time_to_target(nfs, c_per_f, target);
    time
}

#[cfg(test)]
fn round3(x: f64) -> f64 {
    use std::num::Round;
    (x * 1000.0).round() / 1000.0
}

#[test]
fn test_ttt() {
    assert_eq!(round3(time_to_target(3, CtoF(500.0), CperF(4.0), 2000.0)), round3(526.1904762));
}

fn solve(c_to_f: CtoF, c_per_f: CperF, target: f64) -> f64 {
    let mut time = 0.0;
    let mut prev = f64::INFINITY;
    let mut nfs = 0;
    // not very sure that this will have a single minimum
    loop {
        let cur = time + next_time_to_target(nfs, c_per_f, target);
        if cur < prev {
            prev = cur;
        } else {
            return prev;
        }
        time += next_time_to_farm(nfs, c_per_f, c_to_f);
        nfs += 1;
    }
}

fn read_line(r: &mut Buffer) -> ~str {
    r.read_line().unwrap().trim().to_owned()
}

fn case(r: &mut Buffer) -> f64 {
    let nums: Vec<_> = read_line(r).words().map(|s| from_str::<f64>(s).unwrap()).collect();
    assert_eq!(nums.len(), 3);
    solve(CtoF(nums.as_slice()[0]), CperF(nums.as_slice()[1]), nums.as_slice()[2])
}

#[cfg(test)]
fn case_str(r: &str) -> f64 {
    let mut r_ = io::BufReader::new(r.as_bytes());
    case(&mut r_)
}

#[test]
fn test_sample() {
    assert_eq!(round3(case_str("30.0 1.0 2.0")), round3(1.0000000));
    assert_eq!(round3(case_str("30.0 2.0 100.0")), round3(39.1666667));
    assert_eq!(round3(case_str("30.50000 3.14159 1999.19990")), round3(63.9680013));
    assert_eq!(round3(case_str("500.0 4.0 2000.0")), round3(526.1904762));
}

#[test]
fn test_bigger() {
    println!("{}", case_str("1.0 1.0 100000.0"));
}

pub fn main() {
    let mut r = io::BufferedReader::new(io::stdin());
    let t: uint = from_str(read_line(&mut r)).unwrap();
    for i in range(1, t + 1) {
        println!(r"Case \#{}: {:.7}", i, case(&mut r));
    }
}

c.rs

// the one-click solution equals to
// - the click to the zero cell, contained in the only 8-neighbor-connected zeroes
// or
// - the click to the non-zero cell which is the only non-mine
//
// observation:
// with an exception of the latter case, the former case is equivalent to
// *erasing* mines with the consecutive (8-neighbor-connected) area of clicks
//
// ***...* <- this is not a solution (zeroes are connected, clicks are not)
// *...c.*    since clicking one `c` will reavel its neighbors but not others
// *.c...*
// *...***
//
// further observation:
// once you have a solution, you can transform the solution into the following form:
//
// c.............*
// ..............*
// .........******
// ......*********
// ......*********
// ***************
//
// i.e. you are finding some rectangle larger than 2x2, followed by another rectangle
//      which height is smaller than the prior one, and vice versa.
//      (the height of the final rectangle should be at least 2.)
//
// this gives a simple recurrence equation:
// C(n, m, k) returns true when n by m table with k *non-mines* is possible to solve by one click,
// assuming that the first one column is known to be non-mines and that column is duplicated right on that.
//
// - C(1, m, k) = (m >= 2) and (m = k)
//   c c c
//   . . .
//   . .
//   .
//
// - for n>=2, C(n, m, k) = (k >= m) and (m = k or C(n-1, 2, k-m) or C(n-1, 3, k-m) or ... or C(n-1, m, k-m))
//   c## c## c## c**
//   .## .## .## .**   note that ## covers one column which is already known to be non-mines,
//   .## .## .** .**   which is just fine since this assumption is included to the definition of C.
//   .## .** .** .**
//
// so that the final solution would be:
// possible(n, m, 0) = false        ********
// possible(n, m, 1) = true         c*******
// possible(1, m, k) = true iff 0 <= k <= m      c.**** c..*** c...** c....*
// possible(n, 1, k) = true iff 0 <= k <= n
// possible(n, m, k) for n>=2, m>=2, 1<k<n*m
// = C(n-1, m, k-m) or C(n-1, m-1, k-(m-1)) or ... or C(n-1, 2, k-2)
//   c##### c##### c#####
//   .##### .##### .#####   so that we *require* the first two columns are non-mines,
//   .##### .##### ******   as we first expected.
//   .##### ****** ******

extern crate collections;

use std::io;
use std::str;
use collections::HashMap;

#[deriving(Eq, TotalEq, Hash, Clone, Show)]
struct Subprob(uint, uint, uint); // n, m, k

#[deriving(Eq, Clone, Show)]
enum Trace {
    FillMine,
    FillThenAdvance(uint, uint, uint), // left, top, new_m
}

type Memo = HashMap<Subprob, Option<Trace>>;

fn solve_subproblem(memo: &mut Memo, Subprob(n, m, k): Subprob) -> Option<Trace> {
    //println!("solve_subproblem({}, {}, {}) = ...", n, m, k);
    let ret = if n <= 0 {
        None
    } else if n == 1 {
        if m >= 2 && k == n * m {
            Some(FillThenAdvance(n, m, 0))
        } else {
            None
        }
    } else { // n >= 2
        if k < m { return None; }

        // try the memo first
        match memo.find_copy(&Subprob(n, m, k)) {
            Some(maybe_trace) => return maybe_trace,
            None => {}
        }

        let mut ret = None;
        if m == k {
            ret = Some(FillThenAdvance(1, m, 0));
        }
        for i in range(2, m+1).rev() {
            let subret = solve_subproblem(memo, Subprob(n-1, i, k-m));
            if subret.is_some() {
                ret = Some(FillThenAdvance(1, m, i));
                break;
            }
        }
        memo.insert(Subprob(n, m, k), ret);
        ret
    };
    //println!("solve_subproblem({}, {}, {}) = {}", n, m, k, ret);
    ret
}

fn solve_problem(memo: &mut Memo, Subprob(n, m, k): Subprob) -> Option<Trace> {
    //println!("solve_problem({}, {}, {}) = ...", n, m, k);
    if k == 0 || k > n * m { return None; }
    if k == 1 { return Some(FillThenAdvance(1, 1, 0)); }
    if k == n * m { return Some(FillThenAdvance(n, m, 0)); }
    if n == 1 { return Some(FillThenAdvance(1, k, 0)); }
    if m == 1 { return Some(FillThenAdvance(k, 1, 0)); }

    for i in range(2, m+1).rev() {
        if k < i { continue; }
        let subret = solve_subproblem(memo, Subprob(n-1, i, k-i));
        if subret.is_some() {
            return Some(FillThenAdvance(1, i, i));
        }
    }
    None
}

fn solve(memo: &mut Memo, Subprob(n, m, k): Subprob) -> Option<Vec<Vec<char>>> {
    let ret = solve_problem(memo, Subprob(n, m, k));
    if ret.is_none() { return None; }
    let mut ret = ret.unwrap();

    let mut tab = Vec::from_fn(m, |_| Vec::from_elem(n, '*'));
    let mut x = 0;
    let mut k = k;
    loop {
        //println!("tracing: n={} m={} k={} x={} ret={}", n, m, k, x, ret);
        match ret {
            FillMine => break,
            FillThenAdvance(w, h, m) => {
                for i in range(0, h) {
                    for j in range(x, x+w) {
                        tab.as_mut_slice()[i].as_mut_slice()[j] = '.';
                    }
                }
                x += w;
                k -= w * h;
                if m == 0 { break; }
                ret = solve_subproblem(memo, Subprob(n - x, m, k)).unwrap();
            }
        }
    }
    assert!(k == 0);

    assert!(tab.as_slice()[0].as_slice()[0] == '.')
    tab.as_mut_slice()[0].as_mut_slice()[0] = 'c';

    Some(tab)
}

fn read_line(r: &mut Buffer) -> ~str {
    r.read_line().unwrap().trim().to_owned()
}

fn case(memo: &mut Memo, r: &mut Buffer) -> Option<Vec<Vec<char>>> {
    let nums: Vec<_> = read_line(r).words().map(|s| from_str::<uint>(s).unwrap()).collect();
    assert_eq!(nums.len(), 3);
    let nrows = nums.as_slice()[0];
    let ncols = nums.as_slice()[1];
    let nmines = nums.as_slice()[2];
    // we use somewhat different definitions for easier understanding
    solve(memo, Subprob(/*n*/ncols, /*m*/nrows, /*k*/ncols * nrows - nmines))
}

#[cfg(test)]
fn case_str(memo: &mut Memo, r: &str) -> Option<~str> {
    let mut r_ = io::BufReader::new(r.as_bytes());
    match case(memo, &mut r_) {
        Some(v) => {
            let mut s = ~"";
            for (i, line) in v.move_iter().enumerate() {
                if i > 0 { s.push_char('\n'); }
                s.push_str(str::from_chars(line.as_slice()));
            }
            Some(s)
        },
        None => None
    }
}

#[test]
fn test_sample() {
    let mut memo = HashMap::new();
    assert_eq!(case_str(&mut memo, "5 5 23"), None);
    assert_eq!(case_str(&mut memo, "3 1 1"), Some(~"c\n\
                                                    .\n\
                                                    *"));
    assert_eq!(case_str(&mut memo, "2 2 1"), None);
    assert_eq!(case_str(&mut memo, "4 7 3"), Some(~"c......\n\
                                                    .......\n\
                                                    ......*\n\
                                                    .....**"));
    assert_eq!(case_str(&mut memo, "10 10 82"), Some(~"c.********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       ..********\n\
                                                       **********"));
}

#[test]
fn test_small() {
    let mut memo = HashMap::new();
    assert_eq!(case_str(&mut memo, "5 5 0"), Some(~"c....\n\
                                                    .....\n\
                                                    .....\n\
                                                    .....\n\
                                                    ....."));
    assert_eq!(case_str(&mut memo, "5 5 1"), Some(~"c....\n\
                                                    .....\n\
                                                    .....\n\
                                                    .....\n\
                                                    ....*"));
    assert_eq!(case_str(&mut memo, "5 5 2"), Some(~"c....\n\
                                                    .....\n\
                                                    .....\n\
                                                    ....*\n\
                                                    ....*"));
    assert_eq!(case_str(&mut memo, "5 5 3"), Some(~"c....\n\
                                                    .....\n\
                                                    ....*\n\
                                                    ....*\n\
                                                    ....*"));
    assert_eq!(case_str(&mut memo, "5 5 4"), Some(~"c....\n\
                                                    .....\n\
                                                    ....*\n\
                                                    ....*\n\
                                                    ...**"));
    assert_eq!(case_str(&mut memo, "5 5 5"), Some(~"c...*\n\
                                                    ....*\n\
                                                    ....*\n\
                                                    ....*\n\
                                                    ....*"));
    assert_eq!(case_str(&mut memo, "5 5 9"), Some(~"c...*\n\
                                                    ....*\n\
                                                    ...**\n\
                                                    ...**\n\
                                                    ..***"));
    assert_eq!(case_str(&mut memo, "5 5 16"), Some(~"c..**\n\
                                                     ...**\n\
                                                     ...**\n\
                                                     *****\n\
                                                     *****"));
    assert_eq!(case_str(&mut memo, "5 5 17"), Some(~"c.***\n\
                                                     ..***\n\
                                                     ..***\n\
                                                     ..***\n\
                                                     *****"));
    assert_eq!(case_str(&mut memo, "5 5 18"), None);
    assert_eq!(case_str(&mut memo, "5 5 19"), Some(~"c.***\n\
                                                     ..***\n\
                                                     ..***\n\
                                                     *****\n\
                                                     *****"));
    assert_eq!(case_str(&mut memo, "5 5 20"), None);
    assert_eq!(case_str(&mut memo, "5 5 21"), Some(~"c.***\n\
                                                     ..***\n\
                                                     *****\n\
                                                     *****\n\
                                                     *****"));
    assert_eq!(case_str(&mut memo, "5 5 22"), None);
    assert_eq!(case_str(&mut memo, "5 5 24"), Some(~"c****\n\
                                                     *****\n\
                                                     *****\n\
                                                     *****\n\
                                                     *****"));
    assert_eq!(case_str(&mut memo, "5 5 25"), None);
}

#[test]
fn test_larger() {
    let mut memo = HashMap::new();
    for i in range(0, 2501) {
        case_str(&mut memo, format!("50 50 {}", i));
    }
}

pub fn main() {
    let mut r = io::BufferedReader::new(io::stdin());
    let t: uint = from_str(read_line(&mut r)).unwrap();
    let mut memo = HashMap::new();
    for i in range(1, t + 1) {
        println!(r"Case \#{}:", i);
        match case(&mut memo, &mut r) {
            Some(v) => {
                for line in v.move_iter() {
                    println!("{}", str::from_chars(line.as_slice()));
                }
            }
            None => {
                println!("Impossible");
            }
        }
    }
}

d.rs

// Ken's optimal strategy:
// give the lowest weight larger than told, if any. give the lowest weight otherwise.
// Ken has more information than Naomi, so can act as needed.
//
// Naomi's optimal strategy:
// give the lowest weight. Naomi can't control Ken's choices, so giving the highest weight
// does not help; it is better to eliminate the lower weights earlier so that
// Naomi can *force* the higher weights. this is highly dependant of the initial distribution.
//
// Naomi's deceiving strategy:
// give the lowest weight, and tell the Ken's highest weight plus/minus epsilon.
// plus if the chosen weight is higher than the Ken's smallest weight
// (so that Ken will choose the lowest weight and still won't realize the trick);
// minus otherwise (so that Naomi forces Ken to give the highest weight out anyway).

use std::io;

static EPSILON: f64 = 0.0000001;

fn ken_choice(ken: &[f64], told: f64) -> uint {
    for (i, &w) in ken.iter().enumerate() {
        if w > told { return i; }
    }
    0
}

fn naomi_choice(_naomi: &[f64]) -> uint {
    0
}

fn deceiving_naomi_choice(naomi: &[f64], ken: &[f64]) -> (uint, f64) {
    if naomi[0] > ken[0] {
        (0, ken[ken.len()-1] + EPSILON)
    } else {
        (0, ken[ken.len()-1] - EPSILON)
    }
}

fn simulate(mut naomi: Vec<f64>, mut ken: Vec<f64>) -> uint {
    let mut naomi_score = 0;
    while !naomi.is_empty() && !ken.is_empty() {
        let naomi_i = naomi_choice(naomi.as_slice());
        let naomi_w = naomi.remove(naomi_i).unwrap();
        let ken_i = ken_choice(ken.as_slice(), naomi_w);
        let ken_w = ken.remove(ken_i).unwrap();
        if naomi_w > ken_w {
            naomi_score += 1;
        }
    }
    naomi_score
}

fn deceive(mut naomi: Vec<f64>, mut ken: Vec<f64>) -> uint {
    let mut naomi_score = 0;
    while !naomi.is_empty() && !ken.is_empty() {
        let (naomi_i, naomi_w) = deceiving_naomi_choice(naomi.as_slice(), ken.as_slice());
        naomi.remove(naomi_i);
        let ken_i = ken_choice(ken.as_slice(), naomi_w);
        let ken_w = ken.remove(ken_i).unwrap();
        if naomi_w > ken_w {
            naomi_score += 1;
        }
    }
    naomi_score
}

fn solve(mut naomi: Vec<f64>, mut ken: Vec<f64>) -> (uint, uint) {
    naomi.sort_by(|&a, &b| if a > b {Greater} else if a < b {Less} else {Equal});
    ken.sort_by(|&a, &b| if a > b {Greater} else if a < b {Less} else {Equal});

    let opts = simulate(naomi.clone(), ken.clone());
    let optd = deceive(naomi.clone(), ken.clone());
    (optd, opts)
}

fn read_line(r: &mut Buffer) -> ~str {
    r.read_line().unwrap().trim().to_owned()
}

fn case(r: &mut Buffer) -> (uint, uint) {
    let nweights: uint = from_str(read_line(r)).unwrap();
    let naomi: Vec<_> = read_line(r).words().map(|s| from_str::<f64>(s).unwrap()).collect();
    let ken: Vec<_> = read_line(r).words().map(|s| from_str::<f64>(s).unwrap()).collect();
    assert_eq!(naomi.len(), nweights);
    assert_eq!(ken.len(), nweights);
    solve(naomi, ken)
}

#[cfg(test)]
fn case_str(r: &str) -> (uint, uint) {
    let mut r_ = io::BufReader::new(r.as_bytes());
    case(&mut r_)
}

#[test]
fn test_sample() {
    assert_eq!(case_str("1\n\
                         0.5\n\
                         0.6"), (0, 0));
    assert_eq!(case_str("2\n\
                         0.7 0.2\n\
                         0.8 0.3"), (1, 0));
    assert_eq!(case_str("3\n\
                         0.5 0.1 0.9\n\
                         0.6 0.4 0.3"), (2, 1));
    assert_eq!(case_str("9\n\
                         0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899\n\
                         0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458"), (8, 4));
}

pub fn main() {
    let mut r = io::BufferedReader::new(io::stdin());
    let t: uint = from_str(read_line(&mut r)).unwrap();
    for i in range(1, t + 1) {
        let (optd, opts) = case(&mut r);
        println!(r"Case \#{}: {} {}", i, optd, opts);
    }
}