3.
a) Define a Scheme function
myMin that takes as input a list of integers and returns the smallest
integer in the list. This function is undefined for the case that the given list
is empty. You may not use the built-in function min to accomplish this task.
Hint define a version with two parameters one for the list and another for the
minimal value found so far. The function myMin should call this helper function.
(myMin
(list 5 4 9 2 8 11 17 -3 9))
returns -3
b) Define the Scheme function splice which given two lists merges the lists together one item
from each in turn until the shortest list is empty then finishes with all items
remaining, if any, in the longer list.
(splice
(list 1 2 3 4 5)(list 'a 'b 'c))
returns
(1 a 2 b 3 c 4 5)
c)
Write a Scheme function addLists that takes two lists of integers of equal length and
returns a list of integers that is the result of adding element one from both
lists together elements 2 together and so on. Hint this is a sort of map
function. Note you are not allowed to use the built in function map to
accomplish this task.
(addLists
(list 1 2 3 4) (list 10 11 12 13))
returns (11
13 15 17)
d) Write a Scheme function nLists that takes a list containing integers and other lists of
such integers embedded to any depth and returns a count of the number of
embedded lists.
(nLists
(list 2 3 (list 4 (list 5))(list 4 1)) )
returns 3
i.e. do not count the outside
list.
e) Write a version of myMin, myMinLists that like (c) takes as input a of lists of integers and
returns the smallest integer found in any of the lists.
(myMinLists
(list 2 3 (list 4 (list 5))
(list 4 1)) ) returns
1
4.
The
towers of Hanoi problem can be extended in an interesting way. Consider
the problem where the starting position may be N (N > 3) discs distributed
randomly over the three pins. in such a way that larger discs may be on top of
smaller discs and vice versa. The only restriction on the starting position is
that all discs in the game are on pins, none on the table. Now is it possible to
unscramble the discs and build a legal tower of all the discs on any pin that is
where a larger disc is not placed on a smaller disc. The rules for moving discs
in the new game is that discs may be removed one at a time and immediately
placed on to another pin in such a way that the disc placed on a pin is only
ever placed on a pin where the top disc is larger than the disc placed on top of
it.
First a few definitions
A legal tower is a tower of discs on a pin where a larger pin
is not on top of a smaller pin.
A good tower, relative to some
other disc, is a top segment of a tower such that the top segment forms a legal
tower and all the discs are smaller than the given disc.
A moveable
tower is a good tower such that the largest disc in the tower is smaller than
the top discs of the towers on any other pin.
The candidate pin is
the pin not containing the moveable tower such that the candidate pin has at its
top a disc nearest in size to the bottom disc of the moveable tower.
Algorithm
UnScramble
board
if all discs form a single legal tower
return empty instruction
else
append the results of
move using hanoiProc the moveable tower excluding
its bottom disc to the spare (i.e non candidate pin)
List the instruction to move the bottom disc of the
best tower to the candidate pin
UnScramble the resulting board from making the above
changes to the board
hanoiProc
noDiscs board
if noDiscs = 1
do move of top disc on pin 1 to pin 2
else
append together the instructions for
moving the tower one smaller than the given tower
using hanoiProc to the pin 3
the list containing the instruction to move the bottom
disc of the tower to the pin 2
moving the tower one smaller than the given tower
using hanoiProc from pin 3 to the pin 2
Representation of the hanoi board
list of three pins
each pin is a list containing the
list of discs on the pin and the name of the pin
Discs
are integers representing their size.
e.g (list (list (list 1 2 3 4) 'a)(list empty
'b)(list empty 'c))
has a legal tower on disc a - the
other pins have no discs
(list (list (list 4
2) 'a)(list (list 3 1) 'b) (list empty 'c))
has disc 4 on
top of 2 on pin a has disc 3 on top of disc 1 on pin b and
has pin c empty
You are to define part of the
solution to this problem. You will be given the Scheme code
for the remainder of
the problem. The precise elements you must code are described in the supplied
program listing. By function name they are:
pinWithSmallestTopDisc
insertInOrd
sortByPin
goodTower
legalTower?
last
allButLast