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)[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
Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/
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)[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
