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
  19 for node in WORDS.values():
  20   word = node.word; wlen = len(word)
  21   if wlen <= 1: parent = None
  22   else: parent = WORDS.get(word[:wlen  -1])
  23   node.up = parent; nlen = node.len
  24   while parent is not None:
  25     plen = parent.len; nlen += 1
  26     if plen > nlen:
  27       break
  28     elif plen == nlen:
  29       node.right = parent.down; parent.down = node
  30       break
  31     else:
  32       parent.down = node; node.right = None
  33       parent.len = nlen
  34       node = parent; parent = node.up
  35   if nlen > MAX: MAX = nlen
  36
  37 def print_chain(node):
  38   if node.right is None:
  39     SYS.stdout.write(node.word)
  40     if node.down:
  41       SYS.stdout.write(" "); print_chain(node.down)
  42   else:
  43     SYS.stdout.write("{ ")
  44     while True:
  45       SYS.stdout.write(node.word)
  46       if node.down:
  47         SYS.stdout.write(" "); print_chain(node.down)
  48       node = node.right
  49       if node is None: break
  50       SYS.stdout.write(" | ")
  51     SYS.stdout.write(" }")
  52
  53 for node in WORDS.values():
  54   if node.len == MAX: print_chain(node); SYS.stdout.write("\n")