An Erlang solution

From Beautifulcode

This is an (untested and incomplete) Erlang solution to the challenge. As the notion of classes doesn't exist in Erlang, the contestants are required to provide a fun (an anonymous function) that implements their algorithm and returns a board. The referee is one process that spawns players and gets 'go' messages from them. When a 'go' message is received, a new tile is given to each of the players. Each player is made of two processes : player_sup which spawn/kills the real worker and relays boards found, and player_worker which does the actual work (the algorithm provided by each contestant).

As the referee just sends new tiles blindly to the players without waiting for a response, the players each get their new tile at about the same time. 'go' messages from the players are marked with the number of tiles (i.e. the round the message refers to) for the referee to ignore late/unordered solutions that could be sent by a player_worker before it is killed by the arrival of a new tile.

(a) Why you believe your solution works ?

Because the behaviour of one player can't affect the other players (except of course when someone says 'go')

(b) What makes it beautiful ?

The fact that each player's algorithm doesn't run any longer than necessary (it's interrupted when a new tile arrives) and the fact that is it written in Erlang, obviously :)

-module(scrabble).

-export([start/3, referee_init/3, player_sup_init/4, player_worker/5]).


%%
%% not implemented :
%% - storing the tiles and retrieving them for distribution
%%   this can be done using an ets table (private to the referee)
%% - checking the validity of a board
%%
%% possible improvements :
%% - the Dictionnary could be passed by reference to avoid copying,
%%   and implemented as a public ets table
%%


%%
%% PlayScrabble_funs : the list of funs implementing each player's algorithm, in the form
%%   fun(Tiles, Dictionnary, Previous_board) -> Board
%%
%% - If the player did not come up with a board in time in the previous round
%% or if it plays the first round, Previous_board is []
%%

start(PlayScrabble_funs, Tiles, Dictionnary) ->
  spawn(fun()-> referee_init(PlayScrabble_funs, Tiles, Dictionnary) end).
  

%%
%% The 'referee' process
%%
%% Description : 
%% Spawns the players, receives 'go' messages from them, and distributes new tiles.
%% unordered 'go' messages (from previous rounds) are ignored
%% 

referee_init(PlayScrabble_funs, All_tiles, Dictionnary) ->
  % we spawn all of the players with their respective fun and the 7 first tiles
  % we keep all of our Players' pids to distribute new tiles later
  Referee = self(),
  Players = [spawn(
	fun()->
	  player_sup_init(Referee, PlayScrabble_fun, take_tiles(7), Dictionnary)
	end)
	  || PlayScrabble_fun <- PlayScrabble_funs ],
  referee_loop(Players, 7, 15).


referee_loop(Players, Nb_of_tiles, Max_tiles) ->
  receive

	{From_player, go, Max_tiles, Board} ->
	  % received 'go' from the first player to come up with a board with 15 tiles
	  case is_board_valid(Board) of
		true ->
		  io:format("The winner is ~p, with board ~p~n", [From_player, Board]);
		false ->
		  referee_loop(Players, Nb_of_tiles, Max_tiles)
	  end;

	{From_player, go, Nb_of_tiles, Board} ->
	  % received 'go' from a player
	  % send a new tile to each player
	  [Player ! {new_tile, take_tiles(1)} || Player <- Players],
	  referee_loop(Players, Nb_of_tiles + 1, Max_tiles);

	{_From_player, go, _Nb_of_tiles, _Board} ->
	  % received a late/unordered 'go', we take it out of our mailbox
	  referee_loop(Players, Nb_of_tiles, Max_tiles)

  end.


%%
%% The player_sup process
%%
%% Description :
%% Spawns a process that executes the actual algorithm, and wait for it
%% to come up with a solution. Kills it and re-spawns it when a new tile arrives.
%% Forwards the found board the the 'referee'.
%%%

player_sup_init(Referee, PlayScrabble_fun, Tiles, Dictionnary) ->
  % we spawn a 'player_worker' process which does the actual work
  % and sends us a message when it comes up with a solution
  Player_worker = spawn(
	fun() ->
	  player_worker(self(), PlayScrabble_fun, Tiles, Dictionnary, [])
	end),
  player_sup_loop(Referee, Player_worker, PlayScrabble_fun, Tiles, Dictionnary, []).


player_sup_loop(Referee, Player_worker, PlayScrabble_fun, Tiles, Dictionnary, Current_board) ->
  receive

	% received a solution from our worker process
	{solution, Board} ->
	  % we send a 'go' message to the referee
	  Referee ! {self(), go, length(Tiles), Board},
	  player_sup_loop(Referee, Player_worker, PlayScrabble_fun, Tiles, Dictionnary, Board);

	% received a new tile from the referee  
	{new_tile, Tile} ->
	  % we kill our player_worker process in case it's still running
	  exit(Player_worker, new_tile_arrived),
	  % we update our list of tiles
	  New_tiles_list = [Tile|Tiles],
	  % we spawn another player_worker process
	  New_player_worker =
		spawn(
		  fun() ->
			player_worker(self(), PlayScrabble_fun, New_tiles_list, Dictionnary, Current_board)
		  end),
	  player_sup_loop(Referee, New_player_worker, PlayScrabble_fun, New_tiles_list, Dictionnary, Current_board);

	_Other_message ->
	  player_sup_loop(Referee, Player_worker, PlayScrabble_fun, Tiles, Dictionnary, Current_board)

	end.


%%
%% The player_worker process
%%
%% Description :
%% Executes the real algorithm that it's passed as a fun. 
%% Either terminates sending the found board to its 'player_sup' or is killed
%% 

player_worker(Player_sup, PlayScrabble_fun, Tiles, Dictionnary, Previous_board) -> 
  Board = PlayScrabble_fun(Tiles, Dictionnary, Previous_board),
  % send our solution to player_sup (then we terminate ourself, implicitly)
  Player_sup ! {solution, Board}.