DEV Community

Advent of Code 2020 Solution Megathread - Day 12: Rain Risk

Ryan Palo on December 12, 2020

I’m on mobile today, so putting this together is a little later and a little more interesting today. But here you go! Happy day 12! The P...

Read full post

Neil Gall • Dec 12 '20

Still insisting on proper modelling, unit tests and real parsers over string splitting and regex.

use std::fs::File;
use std::io::prelude::*;
use std::ops::{Add, Sub};
use parser::*;

// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

// --- model

type Distance = i64;
type Rotation = i64;

#[derive(Debug, Eq, PartialEq)]
enum Instruction {
    North(Distance),
    South(Distance),
    East(Distance),
    West(Distance),
    Left(Rotation),
    Right(Rotation),
    Forward(Distance)
}

#[derive(Debug, Eq, PartialEq, Copy, Clone)]
enum Direction {
    East = 0,
    North = 90,
    West = 180,
    South = 270
}

impl From<i64> for Direction {
    fn from(i: i64) -> Direction {
        match i {
            0 => Direction::East,
            90 => Direction::North,
            180 => Direction::West,
            270 => Direction::South,
            _ => panic!("invalid direction")
        }
    }
}

impl Add<&Rotation> for Direction {
    type Output = Direction;

    fn add(self, r: &Rotation) -> Direction {
        Direction::from(((self as i64) + r) % 360)
    }
}

impl Sub<&Rotation> for Direction {
    type Output = Direction;

    fn sub(self, r: &Rotation) -> Direction {
        Direction::from(((self as i64) + 360 - r) % 360)
    }
}

impl Direction {
    fn to_instruction(&self, distance: Distance) -> Instruction {
        match self {
            Direction::North => Instruction::North(distance),
            Direction::South => Instruction::South(distance),
            Direction::East => Instruction::East(distance),
            Direction::West => Instruction::West(distance)            
        }
    }
}

#[derive(Debug,PartialEq,Eq)]
struct Pos {
    x: i64,
    y: i64
}

impl Pos {
    fn rotate_around(&self, origin: &Pos, rotation: Rotation) -> Pos {
        let x = self.x - origin.x;
        let y = self.y - origin.y;
        let (new_x, new_y) = match rotation {
            90 => (-y, x),
            180 => (-x, -y),
            270 => (y, -x),
            _ => panic!("invalid rotation")
        };
        Pos {
            x: origin.x + new_x,
            y: origin.y + new_y
        }
    }
}

struct Ship {
    pos: Pos,
    direction: Direction
}

impl Ship {
    fn new() -> Self {
        Ship {
            pos: Pos { x: 0, y: 0 },
            direction: Direction::East
        }
    }

    fn go(&mut self, inst: &Instruction) {
        use Instruction::*;
        match inst {
            North(n) => self.pos.y += n,
            South(n) => self.pos.y -= n,
            East(n) => self.pos.x += n,
            West(n) => self.pos.x -= n,
            Left(n) => self.direction = self.direction + n,
            Right(n) => self.direction = self.direction - n,
            Forward(n) => self.go(&self.direction.to_instruction(*n))
        }
    }

    fn manhattan_distance_from_start(&self) -> Distance {
        self.pos.x.abs() + self.pos.y.abs()
    }
}

struct WaypointShip {
    ship: Pos,
    waypoint: Pos
}

impl WaypointShip {
    fn new() -> Self {
        WaypointShip {
            ship: Pos { x: 0, y : 0 },
            waypoint: Pos { x: 10, y: 1 }
        }
    }

    fn go(&mut self, inst: &Instruction) {
        use Instruction::*;
        match inst {
            North(n) => self.waypoint.y += n,
            South(n) => self.waypoint.y -= n,
            East(n) => self.waypoint.x += n,
            West(n) => self.waypoint.x -= n,
            Left(n) => self.waypoint = self.waypoint.rotate_around(&self.ship, *n),
            Right(n) => self.waypoint = self.waypoint.rotate_around(&self.ship, 360-(*n)),
            Forward(n) => {
                let x = (self.waypoint.x - self.ship.x) * n;
                let y = (self.waypoint.y - self.ship.y) * n;
                self.ship.x += x;
                self.ship.y += y;
                self.waypoint.x += x;
                self.waypoint.y += y;
            }
        }
    }

    fn manhattan_distance_from_start(&self) -> Distance {
        self.ship.x.abs() + self.ship.y.abs()
    }
}

// --- parser

fn parse_input(input: &str) -> ParseResult<Vec<Instruction>> {
    let north = right(match_literal("N"), integer).map(Instruction::North);
    let south = right(match_literal("S"), integer).map(Instruction::South);
    let east = right(match_literal("E"), integer).map(Instruction::East);
    let west = right(match_literal("W"), integer).map(Instruction::West);
    let tright = right(match_literal("R"), integer).map(Instruction::Right);
    let tleft = right(match_literal("L"), integer).map(Instruction::Left);
    let forward = right(match_literal("F"), integer).map(Instruction::Forward);
    let instruction = north.or(south).or(east).or(west).or(tright).or(tleft).or(forward);
    let parser = one_or_more(whitespace_wrap(instruction));

    parser.parse(input)
}

// --- problems

fn part1(instructions: &Vec<Instruction>) -> i64 {
    let mut ship = Ship::new();
    instructions.iter().for_each(|i| ship.go(i));
    ship.manhattan_distance_from_start()
}

fn part2(instructions: &Vec<Instruction>) -> i64 {
    let mut ship = WaypointShip::new();
    instructions.iter().for_each(|i| ship.go(i));
    ship.manhattan_distance_from_start()
}

fn main() {
    let input = read_file("./input.txt").unwrap();
    let instructions = parse_input(&input).unwrap().1;
    println!("part1 {}", part1(&instructions));
    println!("part2 {}", part2(&instructions));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parser() {
        use Instruction::*;
        let instructions = parse_input("F10\nN3\nF7\nR90\nF11");
        assert_eq!(instructions, Ok(("", vec![Forward(10), North(3), Forward(7), Right(90), Forward(11)])));
    }

    #[test]
    fn test_part1() {
        use Instruction::*;
        let instructions = vec![Forward(10), North(3), Forward(7), Right(90), Forward(11)];
        assert_eq!(part1(&instructions), 25);
    }

    #[test]
    fn test_part2() {
        use Instruction::*;
        let instructions = vec![Forward(10), North(3), Forward(7), Right(90), Forward(11)];
        assert_eq!(part2(&instructions), 286);
    }

    #[test]
    fn test_rotate_around_90() {
        let origin = Pos { x: 0, y: 0 };
        let pos = Pos { x: 10, y: 1 };
        assert_eq!(pos.rotate_around(&origin, 90), Pos { x: -1, y: 10 });
    }

    #[test]
    fn test_rotate_around_180() {
        let origin = Pos { x: 0, y: 0 };
        let pos = Pos { x: 10, y: 1 };
        assert_eq!(pos.rotate_around(&origin, 180), Pos { x: -10, y: -1 });
    }

    #[test]
    fn test_rotate_around_270() {
        let origin = Pos { x: 0, y: 0 };
        let pos = Pos { x: 10, y: 1 };
        assert_eq!(pos.rotate_around(&origin, 270), Pos { x: 1, y: -10 });
    }

}

Christopher Kruse • Dec 13 '20

I have to ask - why avoid regex use? Seems just another tool in the toolbox.

Neil Gall • Dec 13 '20

It is another tool in the box, and sometimes even the right tool. But regex is a sub-optimal general solution to what is often a quite specific task. One of my passions in programming is to show that real parsers are almost always better in the long run, and they're not hard to write.

Here's a recording of a talk I did at the Edinburgh Kotlin user's group last year on the subject: vimeo.com/393132096

Benjamin Trent • Dec 12 '20

So many match statements.

#[derive(Debug)]
enum Movement {
    North(i32),
    South(i32),
    East(i32),
    West(i32),
    Left(i32),
    Right(i32),
    Forward(i32),
}

impl From<&str> for Movement {
    fn from(s: &str) -> Self {
        let v = String::from(&s[..1]);
        let val: i32 = (&s[1..]).parse().unwrap();
        match v.as_str() {
            "N" => Movement::North(val),
            "S" => Movement::South(val),
            "E" => Movement::East(val),
            "W" => Movement::West(val),
            "L" => Movement::Left(val),
            "R" => Movement::Right(val),
            "F" => Movement::Forward(val),
            _ => unimplemented!(),
        }
    }
}

#[derive(Debug)]
enum Facing {
    N,
    S,
    E,
    W,
}

impl Facing {
    fn new_direction(&self, degrees: &i32) -> Facing {
        match self {
            Facing::N => match degrees {
                90 => Facing::E,
                180 => Facing::S,
                270 => Facing::W,
                _ => unimplemented!(),
            },
            Facing::S => match degrees {
                90 => Facing::W,
                180 => Facing::N,
                270 => Facing::E,
                _ => unimplemented!(),
            },
            Facing::E => match degrees {
                90 => Facing::S,
                180 => Facing::W,
                270 => Facing::N,
                _ => unimplemented!(),
            },
            Facing::W => match degrees {
                90 => Facing::N,
                180 => Facing::E,
                270 => Facing::S,
                _ => unimplemented!(),
            },
        }
    }
}

#[derive(Debug)]
struct Position {
    facing: Facing,
    x: i32,
    y: i32,
    waypoint_x: i32,
    waypoint_y: i32,
}

impl Position {
    fn new() -> Self {
        Position {
            facing: Facing::E,
            x: 0,
            y: 0,
            waypoint_x: 10,
            waypoint_y: 1,
        }
    }

    fn travel(&mut self, movement: &Movement) {
        match movement {
            Movement::North(val) => self.y += *val,
            Movement::South(val) => self.y -= *val,
            Movement::East(val) => self.x += *val,
            Movement::West(val) => self.x -= *val,
            Movement::Left(val) => self.facing = self.facing.new_direction(&(360 - val)),
            Movement::Right(val) => self.facing = self.facing.new_direction(val),
            Movement::Forward(val) => match self.facing {
                Facing::N => self.y += *val,
                Facing::S => self.y -= *val,
                Facing::E => self.x += *val,
                Facing::W => self.x -= *val,
            },
        }
    }

    fn travel_waypoint(&mut self, movement: &Movement) {
        match movement {
            Movement::North(val) => self.waypoint_y += *val,
            Movement::South(val) => self.waypoint_y -= *val,
            Movement::East(val) => self.waypoint_x += *val,
            Movement::West(val) => self.waypoint_x -= *val,
            Movement::Left(val) => self.rotate_waypoint(&(360 - val)),
            Movement::Right(val) => self.rotate_waypoint(val),
            Movement::Forward(val) => {
                self.x += val * self.waypoint_x;
                self.y += val * self.waypoint_y;
            }
        }
    }

    fn rotate_waypoint(&mut self, degrees: &i32) {
        match degrees {
            90 => {
                let new_x = self.waypoint_y;
                let new_y = -self.waypoint_x;
                self.waypoint_y = new_y;
                self.waypoint_x = new_x;
            }
            180 => {
                self.waypoint_x = -self.waypoint_x;
                self.waypoint_y = -self.waypoint_y;
            }
            270 => {
                let new_x = -self.waypoint_y;
                let new_y = self.waypoint_x;
                self.waypoint_y = new_y;
                self.waypoint_x = new_x;
            }
            _ => unimplemented!(),
        };
    }
}

#[aoc_generator(day12)]
fn to_vec(input: &str) -> Vec<Movement> {
    input.lines().map(|s| s.into()).collect()
}

#[aoc(day12, part1)]
fn manhatten_movement(input: &Vec<Movement>) -> usize {
    let mut position = Position::new();
    for movement in input {
        position.travel(movement);
    }
    return (position.x.abs() + position.y.abs()) as usize;
}

#[aoc(day12, part2)]
fn manhatten_waypoint_movement(input: &Vec<Movement>) -> usize {
    let mut position = Position::new();
    for movement in input {
        position.travel_waypoint(movement);
    }
    return (position.x.abs() + position.y.abs()) as usize;
}

