7 ms·

(from the sibling archive link) > Roll Your Own Chat Server > Implement a simple standalone TCP-based chat server, using the following protocol: > ...

(from the sibling archive link) > Roll Your Own Chat Server > Implement a simple standalone TCP-based chat server, using the following protocol: > ... > When implementing the server, aim for scalability and robustness. (Many submissions fail due to lack of robustness!) > ... > Please do not use an existing networking framework Oh man. You weren't kidding, that's high-precision nerd-sniping.

ncmncm 5y ago
I suspect the earlier puzzles were most of the better ones. What I sent in was the Add-a-gram (on that page, stashed behind the "Puzzle Archive" link). I sent one solution, and when they called, they admitted others were faster, so I redid it that evening ten times faster and sent that. What they never told me, even after I had been there for years, was that my second solution was faster than theirs or any others they had on file. It looks like they retired it right after I started there, maybe because I had shown it didn't actually require backtracking, which they were trying to filter for–ITA was mostly a Lisp shop, so they wanted people who would always reach for recursion first. My solutions were relentlessly iterative. Some years after I left ITA, they posted the Bitvectors puzzle, which I had to solve, in a fever, but never sent off. (At the time I think it had a different name.) That solution also didn't require backtracking.
- hoseja 5y ago
  I just don't get how anyone can use recursion for anything serious. Especially when it can always be unrolled into a more comprehensible / representative of what's actually happening iteration.
  - KineticLensman 5y ago
    If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient. [0] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
    - ncmncm 5y ago
      I.e., the compiler converts the recursive code you wrote into the iterative form you could have written, and runs that instead because it's faster.
      - Jtsummers 5y ago
        I find this argument interesting because, to me, it leads to endorsing a view that we should be using goto and conditional jumps instead of for/while loops and similar structured programming elements. I mean, the former are more explicit, the latter implicit, since the compiler converts the latter into the former. Having maintained a fair amount of unstructured code, I'd rather stick with the higher level languages since they allow me to express my intent more clearly. Which pushes me to using recursion where it's appropriate and the language has appropriate facilities to handle tail call elimination.
        ncmncm 5y ago
        We make languages and compilers the way we do for reasons. But it is a mistake to confuse what automation hides from you, for practical reasons, with fundamental qualities of the universe or of computation. Another common example of the error is describing an algorithm as N log N, assuming that the numbers involved occupy constant space and multiply in constant time. In real-world computation, space tends to log N, and multiply in close to (log N)^2 time and power consumption. We get away with it for the same reason recursion works: the problems we apply our algorithms to usually fit in conveniently constrained space, and our multiplier hardware takes the same time and power for small numbers as for the biggest ones we can conveniently represent.
  - ChrisLomont 5y ago
    Lots of problems have vastly simpler recursive solutions. Try putting a recursive descent parser into a loop. Plenty of tree walking/formatting/analyzing algorithms are much cleaner using recursion. Recursively walking directory structures is cleaner using recursion. Many puzzles, such as Tower of Hanoi, are cleaner with recursion. Many sort algorithms, like merge sort, quicksort, etc., are cleaner with recursion. I could find plenty more algorithms where recursion makes the solution cleaner, simpler (hence less error prone), and sometimes even faster to execute. And some algorithms use mutual recursion to solve problems - often putting those into a non-recursive formulation results in incredibly messy code. Mutual recursion is powerful enough that F# (among others) added an entire keyword to the language simply to support it. And since many languages do proper tail recursion, there is no penalty for using it properly.
    - ncmncm 5y ago
      In CS, you encounter lots of problems that are naturally solved by recursion not because such problems are especially common, but because they are favorites of CS professors. Language parsers do a lot of recursion because the languages we invent are invented by CS people who like problems that can be solved that way, and because language itself is one that lends itself to that. It is hard to tease out which recursions we find because professors just like it, and which ones real-world problems demand. Many commonly cited as the latter turn out, on close examination, to be the former.
      - titzer 5y ago
        > but because they are favorites of CS professors. I work on compilers and compilers are full of graphs. Graphs typically have a lot of algorithms that are naturally recursive. It's not because of some theoretical fetish.
        ncmncm 5y ago
        But CS professors love graph problems. So, it's not so easy to say.
      - 5y ago
  - anonymoushn 5y ago
    Which would you prefer? def msort(xs, lo=None, hi=None): if lo is None: lo = 0 hi = len(xs) if hi-lo < 2: return mid = lo + (hi-lo) // 2 msort(xs, lo, mid) msort(xs, mid, hi) merge(xs, lo, mid, hi) def msort(xs): s = [[0, len(xs) // 2, len(xs), "step 1"]] while s: lo, mid, hi, step = xs[-1] if step == "step 1": if hi-lo < 2: s.pop() else: s[-1][3] = "step 2" s.append([lo, lo + (mid-lo) // 2, mid, "step 1"]) elif step == "step 2": s[-1][3] = "step 3" s.append([mid, mid + (hi-mid) // 2, hi, "step 1"]) else: s.pop() merge(xs, lo, mid, hi)
    - qsort 5y ago
      The one that doesn't blow up the stack.
  - Joker_vD 5y ago
    Okay, here's the very recent problem I had to solve. There is a huge dump of a VM heap, represented as a key-value map: the values are either simple atomic values or compound structures that have addresses (keys into this map) as their parts. There is a list of "entry points" into the heap: addresses of the GC roots in the heap. The problem is to reconstruct the values stored in the heap. E.g., reconstructing starting from "heap(10)" in this heap: heap(10): cons(int(1),heap(18)) heap(18): cons(int(2),heap(20)) heap(20): cons(int(3),nil) should result in [1, 2, 3] Here's the thing: recursive walk is totally straightforward: def restore(v): if v.kind... elif v.kind == 'tuple': return Tuple([restore(v[i]) for i in range(v.arity)]) elif v.kind == 'cons': return List(restore(v[0]), restore(v[1])) elif v.kind... else: return UnknownValue() But since Python has a limit of 1000 nested function calls, restoration of long lists fails with StackOverflow, and so I had to rewrite it using manual stack. The result is sort of ugly, in fact, I had to use two stacks: one for temporary reconstructed pieces of data, one for "what to do next". Essentially it's implementing a variation of the shunting yard algorithm and while the resulting code is kinda clear in intent, it's still three times as long as the recursive version and is not obviously correct. In fact, I had to tweak it several times (including the introduction of the second stack) before I stopped seeing some (not all!) lists reconstructed in the reverse order.
  - martincmartin 5y ago
    Because you get a stack for free. It's very natural for depth first search of a tree.
    - ncmncm 5y ago
      Unpleasant fact best learned early: the stack is not free. The "very natural" appearance is an artifact of the languages we have (very unnaturally) constructed.
      - titzer 5y ago
        The machine stack given by modern CPUs is blazingly fast, because microarchitectures typically have a return stack buffer that allows the processor to perfectly branch-predict returns. Manually coding recursive algorithms means you have to switch over the return state, which involves a different predictor that will be less accurate. Given that, and machines typically have an architectural stack pointer register with dedicated instructions to push and pop to it, the manual datastructure you come up with to simulate a stack is almost certainly going to be slower.
        ncmncm 5y ago
        It is always an error to assume you know which of any architectural alternatives will be faster. You have to measure, if it matters.
        titzer 5y ago
        Please do. This is my prediction based on years and years of optimizing machine code and measuring on recent microarchitectures. I look forward to seeing your handwritten assembly proving your overgeneralized claims about recursion being inherently slower.
        ncmncm 5y ago
        I did not, in fact, claim that recursion is inherently slower than iteration. You are welcome to read what I did write, above. Usually it is considered better (hint, hint) to do that before replying.
  - ncmncm 5y ago
    Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand". But the recursive code can be much shorter, and easier to understand, because our languages have built-in apparatus to support it. They didn't always; original FORTRAN could not do recursion, and used no stack. The stack isn't free at runtime, but it's pretty cheap, and its fatal failure mode is rarely encountered nowadays. In my work, I have always found the iterative version cleaner and faster, but that is an artifact of the kinds of problems I (and most people) solve. Having the iterative version enables more flexibility in details, because everything is explicit. E.g., escaping at the end can be much faster, and patching around errors actually possible. Computer Science education loves to dwell on recursion far beyond its real-world usefulness, in part because CS professors carry a fondness for the Lisp of their youth, but also because arbitrarily complex problems that benefit from recursion are cheap to invent and easy to describe. In real life, recursion in any pure form rarely goes, usefully, more than three levels deep, but we like to make data structures that do. At ITA, they did airline trip computations that would naturally recurse on the number of stops, but no one wants more stops, and time spent on possible trips with more than two is almost always wasted. In a sense, recursion is like object-orientedness: an elegant pattern that fits many problems, but makes a poor basis for a world view or, exclusively, a language. Lisp and Smalltalk are not sidelined because of ignorance.
    - ZephyrP 5y ago
      > Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand". Recursion is required in procedures like Ackermann's Function [1]. You can still simulate or write functions that avoid the syntactic fact that the procedure definition refers (either directly or indirectly) to itself, but you'll always be papering over the fact that it cannot be implemented with a fixed number of state variables. [1] https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function
      - qsort 5y ago
        > Recursion is required to implement non-primitive recursive procedures This is very untrue. While loop and a stack. > cannot be implemented with a fixed number of state variables Of course it can't, any function outside DSPACE(O(1)) can't. The fact that you have an implicit call stack doesn't change the space complexity.
  - dunefox 5y ago
    If you don't get that then I have bad news for you: it's a powerful technique that oftentimes makes code shorter, more elegant, and improves readability.
  - Jtsummers 5y ago
    Like any other tool? If it's useful, use it, if it's not, don't. In many graph problems and parsing problems, it's useful, because it lets you express your solution more "naturally" with respect to the underlying domain. That's where I've used it seriously.
Joker_vD 5y ago
Mmm, I remember doing this, with select(3) for maximum portability and all... then learning that neither Linux nor Windows actually follow what POSIX says select(3) should do, e.g. how to report a socket with non-blocking connect(3) operation when it finally fails to connect: it should be reported as readable (reading from it would fail immediately and would not block), writeable (same reason), having exceptional condition pending (it has a pending error). Nope, Linux reports it as readable/writeable but not having exceptional condition, while Windows reports it as only having exceptional condition pending but not as readable nor writeable. Beautiful, just beautiful. In the end you have to put sockets in such scenarios into all three sets and check what getsockopt(s, SOL_SOCKET, SO_ERROR) returns for them, that's the portable way.

ncmncm 5y ago

I suspect the earlier puzzles were most of the better ones. What I sent in was the Add-a-gram (on that page, stashed behind the "Puzzle Archive" link). I sent one solution, and when they called, they admitted others were faster, so I redid it that evening ten times faster and sent that. What they never told me, even after I had been there for years, was that my second solution was faster than theirs or any others they had on file. It looks like they retired it right after I started there, maybe because I had shown it didn't actually require backtracking, which they were trying to filter for–ITA was mostly a Lisp shop, so they wanted people who would always reach for recursion first. My solutions were relentlessly iterative. Some years after I left ITA, they posted the Bitvectors puzzle, which I had to solve, in a fever, but never sent off. (At the time I think it had a different name.) That solution also didn't require backtracking.

