Question 1

(●◌◌◌)

:

Passing this question, or question 3, is sufficient to pass the linked lists hurdle.

(12 marks)

Note prac_q1.c uses the following data type:

struct node {
    struct node *next;
    char         character;
};

The function count_vowel_word_boundaries takes one argument, head, where head is a pointer to the first node of a linked list.

The function should return the number of vowel word boundaries in the list. If the list is empty, count_vowel_word_boundaries should return -1.

A vowel word boundary occurs when a node containing a vowel is immediately followed by a node containing a consonant.

For example, suppose a linked list contains the following values:

a -> b -> c -> e -> u -> d -> i -> NULL

The vowels in this list are 'a', 'e', 'u', and 'i'.

• 'a' is followed by consonant 'b' so this is one boundary.
• 'e' is followed by vowel 'u' so this is not a boundary.
• 'u' is followed by consonant 'd' so this is one boundary.
• 'i' is followed by nothing, as it is the last node in the list, so this is not a boundary.

The function count_vowel_word_boundaries should return the value 2.

Testing

prac_q1.c also contains a main function which allows you to test your count_vowel_word_boundaries function.

This main function:

• Converts the string entered as a command-line argument to a linked list of characters.
• Assigns a pointer (head) to the first node in the linked list.
• Calls count_vowel_word_boundaries(head).
• Prints the result.

Do not change this main function. If you want to change it, you have misread the question.
Your count_vowel_word_boundaries function will be called directly during marking. The main function is only to let you test your count_vowel_word_boundaries function.
Here is how the main function allows you to test count_vowel_word_boundaries:

dcc prac_q1.c -o prac_q1
./prac_q1 a
0
./prac_q1 aeiou
0
./prac_q1 aeioux
1
./prac_q1 axeixou
2
./prac_q1
-1
./prac_q1 thequickbrownfoxjumpsoverthelazydog
10

Assumptions/Restrictions/Clarifications.

• The linked list can only contain lower case characters.
• count_vowel_word_boundaries should return -1 if the list is empty.
• count_vowel_word_boundaries should return only a single integer.
• count_vowel_word_boundaries should not change the linked list it is given.
• count_vowel_word_boundaries should not change the next or character fields of list nodes.
• count_vowel_word_boundaries should not use arrays.
• count_vowel_word_boundaries should not call malloc.
• count_vowel_word_boundaries should not call scanf (or getchar or fgets).
• count_vowel_word_boundaries should not print anything. It should not call printf.
• count_vowel_word_boundaries does not need to consider integer overflow in its calculations.
• Do not change the definition of struct node.
• Do not change the supplied main function. It will not be tested or marked.

Question 2

(●◌◌◌)

:

Passing this question, or question 4, is sufficient to pass the arrays hurdle.

(12 marks)

Your sum_border function should compute the sum of all elements on the border of a given two-dimensional array and return that sum. This includes all elements in the top row, bottom row, leftmost column and rightmost column, making sure to not double-count the corners.

The sum_border function will be passed two arguments:

• size, representing the dimensions of a square two-dimensional array, such that the array has size rows and size columns.
• The square two-dimensional array itself.

For example, if the 2D array contains these 25 elements, across 5 rows:

{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1} 

Your function should return 16, as there are 16 border elements in the two-dimensional array that sums to 16, without double-counting the corners.

For example, if the 2D array contains these 16 elements, across 4 rows:

{17, -24,   1,   8},
{23,  76,   7,  44},
{ 4,   6,  35, 100},
{10,  81,  19, -21}

Your function should return 262, as there are 12 border elements in the two-dimensional array that sums to 262, without double-counting the corners.

Testing

prac_q2.c also contains a simple main function which allows you to test your sum_border function.

Your sum_border function will be called directly in marking. The main function is only to let you test your sum_border function.

Assumptions/Restrictions/Clarifications.

• size will have a value of at least 2.
• size can have a maximum value of 100.
• sum_border should return a single integer.
• sum_border does not need to consider integer overflow in its calculations.
• sum_border should not change the array it is given.
• sum_border should not call scanf (or getchar or fgets).
• sum_border can assume the array should always be a square.
• sum_border should not print anything. It should not call printf.
• Your submitted file may contain a main function. It will not be tested or marked.

