Need help: Three-Room Vacuum World

[Arthistic]

Simulate the three uninformed search strategies (Breadth-First Search, Uniform-Cost Search, Iterative Deepening Search) for the following problem. There are three rooms in a row, each with varying degrees of dirt. The leftmost room is the room where all dirt is dumped. There is a single vacuum cleaner, which may be in any of the rooms. Dirt-level for each of the rooms is indicated by a non-negative integer. The vacuum cleaner has a capacity, representing the maximum dirt it can hold at any given time. The goal is to get the middle room and the rightmost room cleaned. The following are the actions the vacuum agent may take:

S – Suck: Suck all dirt in the room the cleaner is in, or, if the cleaner cannot accommodate all dirt, fill up the cleaner to its capacity
D – Dump: Dump all dirt in the cleaner into the room it is in.
L – Left: Move left
R – Right: Move right

Use the order indicated above—if there are ambiguities in node expansion order, when carrying out a search. Moves are valid only if the action causes a transition to a different state. In particular,

it is invalid to suck if the room is empty or if the cleaner is full
it is invalid to dump if the cleaner is empty
a left move from the leftmost room is invalid
a right move from the rightmost room is invalid

The input to the program is a description of the general vacuum environment followed by a sequence of initial states, representing the problem instances to be solved. The format is as follows:

<vacuum-capacity> <S-cost> <D-cost> <L-cost> <R-cost>
<dirt-level-0> <dirt-level-1> <dirt-level-2> <vacuum-contents> <vacuum-position>
<dirt-level-0> <dirt-level-1> <dirt-level-2> <vacuum-contents> <vacuum-position>
<dirt-level-0> <dirt-level-1> <dirt-level-2> <vacuum-contents> <vacuum-position>
…

In the first line of the input, <vacuum-capacity> is a positive integer while <S-cost>, <D-cost>, <L-cost>, and <R-cost> are integer costs for each of the actions. The next lines each contain 5 integers: 3 dirt levels, the current contents of the cleaner, and the position of the cleaner (a position is indicated by an integer 0,1, or 2 where 0 means the leftmost room and 2 means the rightmost room)

The output for this program, for each problem instance and for each search strategy, is the solution returned when the strategy is used on the problem instance. Output the step-cost, path-cost, and the action sequence returned (a string of letters from the set {S,L,D,R}). Refer to the sample output line below for format details.

Sample Input

5 2 1 1 1
0 5 3 0 2
0 7 3 0 2
5 5 5 5 0

Sample Output Line

BFS:  step cost - 8, path cost - 10, action sequence - SLLDRSLD
UCS:  step cost - 8, path cost - 10, action sequence - SLLDRSLD
IDS:  step cost - 8, path cost - 10, action sequence - SLLDRSLD
BFS:  step cost - 9, path cost - 12, action sequence - SLSLDRSLD
UCS:  step cost - 9, path cost - 12, action sequence - SLSLDRSLD
IDS:  step cost - 9, path cost - 12, action sequence - SLSLDRSLD
BFS:  step cost - 11, path cost - 13, action sequence - DRSLDRRSLLD
UCS:  step cost - 11, path cost - 13, action sequence - DRRSLLDRSLD
IDS:  step cost - 11, path cost - 13, action sequence - DRSLDRRSLLD

The program should read input from a text file and produce a text file as output.