Assignment 5: Social, Life

Deadline

19 October, 2018 (Friday), 6:00pm.

Prerequisite

You are able to access the CS1010 programming environment.
You are familiar with basic UNIX CLI and using terminal-based editor vim.
You have gone through Exercise 1 and have already set up your .gitconfig.
You are familiar with the steps of accepting, downloading, and submitting your exercise and assignment.
You are familiar with the directory structure and the common files included in your assignment skeleton.

Learning Outcomes

Be comfortable writing C programs that involve arithmetic operations, long, double, bool, and char types, conditional if/else statements, loops with while/for/do-while statements, arrays (including 2D arrays), strings, pointers, and dynamic memory allocation.
Be comfortable breaking down a problem into smaller subproblems which can be resolved using functions, including reusing existing functions written for other programs (with a tweak), writing a function that calls itself, designing what should the inputs and return values/types of a function be.

Setup

Click on this link to accept the assignment.
Login to one of the hosts of CS1010 programming environment
Run:

~cs1010/get-as05

You should see the folder as05-<github id> in your home directory with the assignment skeleton inside.

Solving The Assignments

Edit the files social.c and life.c to solve the corresponding question as described below.
You should break down the problem into smaller subproblems, and write one function for each of the subproblem to solve the problem.
To compile and run tests with the sample inputs and outputs:

make

The test cases are given in the inputs and outputs subdirectory. You can use cat or less to look at the content of these test cases. You can add more test cases or edit the given ones if needed.
new For Question 2, Life, there is no automated testing. So you will not see life: passed as per usual. Instead, you should run each test case manually and view the resulting animation. If an animation is too big to fit into your terminal, try enlarging the terminal or reducing the size of the terminal fonts. The largest canvas is 100 rows and 100 cols.

Submission

When you are ready, run the following command to submit:

~cs1010/submit-as05

The files social.c and life.c will be uploaded to GitHub. You can submit multiple times, but only the last submission will be graded.

Editing Your Files in Multiple Locations

You should edit your code only on the CS1010 PE hosts. If you choose to edit your code in other places, such as directly on Github or in a second location (such as your own laptop), you need to be comfortable with various git command to synchronize your code across the different locations, possibly needing to resolve synchronization conflicts.

Only the C files listed above will be submitted. You can create additional C files for testing different solutions, but eventually, you must put your solution into the corresponding C file provided as the skeleton.

Identifying Yourself

In every C file that you submit to CS1010, you need to identify yourself by writing your name and tutorial group. Marks will be deducted if you fail to do so. You need to edit the line:

@author XXXX (Group YYYY)

and change it to something like:

@author Mikasa Ackermann

Grading

This assignment contributes towards 3% of your final grade. The total mark for this assignment is 30 marks. There are three marking criteria: correctness, documentation, and style.

Documentation: For each question, two marks are allocated for documentation. Please refer to the documentation and follow the recommended format. You need to explain the purpose of every file, function, and parameter. Logic in your code that is not obvious should be explained as well.
new Style: Marks are no longer allocated for style, but we will deduct up to 2 marks if you have a serious violation of the style guideline. Please refer to the CS1010 C Style Guide and follow the recommended guideline.
Correctness: The rest of the marks are allocated to correctness. Note that passing the tests does not guarantee that your code is correct. Correctness here is defined in the broad sense of using the various programming constructs in C (type, function, variable, loops, arrays, pointers, conditionals, arithmetic expressions, logical expressions) properly, not just producing the correct output and bug-free.

We reserve the right to penalize students for using banned C syntax in the assignments. In addition, each grader at his or her own discretion can penalize students for repeating mistakes / bad practices from the student's past assignments (even if it was just a warning with no marks deducted in the earlier assignments).

The idea of six degrees of separation states that everyone in the world is connected to every other person by at most 6 hops. Suppose that a person $A$ is a friend of a person $B$ , then we say that $A$ is one hop away from $B$ . Consider a friend of $B$ , say $C$ , who is not a friend of $A$ . So $C$ is a friend of a friend of $A$ . We say that $C$ is two hops away from $A$ . Six degree of separation generally means there is a chain of friendship that can connect any two people in the world with no more than 6 hops.

In this question, we are going to compute the chain of friendships up to the $k$ degree. Suppose there are $n$ people, and we know the social network of these $n$ people -- i.e., we know who is friend with who. Write a program social to compute a social network representing who is connected to who via a friendship chain of degree $k$ .

We assume that friendship is bi-directional -- if $A$ is a friend of $B$ , then $B$ is a friend of $A$ . Because of this, we can represent a social network as a lower triangular matrix (using jagged 2D array). A proper type to store in each element of the matrix is bool. To simplify our life, however, we store each element of the matrix as a char, with '1' representing a friendship connection, '0' otherwise. The social network for $n$ people is thus an array of $n$ strings, each string containing characters of '0' and '1' only. The first row of the matrix is a string of length one; the second row is of length two; third row, length three, etc. The last character of each string (i.e., the diagonal of the matrix) is 1 since everyone is a friend with him/herself.

For instance, suppose we have the following social network, with Row 1 for Person $A$ , Row 2 for Person $B$ , Row 3 for Person $C$ .

1
01
011

The social network above indicates that $B$ and $C$ are friends with each other. $A$ is not a friend with neither.

As another example, the social network below shows an extra person $D$ (Row 4).

$D$ is friend with both $A$ and $C$ .

Suppose now we consider the social network of degree 2. $A$ is two hops away from $C$ ( $A$ knows $D$ and $D$ knows $C$ ). $B$ is also two hops away from $D$ ( $B$ knows $C$ and $C$ knows $D$ ). The generated social network of degree 2 becomes:

Note that we cannot say everyone is connected to everyone else up to degree 2 in this example since $A$ is not a friend of a friend of $B$ -- i.e., $A$ and $B$ are still not connected, even if we consider a friendship chain of degree 2.

Write a program social, that reads from standard input two positive integers $n$ and $k$ , followed by $n$ lines of strings consisting of '1' or '0' representing the social network of these $n$ people.
Print, to the standard output, the social network formed by a friendship chain of degree $k$ . Finally, print, to the standard output, YES if everyone is connected to everyone within k hops, or NO otherwise.

The purpose of this question is for you to practice using a jagged 2D array. Hence, you are not allowed to store the input matrix or intermediate matrices using a rectangular array, or you risk being penalized heavily for this question.

Sample Run

ooiwt@pe119:~/as05-skeleton$ cat inputs/social.1.in
3 1
1
11
011
ooiwt@pe119:~/as05-skeleton$ ./social < inputs/social.1.in
1
11
011
NO
ooiwt@pe119:~/as05-skeleton$ cat inputs/social.2.in
4 2
1
01
011
1011
ooiwt@pe119:~/as05-skeleton$ ./social < inputs/social.2.in
1
01
111
1111
NO
ooiwt@pe119:~/as05-skeleton$ cat inputs/social.3.in
5 2
1
11
011
0011
10011
ooiwt@pe119:~/as05-skeleton$ ./social < inputs/social.3.in
1
11
111
1111
11111
YES

Question 2: Life (15 marks)

The "Game of Life" is a game played on a two-dimensional orthogonal grid of square cells, while each cell has only two possible states: alive or dead. The game is played in iterations. During each iteration, each cell becomes alive or dead, depending on the state of its four neighboring cells in the previous iteration. Interesting patterns and moving behavior can be created, sometimes infinitely, from an initial state. Refer to wiki page for more details if you are interested.

In this problem, we are going to simulate a game of life for a certain number of iterations, given a starting state. Here is a complete description of the rules of the simulation.

The universe is a bounded plane and can be simply referred to as a two-dimensional orthogonal grid of square cells with $n$ rows and $m$ columns. For convenience, we let row indexes as 0 to $n-1$ from top to bottom, and column indexes as 0 to $m-1$ from left to right. So in total, there are $n \times m$ cells.
The neighbor of a cell is defined as the eight cells that are either horizontally, vertically, or diagonally connected to the cell.
An initial state is given, with each cell is marked as either "live" or "dead".
In each iteration, a cell may switch its state, according to rules below, by referring to the state of the previous iteration:
- Any live cell with fewer than two live neighbors becomes dead
- Any live cell with two or three live neighbors remains alive.
- Any live cell with more than three live neighbors becomes dead.
- Any dead cell with exactly three live neighbors becomes alive
- Border cells, i.e., cells with row number 0 or $n-1$ , or column number 0 or $m-1$ , are always dead. This is to simplify and bound the universe.

Write a program life that reads, from the standard inputs, three positive integers $n$ ( $n > 2$ ), $m$ ( $m > 2$ ) and $k$ , where $n$ and $m$ denotes the number of rows and number of columns of the universe (an $n\times m$ grid), and $k$ is the number of iterations to simulate. It then reads, from the standard input, $n$ rows, with $m$ characters in each row representing the initial state. Each character is either alive ('#') or dead ('.').

The program then prints, to standard output, an animation of the universe for $k$ iterations. The output should only contain $n$ rows with $m$ characters in each row. Similarly, you must use # to represent a live cell, and . to represents a dead cell.

Animation on Screen

We have provided a few lines of code in the skeleton file. You should insert this at appropriate places:

  char clear_screen[] = { 27, '[', '2', 'J',27, '[', ';', 'H'};
     :
  cs1010_print_string(clear_screen);
  // TODO(by student) draw the universe
  usleep(250*1000);

Line 1 in the code above defines a special string that, when printed, will clear the screen and place the cursor on the top left corner of the terminal. Line 5 calls the system function usleep that takes in the number of microseconds. Calling usleep causes the program to pause for that amount of time. We set the sleeping time to 250ms. You can reduce if you wish but you must not increase this beyond 250ms or your program might fail when we test it during grading.

Sample Inputs

The pattern from life.1.in is called a blinker.
The pattern from life.2.in is called a pentadecathlon.
The pattern from life.4.in is called a pulsar.

We provide a total of seven patterns for your to play with.

If you wish the check if your output is correct, you can still redirect the output from life to a file, and compare it with the corresponding output under the output directory using the diff command:

ooiwt@pe119:~/as05-skeleton$ ./life < inputs/life.3.in > OUT
ooiwt@pe119:~/as05-skeleton$ diff OUT outputs/life.3.out

If diff does not list any differences, then the output from your life is the same as the expected output.

Students interested to play more game of life can also check out LifeWiki for more patterns and spiral-click into various information about this game.