State name puzzle: Difference between revisions

This task is inspired by [http://drdobbs.com/windows/198701685 Mark Nelson's DDJ Column "Wordplay"] and one of the weekly puzzle challenges from Will Shortz on NPR Weekend Edition [http://www.npr.org/templates/story/story.php?storyId=9264290] and originally attributed to David Edelheit.

 

 

The problem was reissued on [https://tapestry.tucson.az.us/twiki/bin/view/Main/StateNamesPuzzle the Unicon Discussion Web] which includes several solutions with analysis. Several techniques may be helpful and you may wish to refer to [[wp:Goedel_numbering|Gödel numbering]], [[wp:Equivalence_relation|equivalence relations]], and [[wp:Equivalence_classes|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.

 

* case and spacing aren't significant - just letters (harmonize case)

* don't expect the names to be in any order - such as being sorted

* don't rely on names to be unique (eliminate duplicates - meaning if Iowa appears twice you can only use it once)

 

Comma separated list of state names used in the original puzzle:

<pre>

</pre>

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

<pre>

</pre>

 

=={{header|Bracmat}}==

Alaska

Arizona

& "State name puzzle"$!states

& "State name puzzle"$(!states !extrastates)

Output:

<pre>North Carolina + South Dakota = North Dakota + South Carolina

=={{header|C}}==

Sort by letter occurence and deal with dupes.

#include <stdlib.h>

#include <string.h>

find_mix();

return 0;

 

=={{header|C++}}==

Ported from C solution.

#include <iostream>

#include <string>

start = next;

}

 

=={{header|D}}==

 

auto states = ["Alabama", "Alaska", "Arizona", "Arkansas",

writefln("%-(%-(%s = %)\n%)",

smap.values.sort().filter!q{ a.length > 1 });

{{out}}

<pre>North Carolina + South Dakota = North Dakota + South Carolina</pre>

 

=={{header|Go}}==

 

import (

}

}

Output:

<pre>

 

=={{header|Haskell}}==

 

import Data.Function (on)

 

 

 

 

main :: IO ()

main = do

{{out}}

<pre style="font-size:80%">Matching pairs generated from 50 state names and 5 fake state names:

(("New Kory","York New"),("New York","Wen Kory"))

</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

=== Equivalence Class Solution ===

 

procedure main(arglist)

}

write("... runtime ",(&time - st)/1000.,"\n",m," matches found.")

 

return ["Alabama", "Alaska", "Arizona", "Arkansas",

"California", "Colorado", "Connecticut",

procedure getStates2() # return list of state names + fictious states

return getStates() ||| ["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"]

 

=== Godel Number Solution ===

 

procedure GNsolve(S)

every z *:= xlate[!s]

return z

 

{{libheader|Icon Programming Library}}

Implementation:

 

 

states=:<;._2]0 :0-.LF

pairUp=: (#~ matchUp)@({~ 2 comb #)@~.

matchUp=: (i.~ ~: i:~)@:(<@normalize@;"1)

 

In action:

 

┌──────────────┬──────────────┐

│North Carolina│South Dakota │

├──────────────┼──────────────┤

│North Dakota │South Carolina│

 

Note: this approach is sufficient to solve the original problem, but does not properly deal with the addition of fictitious states. So:

 

 

In action:

 

┌──────────────┬──────────────┐

│Kory New │York New │

├──────────────┼──────────────┤

│North Dakota │South Carolina│

 

=={{header|Java}}==

{{works with|Java|8}}

import java.util.stream.*;

 

});

}

 

Output:

=={{header|jq}}==

{{works with|jq|1.4}}

# Output: an array, being the exploded form of the normalized input

def normalize:

else .

end)

 

'''The task:'''

"Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado",

"Connecticut", "Delaware", "Florida", "Georgia", "Hawaii", "Idaho",

(States + ["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"] | solve) ;

 

{{out}}

Real state names:

[["North Carolina","South Dakota"],["North Dakota","South Carolina"]]

[["New Kory","Wen Kory"],["New York","York New"]]

[["New Kory","York New"],["New York","Wen Kory"]]

 

=={{header|LiveCode}}==

This is going to be O(N^2).

if the optionkey is down then breakpoint

put the long seconds into T

replace comma with empty in X

return X

 

groupSameQ[g1_, g2_] := Sort /@ Partition[g1, 2] === Sort /@ Partition[g2, 2];

permutations[{a_, b_, c_, d_}] = Union[Permutations[{a, b, c, d}], SameTest -> groupSameQ];

Subsets[Union[ToLowerCase/@{"Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "Florida",

"Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland",

"Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", "Virginia", "Washington",

"West Virginia", "Wisconsin", "Wyoming"}], {4}], 1],

 

=={{header|Perl}}==

use warnings;

use strict;

 

say @states + @fictious, ' states:';

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(group

(mapcar '((Name) (cons (clip (sort (chop (lowc Name)))) Name))

(car Y) ) )

(cdr X) ) )

Output:

<pre>-> ((("North Carolina" . "South Dakota") ("North Dakota" . "South Carolina")))</pre>

 

Works with SWI-Prolog. Use of Goedel numbers.

L = ["Alabama", "Alaska", "Arizona", "Arkansas",

"California", "Colorado", "Connecticut",

GC1 is GC + 26 ** Ind,

compute_Goedel(T, GC1, GF).

Output :

<pre> ?- time(state_name_puzzle).

true .

</pre>

 

=={{header|Python}}==

{{trans|D}}

 

states = ["Alabama", "Alaska", "Arizona", "Arkansas",

for pairs in sorted(smap.itervalues()):

if len(pairs) > 1:

 

=={{header|Racket}}==

#lang racket

(define states

(cond [(hash-ref seen c (λ() (hash-set! seen c (list s1 s2)) #f))

=> (λ(states) (displayln (~v states (list s1 s2))))]))

Output:

'("north dakota" "south carolina") '("north carolina" "south dakota")

 

=={{header|REXX}}==

Code was added to the REXX program to remove dead-end words (state names) that can't possibly be part of

<br>a solution, in particular, words that contain a unique letter (among all the state names).

!='Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Delaware, Florida, Georgia,',

'Hawaii, Idaho, Illinois, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Massachusetts, ',

/*──────────────────────────────────────────────────────────────────────────────────────*/

list: say; do i=1 for z; say right(i, 9) ##.i; end; say; return

{{out|output|text=&nbsp; when using the default input:}}

<pre style="height:60ex">

=={{header|Ruby}}==

{{trans|Tcl}}

 

# 26 prime numbers

puts ""

puts "with fictional states"

 

outputs

15 New Kory, Kory New Wen Kory, York New

16 North Carolina, South Dakota North Dakota, South Carolina</pre>

=={{header|Scala}}==

// Logic:

def disjointPairs(pairs: Seq[Set[String]]) =

 

println(anagramPairs(states).map(_.map(_ mkString " + ") mkString " = ") mkString "\n")

{{out}}

<pre>New Kory + Wen Kory = York New + Kory New

 

=={{header|Tcl}}==

# Gödel number generator

proc goedel s {

"New Kory" "Wen Kory" "York New" "Kory New" "New Kory"

}

Output:

<pre>

North Carolina, South Dakota

North Dakota, South Carolina

</pre>

 

=={{header|zkl}}==

{{trans|Python}}

states:=("Alabama, Alaska, Arizona, Arkansas,

California, Colorado, Connecticut, Delaware, Florida,

// pairs=Utils.Helpers.listUnique(pairs); // eliminate dups

if(pairs.len()>1)

{{out}}

<pre>