Go Library for Competitive Programming with Generics

Go Library for Competitive Programming with Generics

Go used to be a difficult language to use for competitive programming. However, with the introduction of generics, Go has become a language with great potential for competitive programming.

This repository is a library of the Go language that is useful for competitive programming. The code in this library does not compile with the current official release of Go 1.17.x, but it will compile with Go 1.17.x if you convert it with go2go. Furthermore, by using Gottani to compile it into a single go file, it is possible to generate Go code that can be submitted to online judges for competitive programming. The author of this repository has actually competed in many competitive programming rounds with Go code generated using this library.

Supported algorithms

AC Library Porting

  • Data structure
    • FenwickTree
    • Segtree
    • LazySegtree
    • SuffixArray
    • LCPArray
    • ZAlgorithm
  • Mathematic
    • PowMod
    • InvMod
    • CRT
    • FloorSum
    • Convolution, not ported yet.
    • ModInt
  • Graph
    • DSU
    • MaxFlow
    • MinCostFlow
    • SCC
    • TwoSat

Other Data Structure and Algorithms

  • Data Structure
    • Deque
    • Heap *HeapPush *HeapPop
    • LCS: Longest Common Subsequence
    • LCSR: Longest Common Subsequence with Reconsturuction
    • LIS: Longest Incresing Subsequence
    • List: Doubly Linked List
    • LLRB: Left-Leaning Red Brack Tree
    • Map: Ordered Map using LLRB
    • Set: Ordered Set using LLRB
    • Pair
    • Trio
    • Permutation
      • NextPermutation
      • PrevPermutation
    • PriorityQueue
    • Queue
    • Rolling Hash
      • StringContains
      • StringFindAll
      • SequenceContains
      • SequenceFindAll
      • SequenceFindAll2D
    • SkewHeap
    • Stack
    • Treap
    • Trie
  • Algorithms for slice []T
    • CountInversion: Find the numbers of pairs (i, j) where a[i] > a[j]
    • Binary Search
      • BinSearch
      • LowerBound
      • UpperBound
      • EqualRange
      • EqualRange
    • Reverse
    • Rotate
    • Shuffle
    • SliceMaxElement
    • SliceFilter
    • SliceMap
    • SliceFoldl
    • SliceFoldr
    • SliceLess
    • SliceUniq
    • Iota
    • SliceBinSearch
    • SliceLowerBound
    • SliceUpperBound
    • SliceEqualRange
    • SliceToString
    • SliceFill
    • SliceEqual
  • Sort
    • Sort: Introsort
    • SortStable: Stable sort by Merge Sort with Insertion Sort
    • InsertionSort
    • HeapSort
    • BubbleSort
    • SelectionSort
    • ShellSort
    • MergeSort
    • CountingSort
    • IsSorted
  • Algorithms for grid [][]T
    • CumulativeSum2D
  • Mathematic
    • IsPrime
    • Primes: Compute prime / composite for range 1 .. n
    • PrimesX: Same as Primes but it can find prime factors.
    • Factorize
    • NewFactorial: Compute combination, permutation, factorial with p as the law
  • Graph
    • Dijkstra
    • GetParent: Reconstruct parents in the minimum cost path with the out put of the Dijkstra
    • BellmanFord
    • WarshallFloyd
    • MST: Minimum Spanning Tree
  • Utilities
    • GetInf: Get numeric value whitch is useful as "infinit" in competitive programming
    • Less
    • More
    • GetRandomSeed
  • IO
    • readb: Reads next string and returns as []byte
    • reads: Reads next string and returns as string
    • readbln: Reads next line and returns as []byte
    • readsln: Reads next line and returns as string
    • readll: Reads next string as int64
    • readi: Reads next string as int
    • readf: Reads next string as float64
    • readInts: Reads next n ints and returns as []int
    • printf: fmt.Printf
    • println: fmt.Println
    • eprintf: fmt.Frintf(os.Stderr, "...")
    • eprintln: fmt.Frintln(os.Stderr, "...")
    • dbgf: fmt.Frintf(os.Stderr, "...")
    • dbg: fmt.Frintln(os.Stderr, "...")
    • sprintf: fmt.Sprintf
    • sprint: fmt.Sprint

Install Prerequisites

Tutorial

Let's use this lib for solving ABC 183 C - Travel.

  1. Clone this repository.
$ git clone https://github.com/ktateish/go-competitive abc183_c
$ cd abc183_c
  1. Edit main.go2 like:
package main

// vim:set ft=go:

// snip ------------------------------------------------------------------------

const (
	// big prime
	P1b7 = 1000000007
	P1b9 = 1000000009
	P0b3 = 998244353
)

var DEBUG bool
var RANDOM_SEED int64

func Main() {
	N := readi()
	K := readi()
	T := make([][]int, N)
	for i := range T {
		_, T[i] = readInts(N)
	}
	M := N - 1
	a := make([]int, M)
	Iota(a, 1)
	var ans int
	for ok := true; ok; ok = NextPermutation(a) {
		var k int
		k += T[0][a[0]]
		k += T[a[M-1]][0]
		for i := 0; i < M-1; i++ {
			k += T[a[i]][a[i+1]]
		}
		if k == K {
			ans++
		}
	}
	println(ans)
}
  1. Build using make
$ make

A single Go file gottani.go and an executable a.out will be generated.

  1. Test a.out for sample input
$ ./a.out < input
  1. Submit gottani.go to the judge and check the result

In this case, the submission is accepted

DISCLAIMER: The author and the contributors of this library are not responsible for any damages caused by using this library.

License

This library is distribted under the BSD License (BSD-2-Clause). See LICENSE file for detail.

Author

Katsuyuki Tateish (@ktateish)

Similar Resources

Go 1.18 generics use cases and examples

Go 1.18 generics use cases What are generics? See Type Parameters Proposal. How to run the examples? As of today, gotip is the simplest way to run the

Jan 10, 2022

Functional tools in Go 1.18 using newly introduced generics

functools functools is a simple Go library that brings you your favourite functi

Dec 5, 2022

Experimenting with golang generics to implement functional favorites like filter, map, && reduce.

funcy Experimenting with golang generics to implement functional favorites like filter, map, && reduce. 2021-12 To run the tests, you need to install

Dec 29, 2021

A collection of functional operators for golang with generics

fn fn is a collection of go functional operators with generics Getting Started P

Jul 8, 2022

Benchmarks to compare Go Generics

This is a collection of various sorts implemnted both as []int only and as const

Dec 8, 2022

CDN-like in-memory cache with shielding, and Go 1.18 Generics

cache CDN-like, middleware memory cache for Go applications with integrated shielding and Go 1.18 Generics. Usage package main import ( "context" "

Apr 26, 2022

Go 1.18 generics based slice and sorts.

genfuncs import "github.com/nwillc/genfuncs" Package genfuncs implements various functions utilizing Go's Generics to help avoid writing boilerplate c

Jan 2, 2023

F - Experimenting with Go 1.18 generics to write more functional Go code

f f is a simple library that leverages the new generics in Golang to create a tools for functional style of code. Pipe like '|' in Elixir or Elm. inp

Apr 12, 2022

A hands-on approach for getting started with Go generics.

Go Generics the Hard Way This repository is a hands-on approach for getting started with Go generics: Prerequisites: how to install the prerequisites

Dec 27, 2022
Code Generation for Functional Programming, Concurrency and Generics in Golang

goderive goderive derives mundane golang functions that you do not want to maintain and keeps them up to date. It does this by parsing your go code fo

Dec 25, 2022
Extended library functions using generics in Go.

Just few extended standard library functions for Golang using generics.

Dec 16, 2021
A library that provides Go Generics friendly "optional" features.

go-optional A library that provides Go Generics friendly "optional" features. Synopsis some := optional.Some[int](123) fmt.Printf("%v\n", some.IsSome(

Dec 20, 2022
Utility library that uses Go generics mechanism

golang-generics-util Utility library that explores Go generics (1.18) xsync Sync

Dec 11, 2022
Use is a go utility library using go1.18 generics

use use is a go utility library using go1.18 generics created by halpdesk 2022-01-22 use/slice Map updates a slice by applying a function to all membe

Jan 22, 2022
Experiments with Go generics

generics Quick experiments with Go generics algebra, a generic square root function for float, complex and and rational. future, a concurrent cache ("

Dec 31, 2022
Example code for Go generics

go-generics-example Example code for Go generics. Usage $ go build -gcflags=-G=3 Requirements Go 1.17 or later Advertise Go 言語にやってくる Generics は我々に何をも

Dec 30, 2022
Collection of unusual generics usecases in Go

Unusual Generics Type parameters or Generics in Go designed to reduce boilerplate for container data types like lists, graphs, etc. and functions like

Dec 14, 2022
Package truthy provides truthy condition testing with Go generics
Package truthy provides truthy condition testing with Go generics

Truthy Truthy is a package which uses generics (Go 1.18+) to create useful boolean tests and helper functions. Examples // truthy.Value returns the tr

Nov 11, 2022
experimental promises in go1.18 with generics

async go a prototype of "promises" in go1.18. note: this is just an experiment used to test alternate patterns for dealing with asynchronous code in g

Dec 23, 2022