Recently, a Python guru, David C. Amos has been putting out some Graph Theory videos. These are fun and happen to be something I’ve wanted to learn for quite some time.

Last week he started a coding challenge that will run weekly(ish). I missed the Sunday deadline but solved it anyway. And not only did I solve it poorly, but the newest computer I used is 38 years old.

The problem

Please check out his Youtube Channel and Github for all of the details. I’d highly recommend you try this using whatever method you find fun.

This is word for word from Github:

This week’s puzzle is about planning a road trip. You’ve flown to Omaha, Nebraska, and plan to rent a car and drive through each of the eight US states shows below:

Can you find a route that passes through all eight states in such a way that you cross each state’s border exactly once? That is, your route must pass:

• The Nebraska (NE) — Wyoming (WY) border once
• The Nebraska (NE) — South Dakota (SD) border once
• The South Dakota (SD) — Wyoming (WY) border once
• And so on

This problem is Problem 6.1 in Problem Solving Through Recreational Mathematics by Bonnie Averbach and Orin Chein.

Feel free to use your favorite programming language to solve the problem. Bonus points if you can find all possible routes!

Python Solutions

David and several others used Python for their solutions. Check out the video:

I learned a TON from each of their solutions, and they are worth some further study.

Implementing it in BASIC

I approached this problem via brute force. This happens to work in this case in a reasonable amount of time. In the future, I suspect we’ll have to make more than a couple of subroutines in Assembly if we want to keep up with the cool kids running Python with their multi-Gigahertz processors and fancy data types.

First, we need to define the states and the borders. I broke them up with borders as letters and the states as integers:

Next, we need to define all 12 possible State and border crossing possibilities:

720 BS$(0)="0A1"
730 BS$(1)="0B3"
740 BS$(2)="1C3"
750 BS$(3)="1D4"
760 BS$(4)="1E2"
770 BS$(5)="2F4"
780 BS$(6)="4G3"
790 BS$(7)="3H5"
800 BS$(8)="4I5"
810 BS$(9)="5J6"
820 BS$(10)="5K7"
830 BS$(11)="6L7"

Next, we just start randomly checking if we can move in one direction or another and removing paths once we’ve crossed them. This is one area where A LOT of optimization could be done.

400 REM TRY ROUTE
410 FORT=0TO150
420 I=INT(RND(1)*12):IFBS$(I)=""GOTO490
430 J=VAL(MID$(BS$(I),1,1))
440 IFJ=CSTHEN TR$=TR$+MID$(BS$(I),2,1):CS=VAL(MID$(BS$(I),3,1)):BS$(I)=""
470 J=VAL(MID$(BS$(I),3,1))
475 IFJ=CSTHEN TR$=TR$+MID$(BS$(I),2,1):CS=VAL(MID$(BS$(I),1,1)):BS$(I)=""
490 NEXT
499 RETURN

Now, let’s check for a complete route which I called a “match,” and then check to see if we’ve seen it before (more arrays, so many wasted bytes! I told you this was a terrible solution!!!)

500 REM CHECK ROUTE
520 PRINTTR$INT(TI/60)"SECS ";
530 IFLEN(TR$)=12THENPRINT"MATCH!";:GOSUB600:PRINTCT:GOTO599
540 PRINT
599 RETURN
600 REM CHECK AND STORE UNIQUES
610 FORZ=1TO100
620 IFSO$(Z)=TR$THENRETURN
630 NEXT
640 CT=CT+1
650 SO$(CT)=TR$
660 IF CT=64THENGOSUB900:END
699 RETURN

That’s really it. The rest is glue code and some setup and tracking of where we are. My whole solution is:

10 REM BORDER CROSSING CHALLENGE #1 STATE
15 REM MICHAEL DOORNBOS - MIKE AT IMAPENGUIN.COM - 2021
20 TI$="000000"
100 DIMSO$(100):DIMBS$(12):TR$="":CT=0:CS=0
110 FOR K=0TO10000
115 TR$="":CS=0
120 GOSUB 700
150 GOSUB 400
160 GOSUB 500
170 NEXT
399 END
400 REM TRY ROUTE
410 FORT=0TO150
420 I=INT(RND(1)*12):IFBS$(I)=""GOTO490
430 J=VAL(MID$(BS$(I),1,1))
440 IFJ=CSTHEN TR$=TR$+MID$(BS$(I),2,1):CS=VAL(MID$(BS$(I),3,1)):BS$(I)=""
470 J=VAL(MID$(BS$(I),3,1))
475 IFJ=CSTHEN TR$=TR$+MID$(BS$(I),2,1):CS=VAL(MID$(BS$(I),1,1)):BS$(I)=""
490 NEXT
499 RETURN
500 REM CHECK FOR ALREADY MADE
520 PRINTTR$INT(TI/60)"SECS ";
530 IFLEN(TR$)=12THENPRINT"MATCH!";:GOSUB600:PRINTCT:GOTO599
540 PRINT
599 RETURN
600 REM CHECK AND STORE UNIQUES
610 FORZ=1TO100
620 IFSO$(Z)=TR$THENRETURN
630 NEXT
640 CT=CT+1
650 SO$(CT)=TR$
660 IF CT=64THENGOSUB900:END
699 RETURN
700 REM SETUP POSSIBLE ROUTES
720 BS$(0)="0A1"
730 BS$(1)="0B3"
740 BS$(2)="1C3"
750 BS$(3)="1D4"
760 BS$(4)="1E2"
770 BS$(5)="2F4"
780 BS$(6)="4G3"
790 BS$(7)="3H5"
800 BS$(8)="4I5"
810 BS$(9)="5J6"
820 BS$(10)="5K7"
830 BS$(11)="6L7"
899 RETURN
900 REM PRINT RESULTS
910 PRINT:PRINT"---------------------------"
920 PRINT"LIST OF ALL VALID ROUTES:"
930 FORR=1TOCT:PRINTSO$(R);" ";:NEXT
940 PRINT:PRINT"TOTAL TIME: "TI/60" SECONDS
950 PRINT"TOTAL LOOPS: "K
999 RETURN

Let’s run it

It took just over an hour to get all 64 possible routes.

Some concessions

I knew ahead of time that there are 64 possible solutions to this problem. I suppose left running long enough; this method would make this number clear. Since I’m new to this, I accepted 64 as the target number ahead of time and stopped after getting all of the unique trips that covered all of the borders.

What will this run on?

As always, my main goal is to do these problems with an unexpanded VIC-20 in mind. If I can get something down to 3583 bytes, I will. This runs quite well on the VIC, and except for the TI strings (to count the time passing), these should run on all 8 Bit Computers from the late 70s and 80s running similar BASIC implementations to this Microsoft BASIC 2.0.

Need it faster?

I happen to have a Color Maximite 2, which runs many times faster than a 6502/10 processor at 1Mhz. Just for fun here is the same code on a more modern machine:

What’s next

The next challenge is already posted. Get coding and have fun.