fork(1) download
copy 
  1. def is_valid(s):
  2.   if not s:
  3.     return True
  4.   char = "x"
  5.   count = 0
  6.   for c in s:
  7.     if c != char:
  8.       char, count = c, 1
  9.     else:
  10.       count += 1
  11.       if count == 3:
  12.         return False
  13.   return True
  14.  
  15.  
  16. # https://stackoverflow.com/a/69322213/2034787
  17. # Code by MTO
  18. def solve(_str):
  19.   opposite = {"a": "b", "b": "a"}
  20.   curr_idx = 0
  21.   output = []
  22.  
  23.   lookahead  = lambda x: None if ((curr_idx + x < 0) or (curr_idx + x >= len(_str))) else _str[curr_idx + x]
  24.   lookbehind = lambda x: None if curr_idx-x< 0 else output[curr_idx - x]
  25.   matches = lambda x, y: x == y or x == None or y == None
  26.   is_replacement = lambda x: x == '?'
  27.  
  28.   while curr_idx < len(_str):
  29.     curr = lookbehind(1) or 'b'
  30.     i = 0
  31.     next = lookahead(i)
  32.     while is_replacement(next):
  33.       i += 1
  34.       next = lookahead(i)
  35.  
  36.     if next == None:
  37.       # Found the end of the string.
  38.       # Append characters opposite to the previous for each ?
  39.       for _ in range(i, 0, -1):
  40.         curr = opposite[curr]
  41.         output.append( curr )
  42.       break
  43.  
  44.     if (i > 1):
  45.       # Found multiple successive ?s
  46.       # Handle the first half of the ?s by
  47.       # Append alternating characters from the previous character.
  48.       j = 0
  49.       while j < i / 2:
  50.         curr = opposite[curr]
  51.         output.append( curr )
  52.         j += 1
  53.       # Then handle the second half of the ?s
  54.       # append alternating characters to the next character after the ?s.
  55.       while j < i:
  56.         output.append( next if (j%2) == (i%2) else opposite[next] )
  57.         j += 1
  58.  
  59.     elif i == 1:
  60.       # Found a single ?
  61.       prev = lookbehind(2)
  62.       if curr == prev and curr == opposite[next] and next == lookahead(2):
  63.         # No solution.
  64.         return None
  65.  
  66.       if curr == prev or matches(curr, next):
  67.         output.append( opposite[curr] )
  68.       else:
  69.         output.append( curr )
  70.  
  71.     if next != None:
  72.       # Output the next non-? character.
  73.       output.append( next )
  74.  
  75.     curr_idx += i + 1
  76.  
  77.   return ''.join(output)
  78.  
  79.  
  80. # My greedy solution
  81. def f(s):
  82.   if len(s) == 2:
  83.     return s.replace('?', 'a')
  84.  
  85.   aa = ['a', 'a']
  86.   bb = ['b', 'b']
  87.  
  88.   out = []
  89.   i = 0
  90.   a, b = 0, 0
  91.  
  92.   while i < len(s):
  93.     if s[i] == 'a' or (s[i] == '?' and b == 2):
  94.       if s[i] == 'a' and a == 2:
  95.         if s[i-3:i-1] == "??":
  96.           out[i-3], out[i-2] = out[i-2], out[i-3]
  97.           a -= 1
  98.         else:
  99.           return ""
  100.       out.append('a')
  101.       a, b = a + 1, 0
  102.       i += 1
  103.     elif s[i] == 'b' or (s[i] == '?' and a == 2):
  104.       if s[i] == 'b' and b == 2:
  105.         if s[i-3:i-1] == "??":
  106.           out[i-3], out[i-2] = out[i-2], out[i-3]
  107.           b -= 1
  108.         else:
  109.           return ""
  110.       out.append('b')
  111.       a, b = 0, b + 1
  112.       i += 1
  113.     elif i == len(s) - 1:
  114.       out.append('a' if b else 'b')
  115.       i += 1
  116.     elif i == len(s) - 2:
  117.       if s[i+1] == '?':
  118.         out.extend(aa if b else bb)
  119.       else:
  120.         out.append('a' if b else 'b')
  121.         out.append(s[i+1])
  122.       i += 2
  123.     elif s[i+1] == '?':
  124.       if a:
  125.         out.append('a')
  126.         a, b = a + 1, 0
  127.       else:
  128.         out.append('b')
  129.         a, b = 0, b + 1
  130.       i += 1
  131.     elif s[i+1] == 'a':
  132.       if a or b < 2:
  133.         out.append('b')
  134.         a, b = 0, b + 1
  135.       else:
  136.         out.append('a')
  137.         a, b = a + 1, 0
  138.       i += 1
  139.     elif s[i+1] == 'b':
  140.       if b or a < 2:
  141.         out.append('a')
  142.         a, b = a + 1, 0
  143.       else:
  144.         out.append('b')
  145.         a, b = 0, b + 1
  146.       i += 1
  147.  
  148.   return ''.join(out)
  149.  
  150.  
  151. strs = [
  152.   "a?bb", # "aabb"
  153.   "??abb", # "ababb" or "bbabb" or "baabb"
  154.   "a?b?aa", # "aabbaa"
  155.   "?bb?",
  156.   "aa?bb", # NO SOLUTION
  157.   "aa??aa", # "aabbaa"
  158.   "ab???bb?",
  159.   "????",
  160.   "??",
  161.   "?????",
  162.   "??????",
  163.   "?",
  164.   "a?",
  165.   "a??",
  166.   "a???",
  167.   "b?",
  168.   "b??",
  169.   "b???",
  170.   "a?a",
  171.   "a?b",
  172.   "b?a",
  173.   "b?b",
  174.   "a??a",
  175.   "a??b",
  176.   "b??a",
  177.   "b??b",
  178.   "aa?",
  179.   "ba?",
  180.   "a?bb",
  181.   "?bb?",
  182.   "??abb",
  183.   "a?b?aa",
  184.   "ab???bb?",
  185.   "aa?bb"
  186. ]
  187.  
  188.  
  189. for s in strs:
  190.   _solve = solve(s)
  191.   _f = f(s)
  192.   print("%s\n%s, %s, %s, %s\n" % (s, is_valid(_f), is_valid(_solve), _solve, _f))
  193.  
  194.  
  195. import random
  196.  
  197. def get_random(n):
  198.   char = 'x'
  199.   count = 0
  200.   out = []
  201.   not_c = lambda c: 'a' if c == 'b' else 'b'
  202.  
  203.   for _ in range(n):
  204.     c = ['a', 'b'][int(random.random() * 2)]
  205.     if c != char:
  206.       out.append(c)
  207.       char, count = c, 1
  208.     elif count == 2:
  209.       out.append(not_c(c))
  210.       char, count = not_c(c), 1
  211.     else:
  212.       out.append(c)
  213.       count += 1
  214.  
  215.   for i in range(n):
  216.      if int(random.random() * 2):
  217.       out[i] = '?'
  218.  
  219.   return ''.join(out)
  220.  
  221. num_tests = 1000
  222. n = 20
  223.  
  224. print("Starting random tests...")
  225.  
  226. for _ in range(num_tests):
  227.   s = get_random(n)
  228.   _solve = solve(s)
  229.   _f = f(s)
  230.   valid_solve = is_valid(_solve)
  231.   valid_f = is_valid(_f)
  232.   if not valid_f or not valid_solve:
  233.     print(s, valid_f, valid_solve, _f, _solve)
  234.     break
  235.  
  236. print("Done testing")
Success #stdin #stdout 0.17s 68712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a?bb
True, True, aabb, aabb

??abb
True, True, ababb, bbabb

a?b?aa
True, True, aabbaa, aabbaa

?bb?
True, True, abba, abba

aa?bb
True, True, None, 

aa??aa
True, True, aabbaa, aabbaa

ab???bb?
True, True, abababba, abbaabba

????
True, True, abab, bbab

??
True, True, ab, aa

?????
True, True, ababa, bbabb

??????
True, True, ababab, bbaaba

?
True, True, a, b

a?
True, True, ab, aa

a??
True, True, aba, abb

a???
True, True, abab, aaba

b?
True, True, ba, ba

b??
True, True, bab, baa

b???
True, True, baba, bbab

a?a
True, True, aba, aba

a?b
True, True, aab, abb

b?a
True, True, bba, baa

b?b
True, True, bab, bab

a??a
True, True, abba, aaba

a??b
True, True, abab, aabb

b??a
True, True, baba, bbaa

b??b
True, True, baab, bbab

aa?
True, True, aab, aab

ba?
True, True, bab, bab

a?bb
True, True, aabb, aabb

?bb?
True, True, abba, abba

??abb
True, True, ababb, bbabb

a?b?aa
True, True, aabbaa, aabbaa

ab???bb?
True, True, abababba, abbaabba

aa?bb
True, True, None, 

Starting random tests...
Done testing
https://ideone.com/N9vXFa
language:
Python (PyPy 2.7.13)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!