8 ms·

Arthur Whitney's one liner sudoku solver (2011)

282 points by secwang 2y ago

nebulous1 2y ago
Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x
- deleted 2y ago
  [deleted]
wileydragonfly 2y ago
Sudoku was always a meditative thing for me. It’s impossible not to win so long as you pay attention. Optimizing solutions seems contrary to the point to me.
- malux85 2y ago
  Optimising solutions is the meditative exercise for me. I enjoy running simulation after simulation after simulation, studying possible outcomes and optimising everything. Everyone is different :)
- UncleOxidant 2y ago
  I guess I'm the opposite. After doing a couple of sudoku many years ago my thought was "Hey, I could just automate this" and started thinking of algorithms.
- swatcoder 2y ago
  Solvers are useful for confirming that a puzzle you've recieved or generated is solvable. The meditative process can really go sideways when there is no solution for you to stumble upon. Puzzles in commercial collections don't usually have that problem, but those from other sources sometimes do. Solvers also make for a nice craft exercise, as here. Simple but not trivial, you can approach them in a lot of different ways and thereby work through different techniques or constraints you mean to explore.
  - sellyme 2y ago
    > Puzzles in commercial collections don't usually have that problem, I would argue that puzzles in commercial collections are more likely to have that problem than ones made freely available by hobbyists, as commercial enterprises inevitably cut corners on things like labour costs for an actual human setter. I have seen dozens of commercial puzzle games and applications that do not make any attempt to verify the (auto-generated) puzzles as solvable, but I don't think I've ever had the same problem on a site like LMD.
- gerdesj 2y ago
  Meta: No need to DV a comment you don't like for no reason. Engage instead. Why not have a chat?
  - riiii 2y ago
    People are saturated with anger and frustration after doom scrolling. They engage with their pitchforks.
    - mcphage 2y ago
      A few anonymous downvotes are what qualifies as pitchforks these days?
  - swatcoder 2y ago
    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 people digging into deep technical walkthroughs like this expect to see. Some downvotes weren't guaranteed, but they're not surprising and they're probably helping new readers stay engaged with more topical and technical alternatives. It's not the end of the world to get a few downvotes, and it's almost never personal. It certainly isn't here.
    - jksmith 2y ago
      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.
  - ben0x539 2y ago
    Wouldn't it be more productive/rewarding to instead engage with comments I do like?
- K0balt 2y ago
  I find that sodoku is not a math or even a logic puzzle, but rather an epistemology puzzle. Lots of how we know/how much we know, and if you get into speed with some failure tolerance through estimating probability it adds even more thought provoking rabbit holes.
- kranner 2y ago
  Optimising a Sudoku solver can be seen as a different puzzle entirely and not as a mode of playing Sudoku.
- teo_zero 2y ago
  Interesting position that was not expressed before. However please note that the same could be said about writing a solver.
29athrowaway 2y ago
There is a video about this. https://www.youtube.com/watch?v=DmT80OseAGs https://www.youtube.com/watch?v=DmT80OseAGs You can try the solution at https://tryapl.org/ https://tryapl.org/
Isamu 2y ago
Not knowing K, am I correct in assuming this is a backtracking brute force solver?
- o11c 2y ago
  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.
  - BobbyTables2 2y ago
    That sounds like 100+ lines in python or similar languages…
    - otteromkram 2y ago
      It probably isn't. At least, not for Python.
    - throwup238 2y ago
      You should be able to do it in under 20 lines using the same matrix operations as the K code via numpy.
      - anonzzzies 2y ago
        Numpy is indeed very apl. Just more horrible to me; not python-y and annoyingly verbose for the apl-er.
    - hrzn 2y ago
      A few years back I made a modest attempt at writing a concise yet readable sudoku solver in Python - in about 29 lines: https://github.com/hrzn/sudoku/blob/master/sudoku.py https://github.com/hrzn/sudoku/blob/master/sudoku.py Could have been made shorter at the price of readability.
shahbazac 2y ago
I’ve often wondered about languages like APL/k, are the programmers actually able to think about problems more efficiently?
- giraffe_lady 2y ago
  Hillel Wayne writes about it on his newsletter every once in a while. He's convinced me that he does in fact think through some problems better in array languages but I still can't really conceive of what that experience is like.
  - RodgerTheGreat 2y ago
    there are several open-source K environments available, some which even run in the browser: http://johnearnest.github.io/ok/index.html http://johnearnest.github.io/ok/index.html if it's something you're interested in trying i'd be happy to point you toward more resources, and i'm sure there are plenty of other arraylang tinkerers reading this thread who could help, too
- Jorge1o1 2y ago
  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, etc. Probably the difference between like 6ish lines of code in some language like C versus the 6 characters above in Q. But every language has features that help you reason about certain types of problems better. Functional languages with algebraic data types and pattern matching (think OCaml or F#) are nicer than switch statements or big if-else-if statements. Languages with built-in syntactic sugar like async/await are better at dealing with concurrency, etc.
  - lll-o-lll 2y ago
    Which is why C# is the giant ever increasing bag of tricks that it is (unkind people might say bloat…) ;-) Personally, I’m all for this; let me express the problem in whatever way is most natural. There are limits, of course, and it’s not without downsides. Still, if I have to code in something all day, I’d like that “something” be as expressive as possible.
pjot 2y ago
> Advocates of the language emphasize its speed, facility in handling arrays, and expressive syntax. Indeed. https://en.m.wikipedia.org/wiki/K_(programming_language) https://en.m.wikipedia.org/wiki/K_(programming_language)
- brookst 2y ago
  “Expressive” = like two cats fought while standing on the keyboard
  - xwolfi 2y ago
    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.
    - rak1507 2y ago
      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)
    - aguaviva 2y ago
      [flagged]
      - inopinatus 2y ago
        "Debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it?" — Kernighan, Brian. The Elements of Programming Style (2e). McGraw-Hill, 1978.
        userbinator 2y ago
