5x5 Arithmetic solver

5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 1707 bytes --]

Dear Dave,

Please find herein attached a contribution to the 5x5 game. This is an
arithmetic solver based on a matrix inversion in a (Z/2Z)^25 vector
space.

Note that will work only with a reasonably recent version of Calc
because that needs a bug fix on matrix inversion for matrix of Z/2Z
modulo forms.

The code works only for 5x5 grid size for the time being. I think that
it is feasible to make it general to work for any size or for any
pattern (I had in mind like replacing the 5-toggles cross by some other
pattern like a V or Y or X pattern). However this would need some
further thinking.

Also, this contribution could be improved in several other minor aspects
like:

- showing only one or a limited number of click positions for suggestion
  instead of all of them --- that could be based on some sort criteria
  to select the position(s) to show, for instance give priority to the
  positions that toggle more positions

- or by updating the solution incrementally after the first matrix
  inversion rather than invert the matrix again every time a new
  suggestion is required by the user --- even with just a 5x5 matrix the
  inversion takes some time, at least on my machine --- but that may be
  due to this that I am using MSWindows instead of GNU Linux ;-) ---

- or hiding the suggestions after some configurable time, like one
  or two second, or more

Nevertheless I believe that this solver makes this game significantly
more funny for my tired brain, as clicking on s (to require a
suggestion) and then trying only to remember the position where to
click, is quite enough thinking of that kind for me.

Very Best Regards,
   Vincent.

PS: The Calc code has been reviewed by Jay.


[-- Attachment #2: 5x5.tgz --]
[-- Type: application/octet-stream, Size: 9722 bytes --]

Re: 5x5 Arithmetic solver

[Stefan Monnier]

> Please find herein attached a contribution to the 5x5 game. This is an
> arithmetic solver based on a matrix inversion in a (Z/2Z)^25 vector
> space.

Thanks.  A few comments:
- avoid using a tarball and just attach the diff as-is,
  makes it a lot easier to review.
- why 5x5-local-variables?
- explain the changes in the 5x5 function.
- many of your lines have trailing whitespace.  I generally don't care
  much, about it, but some people do, and it's usually preferable to
  avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
  a side-effect).
- try to keep the first line of docstrings as a self-sufficient sentence
  (because M-x apropos only shows the first line).
- stay within 80 columns.
- your code is not properly indented (e.g. the `grid' argument in
  5x5-grid-to-vec).
- Please capitalize your comments and terminate them with a "." or some
  other appropriate punctuation.
- 5x5-solve-suggest should have a docstring.
- try C-u checkdoc-current-buffer.
- we need a ChangeLog entry.
- I don't understand the "solve step" message (e.g. it said 23 every
  time, even though I followed its suggestions and finished in 12 moves).


        Stefan

Re: 5x5 Arithmetic solver

[Antoine Levitt]

20/05/11 15:45, Stefan Monnier
> - many of your lines have trailing whitespace.  I generally don't care
>   much, about it, but some people do, and it's usually preferable to
>   avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
>   a side-effect).

As does M-x delete-trailing-whitespace FWIW.

Also, the algorithm looks fun, do you have a link/reference to the
theory behind it? I'm asking for my personal benefit, but it would
probably be a good idea to put it into a comment in the sources.

RE: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 788 bytes --]


Ok, 

I will try to write a short documentation for that. 

  Vincent

> To: emacs-devel@gnu.org
> From: antoine.levitt@gmail.com
> Subject: Re: 5x5 Arithmetic solver
> Date: Fri, 20 May 2011 16:03:37 +0200
> 
> 20/05/11 15:45, Stefan Monnier
> > - many of your lines have trailing whitespace.  I generally don't care
> >   much, about it, but some people do, and it's usually preferable to
> >   avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
> >   a side-effect).
> 
> As does M-x delete-trailing-whitespace FWIW.
> 
> Also, the algorithm looks fun, do you have a link/reference to the
> theory behind it? I'm asking for my personal benefit, but it would
> probably be a good idea to put it into a comment in the sources.
> 
> 
 		 	   		  

[-- Attachment #2: Type: text/html, Size: 1104 bytes --]

Re: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 3379 bytes --]

Salut Stéfan,

Toujours aussi à cheval sur les conventions de codage !

>> Please find herein attached a contribution to the 5x5 game. This is an
>> arithmetic solver based on a matrix inversion in a (Z/2Z)^25 vector
>> space.
> 
>Thanks.  A few comments:
>- avoid using a tarball and just attach the diff as-is,
>  makes it a lot easier to review.

noted 

>- why 5x5-local-variables?

That is used in 5x5-mode to imply that all listed variable are made
local to that very 5x5 buffer. if after `M-x 5x5' you do a `M-x
rename-uniquely' and then `M-x 5x5' again then you have have two
independent games.

>- explain the changes in the 5x5 function.

I had to change slightly the order of operations because setting the
mode has to be done before any buffer local 5x5 variable is touched, as
precisely those variables are made local by setting the mode

>- many of your lines have trailing whitespace.  I generally don't care
>  much, about it, but some people do, and it's usually preferable to
>  avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
>  a side-effect).

Done

>- try to keep the first line of docstrings as a self-sufficient sentence
>  (because M-x apropos only shows the first line).



>- stay within 80 columns.

Do you mean that we are still in the 80ies ;-P ? 

Ok, done.

