## Three Wise Men

### December 28, 2012

We have a simple Christmas puzzle today:

Three wise men named Caspar, Melchior and Balthazar went to Macy’s Department Store on 34th Street to buy gifts of gold, frankincense, and myrrh. When they took their gifts to the cashier, she multiplied the prices of the items and found a total price of $65.52, but the wise men noticed that she multiplied the numbers and asked her to compute the total price again, but this time using addition instead of multiplication. When she did, the cashier found that the total was exactly the same. What were the individual prices of the three gifts?

Your task is to solve the puzzle and find the three prices. 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.

## The Twelve Days Of Christmas

### December 25, 2012

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 determines how many gifts were given in N days, and use it to compute the number of gifts given in 12 days. 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.

## Building Primes

### December 21, 2012

It is sometimes possible, starting with a prime, to add a digit to the front of the number that forms a new prime. For instance, starting from prime 7, adding 1 forms prime 17, adding 3 forms prime 317, adding 6 forms prime 6317, adding 2 forms prime 26317, and so on.

Your task is to write a program to find the largest prime that can be formed in this way. 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.

## Petals Around The Rose

### December 18, 2012

Today’s exercise is our 400th, and our tradition on these anniversaries is to play a game. Today we choose *Petals Around The Rose*. Here’s a sample game:

`Let's play 'Petals Around The Rose.'`

The name of the game is significant.

At each turn I will roll five dice,

then ask you for the score, which

will always be zero or an even number.

After you guess the score, I will tell

you if you are right, or tell you the

correct score if you are wrong. The game

ends when you prove that you know the

secret by guessing the score correctly

six times in a row.

The five dice are: 4 2 5 5 4.

What is the score? 6

The correct score is 8.The five dice are: 2 5 1 3 3.

What is the score? 8

CorrectThe five dice are: 2 5 2 5 6.

What is the score? 8

CorrectThe five dice are: 6 2 5 3 2.

What is the score? 8

The correct score is 6.The five dice are: 4 2 1 1 2.

What is the score? 6

The correct score is 0.The five dice are: 5 6 3 6 6.

What is the score? 6

CorrectThe five dice are: 2 6 2 2 4.

What is the score? 6

The correct score is 0.The five dice are: 3 2 4 2 1.

What is the score? 0

The correct score is 2.The five dice are: 4 4 2 6 3.

What is the score? 2

CorrectThe five dice are: 2 1 5 1 5.

What is the score? 8

CorrectThe five dice are: 1 5 5 2 4.

What is the score? 8

CorrectThe five dice are: 5 2 4 6 3.

What is the score? 6

CorrectThe five dice are: 1 6 1 5 3.

What is the score? 6

CorrectThe five dice are: 1 4 3 2 6.

What is the score? 2

Correct

`Congratulations! You are now a member`

of the Fraternity of the Petals Around

The Rose. You must pledge never to

reveal the secret to anyone.

You can play *Petals Around The Rose* on the internet, or read about Bill Gates’ encounter with the game.

Your task is to figure out the secret, then write a program to play *Petals Around The Rose*. 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.

## 115132219018763992565095597973971522401

### December 14, 2012

Today we have an exercise, a solution, and a question I don’t know the answer to. The exercise is to write a program that lists the *narcissistic* numbers in which the sum of the *n*th powers of the digits of an *n*-digit number is equal to the number. For instance, 153 is a narcissistic number of length 3 because 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153. The largest decimal narcissistic number is the 39-digit number that is the title of today’s exercise.

Your task is to write a program to find narcissistic numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

## Stepwise Program Development: A Heuristic Algorithm

### December 11, 2012

I recently found a book by Niklaus Wirth in a used book store; it’s a fascinating book and has been the source of a few recent exercises:

Niklaus Wirth, Eidgenössische Technische Hochschule, Zürich, Switzerland.

Systematic Programming: An Introduction. 1973: Prentice-Hall, Inc. Englewood Cliffs, New Jersey. ISBN 0-13-880369-2.

Most of the book is concerned with teaching the syntax and semantics of Wirth’s language Pascal, but the final chapter is devoted to stepwise program development, where Wirth demonstrates by example four different problems which he solves by developing programs through a succession of stepwise refinements. The last section is a kind of “final exam” for readers; it’s the longest section of the book, by far, and gives a complete, detailed exposition of the solution to the following problem:

Generate a sequence of

Ncharacters, chosen from an alphabet of three elements (e.g., 1, 2, 3), such that no two immediately adjacent subsequences are equal.For instance, the sequence of length

N= 5 with the characters “12321” is acceptable, but neither “12323” nor “12123” are.

Your task is to write a program that not only solves the stated problem but also gives all possible solutions, not just a single solution, for any given *N*. 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.

## Wirth Problem 15.12

### December 7, 2012

In his 1973 book *Systematic Programming: An Introduction*, Niklaus Wirth gives the following problem as exercise 15.12:

Develop a program that generates in ascending order the least 100 numbers of the set M, where M is defined as follows:

a) The number 1 is in M.

b) If x is in M, then y = 2 * x + 1 and z = 3 * x + 1 are also in M.

c) No other numbers are in M.

Wirth also gives the first six numbers in the result sequence: 1, 3, 4, 7, 9, 10….

Your task is to write a program that finds the first *n* numbers in Wirth’s sequence, and use it to solve Wirth’s exercise. 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.

## Median Of Five

### December 4, 2012

In the previous exercise we computed the median of five items by sorting them and then taking the third item. Sorting does more work than is necessary; for instance, given the list [1, 2, 3, 5, 4], we don’t need to swap 5 and 4 into their correct positions to determine that 3 is the median as long as we know that both 4 and 5 are greater than 3..

Your task is to write a function that determines the median of five items using the fewest possible comparisons. 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.