day22.rs

/*
   Part 1 was easy enough by simply appplying the different shuffles.
   However, for part 2 the solution in the function part_2 will probably
   take a number of years to complete. I was hoping that there would be a
   loop somewhere so that you could determine the answer based on position
   in the loop. But there does not seem to be a loop at least not one that
   is reached in a reasonable time. 

   I need more mathematical puzzle practice, I guess, to handle these kind of
   questions. I might get back and do a solution based on the function
   transformation that is needed (see Reddit) to solve part_2.

*/
use std::io::{BufReader, BufRead};
use std::fs::File;

use std::collections::HashMap;

fn new_deck(deck_size: usize) -> Vec<usize> {
    (0..deck_size).collect()
}

fn deal_into_new_stack(deck: Vec<usize>) -> Vec<usize> {
    let mut new_deck = deck.clone();
    new_deck.reverse();
    new_deck
}

fn  reverse_deal_into_new_stack(deck_size: i64, card_pos: i64) -> i64  {
    (deck_size - 1) - card_pos
}

fn cut(deck: Vec<usize>, n: i64) -> Vec<usize> {
    let mut new_deck: Vec<usize> = vec!();
    let parts = if n > 0 {
        deck.split_at(n as usize)
    } else {
        deck.split_at(deck.len() - (-n as usize))
    };
    let mut p1: Vec<usize> = (parts.0).iter().map(|x| *x).collect();
    let mut p2: Vec<usize> = (parts.1).iter().map(|x| *x).collect();
    new_deck.append(&mut p2);
    new_deck.append(&mut p1);
    new_deck
}

fn reverse_cut(deck_size: i64, card_pos: i64, n: i64) -> i64  {
    if n > 0 {
        if card_pos < deck_size - n {
            card_pos + n
        } else {
            card_pos - (deck_size - n)
        }
    } else {
        reverse_cut(deck_size, card_pos, deck_size + n)
    }
}

fn deal(deck: &mut Vec<usize>, n: usize) -> Vec<usize> {
    let mut new_deck: Vec<usize> = vec!();
    new_deck.resize(deck.len(), 999999);
    let mut cursor = 0;
    while !deck.is_empty() {
        let card = deck.remove(0);
        new_deck[cursor] = card;
        cursor += n;
        if cursor >= new_deck.len() {
            cursor = cursor - new_deck.len()
        }
    }
    new_deck
}

enum Shuffle {
    DealIntoNewStack,
    Cut(i64),
    Deal(usize)
}

fn shuffle(deck: Vec<usize>, shuffle_order: Vec<Shuffle>) -> Vec<usize> {
    let mut new_deck: Vec<usize> = deck.clone();
    for shuffle in shuffle_order {
        match shuffle {
            Shuffle::DealIntoNewStack => { new_deck = deal_into_new_stack(new_deck)},
            Shuffle::Cut(n) => { new_deck = cut(new_deck, n)},
            Shuffle::Deal(n) => { new_deck = deal(&mut new_deck, n) },
        }
    }
    new_deck
} 

fn load_shuffle_order(shuffle_file: &String) -> Vec<Shuffle> {
    let mut shuffle_order: Vec<Shuffle> = vec!();
    let file = File::open(shuffle_file).expect("Could not open shuffle file!");
    let reader = BufReader::new(file);
    for line in reader.lines() {
        let line = line.expect("No string there.");
        if &line[..3] == "cut" {
            let n: i64 = line[4..].parse().unwrap();
            shuffle_order.push(Shuffle::Cut(n))
        } else if &line[..19] == "deal into new stack" {
            shuffle_order.push(Shuffle::DealIntoNewStack)
        } else if &line[..19] == "deal with increment" {
            let n: usize = line[20..].parse().unwrap();
            shuffle_order.push(Shuffle::Deal(n))
        }
    }
    shuffle_order
}

fn main() {
    part_1();
}

