-
Posts
578 -
Joined
-
Last visited
-
Days Won
8
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by EventHorizon
-
-
It's funny, I was thinking it would probably be symmetrical... and it was.
_________________ |1=>=6=< >=6=<=1| | X X X|X|X X X | |>=6 6=< >=6 6=<| ||X|X|X X X|X|X|| |> ^=^ v=v ^=^ <| ||X X X|X|X X X|| |> >=6 6 6 6=< <| ||X|X|X|X|X|X|X|| |> > ^=^ ^=^ < <| ||X|X X X X X|X|| |> >=6=< >=6=< <| ||X X X|X|X X X|| |> v=v < > v=v <| ||X|X|X|X|X|X|X|| |>=6 6=< >=6 6=<| -----------------
1 means 1 pip is showing, 6 means 6 pips are showing. ^ means the 1 is pointing towards the top of the grid, etc. Just follow the = and |. It's sad though. I almost had the solution (if I had assumed it was symmetrical), except for the cactus-like shape in the center. Then I got bored and wrote a backtracking search. Should've tried a while longer. For those interested, here is more code:wasd to move die (press key then enter). (w-up, a-left, s-down, d-right). Space to undo. k to have it find a solution by backtracking.
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <memory.h> #include <vector> using namespace std; #define GRIDSIZE 8 enum dir { dir_front = 0, dir_back = 1, dir_up = 2, dir_down = 3, dir_right = 4, dir_left = 5, num_dirs = 6, dir_error = 7, dir_undo = 8 }; dir facing[GRIDSIZE*GRIDSIZE]; dir move[GRIDSIZE*GRIDSIZE]; vector<int> hist; int displacement[8] = {0,0,-GRIDSIZE,GRIDSIZE,1,-1,0,0}; dir tiltarray[] = {dir_error,dir_error,dir_up,dir_down,dir_right,dir_left, dir_error,dir_error,dir_down,dir_up,dir_left,dir_right, dir_error,dir_error,dir_back,dir_front,dir_up,dir_up, dir_error,dir_error,dir_front,dir_back,dir_down,dir_down, dir_error,dir_error,dir_right,dir_right,dir_back,dir_front, dir_error,dir_error,dir_left,dir_left,dir_front,dir_back, dir_error,dir_error,dir_error,dir_error,dir_error,dir_error, dir_error,dir_error,dir_error,dir_error,dir_error,dir_error}; dir tilt(dir cur, dir tiltdir) { int val = cur*num_dirs+tiltdir; return tiltarray[val]; } void printdir(dir cur) { switch (cur) { case dir_front: cout << "1"; break; case dir_back: cout << "6"; break; case dir_up: cout << "^"; break; case dir_down: cout << "v"; break; case dir_right: cout << ">"; break; case dir_left: cout << "<"; break; default: cout << " "; break; } } void drawgrid() { for(int i = 0; i < GRIDSIZE*2+1; i++) cout << "_"; cout << endl; for(int j = 0; j < GRIDSIZE; j++) { cout << "|"; for(int i = 0; i < GRIDSIZE; i++) { printdir(facing[j*GRIDSIZE+i]); //printdir(move[j*GRIDSIZE+i]); if (i <= GRIDSIZE-2) { if ((move[j*GRIDSIZE+i]==dir_right) || (move[j*GRIDSIZE+i+1]==dir_left)) { cout << "="; } else { cout << " "; } } } cout << "|" << endl; if (j <= GRIDSIZE-2) { cout << "|"; for(int i = 0; i < GRIDSIZE; i++) { if ((move[j*GRIDSIZE+i]==dir_down) || (move[(j+1)*GRIDSIZE+i]==dir_up)) { cout << "|"; } else { cout << " "; } if (i < GRIDSIZE-1) cout << "X"; } cout << "|" << endl; } } for(int i = 0; i < GRIDSIZE*2+1; i++) cout << "-"; cout << endl; } int validmove(dir tiltdir, int verbose) { if (((tiltdir==dir_up)&&(hist.back()<GRIDSIZE)) || ((tiltdir==dir_down)&&(hist.back()>=(GRIDSIZE-1)*GRIDSIZE)) || ((tiltdir==dir_right)&&(hist.back()%GRIDSIZE==GRIDSIZE-1)) || ((tiltdir==dir_left)&&(hist.back()%GRIDSIZE==0))) { if (verbose) cout << "Invalid move: Boundary hit." << endl; return 0; } if (facing[hist.back()+displacement[tiltdir]] != dir_error) { if (verbose) cout << "Invalid move: Repeating a square." << endl; return 0; } if ((tilt(facing[hist.back()],tiltdir)==dir_front) && (hist.back()+displacement[tiltdir] != GRIDSIZE-1)) { if (verbose) cout << "Invalid move: 1 would be facing up." << endl; return 0; } return 1; } int solved() { if ((hist.size()==GRIDSIZE*GRIDSIZE) && (hist.back()==GRIDSIZE-1) && (facing[hist.back()] == dir_front)) return 1; return 0; } int main(int argc, char *argv[]) { hist.push_back(0); for(int i = 0; i < GRIDSIZE*GRIDSIZE; i++) { facing[i] = dir_error; move[i] = dir_error; } facing[0] = dir_front; drawgrid(); while (1) { int ch = getchar(); dir tiltdir = dir_error; switch (ch) { case 'w'://up tiltdir = dir_up; break; case 's'://down tiltdir = dir_down; break; case 'd'://right tiltdir = dir_right; break; case 'a'://left tiltdir = dir_left; break; case ' '://undo tiltdir = dir_undo; break; case 'k'://solve it hist.clear(); hist.push_back(0); for(int i = 0; i < GRIDSIZE*GRIDSIZE; i++) { facing[i] = dir_error; move[i] = dir_error; } facing[0] = dir_front; hist.reserve(GRIDSIZE*GRIDSIZE+1); while(!solved() && hist.size() > 0) { //if (hist.size() > GRIDSIZE*(GRIDSIZE-1)+6) //{ // drawgrid(); // getchar(); //} dir nextone = dir_error; switch(move[hist.back()]) { case dir_error: nextone = dir_up; break; case dir_up: nextone = dir_down; break; case dir_down: nextone = dir_right; break; case dir_right: nextone = dir_left; break; case dir_left: nextone = dir_undo; break; default: cout << "Should never get here!!" << endl; } if (nextone == dir_undo) { if (hist.size() <= 1) break; facing[hist.back()] = dir_error; move[hist.back()] = dir_error; hist.pop_back(); continue; } move[hist.back()] = nextone; if (validmove(nextone,0)) { dir temp = tilt(facing[hist.back()],nextone); hist.push_back(hist.back()+displacement[nextone]); facing[hist.back()] = temp; move[hist.back()] = dir_error; } } if (solved()) cout << "Found solution!" << endl; else cout << "No solution??" << endl; drawgrid(); break; default: break; } if (tiltdir == dir_error) continue; if (tiltdir == dir_undo) { if (hist.size() <= 1) continue; facing[hist.back()] = dir_error; hist.pop_back(); move[hist.back()] = dir_error; drawgrid(); continue; } if (validmove(tiltdir,1)) { move[hist.back()] = tiltdir; dir temp = tilt(facing[hist.back()],tiltdir); hist.push_back(hist.back()+displacement[tiltdir]); facing[hist.back()] = temp; } drawgrid(); } }
- 1
-
1 2 3 4 5 6 7 64 14 13 12 11 10 9 8 63 15 16 17 18 19 20 21 62 28 27 26 25 24 23 22 61 29 30 31 32 33 34 35 60 42 41 40 39 38 37 36 59 43 46 47 50 51 54 55 58 44 45 48 49 52 53 56 57
At position 5 the 1 is on top of the die again breaking that constraint. Unless, that is, if I'm misreading the constraints.
-
Lead...because it hadn't yet been posted as an answer and was feeling left out.
Some other reasons... most aren't that great:
Only one with an L.
Least value if you swap letters for their alphabetical position and add them up.
Only one whose first letter isn't in the last half of the alphabet.
Only one whose position in the list is ironic as it follows the rest.
-
What if our search idepends on the previous responses somehow? If we hear that there are X black cards, can we use that information to modify our strategy?
I assume this is in reponse to my statement about order doesn't matter. I did explain that statement in post #21. The search does depend on the set of previous guesses and responses (just not on the order of them to get to that point) to decide the next sequence of cards to guess. So if we guess all red, and we get a response (which tells us the total red and total black cards)... the search should definitely be different based on the response given (though perhaps not initially in that exact scenario... I'm not sure yet).
-
I can beat bub's 1. Just ask, "wait, how many cards are there to guess for now?" And it would be 2 to the 26th power... assuming the only possible replies were "twenty-six" or "you didn't get all of them." That problem would be like a blind person trying to solve a rubik's cube, and asking "is this it?" and the other person saying "nope." (Was it the movie UHF that had that?)
all true, save for that last bit. had figured this to be the logical starting point
Agreed. I was actually writing a similar post when I noticed Time Out already did the job before my post was ready. I thought about commenting on bonanova's "factorial or exponential" comment in that post... something about needing to confiscate an EH silver star
and at EventHorizon, not a programmer but hope to try to follow your code to hopefully gain some insight into how that works.
I used the binary representation of an integer to hold the binary string guesses, and simply brute force went through each possibility. That's why it is too slow with 26 cards when going through each possible guess's value for each possible target binary string when looking for the best one (though I could speed that up if I get motivated to). I do use MIT's HackMEM method for counting the number of bits (to speed that part up), which is pretty cool. Just figured out how that works. So nothing else all that insightful in the code itself.
-
For those who read my last spoiler anyway...
Then why are words flipped when you read them in the mirror?
-
I debated as to whether I should write the answer yet, but that's what spoiler boxes are for, right?
So if you don't have a good answer to this question... don't read the spoiler!
[spoiler=Don't read this unless you already know what it says ]Things on your right, stay on your right. Things on your left, stay on your left. Things above eye level, stay above eye level. Things below eye level, stay below eye level.
So how, since nothing is flipped, is his/her right hand raised when your left is?
Reference frames!
Since the mirror image appears as if it is looking/facing in the opposite direction that you are, its left is your right.
Horror movies have already used this, but wouldn't it be disturbing if the reflection raised its right hand when you raised yours? Or walked to your left when you walked to your right?
-
An equivalent formulation of the question is to minimize guesses for a binary string when the hamming distance to an unknown string is given in response.
You could imagine a N-dimensional hypercube (yeah, easier said than done), and the strings are its vertices. Since you can rotate the hypercube any way you want, you can see any first guess is equivalent. You are just pointing to a vertex and the other person says how far away you are following the edges.
-
Once guesses have been made, the order to get to that point doesn't matter. But choosing which sequence to guess next is important. So I'm not saying there are 14 specific guesses that will uniquely identify every possible string. In other words, history is a set and not a sequence in this case.
Just me being paranoid about how patently bad I am at explaining myself.
-
event horizon:
no i don't think you're being harsh, think your calling it as you see it. i don't doubt your math, but have you actually put the two first trails
00000000000000000000000000000000
and
00000000000000001111111111111111
into your code to see how much search space each one reduces?
I'm pretty sure the second one slightly more optimal. it gives the extra information of where the 1's are likely to be.
i didn't write a programming approach, so getting as many cut down by a third as i did is i believe fairly good.
First guesses are all equivalent in the amount of information they give.
Just verified it with the code (at least with those two). Both leave 12870 possibilities when the reponse is 8 correct when used with a 16 card deck.
Guessing 000000000 at the first is the same as guessing 000000111111 with the second half of all strings in the search space flipped 0's for 1's. Since after that operation, the search space is the same, there is no real difference between any guess. There is always an operation to make it equivalent to any other.
All guesses by themselves produce the same distribution over the whole search space, it is the combination of them that lets us figure things out. Not only that, but the order of guesses obviously doesn't matter, so an optimality proof would involve this basic distribution and how it overlaps with itself to single out lone possibilities.
Just to point it out, this distribution produced by a guess is the Nth layer of Pascal's triangle, where N is the number of cards in the deck being guessed. (eg, 12870 = 16!/8!8! = 16 choose 8 = middle element of 8th layer of Pascal's triangle)
Also, something is either optimal (ie, the best), or it is not. Something cannot be more optimal than some other optimal thing. It's sorta like saying more best. I had a professor who harped on that, and it has sorta become my pet peeve too. So, instead just say better.
-
The binary representations are done in reverse order, so the least significant bit is on the left. I didn't put in any bounds checking, for the most part, so if you try to break the code or enter something it's not expecting, it will likely crash or hang or something (so ctrl+c it if that happens).
Most commands won't work until you've entered the first guess (either command 4 or 5).
You enter a number of cards on the command line (perhaps I should have made a menu option for it too... oh well), and then it brings you to a menu. You enter a number corresponding to the command you want.
Entering a 0 resets everything.
Entering 1 and then an integer will show what distribution of possible color sequences is produced by that guess (binary representation of that integer) from the remaining possibilities.
Entering 2 and then a binary string of 1's and 0's (autofills with 0's if you don't enter a long enough string) will do the same as command 1, but for the binary representation.
Entering 3 will search through all possible guesses and find the one that has the flattest distribution (the smallest maximum). This guess then minimizes the worst case scenario because there are fewer possibilities (ie locally greedy search, which may not necessarily be globally optimal). This can be quite slow with a lot of cards (but gets faster will less cards or less remaining possibilities). I could speed this up significantly if I use equivalency classes, but that's a lot of extra complexity to find them and use them... so maybe later.
Entering 4 and an integer or 5 and a binary string followed by the desired response will cause it to restrict the pool of possible strings to the ones that result in that response when the given guess is made.
Entering 6 will list all sequences that could still be correct given the guesses and responses made.
Entering 7 will convert a binary string to an integer. This is a remnant from before I made entering binary strings work.
Entering 8 will restrict the possible guesses to the sequences that could still be correct, and it will find the one will the flattest distribution under that restriction.
And that's about it. ctrl+c to quit since I didn't put a quit option in.
If anyone actually tests it out or uses it, let me know what you think and if you want me to add an option or change something.
Edit: Also... I have no idea how it happened, but a b was capitalized (or maybe even more errors introduced) in the line "unsigned int n = (~(a ^ & mask;" in the getCorrect method. I didn't notice any other strange capitalizations introduced, but they may be there.
-
i belive witchofsecrets solution works better for a larger number of cards.
lets take the example of 6 cards, with a solution of 100011.
000000 3 so 3 red, 3 black
000111 4 so 2 of the red guesses are correct.
001011 4 so the bottom half is correct, only need the top half solved
010011 4
100011 correct in 5 guesses.
with 26 i belive it will take 16 guesses tops to get a solution using this method.
also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.
As WitchOfSecrets initially explained, he had separate tests for determining "the number of blacks in the first and second 'quarters' of the deck" and "the third and fourth quarters." So he had tests like 0000111100000000 and 0000000000001111. This initial formulation was what I responded to initially.
looking further at witchofsecrets method, i belive i have derived a method that solves it in 9 guesses 60% of the time, with a 40% chance of requireing 10. to demonstrate this idea further, lets take the case of 32 colors to guess.
the hardest string i can find is... 10010110011010010110100110010110
which can be gotten in 10 guesses.
00000000000000001111111111111111 16
00000000111111110000000011111111 16
00001111000011110000111100001111 16
00110011001100110011001100110011 16
01010101010101010101010101010101 16
10011001100110011001100110011001 16
01011010010110100101101001011010 16
and so on.
in general, the number of trials nessicary is 2*log(2) n.
WitchOfSecrets did mention staggered tests, which is what your approach consists of. This does, in fact, improve upon the worst case of Time Out's solution. It does, however, make things a little hard to see why they are working.
The result of this is how you've handled the tests after the alternating one (ie 0101010101010101010101). Running your trials through my code, I see that the initial trials nearly cut the search space in thirds. The ones after the alternating trial aren't quite as useful. They only cut out about a third in the worst case. So, it seems, any gains you've made in the first half, are given up in the second. It seems to me that you'll end up around Time Out's worst case (perhaps a little better).
Looking strictly at the search space after each guess, the first half of your approach is not optimal. It's not bad, but not optimal. It is, however, easy to replicate.
Like I said previously, removing the 0000000000000000 guess does not buy you anything. It just makes things harder to visualize.
Hopefully you don't think I'm being too harsh here. It's just thought and observations before and after testing the method with my code. And speaking of code... here it is for those who know c++.
& mask; register unsigned int tmp; tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111); return ((tmp + (tmp >> 3)) & 030707070707) % 63; } void printbin(int byte) { for (int i = 0; i < numcards; i++) { if (byte & (1 << i)) printf("1"); else printf("0"); } } vector <int> *pruneit(int guess, int goal, vector <int> *poss) { vector <int> *newposs = new vector<int>; for(int i = 0; i < poss->size(); i++) { if (getCorrect(guess,poss->at(i)) == goal) { newposs->push_back(poss->at(i)); } } delete poss; return newposs; } int getintfrombin() { char buffer[64]; memset(buffer,0,sizeof(char)*64); cin >> buffer; int thenum = 0; for(int i = 0; i < numcards; i++) { if (buffer[i] == '1') { thenum += 1<<i; } } return thenum; } int main(int argc, char *argv[]) { if (argc > 1) { numcards = atoi(argv[1]); } mask = (1<<(numcards)) - 1; vector <int> *poss = new vector <int>; vector<int> guesses; vector<int> responses; int totals[numcards+1]; int command; while (1) { if (guesses.size() > 0) { cout << endl; cout << "Guess/Response List" << endl; for(int i = 0; i < guesses.size(); i++) { printbin(guesses.at(i)); cout << " (" << guesses.at(i) << ") - " << responses.at(i) << endl; } } if (poss->size() > 0) { cout << "Possibilities left == " << poss->size() << endl; } cout << "0 - Reset." << endl; cout << "1 - Check guess." << endl; cout << "2 - Check binary guess." << endl; cout << "3 - Find best guess." << endl; cout << "4 - Enter guess and response." << endl; cout << "5 - Enter binary guess and response." << endl; cout << "6 - List Possibilities." << endl; cout << "7 - Convert bin to int." << endl; cout << "8 - Find best guess in remaining items." << endl; cout << "Enter Command: "; cin >> command; if (command == 0) { responses.clear(); guesses.clear(); poss->clear(); } if ((command == 1) || (command == 2)) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int i; if (command == 1) { cout << "Enter guess: "; cin >> i; } else { cout << "Enter guess in binary: "; i = getintfrombin(); } memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } cout << "guess = "; printbin(i); cout << " (" << i << ")" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } } if (command == 3) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int limit; cout << "Enter limit (0 for no limit): "; cin >> limit; if (limit > (1<<numcards)) limit = (1<<numcards); if (limit==0) limit = (1<<numcards); int best = 1<<numcards; int i; int besti=0; for(i = 0; i < limit; i++) { cout << "\r" << i; memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } int max = totals[0]; for(int j = 1; j < numcards+1; j++) { max = max > totals[j] ? max : totals[j]; } if (max < best) { best = max; cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; cout << "new best!!!" << endl; besti=i; } //else if (max==best) //{ // cout << "\rguess = "; // printbin(i); // cout << " (" << i << ") is equivalent." << endl; //} } i = besti; memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; } if ((command == 4) || (command == 5)) { int guess,goal; if (command == 4) { cout << "Enter guess: "; cin >> guess; } else { cout << "Enter guess in binary: "; guess = getintfrombin(); } cout << "Enter response: "; cin >> goal; guesses.push_back(guess); responses.push_back(goal); if (poss->size() > 0) { poss = pruneit(guess,goal,poss); } else { for(int i = 0; i < 1<<numcards; i++) { if (getCorrect(guess,i) == goal) { poss->push_back(i); } } } } if (command == 6) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } for(int i = 0; i < poss->size(); i++) { printbin(poss->at(i)); cout << " (" << poss->at(i) << ")" << endl; } cout << endl; } if (command == 7) { cout << "Enter binary: "; int thenum = getintfrombin(); cout << "The number is " << thenum << endl; } if (command == 8) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int best = 1<<numcards; int i,k; for(k = 0; k < poss->size(); k++) { i = poss->at(k); cout << "\r" << (poss->size()-k); memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } int max = totals[0]; for(int j = 1; j < numcards+1; j++) { max = max > totals[j] ? max : totals[j]; } if (max < best) { best = max; cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; cout << "new best!!!" << endl; } } } } return 0; }#include <stdio.h> #include <stdlib.h> #include <iostream> #include <memory.h> #include <vector> using namespace std; int numcards=26; unsigned int mask=0; int getCorrect(int a, int b) { //MIT HackMEM method for counting bits unsigned int n = (~(a ^
First off, you can choose a number of cards up to 31 (haven't really tested past 26). I could probably get it working for 32, but... meh. You give the number of cards as a command line argument. If nothing is given, it does 26.
You need to give an initial guess/trial first, this is so that it doesn't need to have a vector of 2^cards length to start off.
And I'll give some use cases once I get back from some volleyball.
this is my first Post in the forum
I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops
I don't find a good answer... but I thing there is something right in this wayWelcome to the Den
-
i belive witchofsecrets solution works better for a larger number of cards.
lets take the example of 6 cards, with a solution of 100011.
000000 3 so 3 red, 3 black
000111 4 so 2 of the red guesses are correct.
001011 4 so the bottom half is correct, only need the top half solved
010011 4
100011 correct in 5 guesses.
with 26 i belive it will take 16 guesses tops to get a solution using this method.
also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.
First, since it is not a power of 2, you get a little more information from the second guess by virtue of the fact that the response cannot evenly divide the colors (this is where this method happens to get the extra guess reduction).
Second, since you chose the string beforehand, you are simply showing a special case and not the worst case scenario. For instance, for the guess of 010011, if the response was 2, it would leave 2 possibilities. This would require 1 more guess for the worst case (in this branch of possibilities).
These are the possibilities before that guess 001110, 001101, 100011, 010011. So the bottom half was not necessarily correct at that point.
Edit:
Looking at equivalence classes, it's easy to see that the first guess will give the same amount of useful information regardless of what is guessed. So stick with 0's, since it gives a simple human-readable answer (ie, x number of this color).
-
[spoiler= ]14... and once I figure out how/why it works, I'll let you know. (cmon computer, tell me the method, not just a bunch of numbers!)
This isn't necessarily the limit, but the result of a greedy search that took 14 guesses to resolve to a single guessed possibility (assuming the response given to a guess was always the one that left the most possibilities). So it might be 15, but probably not 16. Unless a greedy search doesn't produce the best strategy, which is entirely possible, then it might be 12 or 13. So I guess I'm saying 14+/-2.
-
I'm not going to get the minimum, but let's try a starting guess.
First, guess black for all. This tells you the number of black and red cards.
Then guess black for the first half and red for the second half. This lets you determine how many blacks and reds are in the second half of the deck, and consequently how many are in the first half of the deck.
Example: Let's suppose we get (total black) correct the first time. There are that many black cards in the whole deck.
Then we get Y correct. This equals the number of black cards in the first half (call that B1) + the number of red cards in the second half. The number of red cards in the second half must equal 13 - B2, where B2 is the number of black cards in the second half of the deck. So we have Y = B1 + 13 - B2, and (total black) = B1 + B2. This gives us:
(total black) + Y = 2B1 + 13
B1 = [(total black) + Y - 13]/2
Then we can get B2 (and R1 and R2).
That's four questions so far.
Using a similar trick can get us the number of blacks in the first and second "quarters" of the deck. (First 6 and 7 cards). Repeating it again can get us the number of blacks in the third and fourth quarters (Last 6 and 7 cards).
Hmm... all these odd numbers look bad. A 14/12 initial split is probably better. A single question can identify the colors of one pair of cards using this kind of technique, but can't get the colors of three cards, as far as I can tell.
I'm guessing the answer's around 13-15, but I wonder if there's some sneaky combination of staggered tests (test even cards, test first half, test first and third quarters, etc) that somehow gives an answer with certainty.
Lets say there are 4 cards to guess, and there are 2 red and 2 black.
It still ends up with a worst case scenario of #ofcards + 1 guesses, which is the same as the approach given by Time Out. Yes, the average case is improved, but the worst case is unchanged.
Or did I misinterpret your approach?
If this is what you thought of, I thought of it first thing too
-
EventHorizon, I'm not grasping the method. In particular, I can't tell if the "group of three (or more)" is always at least three, or if it resets upon color change. In particular, how would you point the backs for the opening sequence, and what would suits would the observer call?
SHDCSDHCSCHD
The first group of three is HDC. Since H and D are red, that's what the orientation of the first card (S) will say (whichever orientation is designated for red, lets say up).
The guesser will get H (lets say H is up) and D (down) correct. Since C cannot be guessed correctly (wrong color), it's orientation tells the guesser what the color will be for the next three (SDH). Again, it's red (up). So the guesser will incorrectly guess H on C, but that's fine. It tells the guesser to use it as the color instead.
The orientation on S (incorrectly guessed as D, signalling it's orientation is the color indicator) gives the color of black (down) for CSC, while D (down) and H (up) are guessed correctly.
Since all three cards are black in CSC, all three will be guessed correctly (up,down,up). The guesser will just keep using black until one is not a black suit. The very next card is red (H), so it's orientation gives the color for the group of three of D??.
U-UDU-DDU-UDU?-? are the orientations.
?-OOX-XOO-OOOX-? are if they are guessed correctly.
?-HDH-DDH-CSC?-? are the suits guessed.
The hyphen marks the groups (usually three unless the first 3 are correctly guessed).
So the "three or more" quip did confuse things a little bit. It was just there to say that if all three cards in the group of three were the same color, there was no card to give a color for the next group of three. So the guesser would just keep guessing that color until one was missed to give the color for the following three cards.
Hopefully that clears things up. Let me know if you have further questions.
-
The first card tells you the suit color that shows up most in the next three cards, and their respective orientations tell you the suit. If all three are the same color... let it ride until there's a suit of a different color. Once there is a card not predicted correctly, that tells you the color of the suit that shows up most in the next group of three (or more).
Worst case, there is always one missed in the group of three. This will leave a similar ending condition to that of plasmid's 35. Just let the bit of info from the last group tell the color for the 50th card, and it's orientation tell you it's suit.
I'm working on improving the worst case of this one, but it may not prove fruitful.
-
I'm not done thinking about this (nor have I really tested the ideas I posted previously), but this came to me in the shower (I'm convinced a large portion of the world's great epiphanies happen there).
The first two cards are throwaways, and the orientation tells what suit the other person will guess for cards 3-26. The suit will be the one that shows up most often (worst case, they all happen 6 times).
For the orientations of 3-26, they give an extra bit to the information for 27-50. So you can get all of those.
Lastly, the final two cards are simple to get as plasmid pointed out earlier.
In the case of a very large, but finite, deck, this would give at least a quarter of the first half, and all of the second half. So worst case is 50%/4 + 50% = 62.5%.
In the case of a regular deck the total is 0*2 + 24/4 + 24 + 2 = 32 cards guaranteed correct = 61.54%
- 1
-
If your bit of information lets the other person get the right suit, no further information can be gleamed. However, if neither value will get the right answer, you can pass other types of information instead.
So, I haven't gotten a polished answer to give yet, but here's some of the things I've been playing with in regard to this puzzle.
So far, two different solutions for 50% (ignoring endgame) have been given. One, you select two suits and tell which of those two the next card is. Since you can only get cards of those two suits right, that's 50%. The other approach gets every other card right by encoding the suit in two card's orientations. Every other card, 50% again.
Here's a rudimentary combination of the two: Choose two suits and use the bit to choose between those two suits, but with the cards you cannot give the right answer, take every pair of wrong answers to give the suit of cards counting back from the end (so the guy needs to keep track of when the information is put into effect).
But this removes the use of the orientations of the cards at the end. So to improve this, the cards you get wrong tell you (counting backwards from third to last card (last two are easy as previously pointed out)), whether the card will be possible to guess with the two initial suits. If not, you choose from between the other two.
This however, still only guarantees about 50%. You could have all the cards you cannot predict first.
Another option is perhaps that the information you give is to change the two suits you choose between. With two wrong answers gives the chance to change one of the suits, or you can have three answers to set both to something (ie, there are only 6 possible pairs given 4 suits). Perhaps if you get one wrong on purpose that you could have gotten means to change both to the other two suits.
The approach I'm going to test out initially is a combination of the last idea and the combination of the two 50% ideas. Use the first 2,3, or 4 errors to change the suits you choose from, and the rest of the wrong answers to help with identifying suits of the cards counting back from the end (possibly getting one wrong on purpose if it improves things to change what I'm choosing between). I'm thinking I can get something approaching 75%, but don't quote me on that yet.
You could also use the first unpredictable card's orientation to choose between different strategies based on how the deck is shuffled. Or even the first N wrong answers (N chosen beforehand) to give a different set sequence of "predicable-with-initial-suits vs not" that will maximize the score by matching the shuffled deck to the the 2^N options. This approach could even be broken up into groups of X cards, where the wrong answers (however many there are) let you choose the sequence for the next X cards (perhaps not choosing the very best one to allow more information for the next group of cards).
That's all I've got to share as of yet, hopefully more to come. Great puzzle plainglazed!
-
Surely this is a simple misdirection?
The brief turn to hand the coin over is enough, along with the distraction of the introduction of the coin, to glance at the top number on the top die. The totals of the touching numbers on all dice plus the bottom face should be 21 minus the top number, as the opposite faces of a fair die will equal 7. Asking the volunteer to count and add what seem to be random numbers plus the extraneous roll of the dice at the end should be enough to have the audience thinking you've defeated 3 or more random permutations of numbers.
For some reason I was thinking the magician handed the coin with his back turned. If he could glance the top number while he "briefly turn and hand him a coin," that's all that's needed.
-
First, we know that adding the numbers on opposite faces of a regular 6-sided die results in 7. So, the total will end up being 21 minus whatever was on the top of the top die.
I'm assuming you can wait and inspect the dice and the coin after turning around (or if the coin gives the info, you are given the coin before turning around).
If the coin is dirty, a little sticky, made of memory foam, or reacts with the face of the die, then you can inspect the coin to find the number of pips that the top of the top die had.
Or perhaps, the coin leaves a smudge on the face of the die that was on top, and you can use that to identify the face that was on top for the number to subtract.
Perhaps the coin is hot/cold and the dice hold temperature for a long time. Then you could touch each face of the dice until you find the hot/cold one.
Any of these good?
-
Numbers to put on his house to show the street address. So the customer's address is 200 on its street, so he needs to buy two '0''s and a '2'. So three items for $3.
- 1
-
I was rushing out the door when I posted this thread, so here's a quick clarification.
When I say total dates, I meant both mother and child triples included. 'total' should have been replaced with the words 'either mother or child' or 'any type of' in front of 'Pythagorean triple' in both question 2 and 3.
For question 2, I mean per century (ie, ignore wrap around, which would make the answer infinite).
For question 3 and 4, I meant any number of digits for the year, so it never wraps around to 0. For question 4 it makes the answer the last one that will ever happen.
-
Yes, I know Mother's Day is the much bigger deal (Happy Mother's Day to all mothers out there! I hope you feel loved and appreciated every day of the year.).
However, today's date is a Pythagorean triple (5/13/12, 52+122=132), so I thought I'd post some math questions regarding Pythagorean triples.
But first, here are some definitions to those who don't know what Pythagorean triples are:
The Pythagorean theorem states that for a right triangle whose sides are of length a, b, and c where c is the longest length (the one opposite the right angle), a2+b2=c2.
If all three of a,b, and c are positive integers, then {a,b,c} is a Pythagorean triple.
Now, in honor of Mother's Day I'll call a Pythagorean triple a mother triple if there is no d greater than 1 such that {a/d, b/d, c/d} is also a Pythagorean triple (equivalently, at least 2 of {a,b,c} are relatively prime). Otherwise, it is a child triple.
Here are the questions:
1. Let the date be of the form xx/yy/zz (ie, two digit year, any can be c (the longest)). What are the next 3 days that are pythagorean triples?
2. How many dates are mother triples given the two digit year? How many total dates are Pythagorean triples?
3. How many total dates are triples given a four digit year?
4. What was the last date that was a pythagorean triple given a four digit year?
Touring the chessboard with a single die
in New Logic/Math Puzzles
Posted
Yeah, it would be easy. So easy in fact... that here it is