subject:"Re\: \[Jprogramming\] Arc consistency in J"

Re: [Jprogramming] Arc consistency in J

2012-11-30 Thread Linda Alvord

  Another problem is cleared up.

 A=:4
   B=:2 6
   A,.B
┌───┬───┐
│4 2│4 6│
└───┴───┘
   NB.   x u.v y ↔ vi (v x) u (v y)

 (A),0(B)
┌───┬───┐
│4 2│4 6│
└───┴───┘

So,  hh  and ii  replace the two functions  h  and  I  below.

   hh=: [:,[:  ,./
   A hh B
   A hh B
4 2 4 6
   
   ii=: 13 :',(x),0(y)'
   ii
[: , ([:  [) ,0 [:  ]
   A ii B
4 2 4 6 

Also, ii does not involve  .

Linda



_
From: Linda Alvord [mailto:lindaalv...@verizon.net] 
Sent: Tuesday, November 20, 2012 3:23 AM
To: 'programm...@jsoftware.com'
Subject: RE: [Jprogramming] Arc consistency in J


Here’s a simpler version of the domain error that I can’t correct.

   A=:4  
   B=:2 6
   f=:[:  ,./
   ]C=:A f B
4 2
4 6
   g=:,.0 2 
   ]D=:A g B
4 2
4 6
   C-:D
1
   h=:[: f,..
   h
[: f ,..
   i=:[: g ,..
   i
[: g ,..
   5!:4 'h'
  ┌─ [:   
  ├─ f
──┤  ┌─ ,.
  └─ . ─┴─  
   5!:4 'i'
  ┌─ [:   
  ├─ g
──┤  ┌─ ,.
  └─ . ─┴─  
   A h B
4 2 4 6
   A i B
   A i B
|domain error: g
|   A i B
   
 
Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Linda Alvord
Sent: Saturday, November 17, 2012 10:27 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Hi Michal,  I keep working on your code and I hit a snag?  Maybe someone can 
explain the domain error that I encounter.

   n=: 5 
   X=:(?(2#n)$2)*(i.n)/i.n
   adj=: 13 :'(0y)([:#)1 i.#y'
   A=:adj X
   
I'm trying to simplify  arcsX

   arcsX =: [: ( @ (,./)) ([ (,..)0 {)
   ](i.n) arcsX A
0 4
1 4
2 4
   
   h=:[: (G=:[:,./),..
   h
[: ([:  ,./) ,..
   ((i.n) arcsX A)-:(i.n) h A
1

And h works OK.   
   G
[:  ,./
   I=:,.0 2 
   I
,.0 2 
   ((i.n)G A)-:(i.n)I A
1

Then I found  I  to replace  G
   
   j=:[:(I=:,.0 2 ) ,..
   (i.n) h A
0 4
1 4
2 4
   (i.n) j A
|domain error: j
|   (i.n)j A

It doesn't work when inserted in  h

Linda

-
Original Message-
From: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Friday, November 16, 2012 9:44 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Boss is Boss, I eventually arrived at the same (non-negative case) solution.

Thanks km for the explanation of @ vs @: which I'm starting to slowly get.

Linda: I think I prefer having it on three lines.  It better breaks down the 
steps I'm trying to accomplish.  Maybe someday I'll be able to boil it down to 
a single line ;-)

Raul: please let me know if we should still pursue your previous definition in 
light of Mike's commentary.

Mike Day is right on with all his observations about what I'm trying to 
accomplish.  Sorry for the long delay - I'm having trouble keeping up.
Notes:

(0) Interesting {:: vs { and 

(1) The J arc consistency algorithm I've presented is not AC-3 nor any of the 
later AC algorithms.  AC-3 is simply another algorithm that accomplishes the 
same thing.

(2) Using the approach I do with the C-tables allows massive parallelism.
In particular using mostly logical-and and logical-or operations on boolean 
arrays allows a single assembly level operation to have 32 or 64 way 
parallelism (or larger if using vector registers).

(3) A simpler algorithm that requires a single version of each C-table and a 
revDom that reduces both it's input domains is possible but I haven't gotten 
there yet.  I'm working on it along with code to randomly generate a sudoku and 
generate the equivalent CSP.  It might be a while.

Cheers,

Mike


On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.ukwrote:

 Thanks,  but my questions were rhetorical!  I was merely trying to 
 comment on Linda's apparent aversion to @ and @: and her preference 
 for [: which she has justified in a later post.  I'm not the Mike who 
 started this thread on arc consistency.

 Incidentally,  I also commented in that message on 11/11 (still in the 
 history below) about Raul Miller's question concerning the domain matrix D.

 Mike


 On 14/11/2012 11:24 AM, Linda Alvord wrote:

 Kip's comments are helpful.

 Back to your problem, Mike:

 X=:?(2#n)$2  NB. generate random matrix of [0,1]
 X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
 ]X=:X+|:2*X
 0 0 0 0 1
 0 0 1 0 0
 0 2 0 0 0
 0 0 0 0 1
 2 0 0 2 0

 The three lines can be combined in one line.

 ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
 0 1 1 0 1
 2 0 1 0 1
 2 2 0 1 0
 0 0 2 0 0
 2 2 0 0 0

 Linda


 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com[mailto:
 programming-bounces@**forums.jsoftware.comprogramming-bounces@forums
 .jsoftware.com]
 On Behalf Of km
 Sent: Wednesday, November 14, 2012 4:29 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Responding to Mike's query about @

 Mathematical composition  f o g  means

Re: [Jprogramming] Arc consistency in J

2012-11-29 Thread Linda Alvord

I finally wrote  f  without  @

]A=:?3 3$3
0 0 2
0 0 0
0 2 1
   f=: 13 :'(0y)@#i.#y'
   f
(0  ]) @# [: i. #
   f A
--TT---┐
│2││1 2│
L-++
   g=: 13 :'(0y)([:#)1 i.#y'
   g 
(0  ]) ([:  #)1 [: i. #
   g A
--TT---┐
│2││1 2│
L-++
   
I think it came to me after the recent discussion about @: and capped fork.

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Linda Alvord
Sent: Sunday, November 11, 2012 1:56 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

   


 
Mike, I changed  f  as you suggest.

   n=: 5 
   A=:?(2#n)$2  NB. generate random matrix of [0,1]
   A=:A*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
   ]A=:A+|:2*A
0 0 1 0 0
0 0 0 0 0
2 0 0 1 1
0 0 2 0 1
0 0 2 2 0
   
   adj=:((@#)(i.n))@(0)
   adj
@#0 1 2 3 4@(0)
   adj Al
--TT-T---T---┐
│2││0 3 4│2 4│2 3│
L-++-+---+
   
   f=: 13 :'(0y)@#i.#y'
   f
(0  ]) @# [: i. #
   f A
--TT-T---T---┐
│2││0 3 4│2 4│2 3│
L-++-+---+
   

I'm still hoping to remove  @  and I guess it will be useful to deal with
rank as  Henry suggests. I think I'll take a second look at  A.  Thanks for
all your help.

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day
Sent: Sunday, November 11, 2012 7:15 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

I don't think you can remove the @, although you may use the cap, [: ,
instead,  but then you need to force the rank:
([:(#0 1 2 3@(0)))1 A
+-++---+-+
|2||0 3|2|
+-++---+-+

I don't like using 0 1 2 3 explicitly since it presumes you know the
dimension of A, so I prefer either
   adja =: * @# i.@#   NB. or use caps if @ is too horrible
adja A
+-++---+-+
|2||0 3|2|
+-++---+-+

or

adjI =: @I.@:*
adjI A
+-++---+-+
|2||0 3|2|
+-++---+-+

I. is so useful that I've defined an I dfn in my Dyalog APL too!

As for Raul's point about D,  I understood it to represent the domains of
the variables:  if there are m variables  and the domain of all their
possible values is i.n,  then 1 = D{~i,j means that variable number i may
have value j .  m and n are likely to be different.  So  iD is a boolean
representing the a priori values that variable i might have.  
The consistency algorithm apparently examines which of these a priori values
are consistent with the domains of the other variables given certain unary
and binary constraints which are also inputs to the problem.

Michal's example had m=n which tends to mislead the casual reader!

I believe The m*m A array points to which constraints apply,  so 0l=A{i,k
means that binary constraint number l applies between variables i and k.
This is why A isn't just a boolean adjacency matrix nor do the entries
signify distances as they would in a weighted graph.

I'm puzzled that the algorithm requires each binary relation to be presented
in both direct and transposed form  (this explains Michal's need to patch in
a new index (to a transposed C) in the lower triangle of A for each index to
a direct C in the upper triangle).  Perhaps the later algorithms (arc-4...
?) deal with this difficulty.

It strikes me that for a real problem,  concise relations such as x : 
y,  or 2x+3y5 can become pretty large and unwieldy C-tables, but perhaps
that's unavoidable when working in the integers.

(The other) Mike

On 11/11/2012 10:16 AM, Linda Alvord wrote:

Mike, I think this will work as an alternative to  adj

 A
0 0 1 0
0 0 0 0
2 0 0 1
0 0 2 0
adj
@#0 1 2 3@(0)
adj A
--TT---T-┐
│2││0 3│2│
L-++---+--
h
0 1 2 3 @#~ 0  ]
h A
--TT---T-┐
│2││0 3│2│
L-++---+--
 
  Can anyone remove the final  @  from  h  ?

Linda
  

-Original Message-
From:programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul Miller
Sent: Saturday, November 10, 2012 12:44 PM To:programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

On Sat, Nov 10, 2012 at 12:16 PM, Michal D.michal.dobrog...@gmail.com
wrote:

 Here X is telling us to use the constraint c1 (presumably b/c C is not
 shown) between the variables 1 and 3 (0 based).  Likewise, use the 
 transpose going the other direction (3,1).

Ouch, you are correct, I did not specify C.  On retesting, though, it looks
like my results stay the same when I use:

arccon=:3 :0
'D c1 X'=: y
'n d'=: $D
adj =: ((@#)(i.n)) @ (0)
A =: adj X
C=: a: , c1 ; (|:c1)
ac =:  @ (1{) @ (revise^:_) @ ((i.n);)
ac D
)

For longer scripts like this, I really need to get into the habit of
restarting J for every test.  So that probably means I should be using jhs.

 Given the structure of X, only variables 1 and 3 can possibly change.
 So if they are all changing something is definitely wrong.

This line of thinking does not make sense to me.  I thought

Re: [Jprogramming] Arc consistency in J

2012-11-22 Thread Michal D.

 in J
 
  Responding to Mike's query about @
 
  Mathematical composition  f o g  means do g first, then f and is
  expressed in J by the monadic use of  f @: g  or  [: f g .  The
 monadic use
  of  f @ g  can surprise you, compare
 
  |.@:+: 1 2 3
  6 4 2
  |.@+: 1 2 3
  2 4 6
 
  -- the first means double vector 1 2 3 then reverse the resulting
 vector,
  the second means double and reverse each scalar then assemble the
 results.
 
  Kip Murray
 
  Sent from my iPad
 
 
  On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
  wrote:
 
   I can only give a personal response.  Maybe it is because I'm left
  handed.
 
  When I look at  ((@#)(i.n))@(0)  at or
 
  -Original Message-
  From: programming-bounces@forums.**jsoftware.com
 programming-boun...@forums.jsoftware.com
  [mailto:programming-bounces@**forums.jsoftware.com
 programming-boun...@forums.jsoftware.com]
  On Behalf Of Mike
  Day
  Sent: Monday, November 12, 2012 6:40 AM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  But what's wrong with @ that's preferable with [:   ?(I think
  Th is has been asked before.)
 
  Aren't they both devices to represent what ordinary mathematicians
  just write as f g h ... for the composition of f g h ...   ?
 
  Since J cleverly allows hooks and forks and interprets unbracketed
  trains of verbs as such,  it needs some other way to recognise
  composition,  and that's what both @ (and @:) and [: do for us - so
 why
  avoid one or the other of them?   I agree it took a lot of time to get
  my head round the new way of seeing trains of verbs.
 
  Mike
 
  On 12/11/2012 7:57 AM, Linda Alvord wrote:
 
  Well, it was possible, once I managed to get the rank right. Thanks
  for providing hope that it could be done. Actually it is not too bad
  looking after all.
 
  A
  0 0 1 0 0
  0 0 0 0 0
  2 0 0 0 1
  0 0 0 0 1
  0 0 2 2 0
 
  adj=:((@#)(i.n))@(0)
  adj
  @#0 1 2 3 4@(0)
  adj A
  --TT---T-T---┐
  │2││0 4│4│2 3│
  L-++---+-+
 
  f=: 13 :'(0y)([:#)1 i.#y'
  f
  (0  ]) ([:  #)1 [: i. #
  f A
  --TT---T-T---┐
  │2││0 4│4│2 3│
  L-++---+-+
 
 5!:4 'adj'
   -- 
   -- @ ---+- #
 --  -+- 0 1 2 3 4
 │
  -- @ -+ -- 0
 L-  -+- 
 
  5!:4 'f'
   -- 0
 --+- 
 │ L- ]
 │  -- [:
 │ -+- 
  --+-  -+L- #
 │ L- 1
 │
 │ -- [:
 L-+- i.
   L- #
 
  Linda
 
  -Original Message-
  From: programming-bounces@forums.**jsoftware.com
 programming-boun...@forums.jsoftware.com
  [mailto:programming-bounces@**forums.jsoftware.com
 programming-boun...@forums.jsoftware.com]
  On Behalf Of Mike
  Day
  Sent: Sunday, November 11, 2012 7:15 AM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  I don't think you can remove the @, although you may use the cap, [:
  , instead,  but then you need to force the rank:
   ([:(#0 1 2 3@(0)))1 A
  +-++---+-+
  |2||0 3|2|
  +-++---+-+
 
  I don't like using 0 1 2 3 explicitly since it presumes you know the
  dimension of A, so I prefer either
  adja =: * @# i.@#   NB. or use caps if @ is too
 horrible
   adja A
  +-++---+-+
  |2||0 3|2|
  +-++---+-+
 
  or
 
   adjI =: @I.@:*
   adjI A
  +-++---+-+
  |2||0 3|2|
  +-++---+-+
 
  I. is so useful that I've defined an I dfn in my Dyalog APL too!
 
  As for Raul's point about D,  I understood it to represent the
  domains of the variables:  if there are m variables  and the domain
  of all their possible values is i.n,  then 1 = D{~i,j means that
  variable number i may have value j .  m and n are likely to be
  different.  So iD is a boolean representing the a priori values that
  variable i might
 
  have.
 
  The consistency algorithm apparently examines which of these a priori
  values are consistent with the domains of the other variables given
  certain unary and binary constraints which are also inputs to the
  problem.
 
  Michal's example had m=n which tends to mislead the casual reader!
 
  I believe The m*m A array points to which constraints apply,  so
  0l=A{i,k means that binary constraint number l applies between
  variables
 
  i and k.
 
  This is why A isn't just a boolean adjacency matrix nor do the
  entries signify distances as they would in a weighted graph.
 
  I'm puzzled that the algorithm requires each binary relation to be
  presented in both direct and transposed form  (this explains Michal's
  need to patch in a new index (to a transposed C) in the lower
  triangle of A for each index to a direct C in the upper triangle).
  Perhaps the
 
  later algorithms (arc-4...
 
  ?) deal with this difficulty.
 
  It strikes me that for a real problem,  concise relations such as x
 :
  y,  or 2x+3y5 can become pretty large and unwieldy C-tables, but
  perhaps that's unavoidable when working

Re: [Jprogramming] Arc consistency in J

2012-11-21 Thread Michal D.

Hi Raul,

Could you provide some context in which to run this code?

Thanks,

Mike

On Fri, Nov 16, 2012 at 6:52 PM, Raul Miller rauldmil...@gmail.com wrote:

 If you are talking about my post on the 10th, where I proposed

 arcn=:3 :0
   'D c1 X'=: y
   X1=. 1=X
   ([:+./1[: +./((|:c1) *1 2~ (|:X1) *1 2 ]) +. c1 *1 2~ X1 *1 2 ])^:_
 D
 )

 ... note that it works just fine when D is not square.

 And all I got out of Mike's 11/11 message was that D might not be square.

 Am I missing something?

 --
 Raul

 P.S. In the above code, X1=. 1 = X assumes that X had only 2s and 0s
 in the lower triangle.  Perhaps a better expression would have been X1
 =. (*X) * /i./ $X

 On Fri, Nov 16, 2012 at 9:44 PM, Michal D. michal.dobrog...@gmail.com
 wrote:
  Boss is Boss, I eventually arrived at the same (non-negative case)
 solution.
 
  Thanks km for the explanation of @ vs @: which I'm starting to slowly
 get.
 
  Linda: I think I prefer having it on three lines.  It better breaks down
  the steps I'm trying to accomplish.  Maybe someday I'll be able to boil
 it
  down to a single line ;-)
 
  Raul: please let me know if we should still pursue your previous
 definition
  in light of Mike's commentary.
 
  Mike Day is right on with all his observations about what I'm trying to
  accomplish.  Sorry for the long delay - I'm having trouble keeping up.
  Notes:
 
  (0) Interesting {:: vs { and 
 
  (1) The J arc consistency algorithm I've presented is not AC-3 nor any of
  the later AC algorithms.  AC-3 is simply another algorithm that
  accomplishes the same thing.
 
  (2) Using the approach I do with the C-tables allows massive parallelism.
  In particular using mostly logical-and and logical-or operations on
 boolean
  arrays allows a single assembly level operation to have 32 or 64 way
  parallelism (or larger if using vector registers).
 
  (3) A simpler algorithm that requires a single version of each C-table
 and
  a revDom that reduces both it's input domains is possible but I haven't
  gotten there yet.  I'm working on it along with code to randomly
 generate a
  sudoku and generate the equivalent CSP.  It might be a while.
 
  Cheers,
 
  Mike
 
 
  On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.uk
 wrote:
 
  Thanks,  but my questions were rhetorical!  I was merely trying to
 comment
  on Linda's apparent aversion to @ and @: and her preference for [: which
  she has justified in a later post.  I'm not the Mike who started this
  thread on arc consistency.
 
  Incidentally,  I also commented in that message on 11/11 (still in the
  history below) about Raul Miller's question concerning the domain
 matrix D.
 
  Mike
 
 
  On 14/11/2012 11:24 AM, Linda Alvord wrote:
 
  Kip's comments are helpful.
 
  Back to your problem, Mike:
 
  X=:?(2#n)$2  NB. generate random matrix of [0,1]
  X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
  ]X=:X+|:2*X
  0 0 0 0 1
  0 0 1 0 0
  0 2 0 0 0
  0 0 0 0 1
  2 0 0 2 0
 
  The three lines can be combined in one line.
 
  ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
  0 1 1 0 1
  2 0 1 0 1
  2 2 0 1 0
  0 0 2 0 0
  2 2 0 0 0
 
  Linda
 
 
  -Original Message-
  From: programming-bounces@forums.**jsoftware.com
 programming-boun...@forums.jsoftware.com[mailto:
  programming-bounces@**forums.jsoftware.com
 programming-boun...@forums.jsoftware.com]
  On Behalf Of km
  Sent: Wednesday, November 14, 2012 4:29 AM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  Responding to Mike's query about @
 
  Mathematical composition  f o g  means do g first, then f and is
  expressed in J by the monadic use of  f @: g  or  [: f g .  The
 monadic use
  of  f @ g  can surprise you, compare
 
  |.@:+: 1 2 3
  6 4 2
  |.@+: 1 2 3
  2 4 6
 
  -- the first means double vector 1 2 3 then reverse the resulting
 vector,
  the second means double and reverse each scalar then assemble the
 results.
 
  Kip Murray
 
  Sent from my iPad
 
 
  On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
  wrote:
 
   I can only give a personal response.  Maybe it is because I'm left
  handed.
 
  When I look at  ((@#)(i.n))@(0)  at or
 
  -Original Message-
  From: programming-bounces@forums.**jsoftware.com
 programming-boun...@forums.jsoftware.com
  [mailto:programming-bounces@**forums.jsoftware.com
 programming-boun...@forums.jsoftware.com]
  On Behalf Of Mike
  Day
  Sent: Monday, November 12, 2012 6:40 AM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  But what's wrong with @ that's preferable with [:   ?(I think
  Th is has been asked before.)
 
  Aren't they both devices to represent what ordinary mathematicians
  just write as f g h ... for the composition of f g h ...   ?
 
  Since J cleverly allows hooks and forks and interprets unbracketed
  trains of verbs as such,  it needs some other way to recognise
  composition,  and that's what both

Re: [Jprogramming] Arc consistency in J

2012-11-20 Thread Linda Alvord

Here’s a simpler version of the domain error that I can’t correct.

   A=:4  
   B=:2 6
   f=:[:  ,./
   ]C=:A f B
4 2
4 6
   g=:,.0 2 
   ]D=:A g B
4 2
4 6
   C-:D
1
   h=:[: f,..
   h
[: f ,..
   i=:[: g ,..
   i
[: g ,..
   5!:4 'h'
  ┌─ [:   
  ├─ f
──┤  ┌─ ,.
  └─ . ─┴─  
   5!:4 'i'
  ┌─ [:   
  ├─ g
──┤  ┌─ ,.
  └─ . ─┴─  
   A h B
4 2 4 6
   A i B
   A i B
|domain error: g
|   A i B
   
 
Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Linda Alvord
Sent: Saturday, November 17, 2012 10:27 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Hi Michal,  I keep working on your code and I hit a snag?  Maybe someone can 
explain the domain error that I encounter.

   n=: 5 
   X=:(?(2#n)$2)*(i.n)/i.n
   adj=: 13 :'(0y)([:#)1 i.#y'
   A=:adj X
   
I'm trying to simplify  arcsX

   arcsX =: [: ( @ (,./)) ([ (,..)0 {)
   ](i.n) arcsX A
0 4
1 4
2 4
   
   h=:[: (G=:[:,./),..
   h
[: ([:  ,./) ,..
   ((i.n) arcsX A)-:(i.n) h A
1

And h works OK.   
   G
[:  ,./
   I=:,.0 2 
   I
,.0 2 
   ((i.n)G A)-:(i.n)I A
1

Then I found  I  to replace  G
   
   j=:[:(I=:,.0 2 ) ,..
   (i.n) h A
0 4
1 4
2 4
   (i.n) j A
|domain error: j
|   (i.n)j A

It doesn't work when inserted in  h

Linda

-
Original Message-
From: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Friday, November 16, 2012 9:44 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Boss is Boss, I eventually arrived at the same (non-negative case) solution.

Thanks km for the explanation of @ vs @: which I'm starting to slowly get.

Linda: I think I prefer having it on three lines.  It better breaks down the 
steps I'm trying to accomplish.  Maybe someday I'll be able to boil it down to 
a single line ;-)

Raul: please let me know if we should still pursue your previous definition in 
light of Mike's commentary.

Mike Day is right on with all his observations about what I'm trying to 
accomplish.  Sorry for the long delay - I'm having trouble keeping up.
Notes:

(0) Interesting {:: vs { and 

(1) The J arc consistency algorithm I've presented is not AC-3 nor any of the 
later AC algorithms.  AC-3 is simply another algorithm that accomplishes the 
same thing.

(2) Using the approach I do with the C-tables allows massive parallelism.
In particular using mostly logical-and and logical-or operations on boolean 
arrays allows a single assembly level operation to have 32 or 64 way 
parallelism (or larger if using vector registers).

(3) A simpler algorithm that requires a single version of each C-table and a 
revDom that reduces both it's input domains is possible but I haven't gotten 
there yet.  I'm working on it along with code to randomly generate a sudoku and 
generate the equivalent CSP.  It might be a while.

Cheers,

Mike


On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.ukwrote:

 Thanks,  but my questions were rhetorical!  I was merely trying to 
 comment on Linda's apparent aversion to @ and @: and her preference 
 for [: which she has justified in a later post.  I'm not the Mike who 
 started this thread on arc consistency.

 Incidentally,  I also commented in that message on 11/11 (still in the 
 history below) about Raul Miller's question concerning the domain matrix D.

 Mike


 On 14/11/2012 11:24 AM, Linda Alvord wrote:

 Kip's comments are helpful.

 Back to your problem, Mike:

 X=:?(2#n)$2  NB. generate random matrix of [0,1]
 X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
 ]X=:X+|:2*X
 0 0 0 0 1
 0 0 1 0 0
 0 2 0 0 0
 0 0 0 0 1
 2 0 0 2 0

 The three lines can be combined in one line.

 ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
 0 1 1 0 1
 2 0 1 0 1
 2 2 0 1 0
 0 0 2 0 0
 2 2 0 0 0

 Linda


 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com[mailto:
 programming-bounces@**forums.jsoftware.comprogramming-bounces@forums
 .jsoftware.com]
 On Behalf Of km
 Sent: Wednesday, November 14, 2012 4:29 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Responding to Mike's query about @

 Mathematical composition  f o g  means do g first, then f and is 
 expressed in J by the monadic use of  f @: g  or  [: f g .  The 
 monadic use of  f @ g  can surprise you, compare

 |.@:+: 1 2 3
 6 4 2
 |.@+: 1 2 3
 2 4 6

 -- the first means double vector 1 2 3 then reverse the resulting 
 vector, the second means double and reverse each scalar then assemble the 
 results.

 Kip Murray

 Sent from my iPad


 On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
 wrote:

  I can only give a personal response.  Maybe it is because I'm left
 handed.

 When I look at  ((@#)(i.n))@(0)  at or

 -Original Message-
 From

Re: [Jprogramming] Arc consistency in J

2012-11-20 Thread David Ward Lambert

Here's a simpler version of the domain error...

There are two verbs f and g with demonstrated equivalence in a dyadic
case.  Bringing us through
   NB. .
   C-:D

f is a fork, g is a hook.

As monads they don't behave alike with a boxed y.
Let's examine the noun presented to f and j in the definitions of h and
i .  h and i are capped forks.

   A,..B
+---+---+
|4 2|4 6|
+---+---+

   gNB.(stitch open)
,.0 2 

Boxes won't stitch to non-boxes.



On Tue, 2012-11-20 at 08:33 +,
programming-requ...@forums.jsoftware.com wrote:
 Date: Tue, 20 Nov 2012 03:22:50 -0500
 From: Linda Alvord lindaalv...@verizon.net
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J
 Message-ID: 01cdc6f8$3b5c34a0$b2149de0$@net
 Content-Type: text/plain;   charset=utf-8
 
 Here?s a simpler version of the domain error that I can?t correct.
 
A=:4  
B=:2 6
f=:[:  ,./
]C=:A f B
 4 2
 4 6
g=:,.0 2 
]D=:A g B
 4 2
 4 6
C-:D
 1
h=:[: f,..
h
 [: f ,..
i=:[: g ,..
i
 [: g ,..
5!:4 'h'
   ?? [:   
   ?? f
 ???  ?? ,.
   ?? . ???  
5!:4 'i'
   ?? [:   
   ?? g
 ???  ?? ,.
   ?? . ???  
A h B
 4 2 4 6
A i B
A i B
 |domain error: g
 |   A i B

  
 Linda


--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-17 Thread Linda Alvord

Hi Michal,  I keep working on your code and I hit a snag?  Maybe someone can 
explain the domain error that I encounter.

   n=: 5 
   X=:(?(2#n)$2)*(i.n)/i.n
   adj=: 13 :'(0y)([:#)1 i.#y'
   A=:adj X
   
I'm trying to simplify  arcsX

   arcsX =: [: ( @ (,./)) ([ (,..)0 {)
   ](i.n) arcsX A
0 4
1 4
2 4
   
   h=:[: (G=:[:,./),..
   h
[: ([:  ,./) ,..
   ((i.n) arcsX A)-:(i.n) h A
1

And h works OK.   
   G
[:  ,./
   I=:,.0 2 
   I
,.0 2 
   ((i.n)G A)-:(i.n)I A
1

Then I found  I  to replace  G
   
   j=:[:(I=:,.0 2 ) ,..
   (i.n) h A
0 4
1 4
2 4
   (i.n) j A
|domain error: j
|   (i.n)j A

It doesn't work when inserted in  h

Linda

-
Original Message-
From: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Friday, November 16, 2012 9:44 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Boss is Boss, I eventually arrived at the same (non-negative case) solution.

Thanks km for the explanation of @ vs @: which I'm starting to slowly get.

Linda: I think I prefer having it on three lines.  It better breaks down the 
steps I'm trying to accomplish.  Maybe someday I'll be able to boil it down to 
a single line ;-)

Raul: please let me know if we should still pursue your previous definition in 
light of Mike's commentary.

Mike Day is right on with all his observations about what I'm trying to 
accomplish.  Sorry for the long delay - I'm having trouble keeping up.
Notes:

(0) Interesting {:: vs { and 

(1) The J arc consistency algorithm I've presented is not AC-3 nor any of the 
later AC algorithms.  AC-3 is simply another algorithm that accomplishes the 
same thing.

(2) Using the approach I do with the C-tables allows massive parallelism.
In particular using mostly logical-and and logical-or operations on boolean 
arrays allows a single assembly level operation to have 32 or 64 way 
parallelism (or larger if using vector registers).

(3) A simpler algorithm that requires a single version of each C-table and a 
revDom that reduces both it's input domains is possible but I haven't gotten 
there yet.  I'm working on it along with code to randomly generate a sudoku and 
generate the equivalent CSP.  It might be a while.

Cheers,

Mike


On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.ukwrote:

 Thanks,  but my questions were rhetorical!  I was merely trying to 
 comment on Linda's apparent aversion to @ and @: and her preference 
 for [: which she has justified in a later post.  I'm not the Mike who 
 started this thread on arc consistency.

 Incidentally,  I also commented in that message on 11/11 (still in the 
 history below) about Raul Miller's question concerning the domain matrix D.

 Mike


 On 14/11/2012 11:24 AM, Linda Alvord wrote:

 Kip's comments are helpful.

 Back to your problem, Mike:

 X=:?(2#n)$2  NB. generate random matrix of [0,1]
 X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
 ]X=:X+|:2*X
 0 0 0 0 1
 0 0 1 0 0
 0 2 0 0 0
 0 0 0 0 1
 2 0 0 2 0

 The three lines can be combined in one line.

 ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
 0 1 1 0 1
 2 0 1 0 1
 2 2 0 1 0
 0 0 2 0 0
 2 2 0 0 0

 Linda


 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com[mailto:
 programming-bounces@**forums.jsoftware.comprogramming-bounces@forums
 .jsoftware.com]
 On Behalf Of km
 Sent: Wednesday, November 14, 2012 4:29 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Responding to Mike's query about @

 Mathematical composition  f o g  means do g first, then f and is 
 expressed in J by the monadic use of  f @: g  or  [: f g .  The 
 monadic use of  f @ g  can surprise you, compare

 |.@:+: 1 2 3
 6 4 2
 |.@+: 1 2 3
 2 4 6

 -- the first means double vector 1 2 3 then reverse the resulting 
 vector, the second means double and reverse each scalar then assemble the 
 results.

 Kip Murray

 Sent from my iPad


 On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
 wrote:

  I can only give a personal response.  Maybe it is because I'm left
 handed.

 When I look at  ((@#)(i.n))@(0)  at or

 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-bounces@forum
 s.jsoftware.com 
 [mailto:programming-bounces@**forums.jsoftware.comprogramming-bounc
 e...@forums.jsoftware.com]
 On Behalf Of Mike
 Day
 Sent: Monday, November 12, 2012 6:40 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 But what's wrong with @ that's preferable with [:   ?(I think
 Th is has been asked before.)

 Aren't they both devices to represent what ordinary mathematicians
 just write as f g h ... for the composition of f g h ...   ?

 Since J cleverly allows hooks and forks and interprets unbracketed 
 trains of verbs as such,  it needs some other way to recognise 
 composition

Re: [Jprogramming] Arc consistency in J

2012-11-16 Thread Michal D.

Boss is Boss, I eventually arrived at the same (non-negative case) solution.

Thanks km for the explanation of @ vs @: which I'm starting to slowly get.

Linda: I think I prefer having it on three lines.  It better breaks down
the steps I'm trying to accomplish.  Maybe someday I'll be able to boil it
down to a single line ;-)

Raul: please let me know if we should still pursue your previous definition
in light of Mike's commentary.

Mike Day is right on with all his observations about what I'm trying to
accomplish.  Sorry for the long delay - I'm having trouble keeping up.
Notes:

(0) Interesting {:: vs { and 

(1) The J arc consistency algorithm I've presented is not AC-3 nor any of
the later AC algorithms.  AC-3 is simply another algorithm that
accomplishes the same thing.

(2) Using the approach I do with the C-tables allows massive parallelism.
In particular using mostly logical-and and logical-or operations on boolean
arrays allows a single assembly level operation to have 32 or 64 way
parallelism (or larger if using vector registers).

(3) A simpler algorithm that requires a single version of each C-table and
a revDom that reduces both it's input domains is possible but I haven't
gotten there yet.  I'm working on it along with code to randomly generate a
sudoku and generate the equivalent CSP.  It might be a while.

Cheers,

Mike


On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.ukwrote:

 Thanks,  but my questions were rhetorical!  I was merely trying to comment
 on Linda's apparent aversion to @ and @: and her preference for [: which
 she has justified in a later post.  I'm not the Mike who started this
 thread on arc consistency.

 Incidentally,  I also commented in that message on 11/11 (still in the
 history below) about Raul Miller's question concerning the domain matrix D.

 Mike


 On 14/11/2012 11:24 AM, Linda Alvord wrote:

 Kip's comments are helpful.

 Back to your problem, Mike:

 X=:?(2#n)$2  NB. generate random matrix of [0,1]
 X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
 ]X=:X+|:2*X
 0 0 0 0 1
 0 0 1 0 0
 0 2 0 0 0
 0 0 0 0 1
 2 0 0 2 0

 The three lines can be combined in one line.

 ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
 0 1 1 0 1
 2 0 1 0 1
 2 2 0 1 0
 0 0 2 0 0
 2 2 0 0 0

 Linda


 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com[mailto:
 programming-bounces@**forums.jsoftware.comprogramming-boun...@forums.jsoftware.com]
 On Behalf Of km
 Sent: Wednesday, November 14, 2012 4:29 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Responding to Mike's query about @

 Mathematical composition  f o g  means do g first, then f and is
 expressed in J by the monadic use of  f @: g  or  [: f g .  The monadic use
 of  f @ g  can surprise you, compare

 |.@:+: 1 2 3
 6 4 2
 |.@+: 1 2 3
 2 4 6

 -- the first means double vector 1 2 3 then reverse the resulting vector,
 the second means double and reverse each scalar then assemble the results.

 Kip Murray

 Sent from my iPad


 On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
 wrote:

  I can only give a personal response.  Maybe it is because I'm left
 handed.

 When I look at  ((@#)(i.n))@(0)  at or

 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com
 [mailto:programming-bounces@**forums.jsoftware.comprogramming-boun...@forums.jsoftware.com]
 On Behalf Of Mike
 Day
 Sent: Monday, November 12, 2012 6:40 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 But what's wrong with @ that's preferable with [:   ?(I think
 Th is has been asked before.)

 Aren't they both devices to represent what ordinary mathematicians
 just write as f g h ... for the composition of f g h ...   ?

 Since J cleverly allows hooks and forks and interprets unbracketed
 trains of verbs as such,  it needs some other way to recognise
 composition,  and that's what both @ (and @:) and [: do for us - so why
 avoid one or the other of them?   I agree it took a lot of time to get
 my head round the new way of seeing trains of verbs.

 Mike

 On 12/11/2012 7:57 AM, Linda Alvord wrote:

 Well, it was possible, once I managed to get the rank right. Thanks
 for providing hope that it could be done. Actually it is not too bad
 looking after all.

 A
 0 0 1 0 0
 0 0 0 0 0
 2 0 0 0 1
 0 0 0 0 1
 0 0 2 2 0

 adj=:((@#)(i.n))@(0)
 adj
 @#0 1 2 3 4@(0)
 adj A
 --TT---T-T---┐
 │2││0 4│4│2 3│
 L-++---+-+

 f=: 13 :'(0y)([:#)1 i.#y'
 f
 (0  ]) ([:  #)1 [: i. #
 f A
 --TT---T-T---┐
 │2││0 4│4│2 3│
 L-++---+-+

5!:4 'adj'
  -- 
  -- @ ---+- #
--  -+- 0 1 2 3 4
│
 -- @ -+ -- 0
L-  -+- 

 5!:4 'f'
  -- 0
--+- 
│ L

Re: [Jprogramming] Arc consistency in J

2012-11-16 Thread Raul Miller

If you are talking about my post on the 10th, where I proposed

arcn=:3 :0
  'D c1 X'=: y
  X1=. 1=X
  ([:+./1[: +./((|:c1) *1 2~ (|:X1) *1 2 ]) +. c1 *1 2~ X1 *1 2 ])^:_ D
)

... note that it works just fine when D is not square.

And all I got out of Mike's 11/11 message was that D might not be square.

Am I missing something?

-- 
Raul

P.S. In the above code, X1=. 1 = X assumes that X had only 2s and 0s
in the lower triangle.  Perhaps a better expression would have been X1
=. (*X) * /i./ $X

On Fri, Nov 16, 2012 at 9:44 PM, Michal D. michal.dobrog...@gmail.com wrote:
 Boss is Boss, I eventually arrived at the same (non-negative case) solution.

 Thanks km for the explanation of @ vs @: which I'm starting to slowly get.

 Linda: I think I prefer having it on three lines.  It better breaks down
 the steps I'm trying to accomplish.  Maybe someday I'll be able to boil it
 down to a single line ;-)

 Raul: please let me know if we should still pursue your previous definition
 in light of Mike's commentary.

 Mike Day is right on with all his observations about what I'm trying to
 accomplish.  Sorry for the long delay - I'm having trouble keeping up.
 Notes:

 (0) Interesting {:: vs { and 

 (1) The J arc consistency algorithm I've presented is not AC-3 nor any of
 the later AC algorithms.  AC-3 is simply another algorithm that
 accomplishes the same thing.

 (2) Using the approach I do with the C-tables allows massive parallelism.
 In particular using mostly logical-and and logical-or operations on boolean
 arrays allows a single assembly level operation to have 32 or 64 way
 parallelism (or larger if using vector registers).

 (3) A simpler algorithm that requires a single version of each C-table and
 a revDom that reduces both it's input domains is possible but I haven't
 gotten there yet.  I'm working on it along with code to randomly generate a
 sudoku and generate the equivalent CSP.  It might be a while.

 Cheers,

 Mike


 On Wed, Nov 14, 2012 at 3:11 PM, Mike Day mike_liz@tiscali.co.ukwrote:

 Thanks,  but my questions were rhetorical!  I was merely trying to comment
 on Linda's apparent aversion to @ and @: and her preference for [: which
 she has justified in a later post.  I'm not the Mike who started this
 thread on arc consistency.

 Incidentally,  I also commented in that message on 11/11 (still in the
 history below) about Raul Miller's question concerning the domain matrix D.

 Mike


 On 14/11/2012 11:24 AM, Linda Alvord wrote:

 Kip's comments are helpful.

 Back to your problem, Mike:

 X=:?(2#n)$2  NB. generate random matrix of [0,1]
 X=:X*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
 ]X=:X+|:2*X
 0 0 0 0 1
 0 0 1 0 0
 0 2 0 0 0
 0 0 0 0 1
 2 0 0 2 0

 The three lines can be combined in one line.

 ]X+|:2*X=:(?(2#n)$2)*(i.n)/i.**n
 0 1 1 0 1
 2 0 1 0 1
 2 2 0 1 0
 0 0 2 0 0
 2 2 0 0 0

 Linda


 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com[mailto:
 programming-bounces@**forums.jsoftware.comprogramming-boun...@forums.jsoftware.com]
 On Behalf Of km
 Sent: Wednesday, November 14, 2012 4:29 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Responding to Mike's query about @

 Mathematical composition  f o g  means do g first, then f and is
 expressed in J by the monadic use of  f @: g  or  [: f g .  The monadic use
 of  f @ g  can surprise you, compare

 |.@:+: 1 2 3
 6 4 2
 |.@+: 1 2 3
 2 4 6

 -- the first means double vector 1 2 3 then reverse the resulting vector,
 the second means double and reverse each scalar then assemble the results.

 Kip Murray

 Sent from my iPad


 On Nov 13, 2012, at 8:44 PM, Linda Alvord lindaalv...@verizon.net
 wrote:

  I can only give a personal response.  Maybe it is because I'm left
 handed.

 When I look at  ((@#)(i.n))@(0)  at or

 -Original Message-
 From: 
 programming-bounces@forums.**jsoftware.comprogramming-boun...@forums.jsoftware.com
 [mailto:programming-bounces@**forums.jsoftware.comprogramming-boun...@forums.jsoftware.com]
 On Behalf Of Mike
 Day
 Sent: Monday, November 12, 2012 6:40 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 But what's wrong with @ that's preferable with [:   ?(I think
 Th is has been asked before.)

 Aren't they both devices to represent what ordinary mathematicians
 just write as f g h ... for the composition of f g h ...   ?

 Since J cleverly allows hooks and forks and interprets unbracketed
 trains of verbs as such,  it needs some other way to recognise
 composition,  and that's what both @ (and @:) and [: do for us - so why
 avoid one or the other of them?   I agree it took a lot of time to get
 my head round the new way of seeing trains of verbs.

 Mike

 On 12/11/2012 7:57 AM, Linda Alvord wrote:

 Well, it was possible, once I managed to get the rank right. Thanks
 for providing hope that it could be done

Re: [Jprogramming] Arc consistency in J

2012-11-13 Thread Linda Alvord

I can only give a personal response.  Maybe it is because I'm left handed.

When I look at  ((@#)(i.n))@(0)  at or 

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day
Sent: Monday, November 12, 2012 6:40 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

But what's wrong with @ that's preferable with [:   ?(I think 
Th is has been asked before.)

Aren't they both devices to represent what ordinary mathematicians 
just write as f g h ... for the composition of f g h ...   ?

Since J cleverly allows hooks and forks and interprets unbracketed trains of
verbs as such,  it needs some other way to recognise composition,  and
that's what both @ (and @:) and [: do for us - so why 
avoid one or the other of them?   I agree it took a lot of time to get 
my head round the new way of seeing trains of verbs.

Mike

On 12/11/2012 7:57 AM, Linda Alvord wrote:
 Well, it was possible, once I managed to get the rank right. Thanks 
 for providing hope that it could be done. Actually it is not too bad 
 looking after all.

 A
 0 0 1 0 0
 0 0 0 0 0
 2 0 0 0 1
 0 0 0 0 1
 0 0 2 2 0

 adj=:((@#)(i.n))@(0)
 adj
 @#0 1 2 3 4@(0)
 adj A
 --TT---T-T---┐
 │2││0 4│4│2 3│
 L-++---+-+

 f=: 13 :'(0y)([:#)1 i.#y'
 f
 (0  ]) ([:  #)1 [: i. #
 f A
 --TT---T-T---┐
 │2││0 4│4│2 3│
 L-++---+-+

5!:4 'adj'
  -- 
  -- @ ---+- #
--  -+- 0 1 2 3 4
│
 -- @ -+ -- 0
L-  -+- 

 5!:4 'f'
  -- 0
--+- 
│ L- ]
│  -- [:
│ -+- 
 --+-  -+L- #
│ L- 1
│
│ -- [:
L-+- i.
  L- #

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike 
 Day
 Sent: Sunday, November 11, 2012 7:15 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 I don't think you can remove the @, although you may use the cap, [: , 
 instead,  but then you need to force the rank:
  ([:(#0 1 2 3@(0)))1 A
 +-++---+-+
 |2||0 3|2|
 +-++---+-+

 I don't like using 0 1 2 3 explicitly since it presumes you know the 
 dimension of A, so I prefer either
 adja =: * @# i.@#   NB. or use caps if @ is too horrible
  adja A
 +-++---+-+
 |2||0 3|2|
 +-++---+-+

 or

  adjI =: @I.@:*
  adjI A
 +-++---+-+
 |2||0 3|2|
 +-++---+-+

 I. is so useful that I've defined an I dfn in my Dyalog APL too!

 As for Raul's point about D,  I understood it to represent the domains 
 of the variables:  if there are m variables  and the domain of all 
 their possible values is i.n,  then 1 = D{~i,j means that variable 
 number i may have value j .  m and n are likely to be different.  So  
 iD is a boolean representing the a priori values that variable i might
have.
 The consistency algorithm apparently examines which of these a priori 
 values are consistent with the domains of the other variables given 
 certain unary and binary constraints which are also inputs to the problem.

 Michal's example had m=n which tends to mislead the casual reader!

 I believe The m*m A array points to which constraints apply,  so 
 0l=A{i,k means that binary constraint number l applies between variables
i and k.
 This is why A isn't just a boolean adjacency matrix nor do the entries 
 signify distances as they would in a weighted graph.

 I'm puzzled that the algorithm requires each binary relation to be 
 presented in both direct and transposed form  (this explains Michal's 
 need to patch in a new index (to a transposed C) in the lower triangle 
 of A for each index to a direct C in the upper triangle).  Perhaps the
later algorithms (arc-4...
 ?) deal with this difficulty.

 It strikes me that for a real problem,  concise relations such as x :
 y,  or 2x+3y5 can become pretty large and unwieldy C-tables, but 
 perhaps that's unavoidable when working in the integers.

 (The other) Mike

 On 11/11/2012 10:16 AM, Linda Alvord wrote:

 Mike, I think this will work as an alternative to  adj

   A
 0 0 1 0
 0 0 0 0
 2 0 0 1
 0 0 2 0
  adj
 @#0 1 2 3@(0)
  adj A
 --TT---T-┐
 │2││0 3│2│
 L-++---+--
  h
 0 1 2 3 @#~ 0  ]
  h A
 --TT---T-┐
 │2││0 3│2│
 L-++---+--

Can anyone remove the final  @  from  h  ?

 Linda

 -Original Message-
 From:programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul 
 Miller
 Sent: Saturday, November 10, 2012 12:44 PM 
 To:programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 On Sat, Nov 10, 2012 at 12:16 PM, Michal 
 D.michal.dobrog...@gmail.com
 wrote:

 Here X is telling us to use the constraint c1 (presumably b/c C is 
 not
 shown) between the variables 1 and 3 (0 based).  Likewise, use

Re: [Jprogramming] Arc consistency in J

2012-11-12 Thread Mike Day

But what's wrong with @ that's preferable with [:   ?(I think 
this has been asked before.)


Aren't they both devices to represent what ordinary mathematicians 
just write as f g h ... for the composition of f g h ...   ?


Since J cleverly allows hooks and forks and interprets unbracketed 
trains of verbs as such,  it needs some other way to recognise 
composition,  and that's what both @ (and @:) and [: do for us - so why 
avoid one or the other of them?   I agree it took a lot of time to get 
my head round the new way of seeing trains of verbs.


Mike

On 12/11/2012 7:57 AM, Linda Alvord wrote:

Well, it was possible, once I managed to get the rank right. Thanks for
providing hope that it could be done. Actually it is not too bad looking
after all.

A
0 0 1 0 0
0 0 0 0 0
2 0 0 0 1
0 0 0 0 1
0 0 2 2 0

adj=:((@#)(i.n))@(0)

adj
@#0 1 2 3 4@(0)
adj A
--TT---T-T---┐
│2││0 4│4│2 3│
L-++---+-+

f=: 13 :'(0y)([:#)1 i.#y'

f
(0  ]) ([:  #)1 [: i. #
f A
--TT---T-T---┐
│2││0 4│4│2 3│
L-++---+-+

   5!:4 'adj'
 -- 
 -- @ ---+- #
   --  -+- 0 1 2 3 4
   │
-- @ -+ -- 0
   L-  -+- 

5!:4 'f'

 -- 0
   --+- 
   │ L- ]
   │  -- [:
   │ -+- 
--+-  -+L- #
   │ L- 1
   │
   │ -- [:
   L-+- i.
 L- #

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day
Sent: Sunday, November 11, 2012 7:15 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

I don't think you can remove the @, although you may use the cap, [: ,
instead,  but then you need to force the rank:
 ([:(#0 1 2 3@(0)))1 A
+-++---+-+
|2||0 3|2|
+-++---+-+

I don't like using 0 1 2 3 explicitly since it presumes you know the
dimension of A, so I prefer either
adja =: * @# i.@#   NB. or use caps if @ is too horrible
 adja A
+-++---+-+
|2||0 3|2|
+-++---+-+

or

 adjI =: @I.@:*
 adjI A
+-++---+-+
|2||0 3|2|
+-++---+-+

I. is so useful that I've defined an I dfn in my Dyalog APL too!

As for Raul's point about D,  I understood it to represent the domains of
the variables:  if there are m variables  and the domain of all their
possible values is i.n,  then 1 = D{~i,j means that variable number i may
have value j .  m and n are likely to be different.  So  iD is a boolean
representing the a priori values that variable i might have.
The consistency algorithm apparently examines which of these a priori values
are consistent with the domains of the other variables given certain unary
and binary constraints which are also inputs to the problem.

Michal's example had m=n which tends to mislead the casual reader!

I believe The m*m A array points to which constraints apply,  so 0l=A{i,k
means that binary constraint number l applies between variables i and k.
This is why A isn't just a boolean adjacency matrix nor do the entries
signify distances as they would in a weighted graph.

I'm puzzled that the algorithm requires each binary relation to be presented
in both direct and transposed form  (this explains Michal's need to patch in
a new index (to a transposed C) in the lower triangle of A for each index to
a direct C in the upper triangle).  Perhaps the later algorithms (arc-4...
?) deal with this difficulty.

It strikes me that for a real problem,  concise relations such as x :
y,  or 2x+3y5 can become pretty large and unwieldy C-tables, but perhaps
that's unavoidable when working in the integers.

(The other) Mike

On 11/11/2012 10:16 AM, Linda Alvord wrote:

Mike, I think this will work as an alternative to  adj

  A
0 0 1 0
0 0 0 0
2 0 0 1
0 0 2 0
 adj
@#0 1 2 3@(0)
 adj A
--TT---T-┐
│2││0 3│2│
L-++---+--
 h
0 1 2 3 @#~ 0  ]
 h A
--TT---T-┐
│2││0 3│2│
L-++---+--
  
   Can anyone remove the final  @  from  h  ?


Linda
   


-Original Message-
From:programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul Miller
Sent: Saturday, November 10, 2012 12:44 PM To:programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

On Sat, Nov 10, 2012 at 12:16 PM, Michal D.michal.dobrog...@gmail.com
wrote:


Here X is telling us to use the constraint c1 (presumably b/c C is not
shown) between the variables 1 and 3 (0 based).  Likewise, use the
transpose going the other direction (3,1).

Ouch, you are correct, I did not specify C.  On retesting, though, it looks
like my results stay the same when I use:

arccon=:3 :0
 'D c1 X'=: y
 'n d'=: $D
 adj =: ((@#)(i.n)) @ (0)
 A =: adj X
 C=: a: , c1 ; (|:c1)
 ac =:  @ (1{) @ (revise^:_) @ ((i.n);)
 ac D
)

For longer scripts like this, I really need to get into the habit of
restarting J for every test.  So that probably means I should be using jhs.


Given the structure of X, only variables 1

Re: [Jprogramming] Arc consistency in J

2012-11-11 Thread Linda Alvord

   


 
Mike, I changed  f  as you suggest.

   n=: 5 
   A=:?(2#n)$2  NB. generate random matrix of [0,1]
   A=:A*(i.n)/i.n  NB. make it upper diagonal, zeros on diagonal
   ]A=:A+|:2*A 
0 0 1 0 0
0 0 0 0 0
2 0 0 1 1
0 0 2 0 1
0 0 2 2 0
   
   adj=:((@#)(i.n))@(0)
   adj
@#0 1 2 3 4@(0)
   adj Al
--TT-T---T---┐
│2││0 3 4│2 4│2 3│
L-++-+---+
   
   f=: 13 :'(0y)@#i.#y'
   f
(0  ]) @# [: i. #
   f A
--TT-T---T---┐
│2││0 3 4│2 4│2 3│
L-++-+---+
   

I'm still hoping to remove  @  and I guess it will be useful to deal with
rank as  Henry suggests. I think I'll take a second look at  A.  Thanks for
all your help.

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day
Sent: Sunday, November 11, 2012 7:15 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

I don't think you can remove the @, although you may use the cap, [: ,
instead,  but then you need to force the rank:
([:(#0 1 2 3@(0)))1 A
+-++---+-+
|2||0 3|2|
+-++---+-+

I don't like using 0 1 2 3 explicitly since it presumes you know the
dimension of A, so I prefer either
   adja =: * @# i.@#   NB. or use caps if @ is too horrible
adja A
+-++---+-+
|2||0 3|2|
+-++---+-+

or

adjI =: @I.@:*
adjI A
+-++---+-+
|2||0 3|2|
+-++---+-+

I. is so useful that I've defined an I dfn in my Dyalog APL too!

As for Raul's point about D,  I understood it to represent the domains of
the variables:  if there are m variables  and the domain of all their
possible values is i.n,  then 1 = D{~i,j means that variable number i may
have value j .  m and n are likely to be different.  So  iD is a boolean
representing the a priori values that variable i might have.  
The consistency algorithm apparently examines which of these a priori values
are consistent with the domains of the other variables given certain unary
and binary constraints which are also inputs to the problem.

Michal's example had m=n which tends to mislead the casual reader!

I believe The m*m A array points to which constraints apply,  so 0l=A{i,k
means that binary constraint number l applies between variables i and k.
This is why A isn't just a boolean adjacency matrix nor do the entries
signify distances as they would in a weighted graph.

I'm puzzled that the algorithm requires each binary relation to be presented
in both direct and transposed form  (this explains Michal's need to patch in
a new index (to a transposed C) in the lower triangle of A for each index to
a direct C in the upper triangle).  Perhaps the later algorithms (arc-4...
?) deal with this difficulty.

It strikes me that for a real problem,  concise relations such as x : 
y,  or 2x+3y5 can become pretty large and unwieldy C-tables, but perhaps
that's unavoidable when working in the integers.

(The other) Mike

On 11/11/2012 10:16 AM, Linda Alvord wrote:

Mike, I think this will work as an alternative to  adj

 A
0 0 1 0
0 0 0 0
2 0 0 1
0 0 2 0
adj
@#0 1 2 3@(0)
adj A
--TT---T-┐
│2││0 3│2│
L-++---+--
h
0 1 2 3 @#~ 0  ]
h A
--TT---T-┐
│2││0 3│2│
L-++---+--
 
  Can anyone remove the final  @  from  h  ?

Linda
  

-Original Message-
From:programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul Miller
Sent: Saturday, November 10, 2012 12:44 PM To:programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

On Sat, Nov 10, 2012 at 12:16 PM, Michal D.michal.dobrog...@gmail.com
wrote:

 Here X is telling us to use the constraint c1 (presumably b/c C is not
 shown) between the variables 1 and 3 (0 based).  Likewise, use the 
 transpose going the other direction (3,1).

Ouch, you are correct, I did not specify C.  On retesting, though, it looks
like my results stay the same when I use:

arccon=:3 :0
'D c1 X'=: y
'n d'=: $D
adj =: ((@#)(i.n)) @ (0)
A =: adj X
C=: a: , c1 ; (|:c1)
ac =:  @ (1{) @ (revise^:_) @ ((i.n);)
ac D
)

For longer scripts like this, I really need to get into the habit of
restarting J for every test.  So that probably means I should be using jhs.

 Given the structure of X, only variables 1 and 3 can possibly change.
 So if they are all changing something is definitely wrong.

This line of thinking does not make sense to me.  I thought that the
requirement was that a 1 in D exists only when there is a valid relationship
along a relevant arc.  If a 1 in D can also exist in the absence of any
relevant arc, I am back to needing a description of the algorithm.

 Unfortunately I've run out of time to read the rest of your response 
 but hopefully I can get through it soon.  I've also wanted to write a 
 simpler version of the algorithm where the right argument of ac is 
 only D and it runs through all the arcs in the problem instead of 
 trying to be smart about which ones could have changed.

Yes... I am currently suspicious

Re: [Jprogramming] Arc consistency in J

2012-11-10 Thread Linda Alvord

Mike, I think the  0=  is not necessary since both tables are random anyway.

X =: 0= ? (2$n)$2   NB. generate random matrix of [0,1]
   ]X   =: ? (2$n)$2  
1 0 0 0
1 0 0 1
0 1 1 0
1 0 1 0
   0=X 
0 1 1 1
0 1 1 0
1 0 0 1
0 1 0 1

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Linda Alvord
Sent: Saturday, November 10, 2012 2:35 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Kip suggested doing some testing.  Over time you will develop all kinds of
testing skill to answer questions for yourself.  Here's a sample I used on
#$  

In the early days all the explanations like the dictionary were prepared to
be printed and thus are extremely terse.  One of the joys of communication
on the forum is that you can provide a long series of samples which can be
read easily and are just as easily disposed of if not useful. 

So here is a long version:

   rank1=:#$
   rank1
# $
   rank2=:[:#$
   rank2
[: # $
   rank3=:#@$
   rank3
#@$
   
   (#$ 7)-:rank1 7
0
   (#$ 7)-:rank2 7
1
   (#$ 7)-:rank3 7
1
   
   5!:4 'rank1'
  -- #
--+- $
   5!:4 'rank2'
  -- [:
--+- #
  L- $ 
   5!:4 'rank3'
  -- #
-- @ -+- $
   
   #$ A=:i.3 2 5
3
   f=: 13 :'#$y'
   f
[: # $
   5!:4 'f'
  -- [:
--+- #
  L- $ 
   
   f A
3
  
   rank1 Ayo
|length error: rank1
|   rank1 A
   rank2 A
3
   rank3 A
3
   
Conclusion:  As a mathematician you get the answer you want like  #$A . When
it works, you can write  f  .  Earlier there was a discussion about the
default that J uses.  To me it appears to be  [: # $ .

Now that I understand the first couple of lines of your development of your
Sudoku solver, I'm anxious to continue.

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Saturday, November 10, 2012 12:21 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Some nice things learned: ?~ instead of (?]).

Bo: is it true that (3$3) is not a list of integers but (3#3) is?

Fascinating discussion on ?/... so much intricatness.

Mike

On Thu, Nov 8, 2012 at 11:12 PM, Linda Alvord
lindaalv...@verizon.netwrote:

 The dawn finally broke.  It's a deal!

 3 10 4 ? 10 10 10
 8 2 5 0 0 0 0 0 0 0
 4 1 0 9 3 7 6 8 5 2
 9 0 1 8 0 0 0 0 0 0

 3 10 4 ?/ 10 10 10
 6 0 5 0 0 0 0 0 0 0
 9 5 0 0 0 0 0 0 0 0
 2 6 1 0 0 0 0 0 0 0

 8 4 9 5 6 1 3 0 2 7
 9 3 5 8 0 6 4 7 1 2
 1 6 8 0 4 2 5 3 9 7

 1 9 5 7 0 0 0 0 0 0
 3 9 8 0 0 0 0 0 0 0
 1 3 7 0 0 0 0 0 0 0

 So:

8 8 8 8 8 ? 8 8 8 8 8
 0 1 7 6 5 3 4 2
 0 7 3 2 5 1 4 6
 5 0 7 6 4 1 3 2
 6 1 5 7 3 0 2 4
 4 7 3 5 6 0 2 1

 There is only one zero in each row.

 It is nice when the fog lifts.  Thanks to everyone who helped me.

f=:0 = # ? #
5 f 8
 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 1 0
 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 1
 0 0 0 0 0 1 0 0

 5!:4 'f'
   -- 0
   +- =
 --+   -- #
   L---+- ?
   L- #


 Quite a pretty picture.

 Linda



 -Origineal Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boune...@forums.jsoftware.com] On Behalf Of Peter B.
 Kessler
 Sent: Thursday, November 08, 2012 9:24 PM
 To: programm...@jsoftware.comn
 Subject: Re: [Jprogramming] Arc consistency in J

 The shape of the arguments to the verb that's being inserted is 3x4, 
 so when that verb returns an atom, as dyadic + does, the shape of the 
 result is 3x4.
 But dyadic ? (Deal[1]) doesn't return an atom: it returns a list of 
 the number of items of its left argument.  So for each of the 3x4 
 applications of dyadic ? returns a list of 3 elements, so the shape of 
 the result is 3x4x3.  There's probably a more official way to say 
 that, but that's my model of J, so far.

 It might be slightly less confusing to use arguments that aren't also 
 the shapes of those arguments.  E.g.,

 The left argument is a list of length 2, and the right argument is a 
 list of length 4, so there are 2x4 pairs between each of which is 
 inserted a Deal.
 Each Deal chooses 3 items from i. 6 without replacement.

3 3 ?/ 6 6 6 6
 5 0 2
 3 5 0
 1 4 5
 1 0 3

 0 3 2
 0 5 2
 1 2 4
 3 0 1

 so the shape of the result is 2x4x3.

$ 3 3 ?/ 6 6 6 6
 2 4 3

 Does that seem less odd?

 ... peter

 [1] http://www.jsoftware.com/help/dictionary/d640.htm

 Linda Alvord wrote:
 f=: 13 :'0=?~ x#y'
 f
  0 = [: ?~ #
 
  Maybe someday I'll just write expressions like yours easily.   The
 idea
  seems so simple now.
 
  However, I discovered this oddity:
 
  3 3 3 +/ 4 4 4 4
  7 7 7 7
  7 7 7 7
  7 7 7 7
 
 3 3 3 ?/ 4 4 4 4
  3 2 1
  1 3 0
  2 3 1
  3 2 1
 
  2 3 1
  2 1 3
  1 3 0
  1 0 2
 
  2 0 3
  0 3 1
  0 1 3
  2 3 1
 
  This seems odd:
 
  Linda
 
  -Original  Message-
  From: programming-boun...@forums.jsoftware.com
  [mailto:programming

Re: [Jprogramming] Arc consistency in J

2012-11-10 Thread Don Guinn

   3$3
3 3 3
   3#3
3 3 3
   (3#3)-:3$3
1
   3$3 4
3 4 3
   3#3 4
3 3 3 4 4 4

On Fri, Nov 9, 2012 at 10:21 PM, Michal D. michal.dobrog...@gmail.comwrote:

 Some nice things learned: ?~ instead of (?]).

 Bo: is it true that (3$3) is not a list of integers but (3#3) is?

 Fascinating discussion on ?/... so much intricatness.

 Mike


--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-10 Thread Raul Miller

I have been struggling with understanding this program, and I have an
issue that I need clarified:

   D
1 0 0 1
0 1 0 1
1 0 1 0
1 1 0 0
   c1
1 0 1 0
1 1 1 0
1 1 1 0
1 0 0 0
   X
0 0 0 0
0 0 0 1
0 0 0 0
0 2 0 0

Here, I am thinking that an arc consistent result can only have 1
values in half of the rows of D.  But ac gives me 1 values in all of
the rows of D.

Also, consider this case:

   D
0 1 1 0
1 0 1 0
0 0 1 1
0 1 0 1
   c1
1 0 1 1
1 0 1 1
1 0 0 1
0 1 1 0
   X
0 0 1 1
0 0 1 0
2 2 0 0
2 0 0 0

Here, ac gives me:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 1

But I think the result should be
0 1 1 0
1 0 1 0
0 0 1 1
0 1 0 1

The difference is in the 0 value in the second row and the 2 value
in the third row.

If I understand the algorithm properly: according to X, relationships
are considered between the third row and either the first or second
row.  And, according to c1, 0 comp 2 is valid.

In other words, I think this might be a valid implementation of arc consistency:

arcn=:3 :0
  'D c1 X'=: y
  X1=. 1=X
  ([:+./1[: +./((|:c1) *1 2~ (|:X1) *1 2 ]) +. c1 *1 2~ X1 *1 2 ])^:_ D
)


for reference, here's my workalike cover for ac (except, of course,
the results are not the same):

arccon=:3 :0
   'D c1 X'=: y
   'n d'=: $D
   adj =: ((@#)(i.n)) @ (0)
   A =: adj X
   ac =:  @ (1{) @ (revise^:_) @ ((i.n);)
   ac D
)


I do not want to concern myself with efficiency issues until after I
am sure I understand the algorithm properly.  (But making c1 and X
sparse might be appropriate, in some contexts.)

If I have made a mistake here, I'd greatly appreciate an explanation
of where I went wrong.

Thanks,

-- 
Raul

On Fri, Nov 2, 2012 at 1:01 AM, Michal D. michal.dobrog...@gmail.com wrote:
 Hi All,

 I've managed to write my first not-completely-trivial program in J.  It
 implements an arc consistency algorithm (
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I would
 appreciate any comments regarding style, what I'm doing wrong in J or how
 to improve the code.  I also have a couple of questions of my own:

 1) how do I avoid @ especially once we remove explicit arguments?
 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
 3) Is a boxed value always a pointer? One could imagine implementing
 'ragged' arrays without pointers.
 4) Is there a good way to have named variables (ie. avoid getx, gety)?
 5) Why is a hook the default and not composition?

 Code at: http://pastebin.com/k4XuKfFi

 Cheers!

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-10 Thread Raul Miller

On Sat, Nov 10, 2012 at 12:16 PM, Michal D. michal.dobrog...@gmail.com wrote:
 Here X is telling us to use the constraint c1 (presumably b/c C is not
 shown) between the variables 1 and 3 (0 based).  Likewise, use the
 transpose going the other direction (3,1).

Ouch, you are correct, I did not specify C.  On retesting, though, it
looks like my results stay the same when I use:

arccon=:3 :0
   'D c1 X'=: y
   'n d'=: $D
   adj =: ((@#)(i.n)) @ (0)
   A =: adj X
   C=: a: , c1 ; (|:c1)
   ac =:  @ (1{) @ (revise^:_) @ ((i.n);)
   ac D
)

For longer scripts like this, I really need to get into the habit of
restarting J for every test.  So that probably means I should be using
jhs.

 Given the structure of X, only variables 1 and 3 can possibly change. So if
 they are all changing something is definitely wrong.

This line of thinking does not make sense to me.  I thought that the
requirement was that a 1 in D exists only when there is a valid
relationship along a relevant arc.  If a 1 in D can also exist in the
absence of any relevant arc, I am back to needing a description of the
algorithm.

 Unfortunately I've run out of time to read the rest of your response but
 hopefully I can get through it soon.  I've also wanted to write a simpler
 version of the algorithm where the right argument of ac is only D and it
 runs through all the arcs in the problem instead of trying to be smart
 about which ones could have changed.

Yes... I am currently suspicious of the AC-3 algorithm.

In the case of symmetric consistency, I think that it's unnecessary
complexity, because the system converges on the initial iteration.

In the case of asymmetric consistency, I think that the work involved
in maintaining the data structures needed for correctness will almost
always exceed the work saved.

But I could be wrong.  I am not sure yet if I understand the
underlying algorithm!

-- 
Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-09 Thread km

About 3$3 and 3#3 I suggest you experiment.  Type 3$3 then type 3#3 .  Next 
type $ 3$3 and $ 3#3 .  What do you learn?  The following will help you learn 
about $ .

http://www.jsoftware.com/docs/help701/dictionary/d210.htm

Kip Murray

Sent from my iPad


On Nov 9, 2012, at 11:21 PM, Michal D. michal.dobrog...@gmail.com wrote:

 Some nice things learned: ?~ instead of (?]).
 
 Bo: is it true that (3$3) is not a list of integers but (3#3) is?
 
 Fascinating discussion on ?/... so much intricatness.
 
 Mike
 
 On Thu, Nov 8, 2012 at 11:12 PM, Linda Alvord lindaalv...@verizon.netwrote:
 
 The dawn finally broke.  It's a deal!
 
3 10 4 ? 10 10 10
 8 2 5 0 0 0 0 0 0 0
 4 1 0 9 3 7 6 8 5 2
 9 0 1 8 0 0 0 0 0 0
 
3 10 4 ?/ 10 10 10
 6 0 5 0 0 0 0 0 0 0
 9 5 0 0 0 0 0 0 0 0
 2 6 1 0 0 0 0 0 0 0
 
 8 4 9 5 6 1 3 0 2 7
 9 3 5 8 0 6 4 7 1 2
 1 6 8 0 4 2 5 3 9 7
 
 1 9 5 7 0 0 0 0 0 0
 3 9 8 0 0 0 0 0 0 0
 1 3 7 0 0 0 0 0 0 0
 
 So:
 
   8 8 8 8 8 ? 8 8 8 8 8
 0 1 7 6 5 3 4 2
 0 7 3 2 5 1 4 6
 5 0 7 6 4 1 3 2
 6 1 5 7 3 0 2 4
 4 7 3 5 6 0 2 1
 
 There is only one zero in each row.
 
 It is nice when the fog lifts.  Thanks to everyone who helped me.
 
   f=:0 = # ? #
   5 f 8
 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 1 0
 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 1
 0 0 0 0 0 1 0 0
 
 5!:4 'f'
  -- 0
  +- =
 --+   -- #
  L---+- ?
  L- #
 
 
 Quite a pretty picture.
 
 Linda
 
 
 
 -Origineal Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boune...@forums.jsoftware.com] On Behalf Of Peter B.
 Kessler
 Sent: Thursday, November 08, 2012 9:24 PM
 To: programm...@jsoftware.comn
 Subject: Re: [Jprogramming] Arc consistency in J
 
 The shape of the arguments to the verb that's being inserted is 3x4, so
 when
 that verb returns an atom, as dyadic + does, the shape of the result is
 3x4.
 But dyadic ? (Deal[1]) doesn't return an atom: it returns a list of the
 number of items of its left argument.  So for each of the 3x4 applications
 of dyadic ? returns a list of 3 elements, so the shape of the result is
 3x4x3.  There's probably a more official way to say that, but that's my
 model of J, so far.
 
 It might be slightly less confusing to use arguments that aren't also the
 shapes of those arguments.  E.g.,
 
 The left argument is a list of length 2, and the right argument is a list
 of
 length 4, so there are 2x4 pairs between each of which is inserted a Deal.
 Each Deal chooses 3 items from i. 6 without replacement.
 
   3 3 ?/ 6 6 6 6
5 0 2
3 5 0
1 4 5
1 0 3
 
0 3 2
0 5 2
1 2 4
3 0 1
 
 so the shape of the result is 2x4x3.
 
   $ 3 3 ?/ 6 6 6 6
2 4 3
 
 Does that seem less odd?
 
... peter
 
 [1] http://www.jsoftware.com/help/dictionary/d640.htm
 
 Linda Alvord wrote:
   f=: 13 :'0=?~ x#y'
   f
 0 = [: ?~ #
 
 Maybe someday I'll just write expressions like yours easily.   The
 idea
 seems so simple now.
 
 However, I discovered this oddity:
 
3 3 3 +/ 4 4 4 4
 7 7 7 7
 7 7 7 7
 7 7 7 7
 
   3 3 3 ?/ 4 4 4 4
 3 2 1
 1 3 0
 2 3 1
 3 2 1
 
 2 3 1
 2 1 3
 1 3 0
 1 0 2
 
 2 0 3
 0 3 1
 0 1 3
 2 3 1
 
 This seems odd:
 
 Linda
 
 -Original  Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Bo
 Jacoby
 Sent: Thursday, November 08, 2012 4:46 AM
 sTo: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J
 
 Linda, stick to integer arithmetic:
   5 (0=[:?~#) 8
 0 0 0 0 0 0 1 0
 1 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0
 0 0 0 1 0 0 0 0
 0 0 0 0 0 1 0 0
 - Bo
 
 
 
 
 
 Fra: Linda Alvord lindaalv...@verizon.net
 Til: programm...@jsoftware.com
 Sendt: 10:10 torsdag den 8. november 2012
 Emne: Re: [Jprogramming] Arc consistency in J
 
   ee=:(]%2)  ?~@$
   ee
 0.5  ?~@$
   ff=: 13 :'0.5  ?~x$y'
   ff
 0.5  [: ?~ $
   5 ff 8
 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 1
 0 0 0 0 1 0 0 0
 0 1 0 0 0 0 0 0
 0 0 1 0 0 0 0 0
 
 J is so smart, it eliminate the need for  *
 
   hh=: 13 :' ?~x$y'
   hh
 [: ?~ $
   ]A=:5 hh 8
 4 7 1 6 0 5 3 2
 4 2 3 1 5 7 0 6
 7 3 5 4 1 2 6 0
 5 3 2 4 1 7 6 0
 2 5 4 0 3 6 7 1
   0.5  A
 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 1
 0 0 0 0 0 0 0 1
 0 0 0 1 0 0 0 0
 
 Mind boggling!
 
 Linda
 
 
 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon
 McCormick
 Sent: Wednesday, November 07, 2012 12:56 PM
 To: J-programming forum
 Subject: Re: [Jprogramming] Arc consistency in J
 
 At first glance, I thought the right tine of this fork
   (2 %~ ])  [: (? ]) $
 could be replaced by an idiom I frequently use
   (?@$)
 but then realized that what we need is
   (?~@$)
 so dd can be written as
   (]%2)  ?~@$
 
 
 On Wed, Nov 7, 2012 at 1:31 AM, Michal D.
 michal.dobrog...@gmail.comwrote:
 Thanks Roger, that makes sense now.  The history of J is one of it`s
 intriguing aspects for sure.
 
 Re: Linda: I would call

Re: [Jprogramming] Arc consistency in J

2012-11-09 Thread Linda Alvord

Kip suggested doing some testing.  Over time you will develop all kinds of
testing skill to answer questions for yourself.  Here's a sample I used on
#$  

In the early days all the explanations like the dictionary were prepared to
be printed and thus are extremely terse.  One of the joys of communication
on the forum is that you can provide a long series of samples which can be
read easily and are just as easily disposed of if not useful. 

So here is a long version:

   rank1=:#$
   rank1
# $
   rank2=:[:#$
   rank2
[: # $
   rank3=:#@$
   rank3
#@$
   
   (#$ 7)-:rank1 7
0
   (#$ 7)-:rank2 7
1
   (#$ 7)-:rank3 7
1
   
   5!:4 'rank1'
  -- #
--+- $
   5!:4 'rank2'
  -- [:
--+- # 
  L- $ 
   5!:4 'rank3'
  -- #
-- @ -+- $
   
   #$ A=:i.3 2 5
3
   f=: 13 :'#$y'
   f
[: # $
   5!:4 'f'
  -- [:
--+- # 
  L- $ 
   
   f A
3
  
   rank1 Ayo
|length error: rank1
|   rank1 A
   rank2 A
3
   rank3 A
3
   
Conclusion:  As a mathematician you get the answer you want like  #$A . When
it works, you can write  f  .  Earlier there was a discussion about the
default that J uses.  To me it appears to be  [: # $ .

Now that I understand the first couple of lines of your development of your
Sudoku solver, I'm anxious to continue.

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Saturday, November 10, 2012 12:21 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Some nice things learned: ?~ instead of (?]).

Bo: is it true that (3$3) is not a list of integers but (3#3) is?

Fascinating discussion on ?/... so much intricatness.

Mike

On Thu, Nov 8, 2012 at 11:12 PM, Linda Alvord
lindaalv...@verizon.netwrote:

 The dawn finally broke.  It's a deal!

 3 10 4 ? 10 10 10
 8 2 5 0 0 0 0 0 0 0
 4 1 0 9 3 7 6 8 5 2
 9 0 1 8 0 0 0 0 0 0

 3 10 4 ?/ 10 10 10
 6 0 5 0 0 0 0 0 0 0
 9 5 0 0 0 0 0 0 0 0
 2 6 1 0 0 0 0 0 0 0

 8 4 9 5 6 1 3 0 2 7
 9 3 5 8 0 6 4 7 1 2
 1 6 8 0 4 2 5 3 9 7

 1 9 5 7 0 0 0 0 0 0
 3 9 8 0 0 0 0 0 0 0
 1 3 7 0 0 0 0 0 0 0

 So:

8 8 8 8 8 ? 8 8 8 8 8
 0 1 7 6 5 3 4 2
 0 7 3 2 5 1 4 6
 5 0 7 6 4 1 3 2
 6 1 5 7 3 0 2 4
 4 7 3 5 6 0 2 1

 There is only one zero in each row.

 It is nice when the fog lifts.  Thanks to everyone who helped me.

f=:0 = # ? #
5 f 8
 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 1 0
 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 1
 0 0 0 0 0 1 0 0

 5!:4 'f'
   -- 0
   +- =
 --+   -- #
   L---+- ?
   L- #


 Quite a pretty picture.

 Linda



 -Origineal Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boune...@forums.jsoftware.com] On Behalf Of Peter B.
 Kessler
 Sent: Thursday, November 08, 2012 9:24 PM
 To: programm...@jsoftware.comn
 Subject: Re: [Jprogramming] Arc consistency in J

 The shape of the arguments to the verb that's being inserted is 3x4, 
 so when that verb returns an atom, as dyadic + does, the shape of the 
 result is 3x4.
 But dyadic ? (Deal[1]) doesn't return an atom: it returns a list of 
 the number of items of its left argument.  So for each of the 3x4 
 applications of dyadic ? returns a list of 3 elements, so the shape of 
 the result is 3x4x3.  There's probably a more official way to say 
 that, but that's my model of J, so far.

 It might be slightly less confusing to use arguments that aren't also 
 the shapes of those arguments.  E.g.,

 The left argument is a list of length 2, and the right argument is a 
 list of length 4, so there are 2x4 pairs between each of which is 
 inserted a Deal.
 Each Deal chooses 3 items from i. 6 without replacement.

3 3 ?/ 6 6 6 6
 5 0 2
 3 5 0
 1 4 5
 1 0 3

 0 3 2
 0 5 2
 1 2 4
 3 0 1

 so the shape of the result is 2x4x3.

$ 3 3 ?/ 6 6 6 6
 2 4 3

 Does that seem less odd?

 ... peter

 [1] http://www.jsoftware.com/help/dictionary/d640.htm

 Linda Alvord wrote:
 f=: 13 :'0=?~ x#y'
 f
  0 = [: ?~ #
 
  Maybe someday I'll just write expressions like yours easily.   The
 idea
  seems so simple now.
 
  However, I discovered this oddity:
 
  3 3 3 +/ 4 4 4 4
  7 7 7 7
  7 7 7 7
  7 7 7 7
 
 3 3 3 ?/ 4 4 4 4
  3 2 1
  1 3 0
  2 3 1
  3 2 1
 
  2 3 1
  2 1 3
  1 3 0
  1 0 2
 
  2 0 3
  0 3 1
  0 1 3
  2 3 1
 
  This seems odd:
 
  Linda
 
  -Original  Message-
  From: programming-boun...@forums.jsoftware.com
  [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Bo 
  Jacoby
  Sent: Thursday, November 08, 2012 4:46 AM
  sTo: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  Linda, stick to integer arithmetic:
 5 (0=[:?~#) 8
  0 0 0 0 0 0 1 0
  1 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0
  0 0 0 1 0 0 0 0
  0 0 0 0 0 1 0 0
  - Bo
 
 
 
 
  
  Fra: Linda Alvord lindaalv...@verizon.net
  Til: programm...@jsoftware.com
  Sendt: 10:10 torsdag den 8. november 2012
  Emne: Re

Re: [Jprogramming] Arc consistency in J

2012-11-08 Thread Linda Alvord

   ee=:(]%2)  ?~@$
   ee
0.5  ?~@$
   ff=: 13 :'0.5  ?~x$y'
   ff
0.5  [: ?~ $
   5 ff 8
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0

J is so smart, it eliminate the need for  *  

   hh=: 13 :' ?~x$y'
   hh
[: ?~ $
   ]A=:5 hh 8
4 7 1 6 0 5 3 2
4 2 3 1 5 7 0 6
7 3 5 4 1 2 6 0
5 3 2 4 1 7 6 0
2 5 4 0 3 6 7 1
   0.5  A
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
  
Mind boggling!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon
McCormick
Sent: Wednesday, November 07, 2012 12:56 PM
To: J-programming forum
Subject: Re: [Jprogramming] Arc consistency in J

At first glance, I thought the right tine of this fork
   (2 %~ ])  [: (? ]) $
could be replaced by an idiom I frequently use
   (?@$)
but then realized that what we need is
   (?~@$)
so dd can be written as
   (]%2)  ?~@$


On Wed, Nov 7, 2012 at 1:31 AM, Michal D. michal.dobrog...@gmail.comwrote:

 Thanks Roger, that makes sense now.  The history of J is one of it`s 
 intriguing aspects for sure.

 Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But what 
 do I know? ;-)

 Mike

 On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui rogerhui.can...@gmail.com
 wrote:

  'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'
 (noun_
  is a constant verb whose result is noun).  
  http://keiapl.org/anec/#nvv
 
  'verb verb noun' can not be made into a fork because 'verb noun' 
  already has an interpretation (*viz*., apply verb to noun).
 
 
  On Tue, Nov 6, 2012 at 8:47 AM, Michal D. 
  michal.dobrog...@gmail.com
  wrote:
 
Change from a Noun to a verb, view its tacit version and apply 
it to
   data:
   
dd=: 13 :'(y%2)  (?]) x$y'
   
dd
(2 %~ ])  [: (? ]) $
   
  
   That is quite cool.  I'm surprised that you can automatically get 
   the
  tacit
   definition.  Does this work for any explicitly defined verb?
  
   I'm also surprised at the way %~ came out.  Do left hand arguments 
   not require a  to bind the argument?  It is strange to me that 
   (1) works
 but
   (2) does not.  It seems to me that (3) is the logical way to 
   phrase
  either
   of them (ie. a fork with a constant right / left side).  To 
   reiterate,
  why
   does (1) work?
  
   (1)(2 %~ ])  [: (? ]) $
   (2)(] % 2)  [: (? ]) $
   (3a)   (2: %~ ])  [: (? ]) $
   (3b)   (] %~ 2:)  [: (? ]) $
   (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me out
  again)!
   (4b)   ([: %2 ])  [: (? ]) $   NB. correct
  
   Cheers,
  
   Mike
   --
    For information about J forums see 
   http://www.jsoftware.com/forums.htm
  
  
  -- For information about J forums see 
  http://www.jsoftware.com/forums.htm
 
 --
 For information about J forums see http://www.jsoftware.com/forums.htm




--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-08 Thread Bo Jacoby

Linda, stick to integer arithmetic:
   5 (0=[:?~#) 8
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
- Bo





 Fra: Linda Alvord lindaalv...@verizon.net
Til: programm...@jsoftware.com 
Sendt: 10:10 torsdag den 8. november 2012
Emne: Re: [Jprogramming] Arc consistency in J
 
   ee=:(]%2)  ?~@$
   ee
0.5  ?~@$
   ff=: 13 :'0.5  ?~x$y'
   ff
0.5  [: ?~ $
   5 ff 8
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0

J is so smart, it eliminate the need for  *  

   hh=: 13 :' ?~x$y'
   hh
[: ?~ $
   ]A=:5 hh 8
4 7 1 6 0 5 3 2
4 2 3 1 5 7 0 6
7 3 5 4 1 2 6 0
5 3 2 4 1 7 6 0
2 5 4 0 3 6 7 1
   0.5  A
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
      
Mind boggling!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon
McCormick
Sent: Wednesday, November 07, 2012 12:56 PM
To: J-programming forum
Subject: Re: [Jprogramming] Arc consistency in J

At first glance, I thought the right tine of this fork
   (2 %~ ])  [: (? ]) $
could be replaced by an idiom I frequently use
   (?@$)
but then realized that what we need is
   (?~@$)
so dd can be written as
   (]%2)  ?~@$


On Wed, Nov 7, 2012 at 1:31 AM, Michal D. michal.dobrog...@gmail.comwrote:

 Thanks Roger, that makes sense now.  The history of J is one of it`s 
 intriguing aspects for sure.

 Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But what 
 do I know? ;-)

 Mike

 On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui rogerhui.can...@gmail.com
 wrote:

  'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'
 (noun_
  is a constant verb whose result is noun).  
  http://keiapl.org/anec/#nvv
 
  'verb verb noun' can not be made into a fork because 'verb noun' 
  already has an interpretation (*viz*., apply verb to noun).
 
 
  On Tue, Nov 6, 2012 at 8:47 AM, Michal D. 
  michal.dobrog...@gmail.com
  wrote:
 
Change from a Noun to a verb, view its tacit version and apply 
it to
   data:
   
        dd=: 13 :'(y%2)  (?]) x$y'
   
        dd
(2 %~ ])  [: (? ]) $
   
  
   That is quite cool.  I'm surprised that you can automatically get 
   the
  tacit
   definition.  Does this work for any explicitly defined verb?
  
   I'm also surprised at the way %~ came out.  Do left hand arguments 
   not require a  to bind the argument?  It is strange to me that 
   (1) works
 but
   (2) does not.  It seems to me that (3) is the logical way to 
   phrase
  either
   of them (ie. a fork with a constant right / left side).  To 
   reiterate,
  why
   does (1) work?
  
   (1)    (2 %~ ])  [: (? ]) $
   (2)    (] % 2)  [: (? ]) $
   (3a)   (2: %~ ])  [: (? ]) $
   (3b)   (] %~ 2:)  [: (? ]) $
   (4a)   (%2 ])  [: (? ]) $      NB. incorrect (hook caught me out
  again)!
   (4b)   ([: %2 ])  [: (? ]) $   NB. correct
  
   Cheers,
  
   Mike
   --
    For information about J forums see 
   http://www.jsoftware.com/forums.htm
  
  
  -- For information about J forums see 
  http://www.jsoftware.com/forums.htm
 
 --
 For information about J forums see http://www.jsoftware.com/forums.htm




--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm



--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-08 Thread Linda Alvord

   f=: 13 :'0=?~ x#y'
   f
0 = [: ?~ # 

Maybe someday I'll just write expressions like yours easily.   The idea
seems so simple now.

However, I discovered this oddity:

3 3 3 +/ 4 4 4 4
7 7 7 7
7 7 7 7
7 7 7 7
   
   3 3 3 ?/ 4 4 4 4
3 2 1
1 3 0
2 3 1
3 2 1

2 3 1
2 1 3
1 3 0
1 0 2

2 0 3
0 3 1
0 1 3
2 3 1
   
This seems odd:

Linda

-Original  Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Bo Jacoby
Sent: Thursday, November 08, 2012 4:46 AM
sTo: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Linda, stick to integer arithmetic:
   5 (0=[:?~#) 8
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
- Bo





 Fra: Linda Alvord lindaalv...@verizon.net
Til: programm...@jsoftware.com
Sendt: 10:10 torsdag den 8. november 2012
Emne: Re: [Jprogramming] Arc consistency in J
 
   ee=:(]%2)  ?~@$
   ee
0.5  ?~@$
   ff=: 13 :'0.5  ?~x$y'
   ff
0.5  [: ?~ $
   5 ff 8
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0

J is so smart, it eliminate the need for  *

   hh=: 13 :' ?~x$y'
   hh
[: ?~ $
   ]A=:5 hh 8
4 7 1 6 0 5 3 2
4 2 3 1 5 7 0 6
7 3 5 4 1 2 6 0
5 3 2 4 1 7 6 0
2 5 4 0 3 6 7 1
   0.5  A
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
      
Mind boggling!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon 
McCormick
Sent: Wednesday, November 07, 2012 12:56 PM
To: J-programming forum
Subject: Re: [Jprogramming] Arc consistency in J

At first glance, I thought the right tine of this fork
   (2 %~ ])  [: (? ]) $
could be replaced by an idiom I frequently use
   (?@$)
but then realized that what we need is
   (?~@$)
so dd can be written as
   (]%2)  ?~@$


On Wed, Nov 7, 2012 at 1:31 AM, Michal D.
michal.dobrog...@gmail.comwrote:

 Thanks Roger, that makes sense now.  The history of J is one of it`s 
 intriguing aspects for sure.

 Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But what 
 do I know? ;-)

 Mike

 On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui rogerhui.can...@gmail.com
 wrote:

  'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'
 (noun_
  is a constant verb whose result is noun). 
  http://keiapl.org/anec/#nvv
 
  'verb verb noun' can not be made into a fork because 'verb noun' 
  already has an interpretation (*viz*., apply verb to noun).
 
 
  On Tue, Nov 6, 2012 at 8:47 AM, Michal D. 
  michal.dobrog...@gmail.com
  wrote:
 
Change from a Noun to a verb, view its tacit version and apply 
it to
   data:
   
        dd=: 13 :'(y%2)  (?]) x$y'
   
        dd
(2 %~ ])  [: (? ]) $
   
  
   That is quite cool.  I'm surprised that you can automatically get 
   the
  tacit
   definition.  Does this work for any explicitly defined verb?
  
   I'm also surprised at the way %~ came out.  Do left hand 
   arguments not require a  to bind the argument?  It is strange to 
   me that
   (1) works
 but
   (2) does not.  It seems to me that (3) is the logical way to 
   phrase
  either
   of them (ie. a fork with a constant right / left side).  To 
   reiterate,
  why
   does (1) work?
  
   (1)    (2 %~ ])  [: (? ]) $
   (2)    (] % 2)  [: (? ]) $
   (3a)   (2: %~ ])  [: (? ]) $
   (3b)   (] %~ 2:)  [: (? ]) $
   (4a)   (%2 ])  [: (? ]) $      NB. incorrect (hook caught me 
   out
  again)!
   (4b)   ([: %2 ])  [: (? ]) $   NB. correct
  
   Cheers,
  
   Mike
   -
   -
    For information about J forums see 
   http://www.jsoftware.com/forums.htm
  
  ---
  -
  -- For information about J forums see 
  http://www.jsoftware.com/forums.htm
 
 -
 - For information about J forums see 
 http://www.jsoftware.com/forums.htm




--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm



--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-08 Thread Linda Alvord

I would have expected a result with shape  2 3 4  not 2 4 3

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Peter B.
Kessler
Sent: Thursday, November 08, 2012 9:24 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

The shape of the arguments to the verb that's being inserted is 3x4, so when
that verb returns an atom, as dyadic + does, the shape of the result is 3x4.
But dyadic ? (Deal[1]) doesn't return an atom: it returns a list of the
number of items of its left argument.  So for each of the 3x4 applications
of dyadic ? returns a list of 3 elements, so the shape of the result is
3x4x3.  There's probably a more official way to say that, but that's my
model of J, so far.

It might be slightly less confusing to use arguments that aren't also the
shapes of those arguments.  E.g., 

The left argument is a list of length 2, and the right argument is a list of
length 4, so there are 2x4 pairs between each of which is inserted a Deal.
Each Deal chooses 3 items from i. 6 without replacement.

   3 3 ?/ 6 6 6 6
5 0 2
3 5 0
1 4 5
1 0 3

0 3 2
0 5 2
1 2 4
3 0 1

so the shape of the result is 2x4x3.

   $ 3 3 ?/ 6 6 6 6
2 4 3

Does that seem less odd?

... peter

[1] http://www.jsoftware.com/help/dictionary/d640.htm

Linda Alvord wrote:
f=: 13 :'0=?~ x#y'
f
 0 = [: ?~ #

 Maybe someday I'll just write expressions like yours easily.   The
idea
 seems so simple now.

 However, I discovered this oddity:

 3 3 3 +/ 4 4 4 4
 7 7 7 7
 7 7 7 7
 7 7 7 7

3 3 3 ?/ 4 4 4 4
 3 2 1
 1 3 0
 2 3 1
 3 2 1

 2 3 1
 2 1 3
 1 3 0
 1 0 2

 2 0 3
 0 3 1
 0 1 3
 2 3 1

 This seems odd:

 Linda

 -Original  Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Bo 
 Jacoby
 Sent: Thursday, November 08, 2012 4:46 AM
 sTo: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 Linda, stick to integer arithmetic:
5 (0=[:?~#) 8
 0 0 0 0 0 0 1 0
 1 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0
 0 0 0 1 0 0 0 0
 0 0 0 0 0 1 0 0
 - Bo

 Fra: Linda Alvord lindaalv...@verizon.net
 Til: programm...@jsoftware.com
 Sendt: 10:10 torsdag den 8. november 2012
 Emne: Re: [Jprogramming] Arc consistency in J

ee=:(]%2)  ?~@$
ee
 0.5  ?~@$
ff=: 13 :'0.5  ?~x$y'
ff
 0.5  [: ?~ $
5 ff 8
 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 1
 0 0 0 0 1 0 0 0
 0 1 0 0 0 0 0 0
 0 0 1 0 0 0 0 0

 J is so smart, it eliminate the need for  *

hh=: 13 :' ?~x$y'
hh
 [: ?~ $
]A=:5 hh 8
 4 7 1 6 0 5 3 2
 4 2 3 1 5 7 0 6
 7 3 5 4 1 2 6 0
 5 3 2 4 1 7 6 0
 2 5 4 0 3 6 7 1
0.5  A
 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 1
 0 0 0 0 0 0 0 1
 0 0 0 1 0 0 0 0

 Mind boggling!

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon 
 McCormick
 Sent: Wednesday, November 07, 2012 12:56 PM
 To: J-programming forum
 Subject: Re: [Jprogramming] Arc consistency in J

 At first glance, I thought the right tine of this fork
(2 %~ ])  [: (? ]) $
 could be replaced by an idiom I frequently use
(?@$)
 but then realized that what we need is
(?~@$)
 so dd can be written as
(]%2)  ?~@$

 On Wed, Nov 7, 2012 at 1:31 AM, Michal D.
 michal.dobrog...@gmail.comwrote:
 Thanks Roger, that makes sense now.  The history of J is one of it`s 
 intriguing aspects for sure.

 Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But 
 what do I know? ;-)

 Mike

 On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui 
 rogerhui.can...@gmail.com
 wrote:

 'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'
 (noun_
 is a constant verb whose result is noun). 
 http://keiapl.org/anec/#nvv

 'verb verb noun' can not be made into a fork because 'verb noun' 
 already has an interpretation (*viz*., apply verb to noun).

 On Tue, Nov 6, 2012 at 8:47 AM, Michal D. 
 michal.dobrog...@gmail.com
 wrote:
 Change from a Noun to a verb, view its tacit version and apply it 
 to
 data:
  dd=: 13 :'(y%2)  (?]) x$y'

  dd
 (2 %~ ])  [: (? ]) $

 That is quite cool.  I'm surprised that you can automatically get 
 the
 tacit
 definition.  Does this work for any explicitly defined verb?

 I'm also surprised at the way %~ came out.  Do left hand arguments 
 not require a  to bind the argument?  It is strange to me that
 (1) works
 but
 (2) does not.  It seems to me that (3) is the logical way to 
 phrase
 either
 of them (ie. a fork with a constant right / left side).  To 
 reiterate,
 why
 does (1) work?

 (1)(2 %~ ])  [: (? ]) $
 (2)(] % 2)  [: (? ]) $
 (3a)   (2: %~ ])  [: (? ]) $
 (3b)   (] %~ 2:)  [: (? ]) $
 (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me 
 out
 again)!
 (4b

Re: [Jprogramming] Arc consistency in J

2012-11-08 Thread Henry Rich


   ? b. 0
0 0 0

Therefore dyad ?/ is equivalent to ?0 _

The last axis comes from the shape of the individual results.

Henry Rich

On 11/8/2012 10:33 PM, Linda Alvord wrote:

I would have expected a result with shape  2 3 4  not 2 4 3

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Peter B.
Kessler
Sent: Thursday, November 08, 2012 9:24 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

The shape of the arguments to the verb that's being inserted is 3x4, so when
that verb returns an atom, as dyadic + does, the shape of the result is 3x4.
But dyadic ? (Deal[1]) doesn't return an atom: it returns a list of the
number of items of its left argument.  So for each of the 3x4 applications
of dyadic ? returns a list of 3 elements, so the shape of the result is
3x4x3.  There's probably a more official way to say that, but that's my
model of J, so far.

It might be slightly less confusing to use arguments that aren't also the
shapes of those arguments.  E.g.,

The left argument is a list of length 2, and the right argument is a list of
length 4, so there are 2x4 pairs between each of which is inserted a Deal.
Each Deal chooses 3 items from i. 6 without replacement.

3 3 ?/ 6 6 6 6
 5 0 2
 3 5 0
 1 4 5
 1 0 3

 0 3 2
 0 5 2
 1 2 4
 3 0 1

so the shape of the result is 2x4x3.

$ 3 3 ?/ 6 6 6 6
 2 4 3

Does that seem less odd?

... peter

[1] http://www.jsoftware.com/help/dictionary/d640.htm

Linda Alvord wrote:

f=: 13 :'0=?~ x#y'
f
0 = [: ?~ #

Maybe someday I'll just write expressions like yours easily.   The

idea

seems so simple now.

However, I discovered this oddity:

 3 3 3 +/ 4 4 4 4
7 7 7 7
7 7 7 7
7 7 7 7

3 3 3 ?/ 4 4 4 4
3 2 1
1 3 0
2 3 1
3 2 1

2 3 1
2 1 3
1 3 0
1 0 2

2 0 3
0 3 1
0 1 3
2 3 1

This seems odd:

Linda

-Original  Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Bo
Jacoby
Sent: Thursday, November 08, 2012 4:46 AM
sTo: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Linda, stick to integer arithmetic:
5 (0=[:?~#) 8
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
- Bo






Fra: Linda Alvord lindaalv...@verizon.net
Til: programm...@jsoftware.com
Sendt: 10:10 torsdag den 8. november 2012
Emne: Re: [Jprogramming] Arc consistency in J

ee=:(]%2)  ?~@$
ee
0.5  ?~@$
ff=: 13 :'0.5  ?~x$y'
ff
0.5  [: ?~ $
5 ff 8
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0

J is so smart, it eliminate the need for  *

hh=: 13 :' ?~x$y'
hh
[: ?~ $
]A=:5 hh 8
4 7 1 6 0 5 3 2
4 2 3 1 5 7 0 6
7 3 5 4 1 2 6 0
5 3 2 4 1 7 6 0
2 5 4 0 3 6 7 1
0.5  A
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0

Mind boggling!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Devon
McCormick
Sent: Wednesday, November 07, 2012 12:56 PM
To: J-programming forum
Subject: Re: [Jprogramming] Arc consistency in J

At first glance, I thought the right tine of this fork
(2 %~ ])  [: (? ]) $
could be replaced by an idiom I frequently use
(?@$)
but then realized that what we need is
(?~@$)
so dd can be written as
(]%2)  ?~@$


On Wed, Nov 7, 2012 at 1:31 AM, Michal D.

michal.dobrog...@gmail.comwrote:

Thanks Roger, that makes sense now.  The history of J is one of it`s
intriguing aspects for sure.

Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But
what do I know? ;-)

Mike

On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui
rogerhui.can...@gmail.com
wrote:


'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'

(noun_

is a constant verb whose result is noun).
http://keiapl.org/anec/#nvv

'verb verb noun' can not be made into a fork because 'verb noun'
already has an interpretation (*viz*., apply verb to noun).


On Tue, Nov 6, 2012 at 8:47 AM, Michal D.
michal.dobrog...@gmail.com

wrote:

Change from a Noun to a verb, view its tacit version and apply it
to

data:

  dd=: 13 :'(y%2)  (?]) x$y'

  dd
(2 %~ ])  [: (? ]) $


That is quite cool.  I'm surprised that you can automatically get
the

tacit

definition.  Does this work for any explicitly defined verb?

I'm also surprised at the way %~ came out.  Do left hand arguments
not require a  to bind the argument?  It is strange to me that
(1) works

but

(2) does not.  It seems to me that (3) is the logical way to
phrase

either

of them (ie. a fork with a constant right / left side).  To
reiterate,

why

does (1) work?

(1)(2 %~ ])  [: (? ]) $
(2)(] % 2)  [: (? ]) $
(3a)   (2: %~ ])  [: (? ]) $
(3b)   (] %~ 2:)  [: (? ]) $
(4a)   (%2 ])  [: (? ]) $  NB

Re: [Jprogramming] Arc consistency in J

2012-11-07 Thread Devon McCormick

At first glance, I thought the right tine of this fork
   (2 %~ ])  [: (? ]) $
could be replaced by an idiom I frequently use
   (?@$)
but then realized that what we need is
   (?~@$)
so dd can be written as
   (]%2)  ?~@$


On Wed, Nov 7, 2012 at 1:31 AM, Michal D. michal.dobrog...@gmail.comwrote:

 Thanks Roger, that makes sense now.  The history of J is one of it`s
 intriguing aspects for sure.

 Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But what do I
 know? ;-)

 Mike

 On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui rogerhui.can...@gmail.com
 wrote:

  'noun verb verb' is a fork and is interpreted as 'noun_ verb verb'
 (noun_
  is a constant verb whose result is noun).  http://keiapl.org/anec/#nvv
 
  'verb verb noun' can not be made into a fork because 'verb noun' already
  has an interpretation (*viz*., apply verb to noun).
 
 
  On Tue, Nov 6, 2012 at 8:47 AM, Michal D. michal.dobrog...@gmail.com
  wrote:
 
Change from a Noun to a verb, view its tacit version and apply it to
   data:
   
dd=: 13 :'(y%2)  (?]) x$y'
   
dd
(2 %~ ])  [: (? ]) $
   
  
   That is quite cool.  I'm surprised that you can automatically get the
  tacit
   definition.  Does this work for any explicitly defined verb?
  
   I'm also surprised at the way %~ came out.  Do left hand arguments not
   require a  to bind the argument?  It is strange to me that (1) works
 but
   (2) does not.  It seems to me that (3) is the logical way to phrase
  either
   of them (ie. a fork with a constant right / left side).  To reiterate,
  why
   does (1) work?
  
   (1)(2 %~ ])  [: (? ]) $
   (2)(] % 2)  [: (? ]) $
   (3a)   (2: %~ ])  [: (? ]) $
   (3b)   (] %~ 2:)  [: (? ]) $
   (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me out
  again)!
   (4b)   ([: %2 ])  [: (? ]) $   NB. correct
  
   Cheers,
  
   Mike
   --
   For information about J forums see http://www.jsoftware.com/forums.htm
  
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 
 --
 For information about J forums see http://www.jsoftware.com/forums.htm




-- 
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-06 Thread Linda Alvord

(^@j. = cos + 0j1 * sin) 1 2 3 0.1j_0.2
1 1 1 1
   
   (^j. = cos + 0j1 * sin) 1 2 3 0.1j_0.2
1 1 1 1

   ^j.
^ j.

This made a connection with trigonometry relationships.  I now have a little
glimmer about  t. but I must admit it is still fuzzy.
   
   ^t.
%@!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Roger Hui
Sent: Tuesday, November 06, 2012 11:54 AM
To: Programming forum
Subject: Re: [Jprogramming] Arc consistency in J

'noun verb verb' is a fork and is interpreted as 'noun_ verb verb' (noun_
is a constant verb whose result is noun).  http://keiapl.org/anec/#nvv

'verb verb noun' can not be made into a fork because 'verb noun' already has
an interpretation (*viz*., apply verb to noun).


On Tue, Nov 6, 2012 at 8:47 AM, Michal D. michal.dobrog...@gmail.comwrote:

  Change from a Noun to a verb, view its tacit version and apply it to
 data:
 
  dd=: 13 :'(y%2)  (?]) x$y'
 
  dd
  (2 %~ ])  [: (? ]) $
 

 That is quite cool.  I'm surprised that you can automatically get the 
 tacit definition.  Does this work for any explicitly defined verb?

 I'm also surprised at the way %~ came out.  Do left hand arguments not 
 require a  to bind the argument?  It is strange to me that (1) works 
 but
 (2) does not.  It seems to me that (3) is the logical way to phrase 
 either of them (ie. a fork with a constant right / left side).  To 
 reiterate, why does (1) work?

 (1)(2 %~ ])  [: (? ]) $
 (2)(] % 2)  [: (? ]) $
 (3a)   (2: %~ ])  [: (? ]) $
 (3b)   (] %~ 2:)  [: (? ]) $
 (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me out again)!
 (4b)   ([: %2 ])  [: (? ]) $   NB. correct

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-06 Thread Linda Alvord

'noun verb verb' is a fork and is interpreted as 'noun_ verb verb' (noun_
is a constant verb whose result is noun).  http://keiapl.org/anec/#nvv

When I said:

 Change from a Noun to a verb, view its tacit version and apply it to
 data:

 dd=: 13 :'(y%2)  (?]) x$y'

I should have said:

Change from a Noun to a constant verb 

My question:

Is it now a  N(oun) or a v(erb) using Raul's convention?

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Roger Hui
Sent: Tuesday, November 06, 2012 11:54 AM
To: Programming forum
Subject: Re: [Jprogramming] Arc consistency in J

'noun verb verb' is a fork and is interpreted as 'noun_ verb verb' (noun_
is a constant verb whose result is noun).  http://keiapl.org/anec/#nvv

'verb verb noun' can not be made into a fork because 'verb noun' already has
an interpretation (*viz*., apply verb to noun).


On Tue, Nov 6, 2012 at 8:47 AM, Michal D. michal.dobrog...@gmail.comwrote:

  Change from a Noun to a verb, view its tacit version and apply it to
 data:
 
  dd=: 13 :'(y%2)  (?]) x$y'
 
  dd
  (2 %~ ])  [: (? ]) $
 

 That is quite cool.  I'm surprised that you can automatically get the 
 tacit definition.  Does this work for any explicitly defined verb?

 I'm also surprised at the way %~ came out.  Do left hand arguments not 
 require a  to bind the argument?  It is strange to me that (1) works 
 but
 (2) does not.  It seems to me that (3) is the logical way to phrase 
 either of them (ie. a fork with a constant right / left side).  To 
 reiterate, why does (1) work?

 (1)(2 %~ ])  [: (? ]) $
 (2)(] % 2)  [: (? ]) $
 (3a)   (2: %~ ])  [: (? ]) $
 (3b)   (] %~ 2:)  [: (? ]) $
 (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me out again)!
 (4b)   ([: %2 ])  [: (? ]) $   NB. correct

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-06 Thread Michal D.

Hi Raul,

I think you suggested it in another place and I replaced it where I
shouldn`t have.

Cheers,

Mike

On Tue, Nov 6, 2012 at 10:22 AM, Raul Miller rauldmil...@gmail.com wrote:

 Removing 0 = was my suggestion.  I've not taken the time yet to see
 why this was a bug, but I apologize.

 Thanks,

 --
 Raul

 On Mon, Nov 5, 2012 at 10:29 PM, Michal D. michal.dobrog...@gmail.com
 wrote:
  Hi Linda, you are a bug finding machine!  c11 is simpler than the
 original
  and is more correct than the latest version I put up on pastebin.  I
  introduced a bug by removing the 0= from this although I shouldn't have.
 
  Cheers,
 
  Mike
 
  On Mon, Nov 5, 2012 at 3:06 AM, Linda Alvord lindaalv...@verizon.net
 wrote:
 
  Next, isn't c1 the same as c11?
 
  I make silly little scripts like this and I run them in a new Jconsole
 and
  then do T '' lots of times until I'm pretty sure they agree.
 
  T=: 3 : 0
  n=:1+?6
  d=:1+?6
  ]D=:(n%2)  (?]) n$d
  ]E=:?(n,d)$2
  ]c1=:0= ? A=:(2$d)$(. d%2)
  ]c11=:?(d,d)$2
  F=:($D)-:$E
  G=:($c1)-:$c11
  F,G
  )
 
  T ''
 
 
  Linda
 
  -Original Mesesageh
  From: programming-boun...@forums.jsoftware.com
  [mailto:programming-boun...@forums.jsoftrware.com] On Behalf Of Linda
  Alvord
  Sent: Monday, November 05, 2012 5:12 AM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
  I just began to ponder this thread. Do you think E is the same as D?
  th
  D=. (n%2)  (?]) n$d
  E=. ?(n,d)$2
 
  Linda
 
  -Original Message-
  From: programming-boun...@forums.jsoftware.com
  [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal
 D.
  Sent: Sunday, November 04, 2012 11:26 PM
  To: programm...@jsoftware.com
  Subject: Re: [Jprogramming] Arc consistency in J
 
variables.  In other words, if we specify the constraint x  y it
looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
consistency.  In other words, i think we should always use the
symmetric closure of the constraint.
   
Does this sound valid to you?
   
Unfortunately not.  There are no values that can satisfy x1x2 and
  x2x1.
If this was the case all csps would have no solutions
  
   I meant x1x2 OR x2x1
  
   So symmetric closure was the wrong term for me to use.
  
   But I think we want to be using intersection of the relationship with
   its inverse.
  
   Does that sound right to you?
  
 
  Sorry I missed the or.  Unfortunately not, I mean you can have a
 constraint
  like that if you want but you don't have to have to in general.  I think
  we're dwelling on an implementation detail.  They (wikipedia) must just
  have
  the  constraint propagating both ways.
 
  My brain is fried but I did hack together an ugly search procedure.  You
  can
  try it out on a sudoku puzzle if you want.  For some reason I couldn't
  generate it using the code you gave me.  http://pastebin.com/2zPB4DBA
 
  Maybe we can update the printf docs to say:
  load 'format/printf'
  http://www.jsoftware.com/help/jforc/input_and_output.htm
 
  Cheers,
 
  Mike
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-06 Thread Michal D.

Thanks Roger, that makes sense now.  The history of J is one of it`s
intriguing aspects for sure.

Re: Linda: I would call it a v(erb) as opposed to a N(oun).  But what do I
know? ;-)

Mike

On Tue, Nov 6, 2012 at 8:53 AM, Roger Hui rogerhui.can...@gmail.com wrote:

 'noun verb verb' is a fork and is interpreted as 'noun_ verb verb' (noun_
 is a constant verb whose result is noun).  http://keiapl.org/anec/#nvv

 'verb verb noun' can not be made into a fork because 'verb noun' already
 has an interpretation (*viz*., apply verb to noun).


 On Tue, Nov 6, 2012 at 8:47 AM, Michal D. michal.dobrog...@gmail.com
 wrote:

   Change from a Noun to a verb, view its tacit version and apply it to
  data:
  
   dd=: 13 :'(y%2)  (?]) x$y'
  
   dd
   (2 %~ ])  [: (? ]) $
  
 
  That is quite cool.  I'm surprised that you can automatically get the
 tacit
  definition.  Does this work for any explicitly defined verb?
 
  I'm also surprised at the way %~ came out.  Do left hand arguments not
  require a  to bind the argument?  It is strange to me that (1) works but
  (2) does not.  It seems to me that (3) is the logical way to phrase
 either
  of them (ie. a fork with a constant right / left side).  To reiterate,
 why
  does (1) work?
 
  (1)(2 %~ ])  [: (? ]) $
  (2)(] % 2)  [: (? ]) $
  (3a)   (2: %~ ])  [: (? ]) $
  (3b)   (] %~ 2:)  [: (? ]) $
  (4a)   (%2 ])  [: (? ]) $  NB. incorrect (hook caught me out
 again)!
  (4b)   ([: %2 ])  [: (? ]) $   NB. correct
 
  Cheers,
 
  Mike
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
 
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Linda Alvord

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Sunday, November 04, 2012 11:26 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

  variables.  In other words, if we specify the constraint x  y it 
  looks like either x1  x2 or x2  x1 is sufficient to satisfy arc 
  consistency.  In other words, i think we should always use the 
  symmetric closure of the constraint.

  Does this sound valid to you?

  Unfortunately not.  There are no values that can satisfy x1x2 and
x2x1.
  If this was the case all csps would have no solutions

 I meant x1x2 OR x2x1

 So symmetric closure was the wrong term for me to use.

 But I think we want to be using intersection of the relationship with 
 its inverse.

 Does that sound right to you?

Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
like that if you want but you don't have to have to in general.  I think
we're dwelling on an implementation detail.  They (wikipedia) must just have
the  constraint propagating both ways.

My brain is fried but I did hack together an ugly search procedure.  You can
try it out on a sudoku puzzle if you want.  For some reason I couldn't
generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

Maybe we can update the printf docs to say:
load 'format/printf'
http://www.jsoftware.com/help/jforc/input_and_output.htm

Cheers,

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Linda Alvord

Next, isn't c1 the same as c11?

I make silly little scripts like this and I run them in a new Jconsole and
then do T '' lots of times until I'm pretty sure they agree.

T=: 3 : 0
n=:1+?6
d=:1+?6
]D=:(n%2)  (?]) n$d
]E=:?(n,d)$2
]c1=:0= ? A=:(2$d)$(. d%2)
]c11=:?(d,d)$2
F=:($D)-:$E
G=:($c1)-:$c11
F,G
)

T ''


Linda

-Original Mesesageh
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftrware.com] On Behalf Of Linda Alvord
Sent: Monday, November 05, 2012 5:12 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

I just began to ponder this thread. Do you think E is the same as D?
th
D=. (n%2)  (?]) n$d
E=. ?(n,d)$2

Linda

-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Sunday, November 04, 2012 11:26 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

  variables.  In other words, if we specify the constraint x  y it 
  looks like either x1  x2 or x2  x1 is sufficient to satisfy arc 
  consistency.  In other words, i think we should always use the 
  symmetric closure of the constraint.
 
  Does this sound valid to you?
 
  Unfortunately not.  There are no values that can satisfy x1x2 and
x2x1.
  If this was the case all csps would have no solutions

 I meant x1x2 OR x2x1

 So symmetric closure was the wrong term for me to use.

 But I think we want to be using intersection of the relationship with 
 its inverse.

 Does that sound right to you?


Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
like that if you want but you don't have to have to in general.  I think
we're dwelling on an implementation detail.  They (wikipedia) must just have
the  constraint propagating both ways.

My brain is fried but I did hack together an ugly search procedure.  You can
try it out on a sudoku puzzle if you want.  For some reason I couldn't
generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

Maybe we can update the printf docs to say:
load 'format/printf'
http://www.jsoftware.com/help/jforc/input_and_output.htm

Cheers,

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Michal D.


 Ok... so this implies some kind of ordering constraint on the use of
 non-commutative relationships.

 I am going to guess that this constraint has something to do with the
 ordering of your D -- for example that lower-valued row indexes into D
 must always appear on the left side of the comparative relationship
 and higher-valued row indexes into D must always appear on the right
 side of the comparative relationship?

 Does this sound right?


Yes, I was about to suggest this approach if you want to have a single
constraint (no transpose). Ofcourse, now you have the overhead of needing
to switch arguments if they are out of order.

You may also want to take a look at a traditional arc consistency
algorithm: http://en.wikipedia.org/wiki/AC-3_algorithm

Cheers,

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Raul Miller

When n=7, d=3, D will contain only 1s while E will typically contain a
mix of 1s and 0s.

I do not know enough about the purpose of this code to comment on
which is better.

-- 
Raul

On Mon, Nov 5, 2012 at 5:11 AM, Linda Alvord lindaalv...@verizon.net wrote:
 I just began to ponder this thread. Do you think E is the same as D?

 D=. (n%2)  (?]) n$d
 E=. ?(n,d)$2

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
 Sent: Sunday, November 04, 2012 11:26 PM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

  variables.  In other words, if we specify the constraint x  y it
  looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
  consistency.  In other words, i think we should always use the
  symmetric closure of the constraint.
 
  Does this sound valid to you?
 
  Unfortunately not.  There are no values that can satisfy x1x2 and
 x2x1.
  If this was the case all csps would have no solutions

 I meant x1x2 OR x2x1

 So symmetric closure was the wrong term for me to use.

 But I think we want to be using intersection of the relationship with
 its inverse.

 Does that sound right to you?


 Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
 like that if you want but you don't have to have to in general.  I think
 we're dwelling on an implementation detail.  They (wikipedia) must just have
 the  constraint propagating both ways.

 My brain is fried but I did hack together an ugly search procedure.  You can
 try it out on a sudoku puzzle if you want.  For some reason I couldn't
 generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

 Maybe we can update the printf docs to say:
 load 'format/printf'
 http://www.jsoftware.com/help/jforc/input_and_output.htm

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

 --
 For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Michal D.

Actually, this is a bug  in the original code.  Thanks Linda!  It should be:

(d%2)  (?]) n$d

The idea being that each row (domain) has half of it's possible values
set.  Which is different from what you suggest because you may get a row of
all zeros which is already inconsistent and so there is no point in running
arc consistency on it.

Cheers,

Mike


On Mon, Nov 5, 2012 at 2:11 AM, Linda Alvord lindaalv...@verizon.netwrote:

 I just began to ponder this thread. Do you think E is the same as D?

 D=. (n%2)  (?]) n$d
 E=. ?(n,d)$2

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
 Sent: Sunday, November 04, 2012 11:26 PM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

   variables.  In other words, if we specify the constraint x  y it
   looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
   consistency.  In other words, i think we should always use the
   symmetric closure of the constraint.
  
   Does this sound valid to you?
  
   Unfortunately not.  There are no values that can satisfy x1x2 and
 x2x1.
   If this was the case all csps would have no solutions
 
  I meant x1x2 OR x2x1
 
  So symmetric closure was the wrong term for me to use.
 
  But I think we want to be using intersection of the relationship with
  its inverse.
 
  Does that sound right to you?
 

 Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
 like that if you want but you don't have to have to in general.  I think
 we're dwelling on an implementation detail.  They (wikipedia) must just
 have
 the  constraint propagating both ways.

 My brain is fried but I did hack together an ugly search procedure.  You
 can
 try it out on a sudoku puzzle if you want.  For some reason I couldn't
 generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

 Maybe we can update the printf docs to say:
 load 'format/printf'
 http://www.jsoftware.com/help/jforc/input_and_output.htm

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Michal D.

Hi Linda, you are a bug finding machine!  c11 is simpler than the original
and is more correct than the latest version I put up on pastebin.  I
introduced a bug by removing the 0= from this although I shouldn't have.

Cheers,

Mike

On Mon, Nov 5, 2012 at 3:06 AM, Linda Alvord lindaalv...@verizon.netwrote:

 Next, isn't c1 the same as c11?

 I make silly little scripts like this and I run them in a new Jconsole and
 then do T '' lots of times until I'm pretty sure they agree.

 T=: 3 : 0
 n=:1+?6
 d=:1+?6
 ]D=:(n%2)  (?]) n$d
 ]E=:?(n,d)$2
 ]c1=:0= ? A=:(2$d)$(. d%2)
 ]c11=:?(d,d)$2
 F=:($D)-:$E
 G=:($c1)-:$c11
 F,G
 )

 T ''


 Linda

 -Original Mesesageh
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftrware.com] On Behalf Of Linda
 Alvord
 Sent: Monday, November 05, 2012 5:12 AM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

 I just began to ponder this thread. Do you think E is the same as D?
 th
 D=. (n%2)  (?]) n$d
 E=. ?(n,d)$2

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
 Sent: Sunday, November 04, 2012 11:26 PM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

   variables.  In other words, if we specify the constraint x  y it
   looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
   consistency.  In other words, i think we should always use the
   symmetric closure of the constraint.
  
   Does this sound valid to you?
  
   Unfortunately not.  There are no values that can satisfy x1x2 and
 x2x1.
   If this was the case all csps would have no solutions
 
  I meant x1x2 OR x2x1
 
  So symmetric closure was the wrong term for me to use.
 
  But I think we want to be using intersection of the relationship with
  its inverse.
 
  Does that sound right to you?
 

 Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
 like that if you want but you don't have to have to in general.  I think
 we're dwelling on an implementation detail.  They (wikipedia) must just
 have
 the  constraint propagating both ways.

 My brain is fried but I did hack together an ugly search procedure.  You
 can
 try it out on a sudoku puzzle if you want.  For some reason I couldn't
 generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

 Maybe we can update the printf docs to say:
 load 'format/printf'
 http://www.jsoftware.com/help/jforc/input_and_output.htm

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

 --
 For information about J forums see http://www.jsoftware.com/forums.htm

 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Linda Alvord

 Once you have what you want, you can use some tools to study it:
 
Change from a Noun to a verb, view its tacit version and apply it to data:
  
dd=: 13 :'(y%2)  (?]) x$y'
   
dd
(2 %~ ])  [: (? ]) $

   7 dd 3
1 1 0
1 0 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1

Both the boxed version and the tree can be helpful.
   

  5!:4 'dd'
  -- 2  
  +- ~ --- %
  │   L- ]  
  +-   
--+   -- [: 
  │   │ -- ?
  L---+-+- ]
  L- $  
   
  5!:2 'dd'
T-T┐
│--T-T-┐││---T-T-┐│
││2│--T-┐│]││ ││[:│--T-┐│$││
││ ││%│~││ ││ ││  ││?│]││ ││
││ │L-+--│ ││ ││  │L-+--│ ││
│L-+-+--│ │L--+-+--│
L---+-+-

Each in its own way will show you the forks and hooks.  You will begin to
see differences in the patterns of trees that are built from right to left
compared to those built from left to right.

Oddly, I can untangle code long before I can understand what it is doing.
Now I'm ready to try to follow your thinking as it applies to Sudoku.

You should have lots of fun with J!

Linda


-Original Message-
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
Sent: Monday, November 05, 2012 10:19 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

Actually, this is a bug  in the original code.  Thanks Linda!  It should be:

(d%2)  (?]) n$d

The idea being that each row (domain) has half of it's possible values set.
Which is different from what you suggest because you may get a row of all
zeros which is already inconsistent and so there is no point in running arc
consistency on it.

Cheers,

Mike


On Mon, Nov 5, 2012 at 2:11 AM, Linda Alvord lindaalv...@verizon.netwrote:

 I just began to ponder this thread. Do you think E is the same as D?

 D=. (n%2)  (?]) n$d
 E=. ?(n,d)$2

 Linda

 -Original Message-
 From: programming-boun...@forums.jsoftware.com
 [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Michal D.
 Sent: Sunday, November 04, 2012 11:26 PM
 To: programm...@jsoftware.com
 Subject: Re: [Jprogramming] Arc consistency in J

   variables.  In other words, if we specify the constraint x  y it 
   looks like either x1  x2 or x2  x1 is sufficient to satisfy arc 
   consistency.  In other words, i think we should always use the 
   symmetric closure of the constraint.
  
   Does this sound valid to you?
  
   Unfortunately not.  There are no values that can satisfy x1x2 and
 x2x1.
   If this was the case all csps would have no solutions
 
  I meant x1x2 OR x2x1
 
  So symmetric closure was the wrong term for me to use.
 
  But I think we want to be using intersection of the relationship 
  with its inverse.
 
  Does that sound right to you?
 

 Sorry I missed the or.  Unfortunately not, I mean you can have a 
 constraint like that if you want but you don't have to have to in 
 general.  I think we're dwelling on an implementation detail.  They 
 (wikipedia) must just have the  constraint propagating both ways.

 My brain is fried but I did hack together an ugly search procedure.  
 You can try it out on a sudoku puzzle if you want.  For some reason I 
 couldn't generate it using the code you gave me.  
 http://pastebin.com/2zPB4DBA

 Maybe we can update the printf docs to say:
 load 'format/printf'
 http://www.jsoftware.com/help/jforc/input_and_output.htm

 Cheers,

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm

 --
 For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-05 Thread Linda Alvord

Michal, Once you have what you want, you can use some tools to study it:
 
Change from a Noun to a verb, view its tacit version and apply it to data:
  
dd=: 13 :'(y%2)  (?]) x$y'
   
dd
(2 %~ ])  [: (? ]) $

   7 dd 3
1 1 0
1 0 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1

Both the boxed version and the tree can be helpful.
   

 5!:4 'dd'
  -- 2  
  +- ~ --- %
  │   L- ]  
  +-   
--+   -- [: 
  │   │ -- ?
  L---+-+- ]
  L- $  

   5!:2 'dd'
T-T┐
│--T-T-┐││---T-T-┐│
││2│--T-┐│]││ ││[:│--T-┐│$││
││ ││%│~││ ││ ││  ││?│]││ ││
││ │L-+--│ ││ ││  │L-+--│ ││
│L-+-+--│ │L--+-+--│
L---+-+-

Each in its own way will show you the forks and hooks.  You will begin to
see differences in the patterns of trees that are built from right to left
compared to those built from left to right.

Oddly, I can untangle code long before I can understand what it is doing.
Now I'm ready to try to follow your thinking as it applies to Sudoku.

You should have lots of fun with J!

Linda



--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Bo Jacoby

Michal D. michal.dobrog...@gmail.com wrote:  I'm not sure why to prefer 
doubling an entire array as opposed to dividing a single scalar? 

Doubling an integer provides an integer, while division transcends the realm of 
integers. That's why. - Bo
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

In
   A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

The 0= is unnecessary, and probably reflects a habit based on the
false idea that boolean algebra is does not have an integer domain.
Boolean rings have (subset of) integer domains, and [even after
redefinition] boolean algebra is a boolean ring.

If you ever want to treat Heyting Algebras or Bayesian Probability you
might also want to consider what happens when you replace the $2 with
$0.

I think I would also be more comfortable with
   2 2 $ ''; 'y'; 'x'; A
for the displayed table, but that's a minor quibble.

An alternative definition for adj might be
   adj=: @I.@:*

But somewhere around here, I get lost.  Your use pattern for arcsX is:

   (i.n) arcsX A

where A has the shape n,n

What is the domain of the left argument of arcsX?  I am guessing that
it's either i.n or a single element choosen from i.n but if that is
the case, I think I'd define arcsX to only work for the i.n case --
the name says arcs after all.  Also, if I wanted to extract the
values from the result of arcsX which correspond to a single value
from i. n, that's simple enough -- I can select on the first column of
the result.

In other words, perhaps something like this:

   arcs=: $ #: I.@,
   arcs *A

Also, I have not taken the time yet, to read revise, so I will stop here.

-- 
Raul

On Sun, Nov 4, 2012 at 12:31 AM, Michal D. michal.dobrog...@gmail.com wrote:
 Thank you everyone for the comments and encouragement.

 I think Bo's (?]) and accompanying code was an interesting illustration of
 a nice use of the hook.  I'm not sure why to prefer doubling an entire
 array as opposed to dividing a single scalar?  I think that inlining getx
 and gety is anti-style ;-).  See also all the argument unwrapping that
 happens in the new revise.  Too bad there is no way to prevent this.

 I take it that picking # over $ is a purely stylistic preference.  I
 appreciate all the comments regarding coppula and NB.*, both sound like a
 good idea.

 The historical comments regarding a hook conjunction exactly mirror my
 frustrations.  Thank you Raul also for arcsX2, that is a thing of beauty =).

 New and improved code at http://pastebin.com/fzs0GAev with an expanded
 intro to CSPs.

 Cheers,

 Mike

 On Thu, Nov 1, 2012 at 10:01 PM, Michal D. michal.dobrog...@gmail.comwrote:

 Hi All,

 I've managed to write my first not-completely-trivial program in J.  It
 implements an arc consistency algorithm (
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I would
 appreciate any comments regarding style, what I'm doing wrong in J or how
 to improve the code.  I also have a couple of questions of my own:

 1) how do I avoid @ especially once we remove explicit arguments?
 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
 3) Is a boxed value always a pointer? One could imagine implementing
 'ragged' arrays without pointers.
 4) Is there a good way to have named variables (ie. avoid getx, gety)?
 5) Why is a hook the default and not composition?

 Code at: http://pastebin.com/k4XuKfFi

 Cheers!

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

Actually...

ac is a wrapper for revise, which supplies a value for ys (which is
the same thing as xs) which initially takes the value i.#D which is
i.n but this changes over time... I need to think about this pattern.

But for the moment, since the right argument to revise is a pair, and
it's used in ^: it makes sense to leave that part alone.  So, perhaps:

revise=:1 :0
:
  A=. x
  C=. m
  'xs D'=. y
...
)

This means recomputing 'a' in every inductive step, but I do not yet
have a good enough of an understanding of the algorithm to begin to
think about efficiency issues.

-- 
Raul

On Sun, Nov 4, 2012 at 1:40 PM, Raul Miller rauldmil...@gmail.com wrote:
 On Sun, Nov 4, 2012 at 12:53 PM, Mike Day mike_liz@tiscali.co.uk wrote:
 I think Raul has overlooked your use of the right argument ys within that
 verb, ...

 You are right, I had not even tried to read 'revise'.

 Looking at it now, it has a signature:

 NB.* '(A;a;C) revise (xs;D)' filter domains of all variables (ys) adjacent to


 And then a bunch of code to unpack those arguments.

 I think for an initial draft at least, I would try to use a
 conjunction so that my arguments would come pre-packaged.  A bare
 conjunction can deal with four arguments without any packing or
 unpacking.   And we know we can compute a from A, so, perhaps:

A C revise xs D

 If we want to keep the same names:
 revise=:2 :0
 :
   A=. x
   C=. m
   xs=. n
   D=. y
 ...
 )

 Note that we need the line with just a colon because we want to define
 a dyadic verb as the result of our conjunction.

 Now to read the rest of it...

 --
 Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

In revise, you are using a pair for your right argument.

It looks to me like this might be unnecessary -- that you could use
ys=. I.+./1 D

But this does not exactly reproduce your algorithm.  So if this change
breaks your algorithm, could you find an example situation which
illustrates this issue?

Thanks,

-- 
Raul

On Fri, Nov 2, 2012 at 1:01 AM, Michal D. michal.dobrog...@gmail.com wrote:
 Hi All,

 I've managed to write my first not-completely-trivial program in J.  It
 implements an arc consistency algorithm (
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I would
 appreciate any comments regarding style, what I'm doing wrong in J or how
 to improve the code.  I also have a couple of questions of my own:

 1) how do I avoid @ especially once we remove explicit arguments?
 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
 3) Is a boxed value always a pointer? One could imagine implementing
 'ragged' arrays without pointers.
 4) Is there a good way to have named variables (ie. avoid getx, gety)?
 5) Why is a hook the default and not composition?

 Code at: http://pastebin.com/k4XuKfFi

 Cheers!

 Mike
 --
 For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

The adjacency matrix A is important because it tells us which constraint to
look up in C.  This also explains why the lower diagonal is doubled.

For example, take the less than constraint:

   c =: |: (i.n) / (i.n)
   2 2 $ '' ; 'Dx' ; 'Dy' ; c
+--+---+
|  |Dx |
+--+---+
|Dy|0 0 0 0|
|  |1 0 0 0|
|  |1 1 0 0|
|  |1 1 1 0|
+--+---+

This constraint is useful for filtering Dx given Dy. Let's look at how
revDom works (revDom is the heart of the algorithm).  Let's generate a
domain for x and y.

   Dx=: 1 1 1 1   NB. {0,1,2,3}
   Dy=: 1 1 1 0   NB. {0,1,2}

To visualize, stick Dy on the left, and Dx on top:

   2 2 $ '' ; Dx ; (|:,:Dy) ; c
+-+---+
| |1 1 1 1|
+-+---+
|1|0 0 0 0|
|1|1 0 0 0|
|1|1 1 0 0|
|0|1 1 1 0|
+-+---+

Now we use Dy to select the relevant rows of c (each row represents the set
of values compatible with that value of Dy).

   Dy # c
0 0 0 0
1 0 0 0
1 1 0 0

Take the logical-or of these rows to compute the set of values of Dx that
have some compatible value in Dy.

   +./ Dy # c
1 1 0 0

Finally, take the logical-and with Dx so we don't add values that weren't
there in the first place.

   Dx *. +./ Dy # c
1 1 0 0

Now, with all this done, what if we want to filter Dy on Dx?  We need to
take the transpose of c.  To prevent constant transposing, A and C store
these for us.

Mike

On Sun, Nov 4, 2012 at 9:53 AM, Mike Day mike_liz@tiscali.co.uk wrote:

 As far as I can understand the revise verb,  you don't need the
 adjacency matrix a, although it does help to have a 2-column matrix of
 index pairs.

 I think Raul has overlooked your use of the right argument ys within that
 verb,  though he's right about selecting with it. Here's a derivation of
 arcs without explicit recourse to the adjacency matrix  (I've just noticed
 that Raul presents a similar idiom):

 arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

 I. returns a vector of indices to the ravelled boolean;  $ #: turns them
 into a matrix of pairs of indices to an array of the shape of |:A.

 (]#~ (e.~ {.1)) selects those arcs with an element of ys as the from-node
 (or perhaps they're the to-nodes?)

 This form renders the arcs array already sorted,  but note that if you do
 need to sort the elements of an array,  it's sufficient to use the idiom
  /: ~(rather than ({~ /:)   . Presumably sorting arcs is merely a
 matter of taste.

 It's quite nice to be able to input several components of an argument by
 (local) name with
'A a C'=.x
'ys D'=. y
 rather than
 A=.  0{x
 a=.  1{x
 ys=.  0{y
 D=.   1{y

 As A is invariant in ac,   you could of course preset the array of
 indices for all arcs in A,  aix =: ($#: I.@,)  *|:Aand use aix as an
 input to revise instead of   a  .

 I used *|:A or (0|:A) here and wonder why you need to double its lower
 diagonal elements.

 I also wonder whether your example will still work if there are binary
 constraints involving variables (say z and t) indexed with 2 or 3.  And
 what happens if there are more than one binary constraints on a pair of
 variables?  eg,  X+Y=4 AND XY ?

 I'd have been very pleased with myself if I'd come up with code as good as
 this when I started J - would be pretty pleased if I managed it now!

 Mike



 On 04/11/2012 2:40 PM, Raul Miller wrote:

 In
 A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

 The 0= is unnecessary, and probably reflects a habit based on the
 false idea that boolean algebra is does not have an integer domain.
 Boolean rings have (subset of) integer domains, and [even after
 redefinition] boolean algebra is a boolean ring.

 If you ever want to treat Heyting Algebras or Bayesian Probability you
 might also want to consider what happens when you replace the $2 with
 $0.

 I think I would also be more comfortable with
 2 2 $ ''; 'y'; 'x'; A
 for the displayed table, but that's a minor quibble.

 An alternative definition for adj might be
 adj=: @I.@:*

 But somewhere around here, I get lost.  Your use pattern for arcsX is:

 (i.n) arcsX A

 where A has the shape n,n

 What is the domain of the left argument of arcsX?  I am guessing that
 it's either i.n or a single element choosen from i.n but if that is
 the case, I think I'd define arcsX to only work for the i.n case --
 the name says arcs after all.  Also, if I wanted to extract the
 values from the result of arcsX which correspond to a single value
 from i. n, that's simple enough -- I can select on the first column of
 the result.

 In other words, perhaps something like this:

 arcs=: $ #: I.@,
 arcs *A

 Also, I have not taken the time yet, to read revise, so I will stop
 here.


 --**--**--
 For information about J forums see 
 http://www.jsoftware.com/**forums.htmhttp://www.jsoftware.com/forums.htm

--
For information about J forums see

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

I think I am having a problem envisioning how a sudoku-style puzzle
can work with a relationship which is not commutative, and I am also
having a problem having to do with the transitive character of the
relationship.

As you have put it:

   (note: constraints are not symmetric, for example xy)

I think I understand that in the general case we can have asymmetrical
relationships, but taking sudoku as an example... I believe I
understand 5 is not equal to any other value in the same row, in the
same column, or in the same square.  But I am having a problem
understanding 5 is less than any other value in the same row, in the
same column, or in the same square -- it seems to me that even if
that is true for 5, that it cannot be true for any other value in that
row, column, nor square.

So obviously I'm missing something important here.  I just do not know
what question to ask.

Thanks,

-- 
Raul

On Sun, Nov 4, 2012 at 3:54 PM, Michal D. michal.dobrogost@I tgmail.com wrote:
 The adjacency matrix A is important because it tells us which constraint to
 look up in C.  This also explains why the lower diagonal is doubled.

 For example, take the less than constraint:

c =: |: (i.n) / (i.n)
2 2 $ '' ; 'Dx' ; 'Dy' ; c
 +--+---+
 |  |Dx |
 +--+---+
 |Dy|0 0 0 0|
 |  |1 0 0 0|
 |  |1 1 0 0|
 |  |1 1 1 0|
 +--+---+

 This constraint is useful for filtering Dx given Dy. Let's look at how
 revDom works (revDom is the heart of the algorithm).  Let's generate a
 domain for x and y.

Dx=: 1 1 1 1   NB. {0,1,2,3}
Dy=: 1 1 1 0   NB. {0,1,2}

 To visualize, stick Dy on the left, and Dx on top:

2 2 $ '' ; Dx ; (|:,:Dy) ; c
 +-+---+
 | |1 1 1 1|
 +-+---+
 |1|0 0 0 0|
 |1|1 0 0 0|
 |1|1 1 0 0|
 |0|1 1 1 0|
 +-+---+

 Now we use Dy to select the relevant rows of c (each row represents the set
 of values compatible with that value of Dy).

Dy # c
 0 0 0 0
 1 0 0 0
 1 1 0 0

 Take the logical-or of these rows to compute the set of values of Dx that
 have some compatible value in Dy.

+./ Dy # c
 1 1 0 0

 Finally, take the logical-and with Dx so we don't add values that weren't
 there in the first place.

Dx *. +./ Dy # c
 1 1 0 0

 Now, with all this done, what if we want to filter Dy on Dx?  We need to
 take the transpose of c.  To prevent constant transposing, A and C store
 these for us.

 Mike

 On Sun, Nov 4, 2012 at 9:53 AM, Mike Day mike_liz@tiscali.co.uk wrote:

 As far as I can understand the revise verb,  you don't need the
 adjacency matrix a, although it does help to have a 2-column matrix of
 index pairs.

 I think Raul has overlooked your use of the right argument ys within that
 verb,  though he's right about selecting with it. Here's a derivation of
 arcs without explicit recourse to the adjacency matrix  (I've just noticed
 that Raul presents a similar idiom):

 arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

 I. returns a vector of indices to the ravelled boolean;  $ #: turns them
 into a matrix of pairs of indices to an array of the shape of |:A.

 (]#~ (e.~ {.1)) selects those arcs with an element of ys as the from-node
 (or perhaps they're the to-nodes?)

 This form renders the arcs array already sorted,  but note that if you do
 need to sort the elements of an array,  it's sufficient to use the idiom
  /: ~(rather than ({~ /:)   . Presumably sorting arcs is merely a
 matter of taste.

 It's quite nice to be able to input several components of an argument by
 (local) name with
'A a C'=.x
'ys D'=. y
 rather than
 A=.  0{x
 a=.  1{x
 ys=.  0{y
 D=.   1{y

 As A is invariant in ac,   you could of course preset the array of
 indices for all arcs in A,  aix =: ($#: I.@,)  *|:Aand use aix as an
 input to revise instead of   a  .

 I used *|:A or (0|:A) here and wonder why you need to double its lower
 diagonal elements.

 I also wonder whether your example will still work if there are binary
 constraints involving variables (say z and t) indexed with 2 or 3.  And
 what happens if there are more than one binary constraints on a pair of
 variables?  eg,  X+Y=4 AND XY ?

 I'd have been very pleased with myself if I'd come up with code as good as
 this when I started J - would be pretty pleased if I managed it now!

 Mike



 On 04/11/2012 2:40 PM, Raul Miller wrote:

 In
 A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

 The 0= is unnecessary, and probably reflects a habit based on the
 false idea that boolean algebra is does not have an integer domain.
 Boolean rings have (subset of) integer domains, and [even after
 redefinition] boolean algebra is a boolean ring.

 If you ever want to treat Heyting Algebras or Bayesian Probability you
 might also want to consider what happens when you replace the $2 with
 $0.

 I think I would also be more comfortable with
 2 2 $ ''; 'y'; 'x'; A
 for the displayed table, but that's a minor quibble.

 An alternative definition for adj might be
 adj=:

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

The solver can solve sudoku puzzles (hopefully =)) but it should also be
able to handle more general csp instances where the constraints are not
symmetric.  In the case of a sudoku puzzle, I think a single symmetric
not-equal constraint would suffice.

   n=: 81
   d=: 9

   ] C=: a: ,  (i.d) ~:/ (i.d)
++-+
||0 1 1 1 1 1 1 1 1|
||1 0 1 1 1 1 1 1 1|
||1 1 0 1 1 1 1 1 1|
||1 1 1 0 1 1 1 1 1|
||1 1 1 1 0 1 1 1 1|
||1 1 1 1 1 0 1 1 1|
||1 1 1 1 1 1 0 1 1|
||1 1 1 1 1 1 1 0 1|
||1 1 1 1 1 1 1 1 0|
++-+

A is a little bit beyond me to define at the moment.  It would be an 81x81
matrix.  For a variable x, it would be 1 for all variables on the same row,
column and box as x and 0 otherwise.

Side note: as you can see, not-equal is not a very strong constraint.
Interleaving AC with search would probably be necessary to solve harder
sudoku instances.

Would changing:

NB. a single constraint (note: constraints are not symmetric, for example
xy).

to

NB. a single constraint (note: constraints may be asymmetric, for example
xy).

resolve the confusion?

Mike


On Sun, Nov 4, 2012 at 1:31 PM, Raul Miller rauldmil...@gmail.com wrote:

 I think I am having a problem envisioning how a sudoku-style puzzle
 can work with a relationship which is not commutative, and I am also
 having a problem having to do with the transitive character of the
 relationship.

 As you have put it:

(note: constraints are not symmetric, for example xy)

 I think I understand that in the general case we can have asymmetrical
 relationships, but taking sudoku as an example... I believe I
 understand 5 is not equal to any other value in the same row, in the
 same column, or in the same square.  But I am having a problem
 understanding 5 is less than any other value in the same row, in the
 same column, or in the same square -- it seems to me that even if
 that is true for 5, that it cannot be true for any other value in that
 row, column, nor square.

 So obviously I'm missing something important here.  I just do not know
 what question to ask.

 Thanks,

 --
 Raul

 On Sun, Nov 4, 2012 at 3:54 PM, Michal D. michal.dobrogost@I tgmail.com
 wrote:
  The adjacency matrix A is important because it tells us which constraint
 to
  look up in C.  This also explains why the lower diagonal is doubled.
 
  For example, take the less than constraint:
 
 c =: |: (i.n) / (i.n)
 2 2 $ '' ; 'Dx' ; 'Dy' ; c
  +--+---+
  |  |Dx |
  +--+---+
  |Dy|0 0 0 0|
  |  |1 0 0 0|
  |  |1 1 0 0|
  |  |1 1 1 0|
  +--+---+
 
  This constraint is useful for filtering Dx given Dy. Let's look at how
  revDom works (revDom is the heart of the algorithm).  Let's generate a
  domain for x and y.
 
 Dx=: 1 1 1 1   NB. {0,1,2,3}
 Dy=: 1 1 1 0   NB. {0,1,2}
 
  To visualize, stick Dy on the left, and Dx on top:
 
 2 2 $ '' ; Dx ; (|:,:Dy) ; c
  +-+---+
  | |1 1 1 1|
  +-+---+
  |1|0 0 0 0|
  |1|1 0 0 0|
  |1|1 1 0 0|
  |0|1 1 1 0|
  +-+---+
 
  Now we use Dy to select the relevant rows of c (each row represents the
 set
  of values compatible with that value of Dy).
 
 Dy # c
  0 0 0 0
  1 0 0 0
  1 1 0 0
 
  Take the logical-or of these rows to compute the set of values of Dx that
  have some compatible value in Dy.
 
 +./ Dy # c
  1 1 0 0
 
  Finally, take the logical-and with Dx so we don't add values that weren't
  there in the first place.
 
 Dx *. +./ Dy # c
  1 1 0 0
 
  Now, with all this done, what if we want to filter Dy on Dx?  We need to
  take the transpose of c.  To prevent constant transposing, A and C store
  these for us.
 
  Mike
 
  On Sun, Nov 4, 2012 at 9:53 AM, Mike Day mike_liz@tiscali.co.uk
 wrote:
 
  As far as I can understand the revise verb,  you don't need the
  adjacency matrix a, although it does help to have a 2-column matrix of
  index pairs.
 
  I think Raul has overlooked your use of the right argument ys within
 that
  verb,  though he's right about selecting with it. Here's a derivation of
  arcs without explicit recourse to the adjacency matrix  (I've just
 noticed
  that Raul presents a similar idiom):
 
  arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A
 
  I. returns a vector of indices to the ravelled boolean;  $ #: turns them
  into a matrix of pairs of indices to an array of the shape of |:A.
 
  (]#~ (e.~ {.1)) selects those arcs with an element of ys as the
 from-node
  (or perhaps they're the to-nodes?)
 
  This form renders the arcs array already sorted,  but note that if you
 do
  need to sort the elements of an array,  it's sufficient to use the idiom
   /: ~(rather than ({~ /:)   . Presumably sorting arcs is
 merely a
  matter of taste.
 
  It's quite nice to be able to input several components of an argument by
  (local) name with
 'A a C'=.x
 'ys D'=. y
  rather than
  A=.  0{x
  a=.  1{x
  ys=.  0{y
  D=.   1{y
 
  As A is invariant in ac,   you could of course preset the array of
  indices for

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

On Sun, Nov 4, 2012 at 4:47 PM, Michal D. michal.dobrog...@gmail.com wrote:
 The solver can solve sudoku puzzles (hopefully =)) but it should also be
 able to handle more general csp instances where the constraints are not
 symmetric.  In the case of a sudoku puzzle, I think a single symmetric
 not-equal constraint would suffice.

n=: 81
d=: 9

] C=: a: ,  (i.d) ~:/ (i.d)
 ++-+
 ||0 1 1 1 1 1 1 1 1|
 ||1 0 1 1 1 1 1 1 1|
 ||1 1 0 1 1 1 1 1 1|
 ||1 1 1 0 1 1 1 1 1|
 ||1 1 1 1 0 1 1 1 1|
 ||1 1 1 1 1 0 1 1 1|
 ||1 1 1 1 1 1 0 1 1|
 ||1 1 1 1 1 1 1 0 1|
 ||1 1 1 1 1 1 1 1 0|
 ++-+

 A is a little bit beyond me to define at the moment.  It would be an 81x81
 matrix.  For a variable x, it would be 1 for all variables on the same row,
 column and box as x and 0 otherwise.

Here's a brute force implementation of A for sudoku:

   C=: |: R=: ,9#,:i.9 NB. identity within columns (C) and rows (R)
   B=: ,3#3#1 i.3 3 NB. identity within boxes
   A=: ((2*/~i.81)+/~i.81) * (+. |:) (C =/ R) +. (C =/B ) +. (R =/ B)

I left the extraneous right-most set of parenthesis in place because I
liked the rhythm.

 Side note: as you can see, not-equal is not a very strong constraint.
 Interleaving AC with search would probably be necessary to solve harder
 sudoku instances.

 Would changing:

 NB. a single constraint (note: constraints are not symmetric, for example
 xy).

 to

 NB. a single constraint (note: constraints may be asymmetric, for example
 xy).

 resolve the confusion?

No, that was not my problem.  I think I understood the implicit may.

My problem is that I do not know how to look at results from this
computation and determine if they are correct, nor do I have an
illustrative set of test cases.

This means that I do not understand what you are talking about.  I
think I understand the words, but I obviously do not understand the
plot.

Reading over your notes, one of my problems is that I do not
understand what arc consistent state means.

Also, in the context of sudoku, I am not sure what D would be I'm
going to guess though that it would be an 81 row 9 column bit matrix,
with rows being all 1s for blanks in the sudoku puzzle, and being a
single 1 for digits in the sudoku puzzle.  Also, if a solver
returned any rows that were all zero, that would mean that that sudoku
puzzle has no solution.

Does this sound right?

If that is the case, how would this work, for a sudoku puzzle which
has multiple solutions?  Roger at one point mentioned a puzzle with
1905 solutions 
http://www.jsoftware.com/pipermail/programming/2005-December/000303.html

If D were instead a list of 81 by 9 bits, with extra copies of D being
introduced as necessary, the multiple answer case could be addressed
by having an extra item in D for every valid solution.  Here, the
initial D would have shape 1 81 9 and a final D would have shape n,81
9 where n is a (hopefully small) non-negative integer.

But that's not what you are doing here?

-- 
Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

On Sun, Nov 4, 2012 at 5:17 PM, I wrote:
 Here's a brute force implementation of A for sudoku:

C=: |: R=: ,9#,:i.9 NB. identity within columns (C) and rows (R)
B=: ,3#3#1 i.3 3 NB. identity within boxes
A=: ((2*/~i.81)+/~i.81) * (+. |:) (C =/ R) +. (C =/B ) +. (R =/ B)

That was wrong, in 4809 different locations.

Here's a corrected version:

   C=: , |: 9#,:i.9 NB. identity within columns (C)
   R=: ,9#,:i.9 NB. identity within rows (R)
   B=: ,3#3#1 i.3 3 NB. identity within boxes
   A=: ((2*/~i.81)+/~i.81) * (+. |:) (C =/ R) +. (C =/B ) +. (R =/ B)

FYI,

-- 
Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

 Here's a brute force implementation of A for sudoku:

C=: |: R=: ,9#,:i.9 NB. identity within columns (C) and rows (R)
B=: ,3#3#1 i.3 3 NB. identity within boxes
A=: ((2*/~i.81)+/~i.81) * (+. |:) (C =/ R) +. (C =/B ) +. (R =/ B)

 I left the extraneous right-most set of parenthesis in place because I
 liked the rhythm.


Nice!  I haven't gone through it yet.


 My problem is that I do not know how to look at results from this
 computation and determine if they are correct, nor do I have an
 illustrative set of test cases.


Yes, this is unfortunate, but I can only do so much in J and inspecting
randomly generated values was possible for me.


 Reading over your notes, one of my problems is that I do not
 understand what arc consistent state means.


Arc consistent means that for every pair of adjacent variables, x and y,
every value in Dx is compatible with at least one value in Dy.

Put another way, there is no value v in Dx such that the v is not
consistent with any value w in Dy.



 Also, in the context of sudoku, I am not sure what D would be I'm
 going to guess though that it would be an 81 row 9 column bit matrix,
 with rows being all 1s for blanks in the sudoku puzzle, and being a
 single 1 for digits in the sudoku puzzle.  Also, if a solver
 returned any rows that were all zero, that would mean that that sudoku
 puzzle has no solution.

 Does this sound right?


Yes, that is exactly right.



 If that is the case, how would this work, for a sudoku puzzle which
 has multiple solutions?  Roger at one point mentioned a puzzle with
 1905 solutions
 http://www.jsoftware.com/pipermail/programming/2005-December/000303.html


Harder sudokus, or sudokus with multiple solutions, will require
interleaving the ac-filtering with search.  The search consists of guessing
a value for an unassigned variable and assigning that value to the
variable.  At that point you can run '... ac (x;D)' where x is the assigned
variable and D is the domain with Dx assigned to a single value.  If this
produces a D for which isValid is false, we backtrack and try assigning
another value for x.  When we exhaust all values for x we backtrack to the
previous variable we have guessed values for.

The search is nowhere to be seen in the code,



 If D were instead a list of 81 by 9 bits, with extra copies of D being
 introduced as necessary, the multiple answer case could be addressed
 by having an extra item in D for every valid solution.  Here, the
 initial D would have shape 1 81 9 and a final D would have shape n,81
 9 where n is a (hopefully small) non-negative integer.

 But that's not what you are doing here?


TODO ;-)

Although this could potentially be dangerous.  For example the completely
empty sudoku puzzle has very many solutions and I doubt my computer would
have the patience to go through them all.

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

 As far as I can understand the revise verb,  you don't need the
 adjacency matrix a, although it does help to have a 2-column matrix of
 index pairs.

 I think Raul has overlooked your use of the right argument ys within that
 verb,  though he's right about selecting with it. Here's a derivation of
 arcs without explicit recourse to the adjacency matrix  (I've just noticed
 that Raul presents a similar idiom):

 arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

 I. returns a vector of indices to the ravelled boolean;  $ #: turns them
 into a matrix of pairs of indices to an array of the shape of |:A.

 (]#~ (e.~ {.1)) selects those arcs with an element of ys as the from-node
 (or perhaps they're the to-nodes?)


This is a marvel of engineering to be sure ;-).  It took me quite some time
to figure out #: (which require figuring out #. (which required figuring
out /.)).  Wow.  #. and #: seem useful and the fact that you can list
different bases as the left argument is blowing my mind a little bit.  I
did trace through and understand what's meant.  Nice.

|: is not needed since *A should always be symmetric matrix.  If a
constraint between x and y is symmetric, then Axy = Ayx, otherwise Axy is
the index of the transpose constraint at index Ayx.

I'm not sure if we want to remove the adjacency list 'a' in the end
though.  'A' may be sparse and having 'a' should speed up computation (?).
In my long standing csp problem I have an 'A' that has dimensions 256x256
but each variable has at most 4 neighbors.

This form renders the arcs array already sorted,  but note that if you do
 need to sort the elements of an array,  it's sufficient to use the idiom
  /: ~(rather than ({~ /:)   . Presumably sorting arcs is merely a
 matter of taste.


Yes, sorting is unnecessary.  It was brought over from a previous version
of the code from which the current version was distilled.  I lacked the
cojones to throw it out.  This just shows that public dissection is nice to
force these choices.  =)  The J code is serving as prototype for some
OpenCL code and I'm not sure how nicely things will play out there (ie. it
may be better to have the locality of having the arcs sorted).  I've
removed the sorting.



 It's quite nice to be able to input several components of an argument by
 (local) name with
'A a C'=.x
'ys D'=. y
 rather than
 A=.  0{x
 a=.  1{x
 ys=.  0{y
 D=.   1{y


Great, thank you, I was looking for something like this.


 I also wonder whether your example will still work if there are binary
 constraints involving variables (say z and t) indexed with 2 or 3.  And
 what happens if there are more than one binary constraints on a pair of
 variables?  eg,  X+Y=4 AND XY ?


Haven't tried having more than two constraints, indexed with 2, 3 etc., but
it should work.

If you want to have two constraints (X+Y=4 AND XY) in the current scheme
you need to make a new entry in C with the and of both of them.



 I'd have been very pleased with myself if I'd come up with code as good as
 this when I started J - would be pretty pleased if I managed it now!


Thanks =)

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Mike Day

Good one!   I tend to overlook sparse arrays as I seem to encounter 
nonce errors when trying to use them for real.


Mike

On 04/11/2012 7:03 PM, R.E. Boss wrote:

Your ($#: I.@,)  can be replaced:

((4$. $.) -: $#: I.@,)  4 5$ 0 1 0
1


R.E. Boss



-Oorspronkelijk bericht-
Van: programming-boun...@forums.jsoftware.com 
[mailto:programming-boun...@forums.jsoftware.com] Namens Mike Day
Verzonden: zondag 4 november 2012 18:53
Aan: programm...@jsoftware.com
Onderwerp: Re: [Jprogramming] Arc consistency in J

As far as I can understand the revise verb,  you don't need the
adjacency matrix a, although it does help to have a 2-column matrix of
index pairs.

I think Raul has overlooked your use of the right argument ys within
that verb,  though he's right about selecting with it. Here's a
derivation of arcs without explicit recourse to the adjacency matrix
(I've just noticed that Raul presents a similar idiom):

  arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

I. returns a vector of indices to the ravelled boolean;  $ #: turns them
into a matrix of pairs of indices to an array of the shape of |:A.

(]#~ (e.~ {.1)) selects those arcs with an element of ys as the
from-node (or perhaps they're the to-nodes?)

This form renders the arcs array already sorted,  but note that if you
do need to sort the elements of an array,  it's sufficient to use the
idiom  /: ~(rather than ({~ /:)   . Presumably sorting arcs is
merely a matter of taste.

It's quite nice to be able to input several components of an argument by
(local) name with
 'A a C'=.x
 'ys D'=. y
rather than
  A=.  0{x
  a=.  1{x
  ys=.  0{y
  D=.   1{y

As A is invariant in ac,   you could of course preset the array of
indices for all arcs in A,  aix =: ($#: I.@,)  *|:Aand use aix as an
input to revise instead of   a  .

I used *|:A or (0|:A) here and wonder why you need to double its lower
diagonal elements.

I also wonder whether your example will still work if there are binary
constraints involving variables (say z and t) indexed with 2 or 3.  And
what happens if there are more than one binary constraints on a pair of
variables?  eg,  X+Y=4 AND XY ?

I'd have been very pleased with myself if I'd come up with code as good
as this when I started J - would be pretty pleased if I managed it now!

Mike


On 04/11/2012 2:40 PM, Raul Miller wrote:

In
 A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

The 0= is unnecessary, and probably reflects a habit based on the
false idea that boolean algebra is does not have an integer domain.
Boolean rings have (subset of) integer domains, and [even after
redefinition] boolean algebra is a boolean ring.

If you ever want to treat Heyting Algebras or Bayesian Probability you
might also want to consider what happens when you replace the $2 with
$0.

I think I would also be more comfortable with
 2 2 $ ''; 'y'; 'x'; A
for the displayed table, but that's a minor quibble.

An alternative definition for adj might be
 adj=: @I.@:*

But somewhere around here, I get lost.  Your use pattern for arcsX is:

 (i.n) arcsX A

where A has the shape n,n

What is the domain of the left argument of arcsX?  I am guessing that
it's either i.n or a single element choosen from i.n but if that is
the case, I think I'd define arcsX to only work for the i.n case --
the name says arcs after all.  Also, if I wanted to extract the
values from the result of arcsX which correspond to a single value
from i. n, that's simple enough -- I can select on the first column of
the result.

In other words, perhaps something like this:

 arcs=: $ #: I.@,
 arcs *A

Also, I have not taken the time yet, to read revise, so I will stop here.


--
For information about J forums see http://www.jsoftware.com/forums.htm

--
For information about J forums see http://www.jsoftware.com/forums.htm



--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Mike Day


Hello, Michal D - Mike Day here!

Sorry,  I meant your lower case a,  the boxed array of to-nodes, 
derived from upper case A which IS the adjacency matrix, which is of 
course essential.  revise need not be provided with a as well as A,  
and can make do with the 2-column matrix of node-pairs instead.  RE Boss 
demonstrates a nice side-effect of sparse arrays (4 $. $.) .


OK - I'd never used {:: so didn't appreciate the subtlety of the ones 
and twos in A!  So would you need 3s  4s etc in A to cater for 
constraints on pairs of variables other than the first two?


the other Mike D


On 04/11/2012 8:54 PM, Michal D. wrote:

The adjacency matrix A is important because it tells us which constraint to
look up in C.  This also explains why the lower diagonal is doubled.

For example, take the less than constraint:

c =: |: (i.n) / (i.n)
2 2 $ '' ; 'Dx' ; 'Dy' ; c
+--+---+
|  |Dx |
+--+---+
|Dy|0 0 0 0|
|  |1 0 0 0|
|  |1 1 0 0|
|  |1 1 1 0|
+--+---+

This constraint is useful for filtering Dx given Dy. Let's look at how
revDom works (revDom is the heart of the algorithm).  Let's generate a
domain for x and y.

Dx=: 1 1 1 1   NB. {0,1,2,3}
Dy=: 1 1 1 0   NB. {0,1,2}

To visualize, stick Dy on the left, and Dx on top:

2 2 $ '' ; Dx ; (|:,:Dy) ; c
+-+---+
| |1 1 1 1|
+-+---+
|1|0 0 0 0|
|1|1 0 0 0|
|1|1 1 0 0|
|0|1 1 1 0|
+-+---+

Now we use Dy to select the relevant rows of c (each row represents the set
of values compatible with that value of Dy).

Dy # c
0 0 0 0
1 0 0 0
1 1 0 0

Take the logical-or of these rows to compute the set of values of Dx that
have some compatible value in Dy.

+./ Dy # c
1 1 0 0

Finally, take the logical-and with Dx so we don't add values that weren't
there in the first place.

Dx *. +./ Dy # c
1 1 0 0

Now, with all this done, what if we want to filter Dy on Dx?  We need to
take the transpose of c.  To prevent constant transposing, A and C store
these for us.

Mike

On Sun, Nov 4, 2012 at 9:53 AM, Mike Day mike_liz@tiscali.co.uk wrote:


As far as I can understand the revise verb,  you don't need the
adjacency matrix a, although it does help to have a 2-column matrix of
index pairs.

I think Raul has overlooked your use of the right argument ys within that
verb,  though he's right about selecting with it. Here's a derivation of
arcs without explicit recourse to the adjacency matrix  (I've just noticed
that Raul presents a similar idiom):

 arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

I. returns a vector of indices to the ravelled boolean;  $ #: turns them
into a matrix of pairs of indices to an array of the shape of |:A.

(]#~ (e.~ {.1)) selects those arcs with an element of ys as the from-node
(or perhaps they're the to-nodes?)

This form renders the arcs array already sorted,  but note that if you do
need to sort the elements of an array,  it's sufficient to use the idiom
  /: ~(rather than ({~ /:)   . Presumably sorting arcs is merely a
matter of taste.

It's quite nice to be able to input several components of an argument by
(local) name with
'A a C'=.x
'ys D'=. y
rather than
 A=.  0{x
 a=.  1{x
 ys=.  0{y
 D=.   1{y

As A is invariant in ac,   you could of course preset the array of
indices for all arcs in A,  aix =: ($#: I.@,)  *|:Aand use aix as an
input to revise instead of   a  .

I used *|:A or (0|:A) here and wonder why you need to double its lower
diagonal elements.

I also wonder whether your example will still work if there are binary
constraints involving variables (say z and t) indexed with 2 or 3.  And
what happens if there are more than one binary constraints on a pair of
variables?  eg,  X+Y=4 AND XY ?

I'd have been very pleased with myself if I'd come up with code as good as
this when I started J - would be pretty pleased if I managed it now!

Mike



On 04/11/2012 2:40 PM, Raul Miller wrote:


In
 A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

The 0= is unnecessary, and probably reflects a habit based on the
false idea that boolean algebra is does not have an integer domain.
Boolean rings have (subset of) integer domains, and [even after
redefinition] boolean algebra is a boolean ring.

If you ever want to treat Heyting Algebras or Bayesian Probability you
might also want to consider what happens when you replace the $2 with
$0.

I think I would also be more comfortable with
 2 2 $ ''; 'y'; 'x'; A
for the displayed table, but that's a minor quibble.

An alternative definition for adj might be
 adj=: @I.@:*

But somewhere around here, I get lost.  Your use pattern for arcsX is:

 (i.n) arcsX A

where A has the shape n,n

What is the domain of the left argument of arcsX?  I am guessing that
it's either i.n or a single element choosen from i.n but if that is
the case, I think I'd define arcsX to only work for the i.n case --
the name says arcs after all.  Also, if I wanted to extract the
values from the result of arcsX

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

On Sun, Nov 4, 2012 at 6:29 PM, Michal D. michal.dobrog...@gmail.com wrote:
 for all w in Dy there exists a v in Dx such that the relationship v
 compare w is true.

 Does this sound right?

 Yes, that sounds right so long as compare implies looking up the values in
 the correct constraint table. Your formulation also sounds consistent with
 what I said before signalling that something has been lost in translation!
 consistent = compatible = relationship is true

Ok!

I had somehow gotten a different idea of consistency:

   for all w in Dy for all v in Dx the relationship v compare w is true

Now that I know what to look for, though, I see the existential
constraint in the wikipedia article.  (I'm still a bit shaky about the
terminology, but I'm beginning to feel like I understand what you are
doing.)

But I imagine that that is the point of calling it arc consistency
-- each arc is consistent to itself, but need not be consistent with
other arcs?

So...

An consistent arc seems to be implemented as a pair of set bits in D
which corresponds to a set bit in A and a set bit in C.  (So we
consider all the possible cases and if any of them are true we are
satisfied.)

Except you have C implemented a s a pair -- a matrix and its
transpose.  [That's an optimization for performance, though, and I
feel that that should take back seat to simplicity except where it has
a significant measurable benefit which exceeds its cost (complexity
always has a cost).]

A matches along the leading D dimension, C matches along the trailing
D dimension.  The bit pair in D thus corresponds to a row/column pair
against A as well as against C.

A tricky part seems to be that the upper triangle of A corresponds to
the forward direction in C (the bit in D that selects a row in A is
also selecting a row in C) while the lower triangle of A corresponds
to the reverse direction in C.  But I'm not seeing anything like this
in the text of the wikipedia entry.  And, if the diagram on the right
hand side is meant to be an illustration where the constraint is x  y
then it looks like we do not care about the order of the two
variables.  In other words, if we specify the constraint x  y it
looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
consistency.  In other words, i think we should always use the
symmetric closure of the constraint.

Does this sound valid to you?

If not, where have I gone astray?

Thanks,

-- 
Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

Haha, hello Mike D!

I figured you were talking about a.  I think I followed the 2-column
matrix of node-pairs conversation for the most part, except for RE Boss's
contribution which I didn't appreciate until just now.  The -: initially
threw me off so I thought the whole expression was replaced and not just
the generate node-pairs part.  It's quite clever but also very specialized
to J, it would be nice to use more primitive operations.  Why the dislike
for a?  I'm guessing it's a stab at removing some of the code?

Yes, the idea is that 0{C is the empty box corresponding to the 0 indices
in A.  Also (: #C)   =   (./ ,A) - that is the number of entries in C
minus 1 corresponds to the maximum index in A.  So you could imagine A with
3s, 4s, etc.

Cheers,

Mike


On Sun, Nov 4, 2012 at 4:21 PM, Mike Day mike_liz@tiscali.co.uk wrote:

 Hello, Michal D - Mike Day here!

 Sorry,  I meant your lower case a,  the boxed array of to-nodes, derived
 from upper case A which IS the adjacency matrix, which is of course
 essential.  revise need not be provided with a as well as A,  and can
 make do with the 2-column matrix of node-pairs instead.  RE Boss
 demonstrates a nice side-effect of sparse arrays (4 $. $.) .

 OK - I'd never used {:: so didn't appreciate the subtlety of the ones and
 twos in A!  So would you need 3s  4s etc in A to cater for constraints on
 pairs of variables other than the first two?

 the other Mike D



 On 04/11/2012 8:54 PM, Michal D. wrote:

 The adjacency matrix A is important because it tells us which constraint
 to
 look up in C.  This also explains why the lower diagonal is doubled.

 For example, take the less than constraint:

 c =: |: (i.n) / (i.n)
 2 2 $ '' ; 'Dx' ; 'Dy' ; c
 +--+---+
 |  |Dx |
 +--+---+
 |Dy|0 0 0 0|
 |  |1 0 0 0|
 |  |1 1 0 0|
 |  |1 1 1 0|
 +--+---+

 This constraint is useful for filtering Dx given Dy. Let's look at how
 revDom works (revDom is the heart of the algorithm).  Let's generate a
 domain for x and y.

 Dx=: 1 1 1 1   NB. {0,1,2,3}
 Dy=: 1 1 1 0   NB. {0,1,2}

 To visualize, stick Dy on the left, and Dx on top:

 2 2 $ '' ; Dx ; (|:,:Dy) ; c
 +-+---+
 | |1 1 1 1|
 +-+---+
 |1|0 0 0 0|
 |1|1 0 0 0|
 |1|1 1 0 0|
 |0|1 1 1 0|
 +-+---+

 Now we use Dy to select the relevant rows of c (each row represents the
 set
 of values compatible with that value of Dy).

 Dy # c
 0 0 0 0
 1 0 0 0
 1 1 0 0

 Take the logical-or of these rows to compute the set of values of Dx that
 have some compatible value in Dy.

 +./ Dy # c
 1 1 0 0

 Finally, take the logical-and with Dx so we don't add values that weren't
 there in the first place.

 Dx *. +./ Dy # c
 1 1 0 0

 Now, with all this done, what if we want to filter Dy on Dx?  We need to
 take the transpose of c.  To prevent constant transposing, A and C store
 these for us.

 Mike

 On Sun, Nov 4, 2012 at 9:53 AM, Mike Day mike_liz@tiscali.co.uk
 wrote:

  As far as I can understand the revise verb,  you don't need the
 adjacency matrix a, although it does help to have a 2-column matrix of
 index pairs.

 I think Raul has overlooked your use of the right argument ys within that
 verb,  though he's right about selecting with it. Here's a derivation of
 arcs without explicit recourse to the adjacency matrix  (I've just
 noticed
 that Raul presents a similar idiom):

  arcs=. ys  (]#~ (e.~ {.1))   ($#: I.@,)  *|:A

 I. returns a vector of indices to the ravelled boolean;  $ #: turns them
 into a matrix of pairs of indices to an array of the shape of |:A.

 (]#~ (e.~ {.1)) selects those arcs with an element of ys as the
 from-node
 (or perhaps they're the to-nodes?)

 This form renders the arcs array already sorted,  but note that if you do
 need to sort the elements of an array,  it's sufficient to use the idiom
   /: ~(rather than ({~ /:)   . Presumably sorting arcs is
 merely a
 matter of taste.

 It's quite nice to be able to input several components of an argument by
 (local) name with
 'A a C'=.x
 'ys D'=. y
 rather than
  A=.  0{x
  a=.  1{x
  ys=.  0{y
  D=.   1{y

 As A is invariant in ac,   you could of course preset the array of
 indices for all arcs in A,  aix =: ($#: I.@,)  *|:Aand use aix as an
 input to revise instead of   a  .

 I used *|:A or (0|:A) here and wonder why you need to double its lower
 diagonal elements.

 I also wonder whether your example will still work if there are binary
 constraints involving variables (say z and t) indexed with 2 or 3.  And
 what happens if there are more than one binary constraints on a pair of
 variables?  eg,  X+Y=4 AND XY ?

 I'd have been very pleased with myself if I'd come up with code as good
 as
 this when I started J - would be pretty pleased if I managed it now!

 Mike



 On 04/11/2012 2:40 PM, Raul Miller wrote:

  In
  A=. 0= ? (2$n)$2   NB. generate random matrix of [0,1]

 The 0= is unnecessary, and probably reflects a habit based

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Raul Miller

On Sun, Nov 4, 2012 at 9:46 PM, Michal D. michal.dobrog...@gmail.com wrote:
 to J, it would be nice to use more primitive operations.  Why the dislike
 for a?  I'm guessing it's a stab at removing some of the code?

Passing the same data, multiple ways, to  J function is something of a
bad code smell.

Sometimes it's warranted, but we tend to feel a need to investigate
what happens when we eliminate the redundancy.

There are a variety of issues here, ranging from CPU cache
architecture to the nature of J primitive overhead to code simplicity.

And, even if we do not use it, we might keep a copy of a simple
expression to document what a more complicated expression is doing.

-- 
Raul
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-04 Thread Michal D.

  variables.  In other words, if we specify the constraint x  y it
  looks like either x1  x2 or x2  x1 is sufficient to satisfy arc
  consistency.  In other words, i think we should always use the
  symmetric closure of the constraint.
 
  Does this sound valid to you?
 
  Unfortunately not.  There are no values that can satisfy x1x2 and x2x1.
  If this was the case all csps would have no solutions

 I meant x1x2 OR x2x1

 So symmetric closure was the wrong term for me to use.

 But I think we want to be using intersection of the relationship with
 its inverse.

 Does that sound right to you?


Sorry I missed the or.  Unfortunately not, I mean you can have a constraint
like that if you want but you don't have to have to in general.  I think
we're dwelling on an implementation detail.  They (wikipedia) must just
have the  constraint propagating both ways.

My brain is fried but I did hack together an ugly search procedure.  You
can try it out on a sudoku puzzle if you want.  For some reason I couldn't
generate it using the code you gave me.  http://pastebin.com/2zPB4DBA

Maybe we can update the printf docs to say:
load 'format/printf'
http://www.jsoftware.com/help/jforc/input_and_output.htm

Cheers,

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-03 Thread Linda Alvord

I can't seem to stop myself from answering stylequestions:

I learned APL from Ken and was greatly influenced his notion of notation as
a tool of thght. To me he was a mathematician first. So  look at the start
of Taylor Coefficients as influenced by some of Raul's rules:

   X=:10%~I=:i.8
   I
0 1 2 3 4 5 6 7
   X
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
   F=: 1 2 1p. 
   F
1 2 1p.
   5!:4 'F'
  ┌─ 1 2 1
──  ─┴─ p.   
   F 5
36
   F X
1 1.21 1.44 1.69 1.96 2.25 2.56 2.89
   
NB. c p. x  ↔  +/c*x^i.#c from vocabulary
   
   PD=: 13 :'+/x*y^i.#x'   NB.  p.  or p dot   
   PD
[: +/ [ * ] ^ [: i. [: # [
   
   5!:4 'PD'
  ┌─ [:   
  ├─ / ─── +  
  │   
──┤ ┌─ [  
  │ ├─ *  
  └─┤   ┌─ ]  
│   ├─ ^  
└───┤   ┌─ [:  y   
│   ├─ i. 
└───┤┌─ [:
└┼─ # 
 └─ [ 

Build PD by:  tally  x , integers of tally  x, y to power of integers of
tally  x  and so forth ending with the sum of everything. As you build,
some of the “trimmings” are being handled for you. Forks and hooks are
inserted.
   
   PD 5
5
   |length error: PD
|   1 2 1 PD X

So, back to the drawing board:

#1 2 1 
3
   i.#1 2 1 
0 1 2
   X^/ i.#1 2 1 
1   00
1 0.1 0.01
1 0.2 0.04
1 0.3 0.09
1 0.4 0.16
1 0.5 0.25
1 0.6 0.36
1 0.7 0.49
   (+/1) 1 2 1*1 X^/i.#1 2 1  
1 1.21 1.44 1.69 1.96 2.25 2.56 2.89
   PD=: 13 :'+/1 x*1 y^/i.#x'
   PD
[: +/1 [ *1 ] ^/ [: i. [: # [
   5!:4 'PD'
  ┌─ [:   
  │ ┌─ / ─── +
  ├─  ─┴─ 1  
  │   
──┤ ┌─ [  
  │ │ ┌─ *
  │ ├─  ─┴─ 1
  │ │ 
  └─┤ ┌─ ]
│ ├─ / ─── ^  
│ │   
└─┤ ┌─ [: 
  │ ├─ i. 
  └─┤┌─ [:
└┼─ # 
 └─ [ 
   1 2 1 PD X
1 1.21 1.44 1.69 1.96 2.25 2.56 2.89

The story has a happy ending.

Linda

-Original Message-
From: programming-bounces@forums.jsoftware.commailto:programming-bo
un...@forums.jsoftware.com] On Behalf Of Raul Miller
Sent: Friday, November 02, 2012 1:04 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J

On Fri, Nov 2, 2012 at 1:01 AM, Michal D. michal.dobrog...@gmail.com
wrote:
 Hi All,

 I've managed to write my first not-completely-trivial program in J.  
 It implements an arc consistency algorithm ( 
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I 
 would appreciate any comments regarding style, what I'm doing wrong in 
 J or how to improve the code.  I also have a couple of questions of my
own:

Personally, I use mostly coding guidelines.  I recognize that there will
need to be cases where I do not comply with my own guidelines, but I use
these guidelines when I have no reason to do something
different:

No space between name and copula.  This makes it easy to search for
assignments to a name.

Case of name represents type assigned to name.  NOUNS, verbs,
Adverbs/Conjunctions

Feel free to ignore these...

 1) how do I avoid @ especially once we remove explicit arguments?

@ is function composition.  It looks ugly because J limits itself to ASCII
sequences for its language.  What we would ideally want is a character that
looks like a small circle (but elevated slightly, to avoid confusion with
the letter o)  But ASCII itself is ugly -- ASCII's value is not its beauty
but its ubiquity.  That said, here are some equivalent cases:

  f@g
  f@:gg
  ([: f g)g
  fg@(]g)
  f:g@(]g)

Depending on your context, you may be able to remove @(]g) or g and still
retain equivalence, and additional equivalences may also be valid.  For
example:

  f@g y
  fg y
  f g y

 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?

Here are some alternative arcsX definitions:
arcsX1=:   [: ; [ ,.. {
arcsX2=:   [  ((#~ #@) ,. ;@]) {

 3) Is a boxed value always a pointer? One could imagine implementing 
 'ragged' arrays without pointers.

That is how they are currently implemented, yes.

 4) Is there a good way to have named variables (ie. avoid getx, gety)?

Define good...

One option is to use explicit code -- the definition of explicit code is
essentially named variables.

 5) Why is a hook the default and not composition?

It's historical:

http://www.jsoftware.com/pipermail/general/2006-January/026271.html
http://www.jsoftware.com/pipermail/general/2006-January/026274.html

 Code at: http://pastebin.com/k4XuKfFi

I have not taken the time to fully digest what you are doing there, but
it's possible that by characterizing the data differently the expressions
could be made more direct.  I cannot guarantee this (because I have not
taken the time to understand the purpose of what you are doing), but that
has been my experience in many other

Re: [Jprogramming] Arc consistency in J

2012-11-03 Thread Michal D.

Thank you everyone for the comments and encouragement.

I think Bo's (?]) and accompanying code was an interesting illustration of
a nice use of the hook.  I'm not sure why to prefer doubling an entire
array as opposed to dividing a single scalar?  I think that inlining getx
and gety is anti-style ;-).  See also all the argument unwrapping that
happens in the new revise.  Too bad there is no way to prevent this.

I take it that picking # over $ is a purely stylistic preference.  I
appreciate all the comments regarding coppula and NB.*, both sound like a
good idea.

The historical comments regarding a hook conjunction exactly mirror my
frustrations.  Thank you Raul also for arcsX2, that is a thing of beauty =).

New and improved code at http://pastebin.com/fzs0GAev with an expanded
intro to CSPs.

Cheers,

Mike

On Thu, Nov 1, 2012 at 10:01 PM, Michal D. michal.dobrog...@gmail.comwrote:

 Hi All,

 I've managed to write my first not-completely-trivial program in J.  It
 implements an arc consistency algorithm (
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I would
 appreciate any comments regarding style, what I'm doing wrong in J or how
 to improve the code.  I also have a couple of questions of my own:

 1) how do I avoid @ especially once we remove explicit arguments?
 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
 3) Is a boxed value always a pointer? One could imagine implementing
 'ragged' arrays without pointers.
 4) Is there a good way to have named variables (ie. avoid getx, gety)?
 5) Why is a hook the default and not composition?

 Code at: http://pastebin.com/k4XuKfFi

 Cheers!

 Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-02 Thread Bo Jacoby

Hi Mike
You request comments regarding style. Style is a matter of taste, so don't take 
my comments as criticism. 
Your very first expression 

   (n%2)(]?]) n$d
can be written without division:

   n+:(?])n#dThe value depends on two variable, n and d, and so you may create 
a dyadic verb, focusing attention on functions rather than on variables.
   n( 4 : 'x+:(?]) x#y')d

or, using tacit code:
   n([[:+:[:(?])#)d


Your questions:

1) how do I avoid @ especially once we remove explicit arguments?
- by using cap. ([:)


4) Is there a good way to have named variables (ie. avoid getx, gety)?
replace
   getx   =: 0{ ]
   gety   =: 1{ ]
   revDom =: getx *. +./ @ (gety # [)
with
   revDom =: (0{ ]) *. +./ @ ((1{ ]) # [)


5) Why is a hook the default and not composition?
- Because J'ers love hooks! For composition use the capped fork ([: f g)

-Bo




 Fra: Michal D. michal.dobrog...@gmail.com
Til: programm...@jsoftware.com 
Sendt: 6:01 fredag den 2. november 2012
Emne: [Jprogramming] Arc consistency in J
 
Hi All,

I've managed to write my first not-completely-trivial program in J.  It
implements an arc consistency algorithm (
http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I would
appreciate any comments regarding style, what I'm doing wrong in J or how
to improve the code.  I also have a couple of questions of my own:

1) how do I avoid @ especially once we remove explicit arguments?
2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
3) Is a boxed value always a pointer? One could imagine implementing
'ragged' arrays without pointers.
4) Is there a good way to have named variables (ie. avoid getx, gety)?
5) Why is a hook the default and not composition?

Code at: http://pastebin.com/k4XuKfFi

Cheers!

Mike
--
For information about J forums see http://www.jsoftware.com/forums.htm



--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Arc consistency in J

2012-11-02 Thread David Ward Lambert

If your program works I'd say you aren't doing something wrong.
Raul Miller proposed a naming convention which I've found useful.  In
short:

NOUN Conjunction Adverb verb

I think you'd do well to next learn the ~ adverb, reflex/passive.
And someday you'll run across the special code page:
http://www.jsoftware.com/help/dictionary/special.htm
These are phrases that occur often enough to warrant c code to speed
their operation.

Congratulations!


 Date: Thu, 1 Nov 2012 22:01:41 -0700
 From: Michal D. michal.dobrog...@gmail.com
 To: programm...@jsoftware.com
 Subject: [Jprogramming] Arc consistency in J
 Message-ID:
 CAO37ydBc2LP8ERHXVOYRsjHZ3apx9T3
 +urszqjukp7hrxdl...@mail.gmail.com
 Content-Type: text/plain; charset=ISO-8859-1
 
 Hi All,
 
 I've managed to write my first not-completely-trivial program in J.
 It
 implements an arc consistency algorithm (
 http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).  I
 would
 appreciate any comments regarding style, what I'm doing wrong in J or
 how
 to improve the code.


--
For information about J forums see http://www.jsoftware.com/forums.htm

57 matches

Mail list logo