Re: Re: Arithmetic Puzzle (so simple it's hard)
- To: mathgroup at smc.vnet.net
- Subject: [mg71540] Re: [mg71496] Re: [mg71301] Arithmetic Puzzle (so simple it's hard)
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 22 Nov 2006 05:22:22 -0500 (EST)
- References: <200611141006.FAA06684@smc.vnet.net> <200611202311.SAA18418@smc.vnet.net>
János wrote:
> On Nov 14, 2006, at 5:06 AM, Bruce Colletti wrote:
>
>
>>How would this problem be solved in Mathematica?
>>
>>BUT * ASK = FEAST, where each letter is a 1-digit number, no two
>>letters may stand for the same number, and the letters are in
>>{0,1,2,4,5,6,7,9}.
>>
>>Thankx.
>>
>>Bruce
>
>
> Here is a latecomer newbie, without brute force :)
>
> I was wondering if a genetical algorithm would find any solution, so I
> wrote one.
>
> Started with some parameters:
> [...]
> With this relatively high population size of 2^16 after three
> generations a solution was found - five times :). It needs a minimum
> 2^10 population size to iterate the main body more than once. It is
> looking only for those solutions where B aka b is not zero.
>
> Any suggestions to make it faster would be highly appreciated. /It
> took 526 seconds to run with above parameters/
>
> J�nos
I'll instead point out that NMinimize can be adapted to this sort of
problem. I do not claim it is a particularly good fit, and indeed the
speed is worse than brute force. All the same this approach might be of
interest for other optimization problems involving permutations.
We define an auxiliary function that converts a list of reals from zero
to n into a permutation of Range[n]. The idea is to start with Range[n],
then walk the input list, using the kth element to indicate where in a
shuffle to swap with the current kth element of the permutation under
construction.
Use of Compile perhaps not needed for n=8, the case in question. Also we
really force them to be a hair larger than zero because otherwise we
sometimes get values driven down to zero and the permutation finder
fails to work as it should.
getPerm = Compile[{{vec,_Real,1}}, Module[
{p1, len=Length[vec], k, nlen},
p1 = Range[len];
nlen = N[len];
Do [
k = Ceiling[j-1 + vec[[j]]/nlen*(nlen-j+1)];
p1[[{j,k}]] = p1[[{k,j}]];
, {j,len}];
p1
]]
I set this up as a quadratic optimization. Well, not really, actually
it's quartic. But the name "QP" I suppose could apply to that as well.
We minimize the square of the difference of the two values, with the
variables {b,u,...} taking on the permutation given by an auxiliary set
of variables {x[1],x[2],...,x[8]}. We use the DifferentialEvolution
method and allow some settings as parameters. Quite possibly other
methods would work better.
QP[cp_, it_, sp_] := Module[
{letters, len, values, vars, x, rul, rnges,
obj, eval, nmin, vals},
letters = {b,u,t,a,s,k,f,e};
len = Length[letters];
values = {0,1,2,4,5,6,7,9};
vars = Array[x,len];
rnges = Map[0.01<=#<=len&, vars];
rul[vars:{__Real}] := Thread[letters->values[[getPerm[vars]]]];
obj = ((100*b+10*u+t) * (100*a+10*s+k) -
(10000*f+1000*e+100*a+10*s+t))^2;
eval[vv:{__Real}] := obj/.rul[vv];
{nmin,vals} = NMinimize[{eval[vars],rnges},
vars, MaxIterations->it,
Method->{DifferentialEvolution,SearchPoints->sp,
PostProcess->False,CrossProbability->cp}];
{nmin, Thread[letters->values[[getPerm[vars/.vals]]]]}
]
With crossover set fairly high we get a correct result relatively fast.
In[65]:= Timing[QP[.9, 100, 20]]
Out[65]= {2.22, {0., {b -> 0, u -> 5, t -> 6, a -> 4,
s -> 9, k -> 1, f -> 2, e -> 7}}}
Also it seems to be reasonably stable insofar as increasing some
parameters (SearchPoints and/or MaxIterations) usually (based on a
handful of experiments) still gives a correct result.
Again, I don't particularly recommend this approach for an exact
factorization problem. It does however illustrate a way in which one
might approach combinatorial optimization heuristically, in that it
converts a list of reals to a permutation. I would not be surprised if
there are better methods, improvements to be made by use of "local"
refinement (e.g. further swapping of pairs), other optimization
approaches that work better, etc.
Daniel Lichtblau
Wolfram Research
- References:
- Arithmetic Puzzle (so simple it's hard)
- From: Bruce Colletti <vze269bv@verizon.net>
- Re: Arithmetic Puzzle (so simple it's hard)
- From: János <janos.lobb@yale.edu>
- Arithmetic Puzzle (so simple it's hard)