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

6 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;
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: