ハリー・ポッター本の割引き額を求める問題を Squeak Smalltalk で
そろそろ http://railsconf.blip.tv/file/2089545/ について何か言っておこうか…と思い、その下調べにと Robert C. Martin のブログをぼんやりと眺めていたところ Ruby がらみの ArticleS.UncleBob.MakingMessesInRuby というエントリーを見つけたまではよかったのですが、そこに例として登場した問題が面白そうだったので、ついつい本題（Smalltalk を勝手に殺すなとか、自由すぎることの問題とか）そっちのけで、遊んでしまいました。駄目じゃん。
５巻からなるシリーズ本（どれも定価８ユーロ）があり、異なる巻を１冊ずつ組み合わせることでまとめて購入すると、冊数に応じた割引き（２種類なら 5%、３種類なら 10%、４種類なら 20%、全種類なら 25%。巻さえ異なれば連番である必要はない）が受けられる。同じ巻を２冊以上ずつ購入したい場合でも、重複しないようにグループ分けすれば、それぞれのグループに対して前述の割引きルールを適用できる。客は、もっとも合計額が少なくなるような割引きの組み合わせのときの額を支払えばよいとして、その金額を求めるコードを書け。
さいしょはこんなふうに、無駄を承知で全パターンを検証するコードを幅優先探索で書いた（別に深さ優先でもよかったのですが、Squeak ではブロックの再帰が面倒なので…^^;）のですが…
| cart allocations queue discounts priceOf listPrice minPrice | cart := #(0 0 1 1 2 3 3 4). allocations := Set new. queue := OrderedCollection with: {cart asOrderedCollection. Bag new}. [queue notEmpty] whileTrue: [ | rest allocation | queue size printString, ' ' displayAt: 0 @ 0. rest := queue first first. allocation := queue removeFirst second. rest ifEmpty: [allocations add: allocation] ifNotEmpty: [ | set | set := rest asSet. (set size to: 1 by: -1) do: [:size | set asArray combinations: size atATimeDo: [:comb | | next | next := allocation copyWith: comb asSet. (queue noneSatisfy: [:pair | pair second = next]) ifTrue: [ queue add: {rest copy removeAll: comb; yourself. next}]]]]]. discounts := #(1.0 0.95 0.9 0.8 0.75). listPrice := 8. priceOf := [:allocation | allocation inject: 0 into: [:sum :each | sum + (listPrice * each size * (discounts at: each size))]]. minPrice := priceOf value: (allocations detectMin: [:alloc | priceOf value: alloc]). {minPrice. allocations select: [:each | (priceOf value: each) = minPrice]} "=> an Array(51.2 a Set(a Bag(a Set(0 1 3 4) a Set(0 1 2 3)))) "
さすがにこれは無謀で、７〜８冊程度ならともかく、20冊強とか買った日にゃ終わるはずもなく、けっきょく諦めて、ググって見つけた 53 Events Blog: Harry Potter Kata にある Java版を パク… 大いに参考にさせていただくことにしました。そうしてできあがったのがこちら。
| largesetBundlesOf smallestBundlesOf listPrice discountRule costOf orders | largesetBundlesOf := [:vols | | result rest | result := OrderedCollection new. rest := vols asOrderedCollection. [rest notEmpty] whileTrue: [result add: (rest removeAll: rest asSet)]. result]. smallestBundlesOf := [:vols | | width result | width := (vols sort collect: [:vol | vols occurrencesOf: vol]) max. result := (1 to: width) collect: [:each | OrderedCollection new]. (1 to: vols size) do: [:idx | (result atWrap: idx) add: (vols atWrap: idx)]. result]. listPrice := 8. discountRule := #(1.0 0.95 0.9 0.8 0.75). costOf := [:bundles | bundles inject: 0 into: [:total :bundle | total + (listPrice * bundle size * (discountRule at: bundle size))]]. orders := #( 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 4). (costOf value: (smallestBundlesOf value: orders)) min: (costOf value: (largesetBundlesOf value: orders)) "=> 141.2 (141.6 でないことに注意) "
一瞬で、返してきます。そりゃそーですわな。おそらく割引ルールがよほど特殊でなければ、これでいいのでしょうね。きっと。
参考までに、基になった Java版を Squeak Smalltalk で動きを見るために機械的に翻訳したときのコードも。
| costPerVolume uniqueVolumesPercentageCharge createNewBundle findAvailableBundle createLargestVolumeBundles containsSmallerAvailableBundle findSmallestAvailableBundle createSmallestVolumeBundles addToTotal calculateCostOfOrders totalPrice orders | costPerVolume := 8. uniqueVolumesPercentageCharge := #(1.0 0.95 0.9 0.8 0.75). createNewBundle := [:bundles1 | | bundle1 | bundle1 := Set new. bundles1 add: bundle1. bundle1 ]. findAvailableBundle := [:bundles2 :order2 | | return | [:exit2 | bundles2 do: [:bundle2 | (bundle2 includes: order2) not ifTrue: [return := bundle2. exit2 value] ] ] valueWithExit ifNil: [return] ifNotNil: [createNewBundle value: bundles2] ]. createLargestVolumeBundles := [:orders3 | | bundles3 | bundles3 := OrderedCollection new. orders3 do: [:order3 | | bundle3 | bundle3 := findAvailableBundle value: bundles3 value: order3. bundle3 add: order3 ]. bundles3 ]. containsSmallerAvailableBundle := [:bundles4 :bundleBeingConsidered :orders4 | [:exit4 | bundles4 do: [:bundle4 | ((bundle4 includes: orders4) not and: [bundle4 size < bundleBeingConsidered size]) ifTrue: [exit4 value] ] ] valueWithExit isNil ]. findSmallestAvailableBundle := [:bundles5 :order5 | | return | [:exit5 | bundles5 do: [:bundle5 | ((bundle5 includes: order5) not and: [ (containsSmallerAvailableBundle value: bundles5 value: bundle5 value: order5) not]) ifTrue: [return := bundle5. exit5 value] ] ] valueWithExit ifNil: [return] ifNotNil: [createNewBundle value: bundles5] ]. createSmallestVolumeBundles := [:orders6 | | bundles6 | bundles6 := OrderedCollection new. orders6 do: [:order6 | | bundle6 | bundle6 := findSmallestAvailableBundle value: bundles6 value: order6. bundle6 add: order6 ]. bundles6 ]. addToTotal := [:currentTotal :bundleSize | currentTotal + (costPerVolume * bundleSize * (uniqueVolumesPercentageCharge at: bundleSize)) ]. calculateCostOfOrders := [:orderBundles | | total | total := 0.0. orderBundles do: [:orderBundle | total := addToTotal value: total value: orderBundle size. ]. total ]. totalPrice := [:order8 | | smallBundlesTotal largeBundlesTotal | smallBundlesTotal := calculateCostOfOrders value: (createSmallestVolumeBundles value: order8). largeBundlesTotal := calculateCostOfOrders value: (createLargestVolumeBundles value: order8). smallBundlesTotal min: largeBundlesTotal ]. orders := #( 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 4). totalPrice value: orders "=> 141.2 "
