What is Operations Research, and why is it related to this puzzle.
I found the puzzle easy enough. It's just a matter of calculating how many moves are needed from square 11, then square 10, and so on. The chutes complicate matters a little, but not much.
OR is a discipline that studies systems and processes, then optimizes them based on statistical and mathematical modeling. At least from a high level, that's the key. In industry, it's used for routing (see UPS, any big box store, Amazon) of goods, in airlines for management of passengers and routes. In industrial processes they take the various factors involved (material costs, personnel costs, time, safety, whatever) and develop models to enable better decision making. Many applications of it are, essentially, applied statistics and math modeling. EDIT: In a factory setting OR/IE types are heavily involved in layout of the environment, often modeled as a network. Workstations might be nodes, transit between them are edges. Various costs would be involved. Node A generates widget A at a rate of T_A, node B requires node A and item B - externally sourced - to produce widget B. Node B is the bottleneck, break it out into 3 worker processes... If this sounds like how we design distributed processes in software, it's because it's the same problem, fundamentally.
As to the puzzle, I guess it's about modeling the problem in a manner similar to other business processes. Consider the game as a business process model of handling a software CR. Each chute is a potential setback (crap, found an error during QA, send it back to testing for analysis) and the ladders could be things that advance a process unusually quickly (we got the data from the customer on the error, turned out it isn't with our code but documentation on how to use the program, update the manual and bypass testing/SQA). Collect data over time, optimize away inefficiencies or deficiencies that induce extra work or rework.
A simple, principled way of solving October's problem is to model it as a Markov chain with absorbing states (the "Finish" square, and the two invisible squares past it -- the two invisible squares are unnecessary as mentioned by jtsummers below), and compute the expected absorption time starting from the first square.
Since this seems to only care about the probability of any transition would you need the 2 invisible squares, or wouldn't the "Finish" square suffice? That is, in any square that can advance to 12 (10, 11) 10 has a 1/3 probability of advancing to 11, and 2/3 of hitting 12/13. While 11 has a probability of reaching 12 (or beyond) of 1.
Also, thanks for that link. Markov chains are something I know about, but never really set to the task of learning. It's also a much quicker solution than my initial concept, and neatly handles the chute/ladder squares (that is, on square 5 you'd have a 1/3 chance of ending on 11, 1/3 on 2 and 1/3 on 8; 6 and 7 are never actually reached - which also means they can be eliminated from the set of states).
I'd say there simple are 8 possible states -- nominally 12, but 2 each are collapsed via chutes and ladders.
If I had to solve it by hand, however, I wouldn't try to invert an 8x8 matrix. Rather, I'd write it down as a simple system of linear equations. Let f1, ..., f12 be the expected number of steps to completion if you start in position 1, ..., 12.
Re: Author's point - I don't think so. This seems like toy problems about how to frame problems in an OR style. Absorptive Markov chains (for the linked puzzle) are an OR tool that solves the problem very efficiently. Even though it's a small puzzle and it can be solved by hand with other approaches reasonably efficiently, those approaches may not scale as well to larger variations of the problem or aren't as general a solution or don't tie in as well when connecting a number of different optimization/planning problems.
Regarding the wide-ranging difficulty of puzzles (perhaps it's just too late for me here, is that FarmOR one really an elementary school problem? EDIT: Just reread it, it's much easier than I originally thought because I misread it), it reminds me of the puzzles in CACM (I think it was that publication). They were generally math/CS puzzles, 3 at different levels of difficulty. The 3rd was - occasionally? often? - an open problem and all 3 would be similar, but different conditions (perhaps becoming more general) would increase the difficulty from puzzle to puzzle. On a given puzzle it might be trivial to solve 1 & 2 for a CS freshman, others might challenge seniors or grad students (depending on their domain at least). The author wasn't making a comment on the nature of CS, he (IIRC) was simply presenting puzzles and challenges. Some are easy, some are hard, some may be impossible without a lucky insight or domain familiarity.
10 comments
[ 1.6 ms ] story [ 44.3 ms ] threadI found the puzzle easy enough. It's just a matter of calculating how many moves are needed from square 11, then square 10, and so on. The chutes complicate matters a little, but not much.
As to the puzzle, I guess it's about modeling the problem in a manner similar to other business processes. Consider the game as a business process model of handling a software CR. Each chute is a potential setback (crap, found an error during QA, send it back to testing for analysis) and the ladders could be things that advance a process unusually quickly (we got the data from the customer on the error, turned out it isn't with our code but documentation on how to use the program, update the manual and bypass testing/SQA). Collect data over time, optimize away inefficiencies or deficiencies that induce extra work or rework.
[1] http://en.wikipedia.org/wiki/Operations_research
EDIT 2: Not sure if tired or autocorrect, but manor and manner are not the same thing.
See e.g. http://en.wikipedia.org/wiki/Absorbing_Markov_chain
Also, thanks for that link. Markov chains are something I know about, but never really set to the task of learning. It's also a much quicker solution than my initial concept, and neatly handles the chute/ladder squares (that is, on square 5 you'd have a 1/3 chance of ending on 11, 1/3 on 2 and 1/3 on 8; 6 and 7 are never actually reached - which also means they can be eliminated from the set of states).
I'd say there simple are 8 possible states -- nominally 12, but 2 each are collapsed via chutes and ladders.
If I had to solve it by hand, however, I wouldn't try to invert an 8x8 matrix. Rather, I'd write it down as a simple system of linear equations. Let f1, ..., f12 be the expected number of steps to completion if you start in position 1, ..., 12.
f12 = 0. f11 = 1. f10 = (f11 + f12 + f12)/3 + 1. f9 = f8, because of the chute. f8 = (f9 + f10 + f11)/3 + 1.
and so on.
Regarding the wide-ranging difficulty of puzzles (perhaps it's just too late for me here, is that FarmOR one really an elementary school problem? EDIT: Just reread it, it's much easier than I originally thought because I misread it), it reminds me of the puzzles in CACM (I think it was that publication). They were generally math/CS puzzles, 3 at different levels of difficulty. The 3rd was - occasionally? often? - an open problem and all 3 would be similar, but different conditions (perhaps becoming more general) would increase the difficulty from puzzle to puzzle. On a given puzzle it might be trivial to solve 1 & 2 for a CS freshman, others might challenge seniors or grad students (depending on their domain at least). The author wasn't making a comment on the nature of CS, he (IIRC) was simply presenting puzzles and challenges. Some are easy, some are hard, some may be impossible without a lucky insight or domain familiarity.