Arc Forumnew | comments | leaders | submit | jsgrahamus's commentslogin
2 points by jsgrahamus 105 days ago | link | parent | on: A convenience layer over setforms

This turned out to be a LOT more difficult than I imagined.

Thanks so much.

-----

1 point by akkartik 104 days ago | link

Well, it was also doable with existing defset, but rocketnia saw something a bit messy and decided to clean it up in the process :) "Done, and gets things smart." (http://steve-yegge.blogspot.com/2008/06/done-and-gets-things...)

-----

2 points by jsgrahamus 109 days ago | link | parent | on: Lisp/C: lisp-flavored C

Someone has been busy.

-----

2 points by jsgrahamus 111 days ago | link | parent | on: Passing values up the line

Here is a related post: http://arclanguage.org/item?id=4370

-----

2 points by jsgrahamus 111 days ago | link

Here is a version from the linked post altered to take any size n. Can you see the cause of the error?

  (def valid? (stack)
    (let i 0
      (if (or (pos stack.0 cdr.stack)
              (some (fn(x)(++ i)(is i (abs:- x stack.0))) cdr.stack))
        nil
        t)))

  (def queens2 (max size stack)
    (if (is size max)
      (and (prall rev.stack "[ ") (prn " ]"))
      (for rank 1 max
        (push rank stack)
        (if (valid? stack)
            (queens2 max (+ size 1) stack))
        (pop stack))))

  (def queens (max)
     (with (size 0 stack nil)
        (queens2 max size stack)))

  arc> (queens 4)
  Error: "_R: undefined;\n cannot reference undefined identifier"
  arc>

-----

3 points by rocketnia 111 days ago | link

Whenever you see an error message complain about an undefined identifier named "_R", that's because of a long-standing issue with the Racket reader in Windows terminals. If you paste multiple lines into the terminal, what you paste needs to have a blank line at the end already or else Racket will think it sees an R somewhere in the middle of your code.

It's not your fault. It's a bummer to have to work around this.

-----

2 points by akkartik 111 days ago | link

BTW, you can always simplify (if <expression> nil t) to just (no <expression>).

Also, what's that i variable doing in valid?? I don't understand how valid? works..

You _really_ don't want to be making pass-by-reference changes like incrementing i inside some, since there's no guarantee about the order in which it'll run. If you want imperative updates, just use an explicit loop like each.

-----

1 point by akkartik 111 days ago | link

Hmm, that works for me on both Anarki and Arc 3.1. Are you running on Windows or something like that?

-----

1 point by akkartik 111 days ago | link

Ah, thanks! Lots to learn there.

-----

2 points by jsgrahamus 111 days ago | link | parent | on: Passing values up the line

Wow, that was quick: Time and lines of code.

Can you explain how it works?

I believe len.queens is (len queens).

What is:

  - (n (o queens))
  - queens.0.0
  - col
  - curr
  - some
  - (no [ is this the same as (~?]
When I ran it, I got

  arc> (nqueens 4)
  ((3 2) (2 0) (1 3) (0 1))
  ((3 1) (2 3) (1 0) (0 2))
  nil
  arc>
Is this in the form of ((col row) (col row) (col row) (col row))?

Thanks so much.

Steve

-----

1 point by akkartik 111 days ago | link

Yeah, I should have explained more. I'd planned the results to be in the form:

  ((row col) (row col) (row col) ...)
Your version works just as well :) but the variable names might make a little more sense this way.

a) (o queens) means that queens is an optional argument. If I don't pass in a value it's nil by default. I could also have given it an explicit default by saying (o queens 42). You can read more about this in the tutorial: http://www.arclanguage.org/tut.txt. Worth a reread if it's been a while.

b) queens.0.0 expands to ((queens 0) 0). Which is the same as (car (car queens)). Just a quick way to pull out the first row, the row of the most recently added queen (since I'm adding queens on the left using cons).

c) col is just a variable name for the column in the above representation of queens. But perhaps you were asking about up. Try this out at your Anarki prompt:

  arc> (help up)  ; only in Anarki
  arc> (up col 0 8 (prn col))
d) some takes a predicate (function) and a list, and returns true if any of the elements of the list is satisfied by the predicate (function returns true). Check out (help some), as well as the tutorial above. One twist is that you can pass in any number/character/boolean as a predicate, and it's as if you're comparing with it. So I'm asking "have we already seen this column?" in this line:

  (some curr-column (map [_ 1] rest))
e) Yes, no is like ~ though not quite the same. It's just simple boolean negation. (no nil) is t, no on anything else is nil. ~ (complement) is slightly different, it operates on functions and makes them return their negation. So this relation always holds:

   (no f.x) <=> (~f x)
I could have written (no conflicts.new-queens) as (~conflicts new-queens).

Thanks for asking!

-----

2 points by jsgrahamus 111 days ago | link

