TL;DR

We continue looking for more efficient ways to solve aquarium, aiming at solving the monthly mega-puzzle in matters of seconds.

In Aquarium - search the solution space we introduced a dumb, brute force approach to search the solution space. It was up to the job at that time, but now we need something a little smarter, as well as capable of leveraging the enhancements that we introduced so far in terms of pruning.

You can find the code for this post in stage 7.

Look for the best

The main insight at this point is that the choice should not be “just the next in line”, but somehow the best place to guess putting some water in.

One idea is to try out the longest horizontal streak that we find still empty. In other terms, we look for the row that contains the most cells belonging to a single aquarium. In any case - i.e. both if it’s successful or if it’s a wrong choice - we will get rid of that amount of cells, because they will be put either to water (first choice) or to empty (backtrack choice).

This approach is also quite useful to interleave with the “cooperative” constraints, because both investigation legs (i.e. the water first choice and the empty fallback) will set a streak of cells and will (hopefully) help the constraints perform more pruning.

So let’s code it!

We just need to change our moves_iterator to find out the longest available streak and compute the two alternatives (filled with water, left empty):

sub moves_iterator ($puzzle) {
  my ($n, $field, $status) = $puzzle->@{qw< n field status >};

  my ($best_row, $best_id, $best_count);
  for my $row (0 .. $n - 1) {
     my %count_for;
     for my $j (0 .. $n - 1) {
        next if $status->[$row][$j];
        $count_for{$field->[$row][$j]}++;
     }
     for my $id (sort {$a <=> $b} keys %count_for) {
        my $count = $count_for{$id};
        ($best_row, $best_id, $best_count) = ($row, $id, $count)
           if (! defined $best_row) || ($best_count < $count);
     }
  }

  my $alt_status = dclone($status);
  for my $j (0 .. $n - 1) {
     next unless $field->[$best_row][$j] == $best_id;
     $status->[$best_row][$j] = 1;
     $alt_status->[$best_row][$j] = -1;
  }

  my @retval = ($status, $alt_status);
  return sub { return shift @retval };
}

Lines 4..16 look for the longest streak, i.e. the best row and best aquarium identifier that will guarantee us putting as much water (or empty spaces) as possible in a single guess.

As anticipated, the two alternatives are pre-computed. The big time sucker here is dclone, but we would have to do it anyway to save the previous status, so it’s an invariant. Hence, the only real pre-computation overhead that we are introducing is the assignment in line 22, which should be negligible.

The iterator itself (lines 25 and 26) is quite simple: it returns $status with water at the first call, $alt_status the second, and a consistent undefined value from there on.

How does it behave?

Pretty well:

$ time ./run.sh 07-search-differently/ 15x15-hard.aqp >/dev/null && printf 'OK\n'

real	0m0.429s
user	0m0.416s
sys	0m0.008s
OK

$ time ./run.sh 07-search-differently/ daily.aqp >/dev/null && printf 'OK\n'

real	0m0.458s
user	0m0.432s
sys	0m0.016s
OK

$ time ./run.sh 07-search-differently/ weekly.aqp >/dev/null && printf 'OK\n'

real	0m7.515s
user	0m7.468s
sys	0m0.032s
OK

$ time ./run.sh 07-search-differently/ monthly.aqp >/dev/null && printf 'OK\n'

real	1m2.964s
user	1m1.764s
sys	0m0.484s
OK

So, we are the point where we are able to solve all the puzzles on the site… although there’s still space for some big improvement. Why wait one minute when we can wait one second?!?

ETOOBUSY 🚀 minimal blogging for the impatient

Aquarium - search differently

Look for the best

So let’s code it!

How does it behave?