• Activity
  • Votes
  • Comments
  • New
  • All activity
  • Showing only topics in ~comp with the tag "programming". Back to normal view / Search all groups
    1. Programming Q&A Thread

      An experiment I've been thinking about lately: a (recurring?) Q&A thread! Ask any questions about programming, answer other users' questions, or post suggestions for future threads. Don't forget...

      An experiment I've been thinking about lately: a (recurring?) Q&A thread! Ask any questions about programming, answer other users' questions, or post suggestions for future threads.

      Don't forget to format your code using the triple backticks or tildes:

      Here is my schema:
      
      ```sql
      CREATE TABLE article_to_warehouse (
        article_id   INTEGER
      , warehouse_id INTEGER
      )
      ;
      ```
      
      How do I add a `UNIQUE` constraint?
      

      Meta questions:

      • Should I turn this into a recurring thread?
      • If yes, should it be a weekly or a monthly thing?
      • Should DBA and SysAdmin questions be allowed or should someone else make a separate recurring thread for these?
      22 votes
    2. Programming Challenge: Convert between units

      Hi everyone! It's been a long time since last programming challenge list, and here's a nice one I've encountered. If you search for something like 7km to AU, you'll get your answer. But how is it...

      Hi everyone! It's been a long time since last programming challenge list, and here's a nice one I've encountered.

      If you search for something like 7km to AU, you'll get your answer. But how is it done? I don't think they hardcoded all 23 units of distance and every conversion factor between them.

      If you were programming a conversion system - how would you do it?

      First of all, you have input in format that you can specify, for example something like this:

      meter kilometer 1000
      mile kilometer 1.609344
      second minute 60
      ...
      

      Then you should be able answer queries. For example 7 mile meter should convert 7 miles to meters, which is 11265.41.

      Can you design an algorithm that will convert any unit into any other unit?

      Edit: Some conversion rates I extracted from wikipedia:

      ångström
      0.1nm
      astronomical unit
      149597870700m
      attometre
      0.000000000000000001m
      barleycorn
      8.4m
      bohr
      0.00846
      cable length (imperial)
      185.3184m
      cable length
      185.2m
      cable length (US)
      219.456m
      chain (Gunters)
      20.11684m
      cubit
      0.5m
      ell
      1.143m
      fathom
      1.8288m
      femtometre
      0.00000000000001m
      fermi
      0.00000000000001m
      finger
      0.022225m
      finger (cloth)
      0.1143m
      foot (Benoit)
      0.304799735m
      foot (Cape) (H)
      0.314858m
      foot (Clarke's) (H)
      0.3047972654m
      foot (Indian) (H)
      0.304799514m
      foot,metric
      0.31622776602m
      foot,metric (long)
      0.3m
      foot,metric (short)
      0.30m
      foot (International)
      0.3048m
      foot (Sear's) (H)
      0.30479947m
      foot (US Survey)
      0.304800610
      french
      0.0003m
      furlong
      201.168m
      hand
      0.1016m
      inch
      0.0254m
      league
      4828m
      light-day
      25902068371200m
      light-hour
      107925284880m
      light-minute
      17987547480
      light-second
      299792458m
      light-year
      31557600light-second
      line
      0.002116m
      link (Gunter's)
      0.2011684m
      link (Ramsden's; Engineer's)
      0.3048m
      metre
      1m
      m
      1metre
      km
      1000m
      mickey
      0.000127
      micrometre
      0.000001
      mil; thou
      0.0000254
      mil
      10km
      mile (geographical)
      6082foot (International)
      quarter
      0.2286m
      rod
      5.0292m
      rope
      6.096m
      shaku
      0.303 0303m
      span (H)
      0.2286m
      stick (H)
      0.0508m
      toise
      1.949 0363m
      twip
      1.76310
      yard
      0.9144m
      
      17 votes
    3. Typesetting Markdown Blog: What Next?

      Some of you have read the Typesetting Markdown blog series (https://dave.autonoma.ca/blog/). The plan was to finish the last two parts with Annotated Text (basically markup for Markdown) and...

      Some of you have read the Typesetting Markdown blog series (https://dave.autonoma.ca/blog/). The plan was to finish the last two parts with Annotated Text (basically markup for Markdown) and Figure Drawing (MetaPost); however, people have asked for a post on Markdown to EPUB, others have asked for high-quality PDF theme templates using ConTeXt, and some have requested rendering Markdown into HTML.

      Within the realm of Markdown, digital documentation, typesetting with ConTeXt, R, externalized interpolated strings, and bash scripting, what would interest you for the next post in the series?

      (Please flip through the blog series to see the topics that have been covered.)

      3 votes
    4. Which language would you pick to completely rewrite BSD, Linux, etc.?

      It'd my understanding that C has stuck around in the UNIX world for so long, nearly half a century, mostly due to the inertia of legacy code. If you could snap your fingers and magically port/fork...

      It'd my understanding that C has stuck around in the UNIX world for so long, nearly half a century, mostly due to the inertia of legacy code.

      If you could snap your fingers and magically port/fork the entire stack of open source codebases to the language of your choice, which would you pick and why?

      20 votes
    5. Topic Requests: What subject would you like to see covered in more depth?

      For those who haven't seen my essay-length posts in the past, I occasionally like to delve into explaining different programming concepts, particularly with regards to making your code easier to...

      For those who haven't seen my essay-length posts in the past, I occasionally like to delve into explaining different programming concepts, particularly with regards to making your code easier to manage. Sometimes this has to do with how you structure you code and projects, and at others it has to do with how you think about the problems you're solving. I've been in the mood to write up on yet another programming subject, but nothing in particular has stood out to me lately during the course of my work.

      With that in mind, I figured I would take a different approach and see if anyone here had some specific requests for content they would like to see. Requests from all levels of experience are welcome!

      (And for those who are itching to do a write-up on any of the requests that appear here, feel free to call dibs!)


      Edit

      For those who want to take a dive into my previous submissions, you can now find them in the new wiki entry created by @cfabbro or directly via the programming.code_quality_tips tag here.

      8 votes
    6. Code Quality Tip: The importance of understanding correctness vs. accuracy.

      Preface It's not uncommon for a written piece of code to be both brief and functionality correct, yet difficult to reason about. This is especially true of recursive algorithms, which can require...

      Preface

      It's not uncommon for a written piece of code to be both brief and functionality correct, yet difficult to reason about. This is especially true of recursive algorithms, which can require some amount of simulating the algorithm mentally (or on a whiteboard) on smaller problems to try to understand the underlying logic. The more you have to perform these manual simulations, the more difficult it becomes to track what exactly is going on at any stage of computation. It's also not uncommon that these algorithms can be made easier to reason about with relatively small changes, particularly in the way you conceptualize the solution to the problem. Our goal will be to take a brief tour into what these changes might look like and why they are effective at reducing our mental overhead.


      Background

      We will consider the case of the subset sum problem, which is essentially a special case of the knapsack problem where you have a finite number of each item and each item's value is equal to its weight. In short, the problem is summarized as one of the following:

      • Given a set of numbers, is there a subset whose sum is exactly equal to some target value?

      • Given a set of numbers, what is the subset whose sum is the closest to some target value without exceeding it?

      For example, given the set of numbers {1, 3, 3, 5} and a target value of 9, the answer for both of those questions is {1, 3, 5} because the sum of those numbers is 9. For a target value of 10, however, the first question has no solution because no combination of numbers in the set {1, 3, 3, 5} produces a total of 10, but the second question produces a solution of {1, 3, 5} because 9 is the closest value to 10 that those numbers can produce without going over.


      A Greedy Example

      We'll stick to the much simpler case of finding an exact match to our target value so we don't have to track what the highest value found so far is. To make things even simpler, we'll consider the case where all numbers are positive, non-zero integers. This problem can be solved with some naive recursion--simply try all combinations until either a solution is found or all combinations have been exhausted. While more efficient solutions exist, naive recursion is the easiest to conceptualize.

      An initial assessment of the problem seems simple enough. Our solution is defined as the set of array elements whose total is equal to our target value. To achieve this, we loop through each of the elements in the array, try combinations with all of the remaining elements, and keep track of what the current total is so we can compare it to our target. If we find an exact match, we return an array containing the matching elements, otherwise we return nothing. This gives us something like the following:

      function subsetSum($target_sum, $values, $total = 0) {
          // Base case: a total exceeding our target sum is a failure.
          if($total > $target_sum) {
              return null;
          }
      
          // Base case: a total matching our target sum means we've found a match.
          if($total == $target_sum) {
              return array();
          }
      
          foreach($values as $index=>$value) {
              // Recursive case: try combining the current array element with the remaining elements.
              $result = subsetSum($target_sum, array_slice($values, $index + 1), $total + $value);
      
              if(!is_null($result)) {
                  return array_merge(array($value), $result);
              }
          }
      
          return null;
      }
      

      Your Scope is Leaking

      This solution works. It's functionally correct and will produce a valid result every single time. From a purely functional perspective, nothing is wrong with it at all; however, it's not easy to follow what's going on despite how short the code is. If we look closely, we can tell that there are a few major problems:

      • It's not obvious at first glance whether or not the programmer is expected to provide the third argument. While a default value is provided, it's not clear if this value is only a default that should be overridden or if the value should be left untouched. This ambiguity means relying on documentation to explain the intention of the third argument, which may still be ignored by an inattentive developer.

      • The base case where a failure occurs, i.e. when the accumulated total exceeds the target sum, occurs one stack frame further into the recursion than when the total has been incremented. This forces us to consider not only the current iteration of recursion, but one additional iteration deeper in order to track the flow of execution. Ideally an iteration of recursion should be conceptually isolated from any other, limiting our mental scope to only the current iteration.

      • We're propagating an accumulating total that starts from 0 and increments toward our target value, forcing us to to track two different values simultaneously. Ideally we would only track one value if possible. If we can manage that, then the ambiguity of the third argument will be eliminated along with the argument itself.

      Overall, the amount of code that the programmer needs to look at and the amount of branching they need to follow manually is excessive. The function is only 22 lines long, including whitespace and comments, and yet the amount of effort it takes to ensure you're understanding the flow of execution correctly is pretty significant. This is a pretty good indicator that we probably did something wrong. Something so simple and short shouldn't take so much effort to understand.


      Patching the Leak

      Now that we've assessed the problems, we can see that our original solution isn't going to cut it. We have a couple of ways we could approach fixing our function: we can either attempt to translate the abstract problems into tangible solutions or we can modify the way we've conceptualized the solution. With that in mind, let's take a second crack at this problem by trying the latter.

      We've tried taking a look at this problem from a top-down perspective: "given a target value, are there any elements that produce a sum exactly equal to it?" Clearly this perspective failed us. Instead, let's try flipping the equation: "given an array element, can it be summed with others to produce the target value?"

      This fundamentally changes the way we can think about the problem. Previously we were hung up on the idea of keeping track of the current total sum of the elements we've encountered so far, but that approach is incompatible with the way we're thinking of this problem now. Rather than incrementing a total, we now find ourselves having to do something entirely different: if we want to know if a given array element is part of the solution, we need to first subtract the element from the problem and find out if the smaller problem has a solution. That is, to find if the element 3 is part of the solution for the target sum of 8, then we're really asking if 3 + solutionFor(5) is valid.

      The new solution therefore involves looping over our array elements just as before, but this time we check if there is a solution for the target sum minus the current array element:

      function subsetSum($target_sum, $values) {
          // Base case: the solution to the target sum of 0 is the empty set.
          if($target_sum === 0) {
              return array();
          }
      
          foreach($values as $index=>$value) {
              // Base case: any element larger than our target sum cannot be part of the solution.
              if($value > $target_sum) {
                  continue;
              }
      
              // Recursive case: do the remaining elements create a solution for the sub-problem?
              $result = subsetSum($target_sum - $value, array_slice($values, $index + 1));
      
              if(!is_null($result)) {
                  return array_merge(array($value), $result);
              }
          }
      
          return null;
      }
      

      A Brief Review

      With the changes now in place, let's compare our two functions and, more importantly, compare our new function to the problems we assessed with the original. A few brief points:

      • Both functions are the same exact length, being only 22 lines long with the same number of comments and an identical amount of whitespace.

      • Both functions touch the same number of elements and produce the same output given the same input. Apart from a change in execution order of a base case, functionality is nearly identical.

      • The new function no longer requires thinking about the scope of next iteration of recursion to determine whether or not an array element is included in the result set. The base case for exceeding the target sum now occurs prior to recursion, keeping the scope of the value comparison nearest where those values are defined.

      • The new function no longer uses a third accumulator argument, reducing the number of values to be tracked and removing the issue of ambiguity with whether or not to include the third argument in top-level calls.

      • The new function is now defined in terms of finding the solutions to increasingly smaller target sums, making it easier to determine functional correctness.

      Considering all of the above, we can confidently state that the second function is easier to follow, easier to verify functional correctness for, and less confusing for anyone who needs to use it. Although the two functions are nearly identical, the second version is clearly and objectively better than the original. This is because despite both being functionally correct, the first function does a poor job at accurately defining the problem it's solving while the second function is clear and accurate in its definition.

      Correct code isn't necessarily accurate code. Anyone can write code that works, but writing code that accurately defines a problem can mean the difference between understanding what you're looking at, and being completely bewildered at how, or even why, your code works in the first place.


      Final Thoughts

      Accurately defining a problem in code isn't easy. Sometimes you'll get it right, but more often than not you'll get it wrong on the first go, and it's only after you've had some distance from you original solution that you realize that you should've done things differently. Despite that, understanding the difference between functional correctness and accuracy gives you the opportunity to watch for obvious inaccuracies and keep them to a minimum.

      In the end, even functionally correct, inaccurate code is worth more than no code at all. No amount of theory is a replacement for practical experience. The only way to get better is to mess up, assess why you messed up, and make things just a little bit better the next time around. Theory just makes that a little easier.

      17 votes
    7. Challenge: defuse this fork bomb

      On lobste.rs I found link to an article from Vidar Holen, the author of shellcheck. He made a fork bomb that is really interesting. Here's the bomb: DO NOT RUN THIS. eval $(echo...

      On lobste.rs I found link to an article from Vidar Holen, the author of shellcheck. He made a fork bomb that is really interesting. Here's the bomb:

      DO NOT RUN THIS.

      eval $(echo "I<RA('1E<W3t`rYWdl&r()(Y29j&r{,3Rl7Ig}&r{,T31wo});r`26<F]F;==" | uudecode)
      

      This may look pretty obvious, but it's harder than you think. I fell for it. twice. Can you find out how this bomb works?

      Warning: executing the bomb will slow down your computer and will force you to restart.
      You can limit impact of the fork bomb by setting FUNCNEST.

      export FUNCNEST=3
      

      Have fun!

      12 votes
    8. What are the minimal features every good blog should have?

      I've been learning Laravel, and familiarizing myself with the framework by coding up a blogging website. Right now, it's minimally functional, and I'd like to add some more features to it. Since...

      I've been learning Laravel, and familiarizing myself with the framework by coding up a blogging website. Right now, it's minimally functional, and I'd like to add some more features to it. Since this is my first project with Laravel the code is a mess, and it's just about time for me to rewrite the whole thing. Before starting that, I'd like to have a better idea of what my final product should be. I don't want to recreate WordPress in Laravel, but I do want to have something I wouldn't spit at. Basically a project that would be good as a resume builder if I ever needed one.

      So far, my website allows users to...

      • register for an account, log in/out, update their email address and display name
      • create posts with a WISIWYG editor
      • upload files
      • create profiles
      • and manipulate everything through CRUD.

      What do you think the minimal features a blogging platform needs to have to be "complete" and usable as a stand-alone system?

      13 votes
    9. Programming Challenge: Text compression

      In an effort to make these weekly, I present a new programming challenge. The challenge this week is to compress some text using a prefix code. Prefix codes associate each letter with a given bit...

      In an effort to make these weekly, I present a new programming challenge.

      The challenge this week is to compress some text using a prefix code. Prefix codes associate each letter with a given bit string, such that no encoded bitstring is the prefix of any other. These bit strings are then concatenated into one long integer which is separated into bytes for ease of reading. These bytes can be represented as hex values as well. The provided prefix encoding is as follows:

      char value char value
      ' ' 11 'e' 101
      't' 1001 'o' 10001
      'n' 10000 'a' 011
      's' 0101 'i' 01001
      'r' 01000 'h' 0011
      'd' 00101 'l' 001001
      '~' 001000 'u' 00011
      'c' 000101 'f' 000100
      'm' 000011 'p' 0000101
      'g' 0000100 'w' 0000011
      'b' 0000010 'y' 0000001
      'v' 00000001 'j' 000000001
      'k' 0000000001 'x' 00000000001
      'q' 000000000001 'z' 000000000000

      Challenge

      Your program should accept a lowercase string (including the ~ character), and should output the formatted compressed bit string in binary and hex. Your final byte should be 0 padded so that it has 8 bits as required. For your convenience, here is the above table in a text file for easy read-in.

      Example

      Here is an example:

      $> tildes ~comp
      10010100 10010010 01011010 10111001 00000010 11000100 00110000 10100000
      94 92 5A B9 02 C4 30 A0
      

      Bonuses

      1. Print the data compression ratio for a given compression, assuming the original input was encoded in 8 bit ASCII (one byte per character).
        2. Output the ASCII string corresponding to the encoded byte string in addition to the above outputs.
      2. @onyxleopard points out that many bytes won't actually be valid ASCII. Instead, do as they suggested and treat each byte as an ordinal value and print it as if encoded as UTF-8.
      3. An input prefixed by 'D' should be interpreted as an already compressed string using this encoding, and should be decompressed (by inverting the above procedure).

      Previous Challenges (I am aware of prior existing ones, but it is hard to collect them as they were irregular. Thus I list last week's challenge as 'Week 1')
      Week 1

      13 votes
    10. Programming Challenge: Dice Roller

      Its been a while since we did one of these, which is a shame. Create a program that takes is an input of the type: "d6 + 3" or "2d20 - 5", and return a valid roll. The result should display both...

      Its been a while since we did one of these, which is a shame.

      Create a program that takes is an input of the type: "d6 + 3" or "2d20 - 5", and return a valid roll.
      The result should display both the actual rolls as well as the final result. The program should accept any valid roll of the type 'xdx'
      Bonuses:

      • Multiplication "d6 * 3"
      • Division "d12 / 6"
      • Polish notation "4d6 * (5d4 - 3)"

      As a side note, it would be really cool if weekly programming challenges became a thing

      33 votes
    11. How do you structure larger projects?

      I'll be writing a relatively large piece of scientific code for the first time, and before I begin I would at least like to outline how the project will be structured so that I don't run into...

      I'll be writing a relatively large piece of scientific code for the first time, and before I begin I would at least like to outline how the project will be structured so that I don't run into headaches later on. The problem is, I don't have much experience structuring large projects. Up until now most of the code I have written as been in the form of python scripts that I string together to form an ad-hoc pipeline for analysis, or else C++ programs that are relatively self contained. My current project is much larger in scope. It will consist of four main 'modules' (I'm not sure if this is the correct term, apologies if not) each of which consist of a handful of .cpp and .h files. The schematic I have in mind for how it should look is something like:

      src
       ├──Module1 (Initializer)
       │         ├ file1.cpp
       │         ├ file1.h
       │         │...
       │         └ Makefile
       ├───Module2 (solver)
       │          ├ file1.cpp
       │          ├ file1.h
       │          │...
       │          └ Makefile
       ├───Module3 (Distribute)
       │          ├ file1.cpp
       │          └Makefile 
       └ Makefile
      

      Basically, I build each self-contained 'module', and use the object files produced there to build my main program. Is there anything I should keep in mind here, or is this basically how such a project should be structured?

      I imagine the particularly structure will be dependent on my project, but I am more interested in general principles to keep in mind.

      14 votes
    12. Do you enjoy programming outside of work?

      I have found this to be a semi controversial topic. Its almost becoming a required point for getting a new job to have open source work that you can show. Some people just enjoy working on...

      I have found this to be a semi controversial topic. Its almost becoming a required point for getting a new job to have open source work that you can show. Some people just enjoy working on programming side projects and others don't want to do any more after they leave the office.

      Whats your opinion on this? Do you work on any side projects? Do you think its reasonable for interviewers to look for open source work when hiring?

      16 votes
    13. Coding Challenge - Design network communication protocol

      Previous challenges It's time for another coding challenge! This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS. The task is to design a network...

      Previous challenges

      It's time for another coding challenge!

      This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS.

      The task is to design a network communication protocol. You're sending large amount of bits over the network. The problem is that network is not perfect and the message sometimes arrives corrupted. Design a network protocol, that will guarantee that the decoded message will be exactly same as the message that was encoded.

      MESSAGE => (encoding) => message corrupted => (decoding) => MESSAGE
      

      Corruption

      Transmitting the message might corrupt it and introduce errors. Each error in a message (there might be more than one error in a single message) will flip all following bits of the message.

      Example:

      011101 => 011|010
      

      (| is place where an error occured).

      There might be more than one error in a message, but there are some rules:

      • Minimum distance between two errors in a single message is k

      • Number of bits between two errors is always odd number

      According to these rules, describe a communication protocol, that will encode a message, and later decode message with errors.

      Bonus

      • Guarantee your protocol will work always - even when errors are as common as possible

      • Try to make the protocol as short as possible.

      8 votes
    14. Programming Challenge: Build an Interpreter

      Hello everyone! It has been a while since last programming challenge, it's time for another one! This week's goal would be to build your own interpreter. Interpreter is program that receives input...

      Hello everyone! It has been a while since last programming challenge, it's time for another one!

      This week's goal would be to build your own interpreter.

      Interpreter is program that receives input and executes it. For example Python is interpreted language, meaning you are actually writing instructions for the interpreter, which does the magic.

      Probably the easiest interpereter to write is Brainfuck interpreter. If someone here doesn't know, Brainfuck is programming language, which contains following instructions: ,.<>[]-+. Other characters are ignored. It has memory in form of array of integers. At the start, pointer that points to one specific memory cell points to cell 0. We can use < to move pointer to left (decrement) and > to move pointer to right (increment). . can be used to print value of cell the pointer is currently pointing to (ascii). , can be used to read one character from stdin and write it to memory. [ is beggining of loop and ] is end of loop. Loops can be nested. Loop is terminated when we reach ] character and current value in memory is equal to 0. - can be used to decrement value in memory by 1 and + can be used to increment value in memory by 1. Here's Hello World:

      ++++++++++[>+++++++>++++++++++>+++>+<<<<
      -]>++.>+.+++++++..+++.>++.<<++++++++++++
      +++.>.+++.------.--------.>+.>.
      

      People with nothing to do today can attemp to make an interpreter for the Taxi programming language.

      You can even make your own language! There are no limits for this challenge.

      23 votes