Well, Schemers and Schemettes, this season we've come a long way. We've broken in a new crew, exposed Vinnie's sham of a casino, put down a monkey rebellion, survived sabotage, a ship wreck, and a band of ninjas. And much more importantly, Captain Kurt lived out his life-long dream (no, not that one) by beginning his Coke Machine Empire. Having accomplished this great feet, our Captain plans to gracefully retire, and has just announced that Dan the Sailing Man will become the new captain, and Bryan the Brave will become the new first mate. We've come at a good time, the farewall to Kurt party is just about to begin.
...But somewhere off in the distance, someone is determined to crash Kurt's party.
Just as our ship was happily sailing along, its crewmembers merrily partying away, a loud voice is suddenly heard.
????: "Ah, Captain Kurt, so we meet again."
Kurt the Balding: "What?! Who's there?"
And with that, Procedural Jim materializes ondeck.
Procedural Jim: "Hahah, how are you gentlemen? All your base are belong to us."
Several hundred crew members interrupt in unison: "NOOO! NOT AGAIN!"
There is a momentary silence.
Procedural Jim: "Ahem. You didn't think you could just leave without
saying goodbye to your old friend, did you? Haha...
Once more we meet, Captain Kurt, and I assure you,
this time it will be our last."
At this point, a pirate standing in the back shouts, "What you say?!".
He is quickly thrown overboard.
Procedural Jim: "Captain Kurt, I challenge you... to a duel...
We shall see whose crew implement selection-sort
the fastest. Are you game?"
The Balding Captain: "But of course!"
Problem 1
30 Points
Remember all those pesky ninjas from the last homework
episode? We're divided them into two groups, those who will walk the
plank for Kurt and those who will walk the plank for Jim. However,
they must walk the plank in order. So write a function called
selection-sort that takes in a vector and sorts the vector in place
so that the numbers in order, from smallest to largest.
Explanation of selection sort:
Selection sort is a very simple sort. Here's a high-level description
of how it works:
Our Vector:
+---+---+---+---+---+
| 4 | 2 | 5 | 8 | 1 |
+---+---+---+---+---+
0 1 2 3 4 <----index
Find the index of the largest value:
+---+---+---+---+---+
| 4 | 2 | 5 | 8 | 1 |
+---+---+---+---+---+
0 1 2 3 4
^ ^
| +-----Last place
|
Largest
Swap this element with the element in the last place:
+---Largest element now in last spot.
|
V
+---+---+---+---+---+
| 4 | 2 | 5 | 1 | 8 |
+---+---+---+---+---+
0 1 2 3 4
Now the last element is in place. Look through the vector from index
0 to index 3 for the largest element (this will be the second largest
element in the vector).
+---Largest element from index 0 to index 3
|
V
+---+---+---+---+---+
| 4 | 2 | 5 | 1 | 8 |
+---+---+---+---+---+
0 1 2 3 4
Swap this element with the element in index 3:
+---+----Now the two largest elements are in position.
| |
V V
+---+---+---+---+---+
| 4 | 2 | 1 | 5 | 8 |
+---+---+---+---+---+
0 1 2 3 4
Repeat until you've swapped all of the elements into place:
+---+---+---+---+---+
| 1 | 2 | 4 | 5 | 8 |
+---+---+---+---+---+
0 1 2 3 4
SUPER-BIG-ABSTRACTION-HINT: Did you notice that you're doing an
awful lot of swapping? Would it be a good idea to use the swap
function from the previous homework??
Procedural Jim: "Nooo.. I cannot let you win... The power... of...
mullet... failing... I.... must..."
And with that, our captain and Procedural Jim disappear.
Several hours later, Captain Kurt awakens to find himself lost in a dark
place with green numbers floating around.
Cap: "Where am I?"
????: "In the Matrix."
Capt'n: "And who are you?"
????: "I am the elusive calculus professor known only as STAFF"
Capt'n: "What is the 'Matrix'?"
STAFF: "No one can be told what the Matrix is. This is probably
why so many people fail Calc II."
Capt'n: "Okay, well then, how do I get out of here?"
STAFF: "I require some matrix operations to be performed."
Capt'n: "How predictable..."
Problem 2
5 Points
Help Kurt retrieve a specific value in a matrix. Write a function called matrix-ref that takes in three parameters: the first being a two-dimensional vector, and the last two being numbers. (A two-dimensional vector is a vector filled with other vectors.) If the location is outside of the matrix, return #f.
> (matrix-ref #(#(4 2) #(6 7)) 0 0) returns: 4 > (matrix-ref #(#(4 2) #(6 7)) 1 0) returns: 6 > (matrix-ref #(#(4 2) #(6 7)) 2 2) returns: #f
Problem 3
5 Points
Now help Kurt set a specific value in a matrix. Write a function called matrix-set! that takes in four parameters: the first three parameters are the same as in matrix-ref, but the fourth is the new value to put there. If it is successful, return the matrix with the element changed (in other words, make a side-effected change to the matrix that's passed in, and return that matrix; don't make a new matrix to return). Otherwise, return #f.
> (matrix-set! #(#(4 2) #(6 7)) 0 0 7) returns: #2(#2(7 2) #2(6 7)) > (matrix-set! #(#(1 0 0) #(0 1 0) #(0 0 1)) 3 3 7) returns: #f
Problem 4
15 Points
Help Kurt multiply a matrix by a scalar. Write a function called scalar-multiply that takes in two parameters: a value (known as a scalar) and a two-dimensional vector. Every number inside the two-dimensional vector should be multiplied by the scalar.
Mathematical Example (where x is our scalar):
|---|---| |-----|-----|
| a | c | | x*a | x*c |
x * |---|---| = |-----|-----|
| b | d | | x*b | x*d |
|---|---| |-----|-----|
> (scalar-multiply 5 #(#(2 0 4) #(1 2 3) #(5 4 2)))
returns:
#3(#3(10 0 20) #3(5 10 15) #3(25 20 10))
> (scalar-multiply 0 #(#(1 2) #(3 4)))
returns:
#2(#2(0) #2(0))
Problem 5
15 Points
Now Kurt needs to add and subtract some matricies. Write a function called add-matrix that takes two matricies and returns the resultant matrix. You add a matrix by adding all their corresponding values. In other words, the top-left value of the result matrix is the top-left value of the first input matrix added to the top-left value of the second input matrix. (You may assume that the two matricies are the same size.) For this function return a new matrix (don't make any changes to the matrices that are passed in). HINT: perhaps it would be useful to abstract out finding the size of a matrix and creating a matrix of a given size.
+---+---+ +---+---+ +-----+-----+ | a | c | | w | x | | a+w | c+x | +---+---+ + +---+---+ = +-----+-----+ | b | d | | y | z | | b+y | d+z | +---+---+ +---+---+ +-----+-----+ > (add-matrix #(#(4 5) #(6 7)) #(#(1 2) #(3 4))) returns: #2(#2(5 7) #2(9 11)) > (add-matrix #(#(1 2 3) #(3 4 5)) #(#(-1 -2 -3) #(-3 -4 -5))) returns: #2(#3(0 0 0) #3(0 0 0))
Problem 6
5 Points
Now Kurt needs a way to subtract matrices! Using your solutions to problems four and five, write a function called sub-matrix which will take in two matrices and subtract the second from the first.
> (sub-matrix #(#(1 2 3) #(3 4 5)) #(#(1 2 3) #(3 4 5))) returns: #2(#3(0 0 0) #3(0 0 0)) > (sub-matrix #(#(1 2 3) #(3 4 5)) #(#(1 1 1) #(1 1 1))) #2(#3(0 1 2) #3(2 3 4))
Problem 7
15 Points
Now Kurt needs to rotate the matrix. Write a function called transpose-matrix that will make the first row into the first column, and the second row into the second column, .etc. HINT: remember those matrix-ref and matrix-set! functions you wrote?
Example: +---+---+---+ +---+---+---+ | a | b | c | | a | d | g | +---+---+---+ +---+---+---+ | d | e | f | transposed = | b | e | h | +---+---+---+ +---+---+---+ | g | h | i | | c | f | i | +---+---+---+ +---+---+---+ > (transpose-matrix #(#(1 2) #(3 4))) returns: #2(#2(1 3) #2(2 4)) > (transpose-matrix #(#(1 2 3))) returns: #3(#1(1) #1(2) #1(3))
Problem 8
20 Points
Write a function called is-identity-matrix? that takes in a matrix and returns true if all the values are zero except where the row and column are the same, and those values are one. Example of an indentity matrix:
+---+---+---+ | 1 | 0 | 0 | +---+---+---+ | 0 | 1 | 0 | +---+---+---+ | 0 | 0 | 1 | +---+---+---+ > (is-identity-matrix? '#(#(1 0) #(0 1))) returns: #t > (is-identity-matrix? '#(#(1 0) #(0 0))) returns: #f
And with that, the Matrix disappears...
The crew cheers at Kurt's return, and begins to party again (not that the party ever really stops aboard the Good Ship CS1311X). The End...
...or so you might be tempted to think. But that's when the sky darkened, and Procedural Jim reappeared.
Procedural Jim: "Captain Kurt, this ends now. No more mister
nice guy. I challenge you... to a duel...
HEXAPAWN!. And if I win, you must join
me on the dark side."
Capt'n Kurt: "And if I win? Will you give you up your evil ways
and join me on the one true path?"
Procedural Jim: "Hmm. Not only that, but if you win, I will give
you your one true desire... THE HAIR."
At this, everyone on both sides gasps. For you see, Jim's magical hair is one of the two wonders of the programming world. (The other is, of course, Scheme) Kurt has wanted it ever since the first fateful meeting of the two.
Problem 9
30 Points
Procedural Jim and our balding Captain have met for their final battle. The future of the programming world is at stake! Jim's crew is already working on a program to help Jim play Hexapawn. You, of course, must counter this by writing a program to help Kurt play even better and show those fiends the true power of the functional programming paradigm!
Write a function called hexapawn-board-eval. This function will take in two parameters: a 3x3 hexapawn board in list representation, and either the literal 'w or 'b. The list representation will be three nested lists. White pieces will be represented with the literal 'w, and black pieces will be represented with the literal 'b. Blank spaces will be represented with underscores. The initial board set-up will look like this:
((w w w) (_ _ _) (b b b))You may assume that white will always move from the top and black will always move from the bottom. The literal 'w or 'b will be the perspective to look at the board from. Return 100 if the board is a winning board and -100 if it's a losing board. For example:
> (hexapawn-board-eval '((b _ _)(_ _ w)(_ _ _)) 'b) 100(because black is the winner)
> (hexapawn-board-eval '((w _ w)(b _ _)(_ b w)) 'b) -100(because black lost).
Bryan Kennedy did become the new first mate and most likely
edited this line. [Ed. note: I did not change this line]
Captain Kurt went on to found a successful coke machine distributor,
and now makes billions every year selling cokes to the Georgia Tech
College of Computing.
Dan the Sailing Man did become captain of the good ship of 1321, and
he and the sailing woman lived happily ever after.
Dagon the Object-Oriented Dragon's whereabouts are currently
unknown.
Malicious Madame Monica never showed up in this homework.
Procedural Jim now resides in the great coredump in the sky.