Arc Forumnew | comments | leaders | submitlogin
Passing values up the line
2 points by jsgrahamus 2870 days ago | 32 comments
I've been working on the n-queens problem as a way to learn arc. What I have so far is listed below.

However, I have a problem where a variable's value lower in the function reverts to an initial value when I loop back up to the top of the while statement. And I'm not sure how that should be handled.

Any comments?

Thanks, Steve

---

  (def nqueens (board-size)
    (with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
          (while (~ finished)
                 (prn "1: diagonals " diagonals " result " result)
                 (let (diagonals result row)
                   (get-next-row board-size diagonals result)
                   (prn "2: diagonals " diagonals " result " result)
                   (if (> (++ jsg) 2) (= finished t)) 
                   (if row 
                      (if (is (len result) board-size)
                        (let (diagonals result total) 
                          (print-result diagonals result total))
                        (do
                          (prn "3: diagonals " diagonals " result " result)
                          (= result (goto-next-column result))
                          (prn "4: diagonals " diagonals " result " result)))
                      (if (is (len result) 1)
                        (= finished t)
                        (let (diagonals result) 
                          (goto-previous-column diagonals result))))))
          (prn "Number of results: " total)))
---

print out:

  arc> (nqueens 4)
  1: diagonals nil result (0)
  2: diagonals (1 -4) result (1)
  3: diagonals (1 -4) result (1)
  4: diagonals (1 -4) result (1 0)
  1: diagonals nil result (0)
  2: diagonals (1 -4) result (1)
  3: diagonals (1 -4) result (1)
  4: diagonals (1 -4) result (1 0)

   ...

  Number of results: 0
  "Number of results: "
  arc>


3 points by zck 2869 days ago | link

I'm pretty sure that what's going on is that you never set the top binding of result to anything else, so it's always the original value at the beginning of each while loop.

Consider this code:

    arc> (let result 0 (let result 2 (= result 3)) result)
    0
The top-level result is never updated. What part of your code are you expecting to update the value of result?

-----

3 points by akkartik 2869 days ago | link

Ah, you're right. I think jsgrahamus might be expecting result to be modified by this line:

  (let (diagonals result row) (get-next-row board-size diagonals result)
    ..)
But it just creates a new shadowing binding for result, which exists only for the lifetime of the let, and is lost once the let is finished. Think of let as pushing a new value for its variable(s) on a stack before running its body, then popping the new values off, leaving behind any preexisting values.

-----

2 points by jsgrahamus 2869 days ago | link

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 2869 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 2868 days ago | link

Thanks, makes sense.

-----

2 points by jsgrahamus 2869 days ago | link

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 2869 days ago | link

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

-----

2 points by jsgrahamus 2869 days ago | link

Yes, see below.

-----

2 points by jsgrahamus 2869 days ago | link

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 2869 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 2863 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

-----

2 points by akkartik 2869 days ago | link

After an hour of working on it and fixing 2 bugs:

  (def nqueens (n (o queens))
    (if (< len.queens n)
      (let row (if queens (+ 1 queens.0.0) 0)
        (up col 0 n
          (let new-queens (cons (list row col) queens)
            (if (no conflicts.new-queens)
              (nqueens n new-queens)))))
      (prn queens)))

  ; check if the first queen in 'queens' lies on the same column or diagonal as
  ; any of the others
  (def conflicts (queens)
    (let (curr . rest) queens
      (or (let curr-column curr.1
            (some curr-column (map [_ 1] rest)))  ; columns
          (some [diagonal-match curr _] rest))))

  (def diagonal-match (curr other)
    (is (abs (- curr.0 other.0))
        (abs (- curr.1 other.1))))
The first 9 elements of http://oeis.org/A000170 match. 8 queens takes 1.5s; 9 queens takes 7s.

Woohoo, I am smarter than I was 20 years ago :) Though it does help to have a better language..

-----

2 points by jsgrahamus 2868 days ago | link

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 2868 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 2868 days ago | link

Thanks. Quite the learning experience for me.

-----

1 point by akkartik 2868 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 2868 days ago | link

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

-----

2 points by jsgrahamus 2868 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 2868 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 2868 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 2868 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 2868 days ago | link

Ah, thanks! Lots to learn there.

-----

2 points by akkartik 2870 days ago | link

Can you show the other functions like get-next-row? Thanks.

-----

2 points by jsgrahamus 2869 days ago | link

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 2869 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 2869 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 2869 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 2869 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 2868 days ago | link

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

-----

2 points by akkartik 2869 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 2869 days ago | link

Thanks.

-----

2 points by jsgrahamus 2869 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.

-----