Проблема фатальной ошибки

20

Задача

Напишите подпрограмму, которая принимает строку печатных символов ASCII s и возвращает строку, содержащую те же символы, что и s , переупорядоченную таким образом, чтобы ни одна из двухсимвольных подстрок не появлялась более одного раза. Программа должна обработать все строки тестов (см. Ниже) менее чем за одну минуту на современном компьютере . Я также присуждаю специальный бонус в 50 повторений к ответу с наименьшей оценкой, который обрабатывает любую действительную строку из 30 символов менее чем за минуту.

Например, если заданы входные данные Mississippi, допустимым будет вывод issiMspiips(двухсторонние подстроки не появляются дважды), а недопустимый вывод будет ipMsispiiss(поскольку подстрока isпоявляется дважды).

Процедура может принимать форму:

  • полное чтение программы из stdin(или эквивалентной) или из командной строки и вывод в stdout(или эквивалентную)
  • функция, принимающая один строковый аргумент и возвращающая строку

Вы можете предположить, что входная строка всегда допускает хотя бы один допустимый вывод.

Соревнование

Ваша процедура должна содержать 5 или более строк кода, разделенных символами новой строки. Пустые строки (включая строки, содержащие только пробелы) игнорируются во всех контекстах и ​​не учитываются в общем количестве строк.

Замена любых двух строк в вашем исходном коде должна привести к фатальной ошибке. Под «фатальной ошибкой» мы понимаем любое из следующих условий:

  • исходный код не компилируется, компилятор / интерпретатор объявляет фатальную ошибку
  • процедура прерывается с фатальной ошибкой во время выполнения или необработанным исключением во время выполнения
  • подпрограмма принудительно завершается внезапным, ненормальным завершением программы, которое не выдает никаких выходных данных, за исключением возможного сообщения об ошибке и / или дампа стека

В качестве альтернативы , вместо строк могут использоваться непрерывные блоки кода, не содержащие символов новой строки. Каждый из этих блоков должен отображаться на отдельной строке в исходном файле с пониманием того, что новые строки удаляются перед компиляцией / интерпретацией исходного кода.

Например, код

aaaa
bbbb
cccc

будет конденсироваться до

aaaabbbbcccc

перед оценкой.

В этом режиме условие фатальной ошибки применяется к замене любых двух блоков кода (и, таким образом, к обмену строк в исходном коде до удаления новых строк). Следовательно, в приведенном выше примере подпрограммы aaaaccccbbbb, bbbbaaaaccccи ccccbbbbaaaaвсе они должны вызывать фатальные ошибки, либо во время компиляции, либо во время выполнения.

Материалы, использующие этот альтернативный режим, должны декларировать его использование.

счет

Позвольте n быть числом непустых текстовых строк в вашем исходном файле, с n ≥ 5. Позвольте c быть количеством байтов, включенных самой длинной текстовой строкой (длиной в байтах) в вашем исходном файле, не считая никакой завершающей новой строки.

Оценка представления дается с ( n + 10).

Представление с самым низким счетом является победителем.

Удачи. ;)

Тестовые строки

Abracadabra Alacazam
Is Miss. Mississauga Missing?
Ask Alaska's Alaskans
GGGGAAAATTTTCCCCgggaaatttccc
A Man A Plan A Canal Panama
code-challenge restricted-source source-layout COTO
источник
Отличаются ли заглавные буквы от строчных? т.е. вход есть CooliO, выход oOoCli?
FryAmTheEggman
@FryAmTheEggman: Да. Заглавные буквы отличаются от строчных. В общем, учитывайте только кодовые значения символов ASCII.
COTO
Ограничения повторений ограничиваются парами букв, появляющимися на входе? Например, является ли Mspiisiipssдействительным, поскольку единственное повторение, iiкоторое не происходит в Mississippi?
TwiNight
@TwiNight: даже повторяющиеся подстроки, которые не отображаются в исходной строке, не допускаются.
COTO
Могу ли я предположить что-нибудь о длине ввода? (на заднем плане: блестящая идея для решения BF)
PurkkaKoodari

