|
||||||||||
|
ploh wins Room 1
WordGridby gepaSince we have only up to 3 unknown letters, one may be tempted to try all 263 combinations, and brute force each of them, until a solution is found. But brute forcing the word search problem may be slow in a 50 x 50 grid with up to 50 words, so we have to do do the actual word search before trying the letter combinations.
For each word in the given word list we try to locate this in the
given grid (without using any periods '.') - this can be done
simply by brute force checking all possible starting positions
and directions. If it is found, we can remove this word from the
list, since it does not affect the result (whatever letters we place
at the positions of the periods, we can always find this word in the
grid). If a word is not found, we repeat the word search procedure
(checking all possible starting positions and directions), but now
regarding the periods as wildcards. We make a list of all possible
period-letter combinations found that allow the word to be found in
the grid. For this, it is convenient to enumerate the periods in
the grid, and to store a three-letter string for every placement
we found (e.g. in the form
After this preprocessing we have several options for solving the problem.
Let's say we have an array
A simple solution is to iterate over all 263 three-letter
combinations and check for each of them if all Iterate String test from "AAA" to "ZZZ" { boolean solution = true; for (int i = 0; i < letters.length; i++) { boolean found = false; for (int j = 0; j < letters[i].size(); j++) { if (test.matches(letters[i].get(j)) { found = true; break; } } if (found == false) { solution = false; break; } } if (solution == true) { // test represents the solution Replace first period in grid with test.charAt(0); Replace second period in grid with test.charAt(1); Replace third period in grid with test.charAt(2); return grid; } }
Alternatively we can use backtracking, starting with iterating over
the strings of String backtrack(String test, int position) { if (position == letters.length) { return test; } for (int i = 0; i < letters[i].size(); i++) { if (consistent(test, letters[i])) { backtrack(combine(test, letters[i]), position + 1); } } }
In the above, Of course, if we have less than 3 periods in the original grid, we can also use smaller strings in the above procedures.
After we have found the period-letter mappings (e.g. the return
value in the above backtracking implementation - after an initial
call BinaryBoardby gepaIt is clear that we can not brute force this problem trying all possible 236 boards. We have to use backtracking, by filling the positions in the board in some clever order. Let's start by filling in only the first row and first column. With this we have at least the first bit of all 12 numbers. We can now check this bit, if it is consistent with the given ordering (for this we must have firstBit(order[0]) <= firstBit(order[1]) <= firstBit(order[2]) <= ... <= firstBit(order[11])). This allows for up to 13 combinations for the first row and first column in the worst case (instead of 211). For each combination that is consistent with the given ordering, we go on with the second bit of all rows/columns, and check that firstTwoBits(order[0]) <= firstTwoBits(order[1]) <= ... <= firstTwoBits(order[11]). In the worst case, 5 of the first bits in rows/columns H2-H6, V2-V6 are 0 and the other 5 are 1, which allow for the second bits up to 6 * 6 = 36 combinations (instead of 29). We continue with the rest of the bits using the same procedure, until we reach the last bit, where we finally check if the board we have built up is a solution to the problem. If yes, we return this (since the constraints guarantee that there is only one solution), otherwise we continue with the backtracking. In pseudocode: backtracking(int bitnumber) { if (bitnumber == 7) { // we have set all bits 1-6 of all numbers, check that they conform to the ordering if (number(order[0]) < number(order[1]) < number(order[2]) < ... < number(order[11])) { Return the solution found, abort the backtracking. } return; // no solution found yet, jump to the previous backtracking step } Iterate over all values for the bitnumber-th bit of the 12 numbers H1-H6, V1-V6 { // (ignore in the iteration bits that have already been assigned a value, // e.g. when we set the first bit of V2 when calling backtracking(1), this // is also the second bit of H1, so we don't need to reset it during the // call to backtracking(2)). if (first-bitnumber-bits(order[0]) <= first-bitnumber-bits(order[1]) <= ... <= first-bitnumber-bits(order[11])) { backtracking(bitnumber + 1); } } }
Here, SackJourneyby brett1479The infinite sack described in this problem is really an infinite stack. Translated into the language of automata theory, this problem asks which states are reachable in a PDA (pushdown automaton). To solve the problem, we incrementally build a reachability graph. A directed edge from p to q in this graph indicates the ability to travel from p to q without changing the stack configuration. Edges of the form "__" can immediately be added to this graph, since they do not involve the stack. Furthermore, if you can get from location x to location s while adding A to your sack, and you can get from location t to location y by removing A from your sack, then a reachability edge from s to t implies a reachability edge from x to y. Lastly, the reachability graph should be transitive. In other words, an edge from p to q and an edge from q to r yields an edge from p to r. Repeating these steps until no more changes can be made, we can determine which locations are reachable from 0 without changing the stack. To check if a specific location k is reachable, add a new location k' to the graph. In addition, add an edge of the form "__" from k to k'. Lastly, add loops to k' permitting the removal of all types of elements from the sack. The previously described algorithm will determine whether there is a path from 0 to k' resulting in an empty sack. This is equivalent to being able to reach k. |
|