## Exercise 1-9

### January 17, 2017

Sometimes it’s good to go back to basics. Here is Exercise 1-9 from *The C Programming Language* by Brian W. Kernighan and Dennis M. Ritchie:

Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.

Your task is to write a solution to Exercise 1-9. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Words On A Telephone Keypad

### January 13, 2017

The digits on a telephone keypad are associated with letters; for instance, the digit 2 is associated with the letters A, B and C, and the digit 7 is associated with the letters P, Q, R and S. Thus, a word can be converted to its numeric equivalent; for instance, PRAXIS can be converted to the number 772947. The conversion is not necessarily unique, so ACT, BAT and CAT all convert to 228.

Your task is to write a program that takes a number, such as 228, and returns a list of all the words in a dictionary that are represented by that number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Prime String

### January 10, 2017

Today’s exercise is easy to describe, but has some tricky edge cases that make it hard to implement:

Given a string of the prime numbers appended sequentially — 2357111317192…. — and an index

n, return the string of five digits beginning at indexn. For instance, the five characters starting at indexn= 50 are 03107. The first 61 characters of the prime string are shown below:0 1 2 3 4 5 6 0123456789012345678901234567890123456789012345678901234567890 2357111317192329313741434753596167717379838997101103107109113

Your task is to write a program to find the substring of the string of all primes starting at the *n*th character. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Fibonacho Numbers

### January 6, 2017

Mathematicians are strange people:

Two people are sharing a plate of nachos. They take turns dividing the nachos, each taking the

nth Fibonacci number of nachos on thenth turn. When the number of nachos left is less than the next Fibonacci number, they start the sequence over. What number of nachos (less than 500) requires the most number of restarts?

For instance, if you start with *n* = 11 nachos, the first person takes 1 nacho (leaving 10), the second person takes 1 nacho (leaving 9), the first person takes 2 nachos (leaving 7), the second person takes 3 nachos (leaving 4), and the process restarts. Then the first person takes 1 nacho (leaving 3), the second person takes 1 nacho (leaving 2), and the first person takes 2 nachos (leaving none). There were two restarts, which we can notate as [1,1,2,3], [1,1,2].

The fibonacho numbers are those starting numbers *n* that require more restarts than any smaller number. Thus, the first fibonacho number is 1 from [1], the second fibonacho number is 3 from [1,1], [1], the third fibonacho number is 10 from [1,1,2,3], [1,1], [1], and so on.

Your task is to write programs that calculate the number of restarts for a given *n*, and the sequence of fibonacho numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Merry Christmas

### December 25, 2016

Merry Christmas to all my readers, and thank you for staying with me for another year.

Your task is to turn off your computer and spend a week with family and friends.

I’ll see you in 2017!

## A Partridge In A Pear Tree

### December 23, 2016

You all know the old song:

On the first day of Christmas my true love gave to me a partridge in a pear tree.

On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree.

On the third day of Christmas my true love gave to me three French hens, two turtle doves and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eighth day of Christmas my true love gave to me eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me twelve drummers drumming, eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

Your task is to write a program that prints the words of the song, as economically as possible. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Highly Abundant Numbers

### December 20, 2016

We studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly abundant numbers (A002093).

Highly abundant numbers are those numbers *n* such that `sigma`

(*m*) < `sigma`

(*n*) for all *m* < *n*, where *m* and *n* are positive integers and `sigma`

(*n*) is the sum of the divisors of *n*. For instance, 12 is a highly abundant number since the sum of its divisors is 1 + 2 + 3 + 4 + 6 + 12 = 28, and no number less than 12 has a greater sum of divisors.

Your task is to compute the sequence of highly abundant numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## SQL Insert Syntax

### December 16, 2016

When I’m not writing exercises for Programming Praxis, my day job has me writing SQL and PL/SQL code for a large Oracle database. One task I frequently perform is inserting records into a table, using the following syntax:

insert into tablename ( field_1, field_2, field_3, ...) values ( value_1, value_2, value_3, ...)

Here, `tablename`

is replaced by the name of the database table into which records are being inserted, each `field`

is the name of a field in the table, and each `value`

is the value to be inserted. The correspondence between field name and value is positional.

I can’t tell you how many times over the years I wrote that wrong. When I inadvertently skip a field, an error message politely tells me of my mistake. But when I transpose two fields, both of the same type, there is no error message, and I happily go on my way with bad data in the database.

I finally decided to do something about the situation; I wrote a program that converts the syntax shown below, which makes it easy to see the correspondence between fields and values, to the Oracle syntax shown above:

insert into tablename ( field_1 => value_1, field_2 => value_2, field_3 => value_3, ...)

That’s much better: Easy to get right, much harder to get wrong. A significant payback on a few minutes of effort. Why didn’t I do this years ago!?

Your task is to find something annoying in your programming environment, and fix it; you can borrow my annoyance in the unlikely event you have none of your own. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## List Swap

### December 13, 2016

We have today an exercise for students who work with linked lists:

Given a linked list and an integer

k, swap the two list items that are at distancekfrom the beginning of the list and distancekfrom the end of the list. Be sure to consider the case where thekcross, so that the itemkfrom the beginning of the list isafterthe itemkfrom the end of the list. For instance, given the list (1 2 3 4 5 6 7) andk= 2, you should return the list (1 6 3 4 5 2 7), and likewise ifk= 6. The solution must run in O(n) time, wherenis the length of the list.

Your task is to write the list-swapping code described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Searching An Infinite Array

### December 9, 2016

Given an array of positive integers in ascending order, of infinite size, find the index of an integer *k* in the array, or determine that it does not exist. Your solution must work in time logarithmic in the index of the requested integer.

Your task is to write a program that finds the requested integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.