Advent of Code 2020 day22

https://adventofcode.com/2020/day/22

part1

Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10

のような2人のplayerのカードデッキが与えられる。
各playerは一番上のカードを出し合い、数字の大きい方が勝ちとしてデッキ末尾に取り込む。
というのを繰り返してどちらかがデッキが空になったら勝負が決する、というもの。
そのときの勝者のscore(最終デッキの下から順にi番目のカードの数値にiを掛けたものの合計)を求めよ、という問題。

そのままルール通りに実装してシミュレーションしてやれば良いだけ。VecDequeを使うのが良さそう。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> u32 {
        let mut player1 = true;
        let mut decks = (VecDeque::new(), VecDeque::new());
        for input in self.inputs.iter().filter(|&s| !s.is_empty()) {
            if input.starts_with("Player 2") {
                player1 = false;
            }
            if let Ok(card) = input.parse() {
                if player1 {
                    decks.0.push_back(card);
                } else {
                    decks.1.push_back(card)
                }
            }
        }
        while !decks.0.is_empty() && !decks.1.is_empty() {
            if let (Some(top1), Some(top2)) = (decks.0.pop_front(), decks.1.pop_front()) {
                if top1 > top2 {
                    decks.0.push_back(top1);
                    decks.0.push_back(top2);
                } else {
                    decks.1.push_back(top2);
                    decks.1.push_back(top1);
                }
            }
        }
        if decks.0.is_empty() {
            decks
                .1
                .iter()
                .rev()
                .enumerate()
                .map(|(i, card)| (i as u32 + 1) * card)
                .sum()
        } else {
            decks
                .0
                .iter()
                .rev()
                .enumerate()
                .map(|(i, card)| (i as u32 + 1) * card)
                .sum()
        }
    }
}

part2

player1が勝つための特殊なルールが追加された。

• 無限ループを防ぐため、同一game内で両者で同一のデッキ状態が出現した場合、即座にplayer1の勝ちとする (ひどい)
• 各roundで双方のカードの数字が自分のデッキの残り枚数より少ない場合、先頭からその枚数ずつcopyしたデッキで構成した新しいデッキを使ってsubgameに入る。このsubgameの勝者が、元のgameにおいて出していたカードの数字の大小にかかわらず、そのroundの勝者になる

というrecursiveなルールに。
やはりその通りに実装していけば良いだけ。同一デッキの検出のためにHashSetに各playerのデッキをkeyにして保存していきたいが、keyの作り方によって大きく性能が変わってくるようだ。何も考えずに format!("{:?}", decks) などを使っていたら6〜7倍遅かった。

code

use std::collections::{HashSet, VecDeque};
use std::io::{BufRead, BufReader};

struct Solution {
    decks: [VecDeque<u8>; 2],
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        let mut player1 = true;
        let mut decks = [VecDeque::new(), VecDeque::new()];
        for input in inputs.iter().filter(|&s| !s.is_empty()) {
            if input.starts_with("Player 2") {
                player1 = false;
            }
            if let Ok(card) = input.parse() {
                if player1 {
                    decks[0].push_back(card);
                } else {
                    decks[1].push_back(card)
                }
            }
        }
        Self { decks }
    }
    fn solve_1(&self) -> u32 {
        let mut decks = self.decks.clone();
        Solution::combat(&mut decks, false);
        decks
            .iter()
            .map(|deck| {
                deck.iter()
                    .rev()
                    .enumerate()
                    .map(|(i, &card)| (i as u32 + 1) * card as u32)
                    .sum::<u32>()
            })
            .sum()
    }
    fn solve_2(&self) -> u32 {
        let mut decks = self.decks.clone();
        Solution::combat(&mut decks, true);
        decks
            .iter()
            .map(|deck| {
                deck.iter()
                    .rev()
                    .enumerate()
                    .map(|(i, &card)| (i as u32 + 1) * card as u32)
                    .sum::<u32>()
            })
            .sum()
    }
    fn combat(decks: &mut [VecDeque<u8>; 2], recursive: bool) -> bool {
        let mut memo = HashSet::new();
        while decks.iter().all(|deck| !deck.is_empty()) {
            if recursive {
                let key = {
                    let mut v = Vec::with_capacity(decks[0].len() + decks[1].len() + 1);
                    v.extend(decks[0].iter());
                    v.push(0);
                    v.extend(decks[1].iter());
                    v
                };
                if memo.contains(&key) {
                    return true;
                }
                memo.insert(key);
            }
            if let (Some(top0), Some(top1)) = (decks[0].pop_front(), decks[1].pop_front()) {
                let player1_wins = if recursive
                    && top0 as usize <= decks[0].len()
                    && top1 as usize <= decks[1].len()
                {
                    let mut new_decks = [
                        decks[0].clone().into_iter().take(top0 as usize).collect(),
                        decks[1].clone().into_iter().take(top1 as usize).collect(),
                    ];
                    Solution::combat(&mut new_decks, recursive)
                } else {
                    top0 > top1
                };
                if player1_wins {
                    decks[0].push_back(top0);
                    decks[0].push_back(top1);
                } else {
                    decks[1].push_back(top1);
                    decks[1].push_back(top0);
                }
            }
        }
        decks[1].is_empty()
    }
}

fn main() {
    let solution = Solution::new(
        BufReader::new(std::io::stdin().lock())
            .lines()
            .filter_map(|line| line.ok())
            .collect(),
    );
    println!("{}", solution.solve_1());
    println!("{}", solution.solve_2());
}