oboe assignment
June 25, 2026
for a job application, i had to think about the most inefficient way to find a needle in a haystack, here is the solution and math proof(linked) i ended up with! it was such a good learnign experience and was fun, so posted here
Prompt:
With a budget of less than $100, come up with the most inefficient method imaginable to find a needle in a haystack. Briefly explain why it's so bad as well as its computational complexity.
for the most inefficient method, i had a person performing a random walk across every piece from the haystack, and increasing the likelihood that they re-visit pieces.
materials:
- roboclaw - $6
- scissors - $1.67
- blindfold - $1.29
- 144 pack of pencils- $19.99
- 5 pencil sharpeners - $4.45
- 11 reams of paper - 6 bucks(1 individual ream)
- calculator - $11.48 dollars
- 10 sided dice - $6.76(with shipping)
- wood ruler - $0.89
total of $98.53 spent
steps:
- open up all the reams of paper, take each singular piece of looseleaf paper and cut it into cards of 1cm x 0.5cm dimension
- 21cm x 55cm = 1,155 papers per sheet
- 1155 x 500 x 11 = 6,352,500 cards(more than average hay bale of 6 million)
- put a blindfold on
- grab the roboclaw
- begin the process of lining up pieces(from the haystack) and the cards:
- pull out each piece of hay(or needle, you won't know) with roboclaw and place it on the ground
- grab a card of paper and place it after the piece(its an edge). cards will live in between pieces.
- continue until every piece is placed down in line.
at this point, the line looks like this:

- spin around with blindfold on and then point your finger. take blindfold off. you start to the piece closest to the direction your finger is pointing.
- then we begin random walk:
- when you land on a piece that has value of x on the right card, and value of y on the left card, compute odds for progressing to the right side with calculator:
- going to the right is:
- we roll a ten sided dice against the percentage odds to simulate random choice.
- the first roll of the dice determines the tens decimal place of the odds, the second the ones, and so on.
- use the following logic as we iterate through each decimal place:
- if (dice > Pright decimal): go to the left
- else if (dice < Pright decimal): go to the right
- else(its equal): continue rolling
- note: since calculator only computes odds up to 10 decimals, if we are still tied, we favor going to the right ensure it remains sublinear.
- whenever a step is made, the value of the card we crossed increments by 1. to calculate the weight we do (k+1) where k is the value on the card.
- e.g. if the initial weight is , the new weight is
- continue until you find the needle
- note: if you end up at the end of the line, you must go directly to the left/right(of the piece you just crossed)
- when you land on a piece that has value of x on the right card, and value of y on the left card, compute odds for progressing to the right side with calculator:
- needle is found!
this method is terrible because it:
- doesn't remove pieces of hay from pool
- only allows steps of size 1, meaning you cannot easily leave where you started
- favors pieces you have already seen, exponentially decreasing your odds of "escaping" to pieces you have not seen yet
worst case compute complexity here is O(4n). here’s the full proof for more details.
- we know that at your first visit to a given piece i, the weight of the edge to your left is 2, and the weight of the edge to right is 1.
- we determine a fixed escape probability given any attempt at vertex i. this is derived from Beta(1/2, 1).
- from this probability, we write a function for the average number of failures(left) for one success(right).
- we know the n-th vertex(needle in worst case) will be visited once. so we can find that the n-2 edge failures can be calculated by multiplying 1(successes) by average failures.
- we continue doing this all the way down till the first piece. we use the failures number since its approx the same as successes over n turns.
- this gives us the total number of leftward crossings for neighboring vertices, which equates to 4^n.
- although leftward crossings only represents ~half of all visits doubling this number will not impact compute complexity significantly, so it stays at O(4^n)
note: i used oboe to learn about reinforced random walks, and beta distributions when going through this problem. Pemantle(1988), proves that increasing weights linear(or less) guarantees that you will eventually visit each vertex.
