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.
Programming Praxis 
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)
def apply_times_left(tup): return (tup[0]*2, tup[1]+1, tup[2] + ['l']) def apply_times_right(tup): return (tup[0]+1, tup[1]*2, tup[2] + ['r']) def find_recursively(tup, depth): if tup[0] == tup[1]: yield tup else: if depth: yield from find_recursively(apply_times_left(tup), depth-1) yield from find_recursively(apply_times_right(tup), depth-1) max_depth = 20 for i in range(1,10): for j in range(1,10): print('-'*4, i,j, '-'*4) tup = (i,j,[]) best_solution = (1000000000000, 1000000000000) for solution in find_recursively(tup, max_depth): if (solution[0] + solution[1]) < (best_solution[0] + best_solution[1]): best_solution = solution print(best_solution) #outputs # ---- 1 1 ---- # (1, 1, []) # ---- 1 2 ---- # (4, 4, ['l', 'l']) # ---- 1 3 ---- # (8, 8, ['r', 'l', 'l']) # ---- 1 4 ---- # (12, 12, ['l', 'r', 'l', 'l']) # ---- 1 5 ---- # (8, 8, ['l', 'l', 'l']) # ---- 1 6 ---- # (108, 108, ['r', 'r', 'l', 'l', 'r', 'l', 'r', 'l', 'l'])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((2x, y + 1, x, y))
dq.append((x+1, 2y, x, y))
return None
print(find_seq(1, 8))
Perl6 solution that caches similar to PowerShell’s solution:
#!perl6 sub search(Int $x, Int $y, Int $max-depth is copy = 25000) { state %cache{Set}; my @queue = (($x, $y, Nil, Nil),); while @queue and --$max-depth > 0 { my ($x, $y, $px, $py) = @queue.shift(); %cache{Set($x, $y)} = [$px, $py]; if $x == $y { my @path; while $x and $y { @path.push: [$x, $y]; ($x, $y) = %cache{Set($x, $y)}; } return reverse @path; } else { @queue.push: (2 * $x, $y + 1, $x, $y); @queue.push: ($x + 1, 2 * $y, $x, $y); } } return Nil; } say search(1, 8); # ([1 8] [2 9] [4 10] [5 20] [10 21] [11 42] [22 43] [44 44]) say search(5, 49); # ([5 49] [6 98] [12 99] [24 100] [25 200] [50 201] [100 202] [101 404] [202 405] [203 810] [406 811] [812 812]) say search(1, 99); # ([1 99] [2 100] [3 200] [6 201] [12 202] [24 203] [25 406] [50 407] [51 814] [102 815] [204 816] [408 817] [409 1634] [818 1635] [1636 1636]) say search(1, 999); # NilHere’s a solution in C++11.
#include <algorithm> #include <cstdlib> #include <iostream> #include <list> #include <queue> #include <string> #include <utility> #include <vector> using namespace std; struct node { pair<int,int> value; node* parent; }; void search(const pair<int,int> start, vector<pair<int,int>>* result) { queue<node*> frontier; list<node> nodes; nodes.push_back({start, nullptr}); frontier.push(&nodes.back()); node* n; while (!frontier.empty()) { n = frontier.front(); frontier.pop(); int first = n->value.first; int second = n->value.second; if (first == second) break; pair<int,int> left = {first * 2, second + 1}; nodes.push_back({left, n}); frontier.push(&nodes.back()); pair<int,int> right = {first + 1, second * 2}; nodes.push_back({right, n}); frontier.push(&nodes.back()); } while (true) { result->push_back(n->value); if (n->parent == nullptr) break; n = n->parent; } reverse(result->begin(), result->end()); } int main(int argc, char* argv[]) { if (argc != 3) { cerr << "Usage: 12467 <INT> <INT>" << endl; return EXIT_FAILURE; } pair<int,int> start(stoi(argv[1]), stoi(argv[2])); vector<pair<int,int>> result; search(start, &result); for (pair<int,int> x : result) { cout << "(" << x.first << "," << x.second << ")" << endl; } return EXIT_SUCCESS; }Example Usage:
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> typedef struct { int first; int second; } pair_t; typedef struct { pair_t* sequence; size_t steps; } result_t; void init_result(result_t* result) { result->sequence = NULL; result->steps = 0; } void free_result(result_t* result) { free(result->sequence); } void search(const pair_t start, result_t* result) { size_t index = 0; size_t n = 1; pair_t* tree = malloc(n * sizeof(pair_t)); while (1) { if (index >= n) { n *= 2; tree = realloc(tree, n * sizeof(pair_t)); } int first; int second; if (index == 0) { first = start.first; second = start.second; } else { size_t parent_index = (index - 1) / 2; int parent_first = tree[parent_index].first; int parent_second = tree[parent_index].second; if (index % 2 == 0) { first = parent_first + 1; second = parent_second * 2; } else { first = parent_first * 2; second = parent_second + 1; } } tree[index] = (pair_t){first, second}; if (first == second) break; ++index; } size_t steps = 1; size_t index_tmp = index; while (index_tmp >>= 1) steps += 1; result->steps = steps; result->sequence = malloc(steps * sizeof(pair_t)); for (size_t i = 0; i < steps; ++i) { result->sequence[steps - i - 1] = tree[index]; index = (index - 1) / 2; } free(tree); } int main(int argc, char* argv[]) { if (argc != 3) { fprintf(stderr, "Usage: %s <INT> <INT>\n", argv[0]); return EXIT_FAILURE; } result_t result; init_result(&result); pair_t start = {atoi(argv[1]), atoi(argv[2])}; search(start, &result); for (size_t i = 0; i < result.steps; ++i) { int first = result.sequence[i].first; int second = result.sequence[i].second; printf("(%d,%d)\n", first, second); } free_result(&result); return EXIT_SUCCESS; }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:
(define (val-seq X Y) (let step ((seed 0) (ref 0) (x X) (y Y) (diff 0) (trend 0) (seq '())) (let ((pattern (string->list (number->string seed 2)))) (cond ((= x y) (cons (list X Y) (reverse seq))) ((or (> trend 10) (>= ref (length pattern))) (step (add1 seed) 0 X Y 0 0 '())) (else (let* ((pattern-0? (equal? (list-ref pattern ref) #\0)) (new-x (if pattern-0? (* 2 x) (add1 x))) (new-y (if pattern-0? (add1 y) (* 2 y))) (new-diff (abs (- new-x new-y))) (new-trend (if (> new-diff diff) (add1 trend) 0)) (new-seq (cons (list new-x new-y) seq))) (step seed (add1 ref) new-x new-y new-diff new-trend new-seq)))))))