prev • index • info • next
code guessing, round #25 (completed)
started at 2022-09-26T13:19:10.947752+00:00 ; stage 2 at 2022-10-08T16:46:27+00:00 ; ended at 2022-10-12T22:37:04.341545+00:00

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
ðŸ‘‘ LyricLy +3 -0 = 3 razetime GNU Radio Shows lynn (was moshikoi) Olivia moshikoi (was lynn) moshikoi +2 -0 = 2razetime LyricLy (was GNU Radio Shows) Olivia GNU Radio Shows (was lynn) lynn (was LyricLy) lynn +1 -0 = 1GNU Radio Shows (was razetime) razetime (was GNU Radio Shows) LyricLy (was moshikoi) Olivia moshikoi (was LyricLy) GNU Radio Shows +1 -1 = 0lynn (was razetime) LyricLy (was moshikoi) Olivia razetime (was lynn) moshikoi (was LyricLy) razetime +1 -2 = -1LyricLy (was GNU Radio Shows) lynn (was moshikoi) Olivia moshikoi (was lynn) GNU Radio Shows (was LyricLy) Olivia +0 -5 = -5lynn (was razetime) LyricLy (was GNU Radio Shows) razetime (was moshikoi) GNU Radio Shows (was lynn) moshikoi (was LyricLy)
entries you can download all the entries

written by razetime submitted at 2022-10-06T02:49:50.283511+00:00 1 like

guesses GNU Radio Shows (by lynn) lynn (by Olivia) lynn (by GNU Radio Shows) razetime (by LyricLy)razetime (by moshikoi)comments 0Entry.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 ]

written by GNU Radio Shows submitted at 2022-10-03T23:14:42.746690+00:00 0 likes

guesses GNU Radio Shows (by LyricLy)LyricLy (by Olivia) LyricLy (by razetime) LyricLy (by moshikoi) razetime (by lynn) comments 1WhyWastePerfectlyGoodGraphAlgorithmsThatAreAlreadyBuiltIntoTheRuntime.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 []

written by moshikoi submitted at 2022-10-04T22:18:28.124154+00:00 0 likes

guesses LyricLy (by lynn) LyricLy (by GNU Radio Shows) lynn (by razetime) lynn (by LyricLy) razetime (by Olivia) comments 0entry.py ASCII text, with CRLF line terminators 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 2022-10-02T15:34:53.093349+00:00 2 likes

guesses Olivia (by razetime)Olivia (by lynn)Olivia (by LyricLy)Olivia (by GNU Radio Shows)Olivia (by moshikoi)comments 0mlochbaumILanguage.pdf version 1.3, 7 page(s) written by lynn submitted at 2022-10-05T12:46:19.943230+00:00 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 0sym.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 ))

written by LyricLy submitted at 2022-10-08T03:26:20.700326+00:00 0 likes

guesses GNU Radio Shows (by razetime) lynn (by moshikoi) moshikoi (by Olivia) moshikoi (by lynn) moshikoi (by GNU Radio Shows) comments 0bfs.py ASCII text
## post a comment