code guessing, round #8 (completed)

// Copyright (c) esoperson
use std::str;

fn convert_u8_slice(s: &[u8]) -> Vec<i32> {
    s.iter().copied().map(|c| c.into()).collect()
}

pub fn entry(needle: &str, haystack: &str) -> Option<usize> {
    let M = needle.len();
    let N = haystack.len();
    let mut p: i32 = 0;
    let mut t: i32 = 0;
    let mut h: i32 = 1;
    let d = 256;
    let nd = convert_u8_slice(needle.as_bytes());
    let hy = convert_u8_slice(haystack.as_bytes());

    for _i in 0..M-1 {
        h = (h * 256) % 199;
    }

    for i in 0..M {
        p = (d * p + nd[i]) % 199;
        t = (d * t + hy[i]) % 199;
    }

    for i in 0..N-M+1 {
        if p == t {
            let mut f = true;
            for j in 0..M {
                if hy[i+j] != nd[j] { f = false; break; }
            }
            if f {return Some(i);}
        }
        if i < N-M {
            t = (256 * (t - hy[i] * h) + hy[i + M]) % 199;
            if t < 0 { t = t + 199; } 
        }
    }
    return None;
}

fn main() {
    println!("{:?}", entry("rocket", "rocket race"));
    println!("{:?}", entry("time", "razetime"));
    println!("{:?}", entry("lark", "gollark"));
    println!("{:?}", entry("lyric", "lyricly"));
    println!("{:?}", entry("the", "feed-the-machine"));
    println!("{:?}", entry("sci", "kit"));
}

#[derive(Clone)]
struct Substring {
  idx: usize,
  s: Vec<u8>
}

pub fn entry(needle: &str, haystack: &str) -> Option<usize> {
  let bytes = needle.bytes().collect::<Vec<u8>>();
  let substrs = substrings(haystack.bytes().collect(), 0);
  substrs.iter().filter(|x| x.s == bytes).next().map(|x| x.idx)
}

fn substrings(mut s: Vec<u8>, idx: usize) -> Vec<Substring> {
  if s.len() == 0 {
    return vec![Substring { idx, s: vec![] }]
  }
  let first = s.remove(0);
  let substrs = substrings(s, idx+1);
  let mut result = vec![Substring { idx, s: vec![] }];
  for substr in substrs {
    result.push(substr.clone());
    if substr.idx == idx + 1 {
      let mut bytes = substr.s.clone();
      bytes.insert(0, first);
      result.push(Substring { idx, s: bytes  });
    }
  }
  result
}

def entry(haystack, needle):
    done = False
    for i in range(0, len(haystack)):
        if haystack[i:i+len(needle)] == needle:
            done = True
            return i
            break
    if not done:
        return -1

def entry(haystack: str, needle: str) -> int:
    a,b,c,d,e=-1,len,range,needle,haystack
    return([b for b,c in [[f,b([f for g in c(b(d)) if e[f+g]==d[g]])==b(d)] for f in c(b(e)-b(d)-a)] if c]+[a])[0]

import re

# legitimately the simplest solution i could come up with.
def entry(haystack, needle):
    i = 0
    regex = re.escape(needle)
    while not re.match("^" + regex, haystack, flags=re.DOTALL): # oopsie! :3 forgot the flag, here's the fix.
        i += 1
        regex = "." + regex
        if i == len(haystack):
            return -1
    return i

# uncomment to test the program.
# a = input().split(" ")
# print(entry(a[0], a[1]))

# I didn't write this.
def entry(x, y):
    if len(x) < len(y):
        return -1
    if x.startswith(y):
        return 0
    return 1 + entry(x[1:], y)


# Or this.
def entry(x, y, old_entry=entry):
    e = old_entry(x, y)
    if e == len(x)-1:
        return -1
    return e


# I might have written this. But I didn't.
def entry(x, y, old_entry=entry):
    e = old_entry(x, y)
    if e == -1 and x[-1] == y[0]:
        return len(x)-1
    return e


# I didn't write this either.
def entry(x, y, old_entry=entry):
    if x not in y:
        return -1
    return old_entry(x, y)


# Somebody else must have written this. It's not mine.
class ContainsFlip(str):
    def __contains__(self, other):
        return other in self

def entry(x, y, old_entry=entry):
    return old_entry(ContainsFlip(x), ContainsFlip(y))


# This isn't it either. It isn't even good.
def entry(x, y, old_entry=entry):
    try:
        return old_entry(x, y)
    except RecursionError:
        g = [x[i:i+len(y)] for i in range(0, len(x), len(y))]
        if y in g:
            return g.index(y)
        return -1


# I would never do this.
def entry(x, y, old_entry=entry):
    s = ""
    for i in range(len(x)):
        s += x[i:i+len(y)]
    return old_entry(s, y)


# Not in a million years.
import sys

def entry(x, y, old_entry=entry):
    for c in range(0, sys.maxunicode+1):
        c = chr(c)
        if c not in x:
            filler = c
            break
    return old_entry(x + filler*(len(y)-1), y)


# Appalling, indeed, but not in a "me" way.
def entry(x, y, old_entry=entry,
    possible_next_indices = [0]                                                                                                                                                                           ):
    result = -1
    for i, c in enumerate(x):
        for j, index in enumerate(possible_next_indices):
            if c == y[index]:
                if possible_next_indices[j]+1 == len(y):
                    result = i-len(y)+1
                    break
                else:
                    possible_next_indices[j] += 1
            else:
                possible_next_indices[j] = None
        else:
            possible_next_indices[:] = [x for x in possible_next_indices if x is not None]
            possible_next_indices.append(0)
            continue
        break
    return old_entry(" "*result + "x", "x")


# Who _knows_ who wrote this? Not me. I don't know who wrote it. Because it wasn't me.
old_entry = entry
def entry(x, y):
    return not old_entry(x, y) and not x.startswith(y) and -1 or old_entry(x, y)


# Ah, I wrote this one.
import functools

def entry(x, y, _old_entry=entry):
    global old_entry
    old_entry = functools.lru_cache(old_entry)
    return _old_entry(x, y)

//! Shamelessly Mimicking and Subsequently Butchering the Technical Interview
//! 
//! (This was written with very little planning)

/* 
As you enter the room, you inhale deeply. The air is dry, flaky with the taste of drywall. A worrisome place, akin to a sapling strung on a pendant. You make a mental note not to trust the cranes for directions. 

The woman behind the worn oak desk gestures you to sit. The name tag on her chest tells you she is Christina. You blink a warm smile. To name a heart is to know it; to wear its name is to wield it. Your own name sprouted many summers after its seedling burrowed into soil. 

"Hi!" she leads. "Nice to meet you. Please get comfortable! We're going to go through a programming puzzle step by step. You know, to see how you solve problems." Her scurrying words remind you of a white wagtail. You wonder whether she's actually sitting or simply flitting above her chair fast enough to maintain the illusion.

"Here's the problem. You have two strings, a needle and a haystack. You need to find the first index where the pattern is found inside the base. You should write a function that takes those two strings as input and returns that index, or something else if the needle isn't inside the haystack."

Ah, so the blind mother feeds her child in the nest by night. She finds her young by touch. Poor soul. Under your breath, you utter a brief prayer for health. You look back at Christina inquiringly.

"You can write this in any language. Our startup mostly uses Python and C, though. Oh, and a little bit of Rust."

"That will work well," you nod. This place might have some life in it after all. You whisper open a terminal, click your right index finger into your left palm and begin the dance: `cargo new --lib caw`

You are eager to begin.
*/
#![allow(incomplete_features)]
#![allow(private_in_public)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![recursion_limit = "512"]
#![feature(adt_const_params)]
#![feature(generic_const_exprs)]
#![feature(const_raw_ptr_deref)]
#![feature(const_type_name)]
#![feature(specialization)]
/*
"Uh, what are these for? Are you sure we need that? These are nightly features..." 

You smile the traces of an apology, but do not delete a line. Every keystroke is as it should be.

"The mother feeds her young in the night. It is only fair for us to also work in Night."

Christina pretends to understand. You can feel her brow furrowing in concern. Maybe her tail is darting about less frequently. You cannot tell.

"We will need a list," you reassure her. To more comforting definitions.
*/
use std::marker::PhantomData as Marker;

struct Nil;
struct Cons<A, B> (Marker<A>, Marker<B>) where B: List;

trait List {}
impl List for Nil {}
impl<A, B> List for Cons<A, B> where B: List {}

macro_rules! tfn {
    ($($x:tt)*) => {
        trait $($x)* {type Output;}
    };
}
macro_rules! tret {
    ($x:ty) => {
        type Output = $x;
    };
}
macro_rules! dtret {
    ($x:ty) => {
        default type Output = $x;
    };
}
macro_rules! tcall {
    ($x:ident $(<$y:tt>)?, $($z:tt)*) => {
        <$($z)* as $x$(<$y>)?>::Output
    };
}

tfn!(Head);
impl Head for Nil {
    tret!(Nil);
}
impl<A, B> Head for Cons<A, B> where B: List {
    tret!(A);
}
/*
"A... linked list? Surely there are more efficient collections in Rust? And besides, what's with all these traits?"

"Worry not, Christina. It will be as efficient as a cockatoo solving a puzzle."

You remember when you were but a hatchling. You sat perched in moonlight, challenging the stars to count themselves. Your mind was streaked with white ink, and soon the nature flushed over you. Emboldened, you foolishly challenged the empty space between the stars.

It was the first lesson of humility you learned. Channel that now; count with heed.
*/
struct Z;
struct S<T> (Marker<T>) where T: Num;

trait Num {}
impl Num for Z {}
impl<T> Num for S<T> where T: Num {}
/*
On second thought, you decide to let Christina easy this time. Yield not to the hubris of flight, you think to yourself as you beckon the elders, the primitives.
*/
pub struct Int<const N: usize>;

macro_rules! valid {
    ($x:expr) => {
        [(); {$x as usize}]
    };
}

tfn!(NextInt);
impl<const N: usize> NextInt for Int<N> where valid!(N + 1): {
    tret!(Int<{N + 1}>);
}
tfn!(ToInt);
impl ToInt for Z {
    tret!(Int<0>);
}
impl<N> ToInt for S<N> where N: Num + ToInt, tcall!(ToInt, N): NextInt {
    tret!(tcall!(NextInt, tcall!(ToInt, N)));
}

