[ABC357 C] Sierpinski carpet

https://atcoder.jp/contests/abc357/tasks/abc357_c

シェルピンスキーのカーペットをテキストとして書く問題。

アルゴリズム

ルービックキューブのような 9 個のセルで構成する面をイメージした上で、

1. 9 個のセルを順に走査する
2. 中央のセルだけ塗り潰す
3. それ以外のセルには再度 (1) から適用する

グラフィック版との違い

• 描画する領域を 3**N x 3**N で用意する
• rectangle は、その領域に対して書き込む

あとはほぼ同じコードになる。

実装 (AC)

141 ms

class SierpinskiCarpet
  EDGE = 3

  def initialize(n)
    @n = n
    @field = Array.new(EDGE**@n) { Array.new(EDGE**@n) }
  end

  def call
    draw(0, 0, EDGE**@n, @n)
  end

  def draw(x0, y0, size, depth)
    if depth <= 0
      return
    end
    size /= EDGE
    EDGE.times do |y|
      EDGE.times do |x|
        x1 = x0 + x * size
        y1 = y0 + y * size
        if x == EDGE / 2 && y == EDGE / 2
          rectangle(x1, y1, size)
          next
        end
        draw(x1, y1, size, depth - 1)
      end
    end
  end

  def to_s
    @field.collect { |row|
      row.collect { |cell| cell ? "." : "#" }.join
    }.join("\n")
  end

  private

  def rectangle(x0, y0, size)
    size.times do |y|
      size.times do |x|
        @field[y0 + y][x0 + x] = true
      end
    end
  end
end

N = gets.to_i  # => 3
puts SierpinskiCarpet.new(N).tap(&:call)
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > ###...######...######...###
# > #.#...#.##.#...#.##.#...#.#
# > ###...######...######...###
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > #########.........#########
# > #.##.##.#.........#.##.##.#
# > #########.........#########
# > ###...###.........###...###
# > #.#...#.#.........#.#...#.#
# > ###...###.........###...###
# > #########.........#########
# > #.##.##.#.........#.##.##.#
# > #########.........#########
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > ###...######...######...###
# > #.#...#.##.#...#.##.#...#.#
# > ###...######...######...###
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################

関連

https://zenn.dev/megeton/articles/456a4f014bfb5b