Posts

Up to level 40 this week on CodeSignal.com - that’s over 100 challenges solved in just a couple weeks

Evaluating Efficiency with Big-O Notation

Check out my recursive solution to this arcade problem, which made it possible for me solve a problem in *constant time* O(1), a whole world of improvement over my previous approach, which turned out to be a *factorial time* O(n!) solution. Big-O notation is a means of evaluating the computational efficiency of different algorithms.

My solution

boolean stringsRearrangement(String[] inputArray) {
    String[] sorted = Arrays.stream(inputArray).sorted().toArray(String[]::new);

    // test input that does not include duplicates
    if (inputArray.length == Arrays.stream(inputArray).distinct().count()
            && allStringsConform(sorted)) return true;

    // test starting with each individual input string
    for (String string : Arrays.stream(sorted).distinct().toArray(String[]::new)) {
        ArrayDeque<String> input = new ArrayDeque<>(Arrays.stream(sorted).collect(Collectors.toList()));
        input.remove(string);
        ArrayDeque<String> output = new ArrayDeque<>(Collections.singletonList(string));
        if (testPermutations(input, output)) return true;
    }

    return false;
}

[Read More]

import java.math.BigInteger;

class AffineCipher {

    private static final int M = 26;        // size of alphabet
    private static final int A = (int) 'a'; // zero-index of 'a' (ASCII code point 97)

    String encode(String input, int a, int b) {
        if (greatestCommonDivisor(a, M) != 1) {
            throw new IllegalArgumentException("Error: keyA and alphabet size must be coprime.");
        }

        StringBuilder output = new StringBuilder();

        for (int codePoint :
            input.replaceAll("\\W", "") // nix punctuation and whitespace
                    .toLowerCase()
                    .toCharArray()
        ) {
            output.append( Character.isDigit(codePoint)
                    ? (char) codePoint
                    : (char) (((a * (codePoint - A) + b) % M) + A));
        }

        return String.join(" ", splitString(output.toString(), 5));
    }

[Read More]

I was very bemused at my first encounter of bitwise operations, but quickly realized that I couldn’t think of even a single use for this language feature.

My solution to the Say challenge on exercism.io represents the first occasion that I have been able to make use of this knowledge.

The challenge was to convert numbers into English words. To do this, I would need to group them into groups of three, as we normally do using comma notation, so that a number like 6,145,010 would group such as “6 million” “145 thousand” “ten”.

There are a couple different ways to do this, but I decided to pad the number so that the number of digits would always be a multiple of 3. Without a pad, I would end up getting groups like [“614”, “501”, “0”], instead of [“6”, “145”, “010”].

One possibility would be to use the remainder from a modulus division to determine the amount of pad needed. However, it is made much more concise by using the bitwise XOR operator. Here is the resulting code, and my unit tests.

const padString = function (number) {
  const pad = "0".repeat(((String(number).length-1)%3^3)-1);
  return (pad + String(number));
};

const magnitudeGroupedArray = function (number) {
  const paddedString = padString(number);
  return paddedString.match(/.{1,3}/g);
}

describe('pad', () => {
  test('pad-3', () => {
    expect(magnitudeGroupedArray(9)).toEqual(["009"]);
    expect(magnitudeGroupedArray(89)).toEqual(["089"]);
    expect(magnitudeGroupedArray(789)).toEqual(["789"]);
  });
  test('pad-6', () => {
    expect(magnitudeGroupedArray(6789)).toEqual(["006", "789"]);
    expect(magnitudeGroupedArray(56789)).toEqual(["056", "789"]);
    expect(magnitudeGroupedArray(456789)).toEqual(["456", "789"]);
  });
  test('pad-9', () => {
    expect(magnitudeGroupedArray(3456789)).toEqual(["003", "456", "789"]);
    expect(magnitudeGroupedArray(23456789)).toEqual(["023", "456", "789"]);
    expect(magnitudeGroupedArray(123456789)).toEqual(["123", "456", "789"]);
  });
});

[Read More]

Venture Prize Pitch Night at Brown was really fun. The $25,000 first place prize was awarded to Formally - a tech company that aims to streamline visa and asylum applications, which might save law firms thousands of man hours per year!

Here I am with some of my classmates, posing for a photo with Virgin Pulse CMO Rajiv Kumar, who is an exceptional entrepreneur that founded “Shape Up RI” and managed to grow it into something extraordinary, and get acquired by Richard Branson’s Virgin Group.

It might be surprising to some that there is such a wealth of entrepreneural talent right here in little Rhode Island!

[Read More]

I completed the 30 days challenges on HackerRank! HackerRank seems to employ an intentionally convoluted Input scheme, given that they use STATIC classes and instantiate Scanner class as FINAL, but i did manage to create JUnit tests for all the exercises that function equivalently to the online tests. I would be happy to share these (the tests) with others who appreciate the expediency and more robust debugging capabilities of haxoring in their local environment.

I used a tool called PowerMock to get around JUnit’s incapacity for testing static classes, so these unit tests are able to transparently run unmodified code from HR. Ask me for the repo (it just includes my tests and the intermediate code templates they provide for each exercise).

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.runners.MockitoJUnitRunner;
import org.powermock.core.classloader.annotations.PrepareForTest;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;

import static org.junit.Assert.assertEquals;

@RunWith(MockitoJUnitRunner.class)
@PrepareForTest({Solution.class})
public class SolutionTest {