Ответы:

6

PHP, оценка = 289 (17 × (7 + 10))

Встроенные функции PHP позволяют легко сделать это плохо. Следующий код просто перемешивает строку, пока не будет получен правильный результат:

function f($s){
while(preg_match(
'/(..).*?\1/',$s)
+preg_match('/(.'
.')\1\1/',$s))$s=
str_shuffle(
$s);return $s;}

Ориентиры

Среднее и максимальное время выполнения рассчитывается с использованием следующего кода:

$s = 'Mississippi';
$t_total = 0;
$t_max = 0;
for ($i=0; $i<10; $i++) {
  $t0 = microtime(true);
  echo f($s);
  $t = microtime(true) - $t0;
  printf("  %10.7f\n",$t);
  $t_total += $t;
  if ($t > $t_max) $t_max = $t;
}
printf("Avg: %10.7f secs; Max: %10.7f secs\n",$t_total/$i, $t_max);

Результаты:

  • Миссисипи: среднее значение: 0,0002460 с; Макс .: 0,0005491 сек.
  • Антиконституционный элемент: Ср .: 0,0001470 с; Макс .: 0,0002971 сек.
  • Пневмоноултрамикроскопический силиковолканокониоз: Avg: 0,0587177 с; Макс .: 0,1668079 с
  • Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft * : Avg: 9,5642390 с; Макс .: 34,999099 с
  • baaacadaeafbbcbdbebfccdcecfdde † : среднее значение: 5,0858626 с; Макс .: 9,8927171 с

* Я изменил äна, aчтобы избежать многобайтовых проблем
† Это была самая сложная строка из 30 символов, которую я мог придумать. На самом деле это первые 30 символов последовательности Де Брюйна для k = 'abcdef' и n = 2, причем первый 'b' перемещен, чтобы избежать мгновенного совпадения.

брезгливый оссифраж
источник
5
Это на самом деле не удовлетворяет > Программа должна обработать любую действительную 30-символьную строку менее чем за одну минуту на современном компьютере. , учитывая потенциально бесконечное время выполнения.
Боб
@Bob Я добавил несколько тестов к ответу. Код может быть неэффективным, но вероятность того, что для обработки 30-символьной строки потребуется более одной минуты, на самом деле очень мала.
брезгливый оссифраж
5

Dyalog APL (11 (5 + 10) = 165)

f←{a←{⍴⍵}
b←a⌸2,/⍵
c←b⊢⍵[?⍨a⍵]
1∨.≠b:∇c⋄⍵
}

Доказательство:

  • Строки 1 и 5 связывают функцию. Замена любой строки на них может привести к ⍵появлению вне функции, которая являетсяSYNTAX ERROR .
  • Строка 2 определяет b, поэтому ее нельзя поменять местами на строки 3или 4, которые зависят от b. Там будет VALUE ERROR. (И это, очевидно, не может быть заменено 1или5 либо.)
  • Строка 3 определяет c, поэтому она не может быть заменена на строку 4, которая зависит от c. (И мы уже доказали, что никакая другая строка не может быть заменена на другую 3.)
  • Строка 4 зависит от переменных из строк 2 и 3 и поэтому должна быть последней.
Мэринус
источник
3
+1. Но что все это значит ??
брезгливый оссифраж
4

APL (Dyalog), 6 (5 + 10) = 90

{1∧.=
+/∘.≡⍨
2,/⍵:⍵
⋄∇⍵[
?⍨⍴⍵]}

Я использую альтернативу, так что:

{1∧.=+/∘.≡⍨2,/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Это тот же старый алгоритм.

Пояснение
2,/⍵ дает массив пар символов во входной строке,
+/∘.≡⍨генерирует числовой массив того, сколько пар равняется каждой паре (включая себя)
1∧.= проверяет, равен ли каждый элемент этого массива 1, и логически И результаты вместе

:⍵ Если это правда (1 ), вернуть входную строку

∇⍵[?⍨⍴⍵] иначе зашифруй входную строку и сделай рекурсивный вызов

Перестановка

Если строка 1 поменялась местами со строкой 2, то в итоге вы получите +/∘.≡⍨{...}просто беспорядок функций и операторов, которые дают SYNTAX ERROR.
Если строка 1 поменялась местами со строкой 3 или 4, то у вас нет ⍵определения функции, и это a SYNTAX ERROR.
Если строка 1 поменяется местами со строкой 5, несбалансированные фигурные скобки вызовутSYNTAX ERROR , поэтому не беспокойтесь о других 4 синтаксических ошибках.

Если строка 5 поменялась местами со строкой 2/3/4, опять же у вас нет ⍵определения функции. ( SYNTAX ERROR)

Если строка 2 поменялась местами со строкой 3, вы в конечном итоге 1∧.=2,/⍵:⍵. Этот синтаксис называется охранником (думайте об этом как об условном). Условие защиты должно быть равно 0или 1или массиву из 1 элемента 0или 1. Здесь он оценивается как нечто более сложное (скаляр, содержащий массив из 2 элементов). Так что это DOMAIN ERROR.
Если строка 2 поменялась местами со строкой 4, вы получите инструкцию 1∧.=, которая пытается применить функцию ∧.=без обязательного левого аргумента. ( SYNTAX ERROR).

Если строка 3 поменялась местами со строкой 4, снова вы получите беспорядок функций и операторов ( 1∧.=+/∘.≡⍨), так что вы получите SYNTAX ERROR.

Тесты
(числа в миллисекундах)

Abracadabra Alacazam
11 1 3 5 2
Avg: 4.4

Is Miss. Mississauga Missing?
1260 2000 222 117 111
Avg: 742

Ask Alaska's Alaskans
7 2 3 3 4
Avg: 3.8

GGGGAAAATTTTCCCCgggaaatttccc
31 15 24 13 11
Avg: 18.8

A Man A Plan A Canal Panama
377 2562 23 301 49
Avg: 662.4

Я все еще думаю о разных расколах. Также у меня есть детерминированный, систематический способ выполнения задачи. Я просто не могу превратить его в алгоритм (убрать творческую часть «правильных чисел») и не могу убедиться, что он работает каждый раз.

TwiNight
источник
0

Haskell, 129 = 3x (33 + 10)

это использует альтернативный режим.

imp
ort
 Da
ta.
Lis
t;a
%[]
=[[
]];
a%s
=[x
:j|
x<-
s,n
ot$
isI
nfi
xOf
[la
st 
a,x
]a,
j<-
(a+
+[x
])%
(s\
\[x
])]
;g 
s=[
]%s
!!0

или в читаемой форме:

import Data.List
a%[]=[[]]
a%s=[x:j|x<-s,not$isInfixOf[last a,x]a,j<-(a++[x])%(s\\[x])]
g s=[]%s!!0

Хаскель - очень строгий язык. например, importдолжен прийти первым; определения sдолжны объединяться; все типы должны быть согласованы, и между ними нет способа разыграть и так далее. это приводит к тому, что нефатальная ошибка почти невозможна. на самом деле наличие фатальной ошибки во время выполнения слишком почти невозможно.

заметит , что если gдействительная функция , но имеет неправильный тип (любой тип , отличающееся то [a]->[a]или String -> Stringи тому подобное) , чем это фатальная ошибка , потому что это невозможно применить gк входам.

выходы:

Abracadabar Alaazcma
Is Miss. iMsiasusgsa sMniig?s
Ask Alasak's lAaankss
GGAGTGCAATACTTCCggagtaacttcc
A Man AP la nAC  aalnnaPama
гордый хаскеллер
источник