CODEWITHSUNDEEP
pythonarrays
SG Kwon
SG Kwon

Reputation: 125

Failing hidden tests in codesignal. What seems to be the problem in my code?

https://app.codesignal.com/arcade/intro/level-7/PTWhv2oWqd6p4AHB9

Here, the problem is that "Given an array of equal-length strings, you'd like to know if it's possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it's possible, and false if not."

and my code is

import itertools

def only_one_element_different(x, y):
    list1 = []
    for i in x:
        list1.append(i)
    list2 = []
    for j in y:
        list2.append(j)
    list3 = []
    for k in range(0, len(list1)):
        if list1[k] == list2[k]:
            list3.append(True)
        else:
            list3.append(False)
    if list3.count(False) == 1:
        return True
    else:
        return False


def if_list_is_linear(list):
    list4 = []
    for m in range(0, len(list)-1):
        if only_one_element_different(list[m], list[m+1]):
            list4.append(True)
        else:
            list4.append(False)
    if False in list4:
        return False
    else:
        return True

list5 = ['aba', 'bbb','bab','bba']

list6 = list(itertools.permutations(list5))

list7 = []

for n in list6:
    if if_list_is_linear(n) == True:
        list7.append(True)
    else:
        list7.append(False)

if True in list7:
    print("Real True")
else:
    print("False")
​

(In list5, The array is given)

this passed all the tests but failed several hidden tests.

I don't know if it is because of the timeout or flaws in my code. Please help

(sorry for the bad english)

Upvotes: 0

Views: 6540

Answers (2)

LPR
LPR

Reputation: 390

I am also working on CodeSignal's practice problems using python. Sometimes, but not always, if a print statement is included in the submitted solution - even if the line is never read - this can cause a hidden test to fail.

After removing or commenting out print statements double check for edge cases that you may have overlooked and were not tested in the visible tests. (i.e. 'abc','abc' is a discontinuity while 'abc','aba' is okay because exactly one letter changed)

For your reference, I outlined and annotated my solution below.

First: Make a dictionary that keeps a list of all strings that are only one letter different. i.e. for [ 'aba' , 'bbb' , 'bab' , 'bba' ]

dictionary={ 'aba' : ['bba'] , 'bbb' : ['bab','bba'] , ... }

string_dict={}

#iterate through strings comparing each key string to all other strings
for idx in range(len(inputArray)):
    key=inputArray[idx]
    string_dict[key]=[]
    for string in np.concatenate([inputArray[:idx],inputArray[idx+1:]]):

        #check to see if key is within one letter of the string
        count=np.sum([k!=s for (k,s) in zip(key,string)])

        #do not add value to key if value==key or 2 or more letters are different
        if count>1 or count==0:
            continue
        else:
            #Add string to dictionary as a value if it is within 1 letter from the key
            string_dict[key]+=[string]

From now on you do not need to compute whether string1 is within 1 letter change from string2 since it is stored in your dictionary

Second: check all permutations of inputArray to see if any are a solution

Given that there will be 10 strings or less in the given inputArray it is not too expensive to check all possible permutations

    arr_len=len(inputArray)
    for permutation in list(permutations(range(arr_len))):

        #order inputArray values according to each permutation
        arr=inputArray[np.array(permutation)]

        #Count how many adjacent strings are more than 1 letter different
        discontinuities=np.sum([arr[idx+1] not in string_dict[arr[idx]] for idx in range(arr_len-1)])

        if discontinuities==0:
            #Made it to the end of the permutation and found no discontinuities. A solution exists!
            return True

    #Went through all permutations and all of them had at least one discontinuity.  No solution exists.
    return False

Upvotes: 0

bruno desthuilliers
bruno desthuilliers

Reputation: 77912

As I don't know what the "hidden tests" are and am not willing to create an account on this site, read the specs (which are probably incomplete and ambiguous as usual) and take the whole test, I'll only address the perfs issues.

Your first function is about as inefficient as possible:

def only_one_element_different(x, y):
    list1 = []
    for i in x:
        list1.append(i)

This can be rewritten as list1 = list(x), which is faster - but it's not even needed: strings are sequences, and sequences are iterables, so you can just use the strings directly.

    list2 = []
    for j in y:
        list2.append(j)

idem

    list3 = []
    for k in range(0, len(list1)):
        if list1[k] == list2[k]:
            list3.append(True)
        else:
            list3.append(False)

First simplification: use zip() to iterate on both strings at once:

>>> print(list(zip("aba", "bbb")))
[('a', 'b'), ('b', 'b'), ('a', 'b')]

which would give:

     for c1, c2 in zip(x, y):
        if c1 == c2:
            list3.append(True)
        else:
            list3.append(False)

Now c1 == c2 is an expression, which means it's evaluates to an object (a boolean in this case), so you can simplify this as

     for c1, c2 in zip(x, y):
        list3.append(c1 == c2)

Now this is a rather inefficient way to build a list - first because of the method calls overhead, and also because growing the list might lead to memory allocation, which is costly. A much faster solution is a "list comprehesion":

    list3 = [c1 == c2 for c1, c2 in zip(x, y)]

and while we're at it, this:

    if list3.count(False) == 1:
        return True
    else:
        return False

is a convoluted way to write

 return list3.count(False) == 1

IOW you can rewrite the whole thing as 

return [c1 == c2 for c1, c2 in zip(x, y)].count(False) == 1

Now if the x and y strings were long, this would still be inefficient - you are inspecting the whole string when you could detect "non-matching" string way sooner:

def only_one_diff(x, y):
    diff = False
    for c1, c2 in zip(x, y):            
        if c1 != c2:
            if diff:
                # we already found another diff in a previous iteration,  
                # so there's more than one diff, so we are done
                return False
            # else it was the first diff, let's flag it:
            diff = True

   # if we didn't return from within the for loop, 
   # we have either one single diff or no diff at all:
   return diff

Which of those two implementations will actually be faster depends on the strings length. For long strings, this second implemention should be faster, for 3 letters strings it's not garanteed, you'd have to benchmark both using the timeit module. In both cases, the second implementation will eat less memory...

The rest of your code suffers from similar issues:

def if_list_is_linear(list):
    list4 = []
    for m in range(0, len(list)-1):
        if only_one_element_different(list[m], list[m+1]):
            list4.append(True)
        else:
            list4.append(False)
    if False in list4:
        return False
    else:
        return True

here again, you'd save some time by returning as soon as you know one of the strings doesn't pass the only_one_diff predicate:

# NB : don't use `list` as a var name, it shadows the builtin `list` type
def if_list_is_linear(lst):
    for x, y in zip(lst, lst[1:]):
        if not only_one_diff(x, y):
            # no need to test further
            return False
    # ok, we're good  
    return True

I think you get the point by now....

Upvotes: 4

Related Questions