Enigmatic Code

Programming Enigma Puzzles

Tantalizer 491: Cats and dogs

From New Scientist #1042, 10th March 1977 [link]

Six proud but ill-acquainted owners were to be heard exchanging remarks at the village pet show. I noted down some of them and off you a brief selection:

Amble to Bumble: “Dimwit keeps a dog”.

Bumble to Crumble: “Egghead and Fumble have pets of the same sort”.

Crumble to Amble: “Bumble’s pet is not the same sort as yours”.

Dimwit to Egghead: “Bumble has the smelliest dog in the village”.

Egghead to Bumble: “Crumble keeps a dog”.

Fumble to Dimwit: “Crumble’s pet is not the same sort as mine.”

Each man has a cat or a dog (not both) and has spoken the truth if and only if addressing someone with the same sort of pet. “Same sort” means merely cat or dog — finer distinctions, such as that between collie and corgi, do not count.

Who owns what?

[tantalizer491]

Advertisements

One response to “Tantalizer 491: Cats and dogs

  1. Jim Randell 8 February 2017 at 8:28 am

    This code consider all possible pet ownership scenarios (including, if he has a dog, whether Bumble’s dog is (objectively) the smelliest dog in the village or not). It runs in 42ms.

    from itertools import product
    from enigma import printf
    
    # identify the pets
    pets = (cat, dog) = ('cat', 'dog')
    
    # check statement s from X to Y
    def check(X, Y, s):
      return (X == Y) == s
    
    # choose a pet for each owner
    for (A, B, C, D, E, F) in product(pets, repeat=6):
    
      # check statements 1, 2, 3, 5, 6
      if not all((
    
        # 1. A to B: "D has a dog"
        check(A, B, D == dog),
    
        # 2. B to C: "E and F have pets of the same sort"
        check(B, C, E == F),
    
        # 3. C to A: "B's pet is not the same sort as A's"
        check(C, A, B != A),
    
        # 5. E to B: "C has a dog"
        check(E, B, C == dog),
    
        # 6. F to D: "C's pet is not the same sort as F's"
        check(F, D, C != F)
    
      )): continue
    
      # "B has the smelliest dog in the village"
      for smellyB in ([True, False] if B == dog else [False]):
    
        # check statement 4. D to E: "B has the smelliest dog in the village"
        if not check(D, E, smellyB): continue
    
        printf("A={A} B={B} C={C} D={D} E={E} F={F} [smellyB={smellyB}]")
    

    Solution: Amble has a dog; Bumble has a dog (which is not the smelliest dog in the village); Crumble has a cat; Dimwit has a dog; Egghead has a cat; Fumble has a dog.

    We see that for statement 4, when D (a dog owner) states to E (a cat owner) that “B has the smelliest dog in the village”, he is uttering a falsehood. But B does own a dog, so it cannot be the smelliest in the village.

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: