COL100 Assignment 7 Solved

1 Stairway to Heaven (In Lab Component)

Mr. Page has found the stairway to heaven. The number of steps to go to heaven is N. He is currently at the 0th stair and wishes to reach the Nth stair. Mr. Page can take 1 or 2, or 3 steps in a single jump. Mr. Page is not a mathematician and needs your help determining the number of ways in which he can reach heaven.

For example, if N = 9 then some of the possible jump combinations are: (3, 3, 3), (2, 2, 2, 3), (3, 3, 2, 1)…. For example, (3, 3, 3) is a valid jump combination because 3 + 3 + 3 = 9 and each jump covers 1, 2, or 3 steps only. Similarly, for (2, 2, 2, 1), we have 2 + 2 + 2 + 3 = 9, so it is a valid combination. The total number of valid combinations of jumps will be 149 for the input N = 9, and Mr. Page only needs this number (not the list of all jump combinations).

Your solution should run in linear time – O(N). Here N, is the number of steps to reach heaven. You have to write a short description (2-3 lines) of why your code has linear time complexity, write it inside the comments in the skeleton code.

We have provided a skeleton code which takes input; type cast the input into int; call the func- tion heaven() and print the return value of the function heaven(). You have to only implement the function heaven() and return the output as integer — you must not print anything in the function.

Input: The first line (only input line) of input will contain the value of N (only integer (int type); follow the skeleton code.).

Return Output : Only return the total number of combinations of jumps (only integer (int type)). Some points to note:

1. Any algorithm of time complexity more than O(N) will receive 0. As the stairs go to heaven, they might have large values.

2. Combinations like (1, 3) and (3, 1) are considered distinct and are counted as 2 while combination like (1, 1) and (1, 1) are same and considered as 1 .

Example 1:

INPUT: 1 300

OUTPUT:
1 15350287614359738671843506567023635268924281173051801861566524609184461020990367

Example 2:

INPUT: 14

OUTPUT: 17

EXPLANATION:
Possible Combinations are [(3,1),(1,3),(2,2),(2,1,1),(1,2,1),(1,1,2),(1,1,1)]. Total 7

2

2 Sorting (10 marks)

You have been given a string that can contain digits (base 10) or letters(’a’-’z’ or ’A’-’Z’) only. You have to arrange the characters of this string in such a way that all occurrences of digits (0-9) which occur the odd number of times are moved to the front of the string in ascending order. The rest of the characters in the string are to be preserved.

We have provided a skeleton code which takes input; call the function sortings () and print the returned output (which you have returned from function sortings ()). You have to only im- plement the function sortings() and return your output without printing anything in the function.

Input: The first line of input (only input line) will contain string (can only contain digits (base 10) or letters, follow skeleton code.).

Return Output : Only “return” the string arranged in the manner mentioned above. (only string type and string contains only digits (base 10) or letters).

Some points to note:

1. In this question, we will be checking ONLY your output, so make sure to return correct format. Any output format mismatch will result in 0.

2. Characters of strings can be case sensitive like “A” and “a” are different.

Constraint: Example 1:

INPUT:
1 81454aDc5445bd

OUTPUT:
1 1555844aDc44bd

Length of string can be 0 (“”) and can go as large as you can think.

EXPLANATION:
Digits occurring the odd number of times are = 8, 1, 5. Also, 5 occurs three times.
Remaining characters in the string are 44aDc44bd.
So string returned by sortings() is 1555844aDc44bd

Example 2:

INPUT:
1 322fcd223

OUTPUT: 1 322fcd223

EXPLANATION:
Here, digits occurring odd number of times are none. So the character left is the same as the original.

3

3 Sorting a list (25 marks)

You have been given a list of strings and each string can contain digits (base 10) or letters only. For each string, you have to arrange the character of them (each string) in the same manner as mentioned as in Question 2. After this, for the resulting list of strings, you have to sort the list as follows – for each string, you have to extract all digits starting from index 0 until any non-digit character (“a”-“z” or “A”-“Z”) comes or the end of a string is encountered. Compare the extracted numer- ical value of one string with extracted numerical values of other strings to sort the list in ascending order.

For example, if a string output of question 2 is “1112355744hkj887”; then extracted numerical value will be 1112355744.

We have provided a skeleton code which takes input from you; call the function “sortings” and print the returned output (which you have returned from function “sortings”). You have to write your code, in function “sortings” only and “return” your output and do not need to print anything in function.

Input: The first line of input will contain the number of strings in the list (int type). From the second line onwards, each line will contain a string of the list. ( str type, follow skeleton code.).

Return Output : Only “return” the list of strings in the sorted manner as explained in the question. (Only return list , follow skeleton code).

Some important points to note:

1. In this question, we will be checking ONLY your Output, so make sure to return the correct format. Any output format mismatch will result in 0.
2. Follow skeleton code, otherwise you can loose marks. You can make your own function which can be called from function “sortings”
3. If for two strings, numerical values are the same, then either string can be in front of the other (order does not matter for these two).
4. If no numerical value can be extracted from the string, then it is to be put at the last of list because it’s equivalent numerical value will be None and not 0.
5. If length of string is 0 (“”), then it’s equivalent numerical value will be None and not 0.

Constraint: Length of string can be 0 (“”) and can go as large as you can think. Length of list can

be 0 that is ([]) and can go as large as you can think. Use of None is allowed. Example 1:

INPUT:

1 2 3 4 5

OUTPUT:
1 [‘1234455bac889966’, ‘44332211’, ‘44332211abc’, ‘abcdef5588447755’]

EXPLANATION:

4

1. The given list is [’44332211’, ’4412355bac889966’, ’abcdef5588447755’, ’44332211abc’].

2. After calling Question 2 for each string we get [’44332211’, ’1234455bac889966’, ’abcdef5588447755’, ’44332211abc’].

3. Extracted numerical value are [44332211, 1234455, None, 44332211].
4. Sorting these numerical value we get [1234455, 44332211, 44332211, None].
5. Thus, Output list will be [’1234455bac889966’, ’44332211’, ’44332211abc’, ’abcdef5588447755’]

Example 2:

INPUT:

1 2 3 4

OUTPUT:
1 [‘00000hgf0’, ‘124533abc66’, ‘7891010efg’]

5