# Are these states connected?

With the US election going on right now, I noticed that there is one (completely meaningless, but still) thing which Trump can still achieve and which is out of reach for Biden: Having the won states being connected.

Task: Given a list of strings of two-letter abbreviations (see below) for US states, determine whether they are connected. That is, is the graph whose edges are the states in this list and where two edges are connected whenever the corresponding states are neighbors to each other connected? That is, for each two states, does there exist a path (in this graph) from one to another?

On Githhub, ubikuity has compiled a list of neighboring US states, which I copy here for convenience:

AK,WA
AL,FL
AL,GA
AL,MS
AL,TN
AR,LA
AR,MO
AR,MS
AR,OK
AR,TN
AR,TX
AZ,CA
AZ,CO
AZ,NM
AZ,NV
AZ,UT
CA,HI
CA,NV
CA,OR
CO,KS
CO,NE
CO,NM
CO,OK
CO,UT
CO,WY
CT,MA
CT,NY
CT,RI
DC,MD
DC,VA
DE,MD
DE,NJ
DE,PA
FL,GA
GA,NC
GA,SC
GA,TN
IA,IL
IA,MN
IA,MO
IA,NE
IA,SD
IA,WI
ID,MT
ID,NV
ID,OR
ID,UT
ID,WA
ID,WY
IL,IN
IL,KY
IL,MO
IL,WI
IN,KY
IN,MI
IN,OH
KS,MO
KS,NE
KS,OK
KY,MO
KY,OH
KY,TN
KY,VA
KY,WV
LA,MS
LA,TX
MA,NH
MA,NY
MA,RI
MA,VT
MD,PA
MD,VA
MD,WV
ME,NH
MI,OH
MI,WI
MN,ND
MN,SD
MN,WI
MO,NE
MO,OK
MO,TN
MS,TN
MT,ND
MT,SD
MT,WY
NC,SC
NC,TN
NC,VA
ND,SD
NE,SD
NE,WY
NH,VT
NJ,NY
NJ,PA
NM,OK
NM,TX
NM,UT
NV,OR
NV,UT
NY,PA
NY,VT
OH,PA
OH,WV
OK,TX
OR,WA
PA,WV
SD,WY
TN,VA
UT,WY
VA,WV


To be clear, “to be a neighbor of” is symmetric and hence the entry AK,WA means that AK neighbors WA and that WA neighbors AK. There might be some disagreement whether some of these states are indeed neighbors of each other but for the purpose of this question, let us go with the list above. (Although that would mean that Trump needs to lose Alaska in order to have his won states connected.)

Input: A list of two-letter strings or something equivalent such as a single string consisting of a series of two-letter pairs such as "AK WA OR" or "AKWAOR". It may be assumed that each string is one of the two-letter abbreviations in the list above and that no string appears more than once in the list.

Output: Return/Ouput a truthy value if the states are connected and a falsey value if they are not.

(Very!) simple test cases:

• [] is connected.

• ["AK"] is connected.

• ["AK", "WA", "OR"] is connected.

• ["UT", "CO", "WY", "KS", "NM"] is connected. (That is, they form a connected graph although they do not form a “line” of neighboring states.)

• ["AK", "OR"] is not connected.

• ["ID", "OR", "WA", "AL", "GA", "TN"] is not connected.

This is , so shortest code in bytes wins.

• Will the input always be connected in the order given (if connected)? Is IA IN IL considered connected if input in that way? Nov 9, 2020 at 21:00
• Not quire sure why this has been VTCed. As far as I can tell, this is a very clear challenge, with a couple of clarifications which have been made. Would the close voter mind clarifying their reasoning for the rest of us, so we can understand why you've voted? Nov 9, 2020 at 21:23
• A graph with two nodes and zero edges is not connected.
– Keba
Nov 10, 2020 at 0:26
• I suggest adding a falsey test case with two isolated, fully connected subgraphs e.g. ["ID", "OR", "WA", "AL", "GA", "TN"] Nov 10, 2020 at 17:58
• Looks like this was our 10,000th code-golf question - Congrats :) Nov 12, 2020 at 16:49

# Wolfram Language (Mathematica), 169 167 bytes

ConnectedGraphQ@Subgraph[Cases[#[v="StateAbbreviation"]&/@#@"BorderingStates"#@v&/@Interpreter["USState"]@#|"CA""HI"|"AK""WA"/."MI""MN"|"NY""RI"->0,a_ b_:>a<->b,3],#]&


Try it online!

TIO doesn't have data sets downloaded, so most of the footer is to ensure the code works as if they had been.

The BorderingStates properties differ from the given list of adjacencies in four ways: HI and AK do not border any other states, MI borders MN, and NY borders RI.

Interpreter["USStates"]@#           (* get Entitys corresponding to abbreviations *)
#@"BorderingStates"                 (* for each state, get a list of bordering states, *)
#[v="StateAbbreviation"]&/@ % #@v&  (* pair it (unordered) with each of those and convert back to abbreviations. *)
% /@ %%% |"CA""HI"|"AK""WA"         (* append CA-HI and AK-WA, *)
% /."MI""MN"|"NY""RI"->0            (* discard MI-MN and NY-RI, *)
Cases[ % ,a_ b_:>a<->b,3]           (* then get all pairs and convert them to edges. *)
ConnectedGraphQ@Subgraph[ % ,#]&    (* is the subgraph consisting of input states connected? *)


There's also GraphData["ContiguousUSAGraph"], which is missing AK-WA, AZ-CO, CA-HI, and NM-UT edges. Unfortunately, the vertices are numbered in what seems to be an arbitrary order.

• Always fun to see what's built-in in Mathematica. Nice!
– Keba
Nov 10, 2020 at 8:53
• It's odd that the given list includes AK-WA and CA-HI but does not include MI-MN or NY-RI, which actually do have legally defined shared borders (even if they are entirely in the water). At least they seem to agree that the AZ-CO-NM-UT Four Corners counts as all 4 states bordering eachother... Nov 10, 2020 at 21:29
• @DarrelHoffman Agreed. I was happy to find any list and thought that one might make an argument for AK-WA and CA-HI and just kept the list as-is. And yes, then one should also include MI-MN and NY-RI, I guess. (Apart from this answer, the exact list should not matter too much for golfing, however.)
– Keba
Nov 11, 2020 at 13:18

# JavaScript (ES6), 360 bytes

Returns a Boolean value.

A=>!A.some(s=>s,(g=x=>A.map((s,j)=>'dx5d0w805045081o3klg165343501b328xi342010q4z45v3161r7k0q168i383xe40h3k0e0e3j7f090g6i190x120w621h0oax504lfbqd1b1n9g601l4rbb6o1c0p1v262h6vdy4lac1t561n1f06pnkm443q6jpq845x0u1a1c080y2z3a25112b1q9um81cgs1e041s530abh1k1zksin6d0w'.match(/../g).every(s=>t-=P(s,36),t=(P=parseInt)(x>s?s+x:x+s,36)%22958+1)||g(j),A[x=A[i=x],i]=0))(0))


Try it online!

# 05AB1E, 207 ... 194 187 bytes

Thanks to Kevin Cruijssen for -1 byte!
+65 bytes because I had a bug in the generation program and forgot to include quite a few borders.

.•K0®Z"E=м7δþˆLäZΩcÉ!P0:n~Žæ₃ƒû‡âQƶºìtu×^èÂā„∊\¦₁ôβ2Èœ÷Š±TBÀ7Ã•u2ôIkDδ‚εε•AмÎÝ≠ζó'#‚Ó¶–ºÇΘ¶7˜H»«âиÈ8ëf:ÝQº[EÍø’Δ₁#ÍÂ|Q₄T´ƶŽ#UΣMW„é!ʒHµßŠ¸ô7¬·ΔŠ¥Ò÷¾kå«ÛǝO₆ðÿ•51вηOs{R38*+åyË+]DvDøδ*O}˜ĀP


Try it online!

This generates a adjacency matrix $$\A\$$ of the given states and checks if it represents a connected graph using a modified method from this math.se answer. Instead of calculating $$\A^k\$$, we calculate $$\A^{2k}\$$, because it is shorter.
For some reason the matrix multiplication code øδ*O is really slow, this means that the test case with five states doesn't finish on TIO. Edit: The lazy evaluation seems to cause problems here, resulting in extrememly long execution time.

Commented:

.•K...Ã•u2ôIkDδ‚             # convert from list of abbreviations to matrix of integer pairs
.•K...Ã•                     # push compressed string "mirivaiascaldcoknjmoakmtcapacohidevtkywiinmemanmksilwaorgamnsdidohneflnctnnywywvmsndtxnhctarnvmdutlaaz"
# this is the concatenation of all state abbreviations
u                  # convert to uppercase
2ô                # split into groups of 2
Ik              # find the index of the each input in this state list
D             # duplicate
δ‚           # and create a matrix of all pairs

εε•A...ÿ•51вηOs{R38*+åyË+]  # calculate adjacencies
ε                            # map over the rows:
ε                           # map over the pairs:
•A...ÿ•51в                 # push compressed integer list [19, 1, ..., 26, 50]
η                # get all prefixes
O               # sum every prefix
# this list now contains all adjacent states represented as
#   a + b*38, where a>b
# it also contains some pairs (a, a), this reduces the maximum difference
#   between integers, leading to shorter compression in a lower base
s              # swap to current pair
{R            # sort and reverse it => [a, b]
# push both numbers on the stack
38*        # multiply b by 38
+       # sum both values
# this maps a few different pairs of states to the same integers,
#  but with the given permutations of states this is fine
å      # is this contained in the list?
y     # push the pair again
Ë    # are all values equal? (is this the same state twice?)
+   # sum / boolean or
]  # end both maps
# Now the adjacency matrix of the states is on the stack
#  ex.: for input ["AK","WA","OR"] this is [[1,1,0],[1,1,1],[0,1,1]]

DgFDøδ*O}˜ĀP                 # check if adjacency matrix is connected
D                            # duplicate the matrix
v     }                     # for each row square the current matrix M:
D                          #   duplicate the matrix
ø                         #   transpose it
δ                        #   for every pair of rows in M and M^T
*                       #   multiply element-wise
O                      #   and sum each list
˜                    # flatten the matrix
Ā                   # Check if every value is not 0
P                  # take the product / boolean all


Try it with step by step output!

• gF can be v for -1. And you can use --no-lazy for the test case of 5 states to work. Elixir can be a little weird with that sometimes, timing out or giving weird results with maps if it's in default lazy mode. EDIT: Ah, you've already figured the second one out 30 seconds ago, haha.. Nov 10, 2020 at 11:53
• @KevinCruijssen Ah I guess this why my other approach is "faster". Thanks for the byte!
– ovs
Nov 10, 2020 at 11:54
• Also, I'm not sure if you see a way to make it shorter, but the Dδ‚ could alternatively be ã for a flattened list of pairs. The εε...] can then be ε...}. Unfortunately, the rest of your code requires it to be in a list of lists, so you'd still need a Igô after the map (or simply changing the Dδ‚ to ã5ô) and the byte-count remains the same.. :( But figured I'd mention it in case you see something to do this shorter that I've overlooked. Nov 10, 2020 at 11:59
• @KevinCruijssen I couldn't find a way to use this either, but there is still some golfing potential. I'm currently searching for permutations that allow pairs to be mapped to smaller integers, and by including some borders between a state and itself, the border data can be compressed in a lower base.
– ovs
Nov 10, 2020 at 13:13

# Jelly,  143  139 bytes

,OṢ*/V%⁽]Ƙ%⁽9ḃ%⁽ðṭe“€LE<⁼,#g>Q#&68-s¦Ø¬Yḟ¢>ȷ*I¬Þ!Ƈ?øẇ@Þ²m>Ṡ3+@O*c÷©%"*Þ¢Ð⁾ẠþÑẈÐẈ"æ×ḳw³l¢qṠ©|4°€£Ð%½^©Ñ³©Ṇ-N¿ð!ƊẉœK)½ƇØX#²4÷+‘Ä¤ȯ⁼ðþæ*L$PẸ  A monadic Link accepting a list of lists of characters (valid state abbreviations) which yields 1 if the states are connected or 0 if not. Try it online! Or see the test-suite. ### How? ,OṢ*/V%⁽]Ƙ%⁽9ḃ%⁽ðṭe“...‘Ä¤ȯ⁼ðþæ*L$PẸ - Link: states
- use states as both arguments of:
þ        -   table using:   (makes an adjacency matrix)
ð         -     the dyadic chain, f(A, B):
,                                     -       pair -> [A, B]   e.g. ["HI", "CA"]
O                                    -       ordinals              [[72, 73], [67, 65]]
Ṣ                                   -       sorted                [[67, 65], [72, 73]]
/                                 -       reduce using:
*                                  -         exponentiation      [300182793244778239701651745925447642838407176218846116477308730441782375736846470235643437821593799141277880459172066217016359091361, 2201278718441498733883192946340630358395332861266884669706285143644864868806820973839329645162232740318586365901865065097808837890625]
V                                -       evaluate              3001827932447782397016517459254476428384071762188461164773087304417823757368464702356434378215937991412778804591720662170163590913612201278718441498733883192946340630358395332861266884669706285143644864868806820973839329645162232740318586365901865065097808837890625
⁽]Ƙ                            -       24399
%                               -       modulo                12108
⁽9ḃ                        -       15482
%                           -       modulo                12108
⁽ðṭ                    -       7225
%                       -       modulo                4883
“...‘              -       code-page-indices = [96, 12, 76, 69, 60, 140, 44, 35, 103, 62, 81, 35, 38, 54, 56, 45, 115, 5, 18, 7, 89, 235, 1, 62, 26, 42, 73, 7, 20, 33, 144, 63, 29, 246, 64, 20, 130, 109, 62, 205, 51, 43, 64, 79, 42, 99, 28, 6, 37, 34, 42, 20, 1, 15, 142, 171, 31, 16, 187, 15, 187, 34, 22, 17, 217, 119, 131, 108, 1, 113, 205, 6, 124, 52, 128, 12, 2, 15, 37, 10, 94, 6, 16, 131, 6, 180, 45, 78, 11, 24, 33, 145, 227, 30, 75, 41, 10, 144, 18, 88, 35, 130, 52, 28, 43]
Ä             -       cumulative sums = [96, 108, 184, 253, 313, 453, 497, 532, 635, 697, 778, 813, 851, 905, 961, 1006, 1121, 1126, 1144, 1151, 1240, 1475, 1476, 1538, 1564, 1606, 1679, 1686, 1706, 1739, 1883, 1946, 1975, 2221, 2285, 2305, 2435, 2544, 2606, 2811, 2862, 2905, 2969, 3048, 3090, 3189, 3217, 3223, 3260, 3294, 3336, 3356, 3357, 3372, 3514, 3685, 3716, 3732, 3919, 3934, 4121, 4155, 4177, 4194, 4411, 4530, 4661, 4769, 4770, 4883, 5088, 5094, 5218, 5270, 5398, 5410, 5412, 5427, 5464, 5474, 5568, 5574, 5590, 5721, 5727, 5907, 5952, 6030, 6041, 6065, 6098, 6243, 6470, 6500, 6575, 6616, 6626, 6770, 6788, 6876, 6911, 7041, 7093, 7121, 7164]
e                   -       exists in?            1
⁼          -       (A) equals (B)?       0
ȯ           -       logical OR            1
L    -   length
æ*     -   matrix power -> Adj^n_states
P  - product -> products of columns
Ẹ - any?


All this could be shorter if one manages to find a suitable salt and domain for Jelly's built-in hash atom, ḥ, but I don't really know how to find that needle.

# Charcoal, 266 bytes

≔Ｅ⪪Ｓ²⟦ι⟧θＦ⪪”}∨ⅉ\⁸)ιfP≦?OX↙“a:;τ,πC_Ｄβ⁶k4_4÷‽ΦI¹#μＯ⪪ς¶⎇≦↙xh\8ＢＮnkGＭïＴü)﹪▷；⮌Uχγx◧i◧⌊÷iXιh↧υηΠ�Ｅ~*>←ρ↧Ｄ!q⟦⦃№➙U&sU+]I⁹π‹¿ê⁸¤&º⌈ü{³⟦f‽?}Ｏ/ＱＺ7·Ｊ＆ＭＤＬnueÞW≕*"eε§ºＲ0q&ＲGTwbDLFＳ⁸~,*➙Ｊ↨a…⁷{¤[ε↖=ＤC⊞SＳ⌈BφＷ¦ï?ⅉIêＥχ⌊±±3 ·ι.×qShiδiＺyZ¤d↨Ｃζⅈr⪪Hσ ωＷJ”⁴ＦΦθ№κ…ι²ＦΦ⁻θ⟦κ⟧№λ✂ι²Ｗλ⊞κ⊟λ›²ＬΦθι


Try it online! Link is to verbose version of code. Takes input as a string of two-letter pairs. Note that Charcoal requires a trailing newline to identify an empty string. Output is a Charcoal boolean, i.e. - for connected, nothing for disconnected. Explanation:

≔Ｅ⪪Ｓ²⟦ι⟧θ


Split the input into states and create a list for each state.

Ｆ⪪”....”⁴


Split the compressed adjacency list into individual entries and loop over them.

ＦΦθ№κ…ι²


Loop over any entries in the input list that contain the first adjacent state.

ＦΦ⁻θ⟦κ⟧№λ✂ι²


Loop over any other entries in the input list that contain the second adjacent state.

Ｗλ⊞κ⊟λ


Merge all the states from the adjacent entry.

›²ＬΦθι


Check that there is only one list of states left.

# Python 2, 632596550549545 550 bytes

It's long but it works.

-36: Use regex and remove , and ; from compressed string (@nthnchu)

-46: Shorten for loops, compress lists (@ovs)

-1: Change print(len(i)==0) to print len(i)==0 (@nthnchu)

-4: Change len(i)==0 to i==[] (@nthnchu)

+5: Fix for [] by replacing f(i[0]) with if i:f(i[0]) (@nthnchu)

import re
i=input()
l=[re.findall('..',x)for x in re.findall("....","eJwVj2GyAyEIg8+WUdulCuwoi7X3P8jL+/FNECIa9A2M18B4U3VhhGEOYKqThekd878XX/wKiONnShK/JwouKbAs8Fm8r+LWiBb3Xpxz36eEooRRp9SitZZEbdRmn9puvPj2G1beWCRMIEOgVHWBNcGqgi1SNaRaSnUuelhvkEO3yehU+gd9xtqU6ldfyl9Z68t7P6wPeyfoSPSzc0DXQHwVdpGjmKLI0HpDa5Kd2jgTJ1vUrKotwppZlTnVw3SR4Cw4i32srGIMbcxqdVVr/7B/ZdjHjn1uGL/DS1/TJyx9WlIP+yfDrxt+7fQeX58bN3YuZqURD/cnz3+qZoSc".decode("base64").decode("zip"))]
def f(s):i.remove(s);[f(a)for a in[a[1-a.index(s)]for a in l if s in a]if a in i]
if i:f(i[0])
print i==[]


Try it online!

• You can save a few bytes with list comprehensions: l=[re.findall("..",x)for x in re.findall("....","eJ ... Sc".decode("base64").decode("zip"))] and def f(s):i.remove(s);[f(a)for a in[a[1-a.index(s)]for a in l if s in a]if a in i]
– ovs
Nov 10, 2020 at 16:45
• @ovs The for loops looked a little verbose to me but I didn't know how to shorten them (I haven't used python for golfing before). Thanks! Nov 10, 2020 at 16:54
• You might shorten in further by abbreviating 'from re import findall as b' Nov 12, 2020 at 9:25
• @rkellerm I thought about that and It's the same amount of bytes. Nov 12, 2020 at 22:15

# Red, 647 bytes

func[b][
s:{AKWA ALFLGAMSTN ARLAMOMSOKTNTX AZCACONMNVUT CAHINVOR COKSNENMOKUTWY CTMANYRI DCMDVA DEMDNJPA FLGA GANCSCTN IAILMNMONESDWI IDMTNVORUTWAWY ILINKYMOWI INKYMIOH KSMONEOK KYMOOHTNVAWV LAMSTX MANHNYRIVT MDPAVAWV MENH MIOHWI MNNDSDWI MONEOKTN MSTN MTNDSDWY NCSCTNVA NDSD NESDWY NHVT NJNYPA NMOKTXUT NVORUT NYPAVT OHPAWV OKTX ORWA PAWV SDWY TNVA UTWY VAWV}m:
copy#()foreach a split s sp[t: parse a[collect any[keep 2 skip]]u: take t
either m/:u[append m/:u t][put m u t]foreach v t[either m/:v[append m/:v u][put
m v to[]mold u]]]r: on if 1 < length? b[foreach a b[r: r and series?
find collect[d: copy b alter d a foreach e d[keep m/:e]]a]]r]
`

Try it online!

This is a horribly long and naive solution...