MikuroXina’s gists

MikuroXina / cum.rs

Last active November 16, 2023 00:13

Find cumulative sum of numbers with Rust.

	pub fn cum<T: Default + std::ops::AddAssign + Copy>(
	nums: impl IntoIterator<Item = T>,
	) -> impl Iterator<Item = T> {
	nums.into_iter().scan(T::default(), \|state, item\| {
	*state += item;
	Some(*state)
	})
	}

	pub fn cum2<T: Default + std::ops::AddAssign + Copy, NNS, NS>(nums: NNS) -> Vec<Vec<T>>

MikuroXina / alt_sum.rs

Created November 5, 2023 23:37

Monoid implementation of alternating sum with Rust.

	#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
	pub struct AltSum {
	sum: i64,
	len: usize,
	}

	impl AltSum {
	pub fn empty() -> Self {
	Self { sum: 0, len: 0 }
	}

MikuroXina / y.ts

Created October 29, 2023 09:08

Y fixed combinator with TypeScript.

	export type Paradoxical<A, R> = (f: Paradoxical<A, R>) => (a: A) => R;

	export const Y = <A, R>(f: (g: (a: A) => R) => (a: A) => R): ((a: A) => R) =>
	((x: Paradoxical<A, R>) => f((lazy) => x(x)(lazy)))(
	(x: Paradoxical<A, R>) => f((lazy) => x(x)(lazy)),
	);

MikuroXina / inversions.rs

Last active November 8, 2023 01:44

Calculates inversion numbers of sequence with Rust.

	pub fn inversions(nums: &[usize]) -> Vec<usize> {
	let len = nums.len();
	let mut counts = SegTree::<Sum>::new(len);
	let mut inversions = Vec::with_capacity(len);
	for (i, &num) in nums.into_iter().enumerate() {
	let Sum(inv) = counts.query(0..num);
	inversions.push(i - inv);
	counts.insert(num, Sum(1));
	}
	inversions

MikuroXina / lis.rs

Last active October 24, 2023 12:35

Finding lengths of Longest Increasing Subsequence by its length with Rust.

	pub fn longest_increasing_subsequence<T: Ord>(nums: impl IntoIterator<Item = T>) -> Vec<usize> {
	let mut nums = nums.into_iter();
	let Some(first) = nums.next() else {
	return vec![];
	};
	let mut len_by_using = vec![1];
	let mut sorted = vec![first];
	for num in nums {
	let lower_bound = sorted.binary_search(&num).unwrap_or_else(\|idx\| idx);
	if lower_bound == sorted.len() {

MikuroXina / merge.rs

Last active October 24, 2023 08:52

Merges two sorted IntoIterator into a sorted Iterator with Rust.

	#[inline]
	pub fn merge<T, L, R>(left: L, right: R) -> Merge<T, L::IntoIter, R::IntoIter>
	where
	T: PartialOrd,
	L: IntoIterator<Item = T>,
	R: IntoIterator<Item = T>,
	{
	Merge {
	left: left.into_iter().peekable(),
	right: right.into_iter().peekable(),

MikuroXina / strongly_connected_components.rs

Last active October 19, 2023 06:29

An implementation of extracting strongly connected components with Rust.

	pub fn strongly_connected_components(graph: &[Vec<usize>]) -> Vec<Vec<usize>> {
	let vertexes = graph.len();
	let inv_graph = {
	let mut inv_graph = vec![vec![]; vertexes];
	for (from, adj) in graph.into_iter().enumerate() {
	for &to in adj {
	inv_graph[to].push(from);
	}
	}
	inv_graph

MikuroXina / backtrack.rs

Last active June 29, 2025 14:20

An implementation of backtracking algorithm with Rust.

MikuroXina / coord_orient.rs

Last active February 3, 2024 14:26

Definition of coordinate and orientation.

	#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
	pub struct Field {
	// both of width and height must ≤ i64::MAX for safety
	width: u64,
	height: u64,
	}

	impl Field {
	pub fn new(width: u64, height: u64) -> Self {
	assert!(

MikuroXina / poly.rs

Last active October 1, 2023 10:13

Polyomino structure defintion with Rust.

	#[derive(Clone, PartialEq, Eq, Hash)]
	struct Poly<const W: usize, const H: usize> {
	field: [[bool; W]; H],
	}

	impl<const W: usize, const H: usize> std::fmt::Debug for Poly<W, H> {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
	writeln!(f, "\"\"\"")?;
	for y in 0..H {
	for x in 0..W {

Mikuroさいな MikuroXina