1. (20 points) C++ or C# Problem: Spiderman vs. The Scorpion
Spiderman is hunting down his most dangerous foe, the Scorpion. A former private investigator, the Scorpion underwent transgenic mutations that turned gave him the powers of a scorpion (a natural predator of spiders) while also turning him insade. The Scorpion's underground lair is composed of caverns connected by narrow passageways. If Spiderman encounters the Scorpion in a passageway then the Scorpion's superhuman physique, powerful pincers, and poisonous stinger will lead to Spiderman's demise. However, if he encounters the Scorpion in a cavern, there is enough space that he can employ his web-slinging skills to capture the Scorpion.
An example problem is shown below. A-H represent caverns and the lines represent the passageways connecting caverns.
Spiderman's strategy is to search the lair using a counter that starts at 1. Initially, all caverns are numbered with -1 except for the cavern he starts in, which is numbered 0. When in a cavern, Spiderman heads toward the alphabetically smallest cavern that is not numbered -1. When he enters the new cavern he numbers it on his map with the value of the counter. The counter is then incremented by one. If Spiderman ever enters a cavern and all connected caverns have numbered values then he heads to the cavern with the smallest number and then replaces it with the current counter value.
For example, on the above map say that Spiderman starts in A and A is numbered 0. Both B and C are numbered -1, but he heads toward B since it is alphabetically before C. When he enters B, he numbers it with 1. Next he heads to D, and numbers D= 2. Next he heads to C, since both C and G have values of -1 but C is alphabetically smaller than G. When he enters C, he numbers C= 3. From C he heads to A, since A has a value of 0 which is less than D's value of 2. A is assigned the new value of 4. Continuing in this fashion, he heads to B= 5, D= 6, G= 7, E= 8, F= 9, H= 10, G= 11, D = 12, C = 13, etc. The Scorpion uses the same algorithm as Spiderman to traverse the lair, but he will start in a different cavern and use his own map. Both Spiderman and the Scorpion travel at the same speed.
Write a program in either C++ or C# to simulate Spiderman's pursuit of the Scorpion, showing each move that is made. Your program can use as many or as few features of the programming language that you like (e.g., you can implement it without pointers, ... you can use arrays, vectors, arraylist, etc.).
Your program should input the lair from the console using the following format. The first line is the cavern that Spiderman starts in. The second line is the cavern that the Scorpion starts in. The third line is the number of caverns. The next N lines specify the cavern name followed by a colon and then all other caverns that are accessible from the specified cavern. For example, the following is a sample input corresponding to the lair above with Spiderman starting in A and the Scorpion in G:
Given the input above, your program should output:
Spiderman moves from A to B
The Scorpion moves from G to D
Spiderman moves from B to D
The Scorpion moves from D to B
Spiderman is stung by the Scorpion between B and D!
If The Scorpion started in D instead of G, then the output would be:
Spiderman moves from A to B
The Scorpion moves from D to B
Spiderman slings The Scorpion in cavern B!
Also test your program on different configurations; note that some configurations will loop endlessly with Spiderman and the Scorpion never encountering each other.
2. (20 points) C# Problem: VideoCrypt
An analog encryption method once commonly used by major cable/satellite TV companies is known as videocrypt. The videocrypt system is known as a cut and rotate method. Videocrypt encrypts pictures by rotating individual television scan lines based on some "cut" point. In other words, a secret point is determined for each line (that's what the so-called smart card in the decoder does) and then both parts are exchanged.
If an original line in the picture was (each digit represents a greyscale pixel on the screen):
then the rotated versions might look like:
9012345678 (with cut point=1)
8901234567 (with cut point=2)
7890123456 (with cut point=3)
If we assume the first line of a mini-TV broadcast is not encrypted, then all we have to do is rotate the next line through all possible cut points and find the highest correlation with the previous line. (We are assuming there is contiguous picture content, and that the pixel values don't vary too wildly.) More specifically:
line 1 ......................
line 2 ......................
line 3 ......................
Let p1(x) be the pixel value for line 1 at position x, (x starts from 0). Let p2(x) be the pixel value for line 2 at position x. We assume pixel values range between 0 and 9. To find the cut point for line 2, rotate line 2 through all possible cut points, and determine the cut position that minimizes the sum of the absolute differences between pixel p1(x) and p2(x), for all x. After the best cut point for line 2 is found, the line is decrypted (un-rotated). We then move onto processing line 3, but this time we calculate the minimum with respect to line 2. We continue in this manner until all lines are decrypted.
For this problem you will read the following encrypted bitmap file: scr2.bmp and decrypt it. Your solution must be written in C# as a Windows Application.
Every line in the file is cut and rotated. Load the bitmap into a PictureBox object.to read or write each pixel in the bitmap image (see the class notes for examples on how to do this) and:
Add a button to decrypt the image using the algorithm described above. Your solution must minimize the difference between the Red, Green, and Blue values independently since this is a color image instead of greyscale. 2. Add a ProgressBar object to show the progress of the decryption routine to the user.
3. The algorithm assumed the first line was not rotated. This can result in a skewed image. Add buttons to implement a "Horizontal Hold" so that the image can be rotated left or right.
Here is a sample of a working executable. You must have the .NET installed for the program to run it. VideoUnScramble.exe
If you would like to test your program on the image in the sample program, it is located here: scr1.bmp
Images for this problem thanks to Late Night with Conan O'Brien.
Note: Efficiency counts on this problem! If your algorithm runs super-slowly (say O(n^3) or higher) you'll not get full credit.
To turn in: Everything in your project directory except the obj and bin subdirectories. A zip file of the rest would be preferred.
Extra Credit (points awarded will vary depending on your solution)
Add a slider control in place of buttons for the "Horizontal Hold" Write a program that can generate scrambled images using the VideoCrypt algorithm and test your solution on the new images (it is probably easiest to use alt-printscreen to copy the scrambled image window and paste it into a paint program and edit it in the paint program before saving to a file for the decryption program) Modify the decryption algorithm so that it does a better job; e.g. you may notice there are some vertical lines in the image that could be used for determining a better cut point. Describe your algorithm and implement it; your algorithm should not be specific for these images (e.g., an algorithm that matches up the cut point based on a hard-coded specific color would not get you points since this would not work on other images)
Use Patent Claims
Include Install Instructions
These details are provided for information only. No information here is legal advice and should not be used as such.