From: rusty craine
Subject: Lisp - an invitation is show your stuff
Date: 
Message-ID: <742355$bkm$1@excalibur.flash.net>
This semester I've been filling in at a local communtiy college teaching a
night course in trig.  Because of my experience in TSO, ISPF and  REXX in
MVS the head of their CS department  ask if I would give a couple of
presentation for one of his class over these main frame tools (they don't
have a 390 environment).  Over lunch I mentioned lisp and this news group,
esp the lisp's "bad name".  I mentioned that this group was at least some of
the best lisp minds around and ya could learn alot from just reading the
news group.  A "sine qua non" smile crossed his face....uh oh.  He has given
his advanced programming group a problem to solve collectively  over the
semester.

The problem:  There are 10 disk files of random binary numbers (8 bit
integers)  that can be represented as a 500 by 500 matrix.  The numbers are
all random except for one integer that when identified and mapped as a
single line in the 500 x 500 martrix will form (approx) the  pattern of a
circle, rectangle, square, triangle or trapezoid of unspecified size (to the
solving program, i'm sure he know what is it would be).  Five of the files
the mapping integer will only appear in the patterning mapping the object's
outline .  Five of the files the mapping integer will appear in the random
pattern as generated by a random number  routine as well as in the pattern
outline (they were not excluded to just the line forming the pattern).  The
professor's challenge was.....write a program  to produce the "test" files.
He has written one in python and i think he said perl.  Oh and if you want
to be the solver that might be interesting.

The classes can write the solver in the language of their choice as long as
he can run their program on  SCO, win 95 or dos without purchasing any
software.  (seems to me the whole bunch leans heavily to unix-ish - and
perl, python and C).

I've made good progress on the "makers" (not to tough), although some of the
functions are not generalized yet.  I just thought of the whole thing in
cartesian coordinates and use functions to pre-mapped the points in a list,
then compare each write coordinates to my list to see if it is a mapping
integer.  So the first byte written is (-250,250) , next byte -(249,250),
....(250,250) then next matrix line (-250,249).  (ya got a better way?)

Still thinking about the solver.  any thoughts on the "solver"?

(circle-maker 100)         ;;; 100 radius in bytes

(square-maker 250)      ;;; length of a sides in bytes

(triangle-maker 250)     ;;; equilateral sides in bytes

(rectangle-maker 250 100)  ;;;width and height in bytes

(trapeziod-maker 200 100 60)  ;;;width, height[in bytes], left upper
angle[in degrees]

Rusty

Email address  is ········@flash.net.  Under some situation the "a" and the
"l" in flash are reversed in the header.
Rusty Craine

From: Raffael Cavallaro
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <raffael-0112982122540001@raffaele.ne.mediaone.net>
In article <············@excalibur.flash.net>, "rusty craine"
<········@flash.net> wrote:

>Still thinking about the solver.  any thoughts on the "solver"?

Well, if this doesn't have to be done completely programatically, I would
map every integer to a unique color, and plot the 500 x 500 matrix as a
bitmap of the same dimensions. The figures (circle, trapezoid, etc.)
should be easily visible as single color figures among the random color
noise. When dealing with pattern recognition, let the human user do what
s/he's clearly superior to a computer at.

Raf

-- 
Raffael Cavallaro
From: Sunil Mishra
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <efy1zmjje0c.fsf@spanker.cc.gatech.edu>
Hmmm, this gives me an idea. Thinking in terms of vision, probably the best
thing to do would be to attack the outlined figures piecemeal. Find all
lines (diagonals included) of some length, say 4. (You might of course miss
a circle if it is of radius 5 or something in the 500x500 matrix.) Then,
look at the various patterns, and construct a histogram of numbers that
form the various segments. Start with the number that generates the most
segments, and figure out if they fit the model of some pattern the program
knows of.

This might be made marginally more efficient if you also introduced growing
a segment to the largest size possible, as long as it is of greater length
than some threshold, say 4. This would make the task of recognizing
rectilinears somewhat easier.

Sunil

·······@mediaone.net (Raffael Cavallaro) writes:

> In article <············@excalibur.flash.net>, "rusty craine"
> <········@flash.net> wrote:
> 
> >Still thinking about the solver.  any thoughts on the "solver"?
> 
> Well, if this doesn't have to be done completely programatically, I would
> map every integer to a unique color, and plot the 500 x 500 matrix as a
> bitmap of the same dimensions. The figures (circle, trapezoid, etc.)
> should be easily visible as single color figures among the random color
> noise. When dealing with pattern recognition, let the human user do what
> s/he's clearly superior to a computer at.
> 
> Raf
> 
> -- 
> Raffael Cavallaro
From: Paul Wallich
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <pw-0212980939310001@pw.dialup.access.net>
In article <···············@spanker.cc.gatech.edu>, Sunil Mishra
<·······@spanker.cc.gatech.edu> wrote:

>Hmmm, this gives me an idea. Thinking in terms of vision, probably the best
>thing to do would be to attack the outlined figures piecemeal. Find all
>lines (diagonals included) of some length, say 4. (You might of course miss
>a circle if it is of radius 5 or something in the 500x500 matrix.) Then,
>look at the various patterns, and construct a histogram of numbers that
>form the various segments. Start with the number that generates the most
>segments, and figure out if they fit the model of some pattern the program
>knows of.
>
>This might be made marginally more efficient if you also introduced growing
>a segment to the largest size possible, as long as it is of greater length
>than some threshold, say 4. This would make the task of recognizing
>rectilinears somewhat easier.


Since all of these figures are closed you're going to have pairs of
numbers that share x-coordinates, so you can look for repeats by
mapping in y, then check to see if you get the same repeated integer
in other columns, then apply some kind of shape-recognizer. In some
cases, you won't have pairs, you'll have triplets, quads or runs, but
those are easy to recognize. (Same thing goes for y-coord, so you
could do it that direction too.) Actually, it's a little simpler, since
once you get a pair/whatever you can do nearest-neighbor searches in
the array...

Say a function that produces a list of candidates for the nearest-neighbor
searcher to work on (I'm looking to do this prettily, not necessarily
non-consingly, but that's old style habits) that in turn spits out vertices
(aka changes in direction) or things like them for a recognizer...

I wonder what the odds are of finding a figure in the noise -- probably
pretty large for small enough "figures".

paul
From: Gareth McCaughan
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <86ogpmed34.fsf@g.pet.cam.ac.uk>
Rusty Craine wrote:

> The problem:  There are 10 disk files of random binary numbers (8 bit
> integers)  that can be represented as a 500 by 500 matrix.  The numbers are
> all random except for one integer that when identified and mapped as a
> single line in the 500 x 500 martrix will form (approx) the  pattern of a
> circle, rectangle, square, triangle or trapezoid of unspecified size (to the
> solving program, i'm sure he know what is it would be).  Five of the files
> the mapping integer will only appear in the patterning mapping the object's
> outline .  Five of the files the mapping integer will appear in the random
> pattern as generated by a random number  routine as well as in the pattern
> outline (they were not excluded to just the line forming the pattern).  The
> professor's challenge was.....write a program  to produce the "test" files.
> He has written one in python and i think he said perl.  Oh and if you want
> to be the solver that might be interesting.

I would cheat. :-) Specifically, I wouldn't try to recognise the
particular shapes as such. Consider the following approaches to the
first case (special "colour" appears only as outline[1] of shape):

1. Look for a "colour" that doesn't appear at all over a large
   area: say about 100x100 pixels. (To do this without excessive pain,
   chop the 500x500 grid into 100 50x50 blocks, and record for each
   block all the colours that aren't represented within that block.
   Now look for a colour that isn't represented in several neighbouring
   blocks.)

   Your outline can't possibly meet more than 80 of these blocks, and
   probably meets far fewer. If the other colours are genuinely allocated
   at random, the chances of any of the others having this feature are
   very small: we're something like 6 standard deviations away from
   the mean.

2. Look for large (say, at least 20) connected regions of a single
   colour. The probability of a "random" colour having any neighbour
   of the same colour is about 0.03, so it's hugely unlikely that
   any "random" colour will be part of a group of size 20. You can
   search for such groups using a simple recursive thing on each
   pixel; note that most such searches will terminate immediately.

   If you don't find a large connected region, the conclusion is that
   the shape you're looking for is very small. Specifically, it must
   have fewer than 20 pixels. So just look for a "colour" that occurs
   fewer than 20 times.

What about the second case? Well, the second approach will still work
just fine, unless the shape is very small. Even then, we can have a
fair chance of success by looking for the largest available connected
group.


So here's some (somewhat untested) code. The function FIND-SHAPE
takes a single argument: a 2-dimensional array of numbers from
0 to 255. BUT, please note, it needs to be *able* to include the
number 256 too, because we use that for magical purposes. It returns
two values: what we hope is the number of the required colour,
and the location of a pixel that should be part of the desired shape.

(defun find-shape (a)
  (declare (type (simple-array (integer 0 256) (500 500)) a))
  (let ((counts (make-array '(256) :element-type (integer 0 250000)
                                   :initial-element 0))
        (best-colour 0)
        (best-count 0)
        (best-location '(0 0)))
    (dotimes (i 500)
      (dotimes (j 500)
        (let ((colour (aref i j)))
          (unless (= colour 256)
            (let ((n (count-connected a i j colour 20)))
              (when (>= n 20)
                (return-from find-shape (values colour (list i j))))
              (when (> n best-count)
                (setq best-colour colour
                      best-count n
                      best-location (list i j))))
            (incf (aref counts colour))))))
    ;; If we get here, we haven't found a large component
    ;; but we *have* sussed out the counts.
    (dotimes (colour 256)
      (when (< (aref counts colour) 20)
        (return-from find-shape colour)))
    ;; If we get here, we have no large component and no small count.
    ;; Presumably we're in the very random case and the shape is small.
    ;; Return the colour of the biggest component we found.
    (values best-colour best-location)))

The COUNT-CONNECTED function returns the size of the largest connected
group in a particular place, except that if the group is large it
doesn't bother exploring it fully. To avoid embarrassing loops,
as we count each pixel we replace it with colour 256. This ensures
that we will never look twice at any pixel.

(defun count-connected (a i j colour upper-limit)
  (declare (type (simple-array (integer 0 256) (500 500)) a))
  (declare (type (integer 0 255) colour))
  (setf (aref a i j) 256)
  (let ((n 1))
    (loop for di in '(-1 -1 -1  0  0 +1 +1 +1)
          for dj in '(-1  0 +1 -1 +1 -1  0 +1) do
      (let ((ii (- i di))
            (jj (- j dj)))
        (when (and (<= 0 ii 499) (<= 0 jj 499))
          (let ((new-colour (aref a ii jj)))
            (when (= colour new-colour)
              (when (>= (incf n (count-connected a ii jj new-colour
                                                 (- upper-limit n)))
                        upper-limit)
                (return-from count-connected n)))))))
    n))


Of course, all this would be less useful if we were required to say
which sort of shape we were looking at. (But, even then, I think
this sort of thing would be a good first pass; first find what pixels
the shape occupies, and *then* try to decide what shape it is.)


On my P166-ish box, using CMUCL, I've just tried this on an image
of the second type (special colour not excluded from random pixels)
containing a triangle. It took about 1/4 of a second.


[1] I'm assuming outline. Otherwise it's even easier.

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: Barry Margolin
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <z6e92.57$5M.12307@burlma1-snr1.gtei.net>
In article <············@excalibur.flash.net>,
rusty craine <········@flash.net> wrote:
>The problem:  There are 10 disk files of random binary numbers (8 bit
>integers)  that can be represented as a 500 by 500 matrix.  The numbers are
>all random except for one integer that when identified and mapped as a
>single line in the 500 x 500 martrix will form (approx) the  pattern of a
>circle, rectangle, square, triangle or trapezoid of unspecified size (to the
>solving program, i'm sure he know what is it would be).  Five of the files
>the mapping integer will only appear in the patterning mapping the object's
>outline .  Five of the files the mapping integer will appear in the random
>pattern as generated by a random number  routine as well as in the pattern
>outline (they were not excluded to just the line forming the pattern).  The
>professor's challenge was.....write a program  to produce the "test" files.
>He has written one in python and i think he said perl.  Oh and if you want
>to be the solver that might be interesting.

I would compute a histogram of counts of every value in a file.  Assuming a
good random number generator, the value that's used to form the pattern
should would be expected to have a higher frequency than other values.

Of course, a random sequence will occasionally have a series of repeats
(they're just as likely as any other particular sequence).  If a particular
file happens to have been produced from a very unlucky section of the
random sequence, there could be enough repeats that this test would fail.
But, for that matter, it would even be possible for the RNG to generate
enough repeats that real geometric shapes would be produced; there would be
no way to distinguish them from the one that was created intentionally by
the maker.

Others have suggested looking for connected patterns.  Another technique,
which is probably closer to a simple vision implementation, might be to
employ FFT.  However, Fourier Transforms are mainly useful when you
normally have smooth or slowly-transitioning values on a surface, separated
by sudden jumps at boundaries.  Since the surfaces in this case are random
values, I suspect it might be necessary to perform two filtering passes.
The first transform should result in very high frequency values for all the
random locations; these should be filtered out, and then a second transform
should find the pattern.

However, it's been a long time since I studied Fourier Transforms, and I
wasn't very good at them even then, so I may not know what I'm talking
about.  But it sounds clever....

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: ·········@computasoft.com
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <745rrt$ksg$1@nnrp1.dejanews.com>
In article <············@excalibur.flash.net>,
rusty craine <········@flash.net> wrote:
>The problem:  There are 10 disk files of random binary numbers (8 bit
>integers)  that can be represented as a 500 by 500 matrix.  The numbers are
>all random except for one integer that when identified and mapped as a
>single line in the 500 x 500 martrix will form (approx) the  pattern of a
>circle, rectangle, square, triangle or trapezoid of unspecified size (to the
>solving program, i'm sure he know what is it would be).  Five of the files
>the mapping integer will only appear in the patterning mapping the object's
>outline .  Five of the files the mapping integer will appear in the random
>pattern as generated by a random number  routine as well as in the pattern
>outline (they were not excluded to just the line forming the pattern).  The
>professor's challenge was.....write a program  to produce the "test" files.
>He has written one in python and i think he said perl.  Oh and if you want
>to be the solver that might be interesting.

I have to much to do to be thinking about this kinda thing, but...

I'm sure you could write a recursive algorithm, similar to flood fill if my
memory serves me correctly, that would move through every single point in
the array once in roughly the following order, assuming you can move in that
direction and you aren't at a boundary.

    8 1 2
    7 X 3
    6 5 4

You start at point x, and move to point 1 and/or 2 and/or 3 etc if the value
at that position is the same as point x and you haven't already visited the
point. while you are doing this you could how many steps you have made in this
current run of same values. Your terminating condition should be no more
unvisited points of the same value available, at which point you store the
value and the length of the run.

Assuming I've got this right the highest run length should give you the colour
value of the shape.

All that leaves is the shape detection ;-)

Barry

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: rusty craine
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <74cjc8$6gq$1@excalibur.flash.net>
rusty craine wrote in message <············@excalibur.flash.net>...

>Still thinking about the solver.  any thoughts on the "solver"?
>
Atfer hearing some of the students discussions, it was clear that some of
the files were designed not to be solved easily....the gaunlet was dropped.
Lisp may not do it the fastest but I was determined to solve all the files.

So....I read each byte in, caluated the x y cooridinates and wrote it out to
a file

; calcualte x y coordinated
(defun (x y)
  (if (equal x 250)                   ; end of this X vector
      (setq x -250 y (- y 1))    ;  so set X back to first read postion and
drop down one Y
       (setq x (+ x 1))))             ; else inc X

; write the line to tempxy.rcc
(defun file-line (pbyte x y)
  (write-line (pack* pbyte x y "~")))  ; mulisp doesn't use ~ so when i read
the file back
                                                           ; i'll set ~ to
the break character
[...more stuff...]


yep all 250,000 of them suckers...now.   from mulisp i call optsort to sort
the file by pbyte and x cooridinate.  read the file back in break character
at a time.  upack the string, and start building a sublist in a list
[outside list repersents pbyte] with the X cooridinate the car and y
cooridinates subsequent appends to the cdr of the sublist.  when the X
cooridinate changes from the previous read, start a new sublist continue
then  till the pbyte read doesn't equal the previous pbyte. Now we got a
list of sublist with the car of the sublist the X coordindate  and the cdr
all the y's [little math and you can tell if the y's are at reagular
intervals the length, etc].

I check the len of the cdr of the first sublist if it's greater than 1 I
check the Y's for a regular pattern that is next to each other, every other
one,  ever third one etc.  If these test are true, I  calculate the length
of this "side".  Now get the last cdr of the outside list do the same thing
to it.  If it test true we got a four sided figure, if it only has one point
we got a triangle.  Well I won't put you thru the whole process but all the
test are very rude, with little great logic.  Testing for figures within
figures was fairly tedious  but not to compilcated. I used the same
positional type logic, only a lot of it.

Well come to find out there were figures in figures but they were of two
different bytes.    There some files that had two figues that did not over
lap but were of the same character. [these took a lot of very ugly testing
in my program]

The outcome:  I did define all the files and lisp was not the slowest one to
do so.  there was a VB team, a java team, a perl team, a C team and a team
of one [maurice ho, been in the states 3 years] that wrote his in qbasic.
Mr Ho's was at least a work of art, he identifed all the file correctly,
displayed the bit map of the file on the screen [as was discusssed in here],
gave feed back on a window about the progress his program was making and
what it was doing.  The VB and Java team really lacked talent, the perl team
bailed out of their prgram when the figures were identified of one type
bytes and didn't continue to process the rest of the file. They used an
algorithm somewhat like Gearth suggested. Pretty talented group.  The C team
had the talent and identifed all figures but the program was the pretty
unfriendly [kinda real unix-ish :)] and a little slow. On their behalf they
used a sort also but they coded it themselves.  That might have been some of
the reason they were a little slow.  Qbasic was the slowest to identify all
the files but Mr Ho impressed me enough that I have offered him a part time
job.  I think he'll be writting compilers someday....really bright fellow.
He used several very sophisticated math routines to try to predict locations
of other points, if they were there he had a hit.   I haven't had time to
understand all his math yet but pretty clever at first glance.

think it over before ya go up against students.  Some of them got the time
and the talent to really turn out some good code.  i was overall impressed.
Rusty
From: Barry Margolin
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <oDka2.93$9w2.13010@burlma1-snr1.gtei.net>
In article <············@excalibur.flash.net>,
rusty craine <········@flash.net> wrote:
>So....I read each byte in, caluated the x y cooridinates and wrote it out to
>a file
>
>; calcualte x y coordinated
>(defun (x y)
>  (if (equal x 250)                   ; end of this X vector
>      (setq x -250 y (- y 1))    ;  so set X back to first read postion and
>drop down one Y
>       (setq x (+ x 1))))             ; else inc X

Is this function supposed to make sense?  It doesn't have a name, it has no
side effects, it sets local variables that it never uses again, and the
return value doesn't seem to be very useful (if x is 250 it returns y-1,
otherwise it returns x+1).  Furthermore, your other function doesn't seem
to call it (whatever its name is, file-line never calls a function that
takes two numeric arguments).  I suspect what was intended was something
like:

(defun next-coordinate (x y)
  (if (= x 250)
      (setq x -250 y (- y 1))
      (incf x))
  (values x y))

You call this with the current x-y coordinates, and it returns the next one
in the scan, with x's increasing and y's decreasing.

>; write the line to tempxy.rcc
>(defun file-line (pbyte x y)
>  (write-line (pack* pbyte x y "~")))  ; mulisp doesn't use ~ so when i read
>the file back
>                                                           ; i'll set ~ to
>the break character

What's pack*?

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: rusty craine
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <74cn93$ee7$1@excalibur.flash.net>
Barry Margolin wrote in message ...
>In article <············@excalibur.flash.net>,
>rusty craine <········@flash.net> wrote:
>>So....I read each byte in, caluated the x y cooridinates and wrote it out
to
>>a file
>>
>>; calcualte x y coordinated
>>(defun (x y)

>Is this function supposed to make sense?  It doesn't have a name, it has no
>side effects, it sets local variables that it never uses again, and the
>return value doesn't seem to be very useful (if x is 250 it returns y-1,
>otherwise it returns x+1).  Furthermore, your other function doesn't seem
>to call it (whatever its name is, file-line never calls a function that
>takes two numeric arguments).  I suspect what was intended was something
>like:
>
>(defun next-coordinate (x y)
>  (if (= x 250)
>      (setq x -250 y (- y 1))
>      (incf x))
>  (values x y))
>
>You call this with the current x-y coordinates, and it returns the next one
>in the scan, with x's increasing and y's decreasing.


Yes, thank you.  It does not make much sense.   Neither of these were really
functions I used,  both were inline code.  I was just illustrating what was
happening,  but now see i did a very poor job of it.  Ineed your function
does illustrate the process.

>>  (write-line (pack* pbyte x y "~")))  ; mulisp doesn't use ~ so when i
read
>
>What's pack*?


Ah..oh didn't realize common lisp didn't have it.  in muLisp (PACK  list)
and (PACK* atom1 atom2 atom3,,,atomN) . PACK returns the symbol whose name
consists of the concatenated print names of the atoms in list.  PACK* is
merely a no-spread version of PACK i.e. it takes an arbitrary number of
atoms rather than a list of atoms.  Here is was showing what was going to
sorted in the temp file.

Since I'm a muLipser I don't usually include code snippets, it just causes
confusion.  I must admit it is a great deal more confusing when I don't
proof read my submission carefully and get it wrong.  Dang, Barry if i had
you around all the time, it would make debuggin' much faster. :)

will proof carefully in the future ;->
Sorry
Rusty
>--
>Barry Margolin, ······@bbnplanet.com
>GTE Internetworking, Powered by BBN, Burlington, MA
>*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
>Don't bother cc'ing followups to me.
From: rusty craine
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <74cv4p$ba$1@excalibur.flash.net>
Barry Margolin wrote in message ...
>In article <············@excalibur.flash.net>,
I suspect what was intended was something
>like:
>
>(defun next-coordinate (x y)
>  (if (= x 250)
>      (setq x -250 y (- y 1))
>      (incf x))
>  (values x y))
>
>You call this with the current x-y coordinates, and it returns the next one
>in the scan, with x's increasing and y's decreasing.
>
This brings up a topic I have been giving some thought to.  Some of the
students and CS instructors are now interested in lisp or at least curious
about it because of my participation  in their contest using lisp.  Though
just a snippet, when I compare Barry's code to that I actually used, it is
clear that I should not be a mentor to a lisp interest group.  Especially
when this added to the fact that I like muLisp and going to stick with it as
long as I can buy a machine  that will run it's throw's to a catch :o).  At
any rate the department head has mentioned it and I told him I would have to
see how much time I'd have to give to an interest group.

I think I can write most anything in muLisp so that is not the problem.  The
problem is that the code I write would not meet the muster of this group and
I think that a lisp mentor's code should.  Some of the postings and
signatures point out that some of you guys have had formal training in lisp
and some maybe even be teaching it now,  you guys get any thoughts about my
dilemma, that is -  I hate to pass up an opportunity to introduce lisp to CS
students (and instructors)  and I hate to introduce them to my lisp
programming style (or lack of programming style).   Being a math instructor,
if the student passes my course, I feel that next math instructor they get
will know that the student had a good math instructor for their last class
(call me delusional).  I would expect no less of myself being a lisp
mentor....just not near as prepared.

you mean goto's aren't a good thing
rusty
From: rusty craine
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <74heij$9pp$1@excalibur.flash.net>
Below are the two major logic functions for defining the shape (muLisp).  I
have included a list defining a shape.  The function that is not included
(too long) is a long case statment testing the globals and sre-sampling the
shape list.  Everyone that successful completed the 10 test files was ask to
present a short presentation of the method and code.  Any way I can make
these two function  more presentable?

; Y cooridinate is the car of sublist,
; X coordinates the cdr of sublist
; sqr-in-circ list represtents a square
; within a circle. identifcation of a circle
; becomes more difficult as the byte radius
; becomes < 13.  the circle is becoming an octagon.
;;;
;;;set enviornment
;;;
(load common)
;;;
(setq sqr-in-circ '((8 4 5 6 7 8 9 10)
               (7 3 11)
              (6 2 12)
              (5 1 13)
              (4 0 1 2 3 4 5 6 7 14)
              (3 0 7 14)
              (2 0 7 14)
              (1 0 7 14)
              (0 0 7 14)
              (-1 0 1 2 3 4 5 6 7 14)
              (-2 1 13)
              (-3 1 12)
              (-4 3 12)
              (-5 4 11)
              (-6 5 6 7 8 9 10)))
;;;
;;;
(defun y-orderedp (lst)
;;sets three globals
;;       *y-coor-vectors*
;;          how many y's are there
;;       *y-coor-ordered*
;;          are they eaually spaced down axis
;;       *y-coor-distance*
;;          distance in bytes from top to bottom
  (let (y-lst nil y-diff nil)
    (loop
      ((null lst))
      (push (caar lst) y-lst)
      (setq lst (cdr lst)))
    (dotimes (i (/ (length y-lst) 2))
       (push (abs (- (abs (nth i y-lst))
                     (abs (nth (+ i 1) y-lst)))) y-diff))
     (setq *y-coor-vectors* (length y-lst))
    ;;;note y coor are now in reverse order - pushed on list
    (if (plusp (car y-lst))
          (setq *y-coor-distance*        ;if
             (- (car (last y-lst) (car y-lst))))
          (setq *y-coor-distance*  ;else
             (+ (car (last y-lst)) (abs (car y-lst)) 1)))
    (setq *y-coor-ordered*
       (equal 1 (length (remove-duplicates y-diff))))))
;;;
;;;
(defun x-orderedp (lst)
;;set X's globals for shape for shape id
  (let (x-cnt nil x-diff nil)
  (dotimes (i *y-coor-vectors*)
      (push (length (cdr (nth i lst))) x-cnt))
  ;;check relative size of 1st and last x coor list
  (setq *x-coor-1st-cnt* (car x-cnt))
  (setq *x-coor-1st-last-cnt-diff-pct*
     (* 100 (/ (car x-cnt) (car (last x-cnt)))))
  ;distance of 1st x if it is a run
  (if (and (> *x-coor-1st-cnt* 2)
               (plusp (caar lst)))
             (setq *x-1st-distance*   ;if
               (- (car (last (cdar lst))) (cadar lst)))
             (setq *x-1st-distance*   ;else
               (+ (abs (cadar lst) (car (last (cdar lst)))))))
  ;is x growing down y, check max distance of 3ard x coor list
   (if (and (> *x-coor-1st-cnt* 2)
               (plusp (car (nth 3 lst))))
             (setq *x-3ard-distance*   ;if
               (- (car (last (nth 3 lst))) (car (nth 3 lst))))
             (setq *x-3ard-distance*   ;else
               (+ (abs (caar lst) (car (last (car lst)))))))))
