Light Switch Problem

NogDog · Feb 17, 2023

After watching Numberphile: The Light Switch Problem on YouTube this morning, I decided to demonstrate it in PHP during lunch break. I'm sure there are better/cooler ways to do it, but it gets the right result.

<?php

$lights = new Lights();
echo $lights->display();

class Lights {
  private $lights = [];

  public function __construct() {
    foreach (range(0, 9) as $row) {
      $this->lights[$row] = array_fill(1, 10, false);
    }
    foreach(range(1, 100) as $num) {
      $this->switcheroo($num);
    }
  }

  public function display(): string {
    $result = '';
    foreach ($this->lights as $x => $row) {
      foreach ($row as $y => $val) {
        $num = $x * 10 + $y;
        $result .= $val ? str_pad($num, 4, ' ', STR_PAD_LEFT) : '  . ';
      }
      $result .= "\n";
    }
    return $result;
  }

  private function  switcheroo(int $num): void {
    foreach(range(0, 9) as $row) {
      foreach(range(1, 10) as $col) {
        if ((($row * 10) + $col) % $num === 0) {
          $this->lights[$row][$col] = !$this->lights[$row][$col];
        }
      }
    }
  }
}

$ php ~/Desktop/lights.php 
   1  .   .    4  .   .   .   .    9  . 
  .   .   .   .   .   16  .   .   .   . 
  .   .   .   .   25  .   .   .   .   . 
  .   .   .   .   .   36  .   .   .   . 
  .   .   .   .   .   .   .   .   49  . 
  .   .   .   .   .   .   .   .   .   . 
  .   .   .   64  .   .   .   .   .   . 
  .   .   .   .   .   .   .   .   .   . 
  81  .   .   .   .   .   .   .   .   . 
  .   .   .   .   .   .   .   .   .  100

sneakyimp · Feb 18, 2023

echo "lights\n";
$lights = new Lights();
$lights->do_switcheroo();
echo $lights->display();
echo "\n";

echo "lights2\n";
$lights2 = new Lights();
$lights2->not_cheating();
echo $lights2->display();
echo "\n";



class Lights {
  private $lights = [];

  public function __construct() {
    foreach (range(0, 9) as $row) {
      $this->lights[$row] = array_fill(1, 10, false);
    }
  }

  public function display(): string {
    $result = '';
    foreach ($this->lights as $x => $row) {
      foreach ($row as $y => $val) {
        $num = $x * 10 + $y;
        $result .= $val ? str_pad($num, 4, ' ', STR_PAD_LEFT) : '  . ';
      }
      $result .= "\n";
    }
    return $result;
  }

  public function do_switcheroo() {
    $start = microtime(TRUE);
    foreach(range(1, 100) as $num) {
      $this->switcheroo($num);
    }
    echo (microtime(TRUE) - $start), " seconds elapsed\n";
  }

  public function not_cheating() {
    $start = microtime(TRUE);
    $last = floor(sqrt(100));
    for($i=1; $i<=$last; $i++) {
      $square = pow($i, 2);
      $row = floor(($square-1)/10);
      $col = $square - ($row * 10);
      $this->lights[$row][$col] = !$this->lights[$row][$col];
    }
    echo (microtime(TRUE) - $start), " seconds elapsed\n";
  }

  private function  switcheroo(int $num): void {
    foreach(range(0, 9) as $row) {
      foreach(range(1, 10) as $col) {
        if ((($row * 10) + $col) % $num === 0) {
          $this->lights[$row][$col] = !$this->lights[$row][$col];
        }
      }
    }
  }
}

NogDog · Feb 19, 2023

It just occurred to me that I could have used a 1-D array indexed 1-100, and just made it effectively 2-D when displaying it.

<?php

$lights = new Lights();
echo $lights->display();

class Lights {
  private $lights = [];

  public function __construct() {
    $this->lights = array_fill(1, 100, false);
    foreach(range(1, 100) as $num) {
      $this->switcheroo($num);
    }
  }

  public function display(): string {
    $result = '';
    $counter = 0;
    foreach ($this->lights as $ix => $val) {
      $result .= $val ? str_pad($ix, 4, ' ', STR_PAD_LEFT) : '  . ';
      if(++$counter % 10 === 0) {
        $result .= "\n";
      }
    }
    return $result;
  }

  private function  switcheroo(int $num): void {
    foreach($this->lights as $ix => $val) {
      if ($ix % $num === 0) {
          $this->lights[$ix] = !$this->lights[$ix];
      }
    }
  }
}

Weedpacket · Feb 20, 2023

I thought I'd do an animation of the switchings on-and-off (just getting the answer is straightforward: each light is flipped on each pass corresponding to one of its distinct factors; those left on at the end are those with an odd number of distinct factors, i.e., squares). It had been a while since I'd used GD, long enough to forget that it didn't support animated gifs.

const SIZE = 100;

class GridImage
{
	const BulbSize = 20;
	const Padding = 2;
	private int $bulb_width = 0;
	private int $bulb_height = 0;
	private int $pixel_width = 0;
	private int $pixel_height = 0;

	private GdImage $image;
	private int $light_on = 0;
	private int $light_off = 0;

	private function n_to_wh(int $n): array
	{
		--$n;
		$w = $n % $this->bulb_width;
		$h = ($n - $w)/$this->bulb_width;
		return [$w, $h];
	}

	public function __construct()
	{
		$this->bulb_width = (int)ceil(sqrt(SIZE));
		$this->bulb_height = (int)ceil(SIZE / $this->bulb_width);
		$this->pixel_width = ($this->bulb_width - 1) * self::BulbSize + (self::BulbSize - 1) * self::Padding;
		$this->pixel_height = ($this->bulb_height - 1) * self::BulbSize + (self::BulbSize - 1) * self::Padding;
		$this->image = imagecreate($this->pixel_width, $this->pixel_height);
		imagefill($this->image, 0, 0, imagecolorallocate($this->image, 0, 0, 0));
		$this->light_off = imagecolorallocate($this->image, 10, 10, 10);
		$this->light_on = imagecolorallocate($this->image, 255, 255, 64);

		for($i = 1; $i <= SIZE; ++$i)
		{
			$this->paint_bulb($i, false);
		}
	}

	public function paint_bulb(int $i, bool $state): void
	{
		$state = $state ? $this->light_on : $this->light_off;
		[$wpos, $hpos] = $this->n_to_wh($i);
		$xpos = $wpos * (self::BulbSize + self::Padding);
		$ypos = $hpos * (self::BulbSize + self::Padding);
		imagefilledrectangle($this->image, $xpos, $ypos, $xpos + self::BulbSize, $ypos + self::BulbSize, $state);
	}

	public function getImage(): GdImage
	{
		return $this->image;
	}
}

function toggles()
{
	for($i = 1; $i <= SIZE; ++$i)
	{
		for($j = 1; $j <= SIZE; ++$j)
		{
			($j % $i) or yield $j;
		}
	}
}

function actions()
{
	$array = array_fill(0, SIZE, false);

	foreach(toggles() as $toggle)
	{
		yield [$toggle, $array[$toggle - 1] = !$array[$toggle - 1]];
	}
}

$gridimage = new GridImage;
$digs = (int)ceil(log10(SIZE))+1;
$frame = 0;
$filenames = [];
foreach(actions() as [$i, $state])
{
	$frame++;
	$gridimage->paint_bulb($i, $state);
	imagegif($gridimage->getImage(), $filenames[] = sprintf("frames/%0*d.gif", $digs, $frame));
}

$command = "gifsicle --delay 12 -O3 " . join(' ', $filenames) . " > lightup.gif";
`$command`;