💾 Archived View for kenogo.org › literate_programming › 100_doors.gmi captured on 2023-04-19 at 22:37:50. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

100 doors

Homepage

Literate Programming

This program was written using Emacs Org mode with the org-babel package.

100_doors.org

100_doors.c

Task

There are 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, visit every door and /toggle/ the door (open it if closed and close it if opened). The second time, only visit every second door. The third time, only visit every third door, etc., until you only visith the 100th door.

Program structure

First, we will include the necessary libraries and define our constants. All of the actual code will reside in the main function.

    <<Includes>>
    <<Constants>>
    <<Main function>>

Includes

We're not going to need anything fancy here. Just C's standard I/O library so that we can print our results.

    #include <stdio.h>

Constants

We can change the number of doors and the number of passes here.

    #define NUM_DOORS 100
    #define NUM_PASSES 100

Main function

First, we initialize an array to hold the state of the doors. Then, we iterate over them in the specified manner. At last, we print the numbers of the doors which are open after finishing the process.

    int main()
    {
      <<Initialize the doors>>
      <<Open and close the doors>>
      <<Print the result>>
      return 0;
    }

Initialize the doors

We initialize an array of integers where a value of 0 means that the door is closed and a value of 1 means that it is open.

    int is_open[NUM_DOORS] = { 0 };

Open and close the doors

The outer loop is for passing over all doors `NUM_PASSES ` times. The inner loop is for toggling every `(pass + 1) `'th door. We need to add 1 because we start counting at zero.

    for (int pass = 0; pass < NUM_PASSES; pass++)
      {
        for (int door = pass; door < NUM_DOORS; door += (pass + 1))
          {
            is_open[door] = !is_open[door];
          }
      }

Print the result

Finally, we need to iterate over our array and print the numbers of all doors (starting to count at one) that are open after the procedure is completed.

    printf("The following doors are open:");
    for (int door = 0; door < NUM_DOORS; door++)
      {
        if (is_open[door])
          {
            printf(" %d", (door + 1));
          }
      }
    printf("\n");