Dysfunctional Discourse

A salty-and-sweet melding of programming and sociology. All under one…kettle lid.

[dyscourse]

How did you get job in Stack Excahnge?

Back in 2012, David Fullerton (VP of Engineering) wrote me to ask if I was interested in working in the core Q&A team at Stack Exchange. At the time, I had recently renegotiated a very nice compensation package at On-Site and wasn’t ready to quit.Since then, I thought about Stack Exchange a lot (I’ve been in the Stack Overflow community for a long time, being userid 13), but couldn’t find the right opening to recommence the dialogue; it wasn’t like I was particularly looking for a change of scenery. It seemed almost too strange to say “oh hey, so, I’m wondering if you still have that job opening” if you’re not actively jobseeking, y’know?Anyway, two years on, Joel Spolsky wrote a blog post about [Trello spinning off as a separate company](http://www.joelonsoftware.com/items/2014/07/24.html), and how they’re opening up a bunch of jobs. I checked them out out of curiosity. The programming puzzle piqued my interest, and I wrote a 35-byte GolfScript solution and sent it to them. I wasn’t looking to formally apply or anything, but they wanted to interview me anyway.One of my interviewers used to work with David back at Fog Creek, and I mentioned about how he wanted to hire me back in 2012. That ended up in the interview notes, so during the CEO interview, Michael Pryor asked me why I hadn’t followed up with Stack Exchange again. (I now had the perfect opening to reopen the conversation: “Michael Pryor thought I should ping you again”. :-P)After six or so interviews, I got a job offer from Trello. So I had The Talk with my boss, and was ready to accept the Trello offer. But, sometime during my interview process, Trello added a new job requirement that I didn’t fulfil (“You’ve created significant projects using node.js”), so after discussing that with them, I no longer had a job offer.So I wrote David back, and the rest is history.(inb4: I had to do the interview process like everyone else. I wouldn’t want to work somewhere where people can be exempted from interviews!)

[dyscourse]

My solution for Sorted Set

This is a repost from my Dysfunctional Discourse Quora blog. The original post can be found at http://qr.ae/qgYz8.

In Quora Haqathon this year, there was a problem called Sorted Set. Since the contest had a generous week-long time limit, I thought I'd write a well-structured and polished solution. Here it is (also available on GitHub):

import java.io.DataInputStream; import java.io.DataOutputStream; import java.io.File; import java.io.IOException; import java.net.ServerSocket; import java.net.Socket; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.NavigableMap; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import java.util.concurrent.Callable; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; import java.util.concurrent.ExecutionException; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import org.newsclub.net.unix.AFUNIXServerSocket; import org.newsclub.net.unix.AFUNIXSocketAddress; public class Solution implements Runnable { private enum Method { ADD_SCORE(1) { @Override public int[] call(DataStore store, int... args) { store.addScore(args[0], args[1]); return new int[0]; } }, REMOVE_KEY(2) { @Override public int[] call(DataStore store, int... args) { store.removeKey(args[0]); return new int[0]; } }, GET_SIZE(3) { @Override public int[] call(DataStore store, int... args) { return new int[] {store.getSize()}; } }, GET_KEY_VALUE(4) { @Override public int[] call(DataStore store, int... args) { return new int[] {store.getKeyValue(args[0])}; } }, GET_RANGE(5) { @Override public int[] call(DataStore store, int... args) { return mapToArray(store.getRange(args[0], args[1])); } }; private final int cmd; Method(int cmd) { this.cmd = cmd; } public abstract int[] call(DataStore store, int... args); public static Method valueOf(int cmd) { for (Method method : values()) { if (cmd == method.cmd) return method; } return null; } } private enum Reducer { GET_RANGE(5) { @Override public int[] reduce(Collection<int[]> results) { Map<Integer, Set<Integer>> map = new TreeMap<>(); for (int[] result : results) { for (int i = 0; i < result.length; i += 2) { Set<Integer> set = map.get(result[i]); if (set == null) map.put(result[i], set = new TreeSet<>()); set.add(result[i + 1]); } } return mapToArray(map); } }; private final int cmd; Reducer(int cmd) { this.cmd = cmd; } public abstract int[] reduce(Collection<int[]> results); public static Reducer valueOf(int cmd) { for (Reducer reducer : values()) { if (cmd == reducer.cmd) return reducer; } return null; } } private static class DataStore { private final Map<Integer, Integer> fwd = new HashMap<>(); private final NavigableMap<Integer, Set<Integer>> rev = new TreeMap<>(); private void refreshScore(int key, Integer score, Integer old) { if (old != null) rev.get(old).remove(key); if (score != null) { Set<Integer> keys = rev.get(score); if (keys == null) rev.put(score, keys = new HashSet<>()); keys.add(key); } } public synchronized void addScore(int key, int score) { refreshScore(key, score, fwd.put(key, score)); } public synchronized void removeKey(int key) { refreshScore(key, null, fwd.remove(key)); } public synchronized int getSize() { return fwd.size(); } public synchronized int getKeyValue(int key) { Integer value = fwd.get(key); return value != null ? value : 0; } public synchronized NavigableMap<Integer, Integer> getRange(int lower, int upper) { NavigableMap<Integer, Integer> result = new TreeMap<>(); for (Map.Entry<Integer, Set<Integer>> entry : rev.subMap(lower, true, upper, true).entrySet()) { for (Integer key : entry.getValue()) result.put(key, entry.getKey()); } return result; } } private static final ConcurrentMap<Integer, DataStore> DATA_STORES = new ConcurrentHashMap<>(); private final Socket s; public Solution(Socket s) { this.s = s; } @Override public void run() { try (DataInputStream in = new DataInputStream(s.getInputStream()); DataOutputStream out = new DataOutputStream(s.getOutputStream())) { while (true) { int size = in.readInt(); int[] request = new int[size]; for (int i = 0; i < size; ++i) request[i] = in.readInt(); int[] response = dispatch(request); if (response == null) return; out.writeInt(response.length); for (int value : response) out.writeInt(value); } } catch (IOException e) { e.printStackTrace(); } } private static DataStore getDataStore(int set) { DataStore result = DATA_STORES.get(set); if (result != null) return result; synchronized (DATA_STORES) { result = DATA_STORES.get(set); if (result == null) DATA_STORES.put(set, result = new DataStore()); return result; } } private static int[] mapToArray(Map<Integer, ?> map) { int[] result = new int[map.size() * 2]; int i = -1; for (Map.Entry<Integer, ?> entry : map.entrySet()) { int key = entry.getKey(); Object value = entry.getValue(); if (value instanceof Integer) { result[++i] = key; result[++i] = (Integer) value; } else if (value instanceof Collection) { for (Object item : (Collection<?>) value) { result[++i] = key; result[++i] = (Integer) item; } } } return result; } private static int[] singleDispatch(Method method, int set, int[] args) { return method.call(getDataStore(set), args); } private static int[] multiDispatch(final Method method, Reducer reducer, int[] sets, final int[] args) { List<Callable<int[]>> callables = new ArrayList<>(); for (int set : sets) { final DataStore store = getDataStore(set); callables.add(new Callable<int[]>() { @Override public int[] call() { return method.call(store, args); } }); } ExecutorService executor = Executors.newCachedThreadPool(); List<int[]> results = new ArrayList<>(); try { for (Future<int[]> future : executor.invokeAll(callables)) results.add(future.get()); } catch (InterruptedException e) { Thread.currentThread().interrupt(); return null; } catch (ExecutionException e) { e.getCause().printStackTrace(); return null; } finally { executor.shutdown(); } return reducer.reduce(results); } private static int[] dispatch(int[] request) { int cmd = request[0]; Method method = Method.valueOf(cmd); if (method == null) return null; Reducer reducer = Reducer.valueOf(cmd); if (reducer == null) return singleDispatch(method, request[1], Arrays.copyOfRange(request, 2, request.length)); int i = 0; while (++i < request.length) { if (request[i] == 0) break; } return multiDispatch(method, reducer, Arrays.copyOfRange(request, 1, i), Arrays.copyOfRange(request, i + 1, request.length)); } public static void main(String[] args) throws IOException { ServerSocket ss = AFUNIXServerSocket.bindOn(new AFUNIXSocketAddress(new File("socket"))); while (true) new Thread(new Solution(ss.accept())).start(); } }

What I like about my solution is that it handles the single-set and multi-set request types uniformly, with full generality, and no hard-coded dispatching.

The code could be a lot simpler if Java 8 or Racket were options, but they weren't. (You could only choose C, C++, Java 7, Python 2, or Python 3.)

Comments welcome. :-D

[dyscourse]

Any advice for new programmers? Everyone says to find a project and work on one but I'm not creative and there is nothing I can think of doing.

I was originally going to answer by suggesting some open-source projects that you are likely to use daily (and thus find bugs in), and submit patches to, as a foothold to contributing more broadly. However, it can be hard to get into open-source development, [especially for women](http://geekfeminism.wikia.com/wiki/FLOSS).One idea that I think would be useful (someone should make a startup for this!) is a HowAboutWe-like service for matching up people who have compatible project interests. Then they can code something up together, and encourage each other to keep pace, like gym partners. (Who knows, this could be a kind of startup matchmaking if the people involved have any entrepreneurial tendency. :-))Would you be interested in a service like this? Do you know people who would be?

[dyscourse]

hello, I would just like to thank you for helping me on stack :) as a new programmer, and advice on how to get better, I am starting with java but am slowly gaining a passion for this :) good vibes

