Programming Olympics
Learn Computer Programming Here ... and maybe represent Ireland?
You are not logged in.
#1 2008-11-05 21:42:39
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
TASK: Choc-O-Chess (Part I and II)
Fatty Malone loves chocolate. Your task is to beat him in a game of choc-o-chess and to prevent him from eating too much of his beloved snack food. Here's how the game works:
You start with a rectangle of chocolate of MxN squares. You then break it into two rectangular pieces, any way you like. For example, starting with a 10x11 piece, you could split it in a 3x11 and a 7x11 piece. You then put the bigger piece in a bowl and continue the game with the SMALLER piece. You pass this piece to your opponent and they do the same thing (break it in two, put the larger piece in the bowl and pass back the small piece). If you are given a 1x1 piece, then you can't split it in two, and you lose. The winner gets all the chocolate in the bowl.
Part I
You must write a computer program that will play choc-o-chess using the optimal strategy. You are given the MxN rectangle of chocolate first. You can assume there is always a way to win from the starting position.
Example: (Player 1 starts and is given a 7x3 block of chocolate)
1 gets 7x3
2 gets 3x3
1 gets 1x3
2 gets 1x1
Player 1 wins
Part II
How should the strategy change if the rules of choc-o-chess are changed, so that instead of putting the larger piece into the bowl, you put the smaller piece in the bowl and continue the game with the larger piece?
Write a computer program to play with the new strategy.
Offline
#2 2008-11-12 21:59:58
- Prometheus
- New member
- From: Cyberspace
- Registered: 2008-11-12
- Posts: 8
Re: TASK: Choc-O-Chess (Part I and II)
Can you break the chocolate in half or does the fact that you take the smaller piece and put the bigger piece in the bowl mean that you can't break it in half as you wouldn't have a larger or smaller piece?
Offline
#3 2008-11-13 14:43:56
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
Hi Prometheus,
yes you can break it in half, and put either piece in the bowl (since they are both identical).
Ciarán.
Offline
#4 2008-11-14 18:10:16
- stedolan
- New member
- Registered: 2008-11-14
- Posts: 1
Re: TASK: Choc-O-Chess (Part I and II)
This seems familiar... 
Offline
#6 2008-11-18 18:06:18
- Donncha
- New member
- From: Offaly
- Registered: 2008-11-11
- Posts: 5
Re: TASK: Choc-O-Chess (Part I and II)
Sorry I'm just a bit confused about the challange,
1: Do you always start first before Fatty Malone?
2: Do you program to play for Fatty Malone as well as yourself or is it an interactive program?
3: If you do have to play for Fatty Malone as well do you use the same strategy for your opponent that you use for yourself? (i.e. The best strategy)
Thanks,
Donncha
4/3 of people don't understand fractions
Offline
#7 2008-11-19 13:03:42
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
Thanks for your questions Donncha.
1. Yes, you always go first
2. You write the program to play for you. You can input Fatty Malone's move from the keyboard.
For example, you program should:
- Input the size of the starting bar of chocolate
- print out your first move
- Input Fatty's move
- print out your second move
- etc.
Write your program so that if anyone were to play against it, they would lose.
Offline
#8 2008-11-27 16:37:26
- HappySmileMan
- New member
- From: Wexford
- Registered: 2008-11-21
- Posts: 6
Re: TASK: Choc-O-Chess (Part I and II)
There's only one input box for the answer, so do I wait until i have both parts done and submit them as a very long answer or can I submit my code for part one now.
Offline
#9 2008-12-01 11:14:19
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
You can submit them together or separately. Either way is fine.
Offline
#10 2008-12-11 21:49:08
- sipefree
- Member
- Registered: 2008-12-11
- Posts: 11
Re: TASK: Choc-O-Chess (Part I and II)
When you say "you can assume there is always a way to win from the starting position", does this mean that the input variables will always fall in the set where, if played right, there is a 100% chance of winning?
At a certain size of chocolate bar, there is no guaranteed strategy for winning, only counting on the opponent making a mistake.
If the program must win every time it must fall within certain parameters. Can you confirm this is the style of input that will be given?
Offline
#11 2008-12-12 11:08:11
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
Yes, you are correct : "you can assume there is always a way to win from the starting position" means "if played right, there is a 100% chance of winning?", as you stated.
For certain input sizes, there is no optimal strategy that will ensure victory, and so you can assume that these input sizes will NOT be used.
Offline
#12 2008-12-12 11:49:32
- Prometheus
- New member
- From: Cyberspace
- Registered: 2008-11-12
- Posts: 8
Re: TASK: Choc-O-Chess (Part I and II)
Do you get your program to block them sizes?
Offline
#13 2008-12-12 12:32:00
- Ciaran
- New member
- Registered: 2008-11-10
- Posts: 4
Re: TASK: Choc-O-Chess (Part I and II)
As stated, "you can assume that these input sizes will NOT be used", so no need to account for them.
Offline
#14 2009-01-05 04:02:02
- moa
- New member
- From: Newry
- Registered: 2008-12-25
- Posts: 6
Re: TASK: Choc-O-Chess (Part I and II)
Do we assume that the move user is asked to make is valid - for example he does not try to divide 10x11 into 5x2 etc?
Do we assume that user plays fair by the rules and makes only valid moves?
Answer before midnight MUCH APPRECIATED!
PS. Sorry for syntax its quite late 
Last edited by moa (2009-01-05 04:14:06)
Offline
#15 2009-01-05 12:16:39
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
Yes Moa, you should assume that you need to play by the rules ... no cheating!
Offline
#16 2009-01-05 15:27:37
- moa
- New member
- From: Newry
- Registered: 2008-12-25
- Posts: 6
Re: TASK: Choc-O-Chess (Part I and II)
Could you suggest a way of testing if code works? Im getting more and more confused about starting combinations which do not allow for AI to win.
Offline
#17 2009-01-06 16:05:29
- admin
- Administrator
- Registered: 2008-11-02
- Posts: 56
Re: TASK: Choc-O-Chess (Part I and II)
One way to test your program's AI is to try to beat it, by you playing as "Fatty Malone".
As for starting combinations that could cause your program to lose; I would suggest you start with small cases, and see which sizes of bar mean that I will definitely lose. You can then work to bigger sizes by asking "Can I cut the bar in such a way as to give my opponent a losing size?". If so, then this current size is a "winning size" and if your opponent got that, then they could win.
Offline
#18 2009-01-06 18:49:22
- moa
- New member
- From: Newry
- Registered: 2008-12-25
- Posts: 6
Re: TASK: Choc-O-Chess (Part I and II)
Well, too late for this anyway When can we expect results?
Offline
#19 2009-01-19 17:37:07
- damacatak
- New member
- Registered: 2009-01-15
- Posts: 1
Re: TASK: Choc-O-Chess (Part I and II)
Can someone please send me the answers to the questions!! at
nialler00@gmail.com
Offline