DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Java Code Review Solution
  • Leverage Lambdas for Cleaner Code
  • Getting Started With JMS-ActiveMQ: Explained in a Simple Way
  • Binary Code Verification in Open Source World

Trending

  • Breaking Bottlenecks: Applying the Theory of Constraints to Software Development
  • Unlocking AI Coding Assistants Part 3: Generating Diagrams, Open API Specs, And Test Data
  • Testing SingleStore's MCP Server
  • Integrating Security as Code: A Necessity for DevSecOps
  1. DZone
  2. Coding
  3. Java
  4. Java Code Challenge: Bus Gossip Solution

Java Code Challenge: Bus Gossip Solution

Here's the solution to the last Java Code Challenge: Bus Gossip edition! Well done to everyone who submitted a solution.

By 
Sam Atkinson user avatar
Sam Atkinson
·
Jun. 23, 16 · News
Likes (10)
Comment
Save
Tweet
Share
12.4K Views

Join the DZone community and get the full member experience.

Join For Free

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.

code style Java (programming language)

Opinions expressed by DZone contributors are their own.

Related

  • Java Code Review Solution
  • Leverage Lambdas for Cleaner Code
  • Getting Started With JMS-ActiveMQ: Explained in a Simple Way
  • Binary Code Verification in Open Source World

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!