Comments on the "Three Piles" Problem

Comments on the "Three Piles" Problem

Comments on the Three Piles Problem Feb 10, 202 My timings Solved 10000 problems of size 5 in 15 milliseconds. Average time per problem: 0.0015 ms. Solved 200 problems of size 10 in 16 milliseconds. Average time per problem: 0.08 ms. Solved 200 problems of size 15 in 718 milliseconds. Average time per problem: 3.59 ms. Solved 200 problems of size 20 in 34719 milliseconds. Average time per problem: 173.595 ms.

Solved 100 problems of size 25 in 43797 Timing graph General approach The Three Piles problem can be solved by a backtracking algorithm Roughly, the algorithm goes like this: boolean solve(int numbersPlaced) { if (numbersPlaced== all the numbers)

return true; for (each pile p) { if can put the next number, numbersPlaced+1, into pile p { put it in pile p if (solve(numbersPlaced+1)) return true else take the number out again } return false } Problems with this algorithm

Its much easier for the programmer if the method returns a boolean, but the user demands a solution The method requires some data structures (say, arrays or stacks) to keep working information in We cant set this information up inside a recursive method We dont want to hassle the user with extra junk that is only needed to make the algorithm work Solution: Provide a facade method to:

Provide a simplified interface to the user Initialize any needed data structures Call the real recursive method with whatever parameters are convenient for the programmer, not the user The facade method The user wants to do this:

solution = solve(problem) where solution is some data structure containing your results In the code below, I called this data structure a Solution, but it might be implemented by (for example) an int[][] So you do this: Solution solve(int[] problem) { Solution solution; // maybe an int[][] // Create the Solution data structure and any other data // structures and initializations that you need put problem[0] into your solution pile 0 if (reallySolve(problem, solution, 0, other stuff)) { return solution;

} else return null; // Much better than returning a bad solution! } The real recursive method boolean reallySolve(problem, solution, nextNumber, ...) { if nextNumber == problem size, return true** for each pile p, if we can put nextNumber into pile p { put it in the pile if (reallySolve(problem, solution,

nextNumber+1, ...)) return true; else take the number back out again } } return false } ** If some problems may be unsolvable , you should check the solution at this point and return false if it doesnt work Backtracking in general Solution solve(Problem p) { create object to hold solution;

do any other initializations you need; if (solve(p, solution, other stuff)) return solution; else return null; } private boolean solve(Problem p, Solution s, other stuff) { if problem is already solved, return true; for each of the choices available to you { make a choice; if (solve(simpler version of p, s, other stuff)) return true; else undo this choice; // can sometimes be implicit } return false; } Summary

The notion of a facade is this: The code has a complex interface and requires lots of initializations and global structures The user wants a simple and easy to use interface Create a facade to stand between the user and the ugly code and present a simpler interface The End

Recently Viewed Presentations

  • The Challenge: To Create More Value in All Negotiations

    The Challenge: To Create More Value in All Negotiations

    X.always MASTER PART TWO 10 MARCH 2007
  • Welcome! SMART Train-the-Trainer Seminar Train RCAP Master Trainers

    Welcome! SMART Train-the-Trainer Seminar Train RCAP Master Trainers

    This relates to the social marketing aspect of SMART About Water: reaching new audiences with messages that will spur voluntary action, or reaching current audiences with new messages that will spur voluntary action.
  • Models of feedback from health consumers A/Professor Michael

    Models of feedback from health consumers A/Professor Michael

    CEO Health boards MPs Patient groups, Community Councils Local authority Regulators, Standard Authorities Nursing, AHP students Researchers Policymakers Feedback prior to Patient Opinion at Sydney/Sydney Eye Hospital Complimentary letters/cards Complaints process Consumer representation at peak committees Consumer feedback boxes Social...
  • Michigan Tenure Law Update - Dearborn Public Schools

    Michigan Tenure Law Update - Dearborn Public Schools

    High School- Explore, Plan, MME, MEAP, SRI, Star Math, Common Assessments, AP exams, and Departmental Assessments. 10% Classroom Growth Data 10% Classroom Growth based on State Assessments, District Common Assessments or Classroom Assessments (ex. Performance or product measures or other...
  • Assessment of Injuries - 12 Pdhpe

    Assessment of Injuries - 12 Pdhpe

    TOTAPS CONT… TOTAPS: Touch - Touch the casualty, again comparing to the other limb or other side of the body. During his step of the assessment of injuries you are looking to see where the pain begins moving along the...
  • Présentation PowerPoint

    Présentation PowerPoint

    تستغل البكتيرية a.tوجود الجروح الناتجة عن انخفاض درجة الحرارة - تركيب كميات كبيرة من . الأوبينات opines. وهي مركبات ضرورية لنمو . a.t
  • Hamilton Grammar School - scottishschools.info

    Hamilton Grammar School - scottishschools.info

    Numeracy Booklet for Parents (on Maths page of school web site) can be viewed, or printed, to see how examples are taught. Amount of classwork completed can be seen at the front of the jotter (green) Check homework diary is...
  • Handling of fish on-board Quality and safety issues

    Handling of fish on-board Quality and safety issues

    Therefore, handling and holding of the raw ocean tuna are very important. * The slide shows flow diagram of handling and holding of the ocean tuna that is recommended by Canadian and Asia Pacific experts (Training materials on catching and...