• Josephus Problem

    Posted in Coding, C++ on May 20, 2017

    Josephus Problem describes a counting-out game where you progressively remove (kill) people by their position, until only one person remains. For example, take a group of 10 people, then kill each second person until only one person remains. Josephus Problem tells us who is the survivor. There is an analytical solution for the special case of skipping one person (k=2). Within that, there is an intersting sub-problem - you need to calculate the value of n with only the highest bit set. For that, there are both naive and efficient solutions. The following shows how solve Josephus Problem for the...

  • SQL To Get Top 1 In Group

    Posted in Coding on May 11, 2017

    A pretty common problem is to get the top N items from a group from a SQL database. For example, suppose you wanted to get the last order for each customer - this is a top 1 item grouping by customer ID. For some database engines, you can use OVER and PARTITION BY to achieve your goal. These functions don't exist on MySQL and SQLite, so if you are using those engines, then you need to fall back to basic SQL. It is almost certinally not as efficient (basically doing a cross-product), but you can make it work. The key insight, described well by Bill Karwin on Stackoverflow is to join the table w...

  • To Tuple or Not

    Posted in Coding, C++, C# on May 11, 2017

    Libraries for C++, C# and other langauge frequently provide tuple objects as an easy way to create n-pairings of items and objects, for example std::pair and System.Tuple. Because they are "cheap to write" it is temping to use them instead of writing a separate class or struct. But, they come with side effects. The names of the members are not very descriptive. For example, in C++, you get first and second and in C# you get Item1 and Item2, etc. So, when should use these tuple types and when should you write your struct/class? I give the following advice: If the struct/class you would write w...

  • Using Terraform to Build Heroku/S3 Site

    Posted in Coding on May 07, 2017

    I have been playing around with Terraform, and decided to try to use terraform to build a staging environment for this site. (In fact, I actually already had a staging environment - this was just for my own interest). My site consists of a simple Heroku hosted application with static resources stored in AWS S3. My first step was to define my application's architecture in the terrafrom configuration file. For my purposes, I wanted to start with a pretty simple definition. If you follow the Terraform Getting Started guide, you will end up with three files: terraform.tf containing your infrastra...

  • Isomorphic Strings

    Posted in Coding, C++ on May 06, 2017

    The program below is a simple example of testing whether two strings are isomorphic. Isomorphic means there is a straight mapping between the two strings. This example uses a simple "bitmap" to define and check the mapping between the two strings. It works when the input set is small because the map is small and can be allocated upfront. As with other examples, the purpose of this example is to show a simple way to solve the problem. I have generally excluded boundary condition testing, use of templates, and other things you might do to make this generally more useful. #include <algorithm> #in...

  • Quick Select

    Posted in C++ on Apr 28, 2017

    Quick select is an efficient algorithm for finding the k-th item in a list. The following is a simple implemenation to find the k-th smallest item from a list of integers. I've kept the example simple and concrete (instead of with templates) to focus on the algorithm. #include <iostream> #include <cmath> #include <utility> /// Sorts the list about the value of the pivot index. /// After this function completes, the items to the left of the pivotIndex /// are all less than the value at the pivotIndex and the items to the right /// of the pivotIndex are all greater than the value at the pivotIn...

  • Merge Sorted Arrays Algorithm

    Posted on Apr 19, 2017

    The following is a simple algorithm to merge two sorted arrays. Merging two sorted arrays is essentailly the same as a single round in merge sort. If you were implementing this in a real project, you would probably was to use templates so this could work with any type. I've restricted this to only unsigned ints to focus on the algorithm. #include <iostream> #include <cstdint> #include <vector> /// Merge two sorted arrays /// @param array1 The first sorted array to merge /// @param array2 The second sorted array to merge /// @return A new array containing the merged result std::vector<std::uin...

  • Integer to String Algorithm

    Posted on Apr 19, 2017

    The following is a simple example for now to convert an integer to a string (doesn't include error checking, sign detection, non-base 10). #include <cstdint> #include <iostream> #include <string> /// Reverses the characters in the string /// @param str The string to reverse (the original string is modified) /// @return The reversed string std::string reverse(std::string& str) { std::string::size_type half = str.size() / 2; std::string::size_type end = str.size() - 1; for (std::string::size_type i = 0; i < half; ++i) { char tmp = str[i]; str[i] = str[end - i]; str[end - i] =...

  • Setting up a October CMS environment with Vagrant and Heroku

    Posted in Web on Mar 20, 2017

    OctoberCMS is an intersting CMS platform build on Laravel. There is a great official tutorial on how to setup OctoberCMS with a Vagrant box using the quick install approach. That approach is great if you will use OctoberCMS's project management tools to update, install plugins, themes, etc. But if you want to do any custom work, including install a composer package, you are out of luck. The quick install doesn't include composer.json, so there is no way forward. Alternatively, you can setup OctoberCMS via command line, which will give you a standard PHP/composer project, but there is no tutori...

  • Page not found - HTC OneX Mass Storage on JellyBean

    Posted on Feb 26, 2017

    Oops. I've changed the focus of my blog and the page you visited doesn't exist anymore.