previndexinfonext

code guessing, round #26 (completed)

started at ; stage 2 at ; ended at

specification

I misplaced today's spec, but I know it must be similar to my other specs. can you help me find it? your challenge this round is to compute the longest common substring. submissions may be written in python, haskell, c, or zig.

given two strings, there exists at least one string that is a substring of both strings such that there is no longer string with the same property. your challenge is to return one of these strings.

the input strings do not have to be the same length, and the output string may appear in different places within the strings. if there are multiple possible answers, return any one of them.

if the input strings share no characters in common, the result is the empty string.

APIs:

results

  1. 👑 LyricLy +3 -0 = 3
    1. olus2000
    2. Palaiologos
    3. lynn (was indigo (away until 9/26))
    4. MattiDragon
    5. indigo (away until 9/26) (was Olivia)
    6. Olivia (was lynn)
  2. indigo (away until 9/26) +2 -0 = 2
    1. LyricLy (was olus2000)
    2. Palaiologos
    3. olus2000 (was LyricLy)
    4. Olivia (was MattiDragon)
    5. MattiDragon (was Olivia)
    6. lynn
  3. olus2000 +2 -1 = 1
    1. Palaiologos
    2. LyricLy (was indigo (away until 9/26))
    3. Olivia (was LyricLy)
    4. MattiDragon
    5. lynn (was Olivia)
    6. indigo (away until 9/26) (was lynn)
  4. Olivia +1 -0 = 1
    1. indigo (away until 9/26) (was olus2000)
    2. LyricLy (was Palaiologos)
    3. lynn (was indigo (away until 9/26))
    4. Palaiologos (was LyricLy)
    5. MattiDragon
    6. olus2000 (was lynn)
  5. Palaiologos +1 -3 = -2
    1. MattiDragon (was olus2000)
    2. olus2000 (was indigo (away until 9/26))
    3. Olivia (was LyricLy)
    4. indigo (away until 9/26) (was MattiDragon)
    5. LyricLy (was Olivia)
    6. lynn
  6. lynn +0 -2 = -2
    1. MattiDragon +0 -3 = -3
      1. Olivia (was olus2000)
      2. LyricLy (was Palaiologos)
      3. lynn (was indigo (away until 9/26))
      4. olus2000 (was LyricLy)
      5. indigo (away until 9/26) (was Olivia)
      6. Palaiologos (was lynn)

    entries

    you can download all the entries

    entry #1

    written by olus2000
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    bad.c ASCII text, with CRLF line terminators
      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
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    from dataclasses import dataclass, field
    from typing import Optional
    
    
    @dataclass
    class Node:
        first : 'List'
        link : Optional['Node'] = None
    
    @dataclass
    class List:
        start : int
        len : int
        node : Optional[Node] = None
        next : Optional['List'] = None
    
    
    def make_tree(s: str) -> Node:
        tree = Node(List(0, -1))
        cur = tree
        start = 0
        for b in range(len(s)):
            cur, start = extend(cur, start, b - start, s + '\x00')
        return tree
    
    
    def find_l(node: Node, start: int, s1: str, s2: str) -> (List, bool):
        l = node.first
        while s1[l.start] != s2[start]:
            if l.next is None:
                return l, False
            l = l.next
        return l, True
    
    
    def extend(node: Node, start: int, len: int, s: str) -> (Node, int):
        if len < 0: return node, start
        l, flag = find_l(node, start, s, s)
        if not flag:
            assert len == 0
            l.next = List(start, -1)
            l = l.next
        if l.node is None and len == l.len + 1:  # 1st
            l.start = start
            l.len = len
            next_node, next_start, next_len = next_node_start(node, start, len)
            extend(next_node, next_start, next_len, s)
            return node, start
        elif len > l.len:
            return extend(l.node, start + l.len + 1, len - l.len - 1, s)
        elif s[l.start + len] == s[start + len]:  # 3rd
            return node, start
        else:  # 2nd
            new_node = Node(List(start + len, 0, None,
                                 List(l.start + len, l.len - len, l.node)))
            l.len = len - 1
            l.node = new_node
            next_node, next_start, next_len = next_node_start(node, start, len)
            new_node.link, new_start = extend(next_node, next_start, next_len, s)
            return new_node, new_start
    
    
    def next_node_start(node: Node, start: int, len: int) -> (Node, int, int):
        if node.link:
            return node.link, start, len
        return node, start + 1, len - 1
    
    
    def suffixes(node: Node, s: str):
        l = node.first
        while l is not None:
            if l.node is not None:
                yield from (s[l.start:l.start + l.len + 1] + i for i in suffixes(l.node, s))
            else:
                yield s[l.start:l.start + l.len + 1]
            l = l.next
    
    
    def entry(s1, s2):
        node = make_tree(s1)
        best = ''
        match_len = 0
        len = 0
        start = 0
        for i, c in enumerate(s2):
            len += 1
            l, found = find_l(node, start, s1, s2)
            while start <= i and (not found or l.len < i - start or s1[l.start + i - start] != c):
                if not found or l.node is None or l.len >= i - start and s1[l.start + i - start] != c:
                    node, start, _ = next_node_start(node, start, 0)
                    len -= 1
                else:
                    node = l.node
                    start += l.len + 1
                if start > i:
                    break
                l, found = find_l(node, start, s1, s2)
            if len > match_len:
                best = s2[i + 1 - len:i + 1]
                match_len = len
        return best
    

    entry #2

    written by Palaiologos
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    code.hs ASCII text
    1
    2
    3
    4
    import Data.Ord (comparing)
    import Data.List (maximumBy, intersect, inits, tails)
    import Data.Function (on)
    entry=(maximumBy(comparing length).).(intersect`on`concatMap(tail.inits).tails)
    

    entry #3

    written by indigo (away until 9/26)
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    Entry.hs ASCII text, with CRLF line terminators
    1
    2
    3
    4
    5
    6
    7
    module Entry where
    
    import Data.Foldable (maximumBy)
    import Data.Function (on)
    
    entry :: String -> String -> String
    entry a b | a == "" || b == "" = "" | otherwise = maximumBy (compare `on` length)  [map fst $ takeWhile (uncurry (==)) $ zip a b, entry (tail a) b, entry a (tail b)]
    

    entry #4

    written by LyricLy
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    grr.c 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
    // ***'s aphorisms (by ***) in c (lyric and logos (corrupt cg staff) won't let me use hare (2022) (1984))
    
    #include <string.h>
    #include <stdio.h>
    
    char*
    // west const is the best const
    entry(char const* x, char const* y)
    {
        // int index = windex
        int l = strlen(x);
        int l_two_electric_boogaloo = strlen(y);
    
        // column-major wins every wager
        int table[l][l_two_electric_boogaloo];
        int best_len = 0;
        int best;
    
        // for those with foot cancer, merged fors are the answer (and long lines are utterly sublime)
        for (int i = 0, j = 0; j < l_two_electric_boogaloo; i < l ? i++ : (i = 0, j++)) {
            if (x[i] != y[j]) {
                table[i][j] = 0;
                // early exit prevents brexit (a bit too late, but that's great)
                continue;
            }
            int r = i && j ? table[i-1][j-1]+1 : 1;
            table[i][j] = r;
            if (r > best_len) {
                best_len = r;
                best = i+1;
            }
        }
    
        // the first to use strndup scores an alley-oop
        return strndup(x+best-best_len, best_len);
    }
    

    entry #5

    written by MattiDragon
    submitted at
    0 likes

    guesses
    comments 2
    LyricLy

    Taking code from other server members that was written during the round is against the rules. Who originally authored this code?


    MattiDragon *known at the time as [author of #5]

    I was the person who posted it in the server


    post a comment


    26.py ASCII text, with CRLF line terminators
    1
    2
    3
    4
    5
    import itertools
    
    entry = lambda x, y: max((("".join(x[i + o] if x[i + o] == y[j + o] else "\0" for o in range(min(len(x) - i, len(y) - j))).split("\0")[0]) for i, j in itertools.product(range(len(x)), range(len(y)))), key=len, default="")
    
    if __name__ == "__main__": print(entry(input("1: "), input("2: ")))
    

    entry #6

    written by Olivia
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    5 ASCII text, with no line terminators
    1
    r=range(6);entry=lambda x,y:max((s for i in r for j in r if(s:=x[i:j])in y),key=len)
    

    entry #7

    written by lynn
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    readable.py ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    """
    given two strings, there exists at least one string that is a substring of both strings such that there is no longer string with the same property. your challenge is to return one of these strings.
    """
    
    exec(
        __doc__
        .replace("given two strings, ", "def entry(x: str, y: str):")
        .replace("there exists at least one", "substrings_of_x = {x[i:j] for i in range(len(x) + 1) for j in range(i, len(x) + 1)}; substrings_of_y = {y[i:j] for i in range(len(y) + 1) for j in range(i, len(y) + 1)}; substrings_of_both_strings = substrings_of_x & substrings_of_y; these_strings = (")
        .replace("that is a", "for string in")
        .replace("substring of both strings", "substrings_of_both_strings")
        .replace("such that", "if")
        .replace("there is no", "not any(")
        .replace("longer string", "len(x) > len(string)")
        .replace("with the same property.", "for x in substrings_of_both_strings))")
        .replace("your challenge is to ", ";")
        .replace("one of these strings.", "next(these_strings)")
    )