cduzz 2y ago
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...
- rak1507 2y ago
  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
  - cduzz 2y ago
    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...
    - rak1507 2y ago
      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).
make3 2y ago
"one line in your custom language" is not one line at all lol
- Spivak 2y ago
  To be fair K is a real language that's used by more than just him. Why array languages seem to gravitate to symbol soup that makes regex blush I'll never know.
  - fodkodrasz 2y ago
    [flagged]
    - exitheone 2y ago
      Array language have been around far longer than any "HN crowd".
      - fodkodrasz 2y ago
        Which is totally orthogonal to the original statement, and my reflection to it, which was on one hand statig that seemingly array languages tend to be letter soupy, for which I replied that a selection bias is at play, as array languges are used widely, most notably Matlab is used widely which is not a letter soup. It is simply not regurgulated on the site as it does not seem so hardcore. Nevertheless you are right, array langueges have been around earlier, for example Matlab itself dates back to the 1970s. I do not understand the awe some are giving them in the comments, they are an easy to understand paradigm, which is very well suited for certain types of problems. Some having overly terse syntax is a thing, but I do not feel that only geniuses can comprehend array programming, anyone who did learn some university level physics or signal processing has the tools in their belt.
  - IshKebab 2y ago
    Yeah I think MATLAB and Mathematica are waaay more used than K et al. They just don't look insane so people aren't posting them on HN as much.
asah 2y ago
What baud is that? /s
- genewitch 2y ago
  mismatched, whatever it is, that's for sure. It's not quite line noise, so maybe it's just the wrong stop bit?
- speed_spread 2y ago
  My cat puked in the modem receiver cup, sorry.
deleted 2y ago
[deleted]
dang 2y ago
I put 2011 in the title above because https://web.archive.org/web/20110813135700/https://dfns.dyalog.com/n_sudoku.htm https://web.archive.org/web/20110813135700/https://dfns.dyal... appears to have the main thing - is there a better year?
lofaszvanitt 2y ago
It has strong perl vibes and it brings back ptsd :D. Maybe this overshortification of things is a personnel or intelligence indicator of some sorts.
gorgoiler 2y ago
Every K program ought to end in QED, and then I remember that KQED is also a thing, and I wonder if their two worlds have ever overlapped. (KQED is the Bay Area PBS partner. PBS is the US public television org.)
lucw 2y ago
Does anyone have any thoughts on what motivates people to play sudoku or write solvers for sudoku ? I have trouble finding motivation to solve artificial problems. That said I sink hundreds of hours into factorio.
- riffraff 2y ago
  I don't particularly enjoy sudoku but I like word puzzle games. They're all artificial problems, but your brain likes a challenge and you get a dopamine hit when you solve it, I suppose.
- bramhaag 2y ago
  For me personally, I have little motivation to do classical sudokus. They either have a not-so-elegant solve path (usually set by a computer) or are too difficult for me to solve. Variant sudokus on the other hand are a lot of fun. They often have very elegant solve paths and there are many neat tricks you can discover and reason about. Some fun ones, if you'd like to try: - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000DMZ https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id... - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000CN6 https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id... - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000JKX https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id...
  - akleemans 2y ago
    I also mostly enjoy Sudoku variants, most of which I discovered via Geocaches, interestingly. After solving a few I then implemented a solver with customizable constraints, if anyone's interested, should still be available here: https://www.sudoku-solver.ch/ https://www.sudoku-solver.ch/
  - sltkr 2y ago
    To each their own, but the puzzles you linked seem really convoluted compared to regular Sudoku. The last puzzle has no fewer than 9 custom rules, in addition to the regular Sudoku rules, and then it also says “every clue is wrogn [sic]” implying there is some meta out-of-the-box thinking required to even understand what the rules are. That is more a riddle than a logic puzzle. By contrast, the charm of classical Sudoku is that the rules are extremely simple and straightforward (fill the grid using digits 1 through 9, so that each digit occurs exactly once in each row, column, and 3x3 box) and any difficulty solving comes from the configuration of the grid.
upghost 2y ago
Most people are put off by the symbols, that wasn't really the issue I had. So I do love APL and arraylangs, and learning them was really helpful in a lot of other languages. But they never became a daily driver for me not because of the symbols, which were honestly fine if you stick with it long enough, but after about 3-4 years of dabbling on and off I hit a wall with APL I just couldn't get past. Most other languages I know there is a "generic-ish" approach to solving most problems, even if you have to cludge your way through suboptimally until you find "the trick" for that particular problem and then you can write something really elegant and efficient. APL it felt like there was no cludge option -- you either knew the trick or you didn't. There was no "graceful degredation" strategy I could identify. Now, is this actually the case? I can't tell if this is a case of "yeah, thats how it is, but if you learn enough tricks you develop an emergent problem solving intuition", or if its like, "no its tricks all the way down", or if its more like, "wait you didn't read the thing on THE strategy??". Orrr maybe I just don't have the neurons for it, not sure. Not ruling it out.
- lokedhs 2y ago
  You're not wrong. It's very easy to get that impression when trying to learn the array languages. It's very easy for someone who's used these languages for a long time to look at a problem, and say "why did you use that really elaborate solution, when you can just use ⍸⍣¯1?". No one probably ever told you that ⍸ has an inverse, and how you could use it. Even today, after having worked in these languages for years, I am still put off a bit by the walls of code that some array programmers produce. I fully understand the reasoning why it's written like that, but I just prefer a few spaces in my code. I've been working on an array language based on APL, and one of my original goals was to make "imperative style" programming more of a first-class citizen and not punish the beginner from using things like if-statements. It remains to be seen how well I succeeded, but even I tend to use a more expressive style when terseness doesn't matter. Here's an example of code I've written which is the part of the implementation that is responsible for taking any value (such as nested arrays) and format them nicely as text using box drawing characters. I want to say that this style is a middle ground between the hardcore pure APL style found in some projects and the style you'll see in most imperative languages: https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap https://codeberg.org/loke/array/src/branch/master/array/stan...
