The Geeks Shall Inherit the Earth

Personal Ramblings of the Techhouse Admin

Skip to: Content | Sidebar | Footer

Trainyard problems 2 and 3

29 April, 2010 (22:30) | Erlang | By: Brian

After getting the problem structure worked out, I started working on Problem 2, applying a move to a state and getting a new state. This required a couple of helper functions that came over from the lisp code. These two small functions take two track listings and perform the appropriate move. They return a pair of lists as a single Tuple, because functions can only return one term. Creating these methods taught me how to use the list concatenation operator “++.” This operator is used for combining lists in statements, “|” is used for splitting lists in matches.

%% move the first element of front to the last element of back and return both new lists
move_front_to_back([Front | Rest], Back ) ->
 {Rest, Back ++ [Front] }.

%%move the last element of front to the first element of back and return both new lists
move_back_to_front(Front, Back) ->
 {lists:sublist(Front, length(Front) - 1), [lists:last(Front)] ++ Back}.

And some test cases.

{[],[b,a]} = move_front_to_back([a], [b]),
 {[b],[a]} = move_front_to_back([a,b], []),
 {[b,c],[d,e,a]} = move_front_to_back([a,b,c], [d, e]),
 {[],[a,b]} = move_back_to_front([a], [b]),
 {[a],[b]} = move_back_to_front([a,b], []),
 {[a,b],1} = move_back_to_front([a,b,c], [d, e]),

Next I needed a new function to take the two returned lists and apply them to a state list. While working on this problem, I discovered that my track list structure of [{Trackname, Tracklist}, ...] met the definition of an Erlang key store structure. Once I figured this out and read some documentation, the data management of the track list structures became fairly simple calls the lists module’s key methods. This function takes a list of track tuples and applies them recursively to the state. Finally, it sorts the tracklist by trackname and returns the new state.

%%take a list of tuples like {t1, [a,b]} and a state, update tracks, return new state
update_tracks(State, []) ->
 %io:format("No Updates to make, returning input state: ~w~n", [State]),
 lists:keysort(1,State);
update_tracks(State, [{UpdateTrack, UpdateList} | RestUpdate]) ->
 io:format("Updating state ~w with track ~w~n", [State, {UpdateTrack, UpdateList}]),
 case UpdateList of
 [] ->
 %delete the track key and recurse
 %io:format("Deleting track ~w and recursing~n", [UpdateTrack]),
 update_tracks(lists:keydelete(UpdateTrack, 1, State ), RestUpdate);
 _CarsOnTrack ->
 %replace the track key and recurse
 %io:format("Replacing with track ~w~n", [{UpdateTrack, UpdateList}]),
 update_tracks(lists:keystore(UpdateTrack, 1, State, {UpdateTrack, UpdateList}), RestUpdate)
 end.

I also refactored one of my older utility methods to use the built-in key functions.

%%trainswitch:cars_on_track(t1, Yard1#problem.init_state).
cars_on_track(Track, TrackList) ->
 %keysearch for a {Track, Cars} tuple in the list
 case lists:keyfind(Track, 1, TrackList) of
 false -> [];
 {_Track, Cars} -> Cars %try to bind track and return its cars
 end.

Now that we can apply a list of individual track updates to a state, we just generate a list of track updates from a move and apply them.

%%Problem 2
%%apply_move: apply a move to a state and return the new state
%%trainswitch:apply_move({left, t2, t1}, Yard1#problem.init_state).
apply_move({left, Right, Left}, State) ->
 %io:format("Moving car from ~w to ~w in state: ~w~n",[Right, Left, State]),
 {NewRightList, NewLeftList} = move_front_to_back(cars_on_track(Right, State), cars_on_track(Left, State)),
 %io:format("Moved car from ~w to ~w~n",[{Right, NewRightList}, {Left, NewLeftList}]),
 update_tracks(State, [{Right, NewRightList}, {Left, NewLeftList}]); %return the new state
apply_move({right, Left, Right}, State) ->
 %io:format("Moving car from ~w to ~w in state: ~w~n",[Left, Right, State]),
 { NewLeftList, NewRightList} = move_back_to_front(cars_on_track(Left, State), cars_on_track(Right, State) ),
 %io:format("Moved car from ~w to ~w~n",[{Left, NewLeftList}, {Right, NewRightList}]),
 update_tracks(State, [{Right, NewRightList}, {Left, NewLeftList}]). %return the new state

So when we want to apply a move like {left, t2, t1}, we create an update tuple for the new state of t2, an update tuple for the new state of t1, list those updates together and pass that list to the update method.

[{t1, [engine, a]}, {t3, [b]}] = apply_move({left, t2, t1}, [{t1, [engine]}, {t2, [a]}, {t3, [b]}]),
 [{t1, [a]}, {t3, [b]}] = apply_move({left, t2, t1}, [{t2, [a]}, {t3, [b]}]),
 [{t2, [engine, a]}, {t3, [b]}] = apply_move({right, t1, t2}, [{t1, [engine]}, {t2, [a]}, {t3, [b]}]),
 [{t2, [engine]}, {t3, [b]}] = apply_move({right, t1, t2}, [{t1, [engine]}, {t3, [b]}]),

For my structures I decided to just remove empty lists. So, for example, in the last test, you won’t see {t1, []}. This is just to keep the structures smaller and leaner. The function that looks for cars on a track will just return {t1, []} if the track is not in the keystore.

Problem 3 is a fairly trivial expansion of problems 1 and 2. Take a state, generate all moves from it and return a list of all the states that would be reached by applying those moves. It’s a fairly simple map process.

%%Problem 3
%%expand: take a yard and a state and return a list of all states reachable in one step
expand(State, Yard) ->
 lists:map(fun(Move) -> apply_move(Move,State) end, possible_moves(Yard, State)).

Next I get to start on actually solving the problem. When I solved this problem before I chose iterative deepening search as the “blind search” algorithm. Iterative deepening means essentially that at each step of the solution I first generate all the next steps, take one of those steps and try to solve from there before looking at any of the other steps I generated. If I run out of moves to try, I back up and try another path. Imagine blindly trying to drive to a destination and at every fork in the road you went left. When you hit a dead-end, you backed up one fork and tried the right. If you found a dead-end there you backed up twice and tried the right from that branch, and so on. The only trouble with using this method for solving this problem is that you have to be careful to not get stuck in an endless loop of states going back and forth. If you don’t check for this, your solver could endlessly go down a path of {left, 2, 1}, {right, 1, 2}, {left, 2, 1}, {right, 1, 2} … and so on. Re-writing this algorithm will require some new data structures to represent the intermediate solving steps as well as helper methods for traversing the solution space.

Write a comment

You need to login to post comments!