Challenge 14: Binary Christmas Tree

Now that it is mid-October, it's obviously time to break out the Christmas decorations (at least at every retail store in town). This year, in the spirit of bringing the joy of Computer Science to everyone, the instructor has decided to have his kids make their own binary christmas tree:

As can be seen, a BCT is simply a binary tree that has red 1's and green 0's. Besides looking beautiful, this festive decoration also serves as a learning tool!

For instance, each path downwards from any node in the tree will lead to a binary string of digits. Taking advantage of this property, the instructor plays the following game with his children:

Given a binary christmas tree, how many paths are there in the BCT that form the binary representation of a particular integer. Note, a path can begin from any node and always travels downwards (from parent to children).

For example, given the tree above, the children would be ask to determine how many paths in the binary christmas tree yield the number 3. Since 3 is 11 in binary, there are 4 different paths in the binary christmas tree with this sequence of nodes.

The children do not like this game, and want daddy's students to once again help them answer these questions in a time efficient manner.

Input

You will be given a series of integer targets and binary christmas trees in the form:

TARGET BINARY_CHRISTMAS_TREES

Note, the binary christmas trees are provided in breadth-first order.

Example Input

3 110010000111111
9 110010000111111
2 110010000111111

Output

For each target and binary christmas tree, you are to determine how many paths in the binary chistmas tree form the target integer in binary and display this result in the following format:

Paths that form $TARGET in binary ($BINARY): $PATHS

Example Output

Paths that form 3 in binary (11): 4
Paths that form 9 in binary (1001): 4
Paths that form 2 in binary (10): 2

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge14               # Create and checkout challenge14 branch

$ $EDITOR challenge14/program.cpp           # Edit your code

$ git add challenge14/program.cpp           # Stage your changes
$ git commit -m "challenge14: done"         # Commit your changes

$ git push -u origin challenge14            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge14 assignment ...
Submitting challenge14 code ...
  Result Success
   Score 6.00
    Time 0.72

$ curl -F source=@challenge14/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge14
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 07 TA List to determine your corresponding TA for the merge request.