Hacker News Reader

Comment by marknadal | Hacker News Reader

#2 is easy, by using double negatives and asking the same question to each god (asking different questions does you no good):

"Is the other non-random god capable of lying?"

The truth telling god will always answer: "yes" (da || ja)

The false telling god will always answer: "yes" (da || ja) [the truthful answer is 'no', but this god tells only lies, therefore the answer is 'yes']

The random god will answer: "yes || no" ((da || ja) || (ja || da))

This means, you will always only get the following combination of answers, no matter what A,B,C order you ask:

da, da, da; ja, ja, ja;

da, da, ja; ja, ja, da;

ja, ja, da; da, da, ja;

da, ja, da; ja, da, ja;

ja, da, ja; da, ja, da;

'Yes' will always have 2 or 3 of the same values. 'No' can only have 1 or 0 values. Now that you have the cipher, you can decode everything.

(edit: formatting)

View on HN

That's an interesting insight, and it may be useful as part of the solution, but it doesn't solve the puzzle. The question is how to determine the identity of the three gods with three questions.

Personally, I think it's interesting that they are gods. Does this mean that they can answer questions about what WILL happen? E.g. you could ask a god what the next god will answer. If the answer is correct, that's the true or random god. If the answer is wrong, then it's the false or random god. But then we get recursive rather quickly if we ask the question twice in a row. :)

I suspect they are mentioned to be gods to suggest that they may be asked extremely complicated questions, which they will interpret from a purely logical standpoint. ie. Not human.

