## Triangle Roll-Up

### September 23, 2014

We have a simple little exercise today: Given a list, write a triangle showing successive sets of sums of the pair-wise elements of the list. For instance, given the input 4, 7, 3, 6, 7, your program should write this output:

81

40 41

21 19 22

11 10 9 13

4 7 3 6 7

The original list is at the bottom of the triangle. The next row up has pair-wise sums of the elements of the list: 4 + 7 = 11, 7 + 3 = 10, 3 + 6 = 9, and 6 + 7 = 13. The next row up has pair-wise sums of those list elements: 11 + 10 = 21, 10 + 9 = 19, and 9 + 13 = 22. The next-to-top row has only two sums: 21 + 19 = 40 and 19 + 22 = 41. And finally the top row is the sum of those two numbers: 40 + 41 = 81.

Your task is to write a program to print the triangle roll-up of an input list. 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.

## Diophantine Reciprocals

### September 19, 2014

Career Cup claims that Amazon asked this as an interview question; it is also Problem 108 at Project Euler:

In the following equation

x,yandnare positive integers: 1 /x+ 1y= 1 /n. Forn= 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8 = 1/4. What is the least value ofnfor which the number of distinct solutions exceeds one thousand?

Your task is to solve Amazon’s question; you might also like to make a list of the *x*, *y* pairs that sum to a 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.

## Torn Numbers

### September 16, 2014

In 1917, Henry Ernest Dudeney published a book *Amusements in Mathematics* of arithmetic puzzles. Today’s exercise solves puzzle 113 from that book:

A number

nis a torn number if it can be chopped into two parts which, when added together and squared, are equal to the original number. For instance, 88209 is a torn number because (88 + 209)^{2}= 297^{2}= 88209.

Your task is to write a program to find torn 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.

## Levenshtein Distance

### September 12, 2014

In a previous exercise we computed the edit distance between two strings where the allowable operations were insert or delete characters; we made the calculation by determining the longest common subsequence. A different definition of edit distance allows substitutions as well as insertions and deletions, and is called the Levenshtein distance, since it was studied by Vladimir Levenshtein in 1965. For example, the edit distance between “hill” and “hilt” is 2 (delete the “l” and insert the “t”) but the Levenshtein distance is 1 (replace “l” by “t”).

The basic algorithm is recursive: if either string is empty, the Levenshtein distance is the length of the other string, otherwise it is the minimum of the Levenshtein distance computed by deleting the first character from the first string, by deleting the first character from the second string, or by deleting the first characters of each of the two strings (adding 1 if the two characters differ), plus the Levenshtein distance of the remaining substrings. That computation takes exponential time as it recomputes the same substring Levenshtein distances many times. A better algorithm uses dynamic programming to build up the substring distances, so they are always available as they are needed.

Your task is to write two functions to compute the Levenshtein distance between two strings. 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.

## Drawing Diamonds

### September 9, 2014

Given a small positive integer *n*, write a function that draws a diamond, either filled or in outline as specified by the user. For instance, here are filled and outline diamonds for *n* = 5:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Note that there is a single space between asterisks in the filled version of the diamond.

Your task is to write a program that draws diamonds as 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.

## Skyline Puzzle

### September 5, 2014

The Skyline Puzzle is a classic programming exercise; it draws a silhouette of a city skyline by blocking out portions of buildings that are masked by taller buildings. A city is a list of buildings specified as triples containing left edge, height, and right edge. For instance, the list of triples `(1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28)`

encodes the eight buildings shown at the left of the diagram, and the path `1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0`

encodes the skyline shown at the right of the diagram, where the odd-indexed elements of the output are the x-coordinate of the skyline and the even-indexed elements of the output are the y-coordinate of the skyline. (It makes more sense to me that the output should look like `(1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0)`

but that’s not the way the puzzle is ever specified.) Notice that the second (2 6 7) and eighth (24 4 28) buildings are not part of the skyline.

Your task is to write a program that takes a list of buildings and returns a skyline. 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.

## Longest Increasing Subsequence

### September 2, 2014

