問題文
問題文の詳細は👆を参照してください
記事の背景
Atcorderコンテストで書きながらめっちゃ糞コードだなと自覚しつつ無理やりAC(合格)しましたが、後ろ髪ひかれる思いがあったのでリファクタします。
この記事の対象は、未経験エンジニアさん、暦浅エンジニアさん向けに
- 方針ブレブレのまま実装しちゃうとよくこうなるよ
- このままプルリク出すと怒られちゃうよ
- こういうコードは言われる前にリファクタしましょう
ということを自戒の念を込めて書きたいと思います。
糞コード
アルゴリズムの詳細や、ダメ出しは後述するので糞っぷりをご覧ください
from collections import defaultdict
T = list(input())
U = list(input())
if U in T:
print("Yes")
exit()
ct = 0
cts = []
for t in T:
if t == "?":
ct += 1
else:
cts.append(ct)
ct = 0
else:
cts.append(ct)
if max(cts) >= len(U):
print("Yes")
exit()
for i,u in enumerate(U):
for j,t in enumerate(T):
if u == t:
if j-i >= 0 and len(U)-i+j <= len(T):
U1 = U[:i]
U2 = U[i+1:]
T1 = T[j-i:j]
T2 = T[j+1:len(U)-i+j]
# print(U1,U2,T1,T2)
for u1,t1 in zip(U1,T1):
if u1 == t1 or t1 == "?":
pass
else:
break
else:
for u2,t2 in zip(U2,T2):
if u2 == t2 or t2 == "?":
pass
else:
break
else:
print("Yes")
exit()
print("No")
実装方針
先のコードの実装方針は以下です。
- 文字列T中に文字列Uが部分一致する場合はYesを出力
- 文字列T中に連続する"?"が文字列Uの文字数以上ある場合はYesを出力
- 文字列Uを1文字ずつ(Ui)文字列Tと突合し、一致する場合(Tj)、Uと対応するT(U文字分)を突合し、UとTが"?"または同一文字で一致する場合はYesを出力
- 上記を満たさない場合はNoを出力
という方針になります。
糞コードのダメ出し
- defaultdictどこにも使ってない。。。
- exit()連発してるの糞。。。
- 条件式が冗長。。。
- 全体的にやりたいことに対してコードが長すぎる。。。
- 出力の"Yes","No"は各一回だけ記述すべきだが、"Yes"を3回書いている。。。
- 文字列T中に文字列Uが部分一致する場合を以下の書き方では実現できていない。。。
if U in T:
print("Yes")
exit()
リファクタリング過程
意味をなしていないコードは悪
ということで以下を消します
from collections import defaultdict
# この箇所で確認したいことはメイン処理で正しく判定可能なので本質的に不要
if U in T:
print("Yes")
exit()
正規表現を使ってコード圧縮
以下の箇所は正規表現を使えば1行に圧縮可能でした
# BEFORE
ct = 0
cts = []
for t in T:
if t == "?":
ct += 1
else:
cts.append(ct)
ct = 0
else:
cts.append(ct)
# AFTER
import re
cts = [len(m) for m in re.findall(r'\?+', ''.join(T))] or [0]
関数化して見通しをよくする
exit()やprint("Yes")の連呼は関数化をサボるから起きるのでコア処理部分を関数化します。
# コア処理部分を関数化
def check_match(T,U):
for i,u in enumerate(U):
for j,t in enumerate(T):
{...省略}
# 関数化すると以下のようにできる
if max(cts) >= len(U) or check_match(T,U):
print("Yes")
else:
print("No")
コア処理部分の見直し
まずUとTを一致した文字の左右でリストを分けて突合してますが、リストを4つも新規に作っているので確認処理も冗長になってます。
本質的にUと確認対象のT(U文字分)を確認すればいいので以下のように圧縮できます。
※ついでにlen(U),len(T)を毎回計算し直すのは非効率なので計算回数を1回のみに修正します
# BEFORE
for i,u in enumerate(U):
for j,t in enumerate(T):
if u == t:
if j-i >= 0 and len(U)-i+j <= len(T):
U1 = U[:i]
U2 = U[i+1:]
T1 = T[j-i:j]
T2 = T[j+1:len(U)-i+j]
# print(U1,U2,T1,T2)
for u1,t1 in zip(U1,T1):
if u1 == t1 or t1 == "?":
pass
else:
break
else:
for u2,t2 in zip(U2,T2):
if u2 == t2 or t2 == "?":
pass
else:
break
else:
print("Yes")
exit()
# AFTER
def check_match(T,U):
T_length, U_length = len(T), len(U)
for i,u in enumerate(U):
for j,t in enumerate(T):
if u == t:
# Ui一致したTjの位置から対応するTはT[j-i:len(U)-i+j]となる
# j-iが負の数、len(U)-i+jがT文字分を超えるケースがあるのでガード文が必要
if j-i >= 0 and len(U)-i+j <= len(T):
for u1,t1 in zip(U,T[j-i:len(U)-i+j]):
if not u1 == t1 and not t1 == "?":
break
else:
return True
return False
さらに、allメソッドを使うと、物凄く条件式の見通しが良くなります
# AFTER2
def check_match(T,U):
T_length, U_length = len(T), len(U)
for i,u in enumerate(U):
for j,t in enumerate(T):
if u == t:
# Ui一致したTjの位置から対応するTはT[j-i:len(U)-i+j]となる
# j-iが負の数、len(U)-i+jがT文字分を超えるケースがあるのでガード文が必要
if j-i >= 0 and U_length-i+j <= T_length:
if all(u1 == t1 or t1 == "?" for u1,t1 in zip(U,T[j-i : U_length-i+j])):
return True
return False
最終的なコード
とても見通しが良くなりました！
元コードが50行に対して、リファクタ後は23行と半減しました！
このコードならプルリクしても恥ずかしくないです！
import re
def check_match(T,U):
T_length, U_length = len(T), len(U)
for i,u in enumerate(U):
for j,t in enumerate(T):
if u == t:
# Ui一致したTjの位置から対応するTはT[j-i:len(U)-i+j]となる
# j-iが負の数、len(U)-i+jがT文字分を超えるケースがあるのでガード文が必要
if j-i >= 0 and U_length-i+j <= T_length:
if all(u1 == t1 or t1 == "?" for u1,t1 in zip(U,T[j-i : U_length-i+j])):
return True
return False
if __name__ == "__main__":
T = list(input())
U = list(input())
cts = [len(m) for m in re.findall(r'\?+', ''.join(T))] or [0]
if max(cts) >= len(U) or check_match(T,U):
print("Yes")
else:
print("No")
コメントフィードバックの反映(20250504)
@shiracamus (しらかみゅ)さんより貴重なフィードバックを頂いたので更にリファクタします！
関数の命名
「if check match」だと「もしマッチするかチェックするなら」となり、意味不明です。
「if match」「もしマッチするなら」でいいかと思います。
でも問題文は「含んでいた可能性があるかどうか」なので「if includes」や「if contains」の方が良さそうです。matchだと全体一致という意味にとれそうなので。
確かにif {関数名}で考えると現状のコードでは意味不明です。。。
containsに修正します！
Tからlen(U)文字ずつ切り出す処理
Tからlen(U)文字ずつ切り出す処理は、開始位置をずらしたスライスをzipすると楽できますよ。
同じ文字か?かはinで判定するのが楽かと思います。
# @shiracamus (しらかみゅ)さんより頂いたサンプルコード
def contains(T, U):
"""ワイルドカード文字'?'を含む文字列Tに文字列Uが含まれればTrueを返す"""
return any(all(t in (u, '?') for t, u in zip(s, U))
for s in zip(*[T[i:] for i in range(len(U))]))
print("Yes" if contains(input(), input()) else "No")
私のボキャブラリにない凄く素敵な書き方です🧚
少し解説しますと、
# T = "atcoder"
# len(U) = 4
# Tを0からU文字分のスライディングウィンドウをそれぞれ作る
for s in zip(*[T[i:] for i in range(len(U))])
## zip内はこうなる: for s in zip("atcoder","tcoder","coder","oder")
# 各スライディングウィンドウとUを1文字ずつ突合して、tはu又は"?"と一致するか確認する
all(t in (u, '?') for t, u in zip(s, U))
## sは"atco","tcod" ...とTを1文字ずつずらしたU文字分を整形しており、
## Uと突合して条件を満たしているか確認している)
# anyをつけることでsのいずれかが条件を満たせばTrueになる
any(all(t in (u, '?') for t, u in zip(s, U)) for s in zip(*[T[i:] for i in range(len(U))]))
最終的なコード
@shiracamus (しらかみゅ)さんより頂いたサンプルコードでは
T内にU文字分以上"?"がつくチェックも実施できているので、こんなに圧縮できます🧚
コード量が最初の1/10になりました🤩
def contains(T, U):
"""ワイルドカード文字'?'を含む文字列Tに文字列Uが含まれればTrueを返す"""
return any(all(t in (u, '?') for t, u in zip(s, U))
for s in zip(*[T[i:] for i in range(len(U))]))
if __name__ == "__main__":
print("Yes" if contains(input(), input()) else "No")
終わりの言葉
コーディングスキル高める最も効果的な方法は、
自分の実装をホットなうちに見返してリファクタするのが一番だと私は考えてます！
何かの参考になれば幸いです！
※自身でやってみて、allメソッドとかreモジュールとか上手く使うとすごいコード綺麗になるなと改めて自覚する良い機会になりました。汚いコード綺麗にできると実入が凄く多いです！
ぜひお試しあれ！