Weekender #3
It's a simple one this week. Simple but fun. I am sure a few readers would appreciate the "user interface" ;)
The puzzle is at:
http://freeweb.siol.net/danej/riverIQGame.swf
Object:
Get everyone across the river.
How to Start:
Click on link above, and then click on the big blue circle.
Everybody has to cross the river.
How to play:
To move the people click on them.
To move the raft click on the pole on the opposite side of the river.
The following rules apply:
Only 2 persons on the raft at a time
The father can not stay with any of the daughters, without their mother's presence.
The mother can not stay with any of the sons, without their father's presence.
The thief (striped shirt) can not stay with any family member, if The Policeman is not there.
Only the Father, the Mother and the Policeman know how to operate the raft.
Before you think of some smart comments on the rules, remember that this seems to be a Japanese mind teaser. I did not make up the rules.
Let me know how many river crossings you needed for this.
For people looking for more challenge,
Can you arrange 1 2 3...9 with - and + (as many or as few) in between them to make 100.
This is an old one but do you know how many ways are there to achieve this?
valid ways
12 - 3 + 45 - 67..... etc
invalid ways
123-54+... (digits out of sequence).
Here's one more picture. This one is from our last year's trip to Niagara.
The puzzle is at:
http://freeweb.siol.net/danej/riverIQGame.swf
Object:
Get everyone across the river.
How to Start:
Click on link above, and then click on the big blue circle.
Everybody has to cross the river.
How to play:
To move the people click on them.
To move the raft click on the pole on the opposite side of the river.
The following rules apply:
Only 2 persons on the raft at a time
The father can not stay with any of the daughters, without their mother's presence.
The mother can not stay with any of the sons, without their father's presence.
The thief (striped shirt) can not stay with any family member, if The Policeman is not there.
Only the Father, the Mother and the Policeman know how to operate the raft.
Before you think of some smart comments on the rules, remember that this seems to be a Japanese mind teaser. I did not make up the rules.
Let me know how many river crossings you needed for this.
For people looking for more challenge,
Can you arrange 1 2 3...9 with - and + (as many or as few) in between them to make 100.
This is an old one but do you know how many ways are there to achieve this?
valid ways
12 - 3 + 45 - 67..... etc
invalid ways
123-54+... (digits out of sequence).
Here's one more picture. This one is from our last year's trip to Niagara.
posted by Nikhil at 9:45 AM
13 Comments:
A) 17 trips:
P+T, P
P+B1, P+T
M+B2, M
W+M, W
P+T, M
W+M, W
W+G1, P+T
P+G2, P
P+T
B) 11 ways:
123 + 45 - 67 + 8 - 9
123 + 4 - 5 + 67 - 89
123 - 45 - 67 + 89
123 - 4 - 5 - 6 - 7 + 8 - 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
1 + 23 - 4 + 56 + 7 + 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
Pretty impressive with the B there. Frankly, I did not think that anyone could find all 11. How much time did it take you to find all combinations?
I found one by hand in less than a minute...And then it took me less than 10 mins to write a small program that generated all the combinations :-)
Btw, is 17 trips the best possible for (A)?
I have not been able to do it in less than 17 and I don't think it can be. There is only one logical move at every point ( Consider Husband/Wife interchangeable and change son/daughter accordingly)...
So can you put up your program so that I can generate some other cool combos.
Thanks.
C-code: formatting seems to get screwed up after posting...so it might be a bit difficult to read.
typedef enum {
nothing,
plus,
minus
} operation;
void PrintOps(operation* opArray)
{
int i;
for (i = 0; i < 8; i++) {
printf("%1d", i + 1);
if (opArray[i] == plus)
printf(" + ");
else if (opArray[i] == minus)
printf(" - ");
}
printf("9\n");
}
void compute(operation* opArray, int index)
{
if (index == 8) {
int i;
long sum = 0;
unsigned long currNum = 1;
operation lastOp = nothing;
for (i=0; i<8; i++) {
if (opArray[i] == nothing) {
currNum = currNum*10 + (i+2);
}
else if (opArray[i] == plus) {
if (lastOp == plus)
sum += currNum;
else if (lastOp == minus)
sum -= currNum;
else
sum = currNum;
currNum = i + 2;
lastOp = plus;
}
else {
if (lastOp == plus)
sum += currNum;
else if (lastOp == minus)
sum -= currNum;
else
sum = currNum;
currNum = i + 2;
lastOp = minus;
}
}
if (lastOp == plus)
sum += currNum;
else if (lastOp == minus)
sum -= currNum;
if (sum == 100)
PrintOps(opArray);
return;
}
//
// loop through all three possible values
// and recursively call for next index
//
opArray[index] = nothing;
compute(opArray, index+1);
opArray[index] = plus;
compute(opArray, index+1);
opArray[index] = minus;
compute(opArray, index+1);
}
int main(int argc, char** argv)
{
int i;
operation opArray[8];
compute(opArray, 0);
}
Writing a program to do this is one thing. Writing a program in less than 10 minutes takes a genius. That is pretty darn good.
I probably could not even type it within 10 minutes, forget about thinking, typing and compiling w/o error in that time. Pretty good. I will try to run this sometime.
I went through the code. I think you missed one case here. You will never start with "-1". I hate to nitpick here but old habits die hard :)
Now that we have the brute force method out of the way, are you up for generalizing or optimizing it (two different programs). We can do that whenever we have time. I will try to start tonight.
About optimizing this case, one thing that I thought was we cannot use any digit combinations more than 3 digits long.
Proof?? I don't have one but here is one crude attempt.
Say we have a usable four digit number.
If this number is >= 1099, we need another four digit number to get back to 100.
Since we have digits in sequence, the difference between two four digit numbers is >4000 and we will be left with only a single digit and it will not be possible to get back to 100.
So the number is less than 1099.
The only number possible is 1234.
We cannot use another four digit number to get back to 100 by previous reasoning.
Try 3 digit number: +/- (1234 - 999) = 235 is greater that (100 + 99) or (100 + 9 + 9)
(999 is greatest 3 digit number and 99 is greatest 2 digit number that is remaining.)
Try a 2 digit number: +/-(1234 - 99) = +/- 1135 is greater than (100 + 999) or (100 + 99 + 9).
So we cannnot reach 100 if we use any 4 digit number.
We can check times for the brute force and the final optimized one. That would be fun. Lets leave PrintOps out of the time calculation.
And you don't nitpick that I said "in between", you should have gone that extra mile :)
The -1 case can be avoided if you check the sum to be 100 or -100. (I did think of this case, but gave it up because I really thought that it was not allowed.)
As for writing and compiling without error, this was a pretty short program. I knew that I will use recursion, and I decided not to optimize etc, since the number of possibilities is not that huge. And once I thought of the three possibilities for each operation (instead of just +,-), that made the program a lot simpler.
As for code readability and UI etc, I didn't work on it much...I hope nemo won't have any complaints ;-)
An interesting question: since 4 digit numbers cannot be allowed, what is the number of distinct sequences that the program checks? (Forget -1 for now.)
If we didn't have the 4-digit restriction, and looked at the original program, the number of sequences is 3^8 = 6561.
Is there a elegant way to determine the number of sequences in the restricted case?
[I have not checked this but kept writing whatever I was thinking. You can check now and I will do the same before the match tonight.]
There are 8 "positions" for the operations. .
We cannot have three or consecutive "Nothing" operations.
Adjacent position to these cluster of digits cannot be a "nothing" otherwise duplication.
If we have 3 nothing operations, we have 5 "positions" left.
for Four digits, there are 6 combinations. 2 of them have 1 adjancent "position" and the rest have 2.
So for four digits we have (2 * 2^4) + (4 * 2^3)
To generalize,
for n "nothing" operations we have (8 - n) positions left. [n <=8 ]
For this case, (n+1) digits together, there are (9 - n) ways to get the cluster.
If ((9-n) > 1 )
we have 2 ways that have 1 adjacent position.
The rest of the ways, if any, have two adjacent positions.
So the total number of ways is
(2 * 2^(8 -n -1) ) + ((9-n-2) * 2^(8-n-2))
for 1 < n < 7
If((9-n) = 1)
There is only one operation.
So the total number of operations is
3^8 - ( (sigma:n=1to7((2 * 2^(8 -n -1) ) + ((9-n-2) * 2^(8-n-2))) + 1)
3 or more, Yoda meant.
Post a Comment
<< Home