Skip to content

Instantly share code, notes, and snippets.

View Lipen's full-sized avatar
🐈
Working from home

Konstantin Chukharev Lipen

🐈
Working from home
View GitHub Profile
@Lipen
Lipen / combine.kt
Created July 6, 2024 21:11
Cartesian product of possibly-infinite sequences
import org.junit.jupiter.api.Test
fun <T> combine(sequences: List<Sequence<T>>): Sequence<List<T>> = sequence {
if (sequences.isEmpty()) return@sequence
if (sequences.size == 1) {
for (x in sequences[0]) {
yield(listOf(x))
}
return@sequence
@Lipen
Lipen / parse_binary_drat.py
Last active August 7, 2023 01:22
Binary DRAT parser
import mmap
import tqdm
def parse_binary_drat_mmap(path):
with open(path, "rb") as f:
with mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) as mm:
state = 0
# state = 0 -- reading the mode: b'a' or b'd'
# state = 1 -- reading the clause
mode = None # "a" or "d", for user
@Lipen
Lipen / quicksort.py
Created October 10, 2021 10:23
QuickSort
#!/usr/bin/env python
# coding: utf-8
def quicksort(A, p=0, r=None):
if r is None:
r = len(A) - 1
if p < r:
q = partition(A, p, r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
@Lipen
Lipen / coloring.mzn
Created March 11, 2021 14:29
Minizinc models for common graph problems
%%% Graph Coloring
%% Constants.
int: V;
int: E = length(edges1d) div 2;
int: k;
set of int: NODES = 1..V;
set of int: EDGES = 1..E;
set of int: COLORS = 1..k;
@Lipen
Lipen / Exercises.ipynb
Created October 9, 2020 10:21
Bash Exercises - Oct 9, 2020
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@Lipen
Lipen / bf.sygus
Created August 21, 2020 08:47
(Minimal) Boolean Formula Synthesis using SyGuS
; EXPECT: unsat
; COMMAND-LINE: --lang=sygus2
(set-logic ALL)
(synth-fun f ((x Bool) (y Bool) (z Bool)) Bool
((Start Bool)) (
(Start Bool (
x y z
(not Start)
(and Start Start)
@Lipen
Lipen / minimum-vertex-cover.py
Created August 20, 2020 07:56
Minimum Vertex Cover using RC2 MaxSAT Solver from PySAT
from pysat.examples.rc2 import RC2
from pysat.formula import WCNF, IDPool
vpool = IDPool(start_from=1)
def cover(v):
return vpool.id(f'cover@{v}')
@Lipen
Lipen / bf.py
Last active August 19, 2020 17:18
Template for the "Minimal Boolean formula synthesis" problem
from pysat.formula import CNF, IDPool
from pysat.solvers import Minisat22 as Solver
from enum import Enum
NodeType = Enum("NodeType", "VAR AND OR NOT")
class BFSynthesizer:
def __init__(self, n: int, tt: str, P: int):
assert len(tt) == 2 ** n, "Incorrect truth table size"
@Lipen
Lipen / Einstein.kt
Created August 18, 2020 15:06
Einstein riddle via kotlin-satlin
package examples.einstein
import com.github.lipen.satlib.op.exactlyOne
import com.github.lipen.satlib.op.imply
import com.github.lipen.satlib.op.implyOr
import com.github.lipen.satlib.solver.MiniSatSolver
import com.github.lipen.satlib.solver.Solver
import com.github.lipen.satlib.solver.newDomainVarArray
import com.github.lipen.satlib.utils.DomainVarArray
import com.github.lipen.satlib.utils.convert
@Lipen
Lipen / simple.py
Created August 18, 2020 15:03
Sample problem solving using PySAT
from pysat.formula import CNF, IDPool
from pysat.solvers import Minisat22
n, k = map(int, input().split())
cnf = CNF()
vpool = IDPool(start_from=1)
def bit(i):
return vpool.id(f'v@{i}')