Search Results

Search found 6716 results on 269 pages for 'distributed algorithm'.

Page 71/269 | < Previous Page | 67 68 69 70 71 72 73 74 75 76 77 78  | Next Page >

• How to calculate the current index?

  - by niko

  Hi, I have written an algorithm which iteratively solves the problem. The first iteration consists of 6 steps and all the following iterations consist of 5 steps (first step is skipped). What I want to calculate is the current (local) step in the iteration from current global step. For example if there are 41 steps in total which means there are 8 iterations: indices from 1 to 6 belong to 1st iteration indices from 7 to 11 belong to second iteration ... For calculating the current iteration I have written the following code: if(currentStep <= 6) iteration = 1; else iteration = floor((currentStep - 7)/5) + 2; end The problem remains in calculating local steps. in first iteration the performed steps are: 1, 2, 3, 4, 5, 6 in all the following iterations the performing steps are 2, 3, 4, 5, 6 So what has to be done is to transform the array of global steps [1 2 3 4 5 6 7 8 9 10 11 12 13 ... 41] into array of local steps [1 2 3 4 5 6 2 3 4 5 6 2 3 ... 6]. I would appreciate if anyone could help in finding the solution to a given problem. Thank you!

  Read the article

• graph and all pairs shortest path in java

  - by Sandra

  I am writing a java program using Flyod-Warshall algorithm “All pairs shortest path”. I have written the following : a0 is the adjacency matrix of my graph, but has infinity instead of 0. vList is the list of vertexes and the cost for each edge is 1. Path[i][j] = k+1 means for going from I to j you first go to k then j int[][] path = new int[size][size]; for(int i = 0; i<path.length;i++) { for(int j = 0; j<path.length; j++) { if(adjM[i][j]==1) path[i][j]=j+1; } } //*************** for (int k = 0; k < vList.size(); k++) for (int i = 0; i < vList.size(); i++) for (int j = 0; j < vList.size(); j++) { if (a0[i][j]>a0[i][k]+ a0[k][j]) path[i][j] = k + 1; a0[i][j] = Math.min(a0[i][j], a0[i][k] + a0[k][j]); } After running this code, in the result a0 is correct, but path is not correct and I don’t know why!. Would you please help me?

  Read the article

• Generate unique ID from multiple values with fault tolerance

  - by ojreadmore

  Given some values, I'd like to make a (pretty darn) unique result. $unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plnmjfys')); //now $unique1 == "sqef3452y"; I also need something that's pretty close to return the same result. In this case, 20% of the values is missing. $unique2 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8')); //also $unique2 == "sqef3452y"; I'm not sure where to begin with such an algorithm but I have some assumptions. I assume that the more values given, the more accurate the resulting ID – in other words, using 20 values is better than 5. I also assume that a confidence factor can be calculated and adjusted. What would be nice to have is a weight factor where one can say 'value 1 is more important than value 3'. This would require a multidimensional array for input instead of one dimension. I just mashed on the keyboard for these values, but in practice they may be short or long alpha numeric values.

  Read the article

• Reversing strings in a vector using for_each and bind

  - by fmuecke

  Hi! I was wandering how it's possible to reverese strings that are contained in a vector using a single for_each command just in one "simple" line. Yea, I know it is easy with a custom functor, but I can't accept, that it can't be done using bind (at least I couldn't do it). #include <vector> #include <string> #include <algorithm> std::vector<std::string> v; v.push_back("abc"); v.push_back("12345"); std::for_each(v.begin(), v.end(), /*call std::reverse for each element*/); Edit: Thanks a lot for those funtastic solutions. However, the solution for me was not to use the tr1::bind that comes with the Visual Studio 2008 feature pack/SP1. I don't know why it does not work like expected but that's the way it is (even MS admits that it's buggy). Maybe some hotfixes will help. With boost::bind everything works like desired and is so easy (but sometimes relly messy:)). I really should have tried boost::bind in the first place...

  Read the article

• binary quicksort

  - by davit-datuashvili

  hi i want implement Binary quicksort algorithm from robert sedgewick book it looks like this public class quickb{ public static final int bitsword=32; public static void quicksortB(int a[],int l,int r,int d){ int i=l; int j=r-1; if (r<=l || d>bitsword) return ; while (j!=i) { while (digit(a[i],d)==0 && (i<j)) i++; while (digit(a[j],d)==1 && (j>i)) j++; int t=a[i]; a[i]=a[j]; a[j]=t; } if (digit(a[r-1],d)== 0) j++; quicksortB(a,l,j-1,d+1); quicksortB(a,j,r,d+1); } public static void main(String[]args){ int a[]=new int[]{4,7,3,9,8,2}; quicksortB(a,0,a.length-1,0); for (int i=0;i<a.length;i++){ System.out.println(a[i]); } } public static int digit(int m,int d){ return (m>>d)&1; } } but it show me error: java.lang.ArrayIndexOutOfBoundsException: 6 at quickb.quicksortB(quickb.java:13) at quickb.main(quickb.java:32) what is wrong?

  Read the article

• Iterative Reduction to Null Matrix

  - by user1459032

  Here's the problem: I'm given a matrix like Input: 1 1 1 1 1 1 1 1 1 At each step, I need to find a "second" matrix of 1's and 0's with no two 1's on the same row or column. Then, I'll subtract the second matrix from the original matrix. I will repeat the process until I get a matrix with all 0's. Furthermore, I need to take the least possible number of steps. I need to print all the "second" matrices in O(n) time. In the above example I can get to the null matrix in 3 steps by subtracting these three matrices in order: Expected output: 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 I have coded an attempt, in which I am finding the first maximum value and creating the second matrices based on the index of that value. But for the above input I am getting 4 output matrices, which is wrong: My output: 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 My solution works for most of the test cases but fails for the one given above. Can someone give me some pointers on how to proceed, or find an algorithm that guarantees optimality? Test case that works: Input: 0 2 1 0 0 0 3 0 0 Output 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0

  Read the article

• Generate regular expression to match strings from the list A, but not from list B

  - by Vlad

  I have two lists of strings ListA and ListB. I need to generate a regular expression that will match all strings in ListA and will not match any string in ListB. The strings could contain any combination of characters, numbers and punctuation. If a string appears on ListA it is guaranteed that it will not be in the ListB. If a string is not in either of these two lists I don't care what the result of the matching should be. The lists typically contain thousands of strings, and strings are fairly similar to each other. I know the trivial answer to this question, which is just generate a regular expression of the form (Str1)|(Str2)|(Str3) where StrN is the string from ListA. But I am looking for a more efficient way to do this. Ideal solution would be some sort of tool that will take two lists and generate a Java regular expression for this. Update 1: By "efficient", I mean to generate expression that is shorter than trivial solution. The ideal algorithm would generate the shorted possible expression. Here are some examples. ListA = { C10 , C15, C195 } ListB = { Bob, Billy } The ideal expression would be /^C1.+$/ Another example, note the third element of ListB ListA = { C10 , C15, C195 } ListB = { Bob, Billy, C25 } The ideal expression is /^C[^2]{1}.+$/ The last example ListA = { A , D ,E , F , H } ListB = { B , C , G , I } The ideal expression is the same as trivial solution which is /^(A|D|E|F|H)$/ Also, I am not looking for the ideal solution, anything better than trivial would help. I was thinking along the lines of generating the list of trivial solutions, and then try to merge the common substrings while watching that we don't wander into ListB territory. *Update 2: I am not particularly worried about the time it takes to generate the RegEx, anything under 10 minutes on the modern machine is acceptable

  Read the article

• Fastest container or algorithm for unique reusable ids in C++

  - by gman

  I have a need for unique reusable ids. The user can choose his own ids or he can ask for a free one. The API is basically class IdManager { public: int AllocateId(); // Allocates an id void FreeId(int id); // Frees an id so it can be used again bool MarkAsUsed(int id); // Let's the user register an id. // returns false if the id was already used. }; Assume ids happen to start at 1 and progress, 2, 3, etc. This is not a requirement, just to help illustrate. IdManager mgr; mgr.MarkAsUsed(3); printf ("%d\n", mgr.AllocateId()); printf ("%d\n", mgr.AllocateId()); printf ("%d\n", mgr.AllocateId()); Would print 1 2 4 Because id 3 has already been declared used. What's the best container / algorithm to both remember which ids are used AND find a free id? If you want to know the a specific use case, OpenGL's glGenTextures, glBindTexture and glDeleteTextures are equivalent to AllocateId, MarkAsUsed and FreeId

  Read the article

• Learning Java and logic using debugger. Did I cheat?

  - by centr0

  After a break from coding in general, my way of thinking logically faded (as if it was there to begin with...). I'm no master programmer. Intermediate at best. I decided to see if i can write an algorithm to print out the fibonacci sequence in Java. I got really frustrated because it was something so simple, and used the debugger to see what was going on with my variables. solved it in less than a minute with the help of the debugger. Is this cheating? When I read code either from a book or someone else's, I now find that it takes me a little more time to understand. If the alghorithm is complex (to me) i end up writing notes as to whats going on in the loop. A primitive debugger if you will. When you other programmers read code, do you also need to write things down as to whats the code doing? Or are you a genius and and just retain it?

  Read the article

• Finding the closest match

  - by doublescorpio

  I Have an object with a set of parameters like: var obj = new {Param1 = 100; Param2 = 212; Param3 = 311; param4 = 11; Param5 = 290;} On the other side i have a list of object: var obj1 = new {Param1 = 1221; Param2 = 212; Param3 = 311; param4 = 11; Param5 = 290;} var obj3 = new {Param1 = 35; Param2 = 11; Param3 = 319; param4 = 211; Param5 = 790;} var obj4 = new {Param1 = 126; Param2 = 218; Param3 = 2; param4 = 6; Param5 = 190;} var obj5 = new {Param1 = 213; Param2 = 121; Param3 = 61; param4 = 11; Param5 = 29;} var obj7 = new {Param1 = 161; Param2 = 21; Param3 = 71; param4 = 51; Param5 = 232;} var obj9 = new {Param1 = 891; Param2 = 58; Param3 = 311; param4 = 21; Param5 = 590;} var obj11 = new {Param1 = 61; Param2 = 212; Param3 = 843; param4 = 89; Param5 = 210;} What is the best (easiest) algorithm to find the closest match for the first obj in the listed objects?

  Read the article

• Given a vector of maximum 10 000 natural and distinct numbers, find 4 numbers(a, b, c, d) such that

  - by king_kong

  Hi, I solved this problem by following a straightforward but not optimal algorithm. I sorted the vector in descending order and after that substracted numbers from max to min to see if I get a + b + c = d. Notice that I haven't used anywhere the fact that elements are natural, distinct and 10 000 at most. I suppose these details are the key. Does anyone here have a hint over an optimal way of solving this? Thank you in advance! Later Edit: My idea goes like this: '<<quicksort in descending order>>' for i:=0 to count { // after sorting, loop through the array int d := v[i]; for j:=i+1 to count { int dif1 := d - v[j]; int a := v[j]; for k:=j+1 to count { if (v[k] > dif1) continue; int dif2 := dif1 - v[k]; b := v[k]; for l:=k+1 to count { if (dif2 = v[l]) { c := dif2; return {a, b, c, d} } } } } } What do you think?(sorry for the bad indentation)

  Read the article

• Android - How to approach fall detection algorithm

  - by bobby123

  I want to be able to feature a fairly simple fall detection algorithm in my application. At the moment in onSensorChanged(), I am getting the absolute value of the current x,x,z values and subtracting SensorManager.GRAVITY_EARTH (9.8 m/s) from this. The resulting value has to be bigger than a threshold value 10 times in a row to set a flag saying a fall has been detected by the accelerometer, the threshold value is about 8m/s. Also I'm comparing the orientation of the phone as soon as the threshold has been passed and the orienation of it when the threshold is no longer being passed, this sets another flag saying the orientation sensor has detected a fall. When both flags are set, an event occurs to check is user ok, etc etc. My problem is with the threshold, when the phone is held straight up the absolute value of accelerometer is about 9.8 m/s, but when i hold it still at an angle it can be over 15m/s. This is causing other events to trigger the fall detection, and if i increase the threshold to avoid that, it won't detect falls. Can anyone give me some advice here with what possible values i should use or how to even improve my method? Many thanks.

  Read the article

• Writing a recursive sorting algorithm of an array of integers

  - by 12345

  I am trying to write a recursive sorting algorithm for an array of integers. The following codes prints to the console: 3, 5, 2, 1, 1, 2, 6, 7, 8, 10, 20 The output should be sorted but somehow "it doesn't work". public static void main(String[] args) { int[] unsortedList = {20, 3, 1, 2, 1, 2, 6, 8, 10, 5, 7}; duplexSelectionSort(unsortedList, 0, unsortedList.length-1); for (int i = 0; i < unsortedList.length; i++) { System.out.println(unsortedList[i]); } } public static void duplexSelectionSort( int[] unsortedNumbers, int startIndex, int stopIndex) { int minimumIndex = 0; int maximumIndex = 0; if (startIndex < stopIndex) { int index = 0; while (index <= stopIndex) { if (unsortedNumbers[index] < unsortedNumbers[minimumIndex]) { minimumIndex = index; } if (unsortedNumbers[index] > unsortedNumbers[maximumIndex]) { maximumIndex = index; } index++; } swapEdges(unsortedNumbers, startIndex, stopIndex, minimumIndex, maximumIndex); duplexSelectionSort(unsortedNumbers, startIndex + 1, stopIndex - 1); } } public static void swapEdges( int[] listOfIntegers, int startIndex, int stopIndex, int minimumIndex, int maximumIndex) { if ((minimumIndex == stopIndex) && (maximumIndex == startIndex)) { swap(listOfIntegers, startIndex, stopIndex); } else { if (maximumIndex == startIndex) { swap(listOfIntegers, maximumIndex, stopIndex); swap(listOfIntegers, minimumIndex, startIndex); } else { swap(listOfIntegers, minimumIndex, startIndex); swap(listOfIntegers, maximumIndex, stopIndex); } } } public static void swap(int[] listOfIntegers, int index1, int index2) { int savedElementAtIndex1 = listOfIntegers[index1]; listOfIntegers[index1] = listOfIntegers[index2]; listOfIntegers[index2] = savedElementAtIndex1; }

  Read the article

• The perverse hangman problem

  - by Shalmanese

  Perverse Hangman is a game played much like regular Hangman with one important difference: The winning word is determined dynamically by the house depending on what letters have been guessed. For example, say you have the board _ A I L and 12 remaining guesses. Because there are 13 different words ending in AIL (bail, fail, hail, jail, kail, mail, nail, pail, rail, sail, tail, vail, wail) the house is guaranteed to win because no matter what 12 letters you guess, the house will claim the chosen word was the one you didn't guess. However, if the board was _ I L M, you have cornered the house as FILM is the only word that ends in ILM. The challenge is: Given a dictionary, a word length & the number of allowed guesses, come up with an algorithm that either: a) proves that the player always wins by outputting a decision tree for the player that corners the house no matter what b) proves the house always wins by outputting a decision tree for the house that allows the house to escape no matter what. As a toy example, consider the dictionary: bat bar car If you are allowed 3 wrong guesses, the player wins with the following tree: Guess B NO -> Guess C, Guess A, Guess R, WIN YES-> Guess T NO -> Guess A, Guess R, WIN YES-> Guess A, WIN

  Read the article

• Finding k elements of length-n list that sum to less than t in O(nlogk) time

  - by tresbot

  This is from Programming Pearls ed. 2, Column 2, Problem 8: Given a set of n real numbers, a real number t, and an integer k, how quickly can you determine whether there exists a k-element subset of the set that sums to at most t? One easy solution is to sort and sum the first k elements, which is our best hope to find such a sum. However, in the solutions section Bentley alludes to a solution that takes nlog(k) time, though he gives no hints for how to find it. I've been struggling with this; one thought I had was to go through the list and add all the elements less than t/k (in O(n) time); say there are m1 < k such elements, and they sum to s1 < t. Then we are left needing k - m1 elements, so we can scan through the list again in O(n) time looking for all elements less than (t - s1)/(k - m1). Add in again, to get s2 and m2, then again if m2 < k, look for all elements less than (t - s2)/(k - m2). So: def kSubsetSumUnderT(inList, k, t): outList = [] s = 0 m = 0 while len(outList) < k: toJoin = [i for i in inList where i < (t - s)/(k - m)] if len(toJoin): if len(toJoin) >= k - m: toJoin.sort() if(s0 + sum(toJoin[0:(k - m - 1)]) < t: return True return False outList = outList + toJoin s += sum(toJoin) m += len(toJoin) else: return False My intuition is that this might be the O(nlog(k)) algorithm, but I am having a hard time proving it to myself. Thoughts?

  Read the article

• Change value of adjacent vertices and remove self loop

  - by StereoMatching

  Try to write a Karger’s algorithm with boost::graph example (first column is vertice, other are adjacent vertices): 1 2 3 2 1 3 4 3 1 2 4 4 2 3 assume I merge 2 to 1, I get the result 1 2 3 2 1 1 3 4 2 1 3 4 3 1 2 4 4 2 3 first question : How could I change the adjacent vertices("2" to "1") of vertice 1? my naive solution template<typename Vertex, typename Graph> void change_adjacent_vertices_value(Vertex input, Vertex value, Graph &g) { for (auto it = boost::adjacent_vertices(input, g); it.first != it.second; ++it.first){ if(*it.first == value){ *(it.first) = input; //error C2106: '=' : left operand must be l-value } } } Apparently, I can't set the value of the adjacent vertices to "1" by this way The result I want after "change_adjacent_vertices_value" 1 1 3 1 1 1 3 4 2 1 3 4 3 1 2 4 4 2 3 second question : How could I pop out the adjacent vertices? Assume I want to pop out the consecutive 1 from the vertice 1 The result I expected 1 1 3 1 3 4 2 1 3 4 3 1 2 4 4 2 3 any function like "pop_adjacent_vertex" could use?

  Read the article

• CodeGolf: Brothers

  - by John McClane

  Hi guys, I just finished participating in the 2009 ACM ICPC Programming Conest in the Latinamerican Finals. These questions were for Brazil, Bolivia, Chile, etc. My team and I could only finish two questions out of the eleven (not bad I think for the first try). Here's one we could finish. I'm curious to seeing any variations to the code. The question in full: ps: These questions can also be found on the official ICPC website available to everyone. In the land of ACM ruled a greeat king who became obsessed with order. The kingdom had a rectangular form, and the king divided the territory into a grid of small rectangular counties. Before dying the king distributed the counties among his sons. The king was unaware of the rivalries between his sons: The first heir hated the second but not the rest, the second hated the third but not the rest, and so on...Finally, the last heir hated the first heir, but not the other heirs. As soon as the king died, the strange rivaly among the King's sons sparked off a generalized war in the kingdom. Attacks only took place between pairs of adjacent counties (adjacent counties are those that share one vertical or horizontal border). A county X attacked an adjacent county Y whenever X hated Y. The attacked county was always conquered. All attacks where carried out simultanously and a set of simultanous attacks was called a battle. After a certain number of battles, the surviving sons made a truce and never battled again. For example if the king had three sons, named 0, 1 and 2, the figure below shows what happens in the first battle for a given initial land distribution: INPUT The input contains several test cases. The first line of a test case contains four integers, N, R, C and K. N - The number of heirs (2 <= N <= 100) R and C - The dimensions of the land. (2 <= R,C <= 100) K - Number of battles that are going to take place. (1 <= K <= 100) Heirs are identified by sequential integers starting from zero. Each of the next R lines contains C integers HeirIdentificationNumber (saying what heir owns this land) separated by single spaces. This is to layout the initial land. The last test case is a line separated by four zeroes separated by single spaces. (To exit the program so to speak) Output For each test case your program must print R lines with C integers each, separated by single spaces in the same format as the input, representing the land distribution after all battles. Sample Input: Sample Output: 3 4 4 3 2 2 2 0 0 1 2 0 2 1 0 1 1 0 2 0 2 2 2 0 0 1 2 0 0 2 0 0 0 1 2 2 Another example: Sample Input: Sample Output: 4 2 3 4 1 0 3 1 0 3 2 1 2 2 1 2

  Read the article

• [Java] RSA BadPaddingException : data must start with zero

  - by Robin Monjo

  Hello everyone. I try to implement an RSA algorithm in a Java program. I am facing the "BadPaddingException : data must start with zero". Here are the methods used to encrypt and decrypt my data : public byte[] encrypt(byte[] input) throws Exception { Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");// cipher.init(Cipher.ENCRYPT_MODE, this.publicKey); return cipher.doFinal(input); } public byte[] decrypt(byte[] input) throws Exception { Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");/// cipher.init(Cipher.DECRYPT_MODE, this.privateKey); return cipher.doFinal(input); } privateKey and publicKey attributes are read from files this way : public PrivateKey readPrivKeyFromFile(String keyFileName) throws IOException { PrivateKey key = null; try { FileInputStream fin = new FileInputStream(keyFileName); ObjectInputStream ois = new ObjectInputStream(fin); BigInteger m = (BigInteger) ois.readObject(); BigInteger e = (BigInteger) ois.readObject(); RSAPrivateKeySpec keySpec = new RSAPrivateKeySpec(m, e); KeyFactory fact = KeyFactory.getInstance("RSA"); key = fact.generatePrivate(keySpec); ois.close(); } catch (Exception e) { e.printStackTrace(); } return key; } Private key and Public key are created this way : public void Initialize() throws Exception { KeyPairGenerator keygen = KeyPairGenerator.getInstance("RSA"); keygen.initialize(2048); keyPair = keygen.generateKeyPair(); KeyFactory fact = KeyFactory.getInstance("RSA"); RSAPublicKeySpec pub = fact.getKeySpec(keyPair.getPublic(), RSAPublicKeySpec.class); RSAPrivateKeySpec priv = fact.getKeySpec(keyPair.getPrivate(), RSAPrivateKeySpec.class); saveToFile("public.key", pub.getModulus(), pub.getPublicExponent()); saveToFile("private.key", priv.getModulus(), priv.getPrivateExponent()); } and then saved in files : public void saveToFile(String fileName, BigInteger mod, BigInteger exp) throws IOException { FileOutputStream f = new FileOutputStream(fileName); ObjectOutputStream oos = new ObjectOutputStream(f); oos.writeObject(mod); oos.writeObject(exp); oos.close(); } I can't figured out how the problem come from. Any help would be appreciate ! Thanks in advance.

  Read the article

• The Collatz Sequence problem

  - by Gandalf StormCrow

  I'm trying to solve this problem, its not a homework question, its just code I'm submitting to uva.onlinejudge.org so I can learn better java trough examples. Here is the problem sample input : 3 100 34 100 75 250 27 2147483647 101 304 101 303 -1 -1 Here is simple output : Case 1: A = 3, limit = 100, number of terms = 8 Case 2: A = 34, limit = 100, number of terms = 14 Case 3: A = 75, limit = 250, number of terms = 3 Case 4: A = 27, limit = 2147483647, number of terms = 112 Case 5: A = 101, limit = 304, number of terms = 26 Case 6: A = 101, limit = 303, number of terms = 1 The thing is this has to execute within 3sec time interval otherwise your question won't be accepted as solution, here is with what I've come up so far, its working as it should just the execution time is not within 3 seconds, here is code : import java.util.Scanner; class Main { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int start; int limit; int terms; int a = 0; while (stdin.hasNext()) { start = stdin.nextInt(); limit = stdin.nextInt(); if (start > 0) { terms = getLength(start, limit); a++; } else { break; } System.out.println("Case "+a+": A = "+start+", limit = "+limit+", number of terms = "+terms); } } public static int getLength(int x, int y) { int length = 1; while (x != 1) { if (x <= y) { if ( x % 2 == 0) { x = x / 2; length++; }else{ x = x * 3 + 1; length++; } } else { length--; break; } } return length; } } And yes here is how its meant to be solved : An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows: Step 1: Choose an arbitrary positive integer A as the first item in the sequence. Step 2: If A = 1 then stop. Step 3: If A is even, then replace A by A / 2 and go to step 2. Step 4: If A is odd, then replace A by 3 * A + 1 and go to step 2. And yes my question is how can I make it work inside 3 seconds time interval?

  Read the article

• Are there any working implementations of the rolling hash function used in the Rabin-Karp string sea

  - by c14ppy

  I'm looking to use a rolling hash function so I can take hashes of n-grams of a very large string. For example: "stackoverflow", broken up into 5 grams would be: "stack", "tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow" This is ideal for a rolling hash function because after I calculate the first n-gram hash, the following ones are relatively cheap to calculate because I simply have to drop the first letter of the first hash and add the new last letter of the second hash. I know that in general this hash function is generated as: H = c1ak - 1 + c2ak - 2 + c3ak - 3 + ... + cka0 where a is a constant and c1,...,ck are the input characters. If you follow this link on the Rabin-Karp string search algorithm , it states that "a" is usually some large prime. I want my hashes to be stored in 32 bit integers, so how large of a prime should "a" be, such that I don't overflow my integer? Does there exist an existing implementation of this hash function somewhere that I could already use? Here is an implementation I created: public class hash2 { public int prime = 101; public int hash(String text) { int hash = 0; for(int i = 0; i < text.length(); i++) { char c = text.charAt(i); hash += c * (int) (Math.pow(prime, text.length() - 1 - i)); } return hash; } public int rollHash(int previousHash, String previousText, String currentText) { char firstChar = previousText.charAt(0); char lastChar = currentText.charAt(currentText.length() - 1); int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1)); int hash = (previousHash - firstCharHash) * prime + lastChar; return hash; } public static void main(String[] args) { hash2 hashify = new hash2(); int firstHash = hashify.hash("mydog"); System.out.println(firstHash); System.out.println(hashify.hash("ydogr")); System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr")); } } I'm using 101 as my prime. Does it matter if my hashes will overflow? I think this is desirable but I'm not sure. Does this seem like the right way to go about this?

  Read the article

• J: Self-reference in bubble sort tacit implementation

  - by Yasir Arsanukaev

  Hello people! Since I'm beginner in J I've decided to solve a simple task using this language, in particular implementing the bubblesort algorithm. I know it's not idiomatically to solve such kind of problem in functional languages, because it's naturally solved using array element transposition in imperative languages like C, rather than constructing modified list in declarative languages. However this is the code I've written: (((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: # Let's apply it to an array: (((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: # 5 3 8 7 2 2 3 5 7 8 The thing that confuses me is $: referring to the statement within the outermost parentheses. Help says that: $: denotes the longest verb that contains it. The other book (~ 300 KiB) says: 3+4 7 5*20 100 Symbols like + and * for plus and times in the above phrases are called verbs and represent functions. You may have more than one verb in a J phrase, in which case it is constructed like a sentence in simple English by reading from left to right, that is 4+6%2 means 4 added to whatever follows, namely 6 divided by 2. Let's rewrite my code snippet omitting outermost ()s: ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # 5 3 8 7 2 2 3 5 7 8 Reuslts are the same. I couldn't explain myself why this works, why only ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is treated as the longest verb for $: but not the whole expression ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # and not just (<./@(2&{.)), $:@((>./@(2&{.)),2&}.), because if ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is a verb, it should also form another verb after conjunction with #, i. e. one might treat the whole sentence (first snippet) as a verb. Probably there's some limit for the verb length limited by one conjunction. Look at the following code (from here): factorial =: (* factorial@<:) ^: (1&<) factorial 4 24 factorial within expression refers to the whole function, i. e. (* factorial@<:) ^: (1&<). Following this example I've used a function name instead of $:: bubblesort =: (((<./@(2&{.)), bubblesort@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: # bubblesort 5 3 8 7 2 2 3 5 7 8 I expected bubblesort to refer to the whole function, but it doesn't seem true for me since the result is correct. Also I'd like to see other implementations if you have ones, even slightly refactored. Thanks.

  Read the article

• Miller-rabin exception number?

  - by nightcracker

  Hey everyone. This question is about the number 169716931325235658326303. According to http://www.alpertron.com.ar/ECM.HTM it is prime. According to my miller-rabin implementation in python with 7 repetitions is is composite. With 50 repetitions it is still composite. With 5000 repetitions it is STILL composite. I thought, this might be a problem of my implementation. So I tried GNU MP bignum library, which has a miller-rabin primality test built-in. I tested with 1000000 repetitions. Still composite. This is my implementation of the miller-rabin primality test: def isprime(n, precision=7): if n == 1 or n % 2 == 0: return False elif n < 1: raise ValueError("Out of bounds, first argument must be > 0") d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for repeat in range(precision): a = random.randrange(2, n - 2) x = pow(a, d, n) if x == 1 or x == n - 1: continue for r in range(s - 1): x = pow(x, 2, n) if x == 1: return False if x == n - 1: break else: return False return True And the code for the GMP test: #include <gmp.h> #include <stdio.h> int main(int argc, char* argv[]) { mpz_t test; mpz_init_set_str(test, "169716931325235658326303", 10); printf("%d\n", mpz_probab_prime_p(test, 1000000)); mpz_clear(test); return 0; } As far as I know there are no "exceptions" (which return false positives for any amount of repetitions) to the miller-rabin primality test. Have I stumpled upon one? Is my computer broken? Is the Elliptic Curve Method wrong? What is happening here? EDIT I found the issue, which is http://www.alpertron.com.ar/ECM.HTM. I trusted this applet, I'll contact the author his applet's implementation of the ECM is faulty for this number. Thanks. EDIT2 Hah, the shame! In the end it was something that went wrong with copy/pasting on my side. NOR the applet NOR the miller-rabin algorithm NOR my implementation NOR gmp's implementation of it is wrong, the only thing that's wrong is me. I'm sorry.

  Read the article

• Drawing Bresenham’s Line- Algorithm in all quadrants

  - by Yoyo2965259

  I am newbie for OpenGL. I am practicing the exercises from my textbook but I could not get the outputs which is should be in Bresenham's Line Algorithm in all quadrants. Here's the coding: #include <Windows.h> #include <GL/glut.h> void init(void) { glClearColor(0.0, 0.0, 0.0, 0.0); glShadeModel(GL_FLAT); } void BresnCir(void) { int delta, deltadash; glClear(GL_COLOR_BUFFER_BIT); glPointSize(3.0); int r = 150; int x = 0; int y = r; int D = 2 * (1 - r); glBegin(GL_POINTS); do { glVertex2i(x, y); if (D < 0) { delta = 2 * D + 2 * y - 1; if (delta <= 0) { x++; Right(x); } else { x++; y--; Diagonal(x, y); } glVertex2i(x, y); } else { deltadash = 2 * D - 2 * x - 1; if (deltadash <= 0) { x++; y--; Diagonal(x, y); } else { y--; Down(y); } glVertex2i(x, y); } if (D == 0) { x++; y--; Diagonal(x, y); glVertex2i(x, y); } } while (y > 0); glEnd(); glFlush(); } int main(int argc, char** argv) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); glutInitWindowSize(400, 150); glutInitWindowPosition(100, 100); glutCreateWindow(argv[0]); init(); glutDisplayFunc(BresnCir); glutMainLoop(); return 0; } But, it keep comes out with errors C3861.

  Read the article

• Finding what makes strings unique in a list, can you improve on brute force?

  - by Ed Guiness

  Suppose I have a list of strings where each string is exactly 4 characters long and unique within the list. For each of these strings I want to identify the position of the characters within the string that make the string unique. So for a list of three strings abcd abcc bbcb For the first string I want to identify the character in 4th position d since d does not appear in the 4th position in any other string. For the second string I want to identify the character in 4th position c. For the third string it I want to identify the character in 1st position b AND the character in 4th position, also b. This could be concisely represented as abcd -> ...d abcc -> ...c bbcb -> b..b If you consider the same problem but with a list of binary numbers 0101 0011 1111 Then the result I want would be 0101 -> ..0. 0011 -> .0.. 1111 -> 1... Staying with the binary theme I can use XOR to identify which bits are unique within two binary numbers since 0101 ^ 0011 = 0110 which I can interpret as meaning that in this case the 2nd and 3rd bits (reading left to right) are unique between these two binary numbers. This technique might be a red herring unless somehow it can be extended to the larger list. A brute-force approach would be to look at each string in turn, and for each string to iterate through vertical slices of the remainder of the strings in the list. So for the list abcd abcc bbcb I would start with abcd and iterate through vertical slices of abcc bbcb where these vertical slices would be a | b | c | c b | b | c | b or in list form, "ab", "bb", "cc", "cb". This would result in four comparisons a : ab -> . (a is not unique) b : bb -> . (b is not unique) c : cc -> . (c is not unique) d : cb -> d (d is unique) or concisely abcd -> ...d Maybe it's wishful thinking, but I have a feeling that there should be an elegant and general solution that would apply to an arbitrarily large list of strings (or binary numbers). But if there is I haven't yet been able to see it. I hope to use this algorithm to to derive minimal signatures from a collection of unique images (bitmaps) in order to efficiently identify those images at a future time. If future efficiency wasn't a concern I would use a simple hash of each image. Can you improve on brute force?

  Read the article

• Grouping geographical shapes

  - by grenade

  I am using Dundas Maps and attempting to draw a map of the world where countries are grouped into regions that are specific to a business implementation. I have shape data (points and segments) for each country in the world. I can combine countries into regions by adding all points and segments for countries within a region to a new region shape. foreach(var region in GetAllRegions()){ var regionShape = new Shape { Name = region.Name }; foreach(var country in GetCountriesInRegion(region.Id)){ var countryShape = GetCountryShape(country.Id); regionShape.AddSegments(countryShape.ShapeData.Points, countryShape.ShapeData.Segments); } map.Shapes.Add(regionShape); } The problem is that the country border lines still show up within a region and I want to remove them so that only regional borders show up. Dundas polygons must start and end at the same point. This is the case for all the country shapes. Now I need an algorithm that can: Determine where country borders intersect at a regional border, so that I can join the regional border segments. Determine which country borders are not regional borders so that I can discard them. Sort the resulting regional points so that they sequentialy describe the shape boundaries. Below is where I have gotten to so far with the map. You can see that the country borders still need to be removed. For example, the border between Mongolia and China should be discarded whereas the border between Mongolia and Russia should be retained. The reason I need to retain a regional border is that the region colors will be significant in conveying information but adjacent regions may be the same color. The regions can change to include or exclude countries and this is why the regional shaping must be dynamic. EDIT: I now know that I what I am looking for is a UNION of polygons. David Lean explains how to do it using the spatial functions in SQL Server 2008 which might be an option but my efforts have come to a halt because the resulting polygon union is so complex that SQL truncates it at 43,680 characters. I'm now trying to either find a workaround for that or find a way of doing the union in code.

  Read the article

< Previous Page | 67 68 69 70 71 72 73 74 75 76 77 78  | Next Page >