mail-alt git-squared

~/abhirag

Advent of Code (2016) : Day 1

-- Problem --
You can find Part 1 of the problem statement here. Part 2 is unlocked on successful completion of Part 1.

-- Solution in Elixir --

       defmodule Aoc.Day1 do

  @input "L3, R1, L4, L1, L2, R4, L3, L3, R2, R3, L5, R1, R3, L4, L1, L2, R2, R1, L4, L4, R2, L5, R3, R2, R1, L1, L2, R2, R2, L1, L1, R2, R1, L3, L5, R4, L3, R3, R3, L5, L190, L4, R4, R51, L4, R5, R5, R2, L1, L3, R1, R4, L3, R1, R3, L5, L4, R2, R5, R2, L1, L5, L1, L1, R78, L3, R2, L3, R5, L2, R2, R4, L1, L4, R1, R185, R3, L4, L1, L1, L3, R4, L4, L1, R5, L5, L1, R5, L1, R2, L5, L2, R4, R3, L2, R3, R1, L3, L5, L4, R3, L2, L4, L5, L4, R1, L1, R5, L2, R4, R2, R3, L1, L1, L4, L3, R4, L3, L5, R2, L5, L1, L1, R2, R3, L5, L3, L2, L1, L4, R4, R4, L2, R3, R1, L2, R1, L2, L2, R3, R3, L1, R4, L5, L3, R4, R4, R1, L2, L5, L3, R1, R4, L2, R5, R4, R2, L5, L3, R4, R1, L1, R5, L3, R1, R5, L2, R1, L5, L2, R2, L2, L3, R3, R3, R1"


  ###########
  #         #
  # Part 1  #
  #         #
  ###########


  # reducing a list of instructions to the final state by
  # repeatedly applying new_state on the current instruction and state
  def final_state(instruction_list) do
    {x_final, y_final, _} = Enum.reduce(instruction_list, {0,0,"N"}, &new_state/2)
    {x_final, y_final}
  end

  # returning the distance in blocks between
  # the initial position i.e. (0,0) and the given position
  def block_distance({x,y}) do
    abs(x) + abs(y)
  end

  # the state to consider is {x_coordinate, y_coordinate, direction_facing}
  # every instruction changes this state
  # this function takes the old state and a single instruction and returns the new state
  # after this the problem is reduced to finding the final state
  # given {0,0,"N"} is the initial state, and calculating the distance in blocks
  # which is done by final_state and block_distance respectively

  #           +y
  #            N
  #            ^
  #            |
  #            |
  #
  #-x W<-----+0,0+---->E +x
  #
  #            |
  #            |
  #            v
  #            S
  #           -y
  def new_state(instruction, {x, y, facing}) do
    {direction, steps} = parse_instruction(instruction)
    case {x, y, facing, direction} do
      {x, y, "N", "R"} -> {x + steps, y, "E"}
      {x, y, "N", "L"} -> {x - steps, y, "W"}
      {x, y, "S", "R"} -> {x - steps, y, "W"}
      {x, y, "S", "L"} -> {x + steps, y, "E"}
      {x, y, "W", "R"} -> {x, y + steps, "N"}
      {x, y, "W", "L"} -> {x, y - steps, "S"}
      {x, y, "E", "R"} -> {x, y - steps, "S"}
      {x, y, "E", "L"} -> {x, y + steps, "N"}
    end
  end

  # extract direction and number of steps from an instruction
  def parse_instruction(instruction) do
    case instruction do
      "R" <> steps -> {"R", String.to_integer(steps)}
      "L" <> steps -> {"L", String.to_integer(steps)}
    end
  end

  # convert a string of instructions to a list of instructions
  def parse_input(instruction_string) do
    String.split(instruction_string, ",")
    |> Enum.map(&String.trim/1)
  end


  ###########
  #         #
  # Part 2  #
  #         #
  ###########

  # returns the first location we visited twice
  # for every instruction --
  # 1. calculate the new state
  # 2. calculate the positions visited while transitioning states
  # 3. check if any position in the positions_visited list has been visited before
  # 4. return it on finding such a position
  # 5. otherwise recurse and repeat the procedure for the next instruction, with updated state and position set
  def visited_twice(instruction_list, current_state, position_set) do
    [instruction | tail] = instruction_list
    {x, y, facing} = new_state(instruction, current_state)
    position_list = visited_positions(current_state, {x, y, facing})
    case consume_position_list(position_list, position_set) do
      {:position, position} -> position
      {:set, updated_set} -> visited_twice(tail, {x, y, facing}, updated_set)
    end
  end

  # take a list of positions
  # and a set of already visited positions
  # for every position in the list
  # return the position if it has been visited before
  # otherwise add it to the position set and recurse to cover the rest of the list
  # return the updated set of positions after consuming the entire list and not finding
  # any position visted before
  def consume_position_list([], position_set) do
    {:set, position_set}
  end
  def consume_position_list(position_list, position_set) do
    [position | tail] = position_list
    case position in position_set do
      true -> {:position, position}
      false -> consume_position_list(tail, MapSet.put(position_set, position))
    end
  end

  # all positions visited while transitioning states
  # (0,0) -> (4,0) returns [(1,0),(2,0),(3,0),(4,0)]
  # (0,0) -> (0,4) returns [(0,1),(0,2),(0,3),(0,4)]
  # initial position is not included otherwise
  # it would be added twice once as final position of previous state transition
  # and next time as initial position of current state transition
  # that means position_set has to start off with (0,0) in it
  # to handle the case of a cyclic path
  def visited_positions({x_initial, y_initial, _}, {x_final, y_final, _}) do
    cond do
      x_initial == x_final -> Enum.map(y_initial..y_final, fn(y) -> {x_initial, y} end) |> tl
      y_initial == y_final -> Enum.map(x_initial..x_final, fn(x) -> {x, y_initial} end) |> tl
    end
  end

  def output() do
    instruction_list = parse_input(@input)
    IO.puts("Part-1 solution is: #{final_state(instruction_list) |> block_distance}")
    IO.puts("Part-2 solution is: #{visited_twice(instruction_list, {0, 0, "N"}, MapSet.new([{0,0}])) |> block_distance}")
  end

end

    

You can find all my Advent of Code (2016) solutions here.