The Bear's Den

Enter at your own risk

Timeboxing

Task 1: Minimum Time

Submitted by: Mohammad Sajid Anwar


You are given a typewriter with lowercase english letters a to z arranged in a circle.

Typing a character takes 1 sec. You can move pointer one character clockwise or anti-clockwise.

The pointer initially points at a.

Write a script to return minimum time it takes to print the given string.

Example 1

Input: $str = "abc"
Output: 5

The pointer is at 'a' initially.
1 sec - type the letter 'a'
1 sec - move pointer clockwise to 'b'
1 sec - type the letter 'b'
1 sec - move pointer clockwise to 'c'
1 sec - type the letter 'c'

Example 2

Input: $str = "bza"
Output: 7

The pointer is at 'a' initially.
1 sec - move pointer clockwise to 'b'
1 sec - type the letter 'b'
1 sec - move pointer anti-clockwise to 'a'
1 sec - move pointer anti-clockwise to 'z'
1 sec - type the letter 'z'
1 sec - move pointer clockwise to 'a'
1 sec - type the letter 'a'

Example 3

Input: $str = "zjpc"
Output: 34

Solution

The distance \(\operatorname{dist}(x, y)\) between two characters encoded as \(x\) and \(y\) on the “character wheel” can be expressed as

\[\operatorname{dist}(x, y) = 13 - \Bigl| |y - x| - 13 \Bigr|\]

Taking into account that the initial position is at 'a' and that printing a character accounts for another second, we need to prepend an 'a' to the string and add 1 for each character printed.

Using PDL this reads as:

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use experimental 'signatures';

sub minimum_time ($str) {
    return 0 unless $str;
    my $s = PDL::Char->new("a$str")->long;
    sum 14 - abs(abs($s(1:-1) - $s(0:-2)) - 13);
}

See the full solution to task 1.

Task 2: Balls and Boxes

Submitted by: Mohammad Sajid Anwar


There are $n balls of mixed colors: red, blue or green. They are all distributed in 10 boxes labelled 0-9.

You are given a string describing the location of balls.

Write a script to find the number of boxes containing all three colors. Return 0 if none found.

Example 1

Input: $str = "G0B1R2R0B0"
Output: 1

The given string describes there are 5 balls as below:
Box 0: Green(G0), Red(R0), Blue(B0) => 3 balls
Box 1: Blue(B1) => 1 ball
Box 2: Red(R2) => 1 ball

Example 2

Input: $str = "G1R3R6B3G6B1B6R1G3"
Output: 3

The given string describes there are 9 balls as below:
Box 1: Red(R1), Blue(B1), Green(G1) => 3 balls
Box 3: Red(R3), Blue(B3), Green(G3) => 3 balls
Box 6: Red(R6), Blue(B6), Green(G6) => 3 balls

Example 3

Input: $str = "B3B2G1B3"
Output: 0

Box 1: Green(G1) => 1 ball
Box 2: Blue(B2)  => 1 ball
Box 3: Blue(B3)  => 2 balls

Solution

We split the input string at the positions between a digit and a non-digit and translate the characters 'R', 'G' and 'B' to 0, 1 and 2 resp. The result is an alternating sequence of color codes and box numbers that can easily be transformed into a \(2 \times n\)-matrix of color-box-pairs. Using these pairs as coordinates in a \(3 \times m\)-matrix that indicate the presence of a specific color in a box. Taking the logical and over the colors in each box and sum the result over all boxes produces the requested result. This procedure does not limit the boxes to numbers 0-9.

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

BEGIN {
    our %colors = (R => 0, G => 1, B => 2);

    sub balls_and_boxes {
        my $balls = long(
            map s/([RGB])/$colors{$_}/r,
            split /(?<!\d)(?=\d)|(?<=\d)(?!\d)/, shift
        )->splitdim(0, 2);
        my $boxes = zeroes 3, 1 + max $balls(1);
        $boxes->indexND($balls) .= 1;
        $boxes->andover->sum;
    }
}

See the full solution to task 2.


If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.