Find X in a partially sorted Array

2

1

Your job is to find the location (read index) of a given element X in an array gone through the following transformation process:

  1. Take a fully sorted integer array of size N (N is known implicitly)
  2. Take any random number of mutually exclusive even index pairs (as in that no index appears in more than 1 pair) from the array and swap the elements on those indexes.

A sample array can be like

[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

formed by

// Take fully sorted integer array
[-1, 2, 3, 4, 5, 6, 70, 80, 90, 100]
// Take some even index pairs : (0, 4) and (6, 8)
// Swap the elements in these indexes. i.e., element at 4<sup>th</sup> index goes to 0<sup>th</sup> etc.
// Final array:
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

and a sample X to find in this array can be

-1

You should output the index of the element X in the final array (4 in the above example) or -1 if the element is not found in the array.

Rules

  • In built searching functions are prohibited.
  • You must write a method/function/program which takes input from STDIN/Command line arguments/Function arguments.
  • Input must be in <Array> <X> format. Example: [5, 2, 3, 4, 1, 6, 9, 8, 7, 10] 1
  • The input array may also contain duplicate integers. In such case, any one index can be the output. UPDATE : You may assume that total number of duplicates << (far less than) size of array. For the benefit of the question in general, duplicates are now prohibited to avoid playing a role in time complexity of the searching algorithm.
  • Output should be the index of the element X in the array or -1 if not present.

Scoring

  • Being a and a , your score is calculated by <byte count of your program>*<coeff. of complexity>
  • Coefficient of Complexity is decided based on the worst case time complexity of your code (Big-O) using the mappings given below.
  • If your code needs to know the length of the array, it can calculate length using inbuilt methods and that won't be added to the time complexity of the searching part of the code.
Time Complexity      Coefficient
--------------------------------
O(1)                 0.25
O(log(n))            0.5
O(n)                 5
O(n*log(n))          8.5
O(n^2)               10
O(greater than n^2)  20

Minimum score wins!

Bonus

  • Multiply your final score by 0.5 if you can handle a case where the array has gone through the step 2 in the transformation process I times (instead of just 1), where I is passed as the third parameter in input.
  • Note that while going through step 2, I times, pairs in each step are mutually exclusive, but pairs in different steps can have common indexes.

Optimizer

Posted 2014-10-04T22:23:12.877

Reputation: 25 836

Answers

7

JavaScript (E6) 97.5 (39*5*0.5)

(O(n), linear search, the array can be scrambled again and again)
The function accepts (and ignores) a third parameter

F=(a,x)=>a.map((e,i)=>e-x?0:j=i,j=-1)|j

or

F=(a,x)=>a.some((e,i)=>(j=i,e==x))?j:-1

or

F=(a,x)=>a.every((e,i)=>(j=i,e-x))?-1:j

Test in FireFox/FireBug console

F([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1, 2)

Output

4

edc65

Posted 2014-10-04T22:23:12.877

Reputation: 31 086

Nicely played with coefficients and bonus! – Optimizer – 2014-10-05T08:32:37.827

4

Golfscript, 20 * 2.5 = 50

~{={0:-1}*0):0}+%;-1

Explanation:

  • ~ - eval the input. It should be in the form [-1 0 3 2 4] 3.
  • {...}+% - prepend the last argument (needle) to {...}, then map the resulting function over the array
  • ;-1 - discard the results of the mapping, and push -1 to the stack.

The real fun is what happens inside:

  • = - check if the needle matches the haystack element
  • {0:-1} - take the current value of the variable 0 and store it into the variable -1.
  • * - execute the function n times = execute if the previous is true.
  • 0):0 - increment the current value of 0.

yep. In golfscript, numeric all literals are just variables initialised to some useful values.

John Dvorak

Posted 2014-10-04T22:23:12.877

Reputation: 9 048

3

Haskell, 51 * 2.5 = 127.5

a 0= -1;a x=x;f[]_= -1;f(h:t)n|h==n=0|1>0=a$1+f t n      

ungolfed:

adjust 0 = -1
adjust x =  x

find []     _ = -1
find (x:xs) n | x == n    = 0
              | otherwise = adjust $ 1 + find xs n    

John Dvorak

Posted 2014-10-04T22:23:12.877

Reputation: 9 048

2

Python 79.75 (319*0.5*0.5) 106.5 (213*0.5)

UPDATE: Since the time complexity is determined by worst case for any number of swaps, I have reduced my algorithm to work only for the case I=1, which results in O(log n) time.

The findX function is f, while g, and h are helpers.

The function uses the ordering of the odd indices to apply search to find where X should be. If X has been swapped then it uses a second binary to search to find where X has been swapped to, based on the value found at where X should have been. Since I use two binary searches in the worst case it is O(logN).

I find X by applying a binary search on the odd indices. If X is not found on the odd indices, I check the array at the even index where X should be if the array was ordered (call this value n1). If n1 equals X, I found the index. If n1 does not equal X I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n1). Call this new value n2. If n2 equals X, I found the index. Otherwise I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n2) ... etc.

The algorithm terminates when X is found or n1 is found a second time.

Essentially my algorithm traces the random swapping in reverse. That is, it will 'decode' the last swap, then 'decode' the second last swap, and so on until I decode the first swap. For each 'decode', I use a binary search ( O(logN) time ), plus an additional binary search to find the first index. The algorithm will 'decode' the simplest sequence of random swaps to get to the given state (e.g. the algorithm will not apply any decoding to an array that had the same swapping applied twice). Also, note that any sequence of swapping will be equivalent to a sequence of swapping of length less than or equal to N/2. Hence the complexity is at worst O(min(I, N/2) * logN) and the algorithm works for I swaps.

def f(l,X):
   m=len(l)
   i=g(l,X,0,m-m%2)
   return -1 if i>=m else i if l[i]==X else g(l,l[i],0,m-m%2)
def g(l,X,n,m):
   a=(n+m)//2
   a+=a%2-1
   return n if m<=n else g(l,X,a+1,m) if l[a]<X else g(l,X,n,a-1) if l[a]>X else a

def h(l,F,X,s,m): i=g(l,F,0,m-m%2) return -1 if i==s or i>=m else i if l[i]==X else h(l,l[i],X,s,m)

Ex:

print f([-1, 2, 3, 4, 5, 6, 70, 80, 90, 100],-1) print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1) print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100], 5) print f([-1, 2, 70, 4, 90, 6, 3, 80, 5, 100],-1)

Output:

0 4 0 0

Cameron

Posted 2014-10-04T22:23:12.877

Reputation: 997

"I will find the index of X after I iterations." -- Iiiii'm not sure about that. Can you elaborate on that part? Still, very nice. – John Dvorak – 2014-10-05T02:44:00.367

My bad, it will be at most I+1 iterations. I'll edit my post. – Cameron – 2014-10-05T02:52:17.737

Your algorithm fails for e.g. f([1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1],2), which is a transformed version of f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2],2). In fact, since an array consisting of an odd number of 1s followed by a 2 is guaranteed to contain no information in the odd indices, and the 2 may appear at any even index in the list, I've argued with @Optimizer above that sub-O(n) worst case performance is impossible. Otherwise, I had the same idea, hence props for a smooth implementation. ;) – COTO – 2014-10-05T03:13:41.647

@COTO that's an implementation issue - just plop an infinity at the end to handle the case of the element being looked up being at the end. – John Dvorak – 2014-10-05T03:15:20.470

@JanDvorak: The element being looked up isn't at the end. It's somewhere unknown in the middle of the list. That's the problem. – COTO – 2014-10-05T03:17:33.313

@Cameron an off-by-one issue isn't what I meant here - I'm not sure why it should succeed finding the target at all. – John Dvorak – 2014-10-05T03:17:33.030

@COTO I mean, the case of the element being looked up being the largest in the array. – John Dvorak – 2014-10-05T03:18:16.783

@COTO oh. Gotcha. Once you know you might be missing a 2, you still don't know where in the list it is. Forbidding duplicates would solve that. – John Dvorak – 2014-10-05T03:19:24.757

@JanDvorak: I know. But the input is the transformed list, where the largest element, so long as it's at an even position, may have been swapped with a random 1 somewhere in the list. Since all of the odd elements are 1, a binary search avails no information at all about its location. And yes, forbidding duplicates would solve it. :) – COTO – 2014-10-05T03:19:40.333

Still, it's a nice approach for when there are no duplicates in the input array, even if I believe it only works for a single round of swaps. – John Dvorak – 2014-10-05T03:21:10.457

1You're absolutely right about it only working for a single round of swaps. Two or more rounds of swaps allows all permutations of the even elements, meaning that (once again) the odd elements provide absolutely no information about the even elements in the worst case. Thus it is my contention that for I >= 2, it is impossible to beat O(n) worst case performance even with duplicates forbidden. – COTO – 2014-10-05T03:24:45.130

@COTO good catch. I didn't think of the the case of duplicate values, and yes that can only be done in O(N). – Cameron – 2014-10-05T03:25:02.867

@Cameron +1 for putting up with me. ;) – COTO – 2014-10-05T03:26:09.693

1@COTO are you sure two rounds of swaps are sufficient to generate every permutation? How do you generate larger cycles? Two rounds are definitely sufficient to randomise the lower half entirely (enough to force linear-time worst-case)by swapping all up, then all down, but then the permutation of the top half becomes entangled with the permutation of the bottom half (isomorphic cycle space, I believe). – John Dvorak – 2014-10-05T03:33:31.650

@COTO no problem, but I am sure it works for more than one swap. I've added more example tests – Cameron – 2014-10-05T03:34:09.953

I've also added, what I hope to be, a better description of why it works – Cameron – 2014-10-05T03:36:46.493

@JanDvorak: Good observation. I admit my group theory is a bit rusty. Regardless, it does seem as though it would be remarkably difficult to search over the reachable set of permutations in sub-O(n), even with I = 2. – COTO – 2014-10-05T06:54:56.383

@Cameron: After pondering it for a while, I see your point on I log(n) complexity for unique elements (not sure where that ranks on the point scale). The swaps must ultimately create a cycle containing the search value, if it's present. Your implementation has at least one bug, however. Consider f([1, 8, 3, 10, 5, 4, 7, 6, 9, 2], 10) which is obtained from passing [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] through swaps (6, 8), (4, 8), (2, 8), (2, 10). Your routine incorrectly returns -1 in this case. – COTO – 2014-10-05T07:35:48.277

@COTO actually, it is possible to perform an arbitrary permutation using only two rounds of swapping. For each cycle in the cycle space, reverse first the whole cycle (from an arbitrary point), then the cycle without one element. – John Dvorak – 2014-10-05T07:39:50.370

You should really remove your (provably impossible) claims about the behavior for I > 1 and alter the score appropriately. (cc @COTO - are you sure you want to upvote an answer with such impossible claims?) – John Dvorak – 2014-10-05T07:42:53.373

Your actual score is 319/2 = 159.5 - that is, the worst so far rather than the best so far. – John Dvorak – 2014-10-05T07:58:03.757

@COTO, in your example "which is obtained from passing [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] through swaps (6, 8), (4, 8), (2, 8), (2, 10)" - Are you taking those pairs in a single swap step ? If yes, you are violating the rule of mutually exclusive pairs, explained in the question – Optimizer – 2014-10-05T08:28:08.903

@Cameron - Why do you have a second 0.5 multiplier ? Can your algorithm solve for I > 1 swap steps ? If yes, I don't see a code where you read a third argument in your function f – Optimizer – 2014-10-05T08:29:20.080

@Optimizer: No, it's over I = 4 steps. Cameron's algorithm is intended to work for any I, hence it should work for the given sequence, which it doesn't. – COTO – 2014-10-05T09:17:43.410

@COTO [1, 8, 3, 10, 5, 4, 7, 6, 9, 2] is invalid input since you have swapped the odd indices, not the even indices – Cameron – 2014-10-05T17:44:03.750

@Optimizer I have one 0.5 multiplier since it works in O(log n) time for I=1 swaps and I have a second 0.5 multiplier since it works for I>1. I was unsure whether to use the complexity when I=1 or take the worst case for any I – Cameron – 2014-10-05T17:47:54.867

@Cameron Worst case for any I – Optimizer – 2014-10-05T17:50:55.657

@Optimizer Ok, I'll edit my score – Cameron – 2014-10-05T17:53:22.447

1

JavaScript ES6, 95 (38*5*0.5)

Performs an O(n) search. Accepts bonus parameter but ignores it

f=(a,x)=>a.reduce((p,c,i)=>c-x?p:i,-1)

George Reith

Posted 2014-10-04T22:23:12.877

Reputation: 2 424

Shouldn't f([1, 2, 3], 42) return -1? – Chiru – 2015-08-09T11:17:02.937

@Chiru Yeah missed that part working on it – George Reith – 2015-08-09T11:17:41.807

@Chiru Fixed unfortunately with more bytes – George Reith – 2015-08-09T12:41:27.840

+1 for both fixing it and still having the shortest ES6 solution as of now. Great job! – Chiru – 2015-08-09T13:02:08.473