GPNS

GPNS (grid path number sequence) is an esoteric number sequence invented by User:Hakerh400 in 2022.
== Overview ==
Each number in the sequence represents the longest Von Neumann path that can exist in an n\times n grid.
For n=0, the length of the longest path is 0.
For n=1, the length of the longest path is 1.
For n=2, here is the longest path:
 ##
 .#
The # symbol represents path, while the . symbol represents void. The path starts at the top-left corner and ends at the bottom-right corner. The length of the path is 3. Note that there are multiple longest paths. For example, this is also the longest path:
 
 ##
 #.
 
For n=3, here is the longest path:
 
 ###
 ..#
 ###
The length of the path is 7.
For n=4, the maximal path length is 11:
 ####
 ...#
 #..#
 ####
So, the sequence begins with 0,1,3,7,11,\dots
== Properties ==
The author is not sure what the 5th term of the sequence is (the naive implementation takes years to compute). The author also believes that there is no simple formula for the n-th term.
== Implementation ==
Implementation in Haskell:
<nowiki>
import Control.Monad
main :: IO ()
main = mapM_ (print . f) [0..3]
f :: Int -> Int
f n = maximum' # map (path_len n (mk_coords n) . mk_mat n) #
 replicateM (n ^ 2) [0, 1]
mk_mat :: Int -> [a] -> [[a]]
mk_mat n xs = ite (null xs) [] # take n xs : mk_mat n (drop n xs)
mk_range :: Int -> [Int]
mk_range n = [0 .. n - 1]
mk_coords :: Int -> [[(Int, Int)]]
mk_coords n = mk_mat n # do
 a <- mk_range n
 b <- mk_range n
 return (a, b)
maximum' :: [Int] -> Int
maximum' xs = ite (null xs) 0 (maximum xs)
has :: Int -> Int -> Int -> Bool
has n y x = y >= 0 && x >= 0 && y < n && x < n
get :: Int -> Int -> [[a]] -> a
get y x mat = mat !! y !! x
modify' :: Int -> (a -> a) -> [a] -> [a]
modify' 0 f (x:xs) = f x : xs
modify' n f (x:xs) = x : modify' (n - 1) f xs
modify :: Int -> Int -> Int -> (a -> a) -> [[a]] -> [[a]]
modify n y x f mat = ite (has n y x) (modify' y (modify' x f) mat) mat
set' :: Int -> a -> [a] -> [a]
set' 0 z (x:xs) = z : xs
set' n z (x:xs) = x : set' (n - 1) z xs
set :: Int -> Int -> Int -> a -> [[a]] -> [[a]]
set n y x z mat = ite (has n y x) (modify' y (set' x z) mat) mat
path_len :: Int -> [[(Int, Int)]] -> [[Int]] -> Int
path_len n cs mat = maximum' # map (calc_len n mat) #
 filter (\(y, x) -> get y x mat == 1) # concat cs
calc_len :: Int -> [[Int]] -> (Int, Int) -> Int
calc_len n mat (y, x) = iter (step n) # set n y x 2 mat
iter :: (Eq a) => (a -> a) -> a -> Int
iter f z = let z1 = f z in ite (z1 == z) 1 (1 + iter f z1)
step :: Int -> [[Int]] -> [[Int]]
step n mat = map_mat (modify_tile n mat) mat
modify_tile :: Int -> [[Int]] -> Int -> Int -> Int -> Int
modify_tile n mat k y x =
 ite (get y x mat == 1 && (any (\(y, x) -> get y x mat == 2) # adjs n y x)) 2 k
adjs' :: Int -> Int -> [(Int, Int)]
adjs' y x = [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]
adjs :: Int -> Int -> Int -> [(Int, Int)]
adjs n y x = filter (\(y, x) -> has n y x) # adjs' y x
map' :: (a -> Int -> a) -> [a] -> [a]
map' f xs = zipWith f xs [0..]
map_mat :: (a -> Int -> Int -> a) -> [[a]] -> [[a]]
map_mat f = map' # \row y -> map' (\k x -> f k y x) row
infixr 0 # -- Sorry, I don't like money
(#) = id
ite :: Bool -> a -> a -> a
ite True a b = a
ite False a b = b
</nowiki>
Category:Implemented
Category:2022
Category:Languages