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:

Output: 8

Output: 3

Input:  JUSTIN
Output: 0
  • 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\$ – Kevin Cruijssen Dec 6 '18 at 9:50
  • \$\begingroup\$ The "VK" is hard coded. \$\endgroup\$ – Justin Case Dec 6 '18 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 '18 at 10:55
  • \$\begingroup\$ I would appreciate some more test cases =D \$\endgroup\$ – Luis felipe De jesus Munoz Dec 6 '18 at 19:04
  • 1
    \$\begingroup\$ Suggested test case: KV => 0 \$\endgroup\$ – Kamil Drakari Dec 10 '18 at 17:38

Japt, 44 bytes

m£Z¯Y cZtY2 Ô cZsY+2Ãrc
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.


#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.
| improve this answer | |
  • 1
    \$\begingroup\$ A couple of quick savings to get you down to 44 bytes. \$\endgroup\$ – Shaggy Dec 11 '18 at 9:41

Python 3, 125 bytes

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)}

Try it online!

Basic BFS.

| improve this answer | |

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.