Deadfish - один из самых известных языков программирования, не соответствующих Тьюрингу. Он имеет только один аккумулятор (который начинается с 0) для хранения данных и только четыре команды:
i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator
Программа Deadfish может выглядеть так:
iiisdo
И это напечатало бы:
8
Соревнование
Создайте программу, которая будет вводить число и выводить код Deadfish для отображения числа. (Или создать функцию, которая принимает число в качестве параметра и возвращает код.) Оно должно работать для любого целого числа от 0до255
Цель
Постарайтесь сделать так, чтобы ваш код позволил создать самый короткий код для генерации заданного числа. Например:
iiiiiiiiio
а также
iiiso
каждый отпечаток 9, а второй короче.
счет
Ваш счет:
The number of characters in your source code +
The sum of the lengths of your output for all numbers from 1-255
-100 if the language you chose is Deadfish :)
Самый низкий балл побеждает!
В исходном соревновании у меня было только 6 чисел (9, 17, 9, 100 и 123). Это было из-за того, что я не хотел, чтобы все тестировали каждый номер, и я хотел, чтобы самый короткий код был актуален. Затем я понял, что программисты хороши в создании сценариев для тестирования подобных вещей, и я бы предпочел, чтобы это был конкурс на лучший алгоритм с игрой в гольф в качестве тай-брейка.
Поэтому я изменил это, как предложил Мартин Бюттнер.
источник
16^2 = 0или16^2 = 256или16^2 = error?-1ИЛИ256, тогда он будет сброшен до0. Но если вы нажмете число больше, чем256квадрат, то оно не изменится, например17^2 = 289. (см. страницу esolang)Ответы:
Perl,
132131 байт + 2036 байт = 2167Включает +2 для
-lpЗапустите с целевым номером на STDIN, например
deadfish.pl:
Grep - это фильтр, который немного ограничивает экспоненциальный взрыв (хотя этой программе по-прежнему требуется 2 ГБ для тяжелых случаев). Он также работает без, но я не могу запустить его на своем оборудовании, за исключением простых случаев. Но в принципе эта
110=108+2байтовая программа тоже работает:Список вывода:
источник
ES6 JavaScript 2126 + 311 = 2437 баллов
Semi-прокомментировал:
Это использует тот факт, что в Deadfish вы можете напечатать более одного символа.
Пример:
10компилируется вiodoкоторой есть «напечатать одно, уменьшить, напечатать ноль».Использование:
Вот данные вывода json:
Это было сгенерировано этим кодом:
который печатает
result = (the result)иc =вещь выше.Это получает удивительно высокий балл, несмотря на то, что он довольно прост. Он ищет ближайший идеальный квадрат, вычисляет квадратный корень этого идеального квадрата, добавляет 's' и соответственно увеличивает / уменьшает.
Старая версия, в которой не использовался тот факт, что «10» = «печатать один, печатать ноль»
источник
dнеправильно поняли эффект от операции - если она уменьшается-1, она сбрасывается0, а не255.oделает; выводит аккумулятор и символ новой строки.iodoвыходов1\n0\nнет10.o. Многие компиляторы (на разных языках) также не печатают новую строкуoMathematica,
254165 символов + 3455 = 3620Меньше гольфа:
Я считаю, что полученные цифры являются оптимальными. Он выполняет поиск в ширину по всем 256 числам, отслеживая кратчайший способ представления каждого числа. Поиск строит своего рода таблицу поиска в функции
gкоторая затем применяется к вводу.Для справки, вот все 255 результатов:
источник
n > 256нетn ≥ 256. И это также согласуется со страницей esolang: «Хотя комментарий в реализации C гласит/* Make sure x is not greater then [sic] 256 */, реализация устанавливает значение в ноль, если и только еслиvalue == -1 || value == 256».d, поэтому выведите 0.C, код 433 + выход 3455 = 3888
C ++, код 430 + выход 3455 = 3885
А сейчас нечто соверешнно другое.
Я использовал вывод ответа Мартина из Mathematica (обновлен 23 октября, так как раньше он был неверным для 240+). Мой вывод такой же 3455 символов. Я проанализировал закономерности в выводе и обнаружил, что [0,255] может быть представлено этой последовательностью:
iсsсiс илиdсsсiили 0-16dсoСледующий шаг был тщательно построить эти пять столбцов (
cчерезgв коде ниже). Я использовал отрицательные числа, чтобы указать,dа неiв столбцахeиg. Затем оказывается, что результаты работают в основном как счетчик вgстолбце, поскольку каждая строкаuобычно удаляет одинdили добавляет одинiотносительно предыдущей строки (v). Существует 15 исключений, которые хранятся вx(индексах) иb(пять столбцов, упакованных в целое число, для хранения которого требуется максимум 14 битов).10832).Например, первое «исключение» - это самая первая строка, где мы хотим получить ноль символов, кроме окончания
o. Так чтоx[0]есть0, иb[0]есть544, что при распаковке (стиль "little endian", так какgявляется столбцом подсчета){ 32, 0, 4, 0, 0 }. Мы всегда вычитаем 32 изgи 4 из,eчтобы заставить битовые поля без знака работать (то есть эти два столбца концептуально представляют отрицательные числа, когдаdтребуется вместоi, но в реализации значения смещены, чтобы избежать фактических отрицательных чисел).Вот таблица, показывающая, как работают первые десять чисел (пробелы - нули):
Вы можете видеть, что в
gосновном это просто увеличение на единицу для каждой новой строки, но некоторые строки (0, 4, 8, ..., которые я кратко надеялся найти в OEIS) «сбрасывают» последовательность, что означаетgпринимают какое-то новое значение и по крайней мере, еще один столбец также изменен.Количество символов кода исключает пробелы, кроме обязательного символа новой строки перед каждым
#и пробела послеunsignedиint. Вы можете сохранить 3 -х символов при компиляции в C ++ вместо C, заменяя<stdio.h>с<cstdio>, и*(int*)&uс(int&)u.Интересный факт об этом коде: более ранняя версия использовала массив из 256 объединений вместо just
uиv. Эта версия заставила GCC 4.7.2 создать внутреннюю ошибку компилятора! Однако в GCC 4.9 это было исправлено, и приведенный выше код работает с любой версией.источник
for(...)наscanf- это уменьшит количество символов).#include, и, возможно, вы могли бы сделатьstructизнутриunionненазванное.forЦикл по - прежнему требуется из - за того , как я вычислить результат. Этот плюс отмены имен структуры сохранил 5 символов; еще 2 были сохранены путем изменения==к>и удалению задней новой строки. :) Программа полностью действительна только в C99, потомуmainчто не возвращает явно значение; удаление#includeрезультатов в ошибке из-заscanf()сейчас.256.Haskell,
220021772171 = 2036 + 135это работает, имея бесконечный список всех мертвых программ, отсортированных по их длине, сопровождаемых внутренним состоянием и выводом. функция
fищет список и возвращает первую запись, которая соответствует.этот подход учитывает множественность
oв каждом результирующем коде, но не ограничивает его либо печатью всех цифр отдельно, либо печатью целого числа сразу. например, здесь 216 имеет кодiiosso.Редактировать:
согласно спецификации, когда состояние 256 (но не 257), оно превращается в 0. Теперь мой код принимает это во внимание. например, 160
iissoso.это имеет несколько проблем эффективности; потому что
lэто список верхнего уровня, все элементыlкоторого были оценены, остаются в памяти, и поэтому в какой-то момент времени выполнения, вероятно, не хватит памяти.чтобы подсчитать счет, я сделал эквивалентную, но менее загруженную памятью версию.
Мой более эффективный код работает путем пересчета списка в каждом приложении
f, так что сборщик мусора может выбросить уже найденную часть списка. в некотором смысле это поиск в ширину с использованием лени.более эффективный код также добавляет некоторые дополнительные ограничения к элементам списка - он отфильтровывает все коды, которые содержат
idилиdi, или содержат,sкогда состояние меньше 2.Редактировать:
я переместил
gфункцию с верхнего уровня на функцию помощникаf', поэтому теперьgфильтрует коды, которые печатают что-то, что не является префиксом нашего разыскиваемого числа. теперь код намного быстрее.более эффективный код:
обратите внимание, что более эффективный код не будет иметь одинаковых результатов, потому что программы пересекают все возможные коды в другом порядке. однако они будут выводить коды одинаковой длины. также, переключаясь
c:xсx++[c]делает программы эквивалентными.с помощью этого кода я смог вычислить все программы за
520,81 секунды.Редактировать: по-
видимому, это лучший ответ! я заметил это только сейчас, так далеко от того, когда это спросили ...
результаты:
источник
Picat 516 + 2060 = 2576
Это несколько модифицированная версия программы Сергея Дымченко . Эта версия выводит более компактные программы Deadfish.
Насколько я понял предложение «длины выходов», это означает, что я должен суммировать вывод без символов новой строки.
Использование:
1-255 Коды:
Спектакль:
Версия программы для измерения времени:
Результат:
Полный вывод:
источник
ioioпечатает"12"и не печатает"11"JavaScript (E6) 141 + 3455 = 3596
Рекурсивная функция ищет ближайший квадратный корень, но избегая 16 при 16 * 16 = 256, будет изменено на 0. Многие другие ответы не получают эту точку.
Тест в консоли FireFox / FireBug
Выход
источник
Пикат, код 242 + выход 3455 = 3697
См http://picat-lang.org/ для получения информации о Picat.
Меньше гольфа:
источник
Питон 3 - 4286 + 168 = 4454
Не слишком серьезный, но чрезвычайно простой. Просто находит лучший из добавления к 0, квадрат, 4 й степени
и 8 й степени,РЕДАКТИРОВАТЬ: Golfed 75 байт, 8- й степени ничего не сделал
РЕДАКТИРОВАТЬ 2: Удалены некоторые байты для правильной реализации
d. Оценка увеличилась, хотя.Питон 3 - 2594 + 201 = 2795
Этот использует поиск в глубину, чтобы найти самую короткую программу. Я добавил некоторые (ненужные?) Оптимизации, чтобы получить результат; Таким образом, не нужно проходить так много путей. Могу попытаться удалить некоторые из них. Не превосходит JS, так как использует умные трюки, такие как множественные
o.РЕДАКТИРОВАТЬ: Гольф от 93 байтов, у меня, по-видимому, остался бесполезный код при разработке. Также удалены все, что я нашел ненужным до сих пор. Вот и я, JS.
РЕДАКТИРОВАТЬ 2: Гольф от еще 8 байтов. Что
returnбыло ненужно.РЕДАКТИРОВАТЬ 3: Golfed дополнительные 5 байтов. Теперь, когда мы избавились от этого, один мог просто поставить
elifвместо другогоreturn.РЕДАКТИРОВАТЬ 4: Исправлена функциональность
d. Размер увеличен на 1 байт, оценка на несколько байт.источник
APL: 80 + 3456 = 3536
Объяснение: (исправлено после примечания edc65, спасибо)
4 <4: ⍵⍴'i 'Если аргумент меньше 3, повторить «i» много раз
(⌈, ⌊) ⍵ * .5 ⍵ - аргумент, возьми квадратный корень и возьми потолок и пол
| ⍵-2 * ⍨ возвысь потолок и этаж до степени 2, убери аргумент и сделай позитивный
b ← ⊃ (>, <, =) / получить логический вектор с a> b, a
(⍵> 240) ⌽ Чтобы избежать перехода к 256, введите «i» для чисел свыше 240 вместо ^ 2
b / 'ids' используют это логическое значение, чтобы взять i, d или s и добавить его к решению с помощью,
, ∇ (-⊃b) + b [2] + ⍵ * ÷ 1 + 3⊃b Рекурсивно вызывать функцию с аргументом -b 1 + b [2], повышенным до степени (обратной b [3] +1)
Может рассчитывать вывод с:
¨ применяет функцию к каждому номеру 0-255
+ / ⊃, / ⍴¨ подсчитывает общее количество элементов
Опять же, вы можете попробовать все вышеперечисленное на TryApl.org
Кстати: это 3456, а не 3455, потому что я тоже рассматриваю 0, так как я думаю, что проблема была в том, Если это 1-255, то результат 80 + 3455 = 3535
источник
Python 2712 = 2608 + 104
Код:
Использование:
Код 0-255:
источник
CJam,
2436 2392 22962173 ( 74 символа + 2099)Что переводится как:
Пытается оптимизировать длину кода Deadfish, выбирая кратчайший путь для достижения каждой цифры числа.
Спасибо Мартину за перевод Unicode
Вот полный список кода
Попробуйте это онлайн здесь:
источник
oпечатает перевод строки. Все компиляторы также просто печатали без новой строки.C printf("%d\n",x);C# Console.WriteLine(x)GO fmt.Println(x)pascal WRITELN(val);python print accumulator (no comma)bash echo $no;; (no -n)