Java Code Challenge: Bus Gossip Solution

Challenge #2 in the series is much more difficult than challenge one. This thing can get complex if you don’t plan it out a bit. Well done to everyone who submitted a solution, and remember that none of the below is a criticism of the participants, but hopefully can help everyone to improve their code and to help start a discussion.

For me (and most of the solutions created) the challenge breaks down into two sections:

• The “simulation” (or “day”), where we run through a whole chunk of for loops to find the answer, specifically loop through all the minutes of the day, loop through the drivers to advance their stop, loop through to exchange gossip, loop through to see if have a solution.

• The Bus Driver, who is most likely stateful for knowing which gossip they’ve collected.

With that many loop-throughs, it’s easy to produce code that’s hard to understand and maintain. Take for example this solution for the simulation:

public class Gossip {

    private int mins = 0;         // elapsed minutes
    private int[][] routes;        // the bus routes
    private int allGossip;           // all gossips (2^n-1)
    private int[] currentLocation; // current location of each driver
    private int[] currentGossip;   // current gossip set
    private String result = null; // result of evaluation;
    private boolean isDebug = false;

    public Gossip(final int[][] routes) {
        Objects.requireNonNull(routes, "Illegal number of routes");
        if(routes.length ==0 || routes.length > 32) {
            throw new IllegalArgumentException("Invalid number of routes");
        }
        this.routes = routes;
        this.allGossip = (int) Math.pow(2, routes.length)-1;
        this.currentLocation = new int[routes.length];
        this.currentGossip = new int[routes.length];
        for(int i=0; i<routes.length; ++i) {
            currentGossip[i] = 1 << i;
        }
    }

    public String getResult() {
        // only eval once
        if(result == null) {
            // loop until all gossip is disseminated, or until we've tried for 8 hours
            for(mins = 0; mins <= 60 * 8; ++mins) {
                // exchange gossip
                for(int i = 0; i < routes.length; ++i) {
                    for(int j = 0; j < routes.length; ++j) {
                        if(i == j) {
                            continue;
                        }
                        if(routes[i][currentLocation[i]] == routes[j][currentLocation[j]]) {
                            currentGossip[i] |= currentGossip[j];
                        }
                    }
                }
                if(isDebug) {
                    logState();
                }
                // evaluate completion criteria
                if(IntStream.of(currentGossip).allMatch(g -> g == allGossip)) {
                    result = (mins + 1) + "";
                    break;
                }
                // move all drivers
                for(int i = 0; i < routes.length; ++i) {
                    currentLocation[i] = ++currentLocation[i] % routes[i].length;
                }
            }
            if(result == null) {
                result = "never";
            }
        }
        return result;
    }

    // logs the time, gossip-set, route, and current location for each driver
    void logState() {
        System.out.println("t = "+ mins);
        for(int i=0; i<routes.length; ++i) {
            System.out.print(i);
            System.out.print("\t[");
            for(int j=0; j<currentGossip.length; ++j) {
                System.out.print((currentGossip[i] & 1<<j)>>j);
            }
            System.out.print("]");
            for(int j=0; j<routes[i].length; ++j) {
                System.out.print("\t");
                System.out.print(routes[i][j]);
                if(j == currentLocation[i]) {
                    System.out.print("*"); // current_loc stop
                }
            }
            System.out.println();
        }
    }

    public Gossip setDebug(boolean isDebug) {
        this.isDebug = isDebug;
        return this;
    }


}

For me, although the solution may be correct, it’s hard to understand and would turn into a maintenance nightmare. The getResult method (which I would rename to make clear what result we’re getting) is a huge block of code. It would be much better to pull this out into smaller methods.

This also would make the comments redundant. Comments are a bad thing for maintainable code. They quickly become outdated, incorrect and out of place. Most developers (myself included) routinely ignore them now. Instead, create smaller methods and use method names as documentation.

// move all drivers
                for(int i = 0; i < routes.length; ++i) {
                    currentLocation[i] = ++currentLocation[i] % routes[i].length;
                }
        …becomes….

        public void advanceAllDriversToNextLocation(){
         for(int i = 0; i < routes.length; ++i) {
                    currentLocation[i] = ++currentLocation[i] % routes[i].length;
                }
        }

