Codility – MaxProductOfThree

Today I finally decided to get back into working my way through the Codility lessons. I started off by getting stuck into Lesson 4 on sorting found here: https://codility.com/programmers/lessons/4. The first task is called MaxProductOfThree.

The challenge description is in the gist below:

The idea of the task is to find the highest value of any triplet in an array. A triple may be represented as (P, Q, R) where P is greater than or equal to 0, Q is greater than P and R is greater than R. P, Q and R are indexes of an array.

The input array may be unsorted and it will have a length of 3 to 100,000. Any value in the array will be between -1,000 and 1,000.

My first attempt at answering this question only got 44% correctness. I thought the answer would be super easy, below is my first, incorrect solution:

It took me a while to understand why this may not work and I had to cave in and took a look through Google to see where I was going wrong. I found a solution similar to below and I made some changes to improve performance by a tiny bit (every little helps):

What is happening here? It took me a little bit of time staring at this solution to completely understand what was happening below is a pseudocode example of what is going on:

Below is a visual example using a sample array:

A[i] -11 -5 1 3
i 0 1 2 3

Using my first answer to the question I would have found -15 (-5 * 1 * 3) to be the highest result from a triple in the this array.

Using my second answer the highest result from a triple would have been 165 (-11 * -5 * 3).

But why!? How could including two of the smallest numbers in the result create a higher result. The reason is simple. Two negatives make a positive. So the two lowest numbers, if both negative could create a larger positive number than any positive numbers in the array. Below is the result from cordiality with 100%: https://codility.com/demo/results/demoAYEMBX-C94/

The test was completed quickly because I wrote my answer in IntelliJ and copied it over once I has worked it out. Below is a repo with my answer for you to check out: https://github.com/jordanterry/MaxProductOfThree

Android Code Patterns

One of the core principles that should be followed religiously whilst developing an Android Application is the Model-View Controller design principle.

What is Model View Controller?

Model View Controller, MVC for short has three key concepts that are necessary for it to be correctly used.

Model

The Model is used to represent data and to only represent data. It doesn’t do anything. The Model may contain the properties describing an object, such as a Person. The Model has no direct relation to either a View or a Controller. The Model will have a Low Coupling, meaning that it isn’t reliant on any other classes, this Model could be used in another project to represent a Person in the exact same way, and as there is no reliance on other objects, the Model could be completely taken out and then reinserted into the project.

View

A View in a project is used to display the properties within a project. The view may also inform the controller of user interactions within the project itself. These may be things such as the user clicking a button or the user pressing an item within an Applications Action Bar. The View is also independent of any Model.

Controller

The controller is what glues together the Model and the View together. The controller decides where to put the data and it decides what to do with User Interactions, as mentioned above. In some cases, especially with Android, the View and the Controller can be the same object. An Activity may implement a View OnClickListener that would be used to intercept a User Interaction from a Button click, for example, whilst also being used to put data into form elements.

Squares V2

Recently I have launched the second version of my first app Squares. I launched the original version of the app over 10 months ago on Android. In those 10 months the game has had over 7,000 downloads and it has a rating of 3.91/5 from 248 reviews.

At the end of summer, I decided to revamp the app from scratch. Largely because I felt the current game mode was actually quite limiting. Only being able to play for 60 seconds at a time seemed fairly limiting. The scoring system was actually a lot more difficult than it needed to be; 100 points for hitting the right colour and subtract 50 points for tapping the wrong colour.

The revamp of the game was pretty straightforward. The end goal of the update the scores the player of the game would be achieving. I hoped that an incremental point based system would make the game a bit more fun and maybe slightly more addictive! The game itself has been simplified to a 3×3 grid of colours that are continuously updating, and the target colour has been changed to a single coloured square at the top of the screen. I have also added theme support, the reason I have added this is to eventually support extra accessibility support in the future.

Here is the download for iOS.

Here is the download for Android.

Codility – Is Permutation

The next Codility challenge I will be covering is the IsPermutation challenge in chapter 2. The question can be seen in the gist below:

The question asks us to return 1 if an inputted array is a permutation, or 0 if it is not a permutation. As we know, a permutation is an array of elements containing all elements from 1..n, once and only once. Using that, we know that an array will fail any tests if an element is less than 0, or greater than the lengths of the array. We also know that if an element appears more than once, it is not a permutation. A good solution to checking if an element has already been encountered is to use a counter. Either a boolean or an integer counter would be appropriate, as long as it is possible to determine if an element has been checked before. My solution can be found below, I scored 100% correctness and 100% performance:

As always, check out the Git for this problem.

Codility – Minimum Integer

This is the first solution I will be providing for chapter 2 on the Codility site. Te second chapter is about counting elements. The reading material is very interesting, if a bit short, and perhaps unclear. It took me a couple of read throughs, it briefly discusses methods of storing numerical data in arrays. Within the first couple of paragraphs, I was already surprised to discover a counter array; storing the occurrence of a number within an array. Using this method, you can store the same amount of data, in much less storage space.

Back to the challenge though. The question itself can be found here:

The question says, find the minimum missing positive Integer from within the array. The array may not be sorted and elements may appear multiple times. Checkout my solution to the problem below, this achieved 100% performance and 100% correctness. However, I am guilty of going back and changing my result due to using counter.length + 1, instead of counter.length at a point in my code. Unfortunately, this caused a index out of bounds error, giving me only 60% performance, initially.

Also, check out my Git repository with the solution in.

Codility – Missing Permutation Element

The second question within the chapter covering Time Complexity on Codility asks you to find a missing element within an Array. The question is below:

Each element within the Array is unique and within the range 1…n+1, however a single element is missing. The Array is initially unordered. The result of the method should return the missing element. The problem is simple to solve; reorder the array and iterate through until a number is found missing from it. When it is found, return the value. There are a couple of cases that can mean no further processing will be necessary:

  • The Array is empty – Return 1, the missing element should be between 1…n+1, or in this instance between 1..0+1->1…1. (This can happen before sorting the array.)
  • The first element in the array is not 1. Return 1. (Must happen after sorting the Array)
  • The last element of the array is not n+1. Return Array Length + 1. (Must happen after sorting)

Now you have read the brief explanation above, check out my solution below:

Also, check out the Git Repository.

Edit

Since writing this blog post, I have just searched up how other people resolved this issue, and whilst I got 100% on both score and functionality, I was way off the best solution. Going back to my solution for the first puzzle. The key is to calculate the expected element length for the number of elements, then subtract each element of the array, this gives you the remaining element. Here is a link to the Stack Exchange answer where I found the answer. I can’t believe I didn’t think of that.

Codility – Frog Jump

The Frog Jump challenge is the third challenge within Codility’s first chapter on time complexity. This challenge is pretty simple, the question is as follows:

The question simply says, how many jumps of D length will it take for the frog to cover at least distance between Y and X. The key part to take away from the question is that the distance covered won’t be exact; the distance covered by the number of jumps has to be greater than or equal to the distance.

Below is my solution to the issue; it scored 100% on accuracy and on performance.

I made a Git repository for the code on my GitHub, check it out here.

Codility – Tape Equilibrium

Codility is a great site for learning, and testing your knowledge regarding some complex programming theories. Whilst the site contains many challenges, but there is a helpful section called lessons. Each lesson covers a topic and provides challenges for you to test your knowledge on.

 
The first of the chapter within the Codility is about Time Complexity. The first challenege within this section is named TapeEquilibrium, with it’s short description being: Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|. Huh. Let’s take a look at the problem and the final solution for it. The description of the issue is below:

The question is simple, an Array, A, with N elements is passed into a method. Loop through each element of the Array from A[0] … A[n-1] each time calculating the difference between the sums of each side of the current key in the array.

The question tells us that the worst case time complexity should be O(n). We know that this is linear time, but it will likely end if a certain condition is reached.

Below I have put my final solution into a GIST. Using this, I achieved 100% correctness and 100% on performance.

I made a Git repository for the code on my GitHub, check it out here.

Disable Mod Pagespeed

Recently at work I have been developing a large project on a WordPress site. Unfortunately, over night WordPress updated to 3.9.2 and a whole host of errors occurred simultaneously. One error was that my JavaScript wasn’t updating and a some strange console messages were appearing, nothing I did would fix the errors, I originally looked for errors relating to the WordPress update. The error was nothing to do with WordPress itself, I discovered in a fit of disgusted rage 5 hours later.

The issue was related to an Apache Module Mod Pagespeed. This module appeared to have been activated by the hosting company, the same night as a WordPress update.

Fortunately a bit of htaccess wizardry fixed the issue. Below are the 5 lines of code that saved my sanity.