-
Notifications
You must be signed in to change notification settings - Fork 0
/
day05.ex
138 lines (111 loc) · 3.81 KB
/
day05.ex
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
defmodule Y2023.Day05 do
use Advent.Day, no: 05
@operation_order [:seed, :soil, :fertilizer, :water, :light, :temperature, :humidity, :location]
@block_size 1000
def part1(input) do
conversion_rules = generate_conversion_rules(input)
input.seeds
|> Enum.map(&convert(conversion_rules, &1, tl(@operation_order)))
|> Enum.min()
end
def part2(input, block_size \\ @block_size) do
seed_ranges =
input.seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [min, range] -> %{min: min, max: min + range - 1} end)
# Run the conversion in reverse, from location 0 until we find a valid seed.
inverted_order =
@operation_order
|> Enum.reverse()
|> tl()
data = invert_data(input, @operation_order, %{})
# Break down the location space - there will be a looooooooooot of invalid locations
# before we find a valid one
block = check_valid_location(0, block_size, data, seed_ranges, inverted_order)
# But once we do find one, it may not be the first valid one - there may be others in
# the space between the last check and this one
# This makes some assumptions - that there won't be a block of valid locations and
# then more invalid ones - but given the seven-digit sizes of the ranges in the input,
# it should be okay
check_valid_location(block - block_size, 1, data, seed_ranges, inverted_order)
end
defp generate_conversion_rules(input) do
@operation_order
|> tl()
|> Enum.reduce(%{}, fn key, acc ->
data =
input
|> Map.fetch!(key)
|> Enum.map(fn rule ->
%{
min: rule.source,
max: rule.source + rule.size - 1,
offset: rule.destination - rule.source
}
end)
Map.put(acc, key, data)
end)
end
defp invert_data(_input, [:location], data), do: data
defp invert_data(input, [prev, next | rest], data) do
rules = Map.fetch!(input, next)
inverted_rules =
Enum.map(rules, fn rule ->
%{
min: rule.destination,
max: rule.destination + rule.size - 1,
offset: rule.source - rule.destination
}
end)
data = Map.put(data, prev, inverted_rules)
invert_data(input, [next | rest], data)
end
defp check_valid_location(location, offset, input, seed_ranges, order) do
seed = convert(input, location, order)
if Enum.find(seed_ranges, fn range -> seed >= range.min && seed <= range.max end) do
location
else
check_valid_location(location + offset, offset, input, seed_ranges, order)
end
end
defp convert(input, val, order) do
Enum.reduce(order, val, fn operation, current ->
do_convert(input, operation, current)
end)
end
defp do_convert(input, operation, current) do
key =
input
|> Map.fetch!(operation)
|> Enum.find(fn rule -> current >= rule.min && current <= rule.max end)
case key do
nil -> current
%{offset: offset} -> offset + current
end
end
def parse_input(input) do
["seeds: " <> seeds | maps] = String.split(input, "\n\n", trim: true)
maps
|> Enum.reduce(%{seeds: parse_numbers(seeds)}, fn map, acc ->
{name, data} = parse_map(map)
Map.put(acc, String.to_atom(name), data)
end)
end
defp parse_numbers(numbers) do
numbers
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
defp parse_map(map) do
[name | data] = String.split(map, "\n", trim: true)
[_, "to", name, "map:"] = String.split(name, ["-", " "])
data =
Enum.map(data, fn row ->
[destination, source, size] = parse_numbers(row)
%{source: source, destination: destination, size: size}
end)
{name, data}
end
def part1_verify, do: input() |> parse_input() |> part1()
def part2_verify, do: input() |> parse_input() |> part2()
end