It's always my pleasure to help. I also recognise that Stack Overflow can be occasionally intimidating for new programmers, so if you need to, you can always reach me here, or on Quora (where you can specifically "ask to answer", that is, ask a specific user to answer a question).Especially Quora. I spend entirely too much time on it. :-PGood luck with your Java-learning journey! Always feel free to reach out. :-)

[dyscourse]

Don’t assume `argc >= 1`

This is a repost from my Dysfunctional Discourse Quora blog. The original post can be found at http://qr.ae/RGTvQ3.

For all the C and C++ coders out there, it's very important not to assume that argc >= 1. I see a lot of code out there that exhibit undefined behaviour when faced with argc == 0, and that ain't good.

Some years ago, I even submitted a patch for Boost.Program_options because it didn't handle argc == 0 correctly. :-)

Today, I was playing around with my argc == 0 testing program (more on this below) on my MacBook, and discovered that echo(1) on OS X (and its original source, FreeBSD) also does not handle it correctly. At best, it prints garbage. At worst…well, it works by mallocing an array of struct iovec (with the number of elements based on argc, with a minimum of 1), and then traversing from argv[1] onwards until it hits null, writing to successive elements of the iovec array each time. It doesn't check argc or the allocation size during this traversal. Oops!

In another recent example, Nala Ginrut posted a patch to Guile to avoid a segmentation fault when argc == 0: [PATCH] Check if argv[0] is NULL in scm_boot_guile to avoid segfault. There's no end to the fun that can be had with this. :-)

