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를 다음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은 다시 연결한 후에currentcup 옆(다음)에 올 것입니다.
destination cup의 다음 cup은 다시 연결된 세 개의 옆(아래)에서 가져올 물건입니다.
따라서 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());
}