Ore In The Desert (Scientific Expedition) - 砂漠の中の鉱石

どんな問題？

Ore In The Desert
http://www.checkio.org/mission/ore-in-the-desert/

砂漠の中から、鉱石を探し出せ。
探査機を指定の座標に送ると、鉱石までの距離（整数値）がわかる。
4機の探査機を使って、鉱石の座標を見つけよ。

砂漠は10x10マスで座標は [0,0]～[9,9] となる。[y,x] 形式なので注意。
例えば、鉱石が [2,6] にあるとき、探査機を [5,3] に送ると、2点の距離は 4.24... なので、丸めた 4 が得られる。これを4回繰り返して、鉱石の座標を見つければよい。

今回は、checkio()関数が繰り返し呼ばれるタイプの問題。
引数は、今までの探査機の座標と、鉱石までの距離の履歴が list of list で渡される。探査機の座標が [5,3] で距離 4 なら、[5,3,4] となる。
戻り値は、次の探査機の座標を [y,x] 形式で返す。[y,x]が鉱石の座標であれば終了。

例題：

checkio([])
checkio([[5, 3, 4]])
checkio([[5, 3, 4], [2, 9, 3]])

どうやって解く？

前に苦労した、Bulls and Cowsと似ている。全部で10x10=100マスしかないので、前よりも簡単かな。

まず、2点間の距離を計算する関数を作る。

    def get_dist(r, c, ore):
        return round(((r - ore[0]) ** 2 + (c - ore[1]) ** 2) ** 0.5)

あらかじめエディタに記載されているセルフチェック用の関数 check_solution() のものを使った。
平方根（ルート）を求めるのに、math.sqrt() を使わず、 ** 0.5 にしてあるあたりが面白い。

後はBulls and Cowsと同じように、全100マスの中から条件に一致するマスを候補として残していく。

    candidates = [(row, col) for row in range(10) for col in range(10)]
    for row, col, dist in previous:
        candidates = [ore for ore in candidates if get_dist(row, col, ore) == dist]
    return candidates[0]

これで本当に4ステップ以内に正解が見つかるか、確認してみた。
step数を集計するために書いたコードはこちら。

import collections

MAX_STEP = 10

def test():
    def get_step(ore):
        recent_data = []
        for step in range(1, MAX_STEP):
            row, col = checkio([d[:] for d in recent_data])
            if not (0 <= row < 10 and 0 <= col < 10):
                raise IndexError
            if (row, col) == ore:
                return step
            dist = round(((row - ore[0]) ** 2 + (col - ore[1]) ** 2) ** 0.5)
            recent_data.append([row, col, dist])
        return -1

    ores = [(row, col) for row in range(10) for col in range(10)]
    steps = collections.defaultdict(int)
    for ore in ores:
        step = get_step(ore)
        steps[step] += 1

    print('|*step|*count|')
    for step in sorted(steps):
        print('|{}|{}|'.format(step, steps[step]))

結果はこちら。

step	count
1	1
2	13
3	69
4	17

大丈夫みたいだ。

まとめ

def checkio(previous):
    def get_dist(r, c, ore):
        return round(((r - ore[0]) ** 2 + (c - ore[1]) ** 2) ** 0.5)
 
    if not previous:  # previous == []
        return [0, 0]
 
    candidates = [(row, col) for row in range(10) for col in range(10)]
    for row, col, dist in previous:
        candidates = [ore for ore in candidates if get_dist(row, col, ore) == dist]
    return candidates[0]

http://www.checkio.org/mission/ore-in-the-desert/publications/natsuki/python-3/first/
公開しておく。

他の人の答え

あ、しまった。ここいらんかった。

    if not previous:
        return [0, 0]

ちょっと気になったのがこれ。

if round(hypot(x - i, y - j), 0) == d

http://www.checkio.org/mission/ore-in-the-desert/publications/bryukh/python-3/second/

hypotってなんだろ？

math.hypot(x, y)
ユークリッドノルム(sqrt(x*x + y*y))を返します。これは原点から点 (x, y) のベクトルの長さです。

ほほう。