Why Lachrymose Head Breaks Your Brain: Directed State Space Spectral Embedding and SCCs скачать в хорошем качестве

Why Lachrymose Head Breaks Your Brain: Directed State Space Spectral Embedding and SCCs

For the purposes of studying how complicated the puzzles are in the game Stephen's Sausage Roll, I've written a sandbox program for the game in cpp with OpenGL. We can study these massive state spaces using various techniques, and importantly by choosing graph layouts that make the structure more accessible. In this video we look at strongly-connected components, the condensation graph, the in and out Laplacian layouts. The level we are mainly interested in is the very difficult puzzle 'Lachrymose Head'. This is a standalone video #puzzle #mathematics #sokoban #graphtheory #opengl #cpp Discord:   / discord   00:00:00 Lachrymose Head, introduction and optimal solution 00:00:23 State graph with the layout coming from spectral embedding 00:00:51 Zooming in on solutions 00:01:20 Showing the irredeemable states 00:01:47 More basic setup, to see different solutions, directedness and redeemability 00:04:31 Colouring non-sausage moving state changes in a single colour 00:04:50 Collapsing states that don't move a sausage together, as long as they are connected by some movements 00:05:01 Looking at a simpler example to see how collapsing bidirectional edges works 00:06:00 Spectral embedding of collapsed graph 00:06:35 Showing importance of the directedness of the graph 00:07:15 Showing why you can't just reduce to sausage states 00:08:12 Identifying nodes connected by bidirectional edges for Lachrymose head in the full spectral embedding 00:08:23 Spectral embedding for the collapsed graph 00:08:42 Showing those substates in which precisely one, precisely two, or precisely three sausages are cooked