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

171–180 of 210 posts

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

#171

Post by lokedhs »

upghost wrote: post #163
dzaima wrote: post #133

Earlier quoted context omitted.

Once you've learned the syntax of the language, long expressions like that are about as readable as however-many-dozen lines of JS/Python with 1-to-3-character variable names; i.e. some parts may be obvious if they're a common pattern or simple enough, but the big picture may take a while to dig out. Probably the biggest readability concern of overly-golfed expressions really is just being dynamically typed, a proble…

I am kind of curious if you have to mentally keep track of the rank/shape/dimensions in your head or if there is some implicit/explicit convention for conveying that to the reader. Does tracking rank/shape become second nature after awhile? I'm also wondering about things like (APL-style) inner products -- they are undeniably powerful, but it's hard for me to conceptual use cases above rank 3.

That depends on the specific code. Some code is written to be agnostic to the rank, while others make certain assumptions.

In my code I'd sometimes write assertions in the beginning of a function to not only ensure it's called with the right shape but also as documentation.

Also, in practice really high rank arrays aren't used much. Even 4 is pretty rare.

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

#173

Post by dzaima »

upghost wrote: post #163
dzaima wrote: post #133

Earlier quoted context omitted.

Once you've learned the syntax of the language, long expressions like that are about as readable as however-many-dozen lines of JS/Python with 1-to-3-character variable names; i.e. some parts may be obvious if they're a common pattern or simple enough, but the big picture may take a while to dig out. Probably the biggest readability concern of overly-golfed expressions really is just being dynamically typed, a proble…

I am kind of curious if you have to mentally keep track of the rank/shape/dimensions in your head or if there is some implicit/explicit convention for conveying that to the reader. Does tracking rank/shape become second nature after awhile? I'm also wondering about things like (APL-style) inner products -- they are undeniably powerful, but it's hard for me to conceptual use cases above rank 3.

If there's information on input format, it is simple enough to trace through the following shapes, but it does force reading the code rather linearly. Operations which implicitly restrict the allowed shapes are unfortunately intentionally rather few.

I basically never use the generalized inner product; it's rather unique to the original APL - J has a variant that doesn't have the built-in reduction, and k and BQN and many if not most other array languages don't have any builtin for it at all. And in general I don't typically use rank higher than like one plus the natural dimensionality of the operation/data in question.

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

#174

Post by geekraver »

Much better than some of the garbage solutions I have seen, including from sources that should know better, like The Algorithm Design Handbook. Some really absurd approaches out there, so bad I wrote a blog post about it in 2015: https://www.grahamwheeler.com/post/sudoku/

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

#175

Post by upghost »

smabie wrote: post #169
upghost wrote: post #160

Earlier quoted context omitted.

Just looked at the github -- wait, you wrote BQN? My God. Is there any prior art on this -- arraylangs with first class functions? I don't think very many people realize how incredible the semantic power of BQN is. The idea of an arraylang with first class functions... it truly staggers the imagination. I feel like if I were able to wrap my head around it I would never want to code in anything else. Thanks again and…

Don't most array languages have first class functions?

They have functions but not first class functions. Think (the ability to make) a vector/matrix of functions rather than just numbers :O

What could you do with that?

I don't know, but I bet some pretty cool stuff.

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

#176

Post by dzaima »

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.

The k code at least isn't doing any heuristics for the iteration order, and is just doing a fold over the indices of zeroes in index-ascending order.

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

#177

Post by notfed »

mlochbaum wrote: post #136
bryancoxwell wrote: post #31

Earlier quoted context omitted.

Legitimately curious how APL programmers think about maintainability and readability. Is code just thoroughly commented or otherwise documented?

The most uncompromisingly APL-ish code I've written is the BQN compiler[0]. Hard to write, hard to extend, hard to refactor. I generally recommend against writing this way in [1]. But... it's noticeably easy to debug. There's no control flow, I mean, with very few exceptions every line is just run once, in order. So when the output is wrong I skim the comments and/or work backwards through the code to find which vari…

What is this witchcraft? I fear that I have seen something that I cannot unsee...

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

#178

Post by RHSeeger »

boomlinde wrote: post #107
nosianu wrote: post #86

Earlier quoted context omitted.

This view is too static. That is not possible, because the environment can (and at some point always will) change which wasn't planned for due to a lack of working crystal balls. Data, user behavior, the network, the system(s) the software runs on can all change over time. Also, it is way too expensive to try to cover every single conceivable possibility, so we deliberately leave holes. For non-trivial things we ofte…

> That is not possible, because the environment can (and at some point always will) change which wasn't planned for due to a lack of working crystal balls. Data, user behavior, the network, the system(s) the software runs on can all change over time. It sounds to me like you are describing a change of problem, not bugs in the solution. If in the future someone redefines the concept of a Sudoku puzzle such that this s…

In my experience, the vast majority of problems are insufficiently specified. No matter how well you solve the current problem, there are bound to be certain assumptions you've made about the requirements. And when those assumptions don't hold true, your solution may no longer work.

> What do you mean the input file can't be ISO-2WTF encoded?

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

#179

Post by realo »

upghost wrote: post #163
dzaima wrote: post #133

Earlier quoted context omitted.

Once you've learned the syntax of the language, long expressions like that are about as readable as however-many-dozen lines of JS/Python with 1-to-3-character variable names; i.e. some parts may be obvious if they're a common pattern or simple enough, but the big picture may take a while to dig out. Probably the biggest readability concern of overly-golfed expressions really is just being dynamically typed, a proble…

I am kind of curious if you have to mentally keep track of the rank/shape/dimensions in your head or if there is some implicit/explicit convention for conveying that to the reader. Does tracking rank/shape become second nature after awhile? I'm also wondering about things like (APL-style) inner products -- they are undeniably powerful, but it's hard for me to conceptual use cases above rank 3.

I programmed in APL a long time ago... even got 'not bad' at it.

The best analogy i can give of my thought process is that first i unfolded the problem into one or more many-dimension object(s) ... then took a different "stance" of looking at the object, then refolded them into the final solution.

So yes... I had it all in my head at some point.

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

#180

Post by forgotpwd16 »

Intralexical wrote: post #140

It may be interesting to compare this one line to "Code Golfed" equivalents in different programming languages: https://codegolf.stackexchange.com/questions/tagged/sudoku?t...

Funnily top[1] solution for specific problem (brute-force Sudoku solver) is the K snippet. Second comes a J solution that replicates K's.

[1]: https://codegolf.stackexchange.com/a/5030

Post reply on HN