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

   1 /* -*-go-*- */
   2
   3 package main
   4
   5 import ("bufio"; "fmt"; "os")
   6
   7 type wordnode struct {
   8         word *string
   9         len int
  10         up, down, right *wordnode
  11 }
  12
  13 func print_chain(node *wordnode) {
  14         if node.right == nil {
  15                 fmt.Printf("%s", *node.word)
  16                 if node.down != nil {
  17                         fmt.Printf(" ")
  18                         print_chain(node.down)
  19                 }
  20         } else {
  21                 fmt.Printf("{ ")
  22                 for {
  23                         fmt.Printf("%s", *node.word)
  24                         if node.down != nil {
  25                                 fmt.Printf(" ")
  26                                 print_chain(node.down)
  27                         }
  28                         node = node.right
  29                         if node == nil { break }
  30                         fmt.Printf(" | ")
  31                 }
  32                 fmt.Printf(" }")
  33         }
  34 }
  35
  36 func main() {
  37         words := make(map[string] *wordnode)
  38
  39         scanner := bufio.NewScanner(os.Stdin)
  40         for scanner.Scan() {
  41                 word := scanner.Text()
  42                 words[word] = &wordnode { &word, 1, nil, nil, nil }
  43         }
  44
  45         max := 0
  46         for word, node := range words {
  47                 wlen := len(word)
  48                 if wlen <= 1 { continue }
  49                 parent := words[word[:wlen - 1]]
  50                 node.up = parent
  51                 for parent != nil {
  52                         nlen := node.len + 1
  53                         plen := parent.len
  54                         if nlen < plen {
  55                                 break
  56                         } else if nlen > plen {
  57                                 parent.down = nil
  58                                 parent.len = nlen
  59                                 if nlen > max { max = nlen }
  60                         }
  61                         if parent.down != node {
  62                                 node.right = parent.down; parent.down = node
  63                         }
  64                         node = parent; parent = node.up
  65                 }
  66         }
  67
  68         for _, node := range words {
  69                 if node.len == max { print_chain(node); fmt.Printf("\n") }
  70         }
  71 }