Algorithms 101 Roads & Town Centers

Alright, there’s this one algorithm that I’ve solved before. I’ve always found it to be a rather fun little exercise to work out. It popped into my head recently and I wanted to recollect how the logic of it went, but my Google-fu wasn’t so great. In the end, I didn’t find the algorithm problem statement but I’ve recollected it as best as I could from memory. If you know what the name of this challenge is I’d love to know what it’s called or if I’ve put it back together correctly. Ping me @Adron.So the story goes something like this. There once were some nations with a number of cities in each nation. Every citizen has access to every city and every city has a town center for all the citizens to enjoy. Recently the roads were damaged from a lack of maintenance work, ya know, like in real life. Meanwhile there was a revolution that led to catastrophic war that destroyed all the town centers in the nations. So now none of the cities have reachable town centers or functional working town centers anymore! The citizens of the world are angry at the nations and demand immediate fixes to their roads and town centers, with a priority on the town centers! The leaders have decided that the roads shall be repaired and have hired me (you) to assist!The nation has n cities, we’ll number 1 to n. The cities have two way roads, totalling m roads. A citizen has access to the town center if: their city contains a town center and their city has a road to travel from their city with a town center to another city with a town center.

The following is a map of one great nation of cities with currently impassable roads that must be repaired.

nation

Continue reading “Algorithms 101 Roads & Town Centers” →

Algorithms 101 – Big Sums

I’ve been practicing up on some algorithms with Go per my Resolutions for 2018 item “Write More Code, Build Patterns, Algorithms”. Here’s a few of the ones I took a quick review of, from the algorithm perspective.

The first algorithm I took a dive into is a big sum problem. Part of the reason is I wanted a refresher on how Go deals with various integer data types. Easier to set it to memory if I play around with the data types versus just simply reading up on the specifics.

Big Sum!

Imagine being given an array of integers of size N. The task is to get the sum of the elements of the array and print each sum out. The added caveat is that each of the integers may be large.

Input & Sample Input

The first line of the input consists of an integer N. The next line contains N space-seperated integers in the array. Sample input would look something like this.

3
1230983459 90232478345 2349432014

6
982734503 2938563459 100032400 9202345873 701346892 2345010900

Output & Sample Output

Print a single value equal to the sum of the elements in the array.

Sample output for the first example input.

93812893818

Sample output for the second example input.

16270034027

The Solution

Alright. Down to the task. The first thing I’ll need is to setup getting the input into the application, a little standard input. For that I’ll need to use the standard Go “fmt” library. In my main.go file I go ahead and create the start of the code.

package main

import (
    "fmt"
)

Next I’ll write up the input for the index count, which is the first value passed in.

func main() {
    var arraySizeCount int64

    _, err := fmt.Scanf("%d", &arraySizeCount)
}

Now that I know the size of the array of data I’ll be scraping up, I’ll setup the array to put that data in. I’ll add the next line of code just below the previous additions.

data := make([]int64, arraySizeCount)

With data now setup as the array I’ll need, I can step through the data that is retreived from input and put values in the array.

for i := range data {
    _, err = fmt.Scanf("%d", &data[i])
}

Next I’ll need a variable for the total sum of the values in the array. I’ll create that and then also step through the range of values in the array, adding them while I go.

var totalSum int64 = 0

for _, v := range data {
    totalSum += v
}

The final step involves an error catch, I’ll print out the error, then display the value of the sum. That solves the algorithm in a short bit of code.

if err != nil {
    fmt.Print(err)
}

fmt.Printf("%d\n", totalSum)

All of the code together only amounts to 29 lines of code. One additional thing I could do, that might make it more readable is to break out the input phase and output phase of the function. The code currently looks like this.

package main

import (
    "fmt"
)

func main() {
    var arraySizeCount int64

    _, err := fmt.Scanf("%d", &arraySizeCount)

    data := make([]int64, arraySizeCount)

    for i := range data {
        _, err = fmt.Scanf("%d", &data[i])
    }

    var totalSum int64 = 0

    for _, v := range data {
        totalSum += v
    }

    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", totalSum)
}

A Refactoring?

As I start to refactor this code, as I mentioned, the existing code is only 29 lines of code. But I’m going to break it out into two functions; I’ll call one SumTotal and one DataRead. My SumTotal function will take a list of 64 bit integer data types and return a single total 64 bit integer.

func SumTotal(list []int64) int64 {
    var totalSum int64 = 0

    for _, v := range list {
        totalSum += v
    }

    return totalSum
}

