Problem 1187. Knave in the middle attack

Created by Alfonso Nieto-Castanon

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a Matlab adaptation of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Knights_and_Knaves\"><w:r><w:t>Knights and Knaves</w:t></w:r></w:hyperlink><w:r><w:t> logical puzzles, mixed with the famous</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Man-in-the-middle_attack\"><w:r><w:t>man-in-the-middle attack</w:t></w:r></w:hyperlink><w:r><w:t> in computer security.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are in an island where all inhabitants are either</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Knights</w:t></w:r><w:r><w:t>, who always tell the truth, or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Knaves</w:t></w:r><w:r><w:t>, who always lie. Your job is to sit in the middle of an islander and a second person interviewing the islander, intercepting all questions posed to the islander, and answering to the interviewer in a way that will make him think that the islander is the opposite type of what he really is (answer as a Knave if the islander is a Knight, or answer as a Knight if the islander is a Knave). The problem is: a) you really do not know whether the islander is a Knight or a Knave; and b) the islander knows some secret that only he knows, so you may not be able to anticipate what he would answer even if you knew whether he was a Knight or a Knave! Luckily for you, you may ask the islander privately any questions that you wish before responding to the interviewer.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Details:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are given a function handle F that will act as the islander. This function will answer any question the way the islander would. The function</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>function answer=F(question)</w:t></w:r><w:r><w:t> takes a char array as input (the 'question'), and returns a logical value (the yes/no 'answer' this particular islander would give to this question;</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</w:t></w:r><w:r><w:t> means 'yes' and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>false</w:t></w:r><w:r><w:t> means 'no'). Valid questions are any valid matlab string. The islander has access to the following variables (the things that he 'knows'):</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>A</w:t></w:r><w:r><w:t>: Islander's type. A is a logical variable: true for a Knight, false for a Knave</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>X</w:t></w:r><w:r><w:t>: A secret formula only islanders know. An unknown function on positive integer values that when evaluated returns a logical value (e.g.</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>x&gt;1</w:t></w:r><w:r><w:t>).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>F</w:t></w:r><w:r><w:t>: Introspection. F is the handle associated with this islander's answers, so he knows himself what he would respond to some hypothetical question</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The function handles associated with a Knight and a Knave look, respectively, something like:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[function answer = Knight(question)\n A = true;\n X = @(x)x>10;\n F = @Knight;\n answer = eval(question);\nend\n\nfunction answer = Knave(question)\n A = false;\n X = @(x)x>10;\n F = @Knave;\n answer = ~eval(question);\nend]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Of course the values of X will be different and unknown to you.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A few examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Knight('A==true') == true]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This question asks whether the islander is a Knight, and a Knight would respond affirmatively to such question.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Knave('A|X(1)') == true]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This question asks whether the islander is a Knight or the value of the secret formula at 1 is true. None of these are true, but the Knave will lie to you and respond 'yes'.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Knave('F(''A'')') == false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This question asks whether the islander would respond affirmatively to the question of whether he is a knight. Both Knights and Knaves would actually respond affirmatively when questioned whether they are Knights, but a Knave would lie to you when telling you how he would respond to such question, so he would say 'no'.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You must implement a function that will take two inputs: 1) the function handle of an islander (either @Knight or @Knave); and 2) a question (as a char array). Your function should return the answer this same islander would give to this question if he was the opposite type than he really is. In other words:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ your_function(@Knight,str) should return Knave(str)\n your_function(@Knave,str) should return Knight(str)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your function might query the function handle of the islander with whatever questions it sees fit before responding.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ your_function(@Knight,'A==true') == true;\n\n your_function(@Knave,'A==true') == true;]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This question asks whether the islander is a Knight; both Knights and Knaves would respond</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</w:t></w:r><w:r><w:t> to this question.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ your_function(@Knight,'F(''A==true'')==true') == false; \n\n your_function (@Knave,'F(''A==true'')==true') == true;]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This question asks if the islander would respond yes to the question of whether he is a Knight. A Knight would respond 'yes', while a Knave would (falsely) respond 'no', so your function should return exactly the opposite in each case.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ your_function(@Knight,'X(3)~=X(2)') == true\n\n your_function(@Knave,'X(3)~=X(2)') == false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>(Assuming X(2)==X(3); you do not know the values of X, only islanders do) This question asks to the islander whether the value of his secret formula X(2) is different from the value of his secret formula X(3). Assuming that they were actually the same value a Knight would respond negatively (telling you the truth), while a Knave would respond affirmatively (lying to you), so, again, your function should return exactly the opposite response in each case.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This is a Matlab adaptation of the <a href = "http://en.wikipedia.org/wiki/Knights_and_Knaves">Knights and Knaves</a> logical puzzles, mixed with the famous <a href = "http://en.wikipedia.org/wiki/Man-in-the-middle_attack">man-in-the-middle attack</a> in computer security.You are in an island where all inhabitants are either Knights, who always tell the truth, or Knaves, who always lie. Your job is to sit in the middle of an islander and a second person interviewing the islander, intercepting all questions posed to the islander, and answering to the interviewer in a way that will make him think that the islander is the opposite type of what he really is (answer as a Knave if the islander is a Knight, or answer as a Knight if the islander is a Knave). The problem is: a) you really do not know whether the islander is a Knight or a Knave; and b) the islander knows some secret that only he knows, so you may not be able to anticipate what he would answer even if you knew whether he was a Knight or a Knave! Luckily for you, you may ask the islander privately any questions that you wish before responding to the interviewer.Details:You are given a function handle F that will act as the islander. This function will answer any question the way the islander would. The function function answer=F(question) takes a char array as input (the 'question'), and returns a logical value (the yes/no 'answer' this particular islander would give to this question; true means 'yes' and false means 'no'). Valid questions are any valid matlab string. The islander has access to the following variables (the things that he 'knows'):<ul><li>A: Islander's type. A is a logical variable: true for a Knight, false for a Knave</li><li>X: A secret formula only islanders know. An unknown function on positive integer values that when evaluated returns a logical value (e.g. x&gt;1).</li><li>F: Introspection. F is the handle associated with this islander's answers, so he knows himself what he would respond to some hypothetical question</li></ul>The function handles associated with a Knight and a Knave look, respectively, something like:<pre class="language-matlab">function answer = Knight(question)
 A = true;
 X = @(x)x&gt;10;
 F = @Knight;
 answer = eval(question);
