Enigmatic Code

Programming Enigma Puzzles

Enigma 371: No last words

From New Scientist #1520, 7th August 1986 [link]

1. There is at least one true sentence and at least two false sentences here, and the number of the first true sentence added to the number of the second false one gives the number of a sentence which is false.

2. There is at least one false sentence and at least two true sentences here, and the number of the first false sentence added to the number of the second true one gives the number of a sentence which is true.

3. This Enigma would still have a unique answer if the very last of the number of sentences were deleted.

4. There are more true sentences than false sentences in this list.

5. Sentences 1 and 2 are equally true.

How many of the sentences are false?

[enigma371]

Advertisements

5 responses to “Enigma 371: No last words

  1. Jim Randell 18 November 2016 at 7:57 am

    This Python program runs in 52ms.

    from itertools import product
    from enigma import filter2, printf
    
    # check truth values a and b are equivalent
    def check(a, b):
      return a == b
    
    # generate solutions for the puzzle considering only the first n statements
    def solve(n):
    
      # is there a unique solution to the problem with n - 1 statements?
      # (we evaluate this once when/if it is needed)
      v3 = None
    
      # choose truth values
      for ss in product((True, False), repeat=n):
    
        # count the trues and the falses
        (ts, fs) = filter2(lambda i: ss[i], (i for (i, _) in enumerate(ss)))
    
        # 1. "There is at least one true sentence and at least two false
        # sentences here, and the number of the first true sentence added to
        # the number of the second false one gives the number of a sentence
        # which is false."
        if n > 0:
          try:
            v1 = (len(ts) > 0 and len(fs) > 1 and ss[ts[0] + fs[1] + 1] == False)
          except IndexError:
            v1 = False
          if not check(ss[0], v1): continue
    
        # 2. "There is at least one false sentence and at least two true
        # sentences here, and the number of the first false sentence added
        # to the number of the second true one gives the number of a
        # sentence which is true."
        if n > 1:
          try:
            v2 = (len(fs) > 0 and len(ts) > 1 and ss[fs[0] + ts[1] + 1] == True)
          except IndexError:
            v2 = False
          if not check(ss[1], v2): continue
    
        # 3. "This Enigma would still have a unique answer if the very
        # last of the number of sentences were deleted."
        if n > 2:
          if v3 is None:
            rs = set(x.count(False) for x in solve(n - 1))
            v3 = (len(rs) == 1)
          if not check(ss[2], v3): continue
    
        # 4. "There are more true sentences than false sentences in this
        # list."
        if n > 3:
          if not check(ss[3], len(ts) > len(fs)): continue
    
        # 5. "Sentences 1 and 2 are equally true."
        if n > 4:
          if not check(ss[4], ss[0] == ss[1]): continue
    
        yield ss
    
    # solve the puzzle with all 5 statements
    for ss in solve(5):
      printf("{n} false statements; {ss}", n=ss.count(False))
    

    Solution: 4 of the sentences are false.

    • Jim Randell 18 November 2016 at 7:58 am

      Analytically:

      If we consider the problem limited to the first two statements only, then they must be both false. So there is a unique answer (of 2 false statements).

      We can then expand the problem by considering the first three statements. Statement 3 is true (as there is a unique answer to a problem consisting of just the first two statements), and the first two statements are false. So, again, there is a unique answer (of 2 false statements).

      Expanding the problem again by considering the first four statements. Statement 3 is true (as before), but Statements 1, 2 and 4 can be either (False, True, True) or (False, False, False). So there is not a unique answer as there can be 1 false statement or 3 false statements.

      So this brings us to the actual problem as stated. Statement 3 is false (as there is not a unique solution for the problem consisting of the first four statements), but statements 1, 2, 4 and 5 can be either of (True, False, False, False) or (False, False, False, True). But whichever set of statements is chosen, 4 of the statements are false, so there is a unique answer to this problem.

  2. Jim Randell 19 November 2016 at 6:16 pm

    My programmed solution to this puzzle got me thinking about delayed evaluation in Python.

    In my program above the value of v3 does not change during the execution of the loop, and is evaluated the first time it is needed, and then that value is reused if it is needed again. This is known as “delayed evaluation” (or “lazy evaluation”).

    Suppose we have a function that is “expensive” to call (because it uses a lot of computer resources, probably CPU time).

    def expensive(a, b):
      printf("[computing expensive({a}, {b})...]")
      return a + b
    

    In normal Python we can create a list of three calls to the function:

    >>> s = [expensive(1, 2), expensive(3, 4), expensive(5, 6)]
    [computing expensive(1, 2)...]
    [computing expensive(3, 4)...]
    [computing expensive(5, 6)...]
    

    When the list is created all three expensive function calls are made and the results are stored in the list s. We can then access the results however we like without having to call the expensive function again:

    >>> s[1]
    7
    >>> s[0]
    3
    >>> s[1]
    7
    

    However, in this case, we didn’t ask for the third element in the list, so all the time spent computing that value was wasted.

    Here is a class that delays the evaluation of a function until the value is required.

    class Delay(object):
    
      def __init__(self, fn, *args, **kw):
        self.fn = fn
        self.args = args
        self.kw = kw
        self.evaluated = False
    
      def evaluate(self):
        self.value = self.fn(*(self.args), **(self.kw))
        self.evaluated = True
        return self.value
    
      def reset(self):
        del self.value
        self.evaluated = False
    
      def __getattr__(self, key):
        if key == 'value':
          return self.evaluate()
        else:
          raise AttributeError
    

    Instead of calling the expensive function we can use the Delay() class to hold the function and its arguments until the result is needed.

    Here’s the same sequence of events as before:

    >>> s = [Delay(expensive, 1, 2), Delay(expensive, 3, 4), Delay(expensive, 5, 6)]
    >>> s[1].value
    [computing expensive(3, 4)...]
    7
    >>> s[0].value
    [computing expensive(1, 2)...]
    3
    >>> s[1].value
    7
    

    The values are not computed until we first ask for them. The third element in the list has not been used, so we never compute its value.

    As above, we can replace code of the form:

    v = fn(arg1, arg2, ...) # fn() is evaluated here
    
    print(v)
    

    with:

    v = Delay(fn, arg1, arg2, ...)
    
    print(v.value) # fn() is evaluated here
    

    and we can use the lambda keyword to turn an arbitrary expression into a function. So:

    v = {{some expression}} # the expression is evaluated here
    
    print(v)
    

    would become:

    v = Delay(lambda: {{some expression}})
    
    print(v.value) # the expression is evaluated here
    

    So in my program above line 13 could be replaced with:

      v3 = Delay(lambda: len(set(x.count(False) for x in solve(n - 1))) == 1)
    

    and lines 45-49 would be replaced with:

        if n > 2:
          if not check(ss[2], v3.value): continue
    

    Expect the Delay() class to appear in the next version of the enigma.py library (unless I find a better way of doing it).

  3. arthurvause 21 November 2016 at 10:25 am

    Similar to Jim’s first solution, but with memoization.

    from itertools import product
    
    def memoize(fn):
      stored_results = {}
    
      def memoized(*args):
        try:
          return stored_results[args]
        except KeyError:
          result = stored_results[args] = fn(*args)
          return result
    
      return memoized
    
    
    def solutions(n):
      sols = []
      for x in product([True,False],repeat=n):
    
        if x.count(True)>=1 and x.count(False)>=2:
          indexOfAFalseSentence = x.index(True)+1 + [i for i,z in enumerate(x) if not z][1]
          y = [ indexOfAFalseSentence< n and not x[indexOfAFalseSentence] ]
        else:
          y = [ False ]
    
        if x.count(False)>=1 and x.count(True)>=2:
          indexOfATrueSentence = x.index(False)+1 + [i for i,z in enumerate(x) if z][1]
          y.append( indexOfATrueSentence<n and x[indexOfATrueSentence] )
        else:
          y.append( False )
        
        if n>2:
          y.append( len(solutions(n-1)) == 1 )
    
        if n>3:          
          y.append( x.count(True) > x.count(False) )
    
        if n>4:  
          y.append( x[0]==x[1] )
    
        #print "  "*(5-n), n, x, y , "match" if x==tuple(y) else "" 
        if x==tuple(y):
          sols.append( x )
    
      return sols
    
    solutions = memoize(solutions)
    
    for s in solutions(5):
      print s, s.count(False),"False sentences"
    
  4. Brian Gladman 21 November 2016 at 10:01 pm
    from itertools import product
    
    def solve(n, previous_is_unique):
      
      # consider the possible combinations of true and false sentences 
      for bb in product((True, False), repeat=n):
        b = (0,) + bb
        
        # list the statement numbers of true and false statements
        t_n = [i + 1 for i, v in enumerate(bb) if v]
        f_n = [i + 1 for i, v in enumerate(bb) if not v]
                  
        # 1. There is at least one true sentence and at least two false sentences
        # here,  and the number of the first true sentence added to the number of
        # the second  false one gives the number of a sentence which is false.
        if (len(t_n) >= 1 and len(f_n) >= 2 and t_n[0] + f_n[1] in f_n) == b[1]:
        
          # 2. There is at least one false sentence and at least two true sentences
          # here, and the number of the first false sentence added to the number of
          # the second true one gives the number of a sentence which is true.
          if (len(f_n) >= 1 and len(t_n) >= 2 and f_n[0] + t_n[1] in t_n) == b[2]:
          
            # 3. This Enigma would still have a unique answer if the very last of
            # the numbered sentences were deleted.
            if n > 2 and previous_is_unique == b[3]:
          
              # 4. There are more true sentences than false in this list.
              if n > 3 and (len(t_n) > len(f_n)) == b[4]:
           
                # 5. Sentences 1 and 2 are equally true  
                if n > 4 and (b[1] == b[2]) == b[5]:
    
                  yield bb
    
    # find the results for 2, 3, 4 and 5 sentences    
    r2 = list(solve(2, False))
    r3 = list(solve(3, len(r2) == 1))
    r4 = list(solve(4, len(r3) == 1))
    for r5 in solve(5, len(r4) == 1):
      print('{} false sentences: {}.'.format(r5.count(False), r5))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: