April 24, 2018
Today’s exercise is a game that mathematicians play; it comes from /u/HarryPotter5777 on Reddit:
You are given a pair of integers. You make a sequence of steps in which one member of the pair is doubled and the other is incremented by one. Your goal is to find a sequence in which the two members of the pair are equal. For instance, the sequence (1 8), (2 9), (4 10), (5 20), (10 21), (11 42), (22 43), (44 44) ends with the two numbers equal, so (1 8) is a valid starting pair.
The question is whether or not it is always possible to find a sequence, regardless of the starting pair, which makes the two numbers equal. /u/shouldertarget gives a hand-waving explanation that the answer is “Yes” later in the Reddit thread mentioned above.
Your task is to write a program that, given a starting pair, derives a sequence that makes the two numbers equal. 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.
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)))))))