小町算

LL魂 Python

shinhさんのコードを参考に小町算をPythonで実装した。

# shinhさんのコード(Ruby)
*a='1'
('2'..'9').map{|x|b=[]
  a.map{|v|5.times{|i|b<<v+"+-*/"[i,1]+x}}
  a=b}
puts a.select{|f|100==eval(f)}

# 私のコード(Python)
a = ['1']
for n in map(str, range(2, 10)):
    b = []
    for s in a:
        for o in ['+', '-', '*', '/', '']:
            b += [s+o+n]
    a = b
cnt=0
for e in a:
    if eval(e) == 100:
        cnt += 1
        print cnt, e

分かってみると結構シンプルである。単に組み合わせをいかに作るかという問題。


追記：
しかし、Pythonのmapやリスト内包表記に式を1つしか書けないのは軽いストレスを感じる。Rubyみたいに短く書けない…。特にmapはcompose関数みたいなものもないのでタイプ量を減らす以外にリスト内包表記より使えないし。Pythonファンの自分としては辛いところ。


追記2：

shinhさんの小町算問題の別解と、どう書く?orgのアルファベットの繰り上がり問題の#1049の解答が同じ考え方だと気づいた。カウンタが文字列の個数分くるくる回って適切な文字列を見つけ、それをループや再帰で繰り返してくっつけているという考え方。くるくる回ると言えば、itertools.cycle()が使えるかも。検討してみるかな。

# 小町算問題(Ruby)
(5**8).times{|v|
  f='1'
  '2'.upto('9'){|x|
    f+='+-*/'[v%5,1]+x
    v/=5
  }
  puts f if 100==eval(f)
}

# アルファベットの繰り返し問題(Python)
nums = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def convert(n):
  digit = nums[n % len(nums)]
  n = n/len(nums)
  if n:
    return convert(n - 1) + digit
  return digit

for i in range(0, 1000):
  print convert(i)


今日の日記の一番最初に載せたコードは、リストにとにかく溜めていくという考え方で、DFS(深さ優先検索)も似たような考え方だと思う。DFSでのリストの使い方は、条件に合うものをリストに溜めていって、リストの要素を全て調べつくしたら終わりというもの。リストに溜めるという考え方は結構使えるなあ…。