newlispfanclub.alh.net

Posted: **Tue Sep 19, 2006 7:37 pm**

So, I've successfully written my first newLISP routine (it's short -- does it qualify as a program??) Hooray!

Coming from a background of HyperTalk, I'm pretty sure I speak newLISP with a terrible accent. Here's the code I wrote, please tell me the write way to do it. Feel free to bash away...

For those who are interested, the problem description is posted in my other thread: Newbie looking for guidance. Briefly, the below generates a random list for both a warden and his prisoners, representing boxes the warden has set up with the prisoners' names in them. The prisoners' goal is to have all of them independently find their names within a certain number of tries. The code below uses a strategy that maximizes the prisoners' chances of success, and reports whether the method would have succeeded or not.

The equivalent code in Revolution (a HyperTalk variant) can also be found in the other thread: roughly 20 lines of code there becomes roughly 14 of the lines below.

Code: Select all

#choose how many prisoners, and the measure of success
(set 'prisonerCount 100 'prisonerGoal 90)

#set up random lists for the warden and the prisoners
(set 'warden (randomize (sequence 0 (- prisonerCount 1)))
      'prisoners (randomize (sequence 0 (- prisonerCount 1))))

#initialize an array that will store how the two lists map to each other
(set 'prisonerArray (array prisonerCount))

#populate the array with entries.
#the index is the number from the prisoners' list
#the value is the number from the warden's list
(map (fn (x y) (nth-set (prisonerArray x) y)) prisoners warden)

#initialize the results lists
(set 'loopList '() 'prisonerDoneList (array prisonerCount))

#for each prisoner entry
(dolist (i prisoners)

#if the prisoner has already been included in a list, go next
     (until (prisonerDoneList i)

#mark the prisoner as done 
         (nth-set (prisonerDoneList i) 1)

#find what is in the prisoner's box, 
#and start a list with the prisoner
(set 'x (prisonerArray i) 'oneLoop (list i))

#repeat until we find a loop
         (until (= x i)

#put the new box at the end of the list
                (push x oneLoop -1)

#mark the new prisoner/box as done
                (nth-set (prisonerDoneList x) 1)

#move on to the next box in the loop
                (set 'x (prisonerArray x)))

#when we have a complete loop,
#add it to the list of loops
         (push oneLoop loopList -1)))

#create a sorted list with the lengths of the loops
#any way to reverse sort this?
(set 'loopCount (sort(map length loopList)))
         
#print the results
(println warden)
(println prisoners)
(println loopList)
(println loopCount)
(println (if (> (last loopCount) prisonerGoal) 
             "BOO -- The prisoners LOSE!" 
             "HOORAY -- The prisoners WIN!"))

Posted: **Tue Sep 19, 2006 9:42 pm**

Today, we all talk funny because it be September 19, "Talk Like A Pirate Day".
Arrr!

Now THAT be a proper item for this scurvy NEWS forum. Harrr!

Posted: **Wed Sep 20, 2006 7:54 am**

gcanyon wrote:

Code: Select all

#any way to reverse sort this?
(set 'loopCount (sort(map length loopList)))

You can reverse sort using a comparison function:

Code: Select all

(sort (map length loopList) >)

As for the rest - we're a tolerant bunch, and if it works for you, cool! newLISP is flexible enough to allow you to write how you like, to some extent, and to use any sort of formatting and commenting you prefer. There isn't a right way...! (Although there sometimes is a faster way. And sometimes a more efficient way...)

Posted: **Wed Sep 20, 2006 2:17 pm**

cormullion wrote:
gcanyon wrote:
Code: Select all
#any way to reverse sort this?
(set 'loopCount (sort(map length loopList)))
You can reverse sort using a comparison function:
Code: Select all
(sort (map length loopList) >)
As for the rest - we're a tolerant bunch, and if it works for you, cool! newLISP is flexible enough to allow you to write how you like, to some extent, and to use any sort of formatting and commenting you prefer. There isn't a right way...! (Although there sometimes is a faster way. And sometimes a more efficient way...)

Thanks for the sort help. I knew there had to be a way to use a comparison sort.

Is there a better way to do an if than this:

#if the prisoner has already been included in a list, go next
(until (prisonerDoneList i)

Posted: **Wed Sep 20, 2006 3:09 pm**

gcanyon wrote:Is there a better way to do an if than this:

#if the prisoner has already been included in a list, go next
(until (prisonerDoneList i)

There's 'if' and 'unless', 'while' and 'until', 'do-while' and 'do-until'. Also, 'for', 'dolist' and 'dotimes' allow escape routes (tests that can let you quit before the next loop iteration). Then there's 'and', 'or', and 'begin'. And you could write a macro to get exactly the syntax you want.

So there probably is!

I'm not sure which one you need here, though. I'm not too sure why you need to mark each prisoner as done - the loops can be found just by iterating through the prisoner numbers in numerical order, can't they?

Posted: **Wed Sep 20, 2006 3:51 pm**

cormullion wrote:
gcanyon wrote:Is there a better way to do an if than this:

#if the prisoner has already been included in a list, go next
(until (prisonerDoneList i)
(good suggestions snipped)

I'm not sure which one you need here, though. I'm not too sure why you need to mark each prisoner as done - the loops can be found just by iterating through the prisoner numbers in numerical order, can't they?

I only want each loop once. If there were a loop that went 0 3 9 1 then going through all the prisoners would find it four times:

0 3 9 1
1 0 3 9
3 9 1 0
9 1 0 3

Someone (you, I think?) suggested sorting the loops and getting unique on them to have only one example of each list. That solves the problem, but I figured it was better to not recalculate each list a bunch of times, especially in the real problem (100 prisoners) where a loop might be 90 prisoners long.

Also, at least at first, I was interested in what the loops actually were, to make sure that my code was properly capturing them. Therefore I wanted to see them in loop order, not in sorted order, so I could trace them through by hand.

Of course, if speed were really the issue, I wouldn't store the lists at all. I'd just look for whether one went past the length limit, and then bail immediately with a failure for the prisoners.

thanks!

geoff

Posted: **Wed Sep 20, 2006 3:54 pm**

cormullion wrote:As for the rest - we're a tolerant bunch, and if it works for you, cool! newLISP is flexible enough to allow you to write how you like, to some extent, and to use any sort of formatting and commenting you prefer. There isn't a right way...! (Although there sometimes is a faster way. And sometimes a more efficient way...)

I meant to add before -- I'm specifically learning (new)LISP because I'm interested in functional languages and macros in particular. So I definitely don't want to make newLISP bend to my will. Rather I want to learn to bend my mind to newLISP's style.

Posted: **Wed Sep 20, 2006 4:16 pm**

Yes, it's always going to be an interesting trade-off between doing things in code that are better but longer/more complicated, and doing things that are uglier but quicker and simpler.

The added code for eliminating duplicate 'loops' in newLISP could take as long as the original effort involved in finding them...

I tidied up the short and ugly version i threw out yesterday to see how slow it was - it managed 100 prisoners in 20-30 millseconds and I'm not sitting at a quick machine, so there's obviously plenty of scope to do things properly!

Code: Select all

(set 'start (time-of-day))
(seed (date-value))
(set 'prisoner-count 100 'goal 90)
(set 'prisoners (randomize (sequence 1 prisoner-count)))
(set 'warden (randomize (sequence 1 prisoner-count)))

(set 'pw (map list prisoners warden))

(for (p 1 (length pw)) 
	(set 'w (lookup p pw) 'a-loop (list p))
	(until (= p w)
 		(push w a-loop -1) 
		(set 'w (lookup w pw))) 
		(push (sort a-loop) loops )) 

(if (> (length (first (sort (unique loops) (fn (x y) (> (length x) (length y)))))) goal)
	(print "prisoners lose: ")
	(print "prisoners win: "))
	
(println "goal " goal ", loop lengths: " (map length (unique loops)) ", in " (- (time-of-day) start) " ms")

newlispfanclub.alh.net

Tell me how I talk funny

Tell me how I talk funny

Re: Tell me how I talk funny

Re: Tell me how I talk funny

Re: Tell me how I talk funny

Re: Tell me how I talk funny

Re: Tell me how I talk funny