The DataRead function will have a 64 integer paramter and an error result. The function definition will look like func DataRead() ([]int64, error) {}. The function itself I’ll have take in and get the input and also have it build the array. I get to work on that and pull the functionality out of the existing 29 lines of code into the function, which I end up with a function that looks like this.

func DataRead() ([]int64, error) {
    var length int64

    _, err := fmt.Scanf("%d", &length)
    if err != nil {
        return nil, err
    }

    data := make([]int64, length)

    for i := range data {
        _, err := fmt.Scanf("%d", &data[i])
        if err != nil {
            return nil, err
        }
    }

    return data, nil
}

Now I just go ahead and wipe out what is in the main function of the code and replace it with the few lines to call the respective input, and lass it to the respective processor and finalize that by printing out the results.

func main() {
    data, err := DataRead()
    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", SumTotal(data))
}

Now the whole file of code looks like this, which leaves one with a few questions.

package main

import (
    "fmt"
)

func main() {
    data, err := DataRead()
    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", SumTotal(data))
}

func SumTotal(list []int64) int64 {
    var totalSum int64 = 0

    for _, v := range list {
        totalSum += v
    }

    return totalSum
}


func DataRead() ([]int64, error) {
    var length int64

    _, err := fmt.Scanf("%d", &length)
    if err != nil {
        return nil, err
    }

    data := make([]int64, length)

    for i := range data {
        _, err := fmt.Scanf("%d", &data[i])
        if err != nil {
            return nil, err
        }
    }

    return data, nil
}

Both of the solutions work and provide the desired result. However, one is refactored into input and output functions, with the main function minimized. In this particular situation does it even matter? One might say it’s good to practice refactoring, but in the end did the refactored solution end up better in some way? I could argue that the latter is easier to read. I could say that the first solution was easier to read, since it was so much shorter. The argument could fall either way, but in the end it’s a quick, simple, introductory algorithm and some simple refactoring.

If you’ve got a quick second, ping me @Adron if you’ve got suggestions, other refactoring, or other thoughts about this algorithm. I’m always open to a critical editorialization.

In the meantime, happy hacking!

References: The repository for this code I’ve written here is available on Github @ algorithms-101-a-big-sum

Code Katas: Kicking off With a Little JavaScript

BEWARE, this is a crazy long post. So before you jump in for a read, just know that it isn’t a two minute read. 😉

A few days ago, my friend Aeden Jameson (@daliful) asks, “you want to work through a code kata this weekend?” I thought, well yeah, that’d be cool. So we met at Cafe Fiore and hacked out the beginning of a Kata based on the Roman to Arabic and Arabic to Roman Numerals. It was fun, which led me to working up an actual blog entry related to our kata session. This however, is just me working through a similar aspect of the numeral conversions with JavaScript. Enjoy.

First things first, I’m using QUnit which is available on Github with documentation on the jQuery Site. So if you’re going to work through these, go get that first. Or use another unit testing framework. I also am using Webstorm, which is a pretty sweet IDE for editing HTML, CSS, and JavaScript available from Jetbrains. You can even do scary stuff like edit and write PHP! Oh yeah that’s right! It IS absolutely worth the money. 😀

With that out of the way, here’s what I started with. First I created a QUnit and Scripts Directory. In QUnit I placed the qunit.css and qunit.js files and in the Scripts Directory I added the jquery-1.5.1.min.js file. The later file isn’t that important at this point, but I’ve added it since I intend to use it at some point later on.

There are a few main ideas behind doing a Code Kata:

Keep the implementation code to the absolute minimum needed to pass the test.
Use a steady TDD/BDD Style testing first approach to think through each step.

[sourcecode language=”html”]
<!DOCTYPE HTML>
<html>
<head>
<title>TimePiece Object Unit Tests</title>
<link rel="stylesheet"
href="../QUnit/qunit.css"
type="text/css"
media="screen"/>
<script type="text/javascript"
src="../Scripts/jquery-1.5.1.min.js"></script>
<script type="text/javascript"
src="../QUnit/qunit.js"></script>
<script type="text/javascript">
// All the code bits go here!
</script>
<body>
<p>Roman to Arabic, Arabic to Roman…</p>
<span>QUnit Test Results…</span>

<h1 id="qunit-header">Numeral Conversions</h1>

