Code-Golf: secuencia de la Farey (I)

10

Desafío

En esta tarea, se le dará un número entero N (menos de 10 ^ 5), generará la secuencia de Farey de orden N.

La entrada N se da en una sola línea, las entradas son terminadas por EOF.

Entrada

4
3
1
2

Salida

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}

Restricciones

  • El número de entradas no excedería 10 ^ 6 valores
  • Puedes usar cualquier idioma de tu elección
  • ¡La solución más corta gana!
Quijotesco
fuente
Esto se volverá muuuucho ..... la salida, quiero decir.
st0le
¿Se permite N = 0?
Eelvex
44
¿Qué pasa con el »(I)« en el título?
Joey
2
@Joey: Hmm. hay una secuencia de Farey (II) ahora. Debe ser la primera edición! :-)
mellamokb
1
@mellamokb: Bueno, ese es un desafío de código, así que no hay conflicto de títulos en ningún caso. Pero sí, ese tipo de respuestas a mi pregunta.
Joey

Respuestas:

5

J, 96

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

( /:~~.,(%~}:\)i.>:x:yda la lista; el resto es E / S y formato (con mal estilo))

P.ej:

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}  

Ediciones

  • (114 → 106) Anexos más claros,
  • (106 → 105) Cap [:to At@
  • (105 → 101) Eliminar ":conversión superflua
  • (101 → 99) Use infijo \para la lista
  • (99 → 96)
Eelvex
fuente
Consigo |value error: rplc. ¿Estás seguro de que no lo hiciste load 'strings'antes en la sesión y te olvidas de eso?
Jesse Millikan
1
@Jesse: absolutamente. Yo (casi) nunca lo uso 'strings'. Solo uso el entorno predeterminado linux-j-7.01.
Eelvex
Ugh ... Cambié a j602 por wdy ahora es posible que deba volver a cambiar. :)
Jesse Millikan
3

Lisp común, 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)'<)))

(líneas nuevas no necesarias)

Muy brutal, pero los idiomas con racionales nativos son una invitación a eso.

Ungolfed con comentarios:

                                        ; 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
fuente
3

Python, 186 caracteres

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
fuente
+ 1, pero ¿estás seguro de que será rápido para 10 ^ 6 número de entradas?
Quixotic
@Debanjan No. Sería realmente lento para 10 ^ 6 entradas. Sin embargo, es de complejidad lineal (en términos del número de términos).
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 o similar ( wd). Entrada en stdin, salida en stdout.

Todavía se desconoce cómo jugar al golf el código de salida, que tiene aproximadamente 100 caracteres.

Editar: (156-> 135) Tácito-> explícito para largas cadenas de verbos monádicos, menos generación de listas de muertos cerebrales

Editar: (135-> 117) Encontrado raze . Me tomó el tiempo suficiente. Se cambió el manejo de la cadena.

Editar: (117-> 112) Forma un poco menos inteligente para excluir fracciones anteriores 1. Innecesariamente abierto.

Jesse Millikan
fuente
¿Quizás puedas omitir uno de tus dos x:s?
Eelvex
@Eelvex: El izquierdo es 2 & x :, por ejemplo, divide un número racional en numerador y denominador.
Jesse Millikan
oic. Lástima ... :(
Eelvex
2

Golfscript (101)

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'
mellamokb
fuente
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
fuente
Creo que debería mostrar "0/1" y "1/1" en lugar de "0" y "1" respectivamente. Además, ¿esto solo funciona para ruby ​​1.9?
Eelvex
1
@Eelvex: Produce 0/1 y 1/1 en mi sistema. Y sí, requiere 1.9 (debido a los literales de caracteres).
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
fuente