end
</pre><pre class="language-matlab">function answer = Knave(question)
 A = false;
 X = @(x)x&gt;10;
 F = @Knave;
 answer = ~eval(question);
end
</pre>Of course the values of X will be different and unknown to you.A few examples:<pre> Knight('A==true') == true</pre>This question asks whether the islander is a Knight, and a Knight would respond affirmatively to such question.<pre> Knave('A|X(1)') == true</pre>This question asks whether the islander is a Knight or the value of the secret formula at 1 is true. None of these are true, but the Knave will lie to you and respond 'yes'.<pre> Knave('F(''A'')') == false</pre>This question asks whether the islander would respond affirmatively to the question of whether he is a knight. Both Knights and Knaves would actually respond affirmatively when questioned whether they are Knights, but a Knave would lie to you when telling you how he would respond to such question, so he would say 'no'.You must implement a function that will take two inputs: 1) the function handle of an islander (either @Knight or @Knave); and 2) a question (as a char array). Your function should return the answer this same islander would give to this question if he was the opposite type than he really is. In other words:<pre> your_function(@Knight,str) should return Knave(str)
 your_function(@Knave,str) should return Knight(str)</pre>Your function might query the function handle of the islander with whatever questions it sees fit before responding.Examples:<pre> your_function(@Knight,'A==true') == true;</pre><pre> your_function(@Knave,'A==true') == true; </pre>This question asks whether the islander is a Knight; both Knights and Knaves would respond true to this question.<pre> your_function(@Knight,'F(''A==true'')==true') == false; </pre><pre> your_function (@Knave,'F(''A==true'')==true') == true; </pre>This question asks if the islander would respond yes to the question of whether he is a Knight. A Knight would respond 'yes', while a Knave would (falsely) respond 'no', so your function should return exactly the opposite in each case.<pre> your_function(@Knight,'X(3)~=X(2)') == true</pre><pre> your_function(@Knave,'X(3)~=X(2)') == false </pre>(Assuming X(2)==X(3); you do not know the values of X, only islanders do) This question asks to the islander whether the value of his secret formula X(2) is different from the value of his secret formula X(3). Assuming that they were actually the same value a Knight would respond negatively (telling you the truth), while a Knave would respond affirmatively (lying to you), so, again, your function should return exactly the opposite response in each case.

Solve

Solution Stats

59 Solutions
16 Solvers

Last Solution submitted on Jul 03, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Nikolaos Nikolaou on 16 May 2020

Broken test suite? The handle wont work in some cases

Rafael S.T. Vieira on 3 Jul 2020

Yes, it seems that test suit is wrong. cases 13 e 14 won't work.
For instance from case 13:
A=false; X=@(x)rem(x,2); str='F(''F(''''X(3)'''')'')';
f0=inline('logical(interp1([0,1],[0,x],1))','x','A','X');
F=@(str)xor(~A,f0(eval(str),A,X));
if I execute F(str) inside my function AnswerGenerator it complains...
Error using eval
Unrecognized function or variable 'F'.
It seems the syntax is wrong. So we cannot know what the answer would be from the knight or the knave (I'm trying to fix the string input).

Rafael S.T. Vieira on 3 Jul 2020

So I was able to fix the strings (str) manually using replace. Previous solutions won't work, so I guess the test cases were changed and broken. Please ignore my solution if this is fixed later on (it's only right for now, fixing it and evaluating it manually is a pain). I will resubmit a proper solution when it is fixed and I see it fixed.

Problem Recent Solvers16

Problem Tags

Problem 1187. Knave in the middle attack

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers16

Suggested Problems

More from this Author38

Problem Tags

Problem 1187. Knave in the middle attack

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers16

Suggested Problems

More from this Author38

Problem Tags

Players