merge mzuenni changes

3 files changed, 212 insertions, 1 deletions

diff --git a/content/graph/2sat_amo.cpp b/content/graph/2sat_amo.cpp
new file mode 100644
index 0000000..d50e77d
--- /dev/null
+++ b/content/graph/2sat_amo.cpp
@@ -0,0 +1,38 @@
+constexpr int var(int i) {return i << 1;} // use this!
+struct sat2 {
+	int n; // + scc variablen
+	vector<int> sol;
+	sat2(int vars) : n(vars*2), adj(n) {}
+
+	void addImpl(int a, int b) {
+		adj[a].push_back(b);
+		adj[1^b].push_back(1^a);
+	}
+	void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);}
+	void addOr(int a, int b) {addImpl(1^a, b);}
+	void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);}
+	void addTrue(int a) {addImpl(1^a, a);}
+	void addFalse(int a) {addTrue(1^a);}
+	void addAnd(int a, int b) {addTrue(a); addTrue(b);}
+	void addNand(int a, int b) {addOr(1^a, 1^b);}
+
+	bool solve() {
+		scc(); //scc code von oben
+		sol.assign(n, -1);
+		for (int i = 0; i < n; i += 2) {
+			if (idx[i] == idx[i + 1]) return false;
+			sol[i] = idx[i] < idx[i + 1];
+			sol[i + 1] = !sol[i];
+		}
+		return true;
+	}
+};
+void atMostOne(const vector<ll>& vars) {
+	int k = n / 2;
+	n += 2 * sz(vars);
+	adj.resize(n);
+	for (int i = 0; i + 1 < sz(vars); i++) {
+		addImpl(vars[i], var(k+i));
+		addImpl(var(k+i), var(k+i+1));
+		addImpl(var(k+i), vars[i+1] ^ 1);
+}}
diff --git a/content/math/math.tex b/content/math/math.tex
index 1bcf85d..97b6a24 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -438,7 +438,7 @@ $1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
 	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.
 \end{itemize}
 \[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
-\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]
+\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} \cdot C^k_{n-1}\]
 
 \paragraph{\textsc{Euler}-Zahlen:}
 $|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$
diff --git a/tcrracer/tcrracer.py b/tcrracer/tcrracer.py
new file mode 100755
index 0000000..dad3772
--- /dev/null
+++ b/tcrracer/tcrracer.py
@@ -0,0 +1,173 @@
+#!/usr/bin/env python3
+
+import argparse
+import colorama
+import os
+import random
+import signal
+import string
+import subprocess
+import sys
+import tempfile
+import threading
+import time
+import token
+import tokenize
+
+from colorama import Fore, Style
+from difflib import SequenceMatcher
+from pathlib import Path
+
+location = Path(sys.argv[0]).parent
+content = location / ".." / "content"
+
+default_patterns = {
+    "cpp": ["*.cc", "*.C", "*.cpp", "*.cxx", "*.c++"],
+    "py": ["*.py", "*.py2", "*.py3", "*.cpy"],
+    "java": ["*.java"],
+}
+
+colorama.init()
+clear = "\033[K"
+
+def interrupt_handler(sig, frame):
+    print(f"\n{clear}{Fore.RED}aborted{Style.RESET_ALL}")
+    os._exit(1)
+
+signal.signal(signal.SIGINT, interrupt_handler)
+
+parser = argparse.ArgumentParser(description="TCR-Racer is a game to train your TCR typing ability.")
+parser.add_argument("-p", dest="penalty", default="60", type=int, help='The penalty for "submitting" wrong code (in seconds)')
+parser.add_argument("--patterns", default=None, nargs="+", help=f"Patterns to check which files in '{content}' should be considered")
+for name, pattern in default_patterns.items():
+    pattern_text = ",".join(pattern)
+    parser.add_argument(f"--{name}", action="store_true", help=f"add {name} pattern ({pattern_text})")
+parser.add_argument("--debug", action="store_true", help="Show debug information")
+args = parser.parse_args()
+
+selected_default_patterns = []
+for name, pattern in default_patterns.items():
+    if getattr(args, name):
+        selected_default_patterns += pattern
+if selected_default_patterns:
+    args.patterns = (args.patterns or []) + selected_default_patterns
+
+def matches_pattern(f):
+    if args.patterns is None:
+        return True
+    return any(f.match(p) for p in args.patterns)
+
+files = [f for f in content.rglob("*") if f.is_file() and f.suffix not in [".tex", ".sty"]]
+filtered = [f for f in files if matches_pattern(f)]
+print(f"Found {len(filtered)} matching files.")
+if not filtered:
+    sys.exit(1)
+selected = random.choice(filtered)
+
+language = "unknown"
+for name, pattern in default_patterns.items():
+    if any(selected.match(p) for p in pattern):
+        language = name
+if language in ["cpp", "py", "java"]:
+    print(f"Language is: {language}, comments are ignored")
+else:
+    print(f"{Fore.YELLOW}WARNING:{Style.RESET_ALL} Language is unknown, you must type comments")
+
+def normalize(file):
+    if language in ["cpp", "java"]:
+        # call c preprocessor to remove macros, comments and stuff
+        with open(file) as f:
+            text = subprocess.check_output(["cpp", "-dD", "-P", "-fpreprocessed"], stdin=f, encoding="utf-8")
+        # remove whitespaces
+        for whitespace in string.whitespace:
+            text = text.replace(whitespace, "")
+        return text
+    elif language == "py":
+        previous = token.INDENT
+        cleaned = []
+        with open(file) as f:
+            for type, value, _, _, _ in tokenize.generate_tokens(f.readline):
+                # remove comment and multiline comment
+                if type == token.COMMENT:
+                    continue
+                elif type == token.STRING and previous == token.INDENT:
+                    continue
+                # remove whitespaces
+                cleaned.append(value.strip())
+                previous = type
+        return "".join(cleaned)
+    else:
+        text = file.read_text()
+        # remove whitespaces
+        for whitespace in string.whitespace:
+            text = text.replace(whitespace, "")
+        return text
+    
+expected = normalize(selected)
+
+tmpfile = (Path(tempfile.gettempdir()) / "tcrracer").with_suffix(selected.suffix)
+tmpfile.write_text("")
+
+print("You have to type to: ", Fore.YELLOW, tmpfile, Style.RESET_ALL, sep="")
+#print("Press Enter to start",end="")
+input("Press Enter to start")
+print()
+print("You have to type: ", Fore.YELLOW, selected.relative_to(content), Style.RESET_ALL, sep="")
+if args.debug:
+    print("Expected:", f"{Fore.YELLOW}{expected}{Style.RESET_ALL}")
+print('Press enter to "submit" (or ctrl+c to abort)')
+print()
+
+accepted = False
+tries = 0
+start = time.perf_counter()
+
+def edit_distance(a, b):
+    n, m = len(a), len(b)
+    dp = [[0] * (m + 1) for _ in range(n + 1)]
+    for i in range(n + 1):
+        dp[i][0] = i
+    for j in range(m + 1):
+        dp[0][j] = j
+    for i in range(1, n + 1):
+        for j in range(1, m + 1):
+            if a[i - 1] == b[j - 1]:
+                dp[i][j] = dp[i - 1][j - 1]
+            else:
+                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
+    return dp[n][m]
+
+def submit():
+    global accepted
+    global tries
+    while not accepted:
+        debug = input()
+        got = normalize(tmpfile)
+        equal = got == expected
+        verdict = f"{Fore.GREEN}AC{Style.RESET_ALL}" if equal else f"{Fore.RED}WA{Style.RESET_ALL}"
+        message = [f"{clear}submitted:", verdict]
+        if args.debug:
+            message.append(f"(distance: {edit_distance(got, expected)})")
+            if debug == "ac": equal = True
+            if debug == "wa": equal = False
+        print(*message)
+        if equal:
+            accepted = True
+        else:
+            tries += 1
+
+threading.Thread(target=submit, daemon=True).start()
+
+elapsed = 0
+penalty = 0
+while not accepted:
+    elapsed = time.perf_counter() - start
+    penalty = args.penalty * tries
+    print(f"time: {elapsed + penalty:.2f}s (try: {tries+1})", end="\r", flush=True)
+    time.sleep(0.075)
+print()
+print(f"time: {elapsed + penalty:.2f}s (tries: {tries+1})")
+print(f"speed: ~{len(expected) / elapsed:.2f} chars per second", end="")
+if penalty:
+    print(f", ~{len(expected) / (elapsed + penalty):.2f} with penalty", end="")
+print()