Arthur Whitney's one liner sudoku solver (2011) • Hacker News Board

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

#151

Post by upghost » Sun, Oct 06, 2024, 3:38 PM UTC

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://youtu.be/5KUdEZTu06o

More about Scryer Prolog (a modern , performant, ISO-compliant prolog written mostly in rust)

https://www.scryer.pl/

https://github.com/mthom/scryer-prolog

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

#152

Post by iamyourcanary » Sun, Oct 06, 2024, 3:54 PM UTC

[dead]

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

#153

Post by PhilipRoman » Sun, Oct 06, 2024, 3:58 PM UTC

rtpg wrote: post #94

brookst wrote: post #20

Earlier quoted context omitted.

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

I've been messing with Uiua ( https://www.uiua.org/ ) a good amount recently, and find its sort of dance between having a stack and being an array language somehow gets you to a nice level of legibility despite being a combo of two styles that tend to generate line noise.

Cool language. I happened to notice the ⍜ operator, which operates on a transformed array, then reverts the transformation. Not sure if other array languages include this, but it's a really cool idea. I always found the traditional map/filter operators to be limiting in this regard, kind of like trying to write expressions without using parentheses.

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

#154

Post by dahart » Sun, Oct 06, 2024, 3:59 PM UTC

xelxebar wrote: post #112

nine_k wrote: post #90

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.

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 navigat…

Don’t get confused between using smaller keywords and actually understanding the problem at hand. Terse languages do absolutely nothing to prevent over-engineering. They might even contribute by giving a false sense of simplicity and a tendency to prevent certain kinds of code reuse. To prevent over-engineering on large projects, you don’t need a terse language at all, you need the right mentality, the right management & product team, good team culture & cohesion, strong code review process, and job performance metrics that align with not over-producing code.

It seems like parent’s metric (size of parse tree) would easily optimize for terseness and penalize bloat, regardless of language, so maybe your reaction was too reflexive. UX of a language does matter a bit, and one that’s too terse incurs development friction and technical debt when used in larger projects. Just study the history of Perl and why it’s not widely used.

What a one liner looks like is more or less the worst possible metric to use for large software projects. In any language, the style of code changes the larger the codebase, and cleverness and terseness become a liability. https://www.teamten.com/lawrence/writings/norris-numbers.htm...

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

#155

Post by upghost » Sun, Oct 06, 2024, 4:00 PM UTC

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…

God bless, my hat goes off to you sir. I have trouble wrapping my head around the concept of first class functions in ndarrays, let alone implementing it in hardcore APL. That has to be a feat on par with Hsu's Co-Dfns.

Don't suppose you can point to any resources to help wrap your head around BQN, do you?

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

#156

Post by upghost » Sun, Oct 06, 2024, 4:26 PM UTC

eigenvalue wrote: post #145

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 f…

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.

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

#157

Post by mlochbaum » Sun, Oct 06, 2024, 4:27 PM UTC

upghost wrote: post #155

mlochbaum wrote: post #136

Earlier quoted context omitted.

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…

God bless, my hat goes off to you sir. I have trouble wrapping my head around the concept of first class functions in ndarrays, let alone implementing it in hardcore APL. That has to be a feat on par with Hsu's Co-Dfns. Don't suppose you can point to any resources to help wrap your head around BQN, do you?

Well this is pretty much the goal of the BQN website so my best attempts are there. I might point to the quick start page https://mlochbaum.github.io/BQN/doc/quick.html as a way to feel more comfortable with the syntax right away. And the community page https://mlochbaum.github.io/BQN/community/index.html collects links by others; Sylvia's blog in particular focuses on the sorts of flat array techniques that are useful for a compiler.

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

#158

Post by campbel » Sun, Oct 06, 2024, 4:30 PM UTC

shawn_w wrote: post #53

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?

I suspect that if you're fluent in the language, understanding an expression written in it comes just as easily and quickly as reading a sentence in a book does to me.

Information density is studied in linguistics. It could likely apply to programming languages similarly.

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

#159

Post by eigenvalue » Sun, Oct 06, 2024, 4:32 PM UTC

upghost wrote: post #156

eigenvalue wrote: post #145

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 f…

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.

The K-mafia is in control. Just kidding, I don’t really care either way…

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

#160

Post by upghost » Sun, Oct 06, 2024, 4:42 PM UTC

mlochbaum wrote: post #157

upghost wrote: post #155

Earlier quoted context omitted.

God bless, my hat goes off to you sir. I have trouble wrapping my head around the concept of first class functions in ndarrays, let alone implementing it in hardcore APL. That has to be a feat on par with Hsu's Co-Dfns. Don't suppose you can point to any resources to help wrap your head around BQN, do you?

Well this is pretty much the goal of the BQN website so my best attempts are there. I might point to the quick start page https://mlochbaum.github.io/BQN/doc/quick.html as a way to feel more comfortable with the syntax right away. And the community page https://mlochbaum.github.io/BQN/community/index.html collects links by others; Sylvia's blog in particular focuses on the sorts of flat array techniques that are usef…

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 excited to take another look at it!