Pen Settings



CSS Base

Vendor Prefixing

Add External Stylesheets/Pens

Any URL's added here will be added as <link>s in order, and before the CSS in the editor. If you link to another Pen, it will include the CSS from that Pen. If the preprocessor matches, it will attempt to combine them before processing.

+ add another resource


Babel is required to process package imports. If you need a different preprocessor remove all packages first.

Add External Scripts/Pens

Any URL's added here will be added as <script>s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

+ add another resource


Save Automatically?

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

Format on Save

If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.

Editor Settings

Code Indentation

Want to change your Syntax Highlighting theme, Fonts and more?

Visit your global Editor Settings.


  <div id="wrap">
  <textarea id="in" class="block">[
    "fool around",
    "cell phone",
    "work out",
    "right wing",
    "mail carrier",
    "break down",
    "blue jean",
    "computer virus",
    "folk music",
    "index finger",
    "radiation sickness",
    "credit card",
    "gas pedal",
    "short circuit",
    "wear out",
    "human body",
    "break in",
    "egg white",
    "ice cream",
    "old age",
    "mess up",
    "ad hoc",
  <div id="ui" class="block">
    <h2>Directed Acyclic Word Graph</h2>
    <p>A "directed acyclic graph" can also simply be called a tree. A "word tree" is used to find matches from the start of a word quickly. In this sense it's also referred to as a "finite state automaton", a machine that explores a finite set of possibilities. Its full name is a "deterministic acyclic finite state automaton", commonly abbreviated as DAFSA.</p>
    <p>In this tree, each letter that words have in common represents a node, which branches out to subsequential letters that are different. In the leaves, the position (or index) of the word in the list is stored, as well as the entire word.</p>
    <p>Another term for the kind of structure that is used here is <i>trie</i>,  or prefix tree. This term is more accurate, because each leaf in the tree is a separate entry, that contains the index of the word in the list. A DAFSA contains no duplicate nodes, so it won't allow for this metadata to be added, and actually can't be serialized as JSON, in contrast to our example. To conclude, a trie often forms the basis for (immutable) data structures, such as the <a href="" target="_blank">persistent vector</a> and the <a href="" target="_blank">hash-array mapped trie</a>.
    <button id="gen">>> Generate >></button> <span id="gen-feedback"/>
<p>Hit "Generate" to view the entire tree in the panel on the right.</p>
    <button id="verify">Verify</button> <span id="verify-feedback"/>
  Hit "Verify" to test if the positions found in the tree are correct.</p>
      <datalist id="ac"></datalist>
      <label for="lookup">Lookup</label><input id="lookup" list="ac"></input> <span id="lookup-feedback"/>
Enter text in "Lookup" to find a (partial) match. In the dropdown a list of (max. 10) matches is displayed. In the panel on the right, an array is displayed, holding the current selection in the tree, and the path traversed so far.</p>
  <textarea id="out" class="block">


                body {
#wrap {
.block {
  flex:1 1;
#in {
label {
  margin:0 .2rem;
#ui {

button {
  background: none;
	color: inherit;
	vertical-align: middle;
  outline: none;

#out {


                const $ = q => document.querySelector(q);

const empty = x => x === undefined || x === null;

var input, dawg;
function process(word,root,map,processed,key, c){
	if(c==word.length) return;
	let cp = word[c++];
	processed += cp;
	if(map[cp]) {
		return process(word,root, map[cp], processed, key, c);
	} else {
		if(map.constructor == Array){
			for(let i=0;i<map.length;i++){
				if(map[i][cp]) {
					return process(word,root, map[i][cp], processed, key, c);
		map = root;
		var len = processed.length;
		c = 0;
		do {
			let cp = processed[c++];
			if(map[cp]) {
				var newmap = {};
				let entry = map[cp];
				} else {
					map[cp] = [entry,newmap];
				newmap.parent = map[cp];
				map = newmap;
			} else {
				while(map.parent) {
					var found = false;
					var oldmap = map;
					for(var i=0;i<map.parent.length;i++){
						if(map.parent[i][cp] !== undefined){
							let newmap = {};
							if(map.parent[i][cp].constructor == Array){
							} else {
								map.parent[i][cp] = [map.parent[i][cp],newmap];
							newmap.parent = map.parent[i][cp];
							map = newmap;
							found = true;
					delete oldmap.parent;
					if(found) cp = processed[c++];
					if(!found) break;
				map[cp] = {_k:word,_v:parseInt(key)};
		} while(c<len);

function createDawg(input,order) {
  var root = {};
	if(!order) {
		order = function(a,b){
			return input[a].localeCompare(input[b]);
	Object.keys(input).sort(order).forEach(function(k){   process(input[k],root,root,"",k,0);
	const stripObj = x => {
		if("_k" in x) return x;
		for(var k in x) {
			x[k] = strip(x[k]);
		return x;
	const strip = x =>
		x instanceof Array ?
			x.filter(entry => Object.keys(entry).length).map(strip) :
			typeof x == "object" ? stripObj(x) : x;
	return strip(root);

function traverse(tmp,word,eow = false){
	var b ="";
	var ret = tmp[0], path = tmp[1] || [];
	let i = 0,c,l=word.length;
	for(; i<l; i++){
		c = word[i];
		tmp = find(ret,c,b,path,i);
		ret = tmp[0];
		path = tmp[1];
		if(!ret) return;
  const plen = path.length;
    const len = ret.length;
    if(!len && !plen) return;
    if(!plen && eow) {
      if(ret[0]._k === word) return ret[0]._v;
  } else {
    if("_v" in ret && !plen && eow) {
      if(ret._k === word) return ret._v;
  if(eow && plen) {
    for(let j = path.length - 1; j >= 0; --j) {
      if(path[j]._k === word) return path[j]._v;
	return [ret,path];

function filter(path,cp,pos){
	while(path.length && path[0]._k[pos] != cp) path.shift();
	return path;
function find(entry,cp,word,path,pos){
		let len = entry.length;
		for(var i = 0; i < len; i++){
			let a = entry[i];
      if("_v" in a) {
				if(a._k[pos] == cp){
			} else {
				if(a[cp] !== undefined) {
          return [a[cp],filter(path,cp,pos)];
    return [filter(path,cp,pos),[]];
	} else if(!("_v" in entry)){
		return [entry[cp],filter(path,cp,pos)];
	} else {
		if(entry._k[pos] === cp) {
			return [entry,filter(path,cp,pos)];
		return [filter(path,cp,pos),[]];

function generate() {
  var t =;
  input = JSON.parse($("#in").value);
  dawg = createDawg(input);
  $("#out").value = JSON.stringify(dawg,null,4);
  var e =;
  $("#gen-feedback").textContent = `Took ${e-t} ms`;

function verify(){
  if(!dawg) {
    input = JSON.parse($("#in").value);
    dawg = createDawg(input);
  var failed = false;
  var out = [];

  var t =;
  for(let i=0,len=input.length;i<len;i++){
    let ret = traverse([dawg],input[i],true);
    if(ret+'' !== i+'') {
      failed = true;
  var e =;

  if(!failed) {
    $("#verify-feedback").textContent = `Took ${e-t} ms`;
  } else {
    $("#verify-feedback").textContent = 'Verification failed!';

function lookup(w) {
  if(!dawg) {
    input = JSON.parse($("#in").value);
    dawg = createDawg(input);
  var t =;
  let ret = w.length ? traverse([dawg],w) : null;
  var e =;
  $("#out").value = !empty(ret) ? JSON.stringify(ret,null,4) : '';
  const autocomplete = a => {
    if(!empty(a)) {
      const [ret,path] = a;
      a = [path,ret];
      const recurse = (a,out = []) => {
        if(out.length >= 10) return out;
        a.forEach(x => {
          if(Array.isArray(x)) {
          } else if("_k" in x) {
          } else {
        return out;
      return recurse(a);
    return [];
  const list = $("#ac");
  list.innerHTML = "";
  autocomplete(ret).forEach(item => {
    var option = document.createElement('option');
    option.value = item._k;
  $("#lookup-feedback").textContent = !empty(ret) ? `Took ${e-t} ms` : '';

$("#gen").addEventListener("click",() => {

$("#verify").addEventListener("click",() => {

$("#lookup").addEventListener("input",(evt) => {