fork(4) download
copy 
  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 = 1; test <= 8; 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.  
Time limit exceeded #stdin #stdout 5s 325120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test: 1
result: 9
time: 18 ms

test: 2
result: 9009
time: 1 ms

test: 3
result: 906609
time: 287 ms

test: 4
result: 99000099
time: 10 ms

test: 5
result: 9966006699
time: 1070 ms

test: 6
result: 999000000999
time: 0 ms

test: 7
https://ideone.com/HHV5CP
language:
JavaScript (rhino 1.7.9)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!