newlispfanclub.alh.net

Posted: **Mon Sep 18, 2006 4:45 pm**

So let me start by introducing myself: I come from a HyperTalk background mostly, working with HyperCard, SuperCard, and Revolution. I've also worked with FileMaker and 4D, and in the distant past C, Pascal, and way back when BASIC.

I've always been fascinated by LISP, so here I am.

I have several questions:

1. Forgive me for being dense, but I'm having a hard time saving and retrieving source code. I wrote a few lines (referenced below) and I thought I had saved them in much the same way the example files are saved -- drag.lsp for example -- but when I try to reload the file, I get an error:

symbol is protected in function define : (exit)

When I open my saved file in a text editor, I see a bunch of things I didn't type in it. Is there a simple tutorial that walks through creating a simple application, step-by-step?

----------------

2. I'm trying to write a solution to a problem I'm working on as a way of getting started with newLISP. The problem is a puzzle (sorry the description is so long):

A warden says to 100 prisoners, "Next week I'm going to assemble 100 numbered boxes and put your names in them randomly, one to a box. At that point I'll lock you all in solitary (no communication of any sort) and let you into the room with the boxes one by one. Each of you will get to open 90 boxes, hoping to find his own name. Then the boxes will be closed and you will be returned to solitary, so another prisoner can try. If all 100 of you find your own names, you can go free."

Stop reading here if you don't want to know the answer to the puzzle.

By random chance, any prisoner has a 0.9 probability of finding his own name. That means that by random chance with no strategy, 100 prisoners have 0.9^100 = 0.000027 probability of succeeding -- not very good. But there is an answer.

Last chance to stop reading.

The prisoners agree to a random distribution of their names against the 100 boxes before they are moved to solitary. So each prisoner has a number, and knows the numbers of all the other prisoners as well. Let's say my number is 1. When it's my turn to try I open box 1. If it has my name in it, great. Otherwise I look and the name, and using the assignments we previously agreed to, I open _that_ person's number. I repeat this process until either I've opened 90 boxes and failed, or I've succeeded.

Believe it or not, this gives the prisoners about an 85% chance of success. I was stunned by this result. I can explain it if anyone cares. But for now, I just wanted to program a test of this in newLISP. So far I have this:

(define (rsequence x y z) (randomize (sequence x y (if z z 1))))
(setq warden (rsequence 0 99) prisoners (rsequence 0 99))
(set 'prisonerArray (array 100))
(map (fn (x y) (nth-set (prisonerArray x) y)) prisoners warden)

_If_ I understand correctly:

-- The first line gives me random sequences of numbers.
-- The second line sets up the warden's distribution, and the prisoners'.
-- The third line initializes an array of 100 elements. The array will be used to store the number of the next box, by the prisoners' and the warden's sequences, for each of the 100 boxes.
-- The fourth line populates the array with the correct values.

So here are my questions:

2a: Does the above do what I think it does?
2b: How would I go about verifying that? If I just wanted to dump the values of the array at the end, how would I do it?
2c: Is the above a reasonable way to start? Is there a better way?

The array generated by the warden's and the prisoners' distribution of the names into boxes naturally forms loops. Those loops have a length, which is critical to solving the puzzle. If no loop thus generated is longer than 90 elements, then the prisoners win. If the longest loop is greater than 90 elements long, the prisoners lose. So:

2d: My next step is to figure out the loops based on the array. In english that might work out to something like:

-- for each number (X) from 0 to 99
-- if X is already in a loop, skip to the next number
-- using the array, figure out what sequence of numbers the loop starting with X contains.

I have no idea how to code the above. Any suggestions?

Thanks to all,

regards,

Geoff

Posted: **Mon Sep 18, 2006 5:57 pm**

Hi Geoff. Nice to see you.

What I do is open a text editor such as TextWrangler or BBEdit (I'm on Mac) or something similar on other platforms, and type this into a window:

Code: Select all

#!/usr/bin/newlisp

(define (rsequence x y z) 
	(randomize (sequence x y (if z z 1))))
	
(set	'warden (rsequence 0 99) 
		'prisoners (rsequence 0 99)) 

(println prisoners)
(println warden)
(exit)

Then I'd run it with Command R. The results of the println function appear in another window:

Code: Select all

(44 40 97 71 10 59 4 77 24 11 28 34 38 63 75 51 13 33 99 54 76 36 
 57 0 2 53 39 45 30 58 62 12 65 82 87 93 60 25 74 84 47 90 8 20 91 
 98 41 81 79 67 7 72 16 5 55 68 9 89 21 78 19 56 50 73 70 43 69 31 
 92 23 52 6 83 27 32 26 46 29 37 61 1 85 42 66 3 88 80 96 86 48 15 
 14 22 49 35 95 64 17 94 18)
(7 83 73 59 14 12 44 78 18 22 34 65 32 2 75 80 37 84 10 92 15 39 
 24 47 63 16 31 0 54 82 3 99 19 21 40 41 61 4 89 69 25 5 93 79 51 
 45 27 91 94 62 49 88 71 11 68 90 60 96 97 20 9 66 8 76 50 74 6 52 
 46 38 98 81 67 42 85 87 56 43 33 17 58 48 13 64 29 95 72 30 55 70 
 53 57 86 35 23 77 28 1 36 26)

Others like working in a terminal window.

Posted: **Mon Sep 18, 2006 6:10 pm**

cormullion wrote:Hi Geoff. Nice to see you.

What I do is open a text editor such as TextWrangler or BBEdit (I'm on Mac) or something similar on other platforms, and type this into a window:

I'm (most often) on a Mac as well. So people don't use newlisp-tk? I have no problem using TextWrangler, but I had assumed the IDE that came with newLISP was the place to start. How do you debug using an external editor?

thanks for the input,

Geoff

Posted: **Mon Sep 18, 2006 6:47 pm**

My own code isn't complicated enough to use a debugger on, so I can't address that part, but unless I am mistaken, newlisp-tk is not an ide, it's more like a shell for newlisp. For scripts, I think everybody just uses whatever editor they like best. For one-liner testing, I usually just type "newlisp" in an xterm and start typing.

This may be a clue about debugging:

http://www.newlisp.org/downloads/newlis ... html#debug

Someone smarter than I am will have to fill you in on the details.

:-)

Posted: **Mon Sep 18, 2006 6:53 pm**

Welcome Geoff,

the newlisp-tk IDE is more of an exploration and play tool. Its good for trying out little things and exploring, but for serious work, you should follow Corumullion's and Tom's advice and use a text editor to edit your scripts.

The only reason you would use newlisp-tk is for graphics capable applications. But even then you would do your program editing with some other editor and use the 'load' button to load your programs.

Lutz

Posted: **Mon Sep 18, 2006 6:53 pm**

I only used newlisp-tk once - I didn't really like it. Perhaps others do, though.

I like the idea of a debugger/editing environment, but I've never used one, so I don't miss it - I debug using println statements... :-)

As for your 2c question, there might be a better way - there's nearly always a more elegant way, with newLISP. I often find myself formulating a conventional solution (using loops for example), only to find out later that there's a simple way of making things happen. But it looks like you've already got the idea...

I don't understand your 2d question though. Not sure what 'the loops based on the array' means, nor ' what sequence of numbers the loop starting with X contains'. Perhaps the more intelligent forum members will be of more help, or have done this logic stuff before!

Posted: **Mon Sep 18, 2006 7:28 pm**

tom wrote:...unless I am mistaken, newlisp-tk is not an ide, it's more like a shell for newlisp.

That might explain why I'm having a hard time with it. ;-)

Posted: **Mon Sep 18, 2006 8:06 pm**

cormullion wrote:I don't understand your 2d question though. Not sure what 'the loops based on the array' means, nor ' what sequence of numbers the loop starting with X contains'.

I guess I'm trying something harder to start than I should -- or at least harder than my powers of explanation can handle. Here's another shot, with an example:

Suppose there are only 10 prisoners, conveniently named 1, 2, 3...10. Here is the way the warden happened to set up the boxes, and the guess the prisoners made, in two columns:

Warden Prisoners
. . 9 . . . . . . 9
. . 3 . . . . . . 10
. . 6 . . . . . . 5
. . 8 . . . . . . 8
. . 5 . . . . . . 2
. . 7 . . . . . . 3
. . 1 . . . . . . 4
. . 4 . . . . . . 6
. . 2 . . . . . . 1
. . 10 . . . . . 7

So the first box contains prisoner 9's name, the second box contains prisoner 3's name, etc. The prisoners guessed that the first box would have prisoner 9's name, the second box would have prisoner 10's name, etc.

This means that when prisoner 9 walks into the room, he will find his name immediately, because the prisoners happened to select him as the first box, and the warden did as well. Prisoner 8 will find his name immediately in the 4th box.

But what about prisoner 3?

-- He will open the 6th box, because that is where he is on the prisoners' list. In that box he will find prisoner 7's name.
-- He will then open the 10th box (again because that is where it is on the prisoners' list) and find prisoner 10's name.
-- He will then open the 2nd box, and find his name.

It took him 3 boxes to find his name. The same will be true for prisoners 7 and 10. The three of them form a loop, because each of them have the next in the loop's name in their box.

The remaining 5 prisoners form another loop: 2, 5, 6, 4, 1.

So with this particular distribution, the ten prisoners would all find their names in 5 boxes or less.

After choosing random distributions, the trick is to figure out what these loops are. The longest loop will determine whether the prisoners go free. In the problem as stated, if the longest loop is 90 prisoners or less, the prisoners go free.

I wrote a solution to this problem in Revolution in about 15 minutes. So far newLISP is suffering by comparison ;-)

Here's some of the code I wrote, which finds the loops. Comments are prefixed with --

Code: Select all

on mouseUp
  put fLoops(fld "warden",fld "prisoners") into fld "loops"
end mouseUp


function fLoops tWarden, tPrisoners
  put the number of lines of tPrisoners into tCount
  -- this part sets up an array where the index is 
  -- the number the prisoners assigned to the box,
  -- and the number stored in the array is
  -- the number the warden actually put in the box.
  repeat with i = 1 to tCount
    put line i of tWarden into tMap[line i of tPrisoners]
  end repeat
  -- This is the part that finds the loops
  -- First, repeat for each prisoner:
  repeat with i = 1 to tCount
    -- If the prisoner is already in a looop then skip him:
    if tDone[i] = 1 then next repeat
    -- The prisoner is not in a loop yet, so figure out
    -- the loop he is in, starting with him:
    put i into x
    repeat -- finding the loop
      -- add the contents of the current box to the loop
      put tMap[x] after tLoops
      -- mark this prisoner as done
      put 1 into tDone[x]
      -- if we've completed the loop then exit
      if tMap[x] is i then exit repeat
      -- otherwise go to the next step in the loop
      put tMap[x] into x
      -- the loop entries are space-delimited
      put space after tLoops
    end repeat
    -- the loops themselves are line-delimited
    put cr after tLoops
  end repeat
  -- get rid of the final return
  delete char -1 of tLoops
  -- prefix each loop with the number of entries in it
  repeat for each line L in tLoops
    put (the number of words of L) & " -- " & L & cr after tResult
  end repeat
  -- again get rid of final return
  delete char -1 of tResult
  -- put the loops in order from shortest to longest
  sort lines of tResult numeric by word 1 of each
  return tResult
end fLoops

And here is the output of that code for the example listed above:

1 -- 8
1 -- 9
3 -- 7 10 3
5 -- 2 5 6 4 1

What I'm trying to figure out with my imperfect understanding is how to use the array I think I have created to come up with the loops.

Posted: **Tue Sep 19, 2006 8:01 am**

gcanyon wrote:I wrote a solution to this problem in Revolution in about 15 minutes. So far newLISP is suffering by comparison ;-)

That's impressive. Or had you used Revolution before that? :-) Anyway, I don't think newLISP is much harder, really, although your previous experience with Hypertalk won't be quite as useful - but there are probably some interesting common areas - languages are often inspired by each other.

Well, I read your description again and it started to make more sense. I think it boils down to a repeated look-up. So I would probably start by using an association list. For example:

Code: Select all

(set 'pw '(
	(9 9)
	(10 3)
	(5 6)
	(8 8)
	(2 5)
	(3 7)
	(4 1)
	(6 4)
	(1 2)
	(7 10)))

Then you work through the numbers, looking up the 'value' and re-using that for another lookup.

Code: Select all

(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 ))

Now 'loops' contains a list of the loops, which you can work on as you wish:

Code: Select all

(println (unique loops))

((3 7 10) (9) (8) (1 2 4 5 6))

Obviously there's some room for optimisation here (!) but you're not supposed to do that straight away (well that's my excuse) ... :-)

newlispfanclub.alh.net

Newbie looking for guidance

Newbie looking for guidance