## Re: Friday Puzzler!

1

Oh good, I think this is the first time I've seen a puzzle before someone has solved it comment.

Just to be pedantic, Bogo-sort is an algorithm, just not an efficient one.

You could say "flip the cup in the North corner" every time and, given enough time, the probability of having a solution would approach 1.

I'll try to come up with an efficient solution now.

Posted by: NickS | Link to this comment | 07- 3-08 5:16 PM
2

Oooh! We could have a *steal the prize* clause, where if you can come up with a more efficient algorithm, you can steal the honor.

For the record, it can definitely be achieved in a finite number of steps, although I don't remember what n is.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 5:23 PM
3

I've never played that game with a spinning table. Mostly, you just get all your teammates in a line with the alcoholics near the front. Then you drink and flip your cups and everyone shouts and cheers. I mean, if you want to practice flipping cups when you're sober, it is a useful skill to have anyway. But I've never known the compass directions to matter.

Besides, if you lose, your whole team drinks. So, no penalty. I'm not really understanding this puzzler of yours.

Posted by: Megan | Link to this comment | 07- 3-08 5:24 PM
4

You know what would be awesome? If, some future Friday, I made up some bullshit puzzler like:

You have three people and you have to guess the number I'm thinking of, between one and two million, using only matchsticks and a can of beans.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 5:26 PM
5

I'm muddling around with "well, okay, these start scenarios are equivalent to each other, and for this one you can get it cleared out of the way like so..." thinking.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:26 PM
6

You could say "flip the cup in the North corner" every time and, given enough time, the probability of having a solution would approach 1.

I assume the goal is to have a definite upper limit on the number of steps involved.

Posted by: snarkout | Link to this comment | 07- 3-08 5:27 PM
7

Yes.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 5:28 PM
8

While I'm working on it, my current belief is that there is no solution that is guaranteed to be finite. I haven't thought of an algorithm that can't have loops in it.

I'm probably missing something, or there is always the possibility (however small) that the game will go on forever.

Posted by: NickS | Link to this comment | 07- 3-08 5:30 PM
9

For the record, it can definitely be achieved in a finite number of steps, although I don't remember what n is.

Posted by: NickS | Link to this comment | 07- 3-08 5:31 PM
10

Hey, who am I to knock someone's faith? But 8 is not my belief.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 5:31 PM
11

While I'm working on it, my current belief is that there is no solution that is guaranteed to be finite. I haven't thought of an algorithm that can't have loops in it.

I'm wondering if the fact that four is composite is the key here, because I agree with you for the case of a two-position table. I'm working it out now for three.

Posted by: snarkout | Link to this comment | 07- 3-08 5:36 PM
12

I assume the goal is to have a definite upper limit on the number of steps involved.

NickS's solution is O(heebie's patience).

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 5:38 PM
13

Okay, here's the strategy I would pursue, but I didn't check my work at all, so I may well have failed to work this out correctly:

First, if we aren't guaranteed that the start condition is not all face down, flip all.

Then:
1. Flip all
2. Flip any two opposite corners (say, E and W)
3. Flip all
4. Flip any two adjacent corners (say, N and E)

Repeat from 1 until satisfied.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:38 PM
14

I must be wrong though, or other people would have gotten it!

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:39 PM
15

You have three people and you have to guess the number I'm thinking of, between one and two million, using only matchsticks and a can of beans

Tell me the number or I set you on fire, lady.

Posted by: jms | Link to this comment | 07- 3-08 5:40 PM
16

O(cn), n being the number of beers you give Heebie.

Posted by: snarkout | Link to this comment | 07- 3-08 5:40 PM
17

Oh drat, mine isn't guaranteed to be finite either.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:44 PM
18

1. Flip all
2. Flip any two opposite corners (say, E and W)
3. Flip all
4. Flip any two adjacent corners (say, N and E)

I don't think this works.

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 5:45 PM
19

13 has an obvious loop if the table never spins

(let + be face up and - face down)

If you start

---+

+++-
-+--
+-++
-+++
+---
(1 more loop gets to ---+ and you start over).

Posted by: NickS | Link to this comment | 07- 3-08 5:46 PM
20

I have an appointment that I have to go to soon, so I'll see whether someone's solved it when I get back.

Posted by: NickS | Link to this comment | 07- 3-08 5:48 PM
21

