Pushing the limits to make a piece of code solving the K-Goodness String problem shorter

Question

I am trying to push my limits of making a python code as short as possible.

I left the readability part way behind.

I was attempting the K-Goodness String problem from Round A of Google Kick Start 2021.

The following was my initial solution:

def func(N, K, S):
    if not S: return 0
    y = 0
    for i in range(N//2):
        if S[i] != S[N-i-1]:
            y += 1
    return abs(K - y)

for i in range(int(input())):
    N, K = tuple(map(int, input().split(' ')))
    S = input()
    y = func(N, K, S)
    print(f'Case #{i+1}: {y}')

Then I shortened it down to the following:

def func(N, K, S):
    if not S: return 0
    for i in range(N//2): K -= S[i] != S[N-i-1]
    return abs(K)
[print(f'Case #{_}: {func(*tuple(map(int, input().split())), input())}') for _ in range(1, int(input())+1)]

I seriously want to push the limits. Can anyone help me shorten the for loop part:

for i in range(N//2): K -= 1 if S[i] != S[N-i-1] else 0

so that I can make a lambda function out of func, like:

func = lambda N, K, S: 0 if not S else ... #something

P.S. I can do it the following way, but that is inefficient and involves redundant steps that increase time and space complexity:

func = lambda K, S: abs(K - list(map(lambda x: x[0] != x[1], list(zip(S, S[::-1])))).count(True)//2) if S else 0
[print(f'Case #{_}: {func(tuple(map(int, input().split()))[1], list(input()))}') for _ in range(1, int(input())+1)]

Please suggest a good way to do the same.

P.S. I know its not a good practice to compress a piece of code beyond readable, but I just wanted to do this for fun.

Sample Input

2
5 1
ABCAA
4 2
ABAA

Sample Output

Case #1: 0
Case #2: 1

Answer 1

151 bytes by @user

Here is the 151-byte solution presented in @user's answer. I recommend reading through their post for an explanation of how it works.

for t in range(int(input())):N,K=map(int,input().split());print(f'Case #{t+1}:',0if not(S:=input())else abs(K-sum(S[i]!=S[N-i-1]for i in range(N//2))))

From here, three tricks can be used to shorten it by a significant amount:

• The edge case of having an empty string \$ S \$ is simply unnecessary. According to the constraints in the linked problem, \$ N \$ is always at least 1.
• S[N-i-1] gets the ith element from the back, but the same can be achieved with S[~i], as mentioned here.
• input is used a total of three times. We can assign it to a variable with I=input, and reuse I.

130 bytes

Combining these reduces the solution by 21 bytes:

I=input
for t in range(int(I())):N,K=map(int,I().split());S=I();print(f'Case #{t+1}:',abs(K-sum(S[i]!=S[~i]for i in range(N//2))))

To go even further, we'll need a slight change in approach. In particular, sum(S[i]!=S[~i]for i in range(N//2)) can be improved with some clever use of pop: sum(c!=S.pop()for c in S). These are logically equivalent; for each character in S, we compare it to the last element with S.pop().

118 bytes

In total, we save 12 bytes this way. Note that we first need to convert S to a list via *S,=input(), since strings do not have a pop method.

I=input
for t in range(int(I())):K=int(I().split()[1]);*S,=I();print(f'Case #{t+1}:',abs(K-sum(c!=S.pop()for c in S)))

112 bytes

Finally, there is a 6-byte improvement by using open(0) instead of input(), a shortcut that essentially stores the list of lines from STDIN.

_,*a=open(t:=0)
while a:K,(*S,_),*a=a;t+=1;print(f'Case #{t}:',abs(int(K.split()[1])-sum(c!=S.pop()for c in S)))

There is a lot to unpack here (no pun intended), so I will note some of the potentially confusing parts of the code.

_,*a=open(0) reads all input, and stores it as a list of lines. We unpack it by storing the first line in _, and the rest in a. _ contains the number of test cases, but it is not needed for the rest of the program.

while a:K,(*S,_),*a=a removes the first two elements from a, and stores them in K and S. If we take another look at the sample input, what this is really doing is storing 5 1 in K, and ABCAA in S (as in the 1st test case).

The weird-looking (*S,_) is due to the fact that open(0) includes the \n at the end of each line, meaning that S actually equals 'ABCAA\n' instead of 'ABCAA'. The "nested unpacking" solves this by isolating the \n in _.

The while loop terminates when a is empty, or equivalently when there is no more input left.

Answer 2

Here's a 176-byter after some trivial changes (based off of pxeger's comment):

def f(N,K,S):
 if not S:return 0
 for i in range(N//2):K-=S[i]!=S[N-i-1]
 return abs(K)
for _ in range(int(input())):print(f'Case #{_+1}:',f(*map(int,input().split()),input()))

Attempt This Online!

• You don't need to name your function func
• You can use a normal loop instead of a comprehension
• You can make a range starting at 0 and just add 1 to the case number when printing
• You don't need tuple (or even the shorter list) because * takes care of it
• You can make the result of f a separate argument to print to get rid of the braces

You're only calling the function once, so we can put that directly into the loop. To get around not being able to return from a function, we can try to turn the whole function into a single if expression. If S is empty, then it's just 0, but if it's not, we need to turn the for loop to decrement K into a single expression. The amount you're decrementing is sum(S[i]!=S[N-i-1]for i in range(N//2)), so the else part of the if expression is just abs(K-<that sum>).

Once you do that, use semicolons instead of newlines, and use the walrus for assigning S, you get 151 bytes. (I renamed _ c for readability)

for c in range(int(input())):N,K=map(int,input().split());print(f'Case #{c+1}:',0if not(S:=input())else abs(K-sum(S[i]!=S[N-i-1]for i in range(N//2))))

Attempt This Online!

Someone who knows Python and understands your algorithm can probably do much more, but these are some simple changes you can make. Edit: Yup, dingledooper golfed it to 112 bytes!