    // a stream to record the output of our program
    private ByteArrayOutputStream testOutput;

    // run before each test (prepare for input / output)
    @Before
    public void setUpOutputStream() {
        testOutput = new ByteArrayOutputStream();
        System.setOut(new PrintStream(testOutput));
    }

[Read More]

Brad Traversy’s DevConnector tutorial has kept me busy over the past couple weeks. see repo It was great to brush up after being away from developing React.js and Redux for a while. DevConnector is a much larger application than what I have built in the past using these tools, so and I was glad to practice my React/Redux programming patterns on such a larger scale.

I learned some new techniques in addition to brushing up on the familiar ones. mLab.com is a great tool for development. Not just a convenient alternative to working with MongoDB locally, mLab also offers intuitive interfaces for monitoring and managing database indexes.

Concurrently is another great trick I learned from this tutorial. I used to start the API and my frontend as separate processes, but with concurrently, I can combine them into one convenient command in my package.json

Great practice using classes in JavaScript, and working with recursion to solve an insertion problem.

Atbash Cipher

// extend the string object to filter out whitespace and shift to lower case
String.prototype.filterInput = function() {
    return this.replace(/\W/g, '').toLowerCase();
};

// extend the array object to return a string grouped into segments of five
Array.prototype.groupIntoFives = function() {
    return this.reduce((remit, char, index) =>
        index % 5 === 0
            ? remit += ' ' + char
            : remit += char
    , '').trim();
};

function atbashEncodeChar(c) {
    // return number as-is
    if (!isNaN(c))
        return c;

    // get zero-index index of the input letter (ie. a = 0, z = 25)
    const zeroIndex = c.charCodeAt(0) - 'a'.charCodeAt(0);

    // get the transposed letter (bounded by size of alphabet)
    const newLetter = (26 - zeroIndex + 25) % 26;

    // transpose back into ASCII range (ie. a = 97, z = 122)
    return String.fromCharCode(newLetter + 'a'.charCodeAt(0));
}

export const encode = input =>
    input.filterInput()
        .split('')
        .map(c => atbashEncodeChar(c))
        .groupIntoFives();

[Read More]

After almost 4 weeks, I had begun to lose hope of my Steemit account ever coming through, but the confirmation email has finally arrived, nearly a month after my signup. This makes it by far the longest interim between applying and receiving any online account for me personally. Steemit is a fount of great resources for blockchain, but it’s also an ethereum-based social networking blog that pays content producers based on user reviews.

[Read More]

It seems now that innovation comes fast and furious, making the high state of flux one of the most challenging aspects of working with this technology currently. HardlyDifficult‘s great Ethereum Dapp Tutorial on Steemit sometimes required a bit of finesse to maintain coherence with the video, as some of the tools have already evolved with breaking changes.

One tool I was very excited to learn about was Remix

[Read More]

During Christmas break I treated myself to the idle diversion of honing my bash skills.

I must have blasted through about 6000 cookies as I solved a dozen or so bash programming challenges this week (at a frightful clip). Learning new languages by solving Exercism.io challenges has been my casual vice for a while now. Since I already use the bourne again shell incessantly in my work, I have always wanted to dig a bit deeper and really learn the nuts and bolts.

Bash is really weird. Maybe that’s because the shell is somewhat akin to a Ship of Theseus, representing the culmination of decades worth of design innovations stretching all the way back to the storied UNIX days of Bell Labs in the 1970s, where such giants as Ken Thompson and Dennis Ritchie created the seminal C Programming Language and the iconic UNIX operating system. There is a beautiful MC-Esheresque quality to the closely intertwined development of C and UNIX; two amazing tools that were created in mutual benefit of each other. The first implements the second, which facilitates development of the first.

The harsh upshot is that all those years of evolution has had the unfortunate side-effect of creating many situations where arbitrary design decisions become more significant than they ought to be, on account of the implications to program portability. I often also felt unduly challenged to understand the minute differences between variant uses of syntax, and experienced great pining for Python because of some spectacularly bizarre and counter-intuitive behaviors in Bash, like the character-set collation issue

Watch out! - 10 is sometimes less than 2

$ #!/usr/bin/env bash
$ function print() { (( $1 )) && printf X || printf .; }
$ for n in 1 2 9 10 20 'a'; do
$ (( $n < 2 )); print $?
$ [[ $n < 2 ]]; print $?
$ (( $n > 2 )); print $?
$ [[ $n > 2 ]]; print $?
$ printf "\t$n\n"
$ done
..XX    1
XXXX    2
XX..    9
X..X    10
XX..    20
.XX.    a

[Read More]