I don't think this works.

No, you're quite right, it doesn't. I'm no genius this evening. Also, I figured it would be more fun to be wrong in public than to say nothing while I checked my work in private.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:49 PM
22

Flip all
Flip all
Flip opposite corners
Flip all
Flip one
Flip all
Flip opposite corners
Flip all

Posted by: xyzzy | Link to this comment | 07- 3-08 5:50 PM
23

Oh, dang, put another flip all in there after flip one.

Posted by: xyzzy | Link to this comment | 07- 3-08 5:51 PM
24

I'm thinking maybe if you add a "flip three / flip all" or "flip one / flip all" in there...

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:52 PM
25

Right! Like xyzzy is saying. I haven't been able to make a loop with that.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:53 PM
26

Don't forget to start with an extra "flip all" at the beginning, in case it started in the desired configuration.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:55 PM
27

Oh, dang it again, that doesn't work anyway.

Posted by: xyzzy | Link to this comment | 07- 3-08 5:55 PM
28

The following flipping sequence will always work
1. NSEW
2. NW
2. NSEW
3. NS
4. NSEW
5. N
6. NW
7. NSEW
8. NS
9. NSEW

hint: start by assuming some number of cups in the wrong condition - 1,2,3 or 4

after step 1, there are still 2 cups wrong
after step 2, there are 0, 2 or 4 still wrong
after step 3, there are 0 or 2 wrong
after step 4, there are 0 or 4 wrong
after step 5, we're done.

Posted by: Variaga | Link to this comment | 07- 3-08 5:56 PM
29

Oh, dang it again, that doesn't work anyway.

It doesn't?

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:58 PM
30

Whoops, left out step 5.5 NSEW

Posted by: V | Link to this comment | 07- 3-08 5:58 PM
31

Oh my god, trying to read these solutions is making me dizzy. Hang on.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 5:58 PM
32

Repaired 28 is the same as repaired 22.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 5:59 PM
33

32

True enough - we're cross posting. 22/23 are faster than I am

Posted by: Variaga | Link to this comment | 07- 3-08 6:01 PM
34

Problem being that it doesn't always work if you start out with

xo
ox

Ignoring the flip alls as noise, the adjacent flip can result in

ox
ox

then the next diagonal flip

xo
ox

which is no good. That algorithm isn't guaranteed to resolve the 2 case for both adjacent and diagonal starts.

Posted by: xyzzy | Link to this comment | 07- 3-08 6:03 PM
35

which is no good. That algorithm isn't guaranteed to resolve the 2 case for both adjacent and diagonal starts.

The flip-one will jar it out of being a two case, though, right?

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 6:05 PM
36

Okay - I'm sure I'm making errors, too, but I believe there is no correct solution yet.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 6:05 PM
37

Okay I think this may work.

Flip all
Flip opposite corners
Flip all
Flip all
Flip opposite corners
Flip all
Flip one
Flip all
Flip opposite corners
Flip all
Flip all
Flip opposite corners
Flip all

Posted by: xyzzy | Link to this comment | 07- 3-08 6:06 PM
38

34 is wrong

A diagonal flip starting from

OX
OX

results in either
XX
OO

or
OO
XX

not
XO
OX

Posted by: Variaga | Link to this comment | 07- 3-08 6:07 PM
39

then the next diagonal flip

Wait, nuh-uh, that would be with two adjacent flips in a row.

ox
ox

and a diagonal flip would give you

oo
xx

or

xx
oo

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 6:07 PM
40

Hi, I should stop cross-posting now.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 6:08 PM
41

1. Smack it up.
2. Flip it.
3. Rub it down.
4. Move to the Jacuzzi.
5. Oooh that booty.

Posted by: Robert Halford | Link to this comment | 07- 3-08 6:08 PM
42

Yes, I'm pretty sure about that on a second glance. This portion:

Flip opposite corners
Flip all
Flip all
Flip opposite corners
Flip all

should correctly resolve all 2/2 cases.

Starting w/

xo
ox

You win on the first pair.

On

xx
oo

The first flip pair switches it to

xo
xo

Second pair either resolves it or switches it to

xo
ox

And third resolves.

The opening flip all covers the 4/0 case and the flip one in the middle should convert any 3/1 to a 2/2 that will be correctly resolved by repeating the other sequence.

