"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 =
["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",
"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 =
["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",
"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 );
        }
      }
    }
  }
}

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 =
> ["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",
> "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.

http://www.reddit.com/comments/5zhs8/a_simple_programming_puzzle_seen_through_three/c02ceab

(Spoiler. Duh.)

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
        mississippi missouri montana nebraska nevada
        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
    mississippi missouri montana nebraska nevada
    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
        mississippi missouri montana nebraska nevada
        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;
            if (!(sign in sign_pairs))
                sign_pairs[sign] = new Set!(string[]);
            sign_pairs[sign].add([state1, state2]);
        }

    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
    mississippi missouri montana nebraska nevada
    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()
        sign_pairs[sign].add((state1, state2))
print [pairs for pairs in sign_pairs.itervalues() if len(pairs) > 2]

Bye,
bearophile

Reply to wyverex,

> static char[][50] 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",
> "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]);
   }
 }
}

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 =
> ["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",
> "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 =
["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",
"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

Reply to Mike,

//All 50 states, lowercase, no spaces!!
> static char[][50] 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",
> "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!!!