<div id="qunit-testrunner-toolbar"></div>
<h2 id="qunit-userAgent"></h2>
<ol id="qunit-tests"></ol>
<div id="qunit-fixture">hidden text</div>
</body>
</html>
[/sourcecode]

Which gets me to the point that I have a rendering of an empty test results page, as shown below.

The next step was to get started. So jumping right in I got some code put in place for a failing test.

[sourcecode language=”JavaScript”]
module("When converting an integer into a roman numeral");

test("should receive I when passing a 1", function() {
equal(NumeralConverter.get_arabic_numeral("I"), 1, "I was returned when 1 was passed as a parameter.");
});
[/sourcecode]

Red light received, code committed, implementing for green.

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
return 1;
}
}
[/sourcecode]

Code committed. Sticking with the idea to implement the bare minimum needed, one can see pretty obviously that this isn’t much of a converter. So going forward I added the next test, for our second numeral.

[sourcecode language=”JavaScript”]
test("should receive 2 when passing a ‘II’", function() {
equal(NumeralConverter.get_arabic_numeral("II"), 2, "2 was returned when ‘II’ was passed as a parameter.");
});
[/sourcecode]

Again, nothing really specific here, nor is any defined logic really visible in what the method is needing to do. So after the commit I implemented the logic to pass this and committed this also.

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
var result = romanNumeral == "I" ? 1 : 2;
return result;
}
}
[/sourcecode]

That gets those bits passing. With a nice little JavaScript Ternary Operator. Still not hitting on the big picture of converting between the roman to arabic numerals yet, but we’re getting a little closer. Stepping up to the next test, pretty much more of the same.

[sourcecode language=”JavaScript”]
test("should receive 3 when passing a ‘III’", function() {
equal(NumeralConverter.get_arabic_numeral("III"), 3, "3 was returned when ‘III’ was passed as a parameter.");
});
[/sourcecode]

With the failing test committed, I did what seems like the easiest solution, yet so much like it is cheating. But hey! It works! That’s what is is about and one ever knows what kind of alternate solutions will crop up! Think small steps and things will lay out for you in interesting ways. Discipline!

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
return romanNumeral.length;
}
}
[/sourcecode]

So now the first tricky one comes up, the IV. The test continues to repeat. I pondered a rowset style test, but wasn’t really happy with any of the prospective solutions I saw with a quick search on the net for qunit. So on with tests as I’ve been going.

[sourcecode language=”JavaScript”]
test("should receive 4 when passing a ‘IV’", function() {
equal(NumeralConverter.get_arabic_numeral("IV"), 4, "4 was returned when ‘IV’ was passed as a parameter.");
});
[/sourcecode]

Red light received, code committed. The implementation for this, still feels like cheating. Simplest code to get the test passing possible.

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
if(romanNumeral == "IV"){
return 4;
}
return romanNumeral.length;
}
}
[/sourcecode]

Green light, code committed. Again, straight into a test.

[sourcecode language=”JavaScript”]
test("should receive 5 when passing a ‘V’", function() {
equal(NumeralConverter.get_arabic_numeral("V"), 5, "5 was returned when ‘V’ was passed as a parameter.");
});
[/sourcecode]

Red light, code committed.

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
if(romanNumeral == "IV"){
return 4;
}
else if(romanNumeral == "V"){
return 5;
}
return romanNumeral.length;
}
}
[/sourcecode]

Green light. Code committed. It seems like something is starting to brew up out of the method.

[sourcecode language=”JavaScript”]
test("should receive 6 when passing a ‘VI’", function() {
equal(NumeralConverter.get_arabic_numeral("VI"), 6, "6 was returned when ‘VI’ was passed as a parameter.");
});
[/sourcecode]

Red light. Code committed.

Green light, code committed. I implemented the next bits, but at testing that VIII returns 8 I began a refactoring. If I were to split the one Roman Numerals ‘I’ off I could then just count their length and add them to the five Roman Numeral V. I didn’t really think about how that would work past 8, but it seemed like a valid refactoring. After that, these two additional tests were completed and passing.

[sourcecode language=”JavaScript”]
test("should receive 7 when passing a ‘VII’", function() {
equal(NumeralConverter.get_arabic_numeral("VII"), 7, "7 was returned when ‘VII’ was passed as a parameter.");
});

test("should receive 8 when passing a ‘VIII’", function() {
equal(NumeralConverter.get_arabic_numeral("VIII"), 8, "8 was returned when ‘VIII’ was passed as a parameter.");
});
[/sourcecode]

The actual method implementation looked like this now.