yumraj 2y ago
[flagged]
- yumraj 2y ago
  Gemini also identifies it as J and this is the output for comparison: The programming language used in the code is *J* (pronounced "Jay"). It's a concise, array-oriented programming language known for its expressive syntax and powerful capabilities. Here's a breakdown of the code: *1. Verb Definition:* * `x(,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}')/&~x` defines a verb (a function in J terminology) and assigns it to the variable `x`. *2. Verb Structure:* * `x( ... )/&~x` is the basic structure of the verb. `x( ... )` applies the verb defined within the parentheses to its argument, which will be `x` itself. * `/&~x` is a hook, a control flow construct in J. It applies the verb defined within the parentheses to each element of `x` and then applies the verb `&~x` to the resulting array. *3. Verb Body:* * `,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}` is the body of the verb. Let's break it down further: * `{@[x;y;]` creates a gerund (a verb-like noun) that takes two arguments, `x` and `y`. * `'(!10)^x` generates an array of `x` elements, each raised to the power of `!10` (factorial of 10). `/p[;y]=p` is a conjunction that appends the value of `p` to itself for each element in `y`. * `,:,3/:-3!p:!9 9}` generates an array of 3 elements, each of which is the factorial of `-3` (which is undefined and results in an error) followed by the number 9. *4. Overall Functionality:* * The verb takes an array `x` as input. * It applies the gerund to each element of `x`, creating an array of arrays. * It then applies the conjunction to each of these arrays, appending the value of `p` (which is likely defined elsewhere in the code) to itself. * Finally, it generates an array of 3 elements with errors and 9s. * The hook `/&~x` applies the verb to each element of `x` and then applies a function that is likely defined elsewhere in the code (since `&~x` is not defined within this verb). *Note:* Without more context about the definitions of `p` and other variables or functions used in the code, it's difficult to provide a more precise explanation of the verb's exact behavior. However, the breakdown above should give you a general understanding of the code's structure and logic.
  - rak1507 2y ago
    Please kindly delete your account, destroy your devices, and move to the woods far away from technology.
fhdufxm 2y ago
[flagged]
nine_k 2y ago
Lines of code is a poor metric, because languages use lines differently. A much better measure would be the number of nodes in a parse tree, of semantically meaningful non-terminals like "a constant" or "a function call". An even better measure would also involve the depth and the branching factor of that tree.
- tromp 2y ago
  The preferred measure of information content is simply number of bits as used for instance in Algorithmic Information Theory [1]. [1] https://en.wikipedia.org/wiki/Algorithmic_information_theory https://en.wikipedia.org/wiki/Algorithmic_information_theory
  - jodrellblank 2y ago
    By that measure naming a variable “objUser” instead of “user” is better because it has more information, and naming the same variable “cgjkkytdvjkftujmhffetb” is even better because it contains more information. The parse tree approach is trying to get at a fuzzy notion of useful information and useful density of information.
- smokel 2y ago
  The built-in functions and API to a system library spoil these metrics. As an example, consider HQ9+, which is pretty good at printing "Hello, world!" for instance. https://cliffle.com/esoterica/hq9plus/ https://cliffle.com/esoterica/hq9plus/
- xelxebar 2y ago
  Just... no. What are you even trying to compare? UX of a language matters. Clarity, thinking paradigm, expressability etc. all matter and are affected by the visual size of code. A one line solution takes up very little visual real estate. That matters a lot when you are working on some more complex problem. Flitting your eyeballs around a screen takes orders of magnitude less effort than scrolling around and navigating files. Cognitive load is important. We really need to burn this vague "only semantics matter" scourge that's creeped into our programmer values these days. I'm sorry, but I care about things like incentives against over-engineering, ease of directly thinking in the problem domain, and simplicity of the encompassing ecosystem. A terse one-line solution tells me there is virtually no room for over-engineering. Even without knowing K, I can see obvious constants side-by-side, telling me it's likely using a direct data representation of the problem in its code. Does K culture encourage code like that? Does programming in K bias you towards directness and simplicity? Then please, I want some of that special sauce on my team. </rant>
sorokod 2y ago
The LoC count and similar metrics have the advantage of an easy calculation. Ultimately though,they are a proxy to a more relevant but difficult to determine attributes such as Given a reasonably proficient engineer, the amount of time it would take them to resolve a bug in code written by someone else or alternatively extend its functionality in some way.
bazoom42 2y ago
The discussions around “line noise”-languages are always intersting. Most programmers would agree the ‘/’ symbol is at least as clear as writing ‘divideBy’. The question is how often the symbols are used and if their frequency in code justifies learning them.
brador 2y ago
Someone should collate exceptional human coding achievements to test future AI. AFAICT AI cannot replicate this, yet, will be interesting when that day comes.
TZubiri 2y ago
I thought it was written by Ursula K. Le guin. Not sure where I got that from.
Intralexical 2y ago
It may be interesting to compare this one line to "Code Golfed" equivalents in different programming languages: https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes https://codegolf.stackexchange.com/questions/tagged/sudoku?t...
- forgotpwd16 2y ago
  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 https://codegolf.stackexchange.com/a/5030
eigenvalue 2y ago
It's cool in a novelty way that it’s so short, but I would infinitely prefer something like this for actual work and understanding: def solve(grid): def find_empty(grid): for r in range(9): for c in range(9): if grid[r][c] == 0: return r, c return None def is_valid(grid, num, pos): r, c = pos if num in grid[r]: return False if num in [grid[i][c] for i in range(9)]: return False box_r, box_c = r // 3 * 3, c // 3 * 3 for i in range(box_r, box_r + 3): for j in range(box_c, box_c + 3): if grid[i][j] == num: return False return True def backtrack(grid): empty = find_empty(grid) if not empty: return True r, c = empty for num in range(1, 10): if is_valid(grid, num, (r, c)): grid[r][c] = num if backtrack(grid): return True grid[r][c] = 0 return False backtrack(grid) return grid
- upghost 2y ago
  Why is this getting down-voted without comment? Comparative analysis is taboo, now? I don't think Arthur Whitney would feel the least bit threatened by some Python code.
  - eigenvalue 2y ago
    The K-mafia is in control. Just kidding, I don’t really care either way…
  - BoiledCabbage 2y ago
    Speculation, but maybe because there is nothing of interest or to note in the comment. It's not clear why the poster prefers that other implementation, or that they understand APL or array programming. So as a result the comment reads as "it's in a language I don't know. I'd prefer it in a language I do know." Which is a fairly useless comment. If that's not what they intended, it would be helpful for them to add some context to their comment.
upghost 2y ago
Well if we are showing off sudoku solvers, it would be a sin not to share this one: sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), append(Rows, Vs), Vs ins 1..9, maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is). blocks([], [], []). blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]), blocks(Ns1, Ns2, Ns3). While not one line, to me it is pareto optimal for readable, elegant, and incredibly powerful thanks to the first class constraint solvers that ship with Scryer Prolog. If you want to learn more about it or see more of Markus's work: https://www.metalevel.at/sudoku/ https://www.metalevel.at/sudoku/ https://youtu.be/5KUdEZTu06o https://youtu.be/5KUdEZTu06o More about Scryer Prolog (a modern , performant, ISO-compliant prolog written mostly in rust) https://www.scryer.pl/ https://www.scryer.pl/ https://github.com/mthom/scryer-prolog https://github.com/mthom/scryer-prolog
iamyourcanary 2y ago
[dead]
Duanemclemore 2y ago
For me one of the most important things here is the clarity of the problem -maker- at the top. That's the difference between the "Iversonian" symbolic languages (J and K included) and others. It doesn't have the elegance and power of a one line solution, but it's just so clean and comprehensible even without the disciplined commenting. (Although I really think lamp is not a good comment glyph. Sorry about the sacred cow I just took a swipe at fellow array nerds.) One line solutions are incredible, and tacit is mind-bendingly cool. To use the unique compactness of a glyph-based language as a way to efficiently describe and perform functional programming - then to do that all over arrays!? - whoever had these ideas [0] is utterly genius. But as someone trying to make time to write a program ground up in APL, knowing that I won't be able to make it just a set of really good one liners, that example is also significant for me. [0] https://www.jsoftware.com/papers/fork.htm https://www.jsoftware.com/papers/fork.htm
- lokedhs 2y ago
  Just because you can write everything on one line without any spaces doesn't mean you should. You can ofcourse removethe capability to do thatand you'll effectively force the programmer to write more venous code, but then its strength as an interfacing tool is very much reduced. The Iversonian languages has the capability to write incredibly terse code which is really useful when working interactively. When you do, your code truly is write-only because it isn't even saved. This is the majority of code that at least I write in these languages. When writing code that goes in a file, you can choose which style you want to use, and I certainly recommend making it a bit less terse in those cases. The Iversonian languages are still going to give you organs that are much shorter than most other languages even even it's written in a verbose style.
deleted 2y ago
[deleted]
geekraver 2y ago
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/ https://www.grahamwheeler.com/post/sudoku/
cachvico 2y ago
The k code explained: https://chatgpt.com/share/67036e8e-17dc-800f-96c4-1fac8b291f43 https://chatgpt.com/share/67036e8e-17dc-800f-96c4-1fac8b291f...
- rak1507 2y ago
  This is (predictably) wrong.
  - cachvico 2y ago
    hah
bishop77 2y ago
For sudokus of size 9x9 and 16x16 almost any unoptimised DFS will work just fine (even for hard sudokus [0]). The real challenge is for sudokus of size 25x25 and above. [0] https://cdn.aaai.org/ocs/2517/2517-11201-1-PB.pdf https://cdn.aaai.org/ocs/2517/2517-11201-1-PB.pdf
nephronaut 2y ago
So how to feed in the instance if code is only Nebulous1: Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}')/&~x

282 points by secwang 2y ago

Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

deleted 2y ago
[deleted]

wileydragonfly 2y ago

Sudoku was always a meditative thing for me. It’s impossible not to win so long as you pay attention. Optimizing solutions seems contrary to the point to me.

malux85 2y ago
Optimising solutions is the meditative exercise for me. I enjoy running simulation after simulation after simulation, studying possible outcomes and optimising everything. Everyone is different :)
UncleOxidant 2y ago
I guess I'm the opposite. After doing a couple of sudoku many years ago my thought was "Hey, I could just automate this" and started thinking of algorithms.
swatcoder 2y ago
Solvers are useful for confirming that a puzzle you've recieved or generated is solvable. The meditative process can really go sideways when there is no solution for you to stumble upon. Puzzles in commercial collections don't usually have that problem, but those from other sources sometimes do. Solvers also make for a nice craft exercise, as here. Simple but not trivial, you can approach them in a lot of different ways and thereby work through different techniques or constraints you mean to explore.
- sellyme 2y ago
  > Puzzles in commercial collections don't usually have that problem, I would argue that puzzles in commercial collections are more likely to have that problem than ones made freely available by hobbyists, as commercial enterprises inevitably cut corners on things like labour costs for an actual human setter. I have seen dozens of commercial puzzle games and applications that do not make any attempt to verify the (auto-generated) puzzles as solvable, but I don't think I've ever had the same problem on a site like LMD.
gerdesj 2y ago
Meta: No need to DV a comment you don't like for no reason. Engage instead. Why not have a chat?
- riiii 2y ago
  People are saturated with anger and frustration after doom scrolling. They engage with their pitchforks.
  - mcphage 2y ago
    A few anonymous downvotes are what qualifies as pitchforks these days?
- swatcoder 2y ago
  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 people digging into deep technical walkthroughs like this expect to see. Some downvotes weren't guaranteed, but they're not surprising and they're probably helping new readers stay engaged with more topical and technical alternatives. It's not the end of the world to get a few downvotes, and it's almost never personal. It certainly isn't here.
  - jksmith 2y ago
    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.
- ben0x539 2y ago
  Wouldn't it be more productive/rewarding to instead engage with comments I do like?
K0balt 2y ago
I find that sodoku is not a math or even a logic puzzle, but rather an epistemology puzzle. Lots of how we know/how much we know, and if you get into speed with some failure tolerance through estimating probability it adds even more thought provoking rabbit holes.
kranner 2y ago
Optimising a Sudoku solver can be seen as a different puzzle entirely and not as a mode of playing Sudoku.
teo_zero 2y ago
Interesting position that was not expressed before. However please note that the same could be said about writing a solver.

29athrowaway 2y ago

There is a video about this. https://www.youtube.com/watch?v=DmT80OseAGs https://www.youtube.com/watch?v=DmT80OseAGs You can try the solution at https://tryapl.org/ https://tryapl.org/

Isamu 2y ago

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

o11c 2y ago
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.
- BobbyTables2 2y ago
  That sounds like 100+ lines in python or similar languages…
  - otteromkram 2y ago
    It probably isn't. At least, not for Python.
  - throwup238 2y ago
    You should be able to do it in under 20 lines using the same matrix operations as the K code via numpy.
    - anonzzzies 2y ago
      Numpy is indeed very apl. Just more horrible to me; not python-y and annoyingly verbose for the apl-er.
  - hrzn 2y ago
    A few years back I made a modest attempt at writing a concise yet readable sudoku solver in Python - in about 29 lines: https://github.com/hrzn/sudoku/blob/master/sudoku.py https://github.com/hrzn/sudoku/blob/master/sudoku.py Could have been made shorter at the price of readability.

shahbazac 2y ago

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

giraffe_lady 2y ago
Hillel Wayne writes about it on his newsletter every once in a while. He's convinced me that he does in fact think through some problems better in array languages but I still can't really conceive of what that experience is like.
- RodgerTheGreat 2y ago
  there are several open-source K environments available, some which even run in the browser: http://johnearnest.github.io/ok/index.html http://johnearnest.github.io/ok/index.html if it's something you're interested in trying i'd be happy to point you toward more resources, and i'm sure there are plenty of other arraylang tinkerers reading this thread who could help, too
Jorge1o1 2y ago
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, etc. Probably the difference between like 6ish lines of code in some language like C versus the 6 characters above in Q. But every language has features that help you reason about certain types of problems better. Functional languages with algebraic data types and pattern matching (think OCaml or F#) are nicer than switch statements or big if-else-if statements. Languages with built-in syntactic sugar like async/await are better at dealing with concurrency, etc.
- lll-o-lll 2y ago
  Which is why C# is the giant ever increasing bag of tricks that it is (unkind people might say bloat…) ;-) Personally, I’m all for this; let me express the problem in whatever way is most natural. There are limits, of course, and it’s not without downsides. Still, if I have to code in something all day, I’d like that “something” be as expressive as possible.

pjot 2y ago

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

brookst 2y ago
“Expressive” = like two cats fought while standing on the keyboard
- xwolfi 2y ago
  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.
  - rak1507 2y ago
    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)
  - aguaviva 2y ago
    [flagged]
    - inopinatus 2y ago
      "Debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it?" — Kernighan, Brian. The Elements of Programming Style (2e). McGraw-Hill, 1978.
      - userbinator 2y ago

cduzz 2y ago

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...

rak1507 2y ago
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
- cduzz 2y ago
  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...
  - rak1507 2y ago
    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).

make3 2y ago

"one line in your custom language" is not one line at all lol

Spivak 2y ago
To be fair K is a real language that's used by more than just him. Why array languages seem to gravitate to symbol soup that makes regex blush I'll never know.
- fodkodrasz 2y ago
  [flagged]
  - exitheone 2y ago
    Array language have been around far longer than any "HN crowd".
    - fodkodrasz 2y ago
      Which is totally orthogonal to the original statement, and my reflection to it, which was on one hand statig that seemingly array languages tend to be letter soupy, for which I replied that a selection bias is at play, as array languges are used widely, most notably Matlab is used widely which is not a letter soup. It is simply not regurgulated on the site as it does not seem so hardcore. Nevertheless you are right, array langueges have been around earlier, for example Matlab itself dates back to the 1970s. I do not understand the awe some are giving them in the comments, they are an easy to understand paradigm, which is very well suited for certain types of problems. Some having overly terse syntax is a thing, but I do not feel that only geniuses can comprehend array programming, anyone who did learn some university level physics or signal processing has the tools in their belt.
- IshKebab 2y ago
  Yeah I think MATLAB and Mathematica are waaay more used than K et al. They just don't look insane so people aren't posting them on HN as much.

asah 2y ago

What baud is that? /s

genewitch 2y ago
mismatched, whatever it is, that's for sure. It's not quite line noise, so maybe it's just the wrong stop bit?
speed_spread 2y ago
My cat puked in the modem receiver cup, sorry.

deleted 2y ago

[deleted]

dang 2y ago

I put 2011 in the title above because https://web.archive.org/web/20110813135700/https://dfns.dyalog.com/n_sudoku.htm https://web.archive.org/web/20110813135700/https://dfns.dyal... appears to have the main thing - is there a better year?

lofaszvanitt 2y ago

It has strong perl vibes and it brings back ptsd :D. Maybe this overshortification of things is a personnel or intelligence indicator of some sorts.

gorgoiler 2y ago

Every K program ought to end in QED, and then I remember that KQED is also a thing, and I wonder if their two worlds have ever overlapped. (KQED is the Bay Area PBS partner. PBS is the US public television org.)

lucw 2y ago

Does anyone have any thoughts on what motivates people to play sudoku or write solvers for sudoku ? I have trouble finding motivation to solve artificial problems. That said I sink hundreds of hours into factorio.

riffraff 2y ago
I don't particularly enjoy sudoku but I like word puzzle games. They're all artificial problems, but your brain likes a challenge and you get a dopamine hit when you solve it, I suppose.
bramhaag 2y ago
For me personally, I have little motivation to do classical sudokus. They either have a not-so-elegant solve path (usually set by a computer) or are too difficult for me to solve. Variant sudokus on the other hand are a lot of fun. They often have very elegant solve paths and there are many neat tricks you can discover and reason about. Some fun ones, if you'd like to try: - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000DMZ https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id... - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000CN6 https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id... - https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000JKX https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id...
- akleemans 2y ago
  I also mostly enjoy Sudoku variants, most of which I discovered via Geocaches, interestingly. After solving a few I then implemented a solver with customizable constraints, if anyone's interested, should still be available here: https://www.sudoku-solver.ch/ https://www.sudoku-solver.ch/
- sltkr 2y ago
  To each their own, but the puzzles you linked seem really convoluted compared to regular Sudoku. The last puzzle has no fewer than 9 custom rules, in addition to the regular Sudoku rules, and then it also says “every clue is wrogn [sic]” implying there is some meta out-of-the-box thinking required to even understand what the rules are. That is more a riddle than a logic puzzle. By contrast, the charm of classical Sudoku is that the rules are extremely simple and straightforward (fill the grid using digits 1 through 9, so that each digit occurs exactly once in each row, column, and 3x3 box) and any difficulty solving comes from the configuration of the grid.

upghost 2y ago

Most people are put off by the symbols, that wasn't really the issue I had. So I do love APL and arraylangs, and learning them was really helpful in a lot of other languages. But they never became a daily driver for me not because of the symbols, which were honestly fine if you stick with it long enough, but after about 3-4 years of dabbling on and off I hit a wall with APL I just couldn't get past. Most other languages I know there is a "generic-ish" approach to solving most problems, even if you have to cludge your way through suboptimally until you find "the trick" for that particular problem and then you can write something really elegant and efficient. APL it felt like there was no cludge option -- you either knew the trick or you didn't. There was no "graceful degredation" strategy I could identify. Now, is this actually the case? I can't tell if this is a case of "yeah, thats how it is, but if you learn enough tricks you develop an emergent problem solving intuition", or if its like, "no its tricks all the way down", or if its more like, "wait you didn't read the thing on THE strategy??". Orrr maybe I just don't have the neurons for it, not sure. Not ruling it out.

lokedhs 2y ago
You're not wrong. It's very easy to get that impression when trying to learn the array languages. It's very easy for someone who's used these languages for a long time to look at a problem, and say "why did you use that really elaborate solution, when you can just use ⍸⍣¯1?". No one probably ever told you that ⍸ has an inverse, and how you could use it. Even today, after having worked in these languages for years, I am still put off a bit by the walls of code that some array programmers produce. I fully understand the reasoning why it's written like that, but I just prefer a few spaces in my code. I've been working on an array language based on APL, and one of my original goals was to make "imperative style" programming more of a first-class citizen and not punish the beginner from using things like if-statements. It remains to be seen how well I succeeded, but even I tend to use a more expressive style when terseness doesn't matter. Here's an example of code I've written which is the part of the implementation that is responsible for taking any value (such as nested arrays) and format them nicely as text using box drawing characters. I want to say that this style is a middle ground between the hardcore pure APL style found in some projects and the style you'll see in most imperative languages: https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap https://codeberg.org/loke/array/src/branch/master/array/stan...

yumraj 2y ago

[flagged]

yumraj 2y ago
Gemini also identifies it as J and this is the output for comparison: The programming language used in the code is *J* (pronounced "Jay"). It's a concise, array-oriented programming language known for its expressive syntax and powerful capabilities. Here's a breakdown of the code: *1. Verb Definition:* * `x(,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}')/&~x` defines a verb (a function in J terminology) and assigns it to the variable `x`. *2. Verb Structure:* * `x( ... )/&~x` is the basic structure of the verb. `x( ... )` applies the verb defined within the parentheses to its argument, which will be `x` itself. * `/&~x` is a hook, a control flow construct in J. It applies the verb defined within the parentheses to each element of `x` and then applies the verb `&~x` to the resulting array. *3. Verb Body:* * `,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}` is the body of the verb. Let's break it down further: * `{@[x;y;]` creates a gerund (a verb-like noun) that takes two arguments, `x` and `y`. * `'(!10)^x` generates an array of `x` elements, each raised to the power of `!10` (factorial of 10). `/p[;y]=p` is a conjunction that appends the value of `p` to itself for each element in `y`. * `,:,3/:-3!p:!9 9}` generates an array of 3 elements, each of which is the factorial of `-3` (which is undefined and results in an error) followed by the number 9. *4. Overall Functionality:* * The verb takes an array `x` as input. * It applies the gerund to each element of `x`, creating an array of arrays. * It then applies the conjunction to each of these arrays, appending the value of `p` (which is likely defined elsewhere in the code) to itself. * Finally, it generates an array of 3 elements with errors and 9s. * The hook `/&~x` applies the verb to each element of `x` and then applies a function that is likely defined elsewhere in the code (since `&~x` is not defined within this verb). *Note:* Without more context about the definitions of `p` and other variables or functions used in the code, it's difficult to provide a more precise explanation of the verb's exact behavior. However, the breakdown above should give you a general understanding of the code's structure and logic.
- rak1507 2y ago
  Please kindly delete your account, destroy your devices, and move to the woods far away from technology.

