Samrat Man Singh

Fighting an N-headed monster with recursion


A while back, I came upon this problem:

“You need to kill an N-headed monster. To do that, you have two swords. The first sword(A) cuts cutA heads, however, in case the monster doesn’t die(ie no. of heads > 0), it will grow growA heads. The second sword works the same way, except that it’ll cut cutB heads and in case the monster is still alive, it’ll grow growB heads. If a sword is used to result in the no. of monster heads being less than 0, you die.”

The problem is to find the shortest combination of swords that can be used to kill the monster(without killing yourself).

This is a paraphrase of the original question(so the question might have sounded a bit awkward). Here’s my solution to it, in Scheme(Racket):

(define cutA 7)
(define growA 3)
(define cutB 5)
(define growB 2)

(define (attack-monster heads)
  (use-sword heads 0 '()))

(define (use-sword n grow s)
  (cond ((< n 0) '())
         ((= n 0)
          (list s))
           (use-sword (- (+ n grow) cutA) growA (append s (list 'a)))
           (use-sword (- (+ n grow) cutB) growB (append s (list 'b)))))))

(define (shortest-way heads)
  (first (sort (attack-monster heads) (lambda (x y) (< (length x) (length y))))))

Here’s how to use it:

> (shortest-way 23)
'(a a a a a)

Thanks to skeeto on Reddit for helping me out with this, and more importantly for not showing me his code :)

Also, I’d love to see how you guys do this in a more efficient and more elegant ways.

A first look at provisioning with Puppet(on a Vagrant box)


In my previous post, I talked about deploying a Flask app on a Vagrant box using Gunicorn and Nginx. The response I got was mind-blowing, so I’ve decided to write about another neat tool that’s awesome for deploying web apps- Puppet. Vagrant actually encourages its users to use it, and you should use it. There’s also an alternative to Puppet called Chef; some people prefer that over Puppet, so you might want to check it out.

Hopefully I’ll be able to demonstrate what Puppet does and why its awesome in this post. But please note that this isn’t meant as a comprehensive tutorial, you should check out Puppet’s docs for that. Also even though the Puppet docs asks you to get the Learning Puppet VM, I found it much more comfortable to use vagrant ssh for learning Puppet, so if you already have Vagraant installed, you might want to try that out too- just try running puppet inside the virtual machine.

What Puppet does is something called provisioning- that means that it makes computers do what they are supposed to do. In other words, it does the configuring for you. To understand what that means, let’s see it in action.

First create a Vagrant box,

mkdir codebase_with_puppet
cd codebase_with_puppet

vagrant init

You should now see Vagrantfile. Open it with a text editor, then uncomment the lines

config.vm.provision :puppet do |puppet|
    puppet.manifests_path = "manifests"
    puppet.manifest_file  = "base.pp"

Now, create base.pp inside a folder called manifests, and add the following to it.

package {"nginx":
    ensure => present,

Now, run vagrant up. You’ll notice that Vagrant automatically installs nginx after it boots the VM. You should get a message like

notice: /Stage[main]//Package[nginx]/ensure: ensure changed 'purged' to 'present'

This can become a real treasure as this way, you won’t have to memorize what you need to install, to get the app running. All the system needs is to have puppet installed, after that puppet with the right manifests will handle everything.

Now, let’s do something different with Puppet- instead of installing another package, we’ll use it to configure nginx.

First, create a file in your local machine, inside codebase_with_puppet called codebase_nginx. To that file add the following

server {
    location / {

If you’ve gone through the previous post you’ll notice that it’s the same configuration that we had used.

Now, we’ll use Puppet to make sure that the configuration file is placed where its supposed to be. To your base.pp file, add

file {"rm-nginx-default":
    path => '/etc/nginx/sites-enabled/default',
    ensure => absent,
    require => Package['nginx'],

file {"setup-nginx-codebase":
    path => '/etc/nginx/sites-enabled/codebase_nginx',
    ensure => present,
    require => Package['nginx'],
    source => "/vagrant/codebase_nginx",

Run vagrant reload and you’re done with the nginx configuration. Besides removing the repetitiveness for you, Puppet is also wonderful when you’re working on a team or on an open-source project. Now, all you need to do is write the manifests and once you share them you can rest assured that the entire team has the exact same environment.

Flask + Nginx + Gunicorn(on a Vagrant box)


I had some difficulty in grasping how exactly to set up a server when I tried to do so recently, so I decided to write a tutorial that will guide you through the process. Hopefully, this post will help you avoid at least some of the confusion that I encountered.

We’ll be using Nginx + Gunicorn to host a simple Flask app. Many of you may not have access to a server but don’t worry, we’ll use Vagrant, which makes use of a VirtualBox VM to emulate a server.

###The Flask App

Because this is a post about deployment more than development, we’ll make the web app super-simple. If you’re not familiar with Flask, please check it out, its awesome and really easy to learn. You’ll also probably want to develop the app inside virtualenv- it makes things a lot neater. Make a folder in your local machine(we’re not working with the virtual-machine yet) for your app, I’ll call it codebase. Create two folders called static and templates, and a Python file called codebase should now look like this:

├── static
└── templates

Now, open with a text editor and add the following:

from flask import Flask

app = Flask(__name__)

def index():
    return "Hello world!"

if __name__ == '__main__':

At this point, if you run with python, you should be able to open http://localhost:5000/ and see a “Hello World!” printed. Now, freeze your requirements with

pip freeze > requirements.txt

Great, now we’ll start working on the actual server.


As I said before, Vagrant allows you to work with server-like environments on your local machine. It’s absolutely great. To get Vagrant up and running:

# first make sure Virtualbox is installed, then,
gem install vagrant
vagrant box add base
vagrant init
vagrant up

If nothing went wrong, you should now see a file called Vagrantfile inside codebase- that’s Vagrant’s configuration file. Open the file, we’ll need to make a few changes to the file.

First, uncomment the line: :hostonly, ""
If nothing went wrong, you should now see a file called `Vagrantfile` inside `codebase`- that's Vagrant's configuration file. Open the file, we'll need to make a few changes to the file.

and change “” to “”. This will enable the host-machine(that is your computer) to access the webserver running on the VM.

That way we should be able to access a web app running in the VM’s localhost, on our machine.

Because, we did a vagrant up the Vagrant box should already be running. Now, run

vagrant reload

so that the changes we made to the Vagrantfile take place.

After the VM restarts, run

vagrant ssh

This allows you to run commands into the VM. Once inside the VM, we’ll need to get some things installed. Run

apt-get install nginx
pip install virtualenv

Now let’s create a folder inside the VM where we’ll keep the application

cd /home/vagrant
mkdir www
cd www
virtualenv --no-site-packages .
mkdir codebase

And let’s grab the application from our local machine

cp /vagrant/* /home/vagrant/www/codebase/

Note that while I used cp, its always a better idea to use git or some other version-control system. For more on that, I recommend that you read this post.

Then, activate the virtualenv we created.

cd /home/vagrant/www
source bin/activate

Install gunicorn with pip

pip install gunicorn

Also install the other Python dependencies your app has with

pip install -r requirements.txt

That will grab and install your app’s required dependencies like Flask.

Now, if you run

gunicorn /home/vagrant/www/codebase/ -b

you’ll have your app running but if you try opening it from your browser you’ll find that you can’t actually see the “Hello World” message that we were expecting. That’s where nginx comes in.


First of all, you need to start nginx with

/etc/init.d/nginx start


rm /etc/nginx/sites-enabled/default
touch /etc/nginx/sites-available/codebase
ln -s /etc/nginx/sites-available/codebase  /etc/nginx/sites-enabled/codebase

To /etc/nginx/sites-enabled/codebase add

server {
        location / {

And restart nginx with

/etc/init.d/nginx restart

Now, from inside codebase run

gunicorn app:app -b localhost:8000

If everything went right, if you visit you should now see the “Hello World!” message. Congratulations! You’ve successfully set up your own server.

Update- I’ve written a follow-up to this post which covers Puppet, a really handy tool that’s comes packaged with Vagrant- you can find the post here.

Videodropper- Behind the scenes


My previous post about my new web app- Videodropper, which lets you send Youtube videos to your Dropbox account got quite huge on Hacker News yesterday(At least, much more than I’d anticipated). So, I decided to write another post about Videodropper on how it works.

Videodropper is powered by Python, Flask, Redis and Celery. It is hosted on Epio(as you might have guessed from the subdomain). All the downloading is handled by youtube-dl and of course, the uploading is done using the Dropbox API.


What happens when you press the “Send to Dropbox” button is that Videodropper gets the Youtube video URL(playlists won’t work, more on that later), and it queues it up on a Celeryd process; when the download starts, another process also starts that monitors the size of the video file so that it doesn’t cross the upload limit. So, that’s two processes for one file download. Currently, Videodropper runs only four processes which means that it can process only two videos at a time. Up until now, these modest resources have served quite well, as the download and upload speed is pretty high. However, the Celery instance, which is limited to 128MB of memory runs out of memory when Videodropper starts getting a lot of requests.

When Celery starts a task which in this case is a “download, then upload”, youtube-dl starts downloading the Youtube video which, as I mentioned above happens quite fast. Then, if the size hasn’t exceeded Dropbox’s upload limit(which is 150MB now, but it should soon be upgraded to 300MB), the upload process begins. That’s basically the core functionality of the app. Oh, and if you choose to optimize the video for iPhone, youtube-dl simply downloads the .mp4 file(Youtube format=18) of the video, no transcoding takes place.

Size monitoring

One obvious optimization for Videodropper is the size-monitoring as you’ve seen that it eats up a whole process. One solution would have been to find out the file size before downloading, but I couldn’t find any way to do that(if you happen to know of any please, please tell me about it.)

Playlist support

I’ve got some requests for Videodropper to start supporting playlists which is quite a reasonable request, given that Playlists is a huge part of Youtube. However, at present supporting playlists is just not an option. As I’ve mentioned above, Videodropper runs on a very modest server configuration and downloading playlists would surely cause Videodropper to run out of memory. The limits on the server resources are mostly because Videodropper is a free app, so I am not able to invest much money on it, so if you’re interested in supporting Videodropper you could donate some money on Flattr to help upgrade Videodropper’s server capacity.

In a nutshell, Flask serves the website, Celery queues up the download tasks(and also a size monitoring task) and Redis is used mostly as a backend to Celery, but also for storing the “Recent Downloads” of the user. That’s it. If you have any query or suggestion feel free to shoot them at the comments below.



If you’re constantly troubled by having to wait for Youtube to buffer videos, or want to keep some videos with you so you can watch them again and again without wasting bandwidth, then I’ve just recently released a web service that lets you download videos from Youtube. But there are plenty of websites that already do that, why do I need another one?. What Videodropper(yeah, that’s what its called) actually does is it sends videos to your Dropbox folder.

Why send it to Dropbox?

How do I use Videodropper?

Using Videodropper is really easy. After linking Videodropper with your Dropbox account, you just copy the URL of the video you want to send, paste it into Videodropper and then send it. A bookmarklet is also being worked on in order to further simplify this process.

Note that Videodropper is still in Beta, so some of your videos may not get through properly, in case you notice any thing strange kindly send an email to or reach me on Twitter @samratmansingh