Part 2 very dissatisfying. I tried a couple of approaches that I was clearly not smart enough to implement. I tried checking that a high percentage of bots were contained within a triangle using barycentric coordinates to confirm presence within the triangle. I think I either set the threshold too high or screwed up the implementation b/c it would run forever without finding it.
I then tried to find a state where a high percentage of bots had mirror image bots across a line of reflection. I think I screwed this up by again setting the threshold too high.
Finally I just looked for a state where at least 20 bots were in at least one column and 20 bots were in at least one row. That worked but feels like blind luck.
EDIT: Yeah, setting the threshold to a super majority of bots was way off. Setting it to 20% of the bots having mirrored bots is good enough. I think the problem was worded such that it is misleading to say “most of the robots” arrange into the Christmas tree. Pretty sure my tree has fewer than half the bots in it.
EDIT 2: Got my barycentric triangle method working. It requires a slightly higher threshold than the mirrored bots method to avoid false positive.
def find_tree() do
Stream.repeatedly(fn -> Robot.move_all(1) end)
|> Enum.reduce_while(1, fn :ok, time ->
if tree_shape?() do
{:halt, time}
else
{:cont, time + 1}
end
end)
end
defp tree_shape?() do
min_bots =
case :ets.lookup_element(:board, :bot_count, 2, false) do
false ->
x = Robot.bot_count()
:ets.insert(:board, {:bot_count, x})
0.4 * x
x ->
0.4 * x
end
# min_bots in symmetric pattern bounded by isosceles triangle
# triangle has area == min_bots and assume ht == base
# bots inside triangle have mirror or are on center line
botspots =
all_occupants()
|> Enum.map(fn {pos, _name} -> pos end)
|> MapSet.new()
[ht, wd] = [:height, :width] |> Enum.map(fn k -> :ets.lookup_element(:board, k, 2) end)
reflect = 50
triangle = [{reflect, 30}, {30, ht - 30}, {wd - 30, ht - 30}]
# botspots |> long_line?()
botspots
|> Stream.filter(fn pos ->
# has_mirror?(pos, reflect, botspots)
in_triangle?(pos, triangle)
end)
|> Enum.reduce_while(0, fn _pos, acc ->
print_board()
if acc < min_bots do
{:cont, acc + 1}
else
{:halt, acc}
end
end)
|> Kernel.>=(min_bots)
end
@doc "Use barycentric coordinates (alpha, beta, gamma) to determine if point lies within
the bounding triangle (simplex). The barycentric coordinates with any value of zero are on the
simplex lines. Any negative values are outside the simplex. The values are the ratio of the
area of the sub triangle formed by the point and any two vertices of the simplex to the area
of the simplex."
def in_triangle?({px, py}, [{ax, ay}, {bx, by}, {cx, cy}]) do
area_triangle = abs(ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) / 2
alpha = abs((bx - px) * (cy - py) - (cx - px) * (by - py)) / (2 * area_triangle)
beta = abs((cx - px) * (ay - py) - (ax - px) * (cy - py)) / (2 * area_triangle)
gamma = 1 - alpha - beta
[alpha, beta, gamma] |> Enum.all?(fn n -> n >= 0 and n <= 1 end)
end
def has_mirror?({reflect, _y}, reflect, _botspots), do: true
def has_mirror?({x, y}, reflect, botspots) do
opposite = reflect * 2 - x
MapSet.member?(botspots, {opposite, y})
end
def long_line?(botspots) do
print_board()
botspots
|> Enum.group_by(fn {x, _} -> x end)
|> Enum.any?(fn {_, v} -> length(v) > 20 end) and
botspots
|> Enum.group_by(fn {_, y} -> y end)
|> Enum.any?(fn {_, v} -> length(v) > 20 end)
end
