wordPack-v1-with-memo.java

class TrieNode {
    char c;
    boolean isWord;
    int count;
    String word;
    Map<Character, TrieNode> children;

    public TrieNode(char c) {
        this.c = c;
        this.isWord = false;
        this.children = new HashMap<>();
        this.count = 0;
        this.word = "";
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        this.root = new TrieNode(' ');
    }

    public void buildTrie(List<String> words) {
        for (String word : words) {
            this.insert(word);
        }
    }
    public void insert(String word) {
        TrieNode currNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!currNode.children.containsKey(c)) {
                currNode.children.put(c, new TrieNode(c));
            }
            currNode = currNode.children.get(c);
        }
        currNode.isWord = true;
        currNode.word = word;
        currNode.count += 1;
    }
}

int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};

public List<String> wordPackWithMemo(char[][] grid, List<String> words) {
    List<String> results = new ArrayList<>();
    Trie trieTree = new Trie();
    trieTree.buildTrie(words);
    // with memorization
    Map<String, List<String>> memo = new HashMap<>();
    List<String> result = searchStateWithMemo(grid, trieTree.root, trieTree.root, memo);
    Collections.sort(result);
    return result;
}

public Pair<String, Integer> hashGrid(char[][] grid) {
    int r = grid.length, c = grid[0].length;
    StringBuilder[] digits = new StringBuilder[5];
    // 0 start, 1 fromUp, 2 fromDown, 3 fromLeft, 4 fromRight
    for (int i = 0; i < 5; i++) {
        digits[i] = new StringBuilder();
    }
    int remain = r * c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (Character.isDigit(grid[i][j])){
                digits[grid[i][j] - '0'].append(i * c + j).append(',');
                remain --;
            }
        }
    }
    StringBuilder hash = new StringBuilder();
    for (int i = 0; i < 5; i++) {
        hash.append(digits[i]).append(';');
    }
    return new Pair<>(hash.toString(), remain);
}

public int checkCharCount(List<String> result) {
    int res = 0;
    for (String word : result) {
        res += word.length();
    }
    return res;
}

public List<String> searchStateWithMemo(char[][] grid, TrieNode root, TrieNode node,
                                        Map<String, List<String>> memo) {
    Pair<String, Integer> state = hashGrid(grid);
    String stateHash = state.getKey();
    Integer remain = state.getValue();
    if (memo.containsKey(stateHash)) {
        List<String> subList = memo.get(stateHash);
        return subList;
    }
    int r = grid.length;
    int c = grid[0].length;
    List<String>[] stateResult = new List[1];
    stateResult[0] = new ArrayList();
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (!Character.isDigit(grid[i][j])) {
                searchWordWithMemo(grid, root, node, grid[i][j], i, j, '0', stateResult, memo);
                if (stateResult[0].size() >= remain || checkCharCount(stateResult[0]) >= remain) { // early return
                    break;
                }
            }
        }
    }
    memo.put(stateHash, new ArrayList<>(stateResult[0]));
    return memo.get(stateHash);
}

public void searchWordWithMemo(char[][] grid, TrieNode root, TrieNode node, char ch, int x, int y, char move,
                               List[] stateResult, Map<String, List<String>> memo) {
    if (!node.children.containsKey(ch)) {
        return;
    }
    int r = grid.length;
    int c = grid[0].length;
    grid[x][y] = move; // take this tile
    TrieNode curr = node.children.get(ch);
    if (curr.isWord && curr.count > 0) {
        // found a remaining word, found a successor state
        curr.count -= 1;

        List<String> subStateRes = searchStateWithMemo(grid, root, root, memo);
        if (1 + subStateRes.size() > stateResult[0].size()) {
            stateResult[0] = new ArrayList();
            stateResult[0].add(curr.word);
            stateResult[0].addAll(subStateRes);
        }
        // backtrack
        curr.count += 1;
    }

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= r || ny < 0 || ny >= c || Character.isDigit(grid[nx][ny])) {
            continue;
        }
        searchWordWithMemo(grid, root, curr, grid[nx][ny], nx, ny, (char)('0' + k + 1), stateResult, memo);
    }
    grid[x][y] = ch;
}

wordPack-v2-without-memo.java

/**
Without Memo
This version takes forever to run WordPack_3.in
O(n) (n^2) !
**/

class TrieNode {
    char c;
    boolean isWord;
    int count;
    String word;
    Map<Character, TrieNode> children;

    public TrieNode(char c) {
        this.c = c;
        this.isWord = false;
        this.children = new HashMap<>();
        this.count = 0;
        this.word = "";
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        this.root = new TrieNode(' ');
    }

    public void buildTrie(List<String> words) {
        for (String word : words) {
            this.insert(word);
        }
    }
    public void insert(String word) {
        TrieNode currNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!currNode.children.containsKey(c)) {
                currNode.children.put(c, new TrieNode(c));
            }
            currNode = currNode.children.get(c);
        }
        currNode.isWord = true;
        currNode.word = word;
        currNode.count += 1;
    }

}

int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};

public List<String> wordPack(char[][] grid, List<String> words) {
      List<String> results = new ArrayList<>();
      Trie trieTree = new Trie();
      trieTree.buildTrie(words);
      // without memorization
      List<String> wordList = new ArrayList<>();
      List<String>[] result = new List[1];
      result[0] = new ArrayList<>();
      Map<String, List<String>> memo = new HashMap<>();
      searchState(grid, trieTree.root, trieTree.root, result, wordList);
      Collections.sort(result[0]);
      return result[0];
}

public void searchState(char[][] grid, TrieNode root, TrieNode node,
                            List[] result, List<String> wordList) {
    int r = grid.length;
    int c = grid[0].length;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (grid[i][j] != '#') {
                searchWord(grid, root, node, grid[i][j], i, j, result, wordList);
            }
        }
    }
}


public void searchWord(char[][] grid, TrieNode root, TrieNode node, char ch, int x, int y,
                           List[] result, List<String> wordList) {
    if (!node.children.containsKey(ch)) {
        return;
    }
    int r = grid.length;
    int c = grid[0].length;
    grid[x][y] = '#'; // take this tile
    TrieNode curr = node.children.get(ch);
    if (curr.isWord && curr.count > 0) {
        // found a remaining word, found a successor state
        curr.count -= 1;
        wordList.add(curr.word);
        if (wordList.size() > result[0].size()) {
            result[0] = new ArrayList<>(wordList);
        }
        searchState(grid, root, root, result, wordList);
        curr.count += 1;
        wordList.remove(wordList.size() - 1);
    }

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= r || ny < 0 || ny >= c || grid[nx][ny] == '#') {
            continue;
        }
        searchWord(grid, root, curr, grid[nx][ny], nx, ny, result, wordList);
    }
    grid[x][y] = ch;
}

WordPack.java

import javafx.util.Pair;
import org.junit.Assert;
import org.junit.Test;

import java.io.*;
import java.util.*;

public class WordPack {

    class InputValues {
        int n;
        int m;
        char[][] grid;
        List<String> words;
        public InputValues(int n, int m, char[][] grid, List<String> words) {
            this.n = n;
            this.m = m;
            this.grid = grid;
            this.words = words;
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("n: " + n + "\nm: " + m + "\n");
            res.append(Arrays.deepToString(grid)).append("\n");
            words.forEach(word -> res.append(word).append("\n"));
            return res.toString();
        }
    }

    @Test
    public void test() {
        File[] files = readFolder("src/input/WordPack");
        WordPack.InputValues test = readFile(files[3]);
        List<String> res1 = wordPackWithMemo(test.grid, test.words);
        System.out.println(res1);
    }

