August 3, 2022 Single Round Match 834 Editorials
WordleColors
Appropriately assigning the colors to the letters in Wordle is not a trivial task. When writing the problem statement we decided to play nice: instead of just giving you the requirements (e.g., “for each letter of alphabet the number of yellow and green copies of that letter in the guess must not exceed the actual number of occurrences of that letter in the secret word”) we actually described a deterministic process that assigns the colors properly. Your task was just to implement it correctly.
A good tool for the implementation are boolean arrays in which we remember which letters of both words have already been paired.
public String color(String hidden, String guess) {
int N = 5;
boolean[] hiddenUsed = new boolean[N];
boolean[] guessUsed = new boolean[N];
char[] color = new char[5];
for (int n=0; n<N; ++n) color[n] = '-';
// assign green
for (int i=0; i<N; ++i) {
if (guess.charAt(i) == hidden.charAt(i)) {
color[i] = 'g';
guessUsed[i] = true;
hiddenUsed[i] = true;
}
}
// assign yellow
for (int i=0; i<N; ++i) if (!guessUsed[i]) {
for (int j=0; j<N; ++j) if (!hiddenUsed[j]) {
if (guess.charAt(i) == hidden.charAt(j)) {
color[i] = 'y';
guessUsed[i] = true;
hiddenUsed[j] = true;
break;
}
}
}
// assemble and return answer
String answer = "";
for (char c : color) answer += c;
System.out.println(answer);
return answer;
}
GoThereExactly
First, let’s start with just getting from (r1,c1) to (r2,c2) in s steps, without worrying with the “exactly” constraint.
The minimum number of steps is clearly d = abs(r1-r2) + abs(c1-c2). If our s is smaller than that, we are clearly out of luck.
Imagine the whole plane colored like a chessboard. Each step takes us from a white cell onto a black cell or vice versa. In other words, each step changes the color of your cell. (Mathematically, the value (row+column) modulo 2 changes in each step.)
What this means: if the starting cell and the destination cell have the same color, each path from the start to the goal must have an even length. And if they have opposite colors, each path must have an odd length.
Another way of looking at the same observation: We have already shown how to compute the shortest distance d. This is the length of a valid path from the start to the goal, which means that all possible paths must also have the same parity. In other words, there are no paths of length d+1, d+3, d+5, …, there can only be paths of length d+2, d+4, d+6, …
If we were allowed to step on any cell multiple times, we would be done: e.g., we could just walk along the shortest path to reach the goal in d steps, and then we would make a step away and back until the total number of steps reaches exactly s.
In our problem there was one final complication: we were not allowed to step onto the goal too early. There are many ways to deal with this, below we describe one of the simpler ones in terms of the number of different cases to consider.
- Construct one particular shortest path from the start to the goal. Do this by first going U/D as needed and then going R/L as needed.
- Check whether the shortest path is short enough. If it’s already longer than s, report no answer.
- Compare the parities of s and d (d = the length of the shortest path). If they don’t match, report no answer.
- Let r = d-s. We need to add r extra steps in a way that is sure not to visit the goal cell.
- If the shortest path starts with ‘U’, return the following solution: (r/2) steps D + (r/2) steps U + the shortest path to the goal.
- In all other cases, return the following solution: (r/2) steps U + (r/2) steps D + the shortest path to the goal.
Clearly, the detour we added to the beginning is disjoint with the shortest path and thus we are guaranteed that it does not hit the goal too early.
public String walk(int r1, int c1, int r2, int c2, int s) {
String direct = "";
while (r1 < r2) { ++r1; direct += "D"; }
while (r1 > r2) { --r1; direct += "U"; }
while (c1 < c2) { ++c1; direct += "R"; }
while (c1 > c2) { --c1; direct += "L"; }
if (direct.length() > s) return "IMPOSSIBLE";
if (direct.length()%2 != s%2) return "IMPOSSIBLE";
int remain = s - direct.length();
char away = 'U', back = 'D';
if (direct.length() > 0 && direct.charAt(0) == 'U') {
away = 'D'; back = 'U';
}
String delay = "";
for (int i=0; i<remain/2; ++i) delay += away;
for (int i=0; i<remain/2; ++i) delay += back;
return delay + direct;
}
MatchingPatterns
Let’s examine the last example. We have the variables A, B, C, D that represent strings of length 1, 2, 3, 4. We are told that the patterns “ABCD” and “DxAyzB” represent the same string.
The key observation is that as we know the lengths, we can break each string-variable into individual character-variables. The first pattern is the following sequence of characters:
{ A[0], B[0], B[1], C[0], C[1], C[2], D[0], D[1], D[2], D[3] }
while the second pattern is the following sequence of characters:
{ D[0], D[1], D[2], D[3], x, A[0], y, z, B[0], B[1] }
As these sequences have to be completely equal, we get a bunch of equalities: A[0] = D[0], B[0] = D[1], B[1] = D[2], C[0] = D[3], C[1] = x, and so on.
This observation already gives us a complete solution. Imagine a graph where the vertices are all character variables and also all lowercase letters. (There are at most 26*10 + 26 = 286 vertices.) Each forced equality can be represented by adding an edge to this graph. Once we are done adding the edges, the connected components of this graph tell us the information we need: for each connected component, all vertices in it must represent the same lowercase letter.
If any component contains more than one lowercase letter, we have found a contradiction: there can be no solution. If a component contains exactly one lowercase letter, assign it to all the variables in that component. And if a component contains no lowercase letters, the variables in this component can be assigned any lowercase letter we like (but of course all of them must be assigned the same letter).
As the number of vertices is quite small, we can use Floyd-Warshall to locate the connected components in a simple way.
boolean isVariable(char c) { return c >= 'A' && c <= 'Z'; }
int getLength(int[] L, char c) {
if (isVariable(c)) return L[c-'A']; else return 1;
}
int getTotalLength(int[] L, String pattern) {
int answer = 0;
for (char c : pattern.toCharArray()) answer += getLength(L, c);
return answer;
}
public String solve(int N, int[] L, String[] patterns) {
int P = patterns.length;
int Z = getTotalLength(L, patterns[0]);
for (String pat : patterns) if (getTotalLength(L, pat) != Z) return "";
// assign numbers 0..V-1 to the individual character variables
int V = 0;
int[][] variableID = new int[N][];
for (int n=0; n<N; ++n) {
variableID[n] = new int[ L[n] ];
for (int i=0; i<L[n]; ++i) variableID[n][i] = V++;
}
// create variables V..V+25 that are already assigned the lowercase letters
char[] assigned = new char[V+26];
for (int v=0; v<V; ++v) assigned[v] = ' ';
for (int i=0; i<26; ++i) assigned[V+i] = (char)('a'+i);
// rewrite each pattern as a sequence of character variables
int[][] evaluated = new int[P][Z];
for (int p=0; p<P; ++p) {
int w = 0;
for (char c : patterns[p].toCharArray()) {
if (isVariable(c)) {
int n = c-'A';
for (int i=0; i<L[n]; ++i) evaluated[p][w++] = variableID[n][i];
} else {
evaluated[p][w++] = V+(c-'a');
}
}
}
// build the graph by adding edges between variables known to be equal
boolean[][] same = new boolean[V+26][V+26];
for (int i=0; i<V+26; ++i) same[i][i] = true;
for (int z=0; z<Z; ++z) for (int p=0; p+1<P; ++p) {
int x = evaluated[p][z], y = evaluated[p+1][z];
same[x][y] = same[y][x] = true;
}
// run Floyd-Warshall to get the transitive closure (connected components)
for (int k=0; k<V+26; ++k)
for (int i=0; i<V+26; ++i)
for (int j=0; j<V+26; ++j)
same[i][j] = same[i][j] || (same[i][k] && same[k][j]);
// check for contradictions
for (int i=0; i<26; ++i) for (int j=i+1; j<26; ++j)
if (same[V+i][V+j]) return "";
// assign lowercase letters to all variables
for (int v=0; v<V; ++v) for (int i=0; i<26; ++i) if (same[v][V+i])
assigned[v] = (char)('a'+i);
for (int v=0; v<V; ++v) if (assigned[v] == ' ')
assigned[v] = 'g'; // an arbitrary choice
// take the first pattern and convert it to the corresponding string
String answer = "";
for (char c : patterns[0].toCharArray()) {
if (isVariable(c)) {
int n = c-'A';
for (int x : variableID[n]) answer += assigned[x];
} else {
answer += c;
}
}
return answer;
}
ItsWhomYouKnow
This was an intermediate level data structure exercise: we need to keep track of several different things and we need to maintain some structure in it so that we can make all the updates efficiently.
The reference solution maintains the information in the following data structures:
- a simple array clanPower in which we store, for each clan, its current known power
- a hashmap waitingClanMembers in which we store, for each clan, a queue of its members who are currently in the waiting room
- a maximum heap waitingClanHeap in which we store a binary heap of all the clans that currently have someone in the waiting room; current known power is used as the priority for this heap
- a simple array whereInHeap in which we store, for each clan that has someone waiting, its current index in the heap waitingClanHeap.
Whenever a doctor calls for a new patient, we do the following:
- Peek at the top of waitingClanHeap to determine the most powerful waiting clan: O(1).
- Look into waitingClanMembers to get the queue for this clan: expected O(1).
- Pop the longest-waiting member from the queue and remember them as the patient to send in: O(1).
- If the queue just became empty, we need to remove this clan from among the waiting ones: set their whereInHeap to “none” and pop the top of the heap: O(log(C)).
Whenever a new patient enters the waiting room, there are two options: either his clan has already someone waiting, or they don’t. If they don’t:
- Make a new queue for the clan in waitingClanMembers and push the current patient into the queue as its currently only element: expected O(1).
- If needed, update the power of the patient’s clan: O(1)
- Push a new entry for this clan into waitingClanHeap: O(log(C))
If the clan already has someone else waiting:
- Push the current patient into the clan’s queue: expected O(1)
- If needed, update the power of the patient’s clan: O(1)
- If you did update the clan’s power, use whereInHeap to locate the clan’s record in the heap and bubble that record up as necessary according to the clan’s new power: O(log(C))
The last step is simply the “increase key” operation on the maximum heap used to store the priority queue of the clans.
In total, our solution will perform L+3*N operations, and as each of them takes O(log C) time, the total running time of this solution is O( (L+N)*log C ).
In the implementation below, note how swapInHeap is implemented: whenever we swap a record in the heap with its parent/child, we also update the “pointers” in whereInHeap so that they correctly point to their clans’ new locations in the heap.
int[] clanPower;
HashMap<Integer, Queue<Integer> > waitingClanMembers;
int HC;
int[] waitingClanHeap;
int[] whereInHeap;
boolean shouldGoHigher(int where, int other) {
int mc = waitingClanHeap[where], oc = waitingClanHeap[other];
if (clanPower[mc] != clanPower[oc]) {
return clanPower[mc] > clanPower[oc];
} else {
return mc < oc;
}
}
void swapInHeap(int where, int other) {
int mc = waitingClanHeap[where], oc = waitingClanHeap[other];
waitingClanHeap[where] = oc;
waitingClanHeap[other] = mc;
whereInHeap[oc] = where;
whereInHeap[mc] = other;
}
void bubbleUp(int where) {
while (true) {
if (where == 0) break;
int parent = (where - 1) / 2;
if (!shouldGoHigher(where, parent)) break;
swapInHeap(where, parent);
where = parent;
}
}
void bubbleDown(int where) {
while (true) {
int cand = where;
for (int i=1; i<=2; ++i) {
int child = 2*where + i;
if (child >= HC) break;
if (shouldGoHigher(child, cand)) cand = child;
}
if (cand == where) break;
swapInHeap(where, cand);
where = cand;
}
}
void addNewPerson(int id, int clan, int power) {
if (whereInHeap[clan] == -1) {
waitingClanHeap[HC] = clan;
whereInHeap[clan] = HC;
++HC;
}
clanPower[clan] = Math.max( clanPower[clan], power );
bubbleUp( whereInHeap[clan] );
if (waitingClanMembers.containsKey(clan)) {
Queue<Integer> Q = waitingClanMembers.get(clan);
Q.add(id);
} else {
Queue<Integer> Q = new ArrayDeque<Integer>();
Q.add(id);
waitingClanMembers.put( clan, Q );
}
}
int getNextPatient() {
// we know that somebody is waiting, no need to check for an empty heap
int clan = waitingClanHeap[0];
Queue<Integer> Q = waitingClanMembers.get(clan);
int person = Q.remove();
if (!Q.isEmpty()) return person;
whereInHeap[clan] = -1;
int lastClan = waitingClanHeap[HC-1];
waitingClanHeap[0] = lastClan;
whereInHeap[lastClan] = 0;
--HC;
bubbleDown(0);
return person;
}
public long simulate(int N, int C, int P,
int[] initialClans, int[] initialPowers, int seed) {
clanPower = new int[C];
waitingClanMembers = new HashMap<Integer, Queue<Integer>>();
HC = 0;
waitingClanHeap = new int[C+7];
whereInHeap = new int[C]; for (int c=0; c<C; ++c) whereInHeap[c] = -1;
int L = initialClans.length;
for (int i=0; i<L; ++i) addNewPerson(i, initialClans[i], initialPowers[i]);
long state = seed;
long answer = 0;
for (long n=0; n<N; ++n) {
for (int i=0; i<2; ++i) {
state = (state * 1103515245 + 12345) % (1L << 31);
int clan = (int)( (state/10) % C );
state = (state * 1103515245 + 12345) % (1L << 31);
int power = (int)( state % P );
addNewPerson(L++, clan, power);
}
int who = getNextPatient();
answer += who * (n+1);
state = (state + who) % (1L << 31);
}
return answer;
}
WordleBack
This problem turns out to be much trickier than it might seem at the first glance.
Let’s start by making an initial observation about green letters. The green letters in guess can mostly be ignored. Imagine two inputs: one is the original, the other is obtained from the original by completely erasing all green letters. Clearly, there is a one-to-one correspondence between their solutions. In particular, you can take any valid solution to the smaller one and add back the green letters to get the full valid solution to the original test case.
Thus, below we’ll assume there are no green letters, only yellow and gray ones (‘y’s and ‘-’s).
The next step is a necessary condition for a solution to exist. Whenever Wordle colors the letters, the leftmost occurrences of each letter of the alphabet are colored yellow. Thus, in Wordle there can never be a grey X to the left of a yellow X. If we have such a situation in our instance, it clearly has no solution.
While we are checking this necessary condition, we can also gather two useful sets of information:
- For each letter of the alphabet: how many yellow copies have we seen?
- For each letter of the alphabet: have we seen at least one grey copy?
The first information (minCount in the code below) tells us that we need at least that many copies of this letter in the hidden word. The second information (canHaveMore) tells us whether the hidden word can have more copies of this letter than the given guess. (Note that as soon as we’ve seen a grey occurrence of a letter in the guess, we know the exact number of occurrences of that letter in the hidden word.)
Suppose we have Y yellow and G gray letters in our guess. The hidden word must contain the Y yellow letters we have and G additional letters. We’ll call each of the G additional letters a wildcard. Each wildcard can be equal to any letter that canHaveMore, and the wildcards are all mutually independent.
We now need to assign these Y+G letters (Y forced ones + G wildcards) to the Y+G positions in the hidden word. While doing this there is one final constraint: as none of these letters are green in the guess, each letter in hidden must differ from the corresponding letter in guess.
This final step (i.e., checking whether such an assignment exists and then finding one) can be done by a careful case analysis. Essentially, the main problem is if there are too many copies of a single letter: if there’s more of them than positions where they can appear, this creates a contradiction.
However, there is a much cleaner and simpler way to do the final step: we can simply reduce it to bipartite matching. Our Y forced letters + G wildcards will form one partition, the Y+G indices into the hidden word will form the other partition, and edges will represent the relation “this letter/wildcard can be placed onto this position”. (When checking whether a wildcard can be placed on position x, we need to check whether there is a letter other than guess[x] that canHaveMore.)
The valid solutions then correspond precisely to all perfect matchings in the bipartite graph described above.
boolean canPlace(char letter, int position, String guess, String colors) {
return letter != guess.charAt(position);
}
public String deduce(String guess, String colors) {
// temporarily erase all green letters
String guess2 = "", colors2 = "";
for (int i=0; i<guess.length(); ++i) if (colors.charAt(i) != 'g') {
guess2 += guess.charAt(i);
colors2 += colors.charAt(i);
}
// verify the condition “no gray before yellow”
// compute minCount and canHaveMore
int N = guess2.length();
int[] minCount = new int[26];
boolean[] canHaveMore = new boolean[26];
for (int i=0; i<26; ++i) {
char c = (char)('A' + i);
boolean seenDash = false;
for (int n=0; n<N; ++n) {
if (guess2.charAt(n) != c) continue;
if (colors2.charAt(n) == '-') {
seenDash = true;
} else {
if (seenDash) {
System.out.println("abort: seenDash");
return ""; // impossible: '-' then 'y'
}
++minCount[i];
}
}
canHaveMore[i] = !seenDash;
}
// assemble our collection of letters and wildcards
char[] letters = new char[N];
{
int w = 0;
for (int n=0; n<26; ++n) for (int i=0; i<minCount[n]; ++i)
letters[w++] = (char)('A'+n);
while (w < N) letters[w++] = '*';
}
// build the bipartite graph
MaximumMatching MM = new MaximumMatching(N, N); // letter, position
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) {
if (letters[i] == '*') {
boolean canAny = false;
for (int n=0; n<26; ++n) if (canHaveMore[n])
if (canPlace((char)('A'+n), j, guess2, colors2))
canAny = true;
if (canAny) MM.addEdge(i, j);
} else {
if (canPlace(letters[i], j, guess2, colors2)) MM.addEdge(i, j);
}
}
// find the maximum matching and check that it’s perfect
int[] matching = MM.maximumMatching();
for (int x : matching) if (x == -1) return "";
// convert the matching to a sequence of letters
char[] answer2Letters = new char[N];
for (int n=0; n<N; ++n) {
if (letters[n] == '*') {
for (int i=0; i<26; ++i) {
char c = (char)('A'+i);
if (canHaveMore[i] && canPlace(c,matching[n],guess2,colors2)) {
answer2Letters[ matching[n] ] = c;
break;
}
}
} else {
answer2Letters[ matching[n] ] = letters[n];
}
}
String answer2 = "";
for (char c : answer2Letters) answer2 += c;
// insert back the green letters and we are done
String answer = "";
for (int i=0, j=0; i<guess.length(); ++i) {
if (colors.charAt(i) == 'g') {
answer += guess.charAt(i);
} else {
answer += answer2.charAt(j++);
}
}
return answer;
}
misof
