平衡三進表記

Squeak Smalltalk

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 を収めた配列を返すメソッド

Squeak Smalltalk

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

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)