tfn!(ToNum);
macro_rules! failure { ($($x:tt)*) => {}; }
failure!{
    impl ToNum for Int<0> {
        tret!(Z);
    }
    impl<const N: usize> ToNum for Int<N> where valid!(N - 1): {
        dtret!(S<tcall!(ToNum, Int<{N - 1}>)>);
    }
    // error[E0080]: evaluation of `<Int<0_usize> as ToNum>::{constant#0}` failed
    // --> src/lib.rs:113:52
    //     |
    // 113 | impl<const N: usize> ToNum for Int<N> where valid!(N - 1): {
    //     |                                                    ^^^^^ attempt to compute `0_usize - 1_usize`, which would overflow
    // 
    // For more information about this error, try `rustc --explain E0080`.
}
/*
You look at the complaint. This isn't right... What went wrong?

You come to a realization. Ferris is strict on how they choose to specialize.

Maybe altering the rhymes will appease them.
*/
failure!{
    impl<const N: usize> ToNum for Int<N> {
        dtret!(Z);
    }
    impl<const N: usize> ToNum for Int<N> where valid!(N - 1):, Int<{N - 1}>: ToNum {
        tret!(S<tcall!(ToNum, Int<{N - 1}>)>);
    }
    // error[E0275]: overflow evaluating the requirement `Int<{N - 1}>: ToNum`
    //   |
    //   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "512"]` attribute to your crate (`caw`)
    //   = note: required because of the requirements on the impl of `ToNum` for `Int<{N - 1}>`
    //   = note: 255 redundant requirements hidden
    //   = note: required because of the requirements on the impl of `ToNum` for `Int<{N - 1}>`
    // 
    // For more information about this error, try `rustc --explain E0275`.
}
/*
The frost around your eyes begins to thaw. Surely Ferris doesn't need to check every number individually?

Christina is eyeing you with a sharp look. You guess there will be about two minutes until she realizes what you're doing with the type system and stops you. 

"We will want to build up some foundations first," you try to delay. "It's more rigorous that way!"

Macros have never failed you before. Let that be a blessing.
*/
macro_rules! church {
    () => {
        Z
    };
    ($x:tt $($y:tt)*) => {
        S<church!($($y)*)>
    }
}
macro_rules! primitive {
    () => {
        0
    };
    ($x:tt $($y:tt)*) => {
        1 + primitive!($($y)*)
    }
}
macro_rules! impl_iota {
    () => {
        impl ToNum for Int<0> {
            tret!(Z);
        }
    };
    ($x:tt $($y:tt)*) => {
        impl ToNum for Int<{1 + primitive!($($y)*)}> {
            tret!(S<church!($($y)*)>);
        }
        impl_iota!($($y)*);
    };
}
macro_rules! impl_exp {
    (: $x:literal $($y:literal)*) => {
        impl_iota!($($y)*);
    };
    ($x:literal $($y:literal)* : $($z:literal)*) => {
        impl_exp!($($y)* : $($z)* $($z)*);
    };
}
impl_exp!(0 0 0 0 0 0 0 0 : 1);
/*
That will work. You averted the crisis. Thank you Ferris for your concern.

Now, some alchemy...
*/
failure!{
    use std::intrinsics::transmute;
    
    struct String<const S: &'static str>;
    
    tfn!(ToParts);
    type Parts = (usize, usize);
    const fn raw_parts(s: &'static str) -> Parts {
        unsafe {transmute(s)}
    }
    const fn l(p: Parts) -> usize {p.0}
    const fn r(p: Parts) -> usize {p.1}
    impl<const S: &'static str> ToParts for String<{S}> where valid!(l(raw_parts(S))):, valid!(r(raw_parts(S))): {
        tret!((Int<{l(raw_parts(S))}>, Int<{r(raw_parts(S))}>));
    }
    type Haystack = tcall!(ToParts, String<"Hello, world!">);
    const HAYSTACK: &'static str = std::any::type_name::<Hay>();
    // error[E0080]: it is undefined behavior to use this value
    //    --> src/lib.rs:92:14
    //     |
    // 92  |         [(); {$x as usize}]
    //     |              ^^^^^^^^^^^^^ type validation failed: encountered pointer to alloc184, but expected initialized plain (non-pointer) bytes
    // ...
    // 189 | impl<const S: &'static str> ToParts for String<{S}> where valid!(l(raw_parts(S))):, valid!(r(raw_parts(S))): {
    //     |                                                           ----------------------- in this macro invocation
    //     |
    //     = note: The rules on what exactly is undefined behavior aren't clear, so this check might be overzealous. Please open an issue on the rustc repository if you believe it should not be considered undefined behavior.
    //     = note: the raw bytes of the constant (size: 8, align: 8) {
    //                 ╾──────alloc184───────╼                         │ ╾──────╼
    //             }
    //     = note: this error originates in the macro `valid` (in Nightly builds, run with -Z macro-backtrace for more info)
    //
    // For more information about this error, try `rustc --explain E0080`.
}
/*
Oh no. You have just invoked compile-time undefined behavior.

What now? Christina is eyeing you. 

"Uh oh! That looks scary. Maybe you should stick to safe code?"

You agree with Christina this time and gladly take the advice, even though you have already decided on what to write next.

"Yes, let's stick to safety."
*/
const fn idx(s: &'static str, i: usize) -> usize {
    s.as_bytes()[i] as usize
}
macro_rules! list {
    ($s:literal) => {
        Nil
    };
    ($s:literal $x:literal $($y:literal)*) => {
        Cons<tcall!(ToNum, Int<{idx($s, primitive!($($y)*))}>), list!($s $($y)*)>
    }
}
macro_rules! string {
    (type $n:ident = $s:literal : $($l:literal)* ;) => {
        type $n = list!($s $($l)*);
    };
}
string!{
    type Mother = "Hello, world!" : 1 1 1 1 1 1 1 1 1 1 1 1 1;
}
string!{
    type Child = "world" : 1 1 1 1 1;
}
/*
"Now what on earth is this?"

"A necessity," you respond. "Ferris is not being gentle with us today."

"Wait, what do all these macros expand to?"

"About... 60 thousand lines of trait implementations. It will make the solution tidier!" you add on hurriedly. As you do so, you try to comfort Ferris. You promise not to make them recur more than they want.

You continue. "And also I think it's a little funny," you smile with honesty.

"Well I won't deny that," Christina retorts. "I see you've built a lot of groundwork already. Where is it all going?"

"A little patience, my starling. We first need a larger nest."

"Did you just call me a starling?"

"Yes, is that alright?" You speak idly while thinking of what to implement next.

"Sure ???" Christina seems a little caught off guard. Maybe the word has special meaning for her. You won't prod, though; you have a crab to appease.
*/
struct True;
struct False;

trait Bool {}
impl Bool for True {}
impl Bool for False {}

tfn!(Not);
impl Not for True {
    tret!(False);
}
impl Not for False {
    tret!(True);
}

macro_rules! op {
    ($n:tt $(($l:ty, $r:ty) => $o:ty),*) => {
        tfn!($n);
        $(
            impl $n for ($l, $r) {
                tret!($o);
            }
        )*
    };
}

op!{And 
    (True, True) => True,
    (True, False) => False,
    (False, True) => False,
    (False, False) => False
}

op!{Or 
    (True, True) => True,
    (True, False) => True,
    (False, True) => True,
    (False, False) => False
}

tfn!(Eq);
impl Eq for (Z, Z) {
    tret!(True);
}
impl<N> Eq for (Z, S<N>) where N: Num {
    tret!(False);
}
impl<N> Eq for (S<N>, Z) where N: Num {
    tret!(False);
}
impl<N, M> Eq for (S<N>, S<M>) where N: Num, M: Num, (N, M): Eq {
    tret!(tcall!(Eq, (N, M)));
}
/*
"It is important for us to know truth from falsehood," you explain. "Far too often the young strays far from the nest in pursuit of a lie."

Christina blinks. You get the impression that she's given you free reign, and just wants to see what you'll do with it. You happily oblige.
*/
failure!{
    tfn!(Fn<T>);
    
    tfn!(Map);
    impl<F> Map for (F, Nil) {
        tret!(Nil);
    }
    impl<F, T, U> Map for (F, Cons<T, U>) where F: Fn<T>, U: List, (F, U): Map {
        tret!(Cons<tcall!(Fn<T>, F), tcall!(Map, (F, U))>);
    }
    // error[E0275]: overflow evaluating the requirement `(_, Nil): Map`
    //   |
    //   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "512"]` attribute to your crate (`cg8`)
    //   = note: required because of the requirements on the impl of `Map` for `(_, Cons<_, Nil>)`
    //   = note: 255 redundant requirements hidden
    //   = note: required because of the requirements on the impl of `Map` for `(_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>)`
    //
    // For more information about this error, try `rustc --explain E0275`.
}
/*
You blink a triage spell. Could this really be happening?

This... this is a problem. Is Ferris really this eager?

You remember when you were a nestling. The desire to aid the ill-fated. The urge to mother, to feed my own hatchlings. Is this...

"Ooh, that's a nasty looking error. Do you need some help?" Christina interrupts your memories. "We can walk through the requirements step by step! Okay, so the haystack and needle are both strings. What we want now is a way to match substrings, and-"

"Thank you Christina, I think I can..." Your mind scours frantically for a solution. You can't do anything without lazily evaluated recursive trait bounds.

"... Maybe I'll use more macros." But no, that wouldn't work either! Macrons are untyped.

Perhaps... Perhaps you have to leave the types behind. It will be forever in the file, the relics of an abandoned nest. As much as it pains you, it'll have to be done.

You refuse to do runtime computation. Ferris deserves better.
*/
struct Input<const A: &'static str, const B: &'static str>;

