CODEWITHSUNDEEP
pythonoptimization
beninato
beninato

Reputation: 418

Optimizing Python Function to Submit on Codewars

I have a solution for this problem on codewars.com that works when I run it in Sublime, but when I try to submit, I get this error:

Process was terminated. It took longer than 12000ms to complete

Why did my code time out?

Our servers are configured to only allow a certain amount of time for your code to execute. In rare cases the server may be taking on too much work and simply wasn't able to run your code efficiently enough. Most of the time though this issue is caused by inefficient algorithms. If you see this error multiple times you should try to optimize your code further.

The goal of the function is to find the next biggest number after a given number that you can make by rearranging the digits of a given number. For example, if I was given 216, I would need to return 261.

This is the code I have now:

import itertools

def next_bigger(n):

  # takes a number like 472 and puts it in a list like so: [4, 7, 2]
  num_arr = [int(x) for x in str(n)]
  perms = []
  total = ''

  # x would be a permutation of num_arr, like [7, 2, 4]
  for x in itertools.permutations(num_arr):
    for y in x:
      total += str(y)
    perms.append(int(total))
    total = ''

  # bigger is all permutations that are bigger than n, 
  # so bigger[0] is the next biggest number.
  # if there are no bigger permutations, the function returns -1

  bigger = sorted([x for x in perms if x > n])
  return bigger[0] if bigger else -1

I'm new to coding in Python, so is there some mistake I am making which causes my code to be extremely inefficient? Any suggestions are welcome.

Upvotes: 2

Views: 675

Answers (5)

Rohit-Pandey
Rohit-Pandey

Reputation: 2159

Now I edit to calculate next bigger element.

def perms(s):        
    if(len(s)==1): 
        return [s]
    result=[]
    for i,v in enumerate(s):
        result += [v+p for p in perms(s[:i]+s[i+1:])]
        return result

a=input()
b=perms(str(a))
if len(b)!=1:
    for i in range(0,len(b)):
        if b[i]==a:
            print (b[i+1])
            break
else:
    print ("-1")

Upvotes: 0

Mariusz
Mariusz

Reputation: 369

Why are you getting TLE (time limit exceeded)?

Because your algorithm has wrong complexity. How much permutations you will find for list with 3 elements? Only 6. But what if we use list with 23 elements? 25852016738884976640000. This is too much for time limit.

So, if you want to have solve this problem you have to find solution without permutations. Please rethink how the numbers are written. The number 271 is bigger then 216 because the number on the second position has bigger value 7>1.

So, your solution has to find two numbers and swap them position. The number on the left have to smaller then the second one.

For example - for 111115444474444 you should find 5 and 7.

Then you swap them - and now you should sort sublist on right from the first position.

For example after swapped the values (111117444454444) you have to sort (444454444) -> (444444445). Now merge all, and you have solution.

import functools

def next_bigger(a):
    a = map(int, str(a))
    tmp = list(reversed(a))
    for i, item_a in enumerate(reversed(a)):

        for j in (range(i)):
            if item_a < tmp[j]:
                #you find index of number to swap
                tmp[i]=tmp[j]
                print(list(reversed(tmp[i:])))
                tmp[j]=item_a
                fin = list(reversed(tmp[i:])) + sorted(tmp[:i])

                return functools.reduce(lambda x,y: x*10+y, fin)
    return -1

Upvotes: 1

beninato
beninato

Reputation: 418

Thanks for all the help you guys gave me. I ended up finding a solution from here using the Next Lexicographical Permutation Algorithm

This is my tidied up version of the solution provided here:

def next_bigger(n):
  # https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/nextperm.py
  # https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

  # Find non-increasing suffix
  arr = [int(x) for x in str(n)]
  i = len(arr) - 1
  while i > 0 and arr[i - 1] >= arr[i]:
    i -= 1
  if i <= 0:
    return -1

  # Find successor to pivot
  j = len(arr) - 1
  while arr[j] <= arr[i - 1]:
    j -= 1
  arr[i - 1], arr[j] = arr[j], arr[i - 1]

  # Reverse suffix
  arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
  return int(''.join(str(x) for x in arr))

Upvotes: 2

Umais Jan
Umais Jan

Reputation: 28

You should sorting the num_arr in desc order and creating a number by combining the result.

Since OP required, next largest, OP needs to check starting from right, which right digit is larger then its very left digit and rotate their position.

Here is the final code:

def next_bigger(n):
    num_arr = [int(x) for x in str(n)]
    i = 0
    i = len(num_arr) - 1
    while(i > 0):
        if num_arr[i] > num_arr[i-1]:
            a = num_arr[i]
            num_arr[i] = num_arr[i-1]
            num_arr[i-1] = a
            break
        else:
            i = i-1
    newbig = "".join(str(e) for e in num_arr)
    return int(newbig)

Upvotes: 0

Davis Herring
Davis Herring

Reputation: 40013

A simple backtracking approach is to consider the digits one at a time. Starting from the most significant digit, pick the smallest number you have left that doesn't prevent the new number from exceeding the input. This will always start by reproducing the input, then will have to backtrack to the next-to-last digit (because there aren't any other choices for the last digit). For inputs like 897654321, the backtracking will immediately cascade to the beginning because there are no larger digits left to try in any of the intermediate slots.

Upvotes: 0

Related Questions