dev.to staff

Posted on Mar 2, 2020

Daily Challenge #199 - List of All Rationals

#challenge

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 yo+challenge@dev.to with your suggestions!

🐯 🚀 Timescale is now TigerData: Building the Modern PostgreSQL for the Analytical and Agentic Era

We’ve quietly evolved from a time-series database into the modern PostgreSQL for today’s and tomorrow’s computing, built for performance, scale, and the agentic future.

So we’re changing our name: from Timescale to TigerData. Not to change who we are, but to reflect who we’ve become. TigerData is bold, fast, and built to power the next era of software.

Top comments (6)

Avalander • Mar 2 '20

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 • Mar 2 '20 • Edited

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 • Mar 2 '20

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 • Mar 3 '20

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 • Mar 2 '20

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 • Mar 2 '20

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