Created
November 30, 2021 01:07
-
-
Save bbarry/b125db5e436c361496494f5986f59dc0 to your computer and use it in GitHub Desktop.
powershell script to determine if a shape is buildable
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function rotate1($shape) { | |
| $low = $shape -band 0x7777 | |
| $high = $shape -band 0x8888 | |
| ($low -shl 1) + ($high -shr 3) | |
| } | |
| function mirror($shape) { | |
| $a = $shape -band 0x1111 | |
| $b = $shape -band 0x2222 | |
| $c = $shape -band 0x4444 | |
| $d = $shape -band 0x8888 | |
| ($a -shl 3) + ($b -shl 1) + ($c -shr 1) + ($d -shr 3) | |
| } | |
| function normalize($shape) { | |
| $l = $shape -shr 12 | |
| if($l -band 0xF) { | |
| $l = $l -shl 4 | |
| } | |
| $l = $l -bor (($shape -band 0xF00) -shr 8) | |
| if($l -band 0xF) { | |
| $l = $l -shl 4 | |
| } | |
| $l = $l -bor (($shape -band 0xF0) -shr 4) | |
| if($l -band 0xF) { | |
| $l = $l -shl 4 | |
| } | |
| $l = $l -bor ($shape -band 0xF) | |
| if(($l -band 0xF) -eq 0) { | |
| $l = $l -shr 4 | |
| } | |
| $l | |
| } | |
| function stack($top, $bottom) { | |
| $opaqueTop = ($top -bor ($top -shl 4) -bor ($top -shl 8) -bor ($top -shl 12)) -band 0xFFFF | |
| $opaqueBottom = ($bottom -bor ($bottom -shr 4) -bor ($bottom -shr 8) -bor ($bottom -shr 12)) | |
| if($opaqueTop -band $opaqueBottom) { | |
| $top = $top -shl 4 | |
| $opaqueTop = $opaqueTop -shl 4 | |
| } else { | |
| return (($top -bor $bottom) -band 0xffff) | |
| } | |
| if($opaqueTop -band $opaqueBottom) { | |
| $top = $top -shl 4 | |
| $opaqueTop = $opaqueTop -shl 4 | |
| } else { | |
| return (($top -bor $bottom) -band 0xffff) | |
| } | |
| if($opaqueTop -band $opaqueBottom) { | |
| $top = $top -shl 4 | |
| $opaqueTop = $opaqueTop -shl 4 | |
| } else { | |
| return (($top -bor $bottom) -band 0xffff) | |
| } | |
| if($opaqueTop -band $opaqueBottom) { | |
| $top = $top -shl 4 | |
| $opaqueTop = $opaqueTop -shl 4 | |
| } else { | |
| return (($top -bor $bottom) -band 0xffff) | |
| } | |
| return (($top -bor $bottom) -band 0xffff) | |
| } | |
| function output1($shape) { | |
| $bit = 1 | |
| $s = '' | |
| if($shape -eq 0) { return '' } | |
| if($shape -band 8) { | |
| $s += 'Cu' | |
| } else { | |
| $s += '--' | |
| } | |
| if($shape -band 4) { | |
| $s += 'Cu' | |
| } else { | |
| $s += '--' | |
| } | |
| if($shape -band 2) { | |
| $s += 'Cu' | |
| } else { | |
| $s += '--' | |
| } | |
| if($shape -band 1) { | |
| $s += 'Cu' | |
| } else { | |
| $s += '--' | |
| } | |
| $s | |
| } | |
| function output($shape) { | |
| $a = output1 (($shape -band 0xF000) -shr 12) | |
| $b = output1 (($shape -band 0xF00) -shr 8) | |
| $c = output1 (($shape -band 0xF0) -shr 4) | |
| $d = output1 ($shape -band 0xF) | |
| $results= @() | |
| if($d) { $results += $d} | |
| if($c) { $results += $c} | |
| if($b) { $results += $b} | |
| if($a) { $results += $a} | |
| '{0:x2} {1}' -f @($shape, ($results -join ':')) | |
| } | |
| function rotations($i) { | |
| $t90 = rotate1 $i | |
| $t180 = rotate1 $t90 | |
| $t270 = rotate1 $t180 | |
| $t = rotate1 $t270 | |
| $m = mirror $t | |
| $m90 = rotate1 $m | |
| $m180 = rotate1 $m90 | |
| $m270 = rotate1 $m180 | |
| ($t,$t90,$t180,$t270,$m,$m90,$m180,$m270) | sort -unique | |
| } | |
| function gameRotations($i) { | |
| $t90 = rotate1 $i | |
| $t180 = rotate1 $t90 | |
| $t270 = rotate1 $t180 | |
| $t = rotate1 $t270 | |
| ($t,$t90,$t180,$t270) | sort -unique | |
| } | |
| function cut($shape) { | |
| normalize ($shape -band 0x3333) | |
| normalize ($shape -band 0xCCCC) | |
| } | |
| function isSimple($shape) { | |
| $a = ($shape -band 0xf000) -shr 12 | |
| $b = ($shape -band 0xf00) -shr 8 | |
| $c = ($shape -band 0xf0) -shr 4 | |
| $d = ($shape -band 0xf) | |
| return ($a -ne 0) -and ($a -band $b) -ne 0 -and ($b -band $c) -ne 0 -and ($c -band $d) -ne 0 | |
| } | |
| function popcount($shape) { | |
| (($shape -band 8) -shr 3) + (($shape -band 4) -shr 2) + (($shape -band 2) -shr 1) + ($shape -band 1) | |
| } | |
| <# | |
| $shape is a number representing a shape after replacing all units with uncolored circles | |
| for example --WySw--:Sw----Cy:----SyWw:RyWw---- | |
| is the same build process as --CuCu--:Cu----Cu:----CuCu:CuCu---- | |
| this shape can be represented with binary: 0110:1001:0011:1100 | |
| or hex: 0x6:0x9:0x3:0xC | |
| since each layer is only 4 bits, an integer can be used: 0xC396 | |
| that gives us a mechanism for counting every combination of 16 units to produce the shapes 0x0000 through 0xFFFF | |
| most of these are uninteresting because they are very simple to produce (------Cu:------Cu:------Cu:------Cu = 0x1111) | |
| in general if one nibble and the next share a bit then they form complete layers and stack | |
| $write is useful for debugging, it writes the currently evaluated shape and other debug info | |
| $pieces is the set of pieces that must exist to generate the shape | |
| returns true if the shape is possible to make (if write is passed, the last line before is the pieces to make the shape) | |
| sample execution: | |
| PS C:\Users\Bill\Documents> breakup -shape 0x78e1 -write $true | |
| 0x78e1 ------Cu:CuCuCu--:Cu------:--CuCuCu | |
| rotation 78e1 ------Cu:CuCuCu--:Cu------:--CuCuCu | |
| (float 2) f7ad = stack -bottom 21 -top f78c | |
| (no float) f78f = stack -bottom 01 -top f78e | |
| rotation b478 Cu------:--CuCuCu:--Cu----:Cu--CuCu | |
| rotation d2b4 --Cu----:Cu--CuCu:----Cu--:CuCu--Cu | |
| rotation e1d2 ----Cu--:CuCu--Cu:------Cu:CuCuCu-- | |
| (float 2) e1d2 = stack -bottom 12 -top fe1c | |
| 12 ----Cu--:------Cu and fe1c CuCu----:------Cu:CuCuCu--:CuCuCuCu | |
| rotation f786 --CuCu--:Cu------:--CuCuCu:CuCuCuCu | |
| (no float) f786 = stack -bottom 02 -top f784 | |
| 12 ----Cu--:------Cu and 02 ----Cu-- and f784 --Cu----:Cu------:--CuCuCu:CuCuCuCu | |
| rotation f784 --Cu----:Cu------:--CuCuCu:CuCuCuCu | |
| rotation fb42 ----Cu--:--Cu----:Cu--CuCu:CuCuCuCu | |
| (no float) fb6 = stack -bottom 02 -top fb4 | |
| rotation fd21 ------Cu:----Cu--:CuCu--Cu:CuCuCuCu | |
| (float 3) fd21 = stack -bottom 121 -top fc | |
| 12 ----Cu--:------Cu and 02 ----Cu-- and 121 ------Cu:----Cu--:------Cu and fc CuCu----:CuCuCuCu | |
| 12 ----Cu--:------Cu and 02 ----Cu-- and 121 ------Cu:----Cu--:------Cu and 0c CuCu---- and 0f CuCuCuCu | |
| True | |
| #> | |
| function breakup($shape, $pieces, $write, $depth) { | |
| if(!$depth) { | |
| $depth = 1 | |
| } | |
| if(!$pieces) { | |
| $pieces = @() | |
| } | |
| if ($write) { | |
| write-host ((($pieces + $shape) | % { output $_ }) -join ' and ') | |
| } | |
| # simple case: shape is only 1 layer; it can be produced by making the input piece | |
| if(($shape -band 0xF) -ne 0 -and (($shape -band 0xF0) -eq 0)) { | |
| return $true | |
| } | |
| $topCount = (popcount ($shape -shr 12)) | |
| # if no float between first and second layer, check if the shape above the first layer can be broken down | |
| if(($shape -band 0xF) -band (($shape -band 0xF0) -shr 4)) { | |
| return breakup -shape ($shape -shr 4) -write $write -pieces ($pieces + ($shape -band 0xF)) | |
| } | |
| # float between first and second layer; for each rotation, try to find a set of pieces that stack to make the shape | |
| foreach ($_ in (gameRotations $shape)) { | |
| if ($write) { | |
| write-host ('rotation {0}' -f @((output $_))) | |
| } | |
| $withTopper = $_ | |
| if($topCount -ne 0 -and $topCount -ne 4) { | |
| $withTopper += 0xF0000 | |
| } | |
| # extract all 5 layers at variables $a through $e | |
| $e = $withTopper | |
| $a = $e -band 0xF | |
| $e = $e -shr 4 | |
| $b = $e -band 0xF | |
| $e = $e -shr 4 | |
| $c = $e -band 0xF | |
| $e = $e -shr 4 | |
| $d = $e -band 0xF | |
| $e = $e -shr 4 | |
| # if the bottom layer has units in quadrants 1 and 2 | |
| if(($a -band 3) -ne 0) { | |
| # if the bottom layer has only 1 unit in quadrands 1 and 2, and the second layer | |
| # only has a unit in the other quadrant on this half | |
| if (($a -band 3) -ne 3 -and (($a -band 3) -bxor ($b -band 3)) -eq 3) { | |
| # if the 3rd layer matches layer 1 in this half | |
| if ((($b -band 3) -bxor ($c -band 3)) -eq 3) { | |
| # if the 4th layer matches layer 2 in this half | |
| if ((($c -band 3) -bxor ($d -band 3)) -eq 3) { | |
| # then quads 1 and 2 form a 4 layer floating half | |
| # split the shape into a bottom piece and top shape that needs to be reviewed recursively | |
| # in game I would represent this as 5 wires, one for each layer, cutting 4 of them and virtually stacking to make the bottom piece | |
| # and the recursion can be handled by unrolling the recursion and producing the machine that handles each recursive case | |
| # (in the recursive call here for example you can only have this particular case twice: shape 0x5A5A) | |
| $bottom = ($_ -band 0x3333) | |
| $top = (($withTopper -band 0xFCCCC) -shr 4) | |
| while (-not ($top -band 0xF)) { | |
| $top = $top -shr 4 | |
| } | |
| # the real meat of the function is here: you cannot actually use the virtual stacker because at this call you don't know how to make the top shape | |
| # and there is no way to unstack an arbitrary shape off the bottom | |
| $stack = stack -bottom $bottom -top $top | |
| if ($write) { | |
| write-host ('(float 4) {0:x2} = stack -bottom {1:x2} -top {2:x2}' -f @($stack, $bottom, $top)) | |
| } | |
| if(($_ -eq $stack) -and (breakup -shape $top -write $write -pieces ($pieces + $bottom))) { | |
| return $true | |
| } | |
| } | |
| # otherwise quads 1 and 2 form a 3 layer floating half | |
| $bottom = ($_ -band 0x333) | |
| $top = (($withTopper -band 0xFFCCC) -shr 4) | |
| while (-not ($top -band 0xF)) { | |
| $top = $top -shr 4 | |
| } | |
| $stack = stack -bottom $bottom -top $top | |
| if ($write) { | |
| write-host ('(float 3) {0:x2} = stack -bottom {1:x2} -top {2:x2}' -f @($stack, $bottom, $top)) | |
| } | |
| if(($_ -eq $stack) -and (breakup -shape $top -write $write -pieces ($pieces + $bottom))) { | |
| return $true | |
| } | |
| } | |
| # otherwise quads 1 and 2 form a 2 layer floating half | |
| $bottom = ($_ -band 0x33) | |
| $top = (($withTopper -band 0xFFFCC) -shr 4) | |
| while (-not ($top -band 0xF)) { | |
| $top = $top -shr 4 | |
| } | |
| $stack = stack -bottom $bottom -top $top | |
| if ($write) { | |
| write-host ('(float 2) {0:x2} = stack -bottom {1:x2} -top {2:x2}' -f @($stack, $bottom, $top)) | |
| } | |
| if(($_ -eq $stack) -and (breakup -shape $top -write $write -pieces ($pieces + $bottom))) { | |
| return $true | |
| } | |
| } | |
| # otherwise layer 1 might need to be broken down into a half shape | |
| $bottom = ($_ -band 0x3) | |
| if($bottom -eq $a) { | |
| # the whole layer is on the left, not possible? I believe this will be caught by the simple non-float stack case before checking rotations | |
| $top = ($withTopper -shr 4) | |
| while (-not ($top -band 0xF)) { | |
| $top = $top -shr 4 | |
| } | |
| $stack = stack -bottom $bottom -top $top | |
| if ($write) { | |
| write-host ('(no float) {0:x2} = stack -bottom {1:x2} -top {2:x2}' -f @($stack, $bottom, $top)) | |
| } | |
| if(($_ -eq $stack) -and (breakup -shape $top -write $write -pieces ($pieces + $bottom))) { | |
| return $true | |
| } | |
| } else { | |
| # the bottom layer needs to be broken down into a half shape | |
| $top = ($withTopper -band 0xFFFC) | |
| while (-not ($top -band 0xF)) { | |
| $top = $top -shr 4 | |
| } | |
| $stack = stack -bottom $bottom -top $top | |
| if ($write) { | |
| write-host ('(no float) {0:x2} = stack -bottom {1:x2} -top {2:x2}' -f @($stack, $bottom, $top)) | |
| } | |
| if(($_ -eq $stack) -and (breakup -shape $top -write $write -pieces ($pieces + $bottom))) { | |
| return $true | |
| } | |
| } | |
| } | |
| } | |
| return $false | |
| } | |
| function hasFloat($shape) { | |
| $a = ($shape -band 0xF000) -shr 12 | |
| $b = ($shape -band 0xF00) -shr 8 | |
| $c = ($shape -band 0xF0) -shr 4 | |
| $d = $shape -band 0xF | |
| (($a -ne 0 -and ($a -band $b) -eq 0)) -or (($b -ne 0 -and ($b -band $c) -eq 0)) -or (($c -ne 0 -and ($c -band $d) -eq 0)) | |
| } | |
| function multipleFloats($shape) { | |
| $a = ($shape -band 0xF000) -shr 12 | |
| $b = ($shape -band 0xF00) -shr 8 | |
| $c = ($shape -band 0xF0) -shr 4 | |
| $d = $shape -band 0xF | |
| return ((stack -bottom $d -top (stack -bottom $c -top (stack -bottom $b -top $a))) -lt 0x100) | |
| } | |
| function noEmptyLayer($shape, $x90, $x270) { | |
| $a = ($shape -band 0xF000) | |
| $b = ($shape -band 0xF00) | |
| $c = ($shape -band 0xF0) | |
| $d = $shape -band 0xF | |
| return $a -and $b -and $c -and $d | |
| } | |
| # returns every unique shape with more than one floating layer | |
| function uniqueBuildableShapesWithMultipleFloats() { | |
| $i = 0x1000 | |
| while ($i -lt 0x10000) | |
| { | |
| $t = $i | |
| $t90 = rotate1 $t | |
| $t180 = rotate1 $t90 | |
| $t270 = rotate1 $t180 | |
| if ((noEmptyLayer $t) -and (multipleFloats $t)) { | |
| $m = mirror $t | |
| $m90 = rotate1 $m | |
| $m180 = rotate1 $m90 | |
| $m270 = rotate1 $m180 | |
| $min = ($t,$t90,$t180,$t270,$m,$m90,$m180,$m270 | measure -min).Minimum | |
| if($min -eq $i) { | |
| if((breakup -shape $i -write $false)) { | |
| output $i | |
| } | |
| } | |
| } | |
| $i++ | |
| } | |
| } | |
| uniqueBuildableShapesWithMultipleFloats |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment