6
\$\begingroup\$

In an attempt to hide from the sun outside, I gave the community challenge "Rainfall" a try.

Code here, specific questions below.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Collectors;

public class RainfallChallenge
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);

        // building the farm
        int size = input.nextInt();
        Farm farm = new Farm(size);

        // setting heights, creating fields
        for (int x = 0; x < size; x++)
            for (int y = 0; y < size; y++)
                farm.putField(x, y, new Field(input.nextInt()));

        // skynet addon: knows every field as key and maps to the list of all fields of its basin
        HashMap<Field, ArrayList<Field>> basins = new HashMap<Field, ArrayList<Field>>();

        for (int x = 0; x < size; x++)
            for (int y = 0; y < size; y++)
                groupFields(basins, farm.getField(x, y));

        // from lists of fields to sorted list of basin sizes
        System.out.println(
            new StringBuilder(
                basins.values()
                .stream()
                .distinct()                                     // set of field lists
                .mapToInt(b -> b.size())                        // to their number of fields
                .sorted()                                       
                .boxed()                                        // in bubble wrap
                .map(String::valueOf)                           // to String stream
                .collect(Collectors.joining(" "))).reverse());  // desired order
    }

    private static ArrayList<Field> groupFields(HashMap<Field, ArrayList<Field>> basins, Field field)
    {
        ArrayList<Field> basin;

        // end recursion: revisit field
        if(basins.containsKey(field)) 
        {
            return basins.get(field);
        }
        // end recursion: new basin
        else if(field.getLowestNeighbor() == field) 
        {
            basin = new ArrayList<Field>();
        }
        // recursion: find basin of lowest neighbor
        else
        {
            basin = groupFields(basins, field.getLowestNeighbor());
        }

        basin.add(field);
        basins.put(field, basin);
        return basin;
    }
}

class Farm
{
    private Field[][] fields;

    public Farm(int size)
    {
        fields = new Field[size][size];
    }

    public void putField(int x, int y, Field field)
    {
        fields[x][y] = field;

        // check all 4 neighbors
        field.setNeighbor(getField(x + 1, y));
        field.setNeighbor(getField(x - 1, y));
        field.setNeighbor(getField(x, y + 1));
        field.setNeighbor(getField(x, y - 1));
    }

    public Field getField(int x, int y)
    {
        try
        {
            return fields[x][y] != null ? fields[x][y] : NullField.instance;
        }
        catch (IndexOutOfBoundsException e)
        {
            return NullField.instance;
        }
    }
}

class Field
{
    private int height;
    private Field lowestNeighbor;

    public Field(int height)
    {
        this.height = height;
        lowestNeighbor = this;
    }

    public void setNeighbor(Field neighbor)
    {
        if (neighbor.height < lowestNeighbor.height)
        {
            lowestNeighbor = neighbor;
        }
        else if (neighbor.lowestNeighbor.height > height)
        {
            neighbor.lowestNeighbor = this; 
        }
    }

    public Field getLowestNeighbor()
    {
        return lowestNeighbor;
    }
}

class NullField extends Field
{
    public static final NullField instance = new NullField();

    private NullField()
    {
        super(Integer.MAX_VALUE);
    }
}

I got lazy and put everything into one file. General reviews are appreciated, as always.

However, there are two things I want to specifically ask about:

  1. I'm new to Stream.

    // from lists of fields to sorted list of basin sizes
    System.out.println(
        new StringBuilder(
            basins.values()
            .stream()
            .distinct()                                     // set of field lists
            .mapToInt(b -> b.size())                        // to their number of fields
            .sorted()                                       
            .boxed()                                        // in bubble wrap
            .map(String::valueOf)                           // to String stream
            .collect(Collectors.joining(" "))).reverse());  // desired order
    

    I think this code does quite a lot (values of a HashMap as a Set, to integers, sorted, to String) in a compact yet readable way and I see the value of this language feature. Is there anything bad? I had to use StringBuilder to reverse the result. This seems bad. The Stream cannot be reversed as it's considered endless in general. There are workarounds for when I know it's not, but they aren't very readable and not self documenting at all. Ideally, I want to tell .sorted() if I want the order to be ascending or descending. But there's no parameter for that. How can this be done more elegantly?

  2. The use of "null object" pattern to build the grid. The problem I'm trying to solve here is that not every Field has all 4 neighbors. The first one at (0/0) has none at (-1/0) and (0/-1). Also, during construction, future fields are not yet available. The idea behind the pattern (as far as I understand it) is to always have an object, no matter what. If the logic of the program does not allow it, return a special object that acts "neutrally" in the calculation of the program.

    public Field getField(int x, int y)
    {
        try
        {
            return fields[x][y] != null ? fields[x][y] : NullField.instance;
        }
        catch (IndexOutOfBoundsException e)
        {
            return NullField.instance;
        }
    }
    

    This way, there's always an object returned by getField and never null. Does it make sense to apply this pattern here? I only heard of use cases where it might substitute a an uninitialised Object to prevent checks for null in the actual code. I thought the fields out of bounds or not yet created are good examples for that. Is the implementation with exceptions ok? This will occur quite often during execution.

    class NullField extends Field
    {
        public static final NullField instance = new NullField();
    
        private NullField()
        {
            super(Integer.MAX_VALUE);
        }
    }
    

    I made this a singleton because I only want to create one such object. There's no second null either. Other than that I could have provided @Overrides for the methods of the Field class, for example:

    public void setNeighbor(Field neighbor)
    {
        // pffft, whatever
    }
    

    But I never call those on the nullobject, so I omitted them. Is this bad practise?

\$\endgroup\$
1
\$\begingroup\$

You can sort the stream using a Comparator using sorted(Comparator<? super T> comparator)

You want to sort using the reverse of the natural order, there is a static method in Compartator to get the Comparator you need.

.sorted(Comparator.reverseOrder())

You could make some small changes in your stream code to use this method:

System.out.println( 
    basins.values()
    .stream()
    .distinct()                                // set of field lists
    .map(b -> b.size())                        // to their number of fields
    .sorted(Comparator.reverseOrder)           // desired order                            
    .map(Integer::toString)                    // to String stream
    .collect(Collectors.joining(" ")));  
\$\endgroup\$
  • \$\begingroup\$ Great tip. I didn't know this is possible. Why is this not part of the sorted() documentation? To make this work with the original code, the order of boxing and sorting has to be reversed: first box, then sort. \$\endgroup\$ – I'll add comments tomorrow Aug 31 '16 at 21:23
  • 1
    \$\begingroup\$ Stream has a method sorted with a Comparator parameter but IntStream doesn't have this method. You are using mapToInt and then boxed after sorting. I would change mapToInt to map and remove boxed. This way you can use the sortmethod in Stream and your code is boxing the sizes to Integer in both cases. \$\endgroup\$ – David SN Sep 1 '16 at 7:47
  • \$\begingroup\$ Ah, this is where auto boxing happens. The new code reduces self documentation a little bit as it's not mapping to int explicitly, but due to the shortness of the code and the call to size() this is an ok price I'm willing to pay to get rid of the explicit boxing line. Thanks. \$\endgroup\$ – I'll add comments tomorrow Sep 1 '16 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.