Thankfully, any programs that use gnulib's progname module are automatically protected, and in particular, echo(1) on GNU systems is protected. But that module is GPL, so only GPL-compatible projects can use it.

Although command-line shells generally won't let you execute a program with argc == 0, writing a program that will do so is extremely trivial:

#include <unistd.h> int main(int argc, char** argv) { if (argc >= 2) execlp(argv[1], 0); return 1; }

Please, use this program frequently and make sure your programs don't exhibit undefined behaviour with argc == 0!

[dyscourse]

su, the most useless Unix command

I once tweeted my stance on su:

With sudo -s and -i, su is officially useless. And to wean oldtimers off of it, I plan to ln -f /bin/halt /bin/su.

I still hold this stance, for Unix at least.[1] su serves pretty much no useful function at all, because most things you can do with it, you can do better with sudo and setuidgid.

For interactive switching of users, you can use sudo -s for a normal shell, or sudo -i for a login shell. Add a -u foobar to switch to user foobar instead of root.

For setting the user to run a daemon or some other process under when you're already root (e.g., if you're running a daemon in an init script or a service), setuidgid is simple and just works.

For me, seeing people use sudo su ... is akin to seeing code like if (foo) return true; else return false;. It makes me twitch every time. And there's still so many online resources out there that promulgate it! I think a reeducation campaign is in order. :-D

