Current section
Files
Jump to
Current section
Files
src/moves/moves_par.erl
-module(moves_par).
-export([moves/1, test/0]).
-include("../benchutil/ets.hrl").
-define(WHITE, 119).
-define(EMPTY, 101).
-define(BLACK, 98).
-define(LEFT_DIRECTION, -1).
-define(RIGHT_DIRECTION, 1).
moves(String) ->
moves(String, erlang:system_info(schedulers)).
moves(String, NrOfWorkers) ->
Version = erlang:system_info(otp_release),
{ReadConc, WriteConc} = supports_ets_concurrency(Version),
Options = if
ReadConc -> [{read_concurrency, true}, {write_concurrency, true}];
WriteConc -> [{write_concurrency, true}];
true -> []
end,
moves(String, NrOfWorkers, [set, public | Options]).
moves(String, NrOfWorkers, ETSOptions) ->
Array = array:from_list(String),
calculate_moves(Array, NrOfWorkers, ETSOptions).
calculate_moves(Array, NrOfWorkers, ETSOptions) ->
Cache = ets:new(cache, ETSOptions),
NrOfWorkers = NrOfWorkers,
Workers = array:from_list([start_worker(Cache) || _ <- lists:seq(1, NrOfWorkers)]),
Result = calculate_moves([Array], -1, Workers, NrOfWorkers, 0, Cache),
ets:delete(Cache),
Result.
calculate_moves(Arrays, MovesSoFar, Workers, NrOfWorkers, 0, Cache) ->
IsEmpty = is_empty(Arrays),
case IsEmpty of
true ->
send_msg_to_workers(Workers, NrOfWorkers, 0, stop),
receive_msg_from_workers(NrOfWorkers, stopped),
-1;
false ->
divide_work_to_workers(Arrays, Workers, NrOfWorkers, Cache),
calculate_moves([], MovesSoFar + 1, Workers, NrOfWorkers, NrOfWorkers, Cache)
end;
calculate_moves(Arrays, MovesSoFar, Workers, NrOfWorkers, WorkPackagesLeft, Cache) ->
receive
solution_found ->
send_msg_to_workers(Workers, NrOfWorkers, 0, stop),
receive_msg_from_workers(NrOfWorkers, stopped),
MovesSoFar;
{work_done, NewWork} ->
calculate_moves([NewWork, Arrays], MovesSoFar, Workers, NrOfWorkers, WorkPackagesLeft - 1, Cache)
end.
divide_work_to_workers(WorkList, Workers, NrOfWorkers, Cache) ->
divide_work_to_workers(WorkList, Workers, NrOfWorkers, 0, Cache).
divide_work_to_workers(Arrays, Workers, NrOfWorkers, CurrentWorker, Cache) ->
case NrOfWorkers =:= CurrentWorker of
true ->
divide_work_to_workers(Arrays, Workers, NrOfWorkers, 0, Cache);
false ->
R = get_next_and_rest(Arrays),
case R of
empty ->
send_msg_to_workers(Workers, NrOfWorkers, 0, level_completed);
{Work, RemainingWork} ->
array:get(CurrentWorker, Workers) ! {do_work, Work},
divide_work_to_workers(RemainingWork, Workers, NrOfWorkers, CurrentWorker + 1, Cache)
end
end.
send_msg_to_workers(Workers, NrOfWorkers, CurrentWorker, Msg) ->
case NrOfWorkers =:= CurrentWorker of
true ->
ok;
false ->
array:get(CurrentWorker, Workers) ! Msg,
send_msg_to_workers(Workers, NrOfWorkers, CurrentWorker + 1, Msg)
end.
receive_msg_from_workers(NrOfWorkers, Msg) ->
receive
Msg ->
receive_msg_from_workers(NrOfWorkers -1, Msg);
_ ->
receive_msg_from_workers(NrOfWorkers, Msg)
after 0 ->
case NrOfWorkers =< 0 of
true ->
ok;
false ->
receive_msg_from_workers(NrOfWorkers, Msg)
end
end.
is_empty(Arrays) ->
get_next_and_rest(Arrays) == empty.
get_next_and_rest([]) ->
empty;
get_next_and_rest([[]|Rest]) ->
get_next_and_rest(Rest);
get_next_and_rest([[E|RestIn]|RestO]) ->
get_next_and_rest([E, RestIn|RestO]);
get_next_and_rest([E|Rest]) ->
{E, Rest}.
start_worker(Cache) ->
ResultReceiver = self(),
spawn(fun () -> worker(Cache, [], ResultReceiver) end).
worker(Cache, WorkDoneSoFar, ResultReceiver) ->
receive
stop ->
ResultReceiver ! stopped;
{do_work, Step} ->
Work = do_work(Step, Cache),
case Work of
solution_found ->
ResultReceiver ! solution_found,
worker(Cache, [], ResultReceiver);
blocker ->
worker(Cache, WorkDoneSoFar, ResultReceiver);
_ ->
worker(Cache, [Work, WorkDoneSoFar], ResultReceiver)
end;
level_completed ->
ResultReceiver ! {work_done, WorkDoneSoFar},
worker(Cache, [], ResultReceiver)
end.
do_work(Step, Cache) ->
AnalyzeResult = analyze(Step),
case AnalyzeResult of
solution ->
solution_found;
search_further ->
all_next_step_arrays(Step, Cache);
has_blocker ->
blocker
end.
analyze(Array) ->
HasStartOrEndBlocker = has_start_blocker(Array)
orelse has_end_blocker(Array),
case HasStartOrEndBlocker of
true ->
has_blocker;
false ->
analyze(Array, 0, true)
end.
analyze(Array, FromPos, IsSolutionToPos) ->
Size = array:size(Array),
case FromPos =:= Size of
true ->
case IsSolutionToPos of
true ->
solution;
false ->
search_further
end;
false ->
case analyze_pos(Array, FromPos) of
solution_pos ->
analyze(Array, FromPos + 1, IsSolutionToPos);
not_solution_pos ->
analyze(Array, FromPos + 1, false);
blocker_pos ->
has_blocker
end
end.
analyze_pos(Array, Pos) ->
End = array:size(Array) - 1,
case {Pos, End} of
{N, N} ->
solution_pos;
{0, _} ->
solution_pos(Array, Pos);
{_, _} ->
HasBlocker = has_blocker(Array,Pos),
case HasBlocker of
true ->
blocker_pos;
false ->
solution_pos(Array, Pos)
end
end.
solution_pos(Array, Pos) ->
O1 = array:get(Pos, Array),
O2 = array:get(Pos + 1, Array),
case {O1, O2} of
{?BLACK, ?EMPTY} ->
not_solution_pos;
{?BLACK, ?WHITE} ->
not_solution_pos;
{?EMPTY, ?WHITE} ->
not_solution_pos;
_ ->
solution_pos
end.
has_blocker(Array,Pos) ->
Occupant = array:get(Pos, Array),
case Occupant of
?BLACK ->
Size = array:size(Array),
case (Size - Pos) < 3 of
true ->
false;
false ->
(array:get(Pos -1, Array) =:= ?BLACK) andalso
(array:get(Pos + 1, Array) =:= ?WHITE) andalso
(array:get(Pos + 2, Array) =:= ?WHITE)
end;
_ ->
false
end.
has_start_blocker(Array) ->
Size = array:size(Array),
case Size < 3 of
true ->
false;
false ->
(array:get(0, Array) =:= ?BLACK) andalso
(array:get(1, Array) =:= ?WHITE) andalso
(array:get(2, Array) =:= ?WHITE)
end.
has_end_blocker(Array) ->
Size = array:size(Array),
case Size < 3 of
true ->
false;
false ->
(array:get(Size -3, Array) =:= ?BLACK) andalso
(array:get(Size -2, Array) =:= ?BLACK) andalso
(array:get(Size -1, Array) =:= ?WHITE)
end.
all_next_step_arrays(Array, Cache) ->
all_next_step_arrays(Array, 0, Cache).
all_next_step_arrays(Array, CurrentPos, Cache) ->
IsEnd = CurrentPos =:= array:size(Array),
case IsEnd of
true ->
[];
false ->
Occupant = array:get(CurrentPos, Array),
MoveArray =
case Occupant of
?WHITE ->
move_in_direction(Array, CurrentPos, ?LEFT_DIRECTION);
?BLACK ->
move_in_direction(Array, CurrentPos, ?RIGHT_DIRECTION);
?EMPTY ->
none
end,
case MoveArray of
none ->
all_next_step_arrays(Array, CurrentPos + 1, Cache);
_ ->
IsFound = ets:member(Cache, MoveArray),
case IsFound of
false ->
Inserted = ets:insert_new(Cache, {MoveArray}),
case Inserted of
true ->
[MoveArray|all_next_step_arrays(Array, CurrentPos + 1, Cache)];
false ->
all_next_step_arrays(Array, CurrentPos + 1, Cache)
end;
true ->
all_next_step_arrays(Array, CurrentPos + 1, Cache)
end
end
end.
move_in_direction(Array, CurrentPos, Direction) ->
NextPos = CurrentPos + 1*Direction,
case move(CurrentPos, NextPos, Array) of
none ->
JumpPos = CurrentPos + 2*Direction,
move(CurrentPos, JumpPos, Array);
MoveArray ->
MoveArray
end.
move(CurrentPos, MoveToPos, Array) ->
IsMoveOut = (MoveToPos < 0) or (MoveToPos >= array:size(Array)),
case IsMoveOut of
true ->
none;
false ->
MoveToPosOccupant = array:get(MoveToPos, Array),
case MoveToPosOccupant =:= ?EMPTY of
true ->
CurrentPosOccupant = array:get(CurrentPos, Array),
Array2 = array:set(MoveToPos, CurrentPosOccupant, Array),
array:set(CurrentPos, ?EMPTY, Array2);
false ->
none
end
end.
test() ->
0 = moves(""),
0 = moves("www"),
2 = moves("bee"),
4 = moves("bebw"),
5 = moves("beebw"),
-1 = moves("wewebbw"),
8 = moves("bbeww"),
9 = moves("bebwew"),
11 = moves("ebbeewwb"),
12 = moves("bebbeww"),
17 = moves("bebbewww"),
17 = moves("bebwwebww"),
27 = moves("bebwbewbbwew"),
32 = moves("bebbebeweewew"),
-1 = moves("bebbwbwbbwew"),
36 = moves("bebebeewewewew"),
38 = moves("bewebeeewewebewwe"),
40 = moves("bebebeeewewewew"),
40 = moves("bewebeeewbwebewwe"),
42 = moves("bebebbeeeewwwbw"),
-1 = moves("bwwebbewwebbbwbwwwebbw"),
49 = moves("bebebeeewewewewwe"),
53 = moves("bebebeeewewbewwewe"),
ok.