5
\$\begingroup\$

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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Could you provide some example input? That way we could test this ourselves. And a description of what the function func is supposed to do would be helpful, as not every is familiar with that specific problem. \$\endgroup\$
    – ovs
    Nov 13 at 14:51
  • 3
    \$\begingroup\$ @Fmbalbuena That is untrue. tips questions are on-topic here. This meta post details these types of questions. \$\endgroup\$
    – hyper-neutrino
    Nov 13 at 14:57
  • 2
    \$\begingroup\$ Could you add a summary of the challenge you're solving into your question? I put a link in, but questions should be self-contained. (also, let me know if the link I put in isn't right) \$\endgroup\$
    – rues
    Nov 13 at 15:16
  • 2
    \$\begingroup\$ First of all, you can remove almost all of the spaces in your code: ato.pxeger.com/… \$\endgroup\$
    – pxeger
    Nov 13 at 15:31
  • 1
    \$\begingroup\$ @user Thanks a lot for adding the link (yes it is correct). Also, I will keep that in mind for future questions. \$\endgroup\$ Nov 13 at 18:36
10
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ In the final (112 bytes) approach, The program is taking continuous inputs and I can not do anything (except causing KeyboardInterrupt by ctrl+C) to stop it. Also, due to some reason, I can't see the results of the print statements in the terminal. I am sorry, if I am asking something very obvious and silly, This is my first attempt in golfing. \$\endgroup\$ Nov 14 at 9:00
  • \$\begingroup\$ @IshaanKapoor The issue is likely because of the open(0). The program won't continue until all input is read. After pasting the input, try hitting Ctrl+Z then Enter to simulate an EOF. \$\endgroup\$ Nov 15 at 23:43
4
\$\begingroup\$

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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can save a bit by making the return conditional. \$\endgroup\$
    – emanresu A
    Nov 13 at 20:44
  • \$\begingroup\$ @emanresuA Smart golf! Do you want to make your own answer? \$\endgroup\$
    – rues
    Nov 13 at 20:59
  • 1
    \$\begingroup\$ Nah :P. Btw you can save a bit more if you take K as an array - K=eval(input()) or something. \$\endgroup\$
    – emanresu A
    Nov 13 at 21:08
  • \$\begingroup\$ @emanresuA Wait, I don't think that'll work because you can't index into an empty S :( \$\endgroup\$
    – rues
    Nov 13 at 21:20
  • \$\begingroup\$ Oops :P (filler) \$\endgroup\$
    – emanresu A
    Nov 13 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.