3
1
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
Justin Case
Posted 2018-12-06T09:22:38.557
Reputation: 39
1
m£Z¯Y cZtY2 Ô cZsY+2Ãrc
®¬ø"VK"
W+VÌ
Ve ?ß:W
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.
Kamil Drakari
Posted 2018-12-06T09:22:38.557
Reputation: 3 461
0
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)
Basic BFS.
HyperNeutrino
Posted 2018-12-06T09:22:38.557
Reputation: 26 575
2
I've formatted your post a bit. As mentioned by @JoKing above, is the
– Kevin Cruijssen – 2018-12-06T09:50:22.577"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.The "VK" is hard coded. – Justin Case – 2018-12-06T09:54:24.830
3Lowercase
vkor uppercase? Also, I'd recommend rewriting the title to something less "I need help with my homework" sounding – Jo King – 2018-12-06T10:55:36.283I would appreciate some more test cases =D – Luis felipe De jesus Munoz – 2018-12-06T19:04:32.803
bvvkcvdoes not contain any instances ofVK. Perhaps a test case likeVKVKVKVK? – Jo King – 2018-12-09T08:39:00.7201Suggested test case:
KV => 0– Kamil Drakari – 2018-12-10T17:38:45.580This question seems really unclear... so I'm making character swaps to position Vs in front of Ks, so they can be removed as an ordered pair? Will I always have an equal number, or might I end up with extra Vs or Ks? Must I make all the swaps before removing anything? Or can I remove each
VKas it appears, which reduces the number of letters in the way for remaining swaps? – BradC – 2018-12-11T15:29:01.870@KamilDrakari Shouldn't that be 1? – BradC – 2018-12-11T16:03:09.413
@BradC My reading of the challenge is that the original string is only reordered using swaps until "VK" is not a substring of it. Characters are never removed. "VK" is not a substring of "KV" so no swaps are necessary. – Kamil Drakari – 2018-12-11T16:17:22.077
@KamilDrakari Ohhh, that kind of makes sense? Still very unclearly worded. – BradC – 2018-12-11T16:27:25.457
Substring or subsequence? Should 'VXK' return 0 or 2? – user202729 – 2018-12-13T07:10:53.397
@user202729 it should return 0 – Justin Case – 2018-12-14T08:30:39.377