TL;DR

Remember last post about Autobiographical numbers? Here we will take a look at the constraints - horribly laid out, but effective (although maybe not very efficient).

So… the constraints. I coded a few of them, let’s start from a very basic one - although pretty effective on its own terms. If you want to try the code below, you can find it in autobiographical-numbers (the code itself is in stage 1).

The code

sub constraint_basic ($status) {    # little pruning, mostly checking
  my $solution = $status->{solution};
  my %count_for;
  my %is_exact = map { $_ => 1 } 0 .. $#$solution;
  for my $i (0 .. $#$solution) {
     my $slot       = $solution->[$i];
     my @candidates = keys $slot->%*;
     die "no candidate for $i" unless @candidates;
     my $exact = @candidates == 1;
     for my $candidate (@candidates) {
        $count_for{$candidate}++;
        $is_exact{$candidate} = 0 unless $exact;
     }
  } ## end for my $i (0 .. $#$solution)
  my $changes = 0;
  for my $i (0 .. $#$solution) {
     my $amount     = $count_for{$i} // 0;
     my $slot       = $solution->[$i];
     if ($is_exact{$i}) {
        die "invalid amount if $i" unless exists $slot->{$amount};
        if (scalar keys $slot->%* > 1) { # prune
           $slot->%* = ($amount => 1);
           $changes++;
        }
     }
     else {
        for my $needed (keys $slot->%*) {
           if ($needed > $amount) {
              delete $slot->{$needed}; # this can't be fulfilled
              $changes++;
           }
        }
        die "no valid candidate for $i" unless scalar keys $slot->%*;
     }
  } ## end for my $i (0 .. $#$solution)
  return $changes;
} ## end sub constraint_basic ($status)

The first loop (lines 5 to 14) counts the number of available slots where a specific amount can appear, collecting it in hash %count_for. Additionally, it also tracks whether the specific amount appears exactly in all those slots, i.e. if it’s the only candidate remained in there.

The following loop (lines 16 to 35) does the constraints check and possibly pruning, keeping track of the number of changes on the way (so that the constraint function can signal whether pruning happened or not via return).

Every slot is checked (line 16); the amount associated is the count of possible slots where it might appear (line 17).

If the count associated to this slot is exact (i.e. it appeared as the only candidate in all slots where it was present), then we have to make an exact check. Hence we throw an exception in case this amount is not among the possibilities for this slot (line 20) or, if present, we make sure to mark it as the only possibility (lines 21 to 24, which avoid doing this operation over and over).

If the count is not exact, then $amount represents the maximum number of times that the specific value of the slot (i.e. $i) can appear overall. For this reason, we can rule out all possibilities that would require more than $amount (lines 28 to 32). After this pruning, we must have some residual candidate for the slot, otherwise this cannot be a solution (line 33).

How does it go?

I daresay that it goes pretty well - enough to solve the puzzle for the YouTube video in a bunch of milliseconds:

$ time ./run.sh 01-basic/ 10
solution => [6,2,1,0,0,0,1,0,0,0]

real	0m0.084s
user	0m0.068s
sys	0m0.008s

So long…

Curious about the whole series? Here it is:

Comments? Please comment below!

ETOOBUSY 🚀 minimal blogging for the impatient

Autobiographical numbers constraints - basic

The code

How does it go?

So long…