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         var winners *wordnode = nil; winners_tail := &winners
  47         for word, node := range words {
  48                 wlen := len(word)
  49                 if wlen <= 1 { continue }
  50                 parent := words[word[:wlen - 1]]
  51                 if parent == nil { continue }
  52                 node.up = parent
  53                 nlen := node.len
  54                 for {
  55                         if parent == nil {
  56                                 if nlen >= max {
  57                                         if nlen > max {
  58                                                 max = nlen
  59                                                 *winners_tail = nil
  60                                                 winners_tail = &winners
  61                                         }
  62                                         *winners_tail = node
  63                                         winners_tail = &node.right
  64                                 }
  65                                 break
  66                         }
  67                         nlen += 1; plen := parent.len
  68                         if plen > nlen {
  69                                 break
  70                         } else if plen == nlen {
  71                                 node.right = parent.down; parent.down = node
  72                                 break
  73                         }
  74                         parent.down = node; node.right = nil
  75                         parent.len = nlen
  76                         node = parent; parent = node.up
  77                 }
  78         }
  79
  80         *winners_tail = nil
  81         var next *wordnode
  82         for node := winners; node != nil; node = next {
  83                 next = node.right; node.right = nil
  84                 print_chain(node); fmt.Printf("\n")
  85         }
  86 }