def valid? stack
q2 = stack.size - 1
q2.times { |q1|
return nil if stack[q1] == stack[q2] or (q1-q2).abs == (stack[q1]-stack[q2]).abs
}
end
def queens stack, n
if n == 8
p stack
else
(1..8).each do |rank|
stack.push(rank)
queens(stack, n+1) if valid?(stack)
stack.pop
end
end
end
queens [], 0
class Array
def rot
push( shift )
end
end
nqueens = proc{|n|
odds, evens = (1..n).partition{|x| x % 2 > 0 }
case n % 12
when 2
odds = [3,1] + odds[3..-1] + [5]
when 3, 9
odds.rot.rot
evens.rot
when 8
d = -2
odds.map!{|x| d *= -1; x + d}
end
p evens + odds
}
nqueens[8]
class Array
def rot
push( shift )
end
end
proc{|n| p ((1..n).partition{|x|x%2>0}.inject{|o,e|
e + case n % 12
when 2
[3,1]+o[3..-1]+[5]
when 3,9
o.rot.rot;e.rot;o
when 8
d=-2;o.map{|x| x + d*=-1} end})}[ 8 ]
Evaluation of (cons x '()) yields (x), but (cons x nil) yields (x nil) because nil is treated as a boolean value when evaluated instead of as an empty list. The cons of two atoms in newLISP does not yield a dotted pair, but rather a two-element list. The predicate atom? is true for nil, but false for the empty list. The empty list in newLISP is only an empty list and not equal to nil.
A list in newLISP is a LISP cell of type list. It acts like a container for the linked list of elements making up the list cell's contents. There is no dotted pair in newLISP because the cdr (tail) part of a LISP cell always points to another LISP cell and never to a basic data type, such as a number or a symbol. Only the car (head) part may contain a basic data type.
This is why Arc is better than newLISP. The only reason I can think of for this is that newLISP is trying to protect newbies from the actual structure of lists by telling them that cons adds an element to the beginning of a list, car gets the first element of a list, and cdr gets the rest of the list.
Arc doesn't try to protect people from these kinds of things. It's not like we can't handle the real meaning of cons.
If you want to get a feel for Arc, I recommend either reading or skimming the tutorial: http://ycombinator.com/arc/tut.txt . It covers the basics of Arc and its idioms.
I have three objections to (push obj lst -1), however. First, it's not pushing (since that only refers to the top of the list). Second, the last argument is meaningless: -1? Why that? Can I do (push obj lst 2)? (push obj lst -4)? And third, pushing on the end can't be as efficient: lists don't know their last element. If we push 'a onto '(b c d), we create a list whose car is 'a and whose cdr is '(b c d); if we shove 'a onto the end of '(b c d), we have to iterate until we find the element whose car is 'd and whose cdr is nil, and then set its cdr to '(a). That will take more time, and there's no way around that, so it's not fast, per se.
Don't ask me how Lutz did it. (Maybe he keeps a pointer to the end of the list?) I think that lists in NewLisp aren't quite the same as lists in Common Lisp. Lutz wrote:
The concept of a 'cons cell' is about details of early LISP
implementations (CPU registers, etc). newLISP also has a basic cell
structure which can be linked to a list but has no concept of a dotted
pair. When have you last seen a dotted pair used in a real world
program? newLISP has 'cons' but it works differently,
By the way, it would be nice if Arc let you get the last element with -1, as NewLisp does:
arc> ('(2 3 4) -1)
Error: "list-ref: expects type <non-negative exact
integer> as 2nd argument, given: -1;
other arguments were: (2 3 4 . nil)"
Huh. That (in my humble opinion) is a terribly misnamed function (push already has a specific meaning; what about ins, for insert, which is what it actually does?), but certainly a very useful one.
I'd be curious to see what (time (push 8 x 4)) looks like: is that also constant-time? What sort of data structure is newLISP using, if not a linked list? Linked list + end pointer, perhaps--but wouldn't that break on a push? Ah well. I (unfortunately) don't really have time to construct an in-depth analysis, but I'm still curious.
I'm not sure why the Anarki won't let you do ('(2 3 4) -1); it would indeed be useful. Mayhap there are efficiency concerns? Negative indexing works in cut.
Ruby has the opposite problem from conventional Lisp: it appends quickly, but prepends slowly:
t = Time.now; a=[2]; 99_000.times{ a.push( 8 ) }; p Time.now - t
0.14
==>nil
t = Time.now; a=[2]; 99_000.times{ a.unshift( 8 ) }; p Time.now - t
70.902
==>nil
t = Time.now; a=[0,1,2,3,4]; 99_000.times{ a.insert(2, 8) }; p Time.now - t
73.346
That's 73 seconds! NewLisp can insert in a list 1800 times as fast as Ruby can!
Right. In Ruby, pushing, unshifting, and spliceing are all different operations, as they should be. Meaningful names are important.
It's not quite as fast to insert in the middle, but much faster than it should be. This would, to me, imply that newLISP isn't even using linked lists at all, but is instead using some form of array, which is decidedly unLispy. If that is the case (if, I say), then of course this will only work with "one reference only", as you can't construct lists which share cdrs; "one reference only" being an awful idea, I would consider the speed a fair tradeoff.
Have you never seen a good implementation of singly-linked lists? Because accessing the last element is a relatively common operation, a decent implementation will keep a pointer to the last element. Because it's singly-linked, the last element is the only one that pointer is any good for, so (lst -2) is still O(n), but (lst -1) becomes O(1).
The weird thing is, I actually found this good idea in an APCS review book.
Later a shorter Ruby one was posted that used regular expressions:
S =
[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were 1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],
[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",
"Please don't be so personal."]],
[ /.*/, ["That's very interesting. Do go on.",
"Tell me more.",
"I'm not sure that I understand you fully.",
"Can you elaborate on that?" ]]
P = Hash[ *"I|you|my|your|myself|yourself|you are|I am|you're|I am".
split('|')]
( gets;sub(/[.!?,; ]+$/,"");x=Array(S.find{|a|$m=$_.match(a[0])}[1])
puts x[rand(x.size)].gsub(/\d/){$m.to_a[$&.to_i].scan(
/you are|you're|\w+|\W+/).map{|s|P[s]||P.invert[s]||s}.join}
) while 9
By eliminating the step of changing the person of pronouns
in the user's input (e.g., "your" to "my"), a step that the
original Lisp program didn't perform, the Ruby
code was reduced to 2 lines (not counting the "script"):
S =
[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were 1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],
[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",
"Please don't be so personal."]],
[ /.*/, ["That's very interesting. Do go on.",
"Tell me more.",
"I'm not sure that I understand you fully.",
"Can you elaborate on that?" ]]
(gets;sub(/[.!?,; ]+$/,"");x=Array(S.find{|a|$m=$_.match(a[0])}[1])
puts x[rand(x.size)].gsub(/\d/){$m.to_a[$&.to_i]}) while 9
Some explanation about the shorter Ruby program. Consider this line from the "script":
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were 1."]],
Regular expressions are usually enclosed in /.../. The "i" at the end makes it case insensitive, so the regex could just as well have contained "i was". "\b" means that "I" will match only at the beginning of a word; we don't want to
match "cheri was in the room." The parentheses in the regex denote a "capture", the text of which can be recalled later. The dot (.) matches any single character; the star matches any number of the preceding item. So if "\bI was " is found,
(.*)
will match the rest of the string.
I've slightly tweeked the "two lines" of the program and broken them into more lines. p, the programmer's print, has been used to show the state of some variables.
(
gets
Read a line from the keyboard; instead of assigning it to a variable, rely upon Ruby's assigning it to $_.
sub( /[.!?,;\s]+$/, "" )
Since we don't say which string variable the sub should act upon, it acts on $_. We're removing puctuation and whitespace at the end of the user's input.
Assume the user typed "I was thinking."
p $_ # "I was thinking"
The tail of the string has been sanitized.
x = Array(
In the script, sometimes we have only 1 possible response by the computer (i.e., a string); sometimes we have more than 1 response (an array (list) of strings). Array( let's us easily normalize; it converts something that's not an array to an array of 1 element and leaves arrays untouched.
S.find{|a|
Iterate through the script list and return the first item for which our code block returns true. a is the parameter of the code block that receives the value of each item.
$m = $_.match(a[0])
a[0] is the regular expression; we save the match-data in $m.
}[1]
[1] yields the last part of the script item, the computer's response or responses.
)
p x # ["Why were you 1?", "I can't believe you were 1."]
Since the user typed "I was ...", the computer has 2 answers from which to choose.
p $m.class # MatchData
p $m.to_a # ["I was thinking", "thinking"]
.to_a converts match-data to an array. The first item is the complete match; the rest of the items are "captures".
puts x[rand(x.size)].
Randomly choose the computers answer. The "." at the end means a method follows...
gsub( /\d/ ){|s| $m.to_a[s.to_i] } # Why were you thinking?
The .gsub finds every numeral (digit) in the string and replaces it with the corresponding item in the match-data array. "0" would be replaced by the entire match; "1" is replaced by the first capture.
) while 9
"while 0" would work as well. The only untrue things in Ruby are false and nil. You'll have to break out of the loop with a control-key combination.
Please note that this forum doesn't use BBCode; to add code, you need to surround the code by blank lines and indent each line by two spaces or more. The indented lines will be formatted like code, and your * s won't disappear. It would be nice to see the code, but it's unreadable this way.
