January 2020

[what]

http://www.research.ibm.com/haifa/po...nuary2020.html

[axn]

Couple of observations.

1) The example (8 barrels) appears to be for exactly one poisonous barrel. It is not clear from the wording.
2) The wording of the problem suggests a conditional strategy is fine (i.e. Day n's pattern can be defined after observing Day n-1's outcome), but the answer format doesn't allow conditional strategy -- the pattern needs to be defined for all three days at once.

Overall, it looks like this can be solved with pen and paper in a few minutes.

EDIT:- Nevermind. The example does work for 2 barrels.

[a1call]

I am lost as usual.
Why make it so complicated?
4 Orchids x 2 Days = 8 tests
Why not test 1 barrel per plant per day?

Likewise:
4 Orchids x 3 Days = 12 tests
Why not test 1 barrel per plant per day?

What am I missing.

ETA: Never-mind, Early-deaths => reduced number of plants for testing.

[what]

Unless I misunderstood the challenge, I have found a very trivial solution. Are you allowed to check the outcome (whether its rotten or not) after each day? For example, imagine on one of the orchids I use barrel A on day 1, and barrels DG on day 2, can I check whether the plant is rotten or not right after day 1 (this will mean A is guaranteed to be one of the culprits), or do I have to wait until day 2 to check the result?
I assume you must be allowed to, as if you are not, the example they provided would not work if B and A were the culprits.

[a1call]

Even more confused with the format now.
In the example if Barrel-B is poisonous, Then it will kill plant 1 after day one. So you can't test DG on plant-1 on day-2. You could shift the test onto another surviving plant, but I am having problem formulating the parameters.

[axn]

AFAICT, You're allowed to test the status of the plants after each day, but a plant that died on any given day cannot be used for further tests on subsequent days. That's the tricky part. The given example works under these constraints. To wit, these are the death signatures for each potentital combination of 2 out of 8 barrels in the example:

AB	13.2
AC	34.2
AD	23.1
AE	3.2
AF	23.
AG	3.124
AH	3.24
BC	14.23
BD	12.
BE	1.2
BF	12.3
BG	1.24
BH	13.24
CD	24.13
CE	4.3
CF	24.3
CG	4.13
CH	34.
DE	2.1
DF	2.13
DG	2.14
DH	23.14
EF	2.3
EG	.14
EH	3.4
FG	2.134
FH	23.4
GH	3.14

Note that each combination of barrels has a unique signature. AB = 13.2 means flowers 1 & 3 dies on day one and flower 2 dies on day 2, if the poisonous barrels are A & B.

[axn]

Originally Posted by a1call

In the example if Barrel-B is poisonous, Then it will kill plant 1 after day one. So you can't test DG on plant-1 on day-2. You could shift the test onto another surviving plant, but I am having problem formulating the parameters.

No shifting of tests - otherwise puzzle will be too easy. You must specify the full sequence of tests ahead of time.

[what]

In this case, I think my solution is correct however I will check over it to confirm

[a1call]

Ok, back to one test per plant per day. I could see why that would not work 10 minutes ago but can't do so now. Early deaths would determine one death per barrel and you won't have to do further testing.
I am either getting too old or have been an idiot all along and didn't realize it before.

ETA Or both.
ETA II: Nevermind, back to my senses now.
ETA III: No, lost again:
For the example:
1st-day, one barrel per each of the 4 plants: Possibilities:
0 Deaths => test the 4 remaining barrels, one barrel per plant on day 2 => Mystery solved
1 Death => test 3 of the remaining barrels, one per surviving plant => 1 or 0 deaths => Mystery solved
2 Deaths => mystery solved no more tests required



ETA IV: The way I (mis-)see it, extension of the same one barrel test per plant would work for 2-out-of-12 barrels as well.


ETA V: Ok, so the only reason this would not work is because the solution can not be represented in the requested format, even though one barrel test per plant would be conclusive by itself, otherwise.

[axn]

A pari/gp program to validate a potential solution.

tokenize(str, delim)={
  my(v=Vec(str), ret_val=[], s="");
  for(i=1, #v, 
    if(v[i] == delim
      , ret_val = concat(ret_val, [s]); s=""
      , s=concat(s, v[i])
    )
  );
  concat(ret_val, [s])
}

signature( b1, b2, sequence, n_flowers, n_days )={
  my(still_alive=vector(n_flowers, i, 1), sig = "");
  for(i=1, n_days,
    for(j=1, n_flowers,
      barrel_list = sequence[ j ][ i ];
      if( still_alive[j] && (setsearch(barrel_list, b1) > 0 || setsearch(barrel_list, b2) > 0)
        , sig = concat(sig, Str(j)); still_alive[j] = 0;
      )
    );
    sig = concat(sig, ".")
  );
  sig
}

setify(a_str)=apply(n->Set(Vec(n)), tokenize(a_str, "."));

validate(n_barrels, n_flowers, n_days, seqstring)={
  my(i,j,k, barrels=vector(n_barrels, i, Strchr(i+64)), flowers, sequence, S=Set());
  sequence = apply(setify, tokenize(seqstring, ","));
  for(i=1, n_barrels-1, 
  for(j=i+1, n_barrels, 
    sig = signature(barrels[i], barrels[j], sequence, n_flowers, n_days);
    if( setsearch(S, sig)
      , printf("Oops, invalid. Dupe signature %s for %s%s\n", sig, barrels[i], barrels[j]); return 0
      , printf("%s%s has signature %s\n", barrels[i], barrels[j], sig); S = setunion(S, Set(sig))
    )
  )
  );
  1
}

You call it:

validate(8, 4, 2, "B.DG,DF.AB,AH.CF,C.GH")

Output looks like:

AB has signature 13.2.
AC has signature 34.2.
AD has signature 23.1.
AE has signature 3.2.
AF has signature 23..
AG has signature 3.124.
AH has signature 3.24.
BC has signature 14.23.
BD has signature 12..
BE has signature 1.2.
BF has signature 12.3.
BG has signature 1.24.
BH has signature 13.24.
CD has signature 24.13.
CE has signature 4.3.
CF has signature 24.3.
CG has signature 4.13.
CH has signature 34..
DE has signature 2.1.
DF has signature 2.13.
DG has signature 2.14.
DH has signature 23.14.
EF has signature 2.3.
EG has signature .14.
EH has signature 3.4.
FG has signature 2.134.
FH has signature 23.4.
GH has signature 3.14.
%56 = 1

[a1call]

In the 8 barrel example's solution AE & AF would have the same signature of plants 1 & 4 surviving after 2 days.
So no distinguishable advantage over one barrel per plant testing even without test shifting.
You will still need to take into account results of both days' survival results to reach a conclusive determination.

ETA: Things are different for 3 days' tests though. 1st day deaths would hamper 2 future scheduled tests on the dead plants. So it won't work without test shifting for 12 barrel scenario(in the one barrel per plant procedure).