| Name : ghc-ersatz
| |
| Version : 0.4
| Vendor : openSUSE
|
| Release : bp150.2.8
| Date : 2018-07-30 21:26:27
|
| Group : Development/Languages/Other
| Source RPM : ghc-ersatz-0.4-bp150.2.8.src.rpm
|
| Size : 17.76 MB
| |
| Packager : https://bugs_opensuse_org
| |
| Summary : A monad for expressing SAT or QSAT problems using observable sharing
|
Description :
A monad for expressing SAT or QSAT problems using observable sharing.
For example, we can express a full-adder with:
> full_adder :: Bit -> Bit -> Bit -> (Bit, Bit) > full_adder a b cin = (s2, c1
|| c2) > where (s1,c1) = half_adder a b > (s2,c2) = half_adder s1 cin
> half_adder :: Bit -> Bit -> (Bit, Bit) > half_adder a b = (a `xor` b, a && b)
/Longer Examples/
Included are a couple of examples included with the distribution.
Neither are as fast as a dedicated solver for their respective domains, but
they showcase how you can solve real world problems involving 10s or 100s of
thousands of variables and constraints with `ersatz`.
\'ersatz-sudoku\'
> % time ersatz-sudoku > Problem: > ┌───────┬───────┬───────┐ > │ 5 3 │ 7 │ │ >
│ 6 │ 1 9 5 │ │ > │ 9 8 │ │ 6 │ > ├───────┼───────┼───────┤ > │ 8 │ 6 │ 3 │ > │
4 │ 8 3 │ 1 │ > │ 7 │ 2 │ 6 │ > ├───────┼───────┼───────┤ > │ 6 │ │ 2 8 │ > │ │
4 1 9 │ 5 │ > │ │ 8 │ 7 9 │ > └───────┴───────┴───────┘ > Solution: >
┌───────┬───────┬───────┐ > │ 5 3 4 │ 6 7 8 │ 9 1 2 │ > │ 6 7 2 │ 1 9 5 │ 3 4 8
│ > │ 1 9 8 │ 3 4 2 │ 5 6 7 │ > ├───────┼───────┼───────┤ > │ 8 5 9 │ 7 6 1 │ 4
2 3 │ > │ 4 2 6 │ 8 5 3 │ 7 9 1 │ > │ 7 1 3 │ 9 2 4 │ 8 5 6 │ >
├───────┼───────┼───────┤ > │ 9 6 1 │ 5 3 7 │ 2 8 4 │ > │ 2 8 7 │ 4 1 9 │ 6 3 5
│ > │ 3 4 5 │ 2 8 6 │ 1 7 9 │ > └───────┴───────┴───────┘ > ersatz-sudoku 1,13s
user 0,04s system 99% cpu 1,179 total
\'ersatz-regexp-grid\'
This solves the \"regular crossword puzzle\"
(< https://github.com/ekmett/ersatz/raw/master/notes/grid.pdf grid.pdf>) from
the 2013 MIT mystery hunt.
> % time ersatz-regexp-grid
\"SPOILER\"
> ersatz-regexp-grid 2,45s user 0,05s system 99% cpu 2,502 total.
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/openSUSE:/Backports:/SLE-15/standard/x86_64 |
