PowerShell Diversion #4: Discussion

[Follow-up discussion for PowerShell Diversion #4 ]

OK, first the stats:

1. There are 86 solutions if you allow for leading zeros in EFGH and consider ‘AB x CD’ to be distinct from ‘CD x AB’
2. There are 52 solutions if you rule out any with leading zeros in EFGH.  Leading zeros in AB or CD are not a consideration since there are no solutions where that is the case.
3. There are 26 solutions when leading zeros are disallowed and ‘AB x CD’ is considered to be the same as ‘CD x AB’.
4. The largest and smallest values of EFGH are, respectively:  6840 and 0456 (allowing leading zeros), or 6840 and 1058 (disallowing leading zeros).

So, how do you calculate all this?  There are two key things we need to know.  The first is how to build an executable expression one piece at a time. For example, if we set some variables like this:

$a = 5 $b = 7 $c = 2 $d = 4

We can create a string like this: “$a$b * $c$d”, which will generate this output if ‘run’ by itself: 57 * 24.  We get the standard variable replacement, but it didn’t execute the calculation that the string represents.  We can force it to do the calculation using Invoke-Expression:

Invoke-Expression “$a$b * $c$d”

Which gives the expected output: 1568.  We can go a step further:

$e = 1; $f =3; $g = 6; $h = 8
Invoke-Expression  “$a$b * $c$d -eq $e$f$g$h”

Which returns ‘true’.  Notice that the full expression, “57 x 24 = 1368”, is actually one of the solutions to the problem, since all of the digits are unique and the equation is true.  If you set $h = 9, then the digits are all still unique, but Invoke-Expression returns ‘false’, since the equation is no longer valid.  Using this technique we can easily check any possible solution to see if it represents a valid equation.

Now we know how to validate an expression that we build at runtime, we need to find a way to generate candidate expressions to test.  As this is a combinatorial problem, I am guessing there is no shortcut to finding the answers, though if you know different, I’m happy to be proved wrong!  The solution below uses simple brute-force to generate all possible combinations of digits, discarding any that fail the test.

As the final script has formatting issues due to the blog theme, I’ll describe the general approach and you can download the full solution from the link at the end. 

Firstly, we need an array of the digits:

$digits = 0 .. 9

Then we need to loop through these setting $a to each digit, then $b to each remaining digit, and so on:

foreach ($a in $digits) {     foreach ($b in ($digits -ne $a))     {         foreach($c in ($digits -ne $a -ne $b))         {             # rest of processing omitted         }     } }

This nesting carries on, with each level looping through the unassigned digits until we reach $h, at which point we apply the Invoke-Expression test to see if the expression is valid – since we only use the unused digits from the previous step at each stage, we will not generate any duplicates, so anything that passes the test is not only a valid equation, but also guaranteed to have all digits unique – it is a solution to the original problem.

At this point, we could simply print out the correct solutions as we find them.  However, as the original question asked for some statistics, we need a way of counting the solutions.  Rather than run the script multiple times, a more efficient method is to capture each solution into a collection, that way we need only run the script once to get the solutions and we can sort, filter and count the them later.  The final step is to create a PsObject for each solution and add it to an array:

if (Invoke-Expression "$a$b * $c$d -eq $e$f$g$h")
{
     $solutions += New-Object PsObject -Property ` 
                   @{AB="$a$b"; CD="$c$d";EFGH="$e$f$g$h"} 
}

Once we have the array, we can count the solutions (and find the maximum an minimum values for EFGH) like this:

$solutions | Measure-Object EFGH -Maximum -Minimum

Get the full script here.