CareerCup

Ok I got the partial solution by not using backtracking.

Let A1,A2,A3 be the positions of 3 numbers(i.e. A1 for 1,A2 for 2 and A3 for 3) in the 6 slots.

Sum of 6 slots indexes(starting with 1) = 6*7/2=21 (geometric series sum problem)

Based on the position of slots of the numbers, the sum should be
A1+(A1+2)+A2+(A2+3)+A3+A3+4 = 21 There is A1+2 because the second '1' will be 2 indexes after the first '1'. similarly for 2 and 3
2(A1+A2+A3) = 21 -9 i.e. A1+A2+A3 = 6
Had the sum of the numbers been contains decimals, there is no possible solution. i.e. try for 5.

If we choose the highest number in the first slot, then
equation will be A1+A2 = 5. 5 is possible with 2 numbers (remaining) with the following either (4,1) (1 is already taken) and so the other (2,3) is the only place where we can put either 2 or 1. Trying these two cases, will yield A2 = 3 and A1=2

I think this can be further improved. Feel free to jump in with your improvements...

C++ 11 solution:

A recursive solution.

void fillRec(int n, vector<int>& A, vector<vector<int>> &output) {
	if( n == 0 ) {
		output.push_back(A);
		return;
	}
	for(decltype(A.size()) firstLoc = 0; firstLoc <= A.size() - n - 2; firstLoc++) {
		auto secondLoc = firstLoc + n + 1;
		if(A[firstLoc] == 0 && A[secondLoc] == 0) {
			A[firstLoc] = n;
			A[secondLoc] = n;
			fillRec(n-1, A, output);
			A[firstLoc] = 0;
			A[secondLoc] = 0;
			
		}	
	}  
}
vector<vector<int>> fill(int n) {
	vector<int> A(2*n, 0);
	vector<vector<int>> output;
	fillRec(n,A,output);
	return output;
}

Solved using back tracking. solution not possible for all n

import sys
def fillArray(arr, nums):
    if len(nums) == 0:
        print arr
        return True
    for n in xrange(len(nums)):
        #choose number to be filled next
        p = nums[n]
        nums[n] = nums[0]
        
        tobeFilled = -1
        for i in xrange(len(arr)):
            if arr[i] == 0:
                tobeFilled = i
                break
        
        if tobeFilled >= 0 and tobeFilled + p + 1 < len(arr) and arr[tobeFilled + p + 1] == 0:
            #forward
            arr[tobeFilled] = p
            arr[tobeFilled + p + 1] = p
            
            ret = fillArray(arr, nums[1:])
            if ret:
                return True
            #backtrack
            arr[tobeFilled] = 0
            arr[tobeFilled + p + 1] = 0
        #reset numbers
        nums[n] = p
        
    return False

if __name__ == "__main__":
    if len(sys.argv) != 2 or not sys.argv[1].isdigit():
        print "give exactly one argument as int"
        exit(1)
    n = int(float(sys.argv[1]))
    arr = [0] * 2*n
    nums = [x for x in xrange(n, 0, -1)]
    if fillArray(arr, nums):
        print "success"
    else:
        print "failed"
    #print arr

Hi. I'm new here and this is the first task I saw on this site. It bugs me now for a couple of days, so I decided to share my findings, hoping that it might give some ideas to someone else working on it.
I was trying to trace some mathematical dependencies of indexes and this is what I found:

1. Task can be resolved only for 3*i+1 and 3*i+2 for i > 1. For example there is no solution (or at least I couldn't find it) for 5,6,9,10 etc. Solutions for 3,4,7,8,11,12 etc are easy calculated by the backtrack algorithm
2. For each valid n there are 2 solutions: one having n on position 0 and second is mirrored. I.e. for 4: it's 4 1 3 1 2 4 3 2 and 2 3 4 2 1 3 1 4
3. In all the cases I observed the first index of n is 0 (obvious), n - 1 is at 2, n-2 is at 1.

Here are some solutions, to observe:
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
15: 15 13 14 8 5 12 7 11 4 10 5 9 8 4 7 13 15 14 12 11 10 9 6 3 1 2 1 3 2 6
16: 16 14 15 9 7 13 3 12 6 11 3 10 7 9 8 6 14 16 15 13 12 11 10 8 5 2 4 1 2 1 5 4

Were there any clarification on what happens if there are any collisions, and out of range?

let's say we have: (4, 2, 5, 1, 7) -> (4, 2, 5, 1, 4|2, 1, 7, 5, E, E), ..., 7

It is clear that 4 and 2 will compete for the same position.
7 will be moved away, also 7 is the last number in the range so when trying to put into a
position within 2N range, will fall out or range.

Am I to lost on this?

Here is a Java solution to this problem.

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


public class FillArrayBackTracking {
	
	
	
	public static void main(String[] args) {
		List list= Arrays.asList(1,2,3,4,5,6,7);
		ArrayList<Integer> listArr=new ArrayList<Integer>(list);
		int[] solution=new FillArrayBackTracking().solve(listArr);
		System.out.println(Arrays.toString(solution));
	}
	
	
	
	public int[] solve(ArrayList<Integer> list){
		if (list==null || list.size()==0)
			return null;
		
		return solveRec(list, new int[list.size()*2],0);
		
		
		
	}

	private int[] solveRec(ArrayList<Integer> list, int[] arr, int startPos) {
		if (startPos>=arr.length || list.size()==0)
			return arr;
		
		for (int i=0;i<list.size();i++){
			int v=list.get(i);
			if (arr.length>v+startPos+1
					&& arr[v+startPos+1]==0){ // if it's within the range!
				arr[startPos]=v;
				arr[startPos+v+1]=v;
				ArrayList<Integer> nlist=(ArrayList<Integer>) list.clone();
				nlist.remove(i);
				int nStartPos=startPos;
				do{
					nStartPos++;
				}while(nStartPos<arr.length && arr[nStartPos]>0);
				int[] nArr=Arrays.copyOf(arr,arr.length);
				int[] sol=solveRec(nlist, nArr, nStartPos);
				if (sol!=null){
					//It works ... let's return the result and be happy....
					return sol;
				}else{
					//reset the array and try with another value!
					arr[startPos]=0;
					arr[startPos+v+1]=0;
				}
			}
		}
		

		return null;

	}
	

}