Tomb Raider Forums

Tomb Raider Forums (https://www.tombraiderforums.com/index.php)
-   Tomb Raider The Last Revelation (https://www.tombraiderforums.com/forumdisplay.php?f=9)
-   -   Lost Library: Snake problem vs. Linear algebra (https://www.tombraiderforums.com/showthread.php?t=219337)

xtimz 05-02-18 22:30

Lost Library: Snake problem vs. Linear algebra
 
I've always wanted to write this.
In Lost Library, the snake problem:
[IMG]https://i.imgur.com/r1MB107.jpg[/IMG]

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.

[IMG]https://i.imgur.com/A0JJesc.png[/IMG]

That's it. :D

xtimz 05-02-18 22:38

In case the image is lost (as before), you can run the following Latex code to see the 2nd image.

[QUOTE]\documentclass{article}
\begin{document}
\setlength{\parindent}{0em}
Number the $7$ snakes clockwise. (Starting from anyone is OK). Let matrix $A$
\begin{displaymath}
A = \left[
\begin{array}{ccccccc}
1 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1
\end{array}
\right]
\end{displaymath}
where the $i$th column of $A$ denotes which flame will change after the $i$th lever is pulled.
For example, the $1$st, $4$th, $5$th elements are $1$ in column $1$, which means the $1$st, $4$th, $5$th flames will change after the $1$st lever is pulled.
Let vectors $x$, $b$ denotes
\begin{displaymath}
x_i = \left\{
\begin{array}{ll}
1, & \mbox{$i$th lever pulled.} \\
0, & \mbox{$i$th lever not pulled.}
\end{array}
\right.
\end{displaymath}
\begin{displaymath}
b_i = \left\{
\begin{array}{ll}
1, & \mbox{$i$th flame lighted.} \\
0, & \mbox{$i$th flame not lighted.}
\end{array}
\right.
\end{displaymath}
then we have the property $Ax=b$.
For example, if the $1$st, $2$nd lever is pulled, let $x=(1,1,0,0,0,0,0)^T$, from the calculations $b=Ax=(1,1,0,1,0,1,0)^T$, so the $1$st, $2$nd, $4$th, $6$th flames will be lighted.
In this way, we know which flame is lighted given which lever is pulled.
The objective is to find which lever is pulled given which flame is lighted.
By linear algebra, all we need is to find the inverse matrix of $A$, which is
\begin{displaymath}
A^{-1} = \left[
\begin{array}{ccccccc}
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
\end{array}
\right]
\end{displaymath}
then we have $x=A^{-1}b$.
For example, if all flames except the $1$st is lighted, let $b=(0,1,1,1,1,1,1)^T$, from the calculations $x=A^{-1}b=(0,1,0,0,0,0,1)^T$, so the $2$nd, $7$th lever should be pulled.
\end{document}
[/QUOTE]

The Great Chi 06-02-18 00:16

Well done :tmb:

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 :D

[img]https://i.imgur.com/2CqksVh.jpg[/img]

xtimz 07-02-18 04:38

^ 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.

Dug 12-02-18 16:50

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!:cln:

xtimz 23-04-23 13:37

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>
[/CODE]

Salem150 23-04-23 19:40

[QUOTE=xtimz;8397510]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>
[/CODE][/QUOTE]

Wow impressive work, it sure will come handy! thanks :)


All times are GMT. The time now is 15:03.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Tomb Raider Forums is not owned or operated by CDE Entertainment Ltd.
Lara Croft and Tomb Raider are trademarks of CDE Entertainment Ltd.