Anna • Dec 12 '20

COBOL (part 2 on GitHub)

       IDENTIFICATION DIVISION.
       PROGRAM-ID. AOC-2020-12-1.
       AUTHOR ANNA KOSIERADZKA.

       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT INPUTFILE ASSIGN TO "d12.input"
           ORGANIZATION IS LINE SEQUENTIAL.

       DATA DIVISION.
       FILE SECTION.
         FD INPUTFILE
         RECORD IS VARYING IN SIZE FROM 1 to 99
         DEPENDING ON REC-LEN.
         01 INPUTRECORD.
           05 INPUT-ACTION PIC X.
           05 INPUT-ARG PIC 9(3).

       WORKING-STORAGE SECTION.
         01 FILE-STATUS PIC 9 VALUE 0.
         01 REC-LEN PIC 9(2) COMP.
         01 CURR-DIR PIC X VALUE 'E'.
         01 DIR PIC X VALUE 'E'.
         01 DX PIC S9 VALUE 1.
         01 DY PIC S9 VALUE 0.
         01 X PIC S9(6) VALUE 0.
         01 Y PIC S9(6) VALUE 0.
         01 N PIC S9(6) VALUE 0.
         01 ARG PIC S9(3) VALUE 0.

       PROCEDURE DIVISION.
       001-MAIN.
           OPEN INPUT INPUTFILE.
           PERFORM 002-READ UNTIL FILE-STATUS = 1.
           CLOSE INPUTFILE.
           COMPUTE N = FUNCTION ABS(X) + FUNCTION ABS(Y).
           DISPLAY N.
           STOP RUN.

       002-READ.
            READ INPUTFILE
                AT END MOVE 1 TO FILE-STATUS
                NOT AT END PERFORM 003-PROCESS-RECORD
            END-READ.

       003-PROCESS-RECORD.
           COMPUTE ARG = FUNCTION NUMVAL(INPUT-ARG)
           PERFORM 004-COMPUTE-DIRECTION.
           PERFORM 005-COMPUTE-DELTAS.
           PERFORM 008-NAVIGATE.

       004-COMPUTE-DIRECTION.
           IF INPUT-ACTION = 'N' OR INPUT-ACTION = 'S' 
              OR INPUT-ACTION = 'E' OR INPUT-ACTION = 'W' THEN 
                  MOVE INPUT-ACTION TO DIR
                  EXIT PARAGRAPH
           END-IF.
           IF INPUT-ACTION = 'F' THEN
              MOVE CURR-DIR TO DIR
              EXIT PARAGRAPH
           END-IF.
           COMPUTE N = ARG / 90.
           IF INPUT-ACTION = 'R' THEN
              PERFORM 006-ROTATE-RIGHT N TIMES
           ELSE 
               PERFORM 007-ROTATE-LEFT N TIMES
           END-IF.
           MOVE CURR-DIR TO DIR.

      * N -> E -> S -> W     
       006-ROTATE-RIGHT.
           EVALUATE CURR-DIR
            WHEN 'N'
               MOVE 'E' TO CURR-DIR
            WHEN 'E'
               MOVE 'S' TO CURR-DIR
            WHEN 'S'
               MOVE 'W' TO CURR-DIR
            WHEN 'W'
               MOVE 'N' TO CURR-DIR
           END-EVALUATE.

      * N -> W -> S -> E
       007-ROTATE-LEFT.
           EVALUATE CURR-DIR
            WHEN 'N'
               MOVE 'W' TO CURR-DIR
            WHEN 'W'
               MOVE 'S' TO CURR-DIR
            WHEN 'S'
               MOVE 'E' TO CURR-DIR
            WHEN 'E'
               MOVE 'N' TO CURR-DIR
           END-EVALUATE.

       005-COMPUTE-DELTAS.
           EVALUATE DIR
            WHEN 'N'
               MOVE -1 TO DX
               MOVE 0 TO DY
            WHEN 'W'
               MOVE 0 TO DX
               MOVE -1 TO DY
            WHEN 'S'
               MOVE 1 TO DX
               MOVE 0 TO DY
            WHEN 'E'
               MOVE 0 TO DX
               MOVE 1 TO DY
           END-EVALUATE.

       008-NAVIGATE.
           IF INPUT-ACTION = 'L' OR INPUT-ACTION = 'R' THEN
              EXIT PARAGRAPH
           END-IF.
           COMPUTE X = X + DX * ARG.
           COMPUTE Y = Y + DY * ARG.

Saripius • Dec 13 '20

Part 1 Python
New to coding and behind in the calendar but this one looked easy overall.

with open ('input.txt') as inp:
    EW = 0
    NS = 0
    dir = 90

    for line in inp:
        action = line[0]
        num = int(line[1:])
        if action == "F" and dir == 90 or action == "E":
            EW += num
        elif action == "F" and dir == 180 or action == "S":
            NS -= num
        elif action == "F" and dir == 270 or action == "W":
            EW -= num
        elif action == "F" and dir == 0 or action == "N":
            NS += num
        elif action == "L":
            dir -= num
            if dir == 360 or dir == -360:
                dir = 0
            if dir == -90:
                dir = 270
            if dir == -180 or dir == 540:
                dir = 180
            if dir == -270 or dir == 450:
                dir = 90

        elif action == "R":
            dir += num
            if dir == 360 or dir == -360:
                dir = 0
            if dir == -90:
                dir = 270
            if dir == -180 or dir == 540:
                dir = 180
            if dir == -270 or dir == 450:
                dir = 90

print(f"Manhatten Distance: {abs(NS)+ abs(EW)}")

not sure how to get syntax highlighting to show here
Part 2

