Lab 07: Serious Arrays
This lab will give you practice writing functions dealing with arrays — in this case arrays of ints. The end result, if you finish it all, will be a simple game that works like this:
roche@ubuntu$./gena 6 8 112N = 6 : 8 1 6 6 2 4roche@ubuntu$./graphicWelcome to PutInOrder!board:z.6.8.112### # ## # ## # # ## # # ## # # # ## # # # # #-------------A B C D E Fcommand:swap C E### # ## # ## # # ## # # ## # # # ## # # # # #-------------A B C D E Fcommand:cycleleft 1### # ## # ## # # ## # # ## # # # ## # # # # #-------------A B C D E Fcommand:reverse C E### # ## # ## # # ## # # ## # # # ## # # # # #-------------A B C D E F6 points! (3 moves)
1 Some warmup array functions
Write a program warmup.c with a main() exactly as shown below. This will, of course, require you to fill in the definitions of the functions read, print, and is_ordered that you see being used in the code. The output needs to match the examples shown below.
Note: For now at least, you may assume that input elements (i.e. everything other than “N”) are at most 9. That way there’s no problem lining up the numbers and the letters.
#include <stdio.h>
// fills in the array with integers read from stdin
void read(int* array, int size);
// prints the array to stdout, lined up with dashes and
// corresponding capital letters underneath
void print(int* array, int size);
// returns 1 if the array elements are in ascending (non-decreasing)
// order, and otherwise returns 0.
int is_ordered(int* array, int size);
int main() {
int size;
scanf(" N = %i :", &size);
int arr[size];
read(arr, size);
print(arr, size);
if (is_ordered(arr, size)) {
printf("Is in order!\n");
} else {
printf("Is not in order!\n");
}
return 0;
}Examples:
roche@ubuntu$./warmupN = 4 : 1 4 5 91 4 5 9---------A B C DIs in order!
roche@ubuntu$./warmupN = 4 : 1 5 3 21 5 3 2---------A B C DIs not in order!
./warmupN = 7 : 1 3 4 4 6 8 91 3 4 4 6 8 9---------------A B C D E F GIs in order!
2 Welcome to PutInOrder!
Do this first: copy the gena program to your lab directory: cp /courses/roche/204/bin/gena .
Or from your VM: scp mope.academy.usna.edu:/courses/roche/204/bin/gena .
You will implement a simple game as described below, in a program called basic.c. Game instances are generated using the program ./gena, as shown in the following example:
roche@ubuntu$./gena 6 8 1N = 6 : 8 7 2 4 2 8
Note: gena also writes the same output to a file named z.6.8.1 so you can access it later. The first command-line argument (6 here) indicates how big the array is, the second argument (8 here) indicates the largest each number should be, and the third argument (1 here) is the seed used for the random number generator.
The game described by this is a list of 6 (that’s “N”) numbers, and your goal is to put them in order from smallest to largest by swapping elements, and to do it with the lowest score (each “swap” costs 3 points). N is never greater than 26. The examples below ought to show you the basics of how the game functions, including the swap command (which is the only user command available within your game for now).
roche@ubuntu$./basicWelcome to PutInOrder!board:N = 6 : 8 7 2 4 2 88 7 2 4 2 8-------------A B C D E Fcommand:swap A E2 7 2 4 8 8-------------A B C D E Fcommand:swap B C2 2 7 4 8 8-------------A B C D E Fcommand:swap C D2 2 4 7 8 8-------------A B C D E F9 points! (3 moves)
roche@ubuntu$./basicWelcome to PutInOrder!board:N = 5 : 2 5 3 5 22 5 3 5 2-----------A B C D Ecommand:swipUnkown move "swip"2 5 3 5 2-----------A B C D Ecommand:swap B E2 2 3 5 5-----------A B C D E3 points! (1 moves)
roche@ubuntu$./basicWelcome to PutInOrder!board:N = 6 : 1 3 3 1 4 41 3 3 1 4 4-------------A B C D E Fcommand:swap B D1 1 3 3 4 4-------------A B C D E F3 points! (1 moves)
Note 1: Your solution should make nice use of functions! At least you should have functions for printing a board and determining whether a board is in order.
Note 2: For now you may assume that all array elements are less than 10.
3 Reverse your fortunes
Build on your Part 1 solution in basic.c by providing the player with a new move, reverse x y , where x and y are column positions. Column x should come before column y, and the command should reverse the values in columns x through y. Like this:
9 1 2 5 9 8 7 6 4 reverse E H 9 1 2 5 6 7 8 9 4
------------------- ------------> -------------------
A B C D E F G H I A B C D E F G H IOtherwise the elements should be completely unchanged. A “reverse” move costs two points. Now the player has two moves to make, and should be able to creatively find shorter/lower-point solutions. For example:
roche@ubuntu$./basicWelcome to PutInOrder!board:N = 8 : 9 2 8 8 6 5 8 19 2 8 8 6 5 8 1----------------A B C D E F G Hcommand:reverse C F9 2 5 6 8 8 8 1----------------A B C D E F G Hcommand:swap A H1 2 5 6 8 8 8 9----------------A B C D E F G H5 points! (2 moves)
4 Let’s get graphical (going further)
The game is more compelling if the board is printed out “graphically”, which for us will mean a sort of “ASCII Art” thing. Specifically, write a new program graphic.c that prints game boards in the style shown in the following examples.
~/$ ./graphicWelcome to PutInOrder!board:N = 5 : 4 3 2 4 3# ## # # ## # # # ## # # # #-----------A B C D Ecommand:swap A E# ## # # ## # # # ## # # # #-----------A B C D Ecommand:reverse A C# ## # # ## # # # ## # # # #-----------A B C D E5 points! (2 moves)
Hint: This is made vastly easier by defining a function to find the max element in an array.
5 Cycle and Recycle (going further)
Let’s make one last “move” for the game: cycleleft k. A “cycleleft by one” move shifts every column one position to the left, with the leftmost column wrapping around to become the rightmost column. A “cycleleft by k” is just applying the cycleleft-by-one k-times over. I strongly recommend you implement it this way, i.e. get cycleleft by one working and then call it multiple times to get cycleleft by k working. Note, a cycleleft k move costs only 1 point.
Examples:
roche@ubuntu$./graphicWelcome to PutInOrder!board:N = 6 : 8 1 4 8 5 4# ## ## ## # ## # # # ## # # # ## # # # ## # # # # #-------------A B C D E Fcommand:cycleleft 1# ## ## ## # ## # # # ## # # # ## # # # ## # # # # #-------------A B C D E Fcommand:swap C E# ## ## ## # ## # # # ## # # # ## # # # ## # # # # #-------------A B C D E F4 points! (2 moves)
roche@ubuntu$./graphicWelcome to PutInOrder!board:N = 6 : 6 2 8 1 7 3## ## # ## # ## # ## # # ## # # # ## # # # # #-------------A B C D E Fcommand:cycleleft 3## ## # ## # ## # ## # # ## # # # ## # # # # #-------------A B C D E Fcommand:swap B E## ## # ## # ## # ## # # ## # # # ## # # # # #-------------A B C D E F4 points! (2 moves)
roche@ubuntu$./graphicWelcome to PutInOrder!board:N = 8 : 3 4 5 6 7 8 1 2## ## # ## # # ## # # # ## # # # # ## # # # # # ## # # # # # # #-----------------A B C D E F G Hcommand:cycleleft 6## ## # ## # # ## # # # ## # # # # ## # # # # # ## # # # # # # #-----------------A B C D E F G H1 points! (1 moves)
6 Read from file as well as standard in (going further)
Modify your graphic.c program so that the user can can enter a filename rather than N = ... and the game will read the input (in the same format) from the file rather than stdin.
roche@ubuntu$./gena 4 7 99N = 4 : 3 2 7 1roche@ubuntu$./graphicWelcome to PutInOrder!board:z.4.7.99##### ## # ## # # #---------A B C Dcommand: cycleleft 3##### ## # ## # # #---------A B C Dcommand: reverse B C##### ## # ## # # #---------A B C D3 points! (2 moves)
7 Reading from a graphical representation (going further)
As a real challenge, create a new program readgraphic.c that reads its input (whether from stdin or from a file) not in the nice format we’ve used so far, but in the same graphical format as it prints to the screen. Running gena with the -g option produces inputs in this format, e.g.
roche@ubuntu$./gena -g 8 12 122N = 8## ## ## ## # ## # ## # ## # ## # # # ## # # # # ## # # # # # ## # # # # # # #-----------------A B C D E F G H