[HN Gopher] I Spent Three Nights Solving Listen Labs Berghain Ch...
___________________________________________________________________
I Spent Three Nights Solving Listen Labs Berghain Challenge (and
Got #16)
Author : kuberwastaken
Score : 52 points
Date : 2025-09-21 14:11 UTC (3 days ago)
(HTM) web link (kuber.studio)
(TXT) w3m dump (kuber.studio)
| chriskw wrote:
| Nice to see another participant's thinking process for the
| puzzles! I ended up getting 5th place using dynamic programming
| for all of the scenarios, but I'm under the impression that
| almost everybody in the top 20 had almost equally good strategies
| and most of the variance in scores was due to luck with the
| sequence of people they got.
|
| A quick sanity check is in Scenario 2, you needed 300 creative
| people each with a ~6.2% chance of showing up. The odds of
| getting a sequence of people where that's even possible for the
| first place score (2906 rejections + 1000 accepts = 3906 total
| people) is on the order of 1 in 10000, and that's without even
| factoring in the other constraints.
| mpeg wrote:
| That's what I thought when I saw the challenge originally...
| maybe a better way of running it would have been to have each
| run be with a deterministic seed, and apply to all candidates.
|
| That way people can test offline with random sequences, but the
| leaderboard runs have the same seed for everyone. Maybe I'm
| missing something obvious, but I think this would have lessened
| the impact of luck.
| chriskw wrote:
| The tricky thing is the code for making decisions runs
| locally on the contestants machine, so the first time they
| submit they can record the sequence locally and compute the
| best set of actions for the next time they submit. Even if
| the sequence is somehow tied to a user's account so they
| can't resubmit against the same sequence, they could do the
| same thing with an alt account and feed the sequence to a
| main account.
|
| Sites like Kaggle usually get around this problem by running
| contestant code in a containerized environment server side,
| but even then you can get clever with tricks to leak info.
| hermannj314 wrote:
| I peaked at around 21st but stopped playing because it seemed
| to be a lottery.
|
| I ran simulations with perfect information and found the lower
| bound for scores. Scenario 2 was mean 3743 rejections with 265
| std deviation. This is the curve formed from simulated data and
| a strategy that had with perfect information, i.e. you could
| build the best possible strategy after knowing the random
| assignments.
|
| So winners had scores that I could not even theoretically
| achieve unless I could see 1000s of scenarios.
|
| So I ran my code locally and was happy that my code was always
| just a few rejections off of optimal and called that a private
| success.
| florianj wrote:
| How did you use DP for scenario 2 and 3? The table seems to be
| way to big unless you do some optimizations.
|
| Also did you optimize for the best case in any way vs expected
| cases?
| chriskw wrote:
| The trick for Scenarios 2 and 3 is that most of the
| constraints don't end up being bottlenecks. For example in
| Scenario 2, well-connected pretty much always gets satisfied
| while doing the other constraints, so the DP table only needs
| 4 dimensions (space, Berlin local, techno lover, creative).
|
| My other trick was to only build the full DP table for the
| latter half of the game (i.e. when all the constraints are at
| least 50% satisfied) which across 4 dimensions reduces the
| size by a factor of 16. For the beginning half of the game I
| combined Berlin and techno into a single parameter, which
| technically isn't perfect but doesn't matter too much in the
| early game. I wrote up my approach here if you want more
| details: https://chriskw.xyz/2025/09/16/Berghain/
|
| Re: optimizing for best case vs expected case, I thought
| about that but in simulations my strategy mostly performed
| the same as a "perfect knowledge" strategy where you could
| see all of the people in line ahead of time and retroactively
| accept people. When it under performed it was usually because
| some miraculous string of people showed up near the end, but
| betting on that happening seemed like it would do more harm
| than good, i.e. it would throw away more best case scenarios
| than it would salvage.
| 4gotunameagain wrote:
| Wait until they find out that guest list on Berghain does not
| guarantee entry !
|
| What is the probability of a person with both the attributes
| "looks like they belong to berghain" and "can solve an obscure
| live optimisation challenge" ?
| j4hdufd8 wrote:
| What are you implying about people that go to Berghain?
| stavros wrote:
| They don't look like they can solve some obscure optimisation
| challenge.
| aqme28 wrote:
| > What is the probability of a person with both the attributes
| "looks like they belong to berghain" and "can solve an obscure
| live optimisation challenge" ?
|
| As someone who goes there often, I can say it's surprisingly
| high
| 4gotunameagain wrote:
| Surprisingly high is not high, or we're meeting different
| kinds of people in there ;)
| bowsamic wrote:
| How do you know someone goes to Berghain? Don't worry,
| they'll tell you
| vovavili wrote:
| >What is the probability of a person with both the attributes
| "looks like they belong to berghain" and "can solve an obscure
| live optimisation challenge" ?
|
| As a person who has been there, you'd be surprised. Strict door
| policy is sort of a soft intelligence test, and the music there
| is so insanely good that it attracts highly creative, highly
| open folks.
| NooneAtAll3 wrote:
| > For Scenario 1 (just two traits), he solved it _exactly_ using
| dynamic programming.
|
| I wonder if this exact solve tried setting "more rejections than
| X" as failure, so that you can get better best case for the cost
| of dropped worst cases
| florianj wrote:
| Great write-up. Love how everyone is sharing their solutions. Fun
| fact, this is an actual business problem we have to solve at our
| company (Listen Labs).
|
| We have an AI customer interviewing platform our customers ask us
| things like: "I want to talk to 200 people, at least 100 who are
| ChatGPT Pro users, 75 who use Gemini weekly, and 50 from each
| region of the US."
|
| We don't know those attributes upfront, so we have to ask
| participants screening questions and decide in real time whether
| to move forward.
|
| Of course, it's a bit different as we optimize for the average
| case, not the best case, and we don't know the distributions (but
| can estimate with LLMs!).
___________________________________________________________________
(page generated 2025-09-24 23:02 UTC)