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 =
["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"];

Aug 07 2008

Wyverex <wyverex.cypher gmail.com> writes:

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 );
         }
       }
     }
   }
}

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

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
        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

Aug 08 2008

BCS <ao pathlink.com> writes:

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]);
    }
  }
}

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

Aug 08 2008

BCS <ao pathlink.com> writes:

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!!!

Aug 08 2008

D Programming

C/C++ Programming

Other

digitalmars.D.learn - Word Puzzle