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.

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!

Hi,

I've been mulling ideas about a game for a while now, I'd like to hack out a prototype, and my default would be Love2D. (As an aside: one of the things I like about Love2D was that you could make a basic 'game' in a couple of LoC, and it was 'efficient enough' for what you got. Perhaps the only gripe I had with it was that it didn't output compiled binaries (I mean, you could make it do that, but it seemed like a hack). I think Polycode seemed to be a semi-serious contender, but last I checked (a year or two ago) it's pretty much as dead as a doornail. Some of the other alternatives I remember seeing (Godot? Unity?) felt too much like Blender.

So I've been wondering, it's been a while since I've been keeping tabs on the 'gamedev community', so I don't know if there have been any more recent development in that space.

So I guess my question is: What are people using for game jams nowadays? Preach to me (and everyone else) about your favorite framework and language :)

Introduction to Genetic Algorithms

Genetic algorithms can be used to solve problems that are difficult, or impossible to solve with traditional algorithms. Much like neural networks, they provide good-enough solution in short amount of time, but rarely find the best one. While they're not as popular as neural networks nor as widely used, they still have their place, as we can use them to solve complicated problems very fast, without expensive training rigs and with no knowledge of math.

Genetic algorithms can be used for variety of tasks, for example for determining the best radio antenna shape, aerodynamic shapes of cars and planes, wind mill shapes, or various queing problems. We'll use it to print "Hello, World!".

How does it work?

Genetic algorithm works in three steps.

1. Generate random solutions
2. Test how good they are
3. Pick the best ones, breed and mutate them, go to step 2

It works just like evolution in nature. First, we generate randomised solutions to our problem (in this case: random strings of letters).

Then, we test each solution and give it points, where better solutions gain more points. In our problem, we would give one point for each correct letter in the string.

Afterwards, we pick the best solutions and breed it together (just combine the strings). It's not bad idea to mutate (or randomize) the string a bit.

We collect the offsprings, and repeat the process until we find good enough solution.

Generate random solutions

First of all, we need to decide in which form we will encode our solutions. In this case, it will be simply string. If we wanted to build race cars, we would encode each solution (each car) as array of numbers, where first number would be size of the first wheel, the second number would be size of the second wheel, etc. If we wanted to build animals that try to find food, fight and survive, we would choose a decision tree (something like this).

So let's start and make few solutions, or entities. One hundred should be enough.

from random import randint

goal = "Hello, World!"
allowed_characters = list("qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM ,!")

def get_random_entity(n, string_length):
    entities = []
    for _ in range(0, n):
        entity = ""
        for _ in range(0, string_length):
            entity += allowed_characters[randint(0, len(allowed_characters)-1)]
        entities.append(entity)
    return entities

print(get_random_entity(100, 13))

Test how good they are

This is called a "fitness function". Fitness function determines how good a solution is, be it a car (travel distance), animal (food gathered), or a string (number of correct letters).

The most simple function we can use right now will simply count correct letters. If we wanted, we could make something like Levenshtein distance instead.

def get_fitness(entity):
    points = 0
    for i in range(0, len(entity)):
        if goal[i] == entity[i]:
            points += 1
    return points

Crossover and mutation

Now it's time to select the best ones and throw away the less fortunate entities. Let's order entities by their fitness.

Crossover is a process, when we take two entities (strings) and breed them to create new one. For example, we could just give the offspring one part from one parent and another part from second parent.

There are many ways how to do this, and I encourage you to try multiple approaches when you will be doing something like this.

P:  AAAABBB|BCCCC
P:  DDDDEEE|FGGGG

F1: AAAABBB|FGGGG

Or we can just choose at random which letter will go from which parent, which works the best here. After we have the offsprint (F1), we should mutate it. What if we were unfortunate, and H (which we need for our Hello, World!) was not in any of the 100 entities? So we take the string and for each character of the string, there is a small chance to mutate it - change it at random.

