forked from manwar/perlweeklychallenge-club
/
ch-1.pl
100 lines (83 loc) · 2.6 KB
/
ch-1.pl
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
#!/opt/perl/bin/perl
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
#
# See ../README.md
#
#
# Run as: perl ch-1.pl [bsearch] < input-file
#
#
# This challenge confuses me. We're basically asked to find a number
# in a sorted list. Which in languages without hashes one would solve
# with binary search (yielding an O (log N) solution), and in languages
# with hashes you'd use a hash (yielding an O (1) (expected) time solution).
# Sure, the hash takes linear preprocessing time, but since we're asked
# to write a script, we're spending linear time reading in the data
# anyway.
#
# Perhaps the intend was a subroutine which takes a matrix and a target
# number, but that was not what is being asked. The challenge explicitly
# asks for *a script*, which means we have to spend a linear amount of
# time reading data anyway.
#
# Just to cover our bases, we'll do two implementation. Without arguments,
# we'll do that fast, hash bases, implementation. If the program is
# given the 'bsearch' argument, we will make use of a subroutine which
# takes a 2-d matrix and a target number as parameters, and which uses
# a bog standard binary search implementation to find out whether the
# target exists.
#
my $MATRIX_SIZE = 5;
my $HASH = 0;
my $BSEARCH = 1;
my $TYPE = $HASH;
$TYPE = $BSEARCH if @ARGV && $ARGV [0] eq "bsearch";
@ARGV = ();
if ($TYPE == $HASH) {
#
# Read in a matrix of data
#
my %matrix;
@matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE;
#
# Print 0/1 depending on whether the given number is in the matrix or not.
#
chomp, say exists $matrix {$_} || 0 while <>;
exit;
}
if ($TYPE == $BSEARCH) {
#
# Use binary search to find a target value into a sorted set.
#
my sub bsearch ($matrix, $target) {
my ($min, $max) = (0, $MATRIX_SIZE * $MATRIX_SIZE);
while ($min < $max) {
use integer;
my $mid = ($min + $max) / 2;
#
# To map a 1-d coordinate c to a 2-d pair x, y, we use
# x = floor (c / size), y = c % size.
#
my $cmp = $$matrix [$mid / $MATRIX_SIZE]
[$mid % $MATRIX_SIZE] <=> $target;
if ($cmp < 0) {$min = $mid + 1}
elsif ($cmp > 0) {$max = $mid}
else {return 1}
}
return (0)
}
#
# Read in the matrix
#
my $matrix = [map {[<> =~ /-?[0-9]+/g]} 1 .. $MATRIX_SIZE];
#
# Check for existence for the rest of the data
#
say bsearch ($matrix, $_) for <>;
exit;
}