###
algorithms / Permutations playground

Marcel Braghetto 20 September 2015
>>> Read full article

Get the example project here

If you’d like to try it out on your device:

Download and install Permutations-Playground.apk

In my Internet travels, I came across a coding question that looks something like this:

**Find the number of permutations of string A in string B**

**String A (search term): bcba**
**String B (search data): babcabbacaabcbabcacbb**

The idea is that the characters in the *search term* are compared in every permutation to the characters in the *search data* to identify how many instances can be found.

Although it seems kind of simple, the brute force approach of looping through every *permutation* of the *search term* for every permutation of each *frame* of data in the *search data* ends up being O(n!) *factorial* complexity which is pretty much useless for anything.

I can’t recall the exact place where I originally found this question - it might have come from Career Cup or something.

Anyway, it looked like an interesting problem to try and solve - in particular to try out different approaches to see which Java data structures work OK and which ones seemd to be able to do the calculations the fastest.

###
algorithms / Dijkstra's Algorithm - Part 2

Marcel Braghetto 12 September 2015
>>> Read full article

Get the example project here

If you’d like to try it out on your device:

Download and install Treasure-Crab.apk

This post continues on from my Dijkstra’s Algorithm - Part 1 post. In this part we will put together a basic Android app to visualize the pathfinding. Let’s call the app **Treasure Crab**. The goals for the app are to:

- Display a graph along with an
*agent* who needs to travel the shortest distance to reach the *goal*. The *agent* for this demo will be a crab and the *goal* will be a treasure chest.
- Allow the user to choose from some preset graphs.
- Create an render loop to show the
*agent* moving to the *goal* in real time.
- Implement the ability to interact with the graph using touch to move the nodes around.
- Implement the ability to serialize and deserialize the graph so it can
*remember* how we left it.

###
algorithms / Dijkstra's Algorithm - Part 1

Marcel Braghetto 5 September 2015
>>> Read full article

Get the example project here

So there’s probably a bunch of ways to do path finding but I wanted to try out Dijkstra’s algorithm using a basic graph structure.

In this post I’ll show examples of:

- Creating a simple directed, weighted graph.
- Writing an implementation of Dijkstra’s algorithm to run against the graph to find the shortest paths between nodes.

I’ll walk through some basic building blocks for making a graph in general as well.