M635 J520

In this post I'll explore and benchmark some simple dynamic programming concepts in Python. The example I'll use is a classic recursive implementation of the fibonacci series . (And for simplicity I'll skip the first element in the series (fib(0)=0).) Naive approach  This implementation: ...works well (enough) for small numbers: but becomes impossibly slow quickly... ...since it has a time complexity of O(2 n ). (So our seemingly harmless fib(42) would result in more than 4 trillion calls to fib... (Or about 4 times the number of bacteria on the human body... Or 2 times the number of galaxies in the observable universe... Or more than the estimated population of fish in the ocean... Etc.)) Enter dynamic programming Since the result of these recursive calls to fib are all deterministic, we can cache the results instead of recalculating them. @functools.cache First a test by simply leveraging the cache in the library functools ... This speeds, as expected, the runtime up si...

The new visual identity of my work place (and the re-ignition of an old lava lamp) made me think of the good old metaballs from the Amiga demo-scene of yonder and how it has been a while since I have implemented them from scratch. This time I wanted to play around with Python and numpy to see what that could bring. But first, what are metaballs?  It's, for example, this: Wikipedia defines them as: In computer graphics, metaballs are organic-looking n-dimensional isosurfaces, characterised by their ability to meld together when in close proximity to create single, contiguous objects. https://en.wikipedia.org/wiki/Metaballs As cool as multidimensional metaballs are, we'll stick to 2D ones in this post. The algorithm The algorithm behind them is quite straightforward -- in their simplest form. Basically for each pixel in each frame, or buffer, you add up the influence of each metaball in the simulation and then cut off below a certain threshold and normalize what’s left. The...

Inspired by the discovery of the API for the BoardGameGeek website , I decided to play around with some of its data by some Ruby and JavaScript scripting. One thing I wanted to look at was the interconnectedness of game mechanics, but first I wanted to find alternative ways to look at how to measure ones "use" of ones game collection, and the associated question of "can a board game collection ever be too big?". H-index and play per game For example, the concept of H-index  is being discussed quite a bit on the ’geek. In short this entails sorting your games by number of plays and finding the last entry in the list with a number of plays higher than (or equal to) the position in the list. It’s rank is your H-index. (This does, of course require one to  meticulously  log ones plays, but that is another story… For example my overall BGG H-index for the last 12 months is (or seems to be) a measly 5.) Another concept used is to take the number og games owned an...

Marché de La Rochelle HDR  Probably about two years ago - when taking Andrew Ng's excellent "Machine Learning" MOOC, Johannes sent me a piece of JavaScript that populated the video lists with overall time per lesson just by pasting it into the URL-thingy in Chrome. Magic. Today when I sat down to start the course on "General Game Playing" that I have signed up for, but, alas, not (yet) found much time for, I thought of that piece of code and wondered if I, with my new knowledge of JavaScript, could whip up something like that. (Also I couldn't find Johannes' original one.) I quickly hacked together something this afternoon over a flat white in a hipster cafe here in Lyon. And lo and behold it worked. Then I extended the functionality to also show minutes and seconds of unwatched video - as well as total overall counters for the entire course. Now each lesson heading reads "Lesson N - Name [time remaining/total time]" instead of just ...

Yesterday I stumbled upon a very useful tool while (trying to) teach(ing) myself D3, namely http://bl.ocks.org . This lets you access, and preview, your webby gists in a browser - just by browsing to http://bl.ocks.org/<gist-id>. Most handy! (The only minor down side is that there seems to be a slight latency if you update your gist before it updates on bl.ocks.org.)

After writing the post a while back on counting in Ruby I wondered if the two different implementations I outlined had similar runtimes. Inspired by this post by makaroni4  I went ahead and wrote the following little "benchmarker": Loading... So, you see the block centered implementation is about 20% faster than my initial one. Interesting.

A while back a friend of mine asked if I could automate the creation of groups in a class of students - to maximize the variation within each group, but minimize the difference between them. This sounded like an interesting problem, so I set about to solve it in my own naive experimental Monte Carlo (inspired) way - without looking into ways this has been solved (surely elegantly) before. The result was this little Ruby script: Loading... First I just require some code I have previously written. (I guess I really should make them into gems or something instead of copying code around...) names.rb  tries to guess sex from a person's name and/or title, and countries.rb  maps countries to continents, regions etc with some fuzzy matching of names. (I'm looking at you Democratic Republic of Kongo,  Koreas  etc.) Easy-peasy. Then I set some standard variables. (Maybe I'll make this dynamic in the future, why not?) The most interesting entry here is the classifiers ...

Reading the Pragmatic Programmer's PragPub from March (I must admit I don't have/take the time to read them regularly enough) I stumbled upon Scala's sliding function on Arrays. This creates a sliding window of consecutive sub arrays of an array. So an  Array(1,2,3,4).sliding(2) would produce an iterator of arrays (1,2), (2,3), and (3,4). Useful! While googling around to see if Ruby has something similar I stumbled across the windowed function in F# that pretty much works the same way, before finding Ruby's each_cons . The first thing I did to test this was to revisit an old (fairly obvious, brute force) seven line Ruby solution (from back in the day when I had just discovered the language) to an Euler problem , and replaced it with the following (admittedly still brute force) one liner (where 'number' is a 1000 character long string containing only numbers): Unlike Scala where you would have the function sliding on string objects, we need to call chars ...

Sometimes I need to get data out of tables buried in PDFs, so I've written a tiny adaptable Ruby hack for when copying and pasting doesn't cut it - exploiting a couple of excellent libraries. Here's an example. Loading... (Admittedly not the most elegant of scripts, but hey! it gets the job done.) What I do first here is just load up the relevant libraries. (The pdf-reader I use is this one: https://github.com/yob/pdf-reader - installable with a simple command line 'sudo gem install pdf-reader' if you are using Ruby 1.9. (Drop the sudo if you're on Windows.)) Next up is to instantiate input pdf and output table. Straight forward enough. By examining the pdf I found the data I was interested in on pages 42 through 69, so a simple call to pages give me those -  pdf_reader . pages [ 42 . . 69 ] . I'll go through the text on each of them line by line and decide if they contain what I want based on regular expressions. These are my simple rules (in th...

Today I wondered how to add nice-looking gists to future posts here on my dynamic themed blog, and found the following solution: http://blog.moski.me/2012/01/gist-with-bloggers-dynamic-views.html  (Thanks Moski.) That's all. Update 10/12/2014: The script has now moved (Ref: https://stackoverflow.com/questions/24005430/moski-gist-blogger-not-loading-gists-in-chrome-for-gists-in-blogger-dynamic-vie ) Update 25/04/2020: This guide is better: https://betterstack.dev/blog/how-to-embed-a-github-gist-in-your-website/ .