I ended up writing a generator to create my adventofcode files for each challenge and to download the puzzle as well. You can use the code if you want to
cblavier
Papey
I ended up with something nice for finding neighbours on part 2, but wow, this is veeeerryyyy slooooow (~4 seconds)
def neighbours(current, {x, y}) do
Enum.reduce(@dirs, 0, fn {dx, dy}, acc ->
[v] =
Stream.iterate(1, &(&1 + 1))
|> Stream.map(fn mul -> {x + dx * mul, y + dy * mul} end)
|> Stream.map(fn {xx, yy} -> Map.get(current, {xx, yy}) end)
|> Stream.drop_while(&(&1 == @floor))
|> Enum.take(1)
if v == @occupied, do: acc + 1, else: acc
end)
end
I was thinking about the fact that the current map is RO, did someone try to add some concurrency into the mix ?
1
ricardo-h
ugly and not optimized brute force but it works
defmodule Advent.Day11 do
def start(part \\ :part1, file \\ "/tmp/input.txt"), do:
File.read!(file) |> String.split() |> normalize_input() |> execute(part)
defp execute({seats, rows, cols}, part), do:
1..(rows * cols) |> Enum.reduce({false, %{}}, fn idx, {changed, acc} ->
state = seats[idx]
new_state = verify_seat(state, seats, idx, rows, part)
{changed || new_state != state, Map.put(acc, idx, new_state)}
end)
|> execute(rows, cols, part)
defp execute({true, seats}, rows, cols, part), do: execute({seats, rows, cols}, part)
defp execute({false, seats}, _rows, _cols, _part), do: seats |> Map.to_list() |> Enum.count(fn {_, v} -> v == ?# end)
def get_adjacent_state(seats, idx, rows, :part1) do
r = rem(idx, rows)
[ (r == 1) && ?. || (seats[idx - rows - 1]),
seats[idx - rows],
(r == 0) && ?. || (seats[idx - rows + 1]),
(r == 1) && ?. || (seats[idx - 1]),
(r == 0) && ?. || (seats[idx + 1]),
(r == 1) && ?. || (seats[idx + rows - 1]),
seats[idx + rows],
(r == 0) && ?. || (seats[idx + rows + 1])]
end
def get_adjacent_state(seats, idx, rows, :part2), do:
[ get_vertical(seats, idx, rows, - 1 - rows, 1),
get_vertical(seats,idx, rows, -rows, - 1),
get_vertical(seats, idx, rows, -rows + 1, 0),
get_horizontal(seats, idx, rows, 1),
get_horizontal(seats, idx, rows, 0),
get_vertical(seats, idx, rows, rows - 1, 1),
get_vertical(seats, idx, rows, rows, -1),
get_vertical(seats, idx, rows, rows + 1, 0)
]
def verify_seat(?., _seats, _idx, _rows, _part), do: ?.
def verify_seat(?L, seats, idx, rows, part), do:
(get_adjacent_state(seats, idx, rows, part) |> Enum.any?(fn o -> o == ?# end)) && ?L || ?#
def verify_seat(?#, seats, idx, rows, part), do:
(get_adjacent_state(seats, idx, rows, part) |> Enum.count(fn o -> o == ?# end) > (part == :part1 && 3 || 4)) && ?L || ?#
defp normalize_input(lst), do:
Enum.reduce(lst, {1, %{}}, fn lst, {idx, acc} ->
lst |> String.to_charlist() |> Enum.reduce({idx, acc}, fn el, {idx, acc} ->
{idx + 1, Map.put(acc, idx, el)}
end)
end) |> (fn x -> {elem(x, 1), List.first(lst) |> String.length(), length(lst)} end).()
def get_vertical(seats, idx, rows, delta_rows, rr), do:
(rem(idx, rows) == rr) && ?. || (
case seats[idx + delta_rows] do
nil -> ?.
?. -> get_vertical(seats, idx + delta_rows, rows, delta_rows, rr)
v -> v
end
)
def get_horizontal(seats, idx, rows, rr) do
delta = rr == 1 && -1 || 1
(rem(idx, rows) == rr) && ?. || (
case seats[idx + delta] do
nil -> ?.
?. -> get_horizontal(seats, idx + delta, rows, rr)
v -> v
end
)
end
end
0
aaronnamba
No, the first optimization that comes to mind is precomputing/caching the first visible seat location for each seat, because they will never change. Haven’t seen anyone do it yet, and I didn’t bother because I’m happy as long as I get the right answer. 
0
adamu
Yeah, I also just use recursion for that, same as @LostKobrakai.
Stopping when stable:
https://github.com/adamu/AdventOfCode2020/blob/main/day11/day11part2.exs#L12-L20
Stopping as soon as we find the first occupied seat (nil = coordinate not in grid AKA no occupied seat in that direction):
https://github.com/adamu/AdventOfCode2020/blob/main/day11/day11part2.exs#L69-L78
Actually thinking about it, I’m currently counting the number of occupied seats in all directions, but could stop when it hits 4/5 instead of continuing to count all 8. Anyway, day 12 in an hour
0
stevensonmt
I swear my code is almost identical to yours but I’m timing out on part 2 and can’t figure out why. Can anyone tell me where the bottleneck is?
defmodule Day11 do
@input File.stream!("lib/input")
|> Stream.with_index()
|> Stream.map(fn {line, row} -> {row, String.graphemes(String.trim(line))} end)
|> Stream.flat_map(fn {row, line} ->
line
|> Stream.with_index()
|> Stream.map(fn {spot, col} -> {{col, row}, spot} end)
end)
|> Enum.into(%{})
@adjacent [{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}]
def apply_rules(map, part) do
map
|> Stream.filter(fn {_k, v} -> v != "." end)
|> Stream.map(fn {coord, seat} ->
case seat do
"L" ->
if make_occupied?(coord, map, part) do
{coord, "#"}
else
{coord, seat}
end
"#" ->
if make_empty?(coord, map, part) do
{coord, "L"}
else
{coord, seat}
end
end
end)
|> Enum.into(map)
end
def make_occupied?({col, row}, map, _) do
@adjacent
|> Stream.map(fn {a, b} -> {col + a, row + b} end)
|> Stream.map(fn k ->
Map.get(map, k)
end)
|> Enum.all?(fn v -> v != "#" end)
end
def make_empty?({col, row}, map, 1) do
@adjacent
|> Stream.map(fn {a, b} -> {col + a, row + b} end)
|> Stream.map(fn k -> Map.get(map, k) end)
|> Stream.filter(fn v -> v == "#" end)
|> Enum.count()
|> Kernel.>=(4)
end
def make_empty?({col, row}, map, 2) do
find_first_visible({col, row}, map)
|> Stream.filter(fn v -> v end)
|> Enum.count()
|> Kernel.>=(5)
end
def part_1() do
run(@input, 1)
end
def run(map, part) do
run(map, apply_rules(map, part), part)
end
def run(map, new_map, part) do
if Map.equal?(map, new_map) do
count_occupied(new_map)
else
run(new_map, apply_rules(new_map, part), part)
end
end
def count_occupied(map) do
map
|> Stream.filter(fn {_, v} -> v == "#" end)
|> Enum.count()
end
def find_first_visible({col, row}, map) do
@adjacent
|> Enum.map(fn dir -> find_first_visible({col, row}, map, dir) end)
end
def find_first_visible({col, row}, map, {a, b}) do
case Map.get(map, {col + a, row + b}) do
nil ->
false
"." ->
find_first_visible({col + a, row + b}, map, {a, b})
"L" ->
false
"#" ->
true
end
end
def part_2() do
run(@input, 2)
end
end
0
adamu
You need to consider the full line of sight for an empty seat too. An empty seat becomes occupied if there are 0 occupied seats visible in all directions, but you are only checking the immediately adjacent seats.
def make_occupied?({col, row}, map, 1) do
@adjacent
|> Stream.map(fn {a, b} -> {col + a, row + b} end)
|> Stream.map(fn k ->
Map.get(map, k)
end)
|> Enum.all?(fn v -> v != "#" end)
end
def make_occupied?({col, row}, map, 2) do
find_first_visible({col, row}, map)
|> Stream.filter(fn v -> v end)
|> Enum.count()
|> Kernel.==(0)
end
0
felix-alonso
I think I had a similar experience today. Worked out okay, but a bit slower than I would like (~1s/~3s).
defmodule Day11 do
defguard in_bounds(x, list) when 0 <= x and x < length(list)
def part_1, do: solve(&by_adjacency/4)
def part_2, do: solve(&by_visibility/4)
def solve(method) do
load()
|> find_stable(method)
|> count_occupied()
end
def count_occupied(seats) do
seats
|> Enum.map(fn row -> Enum.count(row, &(&1 == ?#)) end)
|> Enum.sum()
end
def find_stable(seats, transform) do
case next_gen(seats, transform) do
next when next == seats -> next
next -> find_stable(next, transform)
end
end
def next_gen(seats, transform) do
for {row, r_idx} <- Enum.with_index(seats) do
for {seat, c_idx} <- Enum.with_index(row) do
transform.(seats, seat, r_idx, c_idx)
end
end
end
def by_visibility(_, ?., _, _), do: ?.
def by_visibility(seats, ?L, row, col) do
if visible(seats, row, col) == 0, do: ?#, else: ?L
end
def by_visibility(seats, ?#, row, col) do
if visible(seats, row, col) >= 5, do: ?L, else: ?#
end
def visible(seats, r_idx, c_idx) do
directions()
|> Enum.count(fn {x, y} -> next(seats, r_idx + x, c_idx + y, x, y) end)
end
def next(_, row, col, _, _) when row < 0 or col < 0, do: false
def next(seats, row, col, drow, dcol) do
case get_seat(seats, row, col) do
?. -> next(seats, row + drow, col + dcol, drow, dcol)
x -> x == ?#
end
end
def by_adjacency(_, ?., _, _), do: ?.
def by_adjacency(seats, ?L, row, col) do
if adjacent(seats, row, col) == 0, do: ?#, else: ?L
end
def by_adjacency(seats, ?#, row, col) do
if adjacent(seats, row, col) >= 4, do: ?L, else: ?#
end
def adjacent(seats, row, col) do
directions()
|> Enum.count(fn {x, y} -> get_seat(seats, row + x, col + y) == ?# end)
end
def directions do
for x <- -1..1, y <- -1..1, not_origin(x, y), do: {x, y}
end
def not_origin(x, y), do: not(x == 0 and y == 0)
def get_seat(seats=[fst|_], row, col)
when in_bounds(row, seats) and in_bounds(col, fst),
do: seats |> Enum.at(row) |> Enum.at(col)
def get_seat(_, _, _), do: nil
def load do
File.read!("day-11.input")
|> String.split("\n", trim: true)
|> Enum.map(&String.to_charlist/1)
end
end
1
stevensonmt
ah, I misread the problem. Thanks.
After fixing that issue I went ahead and implemented the optimization @aaronnamba suggested. I’m not sure that was the bottleneck for me b/c it’s still slow. Anyway, got the right answer so moving on.
defmodule Day11Helper do
def find_first_visible({col, row}, map, {a, b}) do
case Map.get(map, {col + a, row + b}) do
nil ->
false
"." ->
find_first_visible({col + a, row + b}, map, {a, b})
"L" ->
{col + a, row + b}
"#" ->
{col + a, row + b}
end
end
def cache_first_visible(input, adjacent) do
input
|> Enum.map(fn {{col, row} = coord, _seat} ->
{coord,
adjacent
|> Enum.map(fn dir -> find_first_visible({col, row}, input, dir) end)}
end)
|> Enum.into(%{})
end
end
defmodule Day11 do
...
@cache_first_visible Day11Helper.cache_first_visible(@input, @adjacent)
0
akash-akya
Had some time yesterday to try this one. It takes ~0.31s for the part-1 and ~0.72s for part-2.
This might be a different approach compared to the solutions here, not using map for the grid since we only need to know about surrounding seats. Code can be made more readable I guess 
defmodule AOC2020.Day11 do
def parse(input) do
String.split(input, "\n", trim: true)
|> Enum.map(&String.codepoints(&1))
end
def show(room) do
Enum.map(room, &IO.puts(Enum.join(&1)))
room
end
def count_occupied(room) do
Enum.map(room, fn row -> Enum.count(row, &(&1 == "#")) end)
|> Enum.sum()
end
def sample_input do
"""
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
"""
end
defmodule PartOne do
alias AOC2020.Day11
defp new_seat_state(adj_seats, cur) do
count = Enum.count(adj_seats, fn v -> v == "#" end)
cond do
count == 0 && cur == "L" -> "#"
count >= 4 && cur == "#" -> "L"
true -> cur
end
end
defp do_traverse_row(
[t_left, t],
[c_left, c],
[b_left, b]
) do
[new_seat_state([t_left, t, c_left, b_left, b], c)]
end
defp do_traverse_row(
[t_left | [t, t_right | _] = top],
[c_left | [c, c_right | _] = cur],
[b_left | [b, b_right | _] = bottom]
) do
seat = new_seat_state([t_left, t, t_right, c_left, c_right, b_left, b, b_right], c)
[seat | do_traverse_row(top, cur, bottom)]
end
defp traverse_row(
[t, t_right | _] = top,
[c, c_right | _] = cur,
[b, b_right | _] = bottom
) do
seat = new_seat_state([t, t_right, c_right, b, b_right], c)
[seat | do_traverse_row(top, cur, bottom)]
end
defp do_traverse_room([top, cur]) do
bottom = Enum.map(cur, fn _ -> "." end)
row = traverse_row(top, cur, bottom)
[row]
end
defp do_traverse_room([top, cur, bottom | rest]) do
row = traverse_row(top, cur, bottom)
[row | do_traverse_room([cur, bottom | rest])]
end
defp traverse_room([cur, bottom | _] = room) do
top = Enum.map(cur, fn _ -> "." end)
row = traverse_row(top, cur, bottom)
[row | do_traverse_room(room)]
end
defp do_run(room) do
new_room = traverse_room(room)
if new_room == room do
new_room
else
do_run(new_room)
end
end
def run(input) do
Day11.parse(input)
|> do_run()
|> Day11.count_occupied()
end
end
# part 2
defmodule PartTwo do
alias AOC2020.Day11
defp invert(m), do: Enum.reduce(m, [], &[Enum.reverse(&1) | &2])
defp merge_row([], []), do: []
defp merge_row([a | adj_rest], [b | i_adj_rest]) do
[
Map.merge(a, %{
right: b[:left],
bottom_right: b[:top_left],
bottom: b[:top],
bottom_left: b[:top_right]
})
| merge_row(adj_rest, i_adj_rest)
]
end
defp merge([], []), do: []
defp merge([adj_row | adj], [i_adj_row | i_adj]) do
[merge_row(adj_row, i_adj_row) | merge(adj, i_adj)]
end
defp do_row_cache([t_left, t], [c_left, c]) do
seat_cache =
case c do
"." -> %{top_left: t_left.top_left, top: t.top, top_right: ".", left: c_left.left}
"#" -> %{top_left: "#", top: "#", top_right: "#", left: "#"}
"L" -> %{top_left: "L", top: "L", top_right: "L", left: "L"}
end
[seat_cache]
end
defp do_row_cache(
[t_left | [t, t_right | _] = top],
[c_left | [c | rest]]
) do
seat_cache =
case c do
"." ->
%{
top_left: t_left.top_left,
top: t.top,
top_right: t_right.top_right,
left: c_left.left
}
"#" ->
%{top_left: "#", top: "#", top_right: "#", left: "#"}
"L" ->
%{top_left: "L", top: "L", top_right: "L", left: "L"}
end
[seat_cache | do_row_cache(top, [seat_cache | rest])]
end
defp row_cache([t, t_right | _] = top, [c | cur]) do
seat_cache =
case c do
"." -> %{top_left: ".", top: t.top, top_right: t_right.top_right, left: "."}
"#" -> %{top_left: "#", top: "#", top_right: "#", left: "#"}
"L" -> %{top_left: "L", top: "L", top_right: "L", left: "L"}
end
[seat_cache | do_row_cache(top, [seat_cache | cur])]
end
defp adj_cache(top, [cur]), do: [row_cache(top, cur)]
defp adj_cache(top, [cur, bottom | rest]) do
new_cur = row_cache(top, cur)
[new_cur | adj_cache(new_cur, [bottom | rest])]
end
defp create_adj_cache([cur, bottom | rest]) do
top = Enum.map(cur, fn _ -> %{top_left: ".", top: ".", top_right: "."} end)
new_cur = row_cache(top, cur)
[new_cur | adj_cache(new_cur, [bottom | rest])]
end
defp new_seat_state(adj_seats, cur) do
count = Enum.count(adj_seats, fn v -> v == "#" end)
cond do
count == 0 && cur == "L" -> "#"
count >= 5 && cur == "#" -> "L"
true -> cur
end
end
defp do_traverse_row(
[c],
[t_left | [t | _]],
[c_left | [_ | _]],
[b_left | [b | _]]
) do
seat =
new_seat_state(
[
t_left[:top_left],
t[:top],
b[:bottom],
b_left[:bottom_left],
c_left[:left]
],
c
)
[seat]
end
defp do_traverse_row(
[c | row],
[t_left | [t, t_right | _] = top],
[c_left | [_, c_right | _] = cur],
[b_left | [b, b_right | _] = bottom]
) do
seat =
new_seat_state(
[
t_left[:top_left],
t[:top],
t_right[:top_right],
c_right[:right],
b_right[:bottom_right],
b[:bottom],
b_left[:bottom_left],
c_left[:left]
],
c
)
[seat | do_traverse_row(row, top, cur, bottom)]
end
defp traverse_row(
[c | row],
[t, t_right | _] = top,
[_, c_right | _] = cur,
[b, b_right | _] = bottom
) do
seat =
new_seat_state(
[
t[:top],
t_right[:top_right],
c_right[:right],
b[:bottom],
b_right[:bottom_right]
],
c
)
[seat | do_traverse_row(row, top, cur, bottom)]
end
defp do_traverse_room([cur], [near_prev, near_cur]) do
near_next = Enum.map(cur, fn _ -> %{bottom_right: ".", bottom: ".", bottom_left: "."} end)
[traverse_row(cur, near_prev, near_cur, near_next)]
end
defp do_traverse_room([cur | room], [near_prev, near_cur, near_next | rest]) do
new_row = traverse_row(cur, near_prev, near_cur, near_next)
[new_row | do_traverse_room(room, [near_cur, near_next | rest])]
end
defp traverse_room([cur | room], [near_cur, near_next | _] = near) do
near_prev = Enum.map(cur, fn _ -> %{top_left: ".", top: ".", top_right: "."} end)
new_row = traverse_row(cur, near_prev, near_cur, near_next)
[new_row | do_traverse_room(room, near)]
end
defp compute_new_room_state(room) do
adj = create_adj_cache(room)
i_adj = create_adj_cache(invert(room))
adj = merge(adj, invert(i_adj))
traverse_room(room, adj)
end
defp do_run(room) do
new_room = compute_new_room_state(room)
if new_room == room do
new_room
else
do_run(new_room)
end
end
def run(input) do
Day11.parse(input)
|> do_run()
|> Day11.count_occupied()
end
end
end
This vaguely reminded me of convolution matrix.
0