home *** CD-ROM | disk | FTP | other *** search
/ The Unsorted BBS Collection / thegreatunsorted.tar / thegreatunsorted / programming / misc_programming / solve.awk < prev    next >
Text File  |  1991-05-06  |  1KB  |  54 lines
  1. /^#/ {
  2.     print
  3.     next
  4. }
  5.  
  6. NF > 0 {
  7.     if (start == "")
  8.         start = $1
  9.     end = $1
  10.     $1 = ""
  11.     l[end] = $0
  12. }
  13.  
  14. END {
  15.  
  16.     h[start] = start
  17.     q[1] = start
  18.     n = 1
  19.     m = 2
  20.     while (n < m) {
  21.         s = q[n++]                      #get next item in queue.
  22.         split(l[s], b)                  #get connections
  23.         for (i in b) {
  24.             t = b[i]
  25.             if (!(t in h)) {
  26.                 h[t] = h[s] "-" t
  27.                 if (t in l)
  28.                     q[m++] = t          #add to end of queue
  29.             }
  30.         }
  31.     }
  32.     print "Solution"
  33.     print ""
  34.     if (end in h)
  35.         print h[end]
  36.     else
  37.         print "no route from", start, "to", end
  38.     print ""
  39.     e[start] = ""
  40.     e[end] = ""
  41.     print "How-to-get-here list: Starting at", start
  42.     print ""
  43.     printf "%-20s  %s\n","Location:","Route:"
  44.     for (x in h)
  45.         if (!(x in e))
  46.             printf "%-20s  %s\n",x":",h[x]
  47.     print ""
  48.     print "Inaccessible locations:"
  49.     for (x in l)
  50.         if (!(x in h))
  51.             print x
  52. }
  53.  
  54.