Advent of Code Day 6: toggling lights in a grid with Powershell

Question

I am using the "Advent of Code" series to help with my PowerShell education. The Day 6 puzzle has a 1000 ×ばつ 1000 grid of lights. After processing instructions to turn on, turn off, or toggle rectangles of lights in the grid, how many lights are on at the end?

I am confident that this script will produce the right answer. However, it is going way too slow. I am interested in optimizing this script for performance. I am not against coming up with an alternative way to solve this problem with PowerShell.

$lightson = New-Object Collections.Generic.HashSet[string]
$strings = Get-Content C:\test\lights.txt
foreach ($string in $strings){
 $numbers = [regex]::matches($string,"\d+")
 $minX = [convert]::ToInt32($numbers[0],10)
 $minY = [convert]::ToInt32($numbers[1],10)
 $maxX = [convert]::ToInt32($numbers[2],10)
 $maxY = [convert]::ToInt32($numbers[3],10)
 $x = $minX
 $y = $miny
 write-host $string
 write-host $x $y
 if ($string -like "turn on*"){
 write-host "turn on"
 while ($x -le $maxX){
 while ($y -le $maxY){
 $light = "$x,$y"
 if ($light -notin $lightson){
 [void]$lightson.Add("$x,$y")
 #write-host $lightson.Count
 }
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Count "`n"
 }
 if ($string -like "turn off*"){
 write-host "turn off"
 while ($x -le $maxX){
 while ($y -le $maxY){
 $light = "$x,$y"
 if ($light -in $lightson){
 [void]$lightson.Remove("$x,$y")
 #write-host $lightson.Count
 }
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Count "`n"
 }
 if ($string -like "toggle*"){
 write-host "toggle`n"
 while ($x -le $maxX){
 while ($y -le $maxY){
 $light = "$x,$y"
 if ($light -in $lightson){
 $lightson.Remove("$x,$y")
 #write-host $lightson.Count
 }
 else{[void]($lightson.Add("$x,$y"))}
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Count "`n"
 }
}

There are a million different lights that can be on or off. This massive number is obviously causing the long process time. At the moment, I can not think of any alternatives.

• PetSerAl: First of all, to get correct result you need to change -lt to -le. And use some proper collection (like HashSet) instead of array: $lightson = New-Object Collections.Generic.HashSet[string], turn on: [void]$lightson.Add("$x,$y"), turn off: [void]$lightson.Remove("$x,$y"), toggle: [void]($lightson.Add("$x,$y") -or $lightson.Remove("$x,$y")).
• Kai Zhao: Totally agree with the comment @PetSerAl given above. The count of remaining items in the hash table will be the lights turned on. This would be way more effective than dealing with one unorganized array.
• Collin Stump: I have made the changes suggested by @PetSerAl, but the script is still running slow.
• Matt: What are you using to test with exactly? Getting a baseline for this would be hard since we do not know what you test case is. Are you just using the 3 examples from the linked page? Might be worth adding more work to this to be sure the performance changes scale well.

Answer 1

I assume the Write-Host commands are to view progress/status of the script? I would remove these if you are confident the script is reliable and accurate. Maybe one status (write-host $lightson.Count) after every instruction line.

---

When you add a light to the list, you don't need to check if it's already in the list. Add will return True/False for its success. Either way, you won't need to check before or after. Just know that if it was on the list already, it will simply return False and carry on. Likewise when removing it from the list.

while ($x -le $maxX){
 while ($y -le $maxY){
 $light = "$x,$y"
 [void]$lightson.Add("$x,$y")
 $y +=1
 }
 $x += 1
 $y = $miny
}

You will also no longer need $light.

---

When toggling a light, you can again use the return value of Add or Remove:

while ($x -le $maxX){
 while ($y -le $maxY){
 If ($lightson.Remove("$x,$y")) { }
 Else {[void]$lightson.Add("$x,$y")}
 $y +=1
 }
 $x += 1
 $y = $miny
}

---

Every loop of ForEach is evaluating all three If conditions. You can combine these into an If/ElseIf/ElseIf so subsequent conditions are not evaluated when the first has already succeeded.

---

For slightly less verbose loops, you could change While loops to For loops. This didn't make a large difference in times though.

I entered the number into the website you linked, and your algorithm did give the correct answer.

$lightson = New-Object Collections.Generic.HashSet[string]
$strings = Get-Content C:\test\lights.txt
foreach ($string in $strings){
 $numbers = [regex]::matches($string,"\d+")
 $minX = [convert]::ToInt32($numbers[0],10)
 $minY = [convert]::ToInt32($numbers[1],10)
 $maxX = [convert]::ToInt32($numbers[2],10)
 $maxY = [convert]::ToInt32($numbers[3],10)
 if ($string -like "turn on*"){
 For ($x = $minX; $x -le $maxX; $x++) {
 For ($y = $minY; $y -le $maxY; $y++) {
 [void]$lightson.Add("$x,$y")
 }
 }
 } ElseIf ($string -like "turn off*"){
 For ($x = $minX; $x -le $maxX; $x++) {
 For ($y = $minY; $y -le $maxY; $y++) {
 [void]$lightson.Remove("$x,$y")
 }
 }
 } ElseIf ($string -like "toggle*"){
 For ($x = $minX; $x -le $maxX; $x++) {
 For ($y = $minY; $y -le $maxY; $y++) {
 If ($lightson.Remove("$x,$y")) { }
 Else {[void]$lightson.Add("$x,$y")}
 }
 }
 }
 write-host $lightson.Count
}

• Dangph: Just curious, did your version run faster?
• xXhRQ8sD2L7Z: Much faster. Removing lines searching $lightson (-in and -notin) is where I saw the biggest performance gain.

Answer 2

Summary

I recommend doing the following to improve the powershell performance:

• never use the += for adding an additional values to an array, this is gets extremely costly as the array size increases. With millions of records and the numerous nested loops, I can only imagine how long this is running.

  • if you must use an array, then I suggest using the following general frame work:

.

[array]$MyArray = foreach ( $ThisItem in $AllItems ) {
 ... some script that does a desired task for example...
 [string]$output = "$ThisItem is my new item"
 write-output $output
 } 

.

• likewise do not use an @().count function inside a loop, this is also costly. In the below example I've left them in because I don't know if you're really using the output. But instead of counting an array, we're counting the number of keys in the hashtable.

• assuming all your lights are uniquely named then instead of building an array I'd use a hashtable. These things have interesting properties, like all the key names are automatically unique.

• using the value -in array test is also costly, especially in loops. Here I've replaced them with .ContainsKey('<keyname>') method.

• write-host can take some time to update the console. So I recommend not using so many of these write-host commands, unless they're actually being used for debug or updating the user.

Resulting script would look like this

I've commented out the lines with # that I didn't like and replaced them with new lines of similar functionality.

# $lightson = @()
[hashtable]$lightson = @{}
$strings = Get-Content C:\test\lights.txt
foreach ($string in $strings){
 $numbers = [regex]::matches($string,"\d+")
 $minX = [convert]::ToInt32($numbers[0],10)
 $minY = [convert]::ToInt32($numbers[1],10)
 $maxX = [convert]::ToInt32($numbers[2],10)
 $maxY = [convert]::ToInt32($numbers[3],10)
 $x = $minX
 $y = $miny
 write-host $string
 write-host $x $y
 if ($string -like "turn on*"){
 write-host "turn on"
 while ($x -lt $maxX){
 while ($y -lt $maxY){
 $light = "$x,$y"
# if ($light -notin $lightson){
 if ($lightson.ContainsKey($light)){
 } else {
 $lightson[$light] = $light
# $lightson += $light
 write-host $lightson.Keys.Count
 }
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Keys.Count "`n"
 }
 if ($string -like "turn off*"){
 write-host "turn off"
 while ($x -lt $maxX){
 while ($y -lt $maxY){
 $light = "$x,$y"
# if ($light -in $lightson){
 if ($lightson.ContainsKey($light)){
 $lightson[$light] = $lightson[$light] -ne $light
# $lightson = $lightson -ne $light
 write-host $lightson.Keys.Count
 }
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Keys.Count "`n"
 }
 if ($string -like "toggle*"){
 write-host "toggle`n"
 while ($x -lt $maxX){
 while ($y -lt $maxY){
 $light = "$x,$y"
# if ($light -in $lightson){
 if ($lightson.ContainsKey($light)){
 $lightson[$light] = $lightson[$light] -ne $light
# $lightson = $lightson -ne $light
 write-host $lightson.Keys.Count
 }
 else{
 $lightson[$light] = $light
# $lightson += $light
 }
 $y +=1
 }
 $x += 1
 $y = $miny
 }
 write-host $lightson.Keys.Count "`n"
 }
}

Answer 3

I made a few changes to ST8Z6FR57ABE6A8RE9UF's version of your code. First, I made the unpacking of the regex match object a little more compact:

 $numbers = [regex]::matches($string,"\d+")
 [int]$minX, [int]$minY, [int]$maxX, [int]$maxY = $numbers.Value

I used a switch statement instead of the if statements, just for readability:

 switch -wildcard ($string) {
 "turn on*" { # ... 
 }
 "turn off*" { # ... 
 }
 "toggle*" { # ... 
 }
 }

I changed the for statements to foreach. That was done for readability, but as a nice surprise it sped the script up by 30%:

 foreach ($x in $minX .. $maxX) {
 foreach ($y in $minY .. $maxY) {
 [void]$lightson.Add("$x,$y")
 }
 }

This is the final code:

$lightson = New-Object Collections.Generic.HashSet[string]
$strings = Get-Content C:\test\lights.txt
foreach ($string in $strings){
 $numbers = [regex]::matches($string,"\d+")
 [int]$minX, [int]$minY, [int]$maxX, [int]$maxY = $numbers.Value
 switch -wildcard ($string) {
 "turn on*" {
 foreach ($x in $minX .. $maxX) {
 foreach ($y in $minY .. $maxY) {
 [void]$lightson.Add("$x,$y")
 }
 }
 }
 "turn off*" {
 foreach ($x in $minX .. $maxX) {
 foreach ($y in $minY .. $maxY) {
 [void]$lightson.Remove("$x,$y")
 }
 }
 } 
 "toggle*" {
 foreach ($x in $minX .. $maxX) {
 foreach ($y in $minY .. $maxY) {
 If ($lightson.Remove("$x,$y")) { }
 Else {[void]$lightson.Add("$x,$y")}
 }
 }
 }
 }
 write-host $lightson.Count
}

I also tried using an array of bool instead of the HashSet. That sped things up by about 4%, but it made the code slightly more verbose, so I didn't keep that change.

PowerShell is not the ideal language for this sort of problem where we have tight loops. It is the sort of thing you would write in another language and then call that from PowerShell.

If I absolutely had to make it run fast in PowerShell, I would experiment with GDI+ bitmaps (or maybe GDI+ regions).

• Matt: Could you change If ($lightson.Remove("$x,$y")) { }Else {[void]$lightson.Add("$x,$y")} to If (!($lightson.Remove("$x,$y"))) {[void]$lightson.Add("$x,$y")} which would remove the else and empty iftrue block?
• Dangph: @Matt, sure, you could do that. It's just a question of which one is clearer to people reading the code. I think how ST did it above was pretty clear.

Answer 4

I realize that this is a little old, but I'm new to this particular Stack site (I usually haunt StackOverflow) and wanted to chime in.

I too would suggest the use of a Hashtable to track lights. Individual lights can be easily set, and toggled by location if you use a standardized naming scheme.

I would use simple binary 0 for off, and 1 for on values. Then I would also use another very simple hashtable to toggle lights as needed.

Actual actions I would run through functions named for the action being taken defined in the input string (spaces removed): toggle, turnon, turnoff

Then you can use the automatic variable $Matches in coordination with a Where statement that uses -Match, and a following ForEach, and pipe your input file through that.

I would end up with something like:

#Value of 0 means the light is off, and 1 means it's on.
$Toggle = @{1=0;0=1}
$Lights = @{}
Function Toggle([int]$XStart,[int]$YStart,[int]$XEnd,[int]$YEnd){
 For($i=$XStart;$i -le $XEnd;$i++){
 For($j=$YStart;$j -le $YEnd;$j++){
 $Lights."$i,$j" = $Toggle.([int][convert]::ToString($Lights."$i,$j",2))
 }
 }
}
Function TurnOn([int]$XStart,[int]$YStart,[int]$XEnd,[int]$YEnd){
 For($i=$XStart;$i -le $XEnd;$i++){
 For($j=$YStart;$j -le $YEnd;$j++){
 $Lights."$i,$j" = 1
 }
 }
} 
Function TurnOff([int]$XStart,[int]$YStart,[int]$XEnd,[int]$YEnd){
 For($i=$XStart;$i -le $XEnd;$i++){
 For($j=$YStart;$j -le $YEnd;$j++){
 $Lights."$i,$j" = 1
 }
 }
}
Get-Content C:\test\lights.txt | ?{$_ -match "^(\D+)(\d+),(\d+)\D+(\d+),(\d+)\D*$"} | %{
 $Cmd = "{0} {1} {2} {3} {4}" -f $($Matches[1] -replace " "), $Matches[2], $Matches[3], $Matches[4], $Matches[5]
 Invoke-Expression $Cmd
}
$lights.Values|Measure-Object -Sum|% Sum

At the end there I simply take all the values from the $Lights hashtable, and get a sum from them.