A sequence is a list of integers (or any other ordered type, but we’ll use integers to keep things simple). A subsequence is any, possibly non-consecutive, list drawn from the parent sequence with items in the same order as the parent sequence. An increasing subsequence is a subsequence with all the items in increasing order. A longest increasing subsequence (there may be more than one with the same length) is an increasing subsequence of a parent sequence of the greatest possible length. For instance, the sequence (3 2 6 4 5 1) has longest increasing subsequences (2 4 5) and (3 4 5).

The algorithm to find the longest increasing subsequence is similar to the algorithm for patience sorting of a previous exercise, with a small modification. When dealing the cards, each time a card is placed on a pile, a back-pointer to the top card on the previous pile is placed along with the card. Then, when all the cards are dealt, the number of piles is the length of the longest increasing subsequence, and the longest increasing subsequence can be recovered by taking the top card from the last pile and following the back-pointers to previous piles.

For instance, with sequence (3 2 6 4 5 1) the cards are dealt with 3 and 2 on the first pile, 6 and 4 on the second pile, 5 on the third pile, and 1 on the first pile, so the longest increasing subsequence has length 3. The 5 on the third pile ends the longest increasing subsequence, it points to the 4 which was on the top of the second pile when 5 was added to the third pile, and 4 points to the 2 which was on the top of the first pile when 4 was added to the second pile; even though 1 was later added to the first pile, is wasn’t yet on the pile when 4 was added to the second pile, so it’s not part of the longest increasing subsequence.

Your task is to write a program to find the longest increasing subsequence of a sequence. 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.

## Generating Palindromes

### August 29, 2014

The first hundred palindromic numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, and 909.

Your task is to write a program that generates the palindromic numbers in order; use it to find the ten-thousandth palindromic 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.

## Integer Logarithm

### August 26, 2014

The integer logarithm function in the Standard Prelude looks like this:

`(define (ilog b n)`

(let loop1 ((lo 0) (b^lo 1) (hi 1) (b^hi b))

(if (< b^hi n) (loop1 hi b^hi (* hi 2) (* b^hi b^hi))

(let loop2 ((lo lo) (b^lo b^lo) (hi hi) (b^hi b^hi))

(if (<= (- hi lo) 1) (if (= b^hi n) hi lo)

(let* ((mid (quotient (+ lo hi) 2))

(b^mid (* b^lo (expt b (- mid lo)))))

(cond ((< n b^mid) (loop2 lo b^lo mid b^mid))

((< b^mid n) (loop2 mid b^mid hi b^hi))

(else mid))))))))

It performs binary search in `loop1`

until *n* is bracketed between *b^lo* and *b^hi*, doubling at each step, then refines the binayr search in `loop2`

, halving the bracket at each step.

Inspired by that function, Joe Marshall posed this puzzle at his *Abstract Heresies* web site:

You can get the most significant digit (the leftmost) of a number pretty quickly this way:

`(define (leftmost-digit base n)`

(if (< n base)

n

(let ((leftmost-pair (leftmost-digit (* base base) n)))

(if (< leftmost-pair base)

leftmost-pair

(quotient leftmost-pair base)))))The puzzle is to adapt this code to return the position of the leftmost digit.

Your task is to write Joe’s puzzle function; you might also click through to his website to spike his stats. 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.

## Patience Sorting

### August 22, 2014

This sorting algorithm derives its name from the game of Patience (that’s the British name, we call it Solitaire in the United States) because it is implemented by analogy to sorting a shuffled deck of cards:

Starting with no piles, add the next card from the deck to the first pile with top card greater than the next card from the deck. If the next card from the deck is greater than the top card of all the piles, start a new pile. When the deck is exhausted, collect the cards in order by selecting the smallest visible card at each step.

For instance, consider sorting the list (4 3 9 1 5 2 7 8 6). The first stack gets 4 and 3. Since 9 is larger than 3, it starts a second stack, 1 goes on the first stack, then 5 and 2 go on the second stack. At this point the first stack (top to bottom) consists of (1 3 4), the second stack consists of (2 5 9), and the remaining deck consists of (7 8 6). Now 7 goes on a third stack, 8 goes on a fourth stack, and 6 goes on top of the 7 in the third stack. With all the cards dealt, 1 is collected from the first stack, 2 from the second stack, 3 and 4 from the first stack, 5 from the second stack, 6 and 7 from the third stack, 8 from the fourth stack, and 9 from the second stack. The algorithm has complexity O(*n* log *n*).

Your task is to implement the patience sorting algorithm. 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.