How to check if a word can be spelled with sets of letters

Question

So here is what i'm trying to acomplish. Imagine you have 6 sided blocks each of which has a letter on it. i.e {f, e, j, x, s, t} and you also have a word lets say for this example the word is "food" how would you check if the blocks you were given could spell how the word. You are given at least the same amount of blocks in the word so for example the word "food" would give you at least 4 blocks.

I already made it so each block makes an object that only contains usable letters for for instance it would only contain the letters F O or D in the case of the word food

String[] split = word.split("");

        for(int i = 0; i < numberOfCubes; i++){
             letterObject.put(Integer.toString(i), new validLetters());
            for(int j = 0; j < split.length; j++){
                for(int k = 0; k < 6; k++){
                    if(cubes[i][k].equalsIgnoreCase(split[j]) && !letterObject.get(Integer.toString(i)).getLetters().contains(split[j])){
                        letterObject.get(Integer.toString(i)).addLetter(split[j]);
                        System.out.println("letter added" + split[j]);
                    }
                }
            }
        }

So the thing im having problem with is how you loop through the different objects and check if it can spell the word. The main problem that i have is, lets say you have 4 cubes and you are trying to spell food and you have these sets {f,o,d} {f, o} {o} and {f} it is possible to spell it but if you use just a forloop you it will say it cant because it will see "f" in the first set then "o" then "o" then it wont find d in the 4th set. What is the best way to loop through/brute force all the different ways to do it.

EDIT: THis would be an exampe of cubes that would try and spell out the word FOOD

    static String[][] cubes = {
            {"f", "b", "d", "x", "o", "k"},
            {"e", "b", "o", "d", "q", "o"},
            {"f", "l", "c", "o", "e", "f"},
            {"a", "t", "c", "f", "e", "n"}
    };

the triple forloop shown above throws out all of the non valid letters ie B X K ect and also removes duplicates ie if a cube has 2 O's like set 2. Then it puts all of those into its own object that is put into a hashmap. AFter this it has to use this in order to check if the given cubes are able to spell the word. Set 1 ({"f", "b", "d", "x", "o", "k"}) has F and O after its manipulated so it can either be placed at the first slot of the word filling the F spot in the word food or it can be place in either the 2nd or 3rd slot ocupying the letter o but it cant be used to spell "foo" because it can only be used once per slot

Answer 1

I did what most might consider a brute force approach. Essentially I created every possible word in sequence by maintaining an independent index for each block. I then compared the created word to the desired word. I also print out the positions used in constructing each success. Some of the extra overhead is that I permit blocks with different numbers of faces. And finally, there may be bugs.

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;

    public class Blocks {

       public static void main(String[] args) {
          // input parameters
          int nBlocks = 5;
          String wordToFind = "nifty";

          // block sizes may have different number of sides
          // This permits optimization by removing irrelevant letters
          // (which I didn't do).
           String[] blockStrings = { "ffi", "rnnf", "aeif", "drst","vyxksksksksky"
           };
          // Split the blocks into a list of letter arrays
          List<String[]> blocks =
                Arrays.stream(blockStrings).map(s -> s.split("")).collect(
                      Collectors.toList());

          // turn "foobar" into abfoor"
          String[] word = wordToFind.split("");
          String sortedWord =
                Arrays.stream(word).sorted().collect(Collectors.joining());

          int count = 0;
          int[] k = new int[nBlocks];
          String[] w = new String[nBlocks];

          // calculate maximum number of iterations. The product
          // of all the block's faces for n blocks.
          int end = blocks.stream().mapToInt(a -> a.length).reduce(1,
                (a, b) -> a * b);

          for (int ii = 0; ii < end; ii++) {

             List<Integer> usedBlockPositions = new ArrayList<>();
             for (int i = 0; i < nBlocks; i++) {
                w[i] = blocks.get(i)[k[i]];
                usedBlockPositions.add(k[i]);
             }

             // compare sorted word to sorted "found" word to see if there is
             // a match.
             if (sortedWord.equals(
                   Arrays.stream(w).sorted().collect(Collectors.joining()))) {
                count++;
                System.out.println(Arrays.toString(w) + " " + usedBlockPositions);
             }

             // Bump the indices to the blocks for next try. This is used to
             // index into each block face to get the next letter. Once
             // again, this is written to allow variable faced blocks.
             // k starts out as [0,0,0,0]
             // then goes to [1,0,0,0], [2,0,0,0] etc thru to [n1,n2,n3,n4] where
             // n* is the max number of block faces for given block. The size of
             // k is the number of blocks (this shows 4).
             for (int i = 0; i < k.length; i++) {
                int v = k[i];
                if (v >= blocks.get(i).length - 1) {
                   k[i] = 0;
                }
                else {
                   k[i]++;
                   break;
                }
             }
          }
          String format = count != 1 ? "%nThere were %d combinations found.%n"
            : "%nThere was %d combination found.%n";
          System.out.printf(format, count);
       }
    }

The posted code prints the following.

[f, n, i, t, y] [0, 1, 2, 3, 1]
[f, n, i, t, y] [1, 1, 2, 3, 1]
[f, n, i, t, y] [0, 2, 2, 3, 1]
[f, n, i, t, y] [1, 2, 2, 3, 1]
[i, n, f, t, y] [2, 1, 3, 3, 1]
[i, n, f, t, y] [2, 2, 3, 3, 1]
[f, n, i, t, y] [0, 1, 2, 3, 12]
[f, n, i, t, y] [1, 1, 2, 3, 12]
[f, n, i, t, y] [0, 2, 2, 3, 12]
[f, n, i, t, y] [1, 2, 2, 3, 12]
[i, n, f, t, y] [2, 1, 3, 3, 12]
[i, n, f, t, y] [2, 2, 3, 3, 12]

There were 12 combinations found.

Answer 2

my incomplete idea is as follows: the blocks are put in an array and its index serves as unique id for each block. then you build a map of lists: Map<String, List<Integer>> where the key is an occurrence of a letter in the target word (so that for the word 'food' the letter 'o' should apear twice in the map, say with key values "o1" "o2") the values in the map is the list of blocks that contain the letter.
after you build this data structure you need to search for a set of unique integer values across the values in the map.

EDIT:

so the blocks are already represented in an array. so the first block, the one in cubes[0] will have an id of value 0 and so on. for the word "food" you build a map of four entries. the keys are: "f1", "o1", "o2", "d1". the numbers are used so that you can place the same letter more than one time in the map.
after you determined the keys, you loop on all the blocks, for each block on all its letters, for each letter you look if it is part of the target word. if it is, you add the block's id (index in cubes, remember?) to the list that is value in the map. after that is done you will have the following mapping

"f1" -> [0,2,3]  // blocks 0,2,3 contain 'f'
"o1" -> [0,1,2]
"o2" -> [0,1,2]
"d1" -> [0,1]

now you loop on the values (the lists of integers) and you look for a set of unique integer values that is taken from each map entry. for example the set 3,1,2,0 (3 is taken from the first map entry, 1 from the 2nd map entry and so on) --> the set is the answer.

Answer 3

String[] split = word.split("");

Set<String> mySet = new HashSet<>(split);

for(int i = 0; i < numberOfCubes; i++) {
    //get cube

     for(int k = 0; k < 6; k++){

        //loop through each value in the cube and try to remove it from the set
        set.remove(cube[k]); 
     }
}

if mySet length = 0; return true;//i.e. cubes can create the word