Word Puzzle (spoiler)

[bearophile]

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