Instantly share code, notes, and snippets.

# hwayne/kke.md

Last active October 19, 2021 20:43
Show Gist options
• Save hwayne/23cf70e209abb8a7bc45541038ccf52f to your computer and use it in GitHub Desktop.
The Knights and Knaves Express

It's time to drag the Island of Knights and Knaves kicking and screaming into the 19th century! We're going to run a train. For these puzzles, you'll have a set of stations with possible connections, and you need to find a route that starts at one station, goes through every other station exactly once, and ends in a station. IE if our map was

``````A -- B -- C
|    |    |
D -- E -- F
``````

Valid routes might be `A B C F E D`, or `A D E B C F`, but `A B E D C F` is invalid. The ordering matters: `A B C` is a different route from `C B A`.

But also, every station is run by either a Knight or a Knave. The stationmaster has a set of requirements for the route. Knights tell the truth about their requirements, but Knaves always lie. You must plan the route so that every requirement by a Knight is satisfied, and every requirement by a Knave is unsatisfied. IE if we have

``````A --- B
|     |
-- C --
``````

If C says "I must come first", if C is a Knight, then the route starts at C. But if C is a knave, the route does not start with C.

## Problem 1

At least one of the two stationmasters is a Knave.

``````A -- B
``````

A: "Start at my station."

B: "End at my station."

## Problem 2

Two of the stationmasters are knights, two are knaves.

``````A -- D
|    |
B -- C
``````

A: "The route must connect to me right after a Knave's station."

B: "I should come at some point before C."

C: "Make sure the two knights are adjacent to one another: one has to come right after the other."

D: "A and B should both come at some point before me."

B (again): "Oh, also: I should come at some point after A."

## Problem 3

``````   A
/   \
B --- C
``````

A: "Don't put Raymond right before me."

B: "Don't put Raymond right after me."

C: "Don't put Raymond right before or right after me."

You: "What's wrong with Raymond?"

A: "He's an asshole and a Knave."

B: "He wears sunglasses indoors."

C: "He calls himself a 'singer-songwriter'."

The annoying thing with these is that I want people to express requirements like "If X is true, then do Y". That's formally `X => Y`, but the negation is `X /\ !Y`. What I want is that if the person is a Knave, you have to satisfy `X => !Y`.