[sourcecode language=”JavaScript”]
var NumeralConverter = {
get_arabic_numeral : function ( romanNumeral ){
var ones = 0;
var five = 0;
var result = 0;
var vCount = romanNumeral.split(/V/g).length -1;
var iCount = romanNumeral.split(/I/g).length – 1;

if(romanNumeral == "IV"){
return 4;
}
else if(vCount > 0){
five = vCount * 5;
}

ones = iCount;
result = five + ones;

return result;
}
}
[/sourcecode]

Now we’re actually getting some logic in there. If one breaks the rules, there is even a bit of foreshadowing to where the logic and looping will eventually end up. But I’m going to keep going with the KISS idea and doing a minimal implement for each failing test! Moving right along…

[sourcecode language=”JavaScript”]
test("should receive 9 when passing a ‘IX’", function() {
equal(NumeralConverter.get_arabic_numeral("IX"), 9, "9 was returned when ‘IX’ was passed as a parameter.");
});
[/sourcecode]

Ok, ok, now at this point I’m thinking, “oh jeez, this list of tests looks like a mess. These need refactored now.” I did look for a rowtest earlier, and that didn’t exist really. So something else ought to work though, but the question is what? So I looked around and just took a few minutes to think. Take a look at the tests at this point all listed together.

[sourcecode language=”JavaScript”]
module("When converting a roman numeral into an arabic numeral");

test("should receive 1 when passing a ‘I’", function() {
equal(NumeralConverter.get_arabic_numeral("I"), 1, "1 was returned when ‘I’ was passed as a parameter.");
});

test("should receive 2 when passing a ‘II’", function() {
equal(NumeralConverter.get_arabic_numeral("II"), 2, "2 was returned when ‘II’ was passed as a parameter.");
});

test("should receive 3 when passing a ‘III’", function() {
equal(NumeralConverter.get_arabic_numeral("III"), 3, "3 was returned when ‘III’ was passed as a parameter.");
});

test("should receive 4 when passing a ‘IV’", function() {
equal(NumeralConverter.get_arabic_numeral("IV"), 4, "4 was returned when ‘IV’ was passed as a parameter.");
});

test("should receive 5 when passing a ‘V’", function() {
equal(NumeralConverter.get_arabic_numeral("V"), 5, "5 was returned when ‘V’ was passed as a parameter.");
});

test("should receive 6 when passing a ‘VI’", function() {
equal(NumeralConverter.get_arabic_numeral("VI"), 6, "6 was returned when ‘VI’ was passed as a parameter.");
});

test("should receive 7 when passing a ‘VII’", function() {
equal(NumeralConverter.get_arabic_numeral("VII"), 7, "7 was returned when ‘VII’ was passed as a parameter.");
});

test("should receive 8 when passing a ‘VIII’", function() {
equal(NumeralConverter.get_arabic_numeral("VIII"), 8, "8 was returned when ‘VIII’ was passed as a parameter.");
});

test("should receive 9 when passing a ‘IX’", function() {
equal(NumeralConverter.get_arabic_numeral("IX"), 9, "9 was returned when ‘IX’ was passed as a parameter.");
});
[/sourcecode]

That’s a lot of tests. Well, I looked through the documentation a little bit, and realized that I could just do this. Is it more readable? It almost comes off as rowset tests in junit/nunit.

[sourcecode language=”JavaScript”]
module("When converting a roman numeral into an arabic numeral");

test("should receive arabic numeral", function() {
equal(NumeralConverter.get_arabic_numeral("I"), 1, "1 when ‘I’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("II"), 2, "2 when ‘II’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("III"), 3, "3 when ‘III’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("IV"), 4, "4 when ‘IV’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("V"), 5, "5 when ‘V’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("VI"), 6, "6 when ‘VI’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("VII"), 7, "7 when ‘VII’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("VIII"), 8, "8 when ‘VIII’ was passed as a parameter.");
equal(NumeralConverter.get_arabic_numeral("IX"), 9, "9 when ‘IX’ was passed as a parameter.");
});
[/sourcecode]

Either way, I’m sticking to it for now. I added the test for X.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("X"), 10, "10 when ‘X’ is passed in.");
[/sourcecode]

Then implemented it following a similar pattern that I had already started.