Thanks. Quite the learning experience for me.

-----

1 point by akkartik 111 days ago | link

Oh, I missed a question.

curr in conflicts contains the first or most recently added queen. So in this line I'm 'unpacking' the list of queens into the first and the rest.

  (let (curr . rest)  queens
    ..)
Try it out for yourself at the arc prompt. Compare these two:

  (let (a b) '(1 2 3) b)
  (let (a . b) '(1 2 3) b)

-----

2 points by jsgrahamus 112 days ago | link | parent | on: Passing values up the line

Looking at this code segment:

   (do
     (let (diagonals2 result2 total2)
  	(print-result diagonals2 result2 total2)
  	(= diagonals diagonals2 result result2 total total2)))
There must be a way for the system to realize I expect (print-result) to update diagonals, result and total, so it automatically creates diagonals2/result2/total2, puts them in a let statement as the receivers of the return value of (print-result) and upon coming back from (print-result) automatically the system automatically sets diagonals/result/total to each element of the return list.

Perhaps a macro could do such?

-----

2 points by akkartik 112 days ago | link

Yeah, you're bringing up an interesting pattern: how to update variables from a function when it returns multiple values. Let me think about it.

-----

2 points by rocketnia 106 days ago | link

I was working on a response to this thread, but I decided to make it a thread of its own: http://arclanguage.org/item?id=19763

-----

3 points by jsgrahamus 112 days ago | link | parent | on: pg recommending Clojure

Perhaps it is because of the larger community backing Clojure?

-----

2 points by jsgrahamus 112 days ago | link | parent | on: Passing values up the line

Thanks, I'm familiar with that practice. I'm also used to passing by reference so that changes made to the variable in the newer function get passed back to the calling function.

-----

2 points by akkartik 112 days ago | link

Yeah, makes sense. However, let always creates a new binding and never modifies existing bindings. That's why it makes you indent its body to the right. Compare:

  (= x 3 y 4)
  (+ x y)
with:

  (let (x y) '(3 4)
    (+ x y))
The indentation is a hint that these are new x and y variables, compared to any earlier x and y variables.

Besides let there are indeed functions in Arc where you can pass lists or tables by reference (though not primitives like numbers or characters). However, it's usually a good idea to try to avoid these, again so you can practice a less imperative style of programming (http://arclanguage.org/item?id=19709). My usual approach is to first build a program with promiscuous copying everywhere, and then if it turns out to be too slow pick the 2% of cases that can speed it up a lot and make them destructive/call-by-reference, because the cost of doing so is that it makes the program harder to understand.

-----

2 points by jsgrahamus 111 days ago | link

Thanks, makes sense.

-----

2 points by jsgrahamus 112 days ago | link | parent | on: Passing values up the line

Here you go:

  (def get-next-row (board-size diagonals result total)
       (with (column (len result) finished nil new-diagonals nil row (car (rev result)))
         (while (and (~ finished) (~ (> (++ row) board-size)))
	        (if (~ (mem row result))
	  	  (do
		    (= new-diagonals (calculate-diagonals board-size column row))
		    (if (and (~ (mem (car new-diagonals) diagonals))
			     (~ (mem (car (rev new-diagonals)) diagonals)))
		      (do
		        (= finished t)
		        (= result (rev (cons row (cdr (rev result)))))
		        (for i 1 2 (push (pop new-diagonals) diagonals)))))))
         (list diagonals result (if finished row nil) total)))

-----

2 points by akkartik 112 days ago | link

There's still other functions that are missing, such as goto-next-column, goto-previous-column, etc.

Anyways, I think you've gotten me to work on this problem as well :) I found it super hard when I solved it in C back in '97. Perhaps I should go back and see if I've gotten any better at programming.

-----

2 points by jsgrahamus 112 days ago | link

Here is the whole program. I still need to check for reflections [if I already have (2 4 1 3), do not allow (3 1 4 2)].

As I said, I'm using this to learn arc. So if y'all have any suggestions, I'm all ears :-)

  ;; nqueens - Solve n queens problem
  ;;
  (def calculate-diagonals (board-size column row)
       (let new-diagonals nil
         (if (is row 1)
  	   (push column new-diagonals)
  	   (if (is column 1)
  	     (push row new-diagonals)
  	     (push (+ column row -1) new-diagonals)))
         (if (is row 1)
  	   (push (- column board-size 1) new-diagonals)
  	   (if (is column 1)
  	     (push (- 1 board-size row) new-diagonals)
  	       (push (- column board-size row) new-diagonals)))
         new-diagonals))
  
  (def get-next-row (board-size diagonals result total)
       (with (column (len result) finished nil new-diagonals nil row (car (rev result)))
         (while (and (~ finished) (~ (> (++ row) board-size)))
  	      (if (~ (mem row result))
  		(do
  		  (= new-diagonals (calculate-diagonals board-size column row))
  		  (if (and (~ (mem (car new-diagonals) diagonals))
  			   (~ (mem (car (rev new-diagonals)) diagonals)))
  		    (do
  		      (= finished t)
  		      (= result (rev (cons row (cdr (rev result)))))
  		      (for i 1 2 (push (pop new-diagonals) diagonals)))))))
         (list diagonals result (if finished row nil) total)))
  
  (def goto-previous-column (diagonals result)
       (list (cdr (cdr diagonals)) (rev (cdr (rev result)))))
  
  (def goto-next-column (result)
     (rev (cons 0 (rev result))))
  
  (def print-result (diagonals result total)
       (prn result)
       (let (diagonals result) (goto-previous-column diagonals result)
         (list (cdr (cdr diagonals)) result (++ total))))
  
  (def nqueens (board-size)
    (with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
  	(while (~ finished)
  	       (let (diagonals2 result2 row2 total2)
  		 (get-next-row board-size diagonals result total)
  		 (= diagonals diagonals2 result result2 row row2 total total2)
  		 (if row
  		    (if (is (len result) board-size)
                      (do
  			(let (diagonals2 result2 total2)
  			  (print-result diagonals2 result2 total2)
  			  (= diagonals diagonals2 result result2 total total2)))
  		      (= result (goto-next-column result)))
  		    (if (is (len result) 1)
  		      (= finished t)
  		      (let (diagonals2 result2) 
  		        (goto-previous-column diagonals result)
  			(= diagonals diagonals2 result result2))))))
  	(prn "Number of results: " total))
    nil)

-----

2 points by zck 112 days ago | link

> I still need to check for reflections [if I already have (2 4 1 3), do not allow (3 1 4 2)].

There's a cool technique I read about to solve problems like this. I'll put it a few lines down in case you want to think about it yourself.

.

.

.

Sort them, then check for equality! I learned this when reading about anagrams.

-----

3 points by jsgrahamus 112 days ago | link

So if two results were (2 4 1 3) and (3 1 2 4), both of them sort to (1 2 3 4) so delete one of them? Of course all of the results will sort to (1 2 3 4) for a 4x4 board.

Not sure I understand.

-----

2 points by zck 111 days ago | link

Oh, you're right. I misunderstood what you meant by "reflections".

-----

2 points by akkartik 112 days ago | link

Thanks! I think I'll try to solve it on my own without looking at yours in depth first. That might take me a few days. But feel free to keep asking questions in the meantime.

-----

2 points by jsgrahamus 112 days ago | link

Thanks.

-----

2 points by jsgrahamus 112 days ago | link

This took me too many hours in my work language to solve. Initially I next just translated it to arc, but that didn't seem to work, so I started again in arc from scratch. I sure learned a lot about arc and debugging in it.

It took me a while to wrap my mind around this problem. Sure is different than CRUD work, reports and interfaces.

-----

2 points by jsgrahamus 112 days ago | link | parent | on: Passing values up the line

Here's a newer view. A number of variables (diagonals, result, row, total) get modified lower in the function. There must be a better way of updating those variables.

Ideas?

Thanks, Steve

---

  (def nqueens (board-size)
    (with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
	  (while (~ finished)
	         (let (diagonals2 result2 row2 total2)
		   (get-next-row board-size diagonals result total)
	           (if row2
		      (if (is (len result2) board-size)
                        (do
			  (let (diagonals3 result3 total3)
			    (print-result diagonals2 result2 total2)
			    (do
			      (= diagonals2 diagonals3)
			      (= result2 result3)
			      (= total2 total3))))
		        (= result2 (goto-next-column result2)))
		      (if (is (len result2) 1)
		        (= finished t)
		        (let (diagonals3 result3) 
		          (goto-previous-column diagonals2 result2)
			  (= diagonals2 diagonals3)
	  		  (= result2 result3))))
		   (= diagonals diagonals2)
		   (= result result2)
		   (= row row2)
		   (= total total2)))
	  (string "Number of results: " total)))

-----

2 points by akkartik 112 days ago | link

While I mull it over: do you have it working now?

-----

2 points by jsgrahamus 112 days ago | link

Yes, see below.

-----

2 points by jsgrahamus 123 days ago | link | parent | on: Multiple Return Values

Why avoid = in lisp/arc?

-----

1 point by akkartik 123 days ago | link

As long as you use '=' it's easy to keep programming C or MUMPS in Lisp. Avoiding '=' forces you to give up old habits and become fluent with (writing as well as reading) deeply nested calls, 'let' and recursion. Those are some big reasons to use Lisp rather than imperative languages. So if you don't use them you're missing out.

-----

2 points by jsgrahamus 123 days ago | link

Makes sense. Thanks.

It really does force me to think a different way. Painful sometimes, too.

-----

More