毎朝ちびちびCodewars。
Sat Nav directions [5 kyu] www.codewars.com
今日のお題：
""" sat_nav(directions)
東西南北に、1Kmごとの格子状に広がる道路がある。
スタート地点 座標[0，0] からナビゲーションの指示に従って進み、最終到達点の座標返す。
開始メッセージ
Head <NORTH,EAST,SOUTH,WEST>
中間ナビゲーション（次の4パターンのいずれかが指示される。指示数不定）
Take the <NEXT,2nd,3rd,4th,5th> <LEFT,RIGHT> （※）
Go straight on for <100,200,300,...,900>m
Go straight on for <1.0,1.1,1.2,...,5.0>km
Turn around! （その場で真逆に方向転換）
※ Nブロック先の交差点で左/右に曲がる。
ここでいう「NEXT」は、今現在 交差点上にいたとしても、その場で曲がるのでなく、
"次の" 交差点に進んで曲がる意味。
終了メッセージ
You have reached your destination!
Args:
directions (list): メッセージ(str)のリスト
Returns:
[x, y]: 最終座標 (100m = 1)
"""
コード
me
https://www.codewars.com/kata/reviews/5ab06c0d927c13f5890000ac/groups/5cdf6b24cf98fc0001c9b2f5
from decimal import Decimal import math import re def sat_nav(directions): # cosθ whenθ=0, 90, 180, 270° CSIN = (1, 0, -1, 0) # first direction action = directions.pop(0) m = re.match('Head (.+)$', action) head = ['EAST', 'NORTH', 'WEST', 'SOUTH'].index(m.group(1)) x, y = 0, 0 # decode subsequent directions for action in directions: if action == 'You have reached your destination!': return [round(x*10), round(y*10)] elif action == 'Turn around!': head = (head+2)%4 else: # 'Go straight on for (\d)00m$' m = re.match('Go straight on for (\d)00m$', action) if m: dist = Decimal('0.'+m.group(1)) x += dist * CSIN[head] y += dist * CSIN[head-1] continue # 'Go straight on for (\d\.\d)km$' m = re.match('Go straight on for (\d\.\d)km$', action) if m: dist = Decimal(m.group(1)) x += dist * CSIN[head] y += dist * CSIN[head-1] continue # 'Take the (.+?) (LEFT|RIGHT)$' m = re.match('Take the (.+?) (LEFT|RIGHT)$', action) if m: dist = ['NEXT', '2nd', '3rd', '4th', '5th'].index(m.group(1)) if CSIN[head] == 1: x = math.ceil(x+Decimal('0.1')) + dist elif CSIN[head] == -1: x = math.floor(x-Decimal('0.1')) - dist elif CSIN[head-1] == 1: y = math.ceil(y+Decimal('0.1')) + dist else: y = math.floor(y-Decimal('0.1')) - dist head = (head+1)%4 if m.group(2)=='LEFT' else (head+3)%4 continue
- 'Go straight on for X00m' と 'for X.Xkm' は処理が酷似しており、
工夫すれば一つにまとめられそう。※力尽きたので深追いしてない ^^;; - 'Take the (.+?) (LEFT|RIGHT)' の処理もイマイチ。むーん。
リストの要素にサイクリックにアクセスする
- 座標の移動量は、 dx = 移動距離 * cosθ dy = 移動距離 * sinθ で求まる。 今回は直角方向にしか移動しないので cosθ値は90°ごとの4値をタプル csin = (1, 0, -1, 0) で持ち表引きする。sinθ = cos(θ-90°)だから表引き用には csin だけあればいい。
インデックスは 進行方向 head に対応して 東北西南 の順に、0, 1, 2, 3 の値を取る。 csin[head] で cosθ が得られるようにする。
- 方向転換時の 次の進行方向head は、 剰余演算子を使ってサイクリックに算出できる。
現在の head が 東西南北のどこであっても
真逆を向く時 (head+2)%4
左 (head+1)%4
右 (head+3)%4
この方法は、例えばリスト
str = ['a', 'b', 'c', 'd']
に対して、a -> b -> c -> d -> a -> b -> ... のように、 リストの要素にサイクリックにアクセスしたい時にも使える。
"Nブロック先の交差点で左/右に曲がる" の float型の計算にはまる
"Nブロック先の交差点" の処理にすごく苦労した。
言葉で言うと、
- 座標がプラス方向に進む場合は、現在座標の小数点以下の端数を切り捨てて、Nkm分を足す
- 座標がマイナス方向に進む場合は、現在位置の小数点以下の端数を切り上げてから、Nkm分を引く
のだが、float型の特性がくせ者で、
- ちょうど交差点（端数0）上にいる場合の座標値の計算結果が、 ジャスト -4 でなく-3.9999... のような数値を返すことがある。 それを端数切り捨て/切り上げすると、正しい答えから 1ブロック分ずれてしまう。
具体的には、
# 'Take the (.+?) (LEFT|RIGHT)$' m = re.match('Take the (.+?) (LEFT|RIGHT)$', action) if m: debug_before() dist = ['NEXT', '2nd', '3rd', '4th', '5th'].index(m.group(1)) if CSIN[head] == 1: x = math.ceil(x+0.1) + dist
の部分で、例えば
直前の状態: EAST (x,y) = (-4.1, 2.0)
ナビメッセージ: Take the NEXT LEFT
このメッセージ実行後は
NORTH, (x,y) = (-4.0, 2.0)
となるのが正しいが、
> <ipython-input-305-7ad2ec85a613>(62)sat_nav()
-> print(f'x+0.1: {x+0.1}, ceil: {math.ceil(x+0.1)}, dist: {dist}')
(Pdb) n
x+0.1: -3.9999999999999996, ceil: -3, dist: 0
-4.1+0.1 が -4でなく-3.9999... となってしまい、切り上げた結果が 1 ずれてしまった。
=> NORTH x,y = -3, 2.0
1.1 や 2.2 のような数は、二進数の浮動小数点型では正しく表現できないらしい。
正しく計算する場合は、decimal モジュール を使う。標準モジュールで、import して使う。
- decimal --- 十進固定及び浮動小数点数の算術演算 — Python 3.7.3 ドキュメント
- Pythonで小数・整数を四捨五入するroundとDecimal.quantize | note.nkmk.me
文法、関数・メソッドnote
math.ceil(x)
math --- 数学関数 — Python 3.7.3 ドキュメント x 以上の最小の整数を返す。
math.floor(x)
math --- 数学関数 — Python 3.7.3 ドキュメント x 以下の最大の整数を返す。
pdbデバッガ
標準モジュール pdb を使うと、任意箇所で実行を止めて 対話的に ステップ実行したりブレークポイントを設定してデバッグを進めることができる。
Jupyter Notebook上でも動く。
スクリプト内に import pdb して使うこともできるし、デバッグモードで目的のプログラムを実行することもできる。
- pdb --- Python デバッガ — Python 3.7.3 ドキュメント
- pdbデバッガでできることをざっくり把握する参考記事。いずれも古い記事だが、基本的な使い方は変わってない。
使い方メモ
コードの処理を止めてデバッグを始めたい箇所に、
import pdb; pdb.set_trace()
を書いておく。
