8
\$\begingroup\$

This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink.

Note: I do understand merits of unit testing in separate files. But deliberately added it to main method for personal convenience, so I request that you not consider that in your feedback.

I'm looking for request code review, optimizations and best practices.

final class Station {

    private final int stationTime;
    private final int transtionToTime; // time to transition`to` this station
    private final int transitionFromTime; // time to transitition `from` this station.

    public Station(int stationTime, int transitionTime, int transitionFromTime) {
        this.stationTime = stationTime;
        this.transtionToTime = transitionTime;
        this.transitionFromTime = transitionFromTime;
    }

    public int getStationTime() {
        return stationTime;
    }

    public int getTransitionToTime() {
        return transtionToTime;
    }

    public int getTransitionFromTime() {
        return transitionFromTime;
    }
}

public final class AssemblyLine {

    private AssemblyLine() {}

    /**
     * Given an assembly line, outputs the shortest time needed to go through it.
     * The input data structures are not expected to be changed by client.
     * 
     * @param line1     the assembly line 1
     * @param line2     the assumbly line 2
     * @return          the minumum time needed to process the item.
     */
public static int assemblyLineShortestTime(List<Station> line1, List<Station> line2) {
    int prevLine1Min = line1.get(0).getStationTime() + line1.get(0).getTransitionToTime(); 
    int prevLine2Min = line2.get(0).getStationTime() + line2.get(0).getTransitionToTime(); 
    for (int i = 1; i < line1.size(); i++) {
        int currentLine1Min = line1.get(i).getStationTime() + Math.min(prevLine1Min, prevLine2Min + line1.get(i).getTransitionToTime());
        int currentLine2Min = line2.get(i).getStationTime() + Math.min(prevLine1Min + line2.get(i).getTransitionToTime(), prevLine2Min);

        prevLine1Min = currentLine1Min;
        prevLine2Min = currentLine2Min;
    }
    return Math.min(prevLine1Min + line1.get(line1.size() - 1).getTransitionFromTime(), prevLine2Min + line2.get(line2.size() - 1).getTransitionFromTime()); 
}

    public static void main(String[] args) { 

        List<Station> line1 = new ArrayList<Station>(); 
        line1.add(new Station(4, 10, 7));
        line1.add(new Station(5,  9, 4));
        line1.add(new Station(3,  2, 5));
        line1.add(new Station(2,  8, 18));

        List<Station> line2 = new ArrayList<Station>(); 
        line2.add(new Station( 2, 12, 9));
        line2.add(new Station(10,  7, 2));
        line2.add(new Station( 1,  4, 8));
        line2.add(new Station( 4,  5, 7)); 

        assertEquals(35, assemblyLineShortestTime(line1, line2));
    }
}
\$\endgroup\$
  • \$\begingroup\$ I think you misunderstood the problem statement given that you assign two transition times for each station. There's only one transition time per station per line: the time it would take to switch lines. Also, each line has an entry and exit time cost. Perhaps you tried to shoehorn them into the transition times? \$\endgroup\$ – David Harkness Apr 13 '14 at 20:46
  • \$\begingroup\$ yes i did shoehorn, but resulting data structure looked reasonable. if its a concern, then I would say its a valuable feedback. \$\endgroup\$ – JavaDeveloper Apr 13 '14 at 20:49
  • \$\begingroup\$ Rereading your implementation, it does seem you captured the requirements correctly. \$\endgroup\$ – David Harkness Apr 13 '14 at 20:51
  • 1
    \$\begingroup\$ " for personal convenience" It took me less time than writing this comment to (add new package + add new test suite + copy&paste + fix import errors). If you don't have multiple tests how would you know what repeated across tests, therefore what to extract, therefore mitigate design flaws... \$\endgroup\$ – abuzittin gillifirca Apr 14 '14 at 11:41
1
\$\begingroup\$

The code implementing the core algorithm is very cumbersome. This is partly due to shoehorning the line entry/exit times into the first/last stations as evidenced by some internal stations in your tests having unusable exit times. But the code duplication doesn't help either.

Note: The diagram shows the transition time belonging to the station being transitioned from. Your code uses the transition time from the station on the other line. I'm going with the diagram as it seems cleaner to me.

Store the current stations into local variables to avoid having to read .get(0) and .get(i) many times. Also, when you name variables identically except for 1 and 2 (unavoidable in this method), don't hide the numbers in the middle of the names. Finally, since all these time-based local variables are for line X and track minimum times, drop Line and Min from their names.

public static int assemblyLineShortestTime(List<Station> line1, List<Station> line2) {
    return assemblyLineShortestTime(line1.iterator(), line2.iterator());
}

private static int assemblyLineShortestTime(Iterator<Station> line1, Iterator<Station> line2) {
    Station station1 = line1.next();
    Station station2 = line2.next();
    int prev1 = station1.getStationTime() + station1.getTransitionToTime(); 
    int prev2 = station2.getStationTime() + station2.getTransitionToTime(); 
    while (line1.hasNext()) {
        station1 = line1.next();
        station2 = line2.next();
        int curr1 = station1.getStationTime() + Math.min(prev1, prev2 + station2.getTransitionToTime());
        int curr2 = station2.getStationTime() + Math.min(prev2, prev1 + station1.getTransitionToTime());

        prev1 = curr1;
        prev2 = curr2;
    }
    return Math.min(prev1 + station1.getTransitionFromTime(), prev2 + station2.getTransitionFromTime()); 
}

While the code duplication seems much worse with those temporary variables, the logic is more apparent to me. The real problem is that there's no logic inside Station. If you add the line number to Station and added some helper methods, you could clean up that code a bit.

private static int assemblyLineShortestTime(Iterator<Station> line1, Iterator<Station> line2) {
    Station station1 = line1.next();
    Station station2 = line2.next();
    int prev1 = station1.start();
    int prev2 = station2.start();
    while (line1.hasNext()) {
        station1 = line1.next();
        station2 = line2.next();
        int curr1 = station1.proceed(prev1, prev2);
        int curr2 = station2.proceed(prev2, prev1);
        prev1 = curr1;
        prev2 = curr2;
    }
    return Math.min(prev1 + station1.exit(), prev2 + station2.exit()); 
}

class Station {
    public int start() {
        return stationTime + transitionToTime;
    }

    public int proceed(thisLineTime, otherLineTime) {
        // The transitionToTime here is not the correct one,
        // but this demonstrates the technique
        return stationTime + Math.min(thisLineTime, otherLineTime + transitionToTime);
    }

    public int exit() {
        return transitionFromTime;
    }
}

These small refactorings improve the readability only a little, but they don't alter it significantly. The real gains will require expanding the model and moving away from a single, static method.

Starting Over

If you're going to model the stations with classes to solve this, go all in and model the lines and entry/exit times properly to avoid confusion.

class Station
    int runTime - time to process this station
    int switchTime - time to switch lines

class Line
    List<Station> stations
    int entryTime - time to enter this line
    int exitTime - time to exit this line

Next model the location along the lines.

class Location
    Line line - which line are we on
    Station station - which station did we just go through
    int totalTime - elapsed time to reach this location

This design will allow moving the bulk of the algorithm into the model. You may not even need to model the lines themselves if you store the next stations in each station.

class Station
    int runTime - time to process this station
    Station next - next station on the same line
    Station otherNext - next station on the other line
    int switchTime - time to switch lines
\$\endgroup\$
  • 1
    \$\begingroup\$ @Vogel612 "A station is denoted by S[i,j] where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station." [emphasis mine] And items can only go one direction in the flow, so there's no need for prev. \$\endgroup\$ – David Harkness Apr 14 '14 at 22:25

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.