fhdufxm 2y ago

[flagged]

nine_k 2y ago

Lines of code is a poor metric, because languages use lines differently. A much better measure would be the number of nodes in a parse tree, of semantically meaningful non-terminals like "a constant" or "a function call". An even better measure would also involve the depth and the branching factor of that tree.

tromp 2y ago
The preferred measure of information content is simply number of bits as used for instance in Algorithmic Information Theory [1]. [1] https://en.wikipedia.org/wiki/Algorithmic_information_theory https://en.wikipedia.org/wiki/Algorithmic_information_theory
- jodrellblank 2y ago
  By that measure naming a variable “objUser” instead of “user” is better because it has more information, and naming the same variable “cgjkkytdvjkftujmhffetb” is even better because it contains more information. The parse tree approach is trying to get at a fuzzy notion of useful information and useful density of information.
smokel 2y ago
The built-in functions and API to a system library spoil these metrics. As an example, consider HQ9+, which is pretty good at printing "Hello, world!" for instance. https://cliffle.com/esoterica/hq9plus/ https://cliffle.com/esoterica/hq9plus/
xelxebar 2y ago
Just... no. What are you even trying to compare? UX of a language matters. Clarity, thinking paradigm, expressability etc. all matter and are affected by the visual size of code. A one line solution takes up very little visual real estate. That matters a lot when you are working on some more complex problem. Flitting your eyeballs around a screen takes orders of magnitude less effort than scrolling around and navigating files. Cognitive load is important. We really need to burn this vague "only semantics matter" scourge that's creeped into our programmer values these days. I'm sorry, but I care about things like incentives against over-engineering, ease of directly thinking in the problem domain, and simplicity of the encompassing ecosystem. A terse one-line solution tells me there is virtually no room for over-engineering. Even without knowing K, I can see obvious constants side-by-side, telling me it's likely using a direct data representation of the problem in its code. Does K culture encourage code like that? Does programming in K bias you towards directness and simplicity? Then please, I want some of that special sauce on my team. </rant>