with open ('input.txt') as inp:
    ship_ew = 0
    ship_ns = 0
    way_ew = 10
    way_ns = 1

    for line in inp:
        action = line[0]
        num = int(line[1:]) 

        if action == "F":
            ship_ns += (way_ns * num)
            ship_ew += (way_ew * num) 
        elif action == "N":
            way_ns += num
        elif action == "S":
            way_ns -= num
        elif action == "E":
            way_ew += num
        elif action == "W":
            way_ew -= num

        elif action == "L" and num == 90 or action == "R" and num == 270:
            way_ns, way_ew = way_ew, -way_ns
        elif action == "L" and num == 270 or action == "R" and num ==90:
            way_ns, way_ew = -way_ew, way_ns
        elif action == "L" and num == 180 or action == "R" and num == 180:
            way_ns = -way_ns
            way_ew = -way_ew

print(f"Manhattan Distance: {abs(ship_ns)+ abs(ship_ew)}")

I need to refactor this and function it out

Neil Gall • Dec 13 '20

Nice! I like how you folded the absolute directions and the forward commands into one action with checks on the current direction. Look into the % (modulo) operator for handling the circular arithmetic around the rotation additions - in short (dir + num) % 360 for right turns and (dir + 360 - num) % 360 for left.

Derk-Jan Karrenbeld • Dec 13 '20

There are (at least) two ways to "model" the solution: polar coordinates or vector/gonio math. Here is a Ruby OOP solution using the latter:

require 'benchmark'

class Ship

  attr_reader :position

  def initialize
    self.facing = 90
    self.position = Position.new(0, 0)
    self.waypoint = Waypoint.new
  end

  def sail!(instruction)

    case instruction.action
      when 'N'
        position.translate!(0, -instruction.value)
      when 'S'
        position.translate!(0,  instruction.value)
      when 'E'
        position.translate!( instruction.value, 0)
      when 'W'
        position.translate!(-instruction.value, 0)
      when 'L'
        self.facing = (self.facing - instruction.value) % 360
      when 'R'
        self.facing = (self.facing + instruction.value) % 360
      when 'F'
        direction = %w[N E S W][facing / 90]
        sail! instruction.with_action(direction)
        # input only contains 90 180 270 so no need for
        # SOS Castoa (gonio).

      end
  end

  def sail_with_waypoint!(instruction)
    if %w[N S E W L R].include?(instruction.action)
      waypoint.sail! instruction
      return
    end

    dx, dy = waypoint.position.difference(Position.new(0, 0))
    self.position.translate!(dx * instruction.value, dy * instruction.value)
  end

  private

  attr_accessor :facing, :waypoint
  attr_writer :position
end

class Waypoint

  attr_reader :position

  def initialize
    self.position = Position.new(10, -1)
  end

  def sail!(instruction)
    case instruction.action
    when 'N'
      position.translate!(0, -instruction.value)
    when 'S'
      position.translate!(0,  instruction.value)
    when 'E'
      position.translate!( instruction.value, 0)
    when 'W'
      position.translate!(-instruction.value, 0)
    when 'L'
      theta = -(instruction.value / 180.to_f * Math::PI)

      self.position = Position.new(
        (position.x * Math.cos(theta) - position.y * Math.sin(theta)).round,
        (position.x * Math.sin(theta) + position.y * Math.cos(theta)).round
      )
    when 'R'
      theta = instruction.value / 180.to_f * Math::PI

      self.position = Position.new(
        (position.x * Math.cos(theta) - position.y * Math.sin(theta)).round,
        (position.x * Math.sin(theta) + position.y * Math.cos(theta)).round
      )
    end
  end

  private

  attr_accessor :facing
  attr_writer :position
end

class Instruction
  attr_reader :action, :value

  def initialize(action, value)
    self.action = action
    self.value = value.to_i
  end

  def with_action(new_action)
    Instruction.new(new_action, value)
  end

  private

  attr_writer :action, :value
end

class Position
  attr_reader :x, :y

  def initialize(x, y)
    self.x = x
    self.y = y
  end

  def translate!(x, y)
    self.x += x
    self.y += y

    self
  end

  def distance(other)
    difference(other).map(&:abs).sum
  end

  def difference(other)
    [x - other.x, y - other.y]
  end

  private

  attr_writer :x, :y
end

module NavigationInstructions
  def self.from_lines(lines)
    lines.map do |line|
      line = line.chomp
      Instruction.new(line[0], line[1..])
    end
  end
end

def track(ship)
  original = ship.position.dup
  yield
  original.distance(ship.position)
end

source = 'input.txt'

instructions = NavigationInstructions.from_lines(File.readlines(source))
verbose = false

Benchmark.bmbm do |x|
  x.report(:part_1) do
    ship = Ship.new

    distance = track(ship) do
      instructions.each do |instruction|
        ship.sail! instruction
        puts "[ahoy] #{instruction.action} by #{instruction.value}: #{ship.position.x}, #{ship.position.y}" if verbose
      end
    end

    puts distance
  end

  x.report(:part_2) do
    ship = Ship.new

    distance = track(ship) do
      instructions.each do |instruction|
        ship.sail_with_waypoint! instruction
        puts "[ahoy] #{instruction.action} by #{instruction.value}: #{ship.position.x}, #{ship.position.y}" if verbose
      end
    end
    puts distance
  end
end

Frederik 👨‍💻➡️🌐 Creemers • Dec 12 '20

I'm gonna post the 2 parts separately, as it looks like it's gonna be easier to edit the code than to support both parts with the same module.

here's part 1:


defmodule Navigator do
  def execute(s, state) do
    inst = String.first(s)
    arg = String.to_integer(String.slice(s, 1, String.length(s)-1))
    execute(inst, arg, state)
  end

  def execute("N", dist, state) do
    Map.merge(state, %{y: state.y + dist})
  end

  def execute("S", dist, state) do
    Map.merge(state, %{y: state.y - dist})
  end

  def execute("E", dist, state) do
    Map.merge(state, %{x: state.x + dist})
  end

  def execute("W", dist, state) do
    Map.merge(state, %{x: state.x - dist})
  end

  def execute("L", angle, state) do
    Map.merge(state, %{dir: state.dir - div(angle, 90)})
  end

  def execute("R", angle, state) do
    Map.merge(state, %{dir: state.dir + div(angle, 90)})
  end

  def execute("F", dist, state) do
    dir = Enum.at(["E", "S", "W", "N"], rem(state.dir, 4))
    execute(dir, dist, state)
  end

  def read_instructions() do
    {:ok, text} = File.read("12.txt")
    String.split(String.trim(text), "\n")
  end

  def execute_instructions(insts, state \\ %{x: 0, y: 0, dir: 0}) do
    if length(insts) > 0 do
      [inst | remaining] = insts
      nstate = execute(inst, state)
      execute_instructions(remaining, nstate)
    else
      abs(state.x) + abs(state.y)
    end
  end

  def round1() do
    lines = read_instructions()
    IO.puts(execute_instructions(lines))
  end
