Coin Flip Solution

by Jakob Degen

FLAG: 249369, 124813, 62558, 31388, 15476, 7891, 3975, 1982, 943, 486, 270, 107, 64, 33, 15, 8, 4, 1, 1, 1

Even though the file is a million digits long, this problem can still be solved very quickly. This solution will be written in Python, however much of this code can easily be translated into Java, C++, or other languages.

The first step is to open the file and prepare it for reading. In most other languages this will require a few lines of code, however Python allows this to be done in one line:

f = open('data.txt')

The next step is then to read the file. In Python this can once more be done in one line, however in most other languages this will again take a few lines. Using the list() function, a list of flips can be filled with characters representing the flips.

flips = list(f.read())

The list() function simply turns the outputted String into a list of chars. Next, create a list for storing the final output. It is fair to assume that no runs will have a length of more than 50 (statistically highly improbable), and so use a list comprehension to create list of length 50 filled with zero’s:

runCount = [0 for i in range(50)]

While looping through the data, you will need to be able to keep track of the value associated with the current run (0 or 1) and the length of the run. So you can define two more variables to store these values.

currentValue = flips[0]
run = 0

Finally, you can start looping through the data. In each iteration of the loop, there are two scenarios: The current run is continued, or it is cut off. Begin by writing the loop itself, and the if statement for each scenario:

for i in flips:
    if currentValue == i:
    else:

Filling the if statement for a continued run in is easy- The run counter simply goes up one:

run += 1

Filling in the if statement for the end of the run is somewhat more difficult. Begin by counting up your run counter, as the end of this run needs to be kept track of:

runCount[run] += 1

Then, reset your run and currentValue variables. Your run will obviously go back down to just one, and your currentValue will change to the value of the new run:

currentValue = i
run = 0

This completes your for loop. Now, before outputting your results, there is just one more step necessary. Counting the final run, the one that hasn’t technically “ended” yet. For this you can just count up the run counter, in the right place of course:

runCount[run] += 1

Finally, just print your results:

print(runCount)

Running this program will output the following list:

[0, 249369, 124813, 62558, 31388, 15476, 7891, 3975, 1982, 943, 486, 270, 107, 64, 33, 15, 8, 4, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Showing that our flag is:

249369, 124813, 62558, 31388, 15476, 7891, 3975, 1982, 943, 486, 270, 107, 64, 33, 15, 8, 4, 1, 1, 1

The complete program can be found below:

f = open('data.txt') # Open the file
flips = list(f.read()) # Read the contents of the file into a list
runCount = [0 for i in range(50)] #Assumes no runs longer than 50

currentValue = flips[0] # The value that the current run has
run = 0 # The length of the current run
for i in flips:
    if currentValue == i: # i.e. if the run is continued
        run += 1
    else:# i.e. if the run is over
        runCount[run] += 1
        currentValue = i
        run = 1

runCount[run] += 1 # Add the final (uncounted) run to the count

print(runCount) # Print results