05-02-18, 22:30 | #1 |
Member
Joined: Apr 2010
Posts: 998
|
Lost Library: Snake problem vs. Linear algebra
I've always wanted to write this.
In Lost Library, the snake problem: Well, the solution is to solve linear equations in GF(2). GF(2) denotes "finite field", or "galois field" with 2 elements. It's simple. It's just 2 operations defined on 2-element set {0,1}. (1) Addition: 0+0 = 1+1 = 0, 0+1 = 1+0 = 1. (2) Multiplication: 0*0 = 0*1 = 1*0 = 0, 1*1 = 1. The difference between these and traditional operations is only 1+1=0. This is because pulling the same lever twice equals to zero. The following needs the definition of matrix multiplication, so I put them all in one image. Remember: they're matrices in GF(2), so the addition between elements should obey 1+1=0. That's it. Last edited by xtimz; 05-02-18 at 22:58. |
05-02-18, 22:38 | #2 | |
Member
Joined: Apr 2010
Posts: 998
|
In case the image is lost (as before), you can run the following Latex code to see the 2nd image.
Quote:
|
|
06-02-18, 00:16 | #3 |
The Inscrutable One
Joined: Apr 2006
Posts: 9,513
|
Well done
There has been quite a number of very clever mathematical members on here over the years, who have analysed Tomb Raider puzzles using programs and complex maths. But for most of us, me included, we are totally lost on the mathematics of it all. I have trouble just filling in my tax return form each year |
07-02-18, 04:38 | #4 |
Member
Joined: Apr 2010
Posts: 998
|
^ I got an easy explanation by discussions with other people.
To write easier, I'll use A' to denote the inverse of A, which was A^{-1} in the picture. From the meaning of the matrix and the inverse matrix, (1) the ith column of A is: which flame is lighted when only the ith lever is pulled. (2) the ith column of A' is: which lever is pulled when only the ith flame is lighted. So, if we want a given set of flames to be lighted, we just need to sum the corresponding columns in A'. For example, if we want flames {1,2} to be lighted, we sum the 1st, 2nd columns of A', which is (1,1,1,0,0,0,1), so the 1st, 2nd, 3rd, 7th lever should be pulled. Last edited by xtimz; 07-02-18 at 04:41. |
12-02-18, 16:50 | #5 |
Member
Joined: Apr 2005
Posts: 213
|
I always felt like I've been cheated out of that puzzle...
Every time I get across a puzzle like this in a game, I pull ever lever once to get an understanding and feel for the puzzle, and then proceed to think through it. With this puzzle, pulling every lever once solves it (if I remember correctly), so I've never actually given it any thought. Which makes me feel like a simpleton now, considering the amount of thought and clever maths you've put into it! |
23-04-23, 13:37 | #6 |
Member
Joined: Apr 2010
Posts: 998
|
Hi, I wrote a small stupid program to calculate these. Just copy the following code to an html file and open it in a web browser, then click on the yellow/gray circles to change the states and see the results.
Code:
<!DOCTYPE html> <html> <head> <title>Seven Snakes</title> <style> body { font-family: Verdana; font-size: 16px; } #canvas-main { border: 1px solid #C0C0C0; display: block; margin: 0 auto; } </style> </head> <body> <canvas id="canvas-main" width="800" height="600"></canvas> <div style="margin:0 auto; width:800px"> <p style="font-size:larger; font-weight:bold">Legend:</p> <ul> <li>The inner color represents the current states of the snakes. <ul> <li>Yellow: Already lighted.</li> <li>Gray: Not yet.<br> <br> </li> </ul> </li> <li>The border color represents whether the lever needs to pull in order to light all snakes. <ul> <li>Red: Needs to pull.<br> <br> </li> </ul> </li> </ul> </div> <script> var cvs = document.getElementById("canvas-main"); var ctx = cvs.getContext("2d"); // Positions of the elements var circleBig = new Object(); // The big circle for the overall positions of the 7 small circles. var circleSmall = new Array(7); // The 7 small circles representing the 7 snakes. // Transform matrix and state vectors var invMatA = [[1, 0, 1, 1, 1, 1, 0], [0, 1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 1, 1], [1, 1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 0, 1], [1, 1, 1, 1, 0, 1, 0], [0, 1, 1, 1, 1, 0, 1]]; // The inverse transform matrix: A^(-1). var vecSnake = [0, 1, 1, 1, 1, 1, 1]; // The state of snakes: 0 - already lighted, 1 - not yet. var vecLever = new Array(7); // The levers: 1 - needs to pull. // Drawing styles var clrLine = "#C0C0C0"; // Color of lines between small circles. var clrCircleFill = ["#FFFF00", "#E0E0E0"]; // Color to fill the small circles. var clrCircleStroke = "#FF0000"; // Color to stroke the small circles. init(); function init() { initPos(); calculateLever(); redrawAll(); cvs.onclick = canvasEventMouseClick; } function initPos() { var i; circleBig.x = Math.floor(cvs.width / 2); circleBig.y = Math.floor(cvs.height / 2); circleBig.r = 200; for (i = 0; i < 7; i++) { circleSmall[i] = new Object(); circleSmall[i].x = Math.round(circleBig.x + circleBig.r * Math.sin(2 * Math.PI * i / 7)); circleSmall[i].y = Math.round(circleBig.y - circleBig.r * Math.cos(2 * Math.PI * i / 7)); circleSmall[i].r = 40; } } function calculateLever() { var i, j; for (i = 0; i < 7; i++) { vecLever[i] = 0; for (j = 0; j < 7; j++) { vecLever[i] += invMatA[i][j] * vecSnake[j]; } vecLever[i] %= 2; } } function redrawAll() { var i, j, end = new Array(2); ctx.clearRect(0, 0, cvs.width, cvs.height); // Draw lines between small circles ctx.lineWidth = 1; ctx.strokeStyle = clrLine; for (i = 0; i < 7; i++) { end[0] = i + 3; end[1] = i + 4; for (j = 0; j < 2; j++) { end[j] %= 7; if (i < end[j]) { ctx.beginPath(); ctx.moveTo(circleSmall[i].x, circleSmall[i].y); ctx.lineTo(circleSmall[end[j]].x, circleSmall[end[j]].y); ctx.stroke(); } } } // Draw small circles ctx.lineWidth = 3; ctx.strokeStyle = clrCircleStroke; for (i = 0; i < 7; i++) { ctx.fillStyle = clrCircleFill[vecSnake[i]]; ctx.beginPath(); ctx.arc(circleSmall[i].x, circleSmall[i].y, circleSmall[i].r, 0, Math.PI*2, true); ctx.fill(); if (vecLever[i] == 1) { ctx.stroke(); } } } function canvasEventMouseClick(e) { var i, dx, dy; for (i = 0; i < 7; i++) { dx = e.offsetX - circleSmall[i].x; dy = e.offsetY - circleSmall[i].y; if (dx * dx + dy * dy <= circleSmall[i].r * circleSmall[i].r) { vecSnake[i] = 1 - vecSnake[i]; break; } } calculateLever(); redrawAll(); } </script> </body> </html> |
23-04-23, 19:40 | #7 | |
Member
Joined: Jan 2013
Posts: 201
|
Quote:
|
|
Thread Tools | |
|
|