Mutagen puzzle help

[Scully]

http://underrail.info.tm/mutagens/?json=%7B%22Exitus-1%22%3A%22UB%20SZ%20RA%20IN%20BV%20G5%20R7%20OW%20OP%20KE%20JV%22%2C%22Echo-1%22%3A%22OP%20F2%20IY%20IN%20KE%20ML%20G8%20-OW%22%2C%22Echo-2%22%3A%22IR%20GN%20A1%20G5%20KE%20SZ%20OP%20-UB%22%2C%22Echo-3%22%3A%22UB%20G5%20JV%22%2C%22Echo-4%22%3A%22IN%20OP%20GN%20LH%20G8%20-R7%20-OW%20-PC%22%2C%22Helicon-1%22%3A%22SZ%20GN%20R7%20F2%20-PC%22%2C%22Helicon-2%22%3A%22KE%20R7%20G8%20IR%20A1%20RA%20-G5%22%2C%22Helicon-3%22%3A%22ML%20G8%20KE%20R7%20JV%20IR%20-IN%22%2C%22Io-1%22%3A%22R7%20SZ%20PC%20F2%20G5%20-G8%22%2C%22Io-2%22%3A%22ML%20R7%20OW%20-GN%20-A1%20-G8%22%2C%22Io-3%22%3A%22ML%20G5%20A1%20G8%20-GN%20-OP%20-JV%22%2C%22Ovid-1%22%3A%22A1%20UB%20IR%20SZ%20RA%20IN%20BV%20-F2%20-G5%22%2C%22Ovid-2%22%3A%22BV%20KE%20G8%20JV%20-OW%22%2C%22Ovid-3%22%3A%22OP%20F2%20KE%20RA%20-ML%20-JV%20-IR%22%2C%22Solis-1%22%3A%22IN%20IR%20G5%20ML%20OP%20GN%20-F2%20-SZ%22%2C%22Solis-2%22%3A%22KE%20GN%20G8%22%7D

That's the link to the tool that's supposed to help, but it can't figure anything out.

Exitus-1 sequence: UB SZ RA IN BV G5 R7 OW OP KE JV

Echo-1 sequence: OP F2 IY IN KE ML G8 -OW
Echo-2 sequence: IR GN A1 G5 KE SZ OP -UB
Echo-3 sequence: UB G5 JV
Echo-4 sequence: IN OP GN LH G8 -R7 -OW -PC
Helicon-1 sequence: SZ GN R7 F2 -PC
Helicon-2 sequence: KE R7 G8 IR A1 RA -G5
Helicon-3 sequence: ML G8 KE R7 JV IR -IN
Io-1 sequence: R7 SZ PC F2 G5 -G8
Io-2 sequence: ML R7 OW -GN -A1 -G8
Io-3 sequence: ML G5 A1 G8 -GN -OP -JV
Ovid-1 sequence: A1 UB IR SZ RA IN BV -F2 -G5
Ovid-2 sequence: BV KE G8 JV -OW
Ovid-3 sequence: OP F2 KE RA -ML -JV -IR
Solis-1 sequence: IN IR G5 ML OP GN -F2 -SZ
Solis-2 sequence: KE GN G8

Closest I got was: Echo-3, Ovid-1, Io-3, Io-2, Ovid-3, Echo-3



Also, what in tarnation is this verification bullshit?
"How old is Bilbo Baggins when he gives up the One Ring? (answer with a number):"

[hilf]

I'm pretty sure there's a typo somewhere. Please double check your mutagens starting from these:
Ovid-1
Ovid-3
Solis-1

then check every other occurrence of IR and F2, perhaps one of them misses a minus.

Puzzle you posted is unsolvable since a number of required atoms appear only in mutagens containing IR or F2 and those 2 atoms form a cycle of doom:
in order to remove F2 you need to add IR
in order to remove IR you need to add F2
so any mutagens containing IR or F2 are unusable.

[Scully]

I had already double checked before posting. Did a triple check and confirmed 100% no typos in what I've posted.

You're saying it's not actually possible to solve it right?

[hilf]

That's right, it's not possible.

Upload your save file somwhere and post in Bugs section with a link to your save.

[Qiox]

Underrail cannot generate unsolvable puzzles, unless something has gone very, very wrong. My site can have dumb moments, but since hilf also checked it over I'm leaning towards some kind of mistake here.

If you want more help, please post your save as hilf suggested. Preferably near powered mutagen scanner. I have high hopes that your puzzle is solvable.

How deep does your tool search?

The OP first posted this on Steam and I wrote a program that did a full breadth search of all sequences up to length 11 and found no solutions.

[Qiox]

With no pruning it would be: 15^11 + 15^10 + .... + 15^2 + 15 = 9,267,595,563,615

I added in just 1 check and that is to ignore using the same mutagen twice in a row, reducing the branching to 14 instead of 15 nodes.  So not quite that many, but still a lot: 14^11 + 14^10 + ... +14^2 + 15 = 4,361,070,182,715

It took 3 hours 44 minutes to run on an i7700k @ 4.8 GHZ.  No multi-threading or anything fancy.  In fact task manager showed it was only using 15% of 1 core.

Seeing there were 20 different elements to the mutagens I encoded them as bit positions in an unsigned long.  This way each mutagen is represented as 2 numbers.  Mutagen.positive has a 1 in each bit position for what it adds, while Mutagen.negative has a 1 in each position for what it removes.

Adding a mutagen to the current batch, which is also just a single unsigned long, involves just 3 bit-wise operations:

NewBatch = (Current OR Mutagen.positive) XOR (Current AND Mutagen.negative)

Now this value is just compared with the solution, which is also just an unsigned long.

[Qiox]

Oh I see what you mean.  I did not write a general purpose solver.  It is hard coded just for the puzzle given by the OP.  And I was only checking to see if adding and subtracting could give the right set of atoms.   I gave no concern for order.  Since if there is no solution when just considering the required atoms, then obviously there is also no solution that also includes the correct order.

[sthalik]

Adding a mutagen to the current batch, which is also just a single unsigned long, involves just 3 bit-wise operations:

NewBatch = (Current OR Mutagen.positive) XOR (Current AND Mutagen.negative)

Now this value is just compared with the solution, which is also just an unsigned long.

Even if you get a speedup by a factor of twenty, it's not enough. It's only the actual recursive (or backtracking) search that can improve performance. Also that seems to ignore atom order for the solution.

I wrote a working solver using bounded acyclic depth-first search, iterated several times to account for actual cycles.