>- your code is not properly indented (e.g. the `grid' argument in
>  5x5-grid-to-vec).

Done

>- Please capitalize your comments and terminate them with a "." or some
>  other appropriate punctuation.

Some comments by a variable name, so they are not capitalized. 

Some comments are equations like this:

	   ;; B:= targetv
	   ;; A:= transferm
	   ;; P:= base-change
	   ;; P^-1 := inv-base-change
	   ;; X := solution

	   ;; B = A * X
	   ;; P^-1 * B = P^-1 * A * P * P^-1 * X
	   ;; CX = P^-1 * X
	   ;; CA = P^-1 * A * P
	   ;; CB = P^-1 * B
	   ;; CB = CA * CX
	   ;; CX = CA^-1 * CB
	   ;; X = P * CX

I don't think that this is common practice to use a punctuation at the
end of an equation.

Some other comment is commented out code like this:

	   ;;(ctransferm-1-2 (calcFunc-mcol ctransferm-1-: col-2))

This code is not there because I don't need that variable, but I found
useful to show how it would be defined.

For all the remaining comments I have done it

>- 5x5-solve-suggest should have a docstring.

Done

>- try C-u checkdoc-current-buffer.

I get 

checkdoc-continue: Too many occurrences of \[function].  Use \{keymap}
instead

Because 5x5 is used many times as if it was 


>- we need a ChangeLog entry.

Here it is:

-----------------------------------------------------------------------
2011-05-21  Vincent Belaïche  <vincentb1@users.sourceforge.net>

	* play/5x5.el: Add an arithmetic solver to suggest positions to
	click on.
-----------------------------------------------------------------------

>- I don't understand the "solve step" message (e.g. it said 23 every
>  time, even though I followed its suggestions and finished in 12 moves).
> 
> 

Ask it to Jay, this message is output by Calc, not by 5x5. 23 is due
to this that you have to invert a 23x23 matrix. Altough the 5x5 transfer
matrix is 25x25, its rank is only 23, so I extract some submatrix to
compute the solution.

>        Stefan

  Vincent.


[-- Attachment #2: 5x5.el.diff --]
[-- Type: text/x-patch, Size: 13871 bytes --]

=== modified file 'lisp/play/5x5.el'
--- lisp/play/5x5.el	2011-04-21 12:24:46 +0000
+++ lisp/play/5x5.el	2011-05-19 20:05:06 +0000
@@ -41,7 +41,10 @@
 ;; emacs mode.
 ;;
 ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated
-;; solver.
+;; cracker.
+;;
+;; Vincent Belaïche <vincentb1@users.sourceforge.net> & Jay P. Belanger
+;; <jay.p.belanger@gmail.com> for the math solver.
 
 ;;; Code:
 
@@ -134,10 +137,35 @@
     (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.")
 
+(defvar 5x5-solver-output nil
+  "List L such that
+
+L = (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.
 
 (easy-menu-define 5x5-mode-menu 5x5-mode-map "5x5 menu."
@@ -146,6 +174,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]
@@ -162,6 +191,8 @@
 
 \\{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 +225,14 @@
 
   (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 (= 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))
 
 (defun 5x5-new-game ()
   "Start a new game of `5x5'."
@@ -277,10 +308,11 @@
 
 (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 +322,23 @@
                                                  (if (5x5-cell grid y x) ?# ?.))))
                       (insert " | "))
                 (insert "\n")))
+    (when 5x5-solver-output
+      (if (= (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-moves))))
@@ -415,6 +464,273 @@
                 (sit-for 5x5-animate-delay))))
   5x5-grid)
 
