API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 11th, 2019
204
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.04 KB | None | 0 0
raw download clone embed print report
  1. (function (AOF) {
  2. function Puzzle (input, code, config) {
  3.  
  4. if (!config) {
  5. config = {};
  6. config.day = 1;
  7. config.part = 1;
  8. }
  9.  
  10. this.day = config.day || 1;
  11. this.part = config.part || 1;
  12.  
  13. this.input = input;
  14. this.code = code;
  15. this.solution = null;
  16. }
  17.  
  18. Puzzle.prototype.constructor = Puzzle;
  19.  
  20. Puzzle.prototype.solve = function () {
  21. if (this.code && typeof this.code === "function") {
  22. this.solution = this.code(this.input);
  23. }
  24. return this.solution;
  25. }
  26.  
  27. AOF.Puzzle = Puzzle;
  28.  
  29. return AOF;
  30. })(window.AdventOfCode || (AdventOfCode = {}))
  31.  
  32. /**/
  33. var input = `################################
  34. ##########################..####
  35. #########################...####
  36. #########################..#####
  37. ########################G..#####
  38. #####################.#.....##.#
  39. #####################..........#
  40. ##############.#####...........#
  41. ########G...G#.####............#
  42. #######......G....#.....#......#
  43. #######...G....GG.#............#
  44. #######G.G.............####....#
  45. #######.#.....#####....E.....###
  46. #######......#######.G.......###
  47. #..####..G..#########.###..#####
  48. #........G..#########.##########
  49. #..#..#G....#########.##########
  50. #.###...E...#########.##########
  51. #####...G.G.#########.##########
  52. ########G....#######..##########
  53. ####..........#####...##########
  54. ####......E........G..##########
  55. #.G..................###########
  56. #G...................###########
  57. ###.....##E.......E..###########
  58. ###....#............############
  59. ###.................############
  60. ##G.....#.............##########
  61. ###########...#E..##..##########
  62. ###########.E...###.E.EE.#######
  63. ###########......#.......#######
  64. ################################`;
  65. /**/
  66.  
  67. /*
  68. var input = `#########
  69. #G......#
  70. #.E.#...#
  71. #..##..G#
  72. #...##..#
  73. #...#...#
  74. #.G...G.#
  75. #.....G.#
  76. #########`;
  77. */
  78.  
  79. var puzzle = new AdventOfCode.Puzzle(
  80. input,
  81. function (input) {
  82. /*
  83. Utility functions
  84. */
  85. const sortByPosition = (a,b) => {
  86. if (a.y < b.y) {
  87. return -1;
  88. }
  89. if (a.y > b.y) {
  90. return 1;
  91. }
  92. if (a.x < b.x) {
  93. return -1;
  94. }
  95. if (a.x > b.x) {
  96. return 1;
  97. }
  98. return 0;
  99. }
  100.  
  101. const sortByHitPoints = (a,b) => {
  102. if (a.hp < b.hp) {
  103. return -1;
  104. }
  105. if (a.hp > b.hp) {
  106. return 1;
  107. }
  108. return sortByPosition(a,b);
  109. }
  110.  
  111. const sortReachableByLength = (a,b) => {
  112. if (a.length !== b.length) {
  113. return a.length - b.length;
  114. }
  115.  
  116. return sortByPosition(a[a.length-1],b[b.length-1]);
  117. }
  118.  
  119. const getPropSum = (array, prop, filter) => {
  120. let sum = 0;
  121. for (let i = 0; i < array.length; i++) {
  122. let toSum = true;
  123. if (filter) {
  124. for (let p in filter) {
  125.  
  126. if (!(p in array[i]) || ((p in array[i]) && array[i][p] !== filter[p])) {
  127. toSum = false;
  128. break;
  129. }
  130.  
  131. }
  132. if (!toSum) {
  133. continue;
  134. }
  135. }
  136. if (toSum) {
  137. sum += array[i][prop];
  138. }
  139. }
  140. return sum;
  141. }
  142.  
  143. const sortPathsByLength = (a,b) => {
  144. if (a.length !== b.length) {
  145. return a.length - b.length;
  146. }
  147.  
  148. return sortByPosition(a[0],b[0]);
  149. }
  150.  
  151. const findByProps = (haystack, props) => {
  152. for (let i = 0; i < haystack.length; i++) {
  153. let found = true;
  154. for (let prop in props) {
  155. if (haystack[i][prop] !== props[prop]) {
  156. found = false;
  157. break;
  158. }
  159. }
  160. if (found) {
  161. return haystack[i];
  162. }
  163. }
  164. return false;
  165. }
  166.  
  167. class Node {
  168. constructor(x, y, occupied) {
  169. this.x = x;
  170. this.y = y;
  171. this.neighbours = {};
  172. this.occupied = !!occupied;
  173. }
  174.  
  175. addNeighbour(dir, node) {
  176. this.neighbours[dir] = node;
  177. node.neighbours[3 - dir] = this;
  178. }
  179. }
  180.  
  181. class Graph {
  182. constructor () {
  183. this.nodes = {};
  184. }
  185.  
  186. addNode (node) {
  187. this.nodes[`${node.y}|${node.x}`] = node;
  188. return this;
  189. }
  190.  
  191. pathExists (node1, node2) {
  192.  
  193. if (
  194. !this.hasNode(node1)
  195. || !this.hasNode(node2)
  196. ) {
  197. return false;
  198. }
  199.  
  200. let visited = [];
  201. let queue = [node1];
  202. while (queue.length) {
  203. let cur = queue.shift();
  204. if (cur === node2) {
  205. return true;
  206. }
  207. visited.push(cur);
  208. for (let prop in cur.neighbours) {
  209. if (!~visited.indexOf(cur.neighbours[prop])) {
  210. visited.push(cur.neighbours[prop]);
  211. queue.push(cur.neighbours[prop])
  212. }
  213. }
  214. }
  215.  
  216. return false;
  217. }
  218.  
  219. hasNode (node) {
  220. if (!(node instanceof Node)) {
  221. return false;
  222. }
  223. if (
  224. !this.nodes[`${node.y}|${node.x}`]
  225. || this.nodes[`${node.y}|${node.x}`] !== node
  226. ) {
  227. return false;
  228. }
  229.  
  230. return true;
  231. }
  232.  
  233. getPath (node1, node2) {
  234. if (!this.pathExists(node1,node2)) {
  235. return [];
  236. }
  237.  
  238. let visited = [];
  239. let queue = [{node : node1, level : 0, prev : null}];
  240. let cur = null;
  241.  
  242. while (queue.length) {
  243. cur = queue.shift();
  244. if (cur.node === node2) {
  245. break;
  246. }
  247. visited.push(cur.node);
  248. for (let prop in cur.node.neighbours) {
  249. if (!~visited.indexOf(cur.node.neighbours[prop])) {
  250. visited.push(cur.node.neighbours[prop]);
  251. queue.push({node : cur.node.neighbours[prop], level:cur.level+1, prev : cur});
  252. }
  253. }
  254. }
  255.  
  256. let path = [];
  257.  
  258. while (cur) {
  259. path.push(cur.node);
  260. cur = cur.prev;
  261. }
  262.  
  263. return path.reverse();
  264. }
  265.  
  266. getNodeFromCoordinates(point) {
  267. return this.nodes[`${point.y}|${point.x}`];
  268. }
  269. }
  270.  
  271. class Entity {
  272. constructor(map, x, y, type, hp, power) {
  273. this.map = map;
  274. this.x = +x;
  275. this.y = +y;
  276. this.type = type;
  277. this.hp = hp;
  278. this.power = power;
  279. this.target = null;
  280. this.alive = true;
  281. }
  282.  
  283. attack (target) {
  284. target.hp -= this.power;
  285. if (target.hp <= 0) {
  286. target.alive = false;
  287. }
  288. }
  289.  
  290. getTargets(sortFn) {
  291. let entities = this.map.entities;
  292. let targets = [];
  293. for (let i = 0; i < entities.length; i++) {
  294. if (entities[i].type !== this.type && entities[i].alive) {
  295. targets.push(entities[i]);
  296. }
  297. }
  298. return sortFn ? targets.sort(sortFn) : targets;
  299. }
  300.  
  301. getRangeCells() {
  302. let cells = [];
  303. let diffs = [[0,-1],[-1,0],[1,0],[0,1]];
  304. let entities = this.map.entities;
  305.  
  306. for (let pos in diffs) {
  307. let x = +this.x + diffs[pos][0];
  308. let y = +this.y + diffs[pos][1];
  309. if (this.map.cells[y] && this.map.cells[y][x] == '.') {
  310. let entityFound = false;
  311. for (let i in entities) {
  312. if (entities[i].x === x && entities[i].y === y && entities[i].alive) {
  313. entityFound = true;
  314. break;
  315. }
  316. }
  317. if (!entityFound) {
  318. cells.push({x : x, y : y});
  319. }
  320. }
  321. }
  322. return cells;
  323. }
  324.  
  325. getEnemyRangeCells() {
  326. let targets = this.getTargets();
  327. let cells = [];
  328.  
  329. for (let i = 0; i < targets.length; i++) {
  330. let curCells = targets[i].getRangeCells();
  331. for (let j = 0; j < curCells.length; j++) {
  332. if (findByProps(cells,curCells[j]) === false) {
  333. cells.push(curCells[j]);
  334. }
  335. }
  336. }
  337.  
  338. return cells.sort(sortByPosition);
  339. }
  340.  
  341. getEnemyReachableRangeCells() {
  342. let cells = this.getEnemyRangeCells();
  343. let self = this;
  344. cells = cells.filter(function (el) {
  345. return self.map.graph.pathExists(
  346. self.map.graph.nodes[`${self.y}|${self.x}`],
  347. self.map.graph.nodes[`${el.y}|${el.x}`]
  348. );
  349. });
  350.  
  351. return cells;
  352. }
  353.  
  354. getCurrentNode() {
  355. return this.map.graph.nodes[`${this.y}|${this.x}`];
  356. }
  357.  
  358. getShortestPathToReach() {
  359. let toReach = this.getEnemyReachableRangeCells();
  360. let paths = [];
  361. for (let i=0; i<toReach.length; i++) {
  362. let node = this.map.graph.nodes[`${toReach[i].y}|${toReach[i].x}`];
  363. let curPath = this.map.graph.getPath(this.getCurrentNode(),node);
  364. if (curPath.length) {
  365. paths.push(curPath);
  366. }
  367. }
  368. paths.sort(sortReachableByLength);
  369. let path = paths[0] || [];
  370.  
  371. if (path) {
  372. let target = path[path.length - 1]
  373. let neighbours = this.getRangeCells();
  374. paths = [];
  375.  
  376. for (let prop in neighbours) {
  377. /* TODO */
  378. let nodeNeighbour = this.map.graph.getNodeFromCoordinates(neighbours[prop]);
  379. let curPath = this.map.graph.getPath(nodeNeighbour, target);
  380. if (curPath.length) {
  381. paths.push(curPath);
  382. }
  383. }
  384. }
  385.  
  386. return paths.sort(sortPathsByLength)[0];
  387. }
  388.  
  389. getReachableTarget() {
  390. let targets = this.getTargets(sortByHitPoints);
  391. let reachable = [];
  392. for (let i = 0; i < targets.length; i++) {
  393. if (
  394. (targets[i].y === this.y && (targets[i].x == this.x-1 || targets[i].x == this.x+1))
  395. || (targets[i].x === this.x && (targets[i].y == this.y-1 || targets[i].y == this.y+1))
  396. ) {
  397. reachable.push(targets[i]);
  398. }
  399. }
  400. if (!reachable.length) {
  401. this.target = null;
  402. } else {
  403. reachable.sort(sortByHitPoints);
  404. this.target = reachable.shift();
  405. }
  406. return this.target;
  407. }
  408. }
  409.  
  410. class Map {
  411. constructor(cells, entities) {
  412. this.cells = cells;
  413. this.entities = entities;
  414. this.graph = null;
  415. }
  416.  
  417. static create (string) {
  418. string = string.split("\n");
  419. let entities = [];
  420. let map = new this([],[]);
  421. for (let y in string) {
  422. string[y] = string[y].split('');
  423. for (let x in string[y]) {
  424. switch(string[y][x]) {
  425. case 'G':
  426. case 'E':
  427. let type = string[y][x] === 'G' ? 'Goblin' : 'Elf';
  428. entities.push(new Entity(map, x, y, type, 200, 3));
  429. string[y][x] = '.';
  430. break;
  431. }
  432. }
  433. }
  434. for (var i = 0; i < entities.length; i++) {
  435. entities.map = map;
  436. }
  437. map.entities = entities;
  438. map.cells = string;
  439.  
  440. return map;
  441. }
  442.  
  443. resetGraph() {
  444. let graph = this.graph = new Graph();
  445. let cells = this.cells;
  446. let entities = Array.prototype.slice.call(this.entities);
  447.  
  448. for (let y = 0; y < cells.length; y++) {
  449. for (let x = 0; x < cells[y].length; x++) {
  450. let cell = cells[y][x];
  451. if (cell === '.') {
  452. let node = new Node(x,y);
  453. graph.nodes[`${y}|${x}`] = node;
  454. if (findByProps(entities, {x, y, alive: true})) {
  455. node.occupied = true;
  456. if (graph.nodes[`${y-1}|${x}`] && !graph.nodes[`${y-1}|${x}`].occupied) {
  457. node.neighbours[0] = graph.nodes[`${y-1}|${x}`];
  458. }
  459. if (graph.nodes[`${y}|${x-1}`] && !graph.nodes[`${y}|${x-1}`].occupied) {
  460. node.neighbours[1] = graph.nodes[`${y}|${x-1}`];
  461. }
  462. } else {
  463. if (graph.nodes[`${y-1}|${x}`] && !graph.nodes[`${y-1}|${x}`].occupied) {
  464. node.addNeighbour(0,graph.nodes[`${y-1}|${x}`]);
  465. } else if (graph.nodes[`${y-1}|${x}`]) {
  466. graph.nodes[`${y-1}|${x}`].neighbours[3] = node;
  467. }
  468. if (graph.nodes[`${y}|${x-1}`] && !graph.nodes[`${y}|${x-1}`].occupied) {
  469. node.addNeighbour(1,graph.nodes[`${y}|${x-1}`]);
  470. } else if (graph.nodes[`${y}|${x-1}`]) {
  471. graph.nodes[`${y}|${x-1}`].neighbours[2] = node;
  472. }
  473. }
  474. }
  475. }
  476. }
  477. this.graph = graph;
  478. return graph;
  479. }
  480.  
  481. print (entity, filter, filteredArray, chr) {
  482. let char = '.';
  483. let filtered = [];
  484. let string = '';
  485.  
  486. if (filteredArray) {
  487. filtered = filteredArray;
  488. if (chr) {
  489. char = chr;
  490. }
  491. } else if (entity) {
  492. switch (filter) {
  493. case 'getEnemyRangeCells':
  494. char = '?';
  495. break;
  496. case 'getEnemyRangeCells':
  497. char = '@';
  498. break;
  499. }
  500. filtered = entity[filter]();
  501. }
  502.  
  503. for (let y = 0; y < this.cells.length; y++) {
  504. for (let x = 0; x < this.cells[y].length; x++) {
  505. let ent = null;
  506. if (findByProps(filtered, {x, y})) {
  507. string += char;
  508. } else if (ent = findByProps(this.entities, {x, y, alive: true})) {
  509. string += ent.type === 'Goblin' ? 'G' : 'E';
  510. } else {
  511. string += this.cells[y][x];
  512. }
  513. }
  514. string += "\n"
  515. }
  516. return string;
  517. }
  518. }
  519.  
  520. /* BEFORE */
  521. let map = Map.create(input);
  522. /* IN THE LOOP */
  523. let newPrinted = null;
  524. let rounds = 0;
  525. let ended = false;
  526. let sum = 0;
  527. let solution = NaN;
  528. while (!ended) {
  529. rounds++;
  530. let entities = map.entities.sort(sortByPosition);
  531. let graph = map.resetGraph();
  532. for (let i = 0; i < entities.length; i++) {
  533. if (!entities[i].alive) {
  534. continue;
  535. }
  536. let rangeCells = entities[i].getRangeCells();
  537. let curTarget = entities[i].getReachableTarget();
  538. console.log(map.print(null,null,rangeCells,'$'));
  539. if (curTarget === null) {
  540. let path = entities[i].getShortestPathToReach();
  541. console.log(map.print(null,null,path,'w'));
  542. if (path) {
  543. entities[i].x = path[0].x;
  544. entities[i].y = path[0].y;
  545. curTarget = entities[i].getReachableTarget();
  546. if (curTarget) {
  547. entities[i].attack(curTarget);
  548. }
  549. }
  550. } else {
  551. entities[i].attack(curTarget);
  552. }
  553. let targets = entities[i].getTargets();
  554.  
  555. if (targets.length === 0) {
  556. sum = getPropSum(entities,'hp', {alive : true});
  557. solution = sum * (rounds - 1);
  558. console.log('solution', rounds - 1, sum, solution, entities);
  559. ended = true;
  560. break;
  561. }
  562.  
  563. }
  564. }
  565.  
  566.  
  567. },
  568. {
  569. day : 15,
  570. part : 1
  571. }
  572. );
  573.  
  574. console.log(puzzle.solve());
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!