Это другой тип задачи сжатия. В обычном вызове колмогоровской сложности вам необходимо воссоздать список точно. Здесь вам разрешено округлять значения любым удобным для вас способом. В чем подвох? Ваша оценка оштрафована в зависимости от того, насколько неправильны ваши результаты.
В нижней части этого вопроса приведен список первых энергий ионизации для первых 108 элементов. Ваша программа после выполнения должна вывести достаточно точную копию этого списка. Там не будет никаких входных данных или аргументов. В целях оценки ваш вывод должен быть детерминированным (каждый раз один и тот же вывод).
Выходной формат
Ваша программа / функция должна вывести список из 108 чисел, отсортированных в порядке возрастания атомного номера. Этот список может быть в любом подходящем формате. Приведенные ниже исходные данные представлены в правильном порядке, от водорода до хассии.
счет
Ваша оценка будет длиной вашей программы в байтах плюс штраф за округление. Штраф за округление рассчитывается для каждого элемента и суммируется для получения общего штрафа.
В качестве примера возьмем номер 11.81381
. Допустим, ваша программа выдает неверное значение 11.81299999
.
Во- первых, оба числа не умножаются на одной и той же мощностью 10 таким образом, что больше нет точка десятичного в истинном значении:
1181381, 1181299.999
. Конечные нули в истинном значении считаются значимыми.Тогда абсолютная разность берется для определения абсолютной погрешности:
81.001
.Наконец, мы рассчитываем штраф этого элемента как
max(0, log10(err * 4 - 1)) -> 2.50921
. Эта формула была выбрана так, что ошибка <0,5 не дает штрафов (поскольку ответ является правильным при округлении), а также дает асимптотическую 50% -ную вероятность того, что округление числа до любого конкретного десятичного разряда даст чистую выгоду в счете (при условии, что нет другое сжатие).
Вот реализация Try-It-Online программы расчета штрафов. Входные данные для этой программы представлены в виде списка чисел, по одному на строку. Результатом этой программы является общий штраф и разбивка по элементам.
Данные
Ниже приведен список целевых данных в правильном порядке от атомного номера 1 до 108.
13.598434005136
24.587387936
5.391714761
9.322699
8.2980190
11.260296
14.53413
13.618054
17.42282
21.564540
5.1390767
7.646235
5.985768
8.151683
10.486686
10.36001
12.96763
15.7596112
4.34066354
6.11315520
6.56149
6.82812
6.746187
6.76651
7.434018
7.9024678
7.88101
7.639877
7.726380
9.3941990
5.9993018
7.899435
9.7886
9.752392
11.81381
13.9996049
4.177128
5.69486720
6.21726
6.63390
6.75885
7.09243
7.11938
7.36050
7.45890
8.33686
7.576234
8.993822
5.7863552
7.343917
8.608389
9.00966
10.45126
12.1298431
3.893905548
5.211664
5.5769
5.5386
5.473
5.5250
5.582
5.64371
5.670385
6.14980
5.8638
5.93905
6.0215
6.1077
6.18431
6.254159
5.425871
6.825069
7.549571
7.86403
7.83352
8.43823
8.96702
8.95883
9.225553
10.437504
6.1082871
7.4166796
7.285516
8.414
9.31751
10.7485
4.0727409
5.278424
5.380226
6.3067
5.89
6.19405
6.2655
6.0258
5.9738
5.9914
6.1978
6.2817
6.3676
6.50
6.58
6.65
4.90
6.01
6.8
7.8
7.7
7.6
Исходные данные и советы
Приведенные выше исходные данные имеют размер 906 байт, а некоторые инструменты сжатия могут получить их до 500 байтов. Интересными являются решения, которые пытаются выполнить интеллектуальное округление, использовать алгебраические формулы или другие методы для вывода приблизительных значений в меньшем количестве байтов, чем только сжатие. Трудно, однако, судить об этих компромиссах между языками: для некоторых языков только сжатие может быть оптимальным, в то время как во многих других языках могут отсутствовать инструменты сжатия в целом, поэтому я ожидаю значительных различий в оценке по языкам. Это нормально, так как я придерживаюсь философии «соревнования внутри языков, а не между ними».
Я ожидаю, что было бы полезно попытаться воспользоваться тенденциями в периодической таблице. Ниже приведен график, который я нашел для энергий ионизации, так что вы можете увидеть некоторые из этих тенденций.
источник
Ответы:
Чистый , 540 байт + 64,396 штраф = 604,396
Примечание: для удобства чтения я избежал каждого байта в
[Char]
литерале, так как большинство из них не для печати. Тем не менее, они считаются только одним байтом за экранирование (кроме нуля, кавычки и перевода строки), поскольку Clean, естественно, принимает исходные файлы независимо от кодировки (кроме нуля).Попробуйте онлайн!
Это первая задача, в которой я смог использовать универсальную способность сжатия Clean (фактически это не сжатие, а двоичная сериализация), чтобы получить реальное преимущество.
Я начал со
[Real]
списка 64-битных чисел с плавающей точкой, из вопроса. После сериализации этого списка я упростил старшие 10 бит (которые были одинаковыми для каждого числа) и оптимальную конфигурацию младших 32 бит в константу7<<29+2^62
. Оставшиеся 22 бита на число были переведены в 2,75 символа каждый и закодированы в строку.Это оставляет всю сжатую константу только в 302 байта , включая каждый escape!
источник
Python 3 ,
355 + 202353 байта + 198 штрафов = 551Попробуйте онлайн!
Я использовал
0xffff (65535)
верхнюю границу, потому что это максимальное значение, которое может быть сохранено в одном 3-байтовом символе Unicode.Поскольку самая высокая энергия ионизации составляет ~ 24,587, это дает соотношение
2665
.Чтобы сгенерировать саму строку, я использовал фрагмент
''.join([chr(int(round(n*2665)))for n in ionization_energies])
(на python2, который вам нужно использоватьunichr
), ваша консоль может или не сможет печатать символы.4-байтовые символы, 462 байта + штраф 99 = 561
Попробуйте онлайн!
Та же идея, но максимальное значение
0x110000
источник
0x100**2
значения, а не хранить0x100**3
?C, 49 байтов + 626,048 штрафов = 675,048
Попробуйте онлайн!
источник
f(i){for(i=0;i++<108;)printf("6\n");}
; штраф: 625,173030827107; всего = 662,173330827f(i){for(i=0;i<108;)puts("6");}
делает то же самое в 31 байт.i++
тоже (в «31»), ноf(i){for(i=108;i;i--)puts("6");}
делает 32.f(i){for(i=108;i--;)puts("6");}
возвращает его обратно до 31.CJam (389 байт + 33,09 штрафа => 422,09)
XXD-кодируются:
В основном это
При этом используется собственный формат с плавающей запятой переменной ширины для хранения чисел. Для показателя степени достаточно двух битов; мантисса получает от 5 до 47 бит, кратных 7. Оставшийся бит на байт служит разделителем.
Кажется, что происходит некоторая коррупция, когда я копирую волшебную строку, чтобы сделать онлайн-демонстрацию , так что набирает примерно 2 штрафных очка больше. Я должен выяснить, как создать URL напрямую ...
Программа генерации:
Онлайн демо
источник
"
кода увеличивает ошибку слишком сильно, чтобы она того стоила?Желе ,
379 361360 байт + 0 штрафов = 360-18 с использованием наблюдения от Питера Тейлора (значения порядка 10 имеют первые 1 или 2, а значения порядка 1 - нет).
Попробуйте онлайн!
Как?
Создает эти две константы (AKA nilads):
Затем использует их для восстановления представлений чисел с плавающей точкой.
Полная программа имеет следующую форму:
(где
...
кодируются числа для построения B и A)и работает так:
источник
Желе , 116 байт + 429,796016684433 Штраф = 545,796016684433
Попробуйте онлайн!
Ничего особо зрелищное, список индексов коды страницы
“...‘
(число от 0 до 249), к каждому из которых мы добавляем 47 ,+47
и затем разделить на 12 ,÷12
.источник
Желе , 164 байта + 409,846 = 573,846
Попробуйте онлайн!
Там есть сжатое число, которое является объединением первых трех цифр каждой энергии (включая конечные нули). Я получаю список этих трехзначных чисел, а
Ds3Ḍ
затем делю каждое на 100 с÷³
. Некоторые из чисел следует делить только на 10, поэтому я умножаю некоторые из них на 10, чтобы немного улучшить оценку (×⁵$2R;6r⁵¤¤;15r18¤¤¦
).Предыдущая версия :
Желе , 50 байтов + 571,482 штрафа = 621,482
Попробуйте онлайн!
Округлил каждую энергию до ближайшего однозначного числа. Объединенные вместе это дает
995989999958689999467777788889689999466777777889679999456656666666666657888899996778994556666666666677567888
.“¡9;ẋkñ¬nƑḳ_gÐ.RḊụʠṁṬl⁾l>ɼXZĖSṠƈ;cḶ=ß³ṾAiʠʠɼZÞ⁹’
это базовый номер 250, который дает это.DY
соединяет цифры этого номера с символами новой строки.источник
Java 8, 48 байтов + 625.173330827107 Штраф = 673.173330827107
Попробуйте онлайн.
Начальная версия, которая печатается 108 раз
6
. Постараюсь улучшить отсюда.источник
J , 390 байт + 183,319 Штраф = 573,319
Попробуйте онлайн!
Я округлил числа до четырех десятичных цифр и разделил их на один список для целых частей, один список для первых 2 цифр дроби и один для вторых 2 цифр дроби. Я закодировал каждое число печатным символом. Для декодирования я просто извлекаю части числа ingerer и дроби из соответствующих списков символов и собираю их обратно в float.
J , 602 байта + 0 штрафов = 602
Попробуйте онлайн!
На этот раз я выбрал немного другой подход. Я разделил числа на 2 потока - первый содержит целочисленные части, которые просто кодируются одним печатным символом. Второй поток содержит целые дробные части. Я удалил все интервалы между цифрами и добавил каждую подстроку длиной 1-9 (я подправил первую дробь длиной 13 цифр). Затем я закодировал этот список как базовый номер 94, представил его как список символов.
Приблизительно 20 байтов могут быть сохранены, если глагол переписан как молчаливый.
источник
Жевательная резинка , 403 + 9,12 = 412,12
Попробуйте онлайн!
источник