+;; Arithmetic solver
+;;===========================================================================
+(defun 5x5-grid-to-vec (grid)
+  "Convert GRID to an equivalent Calc matrix of (mod X 2) forms
+where X is 1 for set positions, and 0 for unset positions."
+  (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) (/= (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 ?= value-to-log ?\n))))
+	value))
+  (defmacro 5x5-log-init ())
+  (defmacro 5x5-log (name value) value))
+
+(defun 5x5-solver (grid)
+  "Given some grid GRID, return a list of solution LIST sorted
+from least Hamming weight to geatest one. 
+
+   LIST = (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="current grid" and
+	 ;; the end of which is dest="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))))
+	 
+	 ;; transfer matrix 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 primitive. 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 = 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 = 5, make it generic
+	 (transferm-kernel-size 
+	  (if (= 5x5-grid-size 5) 2 
+	    (error "Transfer matrix rank not known for grid-size != 5")))
+	 
+	 ;; TODO: this is hard-coded for grid-size = 5, make it generic
+	 ;;
+	 ;; base-change is a 25x25 matrix, where topleft submatrix 23x25 is a diag of 1,
+	 ;; and 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: targetv 
+	 ;; A: transferm 
+	 ;; P: base-change
+	 ;; P^-1 : inv-base-change
+	 ;; X : solution
+	 
+	 ;; B = A * X
+	 ;; P^-1 * B = P^-1 * A * P * P^-1 * X
+	 ;; CX = P^-1 * X
+	 ;; CA = P^-1 * A * P
+	 ;; CB = P^-1 * B
+	 ;; CB = CA * CX
+	 ;; CX = CA^-1 * CB
+	 ;; X = 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 = 0, so ctransferm-1-2 = 0
+	 ;; and ctransferm-2-2 = 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 = 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)  = ctransferm-1-1(2x23) *cx-1(23x1) + ctransferm-1-2(2x2) *cx-2(2x1);
+	 ;;   ctarget-2(23x1) = ctransferm-2-1(23x23)*cx-1(23x1) + ctransferm-2-2(23x2)*cx-2(2x1);
+	 ;;   by construction
+	 ;;   ctransferm-1-2 == zeros(2,2) and ctransferm-2-2 == zeros(23,2)
+	 ;;   so
+	 ;;   ctarget-2 = ctransferm-2-1*cx-1
+	 ;;   so cx-1 = 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 = 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 = P * CX
+		 (cons
+		  ;; the Hamming Weight is computed by matrix reduction
+		  ;; with an ad-hoc operator
+		  (math-reduce-vec 
+		   ;; (cadadr '(vec (mod x 2))) => 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 --- ie K=2 in if the grid is 5x5 --- for I from 0 to
+	     ;; K-1, each row rI correspond to the binary representatrion 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 = sum for J=0..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)
+  ;; for the time begin 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.
 
 (defun 5x5-flip-current ()

Re: 5x5 Arithmetic solver

[Eli Zaretskii]

> From: Vincent Belaïche <vincent.b.1@hotmail.fr> 
> Date: Sat, 21 May 2011 09:15:57 +0200
> Cc: Vincent Belaïche <vincent.b.1@hotmail.fr>
> 
> >- Please capitalize your comments and terminate them with a "." or some
> >  other appropriate punctuation.
> [...]
> For all the remaining comments I have done it

Did you send the corrected version?  Because I still see
non-capitalized comments that don't fall under any of your exceptions:

> +	 ;; transfer matrix 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.
> [...]
> +	 ;; by construction ctransferm-:-2 = 0, so ctransferm-1-2 = 0
> +	 ;; and ctransferm-2-2 = 0
> [...]
> +	 ;; 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 solutions according to respective Hamming weight

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.

> >- we need a ChangeLog entry.
> 
> Here it is:
> 
> -----------------------------------------------------------------------
> 2011-05-21  Vincent Belaïche  <vincentb1@users.sourceforge.net>
> 
> 	* play/5x5.el: Add an arithmetic solver to suggest positions to
> 	click on.
> -----------------------------------------------------------------------

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:

	(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.

etc.  You can see plenty of examples of the exact style in the
ChangeLog files.

Please also spell-check your comments and doc strings, there are a few
non-English words I spotted here and there.

Thanks.

Re: 5x5 Arithmetic solver

[Vinicius Jose Latorre]

[-- Attachment #1: Type: text/plain, Size: 3524 bytes --]

Hi Vincent,

Could I suggest the attached diff?

Vinicius


On 05/21/2011 04:15 AM, Vincent Belaïche wrote:
> Salut Stéfan,
>
> Toujours aussi à cheval sur les conventions de codage !
>
>>> Please find herein attached a contribution to the 5x5 game. This is an
>>> arithmetic solver based on a matrix inversion in a (Z/2Z)^25 vector
>>> space.
>> Thanks.  A few comments:
>> - avoid using a tarball and just attach the diff as-is,
>>   makes it a lot easier to review.
> noted
>
>> - why 5x5-local-variables?
> That is used in 5x5-mode to imply that all listed variable are made
> local to that very 5x5 buffer. if after `M-x 5x5' you do a `M-x
> rename-uniquely' and then `M-x 5x5' again then you have have two
> independent games.
>
>> - explain the changes in the 5x5 function.
> I had to change slightly the order of operations because setting the
> mode has to be done before any buffer local 5x5 variable is touched, as
> precisely those variables are made local by setting the mode
>
>> - many of your lines have trailing whitespace.  I generally don't care
>>   much, about it, but some people do, and it's usually preferable to
>>   avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
>>   a side-effect).
> Done
>
>> - try to keep the first line of docstrings as a self-sufficient sentence
>>   (because M-x apropos only shows the first line).
>
>
>> - stay within 80 columns.
> Do you mean that we are still in the 80ies ;-P ?
>
> Ok, done.
>
>> - your code is not properly indented (e.g. the `grid' argument in
>>   5x5-grid-to-vec).
> Done
>
>> - Please capitalize your comments and terminate them with a "." or some
>>   other appropriate punctuation.
> Some comments by a variable name, so they are not capitalized.
>
> Some comments are equations like this:
>
> 	   ;; B:= targetv
> 	   ;; A:= transferm
> 	   ;; P:= base-change
> 	   ;; P^-1 := inv-base-change
> 	   ;; X := solution
>
> 	   ;; B = A * X
> 	   ;; P^-1 * B = P^-1 * A * P * P^-1 * X
> 	   ;; CX = P^-1 * X
> 	   ;; CA = P^-1 * A * P
> 	   ;; CB = P^-1 * B
> 	   ;; CB = CA * CX
> 	   ;; CX = CA^-1 * CB
> 	   ;; X = P * CX
>
> I don't think that this is common practice to use a punctuation at the
> end of an equation.
>
> Some other comment is commented out code like this:
>
> 	   ;;(ctransferm-1-2 (calcFunc-mcol ctransferm-1-: col-2))
>
> This code is not there because I don't need that variable, but I found
> useful to show how it would be defined.
>
> For all the remaining comments I have done it
>
>> - 5x5-solve-suggest should have a docstring.
> Done
>
>> - try C-u checkdoc-current-buffer.
> I get
>
> checkdoc-continue: Too many occurrences of \[function].  Use \{keymap}
> instead
>
> Because 5x5 is used many times as if it was
>
>
>> - we need a ChangeLog entry.
> Here it is:
>
> -----------------------------------------------------------------------
> 2011-05-21  Vincent Belaïche<vincentb1@users.sourceforge.net>
>
> 	* play/5x5.el: Add an arithmetic solver to suggest positions to
> 	click on.
> -----------------------------------------------------------------------
>
>> - I don't understand the "solve step" message (e.g. it said 23 every
>>   time, even though I followed its suggestions and finished in 12 moves).
>>
>>
> Ask it to Jay, this message is output by Calc, not by 5x5. 23 is due
> to this that you have to invert a 23x23 matrix. Altough the 5x5 transfer
> matrix is 25x25, its rank is only 23, so I extract some submatrix to
> compute the solution.
>
>>         Stefan
>    Vincent.
>


[-- Attachment #2: 5x5.el.diff-suggestion --]
[-- Type: text/plain, Size: 15107 bytes --]

diff -c 5x5.el-orig 5x5.el
*** 5x5.el-orig	2011-04-21 15:28:20.000000000 -0300
--- 5x5.el	2011-05-21 11:28:39.000000000 -0300
***************
*** 41,47 ****
  ;; emacs mode.
  ;;
  ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated
! ;; solver.
  
  ;;; Code:
  
--- 41,50 ----
  ;; emacs mode.
  ;;
  ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated
! ;; cracker.
! ;;
! ;; Vincent Belaïche <vincentb1@users.sourceforge.net> & Jay P. Belanger
! ;; <jay.p.belanger@gmail.com> for the math solver.
  
  ;;; Code:
  
***************
*** 134,143 ****
--- 137,171 ----
      (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.")
  
+ (defvar 5x5-solver-output nil
+   "List L such that
+ 
+ L = (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.
  
  (easy-menu-define 5x5-mode-menu 5x5-mode-map "5x5 menu."
***************
*** 146,151 ****
--- 174,180 ----
      ["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]
***************
*** 162,167 ****
--- 191,198 ----
  
  \\{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,207 ****
  
    (interactive "P")
    (setq 5x5-cracking nil)
-   (when size
-     (setq 5x5-grid-size size))
    (switch-to-buffer 5x5-buffer-name)
    (if (or (not 5x5-grid) (not (= 5x5-grid-size (length (aref 5x5-grid 0)))))
        (5x5-new-game))
    (5x5-draw-grid (list 5x5-grid))
!   (5x5-position-cursor)
!   (5x5-mode))
  
  (defun 5x5-new-game ()
    "Start a new game of `5x5'."
--- 225,238 ----
  
    (interactive "P")
    (setq 5x5-cracking nil)
    (switch-to-buffer 5x5-buffer-name)
+   (5x5-mode)
+   (when (natnump size)
+       (setq 5x5-grid-size size))
    (if (or (not 5x5-grid) (not (= 5x5-grid-size (length (aref 5x5-grid 0)))))
        (5x5-new-game))
    (5x5-draw-grid (list 5x5-grid))
!   (5x5-position-cursor))
  
  (defun 5x5-new-game ()
    "Start a new game of `5x5'."
***************
*** 277,286 ****
  
  (defun 5x5-draw-grid (grids)
    "Draw the grids GRIDS into the current buffer."
!   (let ((buffer-read-only nil))
      (erase-buffer)
      (loop for grid in grids do (5x5-draw-grid-end))
      (insert "\n")
      (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
--- 308,318 ----
  
  (defun 5x5-draw-grid (grids)
    "Draw the grids GRIDS into the current buffer."
!   (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,295 ****
--- 322,344 ----
                                                   (if (5x5-cell grid y x) ?# ?.))))
                        (insert " | "))
                  (insert "\n")))
+     (when 5x5-solver-output
+       (if (= (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-moves))))
***************
*** 415,420 ****
--- 464,747 ----
                  (sit-for 5x5-animate-delay))))
    5x5-grid)
  
+ ;; Arithmetic solver
+ ;;===========================================================================
+ (defun 5x5-grid-to-vec (grid)
+   "Convert GRID to an equivalent Calc matrix of (mod X 2) forms
+ where X is 1 for set positions, and 0 for unset positions."
+   (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) (/= (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 ?= value-to-log ?\n))))
+ 	value))
+   (defmacro 5x5-log-init ())
+   (defmacro 5x5-log (name value) value))
+ 
+ (defun 5x5-solver (grid)
+   "Given some grid GRID, return a list of solution LIST sorted
+ from least Hamming weight to geatest one.
+ 
+    LIST = (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="current grid"
+ 	  ;; and the end of which is dest="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))))
+ 
+ 	  ;; transfer matrix 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 primitive. 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 = 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 = 5, make it generic
+ 	  (transferm-kernel-size
+ 	   (if (= 5x5-grid-size 5)
+ 	       2
+ 	     (error "Transfer matrix rank not known for grid-size != 5")))
+ 
+ 	  ;; TODO: this is hard-coded for grid-size = 5, make it generic.
+ 	  ;;
+ 	  ;; base-change is a 25x25 matrix, where topleft submatrix 23x25 is a
+ 	  ;; diag of 1, and 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    : targetv
+ 	  ;; A    : transferm
+ 	  ;; P    : base-change
+ 	  ;; P^-1 : inv-base-change
+ 	  ;; X    : solution
+ 
+ 	  ;; B = A * X
+ 	  ;; P^-1 * B = P^-1 * A * P * P^-1 * X
+ 	  ;; CX = P^-1 * X
+ 	  ;; CA = P^-1 * A * P
+ 	  ;; CB = P^-1 * B
+ 	  ;; CB = CA * CX
+ 	  ;; CX = CA^-1 * CB
+ 	  ;; X  = 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 = 0, so ctransferm-1-2 = 0 and
+ 	  ;; ctransferm-2-2 = 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 = 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)  = ctransferm-1-1(2x23)  * cx-1(23x1) +
+ 	  ;;                     ctransferm-1-2(2x2)   * cx-2(2x1);
+ 	  ;;   ctarget-2(23x1) = ctransferm-2-1(23x23) * cx-1(23x1) +
+ 	  ;;                     ctransferm-2-2(23x2)  * cx-2(2x1);
+ 	  ;;   by construction
+ 	  ;;   ctransferm-1-2 == zeros(2,2) and ctransferm-2-2 == zeros(23,2)
+ 	  ;;   so
+ 	  ;;   ctarget-2 = ctransferm-2-1*cx-1
+ 	  ;;   so cx-1 = 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 = 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 = P * CX
+ 		  (cons
+ 		   ;; the Hamming Weight is computed by matrix reduction with
+ 		   ;; an ad-hoc operator
+ 		   (math-reduce-vec
+ 		    ;; (cadadr '(vec (mod x 2))) => 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 --- ie K=2 in if the grid is 5x5 --- for I
+ 	      ;; from 0 to K-1, each row rI correspond to the binary
+ 	      ;; representatrion 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 = sum for
+ 	      ;; J=0..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)
+   ;; for the time begin 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.
  
  (defun 5x5-flip-current ()

Diff finished.  Sat May 21 11:30:24 2011

RE: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 4271 bytes --]


Could you please send me the diff compared to my contribution, rather than compared to the official latest 5x5, that would help me understand your suggestion.

VBR,
   Vincent.

> Date: Sat, 21 May 2011 11:36:52 -0300
> From: viniciusjl@ig.com.br
> To: vincent.b.1@hotmail.fr
> Subject: Re: 5x5 Arithmetic solver
> CC: monnier@iro.umontreal.ca; emacs-devel@gnu.org
> 
> Hi Vincent,
> 
> Could I suggest the attached diff?
> 
> Vinicius
> 
> 
> On 05/21/2011 04:15 AM, Vincent Belaïche wrote:
> > Salut Stéfan,
> >
> > Toujours aussi à cheval sur les conventions de codage !
> >
> >>> Please find herein attached a contribution to the 5x5 game. This is an
> >>> arithmetic solver based on a matrix inversion in a (Z/2Z)^25 vector
> >>> space.
> >> Thanks.  A few comments:
> >> - avoid using a tarball and just attach the diff as-is,
> >>   makes it a lot easier to review.
> > noted
> >
> >> - why 5x5-local-variables?
> > That is used in 5x5-mode to imply that all listed variable are made
> > local to that very 5x5 buffer. if after `M-x 5x5' you do a `M-x
> > rename-uniquely' and then `M-x 5x5' again then you have have two
> > independent games.
> >
> >> - explain the changes in the 5x5 function.
> > I had to change slightly the order of operations because setting the
> > mode has to be done before any buffer local 5x5 variable is touched, as
> > precisely those variables are made local by setting the mode
> >
> >> - many of your lines have trailing whitespace.  I generally don't care
> >>   much, about it, but some people do, and it's usually preferable to
> >>   avoid them.  M-x picture-mode C-c C-c gets rid of them for you (as
> >>   a side-effect).
> > Done
> >
> >> - try to keep the first line of docstrings as a self-sufficient sentence
> >>   (because M-x apropos only shows the first line).
> >
> >
> >> - stay within 80 columns.
> > Do you mean that we are still in the 80ies ;-P ?
> >
> > Ok, done.
> >
> >> - your code is not properly indented (e.g. the `grid' argument in
> >>   5x5-grid-to-vec).
> > Done
> >
> >> - Please capitalize your comments and terminate them with a "." or some
> >>   other appropriate punctuation.
> > Some comments by a variable name, so they are not capitalized.
> >
> > Some comments are equations like this:
> >
> > 	   ;; B:= targetv
> > 	   ;; A:= transferm
> > 	   ;; P:= base-change
> > 	   ;; P^-1 := inv-base-change
> > 	   ;; X := solution
> >
> > 	   ;; B = A * X
> > 	   ;; P^-1 * B = P^-1 * A * P * P^-1 * X
> > 	   ;; CX = P^-1 * X
> > 	   ;; CA = P^-1 * A * P
> > 	   ;; CB = P^-1 * B
> > 	   ;; CB = CA * CX
> > 	   ;; CX = CA^-1 * CB
> > 	   ;; X = P * CX
> >
> > I don't think that this is common practice to use a punctuation at the
> > end of an equation.
> >
> > Some other comment is commented out code like this:
> >
> > 	   ;;(ctransferm-1-2 (calcFunc-mcol ctransferm-1-: col-2))
> >
> > This code is not there because I don't need that variable, but I found
> > useful to show how it would be defined.
> >
> > For all the remaining comments I have done it
> >
> >> - 5x5-solve-suggest should have a docstring.
> > Done
> >
> >> - try C-u checkdoc-current-buffer.
> > I get
> >
> > checkdoc-continue: Too many occurrences of \[function].  Use \{keymap}
> > instead
> >
> > Because 5x5 is used many times as if it was
> >
> >
> >> - we need a ChangeLog entry.
> > Here it is:
> >
> > -----------------------------------------------------------------------
> > 2011-05-21  Vincent Belaïche<vincentb1@users.sourceforge.net>
> >
> > 	* play/5x5.el: Add an arithmetic solver to suggest positions to
> > 	click on.
> > -----------------------------------------------------------------------
> >
> >> - I don't understand the "solve step" message (e.g. it said 23 every
> >>   time, even though I followed its suggestions and finished in 12 moves).
> >>
> >>
> > Ask it to Jay, this message is output by Calc, not by 5x5. 23 is due
> > to this that you have to invert a 23x23 matrix. Altough the 5x5 transfer
> > matrix is 25x25, its rank is only 23, so I extract some submatrix to
> > compute the solution.
> >
> >>         Stefan
> >    Vincent.
> >
> 
 		 	   		  

[-- Attachment #2: Type: text/html, Size: 5531 bytes --]

Re: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 3385 bytes --]


[...]

> 
>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.

> 

[...]

> 
>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.
> 

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.
>> 

[...]

> 
>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:
> 
>	(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.
> 
>etc.  You can see plenty of examples of the exact style in the
>ChangeLog files.
> 

Sorry for the scanty Changelog, I was a bit too shy to provide one like
the following:

2011-05-21  Vincent Belaïche  <vincentb1@users.sourceforge.net>

	* 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.
> 
>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.


[-- Attachment #2: 5x5.el.diff --]
[-- Type: text/x-patch, Size: 15620 bytes --]

=== 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 @@
 
 ;;; Commentary:
 
-;; 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.
 
 ;;; TODO:
 
-;; 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?
 
 ;;; Thanks:
@@ -41,7 +41,10 @@
 ;; emacs mode.
 ;;
 ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated
-;; solver.
+;; cracker.
+;;
+;; Vincent Belaïche <vincentb1@users.sourceforge.net> & Jay P. Belanger
+;; <jay.p.belanger@gmail.com> for the math solver.
 
 ;;; Code:
 
@@ -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.")
 
+(defvar 5x5-solver-output nil
+  "List that is is the output of artihmetic solver.
+
+This list L is such that
+
+L = (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.
 
 (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'.
 
-The key bindings for 5x5-mode are:
+The key bindings for `5x5-mode' are:
 
 \\{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 @@
 
   (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 (= 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))
 
 (defun 5x5-new-game ()
   "Start a new game of `5x5'."
@@ -277,10 +310,11 @@
 
 (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 (= (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-moves))))
@@ -415,6 +466,312 @@
                 (sit-for 5x5-animate-delay))))
   5x5-grid)
 
+;; Arithmetic solver
+;;===========================================================================
+(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) (/= (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 ?= 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 = (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="current
+	   ;; grid" and the end of which is dest="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 = 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 = 5, make it generic.
+	   (transferm-kernel-size
+	    (if (= 5x5-grid-size 5) 2
+	      (error "Transfer matrix rank not known for grid-size != 5")))
+
+	   ;; TODO: this is hard-coded for grid-size = 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:= targetv
+	   ;; A:= transferm
+	   ;; P:= base-change
+	   ;; P^-1 := inv-base-change
+	   ;; X := solution
+
+	   ;; B = A * X
+	   ;; P^-1 * B = P^-1 * A * P * P^-1 * X
+	   ;; CX = P^-1 * X
+	   ;; CA = P^-1 * A * P
+	   ;; CB = P^-1 * B
+	   ;; CB = CA * CX
+	   ;; CX = CA^-1 * CB
+	   ;; X = 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 = 0, so ctransferm-1-2 = 0
+	   ;; and ctransferm-2-2 = 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 = 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)  =   ctransferm-1-1(2x23) *cx-1(23x1)
+	   ;;                     + ctransferm-1-2(2x2) *cx-2(2x1);
+	   ;;   ctarget-2(23x1) =   ctransferm-2-1(23x23)*cx-1(23x1)
+	   ;;                     + ctransferm-2-2(23x2)*cx-2(2x1);
+	   ;;   By construction:
+	   ;;
+	   ;;   ctransferm-1-2 == zeros(2,2) and ctransferm-2-2 == zeros(23,2)
+	   ;;
+	   ;;   So:
+	   ;;
+	   ;;   ctarget-2 = ctransferm-2-1*cx-1
+	   ;;
+	   ;;   So:
+	   ;;
+	   ;;   cx-1 = 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 = 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 = P * CX
+		   (cons
+		    ;; The Hamming Weight is computed by matrix reduction
+		    ;; with an ad-hoc operator.
+		    (math-reduce-vec
+		     ;; (cadadr '(vec (mod x 2))) => 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=2 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 = sum for J=0..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.
 
 (defun 5x5-flip-current ()

Re: 5x5 Arithmetic solver

[Eli Zaretskii]

> From: Vincent Belaïche <vincent.b.1@hotmail.fr> 
> Cc: Vincent Belaïche <vincent.b.1@hotmail.fr> ,
>     Stefan Monnier <monnier@iro.umontreal.ca> ,
>     Jay P Belanger <jay.p.belanger@gmail.com> , 
>     davep@davep.org
> Date: Sat, 21 May 2011 20:15:46 +0200
> 
> >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:
> > 
> >	(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.
> > 
> >etc.  You can see plenty of examples of the exact style in the
> >ChangeLog files.
> > 
> 
> Sorry for the scanty Changelog, I was a bit too shy to provide one like
> the following:

Don't be shy.  This is what is expected, thanks.

Re: 5x5 Arithmetic solver

[Stefan Monnier]

>> - why 5x5-local-variables?

> That is used in 5x5-mode to imply that all listed variable are made
> local to that very 5x5 buffer. if after `M-x 5x5' you do a `M-x
> rename-uniquely' and then `M-x 5x5' again then you have have two
> independent games.

So those vars should always be buffer-local and it's a property of those
vars, rather than some kind of "configuration", so just add
(make-variable-buffer-local '<foo>) after each one of those variables.

>> - explain the changes in the 5x5 function.
> I had to change slightly the order of operations because setting the
> mode has to be done before any buffer local 5x5 variable is touched, as
> precisely those variables are made local by setting the mode

I see, thanks.

>> - stay within 80 columns.
> Do you mean that we are still in the 80ies ;-P ? 

Yup, humans's reading abilities are still the same as in the 80ies, sadly.

>> - try C-u checkdoc-current-buffer.
         ^^^
       C-x M-x

> I get 

> checkdoc-continue: Too many occurrences of \[function].  Use \{keymap}
> instead

> Because 5x5 is used many times as if it was 

Yes, the original code already raised some flags.  It's OK, these are
guidelines, which like all rules need to be broken every once in a while.

> -----------------------------------------------------------------------
> 2011-05-21  Vincent Belaïche  <vincentb1@users.sourceforge.net>

> 	* play/5x5.el: Add an arithmetic solver to suggest positions to
> 	click on.

The ChangeLog comment should be more detailed, see the megabytes of
ChangeLog in Emacs as examples, as well as
http://www.gnu.org/prep/standards/html_node/Change-Logs.html.
The ChangeLog should at the very least answer the questions I asked and
mention all the functions that are modified/added/removed.

>> - I don't understand the "solve step" message (e.g. it said 23 every
>> time, even though I followed its suggestions and finished in 12 moves).

> Ask it to Jay, this message is output by Calc, not by 5x5. 23 is due
> to this that you have to invert a 23x23 matrix. Altough the 5x5 transfer
> matrix is 25x25, its rank is only 23, so I extract some submatrix to
> compute the solution.

I see.  Short of changing Calc, you could add your own `message' after
the call to Calc that produces those messages, so it's a bit more clear
that these are intermediate messages not pertaining to the final answer.


        Stefan

Re: 5x5 Arithmetic solver

[Stefan Monnier]

> 2011-05-21  Vincent Belaïche  <vincentb1@users.sourceforge.net>

> 	* 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.

Thanks.  Note that usually when you add a new functions, you can just
say "(fun1, fun2, fun3): New functions" without having to explain what
it does.


        Stfean

RE: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]



[...]
> 
> Thanks.  Note that usually when you add a new functions, you can just
> say "(fun1, fun2, fun3): New functions" without having to explain what
> it does.
> 

Ok, I will commonalize those that can be.

Concerning the make-variable-local, I had the feeling that it is slightly better practice to do an explicit "dolist" --- I think that it is what is done in org-mode for instance --- at it allows to set the variable at the same time.

> 
>         Stfean
> 

   Vincent
 		 	   		  

[-- Attachment #2: Type: text/html, Size: 778 bytes --]

Re: 5x5 Arithmetic solver

[Stefan Monnier]

>> Thanks.  Note that usually when you add a new functions, you can just
>> say "(fun1, fun2, fun3): New functions" without having to explain what
>> it does.
> Concerning the make-variable-local,

Beware: I'm talking about make-variable-buffer-local, which is different
(but I think it's what you want here).

> I had the feeling that it is slightly
> better practice to do an explicit "dolist"

I'm not sure I understand.
The way I see it, we could have a defvar-local macro, i.e. the
make-variable-buffer-local really belongs next to the
corresponding defvar.

> --- I think that it is what is done in org-mode for instance --- at it
> allows to set the variable at the same time.

If you do want to use make-local-variable rather than
make-variable-buffer-local, then the call to make-local-variable indeed
belongs together with the corresponding `set' (we could have
a setq-local macro for it).


        Stefan

Re: 5x5 Arithmetic solver

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 3465 bytes --]

Cher Stéfan & tous,

> Beware: I'm talking about make-variable-buffer-local, which is
> different (but I think it's what you want here).

Yes, this is what I meant, but I use this function so seldom that I
mispelled it, and as I am my own spell-checker...

Ok, I removed the function list and used a macro 5x5-defvar-local
instead according to your kind recommendations.

I also added a final message "5x5 Solution computation done." ---
hopefully this is correct English --- to mask the obscure Calc verbiage.

I also realized that there was a bug in 5x5, when making random grids,
it was sometimes impossible for the solver to find a solution, and that
happened while I was demonstrating the solver to my 6 years old son ---
then I had to explained the reason for that kind of failure, which was
incredibly more difficult than understand it and find a correction for
it...

I realized that the random grid generator was indeed making a grid whose
each position is random, rather than making a set of random 5x5
moves. The former does not ensure the existence of a solution, while the
latter does. I don't know if that was the initial intention to have this
behaviour, but as « à l'impossible nul n'est tenu », I considered it a
bug, and I corrected it along with providing the solver. So my
contribution is 3 fold:

I   Add an arithmetic solver

II  Make 5x5 multisession

III Ensure that random grids always have a solution --- this is a quick
    patch that makes it only when the grid size is 5, but I am not sure
    that that would work for other size, as I have not proved it
    mathematically.

Here is the updated Changelog, I commonalized comment when possible.

-----------------------------------------------------------------------
2011-05-22  Vincent Belaïche  <vincentb1@users.sourceforge.net>

	* play/5x5.el: I/ Add an arithmetic solver to suggest positions to
	click on. II/ Make 5x5 multisession. III/ Ensure that random grids
	always have a solution in grid size = 5 cases
	(5x5-mode-map): Add keybinding to function `5x5-solve-suggest'.
	(5x5-solver-output): New defvar, output of function
	`5x5-solve-suggest'.
	(5x5-grid, 5x5-x-pos, 5x5-y-pos, 5x5-moves, 5x5-cracking): Make
	these variables buffer local to achieve 5x5 multi-session-ness.
	(5x5): Set 5x5-grid-size only if SIZE is non-negative.
	(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.
	(5x5-randomize): Use 5x5-make-move instead of 5x5-flip-cell to
	randomize a grid so that we ensure that there is always a
	solution.
	(5x5-make-random-grid) allow other movement than flipping.
-----------------------------------------------------------------------

VBR,
   Vincent


[-- Attachment #2: 5x5.el.diff --]
[-- Type: text/x-patch, Size: 16986 bytes --]

=== modified file 'lisp/play/5x5.el'
--- lisp/play/5x5.el	2011-04-21 12:24:46 +0000
+++ lisp/play/5x5.el	2011-05-22 20:20:45 +0000
@@ -24,15 +24,15 @@
 
 ;;; Commentary:
 
-;; 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.
 
 ;;; TODO:
 
-;; 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?
 
 ;;; Thanks:
@@ -41,7 +41,10 @@
 ;; emacs mode.
 ;;
 ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated
-;; solver.
+;; cracker.
+;;
+;; Vincent Belaïche <vincentb1@users.sourceforge.net> & Jay P. Belanger
+;; <jay.p.belanger@gmail.com> for the math solver.
 
 ;;; Code:
 
@@ -89,19 +92,25 @@
 
 ;; Non-customize variables.
 
-(defvar 5x5-grid nil
+(defmacro 5x5-defvar-local (var value doc)
+  "Define VAR to VALUE with documentation DOC and make it buffer local."
+  `(progn
+     (defvar ,var ,value ,doc)
+     (make-variable-buffer-local (quote ,var))))
+
+(5x5-defvar-local 5x5-grid nil
   "5x5 grid contents.")
 
-(defvar 5x5-x-pos 2
+(5x5-defvar-local 5x5-x-pos 2
   "X position of cursor.")
 
-(defvar 5x5-y-pos 2
+(5x5-defvar-local 5x5-y-pos 2
   "Y position of cursor.")
 
-(defvar 5x5-moves 0
+(5x5-defvar-local 5x5-moves 0
   "Moves made.")
 
-(defvar 5x5-cracking nil
+(5x5-defvar-local 5x5-cracking nil
   "Are we in cracking mode?")
 
 (defvar 5x5-buffer-name "*5x5*"
@@ -134,10 +143,28 @@
     (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.")
 
+(5x5-defvar-local 5x5-solver-output nil
+  "List that is is the output of artihmetic solver.
+
+This list L is such that
+
+L = (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.")
+
+
 ;; Menu definition.
 
 (easy-menu-define 5x5-mode-menu 5x5-mode-map "5x5 menu."
@@ -146,6 +173,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,7 +186,7 @@
 (defun 5x5-mode ()
   "A mode for playing `5x5'.
 
-The key bindings for 5x5-mode are:
+The key bindings for `5x5-mode' are:
 
 \\{5x5-mode-map}"
   (kill-all-local-variables)
@@ -194,14 +222,14 @@
 
   (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 (= 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))
 
 (defun 5x5-new-game ()
   "Start a new game of `5x5'."
@@ -277,10 +305,11 @@
 
 (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 +319,23 @@
                                                  (if (5x5-cell grid y x) ?# ?.))))
                       (insert " | "))
                 (insert "\n")))
+    (when 5x5-solver-output
+      (if (= (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-moves))))
@@ -304,13 +350,14 @@
   "Keep track of how many moves have been made."
   (incf 5x5-moves))
 
-(defun 5x5-make-random-grid ()
+(defun 5x5-make-random-grid (&optional move)
   "Make a random grid."
+  (setq move (or move (symbol-function '5x5-flip-cell)))
   (let ((grid (5x5-make-new-grid)))
     (loop for y from 0 to (1- 5x5-grid-size) do
           (loop for x from 0 to (1- 5x5-grid-size) do
                 (if (zerop (random 2))
-                    (5x5-flip-cell grid y x))))
+                    (funcall move grid y x))))
     grid))
 
 ;; Cracker functions.
@@ -415,6 +462,312 @@
                 (sit-for 5x5-animate-delay))))
   5x5-grid)
 
+;; Arithmetic solver
+;;===========================================================================
+(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) (/= (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 ?= 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 = (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="current
+	   ;; grid" and the end of which is dest="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 = 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 = 5, make it generic.
+	   (transferm-kernel-size
+	    (if (= 5x5-grid-size 5) 2
+	      (error "Transfer matrix rank not known for grid-size != 5")))
+
+	   ;; TODO: this is hard-coded for grid-size = 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:= targetv
+	   ;; A:= transferm
+	   ;; P:= base-change
+	   ;; P^-1 := inv-base-change
+	   ;; X := solution
+
+	   ;; B = A * X
+	   ;; P^-1 * B = P^-1 * A * P * P^-1 * X
+	   ;; CX = P^-1 * X
+	   ;; CA = P^-1 * A * P
+	   ;; CB = P^-1 * B
+	   ;; CB = CA * CX
+	   ;; CX = CA^-1 * CB
+	   ;; X = 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 = 0, so ctransferm-1-2 = 0
+	   ;; and ctransferm-2-2 = 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 = 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)  =   ctransferm-1-1(2x23) *cx-1(23x1)
+	   ;;                     + ctransferm-1-2(2x2) *cx-2(2x1);
+	   ;;   ctarget-2(23x1) =   ctransferm-2-1(23x23)*cx-1(23x1)
+	   ;;                     + ctransferm-2-2(23x2)*cx-2(2x1);
+	   ;;   By construction:
+	   ;;
+	   ;;   ctransferm-1-2 == zeros(2,2) and ctransferm-2-2 == zeros(23,2)
+	   ;;
+	   ;;   So:
+	   ;;
+	   ;;   ctarget-2 = ctransferm-2-1*cx-1
+	   ;;
+	   ;;   So:
+	   ;;
+	   ;;   cx-1 = 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 = 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 = P * CX
+		   (cons
+		    ;; The Hamming Weight is computed by matrix reduction
+		    ;; with an ad-hoc operator.
+		    (math-reduce-vec
+		     ;; (cadadr '(vec (mod x 2))) => 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=2 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 = sum for J=0..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)))
+	     )))
+      (message "5x5 Solution computation done.")
+      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.
 
 (defun 5x5-flip-current ()
@@ -490,7 +843,7 @@
     (setq 5x5-x-pos (/ 5x5-grid-size 2)
           5x5-y-pos (/ 5x5-grid-size 2)
           5x5-moves 0
-          5x5-grid  (5x5-make-random-grid))
+          5x5-grid  (5x5-make-random-grid (symbol-function '5x5-make-move)))
     (unless 5x5-cracking
       (5x5-draw-grid (list 5x5-grid)))
     (5x5-position-cursor)))

Re: 5x5 Arithmetic solver

[Stefan Monnier]

> Here is the updated Changelog, I commonalized comment when possible.

Thanks, installed (with a slightly terser comment).


        Stefan