Week 13: Exercises

1. 3-Coloring a Graph

Write a function that takes a graph in adjacency list representation and returns a 3-coloring of the graph if one exists, or otherwise Nothing.

2. Breadth-First Search

Write a function that takes a graph and the ids of start and end vertices v and w, and returns a list of vertices on the shortest path from v to w, or Nothing if there is no such path. Use a breadth-first search.

3. Maze Path

Write a program that reads a rectangular maze from standard input in the following format:

#####.###
#...#...#
#.#...#.#
#.#####.#
#.....#.#
###.#####

If there is any possible path from the top to the bottom, the program should print out the maze, highlighting some such path:

#####x###
#xxx#x..#
#x#xxx#.#
#x#####.#
#xxx..#.#
###x#####

If there is no such path, it should print "no path".

4. Cycle

a) Write a function that takes a directed graph and returns True if the graph is cyclic, otherwise False.

b) Modify your function to work on an undirected graph.

5. Hamiltonian Cycle

In an undirected graph, a Hamiltonian cycle is a cycle that visits every vertex exactly once. A graph possessing a Hamiltonian cycle is said to be Hamiltonian.

Write a function that takes a graph in adjacency-list representation and returns a list containing the vertices in any Hamiltonian cycle in the graph, or Nothing if there is none.

6. Graph Isomorphism

Write a function that takes two graphs in adjacency list representation and returns true if the graphs are isomorphic.

7. Rock, Paper, Scissors

Consider the game of Rock, Paper, Scissors. Two players choose their moves simultaneously. Paper beats rock; rock beats scissors; scissors beats papers. Suppose that two players will play a series of games. A strategy for this game is a function which chooses a move, given all moves that the opponent has played before:

data Move = Rock | Paper | Scissors

type Strategy = [Move] -> Move

Assume that in the list of moves given to a Strategy, the most recent move appears first.

a) Write a Strategy that plays whatever will beat the opponent's last move.

b) Write a Strategy that chooses the move that the opponent has played most often in the past, and plays whatever will beat that.

c) Write a Strategy that ignores the opponent's moves and plays Rock, then Paper, then Scissors, then Rock…

d) Write a function play :: Int -> Strategy -> Strategy -> IO () that simulates a given number of games between two strategies. It should produce output that looks like this:

game 1: p1 = Paper, p2 = Scissors (p2 wins)
game 2: p1 = Rock, p2 = Rock (draw)
game 3: p1 = Rock, p2 = Paper (p2 wins)
total: p1 won 0, p2 won 2, 1 draw

8. Fox and Hounds

Fox and Hounds is a two-player game played on the black squares of an 8 x 8 chessboard:

One player controls a single fox, and the other controls four hounds. On the fox's turn, he can move one square in any direction diagonally. On the hounds' turn, one hound can move one square diagonally forward. The fox moves first. If the fox reaches the last row, he wins. If any player is ever unable to move, they lose.

a) Create a type Game representing the state of this game. Also create a value start :: Game representing the initial state of the game.

b) Write a function show_game :: Game -> String that produces a visual representation of the board:

> putStr (show_game start)
  H   H   H   H 
.   .   .   .   
  .   .   .   . 
.   .   .   .   
  .   .   .   . 
.   .   .   .   
  .   .   .   . 
F   .   .   .   
>

c) Create a type Move representing a move in this game.

d) Write a function possible :: Game -> [Move] that produces a list of all possible moves for any state.

e) Write a function move :: Game -> Move -> Game that applies a valid move to a game state, producing a new state.

f) Write an interactive program that allows a player at the terminal to play as the fox versus a computer player, who controls the hounds. For the computer player, use a dummy strategy that just chooses the first possible move. The player should enter their move as one of the string "ul", "ur", "dl" or "dr", where e.g. "ul" means to move up and left. If the game ends, print "You won!" or "You lost!" and exit.

For example:

> play
  H   H   H   H 
.   .   .   .   
  .   .   .   . 
.   .   .   .   
  .   .   .   . 
.   .   .   .   
  .   .   .   . 
F   .   .   .   
Your move? ur
  .   H   H   H 
H   .   .   .   
  .   .   .   . 
.   .   .   .   
  .   .   .   . 
.   .   .   .   
  F   .   .   . 
.   .   .   .   
Your move? ul
  .   H   H   H 
.   .   .   .   
  H   .   .   . 
.   .   .   .   
  .   .   .   . 
F   .   .   .   
  .   .   .   . 
.   .   .   .   
Your move? 

g) Modify the computer player to be stronger.