;;
Rusty
From: Martti Halminen
Subject: Re: Lisp - an invitation is show your stuff
Date: 
Message-ID: <366D0B14.3B35@dpe.fi>
rusty craine wrote:
> 
> Below are the two major logic functions for defining the shape (muLisp).  I
> have included a list defining a shape.  The function that is not included
> (too long) is a long case statment testing the globals and sre-sampling the
> shape list.  Everyone that successful completed the 10 test files was ask to
> present a short presentation of the method and code.  Any way I can make
> these two function  more presentable?


<snip>
> (defun x-orderedp (lst)
> ;;set X's globals for shape for shape id
>   (let (x-cnt nil x-diff nil)
>   (dotimes (i *y-coor-vectors*)
>       (push (length (cdr (nth i lst))) x-cnt))
>   ;;check relative size of 1st and last x coor list
>   (setq *x-coor-1st-cnt* (car x-cnt))
>   (setq *x-coor-1st-last-cnt-diff-pct*
>      (* 100 (/ (car x-cnt) (car (last x-cnt)))))
>   ;distance of 1st x if it is a run
>   (if (and (> *x-coor-1st-cnt* 2)
>                (plusp (caar lst)))
>              (setq *x-1st-distance*   ;if
>                (- (car (last (cdar lst))) (cadar lst)))
>              (setq *x-1st-distance*   ;else
>                (+ (abs (cadar lst) (car (last (cdar lst)))))))
>   ;is x growing down y, check max distance of 3ard x coor list
>    (if (and (> *x-coor-1st-cnt* 2)
>                (plusp (car (nth 3 lst))))
>              (setq *x-3ard-distance*   ;if
>                (- (car (last (nth 3 lst))) (car (nth 3 lst))))
>              (setq *x-3ard-distance*   ;else
>                (+ (abs (caar lst) (car (last (car lst)))))))))


Some comments (without bothering to thoroughly inspect this stuff):

- I don't know about muLisp, but in CL abs only takes one argument.

- It might be easier if you used some datastructure with named fields
(muLisp ??)

- If you really must use a nested list structure, you could hide a lot
of those list operations inside some accessor functions which were named
after the meaning of the value sought, for example


(defun next-x-coordinate (lst) 
;; or whatever would be a nice name in this context
  (car (last (cdar lst))))

This should make the actual intent of the program somewhat clearer.
Optimally, these functions showing the major logic could be written so
that you couldn't tell what is the datastructure underneath: changing
the lists to something else would only mean changing the definitions of
the access functions.

-- 
________________________________________________________________
    ^.          Martti Halminen
   / \`.        Design Power Europe Oy
  /   \ `.      Tekniikantie 12, FIN-02150 Espoo, Finland
 /\`.  \ |      Tel:+358 9 4354 2306, Fax:+358 9 455 8575
/__\|___\|      ······················@dpe.fi   http://www.dpe.fi