22
\$\begingroup\$

Quote notation is a way of expressing rational numbers based on the concept of \$p\$-adic numbers, written in the form \$x'y\$.

The quote indicates that the number to it's left (\$x\$) is "repeated" infinitely to the left, then prefixed to the number on the right (\$y\$). For example \$3' = \: ...3333\$ and \$764'31 = \: ...76476431\$. We can then consider the geometric series:

$$\cdots + 10^{3k} + 10^{2k} + 10^{k} + 10^{0} = \frac 1 {1 - 10^k}$$

By setting \$k\$ to be equal to the number of digits of \$x\$, we can transform this "infinite" number into a value which converges:

$$\begin{align} 3' & = \: ...333 & 764'31 & = \: ...76476431 \\ & & & = 31 + 764'00 \\ & = \cdots + 3\cdot10^3 + 3\cdot10^2 + 3\cdot10^1 + 3\cdot10^0 & & = 31 + 100 \times 764'\\ & = 3(\cdots + 10^3 + 10^2 + 10^1 + 10^0) & & = 31 + 100 \times 764(\cdots + 10^9 + 10^6 + 10^3 + 10^0)\\ & = 3\left( \frac 1 {1 - 10} \right) & & = 31 + 76400\left( \frac 1 {1 - 10^3} \right) \\ & = \frac {3} {-9} & & = 31 - \frac {76400} {999}\\ & = - \frac 1 3 & & = - \frac {45431} {999} \end{align}$$

Note that \$9'0 \ne 9'\$ as the first equals \$-10\$ and the second \$-1\$. Additionally, note that leading zeros on \$y\$ do affect the output: \$81'09 = -\frac {801} {11} \ne \frac {9} {11} = 81'9\$ Therefore, a value after the \$'\$ (\$y\$) may be omitted in the input.

You are to take, in any reasonable format, up to 2 non-negative integers \$x\$ and \$y\$, and output the fraction \$\frac a b\$ represented by \$x'y\$. Reasonable formats include:

  • A string, delimited by a non-digit character, such as ', e.g. 9' or 9'0. The string will always begin with a digit; if there is no \$x\$ value, it will be a \$0\$ (e.g. 0'3)
  • A list of either 1 or 2 non-negative integers, represented as strings or lists of digits. If there is only 1, it represents \$x'\$. 2 integers represent \$x'y\$.
  • A list of 2 elements. The last element may be either a non-negative integer (as a string or digit list), or a consistent value that is not a non-negative integer (e.g. null or None or -1 etc.) that indicates that there is no \$y\$ value. The first value will always be a non-negative integer.

This is not an exhaustive list, if you have another method, feel free to ask.

You may output the two integers \$a\$ and \$b\$ instead of the fraction \$\frac a b\$. The fraction must be exact, and fully simplified (i.e. \$a\$ and \$b\$ are coprime). If \$b\$ is 1, outputting just \$a\$ is acceptable. For negative outputs, if outputting \$a\$ and \$b\$ separately, either may have the negative sign, but not both.

You may input and output in any convenient method. This is so the shortest code in bytes wins.


Modified from the linked Wikipedia page:

Let \$x\$ and \$y\$ be sequences of digits, as in \$x'y\$

Let \$z\$ be the digit \$1\$ followed by a sequence of zeros of the same length as \$y\$.

Let \$w\$ be a sequence of \$9\$s of the same length as \$x\$.

Then the number represented by \$x'y\$ is given by \$y-\frac{xz}w\$

Test cases

x'y    = a / b
31'491 = 17609 / 99
844'80 = -4480 / 999
4'128  = -2848 / 9
247'0  = -2470 / 999
0'716  = 716 / 1
592'   = -16 / 27
3'45   = 35 / 3
9'7    = -3 / 1
9'     = -1 / 1
3'0    = -10 / 3
764'31 = -45431 / 999
81'09  = -801 / 11
81'9   = 9 / 11
123456' = -41152 / 333333
\$\endgroup\$
15
  • \$\begingroup\$ Apologies for any potential inaccuracies with the actual mathematics - I'm not especially familiar with \$p\$-adic numbers, or this notation. If any doubt arises from such inaccuracies, what's in the challenge is "correct", at least for answers \$\endgroup\$ – caird coinheringaahing Apr 5 at 0:08
  • \$\begingroup\$ Leading zeros are significant in both numbers, right? e.g. 081'09 = 33/37 \$\endgroup\$ – Neil Apr 5 at 0:23
  • \$\begingroup\$ @Neil Leading zeros are significant for \$y\$, but not for \$x\$, as they can be normalised out. You can assume that \$x\$ will never have leading zeros \$\endgroup\$ – caird coinheringaahing Apr 5 at 0:24
  • \$\begingroup\$ @ChartZBelatedly I realised that pretty much instantly after writing the comment \$\endgroup\$ – Lyxal Apr 5 at 0:25
  • \$\begingroup\$ Ah, so 081'10 would be written 810'8110 = 70/37? \$\endgroup\$ – Neil Apr 5 at 0:30

