Multiple paths can be drawn on the grid below following along ten of the twelve segments but never using any segment twice.
+--+--+
| | |
+--+--+
| | |
+--+--+
How many such paths are there?
I used a program to deduce the sequence of right and left turns in each of the 200 overall paths, and listed only the ones where the first turn (not a straight ahead node) was to the right,leaving 100, exactly half as expected. This file was sorted so all that had the same rls sequence were together so that duplicates (there was indeed 4 of each, representing rotations) could be eliminated manually. The 25 remaining are shown below: first the right,left,straight sequence, then the segments traversed in the remaining example of that sequence, and then the two segments not traversed.
rlllrllsl dfhkigebac jl
rllslslsl dfhkljebac gi
rrlrrrlll begikhfdac jl
rrlrrsrrr begikhcadf jl
rrrlllrll begdacfilj hk
rrrlllrrr begdacfikh jl
rrrllslll begdachkif jl
rrrllslsl begdachklj fi
rrrsrrlll dfcabegilj hk
rrrsrrlrr dfcabegikh jl
rrrsrsrrr dfcabejlig hk
rrrsrsrsr dfcabejlkh gi
rrslllsll begfhkidac jl
rrsrrrsll begfcadilj hk
rrsrrrsrr begfcadikh jl
rsrrlrrrl bejlifcadg hk
rsrrsllls bejlidacfg hk
rsrrsllsl bejlidachk fg
rsrsrrlll bejlkhfdac gi
rsrsrsrrl bejlkhcadg fi
rsrsrsrrr bejlkhcadf gi
rsrsrsrrs bejlkhcadi fg
srrrsllsl dikhfgebac jl
srrsrsrrs dikhcabegf jl
srrsrsrsr dikhcabejl fg
DefDbl A-Z
Dim crlf$, seg(12) As String
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
Open "ten seg ref.txt" For Input As #1
For i = 1 To 12
Line Input #1, seg(i)
Next
Close 1
Open "ten seg input.txt" For Input As #1
Do
Line Input #1, l$
bld$ = ""
turnseq$ = "": firstturn$ = ""
For i = 1 To 28 Step 3
lkup$ = Mid(l, i, 5)
dy = Val(Mid(lkup, 5, 1)) - Val(Mid(lkup, 2, 1))
dx = Val(Mid(lkup, 4, 1)) - Val(Mid(lkup, 1, 1))
prevd$ = d$
If dy = 1 Then
d$ = "u"
ElseIf dy = -1 Then
d$ = "d"
ElseIf dx = 1 Then
d$ = "r"
ElseIf dx = -1 Then
d$ = "l"
End If
If i > 1 Then
Select Case prevd + d
Case "ur", "rd", "dl", "lu"
turnseq = turnseq + "r"
Case "ul", "ru", "dr", "ld"
turnseq = turnseq + "l"
Case "uu", "rr", "dd", "ll"
turnseq = turnseq + "s"
End Select
If (Right(turnseq, 1) = "r" Or Right(turnseq, 1) = "l") And firstturn = "" Then
firstturn = Right(turnseq, 1)
End If
End If
For j = 1 To 12
If InStr(seg(j), lkup) > 0 Then Exit For
Next
If j > 12 Then Text1.Text = Text1.Text & "error": Exit Sub
' Text1.Text = Text1.Text & Left(seg(j), 1)
bld = bld & Left(seg(j), 1)
Next
If firstturn = "r" Then
Text1.Text = Text1.Text & turnseq & " " & bld & " "
For i = 1 To 12
If InStr(bld, Mid("abcdefghijkl", i, 1)) = 0 Then Text1.Text = Text1.Text & Mid("abcdefghijkl", i, 1)
Next
Text1.Text = Text1.Text & crlf
rct = rct + 1
End If
Loop Until EOF(1)
Text1.Text = Text1.Text & crlf & rct & " done"
End Sub
|
|
Posted by Charlie
on 2016-02-19 20:48:00 |
The basic set (rotations and reflections eliminated)