sorokod 2y ago

The LoC count and similar metrics have the advantage of an easy calculation. Ultimately though,they are a proxy to a more relevant but difficult to determine attributes such as Given a reasonably proficient engineer, the amount of time it would take them to resolve a bug in code written by someone else or alternatively extend its functionality in some way.

bazoom42 2y ago

The discussions around “line noise”-languages are always intersting. Most programmers would agree the ‘/’ symbol is at least as clear as writing ‘divideBy’. The question is how often the symbols are used and if their frequency in code justifies learning them.

brador 2y ago

Someone should collate exceptional human coding achievements to test future AI. AFAICT AI cannot replicate this, yet, will be interesting when that day comes.

TZubiri 2y ago

I thought it was written by Ursula K. Le guin. Not sure where I got that from.

Intralexical 2y ago

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

forgotpwd16 2y ago
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 https://codegolf.stackexchange.com/a/5030

eigenvalue 2y ago

It's cool in a novelty way that it’s so short, but I would infinitely prefer something like this for actual work and understanding: def solve(grid): def find_empty(grid): for r in range(9): for c in range(9): if grid[r][c] == 0: return r, c return None def is_valid(grid, num, pos): r, c = pos if num in grid[r]: return False if num in [grid[i][c] for i in range(9)]: return False box_r, box_c = r // 3 * 3, c // 3 * 3 for i in range(box_r, box_r + 3): for j in range(box_c, box_c + 3): if grid[i][j] == num: return False return True def backtrack(grid): empty = find_empty(grid) if not empty: return True r, c = empty for num in range(1, 10): if is_valid(grid, num, (r, c)): grid[r][c] = num if backtrack(grid): return True grid[r][c] = 0 return False backtrack(grid) return grid

