RogerBW's Blog

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.