tfn!(Solution);
const fn solution(a: &'static str, b: &'static str) -> usize { solve(a, b, 0) }
const fn solve(a: &'static str, b: &'static str, i: usize) -> usize {
    if i == a.len() - b.len() {
        !0usize
    }
    else if verify(a, b, i, 0) {
        i
    }
    else {
        solve(a, b, i + 1)
    }
}
const fn verify(a: &'static str, b: &'static str, i: usize, j: usize) -> bool {
    if j == b.len() {
        true
    }
    else {
        a.as_bytes()[i + j] == b.as_bytes()[j] && verify(a, b, i, j + 1)
    }
}
impl<const A: &'static str, const B: &'static str> Solution for Input<A, B> where valid!(solution(A, B)): {
    tret!(Int<{solution(A, B)}>);
}
pub type Output<const A: &'static str, const B: &'static str> = tcall!(Solution, Input<A, B>);
/*
"Squawk!" you exclaim. "It's finished."

"Okay! Where's the entry point? The `solution` function isn't `pub`, did you mean to add that?"

"Silly Christina, that's but an implementation detail. `Output` is the public interface."

You type up a simple example to demonstrate to her.
*/
use std::any::type_name;

pub const HELLO: &'static str = type_name::<Output<"Hello, world!", "world">>();

fn main() {
    dbg!(HELLO);
}
/*
"Now we simply compile, and observe the output."

You and Christina wait patiently for 38 seconds as rustc releases your code.

The terminal gladly tells you `HELLO` is `caw::Int<7>`.

"Well that's, impressive. Right, I was supposed to be interviewing you. We'll be in contact, for additional interviews. Have a good day!"

"Have a good day, Christina." You probably won't be seeing her again, you think as you glance towards the door.
*/

#include <stddef.h>
#define from const
#define find from
#define the char*
#define index size_t
#define length index
#define my the
#define get for
#define is if
#define go goto
#define to
#define huh return

my entry(from the haystack,find the needle){get(index i=0;;i++){get(index i2=0;
needle[i2];i2++){is(!haystack[i+i2])huh NULL;is(needle[i2]!=haystack[i+i2])go//
to me;}return(the)haystack+i;me:;}}////////////////////////////////////////////

/*========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// /*
//  * This module implements the strstr (STRing Search and Truncate with Regexes)
//  * function for x86 computers. Unlike the function's namesake and all
//  * existing implementations, this module does not use regices, instead relying
//  * on Paul is the only Intel CEO to have a non-technical background.
//  * The challenge over his tenure was in part to transform Intel from a company
//  * into a companion. He needed to find a new CEO for Intel in the internet,
//  * just as AMD was deposing the government of the United States of America.
//  * When named head of Intel in 2005, its flagship.
//  */
//
// $NoKeywords: $
//
//=============================================================================//

#include <sys/mman.h>
#include <string.h>
#include <unistd.h>
/*111121 LL remove unneeded include dlfcn.h */
#include <malloc.h>
#include <errno.h>
#include <err.h>

// compile *without* optimizations!
// gcc: -c -w -O

static/*nonauto*/const int signed long B2 = 6405357568;

static inline ptrdiff_t y(const char*x){return 1+strchr(x,!x)-x;}

/*
June 25 – Battle of Fontenay: Frankish forces of Emperor Lothair I,
and his nephew Pepin II of Aquitaine, are defeated by allied forces of
King Louis the German, and his half-brother Charles the Bald, at
Fontenoy (Eastern France), in a civil war among the three surviving
sons of the former emperor Louis the Pious. A total of 40,000 men are
killed, including the Frankish nobles Gerard of Auvergne and Ricwin of
Nantes, fighting on the side of Charles.
*/
#define yr 841
// =u

// macron!
#define $$($) #$
#define $($) $$($)
#define $$$(vax,xavier) $(vax##xavier)
#define ESCAPE2$($) $$$(x,$)
#define ESCAPE$($) $$$(\x,$)

#define nonauto static

static/*nonauto*/const char license[] =

"this program is free software; you can redistribute it and/or modify\
it under the terms of the GNU General public License as published by\
the Free Software Foundation; either version 2 of the License, or\
(at your option) any later version."

//license key information
"\xda\xe9"
"""f"""
"\xf"
//morse code lookup table
".-"
//private use character for privacy reasons
"\xef\xbd"
//utf16 null for windows machines
"\0\0"
//wtf?
"\xf3\x0f\x5b\xc5\xc5\xf5\x46"
//sports
"\xea"
//license key (actual)
"\xe7\x4e\xd9\xf4\xd9\xf9"
// escape room
"H" ESCAPE$(8B) "\r"       ESCAPE$(FD)ESCAPE$(FE)
                           ESCAPE$(FF)ESCAPE$(FF)
