Problem 024: Lexicographic Permutations

From Project Euler:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This one can be done by brute force on a modern computer, but that would be way too slow. We can use a little deduction here to reduce the amount of computation we need. We know that there are 10! possible permutations of the digits 0 through 9, or 3 628 800 values. If we fix the first digit, we know that there are 9! or 362 880 numbers starting with that digit. Since the numbers are in numerical order, we konw that the first 362 880 start with 0, the next 362 880 start with 1, etc. Therefore the first permutation that starts with 1 is the 362 881st number, the first that starts with 2 is the 725 761st number (2 times 362 880, plus one), and the first that starts with 3 is the 1 008 641st number. Since this is greater than a million, we know that the first digit must be 2. Once we've found the first digit, we know that all the digits starting with 2 begin at position 725 761. If we subtract that from a million we get 274 239, which is the number of positions from the current one we want to get to. Here we can repeat the same logic as before: there are 8! (or 40 320) possible permutations starting with 20, and another 8! starting with 21, etc. Dividing 8! into 274 239 we get 6 plus some change. This does not mean that 6 is the next digit, but rather the 6th element of our remaining available digits is the next one. Since we've removed 2, the 6th element is 7. So we have 27 as the first two digits of the millionth permutation. We can now repeat the logic again: We subtract 6 times 8! from 274 239 to get 32 319. Fixing the first digit we have 7! (or 5040) remaining possible numbers, we do the quotient and get the index, and loop through. To write this out:

# use zero-based indexing:
999 999 = 2 * 9! + 274 239
# Available digits are (0 1 2 3 4 5 6 7 8 9), index 2 is 2
274 239 = 6 * 8! + 32 319
# Available digits are (0 1 3 4 5 6 7 8 9), index 6 is 7
 32 319 = 6 * 7! + 2079
# Available digits are (0 1 3 4 5 6 8 9), index 6 is 8
   2079 = 2 * 6! + 639
# Available digits are (0 1 3 4 5 6 9), index 2 is 3
...

Here's the code to do this:

(defn nth-lex-permutation
  "Gets the nth permutation from the set of digits up to max."
  [n max]
  (loop [available-numbers (range max)
         ; Keep track of the digits we've used so far as a number.
         digits-so-far 0
         ; Keep track of where we are within the current range of
         ; permutations.
         index-from-offset (- n 1)
         ; Track how many permutations there are when we fix one digit.
         num-permutations (factorial (- max 1))
         ; Track the factorial we're multiplying by.
         current-f (- max 1)]
    (if
     (empty? available-numbers) digits-so-far
     ; index-from-offset = idx * num-permutations + next-offset
     ; idx is the index of the next digit within available-numbers.
     (let [idx (quot index-from-offset num-permutations)
           value (nth available-numbers idx)
           remaining-numbers (remove #(= % value) available-numbers)
           next-digits (+ (* 10 digits-so-far) value)
           next-offset (rem index-from-offset num-permutations)
           next-num-permutations
           (if (zero? current-f)
             0
             (/ num-permutations current-f))]
       (recur remaining-numbers
              next-digits
              next-offset
              next-num-permutations
              (- current-f 1))))))

This runs very fast:

$ lein run
Processing...
Value is: 2783915460
"Elapsed time: 2.049982 msecs"

Problem 018: Maximum Path Sum I

From Project Euler:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

We could brute force this one or even solve it by hand, but since Problem 67 is much more complex we might as well solve this one now. An easy dynamic programming solution is just to start from the bottom and work our way up. Starting from the second-to-last row, for each index $i$ determine whether a left or a right is best by taking the max of the values in spots $i$ and $i + 1$ in the next row, and adding that to our current element.

The code is pretty straight-forward:

(defn collapse [row1 row2]
    (assert (== (+ 1 (count row1)) (count row2)))
    (->> (range (count row1))
         (map #(+ (nth row1 %)
                  (max (nth row2 %)
                       (nth row2 (+ % 1)))))))

(defn solve [rows]
  (assert (> (count rows) 0))
  (loop [current-row (- (count rows) 2)
         _rows rows]
    (if (== current-row -1)
      (first (first _rows))
      (recur (- current-row 1)
             (assoc _rows
                    current-row
                    (collapse (nth _rows current-row)
                              (nth _rows (+ current-row 1))))))))

And it runs really fast:

rob@alien ~/code/euler/clj-euler $ lein run
Processing...
1074
"Elapsed time: 4.771813 msecs"

Problem 015: Lattice paths

From Project Euler:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

There is a very fast solution for this problem using combinatorics. It's a very interesting approach, but since I didn't think of it and swiped it from somewhere else, I'll leave it as an exercise to you to figure that one out.

What I did was approach this as a dynamic programming problem. For each point in the lattice, the only ways to get there are from the left or from the top. An edge case (pun intended) is along the left and top edges, for every point there is only one possible way to get there. So for each point the number of paths $P(x, y)$ is:
$$
P(x, y) = \left\{
\begin{array}{ll}
1 & x = 0\ or\ y = 0 \\
P(x - 1, y) + P(x, y - 1) & otherwise
\end{array}
\right.
$$
At first glance this might look like a recursive solution, however that will be very inefficient since we'll end up calculating several values many times. Instead, we'll use a dynamic programming approach to build up a grid of values, starting from one edge and working our way across. Once we've filled the grid, we return the value in the bottom right corner.

(defn count-routes [width height]
  (loop [x 0
         y 0
         grid {}]
    (if (and (== x 0) (== y height))
      (grid [(- width 1) (- height 1)])
      (recur (mod (+ x 1) width)
             (if (== x (- width 1))
               (+ y 1)
               y)
             (assoc grid
                    [x y]
                    (+ (if (> x 0) (grid [(- x 1) y]) 1)
                       (if (> y 0) (grid [x (- y 1)]) 1)))))))

This runs super fast:

$ lein run
Processing...
137846528820
"Elapsed time: 7.410219 msecs"

Problem 004: Largest Palindrome Product

From Project Euler:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

For this one we'll need to define a few helpers. First, we need a function that determines if a number is palindromic. In order to do that, we'll need to create a function to reverse a number. We could do this easily by converting the number to a string, reversing it, and then converting it back to a number (to avoid issues with leading zeroes) but that's cheating and we can just do it with integer math. Each iteration we have an accumulated number, we just take modulo 10 of our current number and add it to 10 times our accumulator, and then divide our number by 10 to chop off that digit:

(defn reverse-num [n]
  (letfn [(helper [i reversed]
            (if (== i 0)
              reversed
              (helper (quot i 10)
                      (+ (mod i 10)
                         (* 10 reversed)))))]
    (helper n 0)))

We can then use that to define is-palindromic?:

(defn is-palindromic? [n] (== n (reverse-num n)))

Once we have those, we can (mostly) brute force things to get the correct result. We can use a for comprehension to get all the numbers that are products of two 3-digit numbers. We'll do one optimization which is where the second variable y only ranges from the first variable x to 999, since multiplication is commutative and once we've checked 101 * 500 we don't need to check 500 * 101.

(def N 1000)

(println (->> (for [x (range 100 N)
                    y (range x N)]
                (* x y))
              (filter is-palindromic?)
              (apply max)))

There are several other optimizations we can do, if you're interested you can look in the forums for all sorts of creative solutions. However, this code gives the result in a reasonable amount of time (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 4.clj 
906609

real 0m1.747s
user 0m3.478s
sys 0m0.176s