I’ve been doing the Weekly
Challenges. The
latest
involved more finding strings that can be made out of letters, and a
search for a subsequence. (Note that this is open until 18 June 2023.)
I've been away on holiday, so I only did this in my favourite
extra languages (Rust and PostScript) rather than the usual full set.
Task 1: Good Strings
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.
Clearly I'll use word2map from challenge #216 task 2, which breaks
down a word into a hash of letters and their frequencies.
Rust benefits from the Counter class (in effect a hash with a default
value of zero):
use counter::Counter;
fn word2map(word: &str) -> Counter<char> {
let mut m: Counter<char> = Counter::new();
for c in word.to_ascii_lowercase().chars() {
if c >= 'a' && c <= 'z' {
m[&c] += 1;
}
}
m
}
fn goodstrings(words: Vec<&str>, chars: &str) -> u32 {
let mut out: u32 = 0;
Get a map of the available letters.
let cm = word2map(chars);
for w in words {
let f = word2map(w);
let mut valid = true;
For each letter in the candidate word
for c in f.keys() {
If more are needed than are available, bail out.
if f.get(c) > cm.get(c) {
valid = false;
break;
}
}
Otuerwise it's valid, so add its length to the output list.
if valid {
out += w.len() as u32;
}
}
out
}
Task 2: Arithmetic Subsequence
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 subsquence is arithmetic if ints[i + 1] - ints[i] are all the same
value (for 0 <= i < ints.length - 1).
My approach here is a depth-first search. For each sequence on the
stack (starting with the input sequence), return its length if it's a
valid arithmetic sequence; otherwise, push onto the stack a set of
sequences each consisting of this sequence with one entry removed.
(This is quick and dirty so it assumes there will be a non-trivial
arithmetic subsequence to be found.)
In Raku, I start with a test for arithmetic sequentiality:
sub isas(@a) {
my $t = @a[1] - @a[0];
for @a.skip(1).rotor(2 => -1) -> $i {
if ($i[1] - $i[0]) != $t {
return False;
}
}
return True;
}
Then the depth-first search.
sub arithmeticsubsequence(@ints) {
Put the input on the stack.
my @stack = [ @ints, ];
while (@stack.elems > 0) {
Pull a sequence off the stack.
my @t = @stack.shift.List;
If it's arithmetic, return its length.
if (isas(@t)) {
return @t.elems;
} else {
Otherwise, for each entry in it that I might remove,
for (0 .. @t.end) -> $i {
build a new sequence omitting that entry (this is surprisingly hard to
do elegantly)
my @tt;
for (0 .. @t.end) -> $ix {
if ($i != $ix) {
@tt.push(@t[$ix]);
}
}
and push it onto the stack for later testing.
@stack.push(@tt);
}
}
}
return 0;
}
This automatically gets me tests of the full sequence, full sequence
missing one entry, full missing two, etc.; it's not particularly
efficient, because it'll test subsequences multiple times, but at
least the test exits early on failure.
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.