S2T2

Jim Randell 8:35 am on 11 March 2021 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 8:36 am on 11 March 2021 Permalink | Reply

  In upper case the only symbol that can be used for more than one letter is M/W, but W does not appear in the words we are interested in, so we can consider all the symbols to be unique. (In a standard font anyway).

  This Python program finds sets of dice that can make the maximum number of months, and then looks for sets that have a die with 4 vowels on. It runs in 1.18s.

  Run: [ @repl.it ]

  from enigma import (subsets, Accumulator, first, diff, join, printf)
  
  vowels = set('AEIOU')
  months = "JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC".split()
  
  # merge the symbols <ss> to the dice <ds>
  def merge(ds, ss):
    rs = list()
    for (d, s) in zip(ds, ss):
      if s in d:
        rs.append(d)
      elif len(d) == 6:
        return
      else:
        rs.append(d + [s])
    return rs
  
  # add words from <ws> to dice in <ds>
  # return (<dice>, <number-of-words-remaining>)
  def solve(ds, ws):
    # result so far
    yield (ds, len(ws))
    if ws:
      # put letters for the next word on the dice
      for ss in subsets(ws[0], size=len, select="mP"):
        ds_ = merge(ds, ss)
        if ds_:
          yield from solve(ds_, ws[1:])
  
  # start with the first month
  ds0 = list([x] for x in months[0])
  
  # find dice with the fewest remaining words
  r = Accumulator(fn=min, collect=1)
  for (ds, n) in solve(ds0, months[1:]):
    r.accumulate_data(n, ds)
  
  # output result
  printf("months = {ms} [{n} sets of dice]",
    ms=join(first(months, len(months) - r.value), sep=" ", enc="[]"),
    n=len(r.data),
  )
  
  # look for solutions with 4 vowels on one die
  fmt = lambda d: join(d, sep=" ", enc="[]") # format a die
  for ds in r.data:
    ds = sorted(sorted(d) for d in ds)
    # find dice with (exactly) 4 vowels
    vs = list(d for d in ds if len(vowels.intersection(d)) == 4)
    if not vs: continue
    printf("dice = {ds}", ds=join((fmt(d) for d in ds), sep=" "))
    for d in vs:
      printf("-> {d} has 4 vowels; consonants = {c}", d=fmt(d), c=fmt(diff(d, vowels)))
  

  Solution: (a) The last month you would be able to display is OCT. (b) The consonants on the die with 4 vowels are R and Y.

  There are 108 sets of dice that can make JAN … OCT, but only 4 of them have a die with 4 vowels on:

  [A B L N S T] [A E O R U Y] [C F G J M P]
  [A B C L N S] [A E O R U Y] [F G J M P T]
  [A E O R U Y] [A F L N S T] [B C G J M P]
  [A C F L N S] [A E O R U Y] [B G J M P T]

  In each case the die with 4 vowels is: [A E O U] + [R Y]

  We can see that the vowel I does not occur in any of the words, so the four vowels must be [A E O U], and setting the middle die in our initial set of dice (line 31) to have these 4 symbols on to start with finds just the four sets of dice given above, and runs in 401ms.

  ---

  However, if we were to use lower case letters, then there are useful symbols that can be used for more than one letter:

  b / q
  d / p
  n / u

  And by replacing lines 3-4 with:

  vowels = set('aeion')
  months = ['jan', 'feb', 'mar', 'adr', 'may', 'jnn', 'jnl', 'ang', 'sed', 'oct', 'nov', 'dec']
  

  We find there are 10 sets of dice that can make all twelve months. (But none of them have a die containing 4 vowel symbols, so remove line 50 if you want to see them).

  LikeLike

• 

  Hugh Casement 1:38 pm on 11 March 2021 Permalink | Reply

  If we cheat by using upper-case U turned sideways to make C, will that allow us to make DEC?

  LikeLike

  • 

    Jim Randell 1:51 pm on 11 March 2021 Permalink | Reply

    @Hugh: It doesn’t let us get to DEC (we can’t fit a D in), but it means we don’t need a C to make OCT, so we free up a letter, which can be V, so we can get as far as NOV.

    If we can also use an upside down A to make a V, then we can fit the D in and get to DEC.

    I think there is scope for using specialised fonts that would allow some symbols to serve as multiple letters.

    LikeLike

