More on trying to understand managing the state

Here is the puzzle whose solution I am trying to simulate. It is a very famous puzzle. If you like puzzles, you should definitely try to solve it.

Anyhow, the program I write should do the following:

  1. Create the required number of prisoners. (Each prisoner will have a role, either an ordinary prisoner, or the leader. In advanced versions of the solution, there will be other roles, but that is for later.)

  2. Assign prisoner #1 as leader.

  3. And the rest as per the “basic” solution.

The original puzzle has 100 prisoners, but let us start with 10. So we need 10 prisoners and a light bulb. Each of these entities is mutable. (Each prisoner will have an internal knowledge about whether he visited the bulb room or not. In advanced versions, prisoners will/may change roles.)

Questions:

  1. If I were to code this simulation the Elixir way, I would need to assign a process for the light bulb and each prisoner?

  2. How do I automate “creating” prisoners, each with a process? (When there are 100 of them, one cannot do it by hand.)

  3. What exactly is the difference between the concept of genserver and actors? Once a prisoner assigned a process, does he become an actor?

Thank you for any help.

You do not need processes for this, there is an easier way. But its sure more fun to do it with processes. So I don’t know what the Elixir way is here, because Elixir is fun and easy … :grin:

see here https://elixir-lang.org/getting-started/processes.html

Erlang implements the Actor model. In short an actor is an isolated thing communicating with other actors using messages. A GenServer is a very powerful and convenient implementation of an actor. (For example an actor may have just a queue to receive messages, but Erlang processes have a mailbox which is more powerful and GenServers on top of that bring features like simulated synchronicity with GenServer.call and lots more)

If you want to do this with processes, I think it would be fun and instructive to do it with raw processes (spawn) and GenServer. Registry would also com in handy when using GenServers.

https://hexdocs.pm/elixir/Registry.html
https://hexdocs.pm/elixir/GenServer.html

1 Like

You could - but then answering a question like “what is the current state of the system?” is going to require coordinating & synchronizing with all of those processes.

In general, it’s preferable to model the problem without processes when possible and add distribution later as a runtime concern. For this specific problem it’s even more important, since the statement specifically involves “select one prisoner at a time”.


Here’s how I’d approach this problem:

Each prisoner has a “state” - for now, an Erlang term of unspecified shape.

The light bulb has a state - :on or :off. No particular reason for using these atoms vs true and false (which are also atoms FWIW) but it can make things more readable to use specific names.

The final piece of state is a list of which prisoners have visited the room - this is needed to verify if a guess is correct. The simplest choice would be to store the index of each prisoner (call it “cell number” if you want) in a MapSet.

The whole system’s state is representable as the combination {:on | :off, MapSet(integer), list(prisoner_state)}

A single “step” of the puzzle looks like this:

  • select an index at random
  • ask the strategy for a decision, based on the indexed prisoner’s state and the state of the light
  • implement the decision
    • add the indexed prisoner to the “visited” list
    • update the indexed prisoner’s state
    • update the light’s state
    • if they guessed, handle the result

Your strategy function might have a type like this:

@spec compute_strategy(prisoner_state, :on | :off) :: {new_prisoner_state, :on | :off} | {new_prisoner_state, :on | :off, :guess}

Every time compute_strategy is called, it returns a tuple of updates:

  • a new state for the prisoner
  • a new state for the light
  • (optionally) :guess to indicate that the prisoner has guessed that every prisoner has visited the light

You’ll still need to define what prisoner_state is - it likely depends on the specifics of the strategy (a “leader” doesn’t necessarily have the same shape of state as a non-“leader”).

I’ll post a translation of this in code in a couple days, but this should be a good starting point.

2 Likes

I agree with @al2o3cr 's approach of first coming up with the data structures that will model your state and then the functions that will transform those data structures.

There is a lot of fun to be had here with a Genserver, but to start approaching problems from the Functional Programming paradigm, first solve it without using any Genserver or Process or anything.

In functional programming, there is the concept of a token that represents some state of the system. That token can get passed between many different functions and can transform until the desired result is presented at the end.

In Phoenix, that token is called a conn struct.

Here is an example of a token I would come up with for the puzzle:

  %{
    prisioners: [
      %{id: 1, leader: true, visited: :irrelevant},
      %{id: 2, leader: false, visited: false},
      %{id: 3, leader: false, visited: false},
      %{id: 4, leader: false, visited: false},
      %{id: 5, leader: false, visited: false}
    ],
    visited_count: 0,
    claim_made: false,
    light: :off
  }

You can have a Warden module with a pick_prisoner function.

The pick_prisioner function picks a random prisoner to go to the room.

def pick_prisioner(%{prisioners: prisioners} = state) do
  prisoner = Enum.random(state.prisioners)

  Prisioner.go_to_room(state, prisoner)
  |> life_sentence?()
end

defp life_sentence?(state) do
  # check if the claim was made. If it was, check if the number is correct.
end

Then there is a Prisoner module with a go_to_room/2 function. It takes the entire struct as a first argument and a prisoner as a second argument. It transforms the relevant pieces of the state and returns the updated state.

def go_to_room(state, prisoner) do
  # If I am not the leader and I have never visited, turn the light on and return an updated state where I am marked as `visited: true` and `light: :on`
  # Implement all the other rules so that the correct state is returned in every scenario.
end

After this runs, the new state must be passed into the Warden’s pick_prisioner function again.

If I were creating this, I would create many clauses to the visit_room and maybe the life_sentence? function that pattern matches the state for flow control instead of if statements.

2 Likes