mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-05-01, 12:48   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

3·2,683 Posts
Default May 2019

http://www.research.ibm.com/haifa/po...s/May2019.html
Xyzzy is offline   Reply With Quote
Old 2019-05-08, 05:20   #2
SmartMersenne
 
Sep 2017

32×11 Posts
Default

Any ideas on how to solve this?
SmartMersenne is offline   Reply With Quote
Old 2019-05-08, 10:34   #3
Dieter
 
Oct 2017

2·5·11 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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
Dieter is offline   Reply With Quote
Old 2019-05-09, 06:30   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

83×113 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2019-05-09, 06:39   #5
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

31758 Posts
Default

Quote:
Originally Posted by LaurV View Post
... Real life (TM) is killing us right now...
Hope it gets better soon!
Nick is online now   Reply With Quote
Old 2019-05-16, 06:47   #6
Dieter
 
Oct 2017

2·5·11 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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
Dieter is offline   Reply With Quote
Old 2019-05-16, 22:07   #7
SmartMersenne
 
Sep 2017

32×11 Posts
Default

Quote:
Originally Posted by Dieter View Post
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?
SmartMersenne is offline   Reply With Quote
Old 2019-05-17, 07:21   #8
Dieter
 
Oct 2017

1568 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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...
Dieter is offline   Reply With Quote
Old 2019-05-17, 07:37   #9
SmartMersenne
 
Sep 2017

32×11 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
SmartMersenne is offline   Reply With Quote
Old 2019-05-20, 17:59   #10
AKG
 
May 2019

22 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
AKG is offline   Reply With Quote
Old 2019-05-21, 08:12   #11
Dieter
 
Oct 2017

2·5·11 Posts
Default

Quote:
Originally Posted by AKG View Post
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.
Dieter is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
April 2019 Xyzzy Puzzles 17 2019-05-08 23:55
January 2019 Xyzzy Puzzles 74 2019-04-09 13:34
March 2019 Xyzzy Puzzles 6 2019-04-04 16:32
February 2019 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.