I have a porblem that I almost solved it but I'm facing problem with one test case, giving an array of numbers, it is allowed to choose any number and swap it digits so the array become strictly increasing, for example: [2, 4, 800, 12], we can choose 800 and convert it to 008 then array become [2,4,008,12], so it should return true, and it is allowed to it once, so the task is to check if it possible to convert an array to strictly increasing with at most one swap, here is my code
def solution(numbers):
swapped = 0
for i in range(len(numbers)-1):
if numbers[i] > numbers[i 1]:
if swapped >= 1:
return False
s1= int(''.join(sorted(str(numbers[i]))))
if s1 < numbers[i 1]:
if i > 0 and s1 >= numbers[i-1]:
numbers[i] = s1
swapped = 1
continue
s2 = int(''.join(sorted(str(numbers[i 1]), reverse=True)))
if s2 >= numbers[i]:
numbers[i 1] = s2
swapped = 1
continue
return True
the only test case the code doesn't pass is [13,31,30] (returning True instead of False) and I don't know how to solve this problem.
(apologies for any an un-elegant parts in my question, I'm new to this world and I'm trying my best)
CodePudding user response：
Your logic is largely right, except that I would put the check for the swap at the end of the loop, and I would check all the permutations instead of just the smallest and largest integer created from the digits.
from itertools import permutations, pairwise
def soln(numbers):
swapped = 0
for i in range(len(numbers)):
perms = list(int(''.join(shuffled_digits)) for shuffled_digits in permutations(str(numbers[i])))
if i == 0:
candidate_nums = [shuffled_number for shuffled_number in perms if shuffled_number < numbers[i 1]]
elif i < len(numbers) - 1:
candidate_nums = [shuffled_number for shuffled_number in perms if numbers[i-1] < shuffled_number < numbers[i 1]]
else:
candidate_nums = [shuffled_number for shuffled_number in perms if shuffled_number > numbers[i-1]]
if candidate_nums:
swapped_num = candidate_nums.pop()
numbers[i] = swapped_num
swapped =1
if all(x < y for x, y in pairwise(numbers)):
return True
return False
Output
In [80]: inlist
Out[80]: [2, 4, 8, 12]
In [81]: soln(inlist)
Out[81]: True
In [82]: inlist = [2, 4, 800, 12]
In [83]: soln(inlist)
Out[83]: True
In [84]: inlist = [21, 21]
In [85]: soln(inlist)
Out[85]: True
In [86]: inlist = [2, 1, 9, 7]
In [87]: soln(inlist)
Out[87]: False
In [88]: inlist = [2, 1, 1]
In [89]: soln(inlist)
Out[89]: False
In [90]: inlist = [100, 2, 3]
In [91]: soln(inlist)
Out[91]: True
In [92]: inlist = [52, 53, 36]
In [93]: soln(inlist)
Out[93]: True
In [94]: inlist = [44,37,74]
In [95]: soln(inlist)
Out[95]: True
CodePudding user response：
When you have a candidate number that needs to change, I would suggest making a directed search in the (virtual) list of permutations to find the permutation whose value is as close as possible to the value you compared with in order to restore the strictly ascending order.
It is not necessary to generate all permutations for this, which would consume too much time and space when the number of digits in the input numbers exceeds 10.
The idea is to count the number of digits you have of each digit, in the number that needs a permutation, and then take the next digit for building a permutation in such a way that you stay as close as possible to the target value. Some backtracking is needed, but for each digit position at most 2 attempts are needed: one for a digit that exactly matches the digit in the target (the value to compare with), and potentially a second attempt with another digit.
Here is an implementation of that idea.
First a helper function to find a permutation of a given value that is as near as possible to a target value (but not equal to it), and must be either less or greater (last argument controls this):
def permute_near(value, target, side=1):
# If side is 1, we will look for the minimum permutation of value that is
# greater than the target.
# If side is -1, we will look for the maximum permutation of value that is
# less than the target.
freedigit = 0 if side == 1 else 9
end = freedigit 10*side
target = side
# Get a count for each digit of value (could also use Counter module for this)
s = str(value)
n = len(s)
digits = [0]*10
for digit in s:
digits[int(digit)] = 1
# Pad the target value to have the same number of digits
limit = [int(digit) for digit in str(target).rjust(n, "0")]
# Use recursion to find the permutation of value that is nearest to the target
def recur(k, isfree, accumulator):
if k >= n: # All digits were processed, we have the result
return accumulator
limitdigit = limit[k]
for i in range(freedigit if isfree else limitdigit, end, side):
if digits[i]:
digits[i] -= 1 # Select this digit for the permutation
permutation = recur(k 1, isfree or i != limitdigit, accumulator * 10 i)
digits[i] = 1 # Backtrack
if permutation > -1 or i != limitdigit:
return permutation
# If it failed for the case where the chosen digit was the same
# as in the target, try with one alternative digit in a
# second and also last iteration of this loop.
return -1
return recur(0, False, 0)
Here is the main function:
def solution(numbers):
try:
# Find the first index where the next value is not greater
i = next(i for i, val in enumerate(numbers) if val >= numbers[i 1])
except:
return numbers # The input is already completely ascending
# Permute numbers[i], so it becomes less than its successor
result = permute_near(numbers[i], numbers[i 1], -1)
# Check that such permutation exists, and is still greater than its predecessor
if result >= 0 and (i == 0 or numbers[i - 1] < result):
numbers[i] = result # OK, we have success
else:
# ... or permute numbers[i 1], so it becomes greater than its predecessor
result = permute_near(numbers[i 1], numbers[i], 1)
# Check that such permutation exists, and is still less than its successor
if result >= 0 and (i 2 >= len(numbers) or result < numbers[i 2]):
numbers[i 1] = result # OK, we have success
if all(a < b for a, b in zip(numbers, numbers[1:])):
return numbers
Some runs:
# A few test cases
print(solution([2,4,800,12])) # [2, 4, 8, 12]
print(solution([44,37,74])) # [44, 73, 74]
print(solution([52,53,36])) # [52, 53, 63]
print(solution([64,52,53])) # [46, 52, 53]
print(solution([89221173000,89221173456,13437127829,89221173477]))
# [89221173000, 89221173456, 89221173473, 89221173477]
The function returns the adjusted list if there is a solution, None otherwise.
CodePudding user response：
The code mentioned in the question also fails for this testcase: [52,31,30]
Here's the solution that returns True if there's atleast one increasing array / list by swapping only one number.
def solution(numbers):
# Converts to str
numbers = [str(i) for i in numbers]
n = len(numbers)
for j in range(n 1):
if j != n:
# Reverse number
numbers[j] = str(numbers[j])[::-1]
# Checks if the array is in increasing order
if all([int(numbers[i 1]) > int(numbers[i]) for i in range(n - 1)]):
return True
if j != n:
numbers[j] = str(numbers[j])[::-1]
return False