No account? Create an account
 Nerdsnipe challenge! - Lindsey Kuper — LiveJournal [entries|archive|friends|userinfo]
Lindsey Kuper

 [ website | composition.al ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

From:
2012-02-05 05:11 pm (UTC)

### Re: Simulation says

Oops! Yeah, Alex just pointed out the flaw in my algorithm: you can back yourself into a corner. You already know this, but for the benefit of anyone else reading, here's a simple case: Suppose there are only 3 players. You deal the question cards first, and they get question cards A, B, and C, respectively. Now it's time to deal the answer cards. You remove answer card A from the deck and randomly deal one of B or C to player 1. Let's say it's B. Now, you put answer card A back in, take out answer card B, and randomly deal one of A or C to player 2. Let's say it's A. Now you're left with answer card C, but player 3 has question card C, so you're backed into a corner. (You can backtrack, but I think that that would mean crossing over into exponential time.)

I think it's cool how everyone is applying their own favorite hammer to this problem. Alex sees it as a constraint satisfaction problem, and from that angle, it's easier for me to see the NP-ness.

Edited at 2012-02-05 05:16 pm (UTC)
From:
2012-02-05 05:17 pm (UTC)

### Re: Simulation says

NP-ness! Tee hee hee...

my sense of humor should be more mature, but sometimes I fail my saving roll against immature homonyms
From:
2012-02-05 05:19 pm (UTC)