Skip to content

Instantly share code, notes, and snippets.

@youz

youz/solve_m23.lisp

Last active June 24, 2023 02:54
Show Gist options
  • Save youz/b17392219b10c6c2cad333f4b685d312 to your computer and use it in GitHub Desktop.
Save youz/b17392219b10c6c2cad333f4b685d312 to your computer and use it in GitHub Desktop.
Download ZIP
EQUALINE Mission 23 solver (in common lisp)
Raw
solve_m23.lisp
;;; EQUALINE Mission 23 solver
(defstruct kifu
(boards (list #(1 :+ 1 :+ 1 :+ 1 :+ 1))) ; 盤面のリスト (逆順)
(routes nil) ; 指し手(int list)のリスト (逆順)
)
(defun print-kifu (k)
(loop for b in (reverse (kifu-boards k))
for r in (cons nil (reverse (kifu-routes k)))
for i from 0
do (format t "#~d: ~{~a~}~%~13@{-~}~%" i r t)
(format t "~{~3@{|~2@a ~}|~%~}~13@{-~}~%" (coerce b 'list) t)))
(defun update-board (b r)
(let ((nb (copy-seq b)))
(dolist (pos r)
(let ((e #0=(aref nb pos)))
(if (numberp e)
(incf #0#)
(setf #0# (case e (:+ :-) (:- :*) (:* :+)
(t (error "unknown op: ~s" e)))))))
nb))
(defun update-kifu (k r)
(let ((nb (update-board (car #0=(kifu-boards k)) r)))
(make-kifu :boards (cons nb #0#)
:routes (cons r (kifu-routes k)))))
(defun search-route (target board)
(labels ((rec (pos v prev acc)
(let* ((c (aref board pos))
(v (if (numberp c)
(case prev
(:+ (+ v c))
(:- (- v c))
(:* (* v c))
(t (error "wrong board or route: ~s ~s"
board (reverse acc))))
v)))
(append
(and (numberp c) (= v target) (list (reverse acc)))
(loop for (dx dy) in '((1 0) (-1 0) (0 1) (0 -1))
append
(let* ((nx (+ (mod pos 3) dx))
(ny (+ (truncate pos 3) dy))
(npos (+ nx (* ny 3))))
(and (<= 0 nx 2) (<= 0 ny 2) (not (find npos acc))
(rec npos v c (cons npos acc)))))))))
(loop for pos from 0 to 8 by 2
append (rec pos 0 :+ (list pos)))))
(defun solve (k stgmax)
(labels ((rec (k stgno)
(let ((target (* stgno (1+ stgno) 1/2)))
(loop for r in (search-route target (car (kifu-boards k)))
for nk = (update-kifu k r)
append (if (< stgno stgmax)
(rec nk (1+ stgno))
(list nk))))))
(rec k 3)))
(defun mhd (a b)
(+ (abs (- (mod a 3) (mod b 3)))
(abs (- (truncate a 3) (truncate b 3)))))
(defun count-moves (k)
(loop for (a b) on (cons 4 (apply #'append (reverse (kifu-routes k))))
if b sum (mhd a b)))
(defparameter *initial-states*
(let* ((k0 (make-kifu))
(k1 (update-kifu (update-kifu k0 '(0)) '(0 1 4)))
(k2 (update-kifu (update-kifu k0 '(0)) '(0 1 2)))
(k3 (update-kifu (update-kifu k0 '(4)) '(4 1 0))))
(list k1 k2 k3)))
(time
(let* ((stgmax #+sbcl (if #0=(cadr sb-ext:*posix-argv*)
(max 3 (parse-integer #0#))
10)
#-sbcl 10)
(allans (sort (loop for k in *initial-states*
append (solve k stgmax))
#'< :key #'count-moves))
(shortest (car allans)))
(format t "found ~A solutions~%" (length allans))
(format t "shortest solution: ~A moves~%" (count-moves shortest))
(print-kifu shortest)))
Raw
solve_m23_result.txt
$ sbcl --script solve_m23.lisp
found 26408 solutions
shortest solution: 54 moves
#0:
-------------
| 1 | + | 1 |
| + | 1 | + |
| 1 | + | 1 |
-------------
#1: 0
-------------
| 2 | + | 1 |
| + | 1 | + |
| 1 | + | 1 |
-------------
#2: 014
-------------
| 3 | - | 1 |
| + | 2 | + |
| 1 | + | 1 |
-------------
#3: 412587630
-------------
| 4 | * | 2 |
| - | 3 | - |
| 2 | - | 2 |
-------------
#4: 01478
-------------
| 5 | + | 2 |
| - | 4 | - |
| 2 | * | 3 |
-------------
#5: 452103678
-------------
| 6 | - | 3 |
| * | 5 | * |
| 3 | + | 4 |
-------------
#6: 8745210
-------------
| 7 | * | 4 |
| * | 6 | + |
| 3 | - | 5 |
-------------
#7: 6785410
-------------
| 8 | + | 4 |
| * | 7 | - |
| 4 | * | 6 |
-------------
#8: 0145876
-------------
| 9 | - | 4 |
| * | 8 | * |
| 5 | + | 7 |
-------------
#9: 630
-------------
|10 | - | 4 |
| + | 8 | * |
| 6 | + | 7 |
-------------
#10: 0125478
-------------
|11 | * | 5 |
| + | 9 | + |
| 6 | - | 8 |
-------------
Evaluation took:
4.972 seconds of real time
4.687500 seconds of total run time (4.625000 user, 0.062500 system)
[ Run times consist of 0.031 seconds GC time, and 4.657 seconds non-GC time. ]
94.29% CPU
12,411,975,473 processor cycles
946,018,208 bytes consed
Raw
solve_m23_result_50.txt
$ sbcl --script solve_m23.lisp 50
found 480 solutions
shortest solution: 404 moves
#0:
-------------
| 1 | + | 1 |
| + | 1 | + |
| 1 | + | 1 |
-------------
#1: 0
-------------
| 2 | + | 1 |
| + | 1 | + |
| 1 | + | 1 |
-------------
#2: 014
-------------
| 3 | - | 1 |
| + | 2 | + |
| 1 | + | 1 |
-------------
#3: 412587630
-------------
| 4 | * | 2 |
| - | 3 | - |
| 2 | - | 2 |
-------------
#4: 01458
-------------
| 5 | + | 2 |
| - | 4 | * |
| 2 | - | 3 |
-------------
#5: 012587634
-------------
| 6 | - | 3 |
| * | 5 | + |
| 3 | * | 4 |
-------------
#6: 0125876
-------------
| 7 | * | 4 |
| * | 5 | - |
| 4 | + | 5 |
-------------
#7: 0367458
-------------
| 8 | * | 4 |
| + | 6 | * |
| 5 | - | 6 |
-------------
#8: 8763012
-------------
| 9 | + | 5 |
| - | 6 | * |
| 6 | * | 7 |
-------------
#9: 8763410
-------------
|10 | - | 5 |
| * | 7 | * |
| 7 | + | 8 |
-------------
#10: 0147852
-------------
|11 | * | 6 |
| * | 8 | + |
| 7 | - | 9 |
-------------
#11: 6785430
-------------
|12 | * | 6 |
| + | 9 | - |
| 8 | * |10 |
-------------
#12: 8543012
-------------
|13 | + | 7 |
| - |10 | * |
| 8 | * |11 |
-------------
#13: 8763410
-------------
|14 | - | 7 |
| * |11 | * |
| 9 | + |12 |
-------------
#14: 0147852
-------------
|15 | * | 8 |
| * |12 | + |
| 9 | - |13 |
-------------
#15: 6785430
-------------
|16 | * | 8 |
| + |13 | - |
|10 | * |14 |
-------------
#16: 8543012
-------------
|17 | + | 9 |
| - |14 | * |
|10 | * |15 |
-------------
#17: 8763410
-------------
|18 | - | 9 |
| * |15 | * |
|11 | + |16 |
-------------
#18: 0147852
-------------
|19 | * |10 |
| * |16 | + |
|11 | - |17 |
-------------
#19: 6785430
-------------
|20 | * |10 |
| + |17 | - |
|12 | * |18 |
-------------
#20: 8543012
-------------
|21 | + |11 |
| - |18 | * |
|12 | * |19 |
-------------
#21: 8763410
-------------
|22 | - |11 |
| * |19 | * |
|13 | + |20 |
-------------
#22: 0147852
-------------
|23 | * |12 |
| * |20 | + |
|13 | - |21 |
-------------
#23: 6785430
-------------
|24 | * |12 |
| + |21 | - |
|14 | * |22 |
-------------
#24: 8543012
-------------
|25 | + |13 |
| - |22 | * |
|14 | * |23 |
-------------
#25: 8763410
-------------
|26 | - |13 |
| * |23 | * |
|15 | + |24 |
-------------
#26: 0147852
-------------
|27 | * |14 |
| * |24 | + |
|15 | - |25 |
-------------
#27: 6785430
-------------
|28 | * |14 |
| + |25 | - |
|16 | * |26 |
-------------
#28: 8543012
-------------
|29 | + |15 |
| - |26 | * |
|16 | * |27 |
-------------
#29: 8763410
-------------
|30 | - |15 |
| * |27 | * |
|17 | + |28 |
-------------
#30: 0147852
-------------
|31 | * |16 |
| * |28 | + |
|17 | - |29 |
-------------
#31: 6785430
-------------
|32 | * |16 |
| + |29 | - |
|18 | * |30 |
-------------
#32: 8543012
-------------
|33 | + |17 |
| - |30 | * |
|18 | * |31 |
-------------
#33: 8763410
-------------
|34 | - |17 |
| * |31 | * |
|19 | + |32 |
-------------
#34: 0147852
-------------
|35 | * |18 |
| * |32 | + |
|19 | - |33 |
-------------
#35: 6785430
-------------
|36 | * |18 |
| + |33 | - |
|20 | * |34 |
-------------
#36: 8543012
-------------
|37 | + |19 |
| - |34 | * |
|20 | * |35 |
-------------
#37: 8763410
-------------
|38 | - |19 |
| * |35 | * |
|21 | + |36 |
-------------
#38: 0147852
-------------
|39 | * |20 |
| * |36 | + |
|21 | - |37 |
-------------
#39: 6785430
-------------
|40 | * |20 |
| + |37 | - |
|22 | * |38 |
-------------
#40: 8543012
-------------
|41 | + |21 |
| - |38 | * |
|22 | * |39 |
-------------
#41: 8763410
-------------
|42 | - |21 |
| * |39 | * |
|23 | + |40 |
-------------
#42: 0147852
-------------
|43 | * |22 |
| * |40 | + |
|23 | - |41 |
-------------
#43: 6785430
-------------
|44 | * |22 |
| + |41 | - |
|24 | * |42 |
-------------
#44: 8543012
-------------
|45 | + |23 |
| - |42 | * |
|24 | * |43 |
-------------
#45: 8763410
-------------
|46 | - |23 |
| * |43 | * |
|25 | + |44 |
-------------
#46: 0147852
-------------
|47 | * |24 |
| * |44 | + |
|25 | - |45 |
-------------
#47: 6785430
-------------
|48 | * |24 |
| + |45 | - |
|26 | * |46 |
-------------
#48: 8543012
-------------
|49 | + |25 |
| - |46 | * |
|26 | * |47 |
-------------
#49: 8763410
-------------
|50 | - |25 |
| * |47 | * |
|27 | + |48 |
-------------
#50: 0147852
-------------
|51 | * |26 |
| * |48 | + |
|27 | - |49 |
-------------
Evaluation took:
12.994 seconds of real time
12.343750 seconds of total run time (12.328125 user, 0.015625 system)
[ Run times consist of 0.015 seconds GC time, and 12.329 seconds non-GC time. ]
95.00% CPU
32,434,261,527 processor cycles
1,655,213,504 bytes consed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment