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
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.
a) Write a function toArray :: [a] ->
Array Int a that converts a list to an array with integer
indices, indexed from 0.
b) Write a function array2d :: [[a]] ->
Array (Int, Int) a that converts a list of lists to a
2-dimensional array with integer indices, indexed from 0.
Write a function is_perm :: [Int] → Bool
that takes a list of N integers and returns True if the list holds
some permutation of the integers 1, .., N.
In the lecture, we saw that we can use accumArray to implement a counting sort, which can sort N numbers in the range 1..R in O(N) time.
Now implement a radix sort. Given any base d, your function should be able to sort N numbers in the range 1..R in time O(N · logd(R)), using much less memory than a counting sort.
Write a function coins :: [Int] -> Int ->
[Int] that takes a list
of coin denominations and a sum, and returns a minimal list of coins
which can be used to form the sum. Any denomination may be used
multiple times in forming the sum. For example, coins [1, 2, 5,
10] 9 might return the list [2, 2, 5].
Write a function partition :: [Int] ->
Maybe ([Int], [Int]) that takes a list of integers and
determines whether it can be partitioned into two sets whose sum is
equal. If so, the function should return a Just with two lists
containing the numbers in each set. If not, it should return Nothing.
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.
A mini-Sudoku puzzle looks like this:
To solve the puzzle, you must place a number from 1 to 4 in every square so that the numbers in every row, column, and mini-square are distinct.
Write a program that reads a mini-Sudoku puzzle from standard input. Empty squares will be represented by the number 0:
3040 0103 2300 1002
The program should print out a solution to the puzzle if it can find one; otherwise it should print "no solution".
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.
Write a function
dfs :: Eq a => Graph a -> a -> [a]
that takes a graph and the id of a start vertex v, and returns a list of all vertices that are reachable from v. Use a depth-first search. Write the function two ways: (a) using recursion to explore the graph; (b) using a stack data structure.
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.
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".
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.
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.
Write a function that takes two graphs in adjacency list representation and returns true if the graphs are isomorphic.