• 

  Hugh Casement 5:40 pm on 11 March 2021 Permalink | Reply

  Thanks, Jim. I was going to suggest turning the A upside down, though it’s possibly a worse cheat!

  I’m sure I’ve come across a variant of this puzzle, possibly by Martin Gardner. I have a vague recollection that all the months could be done except AUG which wasn’t needed because it was during the university long vacation.

  LikeLike

  • 

    Jim Randell 8:45 pm on 14 March 2021 Permalink | Reply

    @Hugh: Removing AUG from the list in my program finds 6 sets of dice that can make the remaining 11 months.

    Also removing FEB has 30 sets of dice that can make the remaining 11 months, and 2 of the sets also have 4 vowels on one die.

    LikeLike

• 

  Frits 1:54 pm on 12 March 2021 Permalink | Reply

  # place the 4 vowels A, E, O and U on die number 2
  #
  # As either A or U also has to be on die 1 or 3 (in order to form AUG)
  # there are only 18 -5 = 13 spots left for consonants
  
  months = ['JAN', 'FEB', 'MAR', 'APR', 'MAY', 'JUN', 
            'JUL', 'AUG', 'SEP', 'OCT', 'NOV', 'DEC']
  
  s = set()
  for j in range(12):
    lets = "".join([x for x in months[j] if x not in "AEOU"])
    s = s | set(lets)
    print (f"{months[j]}: {len(list(s))} consonants {''.join(s)} ")
  
  # JAN: 2 consonants JN
  # FEB: 4 consonants JNFB
  # MAR: 6 consonants JNFBMR
  # APR: 7 consonants JNFBMRP
  # MAY: 8 consonants JNFBMRPY
  # JUN: 8 consonants JNFBMRPY
  # JUL: 9 consonants JNFBMRPYL
  # AUG: 10 consonants JNFBMRPYLG
  # SEP: 11 consonants JNFBMRPYLGS
  # OCT: 13 consonants JNFBMRPYLGSCT
  # NOV: 14 consonants JNFBMRPYLGSCTV
  # DEC: 15 consonants JNFBMRPYLGSCTVD
  #
  # so NOV and DEC can't be the last month to be displayed
  #
  # Assume last month to be displayed is OCT
  #
  # letter pairs on dice 1 and 3 but not on the same die (no order):
  # v,G + F,B + C,T + S,P (E only on die 2) + J,N (because JUN and JAN)
  # where v is A or U (extra vowel)
  #
  # suppose v = U -> in same group: P and M (APR and MAR), R and Y (MAR and MAY)
  # this is impossible as group 1 and 3 already have 5 candidates
  #
  # suppose v = A 
  # candidates for 2 empty spots on die 2: 
  # NOT: F,B + C,T + S,P + J,N + G + L (as U only on die 2)
  # leaving R, M, Y
  #  -- suppose M and R on die 2: --> we can't form MAR anymore
  #  -- suppose M and Y on die 2: --> we can't form MAY anymore
  #  -- suppose R and Y on die 2: --> no inconsistency
  
  # place A on die 1
  
  # die 1: A  .  .  .  .  .
  # die 2: A  E  O  U  R  Y
  # die 3: .  .  .  .  .  .
  
  # P must be on die 3 (APR) --> S on die 1
  # M must be on die 3 (MAR)
  # G must be on die 3 (AUG)
  # L must be on die 1 (as F,B + C,T + J,N are pairs)
  # J must be on die 3 (as L is on die 1) --> N on die 1
  
  # die 1: A  S  L  N  .  .
  # die 2: A  E  O  U  R  Y
  # die 3: P  M  G  J  .  .
  
  # this leaves 4 ways to place B, F, C and T
  
  for x in ("BF", "FB"):
    for y in ("CT", "TC"):
      print("A S L N", x[0], y[0], end="  -  ")
      print("A  E  O  U  R  Y", end="  -  ")
      print("P  M  G  J", x[1], y[1])
  
  # A S L N B C  -  A  E  O  U  R  Y  -  P  M  G  J F T
  # A S L N B T  -  A  E  O  U  R  Y  -  P  M  G  J F C
  # A S L N F C  -  A  E  O  U  R  Y  -  P  M  G  J B T
  # A S L N F T  -  A  E  O  U  R  Y  -  P  M  G  J B C
  

  LikeLike

• 

  Hugh Casement 5:45 pm on 12 March 2021 Permalink | Reply

  I still don’t know who published the no-August variant, or where, but I’ve found the solution scribbled in the margin of a book. It’s a wee bit shorter than the proof of Fermat’s last theorem: the three cubes bear the letters
  A B C S U V, D F J M O P, E L N R T Y
  With two further cubes we can make the numbers 01 to 31:
  0 1 2 3 4 5, 0 1 2 6 (which also serves as 9), 7, 8.

  LikeLike