Hot answers tagged

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 I⌊EEX²⁻Lθ²↨⁺X²⊖Lθ⊗ι²ΣEθ∧§ιμΣΦ묧ιξ Try it online! Link is to verbose version of code. Explanation: E…X²⁻Lθ²X²⊖Lθ Loop over all cuts... E ↨⊗ι² ... converted to base 2 ΣEθ∧§ιμ 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)[0])/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òlxõ _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[0].reduce((f,l,n)=>!(f[0].push(e[n][n])+f[1].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 Nθ⪫…⮌⌊EEN⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/ Try it online! Link is to verbose version of code. Explanation: Nθ Input decimal as a number N Input maximum denominator E 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)[2]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) [2]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