私は、javascriptでのコードの出現の 9 日目の問題を解決しようとしています。
考えられるすべてのルートを取得するためにバックトラッキングを使用してから、それぞれのコストを計算しています。
私は PHP や C++ などの言語でバックトラッキングを行うことに慣れていますが、JS では行ったことがないので、Google のおかげで、PHP と C++ の両方で&パラメータのような可変パラメータを渡すことができないことがわかりました。
私の意図は、bestRoute変数を最適なルートに割り当てることです。これが問題の解決策だからです。
しかし、いくつかのサイトで return を使用してそうすると、次のような未定義の変数エラーが発生します。
for (var i = 0 ; i < neighborsArray.length ; i++) {
^
TypeError: Cannot read property 'length' of undefined at getCostInNeighbors (/home/freinn/librosjavascript/advent_of_code/day9.js:117:40)
at calculateCost (/home/freinn/librosjavascript/advent_of_code/day9.js:110:17)
これが私の現在のコードです。これは機能せず、最初に定義されたように bestRoute を出力します。
"use strict";
function clone(obj) {
// Handle the 3 simple types, and null or undefined
if (null == obj || "object" != typeof obj) return obj;
// Handle Date
if (obj instanceof Date) {
var copy = new Date();
copy.setTime(obj.getTime());
return copy;
}
// Handle Array
if (obj instanceof Array) {
var copy = [];
for (var i = 0, len = obj.length; i < len; i++) {
copy[i] = clone(obj[i]);
}
return copy;
}
// Handle Object
if (obj instanceof Object) {
var copy = {};
for (var attr in obj) {
if (obj.hasOwnProperty(attr)) {
copy[attr] = clone(obj[attr]);
}
}
return copy;
}
throw new Error("Unable to copy obj! Its type isn't supported.");
}
function generateGraphAsArray(input) {
var lines = input.split("\n");
var getFromTo = /(.*?) to (.*?) = (\d+)/;
var graph = {};
var matches = [];
for (var i = 0 ; i < lines.length ; i++) {
matches = getFromTo.exec(lines[i]);
// console.log(matches[1], matches[2], matches[3]);
var obj = {};
obj['to'] = matches[2];
obj['cost'] = matches[3];
var clonated = clone(obj);
if (!(matches[1] in graph)) {
graph[matches[1]] = [];
}
graph[matches[1]].push(clonated);
if (!(matches[2] in graph)) {
graph[matches[2]] = [];
}
obj['to'] = matches[1];
clonated = clone(obj);
graph[matches[2]].push(clonated);
}
var keys = Object.keys(graph);
var graphArray = [];
var nodeList;
// recuerda: en JS la funcion que no devuelve nada, devuelve algo, undefined
// si no ponemos return en la funcion del map, dara undefined
for (var prop in graph) {
// esto es una clausura sana para poder usar keys
nodeList = graph[prop].map(function(obj) {
return nodeObjectToArray(keys, obj);
});
graphArray.push(nodeList);
}
return graphArray;
}
function nodeObjectToArray(keys, obj) {
var array = new Array(keys.indexOf(obj.to), Number(obj.cost));
return array;
}
function generateAllRoutes(numberOfNodes, graphArray) {
var routes = [];
for (var i = 0 ; i < numberOfNodes; i++) {
var array = [i]
routes.push(array);
}
var bestRoute = generateRangeWithoutUsed([], numberOfNodes);
for (var i = 0 ; i < routes.length; i++) {
bestRoute = generateRoutes(routes[i], numberOfNodes, bestRoute, graphArray);
}
console.log(bestRoute, calculateCost(bestRoute, graphArray));
}
function calculateCost(route, graphArray) {
var limit = graphArray.length - 1;
var cost = 0;
for (var i = 0 ; i < limit ; i++) {
cost += getCostInNeighbors(graphArray[route[i]], route[i+1]);
}
return cost;
}
function getCostInNeighbors(neighborsArray, neighbour) {
for (var i = 0 ; i < neighborsArray.length ; i++) {
if (neighborsArray[i][0] == neighbour) {
return neighborsArray[i][1];
}
}
}
function generateRoutes(currentRoute, numberOfNodes, bestRoute, graphArray) {
if (currentRoute.length == numberOfNodes) {
var currentRouteCost = calculateCost(currentRoute, graphArray);
console.log(currentRouteCost);
if (currentRouteCost < calculateCost(bestRoute, graphArray)) {
return currentRoute;
} else {
return bestRoute;
}
} else {
var possibleNextNodes = generateRangeWithoutUsed(currentRoute, numberOfNodes);
for (var i = 0 ; i < possibleNextNodes.length ; i++) {
currentRoute.push(possibleNextNodes[i]);
generateRoutes(currentRoute, numberOfNodes, bestRoute, graphArray);
currentRoute.splice(-1, 1); // remove the last element
}
}
}
function generateRangeWithoutUsed(used, numberOfNodes) {
var rangeWithoutUsed = [];
for (var i = 0 ; i < numberOfNodes ; i++) {
if (!existInArray(i, used)) {
rangeWithoutUsed.push(i);
}
}
return rangeWithoutUsed;
}
function existInArray(element, array) {
for (var i = 0 ; i < array.length ; i++) {
if (array[i] == element) {
return true;
}
}
return false;
}
var input = "Faerun to Norrath = 129\nFaerun to Tristram = 58\nFaerun to AlphaCentauri = 13\nFaerun to Arbre = 24\nFaerun to Snowdin = 60\nFaerun to Tambi = 71\nFaerun to Straylight = 67\nNorrath to Tristram = 142\nNorrath to AlphaCentauri = 15\nNorrath to Arbre = 135\nNorrath to Snowdin = 75\nNorrath to Tambi = 82\nNorrath to Straylight = 54\nTristram to AlphaCentauri = 118\nTristram to Arbre = 122\nTristram to Snowdin = 103\nTristram to Tambi = 49\nTristram to Straylight = 97\nAlphaCentauri to Arbre = 116\nAlphaCentauri to Snowdin = 12\nAlphaCentauri to Tambi = 18\nAlphaCentauri to Straylight = 91\nArbre to Snowdin = 129\nArbre to Tambi = 53\nArbre to Straylight = 40\nSnowdin to Tambi = 15\nSnowdin to Straylight = 99\nTambi to Straylight = 70";
// var myInput = "a to b = 1\na to c = 2\nb to d = 7\nc to d = 1\nc to e = 3\nd to f = 2\ne to f = 5";
var graphArray = generateGraphAsArray(input);
generateAllRoutes(graphArray.length, graphArray);