Question 3

(●●◌◌)

:

Passing this question, or question 1, is sufficient to pass the linked lists hurdle.

(12 marks)

Note prac_q3.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

The function delete_first_local_max takes one argument, head, where head is a pointer to the first node of a linked list.

The function should delete the first local maximum in the list, free the memory at the deleted node and then return the head of the list.

A local maximum is any node containing a value that is strictly greater than both its previous node and its next node.

If the list:

• Is empty, then delete_first_local_max should return NULL.
• Does not contain a local maximum, then delete_first_local_max should return the head of the unmodified list.

For example, suppose the linked list contains the following values:

11 -> 7 -> 12 -> 9 -> 8 -> 13 -> 2 -> 14 -> X

This list contains two local maxima: 12 and 13.

• 12 is a local maximum because it's greater than both its previous node (7) and its next node (9).
• 13 is a local maximum because it's greater than both its previous node (8) and its next node (2).
• 11 and 14 are not local maxima since:
  • 11 has no previous node to compare with, so cannot be greater than its previous node.
  • 14 has no next node to compare with, so cannot be greater than its next node.

The function delete_first_local_max should delete the node containing the first local maximum (in the above example, it would be the node containing 12), free the memory at the deleted node and then return a pointer to the head of the list.

The final list should be:

11 -> 7 -> 9 -> 8 -> 13 -> 2 -> 14 -> X

Testing

prac_q3.c also contains a main function which allows you to test your delete_first_local_max function.

This main function:

• Converts the command-line arguments to a linked list.
• Assigns a pointer to the first node in the linked list to head.
• Calls delete_first_local_max(head).
• Prints the resulting list.

Do not change this main function. If you want to change it, you have misread the question.
Your delete_first_local_max function will be called directly in marking. The main function is only to let you test your delete_first_local_max function.
Here is how the main function allows you to test delete_first_local_max:

dcc prac_q3.c -o prac_q3
./prac_q3 1 3 2
[1, 2]
./prac_q3
[]
./prac_q3 1 2 3 4
[1, 2, 3, 4]
./prac_q3 7 2 3 4
[7, 2, 3, 4]
./prac_q3 1 7 3 4
[1, 3, 4]
./prac_q3 1 2 7 4
[1, 2, 4]
./prac_q3 1 2 3 7
[1, 2, 3, 7]
./prac_q3 11 7 12 9 8 13 2 14
[11, 7, 9, 8, 13, 2, 14]

Assumptions/Restrictions/Clarifications.

• delete_first_local_max should return NULL if the list is empty.
• delete_first_local_max should return the head of the list.
• delete_first_local_max should call free to free the memory of any node it deletes and must pass --leak-check.
• delete_first_local_max should not use arrays.
• delete_first_local_max should not call malloc.
• delete_first_local_max should not call scanf (or getchar or fgets).
• delete_first_local_max should not print anything. It should not call printf.
• Do not change the definition of struct node.
• Do not change the supplied main function. It will not be tested or marked.

Question 4

(●●◌◌)

:

Passing this question, or question 2, is sufficient to pass the arrays hurdle.

(12 marks)

A saddle point is an element in a 2D matrix that is the smallest in its row, but largest in its column. The find_saddle_point function will take a 5 x 5 two-dimensional integer array as an argument. Your task is to complete find_saddle_point, such that it returns the saddle point element if there is one, or if there is no saddle point in the array, it should return -1.

Examples

If the 2D array contains these elements:

    {16, 11, 13,  9, 12}, 
    {94, 73, 42, 64, 56}, 
    {18, 53, 24, 46, 17}, 
    {15, 14, 31, 10, 35}, 
    { 3,  2,  1,  4, 95}, 

Your function should return 42, since the 42 in the second row is both the smallest of its row and the largest in its column.

Alternatively, if the 2D array contains these elements:

    {16, 15, 19, 13,  9}, 
    {95, 73, 77, 56,  8}, 
    {18, 53, 24, 12,  7}, 
    {17, 14, 31, 35,  6}, 
    { 5,  4,  3,  2, 10}, 

Your function should return -1, as there is no saddle point.

Testing

prac_q4.c also contains a simple main function which allows you to test your find_saddle_point function.

Your find_saddle_point function will be called directly in marking. The main function is only to let you test your find_saddle_point function.

Assumptions/Restrictions/Clarifications.

• You may assume that there will either by 1 saddle point or none.
• You may assume all elements are unique.
• You may change the main function to modify the array and test your code, however do not code your answer there. It will not be marked.
• You may assume elements will not be negative integers.
• Do not change the name, return type or parameters of the supplied find_saddle_point function.

Question 5

(●◌◌◌)

:

(5 marks)

The given program is meant to do the following:

• scan in a bank account number (4 digits) and the corresponding account balance.
• print out a message to indicate whether the account is in good standing, empty or overdrawn. If the account has no money, the account is empty. If the account balance is above $0, the account is in good standing. An account with negative balance means it is overdrawn.
• warn or congratulate the user if their balance is below $100 or above $1000 respectively.

However, it has some issues that you need to fix.

Once fixed, your program should match the following example exactly:

dcc prac_q5.c -o prac_q5
./prac_q5
Enter account number: 1122
Enter account balance: 99.99
Account 1122 is in good standing.
Warning: Your account balance is below $100.
./prac_q5
Enter account number: 8888
Enter account balance: 1000.88
Account 8888 is in good standing.
Congratulations! Your account balance is above $1000.
./prac_q5
Enter account number: 6666
Enter account balance: 500.50
Account 6666 is in good standing.
./prac_q5
Enter account number: 4444
Enter account balance: 0
Account 4444 is empty.
Warning: Your account balance is below $100.

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• Assume bank account numbers can only be 4 digits and start with a digit greater than or equal to 1
• Assume bank account balance can only have 2 decimal places or less and is of type double

Question 6

(●◌◌◌)

:

(5 marks)

The given program is meant to print the sum of the first n natural numbers (integers greater than 0). However, it has some issues that you need to fix.

Once fixed, your program should match the following example exactly:

dcc prac_q6.c -o prac_q6
./prac_q6
Enter a number: 1
The sum of the first 1 natural numbers is: 1
dcc prac_q6.c -o prac_q6
./prac_q6
Enter a number: 5
The sum of the first 5 natural numbers is: 15
dcc prac_q6.c -o prac_q6
./prac_q6
Enter a number: !
You have entered an invalid number!

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• You cannot assume that what the user enters will be a number
• You can assume that, if a numerical value is entered, the input value is an integer greater than 0.

Question 7

(●◌◌◌)

:

(5 marks)

The given program is meant to do the following:

• take an integer length and an integer width as input from the user representing the length and width of a rectangle,
• pass it to a function to calculate the perimeter (2 * (length + width)) and the area (length * width) of the rectangle,
• store the resulting values of perimeter and area in the respective pointer variables, and
• print both the perimeter and area in the main function.

However, it has some issues that you need to fix.

Once fixed, your program should match the following example exactly:

dcc prac_q7.c -o prac_q7
./prac_q7
Enter length of the rectangle (in cm): 10
Enter width of the rectangle (in cm): 20
Perimeter of the rectangle: 60cm
Area of the rectangle: 200cm
./prac_q7
Enter length of the rectangle (in cm): 5
Enter width of the rectangle (in cm): 5
Perimeter of the rectangle: 20cm
Area of the rectangle: 25cm
./prac_q7
Enter length of the rectangle (in cm): 1
Enter width of the rectangle (in cm): 4
Perimeter of the rectangle: 10cm
Area of the rectangle: 4cm

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• You can assume that you will be given values of length and width greater than zero

Question 8

(●◌◌◌)

:

(5 marks)

The following code is meant to ask the user to continuously enter char inputs, to be inserted at the head of a linked list until CTRL+D is pressed.

Inputs that are not digits (between 0-9 inclusive) result in "Input '[character]' is not a digit!" being printed, and not adding to the linked list. This means that only digit inputs can be added to the linked list.

The list is printed after CTRL+D is pressed, which should result in printing all digits scanned in, in reverse order.

For example:

