3
\$\begingroup\$

For example, how many adjacent swaps are at least needed to convert some string such as BVVKCV to one without any instances of VK?

Input-length of the string will be within the range 1 <= length <= 200.
VK will be hardcoded across all test cases.

Input string examples:

Input:  VKVKVVVKVOVKVQKKKVVK
Output: 8

Input:  VVKEVKK
Output: 3

Input:  JUSTIN
Output: 0
\$\endgroup\$
12
  • 2
    \$\begingroup\$ I've formatted your post a bit. As mentioned by @JoKing above, is the "vk" hard-coded, or given as second input? Also, you will need a winning criteria tag. [code-golf] is the most common one to use. \$\endgroup\$ Dec 6, 2018 at 9:50
  • \$\begingroup\$ The "VK" is hard coded. \$\endgroup\$ Dec 6, 2018 at 9:54
  • 3
    \$\begingroup\$ Lowercase vk or uppercase? Also, I'd recommend rewriting the title to something less "I need help with my homework" sounding \$\endgroup\$
    – Jo King
    Dec 6, 2018 at 10:55
  • \$\begingroup\$ I would appreciate some more test cases =D \$\endgroup\$ Dec 6, 2018 at 19:04
  • 1
    \$\begingroup\$ Suggested test case: KV => 0 \$\endgroup\$ Dec 10, 2018 at 17:38

2 Answers 2

1
\$\begingroup\$

Japt, 44 bytes

m£Z¯Y cZtY2 Ô cZsY+2Ãrc
®¬ø"VK"
W+VÌ
Ve ?ß:W

Try it online!

It times out on the first test case because it's super inefficient (something like O(n^n)?) but it should be a viable algorithm. Input is weird; it is a singleton list containing the input, but the input itself is formatted as a list of upper-case characters. I think that would typically be valid, but if not let me know.

Explanation:

#Step 1: try all the swaps
m                          #For each string Z reachable with n swaps (n starts at 0)
 £                  Ã      # For each letter Y in Z:
  Z¯Y                      #  Get the letters before it in Z
      c                    #  Concat
       ZtY2 Ô              #  Y swapped with the following character
              c            #  Concat
               ZsY+2       #  The rest of Z
                     rc    #Flatten by one level
                           #Result: A list of all strings reachable with n+1 swaps

#Step 2: Check for "VK"
®¬         #For each string from Step 1:
  ø"VK"    # Check whether it contains "VK"
           #Result: A list where 1 indicates there was "VK" and 0 otherwise

#Step 3: Increment the counter appropriately
W+      #Increase the counter by
  VÌ    #The value for the original string when run through step 2
        #Result: 0 if 0 swaps were required, the current number of swaps otherwise

#Step 4: Iterate or end
Ve ?       #If all the reachable strings contain "VK"
    ß      # Repeat the program with the current values
     :W    #Otherwise return the counter
           #Result: Outputs the counter when a non-"VK" string is found.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ A couple of quick savings to get you down to 44 bytes. \$\endgroup\$
    – Shaggy
    Dec 11, 2018 at 9:41
0
\$\begingroup\$

Python 3, 125 bytes

s={input()}
a=0
while all("VK"in q for q in s):a+=1;s={a[:i]+a[i+1]+a[i]+a[i+2:]for a in s for i in range(len(a)-1)}
print(a)

Try it online!

Basic BFS.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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