Starting from this premise, imagine this sequence of questions (it's not the answer, btw):

1. What is the answer to the next question? A: 1, 0

2. What was the answer to the previous question? B: 1, 0

3. What was the answer to the previous question? C: 1, 0

000-impossible: no false god

001-C is the false god, but can't distinguish the other two

010-impossible: no true god.

011-C is the true god, but you can't distinguish between the false and random god

100-A is the false god, but can't distinguish the other two

101-impossible: no true god.

110-A is the true god, but you can't distinguish between the false and random god

111-impossible: no false god

This is interesting: we have eliminated 4 possibilities, 000, 111, 101 and 010. Not only that, now we have a whole new universe to converse about - we can ask the gods about these patterns!

The remaining possibilities show some symmetry: 001 and 100, 011 and 110.

So, thinking aloud, start with these questions:

1. Will the result of my questioning be either 001 or 100?

2. Will the result of my questioning be either 011 or 110?

The answers won't give us much information because they can be anything. But we can "break symmetry" and ask them like this instead:

1. Will the result of my questioning be either 001 or 011?

2. Will the result of my questioning be either 100 or 110?

...and I feel like I'm very close but I'm missing something.

How can you then distinguish between the two non-randomly-answering gods? They will answer the same, and the answer from the randomly-answering god appears to contain no useful information.

Oh, I must not have read the instructions thoroughly enough - I thought the solution was looking for an answer, not for the identities. My bad.

I'm guessing the same principle should apply though, I'll comment an update if I don't fall asleep from having been up all night. Thanks for pointing that out, though.

So I started to work it out, only to discover the link about the problem in the article gives it away - counterfactuals can be used, so might as well read that instead of any thing I come up with. And thus I just wasted a bunch of time trying to figure out which specific one worked (now erased) ... but my hunch was correct! (Although hunches are hardly proofs, tsk tsk)

Also, I want to thank you again for helping me out with awk/sed/grep/command line stuff, from a year ago!

You're welcome!

What's a counterfactual? can you give a simple explanation of how that solves the problem?

A counterfactual is a statement or question in the form 'If X ... would Y". Y would happen if X were true. Or, would Y be true, given that X were true? [0]

In the case of this puzzle, a counterfactual can be used to embed a question X within your question Y. By doing so (and exploiting the phrasing of the problem), you force the gods to answer in a manner that either reveals their identity as True, False, or Random.

Explaining the actual process through which the counterfactual is used to solve the problem is a bit tedious but the Wikipedia article on the puzzle has a pretty straightforward explanation of the reasoning[1].

[0] http://en.wikipedia.org/wiki/Counterfactual_conditional [1] http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever.

I haven't looked at the answers yet, but here's what I came up with in pseudocode:

    A: Would one of the other Gods, who is not Random, say "da" \
        if I asked him if God C was Random?
    (DA) {
        :God A or B is Random.

        C: Does "da" mean "yes"?
        (DA) {
            :God C is True.
        } (JA) {
            :God C is False.
        }
        
        C: Would you say "da" if asked whether God A is Random?
        (DA) {
            :God A is Random
            :God B is !God C.
        } (JA) {
            :God B is Random.
            :God A is !God C.
        }
    } (JA) {

        :God A or C is Random.
        B: Does "da" mean "yes"?
        (DA) {
            :God B is True.
        } (JA) {
            :God B is False.
        }
        
        B: Would you say "da" if asked whether God A is Random?
        (DA) {
            :God A is Random
            :God C is !God B.
        } (JA) {
            :God C is Random.
            :God A is !God B.
        }
    }

I found it helpful to build the logic assuming they would answer "yes" and "no" in English. Once that was done it was fairly simply to modify it to handle the da/ja.

vg vf cbffvoyr gb qrgrezvar gur vqragvgvrf bs gur guerr tbqf jvgubhg xabjvat juvpu jnl ebhaq wn naq qn ner. (r.t. guvax nobhg ubj gb qb guvf jvgu whfg gur Gehr naq Snyfr tbqf, vtabevat Enaqbz)

gur dhrfgvbaf lbh ner nfxvat va trareny fubhyq punatr qrcraqvat ba gur bofreirq qn|wn nafjref gb gur cerivbhf dhrfgvbaf. n fgengrtl pna or n gerr bs dhrfgvbaf, abg n frdhrapr svkrq va nqinapr.

gur uneq ovg vf vfbyngvat gur enaqbz tbq sebz gur bgure gjb tbqf. abgr gung gur enaqbz tbq qbrf abg enaqbzyl rzvg lrf be ab (rapbqrq nf wn<->qn), vg enaqbzyl nafjref gur tvira dhrfgvba rvgure gehgushyyl be snyfryl. fb lbh pna senzr n fhvgnoyl pbagbegrq dhrfgvba gung sbeprf gur fnzr erfcbafr sebz gur enaqbz tbq va obgu gehgul-zbqr naq snyfrl-zbqr, gung qvfgvathvfurf vg sebz gur aba-enaqbz tbqf...

Apropos of nothing in particular ...

Not bothering to use ROT13, I just dropped that into my generic substitution cipher decoder and it spat out the answer almost immediately - quite pleased with that.

Interesting. You cycle through substitutions and match against a dictionary to detect a hit?

Nope, I use the shotgun stochastic hill-climbing algorithm I wrote for something else, with the ballistic option disabled.

In short:

    While True:
        Generate a random key
        "Decode"
        Score
        Start timer
        While timer not expired:

            Perturb the key
            Score
            If better:
                Keep the new key
                Reset timer
        Print decrypt

In this case the first output was completely readable.

I have no idea how you'd make a scoring system that worked well with a hill climbing algorithm. You could check each word for a match in the dictionary, but with a substitution cipher you could essentially turn one word into any other word of the same length (excluding words with the same letter in them). Without a way to check for "close" words, you wouldn't be able to climb the hill. would "pello" score a 0.7 and "hello" a 1? I can't think of a fast way to get that number.

I'd like to try my own hand at this, but the way I'm thinking of making the fitness function doesn't seem like it would be smooth enough.

What did you do?

Take a frequency chart of all trigrams in English, and take the vector product of the frequency in the decrypt with the frequency in English.

So, let E(t) be the frequency of occurrence of the trigram t in English, d(t) be how often it occurs in the decrypted text, and compute:

  Score = sum( [ E(t)*d(t) for t in decrypt ] )

If common trigrams turn up frequently in the decrypt, this will be "large". If uncommon trigrams turn up frequently, this will be "small".

...

that is a really good idea...

Turns out there's also a fair amount of data to use as well.

http://www.cse.chalmers.se/edu/year/2010/course/TDA351/ass1/...

I was thinking too rigidly. Thanks!

Norvig has made n-gram data available:

http://norvig.com/ngrams/

Why not use a residual sum of squares here?

https://en.wikipedia.org/wiki/Residual_sum_of_squares

I don't understand your question.

My (admittedly naive) understanding of using RSS is this. I have a model of the data, which in this case will be expected frequencies of my n-grams. Then I compute the actual frequencies of the n-grams, take the difference, square the difference, and add up all the squares. A small number is then indicative of a good fit.

I don't see why this would be better. Not least, this has the problem of all those n-grams that don't turn up in my decrypt. I still have to square their expected frequency and add them into the sum. That contrasts with the method I'm using, where I just take the n-grams that do appear, multiply by the expected frequency, and add that into a running total.

So I guess I don't understand your suggestion.

Please, if you're going to give a solution, rot13 it or link to it or something. Don't blurt it out in the first line of your answer.

Reply on news.ycombinator.com