Code-Golf: séquence de Farey (I)

10

Défi

Dans cette tâche, vous recevrez un entier N (inférieur à 10 ^ 5), sortez la séquence de Farey d'ordre N.

L'entrée N est donnée sur une seule ligne, les entrées sont terminées par EOF.

Contribution

4
3
1
2

Production

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}

Contraintes

  • Le nombre d'entrées ne dépasserait pas 10 ^ 6 valeurs
  • Vous pouvez utiliser la langue de votre choix
  • La solution la plus courte gagne!
Chimérique
la source
Cela deviendra loooong ..... la sortie que je veux dire.
st0le
N = 0 est-il autorisé?
Eelvex
4
Quel est le »(I)« dans le titre?
Joey
2
@Joey: Hmm. il y a maintenant une séquence de Farey (II). Doit être la première édition! :-)
mellamokb
1
@mellamokb: Eh bien, c'est un défi de code, donc pas de conflit de titre en tout cas. Mais oui, ce genre de réponses à ma question.
Joey

Réponses:

5

J, 96

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

( /:~~.,(%~}:\)i.>:x:ydonne la liste; le reste est E / S et formatage (avec un mauvais style))

Par exemple:

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}  

Modifications

  • (114 → 106) Ajout plus clair,
  • (106 → 105) Cap [:à At@
  • (105 → 101) Supprimer la ":conversion superflue
  • (101 → 99) Utilisez infixe \pour la liste
  • (99 → 96)
Eelvex
la source
Je comprends |value error: rplc. Êtes-vous sûr que vous ne l'avez pas fait plus load 'strings'tôt dans la session et que vous l'avez oublié?
Jesse Millikan
1
@Jesse: absolument. Je n'utilise (presque) jamais 'strings'. J'utilise juste l'environnement linux-j-7.01 par défaut.
Eelvex
Ugh ... Je suis passé à j602 pour wdet maintenant je devrai peut-être revenir en arrière. :)
Jesse Millikan
3

Lisp commun, 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)'<)))

(nouvelles lignes non nécessaires)

Très brutal, mais les langues aux logiques natives sont une invitation à cela.

Non golfé avec des commentaires:

                                        ; 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
la source
3

Python, 186 caractères

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
la source
+ 1, mais êtes-vous sûr que ce sera rapide pour 10 ^ 6 entrées?
Quixotic
@Debanjan Non. Ce serait vraiment lent pour 10 ^ 6 entrées. Cependant, sa complexité est linéaire (en termes de nombre de termes).
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 ou similaire ( wd). Entrée sur stdin, sortie sur stdout.

Toujours perplexe sur la façon de jouer au golf le code de sortie, qui est de 100 caractères environ.

Edit: (156-> 135) Tacite-> explicite pour les longues chaînes de verbes monadiques, moins de génération de listes braindead

Edit: (135-> 117) Raze trouvé . Ça m'a pris assez de temps. Gestion des chaînes commutées.

Edit: (117-> 112) Un moyen un peu moins braindead d'exclure les fractions ci-dessus 1. Ouverture inutile.

Jesse Millikan
la source
Vous pouvez peut-être omettre l'un de vos deux x:s?
Eelvex
@Eelvex: celui de gauche est 2 & x :, par exemple, diviser un nombre rationnel en numérateur et dénominateur.
Jesse Millikan
oic. Dommage ... :(
Eelvex
2

Golfscript (101)

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

Ruby, 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
la source
Je pense que vous devriez sortir "0/1" et "1/1" au lieu de "0" et "1" respectivement. Est-ce que cela ne fonctionne que pour ruby ​​1.9?
Eelvex
1
@Eelvex: Il produit des sorties 0/1 et 1/1 sur mon système. Et oui, il nécessite 1.9 (à cause des littéraux de caractères).
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
la source