1g 刻みで重さを量る天秤の問題

README.md

手習（天秤と平衡三進法）

天秤で 1g, 3g, 9g, 27g の分銅を用いて 1～40g の重さを量る方法について.

※2013年12月頃に Python 手習のため書いた短いコードをまとめたもの.

問題の概略

天秤と 1g, 3g, 9g, 27g の4つの分銅があれば 1〜40g の重さを量ることができる.

左		右
1	=	1
2 + 1	=	3
3	=	3
4	=	1 + 3
5 + 1 + 3	=	9
6 + 3	=	9
7 + 3	=	1 + 9
8 + 1	=	9
9	=	9
10	=	1 + 9
...

一般に 3⁰g, 3¹g, ..., 3^n-1g の n 個の分銅があれば 1 〜 (3ⁿ - 1)/2g の重さを量ることができる.

原理

これは平衡三進法 (balanced ternary) で説明できる.

Balanced ternary - Wikipedia [en]

通常の三進法では 0, 1, 2 の3つの数字で表現するところを, 平衡三進法では -1, 0, 1 の3つで表現する.

位取りは通常の三進法と同じで, 右から1の位, 3の位, 9の位, 27の位, …となる.

平衡三進法による 1〜10 を次表に示す. ただし 1 を "+", -1 を "-" と表記する.

数	平衡三進法による表現
1	+
2	+-
3	+0
4	++
5	+--
6	+-0
7	+-+
8	+0-
9	+00
10	+0+
...	...

1の位が 1g の分銅、3の位が 3g の分銅、... に対応し, "+" は右の皿に、 "-" は左の皿に分銅を乗せることに対応する.

左		右	平衡三進法による表現
1	=	1	+
2 + 1	=	3	+-
3	=	3	+0
4	=	3 + 1	++
5 + 3 + 1	=	9	+--
6 + 3	=	9	+-0
7 + 3	=	1 + 9	+-+
8 + 1	=	9	+0-
9	=	9	+00
10	=	9 + 1	+0+
...

実装

任意の入力値を平衡三進法で表現する関数 btern() を何通りかの方法で実装した.

• btern1.py : 最初の実装. いったん通常の三進数を経由する.
  例： 8 の場合. 8 + (1 + 3 + 9) = 20 の三進数表現は 210. この各桁から 1 を引いて（つまり合計 9 + 3 + 1 を引いて）+0-.
  まどろっこしい.
• btern2.py : 平衡三進法の素朴な実装. リスト型で作成してから文字列に変換.
• btern3.py : divmod を使うとかなり短縮できることに気づく.
• btern4.py : さらにジェネレータを駆使し短く書く.
• btern5.py : 再帰を利用して1行で書けた.

btern() を利用して天秤問題の解となる等式を出力する関数 solve() を実装.

• solve1.py : 素朴に if 分岐で左辺と右辺に分銅を乗せていく.
• solve2.py : 少しひねった書き方. 辞書 (dict) を使用.

最後に, できるだけ短く書く挑戦.

• solve3_golf.py (130 bytes) : 1〜40g の解を表示する. btern4() のジェネレータを応用した.

結果

$ python solve3_golf.py
1 = 1
2 + 1 = 3
3 = 3
4 = 1 + 3
5 + 1 + 3 = 9
6 + 3 = 9
7 + 3 = 1 + 9
8 + 1 = 9
9 = 9
10 = 1 + 9
11 + 1 = 3 + 9
12 = 3 + 9
13 = 1 + 3 + 9
14 + 1 + 3 + 9 = 27
15 + 3 + 9 = 27
16 + 3 + 9 = 1 + 27
17 + 1 + 9 = 27
18 + 9 = 27
19 + 9 = 1 + 27
20 + 1 + 9 = 3 + 27
21 + 9 = 3 + 27
22 + 9 = 1 + 3 + 27
23 + 1 + 3 = 27
24 + 3 = 27
25 + 3 = 1 + 27
26 + 1 = 27
27 = 27
28 = 1 + 27
29 + 1 = 3 + 27
30 = 3 + 27
31 = 1 + 3 + 27
32 + 1 + 3 = 9 + 27
33 + 3 = 9 + 27
34 + 3 = 1 + 9 + 27
35 + 1 = 9 + 27
36 = 9 + 27
37 = 1 + 9 + 27
38 + 1 = 3 + 9 + 27
39 = 3 + 9 + 27
40 = 1 + 3 + 9 + 27
$

btern1.py

def btern(n):
  symbols = ['-', '0', '+']
  l = base3(n + offset(n))[::-1]
  r = ''
  for i in l:
    r += symbols[i]
  return r

def base3(n):
  '''
  convert integer into list (reversed ternary)
  >>> base3(6)
  [0, 2]       #  6 = 0 + 6
  >>> base3(15)
  [0, 2, 1]    # 15 = 0 + 6 + 9
  '''
  i = n
  l = []
  while i:
    l.append(i % 3)
    i //= 3
  return l

def offset(n):
  '''
  returns the minimum r = 1+3+9+...+3^i that satisfies r > n
  >>> offset(3)
  4    # 1 + 3
  >>> offset(20)
  40   # 1 + 3 + 9 + 27
  '''
  i = r = 1
  while r < n:
    r = (3 ** i - 1) // 2
    i += 1
  return r

btern2.py

def btern(n):
  symbols = ['0', '+', '-']
  l = btern_list(n)[::-1]
  r = ''
  for i in l:
    r += symbols[i]
  return r

def btern_list(n):
  '''
  convert integer into list (reversed balanced ternary)
  >>> balance(3)
  [0, 1]           #  3 = 0 + 3
  >>> balance(15)
  [0, -1, -1, 1]   # 15 = 0 - 3 - 9 + 27
  '''
  l = []
  while n:
    r = (n + 1) % 3 - 1
    l.append(r)
    n //= 3
    if r == -1:
      n += 1
  return l

btern3.py

def btern(n):
  symbols = ['0', '+', '-']
  s = ''
  while n:
    n, r = divmod(n, 3)
    s += symbols[r]
    if r == 2:
      n += 1
  return s[::-1]

btern4.py

def btern(n):
  return ''.join(['-0+'[i] for i in btern_gen(n)][::-1])

def btern_gen(n):
  while n:
    n, r = divmod(n + 1, 3)
    yield r

btern5.py

def btern(n):
  return btern((n+1)//3)+'-0+'[(n+1)%3] if n else ''

solve1.py

import btern5 as b

def solve(n):
  l = str(n)
  r = ''
  for i, v in enumerate(b.btern(n)[::-1]):
    if v == '-':
      l += ' + ' + str(3 ** i)
    elif v == '+':
      r += ' + ' + str(3 ** i)
    else:
      pass
  return l + ' = ' + r[3:]

import sys
n = int(sys.argv[1]) if len(sys.argv) > 1 else 10000
print(solve(n))

solve2.py

import btern5 as b

def solve(n):
  t = {'-':[str(n)], '+':[], '0':[]}
  for i, s in enumerate(b.btern(n)[::-1]):
    t[s].append(str(3**i))
  return ' + '.join(t['-']) + ' = ' + ' + '.join(t['+'])

import sys
n = int(sys.argv[1]) if len(sys.argv) > 1 else 10000
print(solve(n))

solve3_golf.py

for n in range(1,41):
 s,i=[str(n),'',''],1
 while n:
  n,r=divmod(n+1,3)
  s[r]+=' + '+str(i)
  i*=3
 print(s[0]+' = '+s[2][3:])