[1] I think su is still useful for rooted Android devices.

[dyscourse]

As of the latest version of Google Maps app (for Android, at least), you can finally set up your navigation to use metric! Yay!

[dyscourse]

Sometimes, less customisation is _not_ more

In recent years, there's a trend towards providing less and less customisation options in programs, with a view towards getting the defaults "right" in the first place. Unfortunately, there's a class of settings for which there is no single "right" answer, and customisation is necessary: locale-related settings.

I live in the US, but I'm a New Zealander and I resent having to use US customary units (yes, I have to convert all the road signs to metric in my head, and I'm used to it, but the less of it I have to do, the better, you know?). It really frustrates me that there's still no sane way to get Google Maps to use metric, and it's a key reason why I think the mainstream GPS navigation products still have a use. (Update: there now is, finally, a way to get Google Maps to use metric!)

Date formatting is another pitfall. My preferred date format is %d/%m/%Y %H:%M:%S or %Y-%m-%d %H:%M:%S (where %H is the 24-hour hour counter, for people unfamiliar with strftime format strings), yet some apps (like HipChat) likes to enforce the use of 12-hour time everywhere, even when my phone's locale settings is explicitly set to use 24-hour time only (as you may have noticed from the numerous phone screenshots on this blog).

The Amazon MP3 Android app looks at your language settings to decide which country you're in. This is really silly, because I use UK English for UI† (yes, I'd really much rather see -ise rather than -ize, and colour instead of color, and enrol instead of enroll, etc.), but I live in the US and have US credit cards, and so need to purchase everything from US Amazon.

