33 lines
969 B
Text
33 lines
969 B
Text
defmodule HundredPrisoners do
|
|
def optimal_room(_, _, _, []), do: []
|
|
def optimal_room(prisoner, current_room, rooms, [_ | tail]) do
|
|
found = Enum.at(rooms, current_room - 1) == prisoner
|
|
next_room = Enum.at(rooms, current_room - 1)
|
|
[found] ++ optimal_room(prisoner, next_room, rooms, tail)
|
|
end
|
|
|
|
def optimal_search(prisoner, rooms) do
|
|
Enum.any?(optimal_room(prisoner, prisoner, rooms, Enum.to_list(1..50)))
|
|
end
|
|
end
|
|
|
|
prisoners = 1..100
|
|
n = 1..10_000
|
|
generate_rooms = fn -> Enum.shuffle(1..100) end
|
|
|
|
random_strategy = Enum.count(n,
|
|
fn _ ->
|
|
rooms = generate_rooms.()
|
|
Enum.all?(prisoners, fn pr -> pr in (rooms |> Enum.take_random(50)) end)
|
|
end)
|
|
|
|
IO.puts "Random strategy: #{random_strategy} / #{n |> Range.size}"
|
|
|
|
optimal_strategy = Enum.count(n,
|
|
fn _ ->
|
|
rooms = generate_rooms.()
|
|
Enum.all?(prisoners,
|
|
fn pr -> HundredPrisoners.optimal_search(pr, rooms) end)
|
|
end)
|
|
|
|
IO.puts "Optimal strategy: #{optimal_strategy} / #{n |> Range.size}"
|