オフラインリアルタイムどう書く F10 の実装例

問題 : http://nabetani.sakura.ne.jp/hena/ordf10updown/
実装リンク集 : https://qiita.com/Nabetani/items/dae474bc17827f9b1537

実装戦略は、概ね2つある。

ひとつは、マス目を埋めていく作戦。マス目が埋まれば上下左右の隣は簡単にわかる。
難点は計算量が多くなることだけど、今回のテストデータは最大でも7000弱なので、マス目を埋めても間に合う。

そんな実装を、ruby で。

ruby2.5

def solve( src )
  upperbound = (src+5)*2 # 根拠薄弱な計算
  pos=0+0i
  phase=0
  map={}
  target=nil
  (1..upperbound).each do |n|
    map[pos]=n
    target=pos if n==src
    case phase
    when 0
      pos+=1
      phase=1
    when 1
      pos+=1i
      phase=2 if pos.real==pos.imag
    when 2
      pos-=1
      phase=3 if pos.real==0
    when 3
      pos+=1i
      phase=4
    when 4
      pos+=1
      phase=5 if pos.real==pos.imag
    when 5
      pos-=1i
      phase=0 if pos.imag==0
    end
  end
  [target-1,target+1, target-1i, target+1i ].map{ |pos|
    map[pos] || "-"
  }.join(",")
end

DATA.map do |line|
  num, src, expected = line.split( /\s+/ )
  actual = solve( src.to_i )
  okay = expected == actual
  p [ ( okay ? "ok" : "**NG**" ), num, src, actual, expected ]
  okay
end.all?.yield_self{ |x| puts( x ? "everything is okay" : "SOMETING WRONG" ) }

__END__
0 10  9,25,-,11
1 1 -,2,-,4
2 2 1,9,-,3
3 4 -,3,1,5
33  6772  6771,6773,6677,7009

下→左→上→右→下→左 で、一周期。各移動を phase の 0〜5 に割り当ててみた。
どこまでやるかは不真面目に計算していて、ゴールの二倍ちょっと回せばいいんじゃないかといういい加減な実装になっている。

平面なので複素数を使って。
実装をミスって、下方向が実部、右方向が虚部になっている。単なるミスなんで、他意はない。

続いて別の実装。

数値から場所、場所から数値に変換できればいいというもの。
マス目の数値がどう並んでいるか、構造を理解する必要があるので算数が嫌いだと苦しいかもしれないけど、計算量がすごく少ないし、不安も少ないので仕事ならこちら一択。

そんな実装を、python で。

python3

import math

def num_at(x,y):
  if x<0 or y<0:
    return None
  layer = max(x,y)
  offset = None
  if layer % 2 == 0:
    offset = y if y<x else layer*2-x
  else:
    offset = x if x<y else layer*2-y
  return layer**2 + offset + 1

def pos_for( num ):
  layer = math.floor(math.sqrt(num-1))
  offset = num-1-layer**2
  r = [ offset, layer] if offset<layer else [ layer, layer*2-offset ]
  if layer % 2 ==0:
    r.reverse()
  return r

def impl( src ):
  x,y = pos_for( src )
  return [
    num_at(x,y-1),
    num_at(x,y+1),
    num_at(x-1,y),
    num_at(x+1,y)
  ]

def solve( src ):
  return ",".join( [ str(x) if x else  "-" for x in impl( int(src) ) ] )

def test( num, src, expected ):
  actual = solve( src )
  okay = actual==expected
  print( ( "ok" if okay else "**NG**" ), num, src, actual, expected )

test( 0, "10", "9,25,-,11" )
test( 1, "1", "-,2,-,4" )
test( 33, "6772", "6771,6773,6677,7009" )

何度も書いているんだけど、いまだに慣れないのは iftrue if cond else iffalse。
あと。
上記で r.reverse() しているけど、reversed(r) を return した方がきれいだと思う。上記を書いた時点では、reversed の存在を知らなかった。

出題者としては、上記2つが主な戦略だと思う。
マス目を埋める方の埋め方がいろいろあると思うけどね。