242 Hard

main.rs

extern crate rand;

use std::cmp;
use std::env;
use std::fmt;
use rand::{thread_rng, Rng};

#[derive(PartialEq,Clone)]
enum Colors {
    Black,
    Yellow,
    Red,
    Purple
}

static COLORS: [Colors; 4] = [Colors::Black, Colors::Yellow, Colors::Red, Colors::Purple];

#[derive(Clone)]
struct Tile {
    color: Colors,
    number: u8
}

impl fmt::Display for Tile {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let color_tag = match self.color {
            Colors::Black => "B",
            Colors::Yellow => "Y",
            Colors::Red => "R",
            Colors::Purple => "P"
        };
        return write!(f, "{}{}", color_tag, self.number);
    }
}

impl cmp::PartialEq for Tile {
    fn eq(&self, other: &Self) -> bool {
        return self.number == other.number && self.color == other.color;
    }

    fn ne(&self, other: &Self) -> bool {
        return !self.eq(other);
    }
}

fn main() {
    // Build tilebag
    let mut tilebag = vec![];
    for _ in 0..2 {
        for i in 1..14 {
            for c in COLORS.iter().cloned() {
                tilebag.push(Tile {
                    color: c,
                    number: i
                });
            }
        }
    }

    //Get our starting hand from the command line
    let mut my_tiles = vec![];
    let args: Vec<String> = env::args().skip(1).collect();
    assert!(args.len() == 14, "Must receive 14 starting tiles as input");

    for arg in args.iter() {
        let parts = arg.split_at(1);
        let color = match parts.0 {
            "B" => Ok(Colors::Black),
            "Y" => Ok(Colors::Yellow),
            "R" => Ok(Colors::Red),
            "P" => Ok(Colors::Purple),
            _ => Err("Bad color input")
        }.unwrap();
        // Pull any tiles we're given out of the tilebag
        let tile = tilebag.iter().position(|i| i.color == color && i.number == parts.1.parse::<u8>().unwrap()).unwrap();
        my_tiles.push(tilebag.remove(tile));
    }

    // See if we have any sets
    let mut valid_set;
    let mut rng = thread_rng();
    while {
        valid_set = find_sets(&mut my_tiles);
        valid_set.is_none()
    } {
        // Draw random tiles until we find a valid set
        let tile = rng.gen_range(0, tilebag.len());
        let tile = tilebag.remove(tile);
        println!("Drawing: {}", tile);
        my_tiles.push(tile);
    }

    println!("Found a valid set:");
    for i in valid_set.unwrap() {
        print!("{} ", i);
    }
    println!(""); // Truncate our line of output
}

fn find_sets(hand: &mut Vec<Tile>) -> Option<Vec<Tile>> {
    #[derive(Clone)]
    struct TileSet {
        tiles: Vec<Tile>,
        sum: u16
    }

    // We sort once because we'll be needing it sorted for every search we do
    hand.sort_by(|a, b| a.number.cmp(&b.number));

    // Search for possible runs
    let mut possible_runs: Vec<TileSet> = vec![];
    let mut current_set: TileSet = TileSet {
        tiles: vec![],
        sum: 0
    };
    for c in COLORS.iter().cloned() {
        let mut temp_hand = hand.clone();
        temp_hand.retain(|i| i.color == c);
        temp_hand.dedup();
        let mut last: Option<Tile> = None;
        for i in temp_hand {
            if last.is_some() && last.clone().unwrap().number + 1 == i.number {
                current_set.tiles.push(i.clone());
                current_set.sum += i.number as u16;
                if current_set.tiles.len() >= 3 {
                    possible_runs.push(current_set.clone());
                }
            } else {
                current_set = TileSet {
                    tiles: vec![i.clone()],
                    sum: i.number as u16
                };
            }
            last = Some(i.clone());
        }
    }

    // Exit early if we have a run with 4 or more tiles in it
    let mut best_count = 0;
    let mut best_index = None;
    for (index, i) in possible_runs.iter().enumerate() {
        if i.tiles.len() >= 4 && i.sum >= 30 && i.tiles.len() > best_count {
            best_count = i.tiles.len();
            best_index = Some(index);
        }
    }
    if best_index.is_some() {
        return Some(possible_runs[best_index.unwrap()].tiles.clone());
    }

    // Search for possible groups
    let mut possible_groups: Vec<TileSet> = vec![];
    let mut last_number = 0;
    let temp_hand = hand.clone();
    for i in temp_hand {
        if i.number != last_number {
            if current_set.tiles.len() >= 3 {
                possible_groups.push(current_set.clone());
            }
            last_number = i.number;
            current_set = TileSet {
                tiles: vec![i.clone()],
                sum: i.number as u16
            };
        } else if !current_set.tiles.contains(&i) {
            current_set.tiles.push(i.clone());
            current_set.sum += i.number as u16;
        }
    }

    // Let's see if any of our groups are usable on their own
    best_index = None;
    for (index, i) in possible_groups.iter().enumerate() {
        if i.tiles.len() >= 3 && i.sum >= 30 {
            best_index = Some(index);
            if i.tiles.len() == 4 {
                break;
            }
        }
    }
    if best_index.is_some() {
        return Some(possible_groups[best_index.unwrap()].tiles.clone());
    }

    // Let's see if any of our runs of length 3 are usable
    best_count = 0;
    best_index = None;
    for (index, i) in possible_runs.iter().enumerate() {
        if i.tiles.len() >= 3 && i.sum >= 30 {
            best_count = i.tiles.len();
            best_index = Some(index);
            break;
        }
    }
    if best_count >= 3 {
        return Some(possible_runs[best_index.unwrap()].tiles.clone());
    }

    // Now we'll look for combinations. Last resort because this is slow.
    best_count = 0;
    let mut best_run = None;
    let mut best_group = None;
    for (group, i) in possible_groups.iter().enumerate() {
        for (run, j) in possible_runs.iter().enumerate() {
            let mut duplicate = false;
            for tile in i.tiles.iter().cloned() {
                if j.tiles.contains(&tile) {
                    duplicate = true;
                    break;
                }
            }
            if duplicate {
                continue;
            }
            if i.tiles.len() >= 3 && j.tiles.len() >= 3 && i.sum + j.sum >= 30 {
                if best_count >= i.tiles.len() + j.tiles.len() {
                    continue;
                }
                best_count = i.tiles.len() + j.tiles.len();
                best_run = Some(run);
                best_group = Some(group);
            }
        }
    }
    if best_run.is_some() && best_group.is_some() {
        let mut result = possible_runs[best_run.unwrap()].tiles.clone();
        result.append(&mut possible_groups[best_group.unwrap()].tiles);
        return Some(result);
    }

    return None;
}