Introduction

This answers the fivethirtyeight.com Riddler challenge for this week. The challenge asks:

What is the longest word that shares no letters with a name of a state in the United States, and only that one state. For example, the word “mackerel” shares no letters with the state of “Ohio”, but shares at least one letter with the other 49 states names

Set manipulations

While I’m sure This problem can be solved by some clever application of: Set distributive law: \(A \cup (B \cap C) = (A \cup B) \cap (A \cup B)\) and De Morgan’s law: \(\neg A \cup \neg B = \neg(A \cup B)\)

But get real, this is one of those situations where the computer completes the brute-force computation in less than one second.

Just let the computer count

# load data
names_of_states <- tolower(state.name) 
words <- unlist(read.delim("https://norvig.com/ngrams/word.list", header=F, stringsAsFactors=F))
word_length <- nchar(words)

# the common_letters matrix has a row for each word, and a column for each state
# loop each of the 27 letters and populate the matrix
#     adding TRUE if the letter is both in the word and the state
shares_letters <- matrix(F, nrow=length(words), ncol=length(names_of_states), dimnames=list(words, state.abb))
for(iter_letter in letters){
  states_with_letter <- grepl(iter_letter, names_of_states)
  words_with_letter <- grepl(iter_letter, words)
  shares_letters[words_with_letter, states_with_letter] <- T
}

# Let me show you what I'm talking about
head(shares_letters)
##          AL   AK   AZ   AR   CA   CO    CT   DE   FL   GA   HI   ID    IL
## aa     TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE FALSE
## aah    TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE FALSE
## aahed  TRUE TRUE TRUE TRUE TRUE TRUE  TRUE TRUE TRUE TRUE TRUE TRUE FALSE
## aahing TRUE TRUE TRUE TRUE TRUE TRUE  TRUE TRUE TRUE TRUE TRUE TRUE  TRUE
## aahs   TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE  TRUE
## aal    TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE  TRUE
##          IN   IA   KS    KY   LA   ME   MD   MA   MI   MN    MS    MO   MT
## aa     TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE TRUE FALSE FALSE TRUE
## aah    TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE TRUE FALSE FALSE TRUE
## aahed  TRUE TRUE TRUE  TRUE TRUE TRUE TRUE TRUE TRUE TRUE FALSE FALSE TRUE
## aahing TRUE TRUE TRUE  TRUE TRUE TRUE TRUE TRUE TRUE TRUE  TRUE  TRUE TRUE
## aahs   TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE TRUE  TRUE  TRUE TRUE
## aal    TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE TRUE TRUE FALSE FALSE TRUE
##          NE   NV   NH    NJ    NM    NY   NC   ND    OH   OK    OR   PA
## aa     TRUE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE FALSE TRUE
## aah    TRUE TRUE TRUE FALSE FALSE FALSE TRUE TRUE  TRUE TRUE FALSE TRUE
## aahed  TRUE TRUE TRUE  TRUE  TRUE  TRUE TRUE TRUE  TRUE TRUE  TRUE TRUE
## aahing TRUE TRUE TRUE  TRUE  TRUE  TRUE TRUE TRUE  TRUE TRUE  TRUE TRUE
## aahs   TRUE TRUE TRUE  TRUE FALSE FALSE TRUE TRUE  TRUE TRUE FALSE TRUE
## aal    TRUE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE FALSE TRUE
##          RI   SC   SD    TN   TX   UT    VT   VA   WA   WV    WI    WY
## aa     TRUE TRUE TRUE FALSE TRUE TRUE FALSE TRUE TRUE TRUE FALSE FALSE
## aah    TRUE TRUE TRUE FALSE TRUE TRUE FALSE TRUE TRUE TRUE FALSE FALSE
## aahed  TRUE TRUE TRUE  TRUE TRUE TRUE  TRUE TRUE TRUE TRUE FALSE FALSE
## aahing TRUE TRUE TRUE  TRUE TRUE TRUE  TRUE TRUE TRUE TRUE  TRUE  TRUE
## aahs   TRUE TRUE TRUE  TRUE TRUE TRUE FALSE TRUE TRUE TRUE  TRUE FALSE
## aal    TRUE TRUE TRUE FALSE TRUE TRUE FALSE TRUE TRUE TRUE FALSE FALSE
# the mackrels are the rows where there is only one "FALSE"
mackerels <- (rowSums(!shares_letters) == 1)

# show longest mackerels
longest_mackerel<- max(word_length[mackerels])
words[mackerels & word_length == longest_mackerel]
##                   V148392                  V1106218 
## "counterproductivenesses" "hydrochlorofluorocarbon"
# find the state with the most mackerels
state_owned <- apply(shares_letters[mackerels,], 1, function(x) { which(x == 0) })
table(state.name[state_owned])
## 
##      Alabama       Alaska     Colorado  Connecticut     Delaware 
##         8274         1261          481            9          399 
##       Hawaii     Illinois      Indiana         Iowa       Kansas 
##         1763           79          482          201          884 
##     Kentucky        Maine     Maryland     Michigan  Mississippi 
##         1580           14           67            4         4863 
##     Missouri      Montana       Nevada   New Jersey   New Mexico 
##           73          648         1229          337           30 
##     New York North Dakota         Ohio     Oklahoma       Oregon 
##          105           54        11342          369          682 
##    Tennessee        Texas         Utah      Vermont     Virginia 
##         1339          639         6619           27          107 
##    Wisconsin      Wyoming 
##           60         1364

Holy Mackerel! Ohio is the winner with 11342 “mackerels”

Last week’s solution

See last week’s solution here: https://rpubs.com/nigelhenry/riddler_dungeons_and_dragons