[racket] 27.5.4 Gaussian Elimination

On Nov 22, 2010, at 4:17 PM, Ken Hegeland wrote:

> The problem is 27.5.4 can be found at
> http://htdp.org/2003-09-26/Book/curriculum-Z-H-34.html#node_sec_27.5
> 
> I am still on the beginning of this extended exercise and I am entirely lost. I know how it works but can't get anything even remotely close. I was able to create subtract from 27.5.2, but triangulate eludes me after a few days of thinking. My first thought is to make something that takes either a (listof(listof numbers)), or 3 (listof numbers), and have it output the first part of triangulation.
> 
> So for the lolon of '((2 2 3 10)(2 5 12 31)(4 1 -2 1)) I want to produce an answer of
> '((2 2 3 10)(3 9 21)(-3 -8 -19))
> 
> I feel like applying subtract to first and second in lolon produces (3 9 21), but I am not sure how to make it continue on the rest of the list. I tried (subtract2(subtract(first lolon)(second lolon))), which really doesn't work and it seems obvious to me just from glancing at it.
> 
> I am thinking back to how I did merge sort, create a function that merges 2 lists, apply it to the first and second items in a lolon, then recursively apply it to the rest of the list.
> 
> In subtract2 my final goal is to apply subtract to the first and second item, then recursively apply it to first and rest of the list, but I can't figure out how to get this. 
> 
> I know the real question has to do with applying this over and over to any lists of equal length, until you drop the first position to 0, and maybe I am heading in the wrong direction, but it seems easier to break it into smaller problems. I really want to complete this problem before moving on with the book but I can't find anything that works, everything I think of causes infinite loops and freezes my computer for 10 minutes.
> 
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users


Say you're starting from here: (a rectangle)

> ((2 2  3 10)
>  (2 5 12 31)
>  (4 1 -2  1))

One step -- as described in the book gets you here: 

> ((2  2  3  10)
>  (0  3  9  21)
>  (0 -3 -8 -19))

If you cut the 0s out from row 2 through N, you get closer to the triangle: 

> ((2 2   3  10)
>    (3   9  21)
>    (-3 -8 -19))

This isn't quite a triangle yet. So how do you repeat this process?

Eureka: find a sub-rectangle to which you could apply this trick again. Do so until you're out of naturally chosen sub-rectangles. 

Practically speaking, this means that you subtract the second row -1 times from the last: 

> 
> ((2 2   3  10)
>    (3   9  21)
>        (1   2))

Now you have got a triangle. Of course if the matrix has many more rows you need to repeat this step many more times. 


The good news: Typing in the ideas presented above -- assuming you have internalized Parts I - IV of HtDP -- will take you about as much time as typing the email. Well, perhaps I am slow typist -- Matthias