100 doors problem


See On Github

Data

Contributor

Generic placeholder thumbnail

by JanBerktold

in go

Tags

puzzle

Source Code

package main

import (
	"fmt"
)

func walk() []int32 {
	// doors are stored as 32 bit integers
	// so we actually store 32 * 4 = 128 doors, but we can ignore the extra ones
	doors := make([]int32, 4)

	for every := 1; every <= 100; every++ {
		for changeDoor := every; changeDoor <= 100; changeDoor += every {
			position := uint32(changeDoor % 32)
			doors[int(changeDoor/32)] ^= (1 << position)
		}
	}

	return doors
}

func printDoors(doors []int32) {
	for i := 0; i < 100; i++ {
		element := uint32(i / 32)
		position := uint32(i % 32)
		if (doors[element]>>position)&0x01 == 1 {
			fmt.Printf("%d\n", i)
		}
	}

}

func main() {
	doors := walk()
	printDoors(doors)
}
package main

import (
	"testing"
)

func TestDoors(t *testing.T) {
	doors := walk()

	squarePointer := 0
	perfectSquares := []int{
		1, 4, 9, 16, 25, 36, 49, 64, 81,
	}

	for i := 0; i < 100; i++ {
		element := uint32(i / 32)
		position := uint32(i % 32)
		if (doors[element]>>position)&0x01 == 1 {
			if perfectSquares[squarePointer] != i {
				t.Fatalf("Door %v is open but should not be.", i)
			}
			squarePointer++
		} else {
			if len(perfectSquares) > squarePointer && perfectSquares[squarePointer] == i {
				t.Fatalf("Door %v should have been open.", i)
			}
		}
	}

	if squarePointer <= len(perfectSquares)-1 {
		t.Fatalf("Door %v should have been open, however it is not.", perfectSquares[squarePointer])
	}
}