## 9500 Reputation

18 years, 131 days

## Solving a Numbrix Puzzle with Logic...

Maple

Solving a Numbrix Puzzle with Logic

 Background Parade magazine, a filler in the local Sunday newspaper, contains a Numbrix puzzle, the object of which is to find a serpentine path of consecutive integers, 1 through 81, through a nine by nine grid.  The puzzle typically specifies the content of every other border cell.   The Maple Logic  package has a procedure, Satisfy , that can be used to solve this puzzle.  Satisfy is a SAT-solver; given a boolean expression it attempts to find a set of equations of the form , where are the boolean variables in the given expression and are boolean values (true or false) that satisfy the expression (cause it to evaluate true).   A general technique to solve this and other puzzles with Satisfy is to select boolean-values variables that encode the state of the puzzle (a trial solution, whether valid or not), generate a boolean-expression of these variables that is satisfied (true) if and only if the variables are given values that correspond to a solution, pass this expression to Satisfy, then translate the returned set of boolean values (if any) to the puzzle solution.

Setup

Assign a matrix that defines the grid and the initial position.  Use zeros to indicate the cells that need values. To make it easy to inspect the expressions, a small 2 x 3 matrix is used for this demo---a full size example is given at the end.

 > M := Matrix(2,3, {(1,1) = 1, (1,3) = 5}); (2.1)

Extract the dimensions of the Matrix

 > (m,n) := upperbound(M); (2.2)
 Boolean Variables Let the boolean variable x[i,j,k] mean that cell (i,j) has value k. For example, x[2,3,6] is true when cell (2,3) contains 6, otherwise it is false. There are boolean variables.

Initial Position

The initial position can be expressed as the following and-clause.

 > initial := &and(seq(seq(ifelse(M[i,j] = 0, NULL, x[i,j,M[i,j]]), i = 1..m), j = 1..n)); (4.1)

The requirement that an interior cell with value k is adjacent to the cell with value k+1 can be expressed as the implication

x[i,j,k] &implies &or(x[i-1,j,k+1], x[i+1,j,k+1], x[i,j-1,k+1], x[i,j+1,k+1])

