Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
lib
 
 
sol
 
 
txt
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Advent of Code 2018 in Coq

This repository contains solutions for the Advent of Code 2018 (https://adventofcode.com/2018). Some of them are formally verified. This is an example of applying verification to small programming challenges of that kind. (If you're aiming for prizes, this is probably not the way to go.)

Contributions welcome

It will probably take much longer than the actual span of the AoC to complete this project, so any help implementing, specifying, or verifying solutions is welcome. If you have any questions, open an issue or send me an email (lysxia@gmail.com).

Suggested tasks

  • day02_2.v, day03_2.v are bare of any verification effort.

  • Implement Day 6 (Manhattan geometry).

Project status

As of December 2, the two solutions of Day 1's challenge are verified (significant caveats apply).

Read more about my approach in SUMMARY.md.

Dependencies

  • coq-simple-io, master

    This project serves to test coq-simple-io and see what is missing to make it practical to write executable programs in Coq.

  • coq-ext-lib, 0.10

  • Coq, 8.8.2

  • OCaml, 4.07.0

Older versions of these are likely to work.

Optional dependency

  • coq-itree, master. A library of free monads and algebraic effects (WIP).

Experimental proofs using itree instead of io_rel can be found in files sol/day*_*_extra.v.

To install coq-itree with opam and make it known to advent-of-coq:

git clone https://github.com/DeepSpec/InteractionTrees
opam pin add coq-itree ./InteractionTrees

# Inside advent-of-coq-2018, create a symbolic link _CoqConfig.append
# to _CoqConfig.extras
# The -f option overwrites any existing _CoqConfig.append
ln -sf _CoqConfig.extras _CoqConfig.append

# (Re)generate _CoqProject and compile lib.itree
make lib

Install the development version of coq-simple-io with opam

# Get the source
git clone https://github.com/Lysxia/coq-simple-io

# Register the local version of coq-simple-io with opam
opam pin add -k git coq-simple-io ./coq-simple-io

# When coq-simple-io is updated
cd coq-simple-io && git pull coq-simple-io
opam reinstall coq-simple-io

Build

To compile and run day01_1.v for example:

make exe/day01_1
./exe/day01_1 < txt/day01

About

Advent of Code 2018, in Coq! (https://adventofcode.com/2018)

Resources

Releases

No releases published

Packages

No packages published