Return of the Four Fours

In an attempt to get faster results for the four fours problem mentioned earlier, I've come up with a simpler algorithm that does even more number crunching but somehow computes the precious list faster. Despite being sillier because it computes the same thing twice (or even worse), it'll use waaay less memory.
Oh, and since the algorithm encodes the solutions as stacks of operations, it'll print them accordingly (in reverse polish notation).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens

Four fours

The "Four fours" problem has probably wasted many people's time... As I recently rediscovered the fun in solving this, but I didn't have the patience to figure out how to get more than 2 or 3 values, I started writing a program for it instead. Supposedly, computers are better at number crunching.

It takes about 2 15 seconds to compute five fours on my super-speedy 1.0 GHz AMD not-even-sure-it's-Turing-complete thing. However, trying with seven fours is only for the brave and the patient. The algorithm stores partial results in some huge matrix to reduce computation time, but I have a feeling that this has consequences (especially in JavaScript).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens

The long journey from character to AST... begins elsewhere

Since we're in full compiler-compiler season I thought it would be appropriate for me to also provide a more educational example. This example illustrates how a very rudimentary* compiler works. In more detail, it shows what happens to your code after it's been chopped into nice tokens. Then, it shows how, based on these tokens and the language's grammar an AST is built and then decorated and, finally, how this tree is fed to an interpreter and results start popping up.

By rudimentary I mean that the language consists of simple arithmetic expressions. Below, you can find the compiler-demo. Just type stuff and be amazed!

If you want to find out more about the inner workings of this nifty thing, check this very nicely written article on CodeProject.

Your input code:
7 + pi * (x - 10)
The environment:
{ "x" : 5, "pi" : 3 }
Output:

Melc

Every life form wants to live, naturally, but as our lifespan is limited the next best thing we can do is making sure our species survives. This applies to programmers too, as a species. For some time I've been haunted by the thought that I'll never be a real programmer until I write a compiler and the species metaphor I've come up with 5 minutes ago made a lot of sense. Joking aside, now I'm going to present Melc, a compiler-compiler.

Melc is a compiler-compiler or compiler generator that builds a recursive descent parser corresponding to whatever grammar it's been given. The grammar is written in SEBNF, which is a variation on EBNF. The specification including some examples is available on GitHub. I'm going to go on developing this and writing more examples in the year to come.

Petri dish party

Here's a seak peek of what I'm working on

Amandine

Rewriting rules:
21 -> 12 31 -> 13 32 -> 23

Input string:


Output string:



Amandine is a string-rewriting system.

The input given is rewritten accoding to the specified rules. This is how the process goes:
The first rule is applied repeatedly to the string until no more changes are made. Then the second rule is applied, followed by the third and so on. This process is repeated until the string can not be modified with any of the rules anymore. Rules are of the form source -> replacement where source is a JavaScript regular expression and replacement is a normal string. Lines that start with a ; are ignored.

The default example shows how sorting a sequence of numbers is possible.

OpenCL Experiments

While there are many applications (not necessarily scientific ones) for OpenCL and the technology has been available for some years, I have yet to see any piece of software that took advantage of this. There aren't even many tutorials and books on OpenCL. Now, I'm no expert but I thought I could make some OpenCL demos and share them on Github. Here's what I have so far:

• Simulation of repulsive particles - similar to the n-body problem, except here all particles want to stay apart and all particles are attracted to just one. This makes them chase each other which results in some neat patterns and dynamics.
• Hillclimbing! - the hillclimbing algorithm is a very simple stochastic optimization algorithm. The algorithm can be described as follows: a dwarf is placed in the search space (the hills). The dwarf chooses a random direction and goes that way as long as he keeps climbing, after which he chooses another direction and does that until he's on top of the hill. Obviously the hillclimbing algorithm is prone to getting stuck in local maxima, but that's where OpenCL comes in to save us: initialize N parallel hill climbers (dwarves) from random positions in the search space. Thus, we get N local maxima, one of which is the global maxima (hopefully).
• Particle Swarm Optimization (actually Parallel Asynchronous PSO) - I've already covered PSO in this online demo and extensively in my Bachelor's graduation thesis and Gloptat. PAPSO is more suitable for the GPU since synchronizing "threads" is costly. There is also no clear disadvantage in using asynchronous PSO and there are even scientific studies that show how reliable PAPSO is. PAPSO is even closer to what it simulates, to the natural model.
• Shadow demo - it's just a little demo showing a simple way to compute shadows using rays. It also shows how you can have more than one kernel on the same context/queue and that they can use the same allocated global memory without issues.