Week 3: Exercises

These are optional exercises that I suggest you try to practice the material we've learned so far.


1. Reverse A String

Write a function reverseString(s: string): string that behaves just like the library function of the same name.

2. Words in a String

Write a function words(s: string): integer that returns the number of words in a string, where words are separated by one or more spaces.

3. Capitalize a String

Write a function capitalize(s: string): string that capitalizes the first letter of every word in a string, where words are separated by one or more spaces.

4. Recursive Power

Write a recursive function power(a: integer; b: integer): integer that returns ab, assuming that b ≥ 0. Do not use any assignment statements (:=) or library functions.

5. First and Last

Write a function firstLast(n: integer): integer that returns the sum of the first and last digits in n. Do not use any strings.

6. Number Palindrome

Write a function isPalindrome(n: integer): boolean that returns true if n is a palindrome (i.e. it reads the same forward and backward) when expressed in decimal notation. Do not use any strings.

7. Palindrome Product

Solve Project Euler's problem 4. You may want to use your function isPalindrome from the previous exercise.

8. Bits, Recursively

Write a recursive function bits(n: integer): integer that returns the number of bits (i.e. binary digits) in the base-2 representation of n. Do not use any assignment statements (:=) or library functions.

9. Immediate Binary Digits

Write a function bits(n: integer): integer that returns the number of bits (i.e. binary digits) in the base-2 representation of n without any iteration or recursive calls. You may use library functions.

10. Pythagorean Triplet

Solve Project Euler's problem 9.

11. Printing with Commas

Write a program that reads an integer which may be arbitrarily large, and writes the integer with embedded commas.

Input:

28470562348756298345

Output:

28,470,562,348,756,298,345

12. Column with Largest Number

Write a program that reads an integer N followed by an N x N matrix of integers. The program should print the largest value in the matrix and the column number that contains it.

Input:

3
2 8 3
9 6 7
0 3 -1

Output:

Column 1 contains 9.

13. Largest Row or Column Sum

Write a program that reads an integer N followed by an N x N matrix of integers. The program should print the largest sum of any row or column in the matrix.

Input:

4
2 4 8 10
5 3 7 1
9 6 9 4
2 2 8 3

Output:

32

14. Magic Square

A magic square is an N x N matrix of distinct positive integers in the range 1, 2, …, N2 such that the sum of every row, column and diagonal is the same. For example:

2 7 6
9 5 1
4 3 8

In the square above, all rows, columns and diagonals add up to 15.

Write a program that reads an integer N followed by an N x N matrix of integers. The program should print 'magic' if the square is magic, or 'ordinary' otherwise.

15. Largest product in a grid

Solve Project Euler's problem 11.

16. Longest Sequence in a Column

Write a program that reads an integer N followed by an N x N matrix of integers. The program should print the column number that contains the longest consecutive sequence of positive integers, and the length of that sequence.

Input:

4
0 6 2 3
3 4 -1 4
0 7 4 0
2 -2 3 4

Output:

Column 2 contains a sequence of 3 positive integers

17. Rotate a Matrix

Write a program that reads an integer N followed by an N x N matrix of integers and rotates it to the right.

Input:

4
2 4 6 8
8 6 4 2
1 3 7 9
9 7 3 1

Output:

9 1 8 2
7 3 6 4
3 7 4 6
1 9 2 8

18. Rotate by an Angle

Write a program that reads an integer N, an angle T and an N x N matrix of integers. Print the matrix rotated to the right by T degrees. T is guaranteed to be a multiple of 90, and may be negative.

Input:

4 270
2 4 6 8
8 6 4 2
1 3 7 9
9 7 3 1

Output:

8 2 9 1
6 4 7 3
4 6 3 7
2 8 1 9

19. Simulated Rumor

Write a program that reads an integer N, representing a number of people. Simulate a rumor that spreads among these people as follows. A random person starts the rumor. They tell it to another person selected at random, who tells it to someone else, and so on, until someone hears the rumor who has already heard it before. At that point the rumor stops circulating. The program should produce output like this:

Enter N: 100
Person 41 heard the rumor.
Person 83 heard the rumor.
Person 22 heard the rumor.
…
Person 83 heard the rumor again.
14 people heard the rumor in all.

20. Repeated Rumor

Extend the problem from the previous exercise to accept an additional integer T. The program should run T trials, in each of which a rumor spreads as in the previous exercise. At the end the program should print out a floating-point number representing the average number of people who heard the rumor in all the trials.

21. Simulated Guesser

Write a program that simulates the following game. Player A chooses a random number from 1 to 100. Player B tries the guess the number. After each guess, player A tells player B whether the guess is correct, too high, too low. The program should write output like this:

50: too low
75: too high
62: too low
68: too low
71: correct!

22. Binary Search, Counted

Modify the binary search function from lecture 3 to return an integer k ≥ 0 which is the number of times that the key value appears in the sorted array.

23. Binary Search, Below

Modify the binary search function from lecture 3 to return an integer b which is the greatest value in the array that is less than or equal to the key (which itself might not be in the array). If there is no such value, it should return -1.

24. Binary Search For Range

Modify the binary search function from lecture 3 to look like this:

function binary_search(a: array of integer, lowKey: integer, highKey: integer): integer;

The function should return the number of values v in the array such that lowKey ≤ v ≤ highKey.

25. Tic Tac Toe Winner

Modify the tic tac toe program from tutorial 2 to report who has won the game, or if a draw has occurred.

26. Poker Hands, No Suits

Write a program that reads a string representing a hand of five cards, where cards are represented using the following characters: Jack = J, Queen = Q, King = K, Ace = A, Ten = T, and other cards (2-9) by a digit. (There are no suits). For example, “357JQ” and “TT332” are hands. Cards may appear in any order.

The program should output one of the following ranks:

(Ignore other kinds of poker hands such as full houses for this exercise.)

27. More Poker Hands

Extend the program from the previous exercise to report these ranks as well:

In addition, instead of “no pair” the program should report the high card in a hand with no pair. For example, the hand “357JQ” has rank “Q high”. The hand “A2748” has rank “ace high”. (A > K > Q > J > T > 9 > 8 > … > 2.)

28. Spaceship

Write a program that clears the terminal and draws a single character O in the middle, representing a spaceship. Each time the player presses an arrow key, move the shapeship one character left, right, up or down. If the player presses 'q', quit the program. Use the functions from the crt unit.

29. Moving Spaceship

Modify the spaceship program so that after the player presses an arrow key, the spaceship keeps moving in that direction (once per 100 ms) until the user presses the space bar to stop the ship.