Can anyone help me ?
I need to implement a routine that tests an array if it's possible to move a position field please see the figure
the rules are:
- the type F field can be in any position
- the field of type X cannot be between the Start and End field
- and between Start and End, cannot include another start-end
I would like you to give me ideas on how to implement this algorithm. if example code is needed, it can be in any language...
tanks!
CodePudding user response：
The idea is simple. I would create a range array of indices to encode the (Start,End) positions. I assume that input is a valid formation that follows position related rules.
InputArray: [X1, F1, Start, F2, F3, End, F6, X2, Start, F4, End]
Encoding: [(2,5), (8,10)]
Now you can query the above encoding if the move should be allowed or not.
function query(currentPosition, targetPosition, Encoding):
type = type of InputArray[currentPosition]
if type == F:
return True if targetPosition in bounds of InputArray
if type == X:
return True if binary search of the targetPosition doesn't overlap with any range in Encoding
#e.g. if targetPosition is 3 for above Encoding, then it overlaps with range (2,5).
if type == Start:
index = Binary search for currentPosition in Encoding
return targetPosition <= currentPosition and (index == 0 or targetPosition > Encoding[index-1].second)
#e.g. if query(8, 6, Encoding) returns True
# index => 1
# Encoding[index-1].second => 5
if type == End:
index = Binary search for currentPosition in Encoding
return targetPosition >= currentPosition and (index == len(Encoding)-1 or targetPosition < Encoding[index 1].first)
#e.g. if query(5, 6, Encoding) returns True
# index => 0
# Encoding[index 1].first => 8
return False
Time Complexity per query: O(log(n)). So, I think this is the most efficient solution.
CodePudding user response：
Here are two proposed algorithms, implemented in python. I bent the rules by assuming you were swapping two elements, rather than moving one element. This is because swapping elements is easy in python, but inserting and deleting an element (effectively shifting a whole portion of the array) is really annoying.
# DUMMY FUNCTIONS TO CHECK TYPE, REPLACE WITH YOUR OWN
def is_x(e):
return e.startswith('x')
def is_f(e):
return e.startswith('f')
def is_start(e):
return e.startswith('s')
def is_end(e):
return e.startswith('e')
# CHECK THE ARRAY RESPECTS RULES 2,3: NO TWO CONSECUTIVE STARTS OR ENDS
# NO X IN BETWEEN START-END
def is_valid_array(a):
state = 'end'
for e in a:
if ((is_start(state) and (is_start(e) or is_x(e))) or
(is_end(state) and is_end(e))):
return False
elif is_start(e):
state = 'start'
elif is_end(e):
state = 'end'
return is_end(state)
# FIRST ALGORITHM
# straightforward, easy to debug
# time complexity always proportional to array size
def is_valid_move_firstalgorithm(a, i, j):
a[i], a[j] = a[j], a[i] # perform move
is_valid = is_valid_array(a) # check whole array
a[j], a[i] = a[i], a[j] # undo move
return is_valid
# check if position i is inbetween start-end
def follows_start(a, i):
for k in range(i-1, -1, -1):
if is_start(a[k]):
return True
elif is_end(a[k]):
return False
return False
# SECOND ALGORITHM
# messy, could easily have forgotten an edge case
# time complexity sometimes much smaller than array size
# worst-case time complexity proportional to array size
def is_valid_move_secondalgorithm(a, i, j):
i, j = min(i, j), max(i, j) # reorder i,j if j<i
for is_type in (is_x, is_f, is_start, is_end):
if is_type(a[i]) and is_type(a[j]):
return True
if is_x(a[i]) and not is_x(a[j]) and (is_start(a[j]) or follows_start(a, j) or follows_start(a, i)):
return False
elif is_x(a[j]) and not is_x(a[i]) and (is_end(a[i]) or follows_start(a, j) or follows_start(a, i)):
return False
elif is_start(a[i]) and is_end(a[j]) or is_end(a[i]) and is_start(a[j]):
return False
for k in (i, j):
if is_start(a[k]) and any(is_end(e) or is_x(e) for e in a[i 1:j]):
return False
elif is_end(a[k]) and any(is_start(e) or is_x(e) for e in a[i 1:j]):
return False
return True
Testing:
from itertools import combinations
arr = ['x1', 'f1', 's', 'f2', 'f3', 'e', 'f6', 'x2', 's', 'f4', 'e']
for i, j in combinations(range(len(arr)), 2):
b1 = is_valid_move_firstalgorithm(arr, i, j)
b2 = is_valid_move_secondalgorithm(arr, i, j)
if b1 == b2:
print('# {:2} {:2d} {:5s}'.format(i, j, str(b1)))
else:
print('# {:2} {:2d} {:5s} {:5s} DISAGREE'.format(i, j, str(b1), str(b2)))
# 0 1 True
# 0 2 False
# 0 3 False
# 0 4 False
# 0 5 False
# 0 6 True
# 0 7 True
# 0 8 False
# 0 9 False
# 0 10 False
# 1 2 True
# 1 3 True
# 1 4 True
# 1 5 False
# 1 6 True
# 1 7 True
# 1 8 False
# 1 9 True
# 1 10 False
# 2 3 True
# 2 4 True
# 2 5 False
# 2 6 False
# 2 7 False
# 2 8 True
# 2 9 False
# 2 10 False
# 3 4 True
# 3 5 True
# 3 6 True
# 3 7 False
# 3 8 False
# 3 9 True
# 3 10 False
# 4 5 True
# 4 6 True
# 4 7 False
# 4 8 False
# 4 9 True
# 4 10 False
# 5 6 True
# 5 7 False
# 5 8 False
# 5 9 False
# 5 10 True
# 6 7 True
# 6 8 False
# 6 9 True
# 6 10 False
# 7 8 False
# 7 9 False
# 7 10 False
# 8 9 True
# 8 10 False
# 9 10 True