Source
r/DestinyTheGameā€¢
K900_

Solving the Xenophage puzzle, with MATH

Guide

So me and my roommate nerd sniped each other into finding a generalized solution for the Xenophage puzzle, and it turns out there's some pretty cool math involved.

I might do a full writeup later if people are interested, but for now I've packaged all the math and my highly mediocre web design skills into a very simple page that you can just enter any puzzle state into, and it will tell you the solution (assuming one exists at all).

Here it is. Enjoy.

The source code is open, so if you want to look at the math yourself, or make a less shitty UI, you're more than welcome to do that.

Edit: the write-up is still happening, I'm still pretty sick so not in the headspace to do it today, but will update eventually.

Posted Aug 3, 2020, 7:05 PM UTC Ā· edited

1K99
nave_stoneā€¢

r/raidsecrets might enjoy this

146
K900_OPā€¢

Will definitely post there once I have the math writeup done. It's not particularly complicated, but I want to write it in a way that doesn't require (much) background in math to understand.

64
milfboysā€¢

You may find this post useful

It has some code, and the intro was the same! Lol

8
K900_OPā€¢

I did see it, yes. The approach we've taken is somewhat different and gives solutions faster though.

9
Froggy618157725ā€¢

I'd love to see the math. Mine was definitely not the optimal algorithm, I was more interested in just solving the general problem. So once I figured out how to find all solutions to all puzzles, I didn't bother optimizing it. I did run some brute forcing code to make sure I found all the ones

I don't see any of the math taking a quick look through the code. It looks like it's generating a giant lookup table of all solutions, unless my glances at 3am aren't doing it justice XD

I was more interested in a technique that would scale to an arbitrary sized puzzle, where taking exponential space isn't quite feasible.

3
Froggy618157725ā€¢

Hah. I was about to mention that :p

3
SpicaGenoveseā€¢

Just dropping in here to humble brag that I did those puzzles without cheats. šŸ˜¤

The final one made me die inside.

Also this is badass.

70
Terr_ā€¢

Ditto, although I'd say it was more meditative.

IIRC the real key was ensuring you made "balanced groups" of moves which would preserved certain similarity/difference patterns. For example, "all four corners", or "only the leftmost and rightmost".

That also meant if you made a mistake, you had to follow through a few more clicks to make it a consistently-applied mistake, otherwise you could spiral into a situation where it was harder to recover.

16
fallouthirteen:D: Drifter's Crewā€¢

Yeah, lights out style puzzles aren't THAT bad (I think that's what it was, been so long I forgot exactly how it worked). People really over state difficulty of those and sliding tile puzzles. Like you just get a feel for what you need to do in both those types of puzzles and you don't really have to think about it.

I actually did the Xenophage one twice. Once on my own and then again to help someone when they had to do it.

15
PunchTilItWorks:D: Drifter's Crew // You shall drift.ā€¢

The true masters trained with the ā€œMagic Squareā€ mode on a Merlin in the 70s!

6
TurquoiseLuckā€¢

sliding tile puzzles

Those are incredibly easy when you know a good method. I don't know a good method for the lights out style though.

4
SpicaGenoveseā€¢

Light's Out!! I used to have one of those! I loved that thing. If I could buy one I totally would. They looked so cool.

3
[deleted]ā€¢

[removed]

1
waddlewaddle123ā€¢

Yeah, I didn't even really know what I was doing but by the final puzzle I got it in like 30 seconds.

3
SpicaGenoveseā€¢

Oh man... I had to give the final puzzle a break. I kept going in circles as I was permutating, or hoping I was. Pretty sure I ran out of ammo and started trying things at random.

2
Terwin94:D: Drifter's Crew // No hunter vanguard no hunters for vanguardā€¢

Shooting them randomly for 10 minutes until it clicks or has an obvious solution is usually my go to.

4
SpicaGenoveseā€¢

YUP.

2
TesseonShaw Han's Burner Accountā€¢

Super cool stuff!

But I came here for maths.

40
K900_OPā€¢

The maths shall be revealed tomorrow, cause it's almost midnight here and I'm tired as hell. You can check out src/data/generate.py for now, if you understand Python.

33
RyeOhLouā€¢

Yes, I do understand Gambit and shotguns, this should be easy for me

Edit: what the fuck

15
a_persianā€¢

It's just...

for coeffs in itertools.product(*[range(4)] * len(OPS)):
    result = sum(m * c for c, m in zip(coeffs, OPS)) % 4
    k = tuple(result.reshape(9))
    solutions[k] = min(solutions[k], coeffs, key=sum)

