Эти номера Ружья представляют собой последовательность с довольно простым определением , но некоторые интересными структурами. Начните с натуральных чисел:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
Теперь возьмите все числа с индексами, кратными 2 , сгруппируйте их в пары и поменяйте местами числа в каждой паре:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
^ ^ ^ ^ ^ ^ ^
<---> <---> <-----> <----
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
Теперь сделайте то же самое с индексами, кратными 3 :
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
^ ^ ^ ^
<------> <--------->
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
А потом для 4 , 5 , 6 и так далее:
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
1, 4, 8, 6, 5, 3, 7, 2, 10, 12, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 3, 7, 2, 10, 5, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 14, 7, 2, 10, 5, 11, 3, 13, 16, ...
...
После k таких шагов первые k + 1 числа будут зафиксированы. Таким образом, мы можем определить бесконечную последовательность чисел дробовика как предел, позволяющий k перейти в бесконечность. Первые 66 номеров:
1, 4, 8, 6, 12, 14, 16, 9, 18, 20, 24, 26, 28, 22, 39, 15, 36, 35, 40, 38, 57, 34, 48, 49, 51, 44,
46, 33, 60, 77, 64, 32, 75, 56, 81, 68, 76, 58, 100, 55, 84, 111, 88, 62, 125, 70, 96, 91, 98, 95,
134, 72, 108, 82, 141, 80, 140, 92, 120, 156, 124, 94, 121, 52, 152, 145, ...
Интересный факт: Несмотря на то, что эта последовательность получается только путем перестановки натуральных чисел, она не содержит простых чисел.
Соревнование
По заданному целому числу n > 0
найти n
номер дробовика. Вы можете написать программу или функцию, получая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и возвращать вывод или выводить его в STDOUT (или ближайшую альтернативу).
Это код гольф, поэтому выигрывает самое короткое представление (в байтах).
Leaderboards
Это дает больше ответов, чем я думал, а также несколько человек соревнуются на одном языке. Итак, вот фрагмент стека для генерации как регулярной таблицы лидеров, так и обзора победителей по языкам.
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
# Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
# Ruby, <s>104</s> <s>101</s> 96 bytes
function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=0,c=0,p=-1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);t++;c=p==o?c:t;i=i.replace("{{PLACE}}",c+".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);p=o;$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=47338;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>
10
,21
,25
и30
не появляются либо, например.k
й-й итерации,k
й-й элемент в массиве перемещается в т-2k
ю позицию и больше не будет касаться до2k
итераций, когда он будет транспонирован в т-4k
ю позицию до бесконечности. Простое число не транспонируется до тех пор, пока не наступит его очередь, так что все простые числа перемещаются вперед. Но мы можем легко составить список невинных жертв, просто распечатав первый элемент для транспонирования на итерации 2 и каждой нечетной итерации. Список идет: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ...Ответы:
Пиф, 19
22Довольно наивная реализация ответа @ PeterTaylor's golfscript .
Попробуйте онлайн здесь
При этом используются те же приемы для преобразования цикла while в сгиб, что и в другой программе Pyth, представленной ниже.
Наивная копия алгоритма @ Sp3000, переведенная на Pyth.
Вы можете попробовать это онлайн здесь
Использует уменьшение (имя Python для свертывания) для эмуляции цикла while. Он перечисляет, над
range(input, 2)
чем работает Pythrange(2, input)[::-1]
. Другой Pyth связанных гольф предполагают использованиеnot
вместо<2
и используяy
«ы режим удвоения значения числовых аргументов скрыты.источник
> <>,
5245 байтСтраница Esolangs для> <>
Благодаря нескольким модулям и необходимым умножениям происходит много копирования и перемещения элементов. Логика точно такая же, как и у моего решения на Python .
Принимает ввод через кодовую точку из STDIN, например
"!" = 33 -> 75
.источник
-v
считается три: /Python 2, 58 байт
Как и большинство других ответов, идея состоит в том, чтобы работать задом наперед.
Давайте назовем шаг
k+1
stepi
, так что на шагеi
все кратныеi
поменялись местами. Нам нужно два простых наблюдения:n
в массиве местами только на этапе ,i
еслиn
делится наi
,n/i mod 2
. Если это 1, то у вас меньшее число (и оно будет меняться), в противном случае вы будете иметь более высокое число (и оно будет меняться).Это дает нам алгоритм для работы в обратном направлении. Давайте попробуем это с 6, начиная с последнего шага (шага
i = 6
):Итак, теперь мы знаем, что число пришло с позиции 12. Тогда:
Итак, теперь мы знаем, что это произошло с 16 до этого. В заключение:
Так как это первый шаг (помните
k+1
), мы закончили, и число, которое заканчивается в позиции 6, первоначально пришло из позиции 14, то есть номер 6-го ружья равен 14.Итак, теперь для объяснения Python:
источник
i-1
как~-i
while
. Хорошая работа, Sp3000.u+G**H!%GHty%/GH2rhQ2Q
Haskell, 68 байт
Вероятно, дальше гольф, особенно в первом ряду. Это определяет функцию,
s
которая принимаетn
и возвращаетn
номер дробовика.объяснение
Вспомогательная функция
#
принимает два числаn
иk
и возвращаетk
th-е число в списке, определенном путем применения операции парного обмена к каждомуn
th-му числу. Например, применяя его к первым 20 числам,n = 4
получим следующее:Результат
s n
получается путем сокращения («сворачивания») списка с[2..n]
помощью функции второго порядка(.).(#)
, которая принимает числоm
и функциюf
(первоначально тождественную функциюid
) и возвращает функцию, которая принимаетk
и возвращаетf (m # k)
. Например, в случае,n = 4
если список[2,3,4]
сводится к функции, которая принимаетk
и возвращаетid (4 # (3 # (2 # k)))
. Требуетсяid
только для базового случаяn = 1
, когда список пуст. Наконец, мы даем этой функции входk = n
, получаяn
номер дробовика.источник
CJam, 32 байта
Просто следуя спецификации к сути. Выполнение инструкций на большем наборе, чтобы не влиять на n- е число.
Попробуйте онлайн здесь
источник
Рубин, 92 байта
Мой первый опыт игры в гольф. Не основано ни на каком другом ответе.
Теперь, когда я посмотрел на некоторые другие, я заметил, что большинство просто определяют функцию, а не полную программу, которая принимает ввод и производит вывод. ОП попросил полную программу с вводом и выводом. Принято ли игнорировать такие требования?
84 байта
Посмотрев на другие ответы и поняв, что итеративное решение возможно.
источник
ARGV
в$*
магический глобальный. 2. Этоto_s
ненужно. 3. Вместо того,d
чтобы назначатьn
на отдельной строке, просто сделайте,d=n=...
чтобы сбрить символ. Хорошая работа для вашего первого гольфа! :)n+=
строке не нужны, и оба случая==0
можно смело изменить на<1
.Python 2,
9779 символовДля каждого индекса он определяет правильное значение, рекурсивно преследуя число в обратном направлении. Алгоритм был обнаружен независимо.
редактировать: теперь он печатает только
n
номер вместо первыхn
чисел. Конечно, итеративный подход будет короче, но я не хочу копировать код Sp3000.источник
g(i,i)
часть особенно раздражающей, хотя ...print
утверждения.Haskell, 79 байтов
Использование:
p 66
какие выводы145
Объяснять особо нечего: функция
#
рекурсивно вычисляет номер ружья в положенииi
шагаs
.p n
возвращает число в позицииn
шагаn
.источник
к, 41 байт
{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}
{...}
лямбда, х и у неявный 1-й и 2-й аргумент$[b;t;f]
троичный оператор, оценивает b с последующим t / f соответственноb!a
по модулю б_
этаж, приводит результат деления к int%
деление{...}/[x;y]
простое число {...} с x и применение к списку y, эквивалентно f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]|
обратный!
Функция йота, генерировать список от 0 до n-1источник
Common Lisp,
11391(повторяется: 91)
(оригинал, рекурсив: 113)
пример
С рекурсивной версией:
тесты
Проверки и меры для итерационной версии:
источник
Mathematica,
5349 байтовЯ решил сыграть в свою референсную игру Символ
∣
Unicode для «делит» и имеет значение 3 байта. В противном случае используется тот же алгоритм, что и у всех остальных.Он определяет безымянную функцию, которая принимает
n
в качестве единственного параметра и возвращаетn
номер дробовика.источник
GolfScript, 27 символов
объяснение
Если
f(i, n)
это значение в позицииn
послеi-1
преобразований, мы имеемгде
^
обозначает побитовый xor; учитывая вводn
, мы хотим вычислитьf(n, n)
.Преобразование из рекурсивной функции в цикл неинтересно; Что интересно, так это способ, которым
можно переписать Более очевидный подход состоит в том, чтобы сказать, что это должно быть
для некоторых
g
. Очевидно,g
чередуется между1
и-1
, так как позиции меняются поочередно вверх и вниз; так какg(1) = 1
(потому что1
поменяется2
) мы имеемгде
**
обозначает возведение в степень. Окончательные сбережения прибывают из переписывания этого какрассечение
источник
u-G*H^_!%GH/GHrhQ2Q
Если вы не хотите публиковать это сами, скажите мне / добавьте это в ответ CW.CJam, 24 байта
Онлайн демо
Это порт моего ответа на GolfScript , заимствующий цикл из ответа Мартина CJam и использующий
divmod
оператор CJam . ( Я сказал, что это будет полезно!).источник
Юлия,
6157 байтЭто создает безымянную функцию, которая принимает один аргумент
n
и возвращаетn
номер дробовика. Чтобы назвать его, дайте ему имя, напримерf=n->(...)
.Примеры:
В настоящее время это основано на удивительном Python-ответе @ Sp3000 . Я скоро вернусь к этому, потому что в Джулии должен быть более короткий способ сделать это, чем то, что я сделал здесь. Любой вклад приветствуется, как всегда.
источник
GML, 76 байт
Информация о GML
источник
CJam,
2827 байтТак что это немного смущает ... перед тем как опубликовать это, я сам попробовал сыграть в гольф и получил 30 байтов в CJam. Ни один из существующих ответов еще не победил. Тем временем мне также удалось сбрить еще три байта. В комментарии есть более короткое решение Pyth, но в ответ не было добавлено ничего более короткого, так что вот оно. Может быть, это вдохновляет людей APL / J попытаться немного усерднее (или кто-то действительно публикует решение Pyth), прежде чем я приму свой ответ. ;)
Проверьте это здесь.
объяснение
источник
J,
3432 байтаПопробую немного поиграть в гольф и добавить некоторые объяснения позже.
Попробуйте это онлайн здесь.
источник
TI-Basic 83/84, 40 байтов
Информация о TI-Basic
источник
Рубин,
5747 байтПо сути, это решение Python для Sp3000 (с предложением xnor ) переведено на Ruby. Я мог бы, вероятно, сыграть в гольф в нескольких местах.
источник