### 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.

Pages: 1 2

### 7 Responses to “”

1. Rutger said

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'])

```
2. PowerShell said

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, 2
y, x, y))
return None

print(find_seq(1, 8))

3. mcmillhj said

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); # Nil
```
4. Daniel said

Here’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:

```\$ ./12467 1 8
(1,8)
(2,9)
(4,10)
(5,20)
(10,21)
(11,42)
(22,43)
(44,44)
```
5. Daniel said

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:

```\$ ./12467 1 8
(1,8)
(2,9)
(4,10)
(5,20)
(10,21)
(11,42)
(22,43)
(44,44)
```
6. Daniel said

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

```size_t index_tmp = index+1;
```
7. Kevin said

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)))))))
```