previndexinfonext

code guessing, round #48 (completed)

started at ; stage 2 at ; ended at

specification

help me uncover a conspiracy and find the assassinations foretold in moby-dick. this may be done in python, typescript, rust, or zig.

this problem briefly became popular on Esolangs in 2020 when cyanidesDuality happened across a page satirizing the supposed "bible code", a concept popularized by Michael Drosnin's book The Bible Code, which suggests that the Torah contains encoded predictions of significant events (written by aliens or something?). this lead to myself and umnikos engaging in a duel in which we tried to write as efficient a program as possible to count these strings.

anyway, the basic concept behind these codes can in a few words be described by the term used by bible code enthusiasts: "equidistant letter sequence". one simply chooses a string that they wish to claim was encoded by the bible or moby-dick or whatever, and looks for a place in the book where the chosen string appears as a subsequence with a fixed gap between the characters.

for example, I've just written a book. look out for example book by Christina Hanson in your local bookstore. here is the text of the book:
THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY

there are all sorts of hidden codes in this message. for example, it hints that I am SAD:
THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY

and that the book is a SCAM:
THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY

it even implies I might be GAY:
THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY

however, I am not SICK. (I am in good health, in fact.) it appears as a subsequence, but the gaps between letters are inconsistent:
THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY

your challenge, given a needle and a haystack, is to find a place where the needle appears in the haystack as an equidistant subsequence, returning both the index and the magnitude of the gap between the letters. if there is no valid result, return null (or equivalent).

not just any language is allowed, so there are fixed APIs. the first element of each result tuple is the position, and the second is the gap.

