1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#! /opt/local/bin/perl
#
# four_corners_off_a_twenty.pl
#
# TASK #2 › Find Square
# Submitted by: Mohammad S Anwar
# You are given matrix of size m x n with only 1 and 0.
#
# Write a script to find the count of squares having all four corners
# set as 1.
#
# Example 1:
# Input: [ 0 1 0 1 ]
# [ 0 0 1 0 ]
# [ 1 1 0 1 ]
# [ 1 0 0 1 ]
#
# Output: 1
# Explanation:
# There is one square (3x3) in the given matrix with four corners as 1
# starts at r=1;c=2.
# [ 1 0 1 ]
# [ 0 1 0 ]
# [ 1 0 1 ]
# Example 2:
# Input: [ 1 1 0 1 ]
# [ 1 1 0 0 ]
# [ 0 1 1 1 ]
# [ 1 0 1 1 ]
#
# Output: 4
# Explanation:
# * There is one square (4x4) in the given matrix with four corners as 1
# starts at r=1;c=1.
# * There is one square (3x3) in the given matrix with four corners as 1
# starts at r=1;c=2.
# * There are two squares (2x2) in the given matrix with four corners as 1
# First starts at r=1;c=1 and second starts at r=3;c=3.
# Example 3:
# Input: [ 0 1 0 1 ]
# [ 1 0 1 0 ]
# [ 0 1 0 0 ]
# [ 1 0 0 1 ]
#
# Output: 0
# method:
# We need to methodically examine quads of points, each expressing
# the four corners of an internal square. Each square in turn can be
# expressed as a base corner closest to the origin and an edge size.
# If all four corners are 1s, then we have a match and the square is
# logged. The squares to be looked at range in size from edge length
# 2 to the shorter dimension of the enclosing matrix. Every square
# group of a given size starts with the first instance in the upper
# left corner at (0,0) and from there gets translated righwards and
# down to map all possible placements. The number of repetions in
# each direction will be the length of the matrix dimension minus
# the square edge dimension.
#
# The number of squares to be evaluated is defined by the
# sequence of the square pyrimidal numbers*, A00330 in the OEIS.
# Using the formula for generating the n-th number in the
# sequence
#
# a(n) = n*(n+1)*(2*n+1)/6
#
# As we are only considering squares of minimum edge length 2,
# the number of squares S contained within an (M x M) matrix is
#
# S = a(M-1)
#
# We walk through every point in the matrix, and if it's a 1 we can then
# check it for squares of increasing size until a dimension goes out of bounds.
# This prunes evaluation of many squares immediately.
#
#
# -----------------------------------------------------
# * OEIS A00330, Kristie Smith, Apr 16 2002
# 2020 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
our $squarecount = 0;
srand(1010);
my $r = 5 ;
my $c = 10;
my $matrix = [ map { [ map { int rand 2 == 0 ? 1 : 0 } (1..$c) ] } (1..$r) ] ;
say "@$_" for $matrix->@*;
say '';
my $cols = $matrix->[0]->@*;
my $rows = $matrix->@*;
my $min_dimension = $cols < $rows ? $cols : $rows;
my @output;
for my $c ( 0..$cols-2 ) {
for my $r ( 0..$rows-2) {
next unless $matrix->[$r][$c];
for my $size ( 2..$min_dimension ) { ## for each square size group
last if $c + $size > $cols || $r + $size > $rows;
if (four_corners($r, $c, $size, $matrix)) {
push @output, [ $r, $c, $size ];
}
}
}
}
# say "square at row $_->[0] column $_->[1] with size $_->[2]" for @output;
say "found ", scalar @output, " squares:";
for my $s ( sort { $a->[2] <=> $b->[2] } @output ) {
printf "column %d row %d from top - square of size %d \n", $s->[1]+1, $s->[0]+1, $s->[2];
}
say "\nevaluated $squarecount squares";
## ## ## ## ## SUBS:
sub four_corners {
$squarecount++;
my ($r, $c, $size, $matrix) = @_;
$size--;
## short-circuits out
return 1 if $matrix->[$r][$c] == 1
&& $matrix->[$r][$c+$size] == 1
&& $matrix->[$r+$size][$c] == 1
&& $matrix->[$r+$size][$c+$size] == 1 ;
return 0;
}
|
