4 ms·

Honestly, I can see more than 4 lines of code there.

by pkolaczk 11y ago

agumonkey 11y ago
nqueens is ~4, the rest is output
- eggy 11y ago
  One line of J code taken from the jsoftware site [1]: queenst =: (, #: I.@,@(</)&i.)~ (] #"1~ [ */@:~:&(|@-/) {)&.|: ! A.&i. ] This is the calculation, and you can output all 92 solutions for the 8 queens problems like this: queenst 8 0 4 7 5 2 6 1 3 0 5 7 2 6 3 1 4 0 6 3 5 7 1 4 2 .... each column is a row number, and the integer is which column the queen is in, or vice versa on rows and columns. ,or print how many solutions $queens 92 8 $ gives the 'shape' of the array, that is 92 rows (solutions) x 8 columns (8-queens problem). I always return to J, because I enjoy mathematics and functional programming. Like math, you work with symbols you learn to think as you code in an interpreted window, somewhat like when working in the Lisp REPL. Ken Iverson created the APL language in 1960, and won an ACM Turing Award and gave a lecture 'Notation as a Tool of Thought', which sums it up better than I could ever hope to express it [3]. J was a collaboration between him, Arthur Whitney (of finance's k language, and kdb fame), and Roger Hui, in an attempt to improve on APL, and to do away with needing a special character keyboard. It is under the GPL3 license today. J uses the ASCII character set, and is very functional and composable. [1] http://code.jsoftware.com/wiki/Essays/N_Queens_Problem [2] http://code.jsoftware.com/wiki/Essays/Queens_and_Knights [3] http://www.jsoftware.com/papers/tot.htm
  - agumonkey 11y ago
    Always good to see some APL/J
  - jxy 11y ago
    > queenst =: (, #: I.@,@(</)&i.)~ (] #"1~ [ */@:~:&(|@-/) {)&.|: ! A.&i. ] So this must be the origin of the one liner from [0] queens←{⍵{((+/b)⌿⍵),⍺|(,b)/⍳×/⍴b←~↑(⊂⍳⍺)∊¨(↓⍵)+[0]¨⊂(c-⍳c←1↓⍴⍵)∘.×¯1 0 1}⍣⍵⍳1 0} Somehow J is shorter? I need someone who speaks both J and APL to tell me if they are the same. Never learned J, but I always return to APL. I guess J to APL is like latin alphabet to chinese characters. You don't need a special keyboard for APL, just like you don't need a special keyboard for Chinese. Sometimes I really don't understand why they started J. Native English speaker's mentality? We never needed special keyboard for diacritics, let alone east asian languages. With an input method for APL characters, J does not even save the number of keystrokes. [0] https://dfns.dyalog.com/n_queens.htm https://dfns.dyalog.com/n_queens.htm
    - jxy 11y ago
      I was wrong. The two one-liners for J and APL are different. The original paper [0] gives the original APL implementation of the above J one-liner. I'm not going to delve deep into the algorithm, but the following quote from the paper fascinates me. It is voracious for work space. For concreteness, consider the case n←8 . The intermediate expression p[;c] has shape (!8),(2!8),2 , requiring 9031704 bytes on IBM-based APL systems. It uses 9 MB! Such a 'voracious' algorithm! [0] http://www.jsoftware.com/papers/nqueens.htm http://www.jsoftware.com/papers/nqueens.htm
      - RodgerTheGreat 11y ago
        Even by modern standards that's a pretty hefty chunk of RAM for n=8.
        agumonkey 11y ago
        Still smaller that an 2016 app favicon.
        jxy 11y ago
        The problem is that the complexity is O(n²n!)
        eggy 11y ago
        I am not a J guru, but that is just the concise implementation. There are others in the references previously cited. J is an interpreted language, and when doing db stuff, it memory maps files for speed. I know this is not the same, but I will now look into it, since I haven't done any J tracing unless a program blows up. I also use Dyalog APL,and I don't have a special keyboard. The symbols are MORE like mathematical symbols to me. It's just that it is easier to share code in J's plain ASCII text. Some systems still don't show APL characters correctly, or the user doesn't know how just yet. I was also trying to study K and Kona, so J was the better fit.
        11y ago

Honestly, I can see more than 4 lines of code there.

agumonkey 11y ago

nqueens is ~4, the rest is output

eggy 11y ago
One line of J code taken from the jsoftware site [1]: queenst =: (, #: I.@,@(</)&i.)~ (] #"1~ [ */@:~:&(|@-/) {)&.|: ! A.&i. ] This is the calculation, and you can output all 92 solutions for the 8 queens problems like this: queenst 8 0 4 7 5 2 6 1 3 0 5 7 2 6 3 1 4 0 6 3 5 7 1 4 2 .... each column is a row number, and the integer is which column the queen is in, or vice versa on rows and columns. ,or print how many solutions $queens 92 8 $ gives the 'shape' of the array, that is 92 rows (solutions) x 8 columns (8-queens problem). I always return to J, because I enjoy mathematics and functional programming. Like math, you work with symbols you learn to think as you code in an interpreted window, somewhat like when working in the Lisp REPL. Ken Iverson created the APL language in 1960, and won an ACM Turing Award and gave a lecture 'Notation as a Tool of Thought', which sums it up better than I could ever hope to express it [3]. J was a collaboration between him, Arthur Whitney (of finance's k language, and kdb fame), and Roger Hui, in an attempt to improve on APL, and to do away with needing a special character keyboard. It is under the GPL3 license today. J uses the ASCII character set, and is very functional and composable. [1] http://code.jsoftware.com/wiki/Essays/N_Queens_Problem [2] http://code.jsoftware.com/wiki/Essays/Queens_and_Knights [3] http://www.jsoftware.com/papers/tot.htm
- agumonkey 11y ago
  Always good to see some APL/J
- jxy 11y ago
  > queenst =: (, #: I.@,@(</)&i.)~ (] #"1~ [ */@:~:&(|@-/) {)&.|: ! A.&i. ] So this must be the origin of the one liner from [0] queens←{⍵{((+/b)⌿⍵),⍺|(,b)/⍳×/⍴b←~↑(⊂⍳⍺)∊¨(↓⍵)+[0]¨⊂(c-⍳c←1↓⍴⍵)∘.×¯1 0 1}⍣⍵⍳1 0} Somehow J is shorter? I need someone who speaks both J and APL to tell me if they are the same. Never learned J, but I always return to APL. I guess J to APL is like latin alphabet to chinese characters. You don't need a special keyboard for APL, just like you don't need a special keyboard for Chinese. Sometimes I really don't understand why they started J. Native English speaker's mentality? We never needed special keyboard for diacritics, let alone east asian languages. With an input method for APL characters, J does not even save the number of keystrokes. [0] https://dfns.dyalog.com/n_queens.htm https://dfns.dyalog.com/n_queens.htm
  - jxy 11y ago
    I was wrong. The two one-liners for J and APL are different. The original paper [0] gives the original APL implementation of the above J one-liner. I'm not going to delve deep into the algorithm, but the following quote from the paper fascinates me. It is voracious for work space. For concreteness, consider the case n←8 . The intermediate expression p[;c] has shape (!8),(2!8),2 , requiring 9031704 bytes on IBM-based APL systems. It uses 9 MB! Such a 'voracious' algorithm! [0] http://www.jsoftware.com/papers/nqueens.htm http://www.jsoftware.com/papers/nqueens.htm
    - RodgerTheGreat 11y ago
      Even by modern standards that's a pretty hefty chunk of RAM for n=8.
      - agumonkey 11y ago
        Still smaller that an 2016 app favicon.
      - jxy 11y ago
        The problem is that the complexity is O(n²n!)
        eggy 11y ago
        I am not a J guru, but that is just the concise implementation. There are others in the references previously cited. J is an interpreted language, and when doing db stuff, it memory maps files for speed. I know this is not the same, but I will now look into it, since I haven't done any J tracing unless a program blows up. I also use Dyalog APL,and I don't have a special keyboard. The symbols are MORE like mathematical symbols to me. It's just that it is easier to share code in J's plain ASCII text. Some systems still don't show APL characters correctly, or the user doesn't know how just yet. I was also trying to study K and Kona, so J was the better fit.
        11y ago