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:

results

  1. 👑 LyricLy +3 -0 = 3
    1. razetime
    2. GNU Radio Shows
    3. lynn (was indigo (away until 9/26))
    4. Olivia
    5. indigo (away until 9/26) (was lynn)
  2. indigo (away until 9/26) +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 indigo (away until 9/26))
    4. Olivia
    5. indigo (away until 9/26) (was LyricLy)
  4. GNU Radio Shows +1 -1 = 0
    1. lynn (was razetime)
    2. LyricLy (was indigo (away until 9/26))
    3. Olivia
    4. razetime (was lynn)
    5. indigo (away until 9/26) (was LyricLy)
  5. razetime +1 -2 = -1
    1. LyricLy (was GNU Radio Shows)
    2. lynn (was indigo (away until 9/26))
    3. Olivia
    4. indigo (away until 9/26) (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 indigo (away until 9/26))
    4. GNU Radio Shows (was lynn)
    5. indigo (away until 9/26) (was LyricLy)

entries

you can download all the entries

entry #1

written by razetime
submitted at
1 like

guesses
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
comments 1
razetime *known at the time as [author of #1]

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 indigo (away until 9/26)
submitted at
0 likes

guesses
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
comments 0

post a comment


mlochbaumILanguage.pdf version 1.3, 7 page(s)

entry #5

written by lynn
submitted at
1 like

guesses
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
comments 0

post a comment


bfs.py ASCII text