Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Java Code Challenge: Nodes Solution

DZone's Guide to

Java Code Challenge: Nodes Solution

I’ve been really pleased with the responses to the node challenge. This is a relatively simple challenge but one that demonstrates why programming is more of an art than a science.

· Java Zone
Free Resource

Bitbucket is for the code that takes us to Mars, decodes the human genome, or drives your next car. What will your code do? Get started with Bitbucket today, it's free.

I’ve been really pleased with the responses to the node challenge. Great work everybody!

This is a relatively simple challenge but one that demonstrates why programming is more of an art than a science. Every single response was different in design and style. There is no one “correct” answer, which is one of the wonderful things about programming.

One of the aims for this series for me is to highlight more than just correct solutions, but solutions which are good code—code which, if in a production code base, would not quickly become legacy code or difficult to maintain.

This is not an inditement on any of the solutions- it’s a simple code challenge and so it stands to reason most people will just be solving it for the challenge, not to write beautiful code.

The General Solution

The reason this is particularly easy as a challenge is that the input tells us how many nodes to expect- we don’t need to figure this out for ourselves. We’re also assuming that all our data input is accurate which makes it super simple.

So, we simply need to add up how many times a node ID appears in the input and store that number for each node. Pretty simple bucketing, which is what most people chose to do. Take this example from Jusio, which uses an array to store the totals.

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Scanner;

public class Degrees {

    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(Files.newBufferedReader(Paths.get(args[0])));
        final int[] dependencies = new int[scanner.nextInt()];
        while (scanner.hasNext()) {
            dependencies[scanner.nextInt() - 1]++;
            dependencies[scanner.nextInt() - 1]++;
        }
        for (int i = 0; i < dependencies.length; i++) {
            System.out.printf("Node %s has degree of %s\n", i + 1, dependencies[i]);
        }
    }
}

As we know how many nodes there are up front an array is a perfectly viable solution.

In Java 8 we can "one line" this thanks to Streams. Jusio also offered up a Java solution.

Files.lines(Paths.get(args[0]))
  .skip(1)
  .flatMap(it -> Stream.of(it.split(" ")))
  .collect(Collectors.groupingBy(Integer::new, Collectors.counting()))
  .forEach((node, count) -> out.printf("Node %s has degree of %s\n", node, count));

A nice condensed solution. However, it’s important to be careful with Java 8’s functional features. Since their release I’ve seen a tendancy by developers to go overboard to try and crush all their code into a one liner. When writing code readability should be our number one concern. Clean, readable code is easier to maintain.  I personally find the Java 7 version easier to comprehend, although for an example this simple it's not that big a problem.

A Pause for Thought

The thing that has come across pretty consistenly is that most of the solutions have not been written using TDD or tests. That’s fine- I understand not everyone loves TDD as much as I do. But that has lead to one-shot code that has no seperation of concerns. The entire solution is shoved into a main method. As mentioned before this produces an adequate solution but not sustainable code.

I received an email after posting this challenge:

“to be clear, is the input standard in or a file?”

The answer for me is clear- it doesn’t matter. The way I approached this challenge was to start with the functionality- the bucketing- and providing the data in using a test, and testing the data out by giving access to the underlying sorted data.  A big shout out to Javier Villarreal who clearly used TDD to come up with his solution, and in similar fashion didn't tackle what form the data came in as.

package software.schwering.javacodechallenge;

import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.TreeMap;
import java.util.stream.Stream;

public class NodeDegrees extends TreeMap<Integer, Long> {

    private static final long serialVersionUID = 1L;

    public NodeDegrees(Path inputFile) throws IOException {
        this(Files.lines(inputFile).skip(1));
    }

    public NodeDegrees(Stream<String> input) {
        putAll(input.map(s -> s.split(" "))
        .flatMap(s -> Stream.of(s))
        .collect(groupingBy(Integer::new, counting())));
    }

    public static void main(String... args) throws IOException {
        new NodeDegrees(Paths.get(args[0]))
        .forEach((node, degree)-> System.out.format("Node %d has a degree of %d\n", node, degree));
    }
}

package software.schwering.javacodechallenge;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.stream.Stream;

import org.hamcrest.BaseMatcher;
import org.hamcrest.Description;
import org.hamcrest.Matcher;
import org.junit.Test;

public class NodeDegreesTest {

    @Test
    public void noDegreesForEmptyInput() {
        Stream<String> input = Stream.of();

        NodeDegrees nodeDegrees = new NodeDegrees(input);

        assertThat(nodeDegrees.size(), is(0));
    }

    @Test
    public void twoDegreesOf1forOneEdge() {
        Stream<String> input = Stream.of("1 2");

        NodeDegrees nodeDegrees = new NodeDegrees(input);

        assertThat(nodeDegrees.size(), is(2));
        assertThat(nodeDegrees.get(1), hasDegreeOf(1));
        assertThat(nodeDegrees.get(2), hasDegreeOf(1));
    }