end

Navigator.round1()

Frederik 👨‍💻➡️🌐 Creemers • Dec 12 '20

Part 2:

defmodule Navigator do
  def execute(s, state) do
    inst = String.first(s)
    arg = String.to_integer(String.slice(s, 1, String.length(s)-1))
    execute(inst, arg, state)
  end

  def execute("N", dist, state) do
    Map.merge(state, %{wy: state.wy + dist})
  end

  def execute("S", dist, state) do
    Map.merge(state, %{wy: state.wy - dist})
  end

  def execute("E", dist, state) do
    Map.merge(state, %{wx: state.wx + dist})
  end

  def execute("W", dist, state) do
    Map.merge(state, %{wx: state.wx - dist})
  end

  def execute("L", 90, state) do
    Map.merge(state, %{wx: -state.wy, wy: state.wx})
  end

  def execute("R", 90, state) do
    Map.merge(state, %{wx: state.wy, wy: -state.wx})
  end

  def execute("L", 270, state) do execute("R", 90, state) end
  def execute("R", 270, state) do execute("L", 90, state) end
  def execute(d, 180, state) when d in ["L", "R"] do
    Map.merge(state, %{wx: -state.wx, wy: -state.wy})
  end

  def execute("F", dist, state) do
    Map.merge(state, %{x: state.x + state.wx * dist, y: state.y + state.wy * dist})
  end

  def read_instructions() do
    {:ok, text} = File.read("12.txt")
    String.split(String.trim(text), "\n")
  end

  def execute_instructions(insts, state \\ %{x: 0, y: 0, wx: 10, wy: 1}) do
    if length(insts) > 0 do
      [inst | remaining] = insts
      nstate = execute(inst, state)
      execute_instructions(remaining, nstate)
    else
      abs(state.x) + abs(state.y)
    end
  end

  def round2() do
    lines = read_instructions()
    IO.puts(execute_instructions(lines))
  end
end

Navigator.round2()

Ryan Palo • Dec 12 '20

Not too bad! I had an issue with the rotation in part 2, and I ended up writing so. many. tests. to find it. Which totally payed off!

Day12.h:

#ifndef AOC2020_DAY12_H
#define AOC2020_DAY12_H

#include <stdlib.h>

/// Possible actions the boat can take
typedef enum {
  AC_NORTH,
  AC_EAST,
  AC_SOUTH,
  AC_WEST,
  AC_LEFT,
  AC_RIGHT,
  AC_FORWARD,
  AC_COUNT
} Action;

/// String representation of actions for printing
static char* actions[AC_COUNT] = {"North", "East", "South", "West", "Left", "Right", "Forward"};

/// Figure out the Manhattan Distance after processing the instructions
/// in `filename`.
int part1(const char* filename);

/// The state of the boat for part 2
typedef struct {
  int x;    ///< The E/W location of the boat (E+)
  int y;    ///< The N/S location of the boat (N+)
  int wx;   ///< The E/W location of the waypoint
  int wy;   ///< The N/S location of the waypoint
} ShipState;

/// Move the ship or waypoint based on the action requested
///
/// AC_NORTH: move the waypoint north
/// AC_EAST: move the waypoint east
/// AC_SOUTH: move the waypoint south
/// AC_WEST: move the waypoint west
/// AC_LEFT: rotate the waypoint left `amount` degrees about the ship
/// AC_RIGHT: rotate the waypoint right `amount` degrees about the ship
/// AC_FORWARd: move the ship to the waypoint `amount` times (waypoint
///              always relocates so its final position relative to
///              the ship is the same.)
ShipState move(ShipState current, Action action, int amount);

/// Following the new rules about waypoints followed in `move`, 
/// what is the Manhattan distance from the origin that the ship
/// achieves by following the instructions in `filename`?
int part2(const char* filename);

/// Run both parts
int day12(void);
#endif

Day12.c:

#include "Day12.h"

#include <stdio.h>

#include "parsing.h"

/// Direction enum for part 1
typedef enum {
  DIR_NORTH,
  DIR_EAST,
  DIR_SOUTH,
  DIR_WEST,
} Direction;

/// An instruction is one command to move the ship or waypoint
typedef struct {
  Action action;  ///< The `Action` to perform
  int amount;     ///< A measure of how much to perform that action
} Instruction;

/// Parse the input file, which has lines of 'A123' where 'A' is a 
/// character specifying the action to take and '123' is some 1-3 digit
/// number that specifies the "amount" to do the action.
static Instruction* parse(const char* filename, int* count) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  *count = count_lines(fp);
  Instruction* instructions = (Instruction*)malloc(sizeof(Instruction) * *count);

  for (int i = 0; i < *count; i++) {
    char c = 0;
    int arg = 0;
    fscanf(fp, "%c%d\n", &c, &arg);
    Action action;
    switch (c) {
      case 'N': action = AC_NORTH; break;
      case 'E': action = AC_EAST; break;
      case 'S': action = AC_SOUTH; break;
      case 'W': action = AC_WEST; break;
      case 'L': action = AC_LEFT; break;
      case 'R': action = AC_RIGHT; break;
      case 'F': action = AC_FORWARD; break;
      default: printf("Unrecognized action: %c\n", c); exit(EXIT_FAILURE);
    }
    instructions[i] = (Instruction){.action = action, .amount = arg};
  }

  fclose(fp);
  return instructions;
}

/// Calculate the new direction based on an orientation and an amount
/// to turn.
static Direction turn(Direction current, Action action, int amount) {
  int rotation = action == AC_LEFT ? -1 : 1;
  int new_dir = ((int)current + (amount / 90) * rotation) % 4;
  if (new_dir < 0) new_dir += 4;
  return (Direction)new_dir;
}

