Hey there 
No magic or algorithmic finesse today, I just finished the challenge and I my code is quite slow (1sec for part1, 3sec for part2).
But at least I managed to made my code readable and to reuse most of part1 for part2.
3 Likes
I did this too, and I want to see better solutions. 
I’ve gone ahead with a genserver for the simulation (not really needed but 
) and a state struct, which even implements String.Chars (mostly for comparing to the examples in tests). I like the code, but it’s not very fast as well.
by the way, I often need to do some while true ... break in AOC challenges
Here is what I use instead:
Stream.cycle([0])
|> Enum.reduce_while([], fn _, acc ->
...
end)
Working, but I don’t really like the [0] list coming from nowhere.
Any other way?
Recursion if it’s truely while do or do while:
My other goto for evaluation (does not always fit) is Stream.unfold:
1 Like
There are many cases where it works well to build a Stream, filter it, and take 1.
Mine is also quite slow (~3s for p2) but at least the code is not too convoluted this time
defmodule AdventOfCode.Day11 do
def part1(input) do
input
|> make_grid()
|> next(&switch_status/2)
end
def part2(input) do
input
|> make_grid()
|> next(&switch_status_2/2)
end
def make_grid(input) do
for {row, row_index} <- input |> String.split("\n") |> Enum.with_index(),
{col, col_index} <- row |> String.codepoints() |> Enum.with_index(),
into: %{},
do: {{col_index, row_index}, col}
end
def seat_status(grid, x, y) do
Map.get(grid, {x, y})
end
def count_occupied_seats(grid) do
grid
|> Map.values()
|> Enum.count(&(&1 == "#"))
end
def next(grid, switch_fn) do
new_grid =
grid
|> Enum.filter(fn {_k, v} -> v != "." end)
|> Enum.map(&switch_fn.(grid, &1))
|> Enum.into(grid)
if new_grid == grid, do: count_occupied_seats(grid), else: next(new_grid, switch_fn)
end
def switch_status(grid, {{x, y}, status}) do
adjacent =
for other_x <- (x - 1)..(x + 1),
other_y <- (y - 1)..(y + 1),
{other_x, other_y} != {x, y},
seat_status(grid, other_x, other_y) == "#" do
true
end
|> length()
cond do
status == "#" and adjacent >= 4 -> {{x, y}, "L"}
status == "L" and adjacent == 0 -> {{x, y}, "#"}
true -> {{x, y}, status}
end
end
def switch_status_2(grid, {pos, status}) do
in_sight =
[{-1, -1}, {-1, 0}, {-1, +1}, {0, -1}, {0, +1}, {1, -1}, {1, 0}, {1, 1}]
|> Enum.map(&in_line_of_sight(grid, pos, &1))
|> Enum.count(& &1)
cond do
status == "#" and in_sight >= 5 -> {pos, "L"}
status == "L" and in_sight == 0 -> {pos, "#"}
true -> {pos, status}
end
end
def in_line_of_sight(grid, {x, y}, dir = {dir_x, dir_y}) do
{new_x, new_y} = {x + dir_x, y + dir_y}
case seat_status(grid, new_x, new_y) do
"#" -> true
"L" -> false
nil -> false
_ -> in_line_of_sight(grid, {new_x, new_y}, dir)
end
end
# for debugging
def visualize_grid(grid) do
max_x = grid |> Enum.map(fn {{x, _y}, _} -> x end) |> Enum.max()
max_y = grid |> Enum.map(fn {{_x, y}, _} -> y end) |> Enum.max()
for y <- 0..max_y do
for x <- 0..max_x do
Map.get(grid, {x, y})
end
|> Enum.join()
end
|> Enum.join("\n")
|> IO.puts()
end
end
Could’ve used a better line of sight calculation. Oh, well.
defmodule Day11.Grid do
@empty "L"
@occupied "#"
@space "."
@seats [@empty, @occupied]
def seat?(row, col, grid), do: Map.get(grid, {row, col}) in @seats
def up(-1, _col, _area), do: {-1, -1}
def up(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: up(row - 1, col, area)
end
def down(row, _, {numrows, _, _}) when row == numrows, do: {-1, -1}
def down(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: down(row + 1, col, area)
end
def left(_row, -1, _area), do: {-1, -1}
def left(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: left(row, col - 1, area)
end
def right(_, col, {_, numcols, _}) when col == numcols, do: {-1, -1}
def right(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: right(row, col + 1, area)
end
def ne(-1, _col, _area), do: {-1, -1}
def ne(_row, -1, _area), do: {-1, -1}
def ne(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: ne(row - 1, col - 1, area)
end
def nw(-1, _col, _area), do: {-1, -1}
def nw(_row, col, {_, numcols, _}) when col == numcols, do: {-1, -1}
def nw(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: nw(row - 1, col + 1, area)
end
def se(_row, -1, _area), do: {-1, -1}
def se(row, _col, {numrows, _, _}) when row == numrows, do: {-1, -1}
def se(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: se(row + 1, col - 1, area)
end
def sw(row, col, {numrows, numcols, _}) when row == numrows or col == numcols,
do: {-1, -1}
def sw(row, col, {_, _, grid} = area) do
if seat?(row, col, grid), do: {row, col}, else: sw(row + 1, col + 1, area)
end
def dirs(row, col, _area, 1 = _part) do
[
{row, col - 1},
{row, col + 1},
{row - 1, col},
{row + 1, col},
{row - 1, col - 1},
{row - 1, col + 1},
{row + 1, col - 1},
{row + 1, col + 1}
]
end
def dirs(row, col, area, 2 = _part) do
[
left(row, col - 1, area),
right(row, col + 1, area),
up(row - 1, col, area),
down(row + 1, col, area),
ne(row - 1, col - 1, area),
nw(row - 1, col + 1, area),
se(row + 1, col - 1, area),
sw(row + 1, col + 1, area)
]
end
def occupiedaround(row, col, {numrows, numcols, grid} = area, part) do
dirs(row, col, area, part)
|> Enum.count(fn {r, c} ->
r in 0..(numrows - 1) and c in 0..(numcols - 1) and Map.get(grid, {r, c}) == @occupied
end)
end
def change({r, c, @space}, _area, _part), do: {{r, c}, @space}
def change({r, c, @empty}, area, part) do
countoccupied = occupiedaround(r, c, area, part)
{{r, c}, if(countoccupied == 0, do: @occupied, else: @empty)}
end
def change({r, c, @occupied}, area, part) do
countoccupied = occupiedaround(r, c, area, part)
maxfree = if part == 1, do: 3, else: 4
{{r, c}, if(countoccupied > maxfree, do: @empty, else: @occupied)}
end
def seatround({numrows, numcols, grid} = area, part) do
newgrid =
for col <- 0..(numcols - 1),
row <- 0..(numrows - 1) do
change({row, col, Map.get(grid, {row, col})}, area, part)
end
|> Enum.reduce(%{}, fn {k, v}, acc -> Map.put(acc, k, v) end)
{numrows, numcols, newgrid}
end
def countoccupied({numrows, numcols, grid}) do
for(
col <- 0..(numcols - 1),
row <- 0..(numrows - 1),
do: Map.get(grid, {row, col}) == @occupied
)
|> Enum.count(& &1)
end
def printarea({numrows, numcols, grid} = area) do
for(col <- 0..(numcols - 1), row <- 0..(numrows - 1), do: Map.get(grid, {row, col}))
|> Enum.chunk_every(numrows)
|> Enum.map(&Enum.join(&1, ""))
|> Enum.join("\n")
|> IO.puts()
area
end
end
defmodule Day11 do
alias Day11.Grid
def readinput() do
rows =
File.read!("11.test.txt")
|> String.split("\n", trim: true)
numrows = length(rows)
numcols = String.length(Enum.at(rows, 0))
grid =
rows
|> Enum.with_index()
|> Enum.flat_map(fn {rowstr, rownum} ->
String.graphemes(rowstr)
|> Enum.with_index()
|> Enum.flat_map(fn {letter, colnum} -> %{{rownum, colnum} => letter} end)
end)
|> Enum.into(%{})
{numrows, numcols, grid}
end
def untilstable(area, occupied, part) do
newarea = Grid.seatround(area, part)
newoccupied = Grid.countoccupied(newarea)
if newoccupied == occupied, do: newoccupied, else: untilstable(newarea, newoccupied, part)
end
def part1(area \\ readinput()) do
untilstable(area, Grid.countoccupied(area), 1)
end
def part2(area \\ readinput()) do
untilstable(area, Grid.countoccupied(area), 2)
end
end
I can replace most of that crunk with
def move(-1, _col, _delta, _area), do: {-1, -1}
def move(_row, -1, _delta, _area), do: {-1, -1}
def move(row, _col, _delta, {numrows, _, _}) when row == numrows, do: {-1, -1}
def move(_row, col, _delta, {_, numcols, _}) when col == numcols, do: {-1, -1}
def move(row, col, {dx, dy} = delta, {_, _, grid} = area) do
newrow = row + dx
newcol = col + dy
if seat?(newrow, newcol, grid), do: {newrow, newcol}, else: move(newrow, newcol, delta, area)
end
def dirs(row, col, area, 2 = _part) do
[
move(row, col, {0, -1}, area),
move(row, col, {0, 1}, area),
move(row, col, {-1, 0}, area),
move(row, col, {1, 0}, area),
move(row, col, {-1, -1}, area),
move(row, col, {-1, 1}, area),
move(row, col, {1, -1}, area),
move(row, col, {1, 1}, area),
]
end
Most of those computations involving coordinates can be done with vector math and {x, y} is basically the simplest form of representing an vector.
Ended up putting all the seats in a map and then lookup them up to calculate occupied seats. Also learnt the lesson of making sure to copy the entire test data instead of all but the last ten lines…
Anyone know of a nicer way to iterate a stream until it stabilises, what I ended up with felt a bit cumbersome.
# Part 2
defmodule AdventOfCode.Day11 do
def run() do
AdventOfCode.Helpers.Data.read_from_file("day11.txt")
|> to_room()
|> Stream.iterate(&iterate/1)
|> Stream.chunk_every(2, 1)
|> Stream.filter(fn [new, last] -> new == last end)
|> Enum.take(1)
|> (fn [[x, _]] -> x end).()
|> occupied_seats()
end
def occupied_seats(%{seats: seats}) do
seats
|> Enum.filter(fn {_, state} -> state == "#" end)
|> Enum.count()
end
def to_room(lines) do
seats = lines |> Enum.with_index() |> Enum.map(&create_row/1) |> Enum.reduce(&Map.merge/2)
%{width: String.graphemes(hd(lines)) |> Enum.count(), height: Enum.count(lines), seats: seats}
end
def create_row({line, row_nr}) do
line
|> String.graphemes()
|> Enum.with_index()
|> Enum.filter(fn {spot, _} -> spot != "." end)
|> Enum.reduce(%{}, fn {spot, col}, acc -> Map.put(acc, {row_nr, col}, spot) end)
end
def iterate(%{seats: seats} = room) do
new_seats =
seats
|> Enum.map(fn {{row, col} = pos, state} -> {pos, update_room(room, row, col, state)} end)
|> Map.new()
%{room | seats: new_seats}
end
def update_room(room, row, col, state) do
update_room(occupied(room, row, col), state)
end
def update_room(occupied, state) when occupied == 0 and state == "L", do: "#"
def update_room(occupied, state) when occupied >= 5 and state == "#", do: "L"
def update_room(_, state), do: state
def occupied(room, row, col) do
["N", "E", "S", "W", "NW", "NE", "SE", "SW"]
|> Enum.map(fn direction -> occupied(room, direction, row, col) end)
|> Enum.reduce(&(&1 + &2))
end
def check_dir(%{height: height, width: width}, _, row, col)
when row < 0 or row >= height or col < 0 or col >= width do
0
end
def check_dir(%{seats: seats} = room, direction, row, col) do
case Map.get(seats, {row, col}) do
nil -> occupied(room, direction, row, col)
"#" -> 1
"L" -> 0
end
end
def occupied(room, "N", row, col), do: check_dir(room, "N", row - 1, col)
def occupied(room, "E", row, col), do: check_dir(room, "E", row, col + 1)
def occupied(room, "S", row, col), do: check_dir(room, "S", row + 1, col)
def occupied(room, "W", row, col), do: check_dir(room, "W", row, col - 1)
def occupied(room, "NW", row, col), do: check_dir(room, "NW", row - 1, col - 1)
def occupied(room, "NE", row, col), do: check_dir(room, "NE", row - 1, col + 1)
def occupied(room, "SE", row, col), do: check_dir(room, "SE", row + 1, col + 1)
def occupied(room, "SW", row, col), do: check_dir(room, "SW", row + 1, col - 1)
end
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
1 Like
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 Like
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
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.
Yeah, I also just use recursion for that, same as @LostKobrakai.
Stopping when stable:
Stopping as soon as we find the first occupied seat (nil = coordinate not in grid AKA no occupied seat in that direction):
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
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
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
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 Like
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)