hoseja 5y ago
I just don't get how anyone can use recursion for anything serious. Especially when it can always be unrolled into a more comprehensible / representative of what's actually happening iteration.
- KineticLensman 5y ago
  If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient. [0] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
  - ncmncm 5y ago
    I.e., the compiler converts the recursive code you wrote into the iterative form you could have written, and runs that instead because it's faster.
    - Jtsummers 5y ago
      I find this argument interesting because, to me, it leads to endorsing a view that we should be using goto and conditional jumps instead of for/while loops and similar structured programming elements. I mean, the former are more explicit, the latter implicit, since the compiler converts the latter into the former. Having maintained a fair amount of unstructured code, I'd rather stick with the higher level languages since they allow me to express my intent more clearly. Which pushes me to using recursion where it's appropriate and the language has appropriate facilities to handle tail call elimination.
      - ncmncm 5y ago
        We make languages and compilers the way we do for reasons. But it is a mistake to confuse what automation hides from you, for practical reasons, with fundamental qualities of the universe or of computation. Another common example of the error is describing an algorithm as N log N, assuming that the numbers involved occupy constant space and multiply in constant time. In real-world computation, space tends to log N, and multiply in close to (log N)^2 time and power consumption. We get away with it for the same reason recursion works: the problems we apply our algorithms to usually fit in conveniently constrained space, and our multiplier hardware takes the same time and power for small numbers as for the biggest ones we can conveniently represent.