[sourcecode language=”JavaScript”]
get_arabic_numeral : function (romanNumeral) {
var ones = 0, fives = 0, tens = 0;
var result = 0;
var vCount = romanNumeral.split(/V/g).length – 1;
var iCount = romanNumeral.split(/I/g).length – 1;
var xCount = romanNumeral.split(/X/g).length – 1;

if (romanNumeral == "IV") {
return 4;
}
else if (romanNumeral == "IX") {
return 9;
}
else if (vCount > 0) {
fives = vCount * 5;
}
else if (xCount > 0) {
tens = xCount * 10;
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

That was easy enough. Also note, when the pattern that is now evident among the logic, the next two tests automatically pass. Now some real progress has been made.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("XI"), 11, "11 when ‘XI’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XII"), 12, "12 when ‘XII’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XIII"), 13, "13 when ‘XIII’ is passed in.");
[/sourcecode]

Now however, things get a bit tricky. Add a test for ‘VX’.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("VX"), 14, "14 when ‘VX’ is passed in.");
[/sourcecode]

So adding another simple exception, pretty much takes care of that.

if (romanNumeral == "IV") {
return 4;
}
else if (romanNumeral == "IX") {
return 9;
}
else if(romanNumeral == "VX") {
return 14;
}
else if (vCount > 0) {
fives = vCount * 5;
}
else if (xCount > 0) {
tens = xCount * 10;
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

Now that trickiness comes up when adding the test for ‘XV’.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("XV"), 15, "15 when ‘XV’ is passed in.");
[/sourcecode]

Red light, code commit. Now to implement. An actual reduction of code gets us back in action here.

if (romanNumeral == "IV") {
return 4;
}
else if (romanNumeral == "IX") {
return 9;
}
else if (romanNumeral == "VX") {
return 14;
}
else if (vCount > 0 || xCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

Green light. Code Commit. Now for the next three tests, they’ll all pass. The next test that we run into that gives us a failing test is for 19, or ‘XIX’. For the tests below I went ahead and added XVI, XVII, and XVIII.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("XVI"), 16, "16 when ‘XVI’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XVII"), 17, "17 when ‘XVII’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XVIII"), 18, "18 when ‘XVIII’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XVIII"), 19, "19 when ‘XIX’ is passed in.");
[/sourcecode]

Red light, code commit.

if (romanNumeral == "IV") {
return 4;
}
else if (romanNumeral == "IX") {
return 9;
}
else if (romanNumeral == "VX") {
return 14;
}
else if (romanNumeral == "XIX") {
return 19;
}
else if (vCount > 0 || xCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

Green light, code commit. Add the test for ‘XX’ and you’ll find that this test automatically passes also. There’s still soemthing to be done about the odd else if assigned values above! But onward. After the test for ‘XX’, I’ll jump right in and see how far I can get. Not until 24 do I run into an issue.

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("XXI"), 21, "21 when ‘XXI’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XXII"), 22, "22 when ‘XXII’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XXIII"), 23, "23 when ‘XXIII’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("XXIV"), 24, "24 when ‘XXIV’ is passed in.");
[/sourcecode]

It seems like there is some type of logic happening, some repeatable logic. So I started giving it a good look over. I will admit, I went ahead and worked through several more of the tests and implementation details just to force more of the if else statements to be apparent. I added tests for 25-30 and implemented passing tests with the following code.

