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

Published on 12 May 2024 09:40 PM
#Jq

How to resolve the algorithm State name puzzle step by step in the jq 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 jq programming language

Source code in the jq programming language

# Input: a string
# Output: an array, being the exploded form of the normalized input
def normalize:
  explode
  | map(if . >= 97 then (. - 97) elif . >= 65 then (. - 65) else empty end);

# Input: an array of strings
# Output: a dictionary with key:value pairs: normalizedString:string
def dictionary:
  reduce .[] as $s ( {}; . + { ($s|normalize|implode): $s });

# Input: an array of strings (e.g. state names)
# Output: a stream of solutions
def solve:

  # Given a pair of normalized state names as lists of integers:
  def nletters: map(length) | add;

  # input [[s1,s2], [t2,t2]]
  def solved:
    ( .[0] | add | sort) ==  (.[1] | add | sort);

  unique
  | length as $l
  | dictionary as $dictionary
  | ($dictionary | keys | map(explode)) as $states
  | reduce ( range(0; $l) as $s1
                 | range($s1+1; $l) as $s2
                 | range($s1+1; $l) as $t1
	         | select($s2 != $t1)
	         | range($t1+1; $l) as $t2
     	         | select($s2 != $t2)
	         | [[$states[$s1], $states[$s2]], [$states[$t1], $states[$t2]]] ) as $quad
       ([];
        if ($quad[0] | nletters) == ($quad[1] | nletters)
	   and ($quad | solved)
	then . + [$quad | map( map(  $dictionary[ implode ] ))]
	else .
	end)
  | .[];

def 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"
];

def task:
  "Real state names:",
  (States | solve),
  "",
  "States together with fictional state names:",
  (States + ["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"] | solve)   ;

task

$ jq -c -n -r -f State_name_puzzle.jq
Real state names:
[["North Carolina","South Dakota"],["North Dakota","South Carolina"]]

States together with fictional state names:
[["Kory New","New Kory"],["New York","Wen Kory"]]
[["Kory New","New Kory"],["New York","York New"]]
[["Kory New","New Kory"],["Wen Kory","York New"]]
[["Kory New","New York"],["New Kory","Wen Kory"]]
[["Kory New","New York"],["New Kory","York New"]]
[["Kory New","New York"],["Wen Kory","York New"]]
[["Kory New","Wen Kory"],["New Kory","New York"]]
[["Kory New","Wen Kory"],["New Kory","York New"]]
[["Kory New","Wen Kory"],["New York","York New"]]
[["Kory New","York New"],["New Kory","New York"]]
[["Kory New","York New"],["New Kory","Wen Kory"]]
[["Kory New","York New"],["New York","Wen Kory"]]
[["New Kory","New York"],["Wen Kory","York New"]]
[["New Kory","Wen Kory"],["New York","York New"]]
[["New Kory","York New"],["New York","Wen Kory"]]
[["North Carolina","South Dakota"],["North Dakota","South Carolina"]]


  

You may also check:How to resolve the algorithm Nested function step by step in the Ruby programming language
You may also check:How to resolve the algorithm Sum and product of an array step by step in the Phixmonti programming language
You may also check:How to resolve the algorithm Menu step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm SQL-based authentication step by step in the Tcl programming language
You may also check:How to resolve the algorithm Nim game step by step in the Pebble programming language