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:

- Python:
`def entry(m: list[list[bool]], a: int, b: int) -> list[int]`

- Haskell:
`entry :: [[Bool]] -> Int -> Int -> [Int]`

- Lisp:
`(entry m a b)`

, where`m`

is a nested list of booleans and`a`

and`b`

are integers, should yield a list of integers.

## ðŸ‘‘

**LyricLy**+3 -0 = 3**razetime****GNU Radio Shows**- lynn (was indigo (away until 9/26))
**Olivia**- indigo (away until 9/26) (was lynn)

**indigo (away until 9/26)**+2 -0 = 2**razetime**- LyricLy (was GNU Radio Shows)
**Olivia**- GNU Radio Shows (was lynn)
- lynn (was LyricLy)

**lynn**+1 -0 = 1- GNU Radio Shows (was razetime)
- razetime (was GNU Radio Shows)
- LyricLy (was indigo (away until 9/26))
**Olivia**- indigo (away until 9/26) (was LyricLy)

**GNU Radio Shows**+1 -1 = 0- lynn (was razetime)
- LyricLy (was indigo (away until 9/26))
**Olivia**- razetime (was lynn)
- indigo (away until 9/26) (was LyricLy)

**razetime**+1 -2 = -1- LyricLy (was GNU Radio Shows)
- lynn (was indigo (away until 9/26))
**Olivia**- indigo (away until 9/26) (was lynn)
- GNU Radio Shows (was LyricLy)

**Olivia**+0 -5 = -5- lynn (was razetime)
- LyricLy (was GNU Radio Shows)
- razetime (was indigo (away until 9/26))
- GNU Radio Shows (was lynn)
- indigo (away until 9/26) (was LyricLy)

you can download all the entries

written by razetime

submitted at

1 like

- GNU Radio Shows (by lynn)
- lynn (by Olivia)
- lynn (by GNU Radio Shows)
**razetime**(by LyricLy)**razetime**(by indigo (away until 9/26))

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

**GNU Radio Shows**(by LyricLy)- LyricLy (by Olivia)
- LyricLy (by razetime)
- LyricLy (by indigo (away until 9/26))
- razetime (by lynn)

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

- LyricLy (by lynn)
- LyricLy (by GNU Radio Shows)
- lynn (by razetime)
- lynn (by LyricLy)
- razetime (by Olivia)

`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

**Olivia**(by razetime)**Olivia**(by lynn)**Olivia**(by LyricLy)**Olivia**(by GNU Radio Shows)**Olivia**(by indigo (away until 9/26))

written by lynn

submitted at

1 like

- GNU Radio Shows (by Olivia)
- GNU Radio Shows (by indigo (away until 9/26))
- indigo (away until 9/26) (by razetime)
- indigo (away until 9/26) (by LyricLy)
- razetime (by GNU Radio Shows)

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

- GNU Radio Shows (by razetime)
- indigo (away until 9/26) (by Olivia)
- indigo (away until 9/26) (by lynn)
- indigo (away until 9/26) (by GNU Radio Shows)
- lynn (by indigo (away until 9/26))

bfs.py

## post a comment