tag:blogger.com,1999:blog-10147043243359553922024-03-18T01:44:37.910-07:00MadFlame Softwaremadflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.comBlogger91125tag:blogger.com,1999:blog-1014704324335955392.post-33800112706664713082014-01-29T22:55:00.000-08:002014-01-29T22:55:17.029-08:00DFA problemsWhen learning about automata, you might stumble upon this classical problem which pops up in books, lecture notes and articles:<br />
"Construct a DFA that accepts the strings containing an even number of 1s and 0s"<br />
<br />
The classic solution I've seen associated with the problem is the following:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgavE6xAdTu-Hl71GWshMgFTIXmrL_WqANl5e2ZM2GaJ6nzKHCSczX_Zn685aySWhslS08PhImDlpsCat2o9CSHg6MShFJOQzSgzQmQAGM3HRWFyntHNFnRw_saCO1tCgJM4DDR1ofW6UO/s1600/automaton5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgavE6xAdTu-Hl71GWshMgFTIXmrL_WqANl5e2ZM2GaJ6nzKHCSczX_Zn685aySWhslS08PhImDlpsCat2o9CSHg6MShFJOQzSgzQmQAGM3HRWFyntHNFnRw_saCO1tCgJM4DDR1ofW6UO/s1600/automaton5.png" height="170" width="200" /></a></div>
I'll call this the <i>A<sub>2,2</sub></i> automaton and I'll explain later why.<br />
<br />
We can easily check that this is the minimal automaton for this particular language.<br />
However, I've never seen anyone try to tear this automaton apart and explain how one would reach it. Sure, you could find a non-deterministic automaton first that solves the problem, convert it to a deterministic one, and finally minimize it, but building it from scratch is far nicer.<br />
<br />
First, let's consider a simpler, but related problem for example:<br />
"Construct the DFA that accepts the strings containing an even number of 1s"<br />
<br />
Of course, the solution to this trivial problem is the following:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgV4XQJ3YInP-4f-VLvnWtn-Cnxs_J4wOr45le9oGm9XYIIr6utPTDECwcTHNhnq7tgXBI2yd0LWjmR_NyQtql4U9f9GupSDmCn7eObiMfrLFi04QR5dBz99ED_lDRULzurer3UbXejBlX_/s1600/a9.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgV4XQJ3YInP-4f-VLvnWtn-Cnxs_J4wOr45le9oGm9XYIIr6utPTDECwcTHNhnq7tgXBI2yd0LWjmR_NyQtql4U9f9GupSDmCn7eObiMfrLFi04QR5dBz99ED_lDRULzurer3UbXejBlX_/s1600/a9.png" height="82" width="200" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
I'm naming this <i>A<sub>2</sub></i> and for convenience I'll rewrite it to look like this instead.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZ1cFij5MVgaMaJEbLf-rjSwJRRBFCemdRsmbLz4qsqxCGpW60Zbq7VeNe-amYEPCzDcc1mFfBsvMsZ0TSsNDOodg5Haoir1CbjoKSISHCQ6JLFDkpB8C7KFkajHywyabxCCDdGBWihtMg/s1600/automaton6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZ1cFij5MVgaMaJEbLf-rjSwJRRBFCemdRsmbLz4qsqxCGpW60Zbq7VeNe-amYEPCzDcc1mFfBsvMsZ0TSsNDOodg5Haoir1CbjoKSISHCQ6JLFDkpB8C7KFkajHywyabxCCDdGBWihtMg/s1600/automaton6.png" height="83" width="200" /></a></div>
<br />
Wait, how is this related to the initial problem? Well, if we look closer at <i>A<sub>2,2</sub></i> we observe that we can build a similar structure to that of <i>A<sub>2,2</sub></i>'s out of this simpler automaton.<br />
<br />
Just take these two automata<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwB_6beaWx1xW4-sTpyVKXj7S2qeMVnhI_Kqex51Zdhidkb1W-s0cN58-A3i28lUFQtBrd1uB20Lg6UvBCJLy3ktbtaC3AahIVYDOlq0nd7C20P8bNMtKffqIwjIkp5Z0pWAGnXVrRQy1I/s1600/a6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwB_6beaWx1xW4-sTpyVKXj7S2qeMVnhI_Kqex51Zdhidkb1W-s0cN58-A3i28lUFQtBrd1uB20Lg6UvBCJLy3ktbtaC3AahIVYDOlq0nd7C20P8bNMtKffqIwjIkp5Z0pWAGnXVrRQy1I/s1600/a6.png" height="200" width="86" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbqYRmlbSEFEhCIfXXhB19z-jfNDI0DUi-ZGx7sO99vQyN-JqLN4HmDk7dDuTncmm5GOoi5ucnVWu6yAiz5zwQNFzJwGM_1zhl0DQCMer0NFDuRf0__fWG-J5JBhXi9tgujbXzwoIsWSUy/s1600/a7.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbqYRmlbSEFEhCIfXXhB19z-jfNDI0DUi-ZGx7sO99vQyN-JqLN4HmDk7dDuTncmm5GOoi5ucnVWu6yAiz5zwQNFzJwGM_1zhl0DQCMer0NFDuRf0__fWG-J5JBhXi9tgujbXzwoIsWSUy/s1600/a7.png" height="110" width="200" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Multiply them and that's it!</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqm9tov_54eiygM-cdz_dl0EJ_bZUvafm1RzvAz0HguX-Frmo75BBnBtDkB46vAIkgVmpdQLLUG1CtJ19EjP0PDsKlGcT4pVpUtfaIXOoplx3dJjIZoGGSD_9aCCgRgSyMNKf1zJ9rpMeG/s1600/a3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqm9tov_54eiygM-cdz_dl0EJ_bZUvafm1RzvAz0HguX-Frmo75BBnBtDkB46vAIkgVmpdQLLUG1CtJ19EjP0PDsKlGcT4pVpUtfaIXOoplx3dJjIZoGGSD_9aCCgRgSyMNKf1zJ9rpMeG/s1600/a3.png" height="191" width="200" /></a></div>
<br />
It turns out that an automaton that accepts "an even number of <span style="color: #38761d;">G</span>s" AND "an even number of <span style="color: #0b5394;">B</span>s" is the result of multiplying the automaton that accepts "an even number of <span style="color: #38761d;">G</span>s" with the automaton that accepts "an even number of <span style="color: #0b5394;">B</span>s"<br />
<br />
<br />
Let's now generalise this!<br />
"Construct a DFA that accepts the strings containing <i>k*2</i> Rs and <i>k*3</i> Gs (for any natural number <i>k</i>)"<br />
<br />
Following the recipe, we first need to build the automata that accept the two sublanguages and then multiply them.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCWsha_8efVW93OV73TcpdxEIwZK1WSD9pmHolkig2FxdTOBg-F5qQ6Il4Md9FYytzmf2bGcxp-CIdQ1YNClSTHpgHhlJgFrxjH1gfaZ054343euLHLvkrrV1oPWvt2gHoWzh_kO7kfO-B/s1600/a5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCWsha_8efVW93OV73TcpdxEIwZK1WSD9pmHolkig2FxdTOBg-F5qQ6Il4Md9FYytzmf2bGcxp-CIdQ1YNClSTHpgHhlJgFrxjH1gfaZ054343euLHLvkrrV1oPWvt2gHoWzh_kO7kfO-B/s1600/a5.png" height="200" width="128" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbqYRmlbSEFEhCIfXXhB19z-jfNDI0DUi-ZGx7sO99vQyN-JqLN4HmDk7dDuTncmm5GOoi5ucnVWu6yAiz5zwQNFzJwGM_1zhl0DQCMer0NFDuRf0__fWG-J5JBhXi9tgujbXzwoIsWSUy/s1600/a7.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbqYRmlbSEFEhCIfXXhB19z-jfNDI0DUi-ZGx7sO99vQyN-JqLN4HmDk7dDuTncmm5GOoi5ucnVWu6yAiz5zwQNFzJwGM_1zhl0DQCMer0NFDuRf0__fWG-J5JBhXi9tgujbXzwoIsWSUy/s1600/a7.png" height="110" width="200" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgID3MLDWJ5IvRqvLCvVjjyjSQFI0S6XBT8uDPFfHePvl6t-aSqa4NGtPKRJA7JCCYIusQGl34lZTIBnCoXbaME-T9c0zhVMq7zb0blodNn93IQE74ILzfy5hYhCw05koU9cN2pKLApXb7q/s1600/a4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgID3MLDWJ5IvRqvLCvVjjyjSQFI0S6XBT8uDPFfHePvl6t-aSqa4NGtPKRJA7JCCYIusQGl34lZTIBnCoXbaME-T9c0zhVMq7zb0blodNn93IQE74ILzfy5hYhCw05koU9cN2pKLApXb7q/s1600/a4.png" height="198" width="200" /></a></div>
<br />
I'll call this <i>A<sub>2,3</sub></i>. See, the two indices (<i>2</i> and <i>3</i>) indicate the length of the cycles.<br />
<br />
Can this scheme be extended to fit a third symbol? Yes, of course! Let's see how <i>A<sub>2,2,2</sub></i> would look like.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZ8U6uxa1QjSjPAL2N4xv8Z0A1YtighYpU-ULsysPSKJ1A6lvn7GUyPbPfhAmbXmUi6-IgZzWveVT4ppof7ore6ZyPDQVGQAFjS6PRNX2C0MIf-c2iC8EN5tfRl1N0OErZwvBNfFXnqfq7/s1600/automat3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZ8U6uxa1QjSjPAL2N4xv8Z0A1YtighYpU-ULsysPSKJ1A6lvn7GUyPbPfhAmbXmUi6-IgZzWveVT4ppof7ore6ZyPDQVGQAFjS6PRNX2C0MIf-c2iC8EN5tfRl1N0OErZwvBNfFXnqfq7/s1600/automat3.png" height="178" width="200" /></a></div>
<i><span style="color: #666666;">Special thanks to Mr. Sipos together with whom I cracked this late in the evening years ago.</span></i>madflame992http://www.blogger.com/profile/08408294699819048371noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-26688357730196210102013-10-06T12:10:00.000-07:002013-10-06T12:10:07.118-07:00WebGL is good for your healthHere's a totally random link I've happened to find on the internet: <a href="https://3d.casinofloor.com/">https://3d.casinofloor.com/</a>.<br />
<div>
What is this you might say?! Am I trying to lure you to some online casino and get incredibly wealthy? Well, that, and take a closer look at the link - it says "3d"! Now click on the link, wait 2 seconds for it to load and feast your eyes on one of the biggest tech-demos showing off WebGL - it's a 300 meter long cathedral-like casino containing a ton of slot machines, animated characters, particles, reflective water, gazillions of bottles and glasses, spooky statues and a never-ending sunset.</div>
<div>
<br /></div>
<div>
As far as I'm aware there are only 2 other neat demos out there showing off huge environments in WebGL. The first is the <a href="http://www.unrealengine.com/html5/">Epic Citadel demo</a> by the makes of the Unreal engine and the second is <a href="https://developer.mozilla.org/en/demos/detail/bananabread">Bananabread</a>. These 2 are initially coded in C++ and then transpiled in asm.js flavoured JavaScript. Wait, why are people in this age coding in C++ and then spitting out javascript-machine-code-wannabe apps on the web? Plain JavaScript is fast and mature enough to develop in and drive huge applications as well - as proof, the Casinofloor demo uses the Goo Engine which is written from scratch in JavaScript.<br />
<br />
tl;dr? Short version: <a href="http://www.gooengine.com/">goo.js</a> rules and check out the little snippet below:</div>
<div>
<div>
<br /></div>
<div>
<iframe allowfullscreen="allowfullscreen" frameborder="0" height="500" src="http://jsfiddle.net/cTGxH/embedded/result" width="500"></iframe>
</div>
</div>
madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-64390580327298382132013-08-17T03:57:00.000-07:002013-08-17T03:57:22.325-07:00Meanwhile...<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTWQdMVcAgNVCDgVfvfqwz4OQ03hgkcExZA8yj9PilsLpOELscMW-EBgTnsewOdT4ZUX0_1F0Ha7NDazWyrDdY5XIsdRx37lFMWwmn1EUn2Odb13QYP_tEyHLsYHMgdOhYjpAj1amKuZOw/s1600/Goo_Logo_300x300_Blue_Clear.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTWQdMVcAgNVCDgVfvfqwz4OQ03hgkcExZA8yj9PilsLpOELscMW-EBgTnsewOdT4ZUX0_1F0Ha7NDazWyrDdY5XIsdRx37lFMWwmn1EUn2Odb13QYP_tEyHLsYHMgdOhYjpAj1amKuZOw/s1600/Goo_Logo_300x300_Blue_Clear.png" /></a></div>
I've been a bit absent/slow on this blog and I'm terribly sorry, but I've grown out of my bedroom now, I'm not a "bedroom programmer" any more, I got a job and I program among other programmers (in an office!). I'm working at Goo Technologies and as a Goonian I have the honour of contributing to <a href="http://www.gooengine.com/">GooJS</a> (a really cool JavaScript-WebGL-3D-eyepopping-library) (oh, and yes, we at Goo prefix everything with "goo").<br />
<div>
<br /></div>
<div>
<div>
And in the weekends I still manage to push updates on MUPLex.</div>
<div>
One of the most important additions to MUPLex is a type-inferencer-checker-thing. The language is still dynamically typed (I love dynamic typing), but because the default/preferred bindings in the language are immutable and because there are <b>no implicit conversions</b>, a static code analyser can have a look at the code, infer the possible types of expressions and throw warnings when it concludes that some bits of code can never execute properly if they're reached.</div>
<div>
Another addition is that MUPLex now has a to-javascript transpiler. Yes, I am contributing to the 87563284762 languages that compile to JS nowadays. One of the hardest bits was to find a translation scheme that generates pretty expression-ish looking JS code (even compiled code has to be pretty) and not generate any <i>_var_7a62ff</i> variables. It actually generates <b>no extra variables.</b> MUPLex has some features like implicit currying, lexical scoping and a module/namespace system, but JS is flexible enough that you can emulate these relatively easy.<br />
<br />
"In the future, in the year 2000" I'm looking forward to showing what awesomeness you can achieve with GooJS and you can expect more updates on MUPLex, but not that often.</div>
</div>
madflame992http://www.blogger.com/profile/08408294699819048371noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-82321016643851247462013-04-25T08:21:00.000-07:002013-08-11T04:42:39.816-07:00Introducing MUPLex<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVtbgDgDsGFyvQkFCpO8X_t2khyphenhyphenbJWsUyiSbjWuSuye6SmMqEYRX4HU6EYMWTVtf2TA79-9mW0RW-cNk1yF6uX1js9Rgdq_nY56fDBha8o6fBcWa1_fdOJbISCo0zsbhXXHZOT6SPY46M/s1600/muplex.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVtbgDgDsGFyvQkFCpO8X_t2khyphenhyphenbJWsUyiSbjWuSuye6SmMqEYRX4HU6EYMWTVtf2TA79-9mW0RW-cNk1yF6uX1js9Rgdq_nY56fDBha8o6fBcWa1_fdOJbISCo0zsbhXXHZOT6SPY46M/s1600/muplex.png" /></a></div>
I've been taking one of Dan Grossman's courses on programming languages and it was one of the most illuminating I've ever taken. While teaching, he used a <b>m</b>ade <b>u</b>p <b>p</b>rogramming <b>l</b>anguage called MUPL. This MUPL had higher order functions, pairs, conditionals and the addition operation - this is the bare minimum with which you can teach how to build interpreters but also enough on which you can further build a high level functional language.<br />
<br />
MUPLEx is basically an extensions of MUPL. It adds some syntactic sugar as well as new features. Here's a list:<br />
<br />
<ul>
<li>Functions with an arbitrary number of arguments</li>
<li>Currying by default</li>
<li>Mutability - yes, I know mutability is the source of all evil (most of it, at least) but in some cases it makes sense, like having lazy evaluation or memoization</li>
<li>Records - to be able to build meaningful data structures</li>
<li>More math operations</li>
<li>Letrec - the equivalent of <i>forward declaration</i> in C (this way you can have mutually recursive functions, or other useful constructs)</li>
<li>Cond - syntactic sugar for nested conditionals</li>
<li>Lists - syntactic sugar for nested pairs</li>
<li>A way to print out stuff</li>
<li>Booleans</li>
</ul>
<br />
It also has some primitive type checking to catch some errors as you type. But, unfortunately, at this stage the errors are not too explicit.<br />
<br />
I can't include the interpreter in this post because it's a pretty hefty beast, but I can point you to the <i><a href="http://htmlpreview.github.com/?https://github.com/madflame991/muplex/blob/working/main.html">github HTML preview thingie</a></i> or directly to the <a href="https://github.com/madflame991/muplex">repository</a>.<br />
<span style="color: #999999;">*the preview may not work in Chrome/Safary</span>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-71344566173210073422013-04-03T23:33:00.001-07:002013-08-11T04:40:20.440-07:00Spring updates, RU invades the GPUSpring has come! (for most at least, Sweden is actually a bit behind). So here's some spring news:<br />
<br />
Firstly, I've updated the stochastic optimization framework. The plugin system is now fully functional - yes, you can pack your favourite algorithm into a .jar, drop it in the plug-ins folder and see how it performs. The usual bug fixes here and there also come with this update.<br />
<br />
Secondly, I've updated and shared Particle48 on <a href="https://github.com/madflame991/Particle48">github</a>. It's a particle systems library (for JS & the HTML5 canvas) I made a while ago for use at LD events (and I've actually used it in Homo Vermes). I expect to update it before every LD compo and add new types of particles. If I get fellow ludumers to contribute, things will really start rolling.<br />
<br />
And last but not least, <a href="http://madflame991.blogspot.se/2012/10/opencl-experiments.html">OCLEx</a> got 2 new additions: 1. a simple demo to the bundle to show how to set things up to start doing some image manipulation on the GPU and 2. RU on the GPU - this basically means that every Executor is a separate "process" running on the GPU and doing its duty. It started as an experiment to see how one would simulate a MIMD architecture in a SIMD environment and then got disguised in a nice RU uniform. Early OpenCL capable video cards have terrible performance penalties if the kernels are not executing the same instruction. This is a big bummer if you have any sorts of branches in the kernels. With this simulation you don't get any performance penalties (everything runs slower, but it's independent of the instructions the kernels are executing). I'll come back with more details after I do some more work and prettify it. In the mean time you can find it <a href="https://github.com/madflame991/oclex/tree/working/src/mru">here</a>.<br />
<br />
The screenshot looks like that not because it's a work in progress but because it uses the GL_UGLY texture filter.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5ynUU47ZU318fN3ljJCCXrGVsARrCYuBD7_dxR-lw6xDxUAfw6-T-d0YZWr2BXUGZtRCyIqMNlmV-tEl3jtUlftGGFOD66NrJW0PmDe-ZUV6cP81wEQVDVFpdeXJhA2h5iDqoE5hQBFw/s1600/mru_scrshot1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5ynUU47ZU318fN3ljJCCXrGVsARrCYuBD7_dxR-lw6xDxUAfw6-T-d0YZWr2BXUGZtRCyIqMNlmV-tEl3jtUlftGGFOD66NrJW0PmDe-ZUV6cP81wEQVDVFpdeXJhA2h5iDqoE5hQBFw/s1600/mru_scrshot1.png" /></a></div>
<br />madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-25455199688442096852013-02-27T01:28:00.000-08:002013-08-11T04:40:45.098-07:00Return of the Four Fours<script type="text/javascript">
"use strict";
(function () {
function Emp() { }
Emp.hd = function() { throw 'Emp has no head'; }
Emp.tl = function() { throw 'Emp has no tail'; }
Emp.con = function(n) { return new List(n, this); }
Emp.empty = function() { return true; }
Emp.len = function() { return 0; }
Emp.toString = function() { return ''; }
function List(n, tail) {
this.n = n;
if(tail == undefined) this.tail = Emp;
else this.tail = tail;
this.length = this.tail.length + 1;
this.string = this.tail.toString() + ' ' + this.n;
}
List.prototype.hd = function() { return this.n; }
List.prototype.tl = function() { return this.tail; }
List.prototype.con = function(n) { return new List(n, this); }
List.prototype.empty = function() { return false; }
List.prototype.len = function() { return this.length; }
List.prototype.toString = function() { return this.string; }
//-----------------------------------------------------------------------------
function Put(list) {
return list.con(Put.p);
}
Put.t = 1;
Put.p = 4;
Put.req = 0;
Put.toString = function() { return Put.p + ''; };
//-------------------------------------
function Add(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(a + b);
}
Add.t = 1;
Add.req = 2;
Add.toString = function() { return '+'; };
//-------------------------------------
function Sub(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(a - b);
}
Sub.t = 1;
Sub.req = 2;
Sub.toString = function() { return '-'; };
//-------------------------------------
function Mul(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(a * b);
}
Mul.t = 1;
Mul.req = 2;
Mul.toString = function() { return '*'; };
//-------------------------------------
function Div(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(a / b);
}
Div.t = 1;
Div.req = 2;
Div.toString = function() { return '/'; };
//-------------------------------------
function Sqrt(list) {
var a = list.hd();
return list.tl().con(Math.sqrt(a));
}
Sqrt.t = 0;
Sqrt.req = 1;
Sqrt.toString = function() { return '\u221A'; };
//-------------------------------------
function Mod(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(a % b);
}
Mod.req = 2;
Mod.toString = function() { return '%'; };
//-------------------------------------
function Exp(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con(Math.pow(a, b));
}
Exp.req = 2;
Exp.toString = function() { return '^'; };
//-------------------------------------
function Avg(list) {
var a = list.hd();
var b = list.tl().hd();
return list.tl().tl().con((a + b) / 2);
}
Avg.req = 2;
Avg.toString = function() { return 'a'; };
//-----------------------------------------------------------------------------
function Gen() { }
Gen.op = [Put, Add, Sub, Mul, Div, Sqrt];
Gen.en = 0;
Gen.lim = 0;
Gen.list = [];
Gen.gen = function(part, consum, k, pr) {
if(k < Gen.lim) {
for(var i=0; i<Gen.op.length; i++) {
if(consum[i] > 0 && part.len() >= Gen.op[i].req) {
consum[i]--;
Gen.gen(Gen.op[i](part), consum, k + (Gen.op[i].t), pr.con(Gen.op[i]));
consum[i]++;
}
}
}
else {
if(Gen.list[part.hd()] == undefined)
Gen.list[part.hd()] = pr.toString();
else if(Gen.list[part.hd()].length > pr.toString())
Gen.list[part.hd()] = pr.toString();
}
}
Gen.genAll = function(en, init) {
Gen.en = en;
Gen.lim = en + en - 1;
Put.p = init[0];
Gen.list = [];
Gen.gen(new List(init[0], new List(init[0])), [en-2,10,10,10,10,2], 2, new List(Put, new List(Put)));
var ret = [];
for(var i in Gen.list)
if(i % 1 === 0 && i >= 0)
ret.push(new Entry(i, Gen.list[i]));
return ret;
}
//=============================================================================
function Entry(v, s) {
this.v = v;
this.s = s;
}
//=============================================================================
function prettifyResult(ar) {
var ret = '';
for(var i=0;i<ar.length;i++)
ret += ar[i].v + ' = ' + ar[i].s + '\n';
return ret;
}
function t(en, init) {
var a = Gen.genAll(en, init);
console.log(prettifyResult(a));
}
function onch() {
var s1 = document.getElementById('s1_h');
var s2 = document.getElementById('s2_h');
var v1 = s1.selectedIndex + 3;
var v2 = s2.selectedIndex + 1;
var rd = document.getElementById('res_h');
var a = Gen.genAll(v1, [v2]);
rd.innerHTML = prettifyResult(a);
}
setTimeout(onch, 200);
setTimeout(
function() {
document.getElementById('s1_h').onchange = onch;
document.getElementById('s2_h').onchange = onch; }, 200);
})();
</script>
In an attempt to get faster results for the four fours problem mentioned <a href="http://madflame991.blogspot.se/2013/02/four-fours.html">earlier</a>, 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.<br />
Oh, and since the algorithm encodes the solutions as stacks of operations, it'll print them accordingly (in reverse polish notation).<br />
<br />
I want to see all
<select id="s1_h">
<option value="three">three</option>
<option value="four" selected>four</option>
<option value="five">five</option>
<option value="six">six</option>
<option value="seven">seven</option>
</select>
<select id="s2_h">
<option value="ones">ones</option>
<option value="twos">twos</option>
<option value="threes">threes</option>
<option value="fours" selected>fours</option>
<option value="fives">fives</option>
<option value="sixs">sixes</option>
<option value="sevens">sevens</option>
<option value="eights">eights</option>
<option value="nines">nines</option>
<option value="tens">tens</option>
</select>
<br />
<pre id="res_h"></pre>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com1tag:blogger.com,1999:blog-1014704324335955392.post-13018650657855338402013-02-15T06:23:00.000-08:002013-08-11T04:40:45.092-07:00Four fours<script type="text/javascript">
"use strict";
//=============================================================================
function Add(a, b) { return (a - 0) + (b - 0); }
Add.str = '+';
//-----------------------------------------------------------------------------
function Sub(a, b) { return a - b; }
Sub.str = '-';
//-----------------------------------------------------------------------------
function Mul(a, b) { return a * b; }
Mul.str = '*';
//-----------------------------------------------------------------------------
function Div(a, b) { return a / b; }
Div.str = '/';
//-----------------------------------------------------------------------------
function Sqrt(a) { return Math.sqrt(a); }
Sqrt.str = '\u221A';
//=============================================================================
function Gen() { }
Gen.unaryNestingLimit = 4;
Gen.genAll = function(en, init) {
var op = [Add, Sub, Mul, Div];
var m = [];
for(var i=0;i<=en;i++)
m.push([]);
for(var i=0;i<init.length;i++)
m[1][init[i]] = init[i] + '';
var tmps, tmpv;
for(var i=0;i<init.length;i++) {
m[1][init[i]] = init[i] + '';
tmpv = init[i];
tmps = tmpv + '';
for(var j=0;j<1/*Gen.unaryNestingLimit*/;j++) {
tmpv = Sqrt(tmpv);
tmps = Sqrt.str + tmps;
if(m[1][tmpv] == undefined) {
m[1][tmpv] = tmps;
}
else if(m[1][tmpv].length > tmps.length) {
m[1][tmpv] = tmps;
}
}
}
for(var t=0;t<2;t++)
for(var sumlen=2;sumlen<=en;sumlen++)
for(var os=1;os<en;os++) {
var ns = sumlen-os;
for(var nsi in m[ns])
for(var osi in m[os])
for(var i in op) {
//binary operations
tmpv = op[i](nsi, osi);
if(tmpv > -Infinity && tmpv < Infinity) {
if(m[sumlen][tmpv] == undefined) {
tmps = '(' + m[ns][nsi] + ' ' + op[i].str + ' ' + m[os][osi] + ')';
m[sumlen][tmpv] = tmps;
}
else {
tmps = '(' + m[ns][nsi] + ' ' + op[i].str + ' ' + m[os][osi] + ')';
if(m[sumlen][tmpv].length > tmps.length) {
m[sumlen][tmpv] = tmps;
}
}
//unary operations
for(var j=0;j<Gen.unaryNestingLimit;j++) {
tmpv = Sqrt(tmpv);
tmps = Sqrt.str + tmps;
if(m[sumlen][tmpv] == undefined) {
m[sumlen][tmpv] = tmps;
}
else if(m[sumlen][tmpv].length > tmps.length) {
m[sumlen][tmpv] = tmps;
}
}
}
}
}
var ret = [];
for(var i in m[en])
if(i % 1 === 0 && i >= 0)
ret.push(new Entry(i, m[en][i]));
return ret;
}
//=============================================================================
function Entry(v, s) {
this.v = v;
this.s = s;
}
//=============================================================================
function prettifyResult(ar) {
var ret = '';
for(var i=0;i<ar.length;i++)
ret += ar[i].v + ' = ' + ar[i].s + '\n';
return ret;
}
//=============================================================================
function onch() {
var s1 = document.getElementById('s1');
var s2 = document.getElementById('s2');
var v1 = s1.selectedIndex + 3;
var v2 = s2.selectedIndex + 1;
var rd = document.getElementById('res');
var a = Gen.genAll(v1, [v2]);
rd.innerHTML = prettifyResult(a);
}
setTimeout(onch, 200);
</script>
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.<br />
<br />
It takes about <del>2</del> <ins>15</ins> 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).<br />
<br />
I want to see all
<select id="s1" onchange="onch()">
<option value="three">three</option>
<option value="four" selected>four</option>
<option value="five">five</option>
<option value="six">six</option>
<option value="seven">seven</option>
</select>
<select id="s2" onchange="onch()">
<option value="ones">ones</option>
<option value="twos">twos</option>
<option value="threes">threes</option>
<option value="fours" selected>fours</option>
<option value="fives">fives</option>
<option value="sixs">sixes</option>
<option value="sevens">sevens</option>
<option value="eights">eights</option>
<option value="nines">nines</option>
<option value="tens">tens</option>
</select>
<br />
<pre id="res"></pre>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-74105773400656083422013-01-14T11:22:00.001-08:002013-01-14T11:23:06.952-08:00The long journey from character to AST... begins elsewhere<script type="text/javascript">
function Color(num, identifier, operator, end) {
this.num = num;
this.identifier = identifier;
this.operator = operator;
this.end = end;
}
</script>
<script type="text/javascript">
function End() {
}
End.prototype.match = function(that) {
return that instanceof End;
}
End.prototype.toString = function() {
return "END";
}
End.prototype.toHTML = function(c) {
return '<span style="color:' + c.end + '">END</span>';
}
</script>
<script type="text/javascript">
function Environment(container) {
this.container = container;
}
Environment.prototype.toString = function() {
var ret = 'Environment(';
for(var i in this.container)
ret += i + ' ' + this.container[i] + '\n';
return ret + ')';
}
</script>
<script type="text/javascript">
function Exp(operand, operator) {
this.operand = operand;
this.operator = operator;
}
Exp.prototype.evaluate = function(env) {
var acc = this.operand[0].evaluate(env);
for(var i=1;i<this.operand.length;i++)
if(this.operator[i-1].match(new Operator('+'))) acc += this.operand[i].evaluate(env);
else acc -= this.operand[i].evaluate(env);
return acc;
}
Exp.prototype.toString = function() {
var ret = 'Exp(';
ret += this.operand[0].toString();
for(var i=1;i<this.operand.length;i++)
ret += ' ' + this.operator[i-1].s + ' ' + this.operand[i].toString();
ret += ')';
return ret;
}
</script>
<script type="text/javascript">
function Identifier(name) {
this.name = name;
}
Identifier.prototype.match = function(that) {
return that instanceof Identifier;
}
Identifier.prototype.toString = function() {
return 'Identifier(' + this.name + ')';
}
Identifier.prototype.toHTML = function(colour) {
return '<span style="color:' + colour.identifier + '">' + this.name + '</span>';
}
</script>
<script type="text/javascript">
function IterableString(s) {
this.s = s; //the wrapped string
this.pointer = 0; //keeps track of our current position
this.marker = 0; //helps with
}
IterableString.prototype.adv = function() {
//advances the current position
this.pointer++;
}
IterableString.prototype.setMarker = function() {
//updates the marker
this.marker = this.pointer;
}
IterableString.prototype.cur = function() {
//get the current character
return this.s.charAt(this.pointer);
}
IterableString.prototype.next = function() {
//get the next character
return this.s.charAt(this.pointer + 1);
}
IterableString.prototype.hasNext = function() {
//are there any more characters?
return this.pointer < this.s.length;
}
IterableString.prototype.getMarked = function() {
//get the substring form marker to the current position
return this.s.substring(this.marker, this.pointer);
}
IterableString.prototype.match = function(str) {
//checks if str matches s starting from the current position
if(this.s.substring(this.pointer, this.pointer + str.length) == str) {
this.pointer += str.length;
return true;
}
return false;
}
IterableString.prototype.toString = function() {
var ret = 'IterableString(pointer: ' + this.pointer
+ ', marker: ' + this.marker
+ ', content: [' + this.token.join(', ') + ']';
}
</script>
<script type="text/javascript">
function Num(s) {
this.val = parseFloat(s);
}
Num.prototype.match = function(that) {
return that instanceof Num;
}
Num.prototype.toString = function() {
return 'Num(' + this.val + ')';
}
Num.prototype.toHTML = function(colour) {
return '<span style="color:' + colour.num + '">' + this.val + '</span>';
}
</script>
<script type="text/javascript">
function Operator(s) {
this.s = s;
}
Operator.prototype.match = function(that) {
if(that instanceof Operator)
return that.s == this.s;
return false;
}
Operator.prototype.toString = function() {
return 'Operator(' + this.s + ')';
}
Operator.prototype.toHTML = function(colour) {
return '<span style="color:' + colour.operator + '">' + this.s + '</span>';
}
</script>
<script type="text/javascript">
function RDP() {
}
RDP.tree = function(t) {
var token = new TokenList(t);
var t = RDP.tree.exp(token);
token.expect(new End(), 'RDP: expression not properly terminated');
return t;
}
RDP.tree.num = new Num();
RDP.tree.identifier = new Identifier();
RDP.tree.exp = function(token) {
// Exp -> Term { ( '+' | '-' ) Term }
var operand = [];
var operator = [];
operand.push(RDP.tree.term(token));
while(token.matchAny([[new Operator('+')], [new Operator('-')]])) {
operator.push(token.next());
operand.push(RDP.tree.term(token));
}
//if there's only one operand then we might as well return it without wrapping it
if(operand.length == 1) return operand[0];
else return new Exp(operand, operator);
}
RDP.tree.term = function(token) {
// Term -> Factor { ( '*' | '/' ) Factor }
var operand = [];
var operator = [];
operand.push(RDP.tree.factor(token));
while(token.matchAny([[new Operator('*')], [new Operator('/')]])) {
operator.push(token.next());
operand.push(RDP.tree.factor(token));
}
//if there's only one operand then we might as well return it without wrapping it
if(operand.length == 1) return operand[0];
else return new Term(operand, operator);
}
RDP.tree.factor = function(token) {
// Factor -> '(' Exp ')' | Value | Variable
if(token.match([new Operator('(')])) {
token.adv();
var tmp = RDP.tree.exp(token);
token.expect(new Operator(')'), 'EDP: Factor: missing ")"');
return tmp;
}
else if(token.match([RDP.tree.num])) {
return new Val(token.next().val);
}
else if(token.match([RDP.tree.identifier])) {
return new Var(token.next().name);
}
else throw 'EDP: Factor: Expected either a number, an identifier or a "("';
}
</script>
<script type="text/javascript">
function Term(operand, operator) {
this.operand = operand;
this.operator = operator;
}
Term.prototype.evaluate = function(env) {
var acc = this.operand[0].evaluate(env);
for(var i=1;i<this.operand.length;i++)
if(this.operator[i-1].match(new Operator('*'))) acc *= this.operand[i].evaluate(env);
else acc /= this.operand[i].evaluate(env);
return acc;
}
Term.prototype.toString = function() {
var ret = 'Term(';
ret += this.operand[0].toString();
for(var i=1;i<this.operand.length;i++)
ret += ' ' + this.operator[i-1].s + ' ' + this.operand[i].toString();
ret += ')';
return ret;
}
</script>
<script type="text/javascript">
function Tokenizer() {
}
Tokenizer.chop = function(s) {
//chop the string of characters into tokens
var str = new IterableString(s + ' ');
var tok = [];
while(str.hasNext()) {
var c = str.cur();
//get an idea of what we're dealing with
//and give control to specialized munchers
if(Tokenizer.chop.isDigit(c)) tok.push(Tokenizer.chop.munchNum(str));
else if(Tokenizer.chop.isIdHeadChar(c)) tok.push(Tokenizer.chop.munchAlphanum(str));
else if(Tokenizer.chop.munchOperator.headList.indexOf(c) != -1) tok.push(Tokenizer.chop.munchOperator(str));
else if(Tokenizer.chop.isWS(c)) str.adv(); //ignore whitespace
else throw 'Illegal character: ' + c;
}
tok.push(new End());
return tok;
}
Tokenizer.chop.isWS = function(c) {
return c == ' ' || c == '\n' || c == '\t';
}
Tokenizer.chop.isDigit = function(c) {
return c >= '0' && c <= '9';
}
Tokenizer.chop.isLetter = function(c) {
return (c >= 'A' && c <= 'Z')
|| (c >= 'a' && c <= 'z');
}
Tokenizer.chop.isIdChar = function(c) {
return c == '_'
|| Tokenizer.chop.isLetter(c)
|| Tokenizer.chop.isDigit(c);
}
Tokenizer.chop.isIdHeadChar = function(c) {
return c == '_' || Tokenizer.chop.isLetter(c);
}
Tokenizer.chop.munchNum = function(str) {
str.setMarker();
//munch digits
while(Tokenizer.chop.isDigit(str.cur()))
str.adv();
//and possibly one '.'
if(str.cur() == '.') {
str.adv();
//and some more digits
while(Tokenizer.chop.isDigit(str.cur()))
str.adv();
}
return new Num(str.getMarked());
}
Tokenizer.chop.munchAlphanum = function(str) {
str.setMarker();
//munch alphanumeric characters
while(Tokenizer.chop.isIdChar(str.cur()))
str.adv();
//alphanumeric stuff can only be variable identifiers here
return new Identifier(str.getMarked());
}
Tokenizer.chop.munchOperator = function(str) {
//create an alias
var list = Tokenizer.chop.munchOperator.list;
for(var i in list)
if(str.match(list[i]))
return new Operator(list[i]);
throw 'Unknown symbol sequence';
}
//list of all operators
Tokenizer.chop.munchOperator.list = ['+','-','*','/','(',')'];
//set of first character of every operator
//consequently these two lists match as we don't have lengthy operators
Tokenizer.chop.munchOperator.headList = ['+','-','*','/','(',')'];
</script>
<script type="text/javascript">
function TokenList(token) {
//token list
this.token = token;
this.pointer = 0;
}
TokenList.prototype.matchAny = function(token) {
for(var i=0;i<token.length;i++)
if(this.match(token[i]))
return true;
return false;
}
TokenList.prototype.match = function(token) {
for(var i=0;i<token.length;i++)
if(!(this.token[this.pointer + i].match(token[i])))
return false;
return true;
}
TokenList.prototype.expect = function(token, exMessage) {
if(this.match([token])) this.adv();
else throw exMessage;
}
TokenList.prototype.adv = function() {
if(this.pointer >= this.token.length)
throw 'TokenList: You\'ve not enough tokens!';
this.pointer++;
}
TokenList.prototype.next = function() {
this.adv();
return this.token[this.pointer - 1];
}
TokenList.prototype.toString = function() {
var ret = 'TokenList(pointer: ' + this.pointer
+ ', content: [' + this.token.join(', ') + ']';
}
</script>
<script type="text/javascript">
function Val(val) {
this.val = val;
}
Val.prototype.evaluate = function(env) {
return this.val;
}
Val.prototype.toString = function() {
return this.val;
}
</script>
<script type="text/javascript">
function Var(name) {
this.name = name;
}
Var.prototype.evaluate = function(env) {
if(!env.container.hasOwnProperty(this.name))
throw 'Interpreter: ' + this.name + ' was not declared in the Environment';
return env.container[this.name];
}
Var.prototype.toString = function() {
return this.name;
}
</script>
<!-- ======================= -->
<script type="text/javascript">
setTimeout(process, 200);
function process() {
var hExpIn = document.getElementById('rdp_exp_in');
var hEnvIn = document.getElementById('rdp_env_in');
var hOut = document.getElementById('rdp_out');
var expIn = hExpIn.value;
var envIn = hEnvIn.value;
var out = '';
try {
var t = Tokenizer.chop(expIn);
out += 'Tokens:\n-------\n' + t.join(', ') + '\n\n';
var a = RDP.tree(t);
out += 'AST:\n----\n' + a.toString() + '\n\n';
var env = new Environment(JSON.parse(envIn));
out += 'Result:\n-------\n' + a.evaluate(env);
}
catch(err) { out += err; }
hOut.value = out;
}
</script>
<p>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.</p>
<p>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!</p>
<p>If you want to find out more about the inner workings of this nifty thing, check this very nicely written article on <a href="http://www.codeproject.com/Articles/523097/The-long-journey-from-character-to-AST">CodeProject</a>.</p>
<div>
Your input code:
<br />
<textarea id="rdp_exp_in" onkeyup="process()" rows="2" cols="50">7 + pi * (x - 10)</textarea>
<br />
The environment:
<br />
<textarea id="rdp_env_in" onkeyup="process()" rows="5" cols="50">{
"x" : 5,
"pi" : 3
}</textarea>
<br />
Output:
<br />
<textarea id="rdp_out" rows="14" cols="50"></textarea>
</div>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-12954864326008152112012-12-29T09:53:00.000-08:002012-12-30T09:28:20.657-08:00Melc<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1avIBlsvnpMqpz8VjMHV6J7qhAffx6dGpMLA2r5KsdwFf4NZpGyud7GOTv8bVWf9a7F8vh1UeVx124LGitbODmbVgsshIWQT-1_N4Y4AwFvtrrMlnY1YGB_i3rbwtGWJk7zhJcKEZJUk/s1600/melc_scrshot3.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1avIBlsvnpMqpz8VjMHV6J7qhAffx6dGpMLA2r5KsdwFf4NZpGyud7GOTv8bVWf9a7F8vh1UeVx124LGitbODmbVgsshIWQT-1_N4Y4AwFvtrrMlnY1YGB_i3rbwtGWJk7zhJcKEZJUk/s1600/melc_scrshot3.png" /></a></div>
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.<br />
<br />
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 <a href="https://github.com/madflame991/melc">GitHub</a>. I'm going to go on developing this and writing more examples in the year to come.<br />
<div>
<br /></div>
madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com1tag:blogger.com,1999:blog-1014704324335955392.post-70253488702449138092012-11-19T00:23:00.002-08:002012-11-19T00:23:37.808-08:00Petri dish partyHere's a seak peek of what I'm working on<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRNOibkJwEW1QAUU3xzfjuqPo7YbTXyEv_-aEDV3hqUhrqs7vfgGFapCr7LFYBRK5MPrm6hTCFWIRVg_3FcioIcHBy34oiK9wN9Y2X1IJ9s_45Y5GUECJUoCjalGZg8iG9TF3taU81Udc/s1600/furryanimals_scrshot_1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="499" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRNOibkJwEW1QAUU3xzfjuqPo7YbTXyEv_-aEDV3hqUhrqs7vfgGFapCr7LFYBRK5MPrm6hTCFWIRVg_3FcioIcHBy34oiK9wN9Y2X1IJ9s_45Y5GUECJUoCjalGZg8iG9TF3taU81Udc/s640/furryanimals_scrshot_1.png" width="640" /></a></div>
madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-88205395754293981072012-11-17T13:26:00.000-08:002013-08-11T04:39:09.013-07:00Amandine<script type="text/javascript">
/*
Copyright 2012 Adrian Toncean
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
Rule = function(left, right) {
this.left = left;
this.right = right;
}
Rule.fromStr = function(s) {
var pSep = s.indexOf('->');
var left = new RegExp(s.substr(0,pSep).trim(),'');
var right = s.substr(pSep+2).trim();
return new Rule(left, right);
}
RuleSet = function(rule) {
this.rule = rule;
}
RuleSet.fromStr = function(s) {
var rule = [];
var ar = s.split('\n');
var tmp;
var i;
for(i in ar) {
tmp = ar[i].trim();
if(tmp.length > 0)
if(tmp.charAt(0) != ';')
rule.push(Rule.fromStr(tmp));
}
return new RuleSet(rule);
}
function applyRule(s, rule) {
return s.replace(rule.left, rule.right);
/* //will give infinite loop if used like this
var tmp = s.match(rule.left);
if(tmp != null) {
console.log(tmp);
var found = tmp[0];
var right = rule.right.replace(/\!/g, found);
return s.replace(found, right);
}
return s;
*/
}
function step(s, ruleSet) {
var right, found;
var os;
var changed;
var i;
for(i in ruleSet.rule) {
changed = true;
while(changed) {
os = s;
s = applyRule(s, ruleSet.rule[i]);
changed = (os != s);
}
}
return s;
}
function compute(startString, ruleSet, maxIter) {
var changed = true;
var i = 0;
var os;
var s = startString;
while(changed && i < maxIter) {
i++;
os = s;
s = step(s, ruleSet);
changed = (s != os);
}
return s;
}
function do_compute() {
var startString = document.getElementById('inp_startString').value;
var ruleSetString = document.getElementById('inp_ruleSet').value;
var maxIter = 10000;
try {
var ruleSet = RuleSet.fromStr(ruleSetString);
var result = compute(startString, ruleSet, maxIter);
document.getElementById('out_result').value = result;
} catch(err) {
document.getElementById('out_result').value = err;
}
}
</script>
Rewriting rules:<br />
<textarea id="inp_ruleSet" rows="10" cols="50">
21 -> 12
31 -> 13
32 -> 23
</textarea>
<br />
<br />
Input string:<br />
<input id="inp_startString" type="text" value="21321311232133" size="60"><br /><br />
Output string:<br />
<input id="out_result" type="text" value="" size="60" readonly="readonly"><br />
<input type="button" value="Rewrite!" onclick="do_compute();">
<br />
<br />
Amandine is a string-rewriting system.<br /><br />
The input given is rewritten accoding to the specified rules.
This is how the process goes:<br />
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 <span style="font-family:monospace;background-color:#DDD;font-weight:bold">source -> replacement</span> where <span style="font-family:monospace;background-color:#DDD;font-weight:bold">source</span> is a JavaScript regular expression and <span style="font-family:monospace;background-color:#DDD;font-weight:bold">replacement</span> is a normal string.
Lines that start with a <span style="font-family:monospace;background-color:#DDD;font-weight:bold">;</span> are ignored.<br />
<br />
The default example shows how sorting a sequence of numbers is possible.madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com2tag:blogger.com,1999:blog-1014704324335955392.post-45996582954882768242012-10-07T01:27:00.000-07:002013-08-11T04:39:36.320-07:00OpenCL Experiments<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiB_FcbFxaOTPmAPErC9VBh8ZjYo2distzAJX9XsHe9s65jANaqzzw5PDAfCG4JJf-VFD9Xak_AeKTTmFSTrACRJ-WWyiPE09AveDPDvhIOkru4YB9OcBrekQJ6WVi9Gkxb41imKUYPXns/s1600/oclex_papso.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiB_FcbFxaOTPmAPErC9VBh8ZjYo2distzAJX9XsHe9s65jANaqzzw5PDAfCG4JJf-VFD9Xak_AeKTTmFSTrACRJ-WWyiPE09AveDPDvhIOkru4YB9OcBrekQJ6WVi9Gkxb41imKUYPXns/s200/oclex_papso.png" width="192" /></a></div>
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 <a href="https://github.com/madflame991/oclex">Github</a>. Here's what I have so far:<br />
<br />
<ul><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDSYWxzjQhRrKxhC2IwGlF4OKAPWvhiLcRYvezk16xRJeyummqOlctVYvhRS3gqvX-TY_AwiluNk6Wdm314NxIEZQdCJCsXlIPva80d0sDYwIlkeH33NVQ8Dtm-IVJeZrr5BEBQ7SZb6g/s1600/oclex_shadow.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="249" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDSYWxzjQhRrKxhC2IwGlF4OKAPWvhiLcRYvezk16xRJeyummqOlctVYvhRS3gqvX-TY_AwiluNk6Wdm314NxIEZQdCJCsXlIPva80d0sDYwIlkeH33NVQ8Dtm-IVJeZrr5BEBQ7SZb6g/s320/oclex_shadow.png" width="320" /></a>
<li><b>Simulation of repulsive particles</b> - 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.</li>
<li><b>Hillclimbing!</b> - 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).</li>
<li><b>Particle Swarm Optimization (actually Parallel Asynchronous PSO)</b> - I've already covered PSO in this <a href="http://madflame991.blogspot.se/p/particle-swarm-optimization-demo-1.html">online demo</a> and extensively in my Bachelor's graduation thesis and <a href="http://madflame991.blogspot.se/2012/07/global-optimization-to-max.html">Gloptat</a>. 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.</li>
<li><b>Shadow demo</b> - 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.</li>
</ul>
madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-21302830826912187662012-09-04T00:53:00.000-07:002012-09-04T00:53:03.814-07:00RU gets reflection, GOAT gets full benchmarking functionality<b>RU</b><br />
+ added instruction for sending commands to the other Executor. Executors can now control each other.<br />
+ added instructions for telling the other Executor to place or erase instructions on the "playfield"<br />
+ added a much needed instruction for synchronizing Executors<br />
<br />
Now that the language is reflective it's probably even harder to make a compiler for it than for Befunge.<br />
Check it out here: <a href="http://madflame991.blogspot.se/p/ru-online-interpreter.html">http://madflame991.blogspot.se/p/ru-online-interpreter.html</a><br />
<br />
<b><br /></b>
<b>GOAT</b><br />
+ separated the application into 2 parts: one for visualising how simulations advance and one for benchmarking which launches simulations in parallel and outputs much more detailed results (output in CSV, XML and JSON formats are in the making)<br />
+ added proper classes for intervals and function domains<br />
* streamlined some sections<br />
<br />
Check it out on GitHub: <a href="https://github.com/madflame991/gloptat">https://github.com/madflame991/gloptat</a>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-91744327972434058742012-09-02T03:06:00.000-07:002013-08-11T04:40:08.061-07:00Homo Vermes for LD #24<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEieRoAIFP8ZYWqICV4JQHFx5o87UxFG2TAqY0ZF7jFhJBUe2CXjsmC1sSL3AQdnkWBTr8Bowk9_Wc2EQX9FpzYKi96UXwHDmW2yT6V-LQ3xDL_cHrng_qj_bB2-sSmbXcwpZRf3Raioock/s1600/jim_teaser01.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEieRoAIFP8ZYWqICV4JQHFx5o87UxFG2TAqY0ZF7jFhJBUe2CXjsmC1sSL3AQdnkWBTr8Bowk9_Wc2EQX9FpzYKi96UXwHDmW2yT6V-LQ3xDL_cHrng_qj_bB2-sSmbXcwpZRf3Raioock/s1600/jim_teaser01.png" /></a></div>
<i>Evolution</i> was finally voted for this LD event.<br />
My entry is called Homo Vermes and it's something between Pipe Mania and Entanglement<br />
<br />
Check the entry here: <a href="http://www.ludumdare.com/compo/ludum-dare-24/?action=preview&uid=5035">http://www.ludumdare.com/compo/ludum-dare-24/?action=preview&uid=5035</a><br />
...and play it here: <a href="http://madflame991.blogspot.se/p/homo-vermes.html">http://madflame991.blogspot.se/p/homo-vermes.html</a>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-13367657691487811252012-08-22T23:16:00.000-07:002013-08-11T04:40:08.058-07:00LD coming up - particles activate!<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiHsLu6MMDgWVW3hl8jH6xXzgVUEP4pKHTs2dZ3wPuKYrvDlRr3Koooq0yGf1n_Rpip4blXWbc131mlfAHRqPt4EtJO8l5hVkxDqxBiJbQFb_nm0nkivfYg0vTrvkn7VKbqjTqGV0XLTwE/s1600/particlejs_scrshot2.png" imageanchor="1" style="clear: left; display: inline !important; float: left; margin-bottom: 1em; margin-right: 1em; text-align: center;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiHsLu6MMDgWVW3hl8jH6xXzgVUEP4pKHTs2dZ3wPuKYrvDlRr3Koooq0yGf1n_Rpip4blXWbc131mlfAHRqPt4EtJO8l5hVkxDqxBiJbQFb_nm0nkivfYg0vTrvkn7VKbqjTqGV0XLTwE/s400/particlejs_scrshot2.png" width="362" /></a></div>
In less than 48 hours a new LD begins and this time I've prepared a little library/framework for particle systems.<br />
<br />
After seeing an awesome <a href="http://www.youtube.com/watch?v=Fy0aCDmgnxg">speech</a> by Martin Jonasson and Petri Purho I am now convinced that there can never be too many particles on the screen. They're mesmerizing, fun to program and make your game <b>JUICY</b>.<br />
I've implemented 7 types of particles and 3 types of emitters, but as I use it I'll add more.<br />
<br />
Still, screenshots don't do this justice so check the thing in action --> <a href="http://madflame991.blogspot.com/p/particle-systems.html">link</a>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-18783284967220902602012-08-04T01:57:00.000-07:002012-08-04T02:00:35.607-07:00Lindenmayer power update<div class="" style="clear: both; text-align: left;">
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEidrFhzuZ4PaC3Lb0VXSEywDrWwytRxktG2pF5BrLar9zSoeMPQtT26Yib2VUm39Tg3prtfijJYpQw80bWeFtaMNZ5TdwZSTaJcigJ25fovlnwSL92XNCdZAULvOtFdh2z_6mih3ca_8Oo/s1600/binarytreec.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEidrFhzuZ4PaC3Lb0VXSEywDrWwytRxktG2pF5BrLar9zSoeMPQtT26Yib2VUm39Tg3prtfijJYpQw80bWeFtaMNZ5TdwZSTaJcigJ25fovlnwSL92XNCdZAULvOtFdh2z_6mih3ca_8Oo/s320/binarytreec.png" width="320" /></a></div>
Here's an update for Lindenmayer power! I've rewritten the whole thing and switched from simple context-free grammars to stochastic context-free grammars. The turtle commands have been streamlined and I've also added some new commands. Now you can change the colour of the lines, their thickness and you draw little squares and text.<br />
Link --> <a href="http://madflame991.blogspot.ro/p/lindenmayer-power.html">http://madflame991.blogspot.ro/p/lindenmayer-power.html</a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-75111750777799255662012-07-27T06:00:00.001-07:002012-08-04T01:58:51.031-07:00Hello Tarflex, RU gets updated and wiki page on EsolangFirst of all, I'd like to introduce you to <a href="http://madflame991.blogspot.ro/p/tarflex.html">Tarflex</a>. It's a reflective Turing tarpit. In short the whole program is treated as a list of lists consisting of simple instructions, and some of these instructions can perform operations on the lists.<br />
<br />
And second of all, I've added the ability to export <a href="http://madflame991.blogspot.ro/p/ru-online-interpreter.html">RU</a> programs as HTML tables or Wiki tables.<br />
RU has also made it on <a href="http://esolangs.org/wiki/Main_Page">Esolang</a> - probably the best resource for esoteric programming languages --> <a href="http://esolangs.org/wiki/RU">link</a><br />
<br />
Here's an HTML table!<br />
<table cellpadding="0" cellspacing="1" style="color: white; font-family: monospace; font-size: 150%; font-weight: bold;"><tbody>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #00856a;">>></span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #00856a;">++</span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #00856a;"><<</span></td><td><span style="background-color: #8db500;"><<</span></td><td><span style="background-color: #8db500;"><<</span></td><td><span style="background-color: #8db500;">++</span></td><td><span style="background-color: #005869;"> <</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> ></span></td><td><span style="background-color: #005869;"> ></span></td><td><span style="background-color: #00856a;"><<</span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #00856a;"> +</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #8db500;"><<</span></td><td><span style="background-color: #00856a;"> +</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #8db500;"> +</span></td><td><span style="background-color: #00856a;">>></span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #00856a;"> -</span></td><td><span style="background-color: #00856a;"><<</span></td><td><span style="background-color: #00856a;"><<</span></td><td><span style="background-color: #005869;"> <</span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> ></span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #00856a;"> -</span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #00856a;"> +</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #00856a;">>></span></td><td><span style="background-color: #00856a;"> -</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> ^</span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #00856a;">--</span></td><td><span style="background-color: #00856a;">>></span></td><td><span style="background-color: #005869;"> v</span></td><td><span style="background-color: #8db500;"> #</span></td><td><span style="background-color: #8db500;">>></span></td><td><span style="background-color: #005869;"> <</span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #005869;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
<tr><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td><td><span style="background-color: #574365;"> </span></td></tr>
</tbody></table>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-58531979122949750922012-07-21T04:40:00.001-07:002012-08-04T02:00:44.527-07:00RU online interpreter is up and running<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnMd2K5g6vM60p_GqRbQ_LzEXvHLyyF6keo7HEMj4N4WEpM_6KYVX1Lap-EGL3hFZZtxdYMVsnUHvIi78Oq_t4ZN_ReV8zBJoA0cB-JqqDYRto6GHABiGYDhOcV9ao547FgczMNQZDl1s/s1600/robotunlock.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnMd2K5g6vM60p_GqRbQ_LzEXvHLyyF6keo7HEMj4N4WEpM_6KYVX1Lap-EGL3hFZZtxdYMVsnUHvIi78Oq_t4ZN_ReV8zBJoA0cB-JqqDYRto6GHABiGYDhOcV9ao547FgczMNQZDl1s/s1600/robotunlock.png" /></a></div>
It's been almost 2 years since I devised <a href="http://madflame991.blogspot.com/search/label/robotunlock">Robot Unlock</a>. Due to the <a href="http://jayisgames.com/archives/2011/07/robot_unlock.php">positive feedback</a> and seeing how people shared solutions for levels online I thought Robot Unlock is a fun toy language and deserves more development. That is why I have made an <a href="http://madflame991.blogspot.ro/p/ru-online-interpreter.html">online interpreter</a> for the language. You can program in it and share your marvels with others.<br />
<br />
In the future I will add more instruction sets (some more expressive, some more restrictive and some quirky ones too).<br />
<br />
Mudboy salutes you!madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-84708094230154826252012-07-14T08:36:00.002-07:002012-08-04T02:00:53.252-07:00From Under the Rock<span style="background-color: white;">This is my entry for miniLD #36 (Contrast)</span><br />
Download link for Windows/Linux/OSX + Source: <a href="http://gamejolt.com/open-source/games/other/from-under-the-rock/8666/">http://gamejolt.com/open-source/games/other/from-under-the-rock/8666/</a><br />
Explore, listen, see, taste.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqetR2jXFKMGMEEI05_WU3agezL6LNI6aziNUyJ3p7pnpY8lB_DFJLdDXEChwgFufQRajiYmrLeh4tEz7tpl1xrsI2EBvRnv9gtle_RlIds5hZyGr2y4xw0fLiwC6GeAE-iSZqGJrRaA8/s1600/fromundertherock_scrshot2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="454" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqetR2jXFKMGMEEI05_WU3agezL6LNI6aziNUyJ3p7pnpY8lB_DFJLdDXEChwgFufQRajiYmrLeh4tEz7tpl1xrsI2EBvRnv9gtle_RlIds5hZyGr2y4xw0fLiwC6GeAE-iSZqGJrRaA8/s640/fromundertherock_scrshot2.png" width="640" /></a></div>
<br />madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-8047547421272278652012-07-02T11:52:00.000-07:002012-08-04T01:58:20.476-07:00Global Optimization to the max!<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzv9RX9KfLTiPeV4n0D26l5209B9ZYsQecZnPxe0jZEXhgvWIYbSxY9eB6t9FiTAaVDEbUNNiE4vGpyndoHyi6czOF1uX95lY8x9XTK_lIq2RMbq7pDRAgTQFqSO7jwFd01UahWv0VkA/s1600/goat_scrshot1.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzv9RX9KfLTiPeV4n0D26l5209B9ZYsQecZnPxe0jZEXhgvWIYbSxY9eB6t9FiTAaVDEbUNNiE4vGpyndoHyi6czOF1uX95lY8x9XTK_lIq2RMbq7pDRAgTQFqSO7jwFd01UahWv0VkA/s400/goat_scrshot1.png" width="400" /></a></div>
GOAT, or Global Optimization AT is a framework/sandbox for testing of global optimization algorithms. I've started tinkering with optimization algorithms back in feb 2011 and this whole thing ended up becoming my bachelor's thesis. Now I think the project is mature (ok, it still needs some tidying up) and modular enough so that others can build on it too. That's why I have released it under the GNU GPL on GitHub. <a href="https://github.com/madflame991/gloptat">https://github.com/madflame991/gloptat</a><br />
<br />
Thus far its main components are:<br />
<ol>
<li>A function plotter to see how objective functions look like and why they're so much of a challenge. It also points out where candidate solutions are at every iteration in the search space</li>
<li>Basic benchmarking features - so that one can compare the performance of different algorithms</li>
<li>An implementation of Genetic Algorithms and many variations</li>
Here's a list of operators and variations implementd thus far:<br />
<br />
<ul>
<li><b>[Standard stuff]</b><br />
Tournament and Roulette wheel selection<br />
Singlepoint, 2-point and uniform crossover<br />
Uniform mutation<br />
</li>
<br />
<li><b>[Not so standard stuff]</b><br />
Population reduction<br />
Random immigrants<br />
Iversion<br />
</li>
<br />
<li><b>[Unique* as far as I know]</b><br />
Biased crossover (inheriting the significant part of a chromosome from the better parent)<br />
Non-uniform mutation with dynamic parameters<br />
Growth (a hillclimbing step each generation)<br />
Some methods to adjust selection pressure at runtime ("Damping functions")<br />
<br />
*I haven't found any mention of the last 4 variations. As far as I know they're my original contributions, but I'm sure someone else interested in the field has thought of them already and documented these...<br /><br />
</li>
</ul>
<li>
An inplementation of the Particle Swarm Optimization algorithm and variations.<br />
Here are some features implemented for PSO:<br />
<br />
<ul>
<li>Nighbour networks</li>
<li>Population reduction</li>
<li>Random immigrants</li>
</ul>
</li>
</ol>
<hr />
...and here's a list of things I'm planning to implement:<br />
<ol>
<li>
Split the application in 2 parts: one entitled "demo mode" - this should be used to see how the simulation progresses with fancy 3D graphics and one entitled "benchmark mode" for well... benchmarking. It will probably run simultaneous jobs to minimize the time it takes to benchmark
</li>
<li>
Add more objective functions
</li>
<li>
Add more optimization algorithms
</li>
</ol>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-77615138061288005012012-06-24T09:05:00.000-07:002012-08-04T02:00:26.974-07:00Elementary cellular automata simulator<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaIawiZWaEsNoQHQkCVmqUcInfsn03jDyqFwCB4MA7Q8m_05VHsCzgL3nGf2SKWvZ6JJFLZYbZpfQq5g7Xzh_0rG0LDk2U5k1TaZ5sPNyXVz3cTnX1oDds51XrL7o1kwhqOaqLzOqh0YI/s1600/scrshot_cell1d.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaIawiZWaEsNoQHQkCVmqUcInfsn03jDyqFwCB4MA7Q8m_05VHsCzgL3nGf2SKWvZ6JJFLZYbZpfQq5g7Xzh_0rG0LDk2U5k1TaZ5sPNyXVz3cTnX1oDds51XrL7o1kwhqOaqLzOqh0YI/s320/scrshot_cell1d.png" width="280" /></a></div>
Here's a little 1D cellular automata simulator:<br />
<a href="http://madflame991.blogspot.com/p/elementary-cellular-automata-and-more.html">http://madflame991.blogspot.com/p/elementary-cellular-automata-and-more.html</a>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-51584066783673254532012-05-21T00:41:00.000-07:002012-08-04T02:01:12.793-07:00Sword and Circle for miniLD 34<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.ludumdare.com/compo/wp-content/compo2/thumb/a8dc7e8481bdf5771915611fe9d90936.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="320" src="http://www.ludumdare.com/compo/wp-content/compo2/thumb/a8dc7e8481bdf5771915611fe9d90936.jpg" width="320" /></a></div>
I managed to participate in the miniLD this weekend and I came up with the game you can see in the image here. It's a simple tactical game with swords and circles. Surprisingly enough, I also managed to pass all my exams...<br />
And speaking of LD, it came as a nice surprise that <a href="http://www.ludumdare.com/compo/ludum-dare-23/?uid=5035">my LD23 entry</a> came in 22nd in the Humor category, out of 1072 submissions. That means I'm in the top 2%, which is awesome!<br />
<br />
Play Sword and Circle game here: <a href="http://madflame991.blogspot.com/p/sword-and-circle.html">http://madflame991.blogspot.com/p/sword-and-circle.html</a><br />
<br />
Link to Sword and Circle LD submission: <a href="http://www.ludumdare.com/compo/minild-34/?action=preview&uid=5035">http://www.ludumdare.com/compo/minild-34/?action=preview&uid=5035</a>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-64145652163806788552012-04-24T00:25:00.000-07:002012-08-04T02:01:12.794-07:00Space Bear is up and running<b><i>"Flying around a bear-head with 6 stars trailing behind it is quite a sight."</i> Ergo</b><br />
<br />
I've managed to upload the game to this blog (which was pretty tedious having in mind Bloggers' limitations...). So instead of downloading the game from GameJolt (which is currently offline) you can play it here --> <a href="http://madflame991.blogspot.com/p/space-bear.html">http://madflame991.blogspot.com/p/space-bear.html</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgxyIqjRUsEUBEVijW_b4AuJOP7rgItGH2mMr1uuy0gPwI-mVzhnllv7azdWu7U98zWCDHiPsbqMSP3Xxhg2kC-ROwhG-JHJlBUc7R0Eel-n_gBbR-K_sIViao5zVkg43nJORB0vl0Mw_g/s1600/Spacebear_scrshot2.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgxyIqjRUsEUBEVijW_b4AuJOP7rgItGH2mMr1uuy0gPwI-mVzhnllv7azdWu7U98zWCDHiPsbqMSP3Xxhg2kC-ROwhG-JHJlBUc7R0Eel-n_gBbR-K_sIViao5zVkg43nJORB0vl0Mw_g/s1600/Spacebear_scrshot2.png" /></a></div>
<br />madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0tag:blogger.com,1999:blog-1014704324335955392.post-71698534713151613782012-04-22T10:41:00.001-07:002012-08-04T02:01:12.796-07:00Space Bear - my LD23 submission and 10th released gameFor now I'm just going to post a screenshot and a download link. I'll upload the game to the blog as quick as I can...<br />
Download from --> <a href="http://gamejolt.com/open-source/games/space-bear/files/space-bear/download/7747/9813/">http://gamejolt.com/open-source/games/space-bear/files/space-bear/download/7747/9813/</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg84BjeGgP-Hm1sh4cQc9Oggf3fJc6gLqVvfnokKLNY_ry-q8x8fM_ZQGlxDiaIQ-DqFVlqdIy7ltAXy8xnoiLM2FfgIX7TknDbwElB2URdcyer8cnaDWF-uF4_Tx6c0rd0c0u41MrJUP8/s1600/Spacebear_scrshot1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg84BjeGgP-Hm1sh4cQc9Oggf3fJc6gLqVvfnokKLNY_ry-q8x8fM_ZQGlxDiaIQ-DqFVlqdIy7ltAXy8xnoiLM2FfgIX7TknDbwElB2URdcyer8cnaDWF-uF4_Tx6c0rd0c0u41MrJUP8/s1600/Spacebear_scrshot1.png" /></a></div>
<br />madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com1tag:blogger.com,1999:blog-1014704324335955392.post-85656768854037981582012-04-15T02:48:00.000-07:002012-08-04T01:58:20.478-07:00Functions meet Particle Swarm Optimization, Gears meet Update, LD 10 year anniversary<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhO-Pa9ze4POClc84hh7DK7Sp7b_1ktmcjoCIjFa47cW9Bt4T62gQKbYGtxTrZ2T4fOKd_hp47aHk5sRjxtXca0WkDNfpzT9tbSEmvhn3fsCu8DPcdZbJu03KjZApNuZR3u4jO4oXvCbko/s1600/gearsshot2.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhO-Pa9ze4POClc84hh7DK7Sp7b_1ktmcjoCIjFa47cW9Bt4T62gQKbYGtxTrZ2T4fOKd_hp47aHk5sRjxtXca0WkDNfpzT9tbSEmvhn3fsCu8DPcdZbJu03KjZApNuZR3u4jO4oXvCbko/s320/gearsshot2.png" width="320" /></a><br />
I've posted a little demo showing a Particle Swarm Optimization algorithm in action. Check it out <a href="http://madflame991.blogspot.com/p/particle-swarm-optimization-demo-1.html">here</a>!<br />
<br />
...and I've also updated the "<a href="http://madflame991.blogspot.com/p/more-gears.html">More Gears</a>" thingie. It now supports gears that orbit other gears and I've added examples to go with this.<br />
<br />
And in other news, <a href="http://ludumdare.com/compo/">Ludum Dare</a> 23 is coming up between April 20th - 23rd and it's going to be big since it's the 10 year anniversary edition. Woohoo!<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWyl_540T3aLM5p7ckTacaGxEtwan7ekyg8VTmWhKFVrEYlwbp8toO-Ig-tzzEbutU-v3fRFaJeeHKeZc9xVZNrivNU4t4LSaakVJJwDcBSzWn-DVr5jQ3EBoXWU9Y9zL-c_1QqWjoRmM/s1600/psojs1_schrshot1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="216" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWyl_540T3aLM5p7ckTacaGxEtwan7ekyg8VTmWhKFVrEYlwbp8toO-Ig-tzzEbutU-v3fRFaJeeHKeZc9xVZNrivNU4t4LSaakVJJwDcBSzWn-DVr5jQ3EBoXWU9Y9zL-c_1QqWjoRmM/s640/psojs1_schrshot1.png" width="640" /></a></div>madflame991http://www.blogger.com/profile/07175729945286341757noreply@blogger.com0