Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Arthur Whitney's one liner sudoku solver (2011)

dfns.dyalog.com

Post reply on HN
Print view View original

21–30 of 210 posts

Re: Arthur Whitney's one liner sudoku solver (2011)

#21

Post by cduzz »

I'll sometimes gauge code complexity by comparing the number of lines of code against the output of

  tar -cf - . | gzip | base64 | wc -l
IE "how much does it compress?"

Looking at APL -- I'm reminded of what happens if I accidentally send the gzipped output to my tty...

I'm impressed that there's anyone who can follow along (can you find the bug?) to code like

p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵

It really feels like compressed binary data where everyone's got a copy of the dictionary already...

Re: Arthur Whitney's one liner sudoku solver (2011)

#22

Post by sudosysgen »

Jorge1o1 wrote: post #15
shahbazac wrote: post #10

I’ve often wondered about languages like APL/k, are the programmers actually able to think about problems more efficiently?

As a kdb+/Q programmer I would say it depends on the type of problem. For example, when working with arrays of data it certainly is easier to think and write “avg a+b” to add two arrays together and then take the average. In a non-array programming language you would probably first need to do some bounds checking, then a big for loop, a temporary variable to hold the sum and the count as you loop over the two arrays,…

Well no, not in a non-array programming language. In any language that has a semi-decent type/object system and some kind of functional programming support, `avg a+b` would just be `avg(a, b)`, which is not any easier or harder, with an array type defined somewhere. Once you make your basic array operations (Which they have to be made in q anyways, just in the stdlib), you can compose them just like you would in q, and get the same results. All of the bounds checking and for-loops is unnecessary, all you really need are a few HKTs that do fancy maps and reduces, which the most popular languages already have.

A very real example of this is Julia. Julia is not really an array-oriented programming language, it's a general language with a strong type system and decent functional programming facilities, with some syntactic sugar that makes it look like it's a bit array oriented. You could write any Q/k program in Julia with the same complexity and it would not be any more complex. For a decently complex program Julia will be faster, and in every case it will be easier to modify and read and not any harder to write.

Re: Arthur Whitney's one liner sudoku solver (2011)

#23

Post by rak1507 »

cduzz wrote: post #21

I'll sometimes gauge code complexity by comparing the number of lines of code against the output of tar -cf - . | gzip | base64 | wc -l IE "how much does it compress?" Looking at APL -- I'm reminded of what happens if I accidentally send the gzipped output to my tty... I'm impressed that there's anyone who can follow along (can you find the bug?) to code like p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵ It re…

I'm not sure why it would be any more impressive or surprising than the billions of people who read and write in non English alphabets

Re: Arthur Whitney's one liner sudoku solver (2011)

#24

Post by xwolfi »

brookst wrote: post #20
pjot wrote: post #16

> Advocates of the language emphasize its speed, facility in handling arrays, and expressive syntax. Indeed. https://en.m.wikipedia.org/wiki/K_(programming_language)

“Expressive” = like two cats fought while standing on the keyboard

I work with it daily in a bank, and I couldnt find a better way to express it. Many colleagues throwing their keyboard in despair at this stupid impossible to remember syntax.

Re: Arthur Whitney's one liner sudoku solver (2011)

#25

Post by rak1507 »

sudosysgen wrote: post #22
Jorge1o1 wrote: post #15

Earlier quoted context omitted.

As a kdb+/Q programmer I would say it depends on the type of problem. For example, when working with arrays of data it certainly is easier to think and write “avg a+b” to add two arrays together and then take the average. In a non-array programming language you would probably first need to do some bounds checking, then a big for loop, a temporary variable to hold the sum and the count as you loop over the two arrays,…

Well no, not in a non-array programming language. In any language that has a semi-decent type/object system and some kind of functional programming support, `avg a+b` would just be `avg(a, b)`, which is not any easier or harder, with an array type defined somewhere. Once you make your basic array operations (Which they have to be made in q anyways, just in the stdlib), you can compose them just like you would in q, a…

I don't know what you mean by the q array operations being defined in the standard library. Yes there are things defined in .q, but they're normally thin wrappers over k which has array operations built in.

Re: Arthur Whitney's one liner sudoku solver (2011)

#26

Post by rak1507 »

xwolfi wrote: post #24
brookst wrote: post #20

Earlier quoted context omitted.

“Expressive” = like two cats fought while standing on the keyboard

I work with it daily in a bank, and I couldnt find a better way to express it. Many colleagues throwing their keyboard in despair at this stupid impossible to remember syntax.

There are a lot of things in various programming languages which are hard to remember, but k and array languages have such a small surface area, not being able to remember it while working with it daily amounts to learned helplessness.

(source: mostly amateur k programmer, also worked with it in a bank, find it vastly easier to read/write/remember than most mainstream languages)

Re: Arthur Whitney's one liner sudoku solver (2011)

#27

Post by jksmith »

swatcoder wrote: post #17
gerdesj wrote: post #9

Earlier quoted context omitted.

Meta: No need to DV a comment you don't like for no reason. Engage instead. Why not have a chat?

Downvotes and upvotes work together to manage the visibility of posts that align with the community's tastes. While I myself found an opportunity to reply to the GP and didn't down vote them, their comment only engaged with the article in a shallow way and only then, seemingly, to just dismiss the concept of solver altogether. It wasn't a offensive comment, but it didn't really contribute to the site in the way many…

Aside: Downvotes on HN can be an expression of age related, self-righteous sniper pique; Opinions on what contributes to a conversation can be all over the place and are entirely subject to biases, which can be interesting (I guess). Doesn't really matter, and Hail Satan anyway. Also "Q for Mortals" is an interesting book.

Re: Arthur Whitney's one liner sudoku solver (2011)

#28

Post by BobbyTables2 »

o11c wrote: post #13
Isamu wrote: post #8

Not knowing K, am I correct in assuming this is a backtracking brute force solver?

From the linked page (and the one linked beyond that), it's a breadth-first search actually. Keep a list of possible puzzle states at all times, pick a blank cell (theoretically arbitrary, but in practice intelligently for performance), add copies of the state with each possibility for that state added.

That sounds like 100+ lines in python or similar languages…

Re: Arthur Whitney's one liner sudoku solver (2011)

#29

Post by cduzz »

rak1507 wrote: post #23
cduzz wrote: post #21

I'll sometimes gauge code complexity by comparing the number of lines of code against the output of tar -cf - . | gzip | base64 | wc -l IE "how much does it compress?" Looking at APL -- I'm reminded of what happens if I accidentally send the gzipped output to my tty... I'm impressed that there's anyone who can follow along (can you find the bug?) to code like p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵ It re…

I'm not sure why it would be any more impressive or surprising than the billions of people who read and write in non English alphabets

That's a really good point...

But -- (and forgive me if I'm totally wrong) -- this isn't just "non-english" but "non-phonetic" which is a smaller set of written languages, and the underlying language is ... math.... so understanding the underlying grammer itself relies on having decades of math education to really make it jive.

If this code is just a final result of "learn math for 2-3 decades, and spend years learning this specific programming language" -- my statement stands. Interacting with this kinda binary blob as a programming language is impressive. I think I read somewhere that seymour cray's wife knew he was working too hard when he started balancing the checkbook in hex...

Re: Arthur Whitney's one liner sudoku solver (2011)

#30

Post by rak1507 »

cduzz wrote: post #29
rak1507 wrote: post #23

Earlier quoted context omitted.

I'm not sure why it would be any more impressive or surprising than the billions of people who read and write in non English alphabets

That's a really good point... But -- (and forgive me if I'm totally wrong) -- this isn't just "non-english" but "non-phonetic" which is a smaller set of written languages, and the underlying language is ... math.... so understanding the underlying grammer itself relies on having decades of math education to really make it jive. If this code is just a final result of "learn math for 2-3 decades, and spend years learni…

The underlying language isn't really very mathematical, at most there's a bit of linear algebra in the primitives but that's it. You certainly don't need any sort of formal maths education to learn APL. There are about 50 or so new symbols, which is not a big ask, with any sort of focus the majority of the syntax etc can be learned very quickly. The "bugs" in your original code stand out very clearly because things like "∘}" don't make sense, ∘ being "dyadic" (infix).
Post reply on HN