package fragment.submissions;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Reassembles a given set of text fragments into their original sequence.
 *
 * Author: Rushit Shah
 */
public class RushitShah {
    
    private static final String FRAGMENT_DELIMITER = ";";
    
    public static void main(String[] args) throws IOException {
        try (BufferedReader in = new BufferedReader(new FileReader(args[0]))) {
            in.lines()
                    .map(RushitShah::reassemble)
                    .forEach(System.out::println);
        }
    }
    
    private static String reassemble(final String input) {
        if (input == null) {
            throw new IllegalArgumentException("Cannot process null input, please ensure input is not null");
        }
        // Split the input using the delimiter to obtain fragments
        final List<String> fragments = new ArrayList<>(Arrays.asList(input.split(FRAGMENT_DELIMITER)));
        if (fragments.isEmpty()) {
            throw new IllegalArgumentException("Could not get fragments from input provided. Most likely ; has not been used as a delimiter or the input is not fragmented");
        }
        if (fragments.size() == 1) {
            return fragments.get(0);
        }
        
        int fragmentVisibilityTracker = 0;        // Index tracker used to keep track of which fragments have been looked at in the loop
        boolean hasBeenMerged = false;            // Flag to check if any text has been merged at any point in the iterations
        String text = fragments.get(fragmentVisibilityTracker);
        
        // Loop over all fragments until all have been merged or only "junk" fragments remain
        while (!fragments.isEmpty()) {
            MatchState biggestMatchLength = null;
            int indexToRemove = -1;
            // Check all fragments against the first one (or merged text) for the largest match
            for (int i = 0; i < fragments.size(); i++) {
                final MatchState matchState = computeMatchState(text, fragments.get(i));
                if (matchState.canMerge()) {
                    // If we've found a match, ensure largest as well as remove record index from collection to prevent it being used again
                    if (biggestMatchLength == null) {
                        biggestMatchLength = matchState;
                        indexToRemove = i;
                    } else if (biggestMatchLength.getMatchLength() < matchState.getMatchLength()) {
                        biggestMatchLength = matchState;
                        indexToRemove = i;
                    }
                }
            }
            if (biggestMatchLength != null && indexToRemove > -1 && biggestMatchLength.getMatchLength() > 1) {
                // Remove matching fragments
                fragments.remove(indexToRemove);
                // Merge into main sentence
                text = biggestMatchLength.merge();
                hasBeenMerged = true;
            } else if (!hasBeenMerged && biggestMatchLength != null && biggestMatchLength.cannotMerge()) {
                // We need to track if we've ever merged something in the event that the fragments have no matches
                fragmentVisibilityTracker++;
                text = fragments.get(fragmentVisibilityTracker);
            } else {
                // If there are no more matches, exit the loop - the only remaining fragments can be considered "junk"
                break;
            }
        }
        return text;
    }
    
    private static MatchState computeMatchState(final String leftFragment, final String rightFragment) {
        if (leftFragment == null || rightFragment == null) {
            // Validation to ensure that we don't operate on null - spec said we were sure to receive at least 2 characters in fragments
            throw new IllegalArgumentException("Cannot accept null strings");
        }
        if (leftFragment.equals(rightFragment)) {
            // Do nothing when fragments are equal
            return new MatchState(leftFragment, rightFragment, leftFragment.length(), MergePosition.FULLY_CONTAINED, -1);
        }
        
        // use specialized version of sliding window - but to edges only
        int maximumMatchLengthFound = 0;
        int mergeAtIndex = -1;
        MergePosition mp = MergePosition.CANT_MERGE;
        
        int rightLength = rightFragment.length();
        // Compare first by increasing the window left to right
        for (int expandingWindow = 1; expandingWindow <= rightLength; expandingWindow++) {
            final String expandingWindowContent = rightFragment.substring(0, expandingWindow);
            final boolean leftContainsExpandingWindowContent = leftFragment.contains(expandingWindowContent);
            // Check there is a matching string & that the match is bigger than any previously found match (i.e. maximal match)
            if (leftContainsExpandingWindowContent && (maximumMatchLengthFound < expandingWindow)) {
                if (leftFragment.endsWith(expandingWindowContent)) {
                    maximumMatchLengthFound = expandingWindow;
                    mp = MergePosition.MERGE_AT_END;
                    mergeAtIndex = rightLength - expandingWindow;
                } else if (leftFragment.startsWith(expandingWindowContent)) {
                    maximumMatchLengthFound = expandingWindow;
                    mp = MergePosition.CANT_MERGE;
                    mergeAtIndex = -1;
                } else if (!(mp == MergePosition.MERGE_AT_BEGINNING || mp == MergePosition.MERGE_AT_END)) {
                    maximumMatchLengthFound = expandingWindow;
                    mp = MergePosition.FULLY_CONTAINED;
                    mergeAtIndex = -1;
                }
            }
            
            // When at maximum window length, compare by reducing the window left to right
            if (expandingWindow == rightLength) {
                for (int reducingWindow = 1; reducingWindow < rightLength; reducingWindow++) {
                    // No need to compare from 0, that has been done already
                    final String reducingWindowContent = rightFragment.substring(reducingWindow, rightLength);
                    final boolean leftContainsReducingWindowContent = leftFragment.contains(reducingWindowContent);
                    if (leftContainsReducingWindowContent && (maximumMatchLengthFound < (rightLength - reducingWindow))) {
                        maximumMatchLengthFound = (rightLength - reducingWindow);
                        if (leftFragment.startsWith(reducingWindowContent)) {
                            maximumMatchLengthFound = (rightLength - reducingWindow);
                            mp = MergePosition.MERGE_AT_BEGINNING;
                            mergeAtIndex = rightLength - reducingWindow;
                        } else if (leftFragment.endsWith(reducingWindowContent)) {
                            maximumMatchLengthFound = (rightLength - reducingWindow);
                            mp = MergePosition.CANT_MERGE;
                            mergeAtIndex = -1;
                        } else if (!(mp == MergePosition.MERGE_AT_BEGINNING || mp == MergePosition.MERGE_AT_END)) {
                            maximumMatchLengthFound = (rightLength - reducingWindow);
                            mp = MergePosition.FULLY_CONTAINED;
                            mergeAtIndex = -1;
                        }
                    }
                }
            }
        }
        return new MatchState(leftFragment, rightFragment, maximumMatchLengthFound, mp, mergeAtIndex);
    }
    
