mersenneforum.org May 2019
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-01, 12:48 #1 Xyzzy     "Mike" Aug 2002 3·2,683 Posts May 2019
 2019-05-08, 05:20 #2 SmartMersenne   Sep 2017 32×11 Posts Any ideas on how to solve this?
2019-05-08, 10:34   #3
Dieter

Oct 2017

2·5·11 Posts

Quote:
 Originally Posted by SmartMersenne Any ideas on how to solve this?
Nice and difficult challenge. I have needed some time to program the “breadth first search” (which I didn’t know until this weekend) for verifying the shortest path of length 13 of the example with 8 people and with the restrictions given by 4672616e63657320452e20416c6c656e.
Fortunately the puzzlemaster doesn’t want to know restrictions like “child a isn’t willing to stay with child b” or “the husbands are so jealous, that no woman can be in the presence of another man unless her husband is also present” or so, but he only wants to know the number.
So I’ll vary the 32-digit hexadecimal number randomly, hoping, that I'll find a number leading to a shortest path length of 73.

Last fiddled with by Dieter on 2019-05-08 at 10:36

 2019-05-09, 06:30 #4 LaurV Romulan Interpreter     Jun 2011 Thailand 83×113 Posts We solved the bonus part (which is quite easy) and learned few things on the way by googling her name and her connection with groups of 19 people. For the main task, we don't have much time to try... Real life (TM) is killing us right now... Last fiddled with by LaurV on 2019-05-09 at 06:30
2019-05-09, 06:39   #5
Nick

Dec 2012
The Netherlands

31758 Posts

Quote:
 Originally Posted by LaurV ... Real life (TM) is killing us right now...
Hope it gets better soon!

2019-05-16, 06:47   #6
Dieter

Oct 2017

2·5·11 Posts

Quote:
 Originally Posted by SmartMersenne Any ideas on how to solve this?
Some remarks on the challenge –at the risk of saying only trivial points:
• A combination – f.e. 10110011 – is only legal, if the complement – here 01001100 –is legal, too. Otherwise the format wished by the puzzlemaster wouldn’t work. Furthermore so you can be sure that the conditions are always fulfilled –in the short period between landing and restarting, too.
• For the definition of the nodes of the graph you have to distinguish if the boat is on the left or on the right bank. So every legal combination represents two nodes.
• Breadth first search seems to be appropriate.
• The first digit of the hexadecimal number has to be less than 8. Otherwise 11111111and 00000000 were illegal. I know –that’s really trivial.

My best solution until now has a short path length of 43.

Last fiddled with by Dieter on 2019-05-16 at 06:48

2019-05-16, 22:07   #7
SmartMersenne

Sep 2017

32×11 Posts

Quote:
 Originally Posted by Dieter Some remarks on the challenge –at the risk of saying only trivial points:A combination – f.e. 10110011 – is only legal, if the complement – here 01001100 –is legal, too. Otherwise the format wished by the puzzlemaster wouldn’t work. Furthermore so you can be sure that the conditions are always fulfilled –in the short period between landing and restarting, too. For the definition of the nodes of the graph you have to distinguish if the boat is on the left or on the right bank. So every legal combination represents two nodes. Breadth first search seems to be appropriate. The first digit of the hexadecimal number has to be less than 8. Otherwise 11111111and 00000000 were illegal. I know –that’s really trivial. My best solution until now has a short path length of 43.
There are 2^128 cases, even after simplifications there are at least 2^60 cases to consider. Plus if you add the path search time for each case, isn't it impractical to find the answer in a reasable time using BFS?

2019-05-17, 07:21   #8
Dieter

Oct 2017

1568 Posts

Quote:
 Originally Posted by SmartMersenne There are 2^128 cases, even after simplifications there are at least 2^60 cases to consider. Plus if you add the path search time for each case, isn't it impractical to find the answer in a reasable time using BFS?
You are right, it is impossible to consider all 2^127 (Bit 127 has to be 0) cases.
I use BFS for calculating the shortest path length of a set of restrictions defined by a 32-digit number, because I don't know another procedure.
My current number (lenght 45) contains many "f's" and other digits. I try to improve the number by choosing 6 or 7 digits : two digits = f and four/five digits <> f, and then checking all combinations (2^24 respectively 2^28 combinations). Sometimes I find a better number.
If I use the four threads of my vostro 3560 from 2012 (i5-3210M) I am able to check 2^23 combinations in a little bit more than one hour.
The puzzlemaster hinted the possibility of a prolongation of the challenge to one more month...

2019-05-17, 07:37   #9
SmartMersenne

Sep 2017

32×11 Posts

Quote:
 Originally Posted by Dieter You are right, it is impossible to consider all 2^127 (Bit 127 has to be 0) cases. I use BFS for calculating the shortest path length of a set of restrictions defined by a 32-digit number, because I don't know another procedure. My current number (lenght 45) contains many "f's" and other digits. I try to improve the number by choosing 6 or 7 digits : two digits = f and four/five digits <> f, and then checking all combinations (2^24 respectively 2^28 combinations). Sometimes I find a better number. If I use the four threads of my vostro 3560 from 2012 (i5-3210M) I am able to check 2^23 combinations in a little bit more than one hour. The puzzlemaster hinted the possibility of a prolongation of the challenge to one more month...
If the optimization function has only very little number of local minima then you may be lucky, but if it has a lot, you are like to get stuck in those frequently. So you may end up going up to 60 trips, but that is still no guarantee that you are close to the solution.

2019-05-20, 17:59   #10
AKG

May 2019

22 Posts

Quote:
 Originally Posted by Dieter Some remarks on the challenge –at the risk of saying only trivial points:A combination – f.e. 10110011 – is only legal, if the complement – here 01001100 –is legal, too. Otherwise the format wished by the puzzlemaster wouldn’t work. Furthermore so you can be sure that the conditions are always fulfilled –in the short period between landing and restarting, too. For the definition of the nodes of the graph you have to distinguish if the boat is on the left or on the right bank. So every legal combination represents two nodes. Breadth first search seems to be appropriate. The first digit of the hexadecimal number has to be less than 8. Otherwise 11111111and 00000000 were illegal. I know –that’s really trivial. My best solution until now has a short path length of 43.
The complement is legal only of you add bit for A and in complement it is zero. Add another bit for location of boat, so that is 2 extra bits. Then you can build an array of connected nodes for each node and do a bfs. Have not got solution. I might have to try some sort of random algo on this.

2019-05-21, 08:12   #11
Dieter

Oct 2017

2·5·11 Posts

Quote:
 Originally Posted by AKG The complement is legal only of you add bit for A and in complement it is zero. Add another bit for location of boat, so that is 2 extra bits. Then you can build an array of connected nodes for each node and do a bfs. Have not got solution. I might have to try some sort of random algo on this.
What is your best until now? I have 212 „solutions“ with 51. I guess that they are equivalent — one yields another by renaming the people. But for further searching I‘ll consider them all.

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 17 2019-05-08 23:55 Xyzzy Puzzles 74 2019-04-09 13:34 Xyzzy Puzzles 6 2019-04-04 16:32 Xyzzy Puzzles 17 2019-03-07 21:05

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

Mon Apr 19 16:46:48 UTC 2021 up 11 days, 11:27, 0 users, load averages: 3.81, 3.17, 2.77