Advent of Code 2020 day13

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

part1

939
7,13,x,x,59,x,31,19

과 같은 입력을 제공합니다.
1행은 버스 정류장까지의 도착 시간을, 2행은 각 버스의 ID(= 운행 간격)를 나타낸다.
part1에서 x를 무시할 수 있습니다. 각 ID의 버스는 0부터 시작하고 ID 시간 간격으로 도착합니다.ID7의 버스는 7, 14, 21, ... , 938, 945, ...의 시간에, ID13의 버스는 13, 26, 39, ..., 936, 949, ...의 시간에.
기준 도착 시간 이후 가장 먼저 도착하는 버스를 구하고 이 ID와 대기 시간에 걸리는 값을 구한다.위의 예에서 939 이후 ID59의 버스가 944에 가장 먼저 도착했기 때문에 (944 - 939) * 59에서295가 해가 되었다.
문제에서 설명한 대로 모든 유효 ID가 기준 timestamp 이후에 나타나는 시간을 계산하여 최소값을 얻을 수 있습니다.
기준timestamp까지 하나하나 합치면 소용이 없기 때문에timestamp % id != 0 전제하에서(id * (timestamp / id + 1) - timestamp에서 각 ID의 대기 시간을 구한다.

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let timestamp = self.inputs[0].parse::<i32>().unwrap();
        if let Some((minutes, id)) = self.inputs[1]
            .split(',')
            .filter_map(|s| s.parse::<i32>().ok())
            .map(|id| (id * (timestamp / id + 1) - timestamp, id))
            .min_by_key(|&e| e.0)
        {
            id * minutes
        } else {
            0
        }
    }
}

part2

이번에는 1행의 시간을 무시하고 2행의 버스 ID만 사용했다.제i조 버스가 어느 순간부터 i의 조건을 충족시키는 첫 번째 순간을 찾습니다.저것

7,13,x,x,59,x,31,19

보조 IDi의 버스 도착 시간07

보조 IDt + 0의 버스 도착 시간113

t + 1, 제2항 무시

보조 ID3의 버스 도착 시간459

차t + 4회 무시

보조 ID5의 버스 도착 시간631

보조 IDt + 6의 버스 도착 시간719

모두 충족해야 합니다t + 7.
그걸 왜 빌어?
우선 t각도에서 볼 때 0마다 도착하는 버스7가 바짝 붙어 있기 때문에 t\equiv{0}\pmod{7}로 표시할 수 있다.t 두 번째는 1 목적지13마다 t+1\equiv{0}\pmod{13}, 네 번째t + 1는 t+4\equiv{0}\pmod{59}이다.이 모든 것을 만족시키는 t를 얻기 위해 아래의 연합 방정식을 풀 수 있다.
\begin{aligned}
t + 0 &\equiv 0\pmod{7}\\
t + 1 &\equiv 0\pmod{13}\\
t + 4 &\equiv 0\pmod{59}\\
t + 6 &\equiv 0\pmod{31}\\
t + 7 &\equiv 0\pmod{19}\\
\end{aligned}
제4항과 제0항이 만족하는 내용을 간단하게 고려해 보자.1개는 임의의 정수 m이다{0}에서 t=7m{0}로 표시할 수 있기 때문에 07m에 대입{0}+1\equiv{0}\pmod{13}이 됩니다.만족하다0부터 순서대로 0을 구해보면...
\begin{aligned}
7 * 0 + 1 &= 1\equiv{1}\pmod{13}\\
7 * 1 + 1 &= 8\equiv{8}\pmod{13}\\
7 * 2 + 1 &= 15\equiv{2}\pmod{13}\\
7 * 3 + 1 &= 22\equiv{9}\pmod{13}\\
7 * 4 + 1 &= 29\equiv{3}\pmod{13}\\
7 * 5 + 1 &= 36\equiv{10}\pmod{13}\\
7 * 6 + 1 &= 43\equiv{4}\pmod{13}\\
7 * 7 + 1 &= 50\equiv{11}\pmod{13}\\
7 * 8 + 1 &= 57\equiv{5}\pmod{13}\\
7 * 9 + 1 &= 64\equiv{12}\pmod{13}\\
7 * 10 + 1 &= 71\equiv{6}\pmod{13}\\
7 * 11 + 1 &= 78\equiv{0}\pmod{13}\\
\end{aligned}
m 과0=11시, 즉 t=77로 제1개와 제0개를 만족시킨다.
그리고 이후에도 등간격으로 계속하기 때문에 7*13=91의 주기로 반복해야 한다.따라서 임의의 정수 m에서 t=91m{01}+77로 표시할 수 있습니다.

>>> (77 + 0) % 7
0
>>> (77 + 1) % 13
0

다음 고려 1항도 만족하면 91m{01}+77+4\equiv{0}\pmod{59}로 변했기 때문에 이것에 만족할 것을 찾아야 한다.
\begin{aligned}
91 * 0 + 77 + 4 &= 81\equiv{22}\pmod{59}\\
91 * 1 + 77 + 4 &= 172\equiv{54}\pmod{59}\\
91 * 2 + 77 + 4 &= 263\equiv{27}\pmod{59}\\
91 * 3 + 77 + 4 &= 354\equiv{0}\pmod{59}\\
\end{aligned}
및 m{01}=3시, 즉 t=350시와 이로부터 시작되는 7*13*59=5369주기{014}+350시4,0, 제1항의 관련 조건을 만족시킨다.

>>> (350 + 0) % 7
0
>>> (350 + 1) % 13
0
>>> (350 + 4) % 59
0

같은 요구4로 첫 번째는 t=70147m{0146}+166439,6 만족 첫 번째는 t=3162341m{01467}+10668781로 표시할 수 있습니다.그중에 제일 먼저 나온 건 m.<01467}=0일 때이기 때문에7풀이된다.

>>> (1068781 + 0) % 7
0
>>> (1068781 + 1) % 13
0
>>> (1068781 + 4) % 59
0
>>> (1068781 + 6) % 31
0
>>> (1068781 + 7) % 19
0

Chinese remainder theorem중국의 잉여정리 이런 생각이었죠.
즉, 순서대로 만족해야 할 t,t=am을 구할 수 있다{i}+b로 표현된 경우 t+c\equiv{0}\pmod{d}의 t의 조건(am{i}+b)+c\equiv{0}\pmod{d})의 m을 더 만족시키려면{i}을 찾으면 새 t=(a*d)m{i+1}+(am{i}+b)로 표시할 수 있습니다.m_{i} a와 d는 서로 소박하다고 생각하기 때문에 d회까지 시도해야 한다.
처음에 a=1, b=0을 고려하고 다음 a, b를 요구하는 수속으로 쓰면 됩니다.

    fn solve_2(&self) -> i64 {
        self.inputs[1]
            .split(',')
            .enumerate()
            .filter_map(|(i, s)| {
                if let Ok(id) = s.parse::<i64>() {
                    Some((i as i64, id))
                } else {
                    None
                }
            })
            .fold((1, 0), |(a, b), (i, id)| {
                let m = (0..).find(|m| (a * m + b + i) % id == 0).unwrap();
                (a * id, a * m + b)
            })
            .1
    }