- ChrisLomont 5y ago
  Lots of problems have vastly simpler recursive solutions. Try putting a recursive descent parser into a loop. Plenty of tree walking/formatting/analyzing algorithms are much cleaner using recursion. Recursively walking directory structures is cleaner using recursion. Many puzzles, such as Tower of Hanoi, are cleaner with recursion. Many sort algorithms, like merge sort, quicksort, etc., are cleaner with recursion. I could find plenty more algorithms where recursion makes the solution cleaner, simpler (hence less error prone), and sometimes even faster to execute. And some algorithms use mutual recursion to solve problems - often putting those into a non-recursive formulation results in incredibly messy code. Mutual recursion is powerful enough that F# (among others) added an entire keyword to the language simply to support it. And since many languages do proper tail recursion, there is no penalty for using it properly.
  - ncmncm 5y ago
    In CS, you encounter lots of problems that are naturally solved by recursion not because such problems are especially common, but because they are favorites of CS professors. Language parsers do a lot of recursion because the languages we invent are invented by CS people who like problems that can be solved that way, and because language itself is one that lends itself to that. It is hard to tease out which recursions we find because professors just like it, and which ones real-world problems demand. Many commonly cited as the latter turn out, on close examination, to be the former.
    - titzer 5y ago
      > but because they are favorites of CS professors. I work on compilers and compilers are full of graphs. Graphs typically have a lot of algorithms that are naturally recursive. It's not because of some theoretical fetish.
      - ncmncm 5y ago
        But CS professors love graph problems. So, it's not so easy to say.
    - 5y ago
- anonymoushn 5y ago
  Which would you prefer? def msort(xs, lo=None, hi=None): if lo is None: lo = 0 hi = len(xs) if hi-lo < 2: return mid = lo + (hi-lo) // 2 msort(xs, lo, mid) msort(xs, mid, hi) merge(xs, lo, mid, hi) def msort(xs): s = [[0, len(xs) // 2, len(xs), "step 1"]] while s: lo, mid, hi, step = xs[-1] if step == "step 1": if hi-lo < 2: s.pop() else: s[-1][3] = "step 2" s.append([lo, lo + (mid-lo) // 2, mid, "step 1"]) elif step == "step 2": s[-1][3] = "step 3" s.append([mid, mid + (hi-mid) // 2, hi, "step 1"]) else: s.pop() merge(xs, lo, mid, hi)
  - qsort 5y ago
    The one that doesn't blow up the stack.
- Joker_vD 5y ago
  Okay, here's the very recent problem I had to solve. There is a huge dump of a VM heap, represented as a key-value map: the values are either simple atomic values or compound structures that have addresses (keys into this map) as their parts. There is a list of "entry points" into the heap: addresses of the GC roots in the heap. The problem is to reconstruct the values stored in the heap. E.g., reconstructing starting from "heap(10)" in this heap: heap(10): cons(int(1),heap(18)) heap(18): cons(int(2),heap(20)) heap(20): cons(int(3),nil) should result in [1, 2, 3] Here's the thing: recursive walk is totally straightforward: def restore(v): if v.kind... elif v.kind == 'tuple': return Tuple([restore(v[i]) for i in range(v.arity)]) elif v.kind == 'cons': return List(restore(v[0]), restore(v[1])) elif v.kind... else: return UnknownValue() But since Python has a limit of 1000 nested function calls, restoration of long lists fails with StackOverflow, and so I had to rewrite it using manual stack. The result is sort of ugly, in fact, I had to use two stacks: one for temporary reconstructed pieces of data, one for "what to do next". Essentially it's implementing a variation of the shunting yard algorithm and while the resulting code is kinda clear in intent, it's still three times as long as the recursive version and is not obviously correct. In fact, I had to tweak it several times (including the introduction of the second stack) before I stopped seeing some (not all!) lists reconstructed in the reverse order.
