Exercise 3: Fixed-Length Arrays

Prerequisite

You have completed Exercise 2.

Learning Outcomes

Be comfortable writing simple C programs that involve fixed-length arrays.

Deadline

This is part of the CS1010 formative assessment. Submit before 9 October 2023, 23:59 to receive feedback and earn your achievement "badges".

Acceptance Link

The link to accept the exercise is not available publicly. Visit Canvas for the link.

Concepts and Difficulty

	Question	Array as Lookup Table	Array as Compound Type	Efficiency	Difficulty
1	Counter^
2	Dot
3	Unit
4	Largest^
5	Days^
6	ID^
7	Max
8	Padovan

^: Questions 1, 4 - 6 serve as in-class exercises during the lab session in Week 7.

Efficiency

For max and padovan, your code should not waste time by doing redundant work. With the given compilation settings, max should take no more than 1s for the given test cases; padovan should take no more than 2s for the given test cases.

Question 1: Counter

Write a program called counter that reads in a non-negative integer and count how many times each digit appears in this number. Print each digit and the number of times it appears on a separate line, in ascending order of the digits. Digits that do not appear in the input number need not be printed.

Sample Runs

ooiwt@pe113:~/ex03-ooiwt$ ./counter
24680
1
1
1
1
1
ooiwt@pe113:~/ex03-ooiwt$ ./counter
0
1
ooiwt@pe113:~/ex03-ooiwt$ ./counter
4611686018427387904 
2
3
1
1
3
3
2
3
1

Question 2: Dot

Write a program called dot that, given two 4-dimension vectors, find its dot product.

Your program should read the two vectors from the standard inputs. Each vector is specified by four integers. Print, to the standard output, the dot product of the two vectors.

Sample Runs

ooiwt@pe113:~/ex03-ooiwt$ ./dot
1 2 3 2
2 1 0 3
10
ooiwt@pe113:~/ex03-ooiwt$ ./dot
100 100 100 100
1 2 -2 -1
0

Question 3: Unit

A unit vector is a vector with a length of 1. Write a program that, given a 3-dimensional vector, find the unit vector in the same direction.

Your program should read a 3-D vector \(\vec{v}\) from the standard inputs, specified by three integers. Print, to the standard output, the unit vector in the same direction of \(\vec{v}\). Print each element in the vector on a new line.

Solve this problem by writing a function with the following header:

void find_unit_vector(const long v[3], double unit[3]) { .. }

Sample Runs

ooiwt@pe113:~/ex03-ooiwt$ ./unit
1 1 1
0.5774
0.5774
0.5774
ooiwt@pe113:~/ex03-ooiwt$ ./unit
-2 0 1
-0.8944
0.0000
0.4472

Question 4: Largest

An integer can be transformed into another by rearranging its digits. Given a number \(n\), we want to find the largest number after rearranging the digits in \(n\).

For example, the largest possible number we get by rearranging the digits in 6752378 is 8776532.

The largest possible number we get by rearranging the digits in -1010 is -11.

Write a program called largest that reads an integer \(n\) from the standard input and prints to the standard output the largest possible number we get by rearranging the digits in \(n\).

Solve this by using a fixed-length array, building upon the solution of counter, and by writing a function with the following header:

long find_largest(long n) { .. }

Sample Runs

ooiwt@pe113:~/ex03-ooiwt$ ./largest
6752378
8776532
ooiwt@pe113:~/ex03-ooiwt$ ./largest
-1010
-11

Question 5: Days

Write a program called days that reads in two integers from the standard input, the first is the month (ranged from 1 to 12, inclusive) and the second is the day (ranged from 1 to 31, inclusive). The program then prints to the standard output which day of the year it is. For instance, September 15 is the 258th day of the year. If the input to days is 9 15, the program should print 258.

Assume that the year is not a leap year.

Use a fixed-length array and loops to solve this problem instead of conditional statements. Avoid using conditional statements (in any form, including if-else, switch, and the ? : operator).

Sample Runs