F1:  ADDDEBEFGCGG
F1`: ADHDEBEFGCGG

And it's done. Now kill certain part of old population. I don't know which percentage is best, but I usually kill about 90% of old population. The 90% that we killed will be replaced by new offsprings.

There is just one more thing: which entities do we select for crossover? It isn't bad idea - and it generally works just fine - to just give better entities higher chance to breed.

def get_offspring(first_parent, second_parent, mutation_chance):
    new_entity = ""
    for i in range(0, len(first_parent)):
        if randint(0, 100) < mutation_chance:
            new_entity += allowed_characters[randint(0, len(allowed_characters)-1)]
        else:
            if randint(0, 1) == 0:
                new_entity += first_parent[i]
            else:
                new_entity += second_parent[i]
    return new_entity

When we add everything together, we get this output:

Generation 1, best score: 2 ::: QxZPjoptHfNgX
Generation 2, best score: 3 ::: XeNlTOQuAZjuZ
Generation 3, best score: 4 ::: weolTSQuoZjuK
Generation 4, best score: 5 ::: weTgnC uobNdJ
Generation 5, best score: 6 ::: weTvny uobldb
Generation 6, best score: 6 ::: HellSy mYbZdC
Generation 7, best score: 7 ::: selOoXBWoAKn!
Generation 8, best score: 8 ::: HeTloSoWYZlh!
Generation 9, best score: 8 ::: sellpX WobKd!
Generation 10, best score: 9 ::: welloq WobSdb
Generation 11, best score: 9 ::: selloc WoZjd!
Generation 12, best score: 10 ::: wellxX WoVld!
Generation 13, best score: 10 ::: welltX World!
Generation 14, best score: 10 ::: welltX World!
Generation 15, best score: 10 ::: welltX World!
Generation 16, best score: 11 ::: zellov Wobld!
Generation 17, best score: 11 ::: Hellty World!
Generation 18, best score: 11 ::: welloX World!
Generation 19, best score: 11 ::: welloX World!
Generation 20, best score: 11 ::: welloX World!
Generation 21, best score: 12 ::: welloX World!
Generation 22, best score: 12 ::: Helloy World!
Generation 23, best score: 12 ::: Helloy World!
Generation 24, best score: 12 ::: Helloy World!
Generation 25, best score: 12 ::: Helloy World!
Generation 26, best score: 12 ::: Helloy World!
Generation 27, best score: 12 ::: Helloy World!
Generation 28, best score: 12 ::: Helloy World!
Generation 29, best score: 12 ::: Helloy World!
Generation 30, best score: 12 ::: Helloy World!
Generation 31, best score: 12 ::: Helloy World!
Generation 32, best score: 12 ::: Helloy World!
Generation 33, best score: 12 ::: Helloy World!
Generation 34, best score: 13 ::: Helloy World!
Generation 35, best score: 13 ::: Hello, World!

As we can see, we find pretty good solution very fast, but it takes very long to find perfect solution. The complete code is here.

Maintaining diversity

When we solve difficult problems, it starts to be increasingly important to maintain diversity. When all your entities are basically the same (which happened in this example), it's difficult to find other solutions than those that are almost the same as the currently best one. There might be a much better solution, but we didn't find it, because all solutions that are different to currently best one are discarded. Solving this is the real challenge of genetic algorithms. One of the ideas is to boost diverse solutions in fitness function. So for every solution, we compute distance to the current best solutions and add bonus points for distance from it.

Hey Tildes!

I've got a static, basic website, HTML and CSS. It's one page only. But I'd like to create a second page with some more private content that is password protected.

I know that I can accomplish this via .htaccess but what I don't like about this method is that when the user navigates to the page, they get a pop up asking for a username and password. What I would like is having the user navigate to the page, and then they are met with a simple form asking for just a password (no username). After they enter the password, the "veil" lifts or the page forwards and they get the private content.

Here's the thing... the content really only needs to seem private. It's not super secret, personal information. I don't want it indexed by search engines (nofollow), and I want it basically hidden, but the password is only there to make the user feel exclusive. If some tech-minded person encountered this page and jumped through a bunch of hoops to get in without the password, it's not a big deal to me. In reality, 99.9% of people accessing this page will not be able to bypass the password.

I'm guessing this can be accomplished easily in Javascript, but I don't really know much Javascript apart from finding code snippets and plunking them in. I also want to be able to fully design the password entry page so that it looks branded, so a code snippet plunked down into my HTML doc would be great for this.

If there is an easy way to actually protect the content behind the password, that would be excellent. In this case, I imagine it would be much like a news site with an ad-blocker-blocker. Just some kind of pop-up that blocks all the content. Enter the password, and you're in.

Anyhow, I hope I've described what I'm looking for accurately enough. Anybody have any easy and quick ways to accomplish this?

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?

tldr; chunkwm has been completely rewritten and is now yabai

From the chunkwm site:

chunkwm is no longer in development because of a C99 re-write, yabai.

yabai was originally supposed to be the first RC version of chunkwm. However due to major architectural changes, supported systems, and changes to functionality, it is being released separately. There are multiple reasons behind these changes, based on the experience I've gained through experimenting with, designing, and using both kwm and chunkwm. Some of these changes are performance related while other changes have been made to keep the user experience simple and more complete, attempts to achieve a seamless integration with the operating system (when possible), proper error reporting, and yet still keep the property of being customizable.

For those who don't know, chunkwm was / is a tiling windows manager that is sort of like bspwm / i3 etc. I've been using chunkwm for a few months now and love it. If you're also an i3 user, the lack of a proper super key does make your key combos different, but overall its an excellent window manager. Both chunkwm and yabai use koekeishiya's Simple Hotkey Daemon (skhd).

Anyway, I gave the new version the day and its pretty good, but still has some quirks. It seems like development is moving along quickly, so keep an eye on it.

So I've been messing around with the webp encoder cli tool and I really wish I could quickly achieve a workflow more similar to photoshop's previews. Is there a GUI tool out there where I can specify the arguments for an CLI executable then it lets me adjust the values and run the command. Ideally it would automatically let me view the output file, and define presets would be great.

What is the programming language you enjoy the most, or otherwise define as your favourite? Why is that particular language your favourite?

Bonus: add just a little bit of code in it that you think exposes its beauty.

This is of course the age old debate, which on other sites has been known to quickly devolve (one of the Internet ‘holy wars’ of yore). Nonetheless, I am curious.

I personally use vim. Part of the reason is surely that it is just the first one of the two that I happened to use, and thus by the time I tried emacs I was used to vim. But more broadly, I enjoy using vim because once you get over the hump of ‘weird’ commands and modes, I feel that vim most closely emulates the feelings and thought process that you have when building something with your hands. You can pick up different tools, yank pieces out and rearrange them, turn the object around in your hands to see different parts, etc etc. Once you internalize the movement and editing you really start flying around. At that point the interface seems less like a barrier between you and the text and more like a way to ‘hold’ it.

Of course, people have different preferences.

Hi everyone! Per admin recommendation I'm posting this in comp.

I would like to switch Staining The Timbre from a blogspot domain to its own. I can handle the paperwork and whatnot associated with the url change, but I would like to hire a web designer to spruce up the joint a bit. Right now I'm using a default theme provided by Blogspot and, while it serves its purpose, it makes the page look like it's run by a high schooler.

It should be a relatively basic project. I don't need anything for commerce set up, or anything I think of as "crazy". Just a very basic blog layout that looks professional on both desktop and mobile (the latter is a little lacking in particular right now). Archive links, Tags, ability to comment on posts, Contact Info, and one that preferably preserves the large-picture format the site currently has; that's about it, aside from being able to create the posts themselves.

If anyone is interested please send me a private message. This is very much still in the quoting phase, but I appreciate any assistance you all can provide me in getting an idea on cost.

Thanks in advance!