Extending this to handle all cells results in the following boolean expression.

 > adjacent := &and(seq(seq(seq(          x[i,j,k] &implies &or(NULL                                , ifelse(1 (5.1)

All Values Used

The following expression is true when each integer , from 1 to , is assigned to one or more cells.

 > allvals := &and(seq(seq(&or(seq(x[i,j,k], k=1..m*n)), i=1..m), j=1..n)); (6.1)

Single Value

The following expression is satisfied when each cell has no more than one value.

 > single := ¬ &or(seq(seq(seq(seq(x[i,j,k] &and x[i,j,kk], kk = k+1..m*n), k = 1..m*n-1), i = 1..m), j = 1..n)); (7.1)

Solution

Combine the boolean expressions into a a single and-clause and pass it to Satisfy.

 > sol := Logic:-Satisfy(&and(initial, adjacent, allvals, single)); (8.1)

Select the equations whose right size is true

 > sol := select(rhs, sol); (8.2)

Extract the lhs of the true equations

 > vars := map(lhs, sol); (8.3)

Extract the result from the indices of the vars and assign to a new Matrix

 > S := Matrix(m,n):
 > for v in vars do S[op(1..2,v)] := op(3,v); end do:
 > S; (8.4)
 Procedure We can now combine the manual steps into a procedure that takes an initialized Matrix and fills in a solution. Numbrix := proc( M :: ~Matrix, { inline :: truefalse := false } )

Example

Create the initial position for a 9 x 9 Numbrix and solve it.

 > P := Matrix(9, {(1,1)=11, (1,3)=7, (1,5)=3, (1,7)=81, (1,9)=77, (3,9)=75, (5,9)=65, (7,9)=55, (9,9)=53                , (9,7)=47, (9,5)=41, (9,3)=39, (9,1)=37, (7,1)=21, (5,1)=17, (3,1)=13}); (10.1)
 > CodeTools:-Usage(Numbrix(P));
 memory used=0.77GiB, alloc change=220.03MiB, cpu time=15.55s, real time=12.78s, gc time=3.85s (10.2)
 >

numbrix.mw

## Improve Your Chess Rating with Math...

Over the holidays I reconnected with an old friend and occasional
chess partner who, upon hearing I was getting soundly thrashed by run
of the mill engines, recommended checking out the ChessTempo site.  It
has online tools for training your chess tactics.  As you attempt to
solve chess problems your rating is computed depending on how well you
do.  The chess problems, too, are rated and adjusted as visitors
attempt them.  This should be familar to any chess or table-tennis
player.  Rather than the Elo rating system, the Glicko rating system is
used.

You have a choice of the relative difficulty of the problems.
After attempting a number of easy puzzles and seeing my rating slowly
climb, I wondered what was the most effective technique to raise my
rating (the classical blunder).  Attempting higher rated problems would lower my
solving rate, but this would be compensated by a smaller loss and
larger gain.  Assuming my actual playing strength is greater than my
current rating (a misconception common to us patzers), there should be a
rating that maximizes the rating gain per problem.

The following Maple module computes the expected rating change
using the Glicko system.

```Glicko := module()

export DeltaRating
,  ExpectedDelta
,  Pwin
;

# Return the change in rating for a loss and a win
# for player 1 against player2
DeltaRating := proc(r1,rd1,r2,rd2)
local E, K, g, g2, idd, q;

q := ln(10)/400;
g := rd -> 1/sqrt(1 + 3*q^2*rd^2/Pi^2);
g2 := g(rd2);
E := 1/(1+10^(-g2*(r1-r2)/400));
idd := q^2*(g2^2*E*(1-E));

K := q/(1/rd1^2+idd)*g2;

(K*(0-E), K*(1-E));

end proc:

# Compute the probability of a win
# for a player with strength s1
# vs a player with strength s2.

Pwin := proc(s1, s2)
local p;
p := 10^((s1-s2)/400);
p/(1+p);
end proc:

# Compute the expected rating change for
# player with strength s1, rating r1 vs a player with true rating r2.
# The optional rating deviations are rd1 and rd2.

ExpectedDelta := proc(s1,r1,r2,rd1 := 35, rd2 := 35)
local P, l, w;
P := Pwin(s1,r2);
(l,w) := DeltaRating(r1,rd1,r2,rd2);
P*w + (1-P)*l;
end proc:

end module:
```

Assume a player has a rating of 1500 but an actual playing strength of 1700.  Compute the expected rating change for a given puzzle rating, then plot it.  As expected the graph has a peak.

```Ept := Glicko:-ExpectedDelta(1700,1500,r2):
plot(Ept,r2 = 1000...2000);
``` Compute the optimum problem rating

```fsolve(diff(Ept,r2));

{r2 = 1599.350691}
```

As your rating improves, you'll want to adjust the rating of the problems (the site doesn't allow that fine tuning). Here we plot the optimum puzzle rating (r2) for a given player rating (r1), assuming the player's strength remains at 1700.

```Ept := Glicko:-ExpectedDelta(1700, r1, r2):
dEpt := diff(Ept,r2):
r2vsr1 := r -> fsolve(eval(dEpt,r1=r)):
plot(r2vsr1, 1000..1680);
``` Here is a Maple worksheet with the code and computations.

Glicko.mw

Later

After pondering this, I realized there is a more useful way to present the results. The shape of the optimal curve is independent of the user's actual strength. Showing that is trivial, just substitute a symbolic value for the player's strength, offset the ratings from it, and verify that the result does not depend on the strength.

```Ept := Glicko:-ExpectedDelta(S, S+r1, S+r2):
has(Ept, S);
false
```

Here's the general curve, shifted so the player's strength is 0, r1 and r2 are relative to that.

```r2_r1 := r -> rhs(Optimization:-Maximize(eval(Ept,r1=r), r2=-500..0)[]):
p1 := plot(r2_r1, -500..0, 'numpoints'=30);
``` Compute and plot the expected points gained when playing the optimal partner and your rating is r-points higher than your strength.

```EptMax := r -> eval(Ept, [r1=r, r2=r2_r1(r)]):
plot(EptMax, -200..200, 'numpoints'=30, 'labels' = ["r","Ept"]);
``` When your playing strength matches your rating, the optimal opponent has a relative rating of

```r2_r1(0);
-269.86
```

The expected points you win is

```evalf(EptMax(0));
0.00956
```

## Musings on Package Defaults...

Maple

Am pondering how to best provide user-configurable options for a few packages I've written. The easiest method is to use global variables, preassign their default values during the package definition (but don't protect them) and save them with the mla used for the package. A user could then assign new values, say in their Maple initialization file or in a worksheet.  For example

```  FooDefaultBar := true:
FooDefaultBaz := false:
```

That works for a few variables, but is unwieldy if there are many, as the names generally have to be long and verbose to avoid accidental collision. Better may be to use a single record

```  FooDefaults := Record('Bar' = true, 'Baz' = false):
```

To change one or more values, the user could do

```   use FooDefaults in
Bar := false;
end use:
```

A drawback of using a global variable or record is that the user can assign any type to the variable, so the using program will have to check it. While one could use a record with typed fields, for example,

```  FooDefaults := Record('Bar' :: truefalse = true, 'Baz' :: truefalse := false):
```

that only has an effect on assignments if kernelopts(assertlevel) is 2, which isn't the default.

A different approach is to use a Maple object to handle configuration variables. The object should be defined separate from the package it is configuring, so that the target package doesn't have to be loaded to customize its configuration. I've created a small object for this, but am not satisfied with its usage. Here is how it is currently used

```# Create configuration object for package foo
Configure('fooDefaults', 'Bar' :: truefalse = true, 'Baz' :: truefalse = false):
```

The Assign method is used to reassign one or more fields

```Assign(fooDefaults, 'Bar' = false, 'Baz' = true):
```

If a value does not match the declared type, an error is raised. Values from the object are available via the index operator:

```   fooDefaults['Bar'];
```

Am not wild about this approach, the assignment seems clunky and would require a user to consult a help page to learn about the existence of the Assign method, though that would probably be necessary, regardless, to learn about the defaults themselves. Any thoughts on improvements? Attached is the current code.

```Configure := module()

option object;

local Default # record of values
, Type    # record of types
, nomen   # string corresponding to name of assigned object
, all :: static := {}
;

export
ModuleApply :: static := proc()
Object(Configure, _passed);
end proc;

export
ModuleCopy :: static := proc(self :: Configure
, proto :: Configure
, nm :: name
, defaults :: seq(name :: type = anything)
, \$
)
local eq;
self:-Default := Record(defaults);
self:-Type    := Record(seq(op([1,1], eq) = op([1,2], eq), eq = [defaults]));
self:-nomen   := convert(nm,'`local`');
nm := self;
protect(nm);
self:-all := {op(self:-all), self:-nomen};
nm;
end proc;

export
ModulePrint :: static := proc(self :: Configure)
local default;
if self:-Default :: 'record' then
self:-nomen(seq(default = self:-Default[default]
, default = exports(self:-Default)
));
else
self:-nomen();
end if;
end proc;

export
Assign :: static := proc(self :: Configure
, eqs :: seq(name = anything)
, \$
)
local eq, nm, val;
# Check eqs
for eq in [eqs] do
(nm, val) := op(eq);
if not assigned(self:-Default[nm]) then
error "%1 is not a default of %2", nm, self:-nomen;
elif not val :: self:-Type[nm] then
error ("%1 must be of type %2, received %3"
, nm, self:-Type[nm], val);
end if;
end do;
# Assign defaults
for eq in [eqs] do
(nm, val) := op(eq);
self:-Default[nm] := val;
end do;
self;
end proc;

export
`?[]` :: static := proc(self :: Configure
, indx :: list
, val :: list
)
local opt;
opt := op(indx);
if not assigned(self:-Default[opt]) then
error "'%0' is not an assigned field of this Configure object", indx[];
elif nargs = 2 then
self:-Default[opt];
elif not val :: [self:-Type[opt]] then
error "value for %1 must be of type %2", opt, self:-Type[opt];
else
self:-Default[opt] := op(val);
end if;
end proc;

export
ListAll :: static := proc(self :: Configure)
self:-all;
end proc;

end module:
```

Later: Observing that this is just a glorified record with an assurance that the values match their declared types, but with less nice methods to set and get the values, I concluded that what I really want is a record that enforces types regardless the setting of . Maybe created with

```   FooDefaults := Record[strict]('Bar' :: truefalse = true, 'Baz :: truefalse = false):
```

In the meantime, I'll probably just use a record and not worry about whether a user has assigned an invalid value.

## Bark, a Maple Package for Creating Shell...

Maple 2017

I write shell scripts that call Maple to automate frequent tasks. Because I prefer writing Maple code to shell code, I've created a Maple package, Bark, that generates a shell script from Maple source code. It provides a compact notation for defining both optional and positional command-line parameters, and a mechanism to print a help page, from the command-line, for the script. The optional parameters can be both traditional single letter Unix options, or the more expressive GNU-style long options.

As an example, here is the Maple code, using Bark, for a `hello-world` script.

``````hello := module()
export
Parser := Bark:-ArgParser(NULL
, 'prologue' = ( "Print `Hello, World!'" )
, 'opts' = ['help' :: 'help' &c "Print this help page"]
);
export
ModuleApply := proc(cmdline :: string := "")
Bark:-ArgParser:-Parse(Parser, cmdline);
Bark:-printf("Hello, World!\n");
NULL;
end proc;
end module:
``````

The following command creates and installs the shell script in the user's bin directory.

``````Bark:-CreateScript("hello", hello
, 'add_libname' = Bark:-SaveLib(hello, 'mla' = "hello.mla")
):
``````

The hello script is executed from the command-line as

``````\$ hello
Hello,  World!
``````

Pass the -h (or --help) option to display the help.

``````\$ hello -h
Usage: hello [-h|--help] [--]

Print `Hello, World!'

Optional parameters:
-h, --help Print this help page
``````

CreateScript creates two files that are installed in the bin directory: the shell script and a Maple archive file that contains the Maple procedures. The shell script passes its argument in a call to the parser (a Maple procedure) saved in the archive file (.mla file). Here's the created shell script for the hello command:

``````#!/usr/bin/env sh
MAPLE='/home/joe/maplesoft/sandbox/main/bin/maple'
CMD_LINE=\$(echo \$0; for arg in "\$@"; do printf '%s\n' "\$arg"; done)
echo "hello(\"\$CMD_LINE\");" | "\$MAPLE" -q -w2 -B --historyfile=none -b '/home/joe/bin/hello.mla'
``````

I've used Bark on Linux and Windows (with Cygwin tools). It should work on any unix-compatible OS with the Bash shell. If you use a different shell that does not work with it, let me know and I should be able to modify the CreateScript command to have options for specific shells.

Bark is available on the MapleCloud. To install it, open the MapleCloud palette in Maple, select packages in the drop-down menu and go to the New tab (or possibly the Popular tab). You will also need the TextTools package which is also on the MapleCloud. The intro page for Bark has a command that automatically installs TextTools. Alternatively, executing the following commands in Maple 2017 should install both TextTools and Bark.

``````PackageTools:-Install~([5741316844552192,6273820789833728],'overwrite'):
Bark:-InstallExamples('overwrite'):
``````

The source for a few useful scripts are included in the examples directory of the installed Bark toolbox. Maple help pages are included with Bark, use "Bark" as the topic.

## CodeBuilder: Build a package from code e...

Maple

A number of MaplePrimers have asked how one might use the section and subsections of a Maple worksheet to structure the source code of an extended Maple package.  The usual answer is that it cannot be done; a module-based Maple package must be assigned in a single input region in a worksheet.  A recommended alternative is to write the source in text files and use either command line tools or the Maple read command from a worksheet to assign the package.  Because the read command handles Maple preprocessor macros, specifically the \$include macro, the source can be conveniently split into smaller files.

I prefer this file-based method for development because text files are generally more robust than Maple worksheets, can be edited with the user's preferred editor, can be put under version control, and can be searched and modified by standard Unix-based tools.  However, not everyone is familiar with this method of development.  With that in mind, I wrote a small Maple package, CodeBuilder, that permits splitting the source of a Maple package (or any Maple code) into separate code edit regions in a standard Maple worksheet, using \$include macros to include the source of other regions.  To build the package, the code edit regions are written to external files, using the names of the regions as the local file name relative to a temporary directory.

The package includes a method to run mint on the source code.  The result can be either printed in the worksheet or displayed in a pop-up maplet that allows selecting the infolevel and the region to check.

CodeBuilder includes help pages and a simple example (referenced from the top-level help page) demonstrating the usage.  To install the package, unzip the attached zip file and follow the directions in the README file.

CodeBuilder-1-0-3.zip

Errata Just noticed that a last minute change broke some of the code.  Do not bother with the 1-0-1 version; I'll upload a new version shortly.  The latest version (1-0-3) is now available.

 1 2 3 4 5 6 7 Last Page 1 of 16
﻿