Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation

Introduction

This theme

AtCoder Beginner Contest B - Template Matching Difficulty: 828

This theme, matrix operation

It's a two-dimensional array, but using a matrix library can make operations easier. Ruby

ruby.rb


require 'matrix'

class Matrix
  # v2.Cannot be assigned in 3
  def []=(i, j, x)
    @rows[i][j]=x
  end
end

n, m = gets.split.map(&:to_i)
rows = Array.new(n + m){gets.chomp.chars.map{|c| (c == '#') ? 1 : 0}}
a = Matrix.rows(rows.shift(n))
b = Matrix.rows(rows)
(n - m + 1).times do |i|
  (n - m + 1).times do |j|
    if a.minor(i, m, j, m) == b
      puts "Yes"
      exit
    end
  end
end
puts "No"

matrix.rb


require 'matrix'

class Matrix
  # v2.Cannot be assigned in 3
  def []=(i, j, x)
    @rows[i][j]=x
  end
end

Call the matrix library with require'matrix'. In the local environment v2.7.1, it can be assigned to the matrix element, but in the AtCoder environment v2.3.3, it cannot be assigned, so a method is added. The interesting thing about ** Ruby ** is that you can do this for the standard library as well.

minor.rb


    if a.minor(i, m, j, m) == b

Submatrix is acquired by minor and matrix comparison is performed.

error.rb


(n - m).times do |i|
  (n - m).times do |j|

(n - m + 1).times do |i|
  (n - m + 1).times do |j|

When the matrix is ~~ 1 x 1, the matrix comparison does not go well, so the corresponding processing is included. ~~ (n --m) was wrong and (n --m + 1) was correct.

** Addition ** Please refer to the comment section for the 2D array version. Python

import numpy

n, m = map(int, input().split())
a = numpy.zeros([n, n], dtype=int)
b = numpy.zeros([m, m], dtype=int)
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '#':
            a[i, j] = 1
for i in range(m):
    s = input()
    for j in range(m):
        if s[j] == '#':
            b[i, j] = 1
for i in range(n - m + 1):
    for j in range(n - m + 1):
        if numpy.all(a[i: i + m, j: j + m] == b):
            print("Yes")
            exit()
print("No")

all.py


        if numpy.all(a[i: i + m, j: j + m] == b):

Numpy matrix comparison returns, for example, [[True, True], [True, True]], so I'm using the all function to check if everything is True.

Ruby (Matrix) Ruby (Array) Python (numpy)
Code length(Byte) 420 288 534
Execution time(ms) 22 10 166
memory(KB) 3196 1788 12512

Summary

Recommended Posts

Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solving with Ruby AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solve AtCoder ABC166 with python
Try matrix operation with NumPy
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve AtCoder ABC 186 with Python
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
AtCoder ABC168 A case expression solved in Ruby and Python
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
Scraping with Node, Ruby and Python
Solved AtCoder ABC 114 C-755 with Python3
AtCoder JSC2019 Qual B to solve with Ruby and Python Inverse element of arithmetic progression
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
[Python] Matrix operation
AtCoder ABC 175 Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
[Python] Giga Code 2019 D --Building a house (manipulate with numpy as a matrix !!!) [AtCoder]