Algorithm.co.il

admin

Writing a pandemic simulation

Posted on by Leave a Comment

Over the last weekend I felt like programming something fun and easy, so I thought, why not write yet another pandemic/epidemic simulation.

A quick demo of simpandemic

So between helping a crying child and preparing lunch, I created simpandemic. It’s small, simplistic, but easy to play with and change parameters. As a toy project, it’s far from perfect. I implemented infection based on distance rather than collision detection, like some other simulations do, and optimized it using a grid and not a tree structure (e.g. rtree). However, it works, it is playable and very much tweak-able.

Right now it depends on pygame, which is great fun, but a bit of a pain to get it working on mac these days.

Feel free to download it, fork it, play with it, whatever. I’ll accept fun pull requests in case these actually come.

Stay healthy, stay safe, stay home!

How I learned to stop worrying and actually use StackOverflow

Posted on by Leave a Comment

So apparently almost all of the developers in the world are using stackoverflow. However many developers just use StackOverflow to lookup answers, and rarely to ask their own questions. Answering other people’s questions is of course rarer still.

Up until recently I was the same: I wrote a few questions in StackOverflow, and even answered a few, but by and large I was using it to find existing answers.

This week something changed, something broke. In a way, I stopped caring. I had a problem, I didn’t find a solution fast enough, and decided, “what the heck, the solution is not obvious, I’ll just write a question”. Also, if the solution is obvious to someone else – that’s even better, I’ll learn something.

And so I asked my most recent questions, about distances between 2D segments, projections, etc. I’ll cover this subject in depth in a future blog post, as this one is about StackOverflow.

Writing a question on StackOverflow has a few advantages over not writing it. The most obvious one: you might actually get an answer! Here is a good example, my most recent question. The less obvious is that you get to put down your question in writing which just like in rubber duck debugging and that would help you with solving this problem, and practice the skill of asking the right questions.

Also important to mention – you have nothing to lose but a little bit of time. As long as your question is real and you are not clueless, asking a question will not reflect badly on you in any way, quite the opposite.

What actually surprised me is the gamification of StackOverflow – you get points for participating. I already knew about it, but I was surprised at how effective it is. Here is where I am at the time of writing this post:

My StackOverflow reputation as of 2020-03-12

Participating on SO is surprisingly addictive, and as a close friend told me there are additional advantages: once your reputation is high enough – you start getting job offers, and you can actually use that on your resume/CV (if using them is a thing you do :)

My advice to any developer reading this: you are already looking up answers on StackOverflow. If you don’t find an answer, don’t just move on. Before you do – write a question. Even if you do move on, you’ll get something valuable from it.

Back to writing

Posted on by Leave a Comment

So apparently my last blog post was from 2012. That’s quite a bit of time.

flytrex drone

Since then I’ve:

  • Had a son
  • Sold my startup Desti to HERE
  • Moved with my family to Boston
  • Moved back to Israel, join Cymmetria, first as VP R&D and later as CTO
  • Had another son
  • Left Cymmetria and joined Flytrex as VP R&D

It’s not a long list, but it covers a lot of ground. Right now, Corona virus notwithstanding, I’m pretty excited about the work we do at Flytrex: we’re building a system for food delivery via autonomous drones.

Here is a short video that shows what we’re working on:

The video is by now 11 months old and the system changed a lot since then, and our main challenge right now is getting this system working in the USA.

Learning from my experience, I want to start writing regularly. To achieve that, while I will write mostly about programming, I will also write about other areas of interest. Let’s see where this new adventure takes us. Onwards!

Starting from Scratch – Part 1

Posted on by 5 Comments

About a month ago, someone I met asked me if I could give him C programming lessons. To protect his privacy I won’t talk about him much, besides saying that he is a serious guy and he doesn’t know programming at all.

The first thing I did was give him a general explanation of what C does, the compilation process and so on. I then showed him a simple program, and showed him how to compile it, and how to run it.
I think the first thing beginners see when they start to program with C is all the “unnecessary voodoo”. For someone just starting to program, “#include <stdio.h>” doesn’t make much sense, and he shouldn’t be bothered with it. The same applies to “int main(void)”. So I just told him to ignore that for now, it would be made clear later on.

The next thing I did was give him a C book, and telling him what to read, and more importantly, what not to read. Teaching books suffer from a kind of “split personality” problem – they try to be both a tutorial and a reference. They also cover things fully the first time around. For example, consider variable types.
A first timer doesn’t need to know about anything besides int. He really doesn’t need to know about size limitations. He shouldn’t be bothered by these issues in the first few lessons.

As I see it, the order of things to learn is:

  • General information such as how to compile, etc…
  • Meaning of variables, and variable assignments.
  • if-else, and then do-while.

So we covered these subjects in the first two lessons, and he was able to write some simple programs, such as compute the average of two numbers, and so on.

We wrote a simple ‘guess the number’ game together, and I used this opportunity to explain if-else by writing conditions for cases such as “warm” or “cold”, “too low” and “too high”. Simple while loops were explained as well: “keep playing as long as the number was not guessed”. We wrote some more programs after that.

As homework, I gave him the following problem:

Write a program to compute an average of numbers.
It will read numbers from the user, until the user gives the number -1.
After it finished reading the numbers, it will print their sum, and their average.
If the average is in the range, print: 0-55: failed, 56-72: could be better, 73-85: ok, 85-95: good, 95-100: excellent.

I knew this will be problematic, and indeed it was. He wrote a program that asked for three grades, and averaged them. It went on asking again until the grades 100, 100, 100 were entered – he thought that was nicer than -1.
Well, a few days ago we sat together, and I understood the problem:

He knew how to write C code, but he didn’t know how to program!

I simplified the problem. I asked him to write (during the lesson) a program that reads numbers from the user until a zero is entered. It will then output how many ones were encountered. He couldn’t write that as well, and that’s no surprise – he had a big concept to understand.

So I told him, let’s play this together. I will tell you numbers, and when I finish, you will tell me how many ones were there. I gave him ten numbers and I noticed he was counting on his fingers!

Grasping this opportunity, I told him to explain exactly what he does. Then I asked him to give me instructions on how to count numbers. The instructions were “read a number onto your left hand”, and “if the number on your left hand is one, set the number on your right hand to be the number on your right hand plus one”. It took some effort for him to understand this, but he did. I then asked him to do the same, but now summing the all of the numbers with the right hand.

I then showed him how I translate these instructions into C. I asked him for the definition of an average, and then, looking at the code on the screen, realization dawned on him. He was amazed – he managed to calculate the average of an unknown number of numbers!

It was amazing for me as well – it’s not often that you get to see someone understand a big concept such as programming.

After the averaging program I asked him to write a counter program – given a number, print all the numbers from zero up to this number. When he got stuck, I asked to turn off the screen, and again give me instructions on how to do the task. That he was able to do. Translating these instructions to C wasn’t that hard, and some 30 minutes later, he had a working program. Success!

Fractal Memory Usage and a Big Number

Posted on by 1 Comment

In a previous post I said I’d talk about 4**(4**(4**4)).
First, about the number. I first saw it mentioned in a math lesson back in high-school, when the teacher wanted to demonstrate estimation abilities.
He wrote it on the board, like so:

4444

and then asked students to estimate how big that number is. Turns out this number is much bigger than most students thought. (For comparison, the number of atoms in the observable universe is 1080.)

Given that this number is so big, it should come as no surprise that computing it will consume all available memory.
What is interesting is the way the memory is consumed:

(It died with a MemoryError just before the next “jump”.)

When I first saw this I was fascinated. To those interested it is generated by the long pow function in Python, implemented in longobject.c. According to the comment there, the algorithm is a left to right 5-ary exponentiation, taken from “Handbook of Applied Cryptography”.
In short, the simpler algorithm “left-to-right binary exponentiation” (used for smaller exponents) repeatedly squares the accumulator, and according to the binary digits of the exponents, multiplies it by the base. 5-ary exponentiation basically does the same thing, but in each iteration it ‘eats’ five digits of the exponent instead of just one.

It might be very interesting to study algorithms and code according to their memory usage. Once at work I used a similar memory usage graph to optimize the memory usage of some algorithm that was eating too much memory. I don’t remember the details as it happened a few years ago, but I do remember that I recognized the “type of the memory eating”, which helped me to narrow the problem down to a specific area of code, where indeed the problem was located. (I consider this a case of programming-fu :)

Notes:
1) The reason I’m talking about Python is because it has arbitrarily sized longs built-in.
2) This graph was generated using Windows’ task manager. On my Ubuntu machine it looks quite different, almost a straight line. Any guesses why?

My Bad Memory, High Load, and Python

Posted on by 1 Comment

About a month ago the new Ubuntu 8.04 was released and I wanted a clean install. I downloaded an image and burned it to a CD. Just before installing, I tried “check CD for defects” and found a few. Turns out (*) this was because of bad memory – and memtest confirmed it.
So I went to the shop, replaced the bad memory, and also bought two new sticks. I went home to install the new Ubuntu, and after the installation, Firefox crashed. After rebooting back to memtest, I saw this:

memory errors in memtest

Back at the computer shop, they asked me to reproduce the errors. Just firing up the computer and booting directly into memtest didn’t seem to do the trick, so I suspected that I had to overwork my computer a bit to reproduce this.

Since I was at the lab, I didn’t want to muck around too much.
So I thought, “what’s the quickest way to give your CPU a run around the block?”
That’s right – a tight loop:

while True:
    pass

However, this snippet doesn’t really play with the memory.

The next simplest thing to do, that also jiggles some ram is the following (and one of my favorites):

In [1]: x = 4**(4**4)
In [2]: y = 4**x

I will talk about this peculiar piece of code at a later post.

In any case, this snippet also didn’t reproduce the error. It is also quite unwieldy, as it raises a MemoryError after some time. Later at home I tried two more scripts.
The first is a variation on the one above:

x = 4**(4**4)
while True:
    try:
        y = 4**x
    except MemoryError:
        pass

I ran a few of those in parallel. However, my Ubuntu machine actually killed the processes running this one by one.

The second is smarter. It allocates some memory and then just copies it around:

import sys
import copy
megabytes = int(sys.argv[1])
 
x1 = [["a"*1000 + str(i) for i in range(1000)] for j in range(megabytes)]
while True:
    x2 = copy.deepcopy(x1)

After both of these scripts didn’t reproduce the problem and it still persisted arbitrarily, I returned the computer to the lab. Turns out that the two replacement sticks and the two new sticks weren’t exactly identical, and that was the cause of the problem. So now my memory is well again.

As for the scripts above, I once wrote a similar script at work. I was asked to help with testing some software in some stress testing. The goal was to simulate a heavily used computer. A few lines of Python later and the testing environment was ready.

Footnotes:
(*) – Finding out that it was a memory issue wasn’t as easy as it sounds. I didn’t think of running memtest. I checked the image on my HD with md5, and the hash didn’t match. I downloaded a second image, and again the hash didn’t match. I checked twice.
At this point I was really surprised: not only the second check didn’t match the published md5, it also didn’t match the first check. Some hours and plenty of voodoo later, a friend suggested running memtest, and the culprit was found.