Daily Challenge #199 - List of All Rationals

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

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++;
  }
}

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]];
}

// 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]
    }
}

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