int part1(const char* filename) {
  int count;
  Instruction* instructions = parse(filename, &count);

  int x = 0;
  int y = 0;
  Direction direction = DIR_EAST;

  for (int i = 0; i < count; i++) {
    Instruction inst = instructions[i];
    #ifdef STEPTHRU
    printf("<%d, %d> Facing %d.\n", x, y, direction);
    printf("%d: %d\n", inst.action, inst.amount);
    getc(stdin);
    #endif
    switch (inst.action) {
      case AC_NORTH: y += inst.amount; break;
      case AC_EAST: x += inst.amount; break;
      case AC_SOUTH: y -= inst.amount; break;
      case AC_WEST: x -= inst.amount; break;
      case AC_LEFT: direction = turn(direction, AC_LEFT, inst.amount); break;
      case AC_RIGHT: direction = turn(direction, AC_RIGHT, inst.amount); break;
      case AC_FORWARD: {
        switch (direction) {
          case DIR_NORTH: y += inst.amount; break;
          case DIR_EAST: x += inst.amount; break;
          case DIR_SOUTH: y -= inst.amount; break;
          case DIR_WEST: x -= inst.amount; break;
          default: 
            printf("Unrecognized direction state: %d\n", direction);
            exit(EXIT_FAILURE);
        };
        break;
      }
      default: printf("Unrecognized action. %d\n", inst.action); exit(EXIT_FAILURE);
    }
  }

  return abs(x) + abs(y);
}

ShipState move(ShipState current, Action action, int amount) {
  ShipState new = current;
  switch (action) {
    case AC_NORTH: new.wy += amount; break;
    case AC_EAST: new.wx += amount; break;
    case AC_SOUTH: new.wy -= amount; break;
    case AC_WEST: new.wx -= amount; break;
    case AC_LEFT: {
      for (int j = 0; j < amount / 90; j++) {
        int tmp = new.wx;
        new.wx = new.wy*-1;
        new.wy = tmp;
      }
    }; break;
    case AC_RIGHT: {
      for (int j = 0; j < amount / 90; j++) {
        int tmp = new.wx;
        new.wx = new.wy;
        new.wy = tmp*-1;
      }
    }; break;
    case AC_FORWARD: {
      new.x += new.wx * amount;
      new.y += new.wy * amount;
    }; break;
    default: printf("Unrecognized action. %d\n", action); exit(EXIT_FAILURE);
  }
  return new;
}

int part2(const char* filename) {
  int count;
  Instruction* instructions = parse(filename, &count);

  ShipState state = {0, 0, 10, 1};

  for (int i = 0; i < count; i++) {
    Instruction inst = instructions[i];
    #ifdef STEPTHRU
    printf("<%d, %d> wpt <%d, %d>.\n", state.x, state.y, state.wx, state.wy);
    printf("%s: %d\n", actions[inst.action], inst.amount);
    getc(stdin);
    #endif
    state = move(state, inst.action, inst.amount);
  }

  return abs(state.x) + abs(state.y);
}

int day12() {
  printf("====== Day 12 ======\n");
  printf("Part 1: %d\n", part1("data/day12.txt"));
  printf("Part 2: %d\n", part2("data/day12.txt"));
  return EXIT_SUCCESS;
}

Matt Ellen-Tsivintzeli • Dec 12 '20 • Edited

Another javascript master piece: this gist.

Happy to use the javascript value swap shortcut in this one:

[a, b] = [b, a];

Christopher Kruse • Dec 13 '20

Got through this one fairly quickly (problem sat well with how my mind works, I guess).

As always, on Github.

use aoc_runner_derive::{aoc, aoc_generator};
use std::cmp::Ordering;

#[derive(Debug)]
enum Direction {
    East,
    West,
    North,
    South,
    Left,
    Right,
    Forward,
}

struct Command {
    direction: Direction,
    measure: usize,
}

#[aoc_generator(day12)]
fn parse_input_day12(input: &str) -> Vec<Command> {
    input
        .lines()
        .map(|l| Command {
            direction: match l.chars().next() {
                Some('F') => Direction::Forward,
                Some('N') => Direction::North,
                Some('S') => Direction::South,
                Some('E') => Direction::East,
                Some('W') => Direction::West,
                Some('L') => Direction::Left,
                Some('R') => Direction::Right,
                _ => panic!("Invalid direction!"),
            },
            measure: str::parse(&l[1..]).expect("Unable to parse measure"),
        })
        .collect()
}

fn manhattan_distance(point_1: &(isize, isize), point_2: &(isize, isize)) -> usize {
    ((point_1.0 - point_2.0).abs() + (point_1.1 - point_2.1).abs()) as usize
}

fn move_ship(position: &mut (isize, isize), direction: &Direction, distance: usize) {
    match *direction {
        Direction::North => {
            position.1 += distance as isize;
        }
        Direction::South => {
            position.1 -= distance as isize;
        }
        Direction::East => {
            position.0 -= distance as isize;
        }
        Direction::West => {
            position.0 += distance as isize;
        }
        _ => panic!("cannot move in specified Direction {:?}", direction),
    }
}

fn angle_lookup(direction: &Direction) -> usize {
    match direction {
        Direction::North => 270,
        Direction::South => 90,
        Direction::East => 0,
        Direction::West => 180,
        _ => panic!("not a cardinal direction"),
    }
}

fn direction_lookup(angle: usize) -> Direction {
    match angle {
        0 => Direction::East,
        90 => Direction::South,
        180 => Direction::West,
        270 => Direction::North,
        _ => panic!("invalid angle"),
    }
}

fn turn_ship(orientation: &mut Direction, command: &Command) {
    let mut degree: isize = match command.direction {
        Direction::Left => -1 * command.measure as isize,
        Direction::Right => command.measure as isize,
        _ => panic!(
            "cannot turn with specified Direction {:?}",
            command.direction
        ),
    };

    let mut current_angle = angle_lookup(orientation) as isize;
    while degree != 0 {
        if degree < 0 {
            current_angle -= 90;
            degree += 90;
        } else {
            current_angle += 90;
            degree -= 90;
        }
    }
    let final_angle: usize = match current_angle.cmp(&0) {
        Ordering::Less => (current_angle % 360) + 360,
        _ => current_angle % 360,
    } as usize;
    *orientation = direction_lookup(final_angle);
}

