How to resolve the algorithm Word ladder step by step in the 11l programming language

Published on 12 May 2024 09:40 PM
#11l

How to resolve the algorithm Word ladder step by step in the 11l programming language

Table of Contents

Problem Statement

Yet another shortest path problem. Given two words of equal length the task is to transpose the first into the second. Only one letter may be changed at a time and the change must result in a word in unixdict, the minimum number of intermediate words should be used. Demonstrate the following: A boy can be made into a man: boy -> bay -> ban -> man With a little more difficulty a girl can be made into a lady: girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady A john can be made into a jane: john -> cohn -> conn -> cone -> cane -> jane A child can not be turned into an adult. Optional transpositions of your choice.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Word ladder step by step in the 11l programming language

Source code in the 11l programming language

F isOneAway(word1, word2)
   V result = 0B
   L(i) 0 .< word1.len
      I word1[i] != word2[i]
         I result
            R 0B
         E
            result = 1B
   R result

DefaultDict[Int, [String]] words

L(word) File(‘unixdict.txt’).read().split("\n")
   words[word.len] [+]= word

F find_path(start, target)
   V lg = start.len
   assert(target.len == lg, ‘Source and destination must have same length.’)
   assert(start C :words[lg], ‘Source must exist in the dictionary.’)
   assert(target C :words[lg], ‘Destination must exist in the dictionary.’)

   V currPaths = [[start]]
   V pool = copy(:words[lg])

   L
      [[String]] newPaths
      [String] added
      L(candidate) pool
         L(path) currPaths
            I isOneAway(candidate, path.last)
               V newPath = path [+] [candidate]
               I candidate == target
                  R newPath
               E
                  newPaths.append(newPath)
                  added.append(candidate)
                  L.break

      I newPaths.empty
         L.break
      currPaths = move(newPaths)
      L(w) added
         pool.remove(w)

   R [String]()

L(start, target) [(‘boy’, ‘man’), (‘girl’, ‘lady’), (‘john’, ‘jane’), (‘child’, ‘adult’), (‘cat’, ‘dog’), (‘lead’, ‘gold’), (‘white’, ‘black’), (‘bubble’, ‘tickle’)]
   V path = find_path(start, target)
   I path.empty
      print(‘No path from "’start‘" to "’target‘".’)
   E
      print(path.join(‘ -> ’))

You may also check:How to resolve the algorithm Lah numbers step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Append a record to the end of a text file step by step in the Tcl programming language
You may also check:How to resolve the algorithm Rename a file step by step in the DCL programming language
You may also check:How to resolve the algorithm Babbage problem step by step in the C++ programming language
You may also check:How to resolve the algorithm Generic swap step by step in the BASIC programming language