## 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

## Task

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 24*60=1440 possible times, but only (10*60)+( 3*60)+(24*10)+(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 };
}
```

## Perl

# TWC Task #2 - Frequency Equalizer

## Task

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;
$b.add: $k;
}
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!}

## Leave a comment