#[aoc(day12, part1)]
fn get_travel_distance(input: &Vec<Command>) -> usize {
    let origin = (0, 0);
    let mut position = (0, 0);
    let mut orientation = Direction::East;

    input.iter().for_each(|cmd| match cmd.direction {
        Direction::North | Direction::South | Direction::East | Direction::West => {
            move_ship(&mut position, &cmd.direction, cmd.measure);
        }
        Direction::Forward => {
            move_ship(&mut position, &orientation, cmd.measure);
        }
        Direction::Left | Direction::Right => {
            turn_ship(&mut orientation, &cmd);
        }
    });

    manhattan_distance(&origin, &position)
}

fn move_waypoint(waypoint: &mut (isize, isize), cmd: &Command) {
    match cmd.direction {
        Direction::East => waypoint.0 += cmd.measure as isize,
        Direction::West => waypoint.0 -= cmd.measure as isize,
        Direction::North => waypoint.1 += cmd.measure as isize,
        Direction::South => waypoint.1 -= cmd.measure as isize,
        _ => panic!("Not a move Direction"),
    }
}

fn rotate_waypoint(waypoint: &mut (isize, isize), cmd: &Command) {
    let angle = match cmd.direction {
        Direction::Left => ((-1 * cmd.measure as isize) + 360) as usize,
        Direction::Right => cmd.measure,
        _ => panic!("Not a rotational direction"),
    };

    match angle {
        0 => (),
        270 => {
            let new_x = -1 * waypoint.1;
            let new_y = waypoint.0;
            waypoint.0 = new_x;
            waypoint.1 = new_y;
        }
        180 => {
            waypoint.0 = -1 * waypoint.0;
            waypoint.1 = -1 * waypoint.1;
        }
        90 => {
            let new_x = waypoint.1;
            let new_y = -1 * waypoint.0;
            waypoint.0 = new_x;
            waypoint.1 = new_y;
        }
        _ => panic!("invalid angle"),
    }
}

fn move_ship_toward_waypoint(
    position: &mut (isize, isize),
    waypoint: &(isize, isize),
    times: usize,
) {
    for _ in 0..times {
        position.0 += waypoint.0;
        position.1 += waypoint.1;
    }
}

#[aoc(day12, part2)]
fn get_travel_waypoint_distance(input: &Vec<Command>) -> usize {
    let origin = (0, 0);
    let mut waypoint = (10, 1);
    let mut position = (0, 0);

    input.iter().for_each(|cmd| {
        match cmd.direction {
            Direction::North | Direction::South | Direction::East | Direction::West => {
                move_waypoint(&mut waypoint, cmd);
            }
            Direction::Forward => {
                move_ship_toward_waypoint(&mut position, &waypoint, cmd.measure);
            }
            Direction::Left | Direction::Right => rotate_waypoint(&mut waypoint, &cmd),
        }
    });

    manhattan_distance(&origin, &position)
}

Mike Gasparelli • Dec 13 '20

Warning, lots of code today! I've been making an effort to model my solutions in ways that do not require special branching, or separate solutions for the 2 parts. Today was a fun one, and I think I came up with a good design, even if it's a little verbose!

At this point I think my enterprise development roots are showing. I've got inheritance, interfaces, strategies, factories, and even a DI container in my overall 2020 codebase 🤣

Part1

    public class Part1 : Puzzle<IEnumerable<NavInstruction>, int>
    {
        public override int SampleAnswer => 25;

        public override IEnumerable<NavInstruction> ParseInput(string rawInput)
            => rawInput
                .Split(Environment.NewLine)
                .Where(line => line.Length > 0)
                .Select(line =>
                    new NavInstruction(
                        Action: line[0],
                        Value: int.Parse(line[1..])
                    ));

        public override int Solve(IEnumerable<NavInstruction> input)
        {
            var origin = new Point(0, 0);
            var ferry = new Ferry(origin);
            ferry.Sail(input);
            return ManhattanDistance(origin, ferry.Location);
        }

        protected static int ManhattanDistance(Point a, Point b)
            => Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
    }

Part 2

    public class Part2 : Part1
    {
        public override int SampleAnswer => 286;

        public override int Solve(IEnumerable<NavInstruction> input)
        {
            var origin = new Point(0, 0);
            var ferry = new WaypointFerry(origin, new Point(10, 1));
            ferry.Sail(input);
            return ManhattanDistance(origin, ferry.Location);
        }
    }

FerryBase

public abstract class FerryBase
    {
        public Point Location { get; protected set; }

        public Direction Bearing { get; protected set; }

        protected FerryBase(Point origin)
        {
            Location = origin;
            Bearing = Direction.Right;
        }

        public void Sail(IEnumerable<NavInstruction> instructions)
        {
            foreach (NavInstruction instruction in instructions)
            {
                Move(instruction);
            }
        }

        protected Direction GetDirection(NavInstruction instruction)
            => instruction.Action switch {
                'N' => Direction.Up,
                'S' => Direction.Down,
                'E' => Direction.Right,
                'W' => Direction.Left,
                _ => Bearing
            };

        protected static Point Move(Point p, Direction direction, int value)
            => direction switch {
                Direction.Up => new Point(p.X, p.Y + value),
                Direction.Down => new Point(p.X, p.Y - value),
                Direction.Left => new Point(p.X - value, p.Y),
                Direction.Right => new Point(p.X + value, p.Y),
                _ => p
            };

        protected void Rotate(char turnDirection, int angle)
        {
            for (int i = 0; i < angle / 90; i++)
            {
                Rotate(turnDirection);
            }
        }

        protected abstract void Rotate(char turnDirection);

        protected abstract void Move(NavInstruction instruction);
    }

