acokikoy's notes

最近気になる=[NoCode, Shopify], I am..=[Python, ウクレレ, マニュアル車, CMS] LoveなWebディレクター

毎朝Codewars@2019.05.18(金): Sat Nav directions

毎朝ちびちび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)
"""

https://i.imgur.com/6MFbhPO.png

コード

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 して使う。

文法、関数・メソッド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 して使うこともできるし、デバッグモードで目的のプログラムを実行することもできる。

使い方メモ
コードの処理を止めてデバッグを始めたい箇所に、 import pdb; pdb.set_trace()
を書いておく。

スクリプトを実行すると、その場所で処理がとまり「(Pdb)」プロンプトが表示されてコマンドを受け付け状態になる。

コマンドはここ
pdb --- Python デバッガ >デバッガコマンド — Python 3.7.3 ドキュメント