Python solution to The Hardest Logic Puzzle Ever

Question

The The Hardest Logic Puzzle Ever recently came to my attention:

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

Furthermore, a single god may be asked more than one question, questions are permitted to depend on the answers to earlier questions, and the nature of Random's response should be thought of as depending on the flip of a fair coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

I quickly wrote a Python solution. The code is meant to be mostly PEP8 compliant but was not intended to be very formal — just a straight port from word problem to program. If there is a problem, the program should immediately crash to prevent undiscovered bugs.

Given that the code shown below was meant to simply test the ideas provided in the solution for the puzzle, would it be best to rewrite the program and clean it up if code quality is to be improved without having regards for how the problem and its solution reads?

#! /usr/bin/env python3
# Reference: https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever
from random import choice, sample


def question_1(god):
    if god == 'Random':
        return choice((yes, no))
    truth = a == 'Random'   # part 1
    if god == 'True':
        answer = yes if truth else no
    elif god == 'False':
        answer = no if truth else yes
    truth = answer == 'ja'  # part 2
    if god == 'True':
        return yes if truth else no
    elif god == 'False':
        return no if truth else yes


def question_2(god):
    if god == 'Random':
        return choice((yes, no))
    truth = god == 'False'  # part 1
    if god == 'True':
        answer = yes if truth else no
    elif god == 'False':
        answer = no if truth else yes
    truth = answer == 'ja'  # part 2
    if god == 'True':
        return yes if truth else no
    elif god == 'False':
        return no if truth else yes


def question_3(god):
    if god == 'Random':
        return choice((yes, no))
    truth = b == 'Random'   # part 1
    if god == 'True':
        answer = yes if truth else no
    elif god == 'False':
        answer = no if truth else yes
    truth = answer == 'ja'  # part 2
    if god == 'True':
        return yes if truth else no
    elif god == 'False':
        return no if truth else yes


for _ in range(10000):
    # setup
    a, b, c = sample(('True', 'False', 'Random'), 3)
    da, ja = sample(('yes', 'no'), 2)
    temp = {y: x for x, y in globals().items() if isinstance(y, str)}
    yes, no = temp['yes'], temp['no']
    del temp
    # question
    answer = question_1(b)
    if answer == 'ja':
        not_random = 'c'
    elif answer == 'da':
        not_random = 'a'
    answer = question_2(globals()[not_random])
    if answer == 'da':
        not_random_id = 'True'
    elif answer == 'ja':
        not_random_id = 'False'
    answer = question_3(globals()[not_random])
    if answer == 'ja':
        b_id = 'Random'
    elif answer == 'da':
        if not_random != 'a':
            a_id = 'Random'
        elif not_random != 'c':
            c_id = 'Random'
    # decide
    if not_random == 'a':
        a_id = not_random_id
    elif not_random == 'c':
        c_id = not_random_id
    try:
        a_id
    except NameError:
        a_id = ({'True', 'False', 'Random'} - {b_id, c_id}).pop()
    else:
        try:
            b_id
        except NameError:
            b_id = ({'True', 'False', 'Random'} - {a_id, c_id}).pop()
        else:
            try:
                c_id
            except NameError:
                c_id = ({'True', 'False', 'Random'} - {a_id, b_id}).pop()
    # verify
    try:
        assert (a, b, c) == (a_id, b_id, c_id)
    except AssertionError:
        print(f'a, b, c = {a!r}, {b!r}, {c!r}')
        print(f'a_id, b_id, c_id = {a_id!r}, {b_id!r}, {c_id!r}')
        raise
    else:
        del a, b, c, da, ja, yes, no, \
            answer, not_random, not_random_id, \
            a_id, b_id, c_id

Answer 1

The code is not well organized. The 3 questions are very similar and does not explain what is being asked, and the top-level code mix together the setup logic, the solving logic and the testing logic.

Besides, the whole logic is convoluted: using strings to store state is error-prone; and relying so much on the global state (and even the name of some variables) is even more.

You should:

1. Define some constant using enums:

   import enum
   
   
   class Answer(enum.Enum):
       JA = 'ja'
       DA = 'da'
   
   
   class God(enum.Enum):
       TRUE = True
       FALSE = False
       RANDOM = None
   

2. Extract out the question structure so it is easier to understand what is being asked:

   def answer_truthy(question):
       return yes if question else no
   
   
   def answer_falsey(question):
       return no if question else yes
   
   
   def would_you_say_ja_if_asked(question, god):
       if god is God.RANDOM:
           return choice((yes, no))
   
       god_answer = answer_truthy if god is God.TRUE else answer_falsey
       answer = god_answer(question)
       return god_answer(answer is Answer.JA)
   

   So you can would_you_say_ja_if_asked(a is God.RANDOM, b) for instance, which is clearer what is being asked.

   To make it read even better, you can define this last function as a method on the God class:

   class God(enum.Enum):
       TRUE = True
       FALSE = False
       RANDOM = None
   
       def would_you_say_ja_if_asked(self, question):
           if self is God.RANDOM:
               return choice((yes, no))
   
           god_answer = answer_truthy if self is God.TRUE else answer_falsey
           answer = god_answer(question)
           return god_answer(answer is Answer.JA)
   

   Which is used as b.would_you_say_ja_if_asked(a is God.RANDOM) and reads very well.

3. Extract out your solving logic out of the setup + test one:

   def solve():
       """Solve the puzzle by asking three questions"""
       a = b = c = None
   
       # Determine which of A or C is not the Random god
       answer = B.would_you_say_ja_if_asked(A is God.RANDOM)
       non_random_god = C if answer is Answer.JA else A
   
       # Determine the identity of previously selected god
       answer = non_random_god.would_you_say_ja_if_asked(non_random_god is God.FALSE)
       if non_random_god is C:
           c = God.FALSE if answer is Answer.JA else God.TRUE
       else:
           a = God.FALSE if answer is Answer.JA else God.TRUE
   
       # Determine which god is Random
       answer = non_random_god.would_you_say_ja_if_asked(B is God.RANDOM)
       if answer is Answer.JA:
           b = God.RANDOM
       elif non_random_god is C:
           a = God.RANDOM
       else:
           c = God.RANDOM
   
       # Deduct the identity of the third god
       last_one = (set(God) - {a, b, c}).pop()
       if a is None:
           a = last_one
       elif b is None:
           b = last_one
       else:
           c = last_one
   
       return a, b, c
   

4. Stop relying on global variables and pass state explicitly around:

   #! /usr/bin/env python3
   
   """Setup and find an answer to the hardest puzzle ever.
   
   The puzzle statement is as follows:
   
       Three gods A, B, and C are called, in no particular
       order, True, False, and Random. True always speaks
       truly, False always speaks falsely, but whether Random
       speaks truly or falsely is a completely random matter.
       Your task is to determine the identities of A, B, and
       C by asking three yes-no questions; each question must
       be put to exactly one god. The gods understand English,
       but will answer all questions in their own language, in
       which the words for yes and no are da and ja, in some
       order. You do not know which word means which.
   
       Furthermore, a single god may be asked more than one
       question, questions are permitted to depend on the
       answers to earlier questions, and the nature of Random's
       response should be thought of as depending on the flip
       of a fair coin hidden in his brain: if the coin comes
       down heads, he speaks truly; if tails, falsely.
   
   Reference: https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever
   
   The solution is found as follows:
   
       * ask B if they would say ja if asked 'is A Random?';
       depending on the answer either A or C is not Random.
       * ask the non-Random god if they would say ja if asked
       'are you False?'; the answer will tell who they are.
       * ask the same god if they would say ja if asked
       'is B Random?'; the answer will tell who Random is.
       * the third god can be deduced without further questions.
   """
   
   import sys
   import enum
   from random import choice, sample
   
   
   class Answer(enum.Enum):
       JA = 'ja'
       DA = 'da'
   
   
   class God(enum.Enum):
       TRUE = True
       FALSE = False
       RANDOM = None
   
       def would_you_say_ja_if_asked(self, question, yes_no_meaning):
           if self is God.RANDOM:
               return choice(yes_no_meaning)
   
           god_answer = answer_truthy if self is God.TRUE else answer_falsey
           answer = god_answer(question, yes_no_meaning)
           return god_answer(answer is Answer.JA, yes_no_meaning)
   
   
   def answer_truthy(question, yes_no_meaning):
       yes, no = yes_no_meaning
       return yes if question else no
   
   
   def answer_falsey(question, yes_no_meaning):
       yes, no = yes_no_meaning
       return no if question else yes
   
   
   def solve(A, B, C, yes_no_meaning):
       """Solve the puzzle by asking three questions"""
       a = b = c = None
   
       # Determine which of A or C is not the Random god
       answer = B.would_you_say_ja_if_asked(A is God.RANDOM, yes_no_meaning)
       non_random_god = C if answer is Answer.JA else A
   
       # Determine the identity of previously selected god
       answer = non_random_god.would_you_say_ja_if_asked(non_random_god is God.FALSE, yes_no_meaning)
       if non_random_god is C:
           c = God.FALSE if answer is Answer.JA else God.TRUE
       else:
           a = God.FALSE if answer is Answer.JA else God.TRUE
   
       # Determine which god is Random
       answer = non_random_god.would_you_say_ja_if_asked(B is God.RANDOM, yes_no_meaning)
       if answer is Answer.JA:
           b = God.RANDOM
       elif non_random_god is C:
           a = God.RANDOM
       else:
           c = God.RANDOM
   
       # Deduct the identity of the third god
       last_one = (set(God) - {a, b, c}).pop()
       if a is None:
           a = last_one
       elif b is None:
           b = last_one
       else:
           c = last_one
   
       return a, b, c
   
   
   def setup_puzzle():
       yes, no = sample(list(Answer), 2)
       a, b, c = sample(list(God), 3)
       return yes, no, a, b, c
   
   
   def test(test_cases=10_000):
       for _ in range(test_cases):
           yes, no, A, B, C = setup_puzzle()
           a, b, c = solve(A, B, C, (yes, no))
   
           if (a, b, c) != (A, B, C):
               print(f'a, b, c = {a}, {b}, {c}', file=sys.stderr)
               print(f'A, B, C = {A}, {B}, {C}', file=sys.stderr)
               sys.exit('Found a failing case')
   
       print('All tests passed')
   
   
   if __name__ == '__main__':
       test()
   

Answer 2

1. The code needs a lot more comments to say why. Why is each question_x written as it is written? Why is there a loop over 10000? My best guess is that the questions hard-code a strategy and you test it with 10000 random configurations, but (a) that should be made explicit (and so should the strategy itself); and (b) you should explain why you test 10000 random configurations when there are only 12 possible configurations.

2. The use of globals is very confusing. I strongly suggest passing around an explicit state.

Answer 3

Best general answer

@Mathias Ettinger's answer is very comprehensive for the big picture design changes, so I would probably follow that one for my general design (though your question has piqued my interest in programming this question, so I may come back with my own variant at some point). However, I do have some useful tidbits to offer in my answer, and they can hopefully help you improve your knowledge, even if they aren't the big picture for this problem.

Answering the meta question

In what cases would this implementation of THLPE require more formality?

...

Given that the code shown below was meant to simply test the ideas provided in the solution for the puzzle, it what case(s) would it be best to rewrite the program and clean it up if code quality is to be improved without having regards for how the problem and its solution reads?

Code Review is a place for general review of code quality as described in Do I want the code to be good code? in our on-topic page. I will be reviewing just as described there. I am not approaching the problem in this way just because of how our rules are phrased. In my experience in general coding, I've found that following best practices in general helps to achieve better reliability, and I think most would agree with me on this. There is really not any conflict between best practices and reliability; they go hand in hand.

On the other hand, best practices and performance can sometimes come into conflict. However, for many (most?) problems, optimizing performance beyond best practices is not a real issue, hence the common programming aphorism of premature optimization. And when this becomes a common enough issue in an active programming language (like Python), the language can be revised to address it, or alternate solutions can be developed by the community (like Cython for C-optimized Python code).

Review

Don't repeat yourself!

There's one extremely noticeable bad practice in your program. question_1, question_2, and question_3 are all verbatim identical aside from their names. Instead of having repeated code, there should be a single question function, which I would probably renamed to ask_question for more clarity. If the number of the question was important, then it should be a parameter to that one function (probably named num, unless it has a more specific designation). However, the number does not matter in this problem. The only information that matters for this puzzle is the

Repeating code is a bad practice because there's more code to keep track of when revising the code, so it's easier to introduce a continuity error. It is also generally easier to read shorter code.

Don't abuse globals()

You should be wary of using globals() because it introduces another layer of complexity into a program. Unless you're sure that you need it, you should try to find another way to accomplish your goal. In your case, you could have a dict or even an iterable to store the gods, so there's no reason to haphazardly query globals.

Use the right function for the situation

The following two lines come to my attention:

    a, b, c = sample(('True', 'False', 'Random'), 3)
    da, ja = sample(('yes', 'no'), 2)

Here, you're using random.sample to randomly order a tuple. However, there is some implicit repetition here: you're entering the length of each tuple (3 and 2 respectively), when that information could be retrieved from the tuple itself through the len built-in function. This repetition occurs because sample is the wrong function for this situation: you actually want random.shuffle if you're trying to reorder an iterable (though it modifies its argument in-place, so it would need a list instead of a tuple).

However, for the big picture, I wouldn't even use a randomly generated list like this; I would probably use enums in a way similar to @Mathias Ettinger's answer.

Answer 4

A minor comment for efficiency, for example, you may want to change

def question_1(creature):
    if creature == 'Random':
        return choice((yes, no))
    truth = a == 'Random'   # part 1
    if creature == 'True':
        answer = yes if truth else no
    elif creature == 'False':
        answer = no if truth else yes
    truth = answer == 'ja'  # part 2
    if creature == 'True':
        return yes if truth else no
    elif creature == 'False':
        return no if truth else yes

to

def question_1(creature):
    if creature == 'Random':
        return choice((yes, no))

    truth = a == 'Random'   # part 1

    if creature == 'True':
        answer = yes if truth else no
        truth = answer == 'ja'  # part 2
        return yes if truth else no
    else:
        answer = no if truth else yes
        truth = answer == 'ja'  # part 2
        return no if truth else yes

• Since there are only 3 possibilities for creature: 'Random', 'False', or 'True'. So after if creature == 'True', else is for when creature == False.

• The previous one has two if creature == 'True':..., but you can make it into just one to be more compact.