The 147 Puzzle

2013-02-06

Yesterday saw another puzzle from Programming Praxis, this one entitled The 147 Puzzle. The description is relatively straight forward. Find a set of k fractions each with numerator 1 such that the sum is equal to one.

For example, 1/5 + 1/5 + 1/5 + 1/5 + 1/5 = 1 is a trivial solution for k = 5. It turns out that there are 147 solutions when k = 5, thus the name of the puzzle.

There’s actually not much lead up to the solution. The code is actually pretty straight forward, although the recursive step is a bit more complicated. We’ll just start with code though:

#lang racket

; find sum(1/xi, i = 1 .. k) = 1
; for example, with k = 5:
; 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 1
(define (147-puzzle k)
  (let loop ([depth k]       ; the number of fractions left to add
             [lower-bound 2] ; the lower bound on new demoninator
             [target 1]      ; the remaining target to add up to
             [so-far '()])   ; the fractions so far
    (cond
      ; one more fraction and what's left has numerator 1, so valid
      [(and (= depth 1) (= 1 (numerator target)))
       (list (cons target so-far))]
      ; one more but not a valid last fraction
      [(= depth 1)
       '()]
      ; otherwise, recur
      ; range is bounded by the lower bound and the current fraction
      ; nested for*/list automatically appends into a larger list
      [else
       (for*/list ([i (in-range (max lower-bound (+ 1 (floor (/ 1 target))))
                                (+ 1 (floor (* depth (/ 1 target)))))]
                   [res (loop (- depth 1) 
                              i 
                              (- target (/ 1 i)) 
                              (cons (/ 1 i) so-far))])
         res)])))

Hopefully, the comments do a pretty good job of explaining where I was coming from. Credit where credit is due, I used Paul’s solution in the Programming Praxis’ post’s comments to fix my own version. I had a rougher version almost working, but the bounds checking in this version works far better.

Basically, use recursion. Rather than solve the k = 5 problem, instead solve the k = 4 problem with a target other than one. Then add the number you would need to bump that up to k = 5 with a target of one.

Here’s a sample run:

> (147-puzzle 4)
'((1/42 1/7 1/3 1/2) (1/24 1/8 1/3 1/2) (1/18 1/9 1/3 1/2) (1/15 1/10 1/3 1/2)
  (1/12 1/12 1/3 1/2) (1/20 1/5 1/4 1/2) (1/12 1/6 1/4 1/2) (1/8 1/8 1/4 1/2)
  (1/10 1/5 1/5 1/2) (1/6 1/6 1/6 1/2) (1/12 1/4 1/3 1/3) (1/6 1/6 1/3 1/3)
  (1/6 1/4 1/4 1/3) (1/4 1/4 1/4 1/4))

I like how Racket handles fractions. It’s nice and clean, particularly for problems like this.

And that’s it.

Short and sweet today, but that’s really all there is to the problem. Also I’m a bit otherwise occupied at the moment; I’ll have a post up later today or tomorrow morning with why.