Due Sunday, June 24, 2012 @ 11:59pm
This hw and the next one will likely be worth twice as the later hws as these two require more work.
Updates
- June 18 @ 3:30PM - Readjusted points for each question.
- June 19 @ 2:30PM - Fixed starting code for Q2. If you copied it before then, either recopy or change main's for-loop check to "word < words+numWords".
Goals
This assignment covers a range of topics related to C and number representation. It is also intended to get you to start writing C code on your own.
Submission
Submit your solution by creating a directory named hw1 that contains files named hw1.txt, reverseWords.c, and SolveLightsOut.c.
(File names are case-sensitive and the submission program will not
accept your submission if your file names differ at all from those
specified.) From within that directory, type submit hw1. Partners are not allowed on this assignment.
Copy the contents of ~cs61c/hw/01 to a suitable location in your home directory to obtain files you will want for this homework.
$ mkdir ~/hw1 $ cp -r ~cs61c/hw/01/ ~/hw1
Exercises
Problem 1: Number representation - 4pts
Assume we are dealing with 8 bit numbers for this problem Fill in the following table according to the header of each column. If you are given binary or hex, convert it to decimal. If you are given a decimal value, convert it to hex. Put "n/a" if the value cannot be converted.
| unsigned | sign & magnitude | one's complement | two's complement | |
0b11111110 |
||||
0b00000001 | ||||
0x0F
| ||||
0xFF
| ||||
25
| ||||
-25
| ||||
128
| ||||
-128
|
Put your solution in hw1.txt.
Problem 2: Short C Exercise - 6pts
Fill out the the blanks in reverseWords.c according to the comments.
/*
Takes two char pointers and swaps the chars.
*/
void swapChars(char *a, char *b) {
char temp = ______;
______ = ______;
______ = temp;
}
/*
reverseAllWords takes an array of strings and reverses each of the strings in place.
You may find swapChars from above and strlen useful.
*/
void reverseAllWords(______, ______) { //what parameters do we need?
for(int w = 0; w < ______; w++) {
//you may declare and initialize some variables here for convenience though they are not strictly necessary
for(int i = 0; i < ______; i++) {
__________________;
}
}
}
If done correctly, it should work as shown below.
$ gcc -std=c99 -Wall reverseWords.c -o reverseWords $ ./reverseWords Hello my name is Bob $ olleH ym eman si boB
gcc is the compiler, reverseWords.c is the input to the compiler, and what comes after the -o specifies the name of the output file (and the executable in this case), reverseWords. -std specifies the C standard to be used, in this case c99. -Wall enables a bunch of warnings about things that are questionable in your code.
Problem 3: C Coding - 10pts
Your job is to write code to solve a variant of the popular hand-held toy Lights Out. You are given a 3 x 3 grid of lights. In the initial state, some may be on, some may be off. If you push on a light, it toggles the state of itself and its immediate neighbors (if any) to the north, south, east and west. The goal is to turn all the lights out. Note that the order of the button presses doesn't matter in any solution.
Our version is slightly different; we "sew" the left and right of the board (but NOT the top and bottom), so that if you push a light on the left, it'll affect its neighbors on the right column and vice-versa. You can create such a board and try it out here. For example, if our board had all its lights on (1=on, 0-off):
1 1 1 1 1 1 1 1 1
and you push the bottom-right button, the resulting state would be
1 1 1 1 1 0 0 0 0
Note that the top-right light didn't toggle because there's no "connectivity" left-to-right. As another example, given the following almost-solved state:
1 1 1 1 0 1 1 1 1
the solution is simple -- push buttons highlighted in bold 1s below:
1 0 0 0 0 0 0 0 1 OR 0 0 1 0 0 0 1 0 0
You will complete SolveLightsOut.c which takes a single argument, the initial state written as a row-major bit-string, (the second position shown above would be written 111110000) and prints to stdout the solution, also as a bit string, where '1' means click. The reason we can encode the solution like this is because
- there's no need to click on the same button more than once
- the order in which buttons are pressed doesn't matter.
printUsage().
For example,
$ ./SolveLightsOut 111101111 001000100 010000111 100000001 111000010 $ ./SolveLightsOut 110000000 000001111 Usage: SolveLightsOut <9-bit string> This program generates optimal solutions to a variant of the "Lights Out" game. It solves a 3-by-3 board with the left and right edges "sew" together, and prints the solutions requiring the fewest buttons pressed. Solutions are printed as bit strings representing the board in row-major order where 1 means press. Arguments: <9-bit string> is a string of nine 1's and 0's that describes the initial board in row-major order, where 1 means on and 0 means off. $ ./SolveLightsOut 1100000ab Usage: SolveLightsOut <9-bit string> This program generates optimal solutions to a variant of the "Lights Out" game. It solves a 3-by-3 board with the left and right edges "sew" together, and prints the solutions requiring the fewest buttons pressed. Solutions are printed as bit strings representing the board in row-major order where 1 means press. Arguments: <9-bit string> is a string of nine 1's and 0's that describes the initial board in row-major order, where 1 means on and 0 means off. $ ./SolveLightsOut 111111110
Your code should compile with following command without warnings or errors:
$ gcc -std=c99 -Wall SolveLightsOut.c -o SolveLightsOut
To help get you started, some suggested functions you can write are described in SolveLightsOut.c.
You should test individual parts of your program as you go along. For instance, you can write the function readInput,
which can test the validity of the input string and encode the bit string into your internal representation, and easily test that before moving on.
You're free to ignore the suggested functions and come up with your own; you may change anything given in SolveLightsOut.c.
Tips
- You should encode the board position, as well as each possible solution, as an unsigned number, not an array of bits, and use bit manipulation to toggle your initial board states. You'll find the xor operator useful for flipping bits.
For example, if you want to flip every fourth bit in x, a 32 bit value, you can do
x = x ^ 0x88888888;; note there's a 1 in every fourth bit of 0x88888888. - Other bitwise operators you may find useful are &(and), |(or), ~(negate/flip all bits), <<(shift left), and >>(shift right, likely arithmetic if it's used on a signed type).
For example, one way to zero out the two leftmost bits of x but leave the rest is
x & ~3.