オフラインリアルタイムどう書く E25 の実装例(ruby)

問題 : https://mtsmfm.github.io/2018/07/07/doukaku-e25.html
実装リンク集 : https://qiita.com/mtsmfm/items/9e06456b4330305d4ed0

で。

ビッグセブン という問題を解いた。

30分ぐらいで解いて、そのあとちょっとまとめたのが以下の実装例。

ruby2.5

# frozen_string_literal: true

require "json"

class Seven
  def initialize( w, h )
    @w=w
    @h=h
  end

  def inmap?( p )
    0<=p.real && p.real<@w && 0<=p.imag && p.imag<@h
  end

  def create_seven( s0, s1 )
    return nil if s1==s0
    d1 = s1 - s0
    s2 = s1 + d1 * 1i
    return nil unless inmap?(s2)
    s3 = s2-d1*2
    return nil unless inmap?(s3)
    [d1.abs, [s1, s2, s3]]
  end

  def find(s0)
    @w.times.flat_map do |x1|
      @h.times.flat_map do |y1|
        r=create_seven(s0, x1+y1*1i)
        r ? [r] : []
      end
    end
  end
end

def result_of(r)
  return nil if r.empty?
  maxd = r.max_by{ |e| e[0] }[0]
  cands = r.select{ |e| e[0]==maxd }
  cands.size==1 ? cands[0][1] : nil
end

def solve( src )
  w, h, x, y = src.scan( /\d+/ ).map(&:to_i)
  r=result_of(Seven.new( w, h ).find(x+y*1i))
  r ? r.map{ |e| "(#{e.real},#{e.imag})" }.join(",") : "-"
end

DATA = JSON.parse(%q!
  [
    {
      "input": "4,7,(0,3)",
      "expected": "(0,0),(3,0),(3,6)"
    },
    {
      "input": "4,6,(3,3)",
      "expected": "(2,5),(0,4),(2,0)"
    },
    {
      "input": "200,200,(24,134)",
      "expected": "(0,45),(89,21),(137,199)"
    }
  ]
!).freeze

$stdout.sync=true

DATA.map{ |o|
  actual = solve(o["input"]).to_s
  okay = actual == o["expected"]
  puts "%s s:%s a:%s e:%s" % [(okay ? "ok" : "**NG**"), o["input"], actual, o["expected"]]
  okay
}.all?.tap{ |x| puts(x ? "okay" : "something wrong") }

いつもどおりテストデータの大半は省略。

総当たりで解決という作戦。
もう少しなら計算量を減らすアイディアはあるけど、今回のテストデータはこれで0.3秒で終わるのでこのままで。

劇的に計算量を減らすアイディアはない。

平面上での回転を使いたい問題なので、複素数ととても相性が良い。

あと。

珍しくクラスを作ってみた。