If we label your samples like this:
a01 a02 a03 ... a18 b01 b02 b03 .... b18 ... f18
I would start by testing something like
a06 b06 c06 d06 e06 f06 a12 b12 c12 d12
(*edit* as mfb points out below, only two points are needed to search one set, so lets spread them out evenly)
Then, for each of the sets where we find an egg, we can then search the two each side of it on the next go, and then either side of that on the go after that, etc. Once we get a miss we stop searching in that direction.
By coincidence, that's exactly the labeling scheme I'm using.
If my goal is to "sink" the battleship by completely covering it, then this does seem like the best strategy. If I only need to know where the ends are, though, it seems like I might be able to do better with something like the following (in parallel across the A-Fs):
if A06 is a hit, then look at A03 and A09. If only one is a hit, then shift left or right appropriately for the next round (e.g. [A02 and A08] or [A04 and A10]), or if they're both hits shift outwards [A02 and A10].
I'm not sure if I'd be better off starting with A03 and A09, or maybe A02 and A10, or A04 and A10, or...
mfb wrote:I am a bit unsure how the numbers 8, 6 and 18 are connected:
A sample is the basic unit? So in a set of 18 samples, you may or may not have 8 consecutive slices with an egg - and if there are less, you don't care?
Sounds like you have the right idea, a sample is the basic unit and they come in independent sets of 18 samples. If there are fewer than 8 consecutive samples with egg, then most likely I've screwed something up and the samples are worthless to me.
Why is it impossible to have 2 eggs there?
Each series of 18 slices comes from a separate block that was sliced. I know that I only put one egg into that block, but when I do the actual slicing, I can't tell exactly where in the block the slices came from relative to the egg (there's a small, somewhat random amount that I lose off the front while getting the slicing set up).
As you have 12 disjoint possible positions for eggs, you need 20 checks to find all possible eggs: For example, you can check position 7 and 12 in each set. If both do not contain an egg, the set does not contain one.
If you want to find the position and length of each egg candidate, you will need more checks - that is a tricky because of the 10-check-rule: While you do check11+12 for possible egg candidates, you can already check for the positions of known egg candidates. I think a perfect algorithm will need a bit more knowledge: How many egg candidates (slices with eggs) belong to real eggs, and how do failed eggs look like?
Not sure what you mean by "real eggs" and "failed eggs". There aren't any false positives, if that's what you mean. As far as failed eggs, a couple ways I might have screwed up:
- The egg is too close to the start or end of the slices, e.g.: ++++-------------- or -------------+++++
- In processing the egg slices, I messed up one or more intermediate samples, e.g.: ----+++-++++------ or ---+++-+-++-------. I'll need to think really hard about my protocol, and whether or not having a single gap is acceptable, although more than 2 or 3 probably isn't.
- In processing the slices, I messed up one or more of the slices at the edge of the egg: ------+++++-------
Perhaps in the downtime I have while A6,A12,B6,B12,C6,C12,D6,D12,E6, and E12 are running, I'll code up a simulation. If I do it in a way that's not too bad, I may put up the code and see if other people can come up with better picking algorithms.