if (romanNumeral == "IV") {
return 4;
}
else if (romanNumeral == "IX") {
return 9;
}
else if (romanNumeral == "XIV") {
return 14;
}
else if (romanNumeral == "XIX") {
return 19;
}
else if (romanNumeral == "XXIV") {
return 24;
}
else if (romanNumeral == "XXIX") {
return 29;
}
else if (vCount > 0 || xCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

I started to stop and do research, look up some other functions that already do this. I wanted to bad, but I stuck with the original idea behind the Kata. Just implement the bare minimum code and go through the red, green, refactor approach. In the end I stuck with that approach and came up with this mess.

if (vCount > 0 || xCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
}

if (romanNumeral.length > 1) {
if (romanNumeral == "IV" || romanNumeral == "IX") {
var workingNumber = fives + tens – iCount;
return workingNumber;
}
else if (romanNumeral == "XIV") {
return 14;
}
else if (romanNumeral == "XIX") {
return 19;
}
else if (romanNumeral == "XXIV") {
return 24;
}
else if (romanNumeral == "XXIX") {
return 29;
}
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

From here, I had to get the IV or IX off of the larger roman numerals. I needed some string capabilties, so I pulled in some libraries for string manipulation, namely the Underscore.js + Underscore.string libraries. After that refactor, I knocked out all the code (yup, deleting code!) around the extra else if statements.

if (vCount > 0 || xCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
}

if (romanNumeral.length > 1) {
if (_(romanNumeral).endsWith("IV") || _(romanNumeral).endsWith("IX")) {
var workingNumber = fives + tens – iCount;
return workingNumber;
}
}

ones = iCount;
result = fives + ones + tens;

return result;
}
[/sourcecode]

At this point I was fairly confident that I had a huge number of effective conversions. So I decided to skip a few tests and head into the other numbers and other exception criteria. I did a commit for the refactor that I just finished and then jumped into a test for L, the Roman Numeral which represents 50, and the other numbers M, D, and C. I did write these individually, and then added the code, but I’ve added them altogether here to conserve space in this already long blog entry. 😉

[sourcecode language=”JavaScript”]
equal(NumeralConverter.get_arabic_numeral("L"), 50, "50 when ‘L’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("M"), 1000, "1000 when ‘M’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("D"), 500, "500 when ‘D’ is passed in.");
equal(NumeralConverter.get_arabic_numeral("C"), 100, "100 when ‘C’ is passed in.");
[/sourcecode]

Red light, committed code. Implement.

[sourcecode language=”JavaScript”]
get_arabic_numeral : function (romanNumeral) {
var ones = 0, fives = 0, tens = 0, fifties = 0;
var hundreds = 0, fiveHundreds = 0, thousands = 0;
var result = 0;
var vCount = romanNumeral.split(/V/g).length – 1;
var iCount = romanNumeral.split(/I/g).length – 1;
var xCount = romanNumeral.split(/X/g).length – 1;
var lCount = romanNumeral.split(/L/g).length – 1;
var cCount = romanNumeral.split(/C/g).length – 1;
var dCount = romanNumeral.split(/D/g).length – 1;
var mCount = romanNumeral.split(/M/g).length – 1;

if (vCount > 0 || xCount > 0 || lCount > 0 || cCount > 0 || dCount > 0 || mCount > 0) {
fives = vCount * 5;
tens = xCount * 10;
fifties = lCount * 50;
hundreds = cCount * 100;
fiveHundreds = dCount * 500;
thousands = mCount * 1000;
}

if (romanNumeral.length > 1) {
if (_(romanNumeral).endsWith("IV") || _(romanNumeral).endsWith("IX")) {
var workingNumber = fives + tens – iCount;
return workingNumber;
}
}

ones = iCount;
result = ones + fives + tens + fifties + hundreds + fiveHundreds + thousands;

return result;
}
[/sourcecode]

At this point, one can see some of the changes from refactoring, and the practice of TDD for this specific kata. It is a great way to become more efficient at thinking in a TDD way, or a touch of how one might do BDD. I hope to have more blog entries about BDD vs. TDD, how to do this, and how to get better at it. Of course, I can only write about what I know or am learning myself, and with this particular occupation I’m always learning. 😉

Hopefully this was useful, as material and as an idea. I’m not 100% finished with this kata, and I will post the code in its completed form once I’m done. For now, enjoy, and practice that TDD/BDD awesomeness!

A Zillion Ruby Kōans

NOTE: Because of formatting, I couldn’t have a curly bracket with a colon and an “o” or it turns up with some unavailable WordPress Emoticon URI. So thus I have changed items with this naming to :z_one and :z_two respectively.

Yup, still moving through all the Ruby Koans. There are, after all 276 of these things! 😉 So no more yapping, onto the notes and green lighting the tests. Cheers!

[sourcecode language=”ruby”]
def test_creating_hashes
empty_hash = Hash.new
assert_equal Hash, empty_hash.class
assert_equal({ }, empty_hash)
assert_equal 0, empty_hash.size
end

def test_hash_literals
hash = { :z_one => "uno", :z_two => "dos" }
assert_equal 2, hash.size
end

def test_accessing_hashes
hash = { :z_one => "uno", :z_two => "dos" }
assert_equal "uno", hash[:z_one]
assert_equal "dos", hash[:z_two]
assert_equal nil, hash[:doesnt_exist]
end
[/sourcecode]

From test_creating_hashes a Hash.new or {} both appear to create a new empty hash object. The second test creates and adds values to the hash. The third test has asserts that verify the data is inserted in the positions that are expected.

[sourcecode language=”ruby”]
def test_changing_hashes
hash = { :z_one => "uno", :z_two => "dos" }
hash[:z_one] = "eins"

expected = { :z_one => "eins", :z_two => "dos" }
assert_equal true, expected == hash

# Bonus Question: Why was "expected" broken out into a variable
# rather than used as a literal?
end
[/sourcecode]

Again, the hash is setup into the hash variable. Then the expected is setup in another variable. Since Ruby is pointer oriented, the expected variable is setup identical to the hash variable to assure that they truly are identical.

[sourcecode language=”ruby”]
def test_hash_is_unordered
hash1 = { :z_one => "uno", :z_two => "dos" }
hash2 = { :z_two => "dos", :z_one => "uno" }

assert_equal true, hash1 == hash2
end

def test_hash_keys
hash = { :z_one => "uno", :z_two => "dos" }
assert_equal 2, hash.keys.size
assert_equal true, hash.keys.include?(:z_one)
assert_equal true, hash.keys.include?(:z_two)
assert_equal Array, hash.keys.class
end

def test_hash_values
hash = { :z_one => "uno", :z_two => "dos" }
assert_equal 2, hash.values.size
assert_equal true, hash.values.include?("uno")
assert_equal true, hash.values.include?("dos")
assert_equal Array, hash.values.class
end
[/sourcecode]

test_hash_is_unordered shows that a hash, no matter the order the values are assigned, assigns them to the values that are directly set to.

[sourcecode language=”ruby”]
def test_combining_hashes
hash = { "jim" => 53, "amy" => 20, "dan" => 23 }
new_hash = hash.merge({ "jim" => 54, "jenny" => 26 })

assert_equal true, hash != new_hash

expected = { "jim" => __, "amy" => 20, "dan" => 23, "jenny" => __ }
assert_equal false, expected == new_hash
end
[/sourcecode]

This test asserts that the two different hashes are different, nothing amazing or odd there. The second part asserts that the next and expected hashes are different. Which again, is what we expect.

[sourcecode language=”ruby”]
def test_default_value
hash1 = Hash.new
hash1[:z_one] = 1

assert_equal 1, hash1[:z_one]
assert_equal nil, hash1[:z_two]

hash2 = Hash.new("dos")
hash2[:z_one] = 1

assert_equal 1, hash2[:z_one]
assert_equal "dos", hash2[:z_two]
end
[/sourcecode]

This test confirms that a hash with a request against a hash position that isn’t assigned to yet returns nil. The later two asserts show that a number compared to the hash position that contains a number compares as a number, and a string compared to a position that has a string also compares as equal.

Until next time, hack some koans.

Kōans of Code

I’ve continued the Kōans, but there is one thing that won’t be noticeable from this blog entry. I however wanted to mention it. The first blog entry was worked through on an OS-X Apple Machine, the second on an Ubunta Linux Machine, and now I’m heading for this blog entry to be completed with Windows 7. It is of course completely irrelevant, but at the same time very relevant. 🙂 But enough about operating system awesomeness. Let’s take a look at the new gazillion Kōans that caught my note taking.

[sourcecode language=”ruby”]
class AboutArrays < EdgeCase::Koan
def test_creating_arrays
empty_array = Array.new
assert_equal Array, empty_array.class
assert_equal 0, empty_array.size
end
[/sourcecode]

Easy peasy. Array.new creates a new empty array. Got it. An Array is the class type retrieved when calling empty_array.class. Got it. The empty array has a size of zero, Got it.

[sourcecode language=”ruby”]
def test_array_literals
array = Array.new
assert_equal [], array

array[0] = 1
assert_equal [1], array

array[1] = 2
assert_equal [1, 2], array

array << 333
assert_equal [1, 2, 333], array
end
[/sourcecode]

Ok, this one has some interesting bits in it. Having array[0] and array[1] assigned to a value of 1 and 2 seems standard operating practice for a language. This dual chevrons pointing into the array thing is a little more unique. This operator appears to take the value on the right, and put it onto the array’s stack. Simply, the double kick operator (or whatever it is called) puts the value on the next available array index position. Ok, cool. Got it.

[sourcecode language=”ruby”]
def test_accessing_array_elements
array = [:peanut, :butter, :and, :jelly]

assert_equal :peanut, array[0]
assert_equal :peanut, array.first
assert_equal :jelly, array[3]
assert_equal :jelly, array.last
assert_equal :jelly, array[-1]
assert_equal :butter, array[-3]
end
[/sourcecode]

Alright, got an array with 4 elements in it. First assert confirms that :peanut is the returned value from the first element in the array. The array.first call functionally does the same thing. The third assert gets the 3rd value in the array, keeping in mind a zero based index for the array, that gives us the 4th actual item in the list of items stored within the array. I love it, standard programmer weirdness. Why do programmers start with zero when nobody on earth starts a “list” of items with a zero. Blagh, whatever, that’s the reality of it. (That was, in a sense, somewhat rhetorical, I get the underlying reasons but that doesn’t help explain a zero based index to initial non-programmers.)

[sourcecode language=”ruby”]
def test_slicing_arrays
array = [:peanut, :butter, :and, :jelly]

assert_equal [:peanut], array[0,1]
assert_equal [:peanut, :butter], array[0,2]
assert_equal [:and, :jelly], array[2,2]
assert_equal [:and, :jelly], array[2,20]
assert_equal [], array[4,0]
assert_equal [], array[4,100]
assert_equal nil, array[5,0]
end
[/sourcecode]

Slicing arrays again with the PB & J. With two values, the first thing I notice is that this is no multidimensional array. Two values within the square brackets means that you have a starting position and then a value of how many to retrieve. If there is a value like the fourth asset, starting at the 2nd position (3rd actual value) and taking the next 20 elements, basically retrieves whatever values are available, which in this case gets us 2 elements.

Now, I’m a slight bit perplexed though as to why nil is returned for something request nothing from the 5th starting point of the array versus the same being requested from the 4th starting point in the array. I’ll have to read up on that…

[sourcecode language=”ruby”]
def test_arrays_and_ranges
assert_equal Range, (1..5).class
assert_not_equal [1,2,3,4,5], (1..5)
assert_equal [1,2,3,4,5], (1..5).to_a
assert_equal [1,2,3,4], (1…5).to_a
end
[/sourcecode]

Again, identifying the class object type is easy, a range of numbers is a Range Object. Check. A range stating 1..5 does not provide the numbers one through five. Calling to_a on a range however does provide you those numbers. Doing the same thing to an array specified with three periods instead of two with the to_a provides numbers one through four. That seems odd, but I got it.

[sourcecode language=”ruby”]
def test_slicing_with_ranges
array = [:peanut, :butter, :and, :jelly]

assert_equal [:peanut, :butter, :and], array[0..2]
assert_equal [:peanut, :butter], array[0…2]
assert_equal [:and, :jelly], array[2..-1]
assert_equal [:peanut, :butter, :and], array[0..-2]
end
[/sourcecode]

Slicing an array of four values, stating the starting and ending point with the syntax of a range, provides the elements based on the values associated with that range. I actually added an assert to this test to determine what exactly the negative values do. It appears that the array starts at the point of the first number, then follows a range from that until the negative number from the end of the array. So with 10 items, starting at point 2 and ending -2 from the end will retrieve the middle 6 elements. Strange, but I can see how this would be very useful.

[sourcecode language=”ruby”]
def test_pushing_and_popping_arrays
array = [1,2]
array.push(:last)

assert_equal [1,2,:last], array

popped_value = array.pop
assert_equal :last, popped_value
assert_equal [1, 2], array
end
[/sourcecode]

Pop. Easy, get that last value. But wait a second, the array itself doesn’t have :last in it? Aha! Popping it not only gets that last value, but literally takes the value out of the array.

[sourcecode language=”ruby”]
def test_shifting_arrays
array = [1,2]
array.unshift(:first)

assert_equal [:first, 1, 2], array

shifted_value = array.shift
assert_equal :first, shifted_value
assert_equal [1,2], array
end

end
[/sourcecode]

Ah, kind of like a popped value but shifted out of the array? Weird, this is a little confusing at first. I see what it is appearing to do, but figured a good read of the documentation would be good. I did a search on Google and the first hit is someone asking this question.

What does Ruby’s Array Shift Do?

From that quick read it appears that shift and unshift are used similar to pop and push in a stack (ala git, etc).

That answers that question. With that, I’m off to other realms.

Category: Code Katas

Algorithms 101 Roads & Town Centers

Like this:

Algorithms 101 – Big Sums

Big Sum!

Input & Sample Input

Output & Sample Output

The Solution

A Refactoring?

Like this:

Code Katas: Kicking off With a Little JavaScript

Like this:

A Zillion Ruby Kōans

Like this:

Kōans of Code

Like this:

Share this:

Like this:

Big Sum!

Input & Sample Input

Output & Sample Output

The Solution

A Refactoring?

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this: