I’m rather partial to obtaining my candy the old fashioned way, but still enjoy and identify with the spirit of Halloween. And in that spirit (no pun intended!), I pose this query: with millions of dollars worth of free candy available during a 4-6 hour time window (perhaps more if a plane is available to timezone hop?), how could one start crafting the most efficient algorithm to maximize the candy take. I guess I’m interested in both simple staregies/tricks to get more candy on a small scale, as well as more sophisticated mathmatical approachs involving teams, etc. I know that urban areas would likely be ideal, possibly apartment buildings? Socio-economics and past-year stastistical data would likely aid the endevor, so as to know which areas tend to have the most candy, and which streets have relitively few jackolanterns on them.
I’d rule out apartment buildings, as frequently the residents don’t participate in trick or treating (plus, many are gated/secure, so you can’t even get in).
All I have is this one piece of anecdotal evidence: my biggest take ever was along Lakeshore Drive on Lake Huron in a small town – you know, that’s where all of the expensive, lakeside houses are.
Jason Fox? Is that you?
If you had an algorithm to solve this problem, it should be pretty easy to use it to solve the traveling salesman problem, so don’t expect an exact solution here.
As a city-dweller, my advice is to get the hell outta Dodge. (Or Chicago, or wherever you are.) Apartments are horrible, because hardly any one participates. Immigrant neighborhoods, likewise. Halloween is still very American, and the rest of the world doesn’t get it - recent immigrants are likely to shut their curtains and ignore the goings-on. Besides that, all those walk-ups and brownstones between the apartments have stairs and often gates, which will slow you down.
You want to head for the suburbs, my friend. But not the new shiny McMansion suburbs - the older suburbs, where houses are still close together, and there are lots of grandmotherly types who love to see the little kids. Affluent is going to increase the quality of your candy, but not always the quantity, so weigh your priorities. More money = more chocolate. But, whatever you do, DON’T let them see you jumping out of your mom’s car to trick-or-treat in a neighborhood that isn’t yours! Makes people irritable. Your best bet is to become friends with a suburbanite back in July or so, so you can suggest trick-or-treating together in his neighborhood.
Our preferred pattern is to walk around the blocks in a snake fashion, doing only one side of each street on your way, say, north. Then you can hit the opposite side of each block as you wind back south. This eliminates any dead time walking without gathering candy.
Be polite, always say Please and Thank You and you’ll often get extras. Don’t shove! Lots of people give the last kid an extra piece or two as a reward for being patient, or simply because they grabbed a whole handful out of their bucket and overestimated and don’t want to carry the leftovers back in!
Don’t be noisy or unruly on the porch. If you’re quiet, you can hear when someone is walking to the door. This prevents the wastage of time when you decide no one’s coming and head back down the stairs, just in time to see the door open with CANDY!
You can often get your little sister to trade you some good chocolate for candy corn and gum. She’s little and doesn’t know any better. 
If you’re with a group of other kids, and none of you is wearing a costume that’s too distinctive, you can often hit the same houses multiple times in various permutations. For example, if your group contains a ghost, a clown, a werewolf, and a Superman, a treat-giver might notice if a set of kids wearing those four costumes all showed up together multiple times. But if one time around, it’s a ghost and a clown, and the next time, it’s a ghost and a werewolf, and then a ghost and a Superman (along with all the non-ghost pairings; I’m assuming you’re the ghost) then you could hit the same house three times unnoticed. More, if you also go out singly and in threes.
And even if you don’t have a naïve little sister, you can still profit by trading, since different folks will place different values on various candies. For instance, if one of the folks in your group has braces, you might be able to get 5 or 6 pieces of gum from him for a single piece of chocolate. And if you’re really canny, you might then trade those gumballs to the local Violet Beauregard for one chocolate each. As long as the kid with braces and Violet aren’t trading directly with each other, you can make out like a bandit this way.
Dress up as Borat!
Fill your pumpkin!
Go out on November 1st.
This is a true story:
My first Halloween, my parents got the date wrong. My older brother had told me what Trick or Treating was like. So, we got our costumes and our pillowcases and our parents drove us to a part of town with more houses. We knocked on the first door, yelled “Trick or Treat!”, got a somewhat bemused look from the person who opened the door, who looked at the bowl still full of candy from the night before. He picked it up with a look on his face of “Well, I don’t want to eat all this shit”, dumped half into my brothers bag, half into mine.
:eek:
Four or five houses later, our bags were full and we were done.
It hasn’t been the same since.
Not neccesarily depending on how constrained the problem space is. As a rather trivial example, if you could prove that candy take is a convex function for any straight line across the map, then it’s a simple optimisation problem to find the global minima.
However, it seems the simplest strategy is to outsource the actual candy collecting work into a franchise. Determine the optimal candy routes and write up a candy strategy guide. Then sell the resulting routes to fellow entreprenurial children for a cut of their rake, say 50% of any increase in candy take over the previous year. Using the internet allows you to do this on a national scale and with the right marketing campaign, you could become a candy magnate by next halloween and sell your company to google for $1.65bn.
I’m sure there are lots of special cases where the problem is easy to solve, just like there are with many NP-complete problems. The question isn’t whether the problem is always hard, but how hard it is in the worst case.
Anyway, I’m pretty sure that our problem can be shown to be NP-hard with a reduction from the TSP if you’ll accept the constraint that you can only get candy from a house once. I need to work it out at home, though, so I should have a post this evening.
The popular method around here involves 6 or 8 of your closest friends and a pickup truck.
- Pile into the back of the truck.
- Haul ass to nice neighborhood.
- Race from house to house.
- Pile back into truck and head for the next nice neighborhood.
- Lather, rinse, repeat.
(bolding mine)…aside from trading with the kid with braces or using the group to blend in for multiple visits, I haven’t really seen how working in teams really helps too much. I guess your sellingout to google strategy only works if you’re able to accomplish that optimisation business, but I don’t yet know how that would work?
I recall a scam I pulled with my younger brother one halloween lo these many years ago. I would go up to the house and point out my brother by the gate and say he was afraid to come up & collect his candy. Later we would hit the same house & reverse rolls. We thought we were sooooo clever, but I can’t believe we fooled anyone. I guess we were still young enough to be “cute”.
Those are pretty big asides. Even in a group of only four, the “blend in for multiple visits” tactic triples your haul, and that’s a pretty small group of kids. The value grows exponentially as the number of kids increases. Likewise for the trading: Even if you don’t have the savvy to turn an absolute profit, as in my example, commerce still results in increased total wealth, as in any economy, due to people valuing things differently. Some kids will benefit more than others, of course, but everyone benefits: The kid with braces, for instance, loses only gum that was of no value at all to him, but gains some amount of chocolate that does have value.
I live in a town of about 5000 or so. Most of all the houses are spread out over 50 square miles or so. Next larger town is about 1.5 hours away. Another nearby town has its houses even more spread out.
Well take in this whole area 100 square miles or so and there is a part of “town” where all the houses are all lined up nice and neat like. Probally less then 10% of the total area population. Right near the middle of town.
Guess where EVERYONE goes trick or treating. You got it. Is is crazy. Cars kids parents. Everything. almost a line to get to each door. Folks from other parts of the area drop off candy to help out.
Has to be the highest density of trick-or-treaters almost anywhere.
I live in moderately large town. My son has many kids from around his location and hands out a lot of candy. We live on a circle off the main through street. At one time kids were brought in by the car/truck/van load. It’s been quite a few years since we have had more than one, mostly no TorTers
Happy Halloween and all that rot.** Carve your Own Pumpkin ** 
As promised, here’s the proof that optimizing your candy take is NP-complete.
An instance of the Halloween loot problem is a 5-tuple (H, C, v, M, k), whose elements break down as follows:[ul][li]H is the set of houses.[]C [symbol]Î[/symbol] H [symbol]´[/symbol] H [symbol]®[/symbol] Z[sup]+[/sup] is the cost function for moving from house to house.[]v [symbol]Î[/symbol] H [symbol]®[/symbol] Z is the value function for the candy at a given house. As mentioned above, v(h) = 0 if house h has been visited.[]M is the maximum cost.[]k is the target for the total value.[/ul]A solution to an instance of the Halloween loot problem is a sequence of houses h[sub]1[/sub], h[sub]2[/sub], …, h[sub]n[/sub] with [symbol]S[/symbol][sub]i = 1[/sub][sup]n - 1[/sup]C(h[sub]i[/sub], h[sub]i + 1[/sub]) < M and [symbol]S[/symbol][sub]i = 1[/sub][sup]n[/sup]v(h[sub]i[/sub]) > k.[/li]
The traveling salesman problem is similar. An instance is a 3-tuple (H, C, M) with the following interpretation:[ul][li]H is the set of houses.[]C [symbol]Î[/symbol] H [symbol]´[/symbol] H [symbol]®[/symbol] Z[sup]+[/sup] is the cost function for moving from house to house.[]M is the maximum cost.[/ul]A solution to an instance of the traveling salesman problem is a sequence of houses h[sub]1[/sub], h[sub]2[/sub], …, h[sub]n[/sub] with [symbol]S[/symbol][sub]i = 1[/sub][sup]n - 1[/sup]C(h[sub]i[/sub], h[sub]i + 1[/sub]) < M.[/li]
Notice how similar the definitions are. That makes the reduction easy. Every instance of the traveling salesman problem (H, C, M) can be mapped onto an instance of the Halloween loot problem (H, C, v, M, |H|), where v(h) = 1 if house h has not been visited and 0 otherwise. H, C and M are inputs to the reduction, so they can be computed in constant time. v can be constructed in constant time, and |H| can be computed in linear time. Therefore, the reduction is polynomial, and we have that the Halloween loot problem is NP-hard.
But I promised to prove that it’s NP-complete, and to do that, I need to show that it’s in NP. This is easy. Verifying a solution simply involves n lookups into C, and n computations of v, for a total time that is [symbol]O/symbol. Therefore, the Halloween loot problem is verifiable in polynomial time, and is NP-complete.
Except that distribution of houses (and hence, the distance function between them) usually follows some constraints that are not found in the general Travelling Salesman Problem. Namely, houses are distributed along streets, and the distance between two adjacent houses on the same street is less than the distance from a house to any of its nearest neighbors on on a different street. With these constraints, the problem becomes merely one of finding an Eulerian path on a graph (the vertices are intersections) with every edge doubled (since there are two sides to each street). And, of course, finding an Eulerian path on such a graph (or indeed, on any graph which has an Eulerian path) is child’s play.
wow its going to take me like a week to gather enough background info to appreciate ultrafilter’s elegant solution but I will definitely post back to the thread with my best attempt at an simplified explanation.