Re: programming competition

*To*: mathgroup at smc.vnet.net*Subject*: [mg4890] Re: programming competition*From*: espen.haslund at fys.uio.no (Espen Haslund)*Date*: Fri, 4 Oct 1996 00:17:31 -0400*Organization*: Universitet i Oslo*Sender*: owner-wri-mathgroup at wolfram.com

In article <52664j$8dh at dragonfly.wolfram.com>, xah at best.com says... > >This is a programming problem I recently encountered. The problem has the >attraction of being a programming competition type. I post the problem and my >solution here and hope someone will enjoy and maybe come out with other solutions. > >Problem: >Suppose you have a ordered list {p1, p2, ... , pn} where points has the form >{x,y}. You want to modify the list so any neighboring points will have a distance >less or equal to a given value maxLength. You do this by adding points in between >points. For example, suppose p3 and p4 has length greater than maxLength. Your new >list should then be >{p1, p2, p3, newP1, newP2,..., newPm, p4, p5, ... , pn} where >newP1, ...newPm lies on the line p3 p4. > > >linearInterpolate::usage = " >linearInterpolate[{p1,p2,...}, maxLength ] returns >{P1,P2,...} such that the length between neighboring points >P[i], P[i+1] is less or equal to maxLength. >Newly created points lies on a line between old points"; > Hi, Xah: I want to enter two functions to your competition. As pointed out by Bob Hall your function gives the points in a different order than what you specify (I guess this is not important to your applications). However I do not encounter the divide by zero problem mentioned by Bob Hall. (can it be machine dependent ??) My first entry is a straight forward Do loop approach. All the clever stuff in it, is stolen from you. Also, thanks a lot to Daniel Lichtblau for his resent informative article. linearInterpolateEH1[ li_List, maxLength_ ]:= Module[{res={}, p1, p2, n}, Do[ {p1, p2} = li[[{i, i+1}]]; n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1]; res = {res,Table[p1+(p2-p1)j,{j,0,1-.5/n,1./n}]}, {i, 1, Length[li]-1}]; Partition[Flatten[{res, Last[li]}],2] ] My second entry is basically the same thing with the Do loop replaced with a Table. This makes it slightly more compact and faster, but in my opinion it is more difficult to read and debug. linearInterpolateEH2[ li_List, maxLength_ ]:= Module[{p1, p2, n}, Append[Join @@ Table[{p1, p2} = li[[{i, i+1}]]; n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1]; Table[p1+(p2-p1)j,{j,0,1-.5/n,1./n}], {i,1,Length[li]-1}], Last[li] ] ] Bellow are some timings where I also quote Bob Halls solution, "insertPoints". I think my functions are of linear order in both length (li) and resolution (1/maxLength). I suspect yours to be of second order in the length. Bobs function interpolates with not equidistant points so it's result can not be directly compared with the other results. li = Join[ {{0,0},{1,1}}, Table[{i,1}, {i,1,2,1/5}], {{2,1}, {3,3}} ]; IN: Sort[linearInterpolate[li, 0.2] ] == Sort[linearInterpolateEH1[li, 0.2] ] == Sort[linearInterpolateEH2[li, 0.2] ] OUT: True IN: li = Table[{i,i},{i,100}]; IN: Map[First, { Timing[linearInterpolate[li, 0.1] ], Timing[insertPoints[li, 0.1] ], Timing[linearInterpolateEH1[li, 0.1] ], Timing[linearInterpolateEH2[li, 0.1] ]}] OUT: {6.15 Second, 5.16 Second, 4.95 Second, 4.89 Second} IN: li = Table[{i,i},{i,1000}]; IN: Map[First, { Timing[linearInterpolate[li, 1] ], Timing[insertPoints[li, 1] ], Timing[linearInterpolateEH1[li, 1] ], Timing[linearInterpolateEH2[li, 1] ]}] OUT: {39.61 Second, 11.04 Second, 13.07 Second, 12.8 Second} Greetings -Espen ==== [MESSAGE SEPARATOR] ====