19 Answers 19

13
\$\begingroup\$

J, 25 bytes

(%-.)~/@(10^#&>)#.10#.&>]

Try it online!

Takes a boxed 2-item vector containing the digit vectors of \$x\$ and \$y\$, and returns a rational number. The digits must be given in extended precision. \$y\$ may be an empty vector. I guess it's pretty well golfed when Jelly is at 20 bytes :)

How it works

Uses the formula at the end of the challenge. If we define \$\#x\$ as the number of digits of \$x\$,

$$ z = 10^{\#y}, \quad w=10^{\#x}-1, \quad x'y = -\frac{z}{w}x+y, $$

and observe that the result is the same as the 2-vector \$[x,y]\$ evaluated in base \$-\frac{z}{w}\$.

(%-.)~/@(10^#&>)#.10#.&>]    NB. Monadic train; input = (digits of x;digits of y)
                  10#.&>]    NB. Evaluate each in base 10 to get [x,y]
                #.           NB. Evaluate in base...
        (10^#&>)    NB. 10 raised to the power of length of each; [10^#x, 10^#y]
(%-.)~/@            NB. (10^#y) / (1 - 10^#x) = -z/w

J, 23 bytes

(%-.)~&(10x^#)#.,&{.&".

Try it online!

Modification of Jonah's solution to use the same base trick. This one is a dyadic function accepting plain strings as its two args. One caveat is that eval(".) of an empty string is an empty vector, so we need to make it a 0 explicitly using {..

\$\endgroup\$
2
  • \$\begingroup\$ That's a very clever approach, which I think would heavily outgolf the existing Jelly answer! \$\endgroup\$ – caird coinheringaahing Apr 5 at 2:58
  • 1
    \$\begingroup\$ "and observe that the result is the same as the 2-vector [𝑥,𝑦] evaluated in base..." Very nice! \$\endgroup\$ – Jonah Apr 5 at 3:42
9
\$\begingroup\$

Wolfram Language (Mathematica), 37 33 bytes

d[#/d[0#-9]]~d~#2&
d=Fold[9#+##&]

Try it online!

Input two lists of digits.

Fold[9#+##&] is longer than FromDigits, but has more flexibility with its input.

\$\endgroup\$
7
\$\begingroup\$

Vyxal, 15 bytes

L⁾₁I*₁L⁾⨪/₂I$-ƒ

Try it Online!

I spent roughly an hour on this, trying to arrange it to work properly. Took me a few re-reads of the specs, but I got there in the end.

Input taken as:

y
x

where y and x are strings (done by surrounding them with ""s), and if y isn't provided, [] is used.

Explained

L⁾₁I*₁L⁾⨪/₂I$-ƒ
L⁾               # 10 ** length(y)
  ₁I             # int(x)
    *            # ↑ * ↑↑ (we'll call this W)
     ₁L⁾         # 10 ** length(x)
        ⨪        # ↑ - 1
         /       #  W / ↑
          ₂I     # int(y) # on an empty list, this will return 0
            $-   # ↑↑ - ↑
              ƒ  # fractionify(↑) # this built-in has been around for a long time before this challenge --> it turns a decimal into the most simple fraction
\$\endgroup\$
7
\$\begingroup\$

R, 118 116 108 103 98 92 bytes

function(x,y,`+`=nchar,B=10^+x-1,A=el(max(y,0):0)*B-x*10^+y,q=1:x)c(A,B)/max(q[!A%%q&!B%%q])

Try it online!

Takes first input as integer and second as string (empty if no \$y\$).

GCD implementation borrowed from here: https://codegolf.stackexchange.com/a/48845/55372

-8 bytes thanks to @Kirill & @Dominic;
-5 and another -6 bytes thanks to @Giuseppe

\$\endgroup\$
7
  • 1
    \$\begingroup\$ A quick saving: replace ifelse with "if" \$\endgroup\$ – Kirill L. Apr 5 at 13:43
  • 2
    \$\begingroup\$ I think this can get down to 108 bytes... which frustratingly beats my own attempt... \$\endgroup\$ – Dominic van Essen Apr 5 at 22:45
  • 2
    \$\begingroup\$ el(y:0) is a very clever workaround for strtoi or as.double. I think q=1:B should work, since \$x\leq B\$ and thus \$GCD(x,y)\leq \min(x,y)\leq x\leq B\$ \$\endgroup\$ – Giuseppe Apr 6 at 11:10
  • 1
    \$\begingroup\$ @pajonk the math's pretty simple: the GCD of two numbers is always less than or equal to them, so I just tried to find a number you'd already defined that was bigger than x. That being said, it's more memory efficient to just use x rather than B, since q=1:x would also work. \$\endgroup\$ – Giuseppe Apr 6 at 18:10
  • 2
    \$\begingroup\$ I also got a little inspiration from your el(y:0) to get down to 92 bytes \$\endgroup\$ – Giuseppe Apr 6 at 18:14
7
\$\begingroup\$

R, 114 110 109 107 104 bytes

Edit: -4 and then -2 more bytes thanks to Giuseppe's comments on pajonk's answer, and then -3 bytes after copying a trick from Robin Ryder's answer here

function(s,z=10^nchar(s)-1:0,n=scan(t=pmax(s,0)),a=c(diff(n*z[2:1]),z[1]),c=1:z)a/max(c[!a%%c&!a[2]%%c])

Try it online!

Input is a vector of two strings representing x and y.

I tried to answer this without peeking at the other R answers, but now I realise that pajonk's answer is probably golfier... Bah!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Having a choice of input format makes golfing harder, because you have to think about which is going to be golfiest! \$\endgroup\$ – Giuseppe Apr 6 at 18:16
6
\$\begingroup\$

J, 39 32 30 27 bytes

{.@".@]-".@[*(%<:)~&(10x^#)

Try it online!

-5 thanks to Bubbler. Also go upvote his j answer, which is more creative and has delightful application of base #.

The wikipedia formula translated into J. The only part that might be of some interest is the calculation of z/w:

  • (%&x:<:)~&(10^#)
    • &(1>.10^#) Convert each string input by raising 10 to the power of its length 10^# (which will be 1 when length is 0).
    • (%&x:<:)~ Next swap the argument order ~ and subtract 1 <: from the new right arg, to get a number whose digits are all nines. Divide the left argument by that %.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can remove explicit x: call by making the values extended early, e.g. by using 10x^. \$\endgroup\$ – Bubbler Apr 5 at 2:40
  • \$\begingroup\$ Thanks @Bubbler. I'm racking my brain for a way to further golf this part {.@".@]-".@[, but I'm fried and if there is one I don't see it. \$\endgroup\$ – Jonah Apr 5 at 2:46
  • 1
    \$\begingroup\$ 1>. is not needed, as x part is never empty. After some rearrangement (some of which is also used in my code), 23 bytes solution seems to work. \$\endgroup\$ – Bubbler Apr 5 at 3:28
  • \$\begingroup\$ I fixed the superfluous max, but I think you should take the 23 byte solution for your answer, since you deserve all the fruits of the base trick. \$\endgroup\$ – Jonah Apr 5 at 3:51
6
\$\begingroup\$

Haskell, 58 bytes

x#y=f y-f x*0!y/1!x
c!s=10^length s-c
f x=read$'0':x++"%1"

Try it online!

The relevant function is (#), which takes x and y as strings, with y possibly empty. Returns a Rational.

DISCLAIMER: the compiler is unable to correctly deduce the type of (#), unless it is specified by some other part of the program, either explicitly (i.e. ::Rational) or implicitly (i.e. by using the return value as if it were a Rational). Based on this Meta answer I believe this should be allowed, but since I'm quite inexperienced I'm not sure. If that's not the case, then the best I can do is:

Haskell, 63 bytes

x#y=f y-f x*0!y/1!x
c!s=10^length s-c
f x=toRational.read$'0':x

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Unfortunately, this fails for the recently added 81'09 test case (it calculates 81'9 instead). Additionally, Rational types are perfectly fine IMO for input \$\endgroup\$ – caird coinheringaahing Apr 5 at 1:30
  • \$\begingroup\$ My bad, I did not realize y could have leading zeros. I'll delete this answer for now, since I don't have time to change it at the moment. Thanks for the clarification about Rationals. \$\endgroup\$ – Delfad0r Apr 5 at 1:33
6
\$\begingroup\$

JavaScript (ES7),  80  76 bytes

Expects (x)(y) as strings (y may be an empty string) and returns [numerator, denominator].

x=>y=>(G=(a,b)=>b?G(b,a%b):[p/a,q/a])(q=1-10**x.length,p=y*q+x*10**y.length)

Try it online!

Commented

x =>                       // outer function taking x
y =>                       // inner function taking y
  ( G = (a, b) =>          // G is a helper function which takes 2 integers,
      b ? G(b, a % b)      // computes their GCD a
        : [ p / a, q / a ] // and eventually returns [ p / a, q / a ]
  )(                       // we invoke G with (q, p) defined as follows:
    q =                    //   q =
      1 -                  //   1 - 10 ** len(x)
      10 ** x.length,      //
    p =                    //   p =
      y * q +              //   y * q + x * 10 ** len(y)
      x * 10 ** y.length   //
  )                        //
\$\endgroup\$
4
  • 2
    \$\begingroup\$ TBH I don't see any significant reason to disallow it (and doing so seems kinda unfair), so I'll allow having the negative sign on either, inconsistently, so long as it is only one one \$\endgroup\$ – caird coinheringaahing Apr 5 at 1:48
  • \$\begingroup\$ q=1+x-x-1,p=-(x+y)-y*~q \$\endgroup\$ – tsh Apr 6 at 3:08
  • \$\begingroup\$ @tsh This is much better and should probably be posted as a new answer. \$\endgroup\$ – Arnauld Apr 6 at 5:54
  • \$\begingroup\$ @Arnauld posted \$\endgroup\$ – tsh Apr 6 at 7:08
6
\$\begingroup\$

R + MASS, 99 91 bytes

function(x,y,`[`=gsub)MASS::fractions(eval(parse(t=paste0(y,"-",x,"."[0,y],"/","."[9,x]))))

Try it online!

Takes input as two strings (y possibly empty), outputs a rational fraction or an integer.

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

Husk, 17 bytes

_-d⁰/←₁³*₁⁰d
!İ⁰L

Try it online!

Simply uses the closed form formula from the question.

Explanation

Helper function ₁:
!İ⁰L
   L take the length of the sequence
!İ⁰  get that entry in the powers of 10
     (this is shorter than `^10)

Main program: 
_-d⁰/←₁³*₁⁰d
       ³*₁⁰d multiply ₁(y) with int(x)
    /←₁³     divide by ₁(x) - 1   
_-d⁰         subtract from int(y)
\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 61 bytes

x=>y=>(G=(a,b)=>b?G(b,a%b):[x/a,z/a])(z=-1+x-~x,x-=y+x-(x+y))

Try it online!

Take input as two strings, output an array with two numbers.

JavaScript use + for both number plus and string concatenation. When any operand is string, it works as string concatenation.

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

Jelly, 20 bytes

9ṁḌ+Ø.µ×³ḌU¤_/,Ḣ:g/$

Try it online!

Seems very bad ¯\_(ツ)_/¯

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

Retina, 96 92 bytes

(.+)'(.*)
$($($.1*9)*$2*)-$($1$.2*0)*_/$($.1*9)*
+`_-_
-
-/
/
(_+)(\1)*/(\1)*$
$.(_$#2*)/$#3

Try it online! Link includes faster test cases. Explanation:

(.+)'(.*)
$($($.1*9)*$2*)-$($1$.2*0)*_/$($.1*9)*

Write out yw-xz/w. (Edit: I don't actually multiply x by z, I just suffix the appropriate number of 0s to it, which saves on a 1 amongst other things.)

+`_-_
-
-/
/

Perform the subtraction, slowly.

(_+)(\1)*/(\1)*$
$.(_$#2*)/$#3

Slowly divide by the GCD and convert to decimal.

Just for completeness, optimising for speed results in code that readily dispatches all of the test cases. Try it online!

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

Jelly (fork), 11 bytes

ḌḅẈ⁵*C÷@¥/Ʋ

Try it online!, or rather, don't

As of last week, my fork now includes symbolic math support! Unfortunately, M (Jelly's version with symbolic math) only implements this in the İ atom, not in the ÷ division atom. My fork does both.

Again, implements Bubbler's strategy to evaluate \$[x, y]\$ in base \$-\frac z w\$.

How it works

ḌḅẈ⁵*C÷@¥/Ʋ - Main link. Takes [x, y] as lists of digits on the left
Ḍ           - Convert [x, y] to integers
          Ʋ - Do the following to [x, y]:
  Ẉ         -   Lengths of each
   ⁵*       -   Raise 10 to the power of each length
        ¥/  -   Reduce by the following:
     C      -     Complement; 1 - a
      ÷@    -     Divide b by that; b / (1 - a)
\$\endgroup\$
2
  • \$\begingroup\$ actual symbolic math? or just rationals \$\endgroup\$ – ASCII-only Apr 6 at 9:32
  • 1
    \$\begingroup\$ @ASCII-only Whatever sympy supports \$\endgroup\$ – caird coinheringaahing Apr 6 at 9:40
3
\$\begingroup\$

Charcoal, 55 bytes

F⪪S'«≔ζη≔ιζ»≔I⭆η⁹δ≔⁻×IζδI⁺η⭆ζ⁰ε⊞υε⊞υδW﹪εδ«≔δε≔ιδ»⪫÷υ↔δ/

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

F⪪S'«≔ζη≔ιζ»

Split the input string on ' and save the parts into separate variables.

≔I⭆η⁹δ

Change the digits of the first part to 9s and save the result as an integer.

≔⁻×IζδI⁺η⭆ζ⁰ε

Multiply that by the second part as an integer, then change the digits of the second part to 0s, append that to the first part, and subtract the integer value.

⊞υε⊞υδ

Save the fraction to the predefined empty list.

W﹪εδ«≔δε≔ιδ»

Find the GCD.

⪫÷υ↔δ/

Reduce the fraction to its lowest terms and output it with a / separator.

\$\endgroup\$
3
\$\begingroup\$

Clojure, 92 bytes

#(let[b biginteger p(fn[x](.pow(b 10)(count x)))](-(b(or %2 0))(/(*(b %)(p %2))(dec(p %)))))

Try it online!

Relies on the formula from Wikipedia. Takes input as two strings (nil when there is no y), outputs a rational fraction, or a bigint when denominator is 1.

\$\endgroup\$
3
\$\begingroup\$

M, 13 bytes

Cİ×
L€⁵*ç/ḅ@Ḍ

Try it online!

Implements Bubbler's method

How it works

Cİ× - Helper link. Takes a on the left and b on the right
C   - Yield 1-a
 İ  - Inverse; Yield 1 / (1-a)
  × - Times; Yield b / (1-a)

L€⁵*ç/ḅ@Ḍ - Main link. Takes [x, y] as lists of digits
L€        - Length of each
  ⁵*      - Raise 10 to the power of the lengths
    ç/    - Run the helper link with the powers of 10 as a and b
        Ḍ - Convert [x, y] into integers
      ḅ@  - Evaluate [x, y] as base b / (1-a)
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 70 bytes

Not great, but I felt like submitting it anyway

{⍺←⍬⋄{⍵÷⊃⌽⊃∩⍥(⍸0=⊢|⍨⍳)/|⍵}((W×⍎'0',⍺)-(⍎⍵)×⍎'1','0'\⍨⍴,⍺),W←⍎'9'\⍨⍴,⍵}

Not sure why, but my code to handle single arguments works in TryAPL.org but not in tio.run

Also, because of how APL handles default arguments, I had to swap the order on input...like I said, not the best solution :|

⍺←⍬⋄ ⍝ assign Empty Set to the default value for the left argument (Y from the problem statement)
 ⍵÷⊃⌽ ⍝ divide the 2-tuple (a and b from the problem statement) by their gcd
  ⊃ ⍝ pick (removes one layer of nesting)
   ∩ ⍝ intersection
    ⍥ ⍝ function composition operator (Over)
     (⍸0=⊢|⍨⍳)/ ⍝ fold/reduce by finding divisors
      |⍵ ⍝ absolute value of 2-tuple (a and b from the problem statement)
       W×⍎'0',⍺ ⍝ W (from problem statement) times the integer representation of the left argument (Y from the problem statement) or zero if alpha is the empty set
        -(⍎⍵) ⍝ subtract the integer representation of the right argument (X from the problem statement)
         ×⍎ ⍝ decode then multiply
          '1', ⍝ concatenate the character 1
           '0'\⍨⍴ ⍝ expand the character 0 by the number of characters in Y
             ,⍺ ⍝ ravel Y (effectively making single characters into singleton arrays)
              , ⍝ concatenate
                W←⍎'9'\⍨⍴ ⍝ assign the integer representation of the expansion of the character 9 by the number of characters in X
                 ,⍵ ⍝ ravel X

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5 -apl, 99 bytes

($w,$z)=map s/./9/gr,@F;@e=($F[1]*$w-$F[0]*($z+1),$w);$w--while grep$_%$w,@e;$_=join"/",map$_/$w,@e

Takes two space separated strings from stdin, outputs a fraction.

Try it online!

\$\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.