Skip to content

Instantly share code, notes, and snippets.

Created April 11, 2014 15:35
Show Gist options
  • Save anonymous/a4afaa46b0672ba781d0 to your computer and use it in GitHub Desktop.
Save anonymous/a4afaa46b0672ba781d0 to your computer and use it in GitHub Desktop.
Solution to level 17 in Untrusted: http://alex.nisnevich.com/untrusted/
/***************
* pointers.js *
***************
*
* You! How are you still alive?
*
* Well, no matter. Good luck getting through this
* maze of rooms - you'll never see me or the Algorithm again!
*/
function startLevel(map) {
function shuffle(o){ //v1.0 [http://bit.ly/1l6LGQT]
for(var j, x, i = o.length; i; j = Math.floor(Math.random() * i),
x = o[--i], o[i] = o[j], o[j] = x);
return o;
};
map.createFromGrid(
['+++++++++++++++++++++++++++++++++++++++++++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+* @ o++* o++* o++* o++* o++* o++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+++++++++++++++++++++++++++++++++++++++++++++',
'+++++* o++++* o++++* o++++* o++++* o++++* o++',
'++++o *++o *++o *++o *++o *++o *+',
'+++++* o++++* o++++* o++++* o++++* o++++* o++',
'+++++++++++++++++++++++++++++++++++++++++++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+* o++* o++* o++* o++* o++* o++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+++++++++++++++++++++++++++++++++++++++++++++',
'+++++* o++++* o++++* o++++* o++++* o++++* o++',
'++++o *++o *++o *++o *++o *++o *+',
'+++++* o++++* o++++* o++++* o++++* o++++* o++',
'+++++++++++++++++++++++++++++++++++++++++++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+* o++* o++* o++* o++* o++* E o++++',
'++o *++++o *++++o *++++o *++++o *++++o *+++++',
'+++++++++++++++++++++++++++++++++++++++++++++'],
{
'@': 'player',
'E': 'exit',
'+': 'block',
'o': 'teleporter',
'*': 'trap',
}, 2, 2);
var canvas = map.getCanvasContext();
var teleportersAndTraps = map.getDynamicObjects();
teleportersAndTraps = shuffle(teleportersAndTraps);
for (i = 0; i < teleportersAndTraps.length; i+=2) {
var t1 = teleportersAndTraps[i];
var t2 = teleportersAndTraps[i+1];
// Point each teleporter to either another teleporter
// or a trap
if (t1.getType() == 'teleporter') {
t1.setTarget(t2);
}
if (t2.getType() == 'teleporter') {
t2.setTarget(t1);
}
if(i+2 >= teleportersAndTraps.length)
{
var q=map.getCanvasCoords,c=map.getCanvasContext()
var ENTRY=0, EXIT=5+4*6, ports=[],t=teleportersAndTraps;
function Line(t1,t2,s,w)
{
var a=q(t1),b=q(t2);
c.beginPath(); c.moveTo(a.x,a.y); c.lineTo(b.x,b.y);
c.strokeStyle=s; c.lineWidth=w; c.stroke();
}
function Mark(t,text,color)
{
var a=q(t)
c.font='italic 30pt Arial'
c.fillStyle=color;
c.textBaseline='middle'; c.textAlign='center'
c.fillText(text, a.x,a.y)
}
function GetGroupno(t)
{
var ygroup = Math.floor((t.getY()-3) / 4),
xgroup = Math.floor((t.getX() - (ygroup%2?5:2))/7);
return xgroup + 6*ygroup;
}
// Collect puzzle edges
for(var n=0; n<t.length; ++n)
if(t[n ].getType()=='teleporter'
&& t[n^1].getType()=='teleporter')
{
ports.push( {a:t[n], b:t[n^1], g:GetGroupno(t[n])} );
Line(t[n], t[n^1], '#222',1);
}
// Figure out which teleports are neighbors
var groups = []
for(var n=0; n<6*5; ++n) groups.push([])
for(var n=0; n<ports.length; ++n)
groups[ports[n].g].push(n)
// Solve the puzzle
var heads = [], solution = [], g = groups[ENTRY]
for(var n=0; n<g.length; ++n)
{
var new_head = {h:[], m:{}}
new_head.h.push(g[n])
new_head.m[g[n]] = true;
heads.push(new_head)
}
while(solution.length==0 && heads.length!=0)
{
var nextheads = []
// Go through each head.
// Stop when we find a head connected to EXIT.
// Add all other end's neighbors to new heads list.
for(var n=0; n<heads.length; ++n)
{
var h = heads[n];
var last = h.h[h.h.length-1], tgt = last^1;
var target_group = ports[tgt].g;
Line(ports[last].a, ports[last].b, '#021',2);
if( target_group == EXIT)
{
solution = h.h;
break;
}
for(var m=0; m<groups[target_group].length; ++m)
{
var o = groups[target_group][m]
// Have we been to "o" yet?
if(typeof h.m[o] == 'undefined')
{
var new_head = {h:[], m:{}}
for(var r=0; r<h.h.length; ++r)
{ new_head.h.push( h.h[r] );
new_head.m[ h.h[r] ] = true; }
new_head.h.push(o);
new_head.m[o]=true;
nextheads.push(new_head)
}
}
}
heads = nextheads
}
// Show the solution
for(var n=0; n<solution.length; ++n)
{
var s = solution[n];
Line( ports[s].a, ports[s].b, 'gold', 3)
Mark(ports[s].a, ""+(n+1)+"", 'white');
}
//if(solution.length==0) throw "No solution!";
}
}
}
function validateLevel(map) {
map.validateExactlyXManyObjects(1, 'exit');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment