started at ; stage 2 at ; ended at
I got lost. your challenge this round is to pathfind. again. submissions can be written in python, haskell, or any variant of lisp.
your input is a simple directed graph represented as an adjacency matrix. it's a grid that works similarly to an adjacency list; each coordinate represents a pair of two nodes, and the value at that coordinate is 0 or 1 depending on whether the two nodes are connected. for example:
0 1 2 3
0 --> 1 -------
| / | 0 | 0 1 1 0
| / | 1 | 0 0 1 1
| / v 2 | 1 1 0 1
2 --- 3 3 | 0 0 1 0
note some properties of the resulting matrix: there are no loops, so the main diagonal is all 0s, and the edges are directed, so the matrix is not symmetric.
given such an adjacency matrix and the indices of two nodes start and end (an n*n boolean array and 2 integers where start < n > end), return some path through the graph from start to end represented as a sequence of intermediate nodes (including start and end). such a path is guaranteed to exist.
APIs:
def entry(m: list[list[bool]], a: int, b: int) -> list[int]entry :: [[Bool]] -> Int -> Int -> [Int](entry m a b), where m is a nested list of booleans and a and b are integers, should yield a list of integers.you can download all the entries
written by razetime
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | import Data.List import Data.Maybe import qualified Data.IntMap.Strict as IM entry :: [[Bool]] -> Int -> Int -> [Int] entry mat a b = fromJust $ entry' (adjToMap mat) a b [] entry' :: IM.IntMap [Int] -> Int -> Int -> [Int] -> Maybe [Int] entry' graph a b visited | a == b = Just [b] | next == [] = Nothing | a /= b = Just $ (:) a $ fromJust $ fromJust $ find isJust $ map (\x -> entry' graph x b (a : visited)) next where next = fromJust (IM.lookup a graph) \\ visited adjToMap :: [[Bool]] -> IM.IntMap [Int] adjToMap mat = IM.fromList [(idx, [ v | (True, v) <- zip row [0..]]) | (idx, row) <- zip [0..] mat] |
written by GNU Radio Shows
submitted at
0 likes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | module WhyWastePerfectlyGoodGraphAlgorithmsThatAreAlreadyBuiltIntoTheRuntime (entry) where import System.IO.Unsafe import System.Mem import System.Mem.Weak import Data.IORef import Data.Maybe import Control.Monad data Node = Node { children :: IORef [Node], parents :: IORef [Weak Node], idx :: Int } mark :: [[Bool]] -> Int -> Int -> IO (Node, Node) sweep :: [Int] -> (Node, Node) -> IO [Int] entry :: [[Bool]] -> Int -> Int -> [Int] mark matrix start end = do nodes <- sequence [Node <$> newIORef [] <*> newIORef [] <*> pure i | i <- [0..n-1]] forM (zip [0..] matrix) $ \(i_from, row) -> forM (zip [0..] row) $ \(i_to, c) -> when c $ let node_from = nodes !! i_from node_to = nodes !! i_to in do node_from_ref <- mkWeakPtr node_from Nothing modifyIORef' (children node_from) (node_to :) modifyIORef' (parents node_to) (node_from_ref :) return (nodes !! start, nodes !! end) -- ___ where n = length matrix -- _____#_#_____ -- | | | | | | sweep path (start, end) -- | | | | | | | idx start == idx end = return path' -- | | | | | | | otherwise = do -- | | | | | | writeIORef (children end) [] -- | | | | | | performGC -- \| | | |/ reachable <- readIORef (parents end) -- |_|_|_| >>= mapM deRefWeak sweep path' (start, last (catMaybes reachable)) where path' = idx end : path entry m start end = unsafePerformIO $ do mark m start end >>= sweep [] |
written by indigo (away until 9/26)
submitted at
0 likes
1 | entry = lambda m, a, b: (f := lambda m, q, b: q[:-1] if (c := q[-2] if len(q) > 1 else a) == b else x if m[c][i := q.pop()] and i not in q and (x := f(m, q + [i, 0], b)) is not None else f(m, q + [i + 1], b) if i + 1 < len(m) else None)(m, [0], b) |
written by Olivia
submitted at
2 likes
written by lynn
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | from sympy import * def entry(m, a, b): n = len(m) p = m = Matrix(n, n, lambda i, j: int(m[i][j]) * Symbol(f'e{n*i+j}', commutative=False)) while pprint(p) or not p[a, b]: p *= m path = Mul.make_args(Add.make_args(p[a, b])[0]) return [a] + [int(v.name[1:]) % n for v in path] if __name__ == "__main__": print(entry([ [False, True, True,False], [False,False, True, True], [ True, True,False, True], [False,False, True,False], ], 3, 1)) |
written by LyricLy
submitted at
0 likes
post a comment