Are these states connected?

Question

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.

Standard I/O rules apply and standard loopholes are forbidden.

This is code-golf, so shortest code in bytes wins.

Answer 1

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.

Answer 2

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!

Answer 3

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{R`38*+å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{R`38*+å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!

Answer 4

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
                         ¤            -       nilad followed by link(s) as a nilad:
                   “...‘              -       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
                                  $   - last two links as a monad:
                                 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.

Answer 5

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.

Answer 6

Python 2, 632 596 550 549 545 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!

Answer 7

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