코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이

_READMEME.md

알고리듬 코딩 이벤트 마지막 문제 풀이입니다.

문제

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

###실행 예

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

###사전 데이터

네 글자 단어 - word4

다섯 글자 단어 - word5

###심화 문제 - 풀지 않아도 됩니다

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.

심화문제 2: 최대한 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

풀이

이 문제는 그래프를 탐색해서 두 노드간의 경로를 찾는 문제 같습니다.

그래프 구성

먼저 파일에서 사전을 읽어서 그래프를 만들기로 했습니다.

WordGraphBuilder가 그래프를 그리는 역할을 합니다. 테스트를 쉽게 하려 사전 내용 WordGraphBuilder.WordSource 인터페이스를 구현한 개체를 통해 얻도록 했습니다. ReaderWordSource는 java.util.Reader를 통해 읽기 때문에 파일 시스템의 파일이나 클래스 경로 상의 자원에서 사전을 읽는데 사용됩니다. 테스트에서는 배열에서 읽도록 했습니다.

탐색

저는 두가지 탐색 방식을 구현했습니다. 하나는 비교적 짧은 경로라고 추정되는 경로를 단어의 유사성을 비용으로 취급해 찾아내는 방식이고 또 하나는 모든 경로를 검토해 최단 거리를 찾아내는 방식입니다.

탐색알고리즘은 PathFinder란 인터페이스를 구현해야 합니다.

최장 거리 탐색은 NP인지라 Fork&Join으로 병렬처리하는 방식으로 풀어볼 생각이지만 무식한(Brute Force) 방법이라 굳이 구현할 필요가 있나 싶네요. 다만 비용 추정 탐색을 거꾸로 해서 목적 단어와 비슷하지 않은 단어를 우선 선택하다 보면 휴리스틱하게 먼 경로를 찾을 수 있지 않을까 싶습니다.

비용 추정 탐색: CostEstimatePathFinder

이 그래프에는 비용이라고 할만한 부분이 없어서 순차적으로 탐색해야하지만, 지금 위치한 단어와 유사한(문자가 하나만 다른) 단어 중에서도 목적지 단어에 포함된 문자가 있는 단어를 선택하면 그나마 빠른 길을 찾을 수 있을 거란 약한 추정을 근거로 해서 탐색을 합니다.

최단 거리 탐색: ShortestPathFinder

모든 경로를 뒤져서 가장 짧은 경로를 찾습니다. 메모리를 절약하려고 깊이 우선 탐색 방법을 사용하되 "비용 추전 탐색"을 먼저 해 본 이후에 그 결과를 바탕으로 더 깊은 경로를 배제한 상태에서 탐색하기 때문에 그리 오래 걸리지 않습니다.

실행

비용 추정 경로는 다음과 같이 실행합니다.

$java org/fupfin/insight/evnet2b/Runner org/fupfin/insight/evnet2b/word4.dic ably zain
Run time: 0.124 secs
1:ABLY
2:ABAY
3:AWAY
4:AWNY
5:AWRY
6:ADRY
7:AERY
8:AERO
9:ZERO
10:CERO
11:MERO
12:HERO
13:HERN
14:DERN
15:DARN
16:BARN
17:BAIN
18:ZAIN

최단 거리 경로는 -s 옵션을 줘서 실행합니다.

$java org/fupfin/insight/evnet2b/Runner -s org/fupfin/insight/evnet2b/word4.dic ably zain
Run time: 2.883 secs
1:ABLY
2:ABAY
3:AWAY
4:SWAY
5:SWAN
6:SAAN
7:SAIN
8:ZAIN

AbstractPathFinder.java

package org.fupfin.insight.evnet2b;

import java.util.LinkedList;
import java.util.List;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordGraph;

public abstract class AbstractPathFinder implements PathFinder {

    protected WordGraph graph;

    public AbstractPathFinder(WordGraph graph) {
        super();
        this.graph = graph;
    }

    @Override
    public List<String> find(String start, String target) {
        start = start.toUpperCase();
        target = target.toUpperCase();
        if(!(graph.contains(start) && graph.contains(target)))
            throw new IllegalArgumentException("start('" + start + "') or target('" + target + "') word is not exist in dictionary.");
                
        LinkedList<String> path = new LinkedList<String>();
        startSearching(start.toUpperCase(), target.toUpperCase(), path);
        return path;
    }

    protected abstract void startSearching(String upperCase, String upperCase2, LinkedList<String> path);
}

CostEstimatePathFinder.java

package org.fupfin.insight.evnet2b;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.SortedSet;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordGraph;

public class CostEstimatePathFinder extends AbstractPathFinder implements PathFinder {
    
    public CostEstimatePathFinder(WordGraph graph) {
        super(graph);
    }

    @Override
    protected void startSearching(String start, String target, LinkedList<String> path) {
        search(0, start, target, path);
    }

    protected boolean search(int level, String current, String target, LinkedList<String> path) {

        if(current.equals(target)) {
            path.add(current);
            return true;
        }
        
        SortedSet<String> nearWords = graph.findNearWords(current);
        if(nearWords.size() <= 0 || path.contains(current))
            return false;

        Iterable<String> arrangedNearWords = arrangeOrderOfNearWordsBySimilarity(nearWords, target);
        
        path.add(current);

        for(String word: arrangedNearWords) {
            if(search(level + 1, word, target, path)) {
                return true;
            }
        }

        path.removeLast();
        return false;
    }

    private Iterable<String> arrangeOrderOfNearWordsBySimilarity(SortedSet<String> nearWords, String target) {
        LinkedHashSet<String> arrangedNearWords = new LinkedHashSet<String>();
        Set<String> diffWords = new HashSet<String>();
        int maxSimilarity = 0;
        for(String word: nearWords) {
            int similarity = calcSimilarity(target, word);
            if(similarity > maxSimilarity) {
                diffWords.addAll(arrangedNearWords);
                arrangedNearWords.clear();
                maxSimilarity = similarity;
            }
            
            if(similarity == maxSimilarity)
                arrangedNearWords.add(word);
            else
                diffWords.add(word);
        }
        
        arrangedNearWords.addAll(diffWords);
        return arrangedNearWords;
    }

    int calcSimilarity(String thisWord, String thatWord) {
        int similarity = 0;
        for(int idx = 0; idx < thisWord.length(); idx ++) {
            if(thisWord.charAt(idx) == thatWord.charAt(idx))
                similarity ++;
        }
        return similarity;
    }
}

PathFinder.java

package org.fupfin.insight.evnet2b;

import java.util.List;

public interface PathFinder {

    public abstract List<String> find(String start, String target);
}

ReaderWordSource.java

package org.fupfin.insight.evnet2b;

import java.io.*;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordSource;

public class ReaderWordSource implements WordSource {

    BufferedReader reader;
    int wordLength = 0;
    
    public ReaderWordSource(Reader reader) {
        this.reader = new BufferedReader(reader);
    }

    @Override
    public String takeWord(int idx) {
        
        String line;

        try {
            while((line = reader.readLine()) != null) {
                line = line.trim();
                if(line.length() > 0 && (wordLength == 0 || wordLength == line.length())) {
                    this.wordLength = line.length();
                    break;
                }
            }
        } catch (IOException e) {
            throw new RuntimeException("Fail to read line from dictionary", e);
        }
        
        return line;
    }

    public void close() throws IOException {
        reader.close();
    }
}

Runner.java

package org.fupfin.insight.evnet2b;

import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.util.List;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordGraph;

public class Runner {
    public static void main(String[] args) throws IOException {
        
        if(args.length < 3) {
            printUsage();
            return;
        }

        int argIdx = 0;
        String finderType = null;
        if(args[argIdx].startsWith("-"))
            finderType = args[argIdx++].substring(1);

        String dicFile = args[argIdx++];
        String startWord = args[argIdx++];
        String targetWord = args[argIdx++];

        Long startTime = System.currentTimeMillis();

        Reader reader = new FileReader(dicFile);
        ReaderWordSource source = new ReaderWordSource(reader);

        WordGraph graph = new WordGraphBuilder().build(source);

        source.close();
        reader.close();

        PathFinder finder;
        
        if(finderType.equals("s"))
            finder = new ShortestPathFinder(graph);
        else
            finder = new CostEstimatePathFinder(graph);
        
        List<String> path = finder.find(startWord, targetWord);
        
        System.out.println("Run time: " + (System.currentTimeMillis() - startTime) / 1000.0 + " secs");
        int idx = 0;
        for(String point: path)
            System.out.println(++ idx + ":" + point);
    }

    private static void printUsage() {
        System.out.println("java org.fupfin.insight.event2b.Runner [-s|-l] dictionary_file start_word target_word\n" +
                        "\t-s: find shortest path\n" +
                        "\tdictionary_file : path to dictionary file\n" +
                        "\tstart_word: word to start find path" + 
                        "\ttarget_word: target word");
    }
}

ShortestPathFinder.java

package org.fupfin.insight.evnet2b;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.SortedSet;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordGraph;

public class ShortestPathFinder extends AbstractPathFinder implements
        PathFinder {

    public ShortestPathFinder(WordGraph graph) {
        super(graph);
    }

    @Override
    protected void startSearching(String start, String target, LinkedList<String> path) {
        
        PathFinder finder = new CostEstimatePathFinder(graph);
        List<String> estimatedPath = finder.find(start, target);
        
        Context context = new Context();
        context.currentBestLevel = estimatedPath.size() - 1;
        context.lastBestPath = estimatedPath;
        
        search(context, 0, start, target, path);

        if(context.currentBestLevel > 0) {
            path.clear();
            path.addAll(context.lastBestPath);
        }
    }

    protected void search(Context context, int level, String current, String target, LinkedList<String> path) {

        if(!context.isBetter(level) || path.contains(current))
            return;

        path.add(current);
        
        if(current.equals(target)) {
            context.record(level, path);
        } else {
            SortedSet<String> nearWords = graph.findNearWords(current);
            if(nearWords.size() > 0) {
                for(String word: nearWords)
                    search(context, level + 1, word, target, path);
            }
        }

        path.removeLast();
    }

    static class Context {
        int currentBestLevel = -1;
        List<String> lastBestPath = null;
        
        boolean isBetter(int level) {
            return this.currentBestLevel == -1 || this.currentBestLevel > level;
        }
        
        void record(int level, List<String> path) {
            this.currentBestLevel = level;
            this.lastBestPath = Collections.unmodifiableList(new LinkedList<String>(path));
        }
    }
}

TestSupport.java

package org.fupfin.insight.evnet2b;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;

import org.fupfin.insight.evnet2b.WordGraphBuilder.WordGraph;
import org.fupfin.insight.evnet2b.WordGraphBuilder.WordSource;

public abstract class TestSupport {

    private WordGraphBuilder builder = new WordGraphBuilder();

    public TestSupport() {
        super();
    }
    
    protected WordGraphBuilder getBuilder() {
        return this.builder;
    }

    protected WordGraph buildFromFile(String fileName) throws IOException {
    
        Reader reader = new InputStreamReader(this.getClass().getResourceAsStream(fileName));
        ReaderWordSource source =  new ReaderWordSource(reader);
        
        WordGraph graph = getBuilder().build(source);
        
        source.close();
        reader.close();
    
        return graph;
    }

    static class ArrayWordSource implements WordSource {

        String[] words;
        
        ArrayWordSource(String[] words) {
            this.words = words;
        }

        @Override
        public String takeWord(int idx) {
            return idx >= 0 && idx < this.words.length ? this.words[idx] : null;
        }
    }
}

WordGraphBuilder.java

package org.fupfin.insight.evnet2b;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class WordGraphBuilder {
    
    Map<String, WordSet> wordSets = new HashMap<String, WordSet>();

    public WordGraph build(WordSource source) {
        
        WordGraphBuffer graph = new WordGraphBuffer();

        String word;
        for(int idx = 0; (word = source.takeWord(idx)) != null; idx++ )
            addWordToGraph(word.toUpperCase(), graph);
        
        return graph;
    }
    
    private void addWordToGraph(String word, WordGraphBuffer graph) {

        WordSet[] nearWords = new WordSet[word.length()];

        for(int idx = 0; idx < word.length(); idx ++) {
            WordSet words = getWordSet(getWordSetKey(word, idx));
            words.add(word);
            nearWords[idx] = words;
        }

        graph.add(new Word(word, nearWords));
    }

    private WordSet getWordSet(String key) {
        WordSet result;
        
        if(this.wordSets.containsKey(key))
            result = this.wordSets.get(key);
        else {
            result = new WordSet();
            this.wordSets.put(key, result);
        }
        
        return result;
    }

    private String getWordSetKey(String word, int idx) {
        return new StringBuilder().append(word.substring(0, idx)).append('_')
                    .append(word.substring(idx+1)).toString();
    }

    static interface WordSource {
        public String takeWord(int idx);
    }
    
    static interface WordGraph {
        public boolean contains(String word);
        public SortedSet<String> findNearWords(String word);
    }
    
    private static class WordGraphBuffer implements WordGraph{

        Map<String, Word> words = new HashMap<String, Word>(); 

        @Override
        public boolean contains(String word) {
            return this.words.containsKey(word);
        }

        @Override
        public SortedSet<String> findNearWords(String word) {
            
            SortedSet<String> result = new TreeSet<String>();

            Word wordObj = this.words.get(word);
            if(wordObj == null)
                throw new RuntimeException("Given word, '" + word + "' is not found.");

            WordSet[] set = wordObj.nearWords;
            for(int idx=0; idx < set.length; idx ++) {
                String[] nearWords = set[idx].getWords();
                for(String each: nearWords)
                    if(!each.equals(word))
                        result.add(each);
            }

            return Collections.unmodifiableSortedSet(result);
        }

        public void add(Word word) {
            words.put(word.text, word);
        }

    }
    
    private static class Word {
        String text;
        WordSet[] nearWords;
        
        public Word(String text, WordSet[] nearWords) {
            this.text = text;
            this.nearWords = nearWords;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((text == null) ? 0 : text.hashCode());
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass())
                return false;
            
            Word other = (Word) obj;
            
            if (text == null) {
                if (other.text != null)
                    return false;
            } else if (!text.equals(other.text))
                return false;

            return true;
        }
    }
    
    private static class WordSet {
        Set<String> words = new TreeSet<String>();
        
        public void add(String word) {
            this.words.add(word);
        }

        public String[] getWords() {
            String[] result = new String[this.words.size()];
            int idx = 0;
            for(String word: this.words)
                result[idx++] = word;
            return result;
        }
    }
}