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
|
defmodule Day19 do
defmodule Onsen do
@derive Inspect
@enforce_keys [:patterns, :designs]
defstruct @enforce_keys
def from_data(data) do
[patterns, designs] = data
|> String.split("\n\n", trim: true)
patterns = patterns
|> String.split(", ", trim: true)
designs = designs
|> String.split("\n", trim: true)
%Onsen{patterns: patterns, designs: designs}
end
def count_feasible_designs(onsen) do
onsen.designs
|> Enum.filter(& feasible?(&1, onsen.patterns) |> elem(0))
|> Enum.count()
end
defp feasible?(design, patterns, vis \\ MapSet.new()) do
cond do
MapSet.member?(vis, design) ->
{false, vis}
design == "" ->
{true, vis}
true ->
for pat <- patterns, reduce: {false, MapSet.put(vis, design)} do
{acc, vis} ->
cond do
acc == true ->
{acc, vis}
String.starts_with?(design, pat) ->
design
|> String.split_at(String.length(pat))
|> elem(1)
|> feasible?(patterns, vis)
true ->
{acc, vis}
end
end
end
end
def count_feasible_ways(onsen) do
onsen.designs
|> Enum.map(& ways(&1, onsen.patterns) |> elem(0))
|> Enum.sum()
end
defp ways(design, patterns, vis \\ Map.new()) do
case Map.fetch(vis, design) do
{:ok, count} ->
{count, vis}
:error ->
if design == "" do
{1, vis}
else
for pat <- patterns, reduce: {0, vis} do
{acc, vis} ->
cond do
String.starts_with?(design, pat) ->
design
|> String.split_at(String.length(pat))
|> elem(1)
|> ways(patterns, vis)
|> then(fn {acc2, vis} -> {acc + acc2, vis} end)
true ->
{acc, vis}
end
end
|> then(fn {acc, vis} -> {acc, Map.put(vis, design, acc)} end)
end
end
end
end
def part1(data) do
data
|> Onsen.from_data()
|> Onsen.count_feasible_designs()
end
def part2(data) do
data
|> Onsen.from_data()
|> Onsen.count_feasible_ways()
end
end
data = IO.read(:stdio, :eof)
{time1, ans1} = :timer.tc(fn -> Day19.part1(data) end)
IO.puts("Time : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}")
{time2, ans2} = :timer.tc(fn -> Day19.part2(data) end)
IO.puts("Time : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}")
|
