previndexinfonext

# code guessing, round #25 (completed)

started at ; stage 2 at ; ended at

## specification

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.

## results

1. ðŸ‘‘ LyricLy +3 -0 = 3
1. razetime
2. GNU Radio Shows
3. lynn (was moshikoi)
4. Olivia
5. moshikoi (was lynn)
2. moshikoi +2 -0 = 2
1. razetime
2. LyricLy (was GNU Radio Shows)
3. Olivia
4. GNU Radio Shows (was lynn)
5. lynn (was LyricLy)
3. lynn +1 -0 = 1
1. GNU Radio Shows (was razetime)
2. razetime (was GNU Radio Shows)
3. LyricLy (was moshikoi)
4. Olivia
5. moshikoi (was LyricLy)
4. GNU Radio Shows +1 -1 = 0
1. lynn (was razetime)
2. LyricLy (was moshikoi)
3. Olivia
4. razetime (was lynn)
5. moshikoi (was LyricLy)
5. razetime +1 -2 = -1
1. LyricLy (was GNU Radio Shows)
2. lynn (was moshikoi)
3. Olivia
4. moshikoi (was lynn)
5. GNU Radio Shows (was LyricLy)
6. Olivia +0 -5 = -5
1. lynn (was razetime)
2. LyricLy (was GNU Radio Shows)
3. razetime (was moshikoi)
4. GNU Radio Shows (was lynn)
5. moshikoi (was LyricLy)

## entries

you can download all the entries

### entry #1

written by razetime
submitted at
1 like

guesses
• GNU Radio Shows (by lynn)
• lynn (by Olivia)
• lynn (by GNU Radio Shows)
• razetime (by LyricLy)
• razetime (by moshikoi)
comments 0

### post a comment

Entry.hs ASCII text
 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]

### entry #2

written by GNU Radio Shows
submitted at
0 likes

guesses
• GNU Radio Shows (by LyricLy)
• LyricLy (by Olivia)
• LyricLy (by razetime)
• LyricLy (by moshikoi)
• razetime (by lynn)
comments 1
razetime Â¶

I love C++

### post a comment

WhyWastePerfectlyGoodGraphAlgorithmsThatAreAlreadyBuiltIntoTheRuntime.hs ASCII text
 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 []

### entry #3

written by moshikoi
submitted at
0 likes

guesses
• LyricLy (by lynn)
• LyricLy (by GNU Radio Shows)
• lynn (by razetime)
• lynn (by LyricLy)
• razetime (by Olivia)
comments 0

### post a comment

entry.py ASCII text, with CRLF line terminators
 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)

### entry #4

written by Olivia
submitted at
2 likes

guesses
• Olivia (by razetime)
• Olivia (by lynn)
• Olivia (by LyricLy)
• Olivia (by GNU Radio Shows)
• Olivia (by moshikoi)
comments 0

### post a comment

mlochbaumILanguage.pdf version 1.3, 7 page(s)

### entry #5

written by lynn
submitted at
1 like

guesses
• GNU Radio Shows (by Olivia)
• GNU Radio Shows (by moshikoi)
• moshikoi (by razetime)
• moshikoi (by LyricLy)
• razetime (by GNU Radio Shows)
comments 0

### post a comment

sym.py ASCII text
 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))

### entry #6

written by LyricLy
submitted at
0 likes

guesses
• GNU Radio Shows (by razetime)
• lynn (by moshikoi)
• moshikoi (by Olivia)
• moshikoi (by lynn)
• moshikoi (by GNU Radio Shows)
comments 0

### post a comment

bfs.py ASCII text