Week 12: Exercises

1. Shortest Path

Consider this adjacency-list representation for graphs:

type Graph a = [(a, [a])]

Write a function

shortest_path :: Eq a => Graph a -> a -> a -> Maybe [a]

that takes a graph, a start vertex and end vertex. The function should return a list of vertices on the shortest path from the start to the end vertex, or Nothing if there is none.

2. All Paths

Write a function

all_paths :: Eq a => Graph a -> a -> a -> [[a]]

that takes a graph, a start vertex and end vertex. The function should return a list of all possible paths from the start vertex to the end vertex, in increasing order of length. No path may contain the same vertex twice.

3. State Space Search

Consider this type defining a state space:

type StateSpace s a = (s -> [a], s -> a -> s)

In the type declaration above, s is a state type and a is an action type. The first function returns a list of possible actions in any state. The second function takes a state S and an action A, and returns a state that results from performing the action A in S.

Write a function

solve :: Eq s => StateSpace s a -> s -> (s -> Bool) -> Maybe [a]

that takes a state space, a start state and a function that determines whether a given state is a goal. The function should find the shortest path from the start state to any goal state, and should return a list of actions along that path. If no goal state can be reached, return Nothing.

4. Lunar Landing

Here is a starting position of a puzzle game called Lunar Landing:

In each step, the astronaut or one of the robots may move up, down, left, or right until they hit another robot or astronaut. They stop on the empty square just before that point. They may not move in a direction in which there is no robot or astronaut to stop them, for then they would fly into outer space and be lost forever.

The goal is to move the astronaut into the escape hatch in the center.

Write a Haskell function that can solve this and similar Lunar Landing puzzles. We will represent a board state as a list of X/Y positions. In that list the astronaut's position is first, followed by the positions of the robots:

type Pos = (Int, Int)
type State = [Pos]

puzzle :: State
puzzle = [(2, 5), (3, 1), (5, 2), (1, 3), (4, 4), (1, 5)]

Your function should have this signature:

lunar :: State -> Pos -> Maybe [String]

The function takes an initial board state and the goal position. If it finds a solution to the puzzle, it should return a list of strings describing each move:

> lunar puzzle (3, 3)
Just ["5: (1,5) -> (1,4)","5: (1,4) -> (3,4)", ... ]

Each move should include an entity number (i.e. a robot number or 0 for the astronaut), a starting position and an ending position.