Forget about DRY 13.08.2017

I've once had a heated discussion with my colleagues, which eventually motivated me to write this blog post. This goes about DRY programming principle, being oh so loved by many developers. I'm convinced, that many do not really understand what does this principle really promote. DRY suffers from what I would call an "imprinting fallacy" (trying to mimic senior colleagues, while taking barely understood concepts to extreme), the same way the Singleton design pattern does.

An inexperienced developer, lets say Joe, starts working in a team, where words like "design patterns" are frequently used. Joe looks through some online articles and sees a lot of scary words and complex schemes. But then a simple enough passage pops up - a single instance of some class. So Joe starts to use Singleton extensively, as he thinks it makes him a more senior developer, because he now uses a design pattern. He does not know about all the hidden flaws he's building into the project. Same goes for DRY. It's deceptively easy to understand, while the devil is in the details. DRY - Don't repeat yourself, don't duplicate programmign code, what's more to it? The same Joe, is happy to use a programming principle he has heard about. He vigorously finds out all repeating lines of code and extracts them into separate (usually into static methods) classes. By doing that, he is most likely damaging the project once again. More...

For my job I needed to write a more efficient function to merge multiple sets of segments. Segments were date ranges where some special offers are applicable. So let's say a 10% discount is valid from 1st Jan to 10th Jan and another 20% discount is valid from 5th Jan to 15th Jan. This means both of them are valid between 5th and 10th. Those are just two ranges, there potentially be two lists of any amount of segments.

Now, I've said more efficient, because the code I inherited has been creating an list of all the dates within given ranges and calling array_merge on them. This has worked until we've started getting dates ranges like "0001-01-01 to 9999-12-31". I've came up with an algorithm, which might not be the most optimal, but I'm pretty happy with it. Especially because I've developed it without stealing parts from Google or StackOverflow. For funsies I'll reproduce the algorithm in Golang (it was in PHP originally).

Funnily enough, while writing this article I've come up with even easier solution. It seems much more obvious and looks like it doesn't deserve an article, but I've already wrote it. So there. Update 2: A day after posting I've simplified the algorithm even more by removing the flattening. It's now about 3 times shorter and 100 times easier to comprehend, than the first PHP version I wrote.

Prerequisites are: segments within a set are not overlapping with each other and are sorted. Let's start with a couple of definitions. I'll use ints for segment begin and end, but generally any comparable type will do (like in PHP I just use date strings "2017-01-25", which are perfectly comparable). You can also view the gist with the source + test here.

type segment struct {
    from, to int64
}

type segments []segment

A couple of functions I'm going to use are flatten, min and max. Flatten removes "borders" between ranges flattening them to an int array, min and max are pretty self-explanatory.

func min(a, b int64) int64 {
    if a < b { return a }
    return b
}

func max(a, b int64) int64 {
    if a > b { return a }
    return b
}

So here it goes:

func Merge(a, b segments) segments {

    result := segments{}

    // While there are entries left
    for len(a) > 0 && len(b) > 0 {

        // Set A will be the one, starting with the earliest date (smallest entry)
        if a[0].from > b[0].from {
            a, b = b, a
        }

        // While A has segments before the B starts, remove those
        if a[0].to < b[0].from {
            a = a[1:]
            continue
        }

        // We've thrown away all the non-intersecting segments at the beginning
        // So here we will have an intersection between a and b
        result = append(result, segment{
            max(a[0].from, b[0].from),
            min(a[0].to, b[0].to),
        })

        // Remove the segment of these two, which ends first
        if a[0].to < b[0].to {
            a = a[1:]
        } else {
            b = b[1:]
        }
    }

    return result
}

Every time I use a static method I feel embarassed, like I'm doing something shameful. Or when I see a Pull-Request with a bunch of static methods I think "Why? Why did you have to do it this way?". I dont want to push my beliefs on the others, so I don't decline those PRs. At least they get the work done. However I feel it's time to express why do I hate static methods.

To begin with, a static method is a class method, that can be invoked without instantiating a class. The most common usage I've seen are helper classes (oh my god I do also hate helper classes) and singletones. Let's look at those helper classes from another point of view. We have some set of methods, that, let's say, format a string in different ways. So we have

class Helper
{
   public static formatA() {...}
   public static formatB() {...}
   public static formatC() {...}
}

The thing is, it has absolutely no difference from:

function helper_formatA() {...}
function helper_formatB() {...}
function helper_formatC() {...}

Why would you bother writing this within a class instead of just a set of functions? Is it because you think you are using Object-Oriented Programming and writing class keyword makes your code better? I feel, like using static methods this way is a step away from the ideas of the OOP. This is not an instance of a class anymore.

So we have used this static method somewhere in the code:

// .. within some class
public function foo()
{
    // ...
    Helper::formatA('bar');
}

our module is now dependent on that static class. Can you tell by looking at the class API that it has that dependency? No you don't. It's a hidden dependency that can hit you when you don't expect it. If you extract your class into some library for common usage, you can suddenly find out, that you have to include Helper too. Moreover, this is a tight dependency, you can not substitute a call to this class by some other helper. And the more you use those static methods, the more dependencies you have in your project, that will entangle it like a spider web.

