www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Word Puzzle

reply 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
next sibling parent 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
prev sibling next sibling parent 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
prev sibling next sibling parent 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
prev sibling next sibling parent 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
prev sibling parent reply 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
parent 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