/
ch-2.pl
executable file
·80 lines (77 loc) · 1.92 KB
/
ch-2.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
#!/usr/bin/env perl
# https://theweeklychallenge.org/blog/perl-weekly-challenge-260/#TASK2
#
# Task 2: Dictionary Rank
# =======================
#
# You are given a word, $word.
#
# Write a script to compute the dictionary rank of the given word.
#
## Example 1
##
## Input: $word = 'CAT'
## Output: 3
##
## All possible combinations of the letters:
## CAT, CTA, ATC, TCA, ACT, TAC
##
## Arrange them in alphabetical order:
## ACT, ATC, CAT, CTA, TAC, TCA
##
## CAT is the 3rd in the list.
## Therefore the dictionary rank of CAT is 3.
#
## Example 2
##
## Input: $word = 'GOOGLE'
## Output: 88
#
## Example 3
##
## Input: $word = 'SECRET'
## Output: 255
#
############################################################
##
## discussion
##
############################################################
#
# We first create all possible permutations, for which we use an
# iterator-based solution from Algorithm::Permute. Then we keep
# all permutations, removing duplicates (Algorithm::Permute will
# for example generate the word "GOOGLE" twice, once for each "O"
# in the first and the second of two possible positions). Then we
# just walk the sorted list, counting the index while walking, and
# returning 1+index once we found the original word.
use strict;
use warnings;
use Algorithm::Permute;
dictionary_rank('CAT');
dictionary_rank('GOOGLE');
dictionary_rank('SECRET');
sub dictionary_rank {
my $word = shift;
print "Input: '$word'\n";
my @chars = split //, $word;
my @permutations = ();
my $p_iterator = Algorithm::Permute->new ( \@chars );
my $seen = {};
while(my @perm = $p_iterator->next) {
my $w = join("", @perm);
push @permutations, $w unless $seen->{$w};
$seen->{$w} = 1;
}
my @sorted = sort @permutations;
print join(", ", @sorted) . "\n";
my $i = 0;
while($i <= $#sorted) {
if($sorted[$i] eq $word) {
$i++;
print "Output: $i\n";
last;
}
$i++;
}
}