How much gold (Electronic Station) - 金の含有率を求めよ

どんな問題？

How much gold
http://www.checkio.org/mission/how-much-gold/

ある金属のバーには、gold(金)、iron(鉄)、copper(銅)、tin(スズ)が含まれている。
各金属の含有率は不明だが、合金の含有率はわかっている。
例えば、金＋鉄は全体の1/3、金＋スズは1/2、金＋銅は1/4 など。
与えられた合金の含有率から、金の含有率を求めよ。答えは分数で。

合金の含有率は、dict形式で渡される。Keyが文字列、ValueがFractionクラス。

{
'gold-tin': Fraction(1, 2),
'gold-iron': Fraction(1, 3),
'gold-copper': Fraction(1, 4),
}

答えは、Fractionクラスで返す。

例題：

checkio({
    'gold-tin': Fraction(1, 2),
    'gold-iron': Fraction(1, 3),
    'gold-copper': Fraction(1, 4),
    }) == Fraction(1, 24)
checkio({
    'tin-iron': Fraction(1, 2),
    'iron-copper': Fraction(1, 2),
    'copper-tin': Fraction(1, 2),
    }) == Fraction(1, 4)

どうやって解く？

Fractionなんて使ったことないので不安だが、まずは、その前に数学の問題を解かないと。
金・鉄・銅・錫をそれぞれA,B,C,Dとすると、問題文の例なら、

A+B=1/3
A+C=1/4
A+D=1/2

となる。このとき、Aを求めよという問題。あれ？これ解けないよね？あ、そうか。

A+B+C+D=1

という条件を忘れていた。
となれば、

(A+B)+(A+C)+(A+D)-(A+B+C+D) = Ax2
(A+B)+(A+C)+(A+D)-1 = Ax2
A = ((A+B)+(A+C)+(A+D)-1)÷2

として、Aを求められる。

Gold = (Gold-Iron + Gold-Copper + Gold-Tin - 1) / 2

というわけだ。

ただ、例題を見ればわかるように、引数はAB,AC,ADの組み合わせとは限らない。そもそも合金3つで必ず答えは出るのだろうか？

2つの金属の組み合わせは A+B, A+C, A+D, B+C, B+D, C+D の6通り。そうか、A+B+C+D=1 なんだから、A+B がわかれば C+D もわかる。だとすれば、引数がどんな組み合わせであっても、A+B, A+C, A+D は求められるというわけか。これなら解けそうだ。

Fractionクラス

fractionsモジュールの説明を読んでみる。
http://docs.python.jp/3.3/library/fractions.html?highlight=fractions#fractions

ようするに分数を扱うクラス。intやfloatと同じように四則演算できる。

>>> Fraction(1, 2)  # 2分の1なら (1,2)と書く
Fraction(1, 2)

>>> Fraction(10, 20)  # 約分してくれる
Fraction(1, 2)

>>> Fraction(1, 2) + Fraction(1, 3)  # 足し算
Fraction(5, 6)

>>> 1 - Fraction(1, 3)  # 引き算
Fraction(2, 3)

>>> Fraction('1/2')  # 文字列からの変換も
Fraction(1, 2)

だいたいわかった。

gold-tinを求める

では、引数のdictから、必要な合金データを取り出す部分を書いてみる。

alloys = {
'gold-tin': Fraction(1, 2),
'gold-iron': Fraction(1, 3),
'gold-copper': Fraction(1, 4),
}

'gold-tin'が欲しければ、

alloys['gold-tin']
alloys['tin-gold']

を探す。どちらもなければ

alloys['iron-copper']
alloys['copper-iron']

を探して1から引けばよい。

必要な合金データを求めるコードはこちら。

def get_alloy_proportion(m1, m2, m3, m4):
    # get (m1+m2) or (m2+m1) or (1-(m3+m4)) or (1-(m4+m3))
    if m1 + '-' + m2 in alloys:
        return alloys[m1 + '-' + m2]
    elif m2 + '-' + m1 in alloys:
        return alloys[m2 + '-' + m1]
    elif m3 + '-' + m4 in alloys:
        return 1 - alloys[m3 + '-' + m4]
    elif m4 + '-' + m3 in alloys:
        return 1 - alloys[m4 + '-' + m3]
    else:
        raise Exception("unsolvable!")

'gold-tin'が必要なら、 get_alloy_proportion('gold', 'tin', 'iron', 'copper') とする。
エディタには、あらかじめ金属名が定数METALSで定義されていたが、使わなかった。

'gold-tin'と同じように、'gold-iron'と'gold-copper'を求めればよい。

まとめ

from fractions import Fraction
 
def checkio(alloys):
    def get_alloy_proportion(m1, m2, m3, m4):
        # get (m1+m2) or (m2+m1) or (1-(m3+m4)) or (1-(m4+m3))
        if m1 + '-' + m2 in alloys:
            return alloys[m1 + '-' + m2]
        elif m2 + '-' + m1 in alloys:
            return alloys[m2 + '-' + m1]
        elif m3 + '-' + m4 in alloys:
            return 1 - alloys[m3 + '-' + m4]
        elif m4 + '-' + m3 in alloys:
            return 1 - alloys[m4 + '-' + m3]
        else:
            raise Exception("unsolvable!")
 
    gold_iron = get_alloy_proportion('gold', 'iron', 'tin', 'copper')
    gold_copper = get_alloy_proportion('gold', 'copper', 'tin', 'iron')
    gold_tin = get_alloy_proportion('gold', 'tin', 'iron', 'copper')
 
    # gold + iron + copper + tin = 1
    return (gold_iron + gold_copper + gold_tin - 1) / 2

もうちょっと簡単に書けそうだけど、まあいいか。公開！

他の人の答え

def checkio(alloys):
    return 1 - sum([1 - v if 'gold' in k else v for (k, v) in alloys.iteritems()]) / 2

http://www.checkio.org/mission/how-much-gold/publications/bunnychai/python-27/first/

えっ、短い。
Keyに'gold'が含まれていれば 1-Value、含まれていなければValueとして、足し合わせる。
gold = 1 - sum(～) / 2
なるほど。

ちなみに、Python3.3なら、iteritems()はitems()でよい。

summer_tree_home

Check iOでPython3をマスターするぜっ