Project 5

Last revision:  March 24 1998

Author: YourNameGoesHere

Part A (Individually Pledged):  Digits

1. Write a function "digitList[]" that takes a positive integer amd returns a list of its digits; for example, "digitList[96327]" returns "{9,6,3,2,7}".  Of course, don't use the Mathematica command "IntegerDigits[]".  Also, don't use any string functions.  Hint:  how can you get 9632 from 96327?  (Hint: use Mathematica's Mod[] and Quotient[] functions.)

Quotient[96327, 10]

Mod[9, 10]

digitList[n_Integer, accum_List: {}] := 
If[
        n == {}, "Integer Please"], 
If[n > 0, 
      digitList[
        Quotient[n, 10]]], 
If[n

digitList[1234]

Part B (Individually Pledged or Pledged with One Partner):  Sorting and Delivering

Quicksort: attachLists[] & pivot[]

2. Write a function "attachLists[]" which takes two lists and returns their concatenation.  For instance, attachLists[{"m","a","d"},{"d","o","g"}] returns {"m","a","d","d","o","g"}.  

Of course, don't use the Mathematica function Join[].  The only Mathematica supplied List manipulating functions you may use are First[], Rest[], Append[] and Prepend[].  (Use recursion.)

?Rest

Clear[attachList]
attachList[n_List, 
          x_List] := 
Which[
True, 
          attachList[First[n], 
            Append[First[n], Rest[x]]], 
True, 
          attachList[First[n], 
            Append[Rest[n], First[x]]], 
];

attachList[{1, 2, 3}, {4, 5, 6}]

?x

3. Complete the supplied definition for  "pivot[]".  pivot[x, orig] returns a pair of lists, {s, t}, where s is the list of those items in orig which are less than x (via OrderedQ) and t is the list of those items in orig which are greater than or equal to x.  For example, pivot[3, {5,2,3,1,4}] returns {{2,1},{5,3,4}}.

pivot[x_, orig_List, less_List:{},  more_List:{}] := 
  Which[
    orig == {}, 
      {less, more}, 
    OrderedQ[{x, First[orig]}], 
      pivot[
        x,
        (* you fill in the other 3 arguments *)
        ], 
    True, 
      pivot[
        x,
        (* you fill in the other 3 arguments *)
        ] 
  ];

Remark.  "pivot[]" and "attachLists[]" can be used  to write a sorting function following a version of the "quicksort" algorithm invented in 1960 by C. A. R. "Tony" Hoare of Great Britain.  [Hoare, "Quicksort", Computer Journal 5(1), 1962, 10-15]  We call this function "hsort[]" after Mr. Hoare.

Clear[hsort];

hsort::usage="hsort[s] returns a copy of list s, rearranged in ascending order";

hsort[s_List]:=
  If[
    s=={},
    {},
    Module[
      {smaller, bigger, frst = First[s]},
      {smaller, bigger} = pivot[frst, Rest[s]];
      attachLists[
        Append[hsort[smaller], frst],
        hsort[bigger]]
    ]
  ];

(* testing *)
hsort[{"m","a","d","d","o","g"}]
(* ... should return {"a","d","d","g","m","o"} *)

Radioactive Waste Delivery: minExposure[]

4. Your job is to drop off barrels of radioactive waste on a long straight stretch of desert highway.  You can survive exposure to 50 barrel-hours of radiation, i.e., 50 hours exposed to 1 barrel, 25 to two barrels, and so on.  You begin with 20 barrels on your truck, and you will need to reach 4 delivery sites, as follows:

      Site A is one hour to the west and requires 9 barrels.
      Site B is two hours to the west and requires 1 barrel.
      Site C is one hour to the east and requires 8 barrels.
      Site D is two hours to the east and requires 2 barrels.

Determine the route.  Draw a diagram and work the example by hand!

Now what we really want is a program to solve any such similar problem.  Let's say that a position pair is a pair {x,y} where x represents some number of hours to the east (which may be zero, or even negative for points west) and y represents a number of barrels.  Our function will have three arguments:  a list of position pairs to the west, in order from farthest to closest (representing sites which need barrels), a position pair which represents the location of the truck and its load, and a list of position pairs to the east, in order from closest to farthest (representing sites which need barrels).  Hence for the above example we would give our function the arguments "{{-2,1},{-1,9}}, {0,20}, {{1,8},{2,2}}".  Let's consider this collection a state.  

In making various choices of paths to take, the state changes.   For instance, if we moved one place west (and deposited the barrels), the new state would be "{{-2,1}}, {-1,11}, {{1,8},{2,2}}" and we would have been exposed to 20 barrel-hours of radioactivity.  We might move next west another place, reaching state "{}, {-2,10}, {{1,8},{2,2}}" and costing an additional 11 barrel-hours.  Instead, we might move east two places, reaching state "{{-2,1}}, {1,3}, {{2,2}}" and costing an additional 22 barrel-hours. 

Use recursion to define a function "minExposure[]" that takes a system state (3 lists, as above) and returns the total exposure (in barrel-hours) of the best route that will complete all deliveries.  

In the above example, "minExposure[{{-2,1},{-1,9}},{0,20},{{1,8},{2,2}}]" returns 49.  For full credit, use dynamic programming or tail recursion to speed up your program.