From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: =?iso-8859-1?Q?Vincent_Bela=EFche?= Newsgroups: gmane.emacs.devel Subject: Re: 5x5 Arithmetic solver Date: Sat, 21 May 2011 20:15:46 +0200 Message-ID: <80lixz9ay5.fsf@gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: dough.gmane.org 1306001768 32471 80.91.229.12 (21 May 2011 18:16:08 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 21 May 2011 18:16:08 +0000 (UTC) Cc: Jay P Belanger , =?iso-8859-1?Q?Vincent_Bela=EFche?= , Stefan Monnier , davep@davep.org To: Eli Zaretskii , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat May 21 20:16:03 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1QNqiY-0005nZ-1G for ged-emacs-devel@m.gmane.org; Sat, 21 May 2011 20:16:02 +0200 Original-Received: from localhost ([::1]:39355 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNqiX-0007bu-5J for ged-emacs-devel@m.gmane.org; Sat, 21 May 2011 14:16:01 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:35915) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNqiT-0007bi-J4 for emacs-devel@gnu.org; Sat, 21 May 2011 14:15:59 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QNqiR-0005ZN-GB for emacs-devel@gnu.org; Sat, 21 May 2011 14:15:57 -0400 Original-Received: from smtp09.smtpout.orange.fr ([80.12.242.131]:17887 helo=smtp.smtpout.orange.fr) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QNqiR-0005ZD-1b for emacs-devel@gnu.org; Sat, 21 May 2011 14:15:55 -0400 Original-Received: from CHOUNEK ([92.139.227.58]) by mwinf5d18 with ME id mJFq1g0071GE1uc03JFrrx; Sat, 21 May 2011 20:15:53 +0200 X-Antivirus: avast! (VPS 110521-0, 21/05/2011), Outbound message X-Antivirus-Status: Clean X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 80.12.242.131 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:139607 Archived-At: --=-=-= Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable [...] >=20 >Did you send the corrected version? Because I still see >non-capitalized comments that don't fall under any of your exceptions: Ooops, it seems that I did a mistake, I named the diff update 5x5.diff, but I sent the older one 5x5.el.diff. Anyhow, it was good to double check as I had forgotten some of the capitals anyway. >=20 [...] >=20 >By the way, please leave two spaces after the period that ends a >sentence. This is our convention in any text we write in Emacs, >including comments, doc strings, and manuals. >=20 Done. I found a few missing double space in existing comments too, which shows that this rule is not too tightly followed. >> >- we need a ChangeLog entry. >>=20 [...] >=20 >No, that's not enough. What you've written is the summary line, but >the ChangeLog also needs the details: which functions and variables >were added or deleted, which were modified and how, etc. Like this: >=20 > (5x5-solver-output): New defvar. > (5x5-local-variables): New defconst. > (5x5-mode): Make all variables in 5x5-local-variables local. > (5x5): Set 5x5-grid-size only if SIZE is non-negative. >=20 >etc. You can see plenty of examples of the exact style in the >ChangeLog files. >=20 Sorry for the scanty Changelog, I was a bit too shy to provide one like the following: 2011-05-21 Vincent Bela=EFche * play/5x5.el: Add an arithmetic solver to suggest positions to click on. Make 5x5 multisession. (5x5-mode-map): Add keybinding to function `5x5-solve-suggest'. (5x5-solver-output): New defvar, output of function `5x5-solve-suggest'. (5x5-local-variables): New defconst. List of variable to be made buffer local to achieve 5x5 multi-session-ness. (5x5): Set 5x5-grid-size only if SIZE is non-negative. Modify order of processing, as in order to achieve multi-session-ness you have to set `5x5-mode' first, as `5x5-mode' is what make session-dependent variables buffer local. (5x5-mode): Make session-dependent variables buffer local. (5x5-grid-to-vec): New defun. Convert a 5x5 game grid into a Calc matrix in Z/2Z. (5x5-vec-to-grid): New defun. Convert a Calc matrix in Z/2Z into a 5x5 game grid. (5x5-log-buffer): New defvar. Not defined, provisionned for debugging Arithmetric solver. (5x5-log-init): New defun. Defined to dummy, provisionned for debugging Arithmetric solver. (5x5-log): New defun. Defined to dummy, provisionned for debugging Arithmetric solver. (5x5-solver): New defun, make the actual algorithm of arithmetic solver, to be usable that function needs some wrapper to the 5x5 user interace, this wapper is function `5x5-solve-suggest' for invocation, and function `5x5-draw-grid' for the diplay. (5x5-solve-suggest): New defun, invoke the arithmetic solver, and display solution. Please let me know if you need more details. >Please also spell-check your comments and doc strings, there are a few >non-English words I spotted here and there. >=20 >Thanks. > I have read again the 5x5.el file and found a few errors, like "for the time begin" instead of "for the time being", which was made only of English words and grammatically correct, but was not what I meant. Hopefully what I spotted is sufficient to make you happy. Please feel free to make me know otherwise. VBR Vincent. --=-=-= Content-Type: text/x-patch; charset=iso-8859-1 Content-Disposition: inline; filename=5x5.el.diff Content-Transfer-Encoding: quoted-printable =3D=3D=3D modified file 'lisp/play/5x5.el' --- lisp/play/5x5.el 2011-04-21 12:24:46 +0000 +++ lisp/play/5x5.el 2011-05-21 17:40:11 +0000 @@ -24,15 +24,15 @@ =20 ;;; Commentary: =20 -;; The aim of 5x5 is to fill in all the squares. If you need any more of an +;; The aim of 5x5 is to fill in all the squares. If you need any more of = an ;; explanation you probably shouldn't play the game. =20 ;;; TODO: =20 -;; o The code for updating the grid needs to be re-done. At the moment it +;; o The code for updating the grid needs to be re-done. At the moment it ;; simply re-draws the grid every time a move is made. ;; -;; o Look into tarting up the display with color. gamegrid.el looks +;; o Look into tarting up the display with color. gamegrid.el looks ;; interesting, perhaps that is the way to go? =20 ;;; Thanks: @@ -41,7 +41,10 @@ ;; emacs mode. ;; ;; Pascal Q. Porcupine for inspiring the animated -;; solver. +;; cracker. +;; +;; Vincent Bela=EFche & Jay P. Belanger +;; for the math solver. =20 ;;; Code: =20 @@ -134,10 +137,37 @@ (define-key map [(control c) (control b)] #'5x5-crack-mutating-best) (define-key map [(control c) (control x)] #'5x5-crack-xor-mutate) (define-key map "n" #'5x5-new-game) + (define-key map "s" #'5x5-solve-suggest) (define-key map "q" #'5x5-quit-game) map) "Local keymap for the 5x5 game.") =20 +(defvar 5x5-solver-output nil + "List that is is the output of artihmetic solver. + +This list L is such that + +L =3D (M S_1 S_2 ... S_N) + +M is the move count when the solve output was stored. + +S_1 ... S_N are all the solutions ordered from least to greatest +number of strokes. S_1 is the solution to be displayed. + +Each solution S_1, ..., S_N is a a list (STROKE-COUNT GRID) where +STROKE-COUNT is to number of strokes to achieve the solution and +GRID is the grid of positions to click.") + +(defconst 5x5-local-variables + '(5x5-grid + 5x5-moves + 5x5-grid-size + 5x5-x-pos + 5x5-y-pos + 5x5-cracking + 5x5-solver-output) + "List of variables to be local to a 5x5 buffer.") + ;; Menu definition. =20 (easy-menu-define 5x5-mode-menu 5x5-mode-map "5x5 menu." @@ -146,6 +176,7 @@ ["Random game" 5x5-randomize t] ["Quit game" 5x5-quit-game t] "---" + ["Use Calc solver" 5x5-solve-suggest t] ["Crack randomly" 5x5-crack-randomly t] ["Crack mutating current" 5x5-crack-mutating-current t] ["Crack mutating best" 5x5-crack-mutating-best t] @@ -158,10 +189,12 @@ (defun 5x5-mode () "A mode for playing `5x5'. =20 -The key bindings for 5x5-mode are: +The key bindings for `5x5-mode' are: =20 \\{5x5-mode-map}" (kill-all-local-variables) + (dolist (v 5x5-local-variables) + (make-local-variable v)) (use-local-map 5x5-mode-map) (setq major-mode '5x5-mode mode-name "5x5") @@ -194,14 +227,14 @@ =20 (interactive "P") (setq 5x5-cracking nil) - (when size - (setq 5x5-grid-size size)) (switch-to-buffer 5x5-buffer-name) + (5x5-mode) + (when (natnump size) + (setq 5x5-grid-size size)) (if (or (not 5x5-grid) (not (=3D 5x5-grid-size (length (aref 5x5-grid 0)= )))) (5x5-new-game)) (5x5-draw-grid (list 5x5-grid)) - (5x5-position-cursor) - (5x5-mode)) + (5x5-position-cursor)) =20 (defun 5x5-new-game () "Start a new game of `5x5'." @@ -277,10 +310,11 @@ =20 (defun 5x5-draw-grid (grids) "Draw the grids GRIDS into the current buffer." - (let ((buffer-read-only nil)) + (let ((buffer-read-only nil) grid-org) (erase-buffer) (loop for grid in grids do (5x5-draw-grid-end)) (insert "\n") + (setq grid-org (point)) (loop for y from 0 to (1- 5x5-grid-size) do (loop for lines from 0 to (1- 5x5-y-scale) do (loop for grid in grids do @@ -290,6 +324,23 @@ (if (5x5-cell grid y x) ?= # ?.)))) (insert " | ")) (insert "\n"))) + (when 5x5-solver-output + (if (=3D (car 5x5-solver-output) 5x5-moves) + (save-excursion + (goto-char grid-org) + (beginning-of-line (+ 1 (/ 5x5-y-scale 2))) + (let ((solution-grid (cdadr 5x5-solver-output))) + (dotimes (y 5x5-grid-size) + (save-excursion + (forward-char (+ 1 (/ (1+ 5x5-x-scale) 2))) + (dotimes (x 5x5-grid-size) + (when (5x5-cell solution-grid y x) + (insert-char ?O 1) + (delete-char 1) + (backward-char)) + (forward-char (1+ 5x5-x-scale)))) + (forward-line 5x5-y-scale)))) + (setq 5x5-solver-output nil))) (loop for grid in grids do (5x5-draw-grid-end)) (insert "\n") (insert (format "On: %d Moves: %d" (5x5-grid-value (car grids)) 5x5-m= oves)))) @@ -415,6 +466,312 @@ (sit-for 5x5-animate-delay)))) 5x5-grid) =20 +;; Arithmetic solver +;;=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D +(defun 5x5-grid-to-vec (grid) + "Convert GRID to an equivalent Calc matrix of (mod X 2) forms +where X is 1 for setting a position, and 0 for unsetting a +position." + (cons 'vec + (mapcar (lambda (y) + (cons 'vec + (mapcar (lambda (x) + (if x '(mod 1 2) '(mod 0 2))) + y))) + grid))) + +(defun 5x5-vec-to-grid (grid-matrix) + "Convert a grid matrix GRID-MATRIX in Calc format to a grid in +5x5 format. See function `5x5-grid-to-vec'." + (apply + 'vector + (mapcar + (lambda (x) + (apply + 'vector + (mapcar + (lambda (y) (/=3D (cadr y) 0)) + (cdr x)))) + (cdr grid-matrix)))) + +(if nil; set to t to enable solver logging + (progn + (defvar 5x5-log-buffer nil) + (defun 5x5-log-init () + (if (buffer-live-p 5x5-log-buffer) + (with-current-buffer 5x5-log-buffer (erase-buffer)) + (setq 5x5-log-buffer (get-buffer-create "*5x5 LOG*")))) + + (defun 5x5-log (name value) + "Debug purpuse only. + +Log a matrix VALUE of (mod B 2) forms, only B is output and +Scilab matrix notation is used. VALUE is returned so that it is +easy to log a value with minimal rewrite of code." + (when (buffer-live-p 5x5-log-buffer) + (let* ((unpacked-value + (math-map-vec + (lambda (row) (math-map-vec 'cadr row)) + value)) + (calc-vector-commas "") + (calc-matrix-brackets '(C O)) + (value-to-log (math-format-value unpacked-value))) + (with-current-buffer 5x5-log-buffer + (insert name ?=3D value-to-log ?\n)))) + value)) + (defmacro 5x5-log-init ()) + (defmacro 5x5-log (name value) value)) + +(defun 5x5-solver (grid) + "Return a list of solutions for GRID. + +Given some grid GRID, the returned a list of solution LIST is +sorted from least Hamming weight to geatest one. + + LIST =3D (SOLUTION-1 ... SOLUTION-N) + +Each solution SOLUTION-I is a cons cell (HW . G) where HW is the +Hamming weight of the solution --- ie the number of strokes to +achieves it --- and G is the grid of positions to click in order +to complete the 5x5. + +Solutions are sorted from least to greatest Hamming weight." + (require 'calc-ext) + (flet ((5x5-mat-mode-2 + (a) + (math-map-vec + (lambda (y) + (math-map-vec + (lambda (x) `(mod ,x 2)) + y)) + a))) + (let* (calc-command-flags + (grid-size-squared (* 5x5-grid-size 5x5-grid-size)) + + ;; targetv is the vector the origine of which is org=3D"current + ;; grid" and the end of which is dest=3D"all ones". + (targetv + (5x5-log + "b" + (let ( + ;; org point is the current grid + (org (calcFunc-arrange (5x5-grid-to-vec grid) + 1)) + + ;; end point of game is the all ones matrix + (dest (calcFunc-cvec '(mod 1 2) grid-size-squared 1))) + (math-sub dest org)))) + + ;; transferm is the transfer matrix, ie it is the 25x25 + ;; matrix applied everytime a flip is carried out where a + ;; flip is defined by a 25x1 Dirac vector --- ie all zeros + ;; but 1 in the position that is flipped. + (transferm + (5x5-log + "a" + ;; transfer-grid is not a play grid, but this is the + ;; transfer matrix in the format of a vector of vectors, we + ;; do it this way because random access in vectors is + ;; faster. The motivation is just speed as we build it + ;; element by element, but that could have been created + ;; using only Calc primitives. Probably that would be a + ;; better idea to use Calc with some vector manipulation + ;; rather than going this way... + (5x5-grid-to-vec (let ((transfer-grid + (let ((5x5-grid-size grid-size-squared)) + (5x5-make-new-grid)))) + (dotimes (i 5x5-grid-size) + (dotimes (j 5x5-grid-size) + ;; k0 =3D flattened flip position corresponding + ;; to (i, j) on the grid. + (let* ((k0 (+ (* 5 i) j))) + ;; cross center + (5x5-set-cell transfer-grid k0 k0 t) + ;; Cross top. + (and + (> i 0) + (5x5-set-cell transfer-grid + (- k0 5x5-grid-size) k0 t)) + ;; Cross bottom. + (and + (< (1+ i) 5x5-grid-size) + (5x5-set-cell transfer-grid + (+ k0 5x5-grid-size) k0 t)) + ;; Cross left. + (and + (> j 0) + (5x5-set-cell transfer-grid (1- k0) k0 t)) + ;; Cross right. + (and + (< (1+ j) 5x5-grid-size) + (5x5-set-cell transfer-grid + (1+ k0) k0 t))))) + transfer-grid)))) + ;; TODO: this is hard-coded for grid-size =3D 5, make it generic. + (transferm-kernel-size + (if (=3D 5x5-grid-size 5) 2 + (error "Transfer matrix rank not known for grid-size !=3D 5"))) + + ;; TODO: this is hard-coded for grid-size =3D 5, make it generic. + ;; + ;; base-change is a 25x25 matrix, where topleft submatrix + ;; 23x25 is a diagonal of 1, and the two last columns are a + ;; base of kernel of transferm. + ;; + ;; base-change must be by construction inversible. + (base-change + (5x5-log + "p" + (let ((id (5x5-mat-mode-2 (calcFunc-diag 1 grid-size-squared)))) + (setcdr (last id (1+ transferm-kernel-size)) + (cdr (5x5-mat-mode-2 + '(vec (vec 0 1 1 1 0 1 0 1 0 1 1 1 0 1 + 1 1 0 1 0 1 0 1 1 1 0) + (vec 1 1 0 1 1 0 0 0 0 0 1 1 0 1 + 1 0 0 0 0 0 1 1 0 1 1))))) + (calcFunc-trn id)))) + + (inv-base-change + (5x5-log "invp" + (calcFunc-inv base-change))) + + ;; B:=3D targetv + ;; A:=3D transferm + ;; P:=3D base-change + ;; P^-1 :=3D inv-base-change + ;; X :=3D solution + + ;; B =3D A * X + ;; P^-1 * B =3D P^-1 * A * P * P^-1 * X + ;; CX =3D P^-1 * X + ;; CA =3D P^-1 * A * P + ;; CB =3D P^-1 * B + ;; CB =3D CA * CX + ;; CX =3D CA^-1 * CB + ;; X =3D P * CX + (ctransferm + (5x5-log + "ca" + (math-mul + inv-base-change + (math-mul transferm base-change)))); CA + (ctarget + (5x5-log + "cb" + (math-mul inv-base-change targetv))); CB + (row-1 (math-make-intv 3 1 transferm-kernel-size)) ; 1..2 + (row-2 (math-make-intv 1 transferm-kernel-size + grid-size-squared)); 3..25 + (col-1 (math-make-intv 3 1 (- grid-size-squared + transferm-kernel-size))); 1..23 + (col-2 (math-make-intv 1 (- grid-size-squared + transferm-kernel-size) + grid-size-squared)); 24..25 + (ctransferm-1-: (calcFunc-mrow ctransferm row-1)) + (ctransferm-1-1 (calcFunc-mcol ctransferm-1-: col-1)) + + ;; By construction ctransferm-:-2 =3D 0, so ctransferm-1-2 =3D 0 + ;; and ctransferm-2-2 =3D 0. + + ;;(ctransferm-1-2 (calcFunc-mcol ctransferm-1-: col-2)) + (ctransferm-2-: (calcFunc-mrow ctransferm row-2)) + (ctransferm-2-1 + (5x5-log + "ca_2_1" + (calcFunc-mcol ctransferm-2-: col-1))) + + ;; By construction ctransferm-2-2 =3D 0. + ;; + ;;(ctransferm-2-2 (calcFunc-mcol ctransferm-2-: col-2)) + + (ctarget-1 (calcFunc-mrow ctarget row-1)) + (ctarget-2 (calcFunc-mrow ctarget row-2)) + + ;; ctarget-1(2x1) =3D ctransferm-1-1(2x23) *cx-1(23x1) + ;; + ctransferm-1-2(2x2) *cx-2(2x1); + ;; ctarget-2(23x1) =3D ctransferm-2-1(23x23)*cx-1(23x1) + ;; + ctransferm-2-2(23x2)*cx-2(2x1); + ;; By construction: + ;; + ;; ctransferm-1-2 =3D=3D zeros(2,2) and ctransferm-2-2 =3D=3D zeros(= 23,2) + ;; + ;; So: + ;; + ;; ctarget-2 =3D ctransferm-2-1*cx-1 + ;; + ;; So: + ;; + ;; cx-1 =3D inv-ctransferm-2-1 * ctarget-2 + (cx-1 (math-mul (calcFunc-inv ctransferm-2-1) ctarget-2)) + + ;; Any cx-2 can do, so there are 2^{transferm-kernel-size} solutions. + (solution-list + ;; Within solution-list each element is a cons cell: + ;; + ;; (HW . SOL) + ;; + ;; where HW is the Hamming weight of solution, and SOL is + ;; the solution in the form of a grid. + (sort + (cdr + (math-map-vec + (lambda (cx-2) + ;; Compute `solution' in the form of a 25x1 matrix of + ;; (mod B 2) forms --- with B =3D 0 or 1 --- and + ;; return (HW . SOL) where HW is the Hamming weight + ;; of solution and SOL a grid. + (let ((solution (math-mul + base-change + (calcFunc-vconcat cx-1 cx-2)))); X =3D P * CX + (cons + ;; The Hamming Weight is computed by matrix reduction + ;; with an ad-hoc operator. + (math-reduce-vec + ;; (cadadr '(vec (mod x 2))) =3D> x + (lambda (r x) (+ (if (integerp r) r (cadadr r)) + (cadadr x))) + solution); car + (5x5-vec-to-grid + (calcFunc-arrange solution 5x5-grid-size));cdr + ))) + ;; A (2^K) x K matrix, where K is the dimension of kernel + ;; of transfer matrix --- i.e. K=3D2 in if the grid is 5x5 + ;; --- for I from 0 to K-1, each row rI correspond to the + ;; binary representation of number I, that is to say row + ;; rI is a 1xK vector: + ;; [ n{I,0} n{I,1} ... n{I,K-1} ] + ;; such that: + ;; I =3D sum for J=3D0..K-1 of 2^(n{I,J}) + (let ((calc-number-radix 2) + (calc-leading-zeros t) + (calc-word-size transferm-kernel-size)) + (math-map-vec + (lambda (x) + (cons 'vec + (mapcar (lambda (x) `(vec (mod ,(logand x 1) 2))) + (substring (math-format-number x) + (- transferm-kernel-size))))) + (calcFunc-index (math-pow 2 transferm-kernel-size) 0))) )) + ;; Sort solutions according to respective Hamming weight. + (lambda (x y) (< (car x) (car y))) + ))) + + solution-list))) + +(defun 5x5-solve-suggest (&optional n) + "Suggest to the user where to click. + +Argument N is ignored." + ;; For the time being n is ignored, the idea was to use some numeric + ;; argument to show a limited amount of positions. + (interactive "P") + (5x5-log-init) + (let ((solutions (5x5-solver 5x5-grid))) + (setq 5x5-solver-output + (cons 5x5-moves solutions))) + (5x5-draw-grid (list 5x5-grid)) + (5x5-position-cursor)) + ;; Keyboard response functions. =20 (defun 5x5-flip-current () --=-=-=--