chiark - git - mdw - wordchain/blob - chain.python

   1 #! /usr/bin/python3
   2
   3 import sys as SYS
   4
   5 class Node (object):
   6   __slots__ = ["word", "len", "up", "down", "right"];
   7   def __init__(me, word):
   8     me.word = word
   9     me.len = 1
  10     me.up = me.down = me.right = None
  11
  12 WORDS = dict()
  13
  14 for line in SYS.stdin:
  15   line = line.rstrip("\n")
  16   WORDS[line] = Node(line)
  17
  18 MAX = 0; WINNERS = []
  19 for node in WORDS.values():
  20   word = node.word; wlen = len(word)
  21   if wlen <= 1: continue
  22   parent = WORDS.get(word[:wlen - 1])
  23   if not parent: continue
  24   node.up = parent; nlen = node.len
  25   while True:
  26     if parent is None:
  27       if nlen >= MAX:
  28         if nlen > MAX: MAX = nlen; WINNERS = []
  29         WINNERS.append(node)
  30       break
  31     plen = parent.len; nlen += 1
  32     if plen > nlen:
  33       break
  34     elif plen == nlen:
  35       node.right = parent.down; parent.down = node
  36       break
  37     else:
  38       parent.down = node; node.right = None
  39       parent.len = nlen
  40       node = parent; parent = node.up
  41   if nlen > MAX: MAX = nlen
  42
  43 def print_chain(node):
  44   if node.right is None:
  45     SYS.stdout.write(node.word)
  46     if node.down:
  47       SYS.stdout.write(" "); print_chain(node.down)
  48   else:
  49     SYS.stdout.write("{ ")
  50     while True:
  51       SYS.stdout.write(node.word)
  52       if node.down:
  53         SYS.stdout.write(" "); print_chain(node.down)
  54       node = node.right
  55       if node is None: break
  56       SYS.stdout.write(" | ")
  57     SYS.stdout.write(" }")
  58
  59 for node in WINNERS: print_chain(node); SYS.stdout.write("\n")