18 ms·

While definitely great proof of: 1. The author knowing a lot of the language's functional features (permutations, mapping, zipping, filters) 2. How powerful fun

• tyingq 11y ago
  Here's < 15 lines, clear, but not functional programming :) #!/usr/local/bin/perl #borrowed from Nick Holloway <alfie@dcs.warwick.ac.uk>, 27th May 1993. my $size=8;my @cols=(0..$size-1); sub nextq { (print( "@_\n" ),return) if @_ == $size; foreach my $col(@cols) { next if grep($_ == $col, @_); my $row=@_;next if grep ($_ == $col-$row--, @_); my $row=@_;next if grep ($_ == $col+$row--, @_); nextq(@_,$col); } } nextq(); Not sure if it's slower or more resource intensive than the Scala solution. I'm sure it could be golfed down to be smaller than the Scala counterpart. It has fewer characters already, even with the comments intact.
  • username223 11y ago
    Indeed, it has been golfed: http://www.perlmonks.org/?node_id=196582 http://www.perlmonks.org/?node_id=196582 -l /.{@ARGV}/?print:map/((.).*)(.)(??{$2!=$3&&length$1!=abs$2-$3&&0})/||do$0,$_.1.."$_@ARGV"
    • _asummers 11y ago
      That's frightening. I hate to ask, but is that representative of Perl code?
      • dalke 11y ago
        No. Golf is a game where the winner has the lowest score. It's reused as the term for a programming challenge to implement an algorithm with the fewest number of characters. See https://en.wikipedia.org/wiki/Perl#Perl_pastimes https://en.wikipedia.org/wiki/Perl#Perl_pastimes . This is no more indicative of Perl than the Obfuscated C contest is indicative of C.
      • GregBuchholz 11y ago
        Javascript anyone? !function r(y,a,z,b,x){for(x=y--?-1:print(a);++x<n;z&c|b&d||r(y,a+1?a+' '+x:x,z|c,b|d))c=(1|1<<y+9)<<x,d=1<<9+x-y}(n=readline()) http://golf.shinh.org/reveal.rb?N+Queens/murky-satyr_1217229999&js http://golf.shinh.org/reveal.rb?N+Queens/murky-satyr_1217229...
      • username223 11y ago
        Not at all, but it is representative of the best of Perl culture: smart people who enjoy playing with unexpected corners of a complex system, while remembering the difference between "work" and "play." See Ton Hospel's insane Roman numeral calculator: http://perlmonks.org/?node_id=594299 http://perlmonks.org/?node_id=594299
  • laumars 11y ago
    It's actually more lines than it appears since the author has concatenated lines with a semi-colon: my $size=8;my @cols=(0..$size-1); my $row=@_;next if grep ($_ == $col-$row--, @_); my $row=@_;next if grep ($_ == $col+$row--, @_); Strictly speaking that's 6 lines of code concatenated into 3. But as you said, it would be relatively easy to golf that down and still keep the program logic.
    • tyingq 11y ago
      Perl being big on "more than one way to do things...", semicolons are easy to discard: sub nextq { my $sz=8; (print("@_\n"),return) if @_ == $sz; foreach my $col(0..$sz-1) { my $row; if (grep($_==$col,@_)) {next} else {$row=@_} if (grep($_==$col-$row--,@_)) {next} else {$row=@_} if (grep($_==$col+$row--,@_)) {next} else {$row=@_} nextq(@_,$col); } } nextq();
      • laumars 11y ago
        I still feel that's cheating as you're just replacing the semi-colon with braced blocks; effectively it's still being parsed as multiple lines. I was thinking more along the lines of using the one line conditional: condition ? first_expression : second_expression; eg sub nextq { (print( "@_\n" ),return) if @_ == (my $size = 8); foreach my $col(0..$size-1) { my ($row, $next); grep ($_ == $col, @_) ? $next=1 : $row=@_; grep ($_ == $col-$row--, @_) ? $next=1 : $row=@_; grep ($_ == $col+$row--, @_) ? $next=1 : $row=@_; nextq(@_,$col) unless $next; } } nextq(); The `$next` ugliness is due to not being allowed to use the `next` inside a one line conditional. There's probably cleaner ways of doing the above though. But that was only a quick hack.
        • shasta 11y ago
          It's almost as if "number of lines" isn't particularly meaningful.
          • 11y ago
  • ionforce 11y ago
    The lack of whitespace is maddening. It contributes to the reputation that Perl is write once read never. That "print and return with postfix" is the gold star. /s
    • tyingq 11y ago
      The context being a deliberate effort to make it compact. You can abuse features in most languages and make it hard to read.
      • ionforce 11y ago
        Who cares about "compactness"? You weren't golfing. It just sticks out as bad code.
        • tyingq 11y ago
          Not my code, it was copied (note the attribution) from a specific context where somebody cared about compactness. Edit: Perl's also not the only language that supports the comma operator, predicate if, ternary, and other things that seem to bother you.
