Story:
In our last episode of "CS1311X Pirates", the crew of the good ship 1311X
returned from shore leave to find that the monkeys had completely rearranged
the layout of the ship. This, needless to say, wrecked havoc as the crew
couldn't find their way around the ship, and so new path finding functions
had to be built. Unfortunately, one thing our brilliant crew didn't realize
is that the monkeys changed around the steering mechanism for the ship
causing the ship to slowly drift off course. (You do, of course, realize
they're going to blame this on you.)
It seems that our good ship has drifted into the uncharted waters known as the realm of side effects. What will become of the good ship 1311X? Will they ever get back on course? Will Madame Monica ever attend another TA meeting? To find out, grab your favorite overly-caffeinated 1311X beverage and stay tuned for this week's episode!
Captain Kurt the Balding, Madame Monica, and his crew of pirates are floating hopelessly on their boat when a giant explosion rocks the ship. Suddenly, on Kurt's giant electric display (where DID he get that, anyway?) appears the face of his arch-rival: Jim Greenlee, a pirate captain with a hair-do that Kurt would give anything to have.
Captain Kurt the Balding: What Happen?
Mitchell the Mechanic: Somebody set up us the bomb.
Owens the Operator: We get signal.
Capt'n Kurt: What!
Owens the Operator: Main screen turn on.
(At this point, a face appears on Kurt's giant digital display. Where
did he get that thing, anyway?)
Capt'n Kurt: It's you!!
Jim: How are you gentlemen!! All your base are belong to us.
You are on the way to destruction.
Capt'n Kurt: What you say!!
Jim: You have no chance to survive make your time. Ha Ha Ha Ha ...
The adventures of the 1311X Pirates will return right after these commercials.
NOTICE: Problem one must be done using recursion. The only side effect you may use is printing.
Problem 1
50 points
It looks like this could be it for our plucky crew. So what does our brave
captain do when his life flashes before his eyes? He shares it, of course.
He's muttering something about "2360" and "when I was your age" when suddenly he
starts into a story about when he was younger and went on an expedition to a
volcanic island. Kurt and two of his pirate friends were brokering a treaty
between his pirate ship and the three leaders of the cannibals that lived on the
island when all of the sudden the volcano began to erupt! The pirates and the
cannibals raced towards the shore to get away, but soon they came to a parinha
infested river. There is a rowboat that seats two, but just before Kurt hops in
he realizes that he must be careful. All of this running has made the cannibals
quite hungry, so if there are ever more cannibals than pirates on one side of
the river then the cannibals will eat the pirates! There must be a way for
everyone to make it safely across the river, since Cap'n Kurt is here telling
the story, but he can't seem to remember it at the moment.
Help out our brave captain by writing a function called help-kurt which
will show him how to get everyone safely across the river. Your function will
take in exacly three parameters: a list representation of the start state, a
list representation of the ending state, and a printing flag. We'll
represent the two sides of the river as two nested lists; the first nested
list will be the "lava" side and the second list will represent the "safe"
side. We'll represent the boat with the letter 'b', a pirate with the letter
'p', and a cannibal with the letter 'c'. The representation for the starting
state, with everybody on the wrong side of the river, would look like:
((p p p c c c b) ())
((b c p c c p p) ())a representation of the final state would look like:
(() (b c c p p p c))
(((c c c p p p b) ()) ((c p p p) (b c c)) ((b c c p p p) (c)) ((p p p) (b c c c)) ((b c p p p) (c c)) ((c p) (b p p c c)) ((b p c c p) (p c)) ((c c) (b p p p c)) ((b c c c) (p p p)) ((c) (b c c p p p)) ((b c c) (c p p p)) (() (b c c c p p p)))By now you may be wondering what to do with that printing flag. If the flag is #t then print out each state that you consider and if it's an acceptable state or not. If it's #f then don't print anything. HINT:You can get a newline with the newline function. Sample printed output would look something like this:
((c c c p p p b) ()) state is ok ((p c c c) (b p p)) not ok: too many cannibals on lava side ((p p p c) (c c b)) state is ok ((p p p c c c b) ()) not ok: repeated stateNotice that last state is not ok because it's a repeat (of the first state).
Restrictions:
All of the remaining problems problems must be done iteratively,
not recursively.
Problem 2
10 points
Welcome back, pirates! When we last left our great ship, it appeared that an evil captain had planted bombs on Kurt's ship! Although one has already gone off, the ship is still in sailing condition, although the steering system is still suffering from the monkey's tampering. Anyway, Kurt has met with his most trusted advisor (Dan the Sailing Man), who believes that there may be more bombs. Of course, the best way to find out if this is the case is to look through all the items in the boat to see how many bombs there are.
Write a function called members. It will take in an item, a list, and return the number of times that item appears in the list. (You do not need to worry about recursively checking nested sublists.) Once again, this must be done iteratively, not recursively, and you may not use the built-in member function.
> (members 'Basic '(C C++ Java Lisp Scheme Smalltalk Squeek)) returns: 0 > (members 'bomb '(books cat bomb notes food monkeys bomb Dan)) returns: 2
Problem 3
10 points
Unfortunately, it appears that one bomb went undetected and there's now a serious leak in the ship. Fortunately, one of the TAs in the crow's nest has sighted an island in the distance!
Upon arriving on land, our group of Schemers and Schemettes is greeted by a man who says, "Problem a has boat your think I Uhm". That's when it hits them: everybody on this island speaks backwards!
Write a function called reverse-it that, given a list, will return the reverse of that list. This must be done iteratively.
> (reverse-it '(1 2 3 4 5)) returns: (5 4 3 2 1) > (reverse-it '(you watching is brother big)) returns: (big brother is watching you) > (reverse-it '()) returns: ()
Problem 4
10 points
Madame Monica and a group of Schemers and Schemettes have left for the island's main town, while Kurt and Dan remain behind to guard the boat. On the way to town Madame Monica gets an excellent idea that she thinks will really cheer up Kurt. You see, she knows that every six months or so, Capt'n Kurt gets the urge to upgrade his boat to a new model. She knows how much he's been eyeing the new model 1321 pirateships, but he wanted to wait until the summer when the price would go down. However, Monica hadn't gone to enough of the crew meetings to know the exact amount of money in the pirate treasury, and so she went ahead and bought a new model 1321 pirateship anyway ---- putting our crew way into debt!
But just as she was about to give the news to Kurt, she got a wonderful idea. Madame Monica thinks that the number might look much smaller if expressed as an exponent, and she also thinks it'd be a much better idea if you presented the news to Kurt instead.
Write a function called expt-it. This function will take two parameters, a base and a power. You may assume the second parameter will not be negative. Also, remember that you must do this iteratively, and you may not use the built in expt function.
> (expt-it 5 4) returns: 625 > (expt-it 5 0) returns: 1
Problem 5
10 points
While thinking in her pirate office, Madame Monica is suddenly interrupted by the guy she shares her pirate office with: that's right, the master of Java, David Dagon the Dashing. It seems that Dagon has a problem, and he's hoping Monica will help him with it. You see, one of Dagon's favorite number sequences is the Fibacconai sequence, but he needs it written in Scheme but he only knows Java!
This, of course, gives Monica an idea. She can pay off the loans on the new model boat by selling Scheme code!
Write a function called fib-it that takes in a non-negative number and returns the "fib" of that number. This is just like fib-ag and fib-tr which you wrote some homeworks back, except that now you need to do it iteratively instead of recursively.
> (fib-it 0) returns: 1 > (fib-t 4) returns: 5
Problem 6
10 points
Kurt is very impressed with this idea. In fact, he's so impressed that he's already arranged a job for you. He has just recently received long research papers from all his graduate students, and he wants to make sure that they meet the minimum length requirement.
Write a function called length-it that, given a list, returns the number of items in that list. You do not need to worry about sublists. This must be done iteratively, and you may not use the the built in length function.
> (length-it '()) returns: 0 > (length-it '(Sensei: Kyoo wa ringo o tabemashita. Gakusee: Nanpiki tabemashitaka?)) returns: 9
Well, that's all for tonight's episode. Join us next time when we go where few Schemers have gone before: Arrr!