Cody

Problem 1187. Knave in the middle attack

This is a Matlab adaptation of the Knights and Knaves logical puzzles, mixed with the famous man-in-the-middle attack 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'):

  • A: Islander's type. A is a logical variable: true for a Knight, false for a Knave
  • X: A secret formula only islanders know. An unknown function on positive integer values that when evaluated returns a logical value (e.g. x>1).
  • F: Introspection. F is the handle associated with this islander's answers, so he knows himself what he would respond to some hypothetical question

The function handles associated with a Knight and a Knave look, respectively, something like:

function answer = Knight(question)
  A = true;
  X = @(x)x>10;
  F = @Knight;
  answer = eval(question);
end
function answer = Knave(question)
  A = false;
  X = @(x)x>10;
  F = @Knave;
  answer = ~eval(question);
end

Of course the values of X will be different and unknown to you.

A few examples:

 Knight('A==true') == true

This question asks whether the islander is a Knight, and a Knight would respond affirmatively to such question.

 Knave('A|X(1)') == true

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

 Knave('F(''A'')') == false

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:

 your_function(@Knight,str) should return Knave(str)
 your_function(@Knave,str) should return Knight(str)

Your function might query the function handle of the islander with whatever questions it sees fit before responding.

Examples:

 your_function(@Knight,'A==true') == true;
 your_function(@Knave,'A==true') == true; 

This question asks whether the islander is a Knight; both Knights and Knaves would respond true to this question.

 your_function(@Knight,'F(''A==true'')==true') == false; 
 your_function (@Knave,'F(''A==true'')==true') == true; 

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.

 your_function(@Knight,'X(3)~=X(2)') == true
 your_function(@Knave,'X(3)~=X(2)') == false 

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

Solution Stats

31.71% Correct | 68.29% Incorrect
Last Solution submitted on Dec 05, 2019

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author38