results

  1. 👑 luatic +3 -0 = 3
    1. kotnen (was razetime)
    2. kimapr
    3. LyricLy
    4. vspf (was kotnen)
    5. Olivia (was vspf)
    6. theqwertiest (was Palaiologos)
    7. Lizzy Fleckenstein
    8. olive (was Olivia)
    9. Palaiologos (was olive)
    10. razetime (was theqwertiest)
  2. Olivia +3 -1 = 2
    1. Lizzy Fleckenstein (was razetime)
    2. kimapr
    3. LyricLy
    4. theqwertiest (was kotnen)
    5. olive (was vspf)
    6. Palaiologos
    7. kotnen (was Lizzy Fleckenstein)
    8. vspf (was luatic)
    9. razetime (was olive)
    10. luatic (was theqwertiest)
  3. olive +2 -0 = 2
    1. LyricLy (was razetime)
    2. kimapr
    3. razetime (was LyricLy)
    4. theqwertiest (was kotnen)
    5. luatic (was vspf)
    6. vspf (was Palaiologos)
    7. Lizzy Fleckenstein
    8. Palaiologos (was luatic)
    9. kotnen (was Olivia)
    10. Olivia (was theqwertiest)
  4. theqwertiest +2 -1 = 1
    1. olive (was razetime)
    2. kimapr
    3. kotnen (was LyricLy)
    4. Lizzy Fleckenstein (was kotnen)
    5. luatic (was vspf)
    6. vspf (was Palaiologos)
    7. LyricLy (was Lizzy Fleckenstein)
    8. razetime (was luatic)
    9. Olivia
    10. Palaiologos (was olive)
  5. razetime +1 -0 = 1
    1. Olivia (was kimapr)
    2. Lizzy Fleckenstein (was LyricLy)
    3. luatic (was kotnen)
    4. vspf
    5. LyricLy (was Palaiologos)
    6. Palaiologos (was Lizzy Fleckenstein)
    7. kotnen (was luatic)
    8. theqwertiest (was Olivia)
    9. kimapr (was olive)
    10. olive (was theqwertiest)
  6. kotnen +1 -0 = 1
    1. LyricLy (was razetime)
    2. Lizzy Fleckenstein (was kimapr)
    3. kimapr (was LyricLy)
    4. luatic (was vspf)
    5. vspf (was Palaiologos)
    6. olive (was Lizzy Fleckenstein)
    7. Olivia (was luatic)
    8. Palaiologos (was Olivia)
    9. razetime (was olive)
    10. theqwertiest
  7. LyricLy +2 -2 = 0
    1. Olivia (was razetime)
    2. kimapr
    3. Palaiologos (was kotnen)
    4. razetime (was vspf)
    5. kotnen (was Palaiologos)
    6. Lizzy Fleckenstein
    7. theqwertiest (was luatic)
    8. vspf (was Olivia)
    9. luatic (was olive)
    10. olive (was theqwertiest)
  8. vspf +1 -1 = 0
    1. Lizzy Fleckenstein (was razetime)
    2. kotnen (was kimapr)
    3. theqwertiest (was LyricLy)
    4. kimapr (was kotnen)
    5. Palaiologos
    6. Olivia (was Lizzy Fleckenstein)
    7. razetime (was luatic)
    8. olive (was Olivia)
    9. luatic (was olive)
    10. LyricLy (was theqwertiest)
  9. Palaiologos +0 -2 = -2
    1. kimapr +1 -5 = -4
      1. theqwertiest (was razetime)
      2. olive (was LyricLy)
      3. Palaiologos (was kotnen)
      4. luatic (was vspf)
      5. vspf (was Palaiologos)
      6. Lizzy Fleckenstein
      7. razetime (was luatic)
      8. LyricLy (was Olivia)
      9. Olivia (was olive)
      10. kotnen (was theqwertiest)
    2. Lizzy Fleckenstein +0 -4 = -4

      entries

      you can download all the entries

      entry #1

      written by razetime
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY.py ASCII text
      1
      2
      3
      4
      5
      6
      7
      8
      import re
      def entry(haystack: str, needle: str) -> tuple[int, int] | None:
          final_matches = []
          for i in range(len(haystack)):
              matches = re.finditer(("."*i).join(needle),haystack)
              for j in matches:
                  final_matches.append((j.span()[0],i))
          return final_matches or None
      

      entry #2

      written by kimapr
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      biblical.tar.gz gzip compressed data, from Unix
      dir src
      lib.rs 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
       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
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      pub fn entry(haystack: &str, needle: &str) -> Option<(usize,usize)>
      
      {let solver: solverstd::structs::implemented::SolverBuilderBuilder  = solverstd::structs::implemented::SolverBuilderBuilder::new();
         let solver: solverstd::structs::implemented::SolveBuilder      = solverstd::structs::implemented::SolverBuilderBuilder::haystack(solver,haystack);
       // // / / / / ////  // // //// / YOUR mom is GAY /// // / / / / // / / // / // / / / // // / //// / // /   //  / /
            let solver: solverstd::structs::implemented::Solverer   = solverstd::structs::implemented::SolveBuilder::needle(solver,needle);
       return solverstd::structs::implemented::Solverer::solve(&solver);}
      
         mod solverstd { pub mod structs { pub mod implemented {
      trait CharIter: Iterator<Item=(usize,char)> + Clone {}
      impl<T: Iterator<Item=(usize,char)> + Clone> CharIter for T {}
        struct IncompleteWord<'a> { begin: usize, stride: usize,
          characters_to_go: usize, character: char, characters: std::str::Chars<'a> 
      
         }  impl<'a> Solverer<'a> {
                  pub fn solve(&'a self) -> std::option::Option<(usize,usize)> {
                      if self.Lemonade.is_ascii() {
                          #[cfg(feature="timetest")]println!("ascii!");
                          let chariter = |i,s|self.hackstack.as_bytes()[i..].iter().enumerate().step_by(s).map(move|(o,c)|(o+i,unsafe{char::from_u32_unchecked(*c as u32)}));
                          self.solve_for_real(chariter)
                      } else {
                          #[cfg(feature="timetest")]println!("unicode...");
                          let charinds = str::char_indices(self.hackstack).collect::<Vec<_>>();
                          let chariter = |i,s|charinds[i..].iter().step_by(s).copied();
                          self.solve_for_real(chariter)
                      }
                  }
                   fn solve_for_real<T:CharIter,F:FnMut(usize,usize)->T>(&'a self, mut chariterf: F) -> std::option::Option<(usize,usize)> {#[cfg(any(feature="meow",not(feature="meow")))]{
                      let meow: std::vec::Vec<char> = str::chars(self.Lemonade).collect();
                       let mut characterifier = meow.iter().copied();
      	         let first_character = characterifier.next()?;
                      let characterifier = characterifier;
                   let second_character = characterifier.clone().next();
      
      	            let mut word_seeds: std::vec::Vec<WordSeed<'a>> = std::vec::Vec::new();
                      let mut bad_seeds: std::vec::Vec<usize> = std::vec::Vec::new();
      #[cfg(feature="timetest")]let mut beginned = std::time::Instant::now();
      #[cfg(feature="timetest")]println!("begin...");
               	   for (i,index, character) in chariterf(0,1).enumerate().map(|(i,(cind,character))|(i,cind,character)) {
      	                 if second_character.map(|value|value==character).unwrap_or(false){
                               for (word_index, word_seed) in <[WordSeed]>::iter(std::borrow::Borrow::borrow(&word_seeds)).enumerate() {
                               if index+(index-word_seed.begin)*(self.Lemonade.len()-1)>self.hackstack.len() {
                                   bad_seeds.push(word_index);
                                  } else {
                               let mut count = 1;
                               if chariterf(i,index-word_seed.begin).map(|(_,character)|character).zip(characterifier.clone()).all(|(a,b)|{count+=1;a==b}) && count==self.Lemonade.len() {
                                   return Some((word_seed.begin,index-word_seed.begin-1));
                               }
                                  }
                     }}
      		          for word_index in bad_seeds.drain(..).rev() {
                                word_seeds.swap_remove(word_index);
                          }
                               if character == first_character {
                                  if self.Lemonade.len()<2 { return Some((index,usize::MAX)); }
      	                      std::vec::Vec::push(&mut word_seeds, WordSeed {begin : index, meow: std::marker::PhantomData});
                         }
                               #[cfg(feature="timetest")]{let meow = std::time::Instant::now(); if (meow-beginned).as_millis()>500 { beginned=meow;
                               println!("{} {}",index as f64 / self.hackstack.len() as f64,word_seeds.len())}}
      	      	     }
                    None
                	}
                   }}
        pub struct
      
      SolverBuilderBuilder { murder	//1 481 9991 003 884 4 2342342342 8jg LMK!fc gcc clang llvm
                      	           	//rusted tragedy demonic recruitment
           :()
      }
        pub struct SolveBuilder<'a> {
             haystack: &'a str,
        }
      
      struct WordSeed<'a> {
      	begin: usize,
          meow: std::marker::PhantomData<&'a str>,
       //  characters: std::str::Chars<'a>,
      }
      
      	pub struct Solverer<'a> {
      		hackstack : &'a str,
      		Lemonade : &'a str
      	}
      
      	impl SolverBuilderBuilder {
      		pub fn new() -> Self {
      			Self{murder:()}
      		}
      
      		pub fn haystack<'a>(self, hellostrat: &'a str) -> SolveBuilder<'a> {
      			SolveBuilder {haystack: hellostrat}
      		}
      	}
      
         impl<'a> SolveBuilder<'a> {
           	pub fn needle(self, needLemon: &'a str) -> Solverer {
             Solverer {hackstack: self.haystack,
               Lemonade: needLemon}
                }
      	}
      }}}
      
      
      #[cfg(test)]
      mod tests {
          use super::*;
      
            fn strangle(stack: &str, index: Option<(usize,usize)>, len: usize) -> String {
              let mut buffer = String::new();
            let index = match index {
                 None => {return buffer}
                  Some(index) => {index}
                  };
             for i in 0..len {
                buffer.push(stack.chars().nth(index.0 + i*(index.1)+i).unwrap());
            }
                 return buffer;
         }
      
         #[test]
        fn it_works() {
               let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "S");
             assert!(match result {Some((n,_))=>n==3,None=>false}, "S test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,1));
      
               let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SA");
                assert_eq!(Some((3, 15)), result, "SA test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,2));
      
           let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SAD");
          assert_eq!(Some((10, 8)), result, "SAD test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,3));
      
                let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SCAM");
      	  assert_eq!(Some((9, 4)), result, "SCAM test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,4));
      
            	let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "GAY");
              assert_eq!(Some((39, 0)), result, "GAY test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,3));
      
            let result = entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SICK");
           	assert_eq!(None, result, "SICK test failed: {}", strangle("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY",result,4));
          }
      
         //#[test]
            //fn it_does_not_works() {
          //      unsafe{
            //    *std::mem::transmute::<_,*mut u64>(std::ptr::null::<u8>()) = 42;
        //     };
            //}
      }
      
      .gitignore ASCII text
      1
      2
      /target
      /Cargo.lock
      
      Cargo.toml ASCII text
      1
      2
      3
      4
      5
      6
      7
      8
      [package]
      name = "biblical"
      version = "0.1.0"
      edition = "2021"
      [features]
      timetest=[]
      [dependencies]
      dyn-clone = "1.0.16"
      

      entry #3

      written by LyricLy
      submitted at
      0 likes

      guesses
      comments 1
      Sasuke ¶

      ughhhhhhhhh


      post a comment


      moby2.py ASCII text
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      16
      def entry(body, target):
          seconds = []
          matches = 0
          rest = target[2:]
          for i, c in reversed(list(enumerate(body))):
              if c == target[0]:
                  cd = (len(body) - i) // (len(target) - 1) + i
                  for second in reversed(seconds):
                      if second > cd:
                          break
                      start = second*2 - i
                      step = second - i
                      if body[start:second+step*(len(target)-1):step] == rest:
                          return start, step
              if c == target[1]:
                  seconds.append(i)
      

      entry #4

      written by kotnen
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      rust.rs.tar.gz gzip compressed data, from Unix
      rust.rs 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
      fn entry_impl(haypile: &str, needles: &str)-> Option<(usize, usize)> {
          let hl = haypile.len();
          let nl = needles.len();
          
          for gl in 1 .. (hl / nl) {
              for ni in 0 .. (hl - (nl * gl)) {
                  let mut cn: String = "".to_string();
                  for hi in ni .. hl {
                      if (hi - ni) % gl == 0 && (cn.len() < needles.len()) {
                          cn += &haypile.chars().nth(hi).unwrap().to_string();
                      }
                  }
                  if cn == needles {
                      return Some((ni, gl))
                  }
              }
          }
          
          return None
      }
      
      
      
      fn entry(haystack: &str, needle: &str)-> Option<(usize, usize)> {
          return entry_impl(haystack, needle);
      }
      

      entry #5

      written by vspf
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      feelma.py ASCII text, with CRLF line terminators
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      def feelma ( deez : str , nuts : str ) -> tuple ( [ int , int ] ) or None:
          candice = [ ]
          ligma = len ( nuts )
          sugondese = len ( deez )
          for joe in range ( sugondese ):
              for mama in range ( 1 , sugondese ):
                  try:
                      doomah = ""
                      for kenya in range( ligma ):
                          doomah = doomah + deez [ joe + mama * kenya ]
                      if doomah == nuts:
                          return ( joe , mama )
                  except:
                      pass# deez nuts into your face
          return None
          
      def entry ( haystack : str , needle : str ) -> tuple ( [ int , int ] ) or None:
          return feelma ( haystack , needle )
      

      entry #6

      written by Palaiologos
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      file.py ASCII text
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      from typing import Optional, Tuple
      
      def eqf(haystack: str, needle: str) -> Optional[Tuple[int, int]]:
          if not needle:
              return 0, 0
          elif len(needle) == 1:
              return (haystack.find(needle), 0) if needle in haystack else None
          else:
              for i in range(len(haystack) - len(needle) + 1):
                  if haystack[i] == needle[0] and haystack[i+1:].find(needle[1]) != -1:
                      j = i + 1 + haystack[i+1:].find(needle[1])
                      dist = j - i
                      if needle[2:] == haystack[i + 2 * dist:i + len(needle) * dist:dist]:
                          return i, dist
          return None
      

      entry #7

      written by Lizzy Fleckenstein
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      dir submission
      dir src
      impl.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
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      #include <stdbool.h>
      #include <stddef.h>
      
      bool entry_impl(
      	// strings don't need to be \0 terminated because fuck that
      	const char *haystack, const size_t s_haystack,
      	const char *needle,   const size_t s_needle,
      	// output
      	size_t *start, size_t *gap // thigh gap uwu
      )
      {
      	// search for first char
      	for (*start = 0; *start <= s_haystack-s_needle; haystack++, (*start)++) {
      		// skip over chars that dont match
      		if (*haystack != *needle)
      			continue;
      
      		// reset char gap
      		*gap = 0;
      
      		// if there's only one char in needle, quit early
      		if (s_needle == 1)
      			return true;
      
      		// max pos for second char so the entire needle still fits
      		const char *h_max = haystack + (s_haystack - *start - 1) / (s_needle - 1);
      
      		const char *h = haystack+1;
      		const char *n = needle+1;
      
      		// search for second char
      		for (; *n != *h; h++, (*gap)++) {
      			// skip if no matching second char found
      			if (h > h_max)
      				goto skip;
      		}
      
      		// match remaining chars
      		for (size_t i = 2; i < s_needle; i++) {
      			// skip if mismatch
      			if (*++n != *(h += *gap + 1))
      				goto skip;
      		}
      
      		return true;
      		skip: continue;
      	}
      
      	return false;
      }
      
      lib.rs 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
      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
      // fuck your language limitations
      // just require an ABI or a I/O interface instead of being cringe
      
      #[link(name = "impl")]
      extern "C" {
          pub fn entry_impl(
              haystack: *const u8,
              s_haystack: usize,
              needle: *const u8,
              s_needle: usize,
              start: *mut usize,
              gap: *mut usize,
          ) -> bool;
      }
      
      pub fn entry(haystack: &str, needle: &str) -> Option<(usize, usize)> {
          let mut start = 0;
          let mut gap = 0;
      
          let succ = unsafe {
              entry_impl(
                  haystack.as_ptr(),
                  haystack.len(),
                  needle.as_ptr(),
                  needle.len(),
                  &mut start as *mut usize,
                  &mut gap as *mut usize,
              )
          };
      
          if succ {
              Some((start, gap))
          } else {
              None
          }
      }
      
      #[cfg(test)]
      mod tests {
          use super::*;
      
          #[test]
          fn sad_succeeds() {
              assert_eq!(
                  entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SAD"),
                  Some((10, 8))
              );
          }
      
          #[test]
          fn scam_succeeds() {
              assert_eq!(
                  entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SCAM"),
                  Some((9, 4))
              );
          }
      
          #[test]
          fn gay_succeeds() {
              assert_eq!(
                  entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "GAY"),
                  Some((39, 0))
              );
          }
      
          #[test]
          fn sick_fails() {
              assert_eq!(
                  entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SICK"),
                  None
              );
          }
      }
      
      .gitignore ASCII text
      1
      /target
      
      Cargo.lock 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
      # This file is automatically @generated by Cargo.
      # It is not intended for manual editing.
      version = 3
      
      [[package]]
      name = "cc"
      version = "1.0.83"
      source = "registry+https://github.com/rust-lang/crates.io-index"
      checksum = "f1174fb0b6ec23863f8b971027804a42614e347eafb0a95bf0b12cdae21fc4d0"
      dependencies = [
       "libc",
      ]
      
      [[package]]
      name = "cg48"
      version = "0.1.0"
      dependencies = [
       "cc",
      ]
      
      [[package]]
      name = "libc"
      version = "0.2.150"
      source = "registry+https://github.com/rust-lang/crates.io-index"
      checksum = "89d92a4743f9a61002fae18374ed11e7973f530cb3a3255fb354818118b2203c"
      
      Cargo.toml ASCII text
      1
      2
      3
      4
      5
      6
      7
      [package]
      name = "cg48"
      version = "0.1.0"
      edition = "2021"
      
      [build-dependencies]
      cc = "1.0.83"
      
      build.rs ASCII text
      1
      2
      3
      4
      fn main() {
          println!("cargo:rerun-if-changed=src/impl.c");
          cc::Build::new().file("src/impl.c").compile("impl");
      }
      

      entry #8

      written by luatic
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      entry.ts ASCII text
      1
      export function entry(h:string,n:string):[number,number]|null{for(let g=1;n.length*g<=h.length;++g){const m=RegExp(n.split('').map(c=>(/[.*+?^${}()|[\]\\]/.test(c)?'\\':'')+c).join(`.{${g-1}}`)).exec(h);if(m)return[m.index,--g]}return null}// dis  onli wroks on WIDE CHARS because YES
      

      entry #9

      written by Olivia
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      entry.py ASCII text
      1
      2
      3
      def entry(h,n):import re;r="|".join((i*".").join([f"({n[0]})",*n[1:]])for i in range(len(h)));s=re.search(r,h);return s and(s.start(),s.groups().index(n[0]))#nested loop is shorter
      #like and comment below with your favorite esolang                                                                                                           #long live regis regex
      #dont' forget to ring that [shuffle] button!
      

      entry #10

      written by olive
      submitted at
      0 likes

      guesses
      comments 4
      luatic ¶

      Let's assume the needle of length m is in the haystack of length n. Then there exist an offset o and a gap g such that the needle can be found there. We have g < n/m (since otherwise the needle wouldn't fit). For the offset we then have o < n - gm . Let's pick g around 1/2 n/m. Then we get o < n - 1/2 n = 1/2 n. So we can get o in O(n) and at the same time g in O(n/m).

      Now you've got this beautiful infinite Cantor pairing iterator. How long does it take until we reach the tuple (o, g)? Well, it basically visits the plane in a triangular zig-zag pattern; reaching (o, g) thus takes O(max(o, g)²) = O(n²) many steps.

      But what happens in each step? Well, I'd hope the skip is O(1), at least for a string buffer backed iterator. The rest is however clearly O(m). So I believe we obtain O(n²m), which is not even bad. Nice use of iterators!


      kimapr replying to luatic ¶

      Skip for string -> chars iterators is O(n) because this is utf-8.


      luatic replying to kimapr ¶

      Alright, then we should obtain something like O(n³). Ugh.


      olive ¶

      'beautiful' 🥺

      thanks for your explanation :D can't say I understand the max(o,g)^2…


      post a comment


      dir by-the-gods
      dir src
      lib.rs 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
      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
      struct IterNatPair {
      	next: (usize, usize),
      }
      impl IterNatPair {
      	pub fn new() -> Self {
      		Self { next: (0, 0) }
      	}
      }
      impl Iterator for IterNatPair {
      	type Item = (usize, usize);
      	fn next(&mut self) -> Option<Self::Item> {
      		let next = self.next;
      		self.next = match self.next.0 {
      			0 => (self.next.1 + 1, 0),
      			_ => (self.next.0 - 1, self.next.1 + 1),
      		};
      		Some(next)
      	}
      }
      
      // TODO: If needle isn't in haystack, return None. Currently, we get stuck.
      //       I think this is hard to do without breaking infinite haystacks.
      
      // I'd be interested what time complexity this is, and how you worked it out.
      
      pub fn divine_intellect<T: PartialEq, I: Iterator<Item = T> + Clone>(
      	haystack: I,
      	needle: I,
      ) -> impl Iterator<Item = (usize, usize)> {
      	IterNatPair::new()
      		.filter(|(_, step)| *step != 0)
      		.filter(move |(start, step)| {
      			haystack
      				.clone()
      				.skip(*start)
      				.step_by(*step)
      				.take(needle.clone().count())
      				.eq(needle.clone())
      		})
      }
      
      pub fn entry(haystack: &str, needle: &str) -> Option<(usize, usize)> {
      	divine_intellect(haystack.chars(), needle.chars()).next()
      }
      
      #[cfg(test)]
      mod tests {
      	use super::*;
      
      	#[test]
      	fn iternatpair() {
      		assert_eq!(
      			IterNatPair::new().take(6).collect::<Vec<_>>(),
      			[(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2)],
      		);
      	}
      
      	#[test]
      	fn short() {
      		assert_eq!(entry("hello", "hello"), Some((0, 1)));
      		assert_eq!(entry(" hello", "hello"), Some((1, 1)));
      		assert_eq!(entry("h e l l o", "hello"), Some((0, 2)));
      		assert_eq!(entry(" h e l l o", "hello"), Some((1, 2)));
      		assert!(match entry("abc", "b") {
      			Some((start, _)) => start == 1,
      			None => false,
      		});
      		assert!(match entry("abc", "") {
      			Some((start, _)) => start <= 3,
      			None => false,
      		});
      		matches!(entry("", ""), Some((0, _)));
      	}
      
      	#[test]
      	fn wrong_path() {
      		assert_eq!(entry("ehello", "hello"), Some((1, 1)));
      		assert_eq!(entry("hhello", "hello"), Some((1, 1)));
      		assert_eq!(entry("he hello", "hello"), Some((3, 1)));
      	}
      
      	#[test]
      	fn failure() {
      		assert_eq!(entry("hello", "hi"), None);
      	}
      
      	#[test]
      	fn long() {
      		assert_eq!(
      			entry("abhegggggggggaachjkhfasd h e l l o a", "hello"),
      			Some((25, 2)),
      		);
      	}
      }
      
      Cargo.lock ASCII text
      1
      2
      3
      4
      5
      6
      7
      # This file is automatically @generated by Cargo.
      # It is not intended for manual editing.
      version = 3
      
      [[package]]
      name = "by-the-gods"
      version = "0.1.0"
      
      Cargo.toml ASCII text
      1
      2
      3
      4
      [package]
      name = "by-the-gods"
      version = "0.1.0"
      edition = "2021"
      

      entry #11

      written by theqwertiest
      submitted at
      0 likes

      guesses
      comments 0

      post a comment


      bible.zig 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
      const std = @import("std");
      pub fn entry(haystack: []const u8, needle: []const u8) ?struct{usize, usize}
      {
      	if (needle.len == 0)
      	{
      		return null;
      	}
      
      	var locations: [256]std.ArrayList(usize) = undefined;
      	for (locations[0..]) |*point|
      	{
      		point.* = std.ArrayList(usize).init(std.heap.page_allocator);
      	}
      	for (haystack, 0..) |character, index|
      	{
      		locations[character].append(index) catch @panic("Error.");
      	}
      	const first_character = needle[0];
      	if (needle.len == 1)
      	{
      		if (locations[first_character].items.len > 0)
      		{
      			return .{
      				locations[first_character].items[0],
      				0,
      			};
      		}
      		return null;
      	}
      	for (locations[first_character].items[0..]) |index|
      	{
      		const second_character = needle[1];
      		for (locations[second_character].items[0..]) |index_two|
      		{
      			const gap = index_two -| index;
      			if (gap == 0)
      			{
      				continue;
      			}
      			const index_last = index + gap * (needle.len -| 1);
      			if (index_last >= haystack.len)
      			{
      				continue;
      			}
      			for (2..needle.len) |index_nth|
      			{
      				const haystack_pos = index + gap * index_nth;
      				if (needle[index_nth] != haystack[haystack_pos])
      				{
      					break;
      				}
      			}
      			else
      			{
      				return .{
      					index,
      					gap,
      				};
      			}
      		}
      	}
      	return null;
      }
      pub fn main() !void
      {
      	std.debug.print("{?}, {?}, {?}, {?}\n", .{
      		entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SAD"),
      		entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SCAM"),
      		entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "GAY"),
      		entry("THISBOOKISSOFUCKINGAWESOMEANDIAMTOTALLYGAY", "SICK"),
      	});
      }