Service health monitoring with Reactive Extensions

When integrating independent services to build larger systems, it’s often important for services to keep track of the status of the other services that they depend on. Especially for a microservices approach, where services should expect their dependencies can be absent at any point in time. Services that cope with dependencies being unavailable make a less flaky and more resilient, hands off system.

Services can dynamically change their behaviour as the states of their dependencies change. If a dependency is offline, a service can decide to re-route work, buffer it until processing can resume, or explicitly reject requests. Doing this proactively by reacting to changes in dependencies’ statuses makes this much more fluid.

This post will look at a simple way of using Reactive Extensions to keep track of dependency status.

Continue reading

Solving GCHQ’s Christmas nonogram in 0.07 seconds

GCHQ throws down the gauntlet

A while back I found the GCHQ Director’s Christmas card, which came in the form of a nonogram. GCHQ has a history of puzzle setting and even hiring people through puzzles. The WWII codebreakers were hired through crosswords and other puzzles in the newspaper, which was featured in The Imitation Game.

I was new to nonograms, but quickly found out they’re a “paint by numbers” puzzle where hints for rows and columns give you series of segments (of varying lengths) to colour in. Applying all the clues together logically lets you work out whether each cell is filled in or empty progressively until you reach the final solution.

Typically you then have a badly pixelated picture of something and a sense of accomplishment. With GCHQ’s puzzle, you end up with a QR code that leads you to the next puzzle. So the picture is not very pretty and the sense of accomplishment is short lived. Here’s what GCHQ’s best Christmas wishes look like:

gchq-nonogram

And I thought I was bad at Christmas cards.

Continue reading

Identifying Market Spoofing with Data Visualizations

I love data and data visualizations. They can give deep insight into problems and behaviours, and they can make you interested in something you previously thought dull.

I came across the article “How to Catch a Spoofer” from Bloomberg, by Matthew Leising, Mira Rojanasakul and Adam Pearce. The article gives a fascinating view into the trading activity on the Chicago futures exchange, and how to identify “spoofing” within trading activity. The visualizations take a combination of a difficult concept and large volume of data, and extract genuine, novel insights.

Continue reading

Roomba algorithms and visualization

I once had an interview question asking for an algorithm for a Roomba that ensures it covers every square of a room divided into grid cells, given that the room shape and location of obstacles are unknown. It’s similar to the idea of solving a maze, except that instead of getting to a specific point, you’re trying to visit every point in the room – to clean it!

It’s a pretty common problem, but I hadn’t seen it in the guise of a physical robot before. Running a Depth First Search covers every piece of floor easily enough, but casting it as a physical device that has to move implies a large cost to popping back up the stack that’s generated during DFS. There’s a lot of backtracking in a DFS based approach for a Roomba, so it makes for a slower vacuuming job.

It made me wonder whether there was some better approach than DFS that would be more efficient.

Continue reading

Solving Boggle boards at scale

Princeton’s Algorithms II course includes an assignment on finding Boggle words. Briefly, Boggle is a game where you have a two dimensional grid of random letters and players try to find as many real words as they can from the board by stringing together neighbouring letters.

This post looks at how tweaking the initial implementation can give a 2x speedup, but picking the right data structure gives a 4,200x speedup.

Continue reading

Image resizing with seam carving

I’ve been working on the Algorithms II course from Princeton on Coursera lately, which has been pretty interesting. One of the assignments is on the topic of seam carving, which is a technique for arbitrarily resizing images while maintaining as much of the important detail as possible. It’s also referred to as image re-targeting, coming from the idea of re-targeting an image for a phone/tablet screen with a different resolution and aspect ratio.

Seam carving prioritises important details during resizing

The problem with traditional resizing of images where the aspect ratio is changing is that it requires either cropping or stretching the original image. Stretching makes the main features look warped, especially people, while cropping loses detail – especially if there’s no dead zone on one side that can be cropped away, like an empty sky.

Instead of scaling all parts of the image equally, it can be advantageous to remove more of the dead zone pixels, such as gaps between people in photographs. This is why seam carving has been used to implement Content Aware Scaling in Photoshop. There’s a good example on that page, too.

Seam carving achieves this by identifying the “energy” of each pixel, which is a measurement of the how important to the image the detail of each pixel is. It then identifies horizontal or vertical seams through the image and removes the seam with the least total energy. The seams don’t have to be straight lines, allowing the algorithm to remove paths of low detail pixels that follow the shape of the image.

Continue reading

Rx Learning Resources

I recently ran a workshop on Rx, and as part of preparing I had to hunt down some useful resources for learning. I found that things had come a long way since the early days, when people mostly learned from videos of Wes Dyer, Jeff van Gogh and Bart de Smet drawing on whiteboards at Microsoft, and Lee Campbell’s blog.

Since the initial .Net release, a lot has changed for Rx – it’s become open source, and it’s now available for many platforms: .Net, Java, Javascript, plus quite a few more. It’s also being used and talked about by some big players outside Microsoft, like NetFlix (who are responsible for the RxJava port).

With all this new exposure, there are now a lot more resources for learning Rx. Here are some that I think are particularly useful.

Continue reading