Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Squares stuff
- */
- let squaresLessOrEqualTo = function(n) {
- let count = Math.floor(Math.sqrt(n));
- let squares = [];
- for(let i = 1; i <= count; i++) {
- squares.push(i * i);
- }
- return squares;
- };
- let squareSums = function(n) {
- let allSquares = squaresLessOrEqualTo(n);
- let sums = [];
- //O(n^2), find faster way
- for(let i = 0; i < allSquares.length; i++) {
- for(let j = 0; j < allSquares.length; j++) {
- let a = allSquares[i];
- let b = allSquares[j];
- if(a + b === n) sums.push([a, b]);
- }
- }
- return sums;
- };
- /**
- * Graph stuff
- */
- let createVertex = function(xPos, yPos, d) {
- return {
- xPos: xPos,
- yPos: yPos,
- d: d //distance (in terms of number of coins) from origin
- };
- }
- let createEdge = function(v1, v2, w) {
- return {
- v1: v1,
- v2: v2,
- w: w
- };
- }
- //recursive function.
- //used for creating graph only
- let appendChildVertices = function(vertices, edges, parentVertex, coinTypes, eMod) {
- print('current x position: ' + parentVertex.xPos);
- print('current y position: ' + parentVertex.yPos);
- let newVertices = [];
- for(let i = 0; i < coinTypes.length; i++) {
- //check to see if new vertex won't go out of bounds
- let futureConvVal = parentVertex.xPos + coinTypes[i][0];
- let futureInfoVal = parentVertex.yPos + coinTypes[i][1];
- print('future x position: ' + futureConvVal);
- print('future y position: ' + futureInfoVal);
- if(futureConvVal <= eMod && futureInfoVal <= eMod) {
- print('position valid!');
- if(!vertices[futureConvVal]) {
- vertices[futureConvVal] = [];
- }
- let newEdge;
- if(vertices[futureConvVal][futureInfoVal]) {
- print('use existing vertex');
- newEdge = createEdge(parentVertex, vertices[futureConvVal][futureInfoVal], 1);
- edges.push(newEdge);
- } else {
- print('create new vertex');
- let newVertex = createVertex(futureConvVal, futureInfoVal, Number.MAX_SAFE_INTEGER);
- newEdge = createEdge(parentVertex, newVertex, 1);
- edges.push(newEdge);
- vertices[futureConvVal][futureInfoVal] = newVertex;
- newVertices.push(newVertex);
- }
- }
- }
- for(let i = 0; i < newVertices.length; i++) {
- appendChildVertices(vertices, edges, newVertices[i], coinTypes, eMod);
- }
- }
- let createGraph = function(coinTypes, eMod) {
- //vertices are located by their x and y positions
- let vertices = [];
- let edges = [];
- //initial position
- let originVertex = createVertex(0, 0, 0);
- vertices[0] = [];
- vertices[0][0] = originVertex;
- appendChildVertices(vertices, edges, originVertex, coinTypes, eMod);
- return {
- vertices: vertices,
- edges: edges
- };
- }
- /**
- * Problem stuff
- */
- let graph = createGraph([[1, 2], [3, 5], [50, 3], [4, 6]], 566);
- print(graph.edges.length);
- let vertexCount = 0;
- for(let i = 0 ; i < graph.vertices.length; i++) {
- if(graph.vertices[i]) {
- for(let j = 0; j < graph.vertices[i].length; j++) {
- if(graph.vertices[i][j]) vertexCount++;
- }
- }
- }
- print(vertexCount);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement