30
\$\begingroup\$

I recently learned from a comment by MathOverflow user pregunton that it is possible to enumerate all rational numbers using iterated maps of the form \$f(x) = x+1\$ or \$\displaystyle g(x) = -\frac 1x\$, starting from \$0\$.

For example, $$0 \overset{f}{\mapsto} 1 \overset{f}{\mapsto} 2 \overset{g}{\mapsto} -\frac12 \overset{f}{\mapsto} \frac12 \overset{f}{\mapsto} \frac 32 \overset{g}{\mapsto} -\frac23 \overset{f}{\mapsto} \frac 13.$$

That is, $$ \frac13 = f(g(f(f(g(f(f(0))))))) = f\circ g\circ f\circ f\circ g\circ f\circ f(0).$$ This is an example of a shortest path of iterated maps to reach \$\frac13\$; every path from \$0\$ to \$\frac13\$ requires at least seven steps.


Challenge

Your challenge is to take two integers, n and d, and return a string of f's and g's that represents a shortest path of iterated maps from \$0\$ to \$\displaystyle\frac nd\$.

This is a , so shortest code wins.

Example

  n |  d | sequence of maps
----+----+-----------------
  1 |  3 | fgffgff
  3 |  1 | fff
  8 |  2 | ffff
  1 | -3 | gfff
  2 |  3 | fgfff
  0 |  9 | [empty string]
  1 |  1 | f
  2 |  1 | ff
  1 | -2 | gff
 -1 | -2 | fgff
  6 |  4 | ffgff
 -2 |  3 | gffgff
  8 |  9 | fgfffffffff
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Somewhat related. \$\endgroup\$
    – alephalpha
    Jan 10 at 1:18
  • 2
    \$\begingroup\$ May we return output reversed, i.e. in the order of function application? \$\endgroup\$
    – chunes
    Jan 10 at 1:26
  • 2
    \$\begingroup\$ May we take input as a rational number \$\frac nd\$, if our language supports them? \$\endgroup\$
    – att
    Jan 10 at 1:52
  • 1
    \$\begingroup\$ @att but then, we should only allow reduced fractions input for other answers, imo. Since most languages only support 1/4 but not 2/8. \$\endgroup\$
    – tsh
    Jan 10 at 2:27
  • 2
    \$\begingroup\$ For anyone interested: This can also be visualized and demonstrated in a classroom, using two ropes that get twisted together. A nice introduction to "Conway's Rational Tangles" is here: geometer.org/mathcircles/tangle.pdf \$\endgroup\$
    – mathmandan
    Jan 12 at 18:38

14 Answers 14

13
\$\begingroup\$

Python, 54 bytes (-1 @Jonathan Allan, -1 me)

f=lambda n,d:n and'gf'[p:=n*d>0]+f(p*n-d,[n,d][p])or''

Attempt This Online!

Old Python, 56 bytes (@tsh)

f=lambda n,d:n*d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''

Attempt This Online!

Old Python, 57 bytes

f=lambda n,d:n//d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''

Attempt This Online!

Not 100% sure this is correct. Works on all test cases, though. It's kind of a Euclidean algorithm with overshoot.

Towards a proof of correctness

The group of transformations generated by f and g is called the Modular group. There is quite a bit of interesting theory but the one thing that seems relevant to us is that gg and gfgfgf are a "complete set of relations" and that the modular group is the "free product of the cyclic groups generated by g and h:=gf". This means that any element of the modular group can be uniquely written as g's alternating with either h or hh. Transforming back to f's and g's gh becomes f and ghh becomes fgf, so except for the left end which can be h or hh, i.e. gf or gfgf all valid representations are exactly the words with g's separated by at least 2 f's. And we can check that the algorithm indeed produces such words.

So, are we done? I'm not sure. What's missing is that I don't know how exactly the rationals and the modular group are related. It may well be that two distinct group elements move 0 to the same rational which would send us back quite a bit if not all the way to square 1.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Maybe n//d<0 -> n*d<0 \$\endgroup\$
    – tsh
    Jan 10 at 1:42
  • 1
    \$\begingroup\$ @alephalpha I can see how this shows that it will always find a representation, but does it also guarantee that it's a shortest representation? \$\endgroup\$
    – loopy walt
    Jan 10 at 2:21
  • 1
    \$\begingroup\$ @loopywalt Sorry, I didn't see the word "shortest" in the challenge. \$\endgroup\$
    – alephalpha
    Jan 10 at 2:24
  • 1
    \$\begingroup\$ @loopywalt Although I don't know how it can be proved. But it seems that no counterexample exists for fractions may reached within 20 operators. \$\endgroup\$
    – tsh
    Jan 10 at 6:54
  • \$\begingroup\$ @loopywalt Try it online! \$\endgroup\$
    – tsh
    Jan 10 at 6:55
7
\$\begingroup\$

JavaScript (Node.js), 53 bytes

f=(n,d,p='',...e)=>n?f(...e,-d,n,p+'g',n-d,d,p+'f'):p

Try it online!

Stackoverflow on last testcase.

\$\endgroup\$
6
\$\begingroup\$

Ruby, 45 bytes

