mersenneforum.org Path Counting
 Register FAQ Search Today's Posts Mark Forums Read

 2014-09-15, 10:00 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 585810 Posts Path Counting I have just watched: https://www.khanacademy.org/math/rec...g-brain-teaser This made me think what would happen of you removed the restriction to down and right. Could you use a similar method? The method would have to be modified quite a bit. A special method of dealing with the possibility of getting trapped would be needed. Can anyone come up with an efficient way of solving this problem?
2014-09-15, 11:46   #2
wblipp

"William"
May 2003
New Haven

3·787 Posts

Quote:
 Originally Posted by henryzz I have just watched: https://www.khanacademy.org/math/rec...g-brain-teaser This made me think what would happen of you removed the restriction to down and right. Could you use a similar method? The method would have to be modified quite a bit. A special method of dealing with the possibility of getting trapped would be needed. Can anyone come up with an efficient way of solving this problem?
The first step is defining your new puzzle. For example, am I permitted to go back to the square I just left an unlimited number of times? Does your removal make diagonal moves possible? How about chess-knight moves?

 2014-09-15, 13:53 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 11×853 Posts Version 1: You can go in any direction, without crossing, without visiting the same square two times. No diagonal moves allowed (you still can go only left, right, up, down, like a chess rook, and only one square at a time). This makes a nice puzzle in itself. You are allowed (if you like) to make distinction between odd and even sized boards. (edit: I just got the badge for 20 minutes of video watched totally, since I am member there, hahaha) Last fiddled with by LaurV on 2014-09-15 at 13:55
 2014-09-15, 15:59 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2×29×101 Posts You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.
 2014-09-15, 17:02 #5 cuBerBruce     Aug 2012 Mass., USA 2·3·53 Posts Code: 2x2: ......... 2 3x3: ........ 12 4x4: ....... 184 5x5: ...... 8512 6x6: ... 1262816 I assume path must starts at upper left corner and end at lower right corner.
2014-09-15, 17:25   #6
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts

Quote:
 Originally Posted by cuBerBruce Code: 2x2: ......... 2 3x3: ........ 12 4x4: ....... 184 5x5: ...... 8512 6x6: ... 1262816 I assume path must starts at upper left corner and end at lower right corner.
How did you come by those numbers? Can your method easily scale to 20x20 etc?

 2014-09-15, 17:38 #7 jasonp Tribal Bullet     Oct 2004 33×131 Posts This is closely related to one of the fundamental problems of molecular biology: aligning DNA or protein sequences can be thought of as making a checkerboard with one sequence across the top and the other sequence down the left side. Then an alignment between the two sequences is a path that only goes in horizontal, vertical or diagonal steps from the top left to the bottom right. If each such move has a score, finding the highest-scoring such path is very useful. It's even more useful to find all of the highest-scoring isolated paths somewhere inside the checkerboard. This turns out not to be easy given the number of paths to check; the Smith-Waterman and Needleman-Wunsch algorithms solve the sequence alignment problem via dynamic programming in a number of steps that's only quadratic in the sequences sizes. You can probably count the number of paths in the same way. Believe it or not, this used to be my job :) You can also represent the alignment problem as a graph, and the generalized problem you're considering would mean dealing a directed graph. Maybe use breadth-first search to do the counting? Last fiddled with by jasonp on 2014-09-15 at 17:46
2014-09-15, 18:09   #8
cuBerBruce

Aug 2012
Mass., USA

2×3×53 Posts

Quote:
 Originally Posted by henryzz How did you come by those numbers? Can your method easily scale to 20x20 etc?
I wrote a brute force recursive algorithm using GAP. I'm trying 7x7 now, and its taking awhile. So far it's only tried { right, right } for the first two moves. As coded, I suspect 7x7 may be the practical limit.

It could probably made much more efficient, especially if recoded carefully in C, but the number of paths increases so rapidly with increase grid size, I doubt this brute force approach would be useful for much larger than 7x7.

2014-09-15, 23:10   #9
cuBerBruce

Aug 2012
Mass., USA

2×3×53 Posts

Quote:
 Originally Posted by cuBerBruce I wrote a brute force recursive algorithm using GAP. I'm trying 7x7 now, and its taking awhile.
It finished. The value I got was 575780564.

 2014-09-15, 23:12 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,391 Posts [url]http://oeis.org/A007764[/url]
 2014-09-15, 23:19 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 939110 Posts (using edges is like using a (n+1)*(n+1) board)

 Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Puzzles 1 2017-12-24 19:38 a1call Puzzles 23 2016-03-23 17:46 emily Hardware 20 2012-03-02 08:45 davar55 Puzzles 12 2008-02-26 21:53 jocelynl Soap Box 14 2003-09-22 20:38

All times are UTC. The time now is 13:08.

Tue Apr 20 13:08:18 UTC 2021 up 12 days, 7:49, 0 users, load averages: 3.25, 3.43, 2.85