Dear All:
Some people asked to see the description of the banquet puzzles by Dennis Shasha.
Dennis has kindly provided a writeup, which is attached.
Was great to see you all last week.
--
regards, --- michael
Dear Dennis,
Thank you for the entertaining puzzles. In order to show that logic programming can offer entertaining solutions, I wrote programs (in Picat) for solving the card puzzle:
http://picat-lang.org/exs/shasha_cards1.pi http://picat-lang.org/exs/shasha_cards2.pi
Be aware that the second part of the problem, i.e., finding the minimum k, is time consuming. I hope that other LP people can offer better and more entertaining solutions.
Best regards, Neng-Fa
On Mon, Oct 24, 2016 at 10:12 PM, Michael Kifer kifer@cs.stonybrook.edu wrote:
Dear All:
Some people asked to see the description of the banquet puzzles by Dennis Shasha.
Dennis has kindly provided a writeup, which is attached.
Was great to see you all last week.
--
regards, --- michael
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
Dear Neng-Fa, Great. When I publish the puzzle in CACM (over the next year), I'll include links to your solutions on the solution page.
Warm Regards, Dennis
Neng-Fa Zhou neng.zhou@gmail.com wrote:
Dear Dennis,
Thank you for the entertaining puzzles. In order to show that logic programming can offer entertaining solutions, I wrote programs (in Picat) for solving the card puzzle:
http://picat-lang.org/exs/shasha_cards1.pi http://picat-lang.org/exs/shasha_cards2.pi
Be aware that the second part of the problem, i.e., finding the minimum k, is time consuming. I hope that other LP people can offer better and more entertaining solutions.
Best regards, Neng-Fa
On Mon, Oct 24, 2016 at 10:12 PM, Michael Kifer kifer@cs.stonybrook.edu wrote:
Dear All:
Some people asked to see the description of the banquet puzzles by Dennis Shasha.
Dennis has kindly provided a writeup, which is attached.
Was great to see you all last week.
--
regards, --- michael
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
Hi,
I also found the puzzles very entertaining. I took some time to try to compete with Neng-Fa's programs.
Here is an IDP version of the shasha_cards_1: http://dtai.cs.kuleuven.be/krr/idp-ide/?src=1f49baf8fb785706cff6d63d8f98ab62
For shasha_cards_2 I took a different approach and modelled a problem which is harder for me to win (and easier to model). I take the answer for that as an upperbound. And subsequently I prove that this answer is optimal.
Instead of: for each opponent order: can we find an insertion of our cards I modelled: can we find an insertion of our cards, so that no matter what the numbers on our opponents card will be, that we will still win. win(x) <- on(x) >= k and (forall y: k =< y =< 8 => win(x+y)). meaning that in the model, if we find a card larger than K, we will only consider it winning, if all numbers between k and 8 lead to a win: http://dtai.cs.kuleuven.be/krr/idp-ide/?src=ca9fb22da79dd2c0b6ef62b8ff63a5ff
This problem is easily solved by our system in a very short time. Minimizing k leads to an upper bound of k=3. But of course it could be possible that our winning strategy depends on the order of our opponents cards, so we still want to prove that k = 2 is impossible
So we're left with finding an ordering of 28 cards (2-8), so that each insertion of 1's still leads to a loss. For this I wrote a Haskell program to see check a particular candidate. In this program I check whether [3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8] can be extended to a win using only four 1's. Which it can't. https://goo.gl/YrUzE3
So through the combination of the IDP and the Haskell Program we can conclude that k = 3. And both can be run in a matter of seconds. (The 3 code snippets are runnable online)
Ingmar
On Sat, Oct 29, 2016 at 9:29 AM Dennis Shasha shasha@cims.nyu.edu wrote:
Dear Neng-Fa, Great. When I publish the puzzle in CACM (over the next year), I'll include links to your solutions on the solution page.
Warm Regards, Dennis
Neng-Fa Zhou neng.zhou@gmail.com wrote:
Dear Dennis,
Thank you for the entertaining puzzles. In order to show that logic programming can offer entertaining solutions, I wrote programs (in Picat) for solving the card puzzle:
http://picat-lang.org/exs/shasha_cards1.pi http://picat-lang.org/exs/shasha_cards2.pi
Be aware that the second part of the problem, i.e., finding the minimum
k,
is time consuming. I hope that other LP people can offer better and more entertaining solutions.
Best regards, Neng-Fa
On Mon, Oct 24, 2016 at 10:12 PM, Michael Kifer <kifer@cs.stonybrook.edu
wrote:
Dear All:
Some people asked to see the description of the banquet puzzles by
Dennis
Shasha.
Dennis has kindly provided a writeup, which is attached.
Was great to see you all last week.
--
regards, --- michael
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
Wonderful. Just a few questions below.
Ingmar Dasseville ingmar.dasseville@cs.kuleuven.be wrote:
Hi,
I also found the puzzles very entertaining. I took some time to try to compete with Neng-Fa's programs.
Here is an IDP version of the shasha_cards_1: http://dtai.cs.kuleuven.be/krr/idp-ide/?src=1f49baf8fb785706cff6d63d8f98ab62
For shasha_cards_2 I took a different approach and modelled a problem which is harder for me to win (and easier to model). I take the answer for that as an upperbound. And subsequently I prove that this answer is optimal.
Instead of: for each opponent order: can we find an insertion of our cards I modelled: can we find an insertion of our cards, so that no matter what the numbers on our opponents card will be, that we will still win. win(x) <- on(x) >= k and (forall y: k =< y =< 8 => win(x+y)). meaning that in the model, if we find a card larger than K, we will only consider it winning, if all numbers between k and 8 lead to a win: http://dtai.cs.kuleuven.be/krr/idp-ide/?src=ca9fb22da79dd2c0b6ef62b8ff63a5ff
... I like this version of the problem.
... Warmly, Dennis
This problem is easily solved by our system in a very short time. Minimizing k leads to an upper bound of k=3. But of course it could be possible that our winning strategy depends on the order of our opponents cards, so we still want to prove that k = 2 is impossible
So we're left with finding an ordering of 28 cards (2-8), so that each insertion of 1's still leads to a loss. For this I wrote a Haskell program to see check a particular candidate. In this program I check whether [3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8] can be extended to a win using only four 1's. Which it can't. https://goo.gl/YrUzE3
So through the combination of the IDP and the Haskell Program we can conclude that k = 3. And both can be run in a matter of seconds. (The 3 code snippets are runnable online)
Ingmar
On Sat, Oct 29, 2016 at 9:29 AM Dennis Shasha shasha@cims.nyu.edu wrote:
Dear Neng-Fa, Great. When I publish the puzzle in CACM (over the next year), I'll include links to your solutions on the solution page.
Warm Regards, Dennis
Neng-Fa Zhou neng.zhou@gmail.com wrote:
Dear Dennis,
Thank you for the entertaining puzzles. In order to show that logic programming can offer entertaining solutions, I wrote programs (in Picat) for solving the card puzzle:
http://picat-lang.org/exs/shasha_cards1.pi http://picat-lang.org/exs/shasha_cards2.pi
Be aware that the second part of the problem, i.e., finding the minimum
k,
is time consuming. I hope that other LP people can offer better and more entertaining solutions.
Best regards, Neng-Fa
On Mon, Oct 24, 2016 at 10:12 PM, Michael Kifer <kifer@cs.stonybrook.edu
wrote:
Dear All:
Some people asked to see the description of the banquet puzzles by
Dennis
Shasha.
Dennis has kindly provided a writeup, which is attached.
Was great to see you all last week.
--
regards, --- michael
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
iclp16-attendants mailing list iclp16-attendants@software.imdea.org https://software.imdea.org/mailman/listinfo/iclp16-attendants
iclp16-attendants@software.imdea.org
-
Dennis Shasha -
Ingmar Dasseville -
Michael Kifer -
Neng-Fa Zhou