Add Relative TreePath Hole #1116
Comments
|
Looks like I forgot to specify a shortest condition:
and a couple typos:
function Validate-Solution{
param(
[string]$Path = '' # the case sensitive path to take from start to end
,[int64] $StartR = 0 # the starting r position
,[int64] $StartI = 0 # the starting i position
,[int64] $EndR = 0 # the expected ending r position
,[int64] $EndI = 0 # the expected ending i position
)
$r = $StartR
$i = $StartI
#The shortest path will not back-track away/towards the zero
$RootsTogg = $LeavesTogg = $VinesTogg = $FruitTogg = $false
#debug#>write-host "$r $i $path"
foreach($d in $Path.ToCharArray()){
$ok = switch -exact -CaseSensitive ($d) {
'P'{$i -eq 0 -and $r -gt 0 -and !$RootsTogg ;break}
'L'{$i -eq 0 -and $r -le ([int64]::MaxValue / 2) ;$RootsTogg = $true;break}
'R'{$i -eq 0 -and $r -le ([int64]::MaxValue / 2) ;$RootsTogg = $true;;break}
'p'{$i -eq 0 -and $r -lt 0 -and !$LeavesTogg ;break}
'l'{$i -eq 0 -and $r -ge ([int64]::MinValue / 2) ;$LeavesTogg = $true;break}
'r'{$i -eq 0 -and $r -ge ([int64]::MinValue / 2) ;$LeavesTogg = $true;break}
'H'{$i -gt 0 -and !$VinesTogg ;break}
'I'{$i -le ([int64]::MaxValue / 2) ;$VinesTogg = $true ;break}
'O'{$i -le ([int64]::MaxValue / 2) ;$VinesTogg = $true ;break}
'h'{$i -lt 0 -and !$FruitTogg ;break}
'i'{$i -ge ([int64]::MinValue / 2) ;$FruitTogg = $true ;break}
'o'{$i -ge ([int64]::MinValue / 2) ;$FruitTogg = $true ;break}
default{ $false }
}
if(!$ok){
#debug#> write-host "Cannot move $d from $r $i $ok :$RootsTogg,$LeavesTogg,$VinesTogg,$FruitTogg"
return $false
}
switch -exact -CaseSensitive ($d) {
'P'{$pos = $r + 1 ;$pos -= $pos % 2 ;$pos /= 2 ;$r = $pos - 1 ;break}
'L'{$pos = $r + 1 ;$pos = $pos * 2 ;$r = $pos - 1 ;break}
'R'{$pos = $r + 1 ;$pos = $pos * 2 + 1 ;$r = $pos - 1 ;break}
'p'{$pos = 1 - $r ;$pos -= $pos % 2 ;$pos /= 2 ;$r = 1 - $pos ;break}
'l'{$pos = 1 - $r ;$pos = $pos * 2 + 1 ;$r = 1 - $pos ;break}
'r'{$pos = 1 - $r ;$pos = $pos * 2 ;$r = 1 - $pos ;break}
'H'{$pos = $i + 1 ;$pos -= $pos % 2 ;$pos /= 2 ;$i = $pos - 1 ;break}
'I'{$pos = $i + 1 ;$pos = $pos * 2 ;$i = $pos - 1 ;break}
'O'{$pos = $i + 1 ;$pos = $pos * 2 + 1 ;$i = $pos - 1 ;break}
'h'{$pos = 1 - $i ;$pos -= $pos % 2 ;$pos /= 2 ;$i = 1 - $pos ;break}
'i'{$pos = 1 - $i ;$pos = $pos * 2 ;$i = 1 - $pos ;break}
'o'{$pos = 1 - $i ;$pos = $pos * 2 + 1 ;$i = 1 - $pos ;break}
}
#debug#>write-host "$d $r $i"
}
return $r -eq $EndR -and $i -eq $EndI
}Validate-Solution 'hhhhppppRLLLOIII' -23 -23 23 23
@(# TreePath
@{StartR = 1 ;EndR = 2 ;path = 'PR'}
@{StartR = 2 ;EndR = 1 ;path = 'PL'}
@{StartR = 0 ;EndR = 30 ;path = 'RRRR'}
@{StartR = 22 ;EndR = 23 ;path = 'PPPPRLLL'}
# NegaTravel
@{StartR = 1 ;EndR = 2 ;path = 'PR'}
@{StartR = 2 ;EndR = 1 ;path = 'PL'}
@{StartR = -1 ;EndR = -2 ;path = 'pl'}
@{StartR = -2 ;EndR = -1 ;path = 'pr'}
@{StartR = 1 ;EndR = -1 ;path = 'Pr'}
@{StartR = -1 ;EndR = 2 ;path = 'pR'}
@{StartR = -22 ;EndR = 23 ;path = 'ppppRLLL'}
# Fruitful Imagination
@{StartR = 1 ;StartI = 0 ;EndR = 2 ;EndI = 0 ;path = 'PR'}
@{StartR = 2 ;StartI = 0 ;EndR = 1 ;EndI = 0 ;path = 'PL'}
@{StartR = -1 ;StartI = 0 ;EndR = -2 ;EndI = 0 ;path = 'pl'}
@{StartR = -2 ;StartI = 0 ;EndR = -1 ;EndI = 0 ;path = 'pr'}
@{StartR = 0 ;StartI = 1 ;EndR = 0 ;EndI = 2 ;path = 'HO'}
@{StartR = 0 ;StartI = 2 ;EndR = 0 ;EndI = 1 ;path = 'HI'}
@{StartR = 0 ;StartI = -1 ;EndR = 0 ;EndI = -2 ;path = 'ho'}
@{StartR = 0 ;StartI = -2 ;EndR = 0 ;EndI = -1 ;path = 'hi'}
@{StartR = -23 ;StartI = -23 ;EndR = 23 ;EndI = 23 ;path = 'hhhhppppRLLLOIII'}
) | % { $splat = $_; Validate-Solution @splat ;write-host ''}Looks like the validator could still use some back-tracking refinement though Validate-Solution -Path 'PPLR' -StartR 3 -EndR 4 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Given the infinite binary tree formed by numbering the nodes starting at zero root to leaves left to right.
eg
Find the case-sensitive TreePath between two random non-negative integers A and B using the directions: L for left child, R for right child, and P for parent.
eg
between 1 and 2: PR
between 2 and 1: PL
between 0 and 30: RRRR
between 22 and 23: PPPPRLLL
Example input (if any)
These are provided by the hole and could be either hard-coded or generated, the first line is the number of cases, the the following lines are the two integers on a line per-case separated by a space.
Example output
the golfer's algorithm produces the string output line by line corresponding to the cases given by the hole
NegaTravel Variant
This time given the doubly infinite mostly-binary graph starting at trunk zero growing positive roots left to right and negative leaves right to left.
eg
Find the case-sensitive NegaTravel Path between two random integers A and B using the directions:
eg
between 1 and 2: PR
between 2 and 1: PL
between -1 and -2: pl
between -2 and -1: pr
between 1 and -1: Pr
between -1 and 2: pR
between -23 and 23: ppppRLLL
A Fruitful Imagination Variant
Given the hard to picture yet still countably infinite binary-esque graph starting at trunk zero growing growing positive roots left to right and negative leaves right to left, imagine at each root and leaf a negative fruit growing and positive vines hanging in and out (note: fruit/vies are mirrored not reversed like leaves/roots).
eg
Find the case-sensitive Path between two random integer valued complex numbers A and B using the directions:
eg
between 1+0i and 2+0i: PR
between 2+0i and 1+0i: PL
between -1+0i and -2+0i: pl
between -2+0i and -1+0i: pr
between 0+1i and 0+2i: HO
between 0+2i and 0+1i: HI
between 0-1i and 0-2i: hi
between 0-2i and 0-1i: ho
between -23-23i and 23+23i: hhhhppppRLLLOIII
I'm not too sure what would work best for the input of the imaginary numbers maybe
Note
the diagram stops at 30, but the hole can easily be 64-bit integers since the string output length is at most two times the height of the positive tree.
between 7 and 8: PR
between 8 and 9: PPRL
between 9 and 10: PR
The text was updated successfully, but these errors were encountered: