May 2019

[Xyzzy]

http://www.research.ibm.com/haifa/po...s/May2019.html

[SmartMersenne]

Any ideas on how to solve this?

[Dieter]

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.

[LaurV]

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...

[Nick]

Originally Posted by LaurV

... Real life ^(TM) is killing us right now...

Hope it gets better soon!

[Dieter]

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.

[SmartMersenne]

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?

[Dieter]

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...

[SmartMersenne]

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.

[AKG]

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.

[Dieter]

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.