Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Golf a FRACTRAN interpreter

+8
−0

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
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

General comments (4 comments)

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.

+6
−0

APL (Dyalog Unicode), 33 bytes

{×x←⊃(2⌷⍵)(÷⍨(/⍨)0=|)⍺×1⌷⍵:x∇⍵⋄⍺}

Try it online!

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
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

1 comment thread

General comments (2 comments)
+4
−0

Brachylog, 16 bytes

g₂;.z∋zbᵗ×ᵐ/ℤ↰|w

Try it online!

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
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

0 comment threads

+3
−0

Python 3, 76 71 bytes

Saved 5 bytes thanks to user

def f(p,n):l=[n*p//q for(p,q)in p if n%q<1];return f(p,l[0])if l else n

Try it online!

This code assumes that the fractions are given as completely cancelled pairs of integers.

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

1 comment thread

General comments (1 comment)
+2
−0

Japt v2.0a0, 18 bytes

The can be removed if we can take an array of floats instead.

T=V£*Xr÷Ãæv1)?ßT:U

Try it

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
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

0 comment threads

+2
−0

JavaScript, 44 bytes

a=>g=n=>a.every(([p,q])=>(x=n*p/q)%1)?n:g(x)

Try it online!

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

0 comment threads

+1
−0

Ruby, 51 50 bytes

-1 from Razetime

->p,n{while i=p.find{(_1*n).to_f%1==0}
n*=i
end
n}

Try it online!

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

1 comment thread

-1 changing to `n*=i` (1 comment)
+0
−0

Ruby, 44 bytes

->p,n{n*=I while I=p.find{_1*n%1==0};n.to_i}

Attempt This Online!

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

1 comment thread

Incorrect solution (2 comments)
+0
−0

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
   
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »