Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
103 lines (100 sloc) 3.47 KB
def solve input
# implement
n,*r=input.split /\W/
n=n.to_i
iv=r.flat_map{|s|s.chars.map{|c|(5-c.to_i)%4}}
ms=n*n
mat=(0...ms).map{|r|
y1,x1=r.divmod(n)
(0...ms).map{|c|
next 1 if r==c
y2,x2=c.divmod(n)
(x1-x2).abs+(y1-y2).abs==1 ? 3 : 0
}
}
#p n,iv
ms.times{|r|mat[r].push(iv[r])}
#p mat
done={}
(0...ms).each{|i|
bi=(0...ms).find{|j| !done[j]&&mat[j][i].odd? }
if bi
(i..ms).each{|j| mat[bi][j]=(-mat[bi][j])%4 } if mat[bi][i]==3
else
bi=(0...ms).find{|j| !done[j]&&mat[j][i]==2 } or next
(i..ms).each{|j| t=mat[bi][j]; raise if t.odd?; mat[bi][j]=t/2 }
end
(0...ms).each{|j|
next if j==bi
c=mat[j][i]
(i..ms).each{|k|
mat[j][k]=(mat[j][k]-c*mat[bi][k])%4
}
}
done[bi]=i
}
counts=(0...ms).map{|i| (j=done[i]) ? mat[j][-1] : 0 }
ans=(0...ms).flat_map{|i|
next [] if counts[i]==0
y,x=i.divmod(n)
x+=1
y+=1
[[x,y]]*counts[i]
}
ans.map{|r|r*?,}*?|
end
def test(n,input)
actual=solve(input).to_s
puts "#{n} #{actual}"
end
# test cases below
test( 0, "2|24,21")
test( 1, "2|22,32")
test( 2, "2|43,23")
test( 3, "2|21,42")
test( 4, "2|44,11")
test( 5, "2|41,11")
test( 6, "2|34,31")
test( 7, "2|14,11")
test( 8, "3|313,413,224")
test( 9, "3|313,314,443")
test( 10, "3|332,111,313")
test( 11, "3|214,134,114")
test( 12, "3|312,323,423")
test( 13, "3|332,314,334")
test( 14, "3|134,323,313")
test( 15, "3|213,341,342")
test( 16, "4|4224,3214,4412,4143")
test( 17, "4|3411,1431,3231,3323")
test( 18, "4|2414,3443,2214,4211")
test( 19, "4|2232,1332,3111,3112")
test( 20, "4|2314,2312,1213,4131")
test( 21, "4|1133,2433,3322,2244")
test( 22, "4|2342,2332,4323,3441")
test( 23, "4|4313,2341,2314,4323")
test( 24, "4|1413,4134,4423,3424")
test( 25, "4|4342,4444,3314,1222")
test( 26, "6|132122,422333,312321,143142,241313,422431")
test( 27, "6|342314,133344,224212,223431,412333,332231")
test( 28, "6|114244,133443,434111,144414,441333,222324")
test( 29, "6|211423,341131,123222,333322,132112,434132")
test( 30, "6|213222,213343,421231,431132,114444,333134")
test( 31, "6|344411,142134,432142,332413,423244,234324")
test( 32, "6|213132,123133,131342,413444,114113,231313")
test( 33, "6|422124,433221,223323,314424,123114,424234")
test( 34, "6|124124,142342,432221,331133,243414,242124")
test( 35, "6|411141,323424,434224,221434,132421,421213")
test( 36, "7|3221234,1332413,4441423,1413224,3121142,1444424,1221122")
test( 37, "7|4322444,1221244,4212134,4112243,2214221,2131441,1223332")
test( 38, "7|3421331,1442333,4332132,3414343,1432222,2313113,2244334")
test( 39, "7|4441141,4314132,1211313,2442122,3232134,4212124,2221233")
test( 40, "7|2443244,3114123,3124442,4343313,2323232,2421113,1313234")
test( 41, "7|3241421,1111123,4124111,1132123,2412423,2211421,4232423")
test( 42, "8|13321141,32112142,14123243,14411334,34341213,44244122,24422311,12321322")
test( 43, "8|24432123,44344321,33343424,33414343,21213222,33442112,11414333,23414244")
test( 44, "8|21142332,43322422,43132342,31244421,32324313,21434442,12122111,14142324")
test( 45, "8|14122413,11431421,24321433,33141243,21242443,42141313,41142232,33441423")
test( 46, "8|12143433,23341341,13111422,41441313,32132222,23143214,43211411,41211344")
test( 47, "8|12413313,33431311,31132342,42234213,13312421,13134132,33421331,23141142")
test( 48, "9|243111132,114422314,222214113,344213133,221323134,411212133,123122242,142341144,431142421")
test( 49, "9|122124412,121431343,112332414,241124414,322144221,344142112,311442144,122322313,114334343")
You can’t perform that action at this time.