Еще в мае и июне 2005 года я опубликовал следующие сообщения в своем личном блоге (ecclestoad.co.uk). Теперь, когда я удалил этот блог, я переиздаю его здесь.
25 мая 2005 г. - Решатель судоку в четыре строки.
Возможно, немного глупо, но я подумал, что было бы забавно написать кусок кода для решения этих головоломок судоку, которые продолжают появляться. Поскольку это казалось тривиальным, я решил посмотреть, можно ли это сделать в четыре строки или меньше. Вот:
Он немного загадочен в использовании, но что вы ожидаете от четырех строк Perl? Лучший способ запустить его — сохранить в файл (например, sudoku.pl). Вы также должны кормить его стартовой сеткой. Это одна длинная строка с верхней строкой первой, второй строкой следующей и так далее. Используйте нули для пробелов. Не разделяйте ряды пробелом, просто соедините их все вместе.
Например, в журнале Economist (21 мая 2005 г.) на странице 75 была дана следующая загадка:
. . . . 1 . . . . 3 . 1 4 . . 8 6 . 9 . . 5 . . 2 . . 7 . . 1 6 . . . . . 2 . 8 . 5 . 1 . (dots are used for the blanks) . . . . 9 7 . . 4 . . 3 . . 4 . . 6 . 4 8 . . 6 9 . 7 . . . . 8 . . . .
Это даст вам следующую строку для ввода:
000010000301400860900500200700160000020805010000097004003004006048006907000080000
Если вы сохранили ввод в файл с именем input.txt, вы можете запустить решатель следующим образом:
perl sudoku.pl < input.txt
Вывод имеет тот же формат, что и ввод, то есть все строки в одной строке.
Это будет работать только для сеток 9 × 9, содержащих числа от 1 до 9. Надеюсь, вам понравится.
27 мая 2005 г. - Обфускация как инструмент обучения
Пару дней назад я опубликовал обфускацию, которая решает головоломки судоку в четырех строках Perl. Чтобы сжать код до такого уровня, потребовалось довольно много грязных маленьких трюков, которым не место в производственном коде. Здесь я собираюсь вскрыть обфу и указать, что из него можно извлечь.
Сначала код как обфу:
А потом прибрал perltidy:
Теперь я пробегусь по коду, объясняя, что делает каждый бит, и размышляю об этом.
$a = 8;
$G{ int( ++$a / 9 ) . $a % 9 + 1 } = $_ for split //, <>;
Этот код принимает входные данные и создает хэш. Хэш %G состоит из двух чисел, таких как «23» или «39». Это число представляет собой координату (y,x) в сетке судоку с началом в левом верхнем углу. Я использовал (y,x), а не (x,y), так как это позволяло мне легче распечатать сетку позже.
Создание ключа довольно интересно, так как мы нумеруем значения, входящие в список, в своего рода базе 9. Подумайте об изменении чисел, когда вы переходите от первой строки ко второй: 17, 18, 19, 21, 22, 23. Как видите, нужно перейти от 19 к 21. Координата y получается путем отбрасывания дробной части деления, координата x получается с использованием модуля. Возрастающее значение для работы предоставляется $a, которое начинается с «8», а затем предварительно увеличивается во время создания ключа.
@A = 1 .. 9;
Сама простота. @A - это просто массив от 1 до 9. Если вы посмотрите на остальную часть кода, много раз мне нужно было запустить от 1 до 9, и поэтому для экономии места стоило создать этот массив.
sub c {
int( ( $_[0] - 1 ) / 3 ) * 3;
}
Это вспомогательная функция, которая используется позже при поиске, какие числа в данный момент находятся в блоке, на который мы смотрим. Ему передается одна цифра от 1 до 9. Он возвращает 0, 3 или 6 для 1..3, 4..6 или 7..9. См. далее, как используется возвращаемое значение.
sub G {
Создайте подпрограмму G. Это основная часть обфу, и здесь происходит большинство действий. Основная идея состоит в том, чтобы найти первый квадрат в сетке, который не имеет значения. Затем найдите все возможные числа, которые могут войти. Для каждого числа введите его и рекурсивно. Если мы доходим до конца сетки, выходим, иначе пробуем следующее значение. Если больше нет значений, попробовать сделать резервную копию на предыдущие квадраты.
for $y (@A) {
for $x (@A) {
Сердце программы - две петли, обе из 1..9. Это дает нам координаты квадрата в сетке, над которой мы работаем.
$p = $t = $G{ my $c = $y . $x } && next;
В этой строке происходит несколько вещей. Самое главное — посмотреть, есть ли число в квадрате. Поскольку для всех пустых квадратов установлено значение 0 (ложь), это можно сделать с помощью простого логического теста. Если есть число, то $G{'yx'} истинно, что приводит к вызову следующего. Это использует ленивую оценку терминов в Perl, т.е. если первый тест не пройден (нет номера) то нет необходимости оценивать второй тест, следующий.
В интересах зубрежки кода есть еще несколько вещей. Сначала устанавливается переменная $c, содержащая текущее местоположение (y,x). Это присваивание происходит внутри фигурных скобок хеша. Это работает, потому что возвращаемое значение присваивания является присвоенным значением. Это также используется для присвоения начальных ложных значений $p и $t, которые используются позже. Значения в $p и $t всегда ложны, так как если бы они были истинными, то цикл перепрыгнул бы.
$t .= $G{ $_ . $x } . $G{ $y . $_ } for @A;
Наконец, мы начинаем фактически определять, какие числа могут войти в этот квадрат. К строке $t добавляются числа, которые уже заняты (t означает «занято»). Это делается как для текущей строки, так и для текущего столбца в одном выражении.
for $f ( 1 .. 3 ) { $t .= $G{ c($y) + $f . c($x) + $_ } for 1 .. 3 }
Этот двойной цикл добавляет числа, взятые в текущем блоке, к $t. Есть две переменные, $f и $_, которые запускаются от 1..3. Они добавляются к возвращаемому значению из подпрограммы c, рассмотренной ранее, что приводит к выбору квадратов в текущей сетке.
Забавное использование двух циклов for таким образом заключается в экономии места.
G( $G{$c} = $_ ) && return for grep $t !~ m/$_/, @A;
Здесь происходит несколько вещей. Существует цикл по возможному числу, которое может попасть в квадрат: for grep $t !~ m/$_/, @A. Так как $t содержит взятые числа, grep возвращает только не взятые числа от 1 до 9, т.е. возможные значения.
Для каждого возможного числа G( $G{$c} = $_ ) выполняется возврат &&. Это устанавливает текущий квадрат в возможное значение. Затем он рекурсивно переходит в G. Если возвращаемое значение истинно, он возвращается. На самом деле он возвращает true, поскольку если специально не задано значение return, оно вернет все, что находится в $_, которое, как это бывает, было просто установлено на возвращаемое значение из G. Это всегда будет верно для возврата, который будет вызван, и поэтому true всегда вернулся.
Вы можете задаться вопросом, почему текущему квадрату присваивается его значение в качестве аргумента подпрограммы G? Ответ заключается в том, что таким образом экономится один персонаж. Сравните G($G{$c} = $_) с $G{$c} = $_, G(). Поскольку G ничего не делает с аргументами, это нормально.
return $G{$c} = 0;
}
}
Если код не вернулся выше, то теперь он должен вернуться. Если мы достигнем этой стадии, то будут перепробованы все возможные числа для этого квадрата, и ни одно из них не привело к решению судоку. Мы хотим вернуть текущему квадрату значение false и позволить коду попытаться изменить некоторые предыдущие числа, чтобы увидеть, приведут ли они к решению. Опять же, возвращаемое значение из присваивания используется для экономии места.
die map { $G{$_} } 9 .. 99;
}
Это грязно. Мне нужно было сбрить пару символов, чтобы уместиться в четыре строки, и я сделал это. Если мы достигнем этой точки, то два цикла for для $x и $y достигли конца. Случилось так, что последнему квадрату был присвоен номер. Подпрограмма была рекурсивной, и два цикла for были запущены, и next был вызван для каждого квадрата, поскольку все они содержат числа. Следовательно, мы заканчиваем здесь. Чтобы сохранить последние несколько символов, я использовал die вместо print. Ужасный.
На карте нет необходимости беспокоиться о значениях в G для таких ключей, как 10 или 20, которые не имеют значений. Они просто приводят к выводу undef, что не приводит к ошибкам, поскольку предупреждения об использовании не указаны.
G
Итак, мы в конце кода. Все, что нам нужно сделать сейчас, это запустить G в первый раз.
Довольно интересно, что я заметил экономителя места при написании этого поста. Существует переменная $p, которая была установлена в false, но фактически никогда не используется. Раньше он использовался для возможных значений, которые могли попасть в квадрат, но стали ненужными из-за изменений. Однако я забыл его там. Исправление ошибок чтением кода в действии.
Еще одна экономия места заключается в том, что, поскольку код умирает, когда решение найдено, нет необходимости возвращаться, поскольку код уже умер. Это означает, что можно сократить еще одну строку:
G( $G{$c} = $_ ) && return for grep $t !~ m/$_/, @A; # before
G( $G{$c} = $_ ) for grep $t !~ m/$_/, @A; # after
Это означает, что матрицу можно немного привести в порядок, и мы даже можем отформатировать вывод:
die map { $G{$_} } 9 .. 99; # before
die map { $G{$_} || "\n" } 9 .. 100; # after
Новая, лучшая, более короткая обфу:
Надеюсь, вы согласитесь, что хотя здесь всего четыре строчки кода, есть над чем подумать. Не весь код является «хорошим», на самом деле большая его часть — очень плохой код. Однако искусственное ограничение в четыре строки приводит к некоторым интересным методам, использующим преимущества некоторых из более эзотерических частей языка.
2 июня 2005 г. –объяснение решения судоку в три строки.
В предыдущих сообщениях я создал четырехстрочный решатель судоку, а затем продолжил его объяснение. Понаблюдав за подходом программиста на C к этому, я сократил текст до трех строк. Вот это и как это работает.
Выше версия obfu, ниже тот же код, пропущенный через perltidy. Код работает так же, как и раньше — вы вводите сетку судоку в одну строку, используя нули вместо пробелов. Затем код выдает решение в той же форме.
Основное отличие состоит в том, что в моей четырехстрочной версии я хранил сетку судоку в хэше, тогда как здесь я использую массив. Для удобства вот сетка судоку, где числа представляют индекс в массиве:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
Теперь я пройдусь по коду, объясняющему различные интересные моменты.
use integer; @A = split //, <>;
Обфус редко использует модули, но в этом случае он сэкономил несколько символов. Позже в коде я выполняю довольно много целочисленной математики, и без использования целого числа мне пришлось бы обернуть шесть выражений следующим образом: int( $_ / 9 ).
Вторая строка помещает сетку из STDIN в массив @A.
sub R {
for $i ( 0 .. 80 ) {
next if $A[$i];
Подпрограмма R называется так потому, что она рекурсивная. Основная его часть — это цикл for, который проходит по всей сетке. Однако, если в сетке есть значение, оно переходит к следующей позиции. $i теперь является текущей позицией в сетке, для которой мы ищем значение.
my %t = map {
$_ / 9 == $i / 9
|| $_ % 9 == $i % 9
|| $_ / 27 == $i / 27 && $_ % 9 / 3 == $i % 9 / 3
? $A[$_]
: 0 => 1
} 0 .. 80;
Это немного волосато. Я создаю хэш %t, ключами которого будут числа, которые нельзя использовать в этой позиции, т.е. те, которые были заняты. Карта содержит abool_expr ? if_true : конструкция if_false для определения того, каким должен быть ключ.
Первые три строки на карте — это логические выражения, определяющие, находится ли $_ в той же строке, столбце или сетке, что и $i. $_ / 9 == $i / 9 для строки (помните, что деление целочисленное, поэтому что-то вроде 12/9 равно 1). || $_ % 9 == $i % 9 для столбца и || $_/27 == $i/27 && $_ % 9/3 == $i % 9/3 для сетки (первая часть для строки сетки, вторая часть для столбца сетки). Это довольно прямолинейно, как только вы поймете их.
На самом деле логические значения должны быть заключены в квадратные скобки, чтобы прояснить ситуацию, однако, поскольку Perl перестанет их вычислять, как только найдет истинное, окончание && будет в порядке.
Помните, что карта присваивает хешу пару ключ/значение. Хорошо, если эти тесты возвращают истину, тогда ключ $A[$_], в противном случае он равен 0. Значение жестко закодировано как истина. Я был удивлен, обнаружив, что код для ключа не обязательно должен быть в квадратных скобках, очевидно, что ?: имеет более тесную связь, чем =›, как и следовало ожидать.
R( $A[$i] = $_ ) for grep { !$t{$_} } 1 .. 9;
Здесь происходят три вещи. Цикл for выполняется для всех чисел, которые можно использовать в этой позиции, благодаря grep { !$t{$_} }, который отфильтровывает использованные числа — они имеют истинное значение в хэше %t.
R( $A[$i] = $_ ) устанавливает текущую позицию в одно из возможных значений, а затем рекурсивно.
return $A[$i] = 0;
Если ни одно из значений в цикле for не приводит к решению или если не было значений для проверки, мы сбрасываем текущую позицию на ноль и возвращаемся. Это позволяет пробовать другие значения в «более высоких» вызовах R.
}
die @A;
}
Если самый внешний цикл for когда-либо достигает конца (т. е. $i == 81), то у нас есть решение. Распечатайте его и остановите обработку.
R
Осталось только запустить код.
Итак, судоку решается тремя строками Perl. На мой взгляд, это чище, чем мои предыдущие предложения, поскольку логика жестче. Тем не менее, эта обфу не так коротка, как может быть. Есть две лишние точки с запятой и логика в карте тоже могла бы быть сокращена, как и некоторые другие биты.
5 ноября 2005 г. –обфускация как инструмент заработка
Несколько месяцев назад я разместил запись, в которой решала судоку всего за несколько строк. В результате я устроился на работу и поэтому в последнее время немного отвлекаюсь. Интересно то, что обфу (я так думаю) помог в процессе собеседования, что было неожиданно — ведь это не «производственный» код, что бы это ни было.
Хо хм. Сейчас я работаю в 3B.net над множеством проектов.
