Code-Golf: Sekwencja Farey (I)

10

Wyzwanie

W tym zadaniu otrzymasz liczbę całkowitą N (mniejszą niż 10 ^ 5), wypisz sekwencję Farey rzędu N.

Wejście N jest podane w jednym wierszu, wejścia są zakończone przez EOF.

Wejście

4
3
1
2

Wynik

F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}
F1 = {0/1, 1/1}
F2 = {0/1, 1/2, 1/1}

Ograniczenia

  • Liczba wejść nie przekroczy 10 10 wartości
  • Możesz użyć dowolnego wybranego języka
  • Najkrótsze rozwiązanie wygrywa!
Donkiszotowski
źródło
To będzie długie ..... wyjście mam na myśli.
st0le
Czy N = 0 jest dozwolone?
Eelvex
4
Co to jest »(I)« w tytule?
Joey
2
@Jey: Hmm. jest teraz Farey Sequence (II). To musi być pierwsza edycja! :-)
mellamokb
1
@mellamokb: Cóż, to wyzwanie kodowe, więc w żadnym wypadku nie koliduje tytuł. Ale tak, ten rodzaj odpowiedzi na moje pytanie.
Joey

Odpowiedzi:

5

J, 96

('F',],' = {0/1',', 1/1}',~('r';'/')rplc~', ',"1":"0@(3 :'}./:~~.,(%~}:\)i.1x+y')&".);._2(1!:1)3

( /:~~.,(%~}:\)i.>:x:ypodaje listę; reszta to We / Wy i formatowanie (ze złym stylem))

Na przykład:

4
3
1
2
F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}          
F1 = {0/1, 1/1}                         
F2 = {0/1, 1/2, 1/1}  

Edycje

  • (114 → 106) Bardziej wyraźne dołączanie,
  • (106 → 105) Cap [:to At@
  • (105 → 101) Usuń zbędną ":konwersję
  • (101 → 99) Użyj infiksu \dla listy
  • (99 → 96)
Eelvex
źródło
I dostać |value error: rplc. Jesteś pewien, że load 'strings'wcześniej tego nie robiłeś i nie zapomniałeś o tym?
Jesse Millikan
1
@Jesse: absolutnie. Nigdy (prawie) nigdy nie używam 'strings'. Używam tylko domyślnego środowiska linux-j-7.01.
Eelvex
Ugh ... przełączyłem się na j602 wdi teraz może być konieczne przełączenie z powrotem. :)
Jesse Millikan
3

Common Lisp, 156

(do((l()()))((not(set'n(read()()))))(dotimes(j n)(dotimes(i(1+ j))(push(/(1+ i
)(1+ j))l)))(format t"~&F~D = {0/1~{, ~A~}/1}"n(sort(delete-duplicates l)'<)))

(nowe linie nie są konieczne)

Bardzo brutalne, ale języki z rodzimymi racjonalnymi są do tego zaproszeniem.

Niegolfowany z komentarzami:

                                        ; at each iteration:
(do ((l()()))                           ; - reset l to nil
    ((not (set 'n (read()()))))         ; - read a term (nil for eof)
                                        ;   assign it to n
                                        ;   stop looping if nil
  (dotimes (j n)                        ; for j in 0..n-1
    (dotimes (i (1+ j))                 ;   for i in 0..j
      (push (/ (1+ i) (1+ j)) l)))      ;     prepend i+1/j+1 to l
  (format t "~&F~D = {0/1~{, ~A~}/1}"   ; on a new line, including 0/1,
                                        ; forcing the format for 1
          n                             ; print sequence index, and
          (sort                         ; sorted sequence of
           (delete-duplicates l)        ;   unique fractions
           '<)))                        ; (in ascending order)
JB
źródło
3

Python, 186 znaków

import sys
p=sys.stdout.write
while 1:
 a=0;b=c=x=1;d=y=N=input();p("F%d = {%d/%d, %d/%d"%(d,a,b,c,d))
 while y-1:x=(b+N)/d*c-a;y=(b+N)/d*d-b;p(", %d/%d"%(x,y));a=c;c=x;b=d;d=y
 p("}\n")
fR0DDY
źródło
+ 1, ale czy na pewno będzie to szybkie dla 10 ^ 6 liczby wejść?
Kichot,
@Debanjan Nie. To byłoby naprawdę wolne dla 10 ^ 6 wejść. Ma jednak złożoność liniową (pod względem liczby terminów).
fR0DDY
2

J, 156 135 117 112

d=:3 :0
wd;'F';(":y);' = {';(}.,(', ';2|.'/';|.)"1(<@":)"0(2)x:/:~~.,(-.@>*%)"0/~i.x:>:y),<'}'
)
d@".;._2(1!:1)3

j602 lub podobny ( wd). Wejście na stdin, wyjście na stdout.

Nadal zastanawiasz się, jak zagrać w golfa kod wyjściowy, który ma około 100 znaków.

Edycja: (156-> 135) Tacit-> wyraźne dla długich łańcuchów czasowników monadycznych, mniej generowania listy braindead

Edycja: (135-> 117) Znaleziono raze . Zajęło mi to wystarczająco długo. Obsługa przełączanych łańcuchów.

Edycja: (117-> 112) Nieco mniej braindeadowy sposób wykluczania ułamków powyżej 1. Niepotrzebne otwieranie.

Jesse Millikan
źródło
Może możesz pominąć jedną ze swoich dwóch x:?
Eelvex
@Eelvex: Lewy to 2 & x :, np. Podziel liczbę wymierną na licznik i mianownik.
Jesse Millikan
oic. Szkoda ... :(
Eelvex
2

Golfscript (101)

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'
mellamokb
źródło
2

Rubin, 110 108 102 97 94 92 91 89

#!ruby -lp
$_="F#$_ = {#{a=[];1.upto(eval$_){|d|a|=(0..d).map{|n|n.quo d}};a.sort*', '}}"
Lowjacker
źródło
Myślę, że powinieneś wypisać „0/1” i „1/1” zamiast odpowiednio „0” i „1”. Czy to działa tylko dla Ruby 1.9?
Eelvex
1
@Eelvex: Wyprowadza 0/1 i 1/1 w moim systemie. I tak, wymaga 1.9 (z powodu literałów postaci).
Lowjacker
1

Haskell, 148

f n="F"++show n++" = {"++(intercalate", ".("0/1":).map(\(i:%d)->show i++"/"++show d).sort.nub$[i%d|d<-[1..n],i<-[1..d-1]])++"}"
main=interact$f.read
Taylor Scott
źródło