## DEV Community is a community of 603,444 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

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)
}
``````
Michael Kohl • Edited

Ruby, with a couple of twists:

1. No binary tree, it didn't seem necessary.
2. Actual rational numbers thanks to the `Rational` class.
3. Instead of using `Enumerable::Lazy` I manually implemented the infinite list with a `Fiber`, because why not:
``````def rationals(level:)
[*1..level].permutation(2).map { |n, d| Rational(n, d) }
end

def make_rationals
Fiber.new do
level = 1
s = Set.new([Rational(1)])
loop do
Fiber.yield(s)
level += 1
s.merge(rationals(level: level))
end
end
end
``````

Each call to `Fiber#resume` will return more rational numbers:

``````all_rationals = make_rationals
all_rationals.resume
#=> #<Set: {(1/1)}>
all_rationals.resume
#=> #<Set: {(1/1), (1/2), (2/1)}>
all_rationals.resume
#=> #<Set: {(1/1), (1/2), (2/1), (1/3), (2/3), (3/1), (3/2)}>
all_rationals.resume
#=> #<Set: {(1/1), (1/2), (2/1), (1/3), (2/3), (3/1), (3/2), (1/4), (3/4), (4/1), (4/3)}>
``````

Note that this only includes unique numbers, so e.g. 9/6 will be missing because it's the same as 3/2:

``````9/6r == 3/2r
#=> true
``````

So if you want to be closer to the description, you can change the code to something like this:

``````def rationals(level:)
[*1..level].permutation(2).to_a
end

def make_rationals
Fiber.new do
level = 1
s = Set.new([1, 1]) # this will just add 1
loop do
Fiber.yield(s)
level += 1
s.merge(rationals(level: level))
end
end
end
``````
Matt Ellen

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

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.

Empereol • 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.

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