# Tag Info

14

Python 3, 66 61 bytes lambda x:Fraction(x).limit_denominator from fractions import* Try it online! The above function takes a floating point number and returns a bound function Fraction.limit_denominator which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested. As you can tell, I’m more of an API ...

13

Python 3.8 (pre-release), 77 71 bytes -6 bytes thanks to @ovs ! lambda x,n:min([abs(x-(a:=round(x*b))/b),a,b]for b in range(1,n+1))[1:] Try it online! Simply try all denominators from 1 to n, saving all results into a list where each element has the form [error, numerator, denominator]. By taking the min of the list, the fraction with the smallest error is ...

10

Python 2, 168, 135, 87 bytes z=i=1 def f(x,y):exec"r=round(x*i);q=abs(r/i-x)\nif q<z:z=q;t=r;u=i\ni+=1;"*y;print t,u Try it online! Thank you all for your recommendations on my first golf!

9

MATL, 36 bytes nZ@[]etGg)GXz-yt!hs&ytXdwPXdhsh&-ha The input is an $n \times n$ matrix, with $0$ for the unknown numbers. The code keeps generating random $n \times n$ matrices formed by the numbers $1, \dots, n^2$ until one such matrix meets the required conditions. This procedure is guaranteed to finish with probability one. This is a ...

8

APL (Dyalog Extended), 25 27 bytes {⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣ Try it online! Inline tacit function, which can be used as n f x. Uses the method described in Luis Mendo's MATL answer. I changed one part of the algorithm: This one doesn't consider integer and fractional parts separately; rather, the fractional part is included in the last digit. (e.g. the ...

8

MATL, 8 7 bytes -1 byte thanks to @LuisMendo Xy4LY)i Takes the coefficients in reverse order Try it online! Explanation Xy4LY)i Xy : Create an identity matrix of size equal to input 4LY) : Remove the first row i : Insert input onto the stack

7

05AB1E, 11 bytes î*LãΣ/¹α}н Try it online or verify all test cases (except for the two 1000000 test cases, which take too long). Explanation: î # Ceil the (implicit) input-decimal * # Multiply it by the (implicit) input-integer L # Pop and push a list in the range [1, ceil(decimal)*int] ã # Create all possible pairs of ...

7

MATL, 33 bytes 3y^i*1&\3_YAt1=f"O@QJh(wkw]XB+wW/ Inputs are n, then x. Try it online! Or verify all test cases. Approach The code uses a non-recursive approach, based on the procedure for computing the Cantor function $f_\infty(x)$ that appears in Wikipedia, modified so that it computes $f_n(x)$ instead: Multiply $x$ by $3^n$. Decompose ...

7

JavaScript (ES7),  141 ... 128  125 bytes Saved 2 bytes thanks to @Ada Expects the fraction $p/q$ as (p)(q). Returns $P/Q$ as [P,Q]. p=>q=>(k='0b'+(n=0,g=p=>(r=n-g[p])?'':p/q&1||[p/q>>1]+g(p%q*3,g[p]=n++))(p),r?[((k>>r)*(m=2**r-1)+(k&m))*2,m<<n-r]:[+k,1<<n]) Try it online! How? Ternary and binary expansions k = ...

7

Wolfram Language (Mathematica), 15 bytes CantorStaircase Try it online! Just a built-in function.

7

Charcoal, 37 36 34 bytes Ｉ⌊ＥＥＸ²⁻Ｌθ²↨⁺Ｘ²⊖Ｌθ⊗ι²ΣＥθ∧§ιμΣΦλ¬§ιξ Try it online! Link is to verbose version of code. Explanation: Ｅ…Ｘ²⁻Ｌθ²Ｘ²⊖Ｌθ Loop over all cuts... Ｅ ↨⊗ι² ... converted to base 2 ΣＥθ∧§ιμ Sum rows in source cut ΣΦλ¬§ιξ Sum columns in sink ...

6

JavaScript (Node.js),  88  84 bytes Saved 4 bytes thanks to @NahuelFouilleul d=>-BWe fV?0 @/gU Xd.A.replace(/./g,c=>d.substr((n=Buffer(c))/7-6,2)-3+n%7+' ') Try it online! How? Each value in the matrix is encoded as a character whose ASCII code is: $$7k+o+42$$ where $k$ is the 0-indexed position of the variable in the input string and $o-3$ ...

6

APL (Dyalog Extended), 73 bytes 1-1⊥∘(∊∨/¨⍮2(-⊃⍤∧∘⌽/⍮(3⊃∧∘⌽)⌿)⊢)(⊂4⍴2)⊤¨(9467+⎕AV⍳'ð{dòlxõ _0h8p∆')⍳⎕UCS Try it online! Over half of the bytes were used in converting the char matrix into an easier-to-use format. Basically, converts each box-drawing char into [right, up, down, left], counts non-blanks and joints, and computes 1 - non-blanks + joints. ...

6

JavaScript, 559 551 bytes Fast and methodical. B=Boolean,f=((e,r)=>(v=r*((r**2+1)/2),e.forEach(e=>e.filter(B).length==r-1?e[e.findIndex(e=>!e)]=v-e.reduce((e,f)=>!(e+=f)||e):0),e.reduce((f,l,n)=>!(f.push(e[n][n])+f.push(e[n][r-1-n]))||f,[[],[]]).forEach((f,l)=>{f.filter(B).length==r-1&&(z=f.findIndex(e=>!e),e[z][l?r-1-z:...

6

Python 3.8, 169 bytes Maybe the reason why there was no submissions using Farey sequences is that the code appears rather lengthy. In short, every proper fraction $\frac{m}{k}$ in lowest terms appears in Farey sequence of order $d$ if and only if $k\le d$. Farey sequences are constructed by taking mediant of neighboring terms of lower order: $\left(\... 6 APL (Dyalog Unicode), 38 bytes {×⍺×1-⍵:2÷⍨(1∘≤+(1≠⌊)×(⍺-1)∇⊢-⌊)3×⍵⋄⍵} Try it online! Combines the cases of the recurrence using  f_{n+1}(x) = \frac{1}{2}\begin{cases} 0+1×f_n(3x-0), x\in[0,1/3) \\ 1+0×f_n(3x-1), x\in[1/3,2/3)\\ 1+1×f_n(3x-2), x\in[2/3,1] \end{cases}  which can be condensed (note$u=3x\$) to $$f_{n+1}\left(\frac{1}{3}u\right) = \frac{... 6 J, 10 8 bytes Returns the matrix reversed in both dimensions. ,}:@=@/: Try it online! How it works ,}:@=@/: input: 3 _1 19 /: indices that sort: 1 0 2 (just to get k different numbers) =@ self-classify: 1 0 0 0 1 0 0 0 1 }:@ drop last row: ... 5 Retina, 131 bytes T─┐┬╴┼┤┴┘│╵└├┌╶╷L (?=(.)*[BCEFILMO].*¶(?>(?<-1>.)*)[E-L]) - (?=[ACEGK-N]-?[A-H])|^ - +-\s*\w C- Try it online! TIO counts the box drawing characters as only one byte even though they are not ASCII (the Retina code page). How? This uses a rearranged Euler characterstic F=1+E-V to find the number of faces under the assumption ... 5 Charcoal, 31 bytes Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/ Try it online! Link is to verbose version of code. Explanation: Ｎθ Input decimal as a number Ｎ Input maximum denominator Ｅ Map over implicit range κ Current index (0-indexed) ... 5 Python 3, 54 bytes f=lambda n,x:n and(1<x*3<2or x//.5+f(n-1,3*x%1))/2or x Try it online! Python 3 is used just for the /2 to do float division; Python 2 would be a byte longer with /2.. 5 Python 3.8 (pre-release), 120 119 117 bytes -2 bytes thanks to @Neil! f=lambda p,q,P=0,Q=1,*R:p in R and(P-P//(i:=1<<R.index(p)+1),Q-Q//i)or f((d:=p*3//q+1)%2*(p*3%q),q,P*2+d//2,Q*2,p,*R) Try it online! Same idea as below, but as a lambda function instead. Python 2, 133 131 125 122 bytes -3 bytes thanks to @Neil! def f(p,q,P=0,Q=1,*R): if p in R:i=... 5 JavaScript (ES6), 36 bytes a=>a.map((_,i)=>i?a.map(_=>+!--i):a) Try it online! Returns:$$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_{k-1} & a_k \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 &... 5 05AB1E, 12 bytes -1 thanks to @mypronounismonicareinstate >16/Ížrsm2.ò Try it online! Explanation > Increment 16/ Divide by 16 Í -2 žr Push Euler's constant s Swap operands m Exponentiation 2.ò Round to 2 decimal places 5 JavaScript (ES6), 96 bytes f=(m,k=1,b)=>k*2>>m.length?b:f(m,k+2,m.map((r,y)=>r.map((v,x)=>t+=k>>y&~k>>x&1&&v),t=0)|t>b?b:t) Try it online! Commented f = ( // f is a recursive function taking: m, // m[] = adjacency matrix k = 1, // k = counter, ... 4 APL (Dyalog Unicode), 60 bytes {(⍵,m+.×1+⍺*2)⌹(∘.(×⊢×=)⍨⍵)⍪2×m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺} Try it online! Not likely the shortest approach, but anyway here is one with Matrix Divide ⌹, a.k.a. Solve Linear Equation. This works because all the cells are uniquely determined by the horizontal/vertical/diagonal sums when joined with the givens. ⌹ has no ... 4 JavaScript (ES7), 143 142 140 bytes Expects (n)(m), where unknown cells in m are filled with 0's. n=>g=m=>[0,1,2,3].some(d=>m.some((r,i)=>m.map((R,j)=>t^(t-=(v=d?R:r)[x=[j,i,j,n+~j][d]])||(e--,X=x,V=v),e=1,t=n**3+n>>1)&&!e))?g(m,V[X]=t):m Try it online! Commented n => // outer function taking n g ... 4 Japt v2.0a0 -g, 15 bytes mc ×õ ï ñ@ÎaXr÷ Try it mc ×õ ï ñ@ÎaXr÷ :Implicit input of array U m :Map c : Ceiling × :Reduce by multiplication õ :Range [1,result] ï :Cartesian product with itself ñ :Sort by @ :Passing each pair X ... 4 Zig 0.6.0, 149 bytes fn a(e:f64,m:f64)f64{var n:f64=1;var d=n;var b=d;var c=b;while(d<m){if(n/d>e)d+=1 else n+=1;if(@fabs(n/d-e)<@fabs(b/c-e)){b=n;c=d;}}return.{b,c};} Try it Formatted: fn a(e: f64, m: f64) f64 { var n: f64 = 1; var d = n; var b = d; var c = b; while (d < m) { if (n / d > e) d += 1 else n += ... 4 Perl 5 -p -MList::Util=min, 65, 61 bytes -4 bytes thanks to DomHastings / /;$_=min map abs($-($-=.5+$_*$)/$_)."$-/$_",1..$';s;.* ; Try it online!

Only top voted, non community-wiki answers of a minimum length are eligible