平衡三進表記

Tiki の「天秤を 3 回だけ使って 12 枚のコインの中から重さの異なる 1 枚を見つける方法」数学クイズからたどって、STUDIO KAMADA さんの「天秤を n 回だけ使って 3n-3 / 2 枚のコインの中から重さの異なる 1 枚を見つける方法」という一般解経由で、クヌス先生お気に入りの平衡三進表記(balanced ternary notation)というのを知って、それとからめて SequenceableCollection >> #asDigitsToPower:do: と #polynomialEval: というのを見つけました。

そこで、-(3n - 1) / 2 から (3n - 1) / 2 までの trit 配列をジェネレートするスクリプト

n
n _ 2. World findATranscript: nil. (-1 to: 1) asDigitsToPower: n do: [: each | Transcript cr; show: (each reverse polynomialEval: 3); space; show: '->'; space; show: each]
=> -4 -> #(-1 -1)
   -3 -> #(-1  0)
   -2 -> #(-1  1)
   -1 -> #( 0 -1)
    0 -> #( 0  0)
    1 -> #( 0  1)
    2 -> #( 1 -1)
    3 -> #( 1  0)
    4 -> #( 1  1)

任意の整数について、平衡三進記法の各桁の trit を収めた配列を返すメソッド

なんてものも書いてみました。

Integer >> balancedTritsArray
   | ternary zeroValue numDigits |
   self isZero ifTrue: [^ Array with: 0].
   self < 0 ifTrue: [^ self negated balancedTritsArray negated].
   numDigits _ (self * 2 log: 3) floor + 1.
   zeroValue _ (3 raisedTo: numDigits) - 1 / 2.
   ternary _ ((self + zeroValue) radix: 3) allButFirst: 2.
   ^ (ternary as: Array) collect: [: digitChar | digitChar digitValue - 1]
14 balancedTritsArray   "=> #(1 -1 -1 -1) "


これを使うと、くだんのクイズを解く際に役立つ、各コインに割り振る番号の正負、対応する平衡三進数(の各桁を収めた配列)を導くヘルパースクリプト的なものも比較的簡単に書くことができそうです。

nn coins zeroArray sum
nn _ 3. coins _ (1 to: (3 raisedTo: nn) - 3 / 2) collect: [: mm | | tritsArray ii | zeroArray _ Array new: nn withAll: 0. tritsArray _ (zeroArray, mm balancedTritsArray) last: nn. ii _ tritsArray indexOfSubCollection: #(1 0) startingAt: 1. (ii > 0 and: [(tritsArray first: ii) allSatisfy: [: each | each = 1]]) ifTrue: [{#negated. tritsArray negated}] ifFalse: [{#yourself. tritsArray}]]. World findATranscript: nil. sum _ zeroArray copy. coins keysAndValuesDo: [: key : value | sum _ sum + value last. Transcript cr; show: (key perform: value first); space; show: '->'; space; show: value last]. Transcript cr; show: 'sum -> '; show: sum
=>   1 -> #( 0  0  1)
     2 -> #( 0  1 -1)
     3 -> #( 0  1  0)
     4 -> #( 0  1  1)
     5 -> #( 1 -1 -1)
     6 -> #( 1 -1  0)
     7 -> #( 1 -1  1)
    -8 -> #(-1  0  1)
    -9 -> #(-1  0  0)
   -10 -> #(-1  0 -1)
    11 -> #( 1  1 -1)
   -12 -> #(-1 -1  0)
   sum -> #( 0  0  0)