100 doors problem


See On Github

Data

Contributor

Generic placeholder thumbnail

by sunilshahu

in c

Tags

puzzle

Source Code

CFLAGS=-Wall -o
BUILD=gcc
all: hundred_doors

clean:
	rm -f hundred_doors

hundred_doors : hundred_doors.c hundred_doors.h hundred_doors_test.c 
	$(BUILD) $(CFLAGS) hundred_doors hundred_doors.c hundred_doors_test.c
Puzzle:

There are 100 doors in a long hallway. They are all closed. The first time you
walk by each door, you open it. The second time around, you close every second
door (since they are all opened). On the third pass you stop at every third door
and open it if it’s closed, close it if it’s open. On the fourth pass, you take
action on every fourth door. You repeat this pattern for 100 passes.

At the end of 100 passes, what doors are opened and what doors are closed?

Solution:

This soution is focused on high memory optimization on the cost of processing
time.

An array of four 32 bit integer is used to store status of 100 doors. Each bit
in a integer represents a door. Set bit (1) represents open door and
reset bit (0) represents closed door. Bitwise shifting is used to access each
bit.
#include <stdio.h>
unsigned int ELEMENT_SIZE = 8*sizeof(unsigned int);

void find_open_doors(unsigned int doors[])
{
	unsigned int i, j, element, position;
	for (i = 1; i <= 100; i++) {
		for(j = (i-1); j < 100; j += i) {
			element = (j / ELEMENT_SIZE);
			position = (j % ELEMENT_SIZE);
			doors[element] ^= (1 << position);
		}
	}
}

void print_open_doors(unsigned int doors[])
{
	unsigned int i, element, position;
	printf("Open doors at position :\n");
	for(i = 0; i < 100; i++) {
		element = i / ELEMENT_SIZE;
		position = i % ELEMENT_SIZE;
		if ((doors[element] >> position) & 0x01)
			printf("%d\n", (i+1));
	}
}
void find_open_doors(unsigned int doors[]);
void print_open_doors(unsigned int doors[]);
#include <stdio.h>
#include "hundred_doors.h"
int main() {
	unsigned int doors[4] = {0};
	find_open_doors(doors);
	print_open_doors(doors);
	return 0;
}