## digitalmars.D.learn - Word Puzzle

• Wyverex (15/15) Aug 07 2008 "Take the names of two U.S. States, mix them all together, then
• Wyverex (64/64) Aug 07 2008 import tango.io.Stdout;
• downs (4/22) Aug 07 2008 I answered this before.
• bearophile (78/78) Aug 08 2008 My solution in D, it's O(n^2):
• BCS (27/38) Aug 08 2008 import std.stdio;
• Mike Wey (29/53) Aug 08 2008 import tango.io.Stdout;
• BCS (3/27) Aug 08 2008 Bravo!!!
Wyverex <wyverex.cypher gmail.com> writes:
```"Take the names of two U.S. States, mix them all together, then
rearrange the letters to form the names of two other U.S. States. What
states are these?"

Mark answers with (spoiler!)

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];
```
Aug 07 2008
Wyverex <wyverex.cypher gmail.com> writes:
```import tango.io.Stdout;

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];

void main()
{
foreach( state1; states )
{
foreach( state2;states )
{
if( state1 == state2 ) continue;

int['z' - 'a' + 1] letters;  //store letters

//get all the letters in each state name
foreach(c; state1)
letters[c - 'a']++;

foreach(c; state2)
letters[c - 'a']++;

//now to find two states names we can make from these letters
STATE3:
foreach( state3; states)
{
if ( state3 == state1 || state3 == state2 )
continue;
auto lets = letters.dup;

foreach(c; state3)
{
if( lets[c -'a'] )
lets[c -'a']--;
else
continue STATE3;
}

//okay were good here!! next state!!
STATE4:
foreach(state4; states)
{
if ( state4 == state1 || state4 == state2 || state4 == state3 )
continue;
auto lets2 = lets.dup;

foreach(c; state4)
{
if( lets2[c -'a'] )
lets2[c -'a']--;
else
continue STATE4;
}

//yeah!!! now to test for left overs
foreach(i;lets2)
if(i != 0) continue STATE4;

//Got it!
Stdout.formatln( "{} + {} = {} + {}", state1, state2, state3,
state4 );
}
}
}
}
}
```
Aug 07 2008
downs <default_357-line yahoo.de> writes:
```Wyverex wrote:
"Take the names of two U.S. States, mix them all together, then
rearrange the letters to form the names of two other U.S. States. What
states are these?"

Mark answers with (spoiler!)

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];

I answered this before.

(Spoiler. Duh.)
```
Aug 07 2008
bearophile <bearophileHUGS lycos.com> writes:
```My solution in D, it's O(n^2):

import std.stdio, std.string;

void main() {
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
newhampshire newjersey newmexico newyork northcarolina
northdakota ohio oklahoma oregon pennsylvania rhodeisland
southcarolina southdakota tennessee texas utah vermont
virginia washington westvirginia wisconsin wyoming".split();

uint[string[]][string] sign_pairs;

foreach (state1; states)
foreach (state2; states)
sign_pairs[(state1 ~ state2).sort][[state1, state2]] = 0;

foreach (pairs; sign_pairs)
if (pairs.length > 2)
writefln(pairs);
}

In Python (it has built-in sets, they aren't useless):

states = """alabama alaska arizona arkansas california
colorado connecticut delaware florida georgia hawaii
idaho illinois indiana iowa kansas kentucky louisiana
maine maryland massachusetts michigan minnesota
newhampshire newjersey newmexico newyork northcarolina
northdakota ohio oklahoma oregon pennsylvania rhodeisland
southcarolina southdakota tennessee texas utah vermont
virginia washington westvirginia wisconsin wyoming""".split()

from collections import defaultdict
sign_pairs = defaultdict(set)
for state1 in states:
for state2 in states:
sign_pairs["".join(sorted(state1 + state2))].add((state1, state2))
print [pairs for pairs in sign_pairs.itervalues() if len(pairs) > 2]

This time using my libs (sets too) the code worsens because if a signature is
absent you unfortunately have to create explicitly a Set object (defaultdict of
Python exists to avoid this same thing):

import std.stdio, d.all;

void main() {
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
newhampshire newjersey newmexico newyork northcarolina
northdakota ohio oklahoma oregon pennsylvania rhodeisland
southcarolina southdakota tennessee texas utah vermont
virginia washington westvirginia wisconsin wyoming".split();

Set!(string[])[string] sign_pairs;

foreach (state1; states)
foreach (state2; states) {
auto sign = (state1 ~ state2).sort;
sign_pairs[sign] = new Set!(string[]);
}

putr(filter((Set!(string[]) p){return len(p)>2;}, sign_pairs.values));
}

If you don't want to use a defaultdict in Python you have to do the same thing:

states = """alabama alaska arizona arkansas california
colorado connecticut delaware florida georgia hawaii
idaho illinois indiana iowa kansas kentucky louisiana
maine maryland massachusetts michigan minnesota
newhampshire newjersey newmexico newyork northcarolina
northdakota ohio oklahoma oregon pennsylvania rhodeisland
southcarolina southdakota tennessee texas utah vermont
virginia washington westvirginia wisconsin wyoming""".split()

sign_pairs = {}
for state1 in states:
for state2 in states:
sign = "".join(sorted(state1 + state2))
if sign not in sign_pairs:
sign_pairs[sign] = set()
print [pairs for pairs in sign_pairs.itervalues() if len(pairs) > 2]

Bye,
bearophile
```
Aug 08 2008
BCS <ao pathlink.com> writes:
```Reply to wyverex,

static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];

import std.stdio;
void main()
{
alias byte[26] alpha;
alpha[50][50] set;

foreach(int i1, char[] state1; states)
foreach(int i2, char[] state2; states)
{
foreach(ref b; set[i1][i2]) b=0;
foreach(char c; state1) set[i1][i2][c-'a']++;
foreach(char c; state2) set[i1][i2][c-'a']++;
}

for(int i = 0; i < 50*50; i++)
{
int a = i % 50;
int b = i / 50;
for(int j = i+1; j < 50*50; j++)
{
int c = j % 50;
int d = j / 50;
if(c == b && a == d) continue;
if(set[a][b][] == set[c][d][])
writef("%s/%s == %s/%s\n", states[a], states[b], states[c], states[d]);
}
}
}
```
Aug 08 2008
Mike Wey <mike-wey example.org> writes:
```On Thu, 2008-08-07 at 21:43 -0400, Wyverex wrote:
"Take the names of two U.S. States, mix them all together, then
rearrange the letters to form the names of two other U.S. States. What
states are these?"

Mark answers with (spoiler!)

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];

import tango.io.Stdout;

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];

void main()
{
char[][char[]] pairs;

for(int i = 0; i < states.length; i++)
{
for(int j = i; j < states.length; j++)
{
if( (states[i] ~ states[j]).sort in pairs)
Stdout(states[i])(" ")(states[j])(" -> ")
(pairs[(states[i] ~ states[j]).sort]).newline;

pairs[(states[i] ~ states[j]).sort] = states[i] ~" "~states[j];
}
}
}

time ./states
northdakota southcarolina -> northcarolina southdakota

real	0m0.016s
user	0m0.013s
sys	0m0.003s

--
Mike Wey
```
Aug 08 2008
BCS <ao pathlink.com> writes:
```Reply to Mike,

//All 50 states, lowercase, no spaces!!
static char[][50] states =
"connecticut","delaware","florida","georgia","hawaii","idaho",
"illinois","indiana","iowa","kansas","kentucky","louisiana",
"maine","maryland","massachusetts","michigan","minnesota",
"newhampshire","newjersey","newmexico","newyork","northcarolina",
"northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
"southcarolina","southdakota","tennessee","texas","utah","vermont",
"virginia","washington","westvirginia","wisconsin","wyoming"];
void main()
{
char[][char[]] pairs;
for(int i = 0; i < states.length; i++)
{
for(int j = i; j < states.length; j++)
{
if( (states[i] ~ states[j]).sort in pairs)
Stdout(states[i])(" ")(states[j])(" -> ")
(pairs[(states[i] ~ states[j]).sort]).newline;
pairs[(states[i] ~ states[j]).sort] = states[i] ~" "~states[j];
}
}
}

Bravo!!!
```
Aug 08 2008