Write an algorithm for returning an array in such a way that each number k from 1..n occurs exactly twice and k is a distance different from its replica
This question was asked in an interview.
For a given integer n> = 3, returns an array of size 2n, so that each number k from 1 to n occurs exactly twice, and each number and its repetition are separated by a distance equal to the number.
Functional signature:
int* buildArray(int n)
For example, for n = 3:
3, 1, 2, 1, 3, 2
Number 2
: 1st position 3 and 2nd position 6, so distance 6 - 3 - 1 = 2.
Number 3
: first 3
in position 1 and 2 3
at position 5, so distance 5 - 1 - 1 = 3.
For n = 4:
4, 1, 3, 1, 2, 4, 3, 2
source to share
This is Langford's problem / consistency.
There is already a thread about the same issue on SO with implementation. Langford Haskell or C sequence execution
source to share
This is the problem with the exact shell , which you can solve with the help of X algorithm . (And this is a more convenient, simpler example than Sudoku.) You have the following restrictions:
- each number must be used twice and
- each slot in the array can be occupied by only one number
For your n = 3 problem, you end up with the following matrix:
[0] [1] [2] [3] [4] [5] 1 2 3
--- --- --- --- --- --- --- --- ---
#0 X X X
#1 X X X
#2 X X X
#3 X X X
#4 X X X
#5 X X X
#6 X X X
#7 X X X
#8 X X X
Columns [x]
indicate the slot is in use x
; plain x
means a digit has been set x
. Lines # 0 through # 3 describe the possible placements, # 4 through # 6 the binary placements and # 7 and # 8 twi-opportunities to place the three. This will give two (mirrored) solutions:
2 3 1 2 1 3 (#2 + #4 + #8)
3 1 2 1 3 2 (#1 + #6 + #7)
Not all solutions n yield, no solutions for 5 and 6 for example.
source to share
This is an NP-complete problem.
However, it can be fairly easily coded with recursion and backtracking , making it a suitable interview solution. It's like, for example, N queens puzzle backtracking solution (which was my inspiration).
Ready to run code in Java:
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
for (int i = 3; i < 13; i++) {
int[] answer = buildArray(i);
if (answer[0] != 0) {
System.out.println(i + " " + Arrays.toString(answer));
}
}
}
public static int[] buildArray(int n) {
int[] answer = new int[2 * n];
put(answer, n); // start with placing n, later (n - 1), (n - 2), ..., 1
return answer;
}
private static boolean put(int[] answer, int k) {
for (int i = 0; i + k + 1 < answer.length; i++) { // try every posiiton
if (answer[i] == 0 && answer[i + k + 1] == 0) {
answer[i] = k;
answer[i + k + 1] = k;
if (k == 1) {
return true; // we found a solution, escape!
}
if (put(answer, k - 1)) {
return true; // we found a solution, escape!
}
answer[i] = 0; // step back and erase this placement
answer[i + k + 1] = 0;
}
}
return false; // still not full solution, continue
}
}
Output:
3 [3, 1, 2, 1, 3, 2]
4 [4, 1, 3, 1, 2, 4, 3, 2]
7 [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1]
8 [8, 3, 7, 2, 6, 3, 2, 4, 5, 8, 7, 6, 4, 1, 5, 1]
11 [11, 6, 10, 2, 9, 3, 2, 8, 6, 3, 7, 5, 11, 10, 9, 4, 8, 5, 7, 1, 4, 1]
12 [12, 10, 11, 6, 4, 5, 9, 7, 8, 4, 6, 5, 10, 12, 11, 7, 9, 8, 3, 1, 2, 1, 3, 2]
source to share