Jump to content


fiveworlds

Member Since 06 Dec 2012
Offline Last Active Today, 04:26 PM
***--

Topics I've Started

Subset Sum

6 June 2017 - 12:33 AM

I wrote an algorithm for the subset sum problem that writes a polynomial time algorithm to solve a single number set. It still takes a long time to write the algorithm though. It makes use of ranges.

 

<script>
var numbers = [1,2,-20,12,1,23,12,11,2,4,6,8,123,1298,141,211,12000,22222222,284871581091,849186386108689,9007199254740991];
var positiveEven = [],negativeEven = [], smallest;
var positiveOdd = [], negativeOdd = [], largest;
var sumarray = [];
var ranges = [], useRanges = true, useArrays = false, useBinarySearch = false;
var iterations = 0;
function polynomialFunctionGenerator(){
 function useRanges(){
  var firstnumber = sumarray[0];
  var k = 0;
  for(var i = 0; i < sumarray.length; i++){
   if(sumarray[i]+1 === sumarray[i+1]){
   } else {
    ranges[k]=[firstnumber,sumarray[i]];
    if(sumarray[i+1] != undefined){
     firstnumber = sumarray[i+1];
    }
    k++;
   }
  }
  document.write(sumarray.length + "</br>");
 }
 function useArrays(){
  smallest = sumarray[0];
  largest = sumarray.pop();
  for(var i = 1; i < sumarray.length; i++){
   if(sumarray[i]%2 === 0){
    if(sumarray[i] < 0){
     negativeEven.push(sumarray[i]);
    } else {
     positiveEven.push(sumarray[i]);
    }
   } else {
    if(sumarray[i] < 0){
     negativeOdd.push(sumarray[i]);
    } else {
     positiveOdd.push(sumarray[i]);
    }
   }
  }
 }
 function sortfunction(a, b){return (a - b)}
 var array = [];
 
 for(var i = 0; i < numbers.length; i++){
  array.push(numbers[i]);
  for(var k = i + 1; k < numbers.length; k++){
   var length = array.length;
   for(var t = 0; t < length; t++){
    var sum = array[t]+numbers[k];
    array.push(sum);
    iterations = iterations + 1;
   }
  }
  for(var k = 0; k < array.length; k++){
   if(sumarray.indexOf(array[k])== -1){
    sumarray.push(array[k]);
   }
  }
  array = [];
 }
 sumarray.sort(sortfunction);
 document.write(sumarray.length);
 if(useRanges){useRanges();}
 else if(useArrays){useArrays();}
}


function binarySearch(searchElement, searchArray) {
    'use strict';
    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;
    do {
        last = p;
        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }
        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits
    }while (last !== p);
    return -1; //nothing found
}; 
function Sum(expectedsum){
 if(expectedsum > largest){
  return "Too Big";}
 if(expectedsum < smallest){ return "Too Small";}
 
 if(useBinarySearch){
  if(binarySearch(expectedsum,sumarray) != -1){
   return true;
  }
 }else if(useRanges){
  for(var i = 0; i < ranges.length; i++)
  {
   if((expectedsum > ranges[i][0]-1) && (expectedsum < ranges[i][1]+1)){
    return true;  
   }
  }
 }else if(useArrays){
  if(expectedsum%2 === 0){
   if(positiveEven.indexOf(expectedsum) != -1){
    return true;
   }
   if(negativeEven.indexOf(expectedsum) != -1){
    return true;
   }
  } else if(positiveOdd.indexOf(expectedsum) != -1){
   return true;
  } else if (negativeOdd.indexOf(expectedsum) != -1){
    return true;
  }
 }
 
 return false;
 
}
polynomialFunctionGenerator();
document.write(iterations + "</br>");
document.write(ranges + "</br>");
if(useRanges){
 document.write(
  "Number of Ranges:" + ranges.length + "</br>" +
  "Total Numbers:" + numbers.length + "</br>" +
  "Worst Case Runtime:" + (ranges.length/numbers.length) + "N</br></br>"
 );
} else if (useArrays){
 document.write(
  "largest:" + largest + "</br>" +
  "smallest:" + smallest + "</br>" +
  "Positive Even Numbers:" + positiveEven.length + "</br>" +
  "Positive Odd Numbers:" + positiveOdd.length + "</br>" +
  "Negative Even Numbers:" + negativeEven.length + "</br>" +
  "Negative Odd Numbers:" + negativeOdd.length + "</br>" +
  "Total Numbers:" + numbers.length + "</br>" +
  "Worst Case Runtime:" + (Math.max.apply(Math,[positiveEven.length,positiveOdd.length,negativeEven.length,negativeOdd.length])/numbers.length) + "N</br></br>"
 );
}
 
for(var x=-22; x<500;x++){
 document.write(x+" :"+Sum(x) + "</br>");
}
</script>

This perticular case had the following results

 

Number of numbers: 2588325883
Number of iterations: 2097130
Number of Ranges:4467
Total Numbers:21
Worst Case Runtime:212.71428571428572N

 

I think the useArrays part can be made faster by using primenumbers.


Quantum Multicast

1 June 2017 - 09:19 PM

It seems easy to me that we can make use of quantum entanglement for broadcast however is it possible to make use of quantum entanglement for multicast?? Lets say that we could use the broadcast for dns how would dns tell the computer how to entangle with the server?? It is basically entangling particles at a distance so do the particles we entangle have to be right beside each other when we entangle them??


Exam regulations

18 May 2017 - 11:51 PM

Hey, college exams are really strict in that they force you to hand them your phone, wallet etc to stop cheating. While I can understand where they are coming from am I the only one here that feels uncomfortable with handing their important personal belongings to people they don't know?


Travelling Salesman

17 May 2017 - 01:10 PM

I was asked to make an algorithm for TSP in determinstic polynomial time.

 

 

 

input = list of cities and their distances of length n.
            Each city is seperated by a space e.g.
            "distance,distance,distance distance,distance,distance distance,distance,distance"
k = number of cities = found by reading k distances.
 
  • we populate strings t[] of length k on k! tapes containing all instaces of k! 0000,0001 etc by reading string of length n;
  • each t[] is replaced by string index; 0214 = cities[0][0] cities[1][2] cities[2][1] cities[3][4].
  • replace all t[] with their sum which is equivalent to the distances between the cities.
  • find the minimum of t[];
  • finding k takes O(k) time.
  • making t[] and replacing all t[] with their sum takes O(n) time but O(k!) space;
  • finding the minimum of t[] takes O(k!) time;

Therefore the runtime of TSP is (n + k!) since n can be 1 we can change this to k!.
 
So TSP is reducible to finding the minimum of a list of numbers. We can find the minimum of 2 numbers with combinatorial logic and by extension we can find the minimum value of k! numbers with combinatorial logic in O(1) time. Therefore TSP is reducible to O(1) time in deterministic polynomial time.
 
On modern computers we are limited by the von neumann bottleneck etc so the best runtime on a normal computer would be k! since we can only do one if( a < b)  at a time if we could do it if(a < b < c) then it would half the runtime.

Sat heuristic with Artificial Intelligence

13 May 2017 - 12:43 AM

Hey, I wrote an Artificial Intelligence program to solve SAT in polynomial time. It has a worst case runtime of O(2^N) and a best case runtime of O(1) for the first run of the program and an O(1) runtime thereafter.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class Sat {
 public static char[] getUniqueLetters(String expression){
  String letters = expression.replaceAll("(.)\\1{1,}", "$1").replace('|', ' ').replace('!',' ').replace('&',' ').replace('(',' ').replace(')',' ').replace('=',' ').replace(" ","").replace("'","");
     char[] letterarray = new char[letters.length()];
  for(int i = 0; i < letters.length(); i=i+1){
      letterarray[i]=letters.charAt(i);
  }
  return letterarray;
 };
 
 public static int[] generateIntArray(int length){
  int[] intArray = new int[length];
  for(int i = 0; i < length; i=i+1){
      intArray[i]=0;
  } return intArray;
 }
 
 public static String parse(String booleanExpression){
   while(booleanExpression.indexOf("NAND")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NAND");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NAND")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NAND")));
   booleanExpression = booleanExpression.replaceFirst("NAND", "AND");
  }
  
  while(booleanExpression.indexOf("NOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NOR")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NOR")));
   booleanExpression = booleanExpression.replaceFirst("NOR", "OR");
  }
  
  while(booleanExpression.indexOf("XOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XOR")+3, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XOR", "OR");
  }
  
  while(booleanExpression.indexOf("XNOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XNOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XNOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "!("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XNOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XNOR")+4, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XNOR", "OR");
  }
  
  booleanExpression = booleanExpression.replace("OR", "||");
  booleanExpression = booleanExpression.replace("AND", "&&");
  booleanExpression = booleanExpression.replace("NOT", "!");
  return booleanExpression;
 }
 
 
 public static void main(String[] args) {
  String origbooleanExpression = "(A NAND ((((A === B) AND (A === C)) NAND (NOT(A) === C)) AND (NOT(A))))";
   try {
    File file = new File("C:/SAT/"+origbooleanExpression+".txt");
    if(file.exists() && !file.isDirectory()) {
     FileReader fileReader = new FileReader(file);
     BufferedReader bufferedReader = new BufferedReader(fileReader);
     StringBuffer stringBuffer = new StringBuffer();
     String line;
     while ((line = bufferedReader.readLine()) != null) {
      stringBuffer.append(line);
      stringBuffer.append("\n");
     }
     fileReader.close();
     System.out.println("Contents of file:");
     System.out.println(stringBuffer.toString());
     System.exit(0);
    }
   } catch (IOException e) {
    e.printStackTrace();
   
  }
  String booleanExpression = parse(origbooleanExpression);
  String output = "";
  System.out.println(booleanExpression);
  char[] letterArray = getUniqueLetters(booleanExpression);
  int[] intArray = generateIntArray(letterArray.length);
     while(intArray[intArray.length-1]<2){
      for(int i = 0; i < intArray.length-1; i=i+1){
       if(intArray[i]>1){intArray[i+1] = intArray[i+1] + 1;intArray[i]=0;}
   }
      try {
             ScriptEngineManager sem = new ScriptEngineManager();
             ScriptEngine se = sem.getEngineByName("JavaScript");
             String myExpression = booleanExpression;
             for(int i = 0; i < intArray.length; i=i+1){
              myExpression = myExpression.replace(String.valueOf(letterArray[i]), String.valueOf(Integer.toString(intArray[i]).charAt(0)));
             }
             if(se.eval(myExpression).equals(true)){
              System.out.println(myExpression);
              try{
                  PrintWriter writer = new PrintWriter("C:/SAT/"+origbooleanExpression+".txt", "UTF-8");
                  writer.println("True");
                  writer.close();
              } catch (IOException e) {
                 // do something
              }
              System.exit(0);
             }
         } catch (ScriptException e1) {
             System.out.println("Invalid Expression");
             e1.printStackTrace();
         }
      intArray[0]=intArray[0]+1;
    }
     System.out.println(output);
     try{
         PrintWriter writer = new PrintWriter("C:/SAT/"+origbooleanExpression+".txt", "UTF-8");
         writer.println("False");
         writer.close();
     } catch (IOException e) {
        // do something
     }
    }
}