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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

Cracker Barrel

August 19, 2014

While I was out of town last week, I ate dinner one evening at Cracker Barrel, which provides a triangle puzzle at each table so you can amuse yourself while you are waiting for your food. When my daughter challenged me to solve the problem, I failed, but I promised her that I would write a program to solve it.

As shown in the picture at right, the puzzle is a triangle with 15 holes and 14 pegs; one hole is initially vacant. The game is played by making 13 jumps; each jump removes one peg from the triangle, so at the end of 13 jumps there is one peg remaining. A jump takes a peg from a starting hole, over an occupied hole, to an empty finishing hole, removing the intermediate peg.

Your task is to write a program that solves the Cracker Barrel puzzle; find all possible solutions that start with a corner hole vacant and end with the remaining peg in the original vacant corner. 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.

Pages: 1 2

Today’s exercise is a frequent source of questions at places like Stack Overflow and /r/learnprogramming; it must come from one of the competitive programming sites like SPOJ or UVA. The most common statement of the problem is something like this:

You are given two positive integers P and Q, either of which can be quite large, up to a million digits. Compute PQ, that is, P raised to the Q power. For your convenience, give the result modulo 109 + 7. For instance, with P = 34534985349875439875439875349875 and Q = 93475349759384754395743975349573495, the expected result is 735851262.

The phrase “for your convenience” is a giveaway that the modulo computation is a trick; that kind of contest site never does anything for your convenience. In fact, due to a corollary of Fermat’s little theorem, PQ (mod m) ≡ pq (mod m) where p = P (mod m) and q = Q (mod m − 1). That makes it easy. Compute p and q. Both will be less than 232, so we can use the Montgomery multiplication algorithm of a previous exercise to make the computation.

Your task is to write a program to perform the big modular exponentiations 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.

Pages: 1 2

Minimal Palindromic Base

August 5, 2014

We have a simple little problem today: Given an integer n > 2, find the minimum b > 1 for which n base b is a palindrome. For instance, n = 15 = 11112 = 1203 = 334 = 305 = 236 = 217 = 178 = 169 = 1510 = 1411 = 1312 = 1213 = 1114; of those, bases 2, 4 and 14 form palindromes, and the least of those is 2, so the correct answer is 2.

Your task is to write a program that calculates the smallest base for which a number n is a palindrome. 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.

Pages: 1 2

K’th Largest Item

August 1, 2014

Today’s exercise is a common interview question, and also interesting in its own right:

Find the kth largest integer in a file of n integers, where n is large (defined as too large to fit into memory all at once) and k is small (defined as small enough to all fit in memory).

Your task is to write the program 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.

Pages: 1 2

[ Does anybody know the proper method for writing a-bar and b-bar in plain HTML? The LaTeX symbols are \={a} and \={b}, but WordPress renders LaTeX poorly, and I prefer plain HTML. FIXED! Thanks to Jussi, who suggests writing a amp hash x304 semicolon and b amp hash x304 semicolon. ]

Montgomery multiplication is a method of computing ab mod m for positive integers a, b and m, designed for situations where there are many multiplications to be performed mod m with a small number of multipliers; in particular, it is valuable for computing xy mod m for large y. Montgomery multiplication was invented by Peter Montgomery in a 1985 article. Our exercise today will implement modular multiplication and exponentiation using Montgomery’s method.

The basic idea of Montgomery multiplication is to eliminate the division inherent in the modulo operation by translating the modulus m to a larger modulus r, with gcd(r, m) = 1, where r is a power of 2; thus, the division is rendered as a bit mask. Since r is a power of 2, the modulus m must be odd to satisfy the gcd requirement; we also require the two multipliers a and b be less than m. Then the Montgomery algorithm is as follows:

  1. Find two integers r−1 and m′ such that r r−1 m m′ = 1 by the extended Euclidean algorithm. In particular, the algorithm used is a binary version of the algorithm that performs no divisions.
  2. Translate the multipliers to “Montgomery space” by multiplying them by r (using left shifts) and reducing the product modulo m. Thus, ā = a r mod m and b̄ = b r mod m. These operations are expensive, but they are performed only once for each multiplier in a chain of multiplications.
  3. Perform the Montgomery multiplication: calculate u = a b r mod m by the sequence of operations

    t = ā * b̄
    u = (t + (t * m′ mod r) * m) / r
    if (um) then subtract m from u

    The only division is a right-shift; the final result uses subtraction instead of division because it is known that the product is less than 2m.

  4. Translate the result back from Montgomery space to an ordinary integer by ab = u r−1 mod m.

Montgomery exponentiation is similar. To compute xy mod m, select r, compute r−1 and m′, translate x to Montgomery space, use the square-and-multiply method with Montgomery multiplications to perform the exponentiation starting from 1 in Montgomery space, then translate the result back from Montgomery space. This is much faster than the calculation without Montgomery multiplication, because the cost of initializing the Montgomery space is amortized over several multiplications, each of which avoids the inherent division of the modulo operator.

Your task is to write functions that perform Montgomery multiplication and exponentiation. 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.

Pages: 1 2

Number Words

July 25, 2014

Today’s exercise is an interview question from Career Cup. When I first saw the exercise, I thought it would be easy, but I had trouble writing a solution, so maybe it will a good exercise for all you readers, as well:

Given a positive integer, return all the ways that the integer can be represented by letters using the mapping 1 -> A, 2 -> B, …, 26 -> Z. For instance, the number 1234 can be represented by the words ABCD, AWD and LCD.

Your task is to write the program to generate words from 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.

Pages: 1 2

Follow

Get every new post delivered to your Inbox.

Join 612 other followers