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!
Top comments (6)
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.
TypeScript
Edit: Removed
rationals.shift()
in favor of keeping track of therationals[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.Plain javascript. Slow but correct:
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.
C++
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 theflatTree
formula I found on the web...