Week 6: Exercises

1. Contains

Write a function contains that takes two strings S and T, and returns true if S contains T. For example, contains('key lime pie', 'lime') should return true.

2. Highest Sum in Any Base

Write a program that reads a decimal number N and computes the sum of the digits of N in every base from 2 through 10. The program should write out the base number in which the digit sum is greatest. For example, if N = 10 the program will write 6. That's because 10 = 146 in which the digit sum is 1 + 4 = 5, and no other base would give a higher digit sum.

3. Time Addition

This record type represents a time of day:

type
  time = record
    hours: integer;     // 0 .. 23
    minutes: integer;   // 0 .. 59
  end;

Write a function

function addMinutes(t: time; n: integer): time;

that adds a number of minutes to a time, wrapping around as necessary. For example:

4. Word Reversal

Write a function

function reverseWords(s: string): string;

that reverses the words in a string. For this exercise, a word is any set of non-space characters surrounded by spaces. The output string should have only one space between words, and no spaces at the beginning or end of the string. For example, reverseWords(' big black dog ') returns 'dog black big'.

5. Largest Palindrome Product

(Project Euler, problem 4)

A palindromic number such as 7117 reads the same forwards and backwards.

Find the largest palindromic number that is the product of two 3-digit numbers. Do not use any strings in your solution.

6. Number of Ones

Write a function ones that takes an integer n and returns the number of 1s in n's binary representation. For example, ones(19) = 3 because 1910 = 100112, which has three 1s.

7. Reversed Binary Digits

Write a function

function reverseBinary(n: integer): integer;

that transforms the number n by reversing its digits when written in base 2. For example, reverseBinary(23) is 29. That's because

8. Adjacent Digits

Write a function

function adjacent(n: integer; base: integer): boolean;

that returns true if the number n contains any two identical adjacent digits when written in the given base. For example, adjacent(34, 5) = true, because 3410 = 1145, which contains two adjacent 1s.

9. Distinct Digits

Write a function

function distinct(n: integer; base: integer): boolean;

that returns true if all digits of n are distinct when n is written in the given base – in other words, no two digits are the same. For example, distinct(346, 5) = true, because 34610 = 23415, and no two digits of 23415 are the same.

10. Prime Base

Write a function

function primeBase(n: string): integer;

that takes a string of digits n in the range 0 .. 9 and returns the highest base b such that (a) n can be interpreted as a number in base b and (b) the resulting number is prime.

11. Flipped Binary Digits

Write a function

function flipBinary(n: integer): integer;

that transforms the number n by flipping all its digits when written in base 2: 0 becomes 1 and 1 becomes 0. For example, flipBinary(23) is 8. That's because

Hint: You don't need to flip each digit individually.

12. Beginning With M

Write a function

function firstM(a: const array of string): string;

that takes an array of strings that is sorted in alphabetical order, ignoring case. The function should return the first string in the array that begins with the letter 'm' or 'M', or the empty string if there is no such string in the array. The function must run in time O(log N), where N is the length of the input array (assuming that string lengths are bounded by some constant). For example:

var
  a: array[1..10] of string = (
    'Bridge', 'building', 'meteor', 'mill', 'MIST', 'mountain', 'Roof', 'SKY', 'spire', 'window'

 );

…
  writeln(firstM(a));  // writes 'meteor'

13. Even and Odd

Write a procedure

procedure evenAndOdd(var a: array of integer);

that rearranges the elements of a so that all even elements appear first, followed by all odd elements. Preserve the previous ordering of even and odd elements. For example, if a is

(3, 2, 7, 1, 8, 10, 11, 6, 5, 12)

then after a call to evenAndOdd, a will be

(2, 8, 10, 6, 12, 3, 7, 1, 11, 5)

14. Random Walk

Write a program that reads a number N and simulates a random walk starting at (0, 0) in a square with corners at (-N, -N) and (N, N). At each step of the random walk, move one unit left, right, up or down at random. The random walk should end as soon as it exits the square. When it is done, print out a diagram showing the path of the walk, i.e. the squares it touched. It might look like this:

8
. . . . . . . * . . . . . . . . . 
. . . . . . * * . . . . . . . . . 
. . . . . . * * . . . . . . . . . 
. . . . . . . * * . . . . . . . . 
. . . . * * * * . . . . . . . . . 
. . . . * * . . * * * . . . . . . 
. . . . * * * * * . * * . . . . . 
. . . . * . * * * * * * * * . . . 
. . . * * * * * * * * * . * . . . 
. . . . * * . * * * * * . * * . . 
. . . . . . . . * * * * * * . . . 
. . . . . . . . . * * * * . . . . 
. . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . .