csps - npm Package Compare versions

Comparing version 1.0.4 to 1.0.5

dist/csps.cjs.development.js

@@ -267,56 +267,3 @@ 'use strict';
 
-/* Min-conflicts hill-climbing search for CSPs functions */
-
 /**
- * Solve a CSP by stochastic hill-climbing on the number of conflicts.
- *
- * @param  {CSP<T>} aCSP
- * @param  {number=100000} max_steps
- * @returns LooseObject
- */
-var min_conflicts = function min_conflicts(aCSP, max_steps) {
-  if (max_steps === void 0) {
-    max_steps = 100000;
-  }
-
-  // Generate a complete assignment for all variables (probably with conflicts)
-  var current = {};
-  aCSP.variables.forEach(function (variable) {
-    var val = min_conflicts_value(aCSP, variable, current);
-    aCSP.assign(variable, val, current);
-  }); // Now repeatedly choose a random conflicted variable and change it
-
-  for (var i = 0; i < max_steps; i++) {
-    var conflicted = aCSP.conflicted_vars(current);
-
-    if (!(conflicted.length > 0)) {
-      return current;
-    }
-
-    var variable = random_choice(conflicted);
-    var val = min_conflicts_value(aCSP, variable, current);
-    aCSP.assign(variable, val, current);
-  } // If no solution can be found.
-
-
-  return undefined;
-};
-/**
- * Return the value that will give var the least number of conflicts.
- * If there is a tie, choose at random.
- *
- * @param  {CSP<T>} aCSP
- * @param  {T} variable
- * @param  {LooseObject<T[]>} current
- * @returns T
- */
-
-var min_conflicts_value = function min_conflicts_value(aCSP, variable, current) {
-  var num_conflicts = function num_conflicts(val) {
-    return aCSP.nconflicts(variable, val, current);
-  };
-
-  return argmin_random_tie(aCSP.domains[variable], num_conflicts);
-};
-/**
  * Return a random element from an array.
@@ -328,3 +275,2 @@ *
  */