- martincmartin 5y ago
  Because you get a stack for free. It's very natural for depth first search of a tree.
  - ncmncm 5y ago
    Unpleasant fact best learned early: the stack is not free. The "very natural" appearance is an artifact of the languages we have (very unnaturally) constructed.
    - titzer 5y ago
      The machine stack given by modern CPUs is blazingly fast, because microarchitectures typically have a return stack buffer that allows the processor to perfectly branch-predict returns. Manually coding recursive algorithms means you have to switch over the return state, which involves a different predictor that will be less accurate. Given that, and machines typically have an architectural stack pointer register with dedicated instructions to push and pop to it, the manual datastructure you come up with to simulate a stack is almost certainly going to be slower.
      - ncmncm 5y ago
        It is always an error to assume you know which of any architectural alternatives will be faster. You have to measure, if it matters.
        titzer 5y ago
        Please do. This is my prediction based on years and years of optimizing machine code and measuring on recent microarchitectures. I look forward to seeing your handwritten assembly proving your overgeneralized claims about recursion being inherently slower.
        ncmncm 5y ago
        I did not, in fact, claim that recursion is inherently slower than iteration. You are welcome to read what I did write, above. Usually it is considered better (hint, hint) to do that before replying.
- ncmncm 5y ago
  Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand". But the recursive code can be much shorter, and easier to understand, because our languages have built-in apparatus to support it. They didn't always; original FORTRAN could not do recursion, and used no stack. The stack isn't free at runtime, but it's pretty cheap, and its fatal failure mode is rarely encountered nowadays. In my work, I have always found the iterative version cleaner and faster, but that is an artifact of the kinds of problems I (and most people) solve. Having the iterative version enables more flexibility in details, because everything is explicit. E.g., escaping at the end can be much faster, and patching around errors actually possible. Computer Science education loves to dwell on recursion far beyond its real-world usefulness, in part because CS professors carry a fondness for the Lisp of their youth, but also because arbitrarily complex problems that benefit from recursion are cheap to invent and easy to describe. In real life, recursion in any pure form rarely goes, usefully, more than three levels deep, but we like to make data structures that do. At ITA, they did airline trip computations that would naturally recurse on the number of stops, but no one wants more stops, and time spent on possible trips with more than two is almost always wasted. In a sense, recursion is like object-orientedness: an elegant pattern that fits many problems, but makes a poor basis for a world view or, exclusively, a language. Lisp and Smalltalk are not sidelined because of ignorance.
  - ZephyrP 5y ago
    > Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand". Recursion is required in procedures like Ackermann's Function [1]. You can still simulate or write functions that avoid the syntactic fact that the procedure definition refers (either directly or indirectly) to itself, but you'll always be papering over the fact that it cannot be implemented with a fixed number of state variables. [1] https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function
    - qsort 5y ago
      > Recursion is required to implement non-primitive recursive procedures This is very untrue. While loop and a stack. > cannot be implemented with a fixed number of state variables Of course it can't, any function outside DSPACE(O(1)) can't. The fact that you have an implicit call stack doesn't change the space complexity.
- dunefox 5y ago
  If you don't get that then I have bad news for you: it's a powerful technique that oftentimes makes code shorter, more elegant, and improves readability.
- Jtsummers 5y ago
  Like any other tool? If it's useful, use it, if it's not, don't. In many graph problems and parsing problems, it's useful, because it lets you express your solution more "naturally" with respect to the underlying domain. That's where I've used it seriously.

Joker_vD 5y ago

Mmm, I remember doing this, with select(3) for maximum portability and all... then learning that neither Linux nor Windows actually follow what POSIX says select(3) should do, e.g. how to report a socket with non-blocking connect(3) operation when it finally fails to connect: it should be reported as readable (reading from it would fail immediately and would not block), writeable (same reason), having exceptional condition pending (it has a pending error). Nope, Linux reports it as readable/writeable but not having exceptional condition, while Windows reports it as only having exceptional condition pending but not as readable nor writeable. Beautiful, just beautiful. In the end you have to put sockets in such scenarios into all three sets and check what getsockopt(s, SOL_SOCKET, SO_ERROR) returns for them, that's the portable way.