I saw this video about the Josephus problem yesterday and immediately I thought it might be a fun problem to solve in Erlang. First, here is the video that got me interested.

With Recursion and Pattern Matching

I thought this would be an interesting problem to solve with Erlang’s recursion and pattern matching. I decided to use a list of integers to represent the soldiers in the circle, and a recursive function to loop around the list and remove every second integer until only one remains. Pattern matching makes it easy to pick out every second integer. Here is my first attempt at solving the problem with recursion and pattern matching:

-module(josephus).

-export([survivor_in_circle/1]).

survivor_in_circle(Num) ->
    kill_to_left(lists:seq(1, Num), []).

kill_to_left([Survivor], []) ->
    % One person remaining, they are the survivor
    Survivor;
kill_to_left([], Survivors) ->
    % Start another loop around the circle
    kill_to_left(lists:reverse(Survivors), []);
kill_to_left([Killer], Survivors) ->
    % killer is last person in the loop, start another loop around the circle
    kill_to_left([Killer|lists:reverse(Survivors)], []);
kill_to_left([Killer, _Killed|Rest], Survivors) ->
    % Only the killer survives
    kill_to_left(Rest, [Killer|Survivors]).

1> josephus:survivor_in_circle(1).
1
2> josephus:survivor_in_circle(2).
1
3> josephus:survivor_in_circle(4).
1
4> josephus:survivor_in_circle(5).
3
5> josephus:survivor_in_circle(7).
7
6> josephus:survivor_in_circle(41).
19

While this solution only requires 4 function clauses, it would be nice if it only required 2 clauses. Ideally we should only have one clause for when one number remains in the list, and another clause for when there are two or more numbers in the list. We actually can do this in Erlang with only two clauses by using the ++ operator to concatenate surviving numbers onto the end of the list of remaining numbers, so that it is never empty.

-module(josephus).

-export([survivor_in_circle/1]).

survivor_in_circle(Num) ->
    kill_to_left(lists:seq(1, Num)).

kill_to_left([Survivor]) ->
    % One person remaining, they are the survivor
    Survivor;
kill_to_left([Killer, _Killed|Rest]) ->
    % Only the killer survives
    kill_to_left(Rest ++ [Killer]).

I usually try to avoid using ++ operator in Erlang because it creates an entirely new list each time it’s used, so while it’s more elegant than the first solution it’s less efficient. On small lists this won’t matter. The largest list I created above only contained 41 integers, so both solutions are fast enough for this.

With Binary Pattern Matching

I also thought binary method of solving the problem was interesting. All you need to do is move the first bit in the binary representation of the number to the end of the binary. This is also something that can be done easily with Erlang’s pattern matching, and since it only requires moving around a couple bits it should be by far the fastest way to solve the problem.

After a little tinkering, and little help from #erlang IRC channel, I got it working:

survivor(Num) ->
    <<First:8,Rest/binary>> = integer_to_binary(Num, 2),
    binary_to_integer(<<Rest/binary,First:8>>, 2).

Here I’m not actually moving bits around, I’m moving bytes, because the integer_to_binary/2 call returns a binary representing a sequence of ones and zeros, e.g. <<"101">>. Ideally I’d like move bits instead of bytes. This is easy in Erlang, but it took me a while to figure how to how to get this to work. I asked a quite a few questions on this before I finally got it working. Note here that I’m not using Erlang’s integer_to_binary/2 function, I’m using binary:encode_unsigned/1. encode_unsigned converts the number to binary notation, which is the representation required for the bit moving trick to work. After we convert the number to binary notation we remove all leading zero-bits. Then move the first bit to the end, and convert it back to an integer. You can see we have to specify the number of bits that should be used to construct the resulting integer. We count the number of bits in the original binary to get this number.

bit_solution(Num) ->
     <<First:1,Rest/bits>> = remove_leading_zero_bits(binary:encode_unsigned(Num)),
     Size = bit_size(Rest) + 1,
     <<Survivor:Size>> = <<Rest/bits,First:1>>,
     Survivor.

remove_leading_zero_bits(<<0:1, Rest/bitstring>>) ->
    remove_leading_zero_bits(Rest);
remove_leading_zero_bits(Bin) ->
    Bin.

Conclusion

When writing this I looked online for solutions to the Josephus problem in Erlang and found several different solutions. Some used recursive functions like I did and others used Erlang processes. Erlang’s pattern matching and recursion makes it an ideal tool for solving this sort of problem. It was a fun problem to solve, and with Erlang I didn’t have to spend any time thinking about how I was going to translate the problem into Erlang, I just jumped in and started coding. The binary solution is by far the most efficient, but all of them are expressive and relatively succinct.

References

• https://www.youtube.com/watch?v=uCsD3ZGzMgE
• https://en.wikipedia.org/wiki/Josephus_problem
• http://erlang.org/doc/efficiency_guide/myths.html#id63347
• https://rosettacode.org/wiki/Binary_digits#Erlang
• https://rosettacode.org/wiki/Josephus_problem#Erlang
• http://erlang.org/pipermail/erlang-questions/2011-August/060833.html
• http://stackoverflow.com/questions/40334637/convert-base-2-number-in-a-binary-to-an-erlang-integer
• http://stackoverflow.com/questions/40453402/convert-erlang-integer-to-positional-notation-binary