This documentation is automatically generated by online-judge-tools/verification-helper
spec/point/magic_square_spec.cr
- View this file on GitHub
- Last update: 2022-03-28 10:36:03+09:00
Depends on
src/point.cr
Code
# https://yukicoder.me/problems/no/217
require "../../src/point"
require "../../src/array/new"
require "spec"
private module MagicSquare
extend self
def generate_odd(n)
a = Array.new({n, n}, nil.as(Int32?))
k = 0
p = Point[0, n // 2]
loop do
a[p %= n] = (k += 1)
if a[p.ur % n].nil?
p.ur!
elsif a[p.down % n].nil?
p.down!
else
break
end
end
a.map &.map &.not_nil!
end
def generate_4x(n)
a = Array.new({n, n}, nil.as(Int32?))
Point.each do |p|
p2 = p % 4
if p2.x == p2.y || p2.x + p2.y == 3
a[p] = p.to_i + 1
end
end
Point.reverse_each do |p|
if a[p].nil?
a[p] = n * n - p.to_i
end
end
a.map &.map &.not_nil!
end
LUX = [
[[4, 1], [2, 3]],
[[1, 4], [2, 3]],
[[1, 4], [3, 2]],
]
def generate_4x2(n)
k = n // 4
m = k * 2 + 1
b = generate_odd(m).map &.map { |x| x.pred * 4 }
a = Array.new({n, n}, 0)
Point.each(m, m) do |p|
index = if (p.y <= k && p != Point[k, k]) || p == Point[k + 1, k]
0
elsif p.y <= k + 1
1
else
2
end
{Point.zero, Point.right, Point.down, Point.dr}.each do |d|
a[p * 2 + d] = LUX[index][d] + b[p]
end
end
a
end
def generate(n)
Point.set_range(n, n)
case n
when .odd? then generate_odd(n)
when .divisible_by?(4) then generate_4x(n)
else generate_4x2(n)
end
end
def check(n, a)
sum = n * (n * n + 1) // 2
a.size == n &&
a.all? { |b| b.size == n } &&
a.flatten.sort! == (1..n * n).to_a &&
a.all? { |b| b.sum == sum } &&
a.transpose.all? { |b| b.sum == sum }
end
end
describe Point do
it "magic square" do
(3..500).each do |n|
magic_square = MagicSquare.generate(n)
MagicSquare.check(n, magic_square).should be_true
end
end
end# https://yukicoder.me/problems/no/217
# require "../../src/point"
struct Point
include Comparable(Point)
extend Indexable(Point)
property y : Int32, x : Int32
Direction4 = [Point.up, Point.left, Point.down, Point.right]
Direction8 = Direction4 + [Point.ul, Point.ur, Point.dl, Point.dr]
class_getter! height : Int32, width : Int32
def self.set_range(height : Int, width : Int)
raise ArgumentError.new unless 0 < height && 0 < width
@@height, @@width = height, width
end
def self.reset_range
@@height, @@width = nil, nil
end
def self.size
height * width
end
def self.unsafe_fetch(index : Int)
Point.new(index // Point.width, index % Point.width)
end
def self.each(h : Int, w : Int, &block)
h.times do |y|
w.times do |x|
yield Point[y, x]
end
end
end
def self.each(y : Int, w : Int)
size.times.map { |i| Point.new(i) }
end
def initialize
@y, @x = 0, 0
end
def initialize(y : Int, x : Int)
@y, @x = y.to_i, x.to_i
end
def initialize(i : Int)
raise ArgumentError.new unless 0 <= i && i < Point.size
@y, @x = i // Point.width, i % Point.width
end
# Creates point fomr given array.
def self.from(array : Array) : self
raise ArgumentError.new unless array.size == 2
Point.new(array.unsafe_fetch(0), array.unsafe_fetch(1))
end
# Alias for `.new(y : Int, x : Int)`
def self.[](y : Int, x : Int) : self
Point.new(y, x)
end
def self.scan(scanner, io : IO) : self
Point.new(scanner.i(io), scanner.i(io))
end
{% for name, d in {
:zero => {0, 0},
:up => {-1, 0}, :down => {1, 0}, :left => {0, -1}, :right => {0, 1},
:ul => {-1, -1}, :ur => {-1, 1}, :dl => {1, -1}, :dr => {1, 1},
} %}
{% dy = d[0]; dx = d[1] %}
# Returns `Point.new({{dy}}, {{dx}})`
def self.{{name.id}}
Point.new({{dy}}, {{dx}})
end
# Returns `self + Point.new({{dy}}, {{dx}})`
def {{name.id}}
Point.new(y + {{dy}}, x + {{dx}})
end
# Adds `Point.new({{dy}}, {{dx}})`
def {{name.id}}!
@y += {{dy}}
@x += {{dx}}
self
end
{% end %}
{% for op in %w[+ - * // %] %}
def {{op.id}}(other : Point)
Point.new(y {{op.id}} other.y, x {{op.id}} other.x)
end
def {{op.id}}(other : Int)
Point.new(y {{op.id}} other, x {{op.id}} other)
end
{% end %}
# Returns `Point.new(x, y)`
def xy
Point.new(x, y)
end
# Returns `Point.new(y, x)`
def yx
self
end
def dot(other : Point)
x * other.x + y * other.y
end
def cross(other : Point)
x * other.y - y * other.x
end
# Rotates 90 degrees clockwise.
#
# x.... ..x
# ..... -> ...
# ....y ...
# ...
# y..
#
def rotate90!
@y, @x = x, Point.height - 1 - y
self
end
# :ditto:
def rotate90
dup.rotate90!
end
# Flips the grid vertically.
#
# .x.... .....y
# ...... -> ......
# .....y .x....
#
def flip_vertically!
@y, @x = Point.height - y - 1, x
self
end
# :ditto:
def flip_vertically
dup.flip_vertically!
end
# Flips the grid horizontally.
#
# .x.... ....x.
# ...... -> ......
# .....y y.....
#
def flip_horizontally!
@y, @x = y, Point.width - x - 1
self
end
# :ditto:
def flip_horizontally
dup.flip_horizontally!
end
def ==(other : Point)
x == other.x && y == other.y
end
def <=>(other : Point)
{y, x} <=> {other.y, other.x}
end
def [](i : Int)
return y if i == 0
return x if i == 1
raise IndexError.new
end
def succ
raise IndexError.new unless in_range? && self != Point.last
if x < Point.width - 1
Point.new(y, x + 1)
else
Point.new(y + 1, 0)
end
end
def pred
raise IndexError.new unless in_range? && self != Point.first
if x > 0
Point.new(y, x - 1)
else
Point.new(y - 1, Point.width - 1)
end
end
def in_range?
(0...Point.height).includes?(y) && (0...Point.width).includes?(x)
end
def to_i
raise IndexError.new unless in_range?
y * Point.width + x
end
def distance_square(other : Point)
(y - other.y) ** 2 + (x - other.x) ** 2
end
def distance(other : Point)
Math.sqrt(distance_square(other))
end
def manhattan(other : Point)
(y - other.y).abs + (x - other.x).abs
end
def chebyshev(other : Point)
Math.max((y - other.y).abs, (x - other.x).abs)
end
{% for i in [4, 8] %}
def adjacent{{i}}(&block) : Nil
Direction{{i}}.each do |d|
yield self + d
end
end
def adjacent{{i}}
Direction{{i}}.each.map { |p| self + p }
end
def adj{{i}}_in_range(&block) : Nil
Direction{{i}}.each do |d|
point = self + d
yield point if point.in_range?
end
end
def adj{{i}}_in_range
adjacent{{i}}.select(&.in_range?)
end
{% end %}
# Writes a string representation of the point to *io*.
#
# ```
# Point.new(1, 2).to_s # => "(1, 2)"
# ```
def to_s(io : IO) : Nil
io << '(' << y << ", " << x << ')'
end
# Writes a string representation of the point to *io*.
#
# ```
# Point.new(1, 2).inspect # => "(1, 2)"
# ```
def inspect(io : IO) : Nil
to_s(io)
end
# Convert `Point` into `Char` representing direction.
#
# ```
# Point.down.to_direction_char? # => 'D'
# Point.left.to_direction_char? # => 'L'
# ```
def to_direction_char?(lrud = "LRUD") : Char?
if y == 0 && x != 0
x < 0 ? lrud[0] : lrud[1]
elsif x == 0 && y != 0
y < 0 ? lrud[2] : lrud[3]
end
end
# Convert `Char` representing direction into `Point`.
#
# ```
# Point.to_direction?('R') # => Point.new(0, 1)
# ```
def self.to_direction?(c : Char, lrud = "LRUD")
raise ArgumentError.new unless lrud.size == 4
lrud.index(c).try { |i| {left, right, up, down}[i] }
end
# Convert `String` representing direction into `Point`.
#
# ```
# Point.to_direction?("DR") # => Point.new(1, 1)
# ```
def self.to_direction?(s : String, lrud = "LRUD")
case s.size
when 1
to_direction?(s[0], lrud)
when 2
p1 = to_direction?(s[0], lrud) || return nil
p2 = to_direction?(s[1], lrud) || return nil
return nil unless p1.x ^ p2.x != 0 && p1.y ^ p2.y != 0
p1 + p2
end
end
end
module Indexable(T)
private def check_index_out_of_bounds(point : Point)
check_index_out_of_bounds(point) { raise IndexError.new }
end
private def check_index_out_of_bounds(point : Point)
if 0 <= point.y < size && 0 <= point.x < unsafe_fetch(point.y).size
point
else
yield
end
end
def fetch(point : Point)
point = check_index_out_of_bounds(point) do
return yield point
end
unsafe_fetch(point.y)[point.x]
end
def [](point : Point)
fetch(point) { raise IndexError.new }
end
def []?(point : Point)
fetch(point, nil)
end
end
class Array(T)
def []=(point : Point, value)
index = check_index_out_of_bounds point
@buffer[index.y][index.x] = value
end
end
# require "../../src/array/new"
class Array(T)
def self.new(sizes : Tuple(*I), initial_value) forall I
{% begin %}
{% for i in 0...I.size %} Array.new(sizes[{{i}}]) { {% end %}
initial_value
{% for i in 0...I.size %} } {% end %}
{% end %}
end
def self.new(sizes : Tuple(*I), &block) forall I
{% begin %}
{% for i in 0...I.size %} Array.new(sizes[{{i}}]) { |index{{i}}| {% end %}
yield({% for i in 0...I.size %} index{{i}}, {% end %})
{% for i in 0...I.size %} } {% end %}
{% end %}
end
end
require "spec"
private module MagicSquare
extend self
def generate_odd(n)
a = Array.new({n, n}, nil.as(Int32?))
k = 0
p = Point[0, n // 2]
loop do
a[p %= n] = (k += 1)
if a[p.ur % n].nil?
p.ur!
elsif a[p.down % n].nil?
p.down!
else
break
end
end
a.map &.map &.not_nil!
end
def generate_4x(n)
a = Array.new({n, n}, nil.as(Int32?))
Point.each do |p|
p2 = p % 4
if p2.x == p2.y || p2.x + p2.y == 3
a[p] = p.to_i + 1
end
end
Point.reverse_each do |p|
if a[p].nil?
a[p] = n * n - p.to_i
end
end
a.map &.map &.not_nil!
end
LUX = [
[[4, 1], [2, 3]],
[[1, 4], [2, 3]],
[[1, 4], [3, 2]],
]
def generate_4x2(n)
k = n // 4
m = k * 2 + 1
b = generate_odd(m).map &.map { |x| x.pred * 4 }
a = Array.new({n, n}, 0)
Point.each(m, m) do |p|
index = if (p.y <= k && p != Point[k, k]) || p == Point[k + 1, k]
0
elsif p.y <= k + 1
1
else
2
end
{Point.zero, Point.right, Point.down, Point.dr}.each do |d|
a[p * 2 + d] = LUX[index][d] + b[p]
end
end
a
end
def generate(n)
Point.set_range(n, n)
case n
when .odd? then generate_odd(n)
when .divisible_by?(4) then generate_4x(n)
else generate_4x2(n)
end
end
def check(n, a)
sum = n * (n * n + 1) // 2
a.size == n &&
a.all? { |b| b.size == n } &&
a.flatten.sort! == (1..n * n).to_a &&
a.all? { |b| b.sum == sum } &&
a.transpose.all? { |b| b.sum == sum }
end
end
describe Point do
it "magic square" do
(3..500).each do |n|
magic_square = MagicSquare.generate(n)
MagicSquare.check(n, magic_square).should be_true
end
end
end