The Geeks Shall Inherit the Earth

Personal Ramblings of the Techhouse Admin

Skip to: Content | Sidebar | Footer

Getting Started in the Train Yard

8 April, 2010 (20:48) | Erlang | By: Brian

I’ve started working on my Erlang implementation of the trainyard assignment from my AI CISC class at UD. First I had to decide on a data structure for the problems. They currently look like this:

yard1() ->
 { {yard, [{t1, t2}, {t1, t3}, {t3, t5}, {t4, t5}, {t2, t6}, {t5, t6}]},
 {init_state, [{t1, [engine]}, {t2, [e]}, {t4, [b, c, a]}, {t6, [d]}]},
 {goal_state, [{t1, [engine, a, b, c, d, e]}] } }.

yard2() ->
 { {yard, [{t1, t2}, {t2, t3}, {t2, t4}, {t1, t5}]},
 {init_state, [{t1, [engine]}, {t2, [d]}, {t3, [b]}, {t4, [a, e]}, {t5, 1}]},
 {goal_state, [{t1, [engine, a, b, c, d, e]}] } }.

yard3() ->
 { {yard, [{t1, t2}, {t1, t3}]},
 {init_state, [{t1, [engine]}, {t2, [a]}, {t3, [b]}]},
 {goal_state, [{t1, [engine, a, b]}, {t2, []}, {t3, []}] } }.

yard4() ->
 { {yard, [{t1, t2}, {t1, t3}, {t1, t4}]},
 {init_state, [{t1, [engine]}, {t2, [a]}, {t3, [b, c]}, {t4, [d]}]},
 {goal_state, [{t1, [engine, a, b, c, d]}, {t2, []}, {t3, []}] } }.

yard5() ->
 { {yard, [{t1, t2}, {t1, t3}, {t1, t4}]},
 {init_state, [{t1, [engine]}, {t2, [a]}, {t3, 1}, {t4, [d]}]}, %note c and b are out of order
 {goal_state, [{t1, [engine, a, b, c, d]}, {t2, []}, {t3, []}] } }.

I’m still trying to figure out what standard data structures look like in Erlang, but this is what I have currently. Here a Yard is really made up up three parts. First is the track definition, which is a list of left-to-right connected tracks. Thus yard-3, the simplest of the yards, is a simple switch. Because the actual numbers of the tracks aren’t used for anything computationally, I’ve decided to name them t1, t2 … tx. The second and third parts of the representation are states of the track. Here a state is a list of tagged tuples. The tag is the name of the track, the value is a list of cars on that track. In this representation I’m choosing to not list empty tracks like {t1, []}. I think that’s a waste, I can write functions to return an empty list if a track isn’t found in the state. The first state is the initial state of the track and the second state is the goal state of the track. The object of the assignment is to try to figure out a series of legal moves that will transition from the initial state to the goal state.

To help in testing and fetching data, I wrote three quick getters for parsing the data structure.

get_yard({{yard, Yard}, _, _ }) -> Yard.
get_init({_, {init_state, State}, _ }) -> State.
get_goal({_, _, {goal_state, State} }) -> State.

I use these for passing test data into the functions I’m writing. I’ve started work on the first part of the assignment, which starts with this:

%%Problem 1
possible_moves(Yard, State) ->
 lists:filter(
 fun(Move) -> not is_illegal_move(Move, Yard, State) end, generate_all_moves(Yard) ).

%%generate_all_moves(Yard)
generate_all_moves(Yard) ->
 lists:foldl(
 fun({Left, Right}, Moves) -> [{left, Right, Left}, {right, Left, Right} | Moves] end, [], Yard).

Just have to finish writing the illegal move test function and that will be done. Calls to these functions look like:

trainswitch:possible_moves(
trainswitch:get_yard(trainswitch:yard1()),
trainswitch:get_init(trainswitch:yard1())).

Once I finish this first part of the assignment I want to revisit the functions in the previous post and write better versions of them using the built-in-functions of the language and better pattern matching.

Write a comment

You need to login to post comments!