00:00:12.799
Hello RubyConf! I'm so glad to have this opportunity to present to you. Today, I'm going to talk about golf scripting with Ruby and how I help Santa schedule Christmas.
00:00:18.240
I hope you all enjoy my talk. A little bit about me: I'm a technology fan who has been working in the technology world for more than 20 years in different capacities as a system administrator, developer, tech lead, engineering manager, and project manager.
00:00:27.519
Right now, I'm working at Smile, helping build the loyalty layer for the internet. If you're interested, we're always hiring Ruby developers.
00:00:48.960
You all know Santa, right? I know that many of you are not yet thinking about Christmas; however, a project that big is not planned just one day in advance. In fact, right now at the North Pole, they are in the final phase of gift production and are almost done scheduling their delivery. Despite what you see in movies, it's not Santa himself who delivers the presents; he gets help from the elves, as you well know. Good kids get presents, while naughty kids get coal.
00:01:14.799
Now, I have worked in automated elections for a long time, and like in elections, Christmas is a project that must be planned well in advance, yet executed without failure in just one day. Maybe my experience is the reason why Santa asked for my help with the problem he faces.
00:01:27.680
For reasons that I cannot disclose due to nondisclosure agreements, even at the North Pole, the elves do not spend time traveling between Santa's sleigh and houses, and neither does Santa himself spend time moving from house to house.
00:01:38.320
It takes two hours and four seconds to deliver each present, and since coal is heavier and more dangerous to handle, three elves take five seconds to deliver each lump of coal. Presents have to be delivered to one house at a time, and the elves must return to the sleigh to collect the next gift before proceeding to the next house. "We leave no elf behind" is the motto of the elf squad.
00:01:59.200
So, that's the situation, and Santa needed help with an algorithm to determine the maximum amount of time that a fixed number of elves can take delivering presents, given a map of houses with the number of naughty and good kids in each.
00:02:27.040
Again, for reasons I can't disclose, the code has to be written in a very peculiar way to run in Santa's quantum mainframes. Santa's quantum computers need very short fragments of code to run efficiently, instead of what we usually think of as efficient code—they need to be written using golf scripting.
00:02:35.040
When I mention golf, this might not be what you all are thinking. It's not that class of golf; it looks more like this: sitting in front of a computer solving a problem like we do every day, or at least most of you probably do.
00:02:50.800
Now, what is golf scripting? It's basically a type of puzzle programming competition with the goal of implementing an algorithm in the shortest possible source code. As for the problem you are trying to solve, let's call it the scheduling problem.
00:03:06.159
Let's take a look at the first example. We have a house where we need to deliver one lump of coal and one present, and we have three elves. Now, I'm a visual guy, so I'm going to make a chart to see how long it takes to deliver the present and the coal. It takes three hours and five seconds to deliver the coal and two hours and four seconds to deliver the present, so the last amount of time will be nine seconds.
00:03:28.640
Let's try an example that is a little more elaborate. We have a house where we need to deliver four presents and one lump of coal. There's always a black sheep in the family, right? We have five elves to perform this delivery. How will our chart look? We'll deliver a present, then coal, and then the rest of the presents. No matter how we rearrange the order of delivery, the minimum amount of time it will take us will be 12 seconds. It could take us longer, depending on if we do it in a different order, but it will never take less than 12 seconds.
00:04:01.440
Well, it turns out that this problem is a well-studied problem in computer science called the bin packing problem. In our case, it is specifically related to orthogonal packing in two dimensions, which refers to problems of packing an arbitrary collection of rectangular pieces into an open-ended rectangular bin in such a way as to minimize the height achieved by any piece. For Santa, this problem represents the list of blocks, which are determined by the number of naughty and good kids in the house and the time it takes the elves to deliver the gifts.
00:04:44.840
When the paper talks about minimizing the height, the equivalent for us is minimizing the time it takes to deliver the presents. The constraints are the same as in our problem: it needs to be disjoint, meaning an elf cannot deliver both a present and coal at the same time, and also orthogonal and oriented, as we can't rotate the blocks. It takes two elves four seconds to deliver a present, but that doesn't mean that we can use four elves to take two seconds.
00:05:05.760
Now the funny thing is that when I got to this part, the only thing I could read was 'NP complete', and in my mind, that meant it was just hard. Luckily for me, they later offered some light at the end of the tunnel. Thank God for academics! What would we do without them? So, no matter how much they know, they haven't yet figured out how to write for normal humans.
00:05:57.120
Anyway, now we have our problem clear: it’s a two-dimensional bin packing problem that can be solved using a bottom-up left-justified algorithm. Now, I solved the problem using normal Ruby code, and I'm going to show you how to golf it.
00:06:17.040
Here we have the complete solution for Santa's problem. This code is around four kilobytes, and by the end of this session, we are going to reduce it to 400 bytes. To the left of the screen, we have two things: the result of the test running for this test and also the size of the script. Anytime I save the file, that will be updated.
00:06:32.000
Now, the first thing I do when trying to golf some code is look for pieces of code that are optimizing it, but that could be replaced by brute force implementations. In our case, here we have these unique permutations for an array method, which is adapted from an algorithm by Professor Donald Knuth. This method is incredibly elegant; it might not be idiomatic Ruby, but you can see the brilliance of Professor Knuth all through it.
00:07:02.880
Anyway, it is still 25 lines long, and because we are focusing on reducing the code size and not its efficiency, we can change it completely by using the built-in array permutation method. So, let’s do that! Granted, we will get all permutations and not just the unique ones, which will add a few cycles, but that's not our aim.
00:07:43.360
Now if we have methods like this beam pack max height method that we are calling only once, we can get rid of the method calling and the method definition by inlining them. In our case, this added 100 bytes to the script size, but that is because of indentation. If you were using tabs, it would have been half of it, but we are going to deal with the spaces later.
00:08:29.120
So now I'm going to make up for adding all of those indentation lines and I'm going to remove the empty lines. Who needs comments anyway? This is kind of one of the easiest ways to reduce the file size, so let's get rid of any lines under 'first return', and oops!
00:09:07.200
Now, let's get rid of all the comments. We can also remove all characters till the end of the line and carry that return. Let's try again—to start the line, we have spaces, then one sign for the inner character, and then times the end of the line for the first return.
00:09:56.280
There it is! And we're already down to almost 2 kilobytes. Now, if I were a politician, 50% of progress on my promise would put me in the top 1%, but let's keep moving. I can also rename all the variables in our code to use only one-character names. This will definitely save me a lot of bytes, but it's not as easy as it sounds.
00:10:52.960
It's actually a lot of work if you have many variables and don’t want any scope collisions with the names. This can sometimes take a lot of time, so that’s why, through the magic of git, I'm going to check out my code directly to that stuff.
00:12:13.960
Changing everything to one-character variable names. Let's see that in some parts of the code. Using semantic variable names forces us to split our code across multiple lines, while these lines were just one statement or multiple statements that could be shortened to just one line. I can save some bytes by removing those unnecessary character returns, which will also help fit more code on screen so you can all see it better.
00:13:34.080
This was one statement, as was this one, and it's asking to fit in one line. Looking at the code as it is, we can also notice that there are a few variables that are only used to store intermediate results. For example, "h" here on line 2, which is only used on line 3.
00:15:01.360
We can get rid of it. We also have "b," which is only used to calculate "o," which is used to calculate "f," which is only used to find the minimum. So, we can eliminate all of them if we just change the calls.
00:16:22.080
Now, "g" here can also be removed. If we look at what this code is doing, it’s remapping to use the size of our blocks instead of the zeros and ones in the array in which the permutations were created.
00:16:53.760
If we use directly the size of the blocks when creating the permutations, we can eliminate this map. Now we also have "d" here, and "a" here, which is only used to calculate "d," but we can get rid of the intermediate variables.
00:17:57.520
One of the other things I can do is change all of the two end blocks by opening and closing brackets, since two bytes for an opening and closing bracket is fewer than five bytes required for two end statements. I can also change the end for method definitions if I replace it with a lambda, especially if I use the stabilizer syntax. Who needs names for functions, right?
00:19:15.920
I’m almost running out of easy optimizations and quick gains, but looking at the code here, we can see that "r" and "l" both are calculated by iterating over "c" and I can save a few bytes if I merge both iterations into one. The caveat here is that I will need to return a pair of values.
00:20:34.080
The will need to be returned from the block and used, but I'm pretty sure this will reduce the size of the code. This talk is recorded, so I'm 100% sure. Let's do that; let's move this line here and initialize it.
00:21:58.560
Now we can say that in general the Ruby standard library method names are terse and succinct; they don't tend to be long names, though there are always some exceptions, of course. And I'm looking at you, verify transient heap internal consistency.
00:22:57.000
However, the longest Ruby methods here in this code are permutation with index and reverse. There is no shorter alternative to permutation, but using it saves us a bunch of bytes. However, there is something I can probably do about the other two.
00:23:57.680
Let's start with 'with index'; that's a hoping 10 bytes—what a waste! That isn’t even counting that we have to add an additional argument for the index in the blocks. There are so many bytes on it that we can save characters by not using it and incrementing the counter ourselves.
00:25:13.920
Let’s do that and also remove the manual increment here, and in this case, I can get rid of each with index.
00:25:41.440
You will have to trust me on this one, but I can change it. Well, you don’t have to take my word for it; you can see it as passing.
00:26:59.760
Now, because I'm incrementing 'i' here, I can probably also use this to get rid of this one. Now on lines four and five, assigning zeros to the default values for 'n' and 'g' in case they are not assigned on line three, I can save some bytes if I assign those defaults directly from the map string.
00:28:02.880
We can leverage the fact that assigning variables from an array discards the excess values. On line five, I'm calling next, but the same result can be achieved if a default value of 0 is returned from the following block.
00:29:05.280
Let’s do that! Now I'm in the business of altering loops; I can also take a look at this.
00:29:57.920
Instead of breaking, I can do nothing or nil, which is about as close to doing nothing as you can get in Ruby, or 'p,' which returns nil when called without arguments. Be careful when doing this—you cannot remove all of your breaks, but this just happens to work for this particular algorithm.
00:30:57.760
I can also replace all instances of 'each' with 'map' and save one byte, each time I should say 'map.' Both of them are iterators and are completely equivalent if not using the wrestle, except for those picky code reviewers.
00:32:28.320
Let’s do that: each by map! There it is, three less bytes. On line three, we have one character in one character string; I can save one byte by using this little-known grouping syntax for one character strings.
00:34:24.560
On line 21, we can eliminate these parentheses using some algebra and changing the sign. Now, I've been promising to deal with all of those whitespace, and no, this doesn't involve any tabs. It's time to finally do it! Who needs whitespace anyway? Well, turns out we do need some weighted spaces to avoid confusing the parser.
00:36:14.560
We have to add a space here in our ternary operator, and also, what is def? I don't know, and the parser won't either.
00:37:18.320
But that wasn't so bad; we only needed four white spaces after all! It turns out that we also don't need new lines in some cases. Every block, including pipes, can be joined with the next line, and we also don't need to keep block ends by themselves.
00:38:53.680
Let’s join lines one, two, and three; then three and four; and four and five; lines six and seven; and all these block ends can be joined on one line.
00:40:40.160
Now this is as far as I can get: 392 bytes. This is even better than the 400 bytes I promised at the beginning.
00:41:08.960
The truth is that every time I prepare this talk, I manage to shave off a few additional bytes. Maybe if you try it, you can probably improve my solution, but I still have some work to do.
00:42:22.080
The convention in the code golfing community is to present this as a one-liner, so let’s replace all of the new lines with semicolons, and the code will still be the same but will look more condensed.
00:43:46.720
So this is it, the final result! Now I really feel like Tiger Woods—all in one line. And now a warning from the North Pole Surgeon General: golf scripting is an addictive obsession where you spend a lot of time solving problems, and generally, the code you produce is useless for anything else.
00:45:27.360
However, it's also a fun and challenging way to learn to solve problems under artificial constraints and to practice out-of-the-box thinking. Just to be clear, this is intended to be fun; it's not something I would do in any code base at work, nor would I suggest you do it.
00:46:45.280
But I have given this talk before, and I have gotten mentions on Twitter that it was full of bad practices. Well, of course, you're free to tweet what you like, but come on!
00:48:03.680
Let’s see some tips for golfing Ruby. Some of them we already saw during the golfing exercise, like that one-character string where we could use the question mark preceding the character to save one byte.
00:48:52.640
Or we could use nil, which by itself is three bytes, but we can always call 'b' without any arguments, and it will return nil.
00:50:36.920
Some tips we didn’t see include true, which can be derived from previous examples—true is four bytes, but if we negate nil, we also get true. If we negate 'p', it’s only two bytes, and we yield the same results.
00:52:13.920
Now, what about false? Well, false is five bytes. However, if we negate zero, we get the same result. We could also double negate 'p', which would be three bytes, but if we negate zero, we only get it in two bytes.
00:53:56.640
Using string interpolation is in some cases better—for example, calling '2s'. If we apply the same to string interpolation, we're saving two bytes. This even works for interpolation instead of concatenation.
00:54:57.760
We can save one byte if we interpolate instead, because we don’t have the opening and closing brackets and plus signs surrounding.
00:55:57.820
When dealing with big numbers—specifically, multiples of ten—we can use scientific notation to save at least one byte, two, or three, depending on how long the number is. Granted, it will give you a float, but you can normally substitute it safely.
00:57:33.640
Let’s talk about operator methods. In some cases, we are forced to use parentheses because of operator precedence, but we can also use operator methods to get rid of these parentheses, since calling the method will give the precedence.
00:59:06.640
Now, how about initializing arrays? We normally do this if it is one value, but we can also do it this way and save one byte.
01:00:45.360
For arrays with multiple values, we can also do it without using the brackets, and it will be the same. When we call compact on an array, we remove nil values from it, but it’s a seven-byte method on the array.
01:01:49.680
You could achieve the same result if we subtract an array containing only nil, and using 'p' gives us four bytes less. If we want to remove duplicates, we usually call unique, which is not that long—only four bytes.
01:02:51.240
However, we can even make it shorter if we intersect an array with itself, specifically if you are using one-character variable names.
01:04:21.520
These were a few tips about golfing in Ruby. There are more, and you can find them yourself.
01:04:34.920
Finally, this talk wouldn't have been possible without the amazing coding community at Stack Exchange, especially for the links I'm sharing here to Jojoba’s problem, which this talk is based upon, and their excellent tips on golfing in Ruby.
01:05:12.919
If you want more problems to golf, you can go to the Stack Exchange code golfing community. If you want to take a closer look at my solution, I'm also sharing the wrapper for my code.
01:06:09.360
It includes git tags with every step of the process, and if you don’t mind the boring language in papers, there you have the link.
01:06:45.640
Thank you all for your attention! It was really a pleasure for me to present here at RubyConf 2021, and I hope to see you all next year.