Nicholas Pilkington

Computers. @DroneDeploy. Fun

Page 2

Location Estimation - Part 1

We work a lot with GPS data at DroneDeploy. In this article however we are going to look at accurately determining position using sound data instead. This is based on a problem that appeared in the Challenge 24 Programming Competition in 2014. Let’s get started. Let’s say we have a number of towers at different locations. Each tower is emitting a pure tones at a specific frequency and additionally each tower is rotating at 1 Hz. This is what the layout of the towers looks like:

Screenshot 2016-01-03 13.16.19.png

Now let’s say we have a recording of audio received from all these towers and made at a random location. In addition let’s assume that the towers are emitting their tone at approximately (with 20%) the same volume. How do we determine the exact location that the sound was collected? In order to find out where we are, lets first look at the contents of the audio we are receiving. Loading and plotting the...

Continue reading →

Sudoku SAT-Solver

Sudokus are fun to solve - but watching a machine solve them isn’t as rewarding. However, what is fun is writing programs to solve them for you. I’ve written Sudoku solvers in the past using DFS with pruning and these have done the job fine but I wanted to try and write a solution that uses a SAT-solver.

SAT-solvers are designed to solve the Boolean Satisfiability Problem that seeks to find a truth assignment for each of a set of boolean variables for which the whole expression is true. For example the expression X1.X2 + X3 is true when X1 and X2 are both true. This is not the only solution though. Since X3 being true or X3, X1, X2 all being true are also solutions So this SAT problem has three solutions. The SAT problem is NP complete This means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as...

Continue reading →

General Collector’s Problem

Some time ago at work we wanted a way to represent each person with an avatar to track what they were working on on a board. We were using a sort of Kanban in software engineering and I though it might be fun to get some LEGO mini-figures to represent each person in the team on the board. I was wondering it would be cheaper to just buy a complete set of say 8 LEGO mini-figures at a premium. Or instead buy a number of random individual packs in the hope of getting a set of unique figures without spending all the money on the full set.

Screenshot 2015-12-28 15.29.29.png

I did some reading and found that this is called the coupon collector’s problem problem which seeks to work out the expected number of purchases that need to be made before we have a complete set. In the case of an 8 figure set the expected number of purchases is 22. That is to say that you should expect to purchase 22 random figures before you have at...

Continue reading →