{"id":3589,"date":"2025-01-04T19:17:25","date_gmt":"2025-01-04T13:47:25","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=3589"},"modified":"2025-01-04T19:17:25","modified_gmt":"2025-01-04T13:47:25","slug":"word-transformation-puzzle-part-2-implementation-in-common-lisp","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2025\/01\/04\/word-transformation-puzzle-part-2-implementation-in-common-lisp\/","title":{"rendered":"Word Transformation Puzzle – Part 2: Implementation in Common Lisp"},"content":{"rendered":"

In the last article<\/strong><\/em><\/a>\u00a0I discussed an interesting word puzzle and showed how to solve it using Prolog<\/strong><\/em>. Here is the problem statement:<\/p>\n

\n

\u201cYou are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at a time. The additional constraint is that each intermediate step must be a valid word.\u201d<\/span><\/p>\n<\/blockquote>\n

As I had mentioned in that article, the solution can be implemented in any programming language. In today\u2019s article, I want to share the Lisp<\/strong><\/em> implementation.<\/p>\n

Let us start with a simple dictionary. We need a helper function that returns all possible \u201cnext\u201d<\/strong><\/em> words, given one word. Here is the code:<\/p>\n

\"Getting<\/a>
Getting Word Neighbors<\/strong><\/figcaption><\/figure>\n

We then use this function to find the chain:<\/p>\n

\"Finding<\/a>
Finding Word Chain<\/strong><\/figcaption><\/figure>\n

The function returns “<\/strong>Nil”<\/strong><\/em> if a valid chain cannot be found, else it returns the successive words, starting from the initial word, as a list.<\/p>\n

Here is the output for a few start and end words:<\/p>\n

\"Program<\/a>
Program Output<\/strong><\/figcaption><\/figure>\n

As you can see, the implementation is quite straightforward. You can download the code here.<\/strong><\/em><\/a><\/p>\n

Have a wonderful 2025!<\/p>\n","protected":false},"excerpt":{"rendered":"

In the last article\u00a0I discussed an interesting word puzzle and showed how to solve it using Prolog. Here is the problem statement: \u201cYou are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at a time. The additional constraint is that […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,17],"tags":[110,410],"class_list":["post-3589","post","type-post","status-publish","format-standard","hentry","category-lisp","category-programming","tag-common-lisp","tag-word-puzzle"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-VT","jetpack-related-posts":[{"id":3573,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/12\/17\/using-prolog-to-solve-the-word-transformation-puzzle\/","url_meta":{"origin":3589,"position":0},"title":"Using Prolog to Solve the Word Transformation Puzzle","author":"admin","date":"December 17, 2024","format":false,"excerpt":"In today\u2019s article, I want to share an interesting word puzzle, and then show how to solve it in Prolog. Here is the puzzle: You are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"Our Dictionary","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/12\/prolog1-300x280.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":534,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","url_meta":{"origin":3589,"position":1},"title":"Definite Clause Grammars (DCG) in Lisp","author":"admin","date":"May 22, 2017","format":false,"excerpt":"Definite Clause Grammars (DCG) are an elegant formalism for specifying context free grammars, and part of their popularity is due to their support in the Prolog language. Most books on Natural Language processing usually include a brief coverage of DCGs, even though Natural languages are not context-free. Because of the\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=525%2C300 1.5x"},"classes":[]},{"id":2927,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/20\/why-learn-lisp\/","url_meta":{"origin":3589,"position":2},"title":"Why Learn Lisp?","author":"admin","date":"October 20, 2022","format":false,"excerpt":"In the last article, I had shared my views on why programmers should learn Prolog, preferably as the first language. What language should one learn next? I strongly pitch for Lisp, to be precise, \u201cCommon Lisp\u201d. Lisp happens to be the second oldest (1958) programming language, only after Fortran (1957)!\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2366,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/03\/28\/implementing-ilexicon-using-litedb\/","url_meta":{"origin":3589,"position":3},"title":"Implementing iLexicon using LiteDB","author":"admin","date":"March 28, 2021","format":false,"excerpt":"iLexicon is an \"intelligent\" dictionary that can be used to build Natural Language applications. I have two implementations, one in Lisp and another in Prolog. Both implementations are memory-based, in order to speed up performance. I have written several articles referencing it, for example see this. \u00a0 LiteDB is a\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Sample Commands","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/03\/Session1.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":548,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/23\/definite-clause-grammars-in-lisp-part-3\/","url_meta":{"origin":3589,"position":4},"title":"Definite Clause Grammars in Lisp – Part 3","author":"admin","date":"June 23, 2017","format":false,"excerpt":"In today's post, let us see how we can enhance the grammar representation discussed so far to include both Number constraint and Parse Tree. Fortunately, this turns out to be quite straightforward. Just as we do in Prolog, we need to include additional parameters, as needed, to each grammar rule.\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"POS Functions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=525%2C300 1.5x"},"classes":[]},{"id":912,"url":"https:\/\/www.rangakrish.com\/index.php\/2018\/04\/22\/question-answering-using-dependency-trees\/","url_meta":{"origin":3589,"position":5},"title":"Question Answering\u00a0Using Dependency Trees","author":"admin","date":"April 22, 2018","format":false,"excerpt":"A few weeks ago I had written about my brief experiment with Mathematica's new feature, which provides answers to questions based on given text. After that post, I spent some time thinking about how to implement something similar. In today's post, I want to show you what I have been\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Dependency Tree","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/04\/Deptree-example.png?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/3589","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=3589"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/3589\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=3589"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=3589"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=3589"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}