| 12 October 2026 | Challenge 025 |
Optimal Pokémons
Task 1: Head to tail Pokémon names
Generate a longest sequence of the following “English Pokemon” names where each name starts with the last letter of previous name.
audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan kricketune landorus ledyba loudred lumineon lunatone machamp magnezone mamoswine nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2 porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask
The above names borrowed from wiki page.
Solution
Preface
With this solution I’m cheating in several aspects:
- It is seven years too late.
- It’s not really a Perl solution but a wrapper around an external program.
- I used the aid of a LLM to design the solution.
I’ve never used a LLM before to help me solving a task from the Weekly Challenge and I do not intend to do so in any future current task.
Approach
The names can be viewed as vertices of a directed graph. There is an edge between two vertices if the predecessor vertex ends in the same letter as the successor starts. In this graph we need to find a longest path.
Unfortunately, the longest path problem is NP-hard, i.e. there is no known algorithm to solve it in polynomial time.
Furthermore, I was unable to find any useful hints about approaches to solve the problem or implementations thereof. Thus I asked ChatGPT about approaches and it suggested:
- Depth-first search with backtracking
- Branch-and-bound
- Integer linear programming
The latter sounded interesting and the LLM presented a formulation as an ILP.
ChatGPT:
Assume your graph is \(G=(V,E)\), with \(n = | V |\). The formulation below finds a longest simple directed path: the start and end vertices are unrestricted, and the path may contain any number of vertices.
1. Decision variables
For each vertex \(v\in V\):
-
\(x_v\in\{0,1\}\): 1 if vertex \(v\) is included in the path.
-
\(s_v\in\{0,1\}\): 1 if \(v\) is the start vertex.
-
\(t_v\in\{0,1\}\): 1 if \(v\) is the end vertex.
-
\(p_v\): the position of \(v\) in the path, if selected.
For each directed edge \((u,v)\in E\):
- \(y_{uv}\in\{0,1\}\): 1 if edge \((u,v)\) is used in the path.
Let \(p_v\) be an integer variable, or a continuous variable if you prefer — the formulation works either way.
2. Objective function
Maximize the number of selected vertices:
\[\boxed{\max \sum_{v\in V}x_v}\]A simple path containing \(k\) vertices has \(k-1\) edges, so maximizing vertices is equivalent to maximizing edges.
3. Constraints
A. Select exactly one start and one end
\[\sum_{v\in V}s_v=1\] \[\sum_{v\in V}t_v=1\]B. A selected vertex has the appropriate number of incoming and outgoing path edges
For every vertex \(v\):
\[\sum_{u:(u,v)\in E}y_{uv}=x_v-s_v\] \[\sum_{w:(v,w)\in E}y_{vw}=x_v-t_v\]These constraints mean:
-
The start has no selected incoming edge.
-
The end has no selected outgoing edge.
-
Every other selected vertex has exactly one selected incoming and one selected outgoing edge.
-
Unselected vertices have no selected path edges.
C. Link the edge variables to selected vertices
For every edge \((u,v)\in E\):
\[y_{uv}\le x_u,\qquad y_{uv}\le x_v\]D. Enforce the path order and eliminate cycles
Set \(M=n+1\). For every edge \((u,v)\in E\):
\[p_v\ge p_u+1-M(1-y_{uv})\]For every vertex \(v\in V\):
\[x_v\le p_v\le n x_v\]If edge \((u,v)\) is selected, then \(p_v\ge p_u+1\). Therefore, the positions strictly increase along every selected edge, making a directed cycle impossible.
4. Why this works
The degree constraints alone could allow a path plus one or more disconnected cycles. The position constraints rule out those cycles. Consequently, the selected vertices and edges form one simple directed path, and the objective maximizes its length.
A few practical notes:
-
Self-loops: They cannot appear in a simple path, so you can omit them from \(E\).
-
Disconnected graphs: No special handling is needed; the model chooses the best path in any component.
-
No edges: If the graph has vertices but no edges, the optimum is a single vertex.
-
Complexity: The longest simple path problem in a general directed graph is NP-hard, so a solver may take considerable time on larger or difficult instances.
This looks perfectly reasonable and comprehensible. Formulating this ILP in a form that is accepted by any solver looks challenging, though.
The LMM generated a formulation in
MathProg when I told it that I’d use GLPK.
After a few iterations and some manual tweaking, I got this problem formulation in MathProg, which obviously describes the above ILP:
longest_path.mod:
param n integer > 1;
param M := n + 1;
set V := 0..n-1;
set E within V cross V;
var x{V}, binary;
var s{V}, binary;
var t{V}, binary;
var y{E}, binary;
var p{V} >= 0, <= n;
maximize LongestPath:
sum{v in V} x[v];
# Exactly one start and one end
s.t. OneStart:
sum{v in V} s[v] = 1;
s.t. OneEnd:
sum{v in V} t[v] = 1;
# Incoming and outgoing edges
s.t. Incoming{v in V}:
sum{(u,w) in E: w = v} y[u,w] = x[v] - s[v];
s.t. Outgoing{v in V}:
sum{(u,w) in E: u = v} y[u,w] = x[v] - t[v];
# Selected edges require selected endpoints
s.t. EdgeTail{(u,v) in E}:
y[u,v] <= x[u];
s.t. EdgeHead{(u,v) in E}:
y[u,v] <= x[v];
# Position bounds
s.t. PositionLower{v in V}:
p[v] >= x[v];
s.t. PositionUpper{v in V}:
p[v] <= n * x[v];
# Eliminate directed cycles
s.t. Order{(u,v) in E}:
p[v] >= p[u] + 1 - M * (1 - y[u,v]);
end;
The corresponding data file contains the problem size and the graph’s edges:
graph.dat:
param n := 70;
set E :=
(1,35)
(2,69)
(3,13)
...
(69,26)
;
end;
Implementation
Generating the data file from the given names is simple.
Then call the GLPK solver as an external program and read its output. As there are a few hundred variables, the output is rather long.
Extracting the desired solution isn’t too hard:
- find the single variable
s[i]that has a value of1. Theniis the index of the starting vertex. - loop:
- find the single variable
y[i,j]that has a value of1. Thenjis the successor vertex ofi. - set
i = j - stop if there is no matching
y[i,j].
- find the single variable
use strict;
use warnings;
use autodie;
use constant MODEL => 'longest_path.mod';
use constant DATA => 'graph.dat';
use constant SOLUTION => 'solution.txt';
sub pokemon_names {
-f MODEL || die "model '" . MODEL . "' not found";
open my $data, '>', DATA;
printf $data "param n := %d;\n", scalar @_;
print $data "set E :=\n";
for my $v1 (0 .. $#_) {
for my $v2 (0 .. $#_) {
printf $data "(%d,%d)\n", $v1, $v2
if substr($_[$v1], -1) eq substr($_[$v2], 0, 1);
}
}
print $data ";\n";
print $data "end;\n";
close $data;
system "glpsol --model " . MODEL .
" --data " . DATA . " --output " . SOLUTION;
open my $sol, '<', SOLUTION;
my $solution = do {local $/; <$sol>};
close $sol;
$solution =~ /^ *\d+ +s\[(\d+)\] +\* +1 /m;
my $i = $1;
my @words;
push @words, $_[$i];
while ($solution =~ /^ *\d+ +y\[$i,(\d+)\] +\* +1 /m) {
$i = $1;
push @words, $_[$i];
}
@words;
}
Though this approach looks rather complex, it is indeed very fast: it runs in about 0.2 s. Here is the full output:
$ time ./ch-1.pl
GLPSOL--GLPK LP/MIP Solver 5.0
Parameter(s) specified in the command line:
--model longest_path.mod --data graph.dat --output solution.txt
Reading model section from longest_path.mod...
48 lines were read
Reading data section from graph.dat...
178 lines were read
Generating LongestPath...
Generating OneStart...
Generating OneEnd...
Generating Incoming...
Generating Outgoing...
Generating EdgeTail...
Generating EdgeHead...
Generating PositionLower...
Generating PositionUpper...
Generating Order...
Model has been successfully generated
GLPK Integer Optimizer 5.0
805 rows, 454 columns, 2332 non-zeros
384 integer variables, all of which are binary
Preprocessing...
798 rows, 452 columns, 2248 non-zeros
382 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 7.100e+01 ratio = 7.100e+01
GM: min|aij| = 3.448e-01 max|aij| = 2.900e+00 ratio = 8.411e+00
EQ: min|aij| = 1.192e-01 max|aij| = 1.000e+00 ratio = 8.389e+00
2N: min|aij| = 6.250e-02 max|aij| = 1.109e+00 ratio = 1.775e+01
Constructing initial basis...
Size of triangular part is 789
Solving LP relaxation...
GLPK Simplex Optimizer 5.0
798 rows, 452 columns, 2248 non-zeros
0: obj = -0.000000000e+00 inf = 4.000e+00 (1)
103: obj = 1.000000000e+00 inf = 0.000e+00 (0)
Perturbing LP to avoid stalling [305]...
Removing LP perturbation [594]...
* 594: obj = 2.300000000e+01 inf = 5.468e-13 (0) 3
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 594: mip = not found yet <= +inf (1; 0)
+ 687: >>>>> 2.300000000e+01 <= 2.300000000e+01 < 0.1% (9; 0)
+ 687: mip = 2.300000000e+01 <= tree is empty 0.0% (0; 17)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 1.9 Mb (1995729 bytes)
Writing MIP solution to 'solution.txt'...
Solution:
machamp petilil loudred darmanitan nosepass simisear rufflet trapinch heatmor
registeel landorus seaking girafarig gabite emboar relicanth haxorus starly
yamask kricketune exeggcute emolga audino
real 0m0.238s
user 0m0.212s
sys 0m0.025s
See the full solution to task 1.
Task 2: Chaocipher implementation
Create script to implement Chaocipher. Please checkout wiki page for more information.
We decided to put the optional API task on hold for the time being, while we are working on the format.
Solution
Reproducing my solution from 2023 here. Sadly I hadn’t supplied any comments then.
use strict;
use warnings;
use experimental 'signatures';
sub chaocipher ($plain, $cipher, $text, $decrypt) {
my @keys = ([split //, $plain],
[split //, $cipher]);
my $result;
while ($text) {
my $char = substr $text, 0, 1, '';
my $ind;
for ($ind = 0; $keys[!!$decrypt][$ind] ne $char; $ind++) {}
$result .= $keys[!$decrypt][$ind];
$keys[0] = [($keys[0]->@[$ind + 1 .. 25, 0 .. $ind])[0, 1, 3 .. 13, 2, 14 .. 25]];
$keys[1] = [($keys[1]->@[$ind .. 25, 0 .. $ind - 1])[0, 2 .. 13, 1, 14 .. 25]];
}
$result;
}
See the full solution to task 2.