Even though I could not participate in this years google code jam qualification round, I want to provide you my solution for magic trick.
I actually failed to implement it correctly on the first try. My idea was that after the volunteer chose the row in the first grid, all the cards of this row needed to be in different rows on the second grid. Which is probably how you’d set up the trick too, if you’d perform it.
The thing is, you can still be lucky by placing only the correct card in the row the volunteer actually picks into it’s own new row. The other three can be either in the same row, or wherever. It doesn’t matter.
Let’s assume we start with this as our first grid
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
If you think of your pattern as a matrix it becomes clear, that by laying down the transponse (read the columns and write them as rows) of your matrix, you can always solve what the volunteer picked.
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
This would be the logical thing to do, but you can also just depend on your good luck and try something like this:
1 2 3 5 4 5 6 7 9 10 11 12 13 14 15 16
If the user actually picked the 4, it is still solveable. But if he picked 1, 2 or 3 you’d have no chance to determin which card it was because you failed to spread them into different rows.
And this was the mistake, I forgot that the magician can be lucky even if he did not lay out the cards as transponse of his first grid.
So here’s my solution (or go to github)
public void solve() {
int cases = in.nextInt();
for (int j = 1; j <= cases; j++) {
out.print("Case #" + j + ": ");
// first card
int rowWithCard = in.nextInt();
in.nextLine();
List row1 = getRow(rowWithCard);
//second card
rowWithCard = in.nextInt();
in.nextLine();
List row2 = getRow(rowWithCard);
if (!isWizardWithoutFailure(row1, row2)) {
out.println("Bad Magician!");
continue;
}
String result = findCard(row1, row2);
if (result == null) {
out.println("Volunteer cheated!");
continue;
} else {
out.println(result);
}
}
}
// get the card from the chosen row, every other row is not interesting
private List getRow(int chosenRow) {
List cardRow = new ArrayList();
for (int row = 1; row <= 4; row++) {
if (chosenRow == row) {
cardRow.addAll(Arrays.asList(in.nextLine().split(" ")));
} else {
in.nextLine();
}
}
return cardRow;
}
// check if the wizard did lay down less than two cards from the previous row picked by the volunteer
private boolean isWizardWithoutFailure(List row1, List row2) {
int matchingCards = 0;
for (String card : row1) {
if (row2.contains(card)) {
matchingCards++;
}
}
if (matchingCards > 1) {
return false;
}
return true;
}
// find the duplicate card, if there is none, volunteer cheated
private String findCard(List row1, List row2) {
for (String card : row1) {
if (row2.contains(card)) {
return card;
}
}
return null;
}
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014