Packages
inplace
0.7.10
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
lib/examples/josephus.ex
defmodule InPlace.Examples.Josephus do
@moduledoc """
https://en.wikipedia.org/wiki/Josephus_problem
"""
alias InPlace.LinkedList
@doc """
Form the circle from N soldiers.
Going clockwise, eliminate every k-th soldier
until only one soldier is left.
"""
def solve(num_soldiers, every_k) do
circle = LinkedList.new(num_soldiers)
Enum.each(1..num_soldiers, fn n -> LinkedList.append(circle, n) end)
{_move_count, kill_sequence} =
LinkedList.iterate(
circle,
fn p, {count_acc, sequence_acc} ->
sequence_acc = if rem(count_acc, every_k) == 0 do
LinkedList.delete_pointer(circle, p)
[p | sequence_acc]
else
sequence_acc
end
{count_acc + 1, sequence_acc}
end,
initial_value: {1, []},
stop_on: fn _ -> LinkedList.size(circle) == 1 end
)
## the survivor and kill sequence
%{
kill_sequence: Enum.reverse(kill_sequence),
survivor: LinkedList.data(circle, LinkedList.head(circle))
}
end
end