Pixies in the custard swamp puzzle

Question

(With thanks to Rich Bradshaw)

I'm looking for optimal strategies for the following puzzle.

As the new fairy king, it is your duty to map the kingdom's custard swamp.
The swamp is covered in an ethereal mist, with islands of custard scattered throughout.
You can send your pixies across the swamp, with instructions to fly low or high at each point.
If a pixie swoops down over a custard, it will be distracted and won't complete its sequence. Since the mist is so thick, all you know is whether a pixie got to the other side or not.

In coding terms..

bool flutter( bool[size] swoop_map );

This returns whether a pixie exited for a given sequence of swoops.

The simplest way is to pass in sequences with only one swoop. That reveals all custard islands in 'size' tries.
I'd rather something proportional to the number of custards - but have problems with sequences like:

     C......C     (that is, custards at beginning and end)

Links to other forms of this puzzle would be welcome as well.

Answer 1

This makes me think of divide and conquer. Maybe something like this (this is slightly broken pseudocode. It may have fence-post errors and the like):

retval[size] check()
{
   bool[size] retval = ALLFALSE;
   bool[size] flut1 = ALLFALSE;
   bool[size] flut2 = ALLFALSE;
   for (int i = 0; i < size/2; ++i) flut1[i] = TRUE;
   for (int i = size/2; i < size; ++i) flut2[i] = TRUE;
   if (flutter(flut1)) retval[0..size/2] = <recurse>check
   if (flutter(flut2)) retval[size/2..size] = <recurse>check
}

In plain English, it calls flutter on each half of the custard map. If any half returns false, that whole half has no custard. Otherwise, half of the half has the algorithm applied recursively. I'm not sure if it is possible to do better. However, this algorithm is kind of lame if the swamp is mostly custard.

Idea Two:

int itsize = 1
bool[size] retval = ALLFALSE;
for (int pos = 0; pos < size;)
{
    bool[size] nextval = ALLFALSE;
    for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) nextval[pos2] = true;
    bool flut = flutter(nextval)
    if (!flut || itsize == 1)
    {
        for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) retval[pos2] = flut;
        pos+=itsize;
    }
    if (flut) itsize = 1;
    if (!flut) itsize*=2;
}

In plain English, it calls flutter on each element of the custard map, one at a time. If it does not find custard, the next call will be on twice as many elements as the previous call. This is kind of like binary search, except only in one direction since it does not know how many items it is searching for. I have no idea how efficient this is.

Answer 2

Brian's first divide and conquer algorithm is optimal in the following sense: there exists a constant C such that over all swamps with n squares and at most k custards, no algorithm has a worst case that is more than C times better than Brian's. Brian's algorithm uses O(k log(n/k)) flights, which is within a constant factor the information-theoretic lower bound of log2(n choose k) >= log2((n/k)^k) = k Omega(k log(n/k)). (You need an assumption like k <= n/2 to make the last step rigorous, but at this point, we've already reached the maximum of O(n) flights.)

Why does Brian's algorithm use only O(k log(n/k)) flights? At recursion depth i, it makes at most min(2^i, k) flights. The sum for 0 <= i <= log2(k) is O(k). The sum for log2(k) < i <= log2(n) is k (log2(n) - log2(k)) = k (log2(n/k)).