Write a program that simulates a random walk in two dimensions. The program should take an integer N on the command line, and simulate N random steps starting from the origin (0, 0). Each step should move randomly left, right, up, or down. The program should print the position after each random step. At the end, it should print the number of times that the walk visited the origin, and also the furthest Manhattan distance (|x| + |y|) that was reached from the origin. For example:
$ runghc walk 10 0 0 0 1 1 1 1 2 0 2 0 1 1 1 1 0 0 0 0 1 0 2 visits to origin: 2 furthest distance: 3
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 isPerm
:: [Int] → Bool that takes a list of N integers and returns
True if the list holds some permutation of the integers 1, .., N.
Write a function minCoins
:: [Int] -> Int -> Maybe [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, min_coins [1, 2, 5, 10]
9 might return Just [2, 2, 5]. If the sum cannot
be formed from the given coins, return Nothing.
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.
Write a function csort :: (Int, Int) ->
[Int] -> [Int] that implements a counting sort.
(csort (lo, hi) xs) should sort a list xs of values, all
of which are in the range lo ≤ x ≤ hi. It should run in O(N),
where N = length xs.
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.
Define a type IMap a
that is a map from a fixed range of integers (indexed from 0) to
values of type a. Provide the following functions:
makeIMap :: [a] -> IMap a iget :: IMap a -> Int -> a iset :: IMap a -> Int -> a -> IMap a
makeIMap can assume that the given list is non-empty.
The iget and iset functions should run in
O(log N), where N is the number of elements in the map.
Also declare that IMap is an instance
of Functor.
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
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, and return the list of vertices in the order in which they were discovered.
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 function that takes a graph in adjacency list representation and returns a 3-coloring of the graph if one exists, or otherwise 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".
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.
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.
Three missionaries and three cannibals wish to cross a river using a boat that can carry only two people. At no time may the cannibals outnumber the missionaries on either river bank, since then they would eat the missionaries. How can they cross? Write a Haskell program that can find the shortest solution.
A farmer is on the south bank of a river with a wolf, a goat, and a cabbage. He has a boat that can hold him plus any one of these three items. If the wolf and goat are left alone without the farmer, the wolf will eat the goat. If the goat and cabbage are left alone without the farmer, the goat will eat the cabbage. The wolf does not like cabbage.
How can the farmer cross with all of these possessions to the north bank? Write a Haskell program that can determine the shortest solution.
Three jugs have capacity 8, 5 and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a Haskell program to find the shortest possible solution.
Four people wish to cross a river using a narrow bridge, which can hold only two people at a time. They have one torch and, because it's night, the bridge crossers must take the torch.
Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. Can they all get across the bridge if the torch lasts only 15 minutes? Write a Haskell program that can determine the answer.