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
153
154
155
156
157
158
159
160
161
162
|
━━━━━━━━━━━━━━━
CHALLENGE 081
Andinus
━━━━━━━━━━━━━━━
Table of Contents
─────────────────
1. Task 1 - Common Base String
.. 1. Perl
2. Task 2 - Frequency Sort
.. 1. Perl
1 Task 1 - Common Base String
═════════════════════════════
You are given 2 strings, `$A' and `$B'.
Write a script to find out common base strings in `$A' and `$B'.
A substring of a string $S is called base string if
repeated concatenation of the substring results in the
string.
1.1 Perl
────────
• Program: <file:perl/ch-1.pl>
We will break `$A' & check if any subset of `$A' join to make `$B'. To
speed up the process we only break `$A' by common divisors of both
`$A' & `$B'.
I assume that the length of `$B' is greater than `$A' in later parts
so we make sure that it's true.
┌────
│ my $A = shift @ARGV;
│ my $B = shift @ARGV;
│
│ # We assume length($B) is greater than length($A).
│ unless (length($B) > length($A)) {
│ my $tmp = $A;
│ $A = $B;
│ $B = $tmp;
│ }
└────
If the strings have different sets of characters then common base
string cannot exists so we exit early.
┌────
│ # Check if common base string is even possible.
│ my (%chars_in_A, %chars_in_B);
│ $chars_in_A{$_} = 1 foreach split //, $A;
│ $chars_in_B{$_} = 1 foreach split //, $B;
│ foreach my $char (sort keys %chars_in_A) {
│ last if exists $chars_in_B{$char} ;
│ print "No common base string.\n" and exit 0
│ }
└────
Get all the common divisors of `$A' & `$B'.
┌────
│ # Get all common divisors.
│ my %divisors_of_A = divisors(length($A));
│ my %divisors_of_B = divisors(length($B));
│ my @common_divisors;
│ foreach my $num (sort { $a <=> $b } keys %divisors_of_A) {
│ push @common_divisors, $num
│ if exists $divisors_of_B{$num};
│ }
│
│ # Returns all divisors of a number.
│ sub divisors {
│ my $n = shift @_;
│ my %divisors;
│ foreach my $i ( 1 ... $n){
│ if ($n % $i == 0) {
│ $divisors{$i} = 1;
│ }
│ }
│ return %divisors;
│ }
└────
We check if any subset of `$A' joins to make `$B'.
┌────
│ my @common;
│
│ foreach my $num (@common_divisors){
│ my $tmp;
│ my $base = substr($A, 0, $num);
│ foreach (1 ... length($B) / $num) {
│ $tmp .= $base;
│ }
│ push @common, $base if $tmp eq $B;
│ }
│
│ print "No common base string.\n" and exit 0
│ unless scalar @common;
│ print join(', ', @common), "\n";
└────
2 Task 2 - Frequency Sort
═════════════════════════
You are given file named input.
Write a script to find the frequency of all the words.
It should print the result as first column of each line should be the
frequency of the the word followed by all the words of that frequency
arranged in lexicographical order. Also sort the words in the
ascending order of frequency.
For the sake of this task, please ignore the following in the input
file: `. " ( ) , 's --'
2.1 Perl
────────
• Program: <file:perl/ch-2.pl>
Swap unwanted characters with a space.
┌────
│ my $file = path(shift @ARGV)->slurp;
│
│ $file =~ s/(--|'s)/ /g;
│ $file =~ s/[."(),]+/ /g;
│ $file =~ s/ / /g;
│ $file =~ s/\n/ /g;
└────
Get frequency of each word.
┌────
│ my %words;
│ foreach my $word (split / /, $file) {
│ $words{$word} = 1 and next unless exists $words{$word};
│ $words{$word}++;
│ }
└────
Format the output.
┌────
│ my %out;
│ foreach my $word (sort keys %words) {
│ my $freq = $words{$word};
│ push @{$out{$freq}}, $word;
│ }
│
│ foreach my $freq (sort { $a <=> $b} keys %out) {
│ print "$freq ", join(' ', @{$out{$freq}}, "\n");
│ }
└────
|
