27 February 2024

Challenge 216

New Kit in Town

• Task 2: Word Stickers

Task 2: Word Stickers

Submitted by: Mohammad S Anwar

---

You are given a list of word stickers and a target word.

Write a script to find out how many word stickers is needed to make up the given target word.

Example 1

Input: @stickers = ('perl','raku','python'), $word = 'peon'
Output: 2

We just need 2 stickers i.e. 'perl' and 'python'.
'pe' from 'perl' and
'on' from 'python' to get the target word.

Example 2

Input: @stickers = ('love','hate','angry'), $word = 'goat'
Output: 3

We need 3 stickers i.e. 'angry', 'love' and 'hate'.
'g' from 'angry'
'o' from 'love' and
'at' from 'hate' to get the target word.

Example 3

Input: @stickers = ('come','nation','delta'), $word = 'accommodation'
Output: 4

We just need 2 stickers of 'come' and one each of 'nation' & 'delta'.
'a' from 'delta'
'ccommo' from 2 stickers 'come'
'd' from the same sticker 'delta' and
'ation' from 'nation' to get the target word.

Example 4

Input: @stickers = ('come','country','delta'), $word = 'accommodation'
Output: 0

as there's no "i" in the inputs.

---

Preliminary Note

At the time of challenge 216 I submitted a solution to task 2 in Octave, though I had preferred a Perl solution. However, at that time I could’t find a Perl module that would solve linear programs. I chose Octave because it provides a convenient interface to the GNU Linear Programming Kit (GLPK).

Three weeks later, challenge 219 brought another task that could be formulated as a linear program. Again I chose Octave, but I asked myself why Perl does not have such a nice feature.

To fill the gap I wrote PDL::Opt::GLPK. Now here is my solution in Perl.

Solution

My comment in the Octave solution was:

Building the target from some stickers may be formulated as an integer linear programming problem.

For each letter in the target word, its quantity needs to be covered by the selected stickers. This results in one linear inequality for each unique letter in the target. The objective is to minimize the total number of stickers.

The integer restriction is crucial as “feo” might be build from 1/2 of “fee” and “foo” otherwise.

The Perl solution is very similar to its Octave counterpart, though I’ll explain it in more detail here.

We have a target word \(w\) that consists of unique letters \(l_i\) with a multiplicity of \(b_i\). Then we have some stickers, where sticker \(k\) provides \(a_{ik}\) times the letter \(l_i\). Each letter \(l_i\) has to be provided \(b_i\) times by the selected stickers in their multitude \(x_k\) The number of stickers satisfying these conditions shall be minimal.

This may be written as an integer linear program:

\[\begin{gathered} \text{minimize:} \hfill & \sum_k x_k\\ \text{subject to:} \hfill & \sum_k a_{ik} x_k & \ge b_i\\ & x_k & \ge 0\\ \end{gathered}\]

The parameters \(a_{ik}\) and \(b_i\) can be determined as follows:

• transform the word \(w\) into an ndarray of its character values
• sort these values and perform run length encoding, leading to a list of unique character values and their multiplicity. The latter are the required values \(b_i\).
• count the number of occurences of the letter \(l_i\) in the sticker \(k\) gives the matrix \((a_{ik})\)

Then we start the GLPK engine to solve the linear program. the resulting value \(\mathit{fopt}\) is the solution of this task. Furtermore we may generate a list of stickers found in the optimal solution.

Using PDL this leads to:

use PDL;
use PDL::Opt::GLPK;

sub min_stickers {
    my $target = long map ord, split //, shift;
    my $stickers = long map [map ord, split //, $_], @_;

    my ($b, $required) = $target->qsort->rle;
    my $a = ($required->dummy(0)->dummy(0) == $stickers)->sumover;
    my $c = ones($a->dim(1));

    my $xopt = null;
    my $fopt = null;
    my $status = null;

    eval {
        glpk($c, $a, $b, zeros($c), inf($c),
            GLP_LO * ones($b), GLP_IV * ones($c), GLP_MIN,
            $xopt, $fopt, $status);
        1;
    } || return ([], 0);

    ([map +($_[$_]) x $xopt->at($_), 0 .. $#_], $fopt);
}

See the full solution.