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.


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.


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.


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


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


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) {

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

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

    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

About Bruce Gray

user-pic "Util" on IRC and PerlMonks. Frequent speaker on Perl and Raku, but infrequent blogger.