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
|
#!/usr/bin/perl
#
# Task 2: "Lonely X
#
# You are given m x n character matrix consists of O and X only.
#
# Write a script to count the total number of X surrounded by O only. Print
# 0 if none found.
#
# Example 1:
#
# Input: [ O O X ]
# [ X O O ]
# [ X O O ]
#
# Output: 1 as there is only one X at the first row last column surrounded
# by only O.
#
# Example 2:
#
# Input: [ O O X O ]
# [ X O O O ]
# [ X O O X ]
# [ O X O O ]
#
# Output: 2
#
# a) First X found at Row 1 Col 3.
#
# b) Second X found at Row 3 Col 4.
# "
#
# My notes: interesting question, sounds simple but perhaps not quite
# as simple as it sounds. Especially (obviously) "surrounded by only O"..
# Note that I counted rows and columns from 0, not 1. So the output I
# generate for the second grid (file grid2) is:
# "2 lonely Xs in grid: [0, 2],[2, 3]"
#
use strict;
use warnings;
use feature 'say';
use Function::Parameters;
use Data::Dumper;
use List::Util qw(max);
die "Usage: lonely-x ox-filename\n" unless @ARGV==1;
my $filename = shift;
#
# my @g = readgrid($filename);
# Read the ox grid file, return @g, the grid
# (an array of array-refs).
#
fun readgrid( $filename )
{
open( my $infh, '<', $filename ) || die;
my @result;
while( <$infh> )
{
chomp;
tr/ \t[]//d;
die "readgrid: bad line '$_'\n" unless /^[OX]+$/;
my @ch = split(//);
push @result, \@ch;
}
close($infh);
return @result;
}
my @dir =
(
[-1,0], # up (delta r,c)
[-1,1], # ne
[0,1], # e
[1,1], # se
[1,0], # down
[1,-1], # sw
[0,-1], # w
[-1,-1],# nw
);
#
# my @sol = findlonelyxs( @grid );
# Given @grid, a grid (array of array refs) read by readgrid(),
# find all lonely Xs. Return an array of [R,C] pairs.
#
fun findlonelyxs( @grid )
{
my $rows = @grid;
my $cols = @{$grid[0]};
#say "debug: rows=$rows, cols=$cols";
my @result;
foreach my $r (0..$rows-1)
{
foreach my $c (0..$cols-1)
{
if( $grid[$r][$c] eq 'X' )
{
if( lonelyX( $r, $c, @grid ) )
{
#say "debug: found lonely X @ r=$r, c=$c";
push @result, [$r,$c];
}
}
}
}
return @result;
}
#
# my $islonely = lonelyX( $r, $c, @grid );
# Given that cell ($r,$c) in @grid is an X, is it a lonely one?
# Return 1 iff it is, otherwise 0.
#
fun lonelyX( $r, $c, @grid )
{
my $rows = @grid;
my $cols = @{$grid[0]};
# build the "str of adjacent cell values" in $adjstr.
my $adjstr = "";
foreach my $dir (@dir)
{
my( $dr, $dc ) = @$dir;
my $r2 = $r+$dr;
my $c2 = $c+$dc;
# have we fallen off the grid?
next if $r2<0 || $r2>=$rows || $c2<0 || $c2>=$cols;
my $ch = $grid[$r2][$c2];
#say "debug: X pos ($r,$c), adj pos ($r2,$c2) on board, is $ch";
$adjstr .= $ch;
}
#say "debug: X @ ($r,$c): adjstr: $adjstr";
# not lonely if any 'X' in $adjstr, otherwise lonely
return $adjstr =~ /X/ ? 0 : 1;
}
my @g = readgrid($filename);
#say Dumper \@g;
my @sol = findlonelyxs( @g );
my $n = @sol;
say "$n lonely Xs in grid: ", join(',',map { my($r,$c)=@$_; "[$r, $c]" } @sol);
|
