-
Notifications
You must be signed in to change notification settings - Fork 320
/
ch-1.pl
executable file
·53 lines (46 loc) · 1.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
#!/usr/bin/env perl
#
# The Weekly Challenge - Perl & Raku
# (https://theweeklychallenge.org)
#
# Challenge 233 Task 1: Similar Words
#
# Perl solution by Matthias Muth.
#
use v5.20;
use strict;
use warnings;
use feature 'signatures';
no warnings 'experimental::signatures';
use lib '.';
use TestExtractor;
use List::Util qw( sum uniq );
sub similar_words( @words ) {
# Map each word into its alphabet word.
# A word's alphabet word consists of one of each letter contained in the
# word, ordered alphabetically.
# Thwo words are 'similar' in the sense of this challenge task if their
# alphabet words are equal.
# Get the number of 'similar' words by keeping a counter of how often
# the same alphabet word was produced.
my %alphabet_counts;
for my $word ( @words ) {
my $alphabet = join "", sort( uniq( split "", $word ) );
++$alphabet_counts{$alphabet};
}
# For getting the number of possible pairs, if n is the number of words
# that have the same alphabet, we have n ways to choose the first element
# of the pair, and (n-1) to choose the second one. As we don't want to
# count the same pair twice (also in its reversed form), we divide by two.
# Actually this corresponds to the more elaborate form of computing
# the 'n choose k' combinations, which is
# C( n, k ) = n! / k!(n-k)!
# = n! / 2(n-2)!
# = ( n (n-1) (n-2) ... 1 ) / 2 ( n-2 ... 1 )
# = n (n-1) / 2
return sum(
map $_ * ( $_ - 1 ) / 2,
values %alphabet_counts
);
}
run_tests;