4
\$\begingroup\$

Not sure how to make the title smaller. I was reading the question A truly amazing way of making the number 2016 and some of the answers referred to programatically determining the answer set.

What I am doing is related to that in concept. Given a range of number 1 to X determine all possible mathematical expressions that can be used with those numbers and group the results together to see which whole numbers prevail.

function ConvertTo-Base
{
    [CmdletBinding()]
    param (
        [parameter(ValueFromPipeline=$true,Mandatory=$True, HelpMessage="Base10 Integer number to convert to another base")]
        [int]$Number=1000,
        [parameter(Mandatory=$True)]
        [ValidateRange(2,20)]
        [int]$Base
    )
    [char[]]$alphanumerics = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    do
    {
        # Determine the remainder
        $Remainder = ($Number % $Base)
        # Get the associated character and add it to the beginning of the string.
        $newBaseValue = "$($alphanumerics[$Remainder])$newBaseValue"
        # Adjust the number to remove the calculated portion
        $Number = ($Number - $Remainder) / $Base
        # Loop until we have processed the whole number
    } while ($Number -gt 0)

    return $newBaseValue
}

# Variables
$maxRange = 3                  #13 would make for the largest values 13!. Cap the script as 13
$lowCountThreshold = 1         # Only show group results where the match exists more than five times. 

# Mathematical Operators 
[char[]]$operators = "+-*/"

# Define the number range for calculations. 13 would make for the largest values 13!. Cap the script as 13
$range = 1..$maxRange

# Build the format string that will be used for invoking. Will look like 1{0}2{1}3. Acting as place holders for mathematic operators
$formatString = -join (1..($range.count - 1) | ForEach-Object{"$_{$([int]$_ - 1)}"}) + $range[-1]

# Determine the number of possible permutations of those operators inbetween the number set. 
$permutations = [System.Math]::Pow($operators.Count,$range.count - 1)

# Cycle each permutation
0..($permutations - 1) | ForEach-Object{
    # Convert the number to a base equal to the element count in operators. Use those values to represent the index of the operators array.
    $mathString = $formatString  -f @([string[]][char[]]((ConvertTo-Base -Number $_ -Base $operators.Count).PadLeft($range.count - 1,"0")) | ForEach-Object{$operators[[int]$_]})
    # Build an object that contains the result and the mathematical expression 
    [pscustomobject]@{
        Expression = $mathString
        Value = Invoke-Expression $mathString      
    }
    # Since this take a while try and give the user some semblance of progress. 
    Write-Progress -Activity "Performing mathematical calculations" -Status "Please wait." -PercentComplete ($_ / $permutations * 100) -CurrentOperation "$([math]::Round($_ / $permutations * 100))% Completed."

    # Filter for whole number and only give group results
} | Where-Object{$_.Value -is [int32]} | Group-Object Value | Where-Object{$_.Count -ge $lowCountThreshold} | Sort-Object Count -Descending

So if you were to run this and change the $maxValue to something smaller like 3 and change the you would

Count Name Group                                                       
----- ---- -----                                                       
    2 6    {@{Expression=1+2+3; Value=6}, @{Expression=1*2*3; Value=6}}
    1 0    {@{Expression=1+2-3; Value=0}}                              
    1 7    {@{Expression=1+2*3; Value=7}}                              
    1 2    {@{Expression=1-2+3; Value=2}}                              
    1 -4   {@{Expression=1-2-3; Value=-4}}                             
    1 -5   {@{Expression=1-2*3; Value=-5}}                             
    1 5    {@{Expression=1*2+3; Value=5}}                              
    1 -1   {@{Expression=1*2-3; Value=-1}}          

So there are two operations that would get 6. 1+2+3 and 1*2*3. Who would have thought! If you are testing this be careful of using larger numbers here. Running something like a 9 would take about 7 minutes give or take since it would have 65536 permutations to figure out and then group.

The function helps me convert each permutation number into its mathematical operator sequence. I take a number and convert it into base4. Then take that and use each number to pull an element out of the operator array. Then use the format operator to populate the string and use invoke expression to get the result.

\$\endgroup\$
1
  • \$\begingroup\$ I wanted to use mathematics tag but the description suggested that my math might be too simple for it so I tried a different and hopefully relevant tag. FYI im not hot on the title either but I dont know a shorter version of what I am doing here. \$\endgroup\$
    – Matt
    Commented Mar 12, 2016 at 4:30