upghost 2y ago
Why is this getting down-voted without comment? Comparative analysis is taboo, now? I don't think Arthur Whitney would feel the least bit threatened by some Python code.
- eigenvalue 2y ago
  The K-mafia is in control. Just kidding, I don’t really care either way…
- BoiledCabbage 2y ago
  Speculation, but maybe because there is nothing of interest or to note in the comment. It's not clear why the poster prefers that other implementation, or that they understand APL or array programming. So as a result the comment reads as "it's in a language I don't know. I'd prefer it in a language I do know." Which is a fairly useless comment. If that's not what they intended, it would be helpful for them to add some context to their comment.

upghost 2y ago

Well if we are showing off sudoku solvers, it would be a sin not to share this one: sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), append(Rows, Vs), Vs ins 1..9, maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is). blocks([], [], []). blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]), blocks(Ns1, Ns2, Ns3). While not one line, to me it is pareto optimal for readable, elegant, and incredibly powerful thanks to the first class constraint solvers that ship with Scryer Prolog. If you want to learn more about it or see more of Markus's work: https://www.metalevel.at/sudoku/ https://www.metalevel.at/sudoku/ https://youtu.be/5KUdEZTu06o https://youtu.be/5KUdEZTu06o More about Scryer Prolog (a modern , performant, ISO-compliant prolog written mostly in rust) https://www.scryer.pl/ https://www.scryer.pl/ https://github.com/mthom/scryer-prolog https://github.com/mthom/scryer-prolog

