### April 24, 2018

The problem can be solved by depth-first search through the graph of possible sequences. Here is our solution, which uses the queues of a previous exercise:

(define (f a b) (let loop ((q (enqueue (make-queue) (list (list a b))))) (let ((p (head q)) (q (tail q))) (cond ((= (caar p) (cadar p)) (reverse p)) (else (let ((t (enqueue q (cons (list (+ 1 (caar p)) (* 2 (cadar p))) p)))) (loop (enqueue t (cons (list (* 2 (caar p)) (+ 1 (cadar p))) p)))))))))

> (f 1 8) ((1 8) (2 9) (4 10) (5 20) (10 21) (11 42) (22 43) (44 44))

The problem, of course, is that the queue grows exponentially, and at each step must store the entire sequence, so the program can quickly run out of memory.

You can run the program at https://ideone.com/eHILhZ.

Advertisements

Pages: 1 2

Since this is a coding side, I wrote code rather than find a theoretic mathematical solution. So in Python a brute-force solution using generators. So far found solutions for all tuples up until (10,10). I recon with dynamic programming, this solution can be made very efficiently.

Example output:

—- 2 5 —-

(12, 12, [‘r’, ‘l’, ‘l’])

So (12,12) is found by applying:

– r: times 2 right (plus 1 left) = (3,10)

– l: times 2 left (plus 1 right) = (6,11)

– l: times 2 left (plus 1 right) = (12,12)

from collections import deque

def find_seq(x, y):

table = {}

dq = deque([(x, y, None, None)])

while dq:

x, y, px, py = dq.popleft()

table[(x, y)] = (px, py)

if x == y:

path = []

while x and y:

path.append((x, y))

x, y = table[(x, y)]

return path[::-1]

else:

table[(x, y)] = (px, py)

dq.append((2

x, y + 1, x, y))y, x, y))dq.append((x+1, 2

return None

print(find_seq(1, 8))

Perl6 solution that caches similar to PowerShell’s solution:

Here’s a solution in C++11.

Example Usage:

Here’s a solution in C.

Example:

Line 54 in my C code above should be replaced with the following code. Otherwise the first step is sometimes omitted from the output.

Here’s a solution in racket: