🎄

Advent of Code 2020 day12

2020/12/19に公開

Rust

adventofcode

tech

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が存在しており、

N は waypointが北方向に、valueだけ動く
S は waypointが南方向に、valueだけ動く
E は waypointが東方向に、valueだけ動く
W は waypointが西方向に、valueだけ動く
L は waypointが船から見て左方向に、value度だけ回転する
R は waypointが船から見て右方向に、value度だけ回転する
F は waypointが示す方向に、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しているのがアレなので最初にactionとvalueに分離して持ってしまう。

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()
    }

part1

part2

Discussion