f=->n,d{n==0?"":n/d<0??g+f[-d,n]:?f+f[n-d,d]}

Try it online!

Use as f[n,d]

basically a port of loopy walt's python answer

\$\endgroup\$
5
\$\begingroup\$

Haskell,  44  42 bytes

0#d=[]
n#d|n*d<0='g':(-d)#n|m<-n-d='f':m#d

adaption of the python solution, using guards. Ungolfing barely changes it, just adding whitespace:

0#d          = []
n#d | n*d<0  = 'g':(-d)#n
    | m<-n-d = 'f':m#d

Try it online!

-2 Bytes thanks to xnor, TIO link also thanks to xnor

\$\endgroup\$
1
  • \$\begingroup\$ 42 bytes by tweaking the guards \$\endgroup\$
    – xnor
    Jan 10 at 12:43
4
\$\begingroup\$

Pari/GP, 52 bytes

t(n,d)=if(n/d>0,Str(f,t(n-d,d)),n,Str(g,t(-d,n)),"")

Try it online!

A port of @loopy wait's Python answer.

Shorter (46 bytes) if we can take a rational number as input:

t(r)=if(r>0,Str(f,t(r-1)),r,Str(g,t(-1/r)),"")

Try it online!

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 90 bytes

A naive algorithm trying all sequences of length \$k\$, starting with \$k=0\$ and incrementing \$k\$ until a solution is found.

Expects (n)(d). Returns an empty array instead of an empty string.

n=>F=(d,k)=>(g=(k,o=[],N=n,D=d)=>k--?g(k,o+'f',N-D,D)||g(k,o+'g',-D,N):!N&&o)(k)||F(d,-~k)

Try it online!


JavaScript (ES6), 44 bytes

Assuming loopy walt's method is valid (and it most probably is).

Expects (n,d).

f=(n,d)=>n*d<0?'g'+f(-d,n):n?'f'+f(n-d,d):''

Try it online!

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 104 bytes

n=1;d=3;o;main(){if(d<0){n=-n;d=-d;}while(n){if(n<0){o=d;d=-n;n=o;printf("g");}else{n-=d;printf("f");}}}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ As it stands your submission isn't valid as it hard-codes the input. You should write this as a function and then call it from main in the TIO footer (which would allow you to show off several test cases). \$\endgroup\$
    – Neil
    Jan 10 at 13:43
  • \$\begingroup\$ You can use n<0^d<0 to avoid the first if block. You can also probably use the comma operator to avoid some of the {}s. \$\endgroup\$
    – Neil
    Jan 10 at 13:45
  • \$\begingroup\$ 73 bytes \$\endgroup\$
    – ceilingcat
    Jan 11 at 17:03
3
\$\begingroup\$

05AB1E, 33 bytes

∞ε„fg©sã}˜õš.Δ®'>„z(‚‡0s.VI`/α₄z‹

Naive brute-force approach. Outputs in reversed order. If this is not allowed, a trailing }R will have to be added and it would be 35 bytes instead, making the approach below 1 byte shorter.

Try it online or verify all test cases.

A port of @loopyWalt's second Python answer is 34 bytes, but it outputs in the correct order:

"ÐPdi¬ĀiÆ0ǝ®.V'fìëõë`s(‚®.V'gì"©.V

Try it online or verify all test cases.

Explanation:

∞                     # Push an infinite positive list: [1,2,3,...]
 ε                    # Map over each integer:
  „fg                 #  Push string "fg"
     ©                #  Store it in variable `®` (without popping)
      s               #  Swap so the current integer is at the top
       ã              #  Get the cartesian product
  }˜                  # After the map: flatten the list of lists
    õš                # Prepend an empty string