dcc prac_q8.c -o prac_q8
./prac_q8
Enter digits:
1
2
a
Input 'a' is not a digit!
*
Input '*' is not a digit!
3

3 2 1
./prac_q8
Enter digits:
1a00b5
Input 'a' is not a digit!
Input 'b' is not a digit!

5 0 0 1

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Question 9

(●●●◌)

:

(11 marks)

In this question, you will write a C program that transforms a string based on a given rule.

The program should do the following:

1. Prompt the user with "Original: " and read in a string original containing only lowercase alphabetical characters (a–z), with a maximum length of 100 characters.
2. Prompt the user with "Nums: " and read 26 integers into an array nums. Each value nums[i] corresponds to how many consecutive characters the character 'a' + i should transform into.
3. For each character original[i], use the number at the corresponding position in the nums array to determine how many consecutive characters, n, to generate from the alphabet, starting at original[i]. Wrap from 'z' to 'a' if needed. Concatenate the resulting characters to form a new string. For example, if original[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters which results in "bcd". Or if original[i] = 'y' and nums[24] = 3 , the character 'y' transforms into the next 3 consecutive characters, which results in "zab".
4. Print the final result using the format "Result string: <result>\n", where <result> is the transformed string.

For example, if we have:

• Original: "abc"
• Nums: [2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Then the resulting string stored in result will be "bccdede".

Since:

• The character a is transformed into the sequence bc as nums[0] is 2. Thus, at this point the result string is bcbc.
• The character b is next transformed into the sequence cde as nums[1] is 3. Thus, at this point the result string is bccdec.
• The character c is next transformed into the sequence de as nums[2] is 2. Thus, at this point the result string is bccdede.

Therefore, the final string stored in result is bccdede.

Examples

dcc prac_q9.c -o prac_q9
./prac_q9
Original: azbxcy
Nums: 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
Result string: babcdyzdz
./prac_q9
Original: z
Nums: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
Result string: abc
./prac_q9
Original: hello
Nums: 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Result string: iijklmnopfghijmmp
./prac_q9
Original: 
Nums: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Result string: 

Assumptions/Restrictions/Clarifications

• The original string has a maximum size of 100.
• The resulting string can be of any size. There is no maximum.
• All Nums numbers will be non-negative integers.
• If a letter has a corresponding Nums value of 0, it should be deleted from the string.
• You can create your own helper functions if you wish.
• The original string may be empty (e.g. only contains '\0').
• You may assume you will always be provided valid input for Original and Nums.
• If using fgets to read input, be sure to remove the trailing newline character (i.e., replace '\n' with '\0' if it exists).
• If you call malloc in your solution, you must ensure that the memory is freed and passes --leak-check.

Question 10

(●●●◌)

:

(11 marks)

You have been given the file prac_q10.c containing the function toggle_passage, that you will need to implement.

Problem Context

In this problem, there are a number of underwater tanks connected to each other, potentially containing water themselves. Your job is to simulate how water moves between these tanks when passages between them are opened and closed.

A visualisation of this system is shown below, with all passages closed.

In this example, the second and third tanks currently contain water. Now, let's open up the passage between the first tank and the second tank. This gives us the new result:

As the passage is opened, water from the second tank has made it into the first tank. Furthermore, since water must stay level, the 80L was split in half to fill up the new space.

Now, let's open up the passage between the second and third tank.

In this case, the first three tanks have complete passages between them. As we had 40 + 40 + 30 = 110L, we needed to distribute it equally between the tanks. This can simply be done by diving the total volume in the tanks by the number of tanks: 110 / 3 = 36.66667

For this problem, we will ignore fractional volumes and so the volume we put in each tank is 36

It is also possible to open up passages between outside water and the first/last tanks. In this case, the tank is flooded as the outside has "infinite" water. Let's open up the first tank to the outside.

Since the first three tanks have open passages, they all get filled. Each tank has a maximum of 99L of capacity, hence why they don't fill up further.

Your Goal

In this program, the tanks are a linked list, with each node (tank) containing the following information:

struct tank {
    int volume;
    enum passage_status left_passage;
    enum passage_status right_passage;
    struct tank *next;
};

• volume - represents how much water is filled in this tank
• left_passage - flag for whether the left passage of this tank is opened or not
• right_passage - flag for whether the right passage of this tank is opened or not
• next - pointer to the next tank in this linked list

Your goal for this problem is to implement the toggle_passage function, which opens and closes passages between tanks, and updates the volumes like in the examples above.

toggle_passage takes in two parameters, the head of the tanks linked list, and the position of the passage to toggle open/closed. This position is simply an integer representing the passage. A position of 0 refers to the passage between the first tank and the outside water. A position of 1 refers to the passage between the first tank and the second tank etc.

Examples

When running the program, the initial tanks and their volumes is given in command line arguments, separated by spaces

dcc prac_q10.c -o prac_q10
./prac_q10 10 20 30
Tanks:
/----\/----\/----\
| 10 || 20 || 30 |
\----/\----/\----/
Enter passage: 2
Tanks:
/----\/----\/----\
| 10 || 25    25 |
\----/\----/\----/
Enter passage: 1
Tanks:
/----\/----\/----\
| 20    20    20 |
\----/\----/\----/
Enter passage: 0
Tanks:
/----\/----\/----\
  99    99    99 |
\----/\----/\----/
Enter passage: 
./prac_q10 0 50 0 0 0
Tanks:
/----\/----\/----\/----\/----\
| 00 || 50 || 00 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 1
Tanks:
/----\/----\/----\/----\/----\
| 25    25 || 00 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 4
Tanks:
/----\/----\/----\/----\/----\
| 25    25 || 00 || 00    00 |
\----/\----/\----/\----/\----/
Enter passage: 2
Tanks:
/----\/----\/----\/----\/----\
| 16    16    16 || 00    00 |
\----/\----/\----/\----/\----/
Enter passage: 3
Tanks:
/----\/----\/----\/----\/----\
| 09    09    09    09    09 |
\----/\----/\----/\----/\----/
Enter passage: 
./prac_q10 0 50 0 0 0
Tanks:
/----\/----\/----\/----\/----\
| 00 || 50 || 00 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 1
Tanks:
/----\/----\/----\/----\/----\
| 25    25 || 00 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 1
Tanks:
/----\/----\/----\/----\/----\
| 25 || 25 || 00 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 2
Tanks:
/----\/----\/----\/----\/----\
| 25 || 12    12 || 00 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 3
Tanks:
/----\/----\/----\/----\/----\
| 25 || 08    08    08 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 2
Tanks:
/----\/----\/----\/----\/----\
| 25 || 08 || 08    08 || 00 |
\----/\----/\----/\----/\----/
Enter passage: 4
Tanks:
/----\/----\/----\/----\/----\
| 25 || 08 || 05    05    05 |
\----/\----/\----/\----/\----/
Enter passage: 1
Tanks:
/----\/----\/----\/----\/----\
| 16    16 || 05    05    05 |
\----/\----/\----/\----/\----/
Enter passage: 2
Tanks:
/----\/----\/----\/----\/----\
| 09    09    09    09    09 |
\----/\----/\----/\----/\----/
Enter passage: 0
Tanks:
/----\/----\/----\/----\/----\
  99    99    99    99    99 |
\----/\----/\----/\----/\----/

Assumptions/Restrictions/Clarifications

• Initial volumes given in command line arguments will always be integers within 0 and 99 inclusive.
• You can assume at least one tank will be provided.
• You cannot use arrays in this problem.
• You may assume that the giving position will always be valid.

Question 11

(●●●●)

:

(10 marks)

You have been given the file prac_q11.c containing the function perform_collapse, that you will need to implement.

Problem Context

This problem is centred around a quantum mechanics idea that has been extended to a computer graphics algorithm.

There are a couple of ideas in this algorithm:

1. This algorithm acts on a grid of cells.
2. Each cell contains all the possible states it can take.
3. Some states cannot appear next to other states
4. A cell can be collapsed to a single state from these possibilities.
5. When a cell is collapsed, this can affect any and every remaining cell in the grid, as a result of point 3.

For example, consider a grid that can be made up of 4 states:

State	Image	Valid neighbours
Water
Sand
Grass
Tall Grass

With these rules, play around with the interactive below. For each cell, you can select one of the 4 states described above to collapse it down to a single state. See what happens to the surrounding cells when this occurs.

Importantly, notice how the set of possible states in each cell reduces when a cell is collapsed. For example, if a cell collapses to water, then cells up to 2 blocks away can no longer collapse to tall grass.

Reset states

Your Goal

You will be implementing a very similar version of the interactive above, but on the command line instead, with integers instead of images.

Your program will take in the total number of states in the program as a single command line argument. The starter code handles this. It is important to note that if the user enters 4, then there are 4 states: 1, 2, 3, 4.

Your program will then scan in the total size of the board/grid to be used. The starter code handles this.

You will implement the following, in the function perform_collapse:

Your program should scan in the valid neighbours of each state. If we translate the example states used in the interactive, this would look like:

Enter valid neighbours of state '1', followed by 'x': 1 2 x
Enter valid neighbours of state '2', followed by 'x': 1 2 3 x
Enter valid neighbours of state '3', followed by 'x': 2 3 4 x
Enter valid neighbours of state '4', followed by 'x': 3 4 x

Where states 1, 2, 3, 4 correspond to water, sand, grass, tall grass respectively.

Then, your program will continuously need to scan in row/column pairs representing each cell, followed by what state to collapse it to.

The starter code given already handles the command line arguments, board sizing and grid initialisation.

The starter code also provides some data structures to represent the board:

---

struct node {
    int state;
    struct node *next;
};

This represents a linked list of possible states of a cell. For the provided function print_states to function correctly, this linked list must be sorted by the state value in ascending order.

---

struct state {
    int collapsed_state;
    struct node *possible_states;
};

This represents a cell. Each cell is either a single collapsed state, or a linked list of possible states. If the cell is not collapsed, the collapsed_state value must be set to 0, otherwise it should be set to the state it is collapsed to.

---

You need only complete the perform_collapse function, which gives you a 2D array of struct state cells, already initialised.

You will find the print_states function useful for printing out this 2D array. If you make any changes to the provided structures, then you may have to modify or replace this function to ensure that the board is printed correctly.

Examples

dcc prac_q11.c -o prac_q11
./prac_q11 3
Board size: 3
Enter valid neighbours of state '1', followed by 'x': 3 x
Enter valid neighbours of state '2', followed by 'x': 1 2 3 x
Enter valid neighbours of state '3', followed by 'x': 1 2 x
Initial state board:
-------------
|123|123|123|
|   |   |   |
|   |   |   |
-------------
|123|123|123|
|   |   |   |
|   |   |   |
-------------
|123|123|123|
|   |   |   |
|   |   |   |
-------------
Collapse next cell (row/col/state): 0 0 2
-------------
|222|23 |123|
|222|   |   |
|222|   |   |
-------------
|23 |123|123|
|   |   |   |
|   |   |   |
-------------
|123|123|123|
|   |   |   |
|   |   |   |
-------------
Collapse next cell (row/col/state): 2 2 1
-------------
|222|23 |12 |
|222|   |   |
|222|   |   |
-------------
|23 |12 |3  |
|   |   |   |
|   |   |   |
-------------
|12 |3  |111|
|   |   |111|
|   |   |111|
-------------
Collapse next cell (row/col/state): 1 1 1
-------------
|222|3  |12 |
|222|   |   |
|222|   |   |
-------------
|3  |111|3  |
|   |111|   |
|   |111|   |
-------------
|12 |3  |111|
|   |   |111|
|   |   |111|
-------------
Collapse next cell (row/col/state): 

Assumptions/Restrictions/Clarifications

• You may change any starter code provided.
• The given number of states will always be an integer between 1 and 9 inclusive.
• You will not be asked to collapse a cell down to a state it cannot be.
• Valid neighbours will be given such that it is always possible to place any state in the first collapsed cell.
• No error checking is required when scanning values. All inputs given for row, col, state, etc. will be valid.
• If state a can have state b as a valid neighbour, but not the other way around, then a cannot be placed next to b. Both states must have each other as valid neighbours.
• Your program will not be tested for memory leaks.
• If there are no more cells left to collapse, you can assume that the next input is CTRL-D, ending the program.