1日1個 @nabetani さんの作った問題を解く、どう書くAdventCalendarの5日目です。
今日の問題は http://nabetani.sakura.ne.jp/hena/ord13updowndouble/ にあります。
module Doukaku.UpDownButton (solve) where
import Data.Set (Set, empty, singleton, member, union, elems, fromList, difference)
solve :: String -> String
solve = show . minope empty . singleton . read
minope :: Set Int -> Set Int -> Int
minope done new'
| 1 `member` new' = 1
| (-1) `member` new' = 1
| otherwise = 1 + minope (done `union` new') (new `difference` done)
where
new = fromList $ do
x <- elems new'
(if x `mod` 2 == 0 then [x `div` 2] else []) ++ [x + 1, x - 1]
単純な幅優先探索です。ただし、増加列を考えると値をオーバーしただけだと枝刈りできず判定が面倒かなと直感的に感じたので、ゴールから初めて2で割っていく戦略をとってます。すでに登場した数と奇数を捨てる感じです。
実はこの問題、初めは算術的に解けるかなと https://github.com/hiratara/doukaku-past-questions-advent-2013/blob/96787f588a9c730a74926a14f3edd7bcf25d10fa/src/Doukaku/UpDownButton.hs という回答を書いていたのですが、テストを通すことができず失敗しました。与えられた数値を2進数に直すと、1は「+1、×2」で2個分、0は「×2」で1個分のカウントをすればOKという考え方で、連続する1111のようなシーケンスは1000(-1)のように少ないシーケンスに置き換えられ、これで簡略化すれば解が得られると予想しました。しかし、59 = 111011のようなシーケンスは100(-1)10(-1)という簡略化だけでは最適解が出ず、これをさらに1000(-1)0(-1)のようにする必要があることがわかりました。他にも簡略化があるとすればキリがないので、この方法は今回は諦めました。
http://qiita.com/Nabetani/items/89fb0e2e712d4b396535 に他の方の回答もありますので、見ると参考になるでしょう。