1 Answer 1

4
\$\begingroup\$

About performance (there's a good article to get your started: Slow Code: Top 5 ways to make your Powershell scripts run faster); I apply that advice as follows:

  • Problem #1: Expensive operations repeated, e.g.
    • Invoke-Expression: rather than this time consuming cmdlet, I evaluate math expressions using the Compute method of the DataTable class;
    • Write-Progress: show progress bar. We don't call Write-Progress each time through the loop because that is slow. Edit: due to this Dangph's answer;
  • Problem #0: Not using cmdlet parameter filters, e.g. instead of collecting all the [System.Math]::Pow($operators.Count,$range.count-1) permutations and then narrowing the huge array using the Where-Object cmdlet, I collect only desired values;
  • Problem #4: Searching text: the original script computes a string in the (commonly usable) ConvertTo-Base function and then casts it as [string[]][char[]];

… and some further (maybe minor) enhancements are visible in the following (partially commented) 122635answer.ps1 script:

# [CmdletBinding(PositionalBinding=$false)] # slows script execution cca 50%
param (     # Variables
    [parameter()]                  # [ValidateRange(3,20)] # ???
    [int]$maxRange = 9,
    [parameter()]
    [int]$lowCountThreshold = 5,
    [parameter()]
    [ValidateNotNullOrEmpty()]
    [string]$opString = '+-*/'     # Mathematical Operators as string
)
Begin {
    Set-StrictMode -Version Latest
    # cast $operators variable as an array of characters
    $operators = [char[]]$opString
    $opsCount  = $operators.Count
    # Define the number range for calculations. 13 would make for the largest values 13!. Cap the script as 13
    $maxRangeMinus1 = $maxRange - 1
    # Build an array for extending 
    $maxOpsArray = 1..$maxRange
    for ( $i=0; $i -lt $maxRange; $i++ ) {
        $maxOpsArray[$maxRangeMinus1 -$i] = ,$operators[0] * $i
    }
    # Build the format string that will be used for invoking.
    # Will look like 1{2}2{1}3{0}4. Acting as place holders for mathematic operators
    [string]$formatString = -join (1..($maxRangeMinus1) | 
        ForEach-Object{"$_{$([int]$maxRangeMinus1 - $_)}"}) + $maxRange # reverse order
      # ForEach-Object{"$_{$([int]$_ - 1)}"}) + $maxRange  # $range[-1] # ascending order
      # ascending order would require `[array]::Reverse($newOperatorArr)` below in the process loop
    if ( $maxRange -gt 11 ) {
        # force decimal computing in following `$DataTable.Compute( $mathString, '')`
        $formatString = $formatString.Replace('{','.0{') + '.0'
    }
    # Determine the number of possible permutations of those operators inbetween the number set. 
    [int64]$permutations = [System.Math]::Pow($opsCount, $maxRangeMinus1)
    # Narrow down $alphanumerics array size to necessary count
    $alphanumerics = $([char[]]'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
                      )[0..($opsCount -1)]
    Write-Verbose -Verbose -Message `
      ("maxRange=$maxRange, lowCountThreshold=$lowCountThreshold, operators=""$(-join $operators)""" `
     + "`r`npermutations=$permutations formatString=""$formatString""")
    $DataTable=[System.Data.DataTable]::new()
    $Error.Clear()                             # for debugging purposes
}
Process {
# Cycle each permutation. Use `for` loop instead of `0..($permutations - 1) | ForEach-Object`
$( for ( $i=0; $i -lt $permutations; $i++ ) {
    # Build an array of operators:
    #        ( based on the number converted to base `$opsCount` )
        $Number = $i
        $newOperatorArr = @( $( do {
            $Remainder = $Number % $opsCount
            # Get the associated character
            $operators[$Remainder]
            $Number = ($Number - $Remainder) / $opsCount
        } while ($Number -gt 0) ))
        # Extend array of operators to appropriate length if necessary
        if ( $newOperatorArr.Count -lt $maxRangeMinus1 ) {
            $newOperatorArr += $maxOpsArray[$newOperatorArr.Count]
        }
    ### [array]::Reverse($newOperatorArr) # only if `$formatString` is in ascending order
    $mathString = $formatString -f @( $newOperatorArr )
    # evaluate math expression using the Compute method of the DataTable class
    #                          rather than time consuming Invoke-Expression
    $value122635 = $DataTable.Compute( $mathString, '')
    # Effectively reduce the output size in advance: refuse "non-integers"
    if ( $value122635 -eq [System.Math]::Floor($value122635) ) {
        # Build an object that contains the result and the mathematical expression 
        [pscustomobject]@{
            Expression = $mathString
            Value      = [System.Math]::Floor($value122635) # [int64]$value122635
        }
    }
    # Show progress bar. We don't call Write-Progress each time through the loop 
    # because that is slow. 
    # Due to Dangph's answer https://codereview.stackexchange.com/a/221098/88771
    if ($i % 1000 -eq 0) {
      Write-Progress -Activity "Performing mathematical calculations" `
        -Status "Please wait." -PercentComplete (100 * $i / $permutations) `
        -CurrentOperation "$([math]::Round(100 * $i / $permutations))% Completed."
    }
    # Only give group results
} ) | Group-Object Value |
      Where-Object{$_.Count -ge $lowCountThreshold} |
       Sort-Object -property Count <# -Descending <##>, @{Expression = {[int]$_.Name} }

About correctness: the $_.Value -is [int32] condition seems to be too strong. For instance, 1/2*3*4 gives 6, however (1/2*3*4).GetTypeCode() gives Double; hence, (1/2*3*4) -is [int32] condition (incorrectly) rejects the value from result.

For the sake of comparison, I added appropriate Write-Verbose cmdlet (immediately before the main loop) and used $maxRange = 7; $lowCountThreshold = 1 in the original script. The comparison of the latter with the adapted one I performed using the following wrapper:

param (
    [parameter()]                  
    [ValidateRange(8,13)]
    [int]$maxLoop = 12
)

$y = (Measure-Command {$x = D:\PShell\CR\122635.ps1}).TotalSeconds
$z = ($x | Measure-Object -Property  Count -Sum).Sum
'orig.  {0,4} {1,9} {2,9} {3,16}' -f 7, $x.count, $z, $y

for ( $icnt=7; $icnt -lt $maxLoop; $icnt++ ) { 
    $y = (Measure-Command {
        $x = D:\PShell\CR\122635answer.ps1 -maxRange $icnt -lowCountThreshold 1
                          }).TotalSeconds
    $z = ($x | Measure-Object -Property  Count -Sum).Sum
    'answer {0,4} {1,9} {2,9} {3,16}' -f $icnt, $x.count, $z, $y
    if ($icnt -eq 7) {''}
}

Comparison result shows that the 122635answer.ps1 script runs approximately 26× faster (21.33 / 0.80) than original for given $maxRange=7and $lowCountThreshold=1 (in fact, I see no practical use if maxRange is greater than 9; that's in merely to show exponential time growth…):

pwsh -noprofile -file D:\PShell\CR\122635wrapper.ps1
VERBOSE: maxRange=7, lowCountThreshold=1, operators="+-*/"
permutations=4096 formatString="1{0}2{1}3{2}4{3}5{4}6{5}7"
orig.     7       269       756       21,3338469
VERBOSE: maxRange=7, lowCountThreshold=1, operators="+-*/"
permutations=4096 formatString="1{5}2{4}3{3}4{2}5{1}6{0}7"
answer    7       284       839        0,7970644

VERBOSE: maxRange=8, lowCountThreshold=1, operators="+-*/"
permutations=16384 formatString="1{6}2{5}3{4}4{3}5{2}6{1}7{0}8"
answer    8       663      2605        1,8726185
VERBOSE: maxRange=9, lowCountThreshold=1, operators="+-*/"
permutations=65536 formatString="1{7}2{6}3{5}4{4}5{3}6{2}7{1}8{0}9"
answer    9      1514      7897        7,5665315
VERBOSE: maxRange=10, lowCountThreshold=1, operators="+-*/"
permutations=262144 formatString="1{8}2{7}3{6}4{5}5{4}6{3}7{2}8{1}9{0}10"
answer   10      3286     24349       32,0042106
VERBOSE: maxRange=11, lowCountThreshold=1, operators="+-*/"
permutations=1048576 formatString="1{9}2{8}3{7}4{6}5{5}6{4}7{3}8{2}9{1}10{0}11"
answer   11      7089     73434      158,3116746

Edit: due to this Dangph's answer, above performance improvements become even better…

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.