EventHorizon

If you have an unknown linear function, f(x), and you wish to find it's definite integral between z and z+1, the value can be found if you know the value of the function at those end points, z and z+1. The value of the definite integral is (f(z)+f(z+1))/2. As shown in the topic "Integrate an unknown quadratic," the same thing can be done with quadratics. The value of a definite integral between z and z+2 is (f(z)+4*f(z+1)+f(z+2))/3. Ignoring the constant factor (so the coefficient for f(z)=1), the pattern for linear functions is (1,1). The pattern for quadratic functions is (1,4,1). Does the same possibility exist for cubics? If so, what is the pattern for cubics? For which degree of polynomials can you do this? Is there a way to predict the pattern for an nth-degree polynomial?

Correct. I was hoping it would last longer, but looking at your work I see that it was simpler than I thought.

As you know, a quadratic is of the form ax^2+bx+c. Given the equation, it's easy to integrate to find the area under the curve between two values. Lets see if you can find the area under the curve without knowing the function. You know the following three pieces of information (where g, h, j, and k are real numbers): f(x) is quadratic f(j) - f(j+2k) = g f(j+2k) + 2*f(j+k) = h In terms of g, h, j, and k, what is the value of integrating f(x) between j and j+2k? How did you find it? (Yes, it is possible to solve this, and, yes, I am being really sadistic)

Assuming you cannot edit the map variable (that would be a lot of free space), the algorithm that would take the least amount of space (and still be guaranteed to find the shortest path) would be iterative deepening depth-first search. The space to find it would be simply the space to store the path, whereas the space to store the distances in Lee's algorithm would take another copy of the map. If you would accept probably finding the shortest path, iterative deepening random wouldn't even need to store the path (try a path while printing it out, print out 'failed' and try again until a solution is found). Depending on how long you run it at each depth, you could be almost certain (to any required probability) that you've checked all paths, but it will be monumentally slow. As for the quickest, that would depend on the map. I think A* would be best for large worlds with few obstacles and lots of possible paths. For highly constrained worlds that still have a lot of long dead ends and branches, bidirectional breadth-first search would be my choice. For small constrained worlds with few paths, bidirectional (or just unidirectional if small and only small branches) Lee's is fine (unless you add in variable edge costs, then you'd need to add a priority queue). A contest would be interesting, but I'm not sure how much I'd participate (have other stuff I need to code).

I don't think you'll like it (quite complicated, slow to compute), but here's what I've got... edit - had something numbered 0-based

Wow. That's really cool. Wish I would have tried to answer it myself before looking. I hadn't really thought about the answer that much when I came up with the question, either. Actually, I think I may program up a simulator so people can play around with these easily (both with deterministic and non-deterministic groundhogs). Also, it seems like it would make a nice little mini-game for my will-only-ever-exist-in-my-mind RPG. You got the answer I did for 2, and used the method I thought I would for 3. So, as for this thread... I'll have to say it's answered by Tuckleton (unless someone happens to beat your time). Good Job.

1. Now the groundhog can leave holes 1 and 5 going away from the other holes, realize there is no hole there, and run back to the hole he was in. Now that he can stay in 1 or 5, what would be the maximum number of days that it could take to find the groundhog using the most efficient strategy? If there is no strategy that will be sure to find the groundhog in a finite number of days, prove it. (Too easy?) 2. Now there are 12 holes arranged like the numbers on an analog clock. The groundhog must move to a neighboring hole every night, like usual. You realize there is no strategy that guarantees finding the groundhog in finite time, so you hire another person to check a hole once every day. What would be the maximum number of days before finding the groundhog using the most efficient strategy? 3. Same as 2, but with 3 people checking holes. 4. You have a 5 by 5 grid of holes, and the groundhog can move in the four cardinal directions. What is the minimum number of people needed before you can be sure to find the groundhog in a finite amount of time? How long does it take with that number of people? (yeah, I tend to put multiple problems in threads... it's like a shotgun approach, hopefully 1 or 2 are really good.)

Agreed.

Wow. Never would have guessed, nor would I have believed you if you told me. (Don't look at my spoilers if you haven't thought about the problem and decided on a solution...) Very cool. Thanks for posting.

I'm actually kinda interested now.... I'll code this up a little later and post code/results.

I'm thinking the top one is better, but I'm not gunna try to calculate the probabilities...

Read through the posts, and you'll see that the OP made a mistake and the third circular number is 12, not 8.