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
|
#!/usr/bin/perl
#
# Task 2: "Find Square
#
# You are given a binary matrix of size m x n (all elements are 1 or 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
#
# My notes: clearly defined, seems straightforward.
#
# Input format: CSV rows on command line so example 3 is:
# ./ch-2.pl 0,1,0,1 1,0,1,0 0,1,0,0 1,0,0,1
#
# This is my second attempt, where I found all SQUARES inside the
# matrix (rather than all RECTANGLES, checking which were squares)
# reduces 4 nested loops to 3..
use strict;
use warnings;
use feature 'say';
use Function::Parameters;
use List::Util 'min';
use Data::Dumper;
die "Usage: count-squares list_of_csvrows\n" unless @ARGV;
my @m;
foreach my $row (@ARGV)
{
my @r = split(/,/, $row);
push @m, \@r;
}
#say Dumper(\@m);
my $rows = @m;
my $cols = @{$m[0]};
my $nsquares = 0;
foreach my $startr (0..$rows-2)
{
foreach my $startc (0..$cols-2)
{
next unless $m[$startr][$startc] == 1;
for( my $w=1; ; $w++ )
{
my $endc = $startc + $w;
last if $endc >= $cols;
my $endr = $startr + $w;
last if $endr >= $rows;
next unless $m[$startr][$endc] == 1;
next unless $m[$endr][$startc] == 1;
next unless $m[$endr][$endc] == 1;
$nsquares++;
#say "found 1-square: sr=$startr, sc=$startc, er=$endr, ec=$endc";
}
}
}
say $nsquares;
|
