pfedak
Joined 10 years ago
Joined 10 years ago
I don't get the gotcha you're trying to do. Yes, the simple pattern you posted can be extended, but it has very little to do with the problem. If you had suggested [1,2,3] [4,5,6] [7,8,9] worked I would still have made my comment; I think the fact that you found a pattern that could be extended easily should have itself been a counter-indicator. Compare with something like the Fano plane[2].
I would want you to take away from this that posting the thing you came up with in "20 seconds" isn't as neutral a contribution to conversation as you thought. Things are often complicated and worth engaging with. It would have been cool if you kept going far enough to see there's a nice argument that it's actually impossible to solve it with n-sided dice for n people if n>2.
[1] https://xkcd.com/793/ [2] https://en.wikipedia.org/wiki/Combinatorial_design
You also can't generally "and so on" constrained combinatorial arrangements like this.
Lines in 3D remaining straight in a photo is unrelated and not actually demonstrated by the image. I'm having trouble imagining why this matters - you're trying to find the intersection of two lines in an image without drawing anything?
Paying at 1/2 will be optimal if it ends before you buy, very bad (3x optimal) if it ends right after you buy, and slightly better than the solution in the post if it lasts at least twice that long (1.5x optimal vs e/(e-1)).
The metric in the post is just the worst of those ratios. Assuming the unproven statement in the post (that the solution which is a constant factor worse than optimal is best), any solution of the form you suggest is going to have similar tradeoffs. If we had a distribution, we could choose.
sounds like the concert in question
One way to explain things like height being normally distributed is that there are a bunch of independent factors which contribute, and the central limit theorem applied to those factors would then suggest the observed variable looking normal-ish.
I did finally find the duration logic when I was trying to recreate the path, I made this shader to try to compare: https://www.shadertoy.com/view/l3KBRd
Their zoom actually is my "y" rather than a scale factor, so the metric is ds^2 = dy^2 + (C-y)^2 dx^2 where C is a bit more than the maximal zoom level. There is some special handling for cases where their curve would want to zoom out further.
Normalizing to the same cost to pan all the way zoomed out (zoom=1), their cost for panning is basically flat once you are very zoomed in, and more than the hyperbolic model when relatively zoomed out. I think this contributes to short distances feeling like the viewport is moving very fast (very little advantage to zooming out) vs basically zooming out all the way over larger distances (intermediate zoom levels are penalized, so you might as well go almost all the way).
I considered two metrics that ended up being equivalent. First, minimizing loaded tiles assuming a hierarchical tiled map. The cost of moving x horizontally is just x/y tiles, using y as the side length of the viewport. Zooming from y_0 to y_1 loads abs(log_2(y_1/y_0)) tiles, which is consistent with ds = dy/y. Together this is just ds^2 = (dx^2 + dy^2)/y^2, exactly the upper-half-plane metric.
Alternatively, you could think of minimizing the "optical flow" of the viewport in some sense. This actually works out to the same metric up to scaling - panning by x without zooming, everything is just displaced by x/y (i.e. the shift as a fraction of the viewport). Zooming by a factor k moves a pixel at (u,v) to (k*u,k*v), a displacement of (u,v)*(k-1). If we go from a side length of y to y+dy, this is (u,v)*dy/y, so depending how exactly we average the displacements this is some constant times dy/y.
Then the geodesics you want are just the horocycles, circles with centers at y=0, although you need to do a little work to compute the motion along the curve. Once you have the arc, from θ_0 to θ_1, the total time should come from integrating dtheta/y = dθ/sin(θ), so to be exact you'd have to invert t = ln(csc(θ)-cot(θ)), so it's probably better to approximate. edit: mathematica is telling me this works out to θ = atan2(1-2*e^(2t), 2*e^t) which is not so bad at all.
Comparing with the "blub space" logic, I think the effective metric there is ds^2 = dz^2 + (z+1)^2 dx^2, polar coordinates where z=1/y is the zoom level, which (using dz=dy/y^2) works out to ds^2 = dy^2/y^4 + dx^2*(1/y^2 + ...). I guess this means the existing implementation spends much more time panning at high zoom levels compared to the hyperbolic model, since zooming from 4x to 2x costs twice as much as 2x to 1x despite being visually the same.
I hope your life is full of "personal side quests" pursuing questions that appeal to your particular sensibilities. You should wrestle with that feeling of not understanding something, use it as a signpost pointing towards interesting ideas rather than as a reason to stop.
I'll get you started on the proof: Suppose for n>2 you have n n-sided dice with disjoint sets of numbers and you want each of them to have an equal chance of rolling the highest number. One of them must have the highest overall number, and it will roll that 1/n of the time. What can you say about the other numbers?
The relative ordering of the other dice doesn't depend on this result. They need to each have an equal chance of coming first. How many total outcomes are there?