/cl-competitive

Common Lisp implementation of algorithms

Primary LanguageCommon Lisp

Common Lisp code collection for competitive programming

Build Status

This code collection is maintained mainly for competitive programming, and partly for just understanding algorithms.

License

The greater part of this library is distributed as public domain, or licensed under either CC0 or the MIT license, whichever gives you the most rights in your legislation. Some code, however, has its specific license (usually because it is a dead copy of other library). For the details, please see the header of each file.

Style

Although I put this code collection in a ASDF module, this project is primarily made for competitive programming and the whole structure will be quite different from a common ASDF library. I don't recommend that you directly load this module for your software.

On portability: I try to write portable code as long as the code structure doesn't get too complicated. However, I occasionally use extensions and behaviours of SBCL x86-64, mainly for performance reasons. Below is a SBCL-specific feature that I always depend on:

  • declaration as assertion

Below are the features that I sometimes use:

  • bivalent stream
  • extensible sequence
  • sb-ext:array-storage-vector and sb-kernel:%vector-raw-bits
  • sb-c:define-source-transform

Every data structure and algorithm uses a 0-based index and a half-open interval unless otherwise noted.

Test environment

  • SBCL 2.1.6 (x64, linux) — yukicoder's version
  • SBCL 2.0.3 (x64, linux) — AtCoder's version
  • SBCL 1.3.13 (x64, linux) — CodeChef's version
  • SBCL 1.3.1 (x64, linux) — HackerEarth's version

Contents

Unclassified data structures

Unclassified algorithms

Arithmetic and algebra

Real and complex

Bit operations

Graph

Optimization

Euclidean geometry

String

I/O

Other utilities

Weird things

  • integer-pack.lisp defstruct-like macro to deal with an integer as a structure of several integer slots
  • increase-space.lisp This header runs another SBCL as external process and leaves the entire processing to it. (This ugly hack was invented to increase the stack size of SBCL on online judges.)
  • compile-time-increase-space.lisp analogue of increase-space at compile time