Path Counting

henryzz · 2014-09-15, 10:00

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?

wblipp · 2014-09-15, 11:46

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?

LaurV · 2014-09-15, 13:53

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)

henryzz · 2014-09-15, 15:59

You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.

cuBerBruce · 2014-09-15, 17:02

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.

henryzz · 2014-09-15, 17:25

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?

jasonp · 2014-09-15, 17:38

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?

cuBerBruce · 2014-09-15, 18:09

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.

cuBerBruce · 2014-09-15, 23:10

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.

Batalov · 2014-09-15, 23:12

[url]http://oeis.org/A007764[/url]

Batalov · 2014-09-15, 23:19

(using edges is like using a (n+1)*(n+1) board)

2014-09-15, 10:00	#1
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 13242₈ 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, 13:53	#3
LaurV Romulan Interpreter Jun 2011 Thailand 9153₁₀ 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, 17:02	#5
cuBerBruce Aug 2012 Mass., USA 100111110₂ 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:38	#7
jasonp Tribal Bullet Oct 2004 DCE₁₆ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
A counting problem	jasonp	Puzzles	1	2017-12-24 19:38
The Fastest Path	a1call	Puzzles	23	2016-03-23 17:46
Best settings and upgrade path for i7-2600	emily	Hardware	20	2012-03-02 08:45
Expected Path Length	davar55	Puzzles	12	2008-02-26 21:53
Are you in the path of Isabel	jocelynl	Soap Box	14	2003-09-22 20:38

2014-09-15, 15:59	#4
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2×2,897 Posts	You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.

2014-09-15, 23:12	#10
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×11×421 Posts	[url]http://oeis.org/A007764[/url]

2014-09-15, 23:19	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·11·421 Posts	(using edges is like using a (n+1)*(n+1) board)