iamyourcanary 2y ago

[dead]

Duanemclemore 2y ago

For me one of the most important things here is the clarity of the problem -maker- at the top. That's the difference between the "Iversonian" symbolic languages (J and K included) and others. It doesn't have the elegance and power of a one line solution, but it's just so clean and comprehensible even without the disciplined commenting. (Although I really think lamp is not a good comment glyph. Sorry about the sacred cow I just took a swipe at fellow array nerds.) One line solutions are incredible, and tacit is mind-bendingly cool. To use the unique compactness of a glyph-based language as a way to efficiently describe and perform functional programming - then to do that all over arrays!? - whoever had these ideas [0] is utterly genius. But as someone trying to make time to write a program ground up in APL, knowing that I won't be able to make it just a set of really good one liners, that example is also significant for me. [0] https://www.jsoftware.com/papers/fork.htm https://www.jsoftware.com/papers/fork.htm

lokedhs 2y ago
Just because you can write everything on one line without any spaces doesn't mean you should. You can ofcourse removethe capability to do thatand you'll effectively force the programmer to write more venous code, but then its strength as an interfacing tool is very much reduced. The Iversonian languages has the capability to write incredibly terse code which is really useful when working interactively. When you do, your code truly is write-only because it isn't even saved. This is the majority of code that at least I write in these languages. When writing code that goes in a file, you can choose which style you want to use, and I certainly recommend making it a bit less terse in those cases. The Iversonian languages are still going to give you organs that are much shorter than most other languages even even it's written in a verbose style.

deleted 2y ago

[deleted]

geekraver 2y ago

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/ https://www.grahamwheeler.com/post/sudoku/

cachvico 2y ago

The k code explained: https://chatgpt.com/share/67036e8e-17dc-800f-96c4-1fac8b291f43 https://chatgpt.com/share/67036e8e-17dc-800f-96c4-1fac8b291f...

rak1507 2y ago
This is (predictably) wrong.
- cachvico 2y ago
  hah

bishop77 2y ago

For sudokus of size 9x9 and 16x16 almost any unoptimised DFS will work just fine (even for hard sudokus [0]). The real challenge is for sudokus of size 25x25 and above. [0] https://cdn.aaai.org/ocs/2517/2517-11201-1-PB.pdf https://cdn.aaai.org/ocs/2517/2517-11201-1-PB.pdf

nephronaut 2y ago

So how to feed in the instance if code is only Nebulous1: Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}')/&~x