Advent of Code 2020 day23

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

part1

389125467

のような入力が与えられる。1から9までのカップをこの順番に時計回りに並べ、次の規則で動かしていく。

• 入力の最初のカップをcurrent cupとする
• current cupから時計回りに見て3つを取り出す
• current cupの数値から1だけ引いた数値のcupをdestination cupとする
  • 1引いた数値のものが取り出されている3つに含まれていたら さらに1引いていく
  • 1を引き続けて最低値に到達したら次は最大値に折り返される
• 取り出した3つのcupをdestination cupから時計回りにそのままの順番で移動する
• current cupから時計回りで隣のものを次のcurrent cupとする

これを100回繰り返したとき、1のカップから時計回りに見ていくとどういう順番でカップが並ぶか？という問題。
上の例の場合は67384529になる。

9個のカップを100回動かす程度なら、Vecに入れて順番にremoveとinsertを繰り返していっても問題なくsimulateできる。

struct Solution {
    cups: Vec<u8>,
}

impl Solution {
    fn new(input: String) -> Self {
        Self {
            cups: input.as_bytes().iter().map(|&b| b - b'0').collect(),
        }
    }
    fn solve_1(&self) -> String {
        let mut cups = self.cups.clone();
        for _ in 0..100 {
            let current = cups.remove(0);
            let pickup: Vec<u8> = (0..3).map(|_| cups.remove(0)).collect();
            let mut destination = if current == 1 { 9 } else { current - 1 };
            while pickup.contains(&destination) {
                destination = if destination == 1 { 9 } else { destination - 1 };
            }
            if let Some(p) = cups.iter().position(|&x| x == destination) {
                cups.splice(p + 1..p + 1, pickup);
            }
            cups.push(current);
        }
        while cups[0] != 1 {
            let first = cups.remove(0);
            cups.push(first);
        }
        cups.iter().skip(1).map(|&u| (u + b'0') as char).collect()
    }
}

part2

なんと、カップは9個だけではなく100万個だった…！ 最初の幾つか(入力の9個)はその順番で並べられ、それ以降は順番に続きが並べられる、とのこと。そして動かす回数も100回ではなく1000万回！

さすがにこれはVecのremoveやinsertではまったく計算が終わらない。
LinkedListを繋ぎ直していく、というのが正しいアプローチになりそう。

とはいえRustでそういった操作はわりと面倒…。
実際の操作をよく考えてみると、

current cup -> [picked up 3 cups] -> next1 -> ... -> destination cup -> next2 -> 

という順番で繋がっているものを

current cup -> next1 -> ... -> destination cup -> [picked up 3 cups] -> next2 -> 

と繋ぎ直せば良いだけなので、
この操作をする際には「あるカップのすぐ時計回り方向の隣にあるカップの番号」だけ分かっていれば良い。

current cupから取り上げる3つはcurrent cupを起点に順番に3つ辿れば良いだけ。
そのさらに次のcupが、繋ぎ直した後にcurrent cupの隣(次)に来るべきものになる。
destination cupの次のcupが、繋ぎ直した後に取り上げた3つの隣(次)に来るべきもの、になる。

ということでHashMapなどで「指定した番号のcupから 次に並ぶcupの番号」を引けるようにすれば、それを書き換えていくだけで操作が可能になる。
実際には1000万回操作するのにHashMapではやはり計算が重いのでVecに突っ込んでいくのが早い。

code

impl Solution {
    fn new(input: String) -> Self {
        Self {
            cups: input
                .as_bytes()
                .iter()
                .map(|&b| (b - b'0') as u32)
                .collect(),
        }
    }
    fn solve_1(&self) -> String {
        let cups = self.game(9, 100);
        let mut ret = Vec::new();
        let mut cup = 1;
        for _ in 0..8 {
            ret.push(cups[cup].to_string());
            cup = cups[cup] as usize;
        }
        ret.concat()
    }
    fn solve_2(&self) -> u64 {
        let cups = self.game(1_000_000, 10_000_000);
        let mut ret = 1;
        let mut cup = 1;
        for _ in 0..2 {
            ret *= cups[cup] as u64;
            cup = cups[cup] as usize;
        }
        ret
    }
    fn game(&self, cups: usize, moves: usize) -> Vec<u32> {
        let mut map = vec![0; cups + 1];
        let mut last = None;
        for (i, &cup) in self.cups.iter().enumerate() {
            if i > 0 {
                map[self.cups[i - 1] as usize] = cup;
            }
            last = Some(cup);
        }
        for i in self.cups.len()..cups {
            if let Some(l) = last {
                map[l as usize] = i as u32 + 1;
            }
            last = Some(i as u32 + 1)
        }
        if let Some(l) = last {
            map[l as usize] = self.cups[0];
        }

        let highest = cups as usize;
        let mut current = self.cups[0] as usize;
        let mut pickups = [0; 3];
        for _ in 0..moves {
            let mut p = current;
            for pickup in pickups.iter_mut() {
                p = map[p] as usize;
                *pickup = p;
            }
            let mut destination = if current > 1 { current - 1 } else { highest };
            while pickups.iter().any(|&x| x == destination) {
                destination = if destination > 1 {
                    destination - 1
                } else {
                    highest
                };
            }
            let tmp = map[current];
            map[current] = map[p];
            map[p] = map[destination];
            map[destination] = tmp;
            current = map[current] as usize;
        }
        map
    }
}

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