• CJefferson 11y ago
  Also, this is (I think, I'm not 100% up on Scala), insanely inefficient. Usually when people discuss the n-queens problem, they do a backtrack search, stopping as soon as some queen conflicts with an earlier queen. You can of course then go on and get increasingly clever, but I think you should at least aim for backtracking.
• atemerev 11y ago
  Those are bread and butter of functional programming, like for loop, break and continue in imperative programming. There are really no advanced features here; not even a single monad! For someone completely unfamiliar with FP, the cognitive load might be high. However, even basic familiarity with FP constructs is enough to understand and appreciate the code.
  • hk__2 11y ago
    The fact that it needs two comments to clarify what it’s doing is a code smell in itself.
    • atemerev 11y ago
      So, comments are code smell?
      • deleted 11y ago
        [deleted]
      • hk__2 11y ago
        That’s not what I wrote.
    • Retra 11y ago
      It doesn't need those comments; you do.
• dustingetz 11y ago
  I think a more reasonable comparison is 4 lines of code you have to think hard to decipher but is correct, vs 40 lines of code that has a bunch of bugs and edge cases and is just as jibberish but 10x more code to decipher. Shorter solutions often encode the authors insight from thinking about the problem, and longer solutions encode are more of a history of the path an author took while just hammering on it without any particular insight until it worked good enough.
• mathetic 11y ago
  Arggh, every single time someone posts an incredible cool small piece of code that solves a difficult problem, comments like this appear. This whole HN attitude of pristine code is killing me. This is a piece of code in a GIST and solves the problem in three lines, it is clearly not intended for production use in a large code base. Please stop searching for something wrong and enjoy what is presented in all of its glory.
  • zyngaro 11y ago
    Maybe it's the case here but in the scala community in general I noted a tendency to emphasize cleverness over clarity and simplicity.
    • ADRIANFR 11y ago
      Relevant Stack Overflow question: http://stackoverflow.com/questions/7084212/is-scala-idiomatic-coding-style-just-a-cool-trap-for-writing-inefficient-code http://stackoverflow.com/questions/7084212/is-scala-idiomati...
  • deleted 11y ago
    [deleted]
  • haddr 11y ago
    The difference here is that when you read the title you think: "wow, scala features allows solving interesting problems in few steps, let's see". And the you realize that it's a cheat. This code is literaly squeezed into those 4 lines, full of less common idioms, and quite obscure. It should be called "0,5kb scala contest" than "solving x with scala", to avoid misunderstanding.
  • pyrale 11y ago
    This piece of code doesn't "solve" the problem, it's a crude bruteforce implementation. The problem is hard for a reason. Another way this code could be useful would be to showcase good readability practices, but it doesn't.
• deleted 11y ago
  [deleted]
• gawi 11y ago
  Better yet: 4 lines of code + a few lines of comments.
• deleted 11y ago
  [deleted]
• Veedrac 11y ago
  This has nothing to do with functional programming. Here's an iterative Python solution that's almost a direct translation but uses explicit iteration and avoids `filter`/`map`/etc. from itertools import permutations def n_queens(n): for p in permutations(range(n)): if len({c + i for i, c in enumerate(p)}) == len({c - i for i, c in enumerate(p)}) == n: yield p
  • atemerev 11y ago
    Looks quite functional to me. Except that it uses "for comprehension" instead of map/filter (a matter of preference).
    • Veedrac 11y ago
      Well then functional doesn't mean very much :P. Python's iterators are mutation-based, so not really functional. `yield` is based around pause-resume of function execution, so not really functional. `permutations` is just a function that wraps a list (or iterator coercible to one (which mutates the iterator)) and returns a (mutable) iterator. A `for` comprehension desugars to a `for` loop with `yield` if it's a lazy comprehension, `append` if it's a list comprehension or `add` if it's a set comprehension, which of course involves mutation. Basically nothing here is mutation free. That, at least IMO, means it's not functional.
      • willtim 11y ago
        You seem to be confusing interface and implementation. Lazy lists and for comprehensions appeared in functional programming languages first; and that Python code looks to have borrowed them.
        • Veedrac 11y ago
          Addition appeared in imperative languages first. Does that mean addition is imperative? It's great that functional languages were first to catch onto these ideas, but that doesn't mean that anything else that uses them becomes functional. The interface isn't even functional, since in code like foo = iter((1, 2, 3)) {x for x in foo} `foo` is mutated. No "true" functional language would accept that ;).
• edejong 11y ago
  Such tight structures might be difficult to parse when the patterns used are still relatively unknown. However, once applied more widely, read more often and more familiar, you might start to think the longer version (which undoubtedly relies on ambiguous naming) becomes unreadable. Said in other words: 15 line solutions cannot break into the higher-order pattern-recognition space, since these solutions rely on context specific naming. Naming is one of the most difficult parts of software engineering, so we should try to rely on contextual patterns in order to minimize naming altogether.
  • richard_todd 11y ago
    Indeed, one thing I initially liked about Prolog was that you can't deeply nest expressions due to the way evaluation works. Simple examples looked nice and explicit. But, you quickly run into the problem of having to name 15 intermediate stages of a harder computation, and suddenly all your names are L3, L4, L5, ... which makes the code hard to understand again. So, complexity is complexity in the end, and you can pick your poison. The same issue arises when factoring Forth code into tiny "words" (one of the advantages of a concatenative language): you have to name sequences of operations that don't have an obvious problem-space concept behind them.
• digsmahler 11y ago
  Ironically, the article linked, "Writing good code: how to reduce the cognitive load of your code", itself has a high cognitive load. It's grammatically irksome. The opening sentence has no verb, "Low bug count, good performance, easy modification." Further it uses poor non-examples of the points the author is trying to make. For example, Yoda conditionals are quirky, but do not increase cognitive load. They were also called out as a good habit in Code Complete, the very book the author sites as the long form of what he's writing about. OTOH, the gist has a low cognitive load provided one understands funtional notation. I can look at his four lines of code and see that this is a correct solution, because each atom of the function can be reasoned about separately and then composed into the whole. The same is much more difficult with the looping solutions that have been presented as peers to this comment. These solutions have a higher cognitive load because proving correctness requires a full trace of the algorithm, while keeping all of the variables in working memory as you go. tl;dr; The OP presented a clear and clever solution. I'll allow it. ;)
• qznc 11y ago
  Maybe terse Scala solutions compare to longer C solution, like terse math equations compare to longer prose text? People who are not used to greek symbols, read equations in the same speed and mindset like english text and get confused quickly. Reading requires a different mode. I would always prefer a map/fold to a for-loop. Removing the "i" and its book keeping reduces cognitive load. However, a Python list comprehension often becomes too big an expression if you use too much filtering. Extracting the filter into its own function an giving it a good name compartmentalizes the complexity, though. All in all, it is quite subjective. If you are used to premutations, mapping, zipping, filters the code becomes quite readable. I'm pretty sure there is C code which confuses a Haskell programmer but would be considered "clear and readable" by the average C programmer.
• tunesmith 11y ago
  This is honestly pretty clear to understand - there's hardly anything there other than those general functional features you listed. I think there's a difference between the cognitive load of the solution and the cognitive load of the implementation. The cognitive load of the general solution for queens is somewhat high, but that's why it's a well-known puzzle. But this implementation is practically a description of the problem itself. It's literally selecting (filter) from all queen arrangements (permutations) where the queens aren't conflicting (described via map and zipWithIndex).
• AzzieElbab 11y ago
  it is collections api which has always been very well documented, as opposed to some scary "functional features". Nothing too advanced and absolutely no hacks
• pfn 11y ago
  permutation, mapping, zipping and filtering are all completely idiomatic scala. There is next to no cognitive load in this 4-line solution. Brute-force attack on every permutation. I would say that anyone find there to be an excessive cognitive load would be someone that is not familiar with scala nor functional programming.