-
 var random_choice = function random_choice(arr) {
@@ -384,10 +330,60 @@ return arr[Math.floor(Math.random() * arr.length)];
 
+/* Min-conflicts hill-climbing search for CSPs functions */
+/**
+ * Solve a CSP by stochastic hill-climbing on the number of conflicts.
+ *
+ * @param  {CSP<T>} aCSP
+ * @param  {number=100000} max_steps
+ * @returns LooseObject
+ */
+
+var min_conflicts = function min_conflicts(aCSP, max_steps) {
+  if (max_steps === void 0) {
+    max_steps = 100000;
+  }
+
+  // Generate a complete assignment for all variables (probably with conflicts)
+  var current = {};
+  aCSP.variables.forEach(function (variable) {
+    var val = min_conflicts_value(aCSP, variable, current);
+    aCSP.assign(variable, val, current);
+  }); // Now repeatedly choose a random conflicted variable and change it
+
+  for (var i = 0; i < max_steps; i++) {
+    var conflicted = aCSP.conflicted_vars(current);
+
+    if (!(conflicted.length > 0)) {
+      return current;
+    }
+
+    var variable = random_choice(conflicted);
+    var val = min_conflicts_value(aCSP, variable, current);
+    aCSP.assign(variable, val, current);
+  } // If no solution can be found.
+
+
+  return undefined;
+};
+/**
+ * Return the value that will give var the least number of conflicts.
+ * If there is a tie, choose at random.
+ *
+ * @param  {CSP<T>} aCSP
+ * @param  {T} variable
+ * @param  {LooseObject<T[]>} current
+ * @returns T
+ */
+
+var min_conflicts_value = function min_conflicts_value(aCSP, variable, current) {
+  var num_conflicts = function num_conflicts(val) {
+    return aCSP.nconflicts(variable, val, current);
+  };
+
+  return argmin_random_tie(aCSP.domains[variable], num_conflicts);
+};
+
 exports.CSP = CSP;
 exports.Problem = Problem;
-exports.argmin_random_tie = argmin_random_tie;
-exports.identity = identity;
 exports.min_conflicts = min_conflicts;
 exports.min_conflicts_value = min_conflicts_value;
-exports.random_choice = random_choice;
-exports.shuffle_array = shuffle_array;
 //# sourceMappingURL=csps.cjs.development.js.map

dist/csps.cjs.production.min.js

@@ -1,2 +0,2 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var t=function(t,n){var r=this;void 0===n&&(n=void 0),this.action=function(t){throw Error("Not Implemented")},this.result=function(t,n){throw Error("Not Implemented")},this.goal_test=function(t){return typeof r.goal==typeof Array?r.goal.includes(t):t===r.goal},this.path_cost=function(t,n,r,o){return t+1},this.value=function(t){throw Error("Not Implemented")},this.initial=t,this.goal=n},n=function(t,n,r){return i(t.domains[n],(function(o){return t.nconflicts(n,o,r)}))},r=function(t){return t[Math.floor(Math.random()*t.length)]},o=function(t){for(var n=[].concat(t),r=n.length-1;r>0;r--){var o=Math.floor(Math.random()*(r+1)),e=[n[o],n[r]];n[r]=e[0],n[o]=e[1]}return n},e=function(t){return t},i=function(t,n){return void 0===n&&(n=e),o(t).reduce((function(t,r){return n(t)<n(r)?t:r}))};exports.CSP=function(t){var n,r;function o(n,r,o,e){var i;return(i=t.call(this,[])||this).assign=function(t,n,r){r[t]=n,i.nassigns+=1},i.unassign=function(t,n){n.hasOwnProperty(t)&&delete n[t]},i.nconflicts=function(t,n,r){return Object.keys(i.neighbors).filter((function(o){return r.hasOwnProperty(e=o)&&!i.constraints(t,n,e,r[e]);var e})).length},i.display=function(t){console.log(t)},i.conflicted_vars=function(t){return i.variables.filter((function(n){return i.nconflicts(n,t[n],t)>0}))},i.variables=n||Object.keys(r),i.domains=r,i.neighbors=o,i.constraints=e,i.curr_domains=void 0,i.nassigns=0,i}return r=t,(n=o).prototype=Object.create(r.prototype),n.prototype.constructor=n,n.__proto__=r,o}(t),exports.Problem=t,exports.argmin_random_tie=i,exports.identity=e,exports.min_conflicts=function(t,o){void 0===o&&(o=1e5);var e={};t.variables.forEach((function(r){var o=n(t,r,e);t.assign(r,o,e)}));for(var i=0;i<o;i++){var s=t.conflicted_vars(e);if(!(s.length>0))return e;var a=r(s),c=n(t,a,e);t.assign(a,c,e)}},exports.min_conflicts_value=n,exports.random_choice=r,exports.shuffle_array=o;
+"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var t=function(t,n){var r=this;void 0===n&&(n=void 0),this.action=function(t){throw Error("Not Implemented")},this.result=function(t,n){throw Error("Not Implemented")},this.goal_test=function(t){return typeof r.goal==typeof Array?r.goal.includes(t):t===r.goal},this.path_cost=function(t,n,r,o){return t+1},this.value=function(t){throw Error("Not Implemented")},this.initial=t,this.goal=n},n=function(t){return t},r=function(t,r,o){return void 0===(e=function(n){return t.nconflicts(r,n,o)})&&(e=n),function(t){for(var n=[].concat(t),r=n.length-1;r>0;r--){var o=Math.floor(Math.random()*(r+1)),e=[n[o],n[r]];n[r]=e[0],n[o]=e[1]}return n}(t.domains[r]).reduce((function(t,n){return e(t)<e(n)?t:n}));var e};exports.CSP=function(t){var n,r;function o(n,r,o,e){var i;return(i=t.call(this,[])||this).assign=function(t,n,r){r[t]=n,i.nassigns+=1},i.unassign=function(t,n){n.hasOwnProperty(t)&&delete n[t]},i.nconflicts=function(t,n,r){return Object.keys(i.neighbors).filter((function(o){return r.hasOwnProperty(e=o)&&!i.constraints(t,n,e,r[e]);var e})).length},i.display=function(t){console.log(t)},i.conflicted_vars=function(t){return i.variables.filter((function(n){return i.nconflicts(n,t[n],t)>0}))},i.variables=n||Object.keys(r),i.domains=r,i.neighbors=o,i.constraints=e,i.curr_domains=void 0,i.nassigns=0,i}return r=t,(n=o).prototype=Object.create(r.prototype),n.prototype.constructor=n,n.__proto__=r,o}(t),exports.Problem=t,exports.min_conflicts=function(t,n){void 0===n&&(n=1e5);var o,e={};t.variables.forEach((function(n){var o=r(t,n,e);t.assign(n,o,e)}));for(var i=0;i<n;i++){var s=t.conflicted_vars(e);if(!(s.length>0))return e;var a=(o=s)[Math.floor(Math.random()*o.length)],c=r(t,a,e);t.assign(a,c,e)}},exports.min_conflicts_value=r;
 //# sourceMappingURL=csps.cjs.production.min.js.map

dist/csps.esm.js

@@ -263,56 +263,3 @@ function _inheritsLoose(subClass, superClass) {
 
-/* Min-conflicts hill-climbing search for CSPs functions */
-
 /**
- * Solve a CSP by stochastic hill-climbing on the number of conflicts.
- *
- * @param  {CSP<T>} aCSP
- * @param  {number=100000} max_steps
- * @returns LooseObject
- */
-var min_conflicts = function min_conflicts(aCSP, max_steps) {
-  if (max_steps === void 0) {
-    max_steps = 100000;
-  }
-
-  // Generate a complete assignment for all variables (probably with conflicts)
-  var current = {};
-  aCSP.variables.forEach(function (variable) {
-    var val = min_conflicts_value(aCSP, variable, current);
-    aCSP.assign(variable, val, current);
-  }); // Now repeatedly choose a random conflicted variable and change it
-
-  for (var i = 0; i < max_steps; i++) {
-    var conflicted = aCSP.conflicted_vars(current);
-
-    if (!(conflicted.length > 0)) {
-      return current;
-    }
-
-    var variable = random_choice(conflicted);
-    var val = min_conflicts_value(aCSP, variable, current);
-    aCSP.assign(variable, val, current);
-  } // If no solution can be found.
-
-
-  return undefined;
-};
-/**
- * Return the value that will give var the least number of conflicts.
- * If there is a tie, choose at random.
- *
- * @param  {CSP<T>} aCSP
- * @param  {T} variable
- * @param  {LooseObject<T[]>} current
- * @returns T
- */
-
-var min_conflicts_value = function min_conflicts_value(aCSP, variable, current) {
-  var num_conflicts = function num_conflicts(val) {
-    return aCSP.nconflicts(variable, val, current);
-  };
-
-  return argmin_random_tie(aCSP.domains[variable], num_conflicts);
-};
-/**
  * Return a random element from an array.
@@ -324,3 +271,2 @@ *
  */
-
 var random_choice = function random_choice(arr) {
@@ -380,3 +326,57 @@ return arr[Math.floor(Math.random() * arr.length)];
 
-export { CSP, Problem, argmin_random_tie, identity, min_conflicts, min_conflicts_value, random_choice, shuffle_array };
+/* Min-conflicts hill-climbing search for CSPs functions */
+/**
+ * Solve a CSP by stochastic hill-climbing on the number of conflicts.
+ *
+ * @param  {CSP<T>} aCSP
+ * @param  {number=100000} max_steps
+ * @returns LooseObject
+ */
+
+var min_conflicts = function min_conflicts(aCSP, max_steps) {
+  if (max_steps === void 0) {
+    max_steps = 100000;
+  }
+
+  // Generate a complete assignment for all variables (probably with conflicts)
+  var current = {};
+  aCSP.variables.forEach(function (variable) {
+    var val = min_conflicts_value(aCSP, variable, current);
+    aCSP.assign(variable, val, current);
+  }); // Now repeatedly choose a random conflicted variable and change it
+
+  for (var i = 0; i < max_steps; i++) {
+    var conflicted = aCSP.conflicted_vars(current);
+
+    if (!(conflicted.length > 0)) {
+      return current;
+    }
+
+    var variable = random_choice(conflicted);
+    var val = min_conflicts_value(aCSP, variable, current);
+    aCSP.assign(variable, val, current);
+  } // If no solution can be found.
+
+
+  return undefined;
+};
+/**
+ * Return the value that will give var the least number of conflicts.
+ * If there is a tie, choose at random.
+ *
+ * @param  {CSP<T>} aCSP
+ * @param  {T} variable
+ * @param  {LooseObject<T[]>} current
+ * @returns T
+ */
+
+var min_conflicts_value = function min_conflicts_value(aCSP, variable, current) {
+  var num_conflicts = function num_conflicts(val) {
+    return aCSP.nconflicts(variable, val, current);
+  };
+
+  return argmin_random_tie(aCSP.domains[variable], num_conflicts);
+};
+
+export { CSP, Problem, min_conflicts, min_conflicts_value };
 //# sourceMappingURL=csps.esm.js.map

dist/min_conflicts.d.ts

@@ -21,34 +21,1 @@ import { CSP } from "./csp";
 export declare const min_conflicts_value: <T extends string>(aCSP: CSP<T>, variable: T, current: LooseObject<T[]>) => T[];
-/**
- * Return a random element from an array.
- *
- * @param  {T[]} arr
- * @returns T
- * Ref: https://stackoverflow.com/a/4550514/9931154
- */
-export declare const random_choice: <T>(arr: T[]) => T;
-/**
- * Shuffle the values of an array using Durstenfeld shuffle
- * Returns a copy of the array.
- *
- * @param  {any[]} arr
- * @returns any
- * Ref: https://stackoverflow.com/a/12646864/9931154
- */
-export declare const shuffle_array: (arr: any[]) => any[];
-/**
- * Returns the paramter
- *
- * @param  {any} val
- * @returns any
- */
-export declare const identity: (val: any) => any;
-/**
- * Return a minimum element of seq; break ties at random.
- *
- * @param  {any[]} seq
- * @param  {(val:any)=>number=identity} key
- * @returns any
- * Ref for reduce(): https://stackoverflow.com/a/31844649/9931154
- */
-export declare const argmin_random_tie: (seq: any[], key?: (val: any) => number) => any;

package.json

@@ -7,6 +7,9 @@ {
   "description": "Tools to solve constraint satisfaction problems",
-  "version": "1.0.4",
+  "version": "1.0.5",
   "license": "MIT",
   "keywords": [
-    "constraint-satisfaction-problems"
+    "constraint-satisfaction-problems",
+    "aima",
+    "typescript",
+    "min-conflicts"
   ],
@@ -34,3 +37,4 @@ "repository": {
     "size": "size-limit",
-    "analyze": "size-limit --why"
+    "analyze": "size-limit --why",
+    "build:docs": "typedoc --out docs src --theme node_modules/eledoc/bin/default/"
   },
@@ -60,2 +64,3 @@ "peerDependencies": {},
     "@types/seedrandom": "2.4.28",
+    "eledoc": "0.2.1",
     "husky": "^4.3.6",
@@ -66,4 +71,5 @@ "seedrandom": "3.0.5",
     "tslib": "^2.0.3",
+    "typedoc": "0.20.14",
     "typescript": "^4.1.3"
   }
 }

README.md

@@ -1,12 +0,18 @@
-# CSPS
+# csps
 
 Tools to solve [constraint satisfaction problems](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem): **C**onstraint **S**atisfaction **P**roblem **S**olvers.
 
-![npm](https://img.shields.io/npm/v/csps.svg?cacheSeconds=2592000)
-![Node](https://img.shields.io/badge/node-%3E%3D10-blue.svg?cacheSeconds=2592000)
-![npm bundle size](https://img.shields.io/bundlephobia/minzip/csps.svg?cacheSeconds=2592000)
-![GitHub Workflow Status](https://img.shields.io/github/workflow/status/charkour/csps/CI.svg?cacheSeconds=2592000)
+<a href="https://www.npmjs.com/package/csps"><img src="https://img.shields.io/npm/v/csps.svg" alt="npm version"></a>
+<a href="" disabled><img src="https://img.shields.io/badge/node-%3E%3D10-blue.svg?cacheSeconds=2592000" alt="node >= 10"></a>
+<a href="https://www.npmjs.com/package/csps"><img src="https://img.shields.io/bundlephobia/minzip/csps.svg" alt="size < 1k"></a>
+<a href="https://github.com/charkour/csps"><img src="https://img.shields.io/github/workflow/status/charkour/csps/CI.svg" alt="build status"></a>
 
 > Inspired by [Russell and Norvig's "Artificial Intelligence - A Modern Approach" Python code](https://github.com/aimacode/aima-python) and modified under the MIT license.
 
+## Background
+
+A CSP is a specific type of problem that is represented by states and a goal state. The factored representation of each problem state consists of a set of variables and a value (set of attributes) for each. The problem is considered solve, when all values for each variable satisfy all constraints (Russell, Norvig 2010).
+
+Some example of CSPs would be Sudoku, crosswords, scheduling, map-coloring, n-queens, zebra puzzle, and many others. The tools in this `csps` package help setup and solve CSPs.
+
 ## Installation and Example Usage
@@ -20,3 +26,3 @@
 
-app.ts:
+index.ts:
 
@@ -27,56 +33,25 @@ ```ts
 // Setup your problem
-const variables = ["cs108", "cs112", "cs212", "cs214"];
-const possible_attributes = [
-  ["mwf800", "nh253", "norman"],
-  ["mwf800", "nh253", "vanderlinden"],
-  ["mwf800", "nh253", "adams"],
-  ["mwf800", "sb382", "norman"],
-  ["mwf800", "sb382", "vanderlinden"],
-  ["mwf800", "sb382", "adams"],
-  ["mwf900", "nh253", "norman"],
-  ["mwf900", "nh253", "vanderlinden"],
-  ["mwf900", "nh253", "adams"],
-  ["mwf900", "sb382", "norman"],
-  ["mwf900", "sb382", "vanderlinden"],
-  ["mwf900", "sb382", "adams"],
+const variables = [
+  /* array of strings */
 ];
 const domains = {
-  cs108: possible_attributes,
-  cs112: possible_attributes,
-  cs212: possible_attributes,
-  cs214: possible_attributes,
+  /* var: possible_attributes<string>[] */
 };
 const neighbors = {
-  cs108: ["cs112", "cs212", "cs214"],
-  cs112: ["cs108", "cs212", "cs214"],
-  cs212: ["cs108", "cs112", "cs214"],
-  cs214: ["cs108", "cs112", "cs212"],
+  /* var: neighbors<string>[] */
 };
 const constraints = (
-  class1: string,
-  c1Attributes: string[],
-  class2: string,
-  c2Attributes: string[],
+  var1: string,
+  var1Attributes: string[],
+  var2: string,
+  var2Attributes: string[],
 ): boolean => {
-  /*
-    Constraints for class scheduling
-    c1 and c2 are tuples in the form (time, room, faculty)
-    returns true if constraints are met.
-    The constraint that there is only one section of class
-    is implicit because classes are variables.
-  */
-  // Return true if same class.
-  if (class1 === class2) {
+  // Return true if same variable.
+  if (var1 === var2) {
     return true;
   }
 
-  // Check to make sure faculty is not teaching at the same time
-  if (c1Attributes[0] === c2Attributes[0] && c1Attributes[2] === c2Attributes[2]) {
-    return false;
-  }
+  // more constraints that return false...
 
-  // Check to make sure class is not in the same room at the same time
-  if (c1Attributes[0] === c2Attributes[0] && c1Attributes[1] === c2Attributes[1]) {
-    return false;
-  }
+  // else, return true
   return true;
@@ -90,14 +65,29 @@ };
 console.log(res);
-// {
-//   cs108: [ 'mwf800', 'sb382', 'norman' ],
-//   cs112: [ 'mwf900', 'nh253', 'norman' ],
-//   cs212: [ 'mwf800', 'nh253', 'vanderlinden' ],
-//   cs214: [ 'mwf900', 'sb382', 'adams' ]
-// } // or something similar.
 ```
 
-View the [example](https://github.com/charkour/csps/tree/main/example) for information on how to run the example locally.
+### Demo
 
+View the [example](https://github.com/charkour/csps/tree/main/example) for more in-depth example code.
+
+## API
+
+### Search Functions
+
+Currently, Min-conflicts Hill Climbing is the only search function supported.
+
+- [x] Min-conflicts Hill Climbing
+- [ ] AC3
+- [ ] AC3b
+- [ ] AC4
+- [ ] Backtracking
+
+Please view the [docs](https://charkour.github.io/csps/) to see the full API.
+
 ## Contributing
 
 Please feel free to create issues or make PRs.
+
+## Acknowledgements
+
+- Thank you to Russell and Norvig for their _AIMA_ textbook and code.
+- Thanks you to TSDX, TypeDoc and other open source packages that made this package possible.

src/min_conflicts.ts

@@ -5,2 +5,3 @@ /* Min-conflicts hill-climbing search for CSPs functions */
 import { LooseObject } from "./interfaces";
+import { argmin_random_tie, random_choice } from "./utils";
 
@@ -56,55 +57,1 @@ /**
 };
-
-/**
- * Return a random element from an array.
- *
- * @param  {T[]} arr
- * @returns T
- * Ref: https://stackoverflow.com/a/4550514/9931154
- */
-export const random_choice = <T>(arr: T[]): T => {
-  return arr[Math.floor(Math.random() * arr.length)];
-};
-
-/**
- * Shuffle the values of an array using Durstenfeld shuffle
- * Returns a copy of the array.
- *
- * @param  {any[]} arr
- * @returns any
- * Ref: https://stackoverflow.com/a/12646864/9931154
- */
-export const shuffle_array = (arr: any[]): any[] => {
-  const array = [...arr];
-  for (let i = array.length - 1; i > 0; i--) {
-    const j = Math.floor(Math.random() * (i + 1));
-    [array[i], array[j]] = [array[j], array[i]];
-  }
-  return array;
-};
-
-/**
- * Returns the paramter
- *
- * @param  {any} val
- * @returns any
- */
-export const identity = (val: any): any => val;
-
-/**
- * Return a minimum element of seq; break ties at random.
- *
- * @param  {any[]} seq
- * @param  {(val:any)=>number=identity} key
- * @returns any
- * Ref for reduce(): https://stackoverflow.com/a/31844649/9931154
- */
-export const argmin_random_tie = (
-  seq: any[],
-  // seq: T[][], // TODO: Is this better?
-  key: (val: any) => number = identity,
-): any => {
-  return shuffle_array(seq).reduce((prev, curr) => {
-    return key(prev) < key(curr) ? prev : curr;
-  });
-};

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Number of package files

22

increased by10%

Worsened metrics

Total package byte prevSize

99643

decreased by-0.18%

Dev dependency count

11

increased by22.22%

Lines of code

1262

decreased by-0.32%

Number of lines in readme file

91

decreased by-9.9%

No dependency changes