PuzzleUp 2019

[dm_litv]

Did you start with some intelligent heuristics?

I.
We assumed that the first 3 weighings are (1..4),(5..8),(9..12)

II.
Then we look at the task as at a two-person game.
Evaluation function Eval() of position - the number of possible ball permutations,
that do not contradict the results of already performed weighings.
The player A chooses move (4-ball subset), trying to minimize Eval()
on all possible moves (weighing results) of the player B.
Then we apply standard minimax search with alpha-beta pruning.

III.
Use the limitations of information theory.
 K**NMoves >= Eval()
where
 K - maximal number of outcomes during one weighing,
 NMoves - required number of moves.

A very important consideration that did not immediately come to my mind!
For first 3 weighings (from section I.)
 K = 24
After first 3 weighings
 K <=12
(because from four balls at least two belong to the same group).

If anyone is interested, here is a link to the file with the solution tree.
https://drive.google.com/open?id=1thtexe...P88NE3ezSu