Unlimited detail challenge: the most easy formulation
Thanks to Dave H. for noticing the new Euclideon site!
Now, I propose you to think about the most easy formulation of unlimited detail.
You live in a 2D world, you have a 1D screen which has 4 pixels. You look at the world, through the screen, by using a 90deg frustrum. The 2D world is finite, with diameter N, measured in the unit lengths of the pixels (so the screen has length 4 and your eye is at distance 2 from the screen). The world contains atoms which are located on integer coordinates in the plan. There are no two atoms in the same place. Each atom has attached to it at most P bits, representing its colour. Your position is given by a pair of integer coordinates and the screen points towards N, S, E, W only.
Challenge: give a greedy algorithm which, given your position and the screen direction, it chooses 4 atoms from the world which are visible through the screen, in at most O(log N) steps.
- think about what “visible” means in this setting
- use creatively numbers written in base 2, as words.
The Teaser 2D UD might help.
I’m not giving this challenge because I am a secretive …. but because I enjoy collaborations.