Comment by indescions_2018 | Hacker News Reader

Comment by indescions_2018 | Hacker News Reader

Parent Full thread

indescions_2018

Yeah, I think they are a terrific way to "keep your sword sharp". Jump start the neurons in the early AM or lazy summer day. As well as a way to learn new algorithms, new languages via problem solving.

Code Jam had a particularly juicy one in the recent Qualifying Round, that could easily be part of a modern shadow rendering game engine. Just to put it into perspective, only around 1000 out of 25000 entrants were able to solve the large data set in the allotted time!

Google Code Jam 2018 Qualifying Round Problem D: Cubic UFO

https://codejam.withgoogle.com/2018/challenges/0000000000000...

Incidentally, I don't really learn a lot from books or tutorials such as the one linked. But rather from the contest analyses and top winners code solutions.

Interesting problem.

I imagine the juicy part is that there is no clear cut formula for determining the rotation from the area needed.

Thus the task is to come up with a fast approximation algorithm to work backwards.

So brute force way:

  If area_needed > area_cast:
    rotate_cube(delta)
    delta=/2
  else similar rotation on -delta

Now, my 3d geometry is rusty, so maybe rotation on 2 axis is enough but still optimizing 2 arguments is not going to be easy. Maybe you can max one rotation then max 2nd one.

My first instinct says that if you just project the corners straight down (because of orthographic projection) onto the XZ plane, then the area of the shadow is just the area of the convex hull of those projected points.

I don’t know how to calculate that hull off the top of my head, but that’s the type of stuff you can look up during real world scenarios.

Reply on news.ycombinator.com