Merge pull request #8068 from simongreen-net/master

Simon's solution to challenge 216

6 files changed, 206 insertions, 2 deletions

diff --git a/challenge-216/sgreen/README.md b/challenge-216/sgreen/README.md
index fe4eee3265..1dceb6430a 100644
--- a/challenge-216/sgreen/README.md
+++ b/challenge-216/sgreen/README.md
@@ -1,3 +1,3 @@
-# The Weekly Challenge 215
+# The Weekly Challenge 216
 
-Blog: [Weekly Challenge 215](https://dev.to/simongreennet/weekly-challenge-215-k0b)
+Blog: [Letter frequency](https://dev.to/simongreennet/letter-frequency-338m)
diff --git a/challenge-216/sgreen/blog.txt b/challenge-216/sgreen/blog.txt
new file mode 100644
index 0000000000..bc4fbeb92f
--- /dev/null
+++ b/challenge-216/sgreen/blog.txt
@@ -0,0 +1 @@
+https://dev.to/simongreennet/letter-frequency-338m
\ No newline at end of file
diff --git a/challenge-216/sgreen/perl/ch-1.pl b/challenge-216/sgreen/perl/ch-1.pl
new file mode 100755
index 0000000000..7755b93693
--- /dev/null
+++ b/challenge-216/sgreen/perl/ch-1.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature 'say';
+use experimental 'signatures';
+
+sub get_frequency ($word) {
+    # Return a dict with the frequency of each letter
+    my %freq = ();
+    foreach my $letter ( split //, uc $word ) {
+        if ( 'A' le $letter and $letter le 'Z' ) {
+            ++$freq{$letter};
+        }
+    }
+
+    return %freq;
+}
+
+sub main (@words) {
+    # The last value is the plate we are matching
+    my $plate      = pop(@words);
+    my %plate_freq = get_frequency($plate);
+    my @solution   = ();
+
+  W: foreach my $word (@words) {
+        # Calculate the frequency of letters in the current word
+        my %word_freq = get_frequency($word);
+        foreach my $letter ( keys %plate_freq ) {
+            # Check that letters in the plate appear in the word
+            if ( not exists( $word_freq{$letter} )
+                or $plate_freq{$letter} > $word_freq{$letter} )
+            {
+                next W;
+            }
+        }
+
+        push @solution, $word;
+    }
+
+    say join ', ', @solution;
+}
+
+main(@ARGV);
\ No newline at end of file
diff --git a/challenge-216/sgreen/perl/ch-2.pl b/challenge-216/sgreen/perl/ch-2.pl
new file mode 100755
index 0000000000..2f44699f38
--- /dev/null
+++ b/challenge-216/sgreen/perl/ch-2.pl
@@ -0,0 +1,66 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature 'say';
+use experimental 'signatures';
+
+use Algorithm::Combinatorics qw(variations_with_repetition);
+use List::Util               qw(any max sum);
+
+sub get_frequency ($word) {
+    my %freq = ();
+    foreach my $letter ( split //, $word ) {
+        if ( 'a' le $letter and $letter le 'z' ) {
+            ++$freq{$letter};
+        }
+    }
+
+    return %freq;
+}
+
+sub main (@words) {
+    # The last value is the word we are matching
+    my $target_word = pop(@words);
+    my %target_freq = get_frequency($target_word);
+
+    # Lets check that a solution is possible
+    my $all_letters = join( '', @words );
+    if ( any { index( $all_letters, $_ ) == -1 } split( //, $target_word ) ) {
+        # The letter doesn't exist in the words, so no solution is possible
+        say 0;
+        return;
+    }
+
+    # What is the highest frequency
+    my $highest      = max( values(%target_freq) );
+    my $word_count   = scalar(@words);
+    my $min_stickers = 'Inf';
+
+    my $iter = variations_with_repetition( [ 0 .. $highest ], $word_count );
+  W: while ( my $freq = $iter->next() ) {
+        # This solution won't be better, so skip it
+        next if sum(@$freq) >= $min_stickers;
+
+        # Combine all the words with the defined frequency
+        my $sticker_letters =
+          join( '', map { $words[$_] x $freq->[$_] } ( 0 .. $#words ) );
+        my %sticker_freq = get_frequency($sticker_letters);
+
+        foreach my $letter ( keys %target_freq ) {
+            if ( not exists $sticker_freq{$letter}
+                or $sticker_freq{$letter} < $target_freq{$letter} )
+            {
+                # Either a letter is missing, or doesn't occur enough times
+                next W;
+            }
+        }
+
+        # We have a new solution with fewer letters
+        $min_stickers = sum(@$freq);
+    }
+
+    say $min_stickers;
+}
+
+main(@ARGV);
\ No newline at end of file
diff --git a/challenge-216/sgreen/python/ch-1.py b/challenge-216/sgreen/python/ch-1.py
new file mode 100755
index 0000000000..649ebed4be
--- /dev/null
+++ b/challenge-216/sgreen/python/ch-1.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python3
+
+import sys
+
+
+def get_frequency(word):
+    '''Return a dict with the frequency of each letter'''
+    freq = {}
+    for letter in word.upper():
+        if 'A' <= letter <= 'Z':
+            freq[letter] = freq.get(letter, 0) + 1
+
+    return freq
+
+
+def main(words):
+    # The last value is the plate we are matching
+    plate = words.pop()
+    plate_freq = get_frequency(plate)
+    solution = []
+
+    for word in words:
+        # Calculate the frequency of letters in the current word
+        word_freq = get_frequency(word)
+        for letter, cnt in plate_freq.items():
+            # Check that letters in the plate appear in the word
+            if letter not in word_freq or cnt > word_freq[letter]:
+                break
+        else:
+            solution.append(word)
+
+    print(*solution, sep=', ')
+
+
+if __name__ == '__main__':
+    main(sys.argv[1:])
diff --git a/challenge-216/sgreen/python/ch-2.py b/challenge-216/sgreen/python/ch-2.py
new file mode 100755
index 0000000000..62544df0a8
--- /dev/null
+++ b/challenge-216/sgreen/python/ch-2.py
@@ -0,0 +1,57 @@
+#!/usr/bin/env python3
+
+import itertools
+import math
+import sys
+
+
+def get_frequency(word):
+    freq = {}
+    for letter in word:
+        if 'a' <= letter <= 'z':
+            freq[letter] = freq.get(letter, 0) + 1
+
+    return freq
+
+
+def main(words):
+    # The last value is the word we are matching
+    target_word = words.pop()
+    target_freq = get_frequency(target_word)
+
+    # Lets check that a solution is possible
+    combined = ''.join(words)
+    for letter in target_freq:
+        if letter not in combined:
+            # The letter doesn't exist in the words, so no solution is possible
+            print(0)
+            return
+
+    # What is the highest frequency
+    highest = max(target_freq.values())
+    word_count = len(words)
+    min_stickers = math.inf
+
+    for freq in itertools.product(range(highest+1), repeat=word_count):
+        if sum(freq) >= min_stickers:
+            # This solution won't be better, so skip it
+            continue
+
+        # Combine all the words with the defined frequency
+        sticker_letters = ''.join([words[x] * freq[x]
+                                  for x in range(word_count)])
+        sticker_freq = get_frequency(sticker_letters)
+
+        for letter in target_freq:
+            if letter not in sticker_freq or sticker_freq[letter] < target_freq[letter]:
+                # Either a letter is missing, or doesn't occur enough times
+                break
+        else:
+            # We have a new solution with fewer letters
+            min_stickers = sum(freq)
+
+    print(min_stickers)
+
+
+if __name__ == '__main__':
+    main(sys.argv[1:])