задача
Кодируйте строку, которая полностью состоит из прописных букв ( A-Z
), используя только нули и единицы, используя вашу собственную любимую схему. Но правило не так просто!
правила
- Ваша программа / функция должна правильно обрабатывать любую допустимую строку ввода длиной 8 .
- Результаты должны иметь одинаковую длину для всех входных данных.
- Результаты должны отличаться для разных входов.
- Результаты должны быть максимально короткими.
- Результаты должны быть равны нулю (иметь количество единиц, сходных с нулями). Они не должны быть равными (то есть идеально сбалансированными), но ваш счет будет оштрафован за это.
Вам не нужно предоставлять программу / функцию, которая декодирует вашу кодировку.
Вход и выход
- Вы можете принять любой набор из 26 различных печатаемых символов ASCII вместо
A-Z
. - Вы можете решить вывести любую пару различных печатаемых символов ASCII вместо
0
и1
. - Вам не разрешено выводить целое число вместо битовой строки, так как оно может иметь начальные нули, и неясно, действительно ли вы выполнили правило 2.
- Если вы решили отклониться от значения по умолчанию (
A-Z
ввод и01
вывод), вы должны указать наборы символов ввода / вывода в своем представлении.
счет
- Базовая оценка: размер кода или 1, если ваша программа пуста.
- Штрафы
- Штраф за длину: умножить
1.5 ** (encoded length - 42)
- Там нет бонуса за то, что короче; 42 - минимальная длина для идеально сбалансированного кодирования строк длиной 8 с размером алфавита 26.
- Штраф за несбалансированность: умножить
2 ** max(abs(ones - zeros) for every valid input of length 8)
, гдеones
иzeros
- это числа 1 и 0 в каждом выходе соответственно. - Ваша заявка должна содержать либо пример наихудшего случая (вход / выход), либо теоретическое объяснение значения штрафа.
- Штраф за длину: умножить
- Самый низкий балл побеждает.
Пример представления
Гипотетический esolang, 0 байт, оценка 74733,8906
Вот гипотетический esolang, где пустая программа печатает все ASCII-коды символов ввода в двоичном виде.
Например, если вы дадите в AAAAAAAA
качестве ввода, программа будет печатать 1000001
8 раз подряд, т.е.10000011000001100000110000011000001100000110000011000001
.
Входной алфавит выбран, чтобы быть CEFGIJKLMNQRSTUVXYZabcdefh
. Таким образом, все символы конвертируются в семизначные числа в двоичном виде, а счетчики с нулем один отличаются только на единицу на символ (все они имеют три единицы и четыре нуля или наоборот при преобразовании в двоичную форму).
Длина выхода всегда равна 56, и на входах возникает дисбаланс в худшем случае, например CCCCCCCC
, где нули появляются в 8 раз чаще, чем единицы.
Таким образом, оценка этого представления 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906
.
источник
Ответы:
Stax , 11 байт, 0 пенальти, оценка 11
Эта программа использует
[0-9A-P]
для ввода и[01]
для вывода.Запустите и отладьте его онлайн - нажмите кнопку « Выполнить» , чтобы начать. Первые четыре теста выполняются за миллисекунды. Пятое за секунды. Шестой в тысячелетиях.
Соответствующее ascii представление этой программы таково.
Он сильно опирается на
|N
инструкцию, которая получает последующую перестановку массива.Все выходы являются перестановками исходной строки. Имеет 21 ноль и 21 единицу. Поэтому все выходы имеют 42 символа и идеально сбалансированы.
источник
Желе , 19 байт
Попробуйте онлайн!
объяснение
источник
Pyth,
201914 байтов, Макс. Разность: 0, длина: 64, оценка:149636,5528142154,7251104745,5869Попробуйте онлайн!
Использует строчные буквы алфавита (
[a-z]
) вместо прописных. Можно использовать прописные путем заменыG
сrG1
ценою 2 байта.Я мог бы перевести ответ HyperNeutrino на Python 3 для лучшего результата, но, честно говоря, я хочу получить ответ, который действительно работает.
источник
Python 2 ,
779645 байт, Макс (разность) = 0, длина = 48, оценка = 7346,95Попробуйте онлайн!
Магическое число
4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33
(в базе 36) или его десятичный эквивалент382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271
кодирует все 252 перестановки по 50
с и 51
с.Алгоритм сначала конвертируется
A-Z
в0-25
и обрабатывает его как число с основанием 26, а затем добавляет56*252**4
.Затем число преобразуется в 5-значное число с основанием 252 и заменяется соответствующей перестановкой 5
0
с и 51
с.После этого удалите первые 2 бита, что гарантированно будет
01
. Затем мы закодировали строку в 48-битную строку, которая состоит ровно из 240
с и 241
с.источник
7346.953125
).JavaScript (ES8), оценка 22186,623779296875
При вводе четной длины всегда выводится 3,5 * нулей и единиц, поэтому он платит только штраф 1,5 ** 14. Поддерживаемые символы:
'+-.3569:<GKMNSUVYZ\cefijlqrtx
.источник
Желе , 16 байт
Используется
+,-./0123456789:;<=>?@ABCD
для ввода и возвращает список единиц и нулей.Это попытается создать список из 538 257 874 440 комбинаций в памяти, поэтому вам потребуется большой объем оперативной памяти, чтобы запустить его как есть ...
Попробуйте онлайн! (тестируемый; длина ввода 3, длина вывода 18)
Как это устроено
источник
Python 3 ,
985135 байтов, Max Diff 0, длина 42, оценка 135Попробуйте онлайн!
Предоставлено Bubbler
Код Ungolfed:
Поскольку другие подходы кажутся совершенно неэффективными, я попытался сделать оптимальный по времени. Это просто O (N) в N битах кодирования, что является оптимальным для big-O.
Подсказка: попробуйте подумать о треугольнике Паскаля для этого ( эта диаграмма показывает это)
Пример выходов:
Время выполнения: <0,013 с (примерно постоянно для всех входов)
источник
Perl 5 , 55 байтов, max diff 0, длина 42, оценка
5655Это работает, но займет много времени, но выполнимо (
ZZZZZZZZ
на моем компьютере это заняло 2,5 дня). Память не проблема.Используется
A-Z
как ввод и1
иA
как кодировка символов. Они всегда идеально сбалансированы. Пропускает первые26^7 = 8031810176
сбалансированные комбинации, представляющие строку длиной менее 8 символов, но это нормально, так как они538257874440
доступны, и я использую208827064575
и208827064575 + 8031810176 < 538257874440
.Однако на самом деле он «рассчитывает» до целевой комбинации, которая займет очень много времени. Вот почему в ссылке TIO я использовал только слишком короткую входную строку (которая также поддерживается), чтобы продемонстрировать, что вывод правильный. Будет работать чуть больше, чем
AAAAAA
до истечения времени ожидания TIO.ZZZZZZZZ
должно быть примерно в26^3 = 17576
разы медленнее.Попробуйте онлайн!
Декодер почти такой же:
Попробуйте онлайн!
источник
> <> , 75 байтов, Макс. Разность 0, длина 42, оценка 75
Попробуйте онлайн!
Честное предупреждение, это займет очень очень очень много времени, чтобы завершить даже для тривиального
AAAAAAAA
случая. Выполняется через каждое двоичное представление счетчика, пока не1
будет достигнуто ( двоичное представление входа 26) двоичное число с 21 с. Если вы хотите немного протестировать программу, вы можете заменитьab+
строку в третьей строке,1
которая будет возвращать n-ное двоичное число всего одним1
, попробуйте онлайн!источник
Python 3 , 75 байт, Max Diff 0, длина 42, счет 112
Попробуйте онлайн!
Это работает только в теории из-за ограничений памяти. Существуют
538257874440
четкие сбалансированные ноль-единичные строки длиной 42 и208827064575
возможные входы, поэтому некоторые из возможных выходов не будут использоваться.-37 байт благодаря @recursive
источник
int(s,26)
для своего индекса значение, а неsum(...)
если вы измените свой набор символов ввода.[0-9A-P]
, не так ли? На моей машине,int("123ABC",26) == 12855114
C ++, 146 байт, 42 maxlength, 0 дисбаланс, оценка 146
Работает для любого непрерывного 26 символов, но предупреждает, что оно работает недопустимо
источник
#include<algorithm>
на#import<regex>
.