Enigmatic Code

Programming Enigma Puzzles

Enigma 662: State of the parties II

From New Scientist #1817, 18th April 1992 [link]

As you can see from my friend’s latest letter, there’s been a general election in Utopia too:

“You will recall that the state of the four parties after the 1989 election was Sinistrals 289, Dextrous 243, Others 36, Indeterminates 32. This remained the case right up to the breakup of the ruling coalition last month, when new elections to the Scitting were held. This time the following occurred:

1. The Sinistrals finished with more seats, the other three parties with less.

2. The Sinistrals lost an equal number of seats to each of the other three parties and gained some seats.

3. The Dextrous and Indeterminate parties both won seats from the Sinistrals only.

4. The relative positions of the parties are unchanged.

5. Each party gained and lost either a perfect square or a perfect cube of seats to finish with either a perfect square or perfect cube number of seats.

6. The total number of seats is unchanged and no other party won a seat.

So now you can work out the new state of the parties.”

Can you?

[enigma662]

7 responses to “Enigma 662: State of the parties II

  1. Jim Randell 6 June 2022 at 7:57 am

    We can think of this puzzle as filling out a 4×4 table, where entry (X, Y) corresponds to the number of voters who voted for X in the first election and Y in the second election.

    The column sums then give us the total for each party in the first election (which we are given), and the row sums give us the total for each party in the second election (which we want to find out). The results of the second election are all squares/cubes.

    We are also told that each of the gains/losses for each party are also a square/cube. Which means the row/column sums, excluding the value that falls on a diagonal are all square/cubes.

    This Python program fills out the table, to give the results in the second election.

    It runs in 67ms. (Internal run time is 3.61ms).

    Run: [ @replit ]

    from enigma import (multiset, union, first, irange, inf, sq, cb, decompose, printf)
    
    # collect answers
    ss = multiset()
    
    # total number of seats
    T = 289 + 243 + 36 + 32
    
    # possible squares and cubes, for final values and gains/losses
    select = lambda f: first((f(x) for x in irange(0, inf)), count=(lambda x: not(x > T)))
    sqcb = sorted(union([select(sq), select(cb)]))
    
    # fill out a row with total a sq/cb in the interval [<a>, <b>)
    # and find <k> values that, along with <x>, sum to a smaller sq/cb
    # return: (<total>, (<value>, ...), <diff between sq/cbs>)
    def row(a, b, k, x=0):
      for t in sqcb:
        if not(t < b): break
        if t < a: continue
        if k == 0:
          if x in sqcb:
            yield (t, (), t - x)
        else:
          for s in sqcb:
            if s > t: break
            for vs in decompose(s - x, k, min_v=0, increasing=0, sep=0):
              yield (t, vs, t - s)
    
    # var XY is "number of voters who voted for X, then Y"
    
    # D and I won seats from S only
    # i.e. SD > 0, OD = 0, ID = 0; SI > 0, DI = 0, OI = 0
    OD = ID = DI = OI = 0
    
    # consider row I (total < 32)
    for (I, [SI], II) in row(0, 32, 1):
      if not(SI > 0): continue
      SD = SO = SI
      # losses for S
      lS = SD + SO + SI
      if lS not in sqcb: continue
      SS = 289 - lS
      # losses for I
      lI = 32 - II
      if lI not in sqcb: continue
    
      # consider row O (I < total < 36)
      for (O, [DO, IO], OO) in row(I + 1, 36, 2, SO):
        # losses for O
        lO = 36 - OO
        if lO not in sqcb: continue
        IS = 32 - ID - IO - II
        OS = 36 - OD - OO - OI
        if IS < 0 or OS < 0: continue
    
        # consider row D (O < D < 243)
        for (D, _, DD) in row(O + 1, 243, 0, SD + OD + ID):
          # losses for D
          lD = 243 - DD
          if lD not in sqcb: continue
          # gains for S
          DS = 243 - DD - DO - DI
          gS = DS + OS + IS
          if gS not in sqcb: continue
          S = SS + gS
          if not(S > 289): continue
          ss.add((S, D, O, I))
    
          # output table
          printf("     S   D   O   I")
          printf("S: {SS:3d} {DS:3d} {OS:3d} {IS:3d} -> [{S:3d}]")
          printf("D: {SD:3d} {DD:3d} {OD:3d} {ID:3d} -> [{D:3d}]")
          printf("O: {SO:3d} {DO:3d} {OO:3d} {IO:3d} -> [{O:3d}]")
          printf("I: {SI:3d} {DI:3d} {OI:3d} {II:3d} -> [{I:3d}]")
          printf()
    
    # output solutions
    for ((S, D, O, I), n) in ss.most_common():
      printf("S={S} D={D} O={O} I={I} [{n} solutions]")
    

    Solution: The results in the second election are: Sinistrals = 343; Dextrous = 216; Others = 25; Indeterminate = 16.

    There are 25 possible tables that correspond to this scenario. Here is one of them:

    • Frits 9 June 2022 at 2:18 pm

      @Jim, my python-constraint program prints 26 solutions.

      Is the following solution incorrect?

       
      262  36  20  25    343
        9 207   0   0    216
        9   0  16   0     25
        9   0   0   7     16
      
      • Jim Randell 9 June 2022 at 2:34 pm

        @Frits: The values you give don’t work as a solution.

        Each of the gains/losses for each party must be a square/cube. And in that example the losses for O (i.e. the number of voters who voted for O in the first election and a party other than O in the second) come to 20. Which is neither a square nor a cube.

  2. Tony McArdle 9 June 2022 at 4:05 am

    Hi Jim, I finally noticed that the current number of votes for Dextrous should be 243 (in the question), as in your program. It makeslife easier.
    Tony Mcardle

  3. Frits 9 June 2022 at 5:54 pm

    Some constraints have been coded as domains.
    The program runs in 50ms.

       
    # https://pypi.org/project/python-constraint/
     
    from constraint import Problem
    
    # collect squares and cubes lower than 600
    sqs_cubs = {x**2 for x in range(25)}
    sqs_cubs |= {x**3 for x in range(1, 9)}
    
    p = Problem()
    
    #      S   D   O   I
    #
    # S -  A   B   C   D    J
    # D -  X   E   0   0    K
    # O -  X   F   G   H    L
    # I -  X   0   0   I    M
    #     --------------
    #     289 243 36  32
    
    # domains
    # A is a multiple of 3 plus one, maximum(3 * X) is 93
    p.addVariables(("A"), range(196, 289, 3))  
    p.addVariables(("B"), range(0, 244))
    p.addVariables(("C"), [x for x in sqs_cubs if x < 37])
    p.addVariables(("D"), range(0, 33))
    p.addVariables(("E"), range(0, 243))
    p.addVariables(("F"), range(0, 36))
    p.addVariables(("G"), range(0, 36))
    p.addVariables(("H"), range(0, 36))
    p.addVariables(("I"), range(0, 32))
    
    # The Sinistrals finished with more seats, the other three parties with less
    p.addVariables(("J"), [x for x in sqs_cubs if x > 289])
    p.addVariables(("K"), [x for x in sqs_cubs if x < 243])
    p.addVariables(("L"), [x for x in sqs_cubs if x < 36])
    p.addVariables(("M"), [x for x in sqs_cubs if x < 32])
    
    # both X and 3 * X are a square/cube 
    p.addVariables(("X"), [x for x in range(1, 32) 
                           if all(y in sqs_cubs for y in [x, 3 * x])])  
    
    # Constraints
    
    # horizontal sums
    p.addConstraint(lambda a, b, c, d, j: a + b + c + d == j, 
                    ("A", "B", "C", "D", "J"))  
    p.addConstraint(lambda x, e, k: x + e == k, ("X", "E", "K"))  
    p.addConstraint(lambda x, f, g, h, l: x + f + g + h == l, 
                    ("X", "F", "G", "H", "L"))  
    p.addConstraint(lambda x, i, m: x + i == m, ("X", "I", "M"))  
    
    # vertical sums
    p.addConstraint(lambda a, x: a + 3 * x == 289, ("A", "X"))  
    p.addConstraint(lambda b, e, f: b + e + f == 243, ("B", "E", "F"))  
    p.addConstraint(lambda c, g: c + g == 36, ("C", "G"))  
    p.addConstraint(lambda d, h, i: d + h + i == 32, ("D", "H", "I"))  
    
    # The total number of seats is unchanged and no other party won a seat
    p.addConstraint(lambda j, k, l, m: j + k + l + m == 600, 
                    ("J", "K", "L", "M"))  
    # The relative positions of the parties are unchanged
    p.addConstraint(lambda j, k, l, m: j > k > l > m, ("J", "K", "L", "M"))
    
    # each of the gains/losses for each party are also a square/cube
    
    # row sums, excluding the diagonal value are all square/cubes
    p.addConstraint(lambda a, j: j - a in sqs_cubs, ("A", "J"))  
    # K - E square/cube means X square/cube, add to domain of X
    p.addConstraint(lambda g, l: l - g in sqs_cubs, ("G", "L"))  
    # M - I square/cube means X square/cube 
    
    # column sums, excluding the diagonal value are all square/cubes
    # 3 * X square/cube, add to domain of X
    p.addConstraint(lambda a: (289 - a) in sqs_cubs, ("A"))  
    # 36 - G square/cube means C square/cube, add to domain of C
    p.addConstraint(lambda i: (32 - i) in sqs_cubs, ("I"))  
    
    
    c = 0
    for ans in p.getSolutions():  
      print(f"{ans['A']:>3} {ans['B']:>3} {ans['C']:>3} {ans['D']:>3}    "
            f"{ans['J']:>3}")
      print(f"{ans['X']:>3} {ans['E']:>3}   0   0    "
            f"{ans['K']:>3}")
      print(f"{ans['X']:>3} {ans['F']:>3} {ans['G']:>3} {ans['H']:>3}    "
            f"{ans['L']:>3}")
      print(f"{ans['X']:>3}   0   0 {ans['I']:>3}    {ans['M']:>3}")
      print("--- --- --- ---")
      print(f"{3 * ans['X'] + ans['A']:>3} {ans['B'] + ans['E'] + ans['F']:>3} "
            f"{ans['C'] + ans['G']:>3} {ans['D'] + ans['H'] + ans['I']:>3}")
      print()
      c += 1
      
    print(c, "solutions") 
    

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 )

Connecting to %s

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

%d bloggers like this: