Problem Set 3 : Game Of Fifteen

Be sure to check the previous post before getting started to read this.

Alright! Welcome back. This is CS50! So, recall in the past days we’ve been spending a quite bit of time on C, on programming, on syntax. And, it’s quite normal if you still struggling about Problem Set 2, to banging your head again on the wall. It’s cryptic-error messages and bugs that you can’t quite chase down. So, if that any consolation hang in there for now. If you can solve it then, can you guess what the string actually says when I typed “ X Lvne Noh! “? Fantastic!

Today, though, we begin to transition to higher level which is more complex but actually it can help you more comfortable in programming and how we can go about optimizing and efficiency of our algorithm and generally solving more interesting problem. How can we go coding effectively by using running time. This problem set will introduce you to larger programs with multiple source files. Accustom you to reading someone else’s code, empowering you with Makefiles, and implement a party favor.

You’ll be more comfortable with :

  • Array(s)
  • Searching algorithm
  • Sorting algorithm
  • gdb

And anyway, you have to do 2 parts of this problem set :

  1. find
  2. fifteen

Recommend Watching :
Lecturer : https://www.youtube.com/watch?v=YxgI7ll4Xtg
Binary search : https://www.youtube.com/watch?v=D5SrAga1pno
Linear search : https://www.youtube.com/watch?v=CX2CYIJLwfg
Bubble sort resources : https://www.youtube.com/watch?v=8Kp-8OGwphY
Insertion sort : https://www.youtube.com/watch?v=DFG-XuyPYUQ
Selection sort : https://www.youtube.com/watch?v=f8hXR_Hvybo
GDB : https://www.youtube.com/watch?v=USPvePv1uzE
Recommend Reading :
Page 17 of http://www.howstuffworks.com/c.htm

Phew, so many videos! And so many pages to read! If you’re done with it, be sure you can anwer these questions when it comes to submit this problem set’s form!

1. Why does binary search require that an array be sorted?
2. Why is bubble sort in O(n) ?
3. Why is insertion sort in Ω(n)?
4. What’s the worst-case running time of merge sort?
5. In no more than 3 sentences, how does selection sort works?


Getting Started.

For problem set 3, you’ll instead download “distribution code”(otherwise known as “distro”), written by cs50 team, and add you own line of code to it. You’ll first need to read and understand their code, though, this problem set is as much about learning to read someone else’s code as it is about writing your own!

Let’s get you started. Go ahead and open up terminal window. Then execute :

update50

To make sure your appliance is up-to-date. Then execute

cd ~/Dropbox

Followed by

wget http://cdn.cs50.net/2013/fall/psets/3/pset3/pset3.zip 

to download a ZIP of this problem set’s distro into your appliance (with command-line program wget). You should see a bunch of output followed by:

‘pset3.zip’ saved

Ultimately confirm that you’ve download pset3.zip by executing :

ls

Then, run

unzip pset3.zip

To unzip file. If you run ls again, you should see that you have newly unzipped directory called pset3 as well. Proceed to execute :

cd pset3

Followed by

ls

And you should find see that the directory contains two “subdirectories” :

fifteen find


Searching Algorithm

Searching algorithm is “ an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots of an equation with integer variables; or a combination of the two”

http://en.wikipedia.org/wiki/Search_algorithm

Sorting

A Sorting algorithm is “an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output”
http://en.wikipedia.org/wiki/Sorting_algorithm


Okay, let’s dive into the first of those subdirectories.

Open up the terminal and execute :

cd ~/Dropbox/pset3/find

You should see below :

helpers.c helpers.h Makefile find.c generate.c 

Phew, that’s a lot of files! Take a look at each file. And try to undersand what do they mean.

And again, please read the spec first! http://d2o9nyf4hwsci4.cloudfront.net/2014/x/psets/3/pset3/pset3.html#_getting_started

Let’s begin the first problem “find”.

Find

  • Prompt for numbers to fill the haystack
  • Searches the haystack for a needle
    – call sorts and searches, function defined in helper.c
    helpers.c was the helper function in Problem Set 3. You’ll need to complete the fully function on it.

TODO :

  1. Search
  2. Sort

Open up the terminal and execute :

cd ~/Dropbox/pset3/find

To make sure you are in a right subdirectory. Then, open up gedit and open helpers.c.
Not sure where to begin?
Anyway,you’ll want to implement a searching and sorting algorithm.

Search

  1. Return true if value is found at haystack
  2. Return false if values is not found at haystack

Linear search : you can do better!
• O(n) → slow
• Can search any list
Binary search :
• O(log n) → fast
• Can only search sorted list
Binary search pseudocode :

bool search(int value, int values[], int n)
 while length of the list > 0
    look at the middle of list
    if number found, return true
    else if number higher, search left
    else if number lower, search right
 return false

Sort

Sort the values[] array

void sort(int values[], int n)

Selection sort pseudocode :

for i = 0 to n-1
  for j = i + 1 to n
    find index of minimum value
  swap array[min] and array[i]

Bubble sorts pseudocode :

- iterate over the list
- compare adjacent elements
- swap elements that are in the wrong order
- largest elements will ‘bubble’ till the end
- the list is sorted once no elements have been swapped

And, you’re done the first problem! Conguratulations!


The Game Begins

Now the second problem is a Game Of Fifteen puzzle played on a square, two-dimensional board with numbered tiles that slide. The goal of this puzzle is to arrange the board’s tiles from smallest to largest, left to right, top to bottom, with an empty space in board’s bottom-right corner as in the below :

boardtrue

You should make your “move” (i.e that borders the board’s empty space)with sliding any tile from smallest to largest, left to right, top to bottom. Although the configuration of board above depicts the game is already won. You should not make any move diagonally or forcibly removed from the board. If, however and only if the board contain odd number (i.e the height and weight of board are even), the position of number 1 and 2 must be swapped. It solvable if the configuration as see below :

solvable-board

Navigate your way to :

~/Dropbox/pset3/fifteen

And take a look at fifteen.c with gedit.
Read over the code and comments in fifteen.c and be sure you can answer the questions below before proceeding further.

  1. Besides 4 x 4 (which are game of fifteen’s dimension), what other dimension does the framework allow ?
  2. With what sort of data structure is the game’s board represented?
  3. What function do you apparently need to implement?

You’ll want to take “baby steps” to implement this game. Four things that you’ll need to implements are :

  1. Init
  2. Draw
  3. Move
  4. Won
15 14 13 12
11 10 9  8
7  6  5  4
3  1  2  _

Recall that the positions of tiles numbered 1 and 2 should only start swapped as they are in 4 x 4 as example above. But they do not swapped in 3 x 3 example below :

8  7  6
5  4  3
2  1  _

INIT

void init(void)

Initializes the game’s board with tiles numbered 1 through d*d – 1 (i.e., fills board with values but does not actually print them), whereby board[i][j] represents row i and column j.

Board represented by 2D dimensional array.

2d

Init pseudocode :

board should contain the starting state
   • board[i][j] represents the elements at row[i] col[j]
Starts in descending order
   • if the number tiles odd, swap 2 and 1

DRAW

void draw(void)

Prints the board in its current state. Then, print the blank space before single-digit #s using :

printf("%2d", board[i][j]);

Draw pseudocode :

for each row
  for each value in row
     print value and space
  print new line

MOVE

bool move(int tile)

If tile borders empty space, moves tile and returns true, else returns false.

Move pseudocode :

Accept the number of tile to move
  Not its positions!
  Search for the tile’s position.
Remember where the blank tile is now

WON

bool won(void)

Returns true if game is won (i.e., board is in winning configuration), else false. Game is won when tiles are in increasing order.

1  2  3
4  5  6
7  8  _

Won pseudocode :

  • Iterate over board and check the values
  • If any values in incorrect, return false

Viola, you’ve finished Game Of Fifteen. To test your implementation of fifteen, you can certainly try playing it.(No check50 for this one). Know that program to quit by hitting ctrl-c. To test your program with, say, the first of those inputs, execute the below.

./fifteen 3 < ~cs50/pset3/3x3.txt

Now, you’re done with both Find and Game Of Fifteen!

This was Problem Set 3.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s