Posted by: xyzzy | Link to this comment | 07- 3-08 6:10 PM
43

37 IS THE BIG WINNER!!

xyzzy, relish in your hard-earned smug satisfaction!

Posted by: heebie-geebie | Link to this comment | 07- 3-08 6:11 PM
44

Repaired 28 is the same as repaired 22.

22 isn't an algorithm. "Flip opposite corners" isn't a step, unless it means flip NSEW (ie, all opposite corners). 28 has you flip one set of specific opposite corners, then flip all, then flip the other set, then flip all—you can't get that from 22.

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 6:11 PM
45

37 suffers from the same problem as 22. What do I do when I get to the step that says "flip opposite corners"?

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 6:12 PM
46

Hooray!

Interpret "flip opposite corners" as flip any arbitrary pair of corners opposite one another. The spinning makes the labels irrelevant.

Posted by: xyzzy | Link to this comment | 07- 3-08 6:13 PM
47

Ohhh, no wonder I was tempted to keep cycling between opposite and adjacent at first. I forgot there was actually a reason for that. Foolish me! Good puzzling, people who are not me.

Posted by: redfoxtailshrub | Link to this comment | 07- 3-08 6:14 PM
48

Although 41 wins the contest to first answer the question, "Which verse begins The time was 6 o'clock on the swatch watch. No time to chill! Got a date! Can't be late! Hey, the girl is gonna do me..."

You can't forget the J, the I, the M, the M, the Y. I need a body bag.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 6:14 PM
49

4. NW -> (1,2diagonal,3,4)
5. NSEW -> (1,2diagonal,3)
6. NS -> (1,3,4)
7. NSEW -> (1,3)
12. NW -> (2diagonal, 4)
13. NSEW -> (2diagonal)
14. NS -> (4)
15. NSEW

Posted by: Variaga | Link to this comment | 07- 3-08 6:21 PM
50

48 -- YEAH! I knew I could win at something, as long as it did involve logic. U-S-A! U-S-A! U-S-A!

Posted by: Robert Halford | Link to this comment | 07- 3-08 6:27 PM
51

Don't these all need a do nothing step at the beginning in case the tester is sneaky enough to start with them all down?

Posted by: F | Link to this comment | 07- 3-08 6:32 PM
52

The lame joke in 50 could have been funnier if I'd remembered to include a key "not." To be clear: I suck at both logic and editing, but I like booty.

Posted by: Robert Halford | Link to this comment | 07- 3-08 6:38 PM
53

1. NSEW
2. Replace E with a google image search for "ben w-lfs-n"
3. NSFW.

QED.

Posted by: Wrongshore | Link to this comment | 07- 3-08 6:39 PM
54

53: Ever since you first called our attention to this fact, WS, I have been very concerned about our Benjamin's blind-dating prospects.

Posted by: A White Bear | Link to this comment | 07- 3-08 6:41 PM
55

What are you talking about? Attractive, intelligent oven-ready turkeys can't get enough of him.

Posted by: Wrongshore | Link to this comment | 07- 3-08 6:44 PM
56

Did the powers that be not activate heebiegeebie@unfogged.com or heebie-geebie@unfogged.com when they made h-g a front pager? Can someone, heebie or othereise, e-mail me heebie's e-mail? I have a clarifying question about the puzzle but don't want to look at this thread.

Posted by: washerdreyer | Link to this comment | 07- 3-08 7:48 PM
57

I e-mailed you. The @unfogged ones haven't been created yet.

In case anyone else wants to send me super puzzlers or has questions, I'll leave my e-mail address on my name for this comment.

Posted by: heebie-geebie | Link to this comment | 07- 3-08 8:23 PM
58

The @unfogged ones haven't been created yet.

You have the technology. Don't let Ben tell you otherwise. Go for it. Also… mouseover text, abouts, and the blogroll. ANARCHY!1!l!

Posted by: md 20/400 | Link to this comment | 07- 3-08 8:40 PM
59

The puzzle in mathy terms is that you've got a random unknown 4 bit binary number (representing the initial start position of each cup, up or down), and you want to find another 4 bit number (representing which ones to flip) such that they xor to 0000 (representing the state of all cups being down). So you have to test every number from 0001 to 1111, the only complication being that the state is saved after each operation. So call the original state A1, the second A2, etc., and you'd want to test

