Created
April 7, 2019 17:16
-
-
Save colorbox/0e57a00b22637599ce80becdc14c0081 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# bundle exec ruby ./doukaku.rb | |
require 'bundler/inline' | |
gemfile do | |
source 'https://rubygems.org' | |
gem 'activesupport', require: 'active_support/all' | |
gem 'minitest', require: 'minitest/autorun' | |
gem 'minitest-reporters' | |
gem 'awesome_print' | |
gem 'tapp' | |
gem 'byebug' | |
end | |
class Array | |
def to_lines | |
[ | |
[self[0], self[1], self[2], self[1]], | |
[self[0], self[1], self[0], self[3]], | |
[self[2], self[1], self[2], self[3]], | |
[self[0], self[3], self[2], self[3]], | |
] | |
end | |
end | |
def across?(x,y,x2,y2,lines) | |
lines.each do |line| | |
# Y線をX軸方向に飛び越える | |
across_y = (line[0]==line[2] && ((x == line[0]-1 && x2 == line[0]) || x == line[0] && x2 == line[0]-1) && ([line[1],line[3]].min <= y && [line[1],line[3]].max > y)) | |
# X線をY軸方向に飛び越える | |
across_x = (line[1]==line[3] && ((y == line[1]-1 && y2 == line[1]) || (y == line[1] && y2 == line[1]-1)) && ([line[0],line[2]].min <= x && [line[0],line[2]].max > x)) | |
return true if across_x || across_y | |
end | |
false | |
end | |
def create_figure(x, y, lines, coordinate_set) | |
coordinate_set << [x,y] | |
create_figure(x+1, y, lines, coordinate_set) if x < 34 && !across?(x,y,x+1, y, lines) && !coordinate_set.include?([x+1, y]) | |
create_figure(x-1, y, lines, coordinate_set) if x > 0 && !across?(x,y,x-1, y, lines) && !coordinate_set.include?([x-1, y]) | |
create_figure(x, y+1, lines, coordinate_set) if y < 34 && !across?(x,y,x, y+1,lines) && !coordinate_set.include?([x, y+1]) | |
create_figure(x, y-1, lines, coordinate_set) if y > 0 && !across?(x,y,x, y-1,lines) && !coordinate_set.include?([x, y-1]) | |
return coordinate_set | |
end | |
def is_square?(set) | |
nested_array = set.to_a.inject({}) do |result, item| | |
if result[item[0]].nil? | |
result[item[0]] = [item[1]] | |
result | |
else | |
result[item[0]] << item[1] | |
result | |
end | |
end | |
x_axis = nested_array.keys | |
return false if x_axis.size <= x_axis.max - x_axis.min | |
return nested_array.map{|h|h[1]}.uniq.size == 1 | |
end | |
def is_edged?(set) | |
set.to_a.map{|s|s[0]==0 || s[0]==34 || s[1]==0 || s[1]==34}.any? | |
end | |
def is_edge_enclosed?(square, lines) | |
edged_lines = lines.select{|line| line.any?{|e| e==0 } } | |
edged_square_parts = square.select{|mass|mass.any?{|e|e==0}} | |
judged_parts = edged_square_parts.map do |mass| | |
edged_lines.each do|line| | |
# X=0 線分の右隣にいる or X=35 線分の左隣にいる | |
if (line[0] == line[2] && ((line[0] == 0 && mass[0] == 0) || (mass[0] == 34 && line[0] == 35))) && (mass[1] < [line[1], line[3]].max && mass[1] >= [line[1], line[3]].min) | |
return true | |
end | |
# Y=0 線分の直下にいる or Y=35 線分の直上にいる | |
if (line[1] == line[3] && ((line[1] == 0 && mass[1] == 0) || (mass[1] == 34 && line[1] == 35))) && (mass[0] < [line[0], line[2]].max && mass[0] >= [line[0], line[2]].min) | |
return true | |
end | |
end | |
return false | |
end | |
return judged_parts.all? | |
end | |
# 35*35マスごとに集合を作成 | |
# 隣接マスに再帰で移動 | |
# 隣接するマスに移動する時に、横断判定、横断するならヤメ、作成中の集合に包含判定、含まれていたらヤメ | |
# 集合にマスを放り込んでいく、再帰が終わったら集合を返す | |
# 集合の集合を作る | |
# 各マスに対する集合(図形)ができたらその集合(図形)を集合の集合に突っ込む、同一の図形集合は同一の図形をみなして、除外する。 | |
# 同一集合は同じ図形と認識 | |
# 最後に各図形に矩形判定しておわり | |
def create_set(lines) | |
the_set = Set.new | |
(0..34).each do |x| | |
(0..34).each do |y| | |
next if the_set.to_a.map{|s|s.include?([x,y])}.any? | |
coordinate_set = create_figure(x, y, lines, Set.new) | |
# puts "#{x},#{y}:#{coordinate_set.size}" | |
the_set << coordinate_set | |
end | |
end | |
the_set | |
end | |
def test(input) | |
squares = input.split('/').map{|squre|squre.chars.map{|coordinate|coordinate.to_i(36)}} | |
lines = squares.flat_map(&:to_lines) | |
figure_set = create_set(lines) | |
squares = figure_set.select{|s|is_square?(s)} | |
border_with_line_square = squares.select{|s|is_edge_enclosed?(s, lines)} | |
# falsquare = squares[0] | |
# puts is_edge_enclosed?(falsquare, lines) | |
return border_with_line_square.map(&:size).sort.join(',') | |
end | |
# TEST_DATA = <<~EOS | |
# /*1*/ test( "034a", "28" ); | |
# /*41*/ test( "j4mu/31r5/qeyf/0f5h/r0v5/00qi/j5kf/jlru", "3,4,8,9,10,10,20,27,45,52" ); | |
# /*45*/ test( "0qbs/6cws/l6xj/659q/03lc/bclp/96dj/96wc", "10,12,13,14,14,21,24,42,48,66,77" ); | |
# /*46*/ test( "q8sr/98yu/clyn/s8yl/9lqr/0rsu/0l9m/0n9u", "4,8,9,12,26,27,28,36,42,57,78,221" ); | |
# EOS | |
TEST_DATA = <<~EOS | |
/*0*/ test( "43gw/d7qq/mlop", "8,57" ); | |
/*1*/ test( "034a", "28" ); | |
/*2*/ test( "06qr/8pnq", "15" ); | |
/*3*/ test( "c1th/b2qy", "210" ); | |
/*4*/ test( "c8wz/gbsg/i0xd", "20" ); | |
/*5*/ test( "97uv/2g5x/eihv", "39,51" ); | |
/*6*/ test( "254d/2jvu/mjvu", "16,99,220" ); | |
/*7*/ test( "ggiu/ggzu/g5ig", "22,28,238" ); | |
/*8*/ test( "jbnc/i7xe/i7je/icje", "2,4,5" ); | |
/*9*/ test( "3cey/0fzo", "27,33,99,110,189" ); | |
/*10*/ test( "00ab/p0zd/0ofz/87rs", "8,12,28" ); | |
/*11*/ test( "1dsy/2d9s/2s9y", "21,42,105,399" ); | |
/*12*/ test( "28db/d0lm/d1i8/l0w5", "33,35,55" ); | |
/*13*/ test( "3aen/4fir/1lev", "2,20,40,48,60" ); | |
/*14*/ test( "j7ou/3rms/m4vs", "3,10,16,42,60" ); | |
/*15*/ test( "336a/3rkw/jlor/3akw", "6,21,24,85" ); | |
/*16*/ test( "21om/87bv/67cv", "9,15,18,27,30,45" ); | |
/*17*/ test( "4hhx/056u/4rvu", "6,20,33,39,42,110" ); | |
/*18*/ test( "b0sh/pgxt/88lq/amux", "3,20,35,44,90" ); | |
/*19*/ test( "c0hc/h6md/fdmk/4cfj", "2,35,49,60,77" ); | |
/*20*/ test( "0liz/ilvz/0lvr/0rvz", "78,104,108,144" ); | |
/*21*/ test( "81ib/q1zb/8cir/qczr", "90,100,135,150" ); | |
/*22*/ test( "h7t8/t8ye/g8he/hetz", "6,12,30,72,252" ); | |
/*23*/ test( "b5qy/o6qc/21tb/qoyu/b5eu", "2,10,18,48,57" ); | |
/*24*/ test( "eajn/jkln/j8ua/nkun/u4wy", "6,21,22,60,65" ); | |
/*25*/ test( "wwzz/nfuw/nfzz/41vw/l1r2/nfrg", "4,6,9,17" ); | |
/*26*/ test( "46rb/t6xb/m7zk/4hrj/thxj", "4,8,10,16,20,36" ); | |
/*27*/ test( "olwx/ogul/ogwx/ogux/agux", "10,24,30,72,238" ); | |
/*28*/ test( "b7un/c3hv/fiyo/h6xm", "2,10,12,13,16,20,52,143" ); | |
/*29*/ test( "d6qa/o4qr/tcur/9bto", "2,4,6,8,15,26,39,44,195" ); | |
/*30*/ test( "2lsx/54hf/k3yi/8dhw/bhny", "3,12,18,24,33,60,66" ); | |
/*31*/ test( "apcx/a8pv/7uwx/a2c8/c8pu", "2,4,9,10,12,13,34,286" ); | |
/*32*/ test( "7yjz/jywz/7ejz/j5wy/bejz/jewy", "4,8,13,80,117,160,260" ); | |
/*33*/ test( "d0wk/5dqu/6lqs/77ae/f4mq/56bm", "3,4,5,7,14,18,28,35,49,63" ); | |
/*34*/ test( "d4gn/94in/d4rs/94xu/97xn", "6,9,12,18,27,32,48,64,70,96,144" ); | |
/*35*/ test( "l5wh/wdxn/60xs/c5fd/jpwx/mgqx", "4,9,10,12,15,18,20,24,30,32" ); | |
/*36*/ test( "5178/58xk/uixk/71u8/71uk/71ui/51ui", "4,6,14,20,30,46,161,230" ); | |
/*37*/ test( "m8sp/mosp/2imp/i8sp/2isp/i8si/misp/iosp", "4,6,24,36,40,60,112" ); | |
/*38*/ test( "34d5/253k/f4m5/m5rk/2o3u/3udy/fumy/moru", "6,7,10,15,28,30,40,75" ); | |
/*39*/ test( "2ilw/mbnc/n9wj/9dmy/6qwy/2ekh/9dkh", "1,6,11,18,21,33,72,80,90,96" ); | |
/*40*/ test( "j0le/10uo/q6ue/jeqt/jelf/l6xf", "2,4,5,27,28,32,35,36,40,54,63,432" ); | |
/*41*/ test( "j4mu/31r5/qeyf/0f5h/r0v5/00qi/j5kf/jlru", "3,4,8,9,10,10,20,27,45,52" ); | |
/*42*/ test( "g8kc/dbuv/gbkc/dbgv/evuw/dbui/d8kw", "1,4,6,9,10,12,21,24,39,52,70,130" ); | |
/*43*/ test( "apry/a0ry/a0hx/60hp/6xhy/a0hp/a0hy/6phy/6phx", "4,7,32,56,90,100,175,250" ); | |
/*44*/ test( "1eok/33by/d0kz/1rnw", "10,10,12,12,14,15,16,21,24,35,40,42,48,49,56,88,98" ); | |
/*45*/ test( "0qbs/6cws/l6xj/659q/03lc/bclp/96dj/96wc", "10,12,13,14,14,21,24,42,48,66,77" ); | |
/*46*/ test( "q8sr/98yu/clyn/s8yl/9lqr/0rsu/0l9m/0n9u", "4,8,9,12,26,27,28,36,42,57,78,221" ); | |
/*47*/ test( "5sjy/jbsy/8dgp/gkvp/gdvh/jhvp/i2vk", "3,4,6,8,9,12,15,15,18,27,36,45,81,84,96" ); | |
/*48*/ test( "42va/10nf/23l6/c2uw/3hpo/4ofu/m7sv", "3,5,6,8,8,15,18,20,21,24,27,32,48,50,63,70" ); | |
/*49*/ test( "84lj/10j1/wcxd/ljnl/1njx/01xd/00x1/81wq/1c8q", "1,1,4,7,11,14,18,21,33,70,78,117,126" ); | |
/*50*/ test( "kfvg/76vq/136d/6gvq/6g7q/137g/7dmz/63m6/m3vz", "2,3,9,10,27,45,50,81,81,90,105,135,150" ); | |
/*51*/ test( "4eht/38jt/jeym/htjv/eeyv/eejt/3myv/h1jt/hejm", "4,6,7,12,14,14,16,21,22,24,70,80,120,135" ); | |
/*52*/ test( "smuz/04c7/28zc/83ri/cihu/8flm/masw/8ivo", "2,4,6,8,10,10,12,16,16,20,22,24,24,30,30,36,39,48" ); | |
/*53*/ test( "7fuu/17fd/6cpg/fghu/ahnt/adww/rhxz/4hxl/0pby", "1,2,2,2,3,3,4,4,4,5,8,8,9,10,12,12,12,12,15,15,16,16,20,24,27,30,32,48" ); | |
EOS | |
Minitest::Reporters.use!(Minitest::Reporters::ProgressReporter.new) | |
# docker-compose run --rm -w /app/YYYYmmdd bundle exec ruby doukaku.rb -n /#1$/ | |
describe 'Doukaku' do | |
def self.test_order; :sorted; end | |
TEST_DATA.each_line do |test| | |
number, input, expected = test.scan(/(\d+).*"(.*)", "(.*)"/)[0] | |
it "##{number}" do | |
assert_equal expected, test(input) | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
eval File.read('doukaku.rb').scan(/gemfile do\n(.*?)\nend/m)[0][0] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment