S2T2

Jim Randell 4:36 pm on 11 November 2022 Permalink Reply
Tags: by: Edmund Marshall ( 10 )   

• 

  Jim Randell 5:12 pm on 11 November 2022 Permalink | Reply

  This Python program runs in 51ms. (Internal runtime is 554µs).

  Run: [ @replit ]

  from enigma import (primes, append, tuples, printf)
  
  # possible term lengths
  terms = set(primes.between(0, 30))
  
  # select <k> years from <years>
  # return (<start-years>, <term-lengths>)
  def solve(k, years, ys=[], ts=[]):
    # are we done?
    if k == 0:
      # no-one served more than 30 years
      if ys and ys[-1] > 1968:
        yield (ys, ts)
    elif not k > len(years):
      # choose the next year
      for (i, y) in enumerate(years):
        # consider possible term lengths
        g = y - ys[-1]
        for t in terms.intersection({g, g - 1}):
          if t in ts: continue
          # solve for the remaining years
          yield from solve(k - 1, years[i + 1:], append(ys, y), append(ts, t))
  
  # consider the start year of the incumbent at the start of the century
  for y0 in primes.between(1870, 1901):
    # fill out the 8 starting years in the 20th century
    years = list(primes.between(max(y0 + 1, 1901), 2000))
    years.remove(1973)  # but not 1973
    for (ys, ts) in solve(8, years, [y0]):
      # output solution
      for ((y1, y2), t) in zip(tuples(ys, 2), ts):
        printf("{y1} - {y2} = {t} years")
      printf("{y2} - .... = ? years")
      printf()
  

  Solution: The years are: 1901, 1907, 1931, 1949, 1979, 1993, 1997, 1999.

  The incumbent at the start of the 20th century began office in 1889, so we have:

  1. 1889 – 1901 = 11 years
  2. 1901 – 1907 = 5 years
  3. 1907 – 1931 = 23 years
  4. 1931 – 1949 = 17 years
  5. 1949 – 1979 = 29 years
  6. 1979 – 1993 = 13 years
  7. 1993 – 1997 = 3 years
  8. 1997 – 1999 = 2 years
  9. 1999 – …. = (7 or 19 years)

  There are two primes left that could correspond to the length of the term of the incumbent at the end of the 20th century. Note that it is not required that the term of the successor (if any) starts in a prime year.

  LikeLike

  • 

    Frits 1:24 pm on 12 November 2022 Permalink | Reply

    @Jim, as I don’t have access to a PC I can’t publish/test a program myself.

    I think a check is needed to see if the last Prime Minister can serve a prime number of years and which ends after the 20th century (if high prime numbers already have been used this may not be possible anymore).

    LikeLike

    • 

      Hugh Casement 7:17 am on 13 November 2022 Permalink | Reply

      Frits, the wording of the puzzle is vague on that score, but I think if we do allow the last term of office to extend beyond the end of the century then we get multiple solutions. Jim (line 25) would seem to agree with me that we need to start looking before the beginning of the century.

      LikeLike

    • 

      Jim Randell 8:18 am on 13 November 2022 Permalink | Reply

      @Frits: I did wonder about that. I check the final PM of the 20th century does not have a term that is longer than 30 years (line 12), and when I saw that there was only a single possible solution I didn’t worry about the actual length of the term, as it starts very close to the end of the century, and there are 2 unused primes available.

      Here is the code with an extra check to ensure the final term length is possible. (I also include code to specify the first and last years of the 20th century. I am using the “strict” definition 1901-2000, but you get the same answer with the “popular” usage of 1900-1999).

      Run: [ @replit ]

      from enigma import (primes, append, tuples, printf)
      
      # first/last years for 20th century
      (first, last) = (1901, 2000)
      
      # possible term lengths
      terms = set(primes.between(0, 30))
      
      # select <k> years from <years>
      # return (<start-years>, <term-lengths>)
      def solve(k, years, ys=[], ts=[]):
        # are we done?
        if k == 0:
          yield (ys, ts)
        elif not k > len(years):
          # choose the next year
          for (i, y) in enumerate(years):
            # consider possible term lengths
            g = y - ys[-1]
            for t in terms.intersection({g, g - 1}):
              if t in ts: continue
              # solve for the remaining years
              yield from solve(k - 1, years[i + 1:], append(ys, y), append(ts, t))
      
      # consider the start year of the incumbent at the start of the century
      for y0 in primes.between(first - 31, first):
        # fill out the 8 starting years in the 20th century
        years = list(primes.between(max(y0 + 1, first), last))
        years.remove(1973)  # but not 1973
        for (ys, ts) in solve(8, years, [y0]):
          # check possible term lengths for the incumbent at the end of the century
          fs = sorted(t for t in terms.difference(ts) if ys[-1] + t > last)
          if not fs: continue
          # output solution
          for ((y1, y2), t) in zip(tuples(ys, 2), ts):
            printf("{y1} - {y2} = {t} years")
          printf("{y2} - .... = {fs} years")
          printf()
      

      But it seems that it may be possible that the final PM is still in office at the time the puzzle was set (having served less than 30 years so far), so we can’t say what the length of the term will be yet.

      LikeLike