Pythonで2つの通貨間の変換レートを求めるプログラムの実装方法

問題の概要

3つの配列 curr_a・curr_b・conv_rate が与えられているとします。curr_a と curr_b には通貨名が格納されており、conv_rate[i] は「curr_a[i] から curr_b[i] への変換レート」を表します。

ここで、変換元の通貨 src と変換先の通貨 dest が与えられるので、src から dest への変換レートを求めます。変換が可能ならその値を出力し、不可能な場合は 0 を返します。

たとえば、次のような入力を考えてみましょう。

• src = 「INR」（インドルピー）
• dest = 「JPY」（日本円）
• curr_a = ['INR', 'GBP', 'EUR']
• curr_b = ['GBP', 'EUR', 'JPY']
• conv_rate = [0.009, 1.17, 129.67]

この場合、「INR → GBP → EUR → JPY」という経路でレートを掛け合わせることになるため、出力は 1.3654250999999997 となります（0.009 × 1.17 × 129.67 ≒ 1.3654）。

解法のアプローチ：グラフ問題として捉える

この問題は、各通貨をノード、通貨ペアをエッジとみなしたグラフの経路探索問題として捉えることができます。そして、ベルマンフォード法と同じ要領で「緩和（relaxation）」操作を繰り返し適用することで、src から dest までの最大の変換レートを求められます。

具体的な手順は以下の通りです。

1. デフォルト値が 0 のマップ temp を用意する
2. temp[src] に 1 を設定する（スタート地点のレートは 1）
3. カウンタ i を 0、フラグ p を True で初期化する
4. p が True かつ i が temp のサイズ以下である間、次の処理を繰り返す
   • p を False にする
   • curr_a・curr_b・conv_rate の各組（x, y, z）について、temp[x] × z が temp[y] より大きければ、temp[y] を temp[x] × z に更新し、p を True に戻す
   • 全ペアの一巡が終わるごとに i を 1 増やす
5. ループ終了後、i が temp のサイズ以下であれば temp[dest] を返す
6. そうでなければ -1 を返す（更新が収束しない＝有効な経路が構成できないケース）

Pythonでの実装例

それでは、実際のコードを見てみましょう。

from collections import defaultdict

def solve(src, dest, curr_a, curr_b, conv_rate):
    temp = defaultdict(int)
    temp[src] = 1
    i = 0
    p = True
    while p and i <= len(temp):
        p = False
        for x, y, z in zip(curr_a, curr_b, conv_rate):
            if temp[x] * z > temp[y]:
                temp[y] = temp[x] * z
                p = True
        i += 1
    return temp[dest] if i <= len(temp) else -1

print(solve('INR', 'JPY', ['INR', 'GBP', 'EUR'], ['GBP', 'EUR', 'JPY'], [0.009, 1.17, 129.67]))

入力

'INR', 'JPY', ['INR', 'GBP', 'EUR'], ['GBP', 'EUR', 'JPY'], [0.009, 1.17, 129.67]

出力

1.3654251

コードのポイント

• defaultdict(int)：存在しないキーへアクセスすると自動的に 0 が設定されるため、「まだ到達していない通貨」の扱いがシンプルになります。
• zip(curr_a, curr_b, conv_rate)：3つのリストを同時に走査し、通貨ペアとそのレートをまとめて取り出せます。
• 緩和操作の繰り返し：より高い変換レートが見つかる限り更新を続けるため、間接的な変換経路（レートの掛け合わせ）も正しく反映されます。
• 収束判定：フラグ p とカウンタ i によって、「更新が起きなくなった時点」または「ノード数分の反復を超えた時点」でループを抜けます。これはベルマンフォード法における反復回数の上限と同じ発想です。

まとめ

通貨変換レートの問題は、通貨をノード・変換ペアを重み付きエッジとみなすことで、グラフアルゴリズムの知識がそのまま活かせる典型例です。為替ツールや価格比較サービスなど、実務でも応用範囲の広いテーマなので、ぜひ仕組みを理解しておきましょう。