Merge pull request #8235 from voegelas/challenge-221

Challenge 221 by Andreas Vögele

5 files changed, 161 insertions, 0 deletions

diff --git a/challenge-221/andreas-voegele/README b/challenge-221/andreas-voegele/README
new file mode 100644
index 0000000000..da9f91b22a
--- /dev/null
+++ b/challenge-221/andreas-voegele/README
@@ -0,0 +1 @@
+Solutions by Andreas Vögele.
diff --git a/challenge-221/andreas-voegele/kotlin/ch-1.kts b/challenge-221/andreas-voegele/kotlin/ch-1.kts
new file mode 100755
index 0000000000..2b41679315
--- /dev/null
+++ b/challenge-221/andreas-voegele/kotlin/ch-1.kts
@@ -0,0 +1,25 @@
+#!/usr/bin/env kotlin
+
+/*
+ * You are given a list of @words and a string $chars.  A string is good if it
+ * can be formed by characters from $chars, each character can be used only
+ * once.  Write a script to return the sum of lengths of all good strings in
+ * words.
+ */
+
+typealias CharFrequency = Map<Char, Int>
+
+fun String.toCharFrequency() = this.toList().groupingBy { it }.eachCount()
+
+fun CharFrequency.isSubset(superset: CharFrequency) =
+    this.all { (char, count) -> count <= superset.getOrDefault(char, 0) }
+
+fun goodStrings(chars: String, words: List<String>): List<String> {
+    val validChars = chars.toCharFrequency()
+    return words.filter { it.toCharFrequency().isSubset(validChars) }
+}
+
+fun sumOfLengths(words: List<String>) = words.map { it.count() }.sum()
+
+println(sumOfLengths(goodStrings("atach", listOf("cat", "bt", "hat", "tree"))))
+println(sumOfLengths(goodStrings("welldonehopper", listOf("hello", "world", "challenge"))))
diff --git a/challenge-221/andreas-voegele/kotlin/ch-2.kts b/challenge-221/andreas-voegele/kotlin/ch-2.kts
new file mode 100755
index 0000000000..04f42e7cd6
--- /dev/null
+++ b/challenge-221/andreas-voegele/kotlin/ch-2.kts
@@ -0,0 +1,46 @@
+#!/usr/bin/env kotlin
+
+/*
+ * You are given an array of integers, @ints.  Write a script to find the
+ * length of the longest Arithmetic Subsequence in the given array.  A
+ * subsequence is an array that can be derived from another array by deleting
+ * some or none elements without changing the order of the remaining elements.
+ * A subsequence is arithmetic if ints[i + 1] - ints[i] are all the same value
+ * (for 0 <= i < ints.length - 1).
+ */
+
+typealias Ints = List<Int>
+
+fun nextNumbers(acc: MutableList<Int>, distance: Int, ints: Ints): Ints {
+    var a = acc.last()
+    for (b in ints) {
+        if (Math.abs(a - b) == distance) {
+            acc.add(b);
+            a = b
+        }
+    }
+    return acc
+}
+
+tailrec fun subsequences(acc: MutableList<Ints>, ints: Ints): List<Ints> {
+    if (ints.size >= 2) {
+        val a = ints.first()
+        val tail = ints.drop(1)
+        tail.forEachIndexed({ i, b ->
+            val distance = Math.abs(a - b)
+            acc.add(nextNumbers(mutableListOf(a, b), distance, tail.drop(i + 1)))
+        })
+        return subsequences(acc, tail)
+    }
+    return acc
+}
+
+fun arithmeticSubsequences(ints: Ints): List<Ints> =
+    subsequences(mutableListOf<Ints>(), ints)
+
+fun longestLength(sequences: List<Ints>): Int =
+    sequences.reduce { a, b -> if (a.size > b.size) a else b }.size
+
+println(longestLength(arithmeticSubsequences(listOf(9, 4, 7, 2, 10))))
+println(longestLength(arithmeticSubsequences(listOf(3, 6, 9, 12))))
+println(longestLength(arithmeticSubsequences(listOf(20, 1, 15, 3, 10, 5, 8))))
diff --git a/challenge-221/andreas-voegele/perl/ch-1.pl b/challenge-221/andreas-voegele/perl/ch-1.pl
new file mode 100755
index 0000000000..af7efd88ae
--- /dev/null
+++ b/challenge-221/andreas-voegele/perl/ch-1.pl
@@ -0,0 +1,38 @@
+#!/usr/bin/perl
+
+# You are given a list of @words and a string $chars.  A string is good if it
+# can be formed by characters from $chars, each character can be used only
+# once.  Write a script to return the sum of lengths of all good strings in
+# words.
+
+use 5.036;
+use utf8;
+
+use List::Util qw(sum0);
+
+sub to_char_frequency ($string) {
+    my %frequency_of;
+    for my $char (split //, $string) {
+        ++$frequency_of{$char};
+    }
+    return \%frequency_of;
+}
+
+sub is_subset ($subset, $superset) {
+    while (my ($char, $count) = each %{$subset}) {
+        return 0 if $count > ($superset->{$char} // 0);
+    }
+    return 1;
+}
+
+sub good_strings ($chars, @words) {
+    my $valid_chars = to_char_frequency($chars);
+    return grep { is_subset(to_char_frequency($_), $valid_chars) } @words;
+}
+
+sub sum_of_lengths (@words) {
+    return sum0 map {length} @words;
+}
+
+say sum_of_lengths(good_strings('atach',          qw(cat bt hat tree)));
+say sum_of_lengths(good_strings('welldonehopper', qw(hello world challenge)));
diff --git a/challenge-221/andreas-voegele/perl/ch-2.pl b/challenge-221/andreas-voegele/perl/ch-2.pl
new file mode 100755
index 0000000000..dfe7299d77
--- /dev/null
+++ b/challenge-221/andreas-voegele/perl/ch-2.pl
@@ -0,0 +1,51 @@
+#!/usr/bin/perl
+
+# You are given an array of integers, @ints.  Write a script to find the
+# length of the longest Arithmetic Subsequence in the given array.  A
+# subsequence is an array that can be derived from another array by deleting
+# some or none elements without changing the order of the remaining elements.
+# A subsequence is arithmetic if ints[i + 1] - ints[i] are all the same value
+# (for 0 <= i < ints.length - 1).
+
+use 5.036;
+use utf8;
+
+use List::Util qw(reduce);
+
+sub next_numbers ($acc, $distance, @ints) {
+    my $a = $acc->[-1];
+    while (@ints > 0) {
+        my $b = shift @ints;
+        if (abs $a - $b == $distance) {
+            push @{$acc}, $b;
+            $a = $b;
+        }
+    }
+    return $acc;
+}
+
+sub subsequences ($acc, @ints) {
+    if (@ints >= 2) {
+        my $a = shift @ints;
+        subsequences($acc, @ints);
+        while (@ints > 0) {
+            my $b = shift @ints;
+            my $distance = abs $a - $b;
+            push @{$acc}, next_numbers([$a, $b], $distance, @ints);
+        }
+    }
+    return $acc;
+}
+
+sub arithmetic_subsequences (@ints) {
+    return @{subsequences([], @ints)};
+}
+
+sub longest_length (@sequences) {
+    my $longest_sequence = reduce { @{$a} > @{$b} ? $a : $b } @sequences;
+    return scalar @{$longest_sequence};
+}
+
+say longest_length(arithmetic_subsequences(9, 4, 7, 2, 10));
+say longest_length(arithmetic_subsequences(3, 6, 9, 12));
+say longest_length(arithmetic_subsequences(20, 1, 15, 3, 10, 5, 8));