fork 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. # Code by apple apple
  17. def inverse(c):
  18.   return 'b' if c == 'a' else 'a'
  19.  
  20. def solve(_s):
  21.    s = [char for char in _s]
  22.  
  23.    # boundary conditions
  24.  
  25.    if len(s) < 3:
  26.      for i, c in enumerate(s):
  27.        if c == '?':
  28.          s[i] = 'b'
  29.      return ''.join(s)
  30.  
  31.    if s[0:2] == ["?", "?"]:
  32.      s[0] = 'a'
  33.    if s[0:2] == ["?", "a"] or s[0:2] == ["?", "b"]:
  34.      s[0] = inverse(s[1])
  35.    if s[0:3] == ['a', '?', '?'] or s[0:3] == ['b', '?', '?']:
  36.      s[1] = inverse(s[0])
  37.    if s[0:3] == ['a', '?', 'b'] or s[0:3] == ['b', '?', 'a']:
  38.      s[1] = s[0]
  39.  
  40.    # primary loop
  41.  
  42.    for i in range(1, len(s)):
  43.      if s[i] == '?':
  44.        if s[i-1] != (s[i+1] if i + 1 < len(s) else s[i-1]) and s[i-2] == (s[i+1] if (i + 1 < len(s) and i > 1) else s[i-2]):
  45.          s[i] = s[i-1] # ba?b => baab
  46.        else:
  47.          s[i] = inverse(s[i-1])
  48.  
  49.    return ''.join(s)
  50.  
  51.  
  52. # My greedy solution
  53. def f(s):
  54.   if len(s) == 2:
  55.     return s.replace('?', 'a')
  56.  
  57.   aa = ['a', 'a']
  58.   bb = ['b', 'b']
  59.  
  60.   out = []
  61.   i = 0
  62.   a, b = 0, 0
  63.  
  64.   while i < len(s):
  65.     if s[i] == 'a' or (s[i] == '?' and b == 2):
  66.       if s[i] == 'a' and a == 2:
  67.         if s[i-3:i-1] == "??":
  68.           out[i-3], out[i-2] = out[i-2], out[i-3]
  69.           a -= 1
  70.         else:
  71.           return ""
  72.       out.append('a')
  73.       a, b = a + 1, 0
  74.       i += 1
  75.     elif s[i] == 'b' or (s[i] == '?' and a == 2):
  76.       if s[i] == 'b' and b == 2:
  77.         if s[i-3:i-1] == "??":
  78.           out[i-3], out[i-2] = out[i-2], out[i-3]
  79.           b -= 1
  80.         else:
  81.           return ""
  82.       out.append('b')
  83.       a, b = 0, b + 1
  84.       i += 1
  85.     elif i == len(s) - 1:
  86.       out.append('a' if b else 'b')
  87.       i += 1
  88.     elif i == len(s) - 2:
  89.       if s[i+1] == '?':
  90.         out.extend(aa if b else bb)
  91.       else:
  92.         out.append('a' if b else 'b')
  93.         out.append(s[i+1])
  94.       i += 2
  95.     elif s[i+1] == '?':
  96.       if a:
  97.         out.append('a')
  98.         a, b = a + 1, 0
  99.       else:
  100.         out.append('b')
  101.         a, b = 0, b + 1
  102.       i += 1
  103.     elif s[i+1] == 'a':
  104.       if a or b < 2:
  105.         out.append('b')
  106.         a, b = 0, b + 1
  107.       else:
  108.         out.append('a')
  109.         a, b = a + 1, 0
  110.       i += 1
  111.     elif s[i+1] == 'b':
  112.       if b or a < 2:
  113.         out.append('a')
  114.         a, b = a + 1, 0
  115.       else:
  116.         out.append('b')
  117.         a, b = 0, b + 1
  118.       i += 1
  119.  
  120.   return ''.join(out)
  121.  
  122.  
  123. strs = [
  124.   "a?bb", # "aabb"
  125.   "??abb", # "ababb" or "bbabb" or "baabb"
  126.   "a?b?aa", # "aabbaa"
  127.   "?bb?",
  128.   #"aa?bb", # NO SOLUTION
  129.   "aa??aa", # "aabbaa"
  130.   "ab???bb?",
  131.   "????",
  132.   "??",
  133.   "?????",
  134.   "??????",
  135.   "?",
  136.   "a?",
  137.   "a??",
  138.   "a???",
  139.   "b?",
  140.   "b??",
  141.   "b???",
  142.   "a?a",
  143.   "a?b",
  144.   "b?a",
  145.   "b?b",
  146.   "a??a",
  147.   "a??b",
  148.   "b??a",
  149.   "b??b",
  150.   "aa?",
  151.   "ba?",
  152.   "a?bb",
  153.   "?bb?",
  154.   "??abb",
  155.   "a?b?aa",
  156.   "ab???bb?",
  157.   #"aa?bb"
  158. ]
  159.  
  160.  
  161. for s in strs:
  162.   _solve = solve(s)
  163.   _f = f(s)
  164.   print("%s\n%s, %s, %s, %s\n" % (s, is_valid(_f), is_valid(_solve), _f, _solve))
  165.  
  166.  
  167. import random
  168.  
  169. def get_random(n):
  170.   char = 'x'
  171.   count = 0
  172.   out = []
  173.   not_c = lambda c: 'a' if c == 'b' else 'b'
  174.  
  175.   for _ in range(n):
  176.     c = ['a', 'b'][int(random.random() * 2)]
  177.     if c != char:
  178.       out.append(c)
  179.       char, count = c, 1
  180.     elif count == 2:
  181.       out.append(not_c(c))
  182.       char, count = not_c(c), 1
  183.     else:
  184.       out.append(c)
  185.       count += 1
  186.  
  187.   for i in range(n):
  188.      if int(random.random() * 2):
  189.       out[i] = '?'
  190.  
  191.   return ''.join(out)
  192.  
  193. num_tests = 1000
  194. n = 20
  195.  
  196. print("Starting random tests...")
  197.  
  198. for _ in range(num_tests):
  199.   s = get_random(n)
  200.   _solve = solve(s)
  201.   _f = f(s)
  202.   valid_solve = is_valid(_solve)
  203.   valid_f = is_valid(_f)
  204.   if not valid_f or not valid_solve:
  205.     print(s, valid_f, valid_solve, _f, _solve)
  206.     break
  207.  
  208. print("Done testing")
Success #stdin #stdout 0.17s 69532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a?bb
True, True, aabb, aabb

??abb
True, True, bbabb, ababb

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

?bb?
True, True, abba, abba

aa??aa
True, True, aabbaa, aabbaa

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

????
True, True, bbab, abab

??
True, True, aa, bb

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

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

?
True, True, b, b

a?
True, True, aa, ab

a??
True, True, abb, aba

a???
True, True, aaba, abab

b?
True, True, ba, bb

b??
True, True, baa, bab

b???
True, True, bbab, baba

a?a
True, True, aba, aba

a?b
True, True, abb, aab

b?a
True, True, baa, bba

b?b
True, True, bab, bab

a??a
True, True, aaba, abba

a??b
True, True, aabb, abab

b??a
True, True, bbaa, baba

b??b
True, True, bbab, baab

aa?
True, True, aab, aab

ba?
True, True, bab, bab

a?bb
True, True, aabb, aabb

?bb?
True, True, abba, abba

??abb
True, True, bbabb, ababb

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

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

Starting random tests...
Done testing
https://ideone.com/oGwDef
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!