Really, these kinds of settings are not as trivial as whether trimURLs is enabled (though it does irk me that Chrome doesn't offer a way to turn that off). There is serious usability impact, for people who don't use the same units (or date/time formats) as "most people in the US". Imagine what response I'd get if I wrote a program that only used %Y-%m-%d %H:%M:%S timestamps and metric units, in the name of "sane defaults for the majority of the (English-speaking) world".

Yes, I get that i18n is not a priority for many early-stage products. But seriously, Google Maps is by no means an early-stage product, and it is used by people all over the world. So frankly, I am surprised that they still haven't got with the programme yet.

† I really would prefer to use NZ English for UI, though, since I still primarily use $ rather than £. I wish more programs offered that option.

[dyscourse]

My favourite Scheme feature: named `let`

Recently, on Stack Overflow, there was a discussion on what named let was all about, so I thought I'd write a post on the topic.

What's a named let?

So, let's consider a function for merging two sorted lists of numbers (since I felt that factorial or fibonacci were way overused as examples of self-recursive functions):

(define (merge lhs rhs) (cond ((null? lhs) rhs) ((null? rhs) lhs) ((< (car rhs) (car lhs)) (cons (car rhs) (merge lhs (cdr rhs)))) (else (cons (car lhs) (merge (cdr lhs) rhs)))))

This is fine and good, but some people look at this and say, OMG, this isn't tail-recursive, so if given long lists, it'll blow the stack! Okay, fine. Let's write a tail-recursive version:

(define (merge lhs rhs) (define (loop result lhs rhs) (cond ((null? lhs) (append-reverse! result rhs)) ((null? rhs) (append-reverse! result lhs)) ((< (car rhs) (car lhs)) (loop (cons (car rhs) result) lhs (cdr rhs))) (else (loop (cons (car lhs) result) (cdr lhs) rhs)))) (loop '() lhs rhs))

This is also fine, but now you had to write an inner function. And of course, whenever you're creating a function for the express purpose of immediately calling it, guess what the answer is? :-)

(define (merge lhs rhs) (let loop ((result '()) (lhs lhs) (rhs rhs)) (cond ((null? lhs) (append-reverse! result rhs)) ((null? rhs) (append-reverse! result lhs)) ((< (car rhs) (car lhs)) (loop (cons (car rhs) result) lhs (cdr rhs))) (else (loop (cons (car lhs) result) (cdr lhs) rhs)))))

That is what a named let is.

How do you define named let?

Many Scheme implementations implement let as a macro that creates a lambda and calls it, rather than as a built-in.

An unnamed let is easy to implement:

(define-syntax let (syntax-rules () ((let ((id value) ...) body ...) ((lambda (id ...) body ...) value ...))))

A named let is similarly easy; the lambda is simply wrapped in a rec:

(define-syntax let (syntax-rules () ((let tag ((id value) ...) body ...) ((rec tag (lambda (id ...) body ...)) value ...))))

All the rec does here is to give the lambda a name that can be used within the lambda for self-recursive calls.

But what is rec?

rec is a macro that wraps up a letrec (or an internal definition) in a pretty way. You can implement it in terms of either letrec:

(define-syntax rec (syntax-rules () ((rec name value) (letrec ((name value)) name))))

or an internal definition:

(define-syntax rec (syntax-rules () ((rec name value) (let () (define name value) name))))

In fact, in Scheme implementations where letrec is implemented as a macro on top of internal definitions (or the other way around), the two may well expand to identical code.

rec also provides syntactic sugar for defining a recursive function, much like define does:

(define-syntax rec (syntax-rules () ((rec (name . args) body ...) (rec name (lambda args body ...)))))

Putting it all together

(define-syntax rec (syntax-rules () ((rec (name . args) body ...) (rec name (lambda args body ...))) ((rec name value) (letrec ((name value)) name)))) (define-syntax let (syntax-rules () ((let ((id value) ...) body ...) ((lambda (id ...) body ...) value ...)) ((let tag ((id value) ...) body ...) ((rec (tag id ...) body ...) value ...))))

[dyscourse]

How to use Dvorak or Colemak on Ice Cream Sandwich (Android 4.0)

Recently, Google released the Google Keyboard app, which provides all the functionality of the built-in keyboard from Jelly Bean. So, just install that app, then follow the instructions I wrote for Jelly Bean. It's as simple as that!

Here's a screenshot of my Nook HD+ using the Dvorak layout:

[dyscourse]

Bullseye (Google Code Jam 2013, round 1A, problem A)

I only solved one problem in GCJ 2013 round 1A, and that's problem A, Bullseye. I really liked my solution to this problem (written in Racket):

(define (rings r t) (quotient (- (integer-sqrt (+ (* 4 r r) (* -4 r) (* 8 t) 1)) r r -1) 4))

Is the problem really that simple? Why, yes! It's much simpler than many other entries I've seen, so I wanted to explain my solution approach.

So, let's look at the problem step by step:

You are given t units of paint, and each unit of paint fills in a circle of radius 1.

This means that it takes 4 units of paint to fill in a circle of radius 2, 9 units for radius 3, etc., and generally, n² units to fill in a circle of radius n.

For a black ring with inner boundary r, and outer boundary r + 1, the total units used is, thus, (r + 1)² - r², or fully expanded as 2r + 1.

The next black ring has inner boundary r + 2, and outer boundary r + 3. More generally, for ring i, the inner boundary is r + 2i - 2, and the outer boundary is r + 2i - 1.

The total paint used for the first k rings is thus (2r + 1) + (2r + 5) + (2r + 9) + … + (2r + 4k - 3).

This is the same as k(2r - 3) + 4(1 + 2 + … + k), or in other words, k(2r - 3) + 2k(k + 1), which then becomes 2k² + (2r - 1)k.

You want to find the largest k is that satisfies 2k² + (2r - 1)k ≤ t, or in other words, 2k² + (2r - 1)k - t ≤ 0.

Solving this is easy: just use the quadratic formula! In this case, the factors used are a = 2, b = 2r - 1, and c = -t. Plugging this into the quadratic formula gives ((1 - 2r) ± sqrt((2r - 1)² + 8t)) / 4.

We only care about the positive (you can't have a negative number of rings), so this simplifies to (sqrt(4r² - 4r + 8t + 1) - 2r + 1) / 4, which is almost exactly the code you see.

Finally, we are asked to disregard partial rings, so we simply floor the result. Done.

[dyscourse]

why haven't you set your tag as "ruby on rails" or "rails" but only "ruby" on SO? Anything interesting ?

On [SO](http://stackoverflow.com/users/13), or [SO Careers](http://careers.stackoverflow.com/cky)? To me, I'm interested in Ruby the language. I use Rails at work, but I don't have a special interest in it; it's just another framework (albeit a very popular one).

[dyscourse]

what's your name?

My name is [Chris Jester-Young](http://about.me/cky). You can also find this by clicking "About me" on the site. :-)

[dyscourse]

Whoa, people really keep their work code after leaving?

Apparently, I just read that [some people actually keep their work code after they leave a company](http://programmers.stackexchange.com/q/154155/5167). Really?! Maybe because I'm so gung-ho about copyright, I would never consider such a thing. Even having read that thread, I still would never consider such a thing. When I quit a job, I do not retain work code for any purpose. If I had any work code on my personal machine, I would wipe the machine clean before moving on. My personal sense of ethics would not permit otherwise. I've written some stuff for work that I would consider pretty technically impressive. But the past is the past; I know that I will write even better things in future. Tomorrow is another day.

[dyscourse]

Hey, this is Patrick, the red-neck from Datomic yesterday, where did you take your mensa exam? Not important that you answer. Just saying hey. You are an interesting dude.

Hi Patrick! Wow, sorry for the late reply! I haven't checked my Tumblr inbox for a long time, it seems.I took my Mensa exam in Auckland, back in September 2004. Things may or may not have changed since then. You should definitely take the exam, though! It's fun. :-)

[dyscourse]

How to use Dvorak or Colemak on Jelly Bean (Android 4.1)

Prior to Jelly Bean, if you wanted to type on your Android device using Dvorak or Colemak, you'd have to use a third-party keyboard app. (My favourite is [SwiftKey](http://www.swiftkey.net/), by the way.) But from Jelly Bean onwards, Dvorak and Colemak support is built in! No more third-party apps required! Here's how: 1. Hold down the comma key, then select "Android keyboard settings".  1. Scroll to the bottom and choose "Advanced settings", then "Custom input styles". (On factory default settings, the German QWERTY and French QWERTZ layouts are already present. You can remove them, of course.) Choose "Add style".  1. Choose your desired language and layout, then add it.  1. You'll now be prompted to enable it.  1. Untick the "Use system language" box, then tick the Dvorak or Colemak layout that you've chosen. Finally, you may also wish to untick the QWERTY layout if you never use it.  1. That's it! Your shiny new Dvorak or Colemak layout is ready for you to use. 

[dyscourse]

How to use XTS encryption on Debian and Ubuntu

In [the last post](http://dyscour.se/post/21917863829/whole-disk-encryption-in-debian-ubuntu), I showed how to set up disk encryption in CBC-ESSIV mode in Debian and Ubuntu. This mode was used by default because [`partman-crypto` did not support LRW and XTS modes](http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=482092). Now, I'll show how to make it use XTS instead, which is more secure. First, get to this screen:  Then, load the XTS kernel module. A big hassle here is that the installer `.udeb`s do not contain the requisite `xts` module (and its dependency `gf128mul`). That means we have to extract this by hand (press Alt-F2 to get to a console, and Alt-F1 to return to the installer): mkdir -p /tmp/linux cd /tmp/linux ar x /cdrom/pool/main/l/linux/linux-image-*.deb tar xjf data.tar.bz2 (You can't use `udpkg --unpack` for this, since it doesn't support bzip2 archives.) Now, we can go and load those modules: cd lib/modules/*/kernel/crypto insmod gf128mul.ko insmod xts.ko --- Now that the module is loaded, we can then perform the `partman` tweaks: cd $(dirname /var/lib/partman/devices/=dev=sda/*/ivalgorithm) echo xts-plain > ivalgorithm echo 256 > keysize (For XTS, keysize 256 means AES-128; you can also use 384 for AES-192 and 512 for AES-256.) If you did everything right, then when you leave that crypto selection screen and come back to it, you should see this: