【Project Euler】Problem 220 Heighway Dragonの感想（その１）

8607 ワード
Python ProjectEuler ドラゴン曲線 Python テキストリンク

Heighway Dragonとは

はじめて投稿します。Proejct Eulerをやられている方は結構いらっしゃるみたいですが100番以降になると、なかなか日本語の投稿が見つからなかったので、なんとか解けたもの感想等を投稿して行きたいと思います。（解答のコードは掲載していません）
元の問題はこちら->Project Euler 220 Heighway Dragon

要はD50のHeighway Dragon曲線の1012番目の点の座標を求めろという問題です。

開発環境はGoogle Colaboratory上でPythonで書いています。

まずHeighway Dragonを描いてみた

Heighway Dragonがどんなものか知らなかったのでまず素直に定義通りにプログラムを書いて描いてみました。関数HDragonを再帰的に使っています。

# Heighway Dragon ; s: string, dp: depth 
def HDragon(s,dp): 
  if dp == -1: return 
  for c in s:
    if c == "a":   HDragon("aRbFR", dp-1)
    elif c == "b": HDragon("LFaLb", dp-1)    
    elif c == "F": pos = hdpath.forward()
    elif c == "R": dir = hdpath.turnR()
    elif c == "L": dir = hdpath.turnL()
  return 

depth = 18
posx, posy = [0], [0]
hdpath = path(np.array([0,0]),0,0)
HDragon("Fa", depth)
print(f"End: step={hdpath.step}, dir={hdpath.dir}")

Class Pathは各文字のF,R,Lに従って座標や方向の変数を書き換えています。

DL = np.array([[0,1],[1,0],[0,-1],[-1,0]])  # U, R, D, L
class path:  
  def __init__(self,pos,dir,step):
    self.pos = pos
    self.dir = dir
    self.step = step

  def forward(self):
    self.pos += DL[self.dir]
    self.step += 1
    posx.append(self.pos[0])
    posy.append(self.pos[1])
    return self.pos

  def turnR(self):
    self.dir = (self.dir+1)%4
    return self.dir

  def turnL(self):
    self.dir = (self.dir-1)%4
    return self.dir

この結果得られた座標のリストを使ってmatplotlibで書いたものはこちらです（Depth=18）。

[Dragon Curve D=18]