A KIND REQUEST ON LOGIC EXPLANATION

[jainiresh]

Hi there tmoux,
Can i request for a logic explanation for the Day 12 part 1 problem, even if it is bruteforce ?

[tmoux]

Hi, you can see my part 1 solution here. I haven't cleaned it up at all, but the solve function computes the answer for each test case.

The brute force approach is to enumerate every possible way to assign . or # to a ? in our string, and then check whether the new string has the expected sequence of runs. To enumerate all possible assignments, I use the fact that the first $2^n$ numbers written out in binary correspond to the $2^n$ ways to make $n$ binary choices. For instance, for $n = 3$, the first $2^3$ numbers are:

000
001
010
011
100
101
110
111

As you can see, each number corresponds to a different way to assign a 0 or 1 to 3 indices. We can think of 0 meaning turn the ? in to a ., and 1 meaning turn the ? into a #. In the loop F0R(mask, 1 << M), I iterate over all $2^M$ masks from $0$ to $2^M-1$, and then use some bit manipulation to access the i'th bit in the mask.

I hope that helps; feel free to ask any more questions.