I am doing some of these DS&A questions on various sites online for practice and I ran into this one:
Given an array of non-negative integers numbers, you are allowed to choose any number from this array and swap any two digits in it. If after the swap operation the number contains leading zeros, they can be omitted and not considered. Your task is to check whether it is possible to apply the swap operation at most once, so that the elements of the resulting array are strictly increasing.
For some reason this had me stumped at first so I went to the gym and thought about it for a while. Eventually I came back to it and tried again, this time coming up with a solution. Unfortunately the solution I got is sort of hideous and clunky and I get the feeling this is not a good way to solve this problem. It works with the tests I have tried but I really want to find a better solution for this. I feel like I must be missing some basic thing that improve it.
So I am posting my code here hoping for some feedback on it.
def solution(numbers):
swaps = 0
index = 0
for i in range(len(numbers)-1):
if numbers[i] >= numbers[i 1]:
swaps =1
index=i
if swaps > 1:
return False
elif not swaps:
return True
swappedI = swapToSmallest(numbers[index])
if (index-1 < 0 or numbers[index-1] < swappedI) and numbers[index 1] > swappedI:
return True
swappedIPlus1 = swapToSmallest(numbers[index])
if (index 1 > len(numbers) or numbers[index 1] < swappedIPlus1) and numbers[index-1] < swappedIPlus1:
return True
return False
def swapToSmallest(num) -> int:
num = str(num)
smallIndex = 0
smallestRight = num[smallIndex]
for i in range(1, len(num)):
if num[i] <= smallestRight:
smallestRight = num[i]
smallIndex = i
largeIndex = -1
largeLeft = num[largeIndex]
for i in range(len(num)-2, -1, -1):
if num[i] >= largeLeft:
largeLeft = num[i]
largeIndex = i
res = ""
for i, v in enumerate(num):
if i == largeIndex:
res =smallestRight
elif i == smallIndex:
res =largeLeft
else:
res =v
return int(res)
#tests
numbers = [1, 5, 10, 20]
print(solution(numbers))
numbers = [1, 3, 900, 10]
print(solution(numbers))
numbers = [1000, 10, 100]
print(solution(numbers))
numbers = [1, 2, 10, 7]
print(solution(numbers))
numbers = [1, 3, 3, 3]
print(solution(numbers))
numbers = [1000, 10, 9]
print(solution(numbers))
CodePudding user response：
There are definitely far less complicated solutions. For example, this is one I came up with (just taking a shot, I'm sure there's even more optimised solutions):
def flip(i):
return int(''.join(str(i)[::-1]))
def strict_inc(xs, single_flip_allowed=True):
for n, (a, b) in enumerate(zip(xs, xs[1:])):
if a >= b:
break
else:
return True
# here, n will be the index at which the first problem occurs
return single_flip_allowed and (
(
(n == 0 or xs[n-1] < flip(xs[n]))
and (n == len(xs) or flip(xs[n]) < xs[n 1])
and strict_inc(xs[n 1:], False)
)
or
(
(xs[n] < flip(xs[n 1]))
and (n 1 == len(xs) or flip(xs[n 1]) < xs[n 2])
and strict_inc(xs[n 2:], False)
)
)
(note that this implements your solution, with added flipping, but not the correct one, keep reading)
Although the function calls itself recursively, it never does so more than once, so there's no issues there.
It basically works on the premise that you can only have a single flaw in the original series of positive integers. So, it finds the first flaw, sees if it can be fixed by 'flipping' the first or second of integer in the flaw and it checks that the rest of the sequence in that case is still strictly increasing (without allow further flips).
You were asking for a review of your code, but given that it's clearly far from optimal, that would be quite an undertaking to do comprehensively.
If you do want a review, I'd suggest trying https://codereview.stackexchange.com/ since StackOverflow is really more suited to asking for solutions to concrete technical problems.
Turns out (thanks @barmar for pointing out my mistake, and to @kellybundy for pointing out OP's mistake) that a solution that does work isn't that complicated either (again with room for improvement):
def check(xs):
x = str(xs[1])
return any(xs[0] < int(f'{x[0:i]}{x[j]}{x[i 1:j]}{x[i]}{x[j 1:]}') < xs[2]
for i in range(len(x)) for j in range(i 1, len(x)))
def strict_inc(xs, single_flip_allowed=True):
for n, (a, b) in enumerate(zip(xs, xs[1:])):
if a >= b:
break
else:
return True
# here, n will be the index at which the first problem occurs
return single_flip_allowed and (
(
check(xs[n-1:n 2] if n > 0 else [-1] xs[n:n 2])
and strict_inc(xs[n 1:], False)
)
or
(
check(xs[n:n 3] if n < len(xs)-2 else xs[n:n 2] [int('9'*len(str(xs[n 1])))])
and strict_inc(xs[n 2:], False)
)
)
(another edit: this solution actually tries all possible pairings as needed)
CodePudding user response：
After reading some of the input here and making some modifications I came up with this solution. Pretty similar to my initial solution but I think it is handling the cases the other was not.
def solution(numbers):
flaw = False
for i in range(len(numbers)-1):
if numbers[i] >= numbers[i 1]:
if flaw:
return False
else:
flaw = True
flawIndex = i
if not flaw:
return True
a = swap(numbers[flawIndex])
b = swap(numbers[flawIndex 1]) if flawIndex < len(numbers)-1 else None
return (
(
True if (flawIndex != 0 or a > numbers[flawIndex]) and a < numbers[flawIndex 1] else False
) or (
True if b < numbers[flawIndex] and (flawIndex < len(numbers)-1 or b < numbers[flawIndex 1]) else False
)
)
def swap(num):
sn = str(num)
l, r = max(sn), min(sn)
largeIndex = sn.index(l)
smallIndex = sn.rindex(r)
res = ""
for i in range(len(sn)):
if i==smallIndex:
res =sn[largeIndex]
elif i==largeIndex:
res =sn[smallIndex]
else:
res =sn[i]
return int(res)