    @Test
    public void incomingAndOutgoringEdgeIsCounted() {
        Stream<String> input = Stream.of("1 2", "2 3");

        NodeDegrees nodeDegrees = new NodeDegrees(input);

        assertThat(nodeDegrees.size(), is(3));
        assertThat(nodeDegrees.get(1), hasDegreeOf(1));
        assertThat(nodeDegrees.get(2), hasDegreeOf(2));
        assertThat(nodeDegrees.get(3), hasDegreeOf(1));
    }

    @Test
    public void example() {
        Stream<String> input = Stream.of("1 2", "1 3", "2 3", "1 4", "3 4", "1 5", "2 5", "1 6", "2 6", "3 6", "3 7",
        "5 7", "6 7", "3 8", "4 8", "6 8", "7 8", "2 9", "5 9", "6 9", "2 10", "9 10", "6 11", "7 11", "8 11",
        "9 11", "10 11", "1 12", "6 12", "7 12", "8 12", "11 12", "6 13", "7 13", "9 13", "10 13", "11 13",
        "5 14", "8 14", "12 14", "13 14", "1 15", "2 15", "5 15", "9 15", "10 15", "11 15", "12 15", "13 15",
        "1 16", "2 16", "5 16", "6 16", "11 16", "12 16", "13 16", "14 16", "15 16");

        NodeDegrees nodeDegrees = new NodeDegrees(input);

        assertThat(nodeDegrees.size(), is(16));
        assertThat(nodeDegrees.get(1), hasDegreeOf(8));
        assertThat(nodeDegrees.get(2), hasDegreeOf(8));
        assertThat(nodeDegrees.get(3), hasDegreeOf(6));
        assertThat(nodeDegrees.get(4), hasDegreeOf(3));
        assertThat(nodeDegrees.get(5), hasDegreeOf(7));
        assertThat(nodeDegrees.get(6), hasDegreeOf(10));
        assertThat(nodeDegrees.get(7), hasDegreeOf(7));
        assertThat(nodeDegrees.get(8), hasDegreeOf(7));
        assertThat(nodeDegrees.get(9), hasDegreeOf(7));
        assertThat(nodeDegrees.get(10), hasDegreeOf(5));
        assertThat(nodeDegrees.get(11), hasDegreeOf(9));
        assertThat(nodeDegrees.get(12), hasDegreeOf(8));
        assertThat(nodeDegrees.get(13), hasDegreeOf(8));
        assertThat(nodeDegrees.get(14), hasDegreeOf(5));
        assertThat(nodeDegrees.get(15), hasDegreeOf(9));
        assertThat(nodeDegrees.get(16), hasDegreeOf(9));
    }

    @Test
    public void exampleStringFormat() throws IOException {
        ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
        PrintStream out = new PrintStream(byteStream);
        System.setOut(out);

        NodeDegrees.main("in.txt");

        assertEquals("Node 1 has a degree of 8\n" + "Node 2 has a degree of 8\n" + "Node 3 has a degree of 6\n"
        + "Node 4 has a degree of 3\n" + "Node 5 has a degree of 7\n" + "Node 6 has a degree of 10\n"
        + "Node 7 has a degree of 7\n" + "Node 8 has a degree of 7\n" + "Node 9 has a degree of 7\n"
        + "Node 10 has a degree of 5\n" + "Node 11 has a degree of 9\n" + "Node 12 has a degree of 8\n"
        + "Node 13 has a degree of 8\n" + "Node 14 has a degree of 5\n" + "Node 15 has a degree of 9\n"
        + "Node 16 has a degree of 9\n", byteStream.toString());
    }

    private static Matcher<Long> hasDegreeOf(long degree) {
        return new BaseMatcher<Long>() {

            @Override
            public boolean matches(Object item) {
                return Long.valueOf(degree).equals(item);
            }

            @Override
            public void describeTo(Description description) {
                description.appendText("the node should have a degree of").appendValue(degree);
            }
        };
    }
}

This way I can then plug whatever output and inputs in that I want. I can create a file input or a command line input, I can change the format of the output easily. It’s a nice and decomposed solution.

I do have some issues with this solution though.  Instead of extending TreeMap I would have used composition instead of inheritance which is generally considered best practice, particular as it becomes clearer what's going on as you don't need to understand the inner workings of TreeMap to understand the solution.

I also think the tests could do with some refactoring, particularly the example() test.  There's a lot of data there which I imagine would be hard to debug in the case of an error.  I would also probably create a helper method for looping through the result data and making the assertions.

Bitbucket is the Git solution for professional teams who code with a purpose, not just as a hobby. Get started today, it's free.

Topics:
puzzler ,challenges ,java

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}