Code-Golf: последовательность Фейри (I)

10

Вызов

В этом задании вам дадут целое число N (меньше 10 ^ 5), выведите последовательность Фари порядка N

Вход N указан в одной строке, входы заканчиваются EOF.

вход

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}

Ограничения

  • Количество входов не будет превышать 10 ^ 6 значений
  • Вы можете использовать любой язык на ваш выбор
  • Самое короткое решение побеждает!
донкихотский
источник
Это получится безошибочно ..... я имею в виду вывод.
st0le
Разрешено ли N = 0?
Eelvex
4
Что с »(I)« в названии?
Джои
2
@Джей: Хмм есть последовательность Фэри (II) сейчас. Должно быть первое издание! :-)
mellamokb
1
@mellamokb: Ну, это проблема кода, так что ни в коем случае не конфликтуйте с заголовком. Но да, такие ответы на мой вопрос.
Джои

Ответы:

5

J, 96

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

( /:~~.,(%~}:\)i.>:x:yдает список; остальное - ввод-вывод и форматирование (с плохим стилем))

Например:

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}  

Правки

  • (114 → 106) Более четкое добавление,
  • (106 → 105) Кепка [:к Ат@
  • (105 → 101) Удалить лишнее": преобразование
  • (101 → 99) Используйте инфикс\ для списка
  • (99 → 96)
Eelvex
источник
Я получаю |value error: rplc. Вы уверены, что не сделали этого load 'strings'раньше и забыли об этом?
Джесси Милликен
1
@Jesse: абсолютно. Я (почти) никогда не пользуюсь 'strings'. Я просто использую стандартную среду linux-j-7.01.
Eelvex
Тьфу ... Я переключился на j602 wdи теперь мне, возможно, придется переключиться обратно. :)
Джесси Милликен
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)'<)))

(переводы строки не нужны)

Очень брутально, но языки с местным разумом - приглашение к этому.

Разоблаченный с комментариями:

                                        ; 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
источник
3

Питон, 186 символов

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
источник
+1, но вы уверены, что это будет быстро для 10 ^ 6 входов?
Quixotic
@ Debanjan Нет. Это будет очень медленно для 10 ^ 6 входов. Это линейный по сложности (с точки зрения количества членов), хотя.
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 или аналогичный ( wd). Вход на стандартный вывод, вывод на стандартный вывод.

Все еще ломаю голову над тем, как играть в выходной код, который составляет около 100 символов.

Edit: (156-> 135) Tacit-> явный для длинных цепочек монадических глаголов, меньше генерация списка braindead

Редактировать: (135-> 117) Нашли никак . Взял меня достаточно долго. Переключена обработка строк вокруг.

Редактировать: (117-> 112) Чуть менее разумный способ исключить дроби выше 1. Ненужное открытие.

Джесси Милликен
источник
Может быть, вы можете опустить один из ваших двух x:с?
Eelvex
@Eelvex: левый - 2 & x :, например, разделить рациональное число на числитель и знаменатель.
Джесси Милликен
ова. Жаль ... :(
Eelvex
2

Гольфскрипт (101)

~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'
mellamokb
источник
2

Рубин, 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
источник
Я думаю, что вы должны вывести «0/1» и «1/1» вместо «0» и «1» соответственно. Кроме того, это работает только для ruby ​​1.9?
Eelvex
1
@Eelvex: на моей системе выводится 0/1 и 1/1. И да, требуется 1.9 (из-за литералов символов).
Lowjacker
1

Хаскелл, 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
Тейлор Скотт
источник