~ihabunek/aoc2018

aoc2018/elixir/lib/day18.exs -rw-r--r-- 3.6 KiB
d99cc364Ivan Habunek Day 15, speedup, part1 done 1 year, 10 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# --- Day 18: Settlers of The North Pole ---
# https://adventofcode.com/2018/day/18

defmodule Day18 do
  def parse_char(char) do
    case char do
      ?. -> :open
      ?| -> :tree
      ?# -> :yard
    end
  end

  def parse_input(input) do
    input
    |> String.split("\n")
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {line, y}, acc ->
      line
      |> to_charlist()
      |> Enum.with_index()
      |> Enum.reduce(acc, fn {char, x}, acc ->
        Map.put(acc, {x, y}, parse_char(char))
      end)
    end)
  end

  def frequencies(values) do
    Enum.reduce(values, %{}, fn value, acc ->
      Map.update(acc, value, 1, &(&1 + 1))
    end)
  end

  def count_adjacent(grid, {x, y}) do
    for x <- (x - 1)..(x + 1),
        y <- (y - 1)..(y + 1) do
      {x, y}
    end
    |> List.delete({x, y})
    |> Enum.map(fn pos -> Map.get(grid, pos) end)
    |> frequencies
  end

  defp has(map, type, count) do
    Map.get(map, type, 0) >= count
  end

  def next_cell(grid, pos) do
    field = Map.get(grid, pos)
    adj = count_adjacent(grid, pos)

    case field do
      :open -> if has(adj, :tree, 3), do: :tree, else: :open
      :tree -> if has(adj, :yard, 3), do: :yard, else: :tree
      :yard -> if has(adj, :yard, 1)
              and has(adj, :tree, 1), do: :yard, else: :open
    end
  end

  def tick(grid) do
    Enum.reduce(grid, %{}, fn {pos, _}, new_grid ->
      Map.put(new_grid, pos, next_cell(grid, pos))
    end)
  end

  def cycle(grid, count) do
    Enum.reduce(1..count, grid, fn n, grid ->
      tick(grid)  # |> Day18Debug.dump_file(n) # Uncomment to dump files
    end)
  end

  def find_loop(grid) do
    # Map grid to tick on which it was first seen
    visited = %{}

    Enum.reduce_while(1..1_000_000_000, {grid, visited}, fn n, {grid, visited} ->
      seen_n = Map.get(visited, grid)

      if seen_n do
        {:halt, {seen_n, n, visited}}
      else
        {:cont, {tick(grid), Map.put(visited, grid, n)}}
      end
    end)
  end

  def score(grid) do
    freqs = grid |> Map.values() |> frequencies()
    trees = Map.get(freqs, :tree, 0)
    yards = Map.get(freqs, :yard, 0)
    trees * yards
  end

  def part1(input) do
    input
    |> parse_input
    |> cycle(10)
    |> score()
  end

  def part2(input) do
    target = 1_000_000_000
    grid = input |> parse_input

    {x, y, visited} = find_loop(grid)         # x, y are the bounds of the loop
    loop_size = y - x
    loop_count = div((target - x), loop_size) # this many loops can be skipped
    skip_count = loop_count * loop_size       # this many ticks can be skipped
    new_target = target - skip_count

    # The wanted grid is already in visited map, no need to loop again
    {grid, _} = visited |> Enum.find(fn {_, n} -> n == new_target end)

    score(grid)
  end
end

defmodule Day18Debug do
  def get_bounds(grid) do
    positions = Map.keys(grid) |> Enum.sort()
    {
      List.first(positions),
      List.last(positions)
    }
  end

  def as_string(grid) do
    {{x0, y0}, {x1, y1}} = get_bounds(grid)

    for y <- y0..y1 do
      for x <- x0..x1 do
        case Map.get(grid, {x, y}) do
          :open -> ?.
          :tree -> ?|
          :yard -> ?#
        end
      end
      |> to_string
    end
    |> Enum.join("\n")
  end

  def dump(grid) do
    IO.puts(as_string(grid))
    grid
  end

  def dump_file(grid, n) do
    file = n |> to_string |> String.pad_leading(10, "0")
    path = "tmp/#{file}.txt"
    File.write!(path, as_string(grid))
    grid
  end
end

input = File.read!("lib/day18.in")

IO.write("Part 1: ")
Day18.part1(input) |> IO.inspect()

IO.write("Part 2: ")
IO.inspect(Day18.part2(input))