asciilifeform: it can be made to work ( stuff all the whole piles possib into the two lumps , then solve for linear combinations of the excluded q's) but dun win anyffing
asciilifeform: but the way it goes, is to recurse along all valid paths, and mark the traversals that result in initial-state piles being successfully 'eaten'
asciilifeform: there's a strong chance this won't make sense until shown as lisp proggy.
asciilifeform: if you want optimal decomposition, you keep all valid ones and pick the shortest.
asciilifeform: one of the two attempts will turn up a valid decomposition.
asciilifeform: then attempt to permute the list into two sublists which satisfy the recurrence. if the recursion comes up empty, you slide the guess tuple forward by 1. (there is no need to do this more than once, avg of the final 2 piles cannot exceed that of the entire thing)
asciilifeform: in the case of Mocky's example, this will be initially 172,173
asciilifeform: all you gotta do is to take { floor(sum(mass) / sum(qty)) - 1 , floor(sum(mass) / sum(qty)) } as the initial guess for the split of qualities of the final 2 piles☟︎☟︎
asciilifeform: mircea_popescu : do i need to go on, or has it clicked ?
asciilifeform: in turn both of the piles that went into n1 (and likewise n2) satisfy same recurrence, n1_a * q1_a + n1_b + q1_b = n1*q1 ; n2_a * q2_a + n2_b + q2_b = n2*q2 .
asciilifeform: observe that the final 2 piles always satisfy the form n1*q1 + n2*q2 = S , where S is the sum of the masses (n_x * q_x for all x)
asciilifeform: ( any qa-qb miscible pair of piles, can be merged in either 1 ( corresponding to the inner matrices having white line on diagonal ) moves, or 2 ( corresponding to those which do not ) .
asciilifeform: the diagonal symmetry in the inner matrices. QED.
asciilifeform: i'ma leave the proof for conjecture #2 here :
asciilifeform: then mircea_popescu's proof for this is proof also for $conjecture, lol
asciilifeform: ( and as i understand it, if yer right, then my conjecture must be true )
asciilifeform: mircea_popescu: if my conjecture is troo, then you're right
asciilifeform: if can prove the |qa - qb| != 1 thing, can then use this algo.
asciilifeform: as i see it, this makes for new algo : 1) make list of immiscible piles, henceforth do not iterate with these 2) iterate through possible mixes, solving eqn for Na (for known Nb, entirety of pile B) and k exists . until you end with solely immiscible Q pairs. then stop.
asciilifeform: yea he adds portion of pile a to whole of pile b
asciilifeform: mircea_popescu: do you ? seems like Mocky's proggy doesn't
asciilifeform: nao we haven't yet the proof, but seems like we can conjecture that if |qa - qb| = 1, then piles with qa and qb are immiscible in any ratio; elsewise, yes mixable, in a ratio that can be found, i suspect, in O(1) .
