Tag: <span>algorithms</span>

A few weeks ago, I blogged about some code I was writing to simulate buses arriving at bus stops and picking up passengers.

I mentioned at the end that the code shown there had three major shortcomings. Having nothing better to do with an hour this afternoon (meaning: not being bothered to do what I was supposed to be doing and preferring to have a play instead), I decided to address those shortcomings.

This blog post explains the changes, and how they led to a very pretty, but probably wrong simulation!

The answer to the age-old question of why do buses come in threes is that they don’t. Well, not often.

I decided to write a simple simulation to see how buses might behave, and whether or not they really do arrive in threes.

I was browsing the latest C# questions on StackOverflow, and came across one that caught my eye. Sadly, it was quickly closed by people who, in my opinion, didn’t read it properly. The question was…

I am trying to write a program to find the factor of a number with minimum difference. For Ex: for 20 it should be 4×5 or vice versa. How can this be achieved for a really BIG number. lets say 989287498274928743928174192847219347123984723498. Please guide

Ignoring the usual SO rules about showing some effort or research, the question is not simply “How do I find the factors of n?”, which is what all the linked answers were about. This question was how to find the two closest factors. Sure you can do that by finding them all, then sorting them by their difference, but for a big number, that’s hugely inefficient. There are ways of solving this specific question much more efficiently, which is what I decided to do.

Debunking the Internet myth that this year December (or whatever month is chosen) will have 5 Saturdays, 5 Sundays and 5 Mondays, and how this only happens once every 823 years.

It’s junk, and I proved it using Linq. Afterwards, I realised that I could prove it without Linq, had I only thought about the question first. Still, it was an interesting exercise, both in Linq and in thinking.

This entry is part 11 of 11 in the series Mazes For Programmers

Following on from my experiments in timing the algorithms in part 9 of this series, I was curious as to why my code for Wilson’s algorithm took so much longer than the code for the Aldous-Broder algorithm. Jamis Buck (the author of the book this is all based on) was foolish enough to leave his email address on his blog, inviting people like me to ask him questions! I asked if he had seen anything like this difference. Turns out he hadn’t actually tried timing them, so couldn’t comment. This got me curious, so I pulled up his code, and started searching around to find out how to time code in Ruby. This turned out to be fairly simple (as it should), giving me the following… This gave me 10 numbers, which enabled me to calculate an average, as well as check on the variation (standard deviation for the statistical…

This entry is part 10 of 11 in the series Mazes For Programmers

One of the idea he had for modifying the Aldous-Broder algorithm was to force it to pick an unvisited neighbour, if one exists. I think the idea was to cut down on the number of very short dead ends that the basic algorithm produces. If you look at the following sample, you can see that there are a lot of places in the maze where there are many short walls, making it pretty obvious which way to go… The plain algorithm picks a random cell from the current cell’s neighbours… It was pretty easy to change this so that it would always pick an unvisited cell if there were any… With a little thought, I could probably change the Where clause to include both cases, but it didn’t seem worth it at the time. Anyway, this simple change produced a marked difference in the quality of the mazes. Apart from…

This entry is part 8 of 11 in the series Mazes For Programmers

This was my first real challenge. I converted his code for the Binary Tree and Sidewinder two algorithms, and Aldous-Broder turned out to be pretty straightforward to implement, so my code looked a lot like his. However, Wilson’s algorithm was a different matter altogether. I had been reading the book at night, and didn’t have it by my side when I tackled this algorithm. I had read his description of the algorithm a few times, and it seemed easy enough. Ha, famous last words. My first attempt was pretty rubbish. The algorithm didn’t terminate, and what it produced along the way was not very impressive. Unsure what had gone wrong, I re-read his description (whilst avoiding the code) and realised that I had mis-read it, and had got two small, but significant points wrong. I could go into a lengthy discourse about how important it is to understand your requirements,…