🎄

Advent of Code 2020 day12

5 min read

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

part1

F10
N3
F7
R90
F11

といった入力が与えられる。各行はactionを表す先頭文字に続いてvalueを示す整数値が入る。
船は東向きの状態から開始し、各actionに対応して

N は 北方向に、valueだけ動く
S は 南方向に、valueだけ動く
E は 東方向に、valueだけ動く
W は 西方向に、valueだけ動く
L は 左方向に、value度だけ回転する
R は 右方向に、value度だけ回転する
F は 現在向いている方向に、valueだけ前進する

という命令だと解釈したとき、開始位置からどれだけ離れた位置に到達するか、そのマンハッタン距離を求めよ、という問題。
上の例の場合、(0, 0)から開始したとすると(10, 0) -> (10, 3) -> (17, 3) -> (17, -8) に到達するので 25 が答えになる。

そのまんま実装して実行してやれば良いだけ。現時点の座標を表すp = (0, 0)と、現時点の方向を表すd = (1, 0)を用意しておいて、 'N' | 'S' | 'E' | 'W' のときは座標pを動かし、 'L' | 'R' のときは方向dを更新してやれば良い。 F が来たら方向dに座標pを動かせば良い。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let mut p = (0, 0);
        let mut d = (1, 0);
        for input in self.inputs.iter() {
            if let Ok(value) = input[1..].parse::<i32>() {
                match input.chars().next() {
                    Some('N') => p.1 += value,
                    Some('S') => p.1 -= value,
                    Some('E') => p.0 += value,
                    Some('W') => p.0 -= value,
                    Some('L') => {
                        d = match value {
                            90 => (-d.1, d.0),
                            180 => (-d.0, -d.1),
                            270 => (d.1, -d.0),
                            _ => d,
                        }
                    }
                    Some('R') => {
                        d = match value {
                            90 => (d.1, -d.0),
                            180 => (-d.0, -d.1),
                            270 => (-d.1, d.0),
                            _ => d,
                        }
                    }
                    Some('F') => p = (p.0 + d.0 * value, p.1 + d.1 * value),
                    _ => {}
                }
            }
        }
        p.0.abs() + p.1.abs()
    }
}

part2

なんと、各命令の解釈は間違っていた(!)。
船から東に10、北に1の位置に waypointが存在しており、

Nwaypointが北方向に、valueだけ動く
Swaypointが南方向に、valueだけ動く
Ewaypointが東方向に、valueだけ動く
Wwaypointが西方向に、valueだけ動く
Lwaypointが船から見て左方向にvalue度だけ回転する
Rwaypointが船から見て右方向にvalue度だけ回転する
Fwaypointが示す方向にvalueだけ前進する

というのが正しかったようだ。
上の例だと (0, 0) [(10, 1)] -> (100, 10) [(10, 1)] -> (100, 10) [(10, 4)] -> (170, 38) [(10, 4)] -> (170, 38) [(4, -10)] -> (214, -72) [(4, -10)] といった形で 船の位置もしくはwaypointが動き、最終的な到達位置と開始位置のマンハッタン距離は286となる。

まるっと処理を書き直しても良いが、これはpart1が「東に1の位置にwaypointがある」状態とみなすことができ、 N, S, E, W で動かすのが船そのものかwaypointか、が変わるだけで あとは共通の処理で書けそうだ。

まずは毎回parseしているのがアレなので最初にactionvalueに分離して持ってしまう。

struct Solution {
    instructions: Vec<(char, i32)>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self {
            instructions: inputs
                .iter()
                .filter_map(|input| {
                    if let (Some(action), Ok(value)) =
                        (input.chars().next(), input[1..].parse::<i32>())
                    {
                        Some((action, value))
                    } else {
                        None
                    }
                })
                .collect(),
        }
    }
}

そうしたらあとは共通のメソッドに「waypointの初期値」と「waypointを動かすか否か」の引数だけ与えて処理するようにしてやれば良い。
角度は90, 180, 270のいずれかしか無いようなので繰り返し処理で済ませることにした。

    fn solve_1(&self) -> i32 {
        self.run((1, 0), false)
    }
    fn solve_2(&self) -> i32 {
        self.run((10, 1), true)
    }
    fn run(&self, w: (i32, i32), waypoint: bool) -> i32 {
        let mut p = (0, 0);
        let mut w = w;
        for &inst in self.instructions.iter() {
            match inst.0 {
                'N' if waypoint => w.1 += inst.1,
                'N' => p.1 += inst.1,
                'S' if waypoint => w.1 -= inst.1,
                'S' => p.1 -= inst.1,
                'E' if waypoint => w.0 += inst.1,
                'E' => p.0 += inst.1,
                'W' if waypoint => w.0 -= inst.1,
                'W' => p.0 -= inst.1,
                'L' => {
                    for _ in 0..inst.1 / 90 {
                        w = (-w.1, w.0)
                    }
                }
                'R' => {
                    for _ in 0..inst.1 / 90 {
                        w = (w.1, -w.0)
                    }
                }
                'F' => p = (p.0 + w.0 * inst.1, p.1 + w.1 * inst.1),
                _ => {}
            }
        }
        p.0.abs() + p.1.abs()
    }