Golf a FRACTRAN interpreter
Description
From the Esolangs wiki,
In Fractran,
- a program consists of a finite list of positive, rational numbers.
- The input to a program is a positive integer n.
- The list is then searched in order, for a rational number $p/q$ such that $n×p/q$ is an integer.
- Then n is replaced by $n×p/q$ and the search is restarted from the beginning of the list.
- The program halts when no such number $p/q$ can be found, and the final n becomes the output from the program.
- Output the final value of $n$.
Your task is to implement an interpreter for this language.
Input
You are to take two inputs:
- $n$, an integer
- $A$, an array of fractions, which may be taken as a list of pairs, or in the rational datatype of your language.
Output
A single integer, the final value of $n$.
Test Cases
Formatted as
program
input
output
78/55, 5/3, 1/5, 11/2, 5/7
1096135733
328842888196762472689573703
3/2
1296
6561
455/33, 11/13, 1/11, 3/7, 11/2, 1/3
72
15625
[APL (Dyalog Unicode)], 33 byt …
3y ago
[Brachylog], 16 bytes g …
3y ago
[Python 3], 76 71 bytes Sav …
3y ago
JavaScript, 44 bytes …
3y ago
Japt v2.0a0, 18 bytes The ` …
3y ago
[Ruby], 51 50 bytes -1 from R …
3y ago
J, 36 char ``` {.2{(}.,(=< …
2y ago
Ruby, 44 bytes ->p,n{n=I …
3y ago
8 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
APL (Dyalog Unicode), 33 bytes
{×x←⊃(2⌷⍵)(÷⍨(/⍨)0=|)⍺×1⌷⍵:x∇⍵⋄⍺}
The first case doesn't work because it gets really big, but the other two do. The input is taken on the left and the fractions are taken as a table on the right.
{×x←⊃(2⌷⍵)(÷⍨(/⍨)0=|)⍺×1⌷⍵:x∇⍵⋄⍺}
⍺× ⍝ n multiplied by
1⌷⍵ ⍝ The first row of the right argument (every p)
(2⌷⍵) ⍝ Second row of right arg (all q's)
| ⍝ All n×p modulo q
0= ⍝ Check which ones are 0 (rational)
÷⍨ ⍝ Make another vector of 'n×p÷q's
/⍨ ⍝ And keep the ones that were rational
⊃ ⍝ Pick the first (0 if empty)
x← ⍝ Assign to x
× ⍝ Sign of x
⍺ ⍝ If sign is 0, return n
x∇⍵ ⍝ Otherwise, call again with x as new n
Brachylog, 16 bytes
g₂;.z∋zbᵗ×ᵐ/ℤ↰|w
This is a function submission, which inputs n from the left and A from the right (as a list of two-element lists). Output is to standard output.
Explanation
g₂;.z∋zbᵗ×ᵐ/ℤ↰|w
g₂ place two list wrappers around the left input
;. append the right input
z cycling zip; because the left input is length 1,
this pairs it with each element of the right input
∋ find {the first} element for which no assertions fail
[at this point, the element looks like [[n], [num, denom]]
for some pair [num, denom] in A]
z rearrange to [[n, num], [n, denom]]
bᵗ remove first of last pair ([[n, num], [denom]])
×ᵐ take product of each inner list ([n×num, denom])
/ℤ divide; assert result (n×num÷denom) is an integer
↰ recurse (loop back to start of program)
| if all else fails (i.e. ∋ found no elements)
w output the current value to standard output
0 comment threads
Japt v2.0a0, 18 bytes
The r÷ can be removed if we can take an array of floats instead.
T=V£*Xr÷Ãæv1)?ßT:U
T=V£*Xr÷Ãæv1)?ßT:U :Implicit input of integer U and 2D-array V
T= :Assign to variable T
V£ : Map each X in V
* : Multiply U by
Xr÷ : X reduced by division
à : End map
æ : Get the first element that
v1 : Is divisible by 1
) :End assignment
? :If truthy (not undefined)
ßT :Recursive call with arguments U=T and V unchanged
:U :Else return U
0 comment threads
JavaScript, 44 bytes
a=>g=n=>a.every(([p,q])=>(x=n*p/q)%1)?n:g(x)
0 comment threads
J, 36 char
{._2{(}.,~(=<.)@v{.@#v=.}.*{.)^:(<_)
Sample runs:
{._2{(}.,~(=<.)@v{.@#v=.}.*{.)^:(<_) 1096135733 78r55 5r3 1r5 11r2 5r7
328842888196762472689573703
{._2{(}.,~(=<.)@v{.@#v=.}.*{.)^:(<_) 1296 3r2
6561
{._2{(}.,~(=<.)@v{.@#v=.}.*{.)^:(<_) 72 455r33 11r13 1r11 3r7 11r2 1r3
15625
0 comment threads
1 comment thread