今週末も空いた時間を見つけてはpaizaのスキルチェックを行っていた。

paizaのスキルチェックに関しては正解、というものが提示されない。

そのため、答えが分からず延々と悩んでしまう、ということも多い。

前回のエントリに書いた通り、今はCランクの問題をせっせと解いている状態。

「Paizaのスキルチェックが楽しい」

Cランクレベルであればコードの良し悪しはあるものの、大体は正解はできる、という感じ。

ただBランクに手を付けると、上述の通り延々と悩む、ということが少なくない。

そういう時に発想を転換させてみると、うまくいくことがある。

リストを順に繰り返さない

例えばリスト。

スキルチェックに関わらずコーディングをしていると良く出会うデータ構造で、for文で繰り返したくなる、という罠がある。

例えば以下のようなシンガーソングライターを記録したリストがある。

singers = ['柴田聡子', 'カネコアヤノ', '前野健太']

これを順に出力する際には大体こういうコードを書く。

for singer in singers:
    print(singer)
>>>
柴田聡子
カネコアヤノ
前野健太

こうではなくて順に取り除いて出力させていく、という方法もある。

while singers:
    print(singers.pop(0))
>>>
柴田聡子
カネコアヤノ
前野健太

この取り除いていく、引き出しがあると、ふとした時に役立つことがある。

路線図を書き出す

例えば、以下のように首都圏の路線を表したデータがある。

route_map = [
    ('東京', '神田', '秋葉原'), # 京浜東北線
    ('東京', '新橋', '品川', '熱海'), # 東海道線
　　('品川', '宇都宮'), # 宇都宮線
    ('新宿', '荻窪', '西荻窪'), # 中央線
    ('新宿', '池袋') # 山手線
]

これをある駅から出発して、行くことができるすべての駅を出力したい、というような場合だ。

つまり東京から出発した場合は、京浜東北線、東海道線の駅に加えて、品川を経由して宇都宮まで行くことができる。

こういう問題を考えるときにリストを繰り返す、方法に固執すると難しい。

start = '東京'
stations = []
for route in route_map:
    if start in route:
        for station in route:
            if station in stations:
                continue
            stations.append(station)

print(stations)
>>>
['東京', '神田', '秋葉原', '新橋', '品川', '熱海']

東京が含まれるということを条件にしているので、乗り換えのことは考慮できていない。

つまり、このやりかただと、品川→宇都宮というルートをピックすることはできない。

そして、もう一回stationsを繰り返せば、と考えるが、また乗り換えが生まれた時にそのルートを考慮することができない。

こういう時に「どうやって繰り返しの条件を作れば」と考えてしまいがちだ。

恐らく答えはあるんだろうけど、少なくとも自分には分からなかった。

ここで発想を変えて、取り除く、という工程を加えてうまくいくことがある。

上のケースだと、例えば以下のような関数が作れるだろう。

def get_connected_value_list(a_list, start_value):
    # 検査する値　初期値をリストにしておく
    check_remains = [start_value]
    # 返すリスト
    return_values = []
    while True:
        # 検査値を取り除く
        check_value = check_remains.pop(0)
        # 検査値が含まれる路線をpickする
        for item in a_list:
            if check_value not in item:
                continue
            # 路線の駅をひとつずつ確認
            for elm in item:
                if elm not in return_values:
                    # 返すリストと検査値に加える
                    return_values.append(elm)
                    check_remains.append(elm)
        # 検査値がなくなったら終える
        if not check_remains:
            break
    return return_values

始めに出発する駅を検査値のリストにしておいて、順に取り除いて乗り換えが可能か検査していく…という考え方だ。

この関数を実行することで、網羅的に到達することが可能な駅を洗い出せる。

route_map = [
    ('東京', '神田', '秋葉原'),
    ('東京', '新橋', '品川', '熱海'),
    ('品川', '宇都宮'),
    ('新宿', '荻窪', '西荻窪'),
    ('新宿', '池袋')
]

start = '東京'
print(get_connected_value_list(route_map, start))
>>>
['東京', '神田', '秋葉原', '新橋', '品川', '熱海', '宇都宮']

処理の流れはprintをすると分かりやすい。

def get_connected_value_list(a_list, start_value):
    # ...省略
    while True:
        # ...省略
        for item in a_list:
            # ...省略
        print('check_remains:', check_remains)
        print('return_values:', return_values)
        # 検査値がなくなったら終える
        if not check_remains:
            break
    return return_values
>>>
check_remains: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
check_remains: ['神田', '秋葉原', '新橋', '品川', '熱海']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
check_remains: ['秋葉原', '新橋', '品川', '熱海']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
check_remains: ['新橋', '品川', '熱海']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
check_remains: ['品川', '熱海']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海']
check_remains: ['熱海', '宇都宮']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海', '宇都宮']
check_remains: ['宇都宮']
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海', '宇都宮']
check_remains: []
return_values: ['東京', '神田', '秋葉原', '新橋', '品川', '熱海', '宇都宮']

無駄な計算がまだあるかもしれないが、乗り換えを考慮して出力できているのが分かるのではないかと思う。

ほかの転換方法

このようにリストを取り除いてみる、という風に発想を転換させるとうまくいくことがある。

「反対」から問題を解決してみるという手がある。例えば配列を逆順にイテレートしてみる。データを後ろから挿入してみる。

とにかくいつもと反対のことをやってみるのだ。

上はリーダブルコードの引用だが、行き詰った時に考えることが多い。

例えばできる条件ではなく、できない条件を考える、リストじゃなくて辞書にしてみる、など。

おわりに

人間の習性で、一度ものごとを考え始めるとそのことに執着してしまう、というのはあると思う。

それを集中する、というのかもしれないし、その集中があるからこそ、投げ出さずに問題に取り組むことができるというメリットもある。

だけど、どうしても突破口が見いだせないときは、一度考えを捨てて、発想を変えてみるとうまくいくかもしれない。

ただし発想は天から降ってくるのではなく、自分の中の引き出しから生まれることの方が多いということは意識しておく。

今回の例だと、listのpopメソッドを知っていると、取り除いていく、という手法がイメージしやすいだろう。

ジョジョのこのセリフを思い出したな。

なにジョジョ？ダニーがおもちゃの鉄砲をくわえてはなさない？

ジョジョ、それは無理矢理引き離そうとするからだよ

逆に考えるんだ、「あげちゃってもいいさ」と考えるんだ。

大事なことを言っているのだと思う。ではでは。