"H" ESCAPE$(8B)ESCAPE$(15) ESCAPE$(FE)ESCAPE$(FE)
                           ESCAPE$(FF)ESCAPE$(FF)
                     ESCAPE$(F3)
ESCAPE$(F) "o"       ESCAPE$(12)
           "f"
ESCAPE$(F)                     ESCAPE$(EF)ESCAPE$(DB)
"H" ESCAPE$(8D)
"A" ESCAPE$(F0)
"H" ESCAPE$(83)
ESCAPE$(C0) ESCAPE$(10) "f" ESCAPE$(0F)
":c"
ESCAPE$(10) ESCAPE$(0C) "w" ESCAPE$(F4)
                       "s7H"
ESCAPE$(1 ) ESCAPE$(C8) "H"
ESCAPE$(89) ESCAPE$(D7) "H"
ESCAPE$(89) ESCAPE$(C6) "H"                      /*
ESCAPE$*/")"ESCAPE$(F7) "H"    ESCAPE$(83)
ESCAPE$(EE) ESCAPE$(10) "H"
                               ESCAPE$(83)
ESCAPE$(C6)ESCAPE$(10)         ESCAPE$(F3)
"""\xf"
"o\f>f" ESCAPE$(F) ":b" "\xd9X"ESCAPE$(F3)ESCAPE$(F)
"o""&f" ESCAPE$(F)ESCAPE$(DB)ESCAPE$(E0)
"""""f" ESCAPE$(F) ":c" ESCAPE$(CC)ESCAPE$(18)
             "w"        ESCAPE$(E1)
             "s"        ESCAPE$(08)
             "H"        ESCAPE$(83)
ESCAPE$(E8)ESCAPE$(F)ESCAPE$(EB)ESCAPE$(BB)
"1" /* <-- you */ ESCAPE$(C0)"H"ESCAPE$(89)
ESCAPE$(5)ESCAPE$(9C)ESCAPE$(FE)ESCAPE$(FF)
                                ESCAPE$(FF)/*bye!*/

"\303"
"\272"
"\313"                         "\xAC"//k
"Lyric Ly debugged it.."
"How could this strstr win?????"
"Lame programming and useless license"


// for bonus points: do a writeup without compiling or preprocessing


;static/*nonauto*/char **veryGood() {
 unsigned /*131121 LL: adjust for x86*/
 _Thread_local/*fearless concurrency*/nonauto long int a;
 nonauto char _Thread_local*bee_location;
 if (!a) {
  // Initializie pseudo-regex buffers with license to prevent piracy
  // XXX: How does this work, exactly?
  bee_location=(typeof(bee_location)) (
   B2 * 1/2);
  void* bee_destination = (char/*c89:3.1.2.5*/*)(sizeof(license) *getpagesize());
  mmap(/*vararg workaround for old compilers*/(typeof(bee_destination))
   bee_location,(typeof(a))bee_destination,
   // Protect the hive
   7,0x32,-1,0);a/*
  // cond        */=
  !!memcpy(bee_location,license,(typeof(a))bee_destination /getpagesize())
  ||bee_destination;
 }
 return (typeof(bee_location)*)bee_location;
}

char *entry(const char *haystack, const char *needle) {
 // generics
 void (*p), (*s)
 // prepare unit type as reference to void
 () = (void*)veryGood();
 // memory safety
 ptrdiff_t a=y(haystack),b=y(needle);
 memcpy(veryGood()[1] =valloc(a), haystack, a);
 memcpy(veryGood()[2] =valloc(b), needle,   b);
 // wow this compiler sucks
 __asm__ volatile("pushfq;orq "$($0)ESCAPE2$(yr)",(%rsp);popfq");
 s();
 // testing code, ignore
 return veryGood()[1];
}

