# transition:      -up-       -down-   -up-      -down-   -up-        -down-
# state:     0 0 0 0 1 1 1 1 1 1 0  0  0  1 1 1 1 1 0  0  0  1 1 1 1 1 1 0  0
my $input = "1-2-3-4-X-X-X-X-X-X-11-12-13-X-X-X-X-X-19-20-21-X-X-X-X-X-X-28-29";
my $output = part2($input);
print "$output\n";

sub part2 {
  my($input) = @_;
  my $state = 1;
  my @replace = ("A", "B");
  my $replace_index = 0;  # start at 'A'

  $input =~ s{
    ( \d+ | X ) (?# match a number or X)
    (?= - | \z) (?# followed by '-' or end of string)
  }{
    # capture the old state, to detect transitions
    my $prev_state = $state;

    # decide the new state
    $state = ($1 eq 'X') ? 1 : 0;

    if ($state == 0) {
      # state 0: return the replacement character
      $replace[$replace_index];
    } else {
      # state 1: did we transition?
      if ($prev_state == 0) {
        # flip the replacement character between 'A' and 'B'
        $replace_index = 1 - $replace_index;
      }
      # return the matched value, ie don't change anything
      $1;
    }
  }exg;
  return $input;
}