fn reverse_shuffle(deck_size: i64, final_card_pos: i64, shuffle_order: &Vec<Shuffle>) -> i64 {
    let mut prev_pos = final_card_pos;
    let mut memos: HashMap<(i64, i64), i64> = HashMap::new();
    for shuffle in shuffle_order {
        match shuffle {
            Shuffle::DealIntoNewStack => {prev_pos = reverse_deal_into_new_stack(deck_size, prev_pos) },
            Shuffle::Cut(n) => {prev_pos = reverse_cut(deck_size, prev_pos, *n)},
            Shuffle::Deal(n) => {prev_pos = reverse_deal(deck_size, prev_pos, *n as i64, &mut memos) },
        }
    }
    prev_pos
} 

fn part_2() {
    let shuffle_file = "shuffles".to_string();
    let mut shuffle_order = load_shuffle_order(&shuffle_file);
    shuffle_order.reverse();
    let mut current_pos: i64 = 2020;
    let n_shuffles: i64 = 101741582076661;
    for _ in 0..n_shuffles {
        let new_current_pos = reverse_shuffle(119315717514047, current_pos, &shuffle_order);
        current_pos = new_current_pos;
    }
    println!("The card at position 2020 is {}", current_pos);
}

fn part_1() {
    let shuffle_file = "shuffles".to_string();
    let shuffle_order = load_shuffle_order(&shuffle_file);
    let deck = new_deck(10007);
    let deck = shuffle(deck, shuffle_order);
    let answer = deck.iter().position(|x| *x == 2019).unwrap();
    println!("The card 2019 is at position: {}", answer);
}

fn reverse_deal(deck_size: i64, card_pos: i64, n: i64, memos: &mut HashMap<(i64, i64), i64>) -> i64  {
    let memo_key = (card_pos, n);
    if memos.contains_key(&memo_key) {
        println!("Loop detected");
        return memos[&memo_key];
    }
    
    // TODO: There should be a better way to do this
    let required_start_pos = card_pos % n;
    let mut current_start_pos = 0;
    let mut acc_pos = 0;
    while current_start_pos != required_start_pos {
        // println!("current_start_pos={} acc_pos={}", current_start_pos, acc_pos);
        acc_pos += 1 + (deck_size - current_start_pos) / n;
        current_start_pos = n - (deck_size - current_start_pos) % n;
    }
    let prev_pos = acc_pos + (card_pos - required_start_pos)/n;
    memos.insert(memo_key, prev_pos);
    prev_pos
}


#[cfg(test)]
mod tests {
    use super::*;

#[test]
    fn test_reverse_deal() {
        let mut deck = new_deck(3);
        let deck = deal(&mut deck, 2);
        let mut memos: HashMap<(i64, i64), i64> = HashMap::new();
        let card = reverse_deal(3, 0, 2, &mut memos);
        assert_eq!(deck[0] as i64, card);
        let card = reverse_deal(3, 1, 2, &mut memos);
        assert_eq!(deck[1] as i64, card);
        let card = reverse_deal(3, 2, 2, &mut memos);
        assert_eq!(deck[2] as i64, card);
    }

    #[test]
    fn test_deal_into_new_stack() {
        let deck = new_deck(10);
        assert_eq!(vec!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), deck);
        let deck = deal_into_new_stack(deck);
        assert_eq!(vec!(9, 8, 7, 6, 5, 4, 3, 2, 1, 0), deck);
    }

    #[test]
    fn test_reverse_deal_into_new_stack() {
        let card = reverse_deal_into_new_stack(10, 2);
        assert_eq!(7, card)
    }

    #[test]
    fn test_cut() {
        let deck = new_deck(10);
        let deck = cut(deck, 3);
        assert_eq!(vec!(3, 4, 5, 6, 7, 8, 9, 0, 1, 2), deck);
    }

    #[test]
    fn test_reverse_cut() {
        let card = reverse_cut(10, 2, 3);
        assert_eq!(5, card);
        let card = reverse_cut(10, 1, 3);
        assert_eq!(4, card);
        let card = reverse_cut(10, 8, 3);
        assert_eq!(1, card);
    }

    #[test]
    fn test_negative_cut() {
        let deck = new_deck(10);
        let deck = cut(deck, -4);
        assert_eq!(vec!(6, 7, 8, 9, 0, 1, 2, 3, 4, 5), deck);
    }

    #[test]
    fn test_reverse_negative_cut() {
        let card = reverse_cut(10, 2, -4);
        assert_eq!(8, card);
        let card = reverse_cut(10, 1, -4);
        assert_eq!(7, card);
        let card = reverse_cut(10, 8, -4);
        assert_eq!(4, card);
    }
    #[test]
    fn test_deal() {
        let mut deck = new_deck(10);
        let deck = deal(&mut deck, 3);
        assert_eq!(vec!(0, 7, 4, 1, 8, 5, 2, 9, 6, 3), deck);
    }


    #[test]
    fn test_reverse_deal_fancy() {
        let mut deck = new_deck(10);
        let deck = deal(&mut deck, 7);
        println!("Deck={:?}", deck);
        let mut memos: HashMap<(i64, i64), i64> = HashMap::new();
        let card = reverse_deal(10, 2, 7, &mut memos);
        assert_eq!(deck[2] as i64, card);
    }

    #[test]
    fn test_input1() {
        let shuffle_file = "test1".to_string();
        let shuffle_order = load_shuffle_order(&shuffle_file);
        let deck = new_deck(10);
        let deck = shuffle(deck, shuffle_order);
        assert_eq!(vec!(0, 3, 6, 9, 2, 5, 8, 1, 4, 7), deck);
    }

    #[test]
    fn test_reverse1() {
        let shuffle_file = "test1".to_string();
        let mut shuffle_order = load_shuffle_order(&shuffle_file);
        shuffle_order.reverse();
        let card = reverse_shuffle(10, 1, &shuffle_order);
        assert_eq!(3, card);
    }

    #[test]
    fn test_input2() {
        let shuffle_file = "test2".to_string();
        let shuffle_order = load_shuffle_order(&shuffle_file);
        let deck = new_deck(10);
        let deck = shuffle(deck, shuffle_order);
        assert_eq!(vec!(3, 0, 7, 4, 1, 8, 5, 2, 9, 6), deck);
    }
    #[test]
    fn test_reverse2() {
        let shuffle_file = "test2".to_string();
        let mut shuffle_order = load_shuffle_order(&shuffle_file);
        shuffle_order.reverse();
        let card = reverse_shuffle(10, 1, &shuffle_order);
        assert_eq!(0, card);
    }

    #[test]
    fn test_input3() {
        let shuffle_file = "test3".to_string();
        let shuffle_order = load_shuffle_order(&shuffle_file);
        let deck = new_deck(10);
        let deck = shuffle(deck, shuffle_order);
        assert_eq!(vec!(6, 3, 0, 7, 4, 1, 8, 5, 2, 9), deck);
    }

    #[test]
    fn test_reverse3() {
        let shuffle_file = "test3".to_string();
        let mut shuffle_order = load_shuffle_order(&shuffle_file);
        shuffle_order.reverse();
        let card = reverse_shuffle(10, 1, &shuffle_order);
        assert_eq!(3, card);
    }

    #[test]
    fn test_input4() {
        let shuffle_file = "test4".to_string();
        let shuffle_order = load_shuffle_order(&shuffle_file);
        let deck = new_deck(10);
        let deck = shuffle(deck, shuffle_order);
        assert_eq!(vec!(9, 2, 5, 8, 1, 4, 7, 0, 3, 6), deck);
    }

    #[test]
    fn test_reverse4() {
        let shuffle_file = "test4".to_string();
        let mut shuffle_order = load_shuffle_order(&shuffle_file);
        shuffle_order.reverse();
        let card = reverse_shuffle(10, 1, &shuffle_order);
        assert_eq!(2, card);
        let card = reverse_shuffle(10, 8, &shuffle_order);
        assert_eq!(3, card);
    }
}