A1 xor 0001
A1 xor 0010 (equivalent to A1 xor 0001 xor 1100, or A2 xor 1100)

etc.

Solution guaranteed in 2^4 = 16 operations, no table rotating needed.

Posted by: bbass | Link to this comment | 07- 3-08 10:23 PM
60

Oh, damn, I just realized the table rotating wasn't user-controlled. Ignore that answer then.

Posted by: bbass | Link to this comment | 07- 3-08 10:24 PM
61

53: Ever since you first called our attention to this fact, WS, I have been very concerned about our Benjamin's blind-dating prospects.

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 11:19 PM
62

Also, I just did a GIS for my name and wtf? I wonder when that was taken.

Posted by: ben w-lfs-n | Link to this comment | 07- 3-08 11:19 PM
63

Jeez, you look about 16 in that.

Posted by: A White Bear | Link to this comment | 07- 3-08 11:31 PM
64

62: ben, it seems those folks are looking for you, too:

Ben w-lfs-n
N/A
???

You should contact them. Perhaps the mothership is returning soon.

Posted by: Stanley | Link to this comment | 07- 4-08 12:45 AM
65

No way, man. Ever since dag right-square-bracket-gren snubbed me when I went to Finland, I'm through with that crowd.

I do wonder what's up with plorkwort, though.

Posted by: ben w-lfs-n | Link to this comment | 07- 4-08 12:52 AM
66

And CRGRE!!!

Posted by: ben w-lfs-n | Link to this comment | 07- 4-08 12:52 AM
67

yesterday i read the post and like felt physically how all the receptors're running out of mediators
always happens when i read something and can't concentrate, for example you guys always refer to MY and i tried to read his blog, a very rare state of mediators, i'll try again maybe when i'll get interested in politics
in the morning it's better and i actually read it and my algorithm would be just start from any corner, turn 90 degrees, flip the cup - repeat it 3 times each until all are flept
then i don't see why it's a puzzle
it's an impossible to carry out plan if the table just spins and stops at wherever degrees of angulation
but if it spins and stops at the corner exactly then it could stop however many times at the already flept cup corner, so chaos and when all the cups will be done depends on gods only and how much push you'll apply to the table
now when i got what the puzzle's about i'm waiting for the correct answer like pretty impatiently

Posted by: read | Link to this comment | 07- 4-08 7:35 AM
68

The way I see it, there are 16 possible starting conditions, and each condition has 4 rotations, so one might think at any time there could be one of 64 results.

But some rotations don't result in unique positions and there are actually only 16 possible results. The 0000 result would end the game so I think the following positions are possible:

1111, 0001, 0010, 0100, 1000, 1110, 1101, 1011, 0111, 1010, 0101, 1100, 0110, 0011, and 1001.

My algorithm would be to use these 15 templates for the flips in sequence repeatedly until one works. My solution requires that the table rotations are random so, for example, it won't simply rotate 4 or a multiple of 4 every single time. My algorithm does not guarantee a win but it does make a win very very likely over time.

Posted by: Tripp the crazed! | Link to this comment | 07- 4-08 7:42 AM
69

Comment 41 was sponsored by Ronnie DeVoe Real Estate Inc.

2. You issue a command, of the form: "Flip the cups in the ____ positions",
and you can specify exactly which corners you want, as many as you want.

Can I have 5! flips or does as many as you want max out at 4 ?

Posted by: Econolicious | Link to this comment | 07- 4-08 10:38 AM
70

You can have 5!!!! flips! But I won't tell you if you've succeeded or not until I've finished carrying out your tall order.

Posted by: heebie-geebie | Link to this comment | 07- 4-08 10:41 AM
71

I'd like to order a tall drink of water, please.

Posted by: peter | Link to this comment | 07- 4-08 10:44 AM
72

Coming right up! Do you have a sufficiently tall straw?

Posted by: heebie-geebie | Link to this comment | 07- 4-08 10:52 AM
73

You can have 5!!!! flips!

If that's ((((5!)!)!)!) flips, that would be a lot of flips.

Posted by: NickS | Link to this comment | 07- 4-08 11:19 AM
74

No, it's 5(!(!(!!))).

Posted by: ben w-lfs-n | Link to this comment | 07- 4-08 12:06 PM