The Bear's Den

Enter at your own risk

30 October 2026 Challenge 052

Winning Steps

Task 1: Stepping Numbers

Write a script to accept two numbers between 100 and 999. It should then print all Stepping Numbers between them.

A number is called a stepping number if the adjacent digits have a difference of 1. For example, 456 is a stepping number but 129 is not.

Solution

Stepping Numbers in the range 100..999 can easily be constructed:

Starting with the numbers 111, 222, ..., 999, we may add -12, -10, 10 or 12 to find a Stepping Number. Not all of the generated numbers are valid: the leading digit must not change.

Generate all candidates from the cross product of the two number sets and restrict these according to their validity and the given range.

use strict;
use warnings;
use experimental 'signatures';

use Math::Prime::Util 'forsetproduct';
use List::Gather;

sub stepping_numbers ($low, $high) {
    state $f = [1..9];
    state $step = [-12, -10, 10, 12];
    gather {
        forsetproduct {
            my $b = 111 * $_[0];
            my $n =  $b + $_[1];
            return if $n >= ($_[0] + 1) * 100;
            return if $n < $_[0] * 100;
            take $n if $low <= $n && $n <= $high;
        } $f, $step;
    };
}

See the full solution to task 1.

Task 2: Lucky Winner

Suppose there are following coins arranged on a table in a line in random order.

£1, 50p, 1p, 10p, 5p, 20p, £2, 2p

Suppose you are playing against the computer. Player can only pick one coin at a time from either ends. Find out the lucky winner, who has the larger amounts in total? —

Solution

There is a short and a long answer to the question.

Short:
£2 is more than all other coins together. The player who gets it, is the winner. The player who brings it to an outer position, is the loser.

Therefore both players have to pick from the head until player two is forced to remove a coin on either side of the £2, losing the game.

Long:
The long answer consists in actually writing a program to play against the computer.

There is a difficulty with this approach: We need a program to play against.

In step one, following a Minimax approach:
Player one selects the move with the maximum gain over all of player two’s moves. This requires player two to select the move that minimizes player one’s gain. This is a recursive approach that analyses a complete game.

While finding the best move for player two, it automatically finds the best moves for player one, too. In fact, there is no need for another program.

But I like to find an approach that is less expensive and proceed to step two.

After player one made the first move, both free ends are at positions that are either both even or both odd. Player one may enforce the moves of player two to be all from even positions or all from odd positions just by following every move of player two.

Considering the sum of all items at even positions and the sum of all items at odd position, player one may ensure not to lose the game by making the right first move. In most cases, player one will win the game. The only exception is a game with an even sum over all items, that is distributable over two equal sized sets and these sets being located at the even resp, odd position. In this case the strategy ends in a tie.

Though this may lead to a final sum that is not the possible maximum, it is a very simple way to ensure not to lose the game.

use v5.26;
use warnings;
use experimental 'signatures';

# returns a minimax path and the result:
# - path:
#   H, h for accessing the head
#   T, t for accessing the tail
#   upper case for player one, lower case for player two
# - result:
#   this is the guaranteed gain for player one
#
sub find_best {
    my $head = $_[0];
    my $tail = $_[-1];

    return ('t', 0) if @_ == 1;
    return $head >= $tail ? ('Ht', $head) : ('Tt', $tail) if @_ == 2;

    my ($hpath, $hsum) = __SUB__->(@_[1 .. $#_]);
    my ($tpath, $tsum) = __SUB__->(@_[0 .. $#_ - 1]);

    # player 2 (odd) minimizes, player 1 (even) maximizes
    @_ % 2 ? $hsum >= $tsum                 ? ('t' . $tpath, $tsum) :
                                              ('h' . $hpath, $hsum) :
             $hsum + $head >= $tsum + $tail ? ('H' . $hpath, $hsum + $head) :
                                              ('T' . $tpath, $tsum + $tail);
}

# Find the best next move: head -> 0, tail -> 1
sub next_step {
    my ($path) = find_best(@_);
    $path =~ /^(?:(h)|(t))/i;
    $1 ? 0 : 1;
}

# Play a simple game against a perfect machine:
# pick all even or all odd items
sub play {
    state $ht = [qw(head tail)];
    say("Cannot be player two"), return if @_ % 2;
    my $total = 0;
    my @sum;
    $sum[$_ % 2] += $_[$_] for 0 .. $#_;
    my $target = $sum[0] <= $sum[1];
    say +(qw(Even Odd))[$target], " positions chosen.";
    while (@_) {
        my $self = splice @_, -$target, 1;
        $total += $self;
        say "player one: $ht->[$target] $self";
        # against the machine:
        $target = next_step(@_);
        my $other = splice @_, -$target, 1;
        say "player two: $ht->[$target] $other";
    }
    say "total: $total";
}

A solution to this task:

$ perl/ch-2.pl 1 .5 .01 .1 .05 .2 2 .02 
Full game analysis: HhHhHtTt 3.06
Playing:
Even positions chosen.
player one: head 1
player two: head .5
player one: head .01
player two: head .1
player one: head .05
player two: tail .02
player one: tail 2
player two: tail .2
total: 3.06

To see that the simple algorithm may miss the possible maximum, we move the 50p to the end:

$ perl/ch-2.pl 1 .01 .1 .05 .2 2 .02 .5
Full game analysis: HtHhHtTt 3.06
Playing:
Odd positions chosen.
player one: tail .5
player two: head 1
player one: head .01
player two: head .1
player one: head .05
player two: tail .02
player one: tail 2
player two: tail .2
total: 2.56

Here it is possible to gain £3.06, too. Player one got only £2.56, but won the game.

I’m not going to refine the algorithm to gain more.

See the full solution to task 2.