fivethirtyeight.com The Riddler solution for Sept 13, 2019

abbreviations.py

#!/usr/bin/python

from collections import defaultdict

_ABBRS = [
    'AK', 'AL', 'AR', 'AS', 'AZ', 'CA', 'CO', 'CT', 'DC', 'DE', 'FL', 'FM',
    'GA', 'GU', 'HI', 'IA', 'ID', 'IL', 'IN', 'KS', 'KY', 'LA', 'MD', 'MA',
    'ME', 'MH', 'MI', 'MN', 'MO', 'MP', 'MS', 'MT', 'NC', 'ND', 'NE', 'NH',
    'NJ', 'NM', 'NV', 'NY', 'OH', 'OK', 'OR', 'PA', 'PR', 'PW', 'RI', 'SC',
    'SD', 'TN', 'TX', 'UT', 'VA', 'VI', 'VT', 'WA', 'WI', 'WV', 'WY',
]

class Node:
  def __init__(self, abbreviation, out_edges):
    self.abbreviation = abbreviation
    self.out_edges = out_edges

  def __str__(self):
    return '%s:[%s]' % (self.abbreviation, ','.join(self.out_edges))

class StateAbbrs:
  def __init__(self):
    abbreviations_by_initial = defaultdict(list)
    for abbr in _ABBRS:
      abbreviations_by_initial[abbr[0]].append(abbr)

    self.graph = {}
    for abbr in _ABBRS:
      out_edges = [a for a in abbreviations_by_initial[abbr[1]]]
      self.graph[abbr] = Node(abbr, out_edges)

    self.out_counters = defaultdict(int)
    self.length_counts = defaultdict(dict)
    self.longest_strings = defaultdict(str)

  def Run(self):
    for abbreviation in _ABBRS:
      self.StartRunFromNode(abbreviation)

    print
    print 'NUMBER OF PATHS EXPLORED FOR ALL ABBREVIATIONS'
    print '------------------------------------------------------'
    for abbreviation in _ABBRS:
      print 'Starting from', abbreviation, ":", self.out_counters[abbreviation]

    print
    print 'NUMBER OF STRINGS OF EACH LENGTH FOR ALL ABBREVIATIONS'
    print '------------------------------------------------------'
    for abbreviation in _ABBRS:
      print 'Starting from', abbreviation, ":"
      for (length, count) in self.length_counts[abbreviation].items():
        print '  Length', length, ':', count

    print
    print 'LONGEST FOR ALL ABBREVIATIONS'
    print '-----------------------------'
    for abbreviation in _ABBRS:
      print 'Longest for', abbreviation, ':', self.longest_strings[abbreviation]

    longest_length = None
    best_abbreviations = []
    for (abbreviation, longest_string) in self.longest_strings.items():
      current_length = len(longest_string)
      if current_length > longest_length:
        longest_length = current_length
        best_abbreviations = [abbreviation]
        continue

      if current_length == longest_length:
        best_abbreviations.append(abbreviation)

    print
    print 'Best abbreviation(s):'
    print '---------------------'
    for abbreviation in best_abbreviations:
      print abbreviation, ':', self.longest_strings[abbreviation]

  def StartRunFromNode(self, abbreviation):
    self.start = abbreviation
    self.visited = set()
    self.sequence = []
    self.strings = defaultdict(set)

    self.RunFromNode(abbreviation)

    for (length, string_set) in self.strings.items():
      self.length_counts[abbreviation][length] = len(string_set)

  def RunFromNode(self, abbreviation):
    self.visited.add(abbreviation)
    self.sequence.append(abbreviation)

    current_sequence = [abbreviation[0] for abbreviation in self.sequence]
    if self.sequence:
      current_sequence.append(self.sequence[-1][1])
    current_string = ''.join(current_sequence)
    current_len = len(current_string)
    self.strings[current_len].add(current_string)
    self.AddStringAndSequence(self.start, current_string)

    self.out_counters[self.start] += 1
    if self.out_counters[self.start] % 5000 == 0:
      print
      print 'Counter:', self.out_counters[self.start]
      print '--------------------------------------'
      print 'From start', self.start
      print 'Exploring', abbreviation
      print 'Current string', current_string
      print 'Current best string:', self.longest_strings[self.start]
      print

    for out_edge in self.graph[abbreviation].out_edges:
      if out_edge in self.visited:
        continue

      self.RunFromNode(out_edge)

    self.visited.remove(abbreviation)
    if self.sequence:
      self.sequence.pop()

  def AddStringAndSequence(self, abbreviation, current_string):
    if len(current_string) <= len(self.longest_strings[abbreviation]):
      return

    print 'New longest for', abbreviation, ':', current_string

    self.longest_strings[abbreviation] = current_string


abbrs = StateAbbrs()
abbrs.Run()