Python Use Variable In Regex As Repetition Amount
Solution 1:
regexes are strings, so feel free to use your favorite string formatting construct:
combo = re.compile(r'(?=(.*1.*){%d})' % k)
As to your edited question, I can't find an easy way to do that with regexps, how about the following?
def all_substrings(s):
m = len(s)
for i in range(m):
for j in range(i, m):
yield s[i:j+1]
s = '01010'
print [x for x in all_substrings(s) if x.count('1') == 2]
Solution 2:
So after these many years, someone upvoted this question.
At first, I couldn't recall where I first saw this problem when I posted the question on SO. No it wasn't homework as implied by this comment, but just typing a few keywords into Google, I found the problem description in the following places:
- https://leetcode.com/problems/count-binary-substrings/
- https://www.codechef.com/problems/STRSUB
- https://codeforces.com/problemset/problem/165/C (I believe this is the specific one I was working on)
And I was right about codeforces. I see that I had actually come up with a solution and submitted it. Here was my fastest solution: https://codeforces.com/contest/165/submission/4171748:
k = int(raw_input())
def stable_search( zero, bin_num ):
import collections
c_one = ans = temp_ans = temp_z = 0
c_zero = collections.deque()
for f in bin_num[zero:]:
if f == '1':
c_zero.append(zero); zero = 0
c_one = -~c_one
if c_one >= k:
ans = ans + ( temp_z * temp_ans ) + temp_z
temp_ans = 0; temp_z = -~c_zero.popleft()
else: temp_ans, zero = -~temp_ans, -~zero
return ans + ( temp_z * temp_ans ) + temp_z
def mid(bin_num):
return stable_search(bin_num.find('1'), bin_num)
def find_zeros(bin_num):
import re
return sum((len(sed)*-~len(sed))>>1 for sed in re.findall( '0+', bin_num))
if k == 0: print find_zeros(raw_input())
else: print mid(raw_input())
Yikes! Look at all that bit-twiddling (I must have recently learnt about bitwise operations). Btw, -~n just adds one to n 🙄.
Looking at the code again, I see that regex is used to solve one aspect of the problem (when k is 0), but otherwise the rest is done using a technique I not sure I fully understand now. This looks like a 2 pointer problem, but I think there may be more to it especially given the time limit.
As you can see, the solution runs in O(N) time and was written in python 2 (there was a rumor back then that python 3 was slower than python 2, so everyone religiously stuck with python 2, including yours truly). Let's see if rewriting it in python 3 really makes it slower:
https://codeforces.com/contest/165/submission/115388714
Nope! It got faster.
#!/usr/bin/python3
import collections
import re
def find_bin_ksubs (k: int, bin_num: str) -> int:
tmp_z = tmp_count = count = count_1 = 0
zeros = collections.deque()
count_0 = bin_num.find('1')
if count_0 == -1:
return 0
for b in bin_num[count_0:]:
if b == '1':
zeros.append(count_0)
count_0 = 0
count_1 += 1
if count_1 >= k:
count = count + (tmp_z * tmp_count) + tmp_z
tmp_count = 0
tmp_z = zeros.popleft() + 1
else:
count_0 += 1
tmp_count += 1
return count + (tmp_z * tmp_count) + tmp_z
def find_empties (bin_num: str) -> int:
reg = re.compile(r'0+')
return sum((count ** 2 + count) >> 1 \
for zeros in reg.findall(bin_num) if (count := len(zeros)))
if __name__ == '__main__':
if (k := int (input ())) == 0:
print (find_empties(input()))
else:
print (find_bin_ksubs(k, input()))
EDIT
To be fair, computers have evolved since 2013, so I decided to upload the python2 solution one more time just to make the comparison fair...well it looks like the rumors are still true:
Post a Comment for "Python Use Variable In Regex As Repetition Amount"