    @Test
    public void testALL() {
        File[] files = readFolder("src/input/WordPack");
        for (int i = 0; i < files.length; i++) {
            if (i == 3) continue;
            System.out.println(files[i].getName());
            WordPack.InputValues test = readFile(files[i]);
            List<String> res1 = wordPack(test.grid, test.words);
            List<String> res2 = wordPack(test.grid, test.words);
            Assert.assertEquals(res1, res2);
        }
    }

  
    public void generateOutput() throws IOException {
        File[] files = readFolder("src/input/WordPack");
        for (int i = 0; i < files.length; i++) {
            File file = files[i];
            String outfileName = "src/output/WordPack/" + file.getName().replace(".in", ".out");
            File outfile = new File(outfileName);
            outfile.getParentFile().mkdirs();
            outfile.createNewFile();
            PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName));
            WordPack.InputValues test = readFile(file);
            List<String> result = wordPackWithMemo(test.grid, test.words);
            for (String word : result) {
                printWriter.print(word);
                printWriter.print(" ");
            }
            printWriter.close();
        }
    }

    class TrieNode {
        char c;
        boolean isWord;
        int count;
        String word;
        Map<Character, TrieNode> children;

        public TrieNode(char c) {
            this.c = c;
            this.isWord = false;
            this.children = new HashMap<>();
            this.count = 0;
            this.word = "";
        }
    }

    class Trie {
        TrieNode root;
        public Trie() {
            this.root = new TrieNode(' ');
        }

        public void buildTrie(List<String> words) {
            for (String word : words) {
                this.insert(word);
            }
        }
        public void insert(String word) {
            TrieNode currNode = this.root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!currNode.children.containsKey(c)) {
                    currNode.children.put(c, new TrieNode(c));
                }
                currNode = currNode.children.get(c);
            }
            currNode.isWord = true;
            currNode.word = word;
            currNode.count += 1;
        }

    }


    public List<String> wordPack(char[][] grid, List<String> words) {
        List<String> results = new ArrayList<>();
        Trie trieTree = new Trie();
        trieTree.buildTrie(words);
        // without memorization
        List<String> wordList = new ArrayList<>();
        List<String>[] result = new List[1];
        result[0] = new ArrayList<>();
        Map<String, List<String>> memo = new HashMap<>();
        searchState(grid, trieTree.root, trieTree.root, result, wordList);
        Collections.sort(result[0]);
        return result[0];
    }

    public List<String> wordPackWithMemo(char[][] grid, List<String> words) {
        List<String> results = new ArrayList<>();
        Trie trieTree = new Trie();
        trieTree.buildTrie(words);
        // with memorization
        Map<String, List<String>> memo = new HashMap<>();
        List<String> result = searchStateWithMemo(grid, trieTree.root, trieTree.root, memo);
        Collections.sort(result);
        return result;
    }

    // can add a memo in search state to improve efficiency
    // a state include status of the grid, word have been selected
    public void searchState(char[][] grid, TrieNode root, TrieNode node,
                            List[] result, List<String> wordList) {
        int r = grid.length;
        int c = grid[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] != '#') {
                    searchWord(grid, root, node, grid[i][j], i, j, result, wordList);
                }
            }
        }
    }

    public Pair<String, Integer> hashGrid(char[][] grid) {
        int r = grid.length, c = grid[0].length;
        StringBuilder[] digits = new StringBuilder[5];
        // 0 start, 1 fromUp, 2 fromDown, 3 fromLeft, 4 fromRight
        for (int i = 0; i < 5; i++) {
            digits[i] = new StringBuilder();
        }
        int remain = r * c;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (Character.isDigit(grid[i][j])){
                    digits[grid[i][j] - '0'].append(i * c + j).append(',');
                    remain --;
                }
            }
        }
        StringBuilder hash = new StringBuilder();
        for (int i = 0; i < 5; i++) {
            hash.append(digits[i]).append(';');
        }
        return new Pair<>(hash.toString(), remain);
    }

    public int checkCharCount(List<String> result) {
        int res = 0;
        for (String word : result) {
            res += word.length();
        }
        return res;
    }

    public List<String> searchStateWithMemo(char[][] grid, TrieNode root, TrieNode node,
                                            Map<String, List<String>> memo) {
        Pair<String, Integer> state = hashGrid(grid);
        String stateHash = state.getKey();
        Integer remain = state.getValue();
        if (memo.containsKey(stateHash)) {
            List<String> subList = memo.get(stateHash);
            return subList;
        }
        int r = grid.length;
        int c = grid[0].length;
        List<String>[] stateResult = new List[1];
        stateResult[0] = new ArrayList();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (!Character.isDigit(grid[i][j])) {
                    searchWordWithMemo(grid, root, node, grid[i][j], i, j, '0', stateResult, memo);
                    if (stateResult[0].size() >= remain || checkCharCount(stateResult[0]) >= remain) { // early return
                        break;
                    }
                }
            }
        }
        memo.put(stateHash, new ArrayList<>(stateResult[0]));
        return memo.get(stateHash);
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    public void searchWordWithMemo(char[][] grid, TrieNode root, TrieNode node, char ch, int x, int y, char move,
                                   List[] stateResult, Map<String, List<String>> memo) {
        if (!node.children.containsKey(ch)) {
            return;
        }
        int r = grid.length;
        int c = grid[0].length;
        grid[x][y] = move; // take this tile
        TrieNode curr = node.children.get(ch);
        if (curr.isWord && curr.count > 0) {
            // found a remaining word, found a successor state
            curr.count -= 1;

            List<String> subStateRes = searchStateWithMemo(grid, root, root, memo);
            if (1 + subStateRes.size() > stateResult[0].size()) {
                stateResult[0] = new ArrayList();
                stateResult[0].add(curr.word);
                stateResult[0].addAll(subStateRes);
            }
            // backtrack
            curr.count += 1;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c || Character.isDigit(grid[nx][ny])) {
                continue;
            }
            searchWordWithMemo(grid, root, curr, grid[nx][ny], nx, ny, (char)('0' + k + 1), stateResult, memo);
        }
        grid[x][y] = ch;
    }

    public void searchWord(char[][] grid, TrieNode root, TrieNode node, char ch, int x, int y,
                           List[] result, List<String> wordList) {
        if (!node.children.containsKey(ch)) {
            return;
        }
        int r = grid.length;
        int c = grid[0].length;
        grid[x][y] = '#'; // take this tile
        TrieNode curr = node.children.get(ch);
        if (curr.isWord && curr.count > 0) {
            // found a remaining word, found a successor state
            curr.count -= 1;
            wordList.add(curr.word);
            if (wordList.size() > result[0].size()) {
                result[0] = new ArrayList<>(wordList);
            }
            searchState(grid, root, root, result, wordList);
            curr.count += 1;
            wordList.remove(wordList.size() - 1);
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c || grid[nx][ny] == '#') {
                continue;
            }
            searchWord(grid, root, curr, grid[nx][ny], nx, ny, result, wordList);
        }
        grid[x][y] = ch;
    }



    private int getInt(String name) {
        return Integer.parseInt(name.replaceAll("\\D", ""));
    }

    private File[] readFolder(String path) {
        File folder = new File(path);
        File[] files = folder.listFiles();
        Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName()));
        return files;
    }

    private WordPack.InputValues readFile(File file) {
        try {
            // assume the input file is always valid
            Scanner sc = new Scanner(file);
            String[] nm = sc.nextLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            char[][] grid = new char[n][n];
            for (int i = 0; i < n; i++) {
                String line = sc.nextLine();
                for (int j = 0; j < n; j++) {
                    grid[i][j] = line.charAt(j);
                }
            }
            List<String> words = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                words.add(sc.nextLine());
            }
            sc.close();
            return new WordPack.InputValues(n, m, grid, words);
        } catch (FileNotFoundException e) {
            System.out.println(file.getName() + " not exist");
        }
        return null;
    }

}