Ferry (Part1's Implementation)

public class Ferry : FerryBase
    {
        public Ferry(Point origin)
            : base(origin)
        {
        }

        protected override void Rotate(char turnDirection)
        {
            int iBearing = (int)Bearing;
            Bearing = turnDirection switch {
                'L' => (Direction)((iBearing + 3) % 4),
                'R' => (Direction)((iBearing + 1) % 4),
                _ => Bearing
            };
        }

        protected override void Move(NavInstruction instruction)
        {
            if (instruction.Action is 'L' or 'R')
            {
                Rotate(instruction.Action, instruction.Value);
                return;
            }

            Move(GetDirection(instruction), instruction.Value);
        }

        void Move(Direction direction, int value)
            => Location = Move(Location, direction, value);
    }

WaypointFerry (Part2's Implementation)

public class WaypointFerry : FerryBase
    {
        Point Waypoint = new Point(0, 0);

        public WaypointFerry(Point origin, Point waypoint)
            : base(origin)
        {
            Waypoint = waypoint;
        }

        protected override void Move(NavInstruction instruction)
        {
            if (instruction.Action is 'L' or 'R')
            {
                Rotate(instruction.Action, instruction.Value);
                return;
            }

            if (instruction.Action is 'F')
            {
                for (int i = 0; i < instruction.Value; i++)
                {
                    Location = new Point(Location.X + Waypoint.X, Location.Y + Waypoint.Y);
                }

                return;
            }

            Waypoint = Move(Waypoint, GetDirection(instruction), instruction.Value);
        }

        protected override void Rotate(char turnDirection)
            => Waypoint = turnDirection switch {
                'L' => new Point(-1 * Waypoint.Y, Waypoint.X),
                'R' => new Point(Waypoint.Y, -1 * Waypoint.X),
                _ => throw new Exception($"turnDirection not supported: {turnDirection}")
            };
    }

Benedict Gaster • Dec 12 '20 • Edited

Fun today, although solved part 1 before going out this morning, only to realise I needed slighty different function for part 2 :-) In the end just went with 2, mostly same, functions, as did not have the will power to generalize!

It's nice now that I'm starting to have a litlte library of "AOC" functions that I can call upon.

-- we need to accumulate, rather than simply fold
foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs

----------------------------------------------

data Move = N | E | S | W | F | B | L | R
    deriving (Show, Eq, Enum)

data Ship = Ship {  
    --update :: Ship -> Move -> Ship,
    way :: (Int, Int),
    northSouth :: Int,
    eastWest :: Int  }
  deriving Show


-- Simple parser
lexer = Token.makeTokenParser (TP.emptyDef { Token.reservedNames   = [ "nop", "acc", "jmp" ] })
reserved   = Token.reserved   lexer -- op code
integer    = Token.integer    lexer -- integer
whiteSpace = Token.whiteSpace lexer -- whitespace

-- parse individual opcode
pMoveOp :: TP.Parser (Int -> (Move, Int))
pMoveOp = TP.choice [
  (N,) <$ TP.char 'N', (S,) <$ TP.char 'S', 
  (W,) <$ TP.char 'W', (E,) <$ TP.char 'E',
  (F,) <$ TP.char 'F', (B,) <$ TP.char 'B',
  (L,) <$ TP.char 'L', (R,) <$ TP.char 'R']

-- parse an individual instructionr
pMove :: TP.Parser (Move, Int)
pMove = pMoveOp <*> (fromIntegral <$> integer)

-- parse all ops
parseMoves :: String -> [(Move, Int)]
parseMoves = either (error . show) id . TP.parse (TP.many1 (whiteSpace >> pMove)) ""

------

move ship (m, i) = aux m 
  where 
    aux = \case 
        N -> ship { northSouth = northSouth ship + i}
        S -> ship { northSouth = northSouth ship - i}
        E -> ship { eastWest = eastWest ship + i}
        W -> ship { eastWest = eastWest ship - i}
        L | i == 90  -> ship { way = let (dx, dy) = way ship in (-dy, dx) }
          | i == 180 -> ship { way = let (dx, dy) = way ship in (-dx, -dy) }
          | i == 270 -> ship { way = let (dx, dy) = way ship in (dy, -dx) }
        R | i == 90  -> ship { way = let (dx, dy) = way ship in (dy, -dx) }
          | i == 180 -> ship { way = let (dx, dy) = way ship in (-dx, -dy) }
          | i == 270 -> ship { way = let (dx, dy) = way ship in (-dy, dx) }
        F -> let (ns,ew, (dx,dy)) = (northSouth ship, eastWest ship, way ship)
             in ship { northSouth = ns + i * dy, eastWest = ew + i * dx}             

move' ship (m, i) = aux m 
    where 
      aux = \case 
          N -> ship { way = let (dx, dy) = way ship in (dx, dy+i) }
          S -> ship { way = let (dx, dy) = way ship in (dx, dy-i) }
          E -> ship { way = let (dx, dy) = way ship in (dx+i, dy) }
          W -> ship { way = let (dx, dy) = way ship in (dx-i, dy) }
          L | i == 90  -> ship { way = let (dx, dy) = way ship in (-dy, dx) }
            | i == 180 -> ship { way = let (dx, dy) = way ship in (-dx, -dy) }
            | i == 270 -> ship { way = let (dx, dy) = way ship in (dy, -dx) }
          R | i == 90  -> ship { way = let (dx, dy) = way ship in (dy, -dx) }
            | i == 180 -> ship { way = let (dx, dy) = way ship in (-dx, -dy) }
            | i == 270 -> ship { way = let (dx, dy) = way ship in (-dy, dx) }
          F -> let (ns,ew, (dx,dy)) = (northSouth ship, eastWest ship, way ship)
              in ship { northSouth = ns + i * dy, eastWest = ew + i * dx} 



run begin move = manhattan . foldl' move begin
  where 
    manhattan ship = abs ( northSouth ship ) + abs (eastWest ship)

main = do
  moves <- readFile "day12_input" <&> parseMoves
  print (run (Ship (1,0) 0 0) move moves)
  print (run (Ship (10,1) 0 0) move' moves)

Thibaut Patel • Dec 13 '20

My JavaScript walkthrough: