24
\$\begingroup\$

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 , so shortest code in bytes wins.

\$\endgroup\$
16
  • 2
    \$\begingroup\$ Will the input always be connected in the order given (if connected)? Is IA IN IL considered connected if input in that way? \$\endgroup\$ – Xcali Nov 9 '20 at 21:00
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ – caird coinheringaahing Nov 9 '20 at 21:23
  • 2
    \$\begingroup\$ A graph with two nodes and zero edges is not connected. \$\endgroup\$ – Keba Nov 10 '20 at 0:26
  • 2
    \$\begingroup\$ I suggest adding a falsey test case with two isolated, fully connected subgraphs e.g. ["ID", "OR", "WA", "AL", "GA", "TN"] \$\endgroup\$ – Jonathan Allan Nov 10 '20 at 17:58
  • 3
    \$\begingroup\$ Looks like this was our 10,000th code-golf question - Congrats :) \$\endgroup\$ – Shaggy Nov 12 '20 at 16:49
13
\$\begingroup\$

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? *)

screenshot of test cases in Mathematica


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.

ContiguousUSAGraph with labeled vertices

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Always fun to see what's built-in in Mathematica. Nice! \$\endgroup\$ – Keba Nov 10 '20 at 8:53
  • \$\begingroup\$ 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... \$\endgroup\$ – Darrel Hoffman Nov 10 '20 at 21:29
  • \$\begingroup\$ @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.) \$\endgroup\$ – Keba Nov 11 '20 at 13:18
9
\$\begingroup\$

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!

\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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.. \$\endgroup\$ – Kevin Cruijssen Nov 10 '20 at 11:53
  • \$\begingroup\$ @KevinCruijssen Ah I guess this why my other approach is "faster". Thanks for the byte! \$\endgroup\$ – ovs Nov 10 '20 at 11:54
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Nov 10 '20 at 11:59
  • \$\begingroup\$ @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. \$\endgroup\$ – ovs Nov 10 '20 at 13:13
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 266 bytes

≔E⪪S²⟦ι⟧θF⪪”}∨ⅉ\`⁸)ιfP≦?OX↙“a:;τ,πC_Dβ⁶k4_4÷‽ΦI¹#μO⪪ς¶⎇≦↙xh\8BNnkGMïTü)﹪▷;⮌Uχγx◧i◧⌊÷iXιh↧υηΠ�E~*>←ρ↧D!q⟦⦃№➙U&sU+]I⁹π‹¿ê⁸¤&º⌈ü{³⟦f‽?}O/QZ7·J&MDLnueÞW≕*"eε§ºR0q&RGTwbDLFS⁸~,*➙J↨a…⁷{¤[ε↖=DC⊞SS⌈BφW¦ï?ⅉIêEχ⌊±±3 ·ι.×qShiδiZyZ¤d↨Cζⅈr⪪Hσ ωWJ”⁴FΦθ№κ…ι²FΦ⁻θ⟦κ⟧№λ✂ι²Wλ⊞κ⊟λ›²LΦθι

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:

≔E⪪S²⟦ι⟧θ

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

F⪪”....”⁴

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

FΦθ№κ…ι²

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

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

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

Wλ⊞κ⊟λ

Merge all the states from the adjacent entry.

›²LΦθι

Check that there is only one list of states left.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – ovs Nov 10 '20 at 16:45
  • \$\begingroup\$ @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! \$\endgroup\$ – nthnchu Nov 10 '20 at 16:54
  • \$\begingroup\$ You might shorten in further by abbreviating 'from re import findall as b' \$\endgroup\$ – rkellerm Nov 12 '20 at 9:25
  • 1
    \$\begingroup\$ @rkellerm I thought about that and It's the same amount of bytes. \$\endgroup\$ – nthnchu Nov 12 '20 at 22:15
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.