A singletone is absolutely no better. But how do I ensure, that I have just a single connection to my DB, you may ask? Well, you can instantiate it once at the bootstrapping, put it in the service container and reuse it. True, you will end up with more code that before, but if you want your project to be flexible you have to accept abstraction costs.

The same goes for the Helper Formatter example. Take an advantage of passing an instance of a Formatter class as a dependency injection. Use an interface as a type hinting to make it loosely coupled and be easily replacable. And then your method will depend on an abstraction rather than a specific object.

Usage of static methods can probably be explained somehow, the same way as a usage of goto. I used goto once, because of the PHP 'continue 2' memory leak bug. But under normal circustumstances I don't think there is a justification of using a static method.

Project Euler 502 11.04.2015

Hello everyone, I've decided to continue writing posts into my blog, when I deal with something interesting. This time my attention has been drawn to Project Euler problems. I tend to refer to those problems when I'm learning a new programming language. Solving easier problems help to get handy with the syntax and language constructs. So it's Haskell now. I'm not going to tell how Haskell is different from anything I've learned before (Coursera Scala course was the closest), so i'll just proceed with the Problem 502, which I found really intriguing.

The problem itself can be found here. Brief comprehension is: how many castles can you build, that follow the rules: no hanging blocks, total amount of blocks is even. I am currently at the first approach stage. The first approach is usually naive: generate every possible castle, check the validity and calculate how many there are.

But there are several concepts I used, which I find quite interesting. A castle consists of levels, each level consists of blocks and spaces between them. If you encode blocks and spaces as 0's and 1's you get a binary string, which you can convert to decimal. So, a castle is a just list of integers.

The next thing is, how do we generate a level on top of the previus level. And the answer is again, quite simple. If a level has a width of 3, then there are 8 possible combinations of blocks and spaces, which are also numbers from 0 (no blocks, only spaces) to 7 (one block across the whole level). So on the 2x2 grid there are: 1 for the base level + 3 possible combinations (0, 1, 2) of the second level = 4 castles. At this point there will also be invalid castles (with hanging blocks), but we will filter them out later. On a WxH grid we will have 1 + (2 ^ W - 1) ^ (H - 1) castles. As a simple example in the task it is given a 10x13 grid, which would produce ~1.65*10^35 possible castles (Eeek).

The next idea, which will cut the number of computations by a huge amount is a check, if there are any hanging blocks. Because if there is at least one, we can skip this "branch". How do we do it? Let's see, if a level is a binary number, the next level may not be bigger, than that number, because otherwise most significant bit will hover over 0 of the underlying level, which is not allowed. Moreover, every 1 of the new level must have an underlying 1 from the previous level - bitwise AND. (New level) AND (Old level) must be equal to the (New level), otherwise new level is invalid.

So this is basically it, I start with a base level, add numbers from 0 to (2 ^ W) - 1, if they AND with the previous level, and after all I calculate amonut of blocks by grouping them.

import Data.List
import Data.Bits

{-|
  Decimal to binary conversion
 -}
binary :: Integer -> [Integer]
binary 0 = [0]
binary 1 = [1]
binary x = binary (div x 2) ++ [mod x 2]

{-|
  Naive implementation of Euler Problem 502. Generate all castles, check validity, count
-}
castles :: Integer -> Integer -> Integer
castles w h = genericLength [c | c <- (allCastles w h), (even . sum . (map (countBlocks))) c]

{-|
  Generates all possible castles, even invalid ones. Each level is introduced
  with a number, which in binary form represents blocks
-}
allCastles :: Integer -> Integer -> [[Integer]]
allCastles _ 0 = []
allCastles 0 _ = []
allCastles w h = addLevel [[base]] (h-1)
  where base = (2 ^ w)-1
        addLevel castles levelsLeft
            | levelsLeft == 0 = castles
            | otherwise = addLevel ([c ++ [p] | c <- castles, p <- [0..(last c)], (p == p .&. (last c))]) (levelsLeft-1)

{-|
  Counts amount of blocks within a castle row
-}
countBlocks :: Integer -> Integer
countBlocks = genericLength . (filter ((== 1).head)) . group . binary

This is by no means an optimal solution, I couldn't even compute a 10x13 grid from the simpler example within a reasonable amonut of time. The biggest so far was a 9x7 grid for 28+ millions of castles.

Эффект плазмы (или попросту плазма) - эффект часто использующийся в демках, чтобы создать переливающийся эффект. Есть много способов создать анимацию плазмы, но я рассмотрю только один: сумма синусов и некоторых других функций. Экспериментируя с параметрами и пробуя различные функции, а так же цвета, можно найти очень круто выглядящие комбинации. Оригинал этой статьи можно найти здесь. В ней примеры указаны с использованием С, я же делал все на HTML5 (JavaScript + canvas). Примеры довольно просты и перенести на любой другой язык будет несложно. Внутри около 5 мегабайт картинок, если кого-то это беспокоит. More...