Enigmatic Code

Programming Enigma Puzzles

Enigma 1033: Squirrels up and down

From New Scientist #2189, 5th June 1999

Samantha and Douglas are counting the squirrels visiting their garden. They record the monthly total for each of the 15 months January 1998 to March 1999. Samantha calculates that the number of squirrels is increasing, for she divides the 15 months into three five-month periods and finds the five-month totals are increasing with time. For example, there were more squirrels June to October 1998 than January to May 1998. But Douglas says the number of squirrels is decreasing, for he divides the 15 months into five three-month periods and finds the three-month totals decreasing with time, for example there were fewer squirrels April to June 1998 than January to March 1998.

1. Could there have been a total of 4 squirrels for the two months April and May 1998 and fewer than 75 squirrels for the whole of the 15 months? If so, how many squirrels were there for the 15 months?

2. Could there have been a total of 5 squirrels for the two months April and May 1998 and a total of fewer than 65 squirrels for the 15 months?

3. Could there have been 107 squirrels in June 1998 and 100 squirrels in October 1998? If so, how many squirrels were there in the 15 months?

4. Could there have been 108 squirrels in June 1998 and 100 squirrels in October 1998? If so, how many squirrels were there in the 15 months?

[enigma1033]

2 responses to “Enigma 1033: Squirrels up and down

  1. Jim Randell 7 December 2018 at 7:48 am

    I used MiniZinc models for each of the four questions. As they are all similar I wrote a Python program to generate and execute them using the minizinc.py wrapper.

    This Python 3 program executes in 469ms.

    from minizinc import MiniZinc
    from enigma import join, printf
    
    def solve(name, condition, solver="mzn-gecode -a"):
    
      model = f"""
    
      % count the number of visits
      var int: A; % months [1,2,3]
      var int: B; % months [4,5]
      var int: C; % months [6]
      var int: D; % months [7,8,9]
      var int: E; % months [10]
      var int: F; % months [11,12]
      var int: G; % months [13,14,15]
      var int: T = A + B + C + D + E + F + G; % total
    
      % number of visits is non-negative
      constraint forall (x in [A, B, C, D, E, F, G]) (not(x < 0));
    
      % S calculates the number of visits is increasing, using 5 month chunks
      constraint A + B < C + D + E /\ C + D + E < F + G;
    
      % D calculate the number of visits is decreasing, using 3 month chunks
      constraint A > B + C /\ B + C > D /\ D > E + F /\ E + F > G;
    
      % additional conditions
      constraint {condition};
    
      solve satisfy;
      """
    
      p = MiniZinc(model, solver=solver)
    
      n = 0
      for (A, B, C, D, E, F, G) in p.solve(result="A B C D E F G"):
        T = A + B + C + D + E + F + G
        printf("{name}: T={T} [A={A} B={B} C={C} D={D} E={E} F={F} G={G}]")
        n += 1
      if n == 0:
        printf("{name}: UNSATISFIABLE")
      return n
    
    solve("Q1", "B = 4 /\ T < 75")
    solve("Q2", "B = 5 /\ T < 65")
    solve("Q3", "C = 107 /\ E = 100")
    solve("Q4", "C = 108 /\ E = 100")
    

    Solution: (1) No; (2) Yes. 60 total visits; (3) No; (4) Yes. 1560 total visits.

    I split the time period into:

    A = Jan 98, Feb 98, Mar 98
    B = Apr 98, May 98
    C = Jun 98
    D = Jul 98, Aug 98, Sep 98
    E = Oct 98
    F = Nov 98, Dec 98
    G = Jan 99, Feb 99, Mar 99

    Then S sees increasing visits using 5 month chunks:

    A + B < C + D + E < F + G

    and D sees decreasing visits using 3 month chunks:

    A > B + C > D > E + F > G

    There is a solution for question (2) when:

    A=14 B=5 C=8 D=12 E=0 F=11 G=10, total = 60

    Which gives:

    19 < 20 < 21
    14 > 13 > 12 > 11 > 10

    Adding 100 visits to each month then gives a solution for question (4):

    A=314 B=205 C=108 D=312 E=100 F=211 G=310, total = 1560

    and these are the only solutions.

    • Jim Randell 8 December 2018 at 9:50 am

      There are two cases to consider:

      Q1 & Q2: B is known, and there is an upper bound on the total.
      Q3 & Q4: C and E are known.

      By manipulating the inequalities we can come up with bounded expressions for the unknown variables.

      Here is a Python program bases on this approach. It runs in 75ms.

      Run: [ @repl.it ]

      from enigma import irange, divc, divf, printf
      
      # solve for a given B and T < M:
      #
      #   3B / 2 < A
      #   (2A - B) / 4 < C < A - B
      #   (2A + 2B - C) / 3 < D < B + C
      #   A + B - C - D < E < (D - C) / 2
      #   (C + D) / 2 < F < D - E
      #   C + D + E - F < G < E + F
      #
      def solve1(q, B, M):
        for A in irange(divc(3 * B + 1, 2), M - B - 4):
          for C in irange(divc(2 * A - B + 1, 4), min(A - B - 1, M - A - B - 3)):
            for D in irange(divc(2 * (A + B) - C + 1, 3), min(B + C - 1, M - A - B - C - 3)):
              for E in irange(max(A + B - C - D + 1, 0), min(divf(D - C - 1, 2), M - A - B - C - D - 1)):
                for F in irange(divc(C + D + 1, 2), min(D - E - 1, M - A - B - C - D - E - 1)):
                  for G in irange(C + D + E - F + 1, min(E + F - 1, M - A - B - C - D - E - F - 1)):
                    T = A + B + C + D + E + F + G
                    printf("[{q}] A={A} B={B} C={C} D={D} E={E} F={F} G={G}, T={T}")
      
      # solve for given C and E:
      #
      #   C + 2E < A < 2C + E
      #   2E < B < A - C
      #   C + 2E < D < B + C
      #   (C + D) / 2 < F < D - E
      #   C + D + E - F < G < E + F
      #
      def solve2(q, C, E):
        for A in irange(C + 2 * E + 1, 2 * C + E - 1):
          for B in irange(2 * E + 1, A - C - 1):
            for D in irange(C + 2 * E + 1, B + C - 1):
              if not(A + B < C + D + E): continue
              for F in irange(divc(C + D + 1, 2), D - E - 1):
                for G in irange(C + D + E - F + 1, E + F - 1):
                  T = A + B + C + D + E + F + G
                  printf("[{q}] A={A} B={B} C={C} D={D} E={E} F={F} G={G}, T={T}")
      
      
      solve1("Q1", 4, 75)
      solve1("Q2", 5, 65)
      solve2("Q3", 107, 100)
      solve2("Q4", 108, 100)
      

      Note that in the standard implementation of Python you cannot go on nesting [[ for ]] loops indefinitely. There is a hard coded limit of 20 nested blocks in the Python interpreter. Although this restriction does not seem to apply to the PyPy implementation.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: