CODEWITHSUNDEEP
javaarraysrecursionmultidimensional-arraychar
FRin
FRin

Reputation: 21

Searching a 2D char array for occurrences

I'm hoping to find a bit of direction for this problem I was given. Been banging my head over it for two weeks now. Essentially, I'm to write a function, public static int FindWords(char[][] puzzle) , where given a 2D char array, I can find the amount of times a given set of strings occur. Given:

    public static class PuzzleSolver
    {
        public static string[] DICTIONARY = {"OX","CAT","TOY","AT","DOG","CATAPULT","T"};
        static bool IsWord(string testWord)
        {
            if (DICTIONARY.Contains(testWord))
                return true;
            return false;
        }
    }

A 2D Array for instance that is like this:

    public static char[][] puzzle = {{'C','A','T'},
                                     {'X','Z','T'},
                                     {'Y','O','T'}};

Would return back 8 for the following instances: (AT, AT, CAT, OX, TOY, T, T, T) because we would be searching horizontally, vertically, diagonally and in reverse for all the same directions.

My approach was to visit each char in the array and then search for all possible directions with the SearchChar function...

public static int FindWords(char[][] puzzle){   
    int arrayRow    = puzzle.length;
    int arrayCol    = puzzle[0].length;
    int found       = 0;

    for(int i = 0; i < arrayRow; i++){
        for(int j = 0; j < arrayCol; j++){
            found += SearchChar(i,j);
        }
    }
    return found;
}

Which looks like this:

public static int SearchChar(int row, int col){     
    if(row < 0 || col < 0 || row > puzzle.length || col > puzzle[0].length)//Is row or col out of bounds?
        return 0;

    if(IsWord(puzzle[row][col]))
        return 1;       
    return 0;
}

Conceptually, I feel like I need some kind of recursive function to handle this but I can't seem to wrap my head around it. I don't even know if that's the right approach. I've been playing around with StringBuilder appending but I'm still struggling with that too. I think this recursive function would need to take for instance, puzzle[0][0] (or 'C') and see if it is in the dictionary. Followed by puzzle[0][0] + puzzle[0][1] (or 'CA') and then finally puzzle[0][0] + puzzle[0][1] + puzzle[0][2] (or 'CAT'). Then the same would have to be don vertically and diagonally. I'm having trouble trying to get back into the SearchChar function with a position change to append to the original char so that I can see if it is in the DICTIONARY.

Sorry if this is a bit wordy, but I just want to give the impression that I'm actually trying to solve this. Not just some lazy programmer that's copy & pasting some problem up here for someone else to solve. Thanks in advance for any help!

Upvotes: 2

Views: 990

Answers (1)

FaNaJ
FaNaJ

Reputation: 1359

I will show you how to solve this problem step by step.

1. Generating All Possible Words from the given Puzzle

to do this we must start anywhere in the puzzle and move towards all directions (except the previous Point) to generate all possible words;

2. Choosing Suitable Data Structure for Dictionary

I think Trie is a good choice and is suitable for use in such situations.

The most important reason for choosing Trie is that during the search, we can easily test if a word exists in our dictionary or is there any word that starts with the word generated by searching through the puzzle or not. As a result, we can decide whether or not to continue the search.

This will save us a lot of time and helps to generate words correctly. otherwise, we'll be stuck in an endless loop...

3. Implementation

there are several implementations for Tire , but I wrote my own CharTrie :

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;

/**
 * @author FaNaJ
 */
public final class CharTrie {

    /**
     * Pointer to root Node
     */
    private final Node root = new Node();