.Δ                    # Then find the first value which is truthy for:
  ®                   #  Push "fg" from variable `®`
   '>                '#  Push string ">"
     „z(              #  Push string "z("
        ‚             #  Pair them together: [">","z("]
         ‡            #  Transliterate all "f" to ">" and "g" to "z("
          0           #  Push 0
           s          #  Swap so the string is at the top again
            .V        #  Evaluate as 05AB1E code:
                      #   `>`: Increase the value by 1
                      #   `z(`: `z` will push 1/value, `(` will negate it
              I       #  Push the input-pair: [n,d]
               `      #  Pop and push `n` and `d` separated to the stack
                /     #  Divide `n` by `d`
                 α    #  Get the absolute difference between the two values
                    ‹ #  Check if this is smaller than
                  ₄z  #  1/1000
                      #  (`α₄z‹` can't be `Q` due to floating point inaccuracies)
                      # (after which the result is output implicitly)
"..."                 # Push the recursive string defined below
     ©                # Store this string in variable `®` (without popping)
      .V              # Evaluate it as 05AB1E code

Ð                     # Triplicate the current pair [n,d]
                      # (which will be the implicit input in the first call)
   i                  # If
 P                    # n*d (product of the pair)
  d                   # is >= 0:
      i               #  If
    ¬                 #  n (without popping the pair)
     Ā                #  is not 0:
       Æ              #   Push n-d (reduce by subtracting)
         ǝ            #   And insert this n-d back into the pair
        0             #   at index 0: [n-d,d]
          ®.V         #   Then do a recursive call
             'fì     '#   And prepend "f" to that
      ë               #  Else:
       õ              #   Push an empty string ""
   ë                  # Else:
    `                 #  Pop and push `n` and `d` separated to the stack
     s                #  Swap the two values on the stack
      (               #  Negate `n`
       ‚              #  Pair them back together: [d,-n]
        ®.V           #  Then do a recursive call
           'gì       '#  And prepend "g" to that
                      # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 65 62 52 48 bytes

NθNη¿θWφ«≔θφ≔ηζ⊞υωP←⍘LυgfF⮌↨Lυ²¿κ≧⁻ζφ«≔ζε≔φζ≔±εφ

Try it online! Link is to verbose version of code. Feels like it should be a bit shorter. Explanation:

NθNη

Input n and d.

¿θWφ«

Do nothing if n=0, otherwise loop until a reverse path to zero is found. (This loop uses the variable f which is predefined to 1000, thus ensuring the loop happens at least once; it saves a byte over saving n and using while (n).)

≔θφ≔ηζ

Make new copies of n and d.

⊞υω

Increment the length of the predefined empty list.

P←⍘Lυgf

Replace the canvas with the length interpreted as a base 2 string of fs and gs (with f=1 and g=0). The string is reversed so that the last letter is always f.

F⮌↨Lυ²

Loop over the base 2 digits in reverse.

¿κ≧⁻ζφ

For 1s undo the f step.

«≔ζε≔φζ≔±εφ

Otherwise undo the g step.

Switching to undoing steps saved me 10 bytes. It's possible that deciding whether to undo an f or g step based on the sign of the current fraction suffices to produce a minimal result. If that's true then the solution would only be 31 bytes:

NθNηWθ¿›×θη⁰«f≧⁻ηθ»«g≔ηζ≔θη≔±ζθ

Try it online! Link is to verbose version of code. Explanation:

NθNη

Input n and d.

Wθ

Repeat until n=0.

¿›×θη⁰«

If n/d is positive, then...

f≧⁻ηθ

... output an f and subtract d from n.

»«

Otherwise...

g≔ηζ≔θη≔±ζθ

... output a g, switch n and d, and negate n.

\$\endgroup\$
2
\$\begingroup\$

Nibbles, 16

`.~$@?*@$~-@__*~@$$=`$*@$"fg "

That's 31 nibbles at half a byte each in the binary form.

This is based on the python answer although I found an iterative solution shorter. It felt kind of awkward still though.

`. ~$@      Iterate while unique, starting with the tuple $ @ (which is the input arguments)
  ? *@$     if product of values > 0
    ~-@_ _  then ($-@, @) since true clause has condition's value put in $ (unused here though)
    *~@ $   else (-1*@, $)
  $         the second value of the tuple from the if (tuple's aren't returned as first class things but splat into the context and must be reconstructed, normally very concise but here a bit awkward

The above code computes the sequences of numerators and denominators, now we just need to convert it to f and g. Note that it has a few extra terms since it didn't stop being unique until after the solution was found. Luckily n*d is 0 in that case so we can use that to map it to a space. The below code is implicitly done via a map.

= `$ *@$   subscript using signum of n*d
  "fg "    into this list (0 is the last since 1 based).

Call it like nibbles filename.nbl 1 3 (Nibbles isn't on TIO yet).

Note that this will also output 4 spaces after the answer, you could remove it by doing a filter, this would add two nibbles or 1 byte.

\$\endgroup\$
2
\$\begingroup\$

Python3, 192 bytes:

lambda n,d:f([(0,n/float(d),'')])
f=lambda d:r[0][-1]if(r:=[i for i in d if round(i[0],4)==round(i[1],4)])else f([j for a,b,c in d for j in[(a+1,b,'f'+c)]+([(-1/(1.0*a),b,'g'+c)]if a else[])])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Extended), 48 bytes

Basic bruteforce approach, expects index origin 0.

f←-⍨\⍢⌽
g←-@0⌽
⌽o⊣1+⍣{0=⊃⍎⍕t,⍨↓⍪o∘←'gf'[⊤⍵]}⍱t←⎕

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (clang), 59 \$\cdots\$ 53 52 bytes

z;f(n,d){z=n*d>=0;n&&f(z*n-d,z?d:n,putchar(103-z));}

Try it online!

Port of loopy walt's Python answer.
Saved 5 6 bytes thanks to ceilingcat!!!
Saved a byte thanks to dingledooper!!!

Inputs integers \$n\$ and \$d\$.
Outputs string of f's and g's that represents a shortest path of iterated maps from \$0\$ to \$\frac{n}{d}\$.

\$\endgroup\$
2
  • \$\begingroup\$ The printf is neat, but putchar('g'-z) is one shorter, surely? \$\endgroup\$ Jan 12 at 1:18
  • \$\begingroup\$ @dingledooper Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Jan 12 at 9:59
1
\$\begingroup\$

Stax, 18 bytes

âNW≡(hz¶╚òZS/ò⌂==T

Run and debug it

Pretty convenient with the rational type.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.