easy!

/s

5
K900_OPā€¢

I am very sorry for inflicting this code upon the world.

6
Vague_Intentions:W:ā€¢

This is it actually:

float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F;

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;                       // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration

// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

return y;

}

Edit: Alright reddit kinda ruined the formatting.

3
RandomError86ā€¢

I'm here for the math too!

I love seeing people do stuff like this for the game. Nice work!

8
Froggy618157725ā€¢

I did a write-up on the math I did for it here. Definitely not fully rigorous, but close enough to find all solutions. Uses a bit of linear algebra, so a bit of background there might help.

2
Luigispikachuā€¢

huh. nice.

15
patchintheboxI WANT MY FACTION BACKā€¢

This would have been so useful for me 3 months ago.

11
drygsā€¢

"Destiny is just another video game"

You're mistaken

9
milfboysā€¢

I showed my mom the puzzle in the last wish with antumbra and penumbraā€”she loves etymology, so I asked her about those words and showed her some of the puzzle and she understood it and loved it!

5
SpicaGenoveseā€¢

You should have her write something up! I'd love to hear her thoughts. I've done last wish a lot, but I've only ever done add clear in the vault.

2
GHendersā€¢

I made a point to solve them by myself and made some revelations but nothing as complete as this. Good on ya

8
Wrestle_with_riceā€¢

this is some cool shit! Good work my friend.

Edit: I'm an idiot and said some fuckshit

6
thexvoidā€¢

It was literally 20-30 minutes old when you posted this comment.

6
Wrestle_with_riceā€¢

Honestly didn't even check the time posted I didn't even think about it I am indeed a fool

3
MiddleBodyInjuryā€¢

It's a hour old. What you gonna do?

1
human-7265ā€¢

???

-1
JazzyDaggerā€¢

I just helped a friend through this last night. I was using a guide that was incorrect and the nerd in me starting thinking there had to be a better way. I was a math major too so I'd love to check out a full write up if you were so inclined. Great post!

3
pinkdolphin02ā€¢

I totally forgot about this puzzle. Great solution calculator!

3
Daracaexā€¢

In case anyone needs generalized instructions, I found this a while back:

  1. Make two opposite corners match
  2. Shoot one of the two other corners not matched in step one until three corners match.
  3. Shoot the opposite corner from step 2 until all corners match.
  4. Shoot the center until it matches the corners.
  5. Now we look at the edge symbols. If an edge symbol does not match the corners and center, shoot it, the two adjacent edge symbols, and the two corners of the side of the opposite edge. Hereā€™s an example:

x x _

_ _ X

x x _

Repeat this for any edges that still do not match.

  1. Now all the symbols in the 3x3 grid should match each other. If they donā€™t match the target symbol, shoot all nine symbols once to step the entire grid through the sequence until everything matches.
3
DarthPaxsonā€¢

Step 5 isnā€™t right, for example

    1. 110.      221.     332

100 -> 211 -> 221 -> 231 -> 232 000. 100. 211. 221. 222

333 233 333

Now Iā€™m in the same boat

1
Hotman_75:T:ā€¢

Very cool job! I will share your website as much as I can. Thank you for that

1
KR0NKBERRYā€¢

holy shit dude thats really cool

1
majic911ā€¢

I would enjoy some numbers. I've basically had no numbers to do for a few months so I've resorted to making spreadsheets for wildly speculative card changes in another game, clash royale, just to see how it would change things.

But puzzle numbers are always fun.

1
K900_OPā€¢

Give me another, like, 12 hours.

1
majic911ā€¢

I believe in you. Good luck and don't forget to enjoy the numbers.

1
YaB01Keefā€¢

Im wondering how people knew the solution without knowing this?

1
K900_OPā€¢

Brute force and/or guessing.

2
Cutsdeep-FWCā€¢

it's like a rubiks cube but with different shaped changes and only one side

2
meneoā€¢

The puzzles are always in the same starting state, so some people found one solution by trial and error I guess.

1
Bee_Cerealā€¢

Please do a write-up of how you solved it! I love this kind of stuff

1
K900_OPā€¢

I will later today.

1
[deleted]ā€¢

[deleted]

1
K900_OPā€¢

Look up the Xenophage quest.

1
mrdouganā€¢

Thatā€™s really cool

1
[deleted]ā€¢

[deleted]

1
khamikeā€¢

I always upvote math. I did some matrix algebra to figure out the solutions when I was doing it but didn't bother dealing with the general case.

1