Write a Haskell program that reads a rectangular matrix of integers from standard input. For example:
3 9 8 2 5 12 1 7 4
The program should print out the matrix rotated 90 degrees to the right:
1 2 3 7 5 9 4 12 8
a) Write a program in which the computer thinks of a number from 1 to 1000, and the human player has to guess it.
b) Now write a similar program in which the human player thinks of a number, and the computer has to guess it.
Write a Haskell program that is like the command-line utility 'grep'. It should take two command-line arguments: a string to search for, plus a filename. It should print out all lines in the file that contain the given string.
Write a Haskell program that is like the command-line utility 'find'. It should take one command-line argument: a string. The program should look in the current directory and all subdirectories (recursively) for files whose names contain the given string, and print out the (relative) paths of these files, one per line.
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
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.
In Haskell, we may represent a graph in adjacency-list representation using an association list that maps each vertex to a list of its neighbors:
type Graph a = [(a, [a])]
For example, consider this undirected graph:
We may represent it as
graph = [ ('a', "ce"), ('b', "de"), ('c', "adf"), ('d', "bcef"),
('e', "bdf"), ('f', "cdeg"), ('g', "f") ]a) Write a function
adjacent :: Eq a => Graph a -> a -> [a]
that returns a list of a vertex's neighbors in a graph.
b) Write a function
paths :: Eq a => Graph a -> a -> a -> [[a]]
that takes a graph and the ids of start and end vertices v and w, and returns a list of all possible paths from v to w, where a path is represented as a list of vertices. A path may not contain the same vertex twice.
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.