"Another Powershell Math Challenge" と "Solving Another PowerShell Math Challenge" に寄せて
PowerShell で算数の問題の解き方を考えている方々を見つけました。面白そうだったので私も挑戦してみます。
問題
私が見た記事はこちらです。Problem #2 に挑戦します。
元ネタはこちらだそうです。上記の Problem #2 は、元ネタだと Advanced Level となっています。
以下のような数値の配列を受け取り、
$a = 2,5,6
数値の全ての組み合わせの和を求めるという問題です。
2 5 6 2+5 = 7 2+5+6 = 13 2+6 = 8 5+6 = 11
Another PowerShell Math Challenge – Iron Scripter より
私の考え方
数の全ての組み合わせの和を求めるという問題なので、それそれの数について、使うか使わないかの二択を考えたらいいですね。
使う→o、使わない→x とすると以下の通りになります。
| Pattern | 2 | 5 | 6 |
|---|---|---|---|
| 0 | x | x | x |
| 1 | o | x | x |
| 2 | x | o | x |
| 3 | x | x | o |
| 4 | o | o | x |
| 5 | o | o | o |
| 6 | o | x | o |
| 7 | x | o | o |
この感じ、なんだか見覚えが……そうですね、2進数ですね！
使う→1、使わない→0 です。
| Pattern | 2 | 5 | 6 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
| 7 | 1 | 1 | 1 |
たとえば以下のパターンだと、2 と 6 を使い、5 は使いません。和は 8 です。
| Pattern | 2 | 5 | 6 |
|---|---|---|---|
| 5 | 1 | 0 | 1 |
ということで、2進数を使って全ての組み合わせを作り、和を求めます。
作業環境
- Windows 10 20H2 (Build 19042.1237)
- Windows PowerShell 5.1.19041.1237
- PowerShell 7.1.4
コード
function
元ネタのページに提出しようと思いましたが締め切られていました。
one-liner
ワンライナーでもどうぞ。
$nums = 2, 5, 6 1..([Math]::Pow(2, $numbers.Length) - 1) | % {([long][Convert]::ToString($_, 2)).ToString($('0' * $numbers.Length))} | % {$binaryString = $_; $sum = 0; 0..($_.Length - 1) | % {if ($binaryString[$_] -eq '1') {$sum += $numbers[$_]}}; $sum} | sort | unique
説明
function 版で説明します。
int の配列を受け取ります。
param ( [int[]] $Numbers )
組み合わせの数を数えます。数が 3 つなら 23- 1 = 7 通りです。どの数も使わないパターン（つまり 0）は不要なので除きます。
(2022/05/18 変数名を訂正)
$patternCount = [Math]::Pow(2, $Numbers.Length) - 1
2進数を3桁で表すための「カスタム数値形式文字列」を作り、
[string]$binaryFormatString = '0' * $Numbers.Length
1から7の整数 ($i) を3桁の2進数で表し、
(2021/09/26 変数名を訂正)
for ($i = 1; $i -le $patternCount; $i++) { [string]$patternBinary = ([long][Convert]::ToString($i, 2)).ToString($binaryFormatString)
2進数の左から $j 桁目が 1 だったら、配列の $j 番目の要素を $sum に加算します。2進数が 101 の場合、配列の 0 番目の要素と 2 番目の要素を $sum に加算します。
(2022/05/18 一部表記を変更)
for ($j = 0; $j -lt $patternBinary.Length; $j++) { if ($patternBinary[$j] -eq '1') { $sum += $Numbers[$j] } }
その組み合わせの和を $result 配列に追加します。
$result += $sum
全組み合わせでこれを行ったら、各組合せの和を昇順にして、重複を除いて出力します。
return $result | Sort-Object | Get-Unique
発展問題
Twitter でこんな問題を見つけました。
#VBA100本ノック 魔球編
— エクセルの神髄 (@yamaoka_ss) 2020年12月2日
5つの数値を引数で受け取ります。
数値は正の整数(重さg)です。
20~40(g)まで幅があります。
この中から100gを超える100gに最も近い組み合わせを見つけて、その組み合わせを配列で返してください。
お菓子の定量詰めと考えてください。
組み合わせる個数に制限はありません。
今回の function を応用してこちらも解いてみます。
function Get-AllPossibleSum2 { param ( # Specifies numbers to get all the possible sums [Parameter(Mandatory=$true, HelpMessage="Numbers to get all the possible sums." )] [int[]] $Numbers ) Write-Verbose "`$Numbers.Length: $($Numbers.Length)" [int]$patternCount = [Math]::Pow(2, $numbers.Length) - 1 Write-Verbose "`$patternCount: $patternCount" [string]$binaryFormatString = '0' * $Numbers.Length Write-Verbose "`$binaryFormatString: $binaryFormatString" for ($i = 1; $i -le $patternCount; $i++) { Write-Verbose "`$i: $i" [string]$patternBinary = ([long][Convert]::ToString($i, 2)).ToString($binaryFormatString) Write-Verbose "`$patternBinary: $patternBinary" $currentPattern = [PSCustomObject]@{ Pattern = $patternBinary Numbers = @() Sum = 0 } for ($j = 0; $j -lt $patternBinary.Length; $j++) { Write-Verbose "`$patternBinary[$j]: $($patternBinary[$j])" if ($currentPattern.Pattern[$j] -eq '1') { $currentPattern.Numbers += $numbers[$j] $currentPattern.Sum += $numbers[$j] } } Write-Output $currentPattern } }
$nums = 24,35,26,31,29 Get-AllPossibleSum2 -Numbers $nums | ? {$_.Sum -gt 100} | sort Sum | select -First 1
配列は Number プロパティに入っています。
Pattern Numbers Sum
------- ------- ---
10111 {24, 26, 31, 29} 110
まとめ
情報Ⅰの授業で2進数を扱うときに、どうすれば生徒の興味を引いたり、2進数の有用性を伝えたりできるか考えていた時にこの問題に出会いました。
実生活でも「2択の組み合わせを全て考える」ということはままあるのではないでしょうか。そんなときに2進数が使えるよ、というのは有用性の話としていいのかもしれません。「お土産が5種類あって、買うか買わないかの2択の組み合わせを全て考えて予算内で収まるものを考える」とかでしょうか。テンション上がってきましたよ。