ooiwt@pe112:~/ex01-ooiwt$ ./days
1 1
1
ooiwt@pe112:~/ex01-ooiwt$ ./days
9 15
258
ooiwt@pe112:~/ex01-ooiwt$ ./days
12 31
365

Question 6: ID

Your NUS student id has a letter at the end. This letter is called a check code and is a form of redundancy check used for detecting errors, especially when your student id is manually entered into a software application.

Your check code is calculated by:

Sum up the digits in your student id. Let the sum be \(N\).
Divide \(N\) by 13, and take the remainder. Let the remainder be \(R\).
Look up the table below:

R	Check Code
0	Y
1	X
2	W
3	U
4	R
5	N
6	M
7	L
8	J
9	H
10	E
11	A
12	B

Write a program id.c that reads in an integer containing the digits of a student's id from the standard input. Print out the check code to the standard output.

Each check code can be stored as a char variable. In C, char constants are surrounded by a single quote, e.g., 'A'. You can use the putchar function to print a single char variable to the standard output.

Example:

#include "cs1010.h"
int main() {
  char a[2] = { 'A', 'B' }; // an array of two `char`
  putchar(a[0]); // print 'A'
}

Use a fixed-length array and loops to solve this problem instead of conditional statements. Avoid using conditional statements (in any form, including if-else, switch, and the ? : operator).

Sample Runs

ooiwt@pe116:~/ex03-ooiwt$ ./id
1933091
Y
ooiwt@pe116:~/ex03-ooiwt$ ./id
3364497
E
ooiwt@pe116:~/ex03-ooiwt$ ./id
1111111111111
Y

Question 7: Max

Write a program max that finds the maximum value from a list \(L\) of \(k\) integers.

Instead of doing this with a loop, solve this question with recursion. Fill in the function

long find_max(const long list[], long start, long end)
{
    :
}

that calls itself recursively and returns the maximum value among the array elements list[start] .. list[end - 1].

In the function definition above, the keyword const (short for constant) is used to annotate that the array list is meant to remain unchanged.

The program should read the following from the standard inputs:

The first number is a positive integer \(k\).
The next \(k\) numbers correspond to the list of integers \(L\).

The program should then print the largest integer from the list to the standard output.

\(k\) is guaranteed to be no more than 100000. We can use a fixed-length array on the stack to store the inputs. The main function to read the inputs and print the maximum value has been given. You should not change the main function unless you have a good reason.

Since you are supposed to solve this problem with recursion, you are not allowed to use loops of any kind (for, while, do-while) inside the function find_max. Solutions that use loops inside find_max is considered incorrect.

Sample Runs

ooiwt@pe116:~/ex03-ooiwt$ cat input
5
-5 3 1 8 2
ooiwt@pe116:~/ex03-ooiwt$ ./max < input
8

Question 8: Padovan

Padovan numbers are a sequence of numbers defined as follows:

\[ p(i)= \begin{cases} 1 & i = 0 \\ 0 & i = 1 \\ 0 & i = 2 \\ p(i-2) + p(i-3) & i > 2\\ \end{cases} \]

You might notice the similarity between the Padovan numbers and Fibonacci numbers. Padovan numbers are named after Richard Padovan, an architect. Unlike Fibonacci, Mr. Padovan is "only" 88 years old and the sequence is named after him only recently!

Like the Fibonacci sequence, the Padovan sequence grows quickly. The number \(p(161)\) would exceed the limit of the type long. For this question, we will thus consider a variation of Padovan sequence, called 4D-Padovan, where we only compute the last 4 digits, as such:

\[ p(i)= \begin{cases} 1 & i = 0 \\ 0 & i = 1 \\ 0 & i = 2 \\ (p(i-2) + p(i-3)) \bmod 10000 & i > 2\\ \end{cases} \]

Write a program padovan that reads in a non-negative integer \(n\) from the standard input, and writes to the standard output, 100 4D-Padovan numbers \(p(n - 1)\), \(p(n - 2)\), .. \(p(n-100)\), in order (one number per line).

\(n\) is guaranteed to be 100 or more.

There is a time-limit of 2s per test case. Hint: To solve within this time limit, avoid repetitively re-calculating the same sequence of numbers over and over.