4 developers picking a random restaurant

4 developers (including me) decided to go out for dinner. They came up with 20 possible restaurants to go. I received a message which reads as follows:

Pick one of the 20 restaurants at random. And do so with 0 inputs from any of us. You should be able to prove that it's random.

The message was an email with all 4 developers in the loop. (Or a slack group where all 4 developers were part of it, Or WhatsApp group, anything really, except that they are not all physically present at the same place)

Constraints:

  1. It has to be truly random. For the scope of this post, we will assume truly random as follows: None of the 4 developers had any chance to influence the outcome, and from the perspective of those 4 developers it's totally random. (just use common sense here to say if something can be manipulated)
  2. You should not take additional inputs that would manipulate the result from any of the other developers (or) that are part of the decision process (Like asking for a seed number, etc)
  3. If need be, you should be able to prove that it was truly random.

Update: A lot of solutions proposed on reddit are missing constraint-2. The interesting part in this problem is that dev1 has to do it without inputs from other devs.

Sounds simple!!

Let's look at the most common ways to do this and why they all fail. These wrong solutions also give you an idea about what the real problem here is to solve.

1) I quickly opened up terminal, ran "echo $RANDOM" and responded to the message saying here is a random number, let's take modulo 20 to pick the restaurant. Wrong. This fails because there is no way to prove that it was indeed random. What if I picked a number of choice and responded? (So that I can go to my fav restaurant — I would do it :P)

2) I told each of the developers should run "echo $RANDOM" and then multiply them all. This does not work for 2 reasons: the last person to respond has full control of the outcome, he can multiply the 3 inputs and then decide his random number to manipulate the answer. And this also fails constraint-2.

3) I came up with a smart solution. I said, let's concat first names of all 4 developers in lexicographical order and then calculate md5 hash of that string. Then use that hash modulo 20. Nope, this does not work as well. Because it's me who came up with the idea to 'concat first names in lexicographical order'. What if I actually ran the md5 and checked that it's in my favor. I could have also checked for 'concat 4 last names', 'concat full names', 'concat birthdays'. You see there are a lot of different ways, and I may have tried all of them and picked the one that benefits me. Yet again, this fails constraint-3.

4) Here is another solution: we shall take the first 20 digits (since there are 20 restaurants) of PI and do modulo to get the solution. Okay, this got to work right? It's a universal constant, and 20 digits since we got 20 restaurants, I had no influence. Nope fails. Because once again like above case, I am the one who came up with the idea to use PI. What if I tried other universal constants and then chose PI as it is benefiting me?

Bring in your answers. There are no other constraints except the ones I told above — so go wild with your creativity. You can comment on the reddit thread below. If you want the solutions, they are available at the end of this post — collapsed. I am expecting many more solutions on the reddit thread (If the post gets noticed in the first place). reddit thread.

Update: You should check the reddit thread, it has some interesting discussions. And couple of new answers

Solutions (click to expand)

You might be thinking of something complex. The solutions are quite simple actually.

1) This is only partially correct. I create a post on Hacker News saying 'dinner choice selection'. And then use the post-ID given by HN (modulo 20) to decide the restaurant. This seems legit because the number is generated by HN, so none of the developers have a influence on it and no one need to give additional inputs. I can respond to the original message saying 'Here I created a post on HN, and the ID of that post modulo 20 is our choice'. Almost there, except one issue: I could have created 20 posts and picked the ID that's in your favor (and deleted the rest 19, and in doing so get banned from HN).

We are a step closer. If the random number is generated somehow by a 3rd party that none of the 4 have control on, that's going to be truly random as per our definition. However, as seen above we have one more issue, we can repeat the process and choose the one that works in our favor. How do we avoid that as well?

2) A solution that works for 2 developers but not for more. I can transfer 1$ to the other developer on PayPal (or any network) and use the unique message ID. It satisfies all the rules — no one has control over the ID, and it's irreversible.

We actually have a working solution here. So the idea is to incorporate 2 things — a) ID is randomly generated by a 3rd party. b) It should not be possible to delete that ID without the other developers noticing. With that pattern in mind, let's check a couple of solutions

3) Email. Write an email with other 3 developers as recipients and tell them that the message ID of that email will be used as the starting string. md5 hash is calculated for that string and modulo 20 is used. If you are not aware of this — every email should have a unique message ID that's generated by the sending server. (With Gmail you can unsend an email up to 30 seconds after initial send. So, in theory it's possible to write a program to send 100 emails at once, fetch the message ID's of them all, find the one that favors you and then unsend rest 99 emails. That said, this is a valid solution, you have to avoid Gmail to prove it)

4) Create a repo on GitHub, invite other 3 developers to it. Make a single commit after all 3 accepted the invitations (using online create file UI). Use the commit ID. This is a possible solution. It's important that developers are added before the commit, else it fails. However, one can argue that asking the other 3 developers to accept the invitation to repo is one additional input from those and so fails constraint-2 but that's not true. If you read constraint-2 — no additional inputs that would manipulate the result — accepting invitation does not manipulate the results. (I am not sure this solution works. Can someone confirm?)

That's just 2 solutions. I believe there are a lot more interesting ways as it's an open problem. Comment solutions on HN thread. Blockchain-based? Fingerprint-based? DNA based? Simple 3rd party ID based? Good old IRC?

Do you like problem solving & critical thinking? If so checkout this weekly newsletter.
A lil fun image :)