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:
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 aSet
, to integers, sorted, toString
) in a compact yet readable way and I see the value of this language feature. Is there anything bad? I had to useStringBuilder
to reverse the result. This seems bad. TheStream
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?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 nevernull
. 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 fornull
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@Override
s for the methods of theField
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?