mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2014-09-15, 10:00   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

11·523 Posts
Default 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?
henryzz is offline   Reply With Quote
Old 2014-09-15, 11:46   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by henryzz View Post
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?
wblipp is offline   Reply With Quote
Old 2014-09-15, 13:53   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

214028 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2014-09-15, 15:59   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

11·523 Posts
Default

You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.
henryzz is offline   Reply With Quote
Old 2014-09-15, 17:02   #5
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

4768 Posts
Default

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.
cuBerBruce is offline   Reply With Quote
Old 2014-09-15, 17:25   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131718 Posts
Default

Quote:
Originally Posted by cuBerBruce View Post
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?
henryzz is offline   Reply With Quote
Old 2014-09-15, 17:38   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·883 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2014-09-15, 18:09   #8
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

31810 Posts
Default

Quote:
Originally Posted by henryzz View Post
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 is offline   Reply With Quote
Old 2014-09-15, 23:10   #9
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

13E16 Posts
Default

Quote:
Originally Posted by cuBerBruce View Post
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.
cuBerBruce is offline   Reply With Quote
Old 2014-09-15, 23:12   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23DE16 Posts
Default

[url]http://oeis.org/A007764[/url]
Batalov is offline   Reply With Quote
Old 2014-09-15, 23:19   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts
Default


(using edges is like using a (n+1)*(n+1) board)
Batalov is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 16:47.

Thu Dec 3 16:47:34 UTC 2020 up 12:58, 0 users, load averages: 1.42, 1.55, 1.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.