Full bit search with Python

What is bit full search? 2 ^ n full search

Example ARC061: Many mathematical formulas

You will be given the string S, which consists only of numbers> 1 and 9 and less. Within this string, you can put a + in some places between these characters. You don't have to put in one. However, the + must not be consecutive. All the strings created in this way can be regarded as mathematical expressions and the sum can be calculated. Calculate the values of all possible formulas and output the sum.

Constraints ・ 1 ≤|S|≤10 ・ All letters contained in S are numbers from 1 to 9.

Input / output example

[in]  125
[out] 176
#  125、1+25、12+5、1+2+4 patterns of 5 can be considered.

Way of thinking

If it is 125, there are two places (1 {a} 2 {b} 5) where you can put "+", so 2 ^ 2 = 4 ways of formulas can be considered. ab There are two choices, with or without "+". And since it is about bit, look for the place where bit stands. The image looks like the following.

index a b
0 0 0
1 0 1
2 1 0
3 1 1

You can see that there are 4 patterns in all.

Implementation in python

Use the python bit operator right shift ">>" bitAND "&". For details on bit operators, here was very helpful.

--Right shift >>

Try shifting 11 to the right by 1 bit. The 1 on the far right disappears and the 0 on the far left is inserted. 1011 = 11 0101 = 5

Let's take 10 & 12 bitAND. (Leave 1 only where both are 1 for each place.) 1010 = 10 1100 = 12 1000 = 08

#Input: 125
s = ["1", "2", "5"]
n = len(s)

for i in range(2 ** (n-1)):
    tmp = [False] * (n-1)
    for j in range(n-1):
        if i >> j & 1:
            tmp[j] = True
    pattern.append(tmp)

print(pattern)
[[False, False], [True, False], [False, True], [True, True]]

I was able to find all the patterns by bit full search. By the way, the answer to the example I solved is like this. (Although the code is dirty and there should be a smarter way to solve it)

Recommended Posts

Full bit search with Python
python bit full search
Bit full search with Go
Learn search with Python # 2bit search, permutation search
Sequential search with Python
Confirm bit full search
Binary search with python
Binary search with Python3
Search engine work with python
Search twitter tweets with python
Streamline web search with python
Build mlpy with python3.3 (64bit) (windows 64bit)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
FizzBuzz with Python3
Algorithm learned with Python 10th: Binary search
Scraping with Python
Change Python 64bit environment to 32bit environment with Anaconda
Statistics with python
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Search the maze with the python A * algorithm
Play with 2016-Python
AES256 with python
Tested with Python
I want to do a full text search with elasticsearch + python
python starts with ()
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
Bit full search and direct product set
PYTHON2.7 64bit version
Solve the subset sum problem with a full search in Python
Algorithm learned with Python 12th: Maze search
Excel with Python
Microcomputer with Python
Cast with python
Automatically search and download YouTube videos with Python
Causal reasoning and causal search with Python (for beginners)
Learn algorithms with Go @ Full search_Linear search method
Use Search Tweets: Full Archive / Sandbox in Python
About bit full search that often appears in competition pros From the eyes of beginners with python
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Primality test with Python
Socket communication with Python
Data analysis with python 2
Try scraping with Python.
Learning Python with ChemTHEATER 03
"Object-oriented" learning with python
Run Python with VBA
Handling yaml with python
Solve AtCoder 167 with python
Serial communication with python
[Python] Use JSON with Python
Learning Python with ChemTHEATER 05-1
Run prepDE.py with python3
1.1 Getting Started with Python
Collecting tweets with Python