dl

README

dk-7.2.2.1

dk-7.2.2.1 provides package dl - what else ;-)

---

Note: 'Don' intends to "save time and space by allocationg them sequential." Page 4 first paragraph in his pre-print.

The implementation in this repo takes his approach very literally.

And Yes, the data is very compact and its locality may be very friendly to CPU caches. Further, it is easy to clone the data as is needed by any concurrent approach to subproblems.

Just - due to the very many index operations involved in this sequential allocation, performance time suffers substantially.

So this implementation is useful as a counter-example and for comparsions with other implementations such as a hybrid approach (with pointers and indices) here or a pointers-only approach here.

---

Your suggestions, remarks, questions and/or contributions are welcome ;-)

---

Think deep - code happy - be simple - see clear :-)

---

Support on Beerpay

Hey dude! Help me out for a couple of 🍻!

Documentation

Overview

Package dl allows to solve any exact cover problem via dancing links.

The implementation is spread across internal packages:

x provides basic constituents (Names, Items, Optas, Dict ...).

m implements M, the matrix representing a named problem
  built from a given list of lists of symbols.

d provides D, a dancer dancing its graceful dance -pretty fast-
  on the links of the given M which implements Searcher.
  This is the core of the algorithm - the heartbeat!

s provides a Searcher who invokes a suitable D,
  manages its heartbeat, operation and output,
  given a way to build some M.
  Many options permit finetuning on the fly:
  plug-in functions as needed.

Index

• func CountDeadEnd(perLevel bool) do.Option
• func CountGrooves(perLevel bool) do.Option
• func CountNiveaus(perLevel bool) do.Option
• func CountUpDates(perLevel bool) do.Option
• func CountUpdates(perCells bool) do.Option
• func LogProgress(everyNmillion int64) do.Option
• func LogSize() do.Option
• func LogTime() do.Option
• func OnFail(fs ...func(*d.D)) do.Option
• func OnGoal(fs ...func(*d.D)) do.Option
• func OnLeaf(fs ...func(*d.D)) do.Option
• func OnSkip(fs ...func(*d.D) bool) do.Option
• func VerboseD(v bool) do.Option
• func VerboseM(v bool) do.Option
• func VerboseX(v bool) do.Option

Functions

func CountDeadEnd

func CountDeadEnd(perLevel bool) do.Option

CountDeadEnd counts failures

func CountGrooves

func CountGrooves(perLevel bool) do.Option

CountGrooves counts solutions

func CountNiveaus

func CountNiveaus(perLevel bool) do.Option

CountNiveaus counts effort

func CountUpDates

func CountUpDates(perLevel bool) do.Option

CountUpDates counts unLink

func CountUpdates

func CountUpdates(perCells bool) do.Option

CountUpdates returns a function which sets D.Drum.UseMap to perCell and returns it's undo do.Opt.

func LogProgress

func LogProgress(everyNmillion int64) do.Option

LogProgress sends a progress line to the current logger upon everyNmillion (minimum = 10) updates which shows the completition (in permille) as well as the number of Grooves, DeadEnd and millions-of-Updates.

func LogSize

func LogSize() do.Option

LogSize logs a starting-line upon Init with the size of the problem representation.

func LogTime

func LogTime() do.Option

LogTime logs a finished-line upon Done with the time elapsed since On.Init.

Note: runtime.GC is forced before the timer starts.

func OnFail

func OnFail(fs ...func(*d.D)) do.Option

OnFail returns a function which sets D.On.Fail to f and returns it's undo do.Opt.

func OnGoal

func OnGoal(fs ...func(*d.D)) do.Option

OnGoal returns a function which sets D.On.Goal to f and returns it's undo do.Opt.

func OnLeaf

func OnLeaf(fs ...func(*d.D)) do.Option

OnLeaf returns a function which sets D.On.Leaf to f and returns it's undo do.Opt.

func OnSkip

func OnSkip(fs ...func(*d.D) bool) do.Option

OnSkip returns a function which sets D.On.Skip to f and returns it's undo doFn.

func VerboseD

func VerboseD(v bool) do.Option

VerboseD controls the verbosity setting of package d.

func VerboseM

func VerboseM(v bool) do.Option

VerboseM controls the verbosity setting of package m.

func VerboseX

func VerboseX(v bool) do.Option

VerboseX controls the verbosity setting of package x.