Решая задачки на projecteuler.net столкнулся с такой проблемой.
Задача №35:
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
написал функции:
primes =: i.&.(p:^:_1) 1e6 NB. список простых чисел до миллиона
list =: (#~ *./@(e.&'1379')@":"0) primes NB. выкинем все, в которых есть цифры отличные от 1,3,7,9 (к результату потом надо добавить числа 2 и 5)
m =: (".)@((|."0 1)~ (i.)@#)@(":)
m генерирует список списков циклических перестановок, то есть, например
дальше я хочу сделать следующую вещь.
Подзадача: написать функцию, которая будучи примененной к списку, даст для каждого элемента 0 (если хотя бы одна циклическая перестановка отсутствует в списке) или 1 (если они все там есть), затем по этому списку выберу нужные мне элементы :)
так вот... рассмотрим частные случаи:
(m 13) e. (13 31 133) NB. обе перестановки числа 13 есть в списке, применяя AND, получаем, что 13 удовлетворяет условиям подзадачи
1 1
(m 313) e. (13 31 133) NB. только одна из трех перестановок числа 313 есть в списке, применяя AND, получаем, что 313 не удовлетворяет условиям подзадачи
0 1 0
Но!
(m"0 (13 313)) e. (13 31 133) NB. если после этого применить AND к строчкам, то неправильный ответ
1 1 0
0 1 0
Куда и как воткнуть этот *./ (выполняющий роль AND для списка) и с каким рангом, чтобы он выполнился до построения таблицы и в итоге получился список или одномерная таблица из 0 и 1, я ума не приложу.
И еще, как записать
Теперь собственно к проблеме:
AL>написал функции: AL>
AL> primes =: i.&.(p:^:_1) 1e6 NB. список простых чисел до миллиона
AL> list =: (#~ *./@(e.&'1379')@":"0) primes NB. выкинем все, в которых есть цифры отличные от 1,3,7,9 (к результату потом надо добавить числа 2 и 5)
AL> m =: (".)@((|."0 1)~ (i.)@#)@(":)
AL>
Я поменял list:
list =: 2,(0{l),5,}.l=.(#~ *./@(e.&'1379')@":"0) primes NB. выкинем все, в которых есть цифры отличные от 1,3,7,9 (и вернем на место числа 2 и 5)
но, к вопросу это отношение не имеет.
AL>так вот... рассмотрим частные случаи: AL>
AL> (m 13) e. (13 31 133) NB. обе перестановки числа 13 есть в списке, применяя AND, получаем, что 13 удовлетворяет условиям подзадачи
AL>1 1
AL> (m 313) e. (13 31 133) NB. только одна из трех перестановок числа 313 есть в списке, применяя AND, получаем, что 313 не удовлетворяет условиям подзадачи
AL>0 1 0
AL>
AL>Но! AL>
AL> (m"0 (13 313)) e. (13 31 133) NB. если после этого применить AND к строчкам, то неправильный ответ
AL>1 1 0
AL>0 1 0
AL>
Это вполне нормальное поведение, честно говоря не понятно, что ты ожидал тут получить применяя m"0
AL>Куда и как воткнуть этот *./ (выполняющий роль AND для списка) и с каким рангом, чтобы он выполнился до построения таблицы и в итоге получился список или одномерная таблица из 0 и 1, я ума не приложу.
Да бог с ней таблицей, пусть себе строится. Тебя смущают лишние нули? Дык, можно не только на вхождения проверять, но и на их отсутствие
Но я бы вообще к списку привязываться не стал. Ведь есть функция проверки числа на простоту:
x p: y
NB. x=0: 0 if y is prime, 1 otherwise
NB. x=1: 1 if y is prime, 0 otherwise
ie>Пока обедал, понял что намудрил, достаточно так: ie>
ie>(#~ -. @ (+./ @ (0&p:) @ m"0)) list
ie>
ну да, так работает, но приходится заново определять, простое ли число — не самый эффективный вариант.
кажется, я понял в чем штука. если писать
(m"0 e.~) list
то в таком варианте е. применяется уже к таблице (поэтому поздно вставлять И). А надо, чтобы это происходило сразу после генерации перестановок.
Вот так работает
(#~ (*./)@(e.&list)@(m"0)) list
И еще один вопрос можно?
Как прервать процесс выполнения какой-либо функции, если создается впечатление, что перемудрил и она будет считаться очень долго. Убивать интерпретатор и терять все что написал, как-то не хочется
Здравствуйте, AutumnLeaf, Вы писали:
AL>ну да, так работает, но приходится заново определять, простое ли число — не самый эффективный вариант.
А определить присутствует ли число в 1111 элементном массиве быстрее? Спорно...
AL>И еще один вопрос можно? AL>Как прервать процесс выполнения какой-либо функции, если создается впечатление, что перемудрил и она будет считаться очень долго. Убивать интерпретатор и терять все что написал, как-то не хочется
Здравствуйте, AutumnLeaf, Вы писали:
AL>Как прервать процесс выполнения какой-либо функции, если создается впечатление, что перемудрил и она будет считаться очень долго. Убивать интерпретатор и терять все что написал, как-то не хочется
Вроде бы в 6-й версии они добавили утилиту jbreak, которая позволяет делать именно такую штуку
AutumnLeaf,
AL>И еще один вопрос можно? AL>Как прервать процесс выполнения какой-либо функции, если создается впечатление, что перемудрил и она будет считаться очень долго. Убивать интерпретатор и терять все что написал, как-то не хочется
Quintanar,
Q>А в чем прикол таких обозначений? Реально писать нисколько не меньше, а результат даже лучше. Вот на q это вычисляется так, например:
Нет, в данном (довольно специфичном случае) Q хуже, потому как натыкать стилусом "tmp[;0] ..." более напряжно, чем аналог на J. Хотя вот лично мне определения функций в K (в Q такой же?) нравятся больше.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Нет, в данном (довольно специфичном случае) Q хуже, потому как натыкать стилусом "tmp[;0] ..." более напряжно, чем аналог на J. Хотя вот лично мне определения функций в K (в Q такой же?) нравятся больше.
На K тоже можно покороче (в Q вроде есть режим совместимости с К).
Здравствуйте, Трурль, Вы писали:
Т>(в Q вроде есть режим совместимости с К).
k)primes@&&/'isprime"I"${(!#x).q.rotate\:x}'$primes
/ 0$ -> "I"
/ is_prime@ -> isprime @ - no need, _ - forbidden
/ ! -> .q.rotate (! is used for dictionaries)
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
