## TWC 194: Bag Time!

In which analysis speeds, and mis-leads.

(Still editing!)

Old Mr. Kringle is soon gonna jingle
The bells that'll tingle all your troubles away
Everybody's waitin' for the man with the bag
'cause Christmas is coming again -- The Brian Setzer Orchestra

# TWC Task #1 - Digital Clock

Given time in the format `hh:mm` with one missing digit, find the highest digit `0-9` that makes it a valid time.

## Observations

Example #4 says `'2?:00'` should return `3`, which tells us that we should work with 24-hour time, and that `24:00` is not allowed as a alternate expression of `00:00 the-next-day`.

• Question mark in 4th digit place, the answer is 9.
• Question mark in 3th digit place, the answer is 5.
• Question mark in 2th digit place, the answer is 9 or 3, depending on whether the 1st digit is 0|1 or 2.
• Question mark in 1st digit place, the answer is 2 or 1, depending on whether the 2nd digit is 0..3 or 4..9.

There are only 2460=1440 possible times, but only (1060)+( 360)+(2410)+(24* 6) = 1164 possible (valid) inputs.

## Raku

``````sub is_time_valid ( Str \$s --> Bool ) {
constant \$valid_times = ( ^24 X ^60 ).map( *.fmt('%02d', ':') ).Set;
return \$s ∈ \$valid_times;
}
sub task1 ( Str \$s --> UInt ) {
return (9…0).first: { \$s.subst( '?', \$_ ).&is_time_valid };
}
``````

# TWC Task #2 - Frequency Equalizer

Given a string, determine whether removing only one character can make the frequency of the remaining characters the same.

## Observations

The test cases led many participants to shortcut the analysis and produce concise solutions that would fail one of these cases:

• 'aaaaab', 1

The count of `a` (`5`) is not within striking distance of the count of `b` (1), but because `b` is the only solo character, removing it would succeed.

• 'aaabbbcc', 0

`3` can be reduced to `2` be removing `1`, but there are two letters that each have `3`, so the frequency cannot be made equal with just one character removed.

Alternately, one of the groups has only one letter in it (`c`), and `abs(3-2) == 1`, but in the wrong direction; you would have to add a `c` to equalize.

• 'abcd', 1

Removing any of the letters leaves us with equal frequency.

### Generating test cases

Of interest to me were methods to generate minimal sets of test cases:

``````raku -e 'my @a = "a".."e"; for ( [X] (@a xx 5) ) { say .join if [le] .list and (.join ~~ /^a+[b+[c+[d+[e+]?]?]?]?\$/)}' | m
aaaaa aaaab aaabb aaabc aabbb aabbc aabcc aabcd abbbb abbbc abbcc abbcd abccc abccd abcdd abcde
``````

Longer code, but more efficient to run:

``````raku -e 'my \$w = 5; my \$f = "\%0{\$w}b"; for ^(2 ** \$w) { my @bin = .fmt(\$f).comb;
my \$c = "a";
my \$out = "a";
for @bin {
\$c++ if +\$_;
\$out ~= \$c;
}
say \$out;
}'
``````

The above is not fully minimal; it misses the nuance that `aabbc` and `aabcc` both are "two of two, and one of one". We need partitioning!

``````perl -MList::Util=zip -MInteger::Partition -wE 'my \$i = Integer::Partition->new(shift); while (my \$p = \$i->next){say map { \$_->[0] x \$_->[1] } zip [("a".."z")[keys @\$p]], \$p}' 5
aaaaa
aaaab
aaabb
aaabc
aabbc
aabcd
abcde
``````

## Raku

``````# Best compromise between performance, complexity, reducing chance to "get it wrong",
# and likelihood of a maintenance programmer to reverse-engineer the original requirements.
sub task2 ( Str \$s --> Bool ) {
my BagHash \$b = \$s.comb.BagHash;
my @k = \$b.keys;

for @k -> \$k {
\$b.remove: \$k;
return True if \$b.values.unique.elems == 0|1;
}
return False;
}
``````

## Perl

Translation of my Raku solution, with `%h` as a improvised `Bag`. The code `grep { \$_ != 0 }` is needed to adapt to the hash entry not disappearing when the value goes to `0`.

``````use v5.36;
use List::Util qw<uniq>;
sub task2 (\$s) {
my %h;
\$h{\$_}++ for split '', \$s;
my @k = keys %h;

for my \$k (@k) {
\$h{\$k}--;

my \$c = 0 + grep { \$_ != 0 } uniq values %h;

return 1 if \$c == 0
or \$c == 1;

\$h{\$k}++;
}
return 0;
}
``````

He'll make this December the one you'll remember
The best and the merriest you ever did have
Everybody's waitin', they're all congregating
Waitin' for the man with the bag -- #Voctave {A Cappella, and Breath-taking; We got to see them in concert last week!}