@Adám Put them both in and got the Extended version down to 114

@J.Sallé this could be a lot simpler, if i understand the challenge correctly

the plan: generate an int i with the required distribution (1/2, 1/4, 1/8, ..), then find the i-th rational fraction

would this be acceptable for the first part? i←+/×\11⎕dr?0

for the second part i've got this: ⌽i⊃⍸1=(>∧∨)/↑⍳2⍴2+i

29 bytes: ⌽i⊃⍸1=(>×∨)/↑⍳2⍴2+i←1+⍣{?2}¯1. tio with stats from 1e5 runs

@Adám @Sherlock9 127 by packing the strings 'S' 'NE' 'NW' etc

@ngn Excellent! There's a bug where it needs to be 3+Q... but that's easily fixed and I'll put it in shortly

@Sherlock9 ah, right... i must've hit the wrong key

@Sherlock9 t←s[...]⋄(⍺,t)∇t↑⍵ -> (⍺∘,∇↑∘⍵)s[...]

⊃∘⌽∘⍸¨⍵∘=¨∪⌽⍵ -> {⊃⌽⍵}⌸⍵ or maybe ⌽{⊃⌽⍵}⌸⍵, i'm not sure if order is significant there

even shorter: {⊃⌽⍵}⌸⍵ -> ⊢.⊢⌸⍵

@ngn Ooh let me investigate

@ngn Belatedly, order is significant, and so ⌽{⊃⌽⍵}⌸⍵ works best so far

Ah right ⌽⊢.⊢⌸⍵ also works

One of these days, I ought to go back through the lessons and see what's been said about ⌸ because it's great for golf but I have no idea how to use it

⍝ ⍺ is unique elements (key), ⍵ is indices

⎕←{⍺⍵}⌸1 2 3 1 2 3

@RichardPark
┌─┬───┐
│1│1 4│
├─┼───┤
│2│2 5│
├─┼───┤
│3│3 6│
└─┴───┘

⍝ Left operand provides a key

⎕←'aabbcc'{⍺⍵}⌸1 2 3 1 2 3

@RichardPark
┌─┬───┐
│a│1 2│
├─┼───┤
│b│3 1│
├─┼───┤
│c│2 3│
└─┴───┘

⎕←'abcabc'{⍺⍵}⌸1 2 3 1 2 3

@RichardPark
┌─┬───┐
│a│1 1│
├─┼───┤
│b│2 2│
├─┼───┤
│c│3 3│
└─┴───┘

Oh seems like dyadic case: ⍺ is key, ⍵ is values

Oooh ⍤ that makes a lot of sense. Thanks!

@RichardPark Yes, odd isn't it. Imho, f⌸ has its arguments swapped compared to the "obvious" order.

@ngn holy crap that was eventful

@ngn It really could be simpler, since I just ported Arnauld's answer. I'll try to understand your (surprisingly scanless) train

Oh. What if I reversed the 3-adic thing and so the paths went right to left? Hm. Must investigate.

@ngn I think I understand most of it. I just fail to see how it could go past 5 iterations. My understanding is, since i←1+⍣{?2}¯1 can only be one of 0 1 2 3, ⍳2⍴2+i←1+⍣{?2}¯1 would generate at most ⍳2⍴5 iterations, no?

I mean, I can see from the tests that it does go past the 5th iteration, but I don't see how.

And by iterations I mean fractions

Testing shows me that i can be > 3; I think that means I don't understand ⍣ that well.

@J.Sallé the ?2 is in curly brackets

since ⎕io←0 it's either 1 or 0

⍣ with a function calls the function after each iteration, also supplying it with 2 latest results as arguments

nevermind I don't get it

as FrownyFrog said, {?2} is randomly either 0 or 1. ⍣ could make potentially infinite iterations.

⍳2⍴5 will make a gcd table of i+2 by i+2. the indices of each 1 value in that table correspond the numerator and denominator of a rational number.

every row of that table, except the first, contains at least one 1, so we know i+2 by i+2 will surely contain the i-th rational

hah, i've just seen an opportunity for -1 byte: ⌽i⊃⍸1=∘.(>×∨)⍨⍳2+i←1+⍣{?2}¯1

@ngn i'm not sure i explained this well, let me try again: 1+⍣{?2}¯1 ←→ 1+ 1+ ... 1+ ¯1. after each "1+" step there's a 50% chance of stopping the sequence.

@ngn aaah, this is what was confusing me

I thought it'd just return one of 0 1 2 3 because of the way it was written

Btw, I think we can drop the ⌽, since OP says "As long as the numerator and the denominator are distinguishable, the output format doesn't matter."

@J.Sallé great :) that makes it 27 bytes

Posted with my version of the explanation. Let me know if anything is not explained properly

@J.Sallé btw, it's not a train

Ah yeah, sure. I'll change it