    /**
     * Puts the specified word in this CharTrie and increases its frequency.
     *
     * @param word word to put in this CharTrie
     * @return the previous frequency of the specified word
     */
    public int put(String word) {
        if (word.isEmpty()) {
            return 0;
        }
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            current = current.getChildren().computeIfAbsent(word.charAt(i), ch -> new Node());
        }
        return current.getAndIncreaseFrequency();
    }

    /**
     * @param word the word whose frequency is to be returned
     * @return the current frequency of the specified word or -1 if there isn't such a word in this CharTrie
     */
    public int frequency(String word) {
        if (word.isEmpty()) {
            return 0;
        }
        Node current = root;
        for (int i = 0; i < word.length() && current != null; i++) {
            current = current.getChildren().get(word.charAt(i));
        }
        return current == null ? -1 : current.frequency;
    }

    /**
     * @param word the word whose presence in this CharTrie is to be tested
     * @return true if this CharTrie contains the specified word
     */
    public boolean contains(String word) {
        return frequency(word) > 0;
    }

    /**
     * @return a CharTrie Iterator over the Nodes in this CharTrie, starting at the root Node.
     */
    public Iterator iterator() {
        return new Iterator(root);
    }

    /**
     * Node in the CharTrie.
     * frequency-children entry
     */
    private static final class Node {

        /**
         * the number of occurrences of the character that is associated to this Node,
         * at certain position in the CharTrie
         */
        private volatile int frequency = 0;
        private static final AtomicIntegerFieldUpdater<Node> frequencyUpdater
                = AtomicIntegerFieldUpdater.newUpdater(Node.class, "frequency");

        /**
         * the children of this Node
         */
        private Map<Character, Node> children;

        public Map<Character, Node> getChildren() {
            if (children == null) {
                children = new ConcurrentHashMap<>();
            }
            return children;
        }

        /**
         * Atomically increments by one the current value of the frequency.
         *
         * @return the previous frequency
         */
        private int getAndIncreaseFrequency() {
            return frequencyUpdater.getAndIncrement(this);
        }

    }

    /**
     * Iterator over the Nodes in the CharTrie
     */
    public static final class Iterator implements Cloneable {

        /**
         * Pointer to current Node
         */
        private Node current;

        private Iterator(Node current) {
            this.current = current;
        }

        /**
         * Returns true if the current Node contains the specified character in its children,
         * then moves to the child Node.
         * Otherwise, the current Node will not change.
         *
         * @param ch the character whose presence in the current Node's children is to be tested
         * @return true if the current Node's children contains the specified character
         */
        public boolean next(char ch) {
            Node next = current.getChildren().get(ch);
            if (next == null) {
                return false;
            }
            current = next;
            return true;
        }

        /**
         * @return the current frequency of the current Node
         */
        public int frequency() {
            return current.frequency;
        }

        /**
         * @return the newly created CharTrie Iterator, starting at the current Node of this Iterator
         */
        @Override
        @SuppressWarnings("CloneDoesntCallSuperClone")
        public Iterator clone() {
            return new Iterator(current);
        }

    }

}

and the WordGenerator :

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.function.BiConsumer;

/**
 * @author FaNaJ
 */
public final class WordGenerator {

    private WordGenerator() {
    }

    public static void generate(char[][] table, CharTrie.Iterator iterator, BiConsumer<String, Integer> action) {
        final ForkJoinPool pool = ForkJoinPool.commonPool();
        final VisitorContext ctx = new VisitorContext(table, action);
        for (int y = 0; y < table.length; y++) {
            for (int x = 0; x < table[y].length; x++) {
                pool.invoke(new Visitor(new Point(x, y), null, "", iterator.clone(), ctx));
            }
        }
    }

    private static final class VisitorContext {

        private final char[][] table;
        private final BiConsumer<String, Integer> action;

        private VisitorContext(char[][] table, BiConsumer<String, Integer> action) {
            this.table = table;
            this.action = action;
        }

        private boolean validate(Point point) {
            Object c = null;
            try {
                c = table[point.getY()][point.getX()];
            } catch (ArrayIndexOutOfBoundsException ignored) {
            }
            return c != null;
        }

    }

    private static final class Visitor extends RecursiveAction {

        private final Point current;
        private final Point previous;
        private final CharTrie.Iterator iterator;
        private final VisitorContext ctx;

        private String word;

        private Visitor(Point current, Point previous, String word, CharTrie.Iterator iterator, VisitorContext ctx) {
            this.current = current;
            this.previous = previous;
            this.word = word;
            this.iterator = iterator;
            this.ctx = ctx;
        }

        @Override
        protected void compute() {
            char nextChar = ctx.table[current.getY()][current.getX()];
            if (iterator.next(nextChar)) {
                word += nextChar;
                int frequency = iterator.frequency();
                if (frequency > 0) {
                    ctx.action.accept(word, frequency);
                }
                List<Visitor> tasks = new ArrayList<>();
                for (Direction direction : Direction.values()) {
                    Point nextPoint = direction.move(current);
                    if (!nextPoint.equals(previous) && ctx.validate(nextPoint)) {
                        tasks.add(new Visitor(nextPoint, current, word, iterator.clone(), ctx));
                    }
                }
                invokeAll(tasks);
            }
        }

    }

}

Note that I've used ForkJoinPool and RecursiveAction to speed up the search.

learn more :

the rest of classes :

PuzzleSolver

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.BiConsumer;
import java.util.stream.Stream;

/**
 * @author FaNaJ
 */
public final class PuzzleSolver {

    private final CharTrie dictionary;

    public enum OrderBy {FREQUENCY_IN_DICTIONARY, FREQUENCY_IN_PUZZLE}

    public PuzzleSolver(CharTrie dictionary) {
        this.dictionary = dictionary;
    }

    public CharTrie getDictionary() {
        return dictionary;
    }

    public Stream<Word> solve(char[][] puzzle) {
        return solve(puzzle, OrderBy.FREQUENCY_IN_DICTIONARY);
    }

    public Stream<Word> solve(char[][] puzzle, OrderBy orderBy) {
        Stream<Word> stream = null;
        switch (orderBy) {
            case FREQUENCY_IN_DICTIONARY: {
                final Map<String, Integer> words = new ConcurrentHashMap<>();
                WordGenerator.generate(puzzle, dictionary.iterator(), words::put);
                stream = words.entrySet().stream()
                        .map(e -> new Word(e.getKey(), e.getValue()));
                break;
            }
            case FREQUENCY_IN_PUZZLE: {
                final Map<String, AtomicInteger> words = new ConcurrentHashMap<>();
                BiConsumer<String, Integer> action = (word, frequency) -> words.computeIfAbsent(word, s -> new AtomicInteger()).getAndIncrement();
                WordGenerator.generate(puzzle, dictionary.iterator(), action);
                stream = words.entrySet().stream()
                        .map(e -> new Word(e.getKey(), e.getValue().get()));
                break;
            }
        }
        return stream.sorted((a, b) -> b.compareTo(a));
    }

}

Point

import java.util.Objects;

/**
 * @author FaNaJ
 */
public final class Point {

    private final int x;
    private final int y;

    public Point() {
        this(0, 0);
    }

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public int hashCode() {
        return x * 31 + y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Point that = (Point) obj;
        return x == that.x && y == that.y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + ']';
    }

}

Word

/**
 * @author FaNaJ
 */
public final class Word implements Comparable<Word> {

    private final String value;
    private final int frequency;

    public Word(String value, int frequency) {
        this.value = value;
        this.frequency = frequency;
    }

    public String getValue() {
        return value;
    }

    public int getFrequency() {
        return frequency;
    }

    @Override
    public int hashCode() {
        return value.hashCode() * 31 + frequency;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Word that = (Word) o;
        return frequency == that.frequency && value.equals(that.value);
    }

    @Override
    public String toString() {
        return "{" +
                "value='" + value + '\'' +
                ", frequency=" + frequency +
                '}';
    }

    @Override
    public int compareTo(Word o) {
        return Integer.compare(frequency, o.frequency);
    }

}

Direction

/**
 * @author FaNaJ
 */
public enum Direction {

    UP(0, 1), UP_RIGHT(1, 1), UP_LEFT(-1, 1),
    RIGHT(1, 0), LEFT(-1, 0),
    DOWN(0, -1), DOWN_RIGHT(1, -1), DOWN_LEFT(-1, -1);

    private final int x, y;

    Direction(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Point move(Point point) {
        return new Point(point.getX() + x, point.getY() + y);
    }

}

4. Test it

/**
 * @author FaNaJ
 */
public class Test {

    public static String[] DICTIONARY = {"OX", "CAT", "TOY", "AT", "DOG", "CATAPULT", "T", "AZOYZACZOTACXY"};

    public static void main(String[] args) {
        CharTrie trie = new CharTrie();
        for (String word : DICTIONARY) {
            trie.put(word);
        }

        PuzzleSolver solver = new PuzzleSolver(trie);

        char[][] puzzle = {
                {'C', 'A', 'T'},
                {'X', 'Z', 'T'},
                {'Y', 'O', 'T'}
        };
        solver.solve(puzzle, PuzzleSolver.OrderBy.FREQUENCY_IN_PUZZLE).forEach(System.out::println);
    }

}

output :

{value='T', frequency=3}
{value='AT', frequency=2}
{value='CAT', frequency=2}
{value='TOY', frequency=2}
{value='OX', frequency=1}
{value='AZOYZACZOTACXY', frequency=1}

Upvotes: 2

Related Questions