    private enum MergePosition {
        /**
         * Describes that merging should prefix to the input.
         */
        MERGE_AT_BEGINNING,
        
        /**
         * Describes that merging should post-fixed to the input.
         */
        MERGE_AT_END,
        
        /**
         * Describes that the input already contains the matches
         */
        FULLY_CONTAINED,
        
        /**
         * Describes input that cannot be merged either because of no matches or center-only matching
         */
        CANT_MERGE
    }
    
    /*
     * Tracks the merging positions and length of the two different inputs.
     */
    private static class MatchState {
        
        private final String leftFragment;
        
        private final String rightFragment;
        
        private final int matchLength;
        
        private final MergePosition mergePosition;
        
        private final int mergeIndex;
        
        /**
         * Instantiates a new match state with enough information to merge the fragments if required.
         *
         * @param leftFragment the left fragment
         * @param rightFragment the right fragment
         * @param matchLength the maximal match length
         * @param mergePosition the merge position
         * @param mergeIndex the merge index
         */
        MatchState(final String leftFragment, final String rightFragment, final int matchLength, final MergePosition mergePosition, final int mergeIndex) {
            this.leftFragment = leftFragment;
            this.rightFragment = rightFragment;
            this.matchLength = matchLength;
            this.mergePosition = mergePosition;
            this.mergeIndex = mergeIndex;
        }
         
        /**
         * Gets the maximal match length for the input fragments.
         *
         * @return the match maximal length
         */
        final int getMatchLength() {
            return this.matchLength;
        }
        
        /**
         * Merges the left and right fragments and returns the result. Returns null if the fragments can't be merged.
         *
         * @return the merged fragments
         */
        String merge() {
            switch (mergePosition) {
                case MERGE_AT_BEGINNING:
                    if (mergeIndex < 0) {
                        throw new IllegalStateException("Incorrect internal state (this is a bug) - there shouldn't be an < 0 index for MERGE_AT_BEGINNING");
                    }
                    return (rightFragment.substring(0, rightFragment.length() - mergeIndex)) + leftFragment;
                case MERGE_AT_END:
                    if (mergeIndex < 0) {
                        throw new IllegalStateException("Incorrect internal state (this is a bug) - there shouldn't be an < 0 index for MERGE_AT_END");
                    }
                    return leftFragment + (rightFragment.substring(rightFragment.length() - mergeIndex, rightFragment.length()));
                case FULLY_CONTAINED:
                    return leftFragment;
                default:
                    return null;
            }
        }
           
        /*
         * Returns true if and only if the fragments can be merged. This excludes the {@link MergePosition#FULLY_CONTAINED} state.
         *
         * @return the boolean
         */
        boolean canMerge() {
            return mergePosition == MergePosition.MERGE_AT_BEGINNING || mergePosition == MergePosition.MERGE_AT_END;
        }
        
        /*
         * Returns true if and only if the fragments cannot be merged (merge state is CANT_MERGE).
         *
         * @return the boolean
         */
        boolean cannotMerge() {
            return mergePosition == MergePosition.CANT_MERGE;
        }
    }
}
