Daily Challenge #199 - List of All Rationals

Implement a function that will construct a list containing every positive rational number:

Build a binary tree where each node is a rational and the root is 1/1, with the following rules for creating the nodes below:

The value of the left-hand node below a/b is a/a+b
The value of the right-hand node below a/b is a+b/b
So the tree will look like this:

                       1/1
                  /           \ 
            1/2                  2/1
           /    \              /     \
       1/3        3/2        2/3       3/1
      /   \      /   \      /   \     /   \
   1/4    4/3  3/5   5/2  2/5   5/3  3/4   4/1

Now traverse the tree, breadth first, to get a list of rationals.

[ 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, .. ]
Every positive rational will occur, in its reduced form, exactly once in the list, at a finite index.

We will use tuples of type [ Number, Number ] to represent rationals, where [a,b] represents a / b

Use this method to create an infinite list of tuples:
function* allRationals() => [Number,Number] // forever
matching the list described above:

allRationals => [ [1,1], [1,2], [2,1], [1,3], [3,2], .. ]

Tests

a = { 0: [1,1], 3: [1,3], 4: [3,2], 10: [5,2] }

a = { 100: [19,12], 1000: [39,28], 10000: [205,162], 100000: [713,586] }

---

This challenge comes from Paul Robertson on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Avalander]

Scala

This was really fun. I want to refine the algorithm to not need to carry each generated level and keep track of where I am, but I didn't have time to fix it right now.

case class Rational(n: Int, d: Int) {
  override def toString (): String = s"$n/$d"
}

def nextLevel (s: LazyList[Rational]): LazyList[Rational] =
  s flatMap {
    case Rational(n, d) => LazyList(
      Rational(n, n + d),
      Rational(n + d, d)
    )
  }

def rationals (from: LazyList[Rational] = LazyList(Rational(1, 1)), pos: Int = 0): LazyList[Rational] = {
  if (pos >= from.size) rationals (nextLevel(from))
  else from(pos) #:: rationals (from, pos + 1)
}

[Empereol]

TypeScript

function* allRationals(): Generator<[number, number]> {
  let rationals: [number, number][] = [[1, 1]];

  let i = 0;
  while (true) {
    const rational = rationals[i];
    yield rational;
    rationals.push([rational[0], rational[0] + rational[1]]);
    rationals.push([rational[0] + rational[1], rational[1]]);
    i++;
  }
}

Edit: Removed rationals.shift() in favor of keeping track of the rationals[i]... It's much faster since it doesn't have to move tons of array items when accessing higher values like the 100000th value... Went from ~28000ms to ~180ms.

[Matt Ellen-Tsivintzeli]

Plain javascript. Slow but correct:

module.exports =
{
    allRationals: function* allRationals()
    {
        yield [1,1];
        let current = [1,1];
        let nexts = nextRationals(...current);
        while(true)
        {
            current = nexts.pop();
            yield current;
            let nnexts = nextRationals(...current);
            nexts = nnexts.concat(nexts);
        }

    },

    getRational: function(n)
    {
        let r = [1,1];
        let a = this.allRationals();
        while(n >= 0)
        {
            r = a.next();
            n--;
        }
        return r;
    }

};

function nextRationals(a, b)
{
    return [[b+a, b], [a, a+b]];
}

[Matt Ellen-Tsivintzeli]

My main issue with this solution is that it will eventually run out of space (for every rational I yield, I add two more to the list). I think it must be possible to write a solution that doesn't maintain a list of rationals.

[Vidit Sarkar]

C++

// returns the pos-th element in the allRationals list as a pair
// like allRationals(0) = [1,1], allRationals(10) = [5,2]
pair<int, int> allRationals(int pos){
    queue<pair<int,int>> rationals; // for storing like BFS
    rationals.push(make_pair(1,1)); // push the first pair
    int index = 0; // index of element in BFS array

    while(true){
        pair<int, int> p = rationals.front();
        if(index++ == pos)
            return p;
        rationals.pop();
        rationals.push(make_pair(p.first, p.first+p.second)); // push the left child [a,a+b]
        rationals.push(make_pair(p.first+p.second,p.second)); // push the right child [a+b,b]
    }
}

// if the rationals-list is required upto index pos, then this function can be used
// same as allRationals, but we are also storing elements in the vector
// Example: rationals(4) = [[1,1], [1,2], [2,1], [1,3], [3,2]]
vector<pair<int,int>> rationals(int pos){
    queue<pair<int,int>> rationals; // for storing like BFS
    rationals.push(make_pair(1,1)); // push the first pair
    vector<pair<int,int> > rationalsArray;
    int index = 0; // index of element in BFS array

    while(true){
        pair<int, int> p = rationals.front();
        rationalsArray.push_back(p);
        if(index++ == pos)
            return rationalsArray;
        rationals.pop();
        rationals.push(make_pair(p.first, p.first+p.second)); // push the left child [a,a+b]
        rationals.push(make_pair(p.first+p.second,p.second)); // push the right child [a+b,b]
    }
}

[Craig McIlwrath]

Haskell. Changed things a bit to make more sense in Haskell, allRationals is just a normal list of Rationals. Not 100% happy with this because I don't fully understand the flatTree formula I found on the web...

import Data.Ratio (numerator, denominator, (%))

data Tree a = Tree a (Tree a) (Tree a)

rationalTree :: Tree Rational
rationalTree = build' (1 % 1)
  where build' :: Rational -> Tree Rational
        build' n = let a = numerator n
                       b = denominator n
                   in  Tree n (build' (a % (a + b))) (build' ((a + b) % b))

-- from https://doisinkidney.com/posts/2018-12-18-traversing-graphs.html, idk how it works
flatTree :: Tree a -> [a]
flatTree r = f r b []
  where f (Tree x l r) fw bw = x : fw ([l, r] : bw)

        b [] = []
        b qs = foldl (foldr f) b qs []

allRationals :: [Rational]
allRationals = flatTree rationalTree