Пошук гамільтонового циклу на CLISP

Лабораторна яку я ще не здав. Бо Володимира Юрійовича і без мене було кому діставати. Але сидів до першої ночі, а потім від шостої ранку до першої пари. Потім дві години ходив за Володимиром Юрійовичем. 🙂 Безрезультатно. Щоденник закінчую, далі обгрунтування актуальності:

Лісп, бо він простий і елегантний, на відміну від Пролога. Ну, і звісно Лісп може бути імперативним, тобто іти на компроміс з вашими звичками. Пролог такого не допустить, або я ще не вияснив як.

І що найголовніше Лісп, хоча це й мова на якій Бог написав всесвіт, достатньо проста. Принаймі простіша за C++. І дуже дуже приємна. Натикаєшся наприклад на функцію (dolist (x list)..., і думаєш, хей, це ж як for x in list: .... А (make-array (list FIELD_SIZE FIELD_SIZE) :initial-element 0) – це майже MatLab. Про lambda, map, reduce, eval я взагалі мовчу.

Крім того, синтаксис простіший ніж в XML.

Найбільша проблема в вивченні Lisp – це визначити що вчити – його, чи Scheme. Схему я ще не копав достатньо глибоко, щоб розповідати про відмінності. Знаю лише що до плюсів Scheme входить SICP. А ще функції описуються за допомогою (define, а не (defun, і в цьому напевне є якась змістовна відмінність.

А до плюсів Common Lisp я сміливо відношу те, що з ним можна познайомитись за кілька годин, дуже весело, і без шкоди для здоров’я. Тут.

Ах, ну і власне, лабораторна:

Умова

КиГ №22 4г – вказівники.
Ми стартуємо у верхній лівій клітинці, яку позначено цифрою 1. Дозволено рухатись тільки в напрямку вказаному стрілками, тобто з першої можна перейти в будь-яку з тих що під нею. Наше завдання – попасти в кожну з клітинок поля послідовно їх нумеруючи, і закінчити в останній, позначеній телефоном, і цифрою 25. Коли всі цифри пронумеровані – знайти їх суму в середньому рядку.

Ах. І ще одне. Клітинка позначена цифрою 17 має бути позначена так само і у вас. Інакше може вийти відповідь не 66, а 60 наприклад, хоча цикл все одно буде гамільтоновим.

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

Код

; №22 4г – вказівники
; Починаємо в верхній лівій клітинці, а далі можемо рухатись лише в напрямку вказаному стрілкою.
; Де зупинитись – вибираємо самі. треба прийти в нижню праву клітинку. 

; Напрямки: 
; 7 8 9 
; 4   6
; 1 2 3

; поле:
(defconstant FIELD_SIZE 5)
(defconstant FIELD_SIZE-1 4)
(defconstant CELL_COUNT 25)

(setf field #2A((2 2 1 4 1) 
                (6 3 3 3 1) 
                (2 8 8 4 1) 
                (9 9 7 1 8) 
                (6 9 4 8 0)))

(defun nl () "newline"
        (format t "~%"))

(defun printfield (&optional (what field)) ; print field (by default) or any other 2d array
        (dotimes (y FIELD_SIZE) 
                (progn 
                (dotimes (x FIELD_SIZE)
                        (format t "~2d " (aref what y x))
                )
                (nl))))

(setf visits (make-array (list FIELD_SIZE FIELD_SIZE) :initial-element 0))

(defun infield (x y) (and (>= x 0) (>= y 0) (< x FIELD_SIZE) (< y FIELD_SIZE)))

(defun waylist (x y dir)
        (if (not (infield x y))
                nil
                (cond ((= dir 1) 
                        (cons (list x y) (waylist (– x 1) (+ y 1) dir)))
                ((= dir 2) 
                        (cons (list x y) (waylist x (+ y 1) dir)))
                ((= dir 3) 
                        (cons (list x y) (waylist (+ x 1) (+ y 1) dir)))
                ((= dir 4) 
                        (cons (list x y) (waylist (– x 1) y dir)))
                ((= dir 6) 
                        (cons (list x y) (waylist (+ x 1) y dir)))
                ((= dir 7) 
                        (cons (list x y) (waylist (– x 1) (– y 1) dir)))
                ((= dir 8) 
                        (cons (list x y) (waylist x (– y 1) dir)))
                ((= dir 9) 
                        (cons (list x y) (waylist (+ x 1) (– y 1) dir)))
                ((= dir 0) nil)
                )))

(defun canvisit (x y)
        (and (infield x y) (= (aref visits y x) 0))
)
(defun visit (x y n) ; return true if going to cell x y in n-th route will lead you to finish
        (defun vis (x y) (setf (aref visits y x) n))
        (defun unvis (x y) (setf (aref visits y x) 0))
        (if (canvisit x y) 
                (progn 
                (if (and (= x 2) (= y 3) (not (= n 17))) (return-from visit nil)) ; special condition
                (vis x y)
                (if (and (= x FIELD_SIZE-1) (= y FIELD_SIZE-1) (= n CELL_COUNT)) 
                        T
                        (progn
                        (dolist (point (cdr (waylist x y (aref field y x))))
                                (if (visit (first point) (second point) (1+ n)) 
                                        (return-from visit T)))
                        (unvis x y)     
                        nil
                        )))
                nil)
)

(printfield)
(print "Wait for it!")
(print (visit 0 0 1)) (nl)
(printfield visits)
(setf res 0)
(dotimes (x FIELD_SIZE) (setf res (+ res (aref visits x 2))))
(print res)

Тест:

 2  2  1  4  1 
 6  3  3  3  1 
 2  8  8  4  1 
 9  9  7  1  8 
 6  9  4  8  0 

"Wait for it!" 
T 
 1  4  8  3  6 
18 24 19 12 21 
 9 23  7 22 13 
 2  5 17 14 20 
10 16 15 11 25 

66 
Натисніть ENTER або введіть команду для продовження