How to resolve the algorithm State name puzzle step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm State name puzzle step by step in the Nim programming language

Table of Contents

Problem Statement

Background This task is inspired by Mark Nelson's DDJ Column "Wordplay" and one of the weekly puzzle challenges from Will Shortz on NPR Weekend Edition [1] and originally attributed to David Edelheit. The challenge was to take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two different U.S. States (so that all four state names differ from one another). What states are these?

The problem was reissued on the Unicon Discussion Web which includes several solutions with analysis. Several techniques may be helpful and you may wish to refer to Gödel numbering, equivalence relations, and equivalence classes. The basic merits of these were discussed in the Unicon Discussion Web. A second challenge in the form of a set of fictitious new states was also presented.

Write a program to solve the challenge using both the original list of states and the fictitious list.

Comma separated list of state names used in the original puzzle: Comma separated list of additional fictitious state names to be added to the original (Includes a duplicate):

Let's start with the solution:

Step by Step solution about How to resolve the algorithm State name puzzle step by step in the Nim programming language

Source code in the nim programming language

import algorithm, sequtils, strformat, strutils, tables


const
  States = @["Alabama",  "Alaska",  "Arizona",  "Arkansas",
             "California",  "Colorado",  "Connecticut",  "Delaware",
             "Florida",  "Georgia",  "Hawaii",  "Idaho",  "Illinois",
             "Indiana",  "Iowa",  "Kansas",  "Kentucky",  "Louisiana",
             "Maine",  "Maryland",  "Massachusetts",  "Michigan",
             "Minnesota",  "Mississippi",  "Missouri",  "Montana",
             "Nebraska",  "Nevada",  "New Hampshire",  "New Jersey",
             "New Mexico",  "New York",  "North Carolina",  "North Dakota",
             "Ohio",  "Oklahoma",  "Oregon",  "Pennsylvania",  "Rhode Island",
             "South Carolina",  "South Dakota",  "Tennessee",  "Texas",
             "Utah",  "Vermont",  "Virginia",
             "Washington",  "West Virginia",  "Wisconsin",  "Wyoming"]

  Fictitious = @["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"]

type MatchingPairs = ((string, string), (string, string))


proc matchingPairs(states: openArray[string]): seq[MatchingPairs] =
  ## Build the list of matching pairs of states.

  let states = sorted(states).deduplicate()

  # Build a mapping from ordered sequence of chars to sequence of (state, state).
  var mapping: Table[seq[char], seq[(string, string)]]
  for i in 0..<states.high:
    let s1 = states[i]
    for j in (i + 1)..states.high:
      let s2 = states[j]
      mapping.mgetOrPut(sorted(map(s1 & s2, toLowerAscii)), @[]).add (s1, s2)

  # Keep only the couples of pairs of states with no common state.
  for pairs in mapping.values:
    if pairs.len > 1:
      # These pairs are candidates.
      for i in 0..<pairs.high:
        let pair1 = pairs[i]
        for j in i..pairs.high:
          let pair2 = pairs[j]
          if pair1[0] != pair2[0] and pair1[0] != pair2[1] and
             pair1[1] != pair2[0] and pair1[1] != pair2[1]:
            # "pair1" and "pair2" have no common state.
            result.add (pair1, pair2)


proc `$`(pairs: MatchingPairs): string =
  ## Return the string representation of two matching pairs.
  "$1 & $2 = $3 & $4".format(pairs[0][0], pairs[0][1], pairs[1][0], pairs[1][1])

echo "For real states:"
for n, pairs in matchingPairs(States):
  echo &"{n+1:2}:  {pairs}"
echo()
echo "For real + fictitious states:"
for n, pairs in matchingPairs(States & Fictitious):
  echo &"{n+1:2}:  {pairs}"

You may also check:How to resolve the algorithm Mastermind step by step in the Ada programming language
You may also check:How to resolve the algorithm Pig the dice game step by step in the CLU programming language
You may also check:How to resolve the algorithm Damm algorithm step by step in the 11l programming language
You may also check:How to resolve the algorithm Self-describing numbers step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Pangram checker step by step in the Ring programming language