CodeIQのジェムストリング問題をPowerShellで解いてみた
結城浩さんがCodeIQで出題したジェムストリング問題。
限られた時間の中で解いて期限ギリギリに提出したのですが、使い慣れたJavaでかつマシンパワーに任せるという力技になってしまいました。
解答・解説を読み、高速化・省力化の手法を改めて学びなおしました。
というわけで、2月中ごろから本格的に手を付けてこれから習得しようとしているPowerShellで、改めてジェムストリング問題を解いてみました。
PowerShellで挑戦されている方は解答pdfの中には記載なかったかと思いますので初！かもしれません。
コード
まだPowerShell初心者丸出しですが生暖かい目でご覧下さい。
# Get-GemDays.ps1 ジェムストリング問題の計算
# usage
# > Set-ExecutionPolicy -Scope CurrentUser Unrestricted
# > .\Get-GemDays.ps1
#
# 対象宝石パターンを発見したか
$foundTarget = $false
# メモ化の実施有無($true or $false)
$memoized = $true
#$memoized = $false
# 宝石メモ
$memo = @{}
function Get-GemDays($gems, $target, $depth=0, $prevmatch=$false, $gemKeys=$null) {
$days = 0
$match = $false
if (!$gemKeys) {
$gemKeys = $gems.Keys | %{$_} | sort
}
# アルファベット順に宝石の組合せ計算
$gemKeys | %{
if (!$match) {
$gems.$_--
# メモ化のキー(配列だとうまくいかなかったので文字列)
$gemMemoKey = $gems.Values | %{$_} | sort
$gemMemoKey = $gemMemoKey -join ","
if ($gems.$_ -ge 0) {
$days++
# 対象宝石パターンと一致確認
$match = ($depth -eq 0 -or $prevmatch) -and $target[$depth] -eq $_
# 対象宝石パターンと完全一致した場合、以後の処理を行わない
if ($match -and $depth -eq ($target.Length-1)) {
$foundTarget = $true
}
if (!$foundTarget) {
if (!$match -and $memo.Keys -contains $gemMemoKey -and $memoized) {
# Write-Host "Memo-Hit:" $gemMemoKey $memo[$gemMemoKey]
$days += $memo[$gemMemoKey]
} else {
$tmpdays = Get-GemDays $gems $target ($depth+1) $match $gemKeys
$days += $tmpdays
if (!$match -and $memoized) {
$memo[$gemMemoKey] = $tmpdays
# Write-Host "Memo-in:" $gemMemoKey $tmpdays
}
}
}
}
$gems.$_++
}
}
# Write-Host "gems:" $gems.Values
# Write-Host "days:" $days
return $days
}
# "aaabcc" -> @{a=3;b=1;c=2}
function Hash-Gems($gemstr) {
$hashgems =@{};
$gemstr -split "" | %{if($_ -ne ""){$hashgems[$_]++}}
return $hashgems
}
Measure-Command {
# $days = Get-GemDays (Hash-Gems "aaabcc") ""
$days = Get-GemDays (Hash-Gems "abbbbcddddeefggg") "eagcdfbe"
}
Write-Host "days:" $days
実行結果
メモ化有りの場合
約2秒。
> .\Get-GemDays.ps1 Days : 0 Hours : 0 Minutes : 0 Seconds : 2 Milliseconds : 148 Ticks : 21489916 TotalDays : 2.4872587962963E-05 TotalHours : 0.000596942111111111 TotalMinutes : 0.0358165266666667 TotalSeconds : 2.1489916 TotalMilliseconds : 2148.9916 days: 5578864439
メモ化無しの場合
# メモ化の実施有無($true or $false) #$memoized = $true $memoized = $false
に変えて実行。
・・・1時間経ちましたが終わる気配がありません。
気になること
break/continueの動作
for-each内で再帰呼出を行っているが、for-each内にbreakやcontinueを入れたら再帰呼出自体が終了してしまった。
ひとまずはif文のネストで回避したものの、動きが怪しいので余裕があれば調べてみます。
Where-Objectの扱い
「連想配列で、値が1以上のキー取り出し」がWhere-Objectを使ってできないか、気になったので後から調べてみました。
> $a = @{a=3;b=1;c=2;d=0;e=0;f=1}
> $a.Keys | Where-Object {$a.$_ -gt 0}
a
f
b
cどうもキー定義順にはならないようで、アルファベット順にするためにsortしています。
