Alternativ lösning 4: Elegant och lättläst pivotering

2011-02-21 — Tobias HillTobias Hill

Anders Gustafssons lösare kunde konfigureras hur den skulle köras - med eller utan pivotering respektive memoisering. Framförallt var det kvaliteter kring tydlighet och läsbarhet som fångade ögat denna gång. I synnerhet pivoteringen är elegant och enkel att förstå (metoden divideAndConquer(String))

public class JFokus2011 {

    protected static final String ORIGINAL_PROBLEM_TEXT = "VOCDIITEIOCRUDOIANTOCSLOIOCVESTAIOCVOLIOCENTSU";
    protected static final String[] ORIGINAL_PATTERNS =
            new String[]{ "TDD", "DDD", "DI", "DO", "OO", "UI", "ANT", "CV", "IOC", "LOC", "SU", "VO" };

    public static void main( final String[] args ) {
        String text = null;
        final List<String> patterns = new ArrayList<String>();
        boolean usePivot = true;
        boolean useExaminedTexts = true;

        for ( final String arg : args ) {
            if ( "-p".equals( arg ) ) {
                usePivot = false;
            } else if ( "-et".equals( arg ) ) {
                useExaminedTexts = false;
            } else if ( text == null ) {
                text = arg;
            } else {
                patterns.add( arg );
            }
        }
        if ( text == null ) {
            text = ORIGINAL_PROBLEM_TEXT;
            patterns.addAll( Arrays.asList( ORIGINAL_PATTERNS ) );
        }
        solve( text, patterns, usePivot, useExaminedTexts );
    }

    private static void solve( final String text,
                               final List<String> patterns,
                               final boolean usePivot,
                               final boolean useExaminedTexts ) {

        final ProblemSolver task = new ProblemSolver();
        task.setOriginalText( text );
        for ( final String pattern : patterns ) {
            task.addPattern( pattern );
        }
        task.setUsePivot( usePivot );
        task.setUseExaminedTexts( useExaminedTexts );
        task.printInformation();
        task.solve();
        task.printResult();
    }
}

class ProblemSolver {
    protected boolean usePivot;
    protected boolean useExaminedTexts;
    protected String originalText;
    protected List<String> patterns;
    protected Set<Character> charactersInPatterns;
    protected Map<String, String> examinedTexts;
    protected String result;
    protected long noOfTries;

    protected ProblemSolver() {
        this.patterns = new ArrayList<String>();
        this.examinedTexts = new HashMap<String, String>();
        this.charactersInPatterns = new HashSet<Character>();
    }

    protected void setOriginalText( final String originalText ) {
        this.originalText = originalText;
    }

    protected void addPattern( final String pattern ) {
        this.patterns.add( pattern );
    }

    protected void setUsePivot( final boolean usePivot ) {
        this.usePivot = usePivot;
    }

    protected void setUseExaminedTexts( final boolean useExaminedTexts ) {
        this.useExaminedTexts = useExaminedTexts;
    }

    protected void printInformation() {
        final StringBuilder sb = new StringBuilder();
        for ( String pattern : this.patterns ) {
            sb.append( pattern ).append( " " );
        }
        System.out.format( "Original text      : %s%n", this.originalText );
        System.out.format( "Patterns           : %s%n", sb );
        System.out.format( "No of patterns     : %d%n", this.patterns.size() );
        System.out.format( "Use pivot          : %b%n", this.usePivot );
        System.out.format( "Use examined texts : %b%n", this.useExaminedTexts );
    }

    protected void printResult() {
        System.out.format( "Result             : %s%n", this.result );
        System.out.format( "Examined texts     : %s%n", this.examinedTexts.size() );
        System.out.format( "No of tries        : %d%n", this.noOfTries );
        System.out.println();
    }

    public void solve() {
        if ( this.originalText == null || this.patterns.size() == 0 ) {
            throw new IllegalStateException( "Missing TEXT and/or PATTERN" );
        }
        collectCharactersUsedInPatterns();
        divideAndConquer();
    }

    private void collectCharactersUsedInPatterns() {
        for ( final String pattern : this.patterns ) {
            for ( final Character c : pattern.toCharArray() ) {
                if ( !this.charactersInPatterns.contains( c ) ) {
                    this.charactersInPatterns.add( c );
                }
            }
        }
    }

    private void divideAndConquer() {
        if ( this.usePivot ) {
            this.result = divideAndConquer( this.originalText );
        } else {
            this.result = shorten( this.originalText );
        }
    }

    private String divideAndConquer( final String text ) {
        String result = null;
        for ( int i = 0; i < text.length(); i++ ) {
            final char c = text.charAt( i );
            if ( !this.charactersInPatterns.contains( c ) ) {
                final String head = text.substring( 0, i );
                final String pivot = text.substring( i, i + 1 );
                final String tail = text.substring( i + 1 );
                result = shorten( head ) + pivot + divideAndConquer( tail );
                break;
            }
        }
        if ( result == null ) {
            result = shorten( text );
        }
        return result;
    }

    protected String shorten( final String text ) {
        String currentResult = text; // May be shortened in loop below.
        this.noOfTries++;

        if ( this.useExaminedTexts && this.examinedTexts.keySet().contains( text ) ) {
            currentResult = this.examinedTexts.get( text );
        } else {

            for ( final String pattern : this.patterns ) {
                int index = text.indexOf( pattern, 0 ); // Search for first match.
                while ( index >= 0 ) {
                    final String textBefore = text.substring( 0, index );
                    final String textAfter = text.substring( index + pattern.length() );
                    final String subResult = shorten( textBefore + textAfter );
                    if ( subResult.length() < currentResult.length() ) {
                        currentResult = subResult;
                    }
                    index = text.indexOf( pattern, index + 1 ); // See if there are more matches.
                }
            }
            this.examinedTexts.put( text, currentResult );
        }
        return currentResult;
    }
}