NoNameCracksInc

Subset sum problem bruteforce solver

Sep 8th, 2016
351
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.96 KB | None | 0 0
  1. <!DOCTYPE html>
  2.  
  3. <body>
  4. Subset sum problem bruteforce solver
  5. <canvas id="g" width="100%" height="100%" style="position:absolute;left:0;top:0;">
  6.  
  7. <script>
  8.  
  9. var set = [-98, -96, -95, -94, -84, -75, -73, -66, -61, -60, -58, -55, -54, -53, -44, -37, -26, -21, -18, -17, -9, -3, 1, 2, 3, 5, 13, 14, 15, 22, 27, 28, 36, 43, 46, 47, 48, 55, 58, 60, 63, 70, 72, 74, 76, 78, 80, 91, 95, 97];
  10. var loopinc = 0;
  11. var success = 0;
  12. var average = [];
  13. var k = 20;
  14. var lastway = "down";
  15.  
  16. function random_unique_index_generator(number_of_indexes,top_index)
  17. {
  18.  
  19. var cycles = 0;
  20. var storage = [];
  21.  
  22. parental_loop:
  23. while(cycles != number_of_indexes)
  24. {
  25.  
  26. loopinc++;
  27.  
  28. var push_waiter = random_number(0,top_index);
  29.  
  30. for(var i=0;i<=storage.length-1;i++)
  31. {
  32.  
  33. loopinc++;
  34.  
  35. if(storage[i] == push_waiter)
  36. continue parental_loop;
  37. }
  38. storage[cycles] = push_waiter;
  39. cycles++;
  40. }
  41. return storage;
  42. }
  43.  
  44. function random_number(minimum,maximum){return Math.floor(Math.random() * (maximum - minimum + 1)) + minimum;}
  45.  
  46. function engage()
  47. {
  48. var subset = random_unique_index_generator(random_number(1,set.length),set.length-1);
  49. var sum = 0;
  50.  
  51. for(var i=0;i<=subset.length-1;i++)
  52. {
  53.  
  54. loopinc++;
  55.  
  56. sum = sum + set[subset[i]];
  57. }
  58.  
  59. if(sum == 0)
  60. {
  61. success++;
  62. average[success-1] = success/loopinc;
  63. return "["+subset + "] in "+loopinc + " cycles. Total finds: "+success+". Average finds per generic cycle: "+average[success-1]+(average[success-1]>average[success-2] ? " (increase)." : " (decrease).");
  64. }
  65.  
  66. else
  67. return false;
  68. }
  69.  
  70. function graphics()
  71. {
  72.  
  73. var g = document.getElementById("g");
  74. g.width = window.innerWidth;
  75. g.height = window.innerHeight;
  76.  
  77. var ctx = g.getContext('2d');
  78. ctx.lineWidth = 1;
  79. ctx.beginPath();
  80.  
  81. ctx.moveTo(0,window.innerHeight/2);
  82. var current_left = 0;
  83. var current_top = window.innerHeight/2;
  84.  
  85. setInterval(function draw(){
  86.  
  87. var x = engage();
  88.  
  89. if(x != false)
  90. {
  91.  
  92. if(lastway == "up" && x.indexOf("decrease")>-1){ctx.fillText(loopinc,current_left-10,current_top-20);}
  93.  
  94. if(x.indexOf("decrease")>-1){current_top = current_top + k; lastway="down";}
  95. else{current_top = current_top - k; lastway = "up";}
  96.  
  97. current_left = current_left+k;
  98. ctx.lineTo(current_left,current_top);
  99. ctx.moveTo(current_left,current_top);
  100. ctx.stroke();
  101. }
  102. },1);
  103. }
  104. graphics();
  105.  
  106. </script>
  107.  
  108. </body>
  109.  
  110. </html>
Advertisement
Add Comment
Please, Sign In to add comment