A really good example of this comes from GitHub user @lutzhorn who has broken down the solution into lots of nice small helper methods.

/**
 * A day with a set of drivers. The only public method can be used to calculate
 * the minute after which all drivers know all gossips.
 *
 * @author Lutz Horn <lutz.horn@posteo.de>
 */
public class Day {

    private final List<BusDriver> drivers = new ArrayList<>();
    private final List<Integer> allGossips = new ArrayList<>();

    public Day(BusDriver... drivers) {
        this.drivers.addAll(Arrays.asList(drivers));
        for (final BusDriver driver : this.drivers) {
            allGossips.add(driver.getGossip());
        }
    }

    public Day(List<BusDriver> drivers) {
        this.drivers.addAll(drivers);
        for (final BusDriver driver : this.drivers) {
            allGossips.add(driver.getGossip());
        }
    }

    /**
     * Calculates the minute after which all drivers know all gossips.
     *
     * @return the minutea after which all drivers know all gossips.
     * @throws GossipsAreNeverKnownByAllDriversException when not all drivers
     * know all gossips after the complete day
     */
    public Integer minuteAllDriversKnowAllGossips() throws GossipsAreNeverKnownByAllDriversException {
        if (drivers.size() == 1) {
            return 0;
        }

        for (int minute = 1; minute <= 480; minute++) {
            final Map<Integer, Set<BusDriver>> stops = calculateDriversAtStops(minute);
            shareGossips(stops);
            if (allDriversKnowAllGossip()) {
                return minute;
            }
        }

        throw new GossipsAreNeverKnownByAllDriversException();
    }

    private boolean allDriversKnowAllGossip() {
        // Check if all drivers know all gossips now.
        boolean allDrivesknowAllGossips = true;
        for (final BusDriver driver : drivers) {
            if (!allGossips.equals(driver.getKnownGossips())) {
                allDrivesknowAllGossips = false;
            }
        }
        return allDrivesknowAllGossips;
    }

    private Map<Integer, Set<BusDriver>> calculateDriversAtStops(int minute) {
        // For each driver get the stop where he is now.
        final Map<Integer, Set<BusDriver>> stops = new HashMap<>();
        for (final BusDriver driver : drivers) {
            final int currentStopOfDriver = driver.getStop(minute);
            final Set<BusDriver> driversAtStop = stops.getOrDefault(currentStopOfDriver, new HashSet<>());
            driversAtStop.add(driver);
            stops.put(currentStopOfDriver, driversAtStop);
        }
        return stops;
    }

    private void shareGossips(final Map<Integer, Set<BusDriver>> stops) {
        // Loop over all stops and share gossips.
        for (final Integer stop : stops.keySet()) {
            final Set<BusDriver> driversAtStop = stops.get(stop);
            if (driversAtStop.size() > 1) {
                for (BusDriver driver : driversAtStop) {
                    for (BusDriver otherDriver : driversAtStop) {
                        otherDriver.nowKnowsGossip(driver.getKnownGossips());
                    }
                }
            }
        }
    }
}

There’s still a few comments in there I would remove, but on the whole that’s a good solution.

The other big question is the design of the bus/driver object. All the solutions converged on the fact the object would have the state of which gossips the driver knew (and that the gossip would be an “ID” assigned to each driver at construction).

The main variation was regarding the location of the bus. For the non-bonus question it was very feasible to have this knowledge be stateless and calculated on the fly.

public int getStop(int minute) {
    int effectiveStop = (minute - 1) % route.size();
    return route.get(effectiveStop);
}

// It was also possible to keep the state on each driver, as so.

public int travelAStop() {
    if (minutesTravelled >= totalMinutesToTravel) {
        throw new CannotTravelException("Driver cannot travel. Total time to travel will be exceeded.");
    }
    minutesTravelled++;
    currentStop = route[routeIndex++ % route.length];
    return currentStop;
}

Generally it’s a good idea to go for immutable objects, which is very much possible for the original question in this case, as the location of the driver can be calculated on the fly for each minute, and is probably the preferred solution in this case.