All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Counting Ten Segment Paths (Posted on 2016-02-19) Difficulty: 2 of 5
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?

No Solution Yet Submitted by Brian Smith    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution The basic set (rotations and reflections eliminated) Comment 6 of 6 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information