fork(1) download
  1. importPackage(java.io);
  2. importPackage(java.lang);
  3.  
  4. // your code goes here
  5.  
  6.  
  7.  
  8.  
  9. //==========================================
  10. // lib Bin Heap from http://e...content-available-to-author-only...t.net/1st_edition/appendix2.html
  11.  
  12. function BinaryHeap(scoreFunction){
  13. this.content = [];
  14. this.scoreFunction = scoreFunction;
  15. }
  16.  
  17. BinaryHeap.prototype = {
  18. push: function(element) {
  19. // Add the new element to the end of the array.
  20. this.content.push(element);
  21. // Allow it to bubble up.
  22. this.bubbleUp(this.content.length - 1);
  23. },
  24.  
  25. pop: function() {
  26. // Store the first element so we can return it later.
  27. var result = this.content[0];
  28. // Get the element at the end of the array.
  29. var end = this.content.pop();
  30. // If there are any elements left, put the end element at the
  31. // start, and let it sink down.
  32. if (this.content.length > 0) {
  33. this.content[0] = end;
  34. this.sinkDown(0);
  35. }
  36. return result;
  37. },
  38.  
  39. remove: function(node) {
  40. var length = this.content.length;
  41. // To remove a value, we must search through the array to find
  42. // it.
  43. for (var i = 0; i < length; i++) {
  44. if (this.content[i] != node) continue;
  45. // When it is found, the process seen in 'pop' is repeated
  46. // to fill up the hole.
  47. var end = this.content.pop();
  48. // If the element we popped was the one we needed to remove,
  49. // we're done.
  50. if (i == length - 1) break;
  51. // Otherwise, we replace the removed element with the popped
  52. // one, and allow it to float up or sink down as appropriate.
  53. this.content[i] = end;
  54. this.bubbleUp(i);
  55. this.sinkDown(i);
  56. break;
  57. }
  58. },
  59.  
  60. size: function() {
  61. return this.content.length;
  62. },
  63.  
  64. bubbleUp: function(n) {
  65. // Fetch the element that has to be moved.
  66. var element = this.content[n], score = this.scoreFunction(element);
  67. // When at 0, an element can not go up any further.
  68. while (n > 0) {
  69. // Compute the parent element's index, and fetch it.
  70. var parentN = Math.floor((n + 1) / 2) - 1,
  71. parent = this.content[parentN];
  72. // If the parent has a lesser score, things are in order and we
  73. // are done.
  74. if (score >= this.scoreFunction(parent))
  75. break;
  76.  
  77. // Otherwise, swap the parent with the current element and
  78. // continue.
  79. this.content[parentN] = element;
  80. this.content[n] = parent;
  81. n = parentN;
  82. }
  83. },
  84.  
  85. sinkDown: function(n) {
  86. // Look up the target element and its score.
  87. var length = this.content.length,
  88. element = this.content[n],
  89. elemScore = this.scoreFunction(element);
  90.  
  91. while(true) {
  92. // Compute the indices of the child elements.
  93. var child2N = (n + 1) * 2, child1N = child2N - 1;
  94. // This is used to store the new position of the element,
  95. // if any.
  96. var swap = null;
  97. // If the first child exists (is inside the array)...
  98. if (child1N < length) {
  99. // Look it up and compute its score.
  100. var child1 = this.content[child1N],
  101. child1Score = this.scoreFunction(child1);
  102. // If the score is less than our element's, we need to swap.
  103. if (child1Score < elemScore)
  104. swap = child1N;
  105. }
  106. // Do the same checks for the other child.
  107. if (child2N < length) {
  108. var child2 = this.content[child2N],
  109. child2Score = this.scoreFunction(child2);
  110. if (child2Score < (swap == null ? elemScore : child1Score))
  111. swap = child2N;
  112. }
  113.  
  114. // No need to swap further, we are done.
  115. if (swap == null) break;
  116.  
  117. // Otherwise, swap and continue.
  118. this.content[n] = this.content[swap];
  119. this.content[swap] = element;
  120. n = swap;
  121. }
  122. }
  123. };
  124.  
  125.  
  126.  
  127.  
  128. //========================
  129. // Program
  130.  
  131.  
  132. function isPalindrome(number) {
  133. var numberStr = String(number);
  134. var reverse = numberStr.split("").reverse().join("");
  135.  
  136. return (reverse == numberStr);
  137. }
  138.  
  139. function hash(point) {
  140. return (point.x*10000000)+point.y;
  141. }
  142.  
  143. function getMaxPalindrome(multiplierLength) {
  144.  
  145. if (multiplierLength % 2 == 0 ) {
  146. return getMaxPalindromeEvenLength(multiplierLength);
  147. }
  148.  
  149. var min = Math.pow(10, multiplierLength - 1);
  150. var max = Math.pow(10, multiplierLength) - 1;
  151.  
  152. var visitedPoints = {};
  153.  
  154. var pointsWave = new BinaryHeap(function(point) {
  155. return ( - point.product);
  156. });
  157.  
  158.  
  159. function addPointToWave(point) {
  160. if (point.x > point.y) {
  161. return;
  162. }
  163. if (point.x < min || point.y < min) {
  164. return;
  165. }
  166. if (visitedPoints[hash(point)] === undefined) {
  167. pointsWave.push({
  168. x: point.x,
  169. y: point.y,
  170. product: (point.x * point.y)
  171. });
  172. visitedPoints[hash(point)] = true;
  173. }
  174. }
  175.  
  176. addPointToWave({x: max, y:max});
  177.  
  178. while (true) {
  179.  
  180. var point = pointsWave.pop();
  181. if ( ! point) {
  182. break;
  183. }
  184.  
  185. if (isPalindrome(point.product)) {
  186. return point.product;
  187. }
  188.  
  189. addPointToWave({x: point.x - 1, y: point.y});
  190. addPointToWave({x: point.x, y: point.y - 1});
  191. addPointToWave({x: point.x - 1, y: point.y - 1});
  192. }
  193.  
  194. return null;
  195. }
  196.  
  197. function getMaxPalindromeEvenLength(multiplierLength) {
  198. if (multiplierLength % 2 != 0 ) {
  199. throw 'Incorrect len';
  200. }
  201.  
  202. var halfLength = Math.round(multiplierLength / 2);
  203.  
  204. return Array(halfLength+1).join(9)
  205. + Array(multiplierLength+1).join(0)
  206. + Array(halfLength+1).join(9);
  207. }
  208.  
  209.  
  210.  
  211. //--------------------------------------
  212. // Run
  213.  
  214. for (var test = 3; test <= 3; test++) {
  215.  
  216. print('test: '+test);
  217. var timer = new Date();
  218. var palindromeNumber = getMaxPalindrome(test);
  219. print('result: '+palindromeNumber);
  220. print('time: '+(new Date() - timer)+' ms');
  221. print('');
  222. }
  223.  
  224.  
Success #stdin #stdout 0.82s 323264KB
stdin
Standard input is empty
stdout
test: 3
result: 906609
time: 304 ms