Августовский конкурс по функциональному программированию
За несколько часов до окончания сабжа я, внезапно, тоже решил принять участие.
Задание в этот раз относительно простое, поэтому наивную реализацию делать было не интересно. Подумал, может собрать классическую макру, которая по шаблонам дерево сравнений строит, но там какой-то дружище-ракетчик уже меня опередил :) Посмотрел остальные решения: в основном, все соревнуются в изящности и лаконичности своих хаскелей, кложурей, ди и эрлангов. И я уже засел было за perlgolf, саморазвлечения ради (J всё недосуг выучить), но потом нашёл вот такой кошмар на плюсах, и передумал =)
Короче, решил сделать генератор макрой конечного автомата из заданных матричных шаблонов. Вкрадце, идея такова: есть текстовые данные (в которых нужно искать цифры почтового индекса), по которым, за один проход, куда-то наружу выплёвываются символы. Один за одним, со своими координатами. Там, "где-то снаружи" есть дополнительный слой, который поддерживает очередь неких состояний КА, представленных замыканиями. Каждый новоприбывший символ скармливается всем замыканиям в очереди, в результате чего порождаются новые состояния (либо не порождаются), и из этих новый состояний формируется новая очередь.
Сам конечный автомат генерируется из вот такого dsl:
(deffsm mail-digits
(0 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(1 ((#\1 #\1 #\0) (#\0 #\1 #\0) (#\0 #\1 #\0) (#\0 #\1 #\0) (#\1 #\1 #\1)))
(2 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1)))
(3 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1)))
(4 ((#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\0 #\0 #\1)))
(5 ((#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1)))
(6 ((#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(7 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\0 #\1 #\1) (#\0 #\1 #\0) (#\0 #\1 #\0)))
(8 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(9 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1))))
Соответственно, из этого описания нужно породить некий код КА, начальное состояние 0 которого должно ожидать на вход единицу (в описании нет ни одного шаблона, начинающегося на символ нуля), и при получении оной в относительных координатах (0, 0) переходить в состояние 1. В состоянии 1 возможны уже варианты: при получении нуля в координатах (1, 0) пусть будет переход в состояние 3, а при получении единицы в состояние 4, ну и так далее, идея должна быть понятна. В конце должен быть набор состояний с координатами (2, 4), где мы будем считать, что паттерн поматчился, и печатать результат.
Для ориентировки, простыня макроэкспанда получается вот какой-то такой:
(DEFUN MAIL-DIGITS (CHAR INIT-ROW INIT-COL NEXT RESET)
(DECLARE (OPTIMIZE (DEBUG 3)))
(LABELS ((STATE-0 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 0)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-1))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 0)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-0))))
(STATE-1 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 1)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-2))
((CHAR= CHAR #\0) (FUNCALL NEXT #'STATE-3))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 1)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-1))))
(STATE-2 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 2)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-4))
((CHAR= CHAR #\0) (FUNCALL NEXT #'STATE-5))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-2))))
(STATE-3 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 2)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-6))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-3))))
(STATE-4 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 1)) (= COL (+ INIT-COL 0)))
;; 627 lines skipped
(STATE-89 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 4)) (= COL (+ INIT-COL 2)))
(COND
((CHAR= CHAR #\1)
(FORMAT T ";; found [ 4 ] @ (~a, ~a)~%" INIT-COL INIT-ROW)
(FUNCALL RESET))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 4)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-89)))))
(STATE-0 CHAR INIT-ROW INIT-COL NEXT RESET)))
Собственно, по DSL-ю и сгенерированному коду уже должно быть очевидно, как можно спрограммировать макру. Мой зигзагообразный код в лучших традициях хардкорного олимпиадного программирования (другими словами: индусятина, говнокод) можно посмотреть здесь. Но, опять же, это необязательно, можно просто забрать себе идею :)
Для сабжевой задачи преимущества решения через автомат понятны. Можно относительно спокойно (если переписать process-stream с read-line на read-char) зарулить в парсер поток из /dev/random, а вот все остальные решения на этом конкурсе лопнут. Можно описывать шаблоны матрицами разного размера. Символы для матчинга можно задавать любые (не только 0/1), а с совсем небольшой доработкой DSL-я можно вообще задавать классы символов или кастомные правила матчинга, и автоматически можно будет искать сложные фигуры типа крестиков, звёздочек и тд.
Ну, короче, как-то так, вроде, весело получилось.
Апдейт: версия с исправлением проблемы производительности: http://swizard.livejournal.com/192154.html?thread=2188186#t2188186
Задание в этот раз относительно простое, поэтому наивную реализацию делать было не интересно. Подумал, может собрать классическую макру, которая по шаблонам дерево сравнений строит, но там какой-то дружище-ракетчик уже меня опередил :) Посмотрел остальные решения: в основном, все соревнуются в изящности и лаконичности своих хаскелей, кложурей, ди и эрлангов. И я уже засел было за perlgolf, саморазвлечения ради (J всё недосуг выучить), но потом нашёл вот такой кошмар на плюсах, и передумал =)
Короче, решил сделать генератор макрой конечного автомата из заданных матричных шаблонов. Вкрадце, идея такова: есть текстовые данные (в которых нужно искать цифры почтового индекса), по которым, за один проход, куда-то наружу выплёвываются символы. Один за одним, со своими координатами. Там, "где-то снаружи" есть дополнительный слой, который поддерживает очередь неких состояний КА, представленных замыканиями. Каждый новоприбывший символ скармливается всем замыканиям в очереди, в результате чего порождаются новые состояния (либо не порождаются), и из этих новый состояний формируется новая очередь.
Сам конечный автомат генерируется из вот такого dsl:
(deffsm mail-digits
(0 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(1 ((#\1 #\1 #\0) (#\0 #\1 #\0) (#\0 #\1 #\0) (#\0 #\1 #\0) (#\1 #\1 #\1)))
(2 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1)))
(3 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1)))
(4 ((#\1 #\0 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\0 #\0 #\1)))
(5 ((#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1)))
(6 ((#\1 #\1 #\1) (#\1 #\0 #\0) (#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(7 ((#\1 #\1 #\1) (#\0 #\0 #\1) (#\0 #\1 #\1) (#\0 #\1 #\0) (#\0 #\1 #\0)))
(8 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1)))
(9 ((#\1 #\1 #\1) (#\1 #\0 #\1) (#\1 #\1 #\1) (#\0 #\0 #\1) (#\1 #\1 #\1))))
Соответственно, из этого описания нужно породить некий код КА, начальное состояние 0 которого должно ожидать на вход единицу (в описании нет ни одного шаблона, начинающегося на символ нуля), и при получении оной в относительных координатах (0, 0) переходить в состояние 1. В состоянии 1 возможны уже варианты: при получении нуля в координатах (1, 0) пусть будет переход в состояние 3, а при получении единицы в состояние 4, ну и так далее, идея должна быть понятна. В конце должен быть набор состояний с координатами (2, 4), где мы будем считать, что паттерн поматчился, и печатать результат.
Для ориентировки, простыня макроэкспанда получается вот какой-то такой:
(DEFUN MAIL-DIGITS (CHAR INIT-ROW INIT-COL NEXT RESET)
(DECLARE (OPTIMIZE (DEBUG 3)))
(LABELS ((STATE-0 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 0)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-1))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 0)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-0))))
(STATE-1 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 1)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-2))
((CHAR= CHAR #\0) (FUNCALL NEXT #'STATE-3))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 1)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-1))))
(STATE-2 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 2)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-4))
((CHAR= CHAR #\0) (FUNCALL NEXT #'STATE-5))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-2))))
(STATE-3 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 0)) (= COL (+ INIT-COL 2)))
(COND ((CHAR= CHAR #\1) (FUNCALL NEXT #'STATE-6))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 0)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-3))))
(STATE-4 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 1)) (= COL (+ INIT-COL 0)))
;; 627 lines skipped
(STATE-89 (CHAR ROW COL NEXT RESET)
(IF (AND (= ROW (+ INIT-ROW 4)) (= COL (+ INIT-COL 2)))
(COND
((CHAR= CHAR #\1)
(FORMAT T ";; found [ 4 ] @ (~a, ~a)~%" INIT-COL INIT-ROW)
(FUNCALL RESET))
(T (FUNCALL RESET)))
(IF (AND (>= ROW (+ INIT-ROW 4)) (> COL (+ INIT-COL 2)))
(FUNCALL RESET)
(FUNCALL NEXT #'STATE-89)))))
(STATE-0 CHAR INIT-ROW INIT-COL NEXT RESET)))
Собственно, по DSL-ю и сгенерированному коду уже должно быть очевидно, как можно спрограммировать макру. Мой зигзагообразный код в лучших традициях хардкорного олимпиадного программирования (другими словами: индусятина, говнокод) можно посмотреть здесь. Но, опять же, это необязательно, можно просто забрать себе идею :)
Для сабжевой задачи преимущества решения через автомат понятны. Можно относительно спокойно (если переписать process-stream с read-line на read-char) зарулить в парсер поток из /dev/random, а вот все остальные решения на этом конкурсе лопнут. Можно описывать шаблоны матрицами разного размера. Символы для матчинга можно задавать любые (не только 0/1), а с совсем небольшой доработкой DSL-я можно вообще задавать классы символов или кастомные правила матчинга, и автоматически можно будет искать сложные фигуры типа крестиков, звёздочек и тд.
Ну, короче, как-то так, вроде, весело получилось.
Апдейт: версия с исправлением проблемы производительности: http://swizard.livejournal.com/192154.html?thread=2188186#t2188186