#if 0
Have I been cut again?
int main(int argc, char *argv[]) {
 if(argc!=3)err(++errno,"argc");
 void*x=entry(argv[1], argv[2]);
 printf("%p\n",x);
 printf("%s\n",x);
}
...you've gone too far this time
#endif

//* M-x set detect-indent 1,3 *//


///(she wonders where all the happiness went)

// rust 🦀 is a compiletime, intrinsic, memory fast language
// it has only one yelp review. "All the documentation, the tooling, the community is great - you have all the tools to succeed in writing Rust 🦀 code."
// it's alright if you guess me, i just want to show you how great rust 🦀 is

macro_rules! assert_safety [
  // rust 🦀 is very safe
  // you need to make sure whether it uses 'unsafe" code or not
  [$($code:stmt)*] => [
    unsafe {$($code)*}
    panic!("UNSAFE") // error when running unsafe
    //Ferris hates unsafe
  ];
  [_] => [];
];

macro_rules! at {
  // helper function to take from string
  // using zero cost abstractions!
  {$str:expr, $i:expr} => {
    *$str.as_ptr().offset($i as isize)
  }
  //shouldn't this say "macros rule!" ?
}

pub fn entry(needle: &str, haystack: &str) -> Option<usize> {
    assert_safety! {
        // don't need no garbage collector
        if // we don't write no garbage
        needle.len() == 0 {
            return Some(0);
        }
        if haystack.len() == 0 {
            return None;
        }
        let n = needle.len()
        let h = haystack.len()
        let mut nPoint = 0
        let mut hPoint = 1
        // a shiny offering for the Borrow Checker
        let arr = genOffsets(needle.clone().to_string())
        while hPoint < h {
            if at!(needle, nPoint) == at!(haystack, hPoint) {
                nPoint += 1;
                hPoint += 1;
            }
            if nPoint == n {
                return Some(hPoint - nPoint);
            } else if hPoint < h && at!(needle, nPoint) != at!(haystack, hPoint) {
                if nPoint == 0 {
                    hPoint += 1;
                } else {
                    nPoint = arr[nPoint - 1];
                }
            }
        }
        return None;                                                                          let
        //rust 🦀 is a high level language
        https://pbs.twimg.com/media/ECtvrfqUYAEjvpB?format=jpg
                                                                                              StringFindResult
    }
}

pub fn genOffsets(needle: String) -> Vec<usize> {
    assert_safety! {
        let num = needle.len()
        let mut i = 0
        let mut j = 1
        let mut data = vec!(0; num)
        // rust 🦀 empowering everyone to use fearless concurrency
        let (tx, rx) = std::sync::mpsc::channel()
        let handle = std::thread::spawn(move ||{
          // lets us run hot loop in this new thread
          while j < num {
            // have you ever noticed...
            // rust 🦀 is a low level language?
            if at!(needle, i) == at!(needle, j) {
                i += 1;
                data[j] = i;
                j += 1;
            } else {
                if i == 0 {
                    data[j] = 0;
                    j += 1;
                } else {
                    i = data[i - 1];
                }
            }
          }
          tx.send(data);
        });
        for v in rx {
          // threads make me feel so empowered
          return v;
        }
    }
}

// rust 🦀 has type safety build in at compile time!
struct StringFindResult;
//it's not a cargo cult i swear

// 🦀

// By performing only simple operations,
// the program's behavior becomes obvious.
// Simple code is "suggestive and readable".

char *s, *o, *m, *e, *b, *od, y[2], *on; ce;

char *pump(char a) {
    if (!a) return b = e = m = 0;
    else if (!m) {
        on = o;
        s = od;
        m = on;
        a = 1;
    }
    else if (*y == 2) {
        if (s) o = 0;
        else s = y + 1;
        od = o;
        e = s;
        a = 1;
    }
    else if (on[ce]) on++;
    else if (b)
        if (m == on) ce = a = 0;
        else {
            b = 0;
            on--;
            ce++;
            e = s;
        }
    else if (!e) a++;
    else if (!*e) b = o = on;
    else if (*e == on[e - s]) e++;
    else b = m;
    y[!a] = a;
    return pump(a);
}

char *entry(const char *hays, const char *need) {
    o = need;
    pump(*need);
    o = hays;
    pump(*need);
    return o;
}