State name puzzle
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.
Task:
Write a program to solve the challenge using both the original list of states and the fictitious list.
Caveats:
- case and spacing isn'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:
"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"
Comma separated list of additional fictitious state names to be added to the original (Includes a duplicate):
"New Kory", "Wen Kory", "York New", "Kory New", "New Kory"
C
Sort by letter occurence and deal with dupes. <lang C>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- define USE_FAKES 1
char *states[] = {
- if USE_FAKES
"New Kory", "Wen Kory", "York New", "Kory New", "New Kory",
- endif
"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" };
int n_states = sizeof(states)/sizeof(char*); typedef struct { unsigned char c[26]; char *name[2]; } letters;
void count_letters(letters *l, char *s) { int c; if (!l->name[0]) l->name[0] = s; else l->name[1] = s;
while ((c = *s++)) { if (c >= 'a' && c <= 'z') l->c[c - 'a']++; if (c >= 'A' && c <= 'Z') l->c[c - 'A']++; } }
int lcmp(const void *aa, const void *bb) { int i; const letters *a = aa, *b = bb; for (i = 0; i < 26; i++) if (a->c[i] > b->c[i]) return 1; else if (a->c[i] < b->c[i]) return -1; return 0; }
int scmp(const void *a, const void *b) { return strcmp(*(char**)a, *(char**)b); }
void no_dup() { int i, j;
qsort(states, n_states, sizeof(char*), scmp);
for (i = j = 0; i < n_states;) { while (++i < n_states && !strcmp(states[i], states[j])); if (i < n_states) states[++j] = states[i]; }
n_states = j + 1; }
void find_mix() { int i, j, n; letters *l, *p;
no_dup(); n = n_states * (n_states - 1) / 2; p = l = calloc(n, sizeof(letters));
for (i = 0; i < n_states; i++) for (j = i + 1; j < n_states; j++, p++) { count_letters(p, states[i]); count_letters(p, states[j]); }
qsort(l, n, sizeof(letters), lcmp);
for (j = 0; j < n; j++) { for (i = j + 1; i < n && !lcmp(l + j, l + i); i++) { if (l[j].name[0] == l[i].name[0] || l[j].name[1] == l[i].name[0] || l[j].name[1] == l[i].name[1]) continue; printf("%s + %s => %s + %s\n", l[j].name[0], l[j].name[1], l[i].name[0], l[i].name[1]); } } free(l); }
int main(void) { find_mix(); return 0; }</lang>
D
<lang d>import std.stdio, std.algorithm, std.array, std.exception;
auto 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", // Uncomment the next line for the fake states. // "New Kory", "Wen Kory", "York New", "Kory New", "New Kory" ];
void main() {
states.length -= copy(uniq(states.sort()), states).length;
string[][string] smap;
foreach (i, s1; states[0 .. $-1])
foreach (s2; states[i + 1 .. $])
smap[(s1.dup ~ s2.dup).sort.idup] ~= s1 ~ " + " ~ s2;
foreach (pairs; sort(smap.values))
if (pairs.length > 1)
writeln(pairs.join(" = "));
}</lang> Output:
North Carolina + South Dakota = North Dakota + South Carolina
More complex version to be used when the .sort built-in goes away (same output): <lang d>import std.stdio, std.algorithm, std.array;
auto 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", // Uncomment the next line for the fake states. // "New Kory", "Wen Kory", "York New", "Kory New", "New Kory" ];
void main() {
states.length -= copy(uniq(states.sort()), states).length;
string[][const(ubyte)[]] smap;
foreach (i, s1; states[0 .. $-1])
foreach (s2; states[i + 1 .. $]) {
const aux = sort(cast(ubyte[])(s1 ~ s2)).release();
smap[aux] ~= s1 ~ " + " ~ s2;
}
foreach (pairs; sort(smap.values))
if (pairs.length > 1)
writeln(pairs.join(" = "));
}</lang>
Go
<lang go>package main
import (
"fmt" "unicode"
)
var states = []string{"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"}
func main() {
play(states)
play(append(states,
"New Kory", "Wen Kory", "York New", "Kory New", "New Kory"))
}
func play(states []string) {
fmt.Println(len(states), "states:")
// get list of unique state names
set := make(map[string]bool, len(states))
for _, s := range states {
set[s] = true
}
// make parallel arrays for unique state names and letter histograms
s := make([]string, len(set))
h := make([][26]byte, len(set))
var i int
for us := range set {
s[i] = us
for _, c := range us {
if u := uint(unicode.ToLower(c)) - 'a'; u < 26 {
h[i][u]++
}
}
i++
}
// use map to find matches. map key is sum of histograms of
// two different states. map value is indexes of the two states.
type pair struct {
i1, i2 int
}
m := make(map[string][]pair)
b := make([]byte, 26) // buffer for summing histograms
for i1, h1 := range h {
for i2 := i1 + 1; i2 < len(h); i2++ {
// sum histograms
for i := range b {
b[i] = h1[i] + h[i2][i]
}
k := string(b) // make key from buffer.
// now loop over any existing pairs with the same key,
// printing any where both states of this pair are different
// than the states of the existing pair
for _, x := range m[k] {
if i1 != x.i1 && i1 != x.i2 && i2 != x.i1 && i2 != x.i2 {
fmt.Printf("%s, %s = %s, %s\n", s[i1], s[i2],
s[x.i1], s[x.i2])
}
}
// store this pair in the map whether printed or not.
m[k] = append(m[k], pair{i1, i2})
}
}
}</lang> Output:
50 states: North Dakota, South Carolina = North Carolina, South Dakota 55 states: South Dakota, North Carolina = North Dakota, South Carolina New Kory, Kory New = Wen Kory, York New New Kory, Kory New = Wen Kory, New York New Kory, York New = Wen Kory, Kory New New Kory, York New = Wen Kory, New York New Kory, New York = Wen Kory, Kory New New Kory, New York = Wen Kory, York New Kory New, York New = Wen Kory, New Kory Kory New, York New = Wen Kory, New York Kory New, York New = New Kory, New York Kory New, New York = Wen Kory, New Kory Kory New, New York = Wen Kory, York New Kory New, New York = New Kory, York New York New, New York = Wen Kory, New Kory York New, New York = Wen Kory, Kory New York New, New York = New Kory, Kory New
Icon and Unicon
Equivalence Class Solution
<lang Icon>link strings # for csort and deletec
procedure main(arglist)
ECsolve(S1 := getStates()) # original state names puzzle ECsolve(S2 := getStates2()) # modified fictious names puzzle GNsolve(S1) GNsolve(S2)
end
procedure ECsolve(S) # Solve challenge using equivalence classes
local T,x,y,z,i,t,s,l,m
st := &time # mark runtime
/S := getStates() # default
every insert(states := set(),deletec(map(!S),' \t')) # ignore case & space
# Build a table containing sets of state name pairs
# keyed off of canonical form of the pair
# Use csort(s) rather than cset(s) to preserve the numbers of each letter
# Since we care not of X&Y .vs. Y&X keep only X&Y
T := table()
every (x := !states ) & ( y := !states ) do
if z := csort(x || (x << y)) then {
/T[z] := []
put(T[z],set(x,y))
}
# For each unique key (canonical pair) find intersection of all pairs
# Output is <current key matched> <key> <pairs>
i := m := 0 # keys (i) and pairs (m) matched
every z := key(T) do {
s := &null
every l := !T[z] do {
/s := l
s **:= l
}
if *s = 0 then {
i +:= 1
m +:= *T[z]
every x := !T[z] do {
#writes(i," ",z) # uncomment for equiv class and match count
every writes(!x," ")
write()
}
}
}
write("... runtime ",(&time - st)/1000.,"\n",m," matches found.")
end</lang>
The following are common routines:<lang Icon>procedure getStates() # return list of state names return ["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"]
end
procedure getStates2() # return list of state names + fictious states return getStates() ||| ["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"] end</lang>
Godel Number Solution
<lang Icon>link factors
procedure GNsolve(S)
local min, max
st := &time
equivClasses := table()
statePairs := table()
/S := getStates()
every put(states := [], map(!S)) # Make case insignificant
min := proc("min",0) # Link "factors" loses max/min functions
max := proc("max",0) # ... these statements get them back
# Build a table of equivalence classes (all state pairs in the
# same equivalence class have the same characters in them)
# Output new pair couples *before* adding each state pair to class.
every (state1 := |get(states)) & (state2 := !states) do {
if state1 ~== state2 then {
statePair := min(state1, state2)||":"||max(state1,state2)
if /statePairs[statePair] := set(state1, state2) then {
signature := getClassSignature(state1, state2)
/equivClasses[signature] := set()
every *(statePairs[statePair] ** # require 4 distinct states
statePairs[pair := !equivClasses[signature]]) == 0 do {
write(statePair, " and ", pair)
}
insert(equivClasses[signature], statePair)
}
}
}
write(&errout, "Time: ", (&time-st)/1000.0)
end
- Build a (Godel) signature identifying the equivalence class for state pair s.
procedure getClassSignature(s1, s2)
static G initial G := table() /G[s1] := gn(s1) /G[s2] := gn(s2) return G[s1]*G[s2]
end
procedure gn(s) # Compute the Godel number for a string (letters only)
static xlate
local p, i, z
initial {
xlate := table(1)
p := create prime()
every i := 1 to 26 do {
xlate[&lcase[i]] := xlate[&ucase[i]] := @p
}
}
z := 1
every z *:= xlate[!s]
return z
end</lang>
strings.icn provides deletec, csort factors.icn provides prime
Sample Output (ECsolve):
northcarolina southdakota northdakota southcarolina ... runtime 0.019 2 matches found. wenkory yorknew wenkory newyork newyork yorknew wenkory korynew newyork korynew newkory korynew korynew yorknew wenkory newkory newkory newyork newkory yorknew northcarolina southdakota northdakota southcarolina ... runtime 0.026 12 matches found.
Sample Output (GNsolve):
north dakota:south carolina and north carolina:south dakota Time: 0.008999999999999999 north dakota:south carolina and north carolina:south dakota new kory:wen kory and new york:york new new kory:wen kory and kory new:new york new kory:york new and new york:wen kory new kory:york new and kory new:new york kory new:new kory and new york:wen kory kory new:new kory and new york:york new wen kory:york new and kory new:new york wen kory:york new and kory new:new kory wen kory:york new and new kory:new york kory new:wen kory and new york:york new kory new:wen kory and new kory:york new kory new:wen kory and new kory:new york kory new:york new and new york:wen kory kory new:york new and new kory:wen kory kory new:york new and new kory:new york Time: 0.018
J
Implementation:
<lang j>require'strings stats'
states=:<;._2]0 :0-.LF
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, Maine,Maine,Maine,Maine,Maine,Maine,Maine,Maine,
)
pairUp=: (#~ matchUp)@({~ 2 comb #)@~. matchUp=: (i.~ ~: i:~)@:(<@normalize@;"1) normalize=: /:~@tolower@-.&' '</lang>
In action:
<lang j> pairUp states ┌──────────────┬──────────────┐ │North Carolina│South Dakota │ ├──────────────┼──────────────┤ │North Dakota │South Carolina│ └──────────────┴──────────────┘</lang>
Note: this approach is sufficient to solve the original problem, but does not properly deal with the addition of fictitious states. So:
<lang j>isolatePairs=: ~.@matchUp2@(#~ *./@matchUp"2)@({~ 2 comb #) matchUp2=: /:~"2@:(/:~"1)@(#~ 4=#@~.@,"2)</lang>
In action:
<lang j> isolatePairs pairUp 'New Kory';'Wen Kory';'York New';'Kory New';'New Kory';states ┌──────────────┬──────────────┐ │Kory New │York New │ ├──────────────┼──────────────┤ │New Kory │Wen Kory │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │New Kory │Wen Kory │ ├──────────────┼──────────────┤ │New York │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New York │ ├──────────────┼──────────────┤ │New Kory │Wen Kory │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │Wen Kory │ ├──────────────┼──────────────┤ │New Kory │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │New Kory │York New │ ├──────────────┼──────────────┤ │New York │Wen Kory │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New York │ ├──────────────┼──────────────┤ │New Kory │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New Kory │ ├──────────────┼──────────────┤ │Wen Kory │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New Kory │ ├──────────────┼──────────────┤ │New York │Wen Kory │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New Kory │ ├──────────────┼──────────────┤ │New York │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │New Kory │New York │ ├──────────────┼──────────────┤ │Wen Kory │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │Wen Kory │ ├──────────────┼──────────────┤ │New Kory │New York │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │York New │ ├──────────────┼──────────────┤ │New Kory │New York │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │New York │ ├──────────────┼──────────────┤ │Wen Kory │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │Wen Kory │ ├──────────────┼──────────────┤ │New York │York New │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │Kory New │York New │ ├──────────────┼──────────────┤ │New York │Wen Kory │ └──────────────┴──────────────┘
┌──────────────┬──────────────┐ │North Carolina│South Dakota │ ├──────────────┼──────────────┤ │North Dakota │South Carolina│ └──────────────┴──────────────┘</lang>
Perl 6
<lang perl6>my @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
>;
say "50 states:"; .say for anastates @states;
say "\n54 states:"; .say for anastates @states, < New_Kory Wen_Kory York_New Kory_New New_Kory >;
sub anastates (*@states) {
my @s = @states.uniq».subst('_', ' ');
my @pairs = gather for ^@s -> $i {
for $i ^..^ @s -> $j { take [ @s[$i], @s[$j] ]; }
}
my $equivs = hash @pairs.classify: *.lc.comb.sort.join.trim;
gather for $equivs.values -> @c {
for ^@c -> $i { for $i ^..^ @c -> $j { my $set = set @c[$i].list, @c[$j].list; take $set.join(', ') if $set == 4; } }
}
}</lang>
Output:
50 states: North Carolina, South Dakota, North Dakota, South Carolina 54 states: North Carolina, South Dakota, North Dakota, South Carolina New York, New Kory, Wen Kory, York New New York, New Kory, Wen Kory, Kory New New York, New Kory, York New, Kory New New York, Wen Kory, New Kory, York New New York, Wen Kory, New Kory, Kory New New York, Wen Kory, York New, Kory New New York, York New, New Kory, Wen Kory New York, York New, New Kory, Kory New New York, York New, Wen Kory, Kory New New York, Kory New, New Kory, Wen Kory New York, Kory New, New Kory, York New New York, Kory New, Wen Kory, York New New Kory, Wen Kory, York New, Kory New New Kory, York New, Wen Kory, Kory New New Kory, Kory New, Wen Kory, York New
PicoLisp
<lang PicoLisp>(setq *States
(group
(mapcar '((Name) (cons (clip (sort (chop (lowc Name)))) Name))
(quote
"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"
"New Kory" "Wen Kory" "York New" "Kory New" "New Kory" ) ) ) )
(extract
'((P)
(when (cddr P)
(mapcar
'((X)
(cons
(cadr (assoc (car X) *States))
(cadr (assoc (cdr X) *States)) ) )
(cdr P) ) ) )
(group
(mapcon
'((X)
(extract
'((Y)
(cons
(sort (conc (copy (caar X)) (copy (car Y))))
(caar X)
(car Y) ) )
(cdr X) ) )
*States ) ) )</lang>
Output:
-> ((("North Carolina" . "South Dakota") ("North Dakota" . "South Carolina")))
Prolog
Works with SWI-Prolog. Use of Goedel numbers. <lang Prolog>state_name_puzzle :- L = ["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", "New Kory", "Wen Kory", "York New", "Kory New", "New Kory"],
maplist(goedel, L, R),
% sort remove duplicates sort(R, RS),
study(RS).
study([]).
study([V-Word|T]) :- study_1_Word(V-Word, T, T), study(T).
study_1_Word(_, [], _).
study_1_Word(V1-W1, [V2-W2 | T1], T) :-
TT is V1+V2,
study_2_Word(W1, W2, TT, T),
study_1_Word(V1-W1, T1, T).
study_2_Word(_W1, _W2, _TT, []).
study_2_Word(W1, W2, TT, [V3-W3 | T]) :- ( W2 \= W3 -> study_3_Word(W1, W2, TT, V3-W3, T); true), study_2_Word(W1, W2, TT, T).
study_3_Word(_W1, _W2, _TT, _V3-_W3, []).
study_3_Word(W1, W2, TT, V3-W3, [V4-W4|T]) :- TT1 is V3 + V4, ( TT1 < TT -> study_3_Word(W1, W2, TT, V3-W3, T) ; (TT1 = TT -> ( W4 \= W2 -> format('~w & ~w with ~w & ~w~n', [W1, W2, W3, W4]) ; true),
study_3_Word(W1, W2, TT, V3-W3, T))
; true).
% Compute a Goedel number for the word goedel(Word, Goedel-A) :- name(A, Word), downcase_atom(A, Amin), atom_codes(Amin, LA), compute_Goedel(LA, 0, Goedel).
compute_Goedel([], G, G).
compute_Goedel([32|T], GC, GF) :- compute_Goedel(T, GC, GF).
compute_Goedel([H|T], GC, GF) :- Ind is H - 97, GC1 is GC + 26 ** Ind, compute_Goedel(T, GC1, GF). </lang> Output :
?- time(state_name_puzzle). North Carolina & South Dakota with North Dakota & South Carolina Kory New & New Kory with New York & Wen Kory Kory New & New Kory with New York & York New Kory New & New Kory with Wen Kory & York New Kory New & New York with New Kory & Wen Kory Kory New & New York with New Kory & York New Kory New & New York with Wen Kory & York New Kory New & Wen Kory with New Kory & New York Kory New & Wen Kory with New Kory & York New Kory New & Wen Kory with New York & York New Kory New & York New with New Kory & New York Kory New & York New with New Kory & Wen Kory Kory New & York New with New York & Wen Kory New Kory & New York with Wen Kory & York New New Kory & Wen Kory with New York & York New New Kory & York New with New York & Wen Kory % 1,076,511 inferences, 1.078 CPU in 1.141 seconds (94% CPU, 998503 Lips) true .
Python
<lang python>from collections import defaultdict
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",
- Uncomment the next line for the fake states.
- "New Kory", "Wen Kory", "York New", "Kory New", "New Kory"
]
states = sorted(set(states))
smap = defaultdict(list) for i, s1 in enumerate(states[:-1]):
for s2 in states[i + 1:]:
smap["".join(sorted(s1 + s2))].append(s1 + " + " + s2)
for pairs in sorted(smap.itervalues()):
if len(pairs) > 1:
print " = ".join(pairs)</lang>
Ruby
<lang ruby>require 'set'
- 26 prime numbers
Primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
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 print_answer(states)
# find goedel numbers for all pairs of states
goedel = lambda {|str| str.chars.map {|c| Primes[c.ord - 65]}.reduce(:*)}
pairs = Hash.new {|h,k| h[k] = Array.new}
map = states.uniq.map {|state| [state, goedel[state.upcase.delete("^A-Z")]]}
map.combination(2) {|(s1,g1), (s2,g2)| pairs[g1 * g2] << [s1, s2]}
# find pairs without duplicates
result = []
pairs.values.select {|val| val.length > 1}.each do |list_of_pairs|
list_of_pairs.combination(2) do |pair1, pair2|
if Set[*pair1, *pair2].length == 4
result << [pair1, pair2]
end
end
end
# output the results
result.each_with_index do |(pair1, pair2), i|
puts "%d\t%s\t%s" % [i+1, pair1.join(', '), pair2.join(', ')]
end
end
puts "real states only" print_answer(States) puts "" puts "with fictional states" print_answer(States + ["New Kory", "Wen Kory", "York New", "Kory New", "New Kory"])</lang>
outputs
real states only 1 North Carolina, South Dakota North Dakota, South Carolina with fictional states 1 New York, New Kory Wen Kory, York New 2 New York, New Kory Wen Kory, Kory New 3 New York, New Kory York New, Kory New 4 New York, Wen Kory New Kory, York New 5 New York, Wen Kory New Kory, Kory New 6 New York, Wen Kory York New, Kory New 7 New York, York New New Kory, Wen Kory 8 New York, York New New Kory, Kory New 9 New York, York New Wen Kory, Kory New 10 New York, Kory New New Kory, Wen Kory 11 New York, Kory New New Kory, York New 12 New York, Kory New Wen Kory, York New 13 New Kory, Wen Kory York New, Kory New 14 New Kory, York New Wen Kory, Kory New 15 New Kory, Kory New Wen Kory, York New 16 North Carolina, South Dakota North Dakota, South Carolina
Tcl
<lang tcl>package require Tcl 8.5
- Gödel number generator
proc goedel s {
set primes {
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
}
set n 1
foreach c [split [string toupper $s] ""] {
if {![string is alpha $c]} continue set n [expr {$n * [lindex $primes [expr {[scan $c %c] - 65}]]}]
} return $n
}
- Calculates the pairs of states
proc groupStates {stateList} {
set stateList [lsort -unique $stateList]
foreach state1 $stateList {
foreach state2 $stateList { if {$state1 >= $state2} continue dict lappend group [goedel $state1$state2] [list $state1 $state2] }
}
foreach g [dict values $group] {
if {[llength $g] > 1} { foreach p1 $g { foreach p2 $g { if {$p1 < $p2 && [unshared $p1 $p2]} { lappend result [list $p1 $p2] } } } }
} return $result
} proc unshared args {
foreach p $args {
foreach a $p {incr s($a)}
}
expr {[array size s] == [llength $args]*2}
}
- Pretty printer for state name pair lists
proc printPairs {title groups} {
foreach group $groups {
puts "$title Group #[incr count]" foreach statePair $group { puts "\t[join $statePair {, }]" }
}
}
set realStates {
"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"
} printPairs "Real States" [groupStates $realStates] set falseStates {
"New Kory" "Wen Kory" "York New" "Kory New" "New Kory"
} printPairs "Real and False States" [groupStates [concat $realStates $falseStates]]</lang> Output:
Real States Group #1 North Carolina, South Dakota North Dakota, South Carolina Real and False States Group #1 Kory New, New Kory New York, Wen Kory Real and False States Group #2 Kory New, New Kory New York, York New Real and False States Group #3 Kory New, New Kory Wen Kory, York New Real and False States Group #4 Kory New, New York New Kory, Wen Kory Real and False States Group #5 Kory New, New York New Kory, York New Real and False States Group #6 Kory New, New York Wen Kory, York New Real and False States Group #7 Kory New, Wen Kory New Kory, New York Real and False States Group #8 Kory New, Wen Kory New Kory, York New Real and False States Group #9 Kory New, Wen Kory New York, York New Real and False States Group #10 Kory New, York New New Kory, New York Real and False States Group #11 Kory New, York New New Kory, Wen Kory Real and False States Group #12 Kory New, York New New York, Wen Kory Real and False States Group #13 New Kory, New York Wen Kory, York New Real and False States Group #14 New Kory, Wen Kory New York, York New Real and False States Group #15 New Kory, York New New York, Wen Kory Real and False States Group #16 North Carolina, South Dakota North Dakota, South Carolina