This is pretty cool... I tried to answer it myself, but I was absolutely stumped.
I implemented it for fun, and it does end up exactly as described in the video.
I implemented it for fun, and it does end up exactly as described in the video.
Code can be run online here. Just select .NET 6 as compiler on the left and then paste it in (has to be in that order).
Code:
using System;
using System.Collections.Generic;
using System.Linq;
namespace OnlineRestaurant
{
class Program
{
static void Main(string[] args)
{
const int Count = 100;
int dead = 0;
const int TestCount = 10000;
for (int i = 0; i < TestCount; ++i)
{
var boxes = GetRandomBoxes(Count);
for (int n = 0; n < Count; ++n)
{
if (!Find(n, boxes, Count / 2))
{
dead++;
break;
}
}
}
double pct = 1.0 - (dead / (double)TestCount);
Console.WriteLine($"Alive: {TestCount - dead}, dead: {dead}, success rate: {pct:0.00}");
}
static List<int> GetRandomBoxes(int count)
{
var rnd = new Random();
var numbers = Enumerable.Range(0, count).ToList();
var boxes = new List<int>();
while (numbers.Count > 0)
{
int idx = rnd.Next(0, numbers.Count);
boxes.Add(numbers[idx]);
numbers.RemoveAt(idx);
}
return boxes;
}
static bool Find(int n, List<int> boxes, int maxAttempts)
{
int attempt = 0;
int pointer = n;
while (attempt < maxAttempts)
{
if (boxes[pointer] == n)
return true;
pointer = boxes[pointer];
attempt++;
}
return false;
}
}
}
