An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
0
votes
1answer
5 views
Weaving an array
In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:
Given an array \$A\$ with ...
3
votes
0answers
21 views
Count groups of open cells around a cell on a grid
Consider a 3x3 square surrounding a cell (marked @) on a grid:
0 1 1
1 @ 0
1 1 1
I need to find the number of groups of open cells (ones) surrounding the center ...
2
votes
1answer
29 views
Word Wrapping and Boxing
This was an experiment to take any text and wrap it to a given number of columns. It also wraps
the text in just one box, lets you box multiple blocks of text, and also lets you limit the number
of ...
0
votes
2answers
47 views
Minimum element in a sorted rotated array
A sorted array [0,1,2,3,4,5] when rotated n times (3 times in this case) becomes [3,4,5,0,1,2], meaning elements in the front move to the end. The code below finds the minimum element in this array, ...
5
votes
1answer
46 views
Comparing two approximate string matching algorithms in Java
Problem description
Given a text \$T[0..n)\$, a pattern \$P[0..m)\$, and a nonnegative
integer \$k\$, report all positions \$j \in [0..n)\$ such that \$ed(P,
T(j - l..j]) \leq k\$ for some \$l \geq ...
4
votes
1answer
57 views
TicTacToe 5x5 win or draw algorithm
I have file which contains a lot of boards from TicTacToe 5x5.
First line says how many boards this file contains (n*5x5).
We check the winner in Horizontals, Verticals and Diagonals lines.
Player A ...
0
votes
1answer
20 views
Improving the running time of finding the count of pairs satisfying a symmetric relation
I had an online coding test yesterday. The question is not hard to solve, but I could not achieve the required running time. The question is as follow:
Given \$1 <= M\$, \$N <= 10^5\$ find the ...
5
votes
5answers
199 views
Removing duplicates in an array
Problem: Remove duplicates from a given array of integers.
I want this method to work without using data sets except an array.
My code is currently \$O(n^2 + n) = O(n^2)\$. How do I shorten this? My ...
2
votes
1answer
50 views
Counting the number of increasing sub-sequences
The problem is to find the number of increasing sub-sequence of a string with only digit characters.
Answer may be very large, so output it modulo 10^9+7.
I have been able to get a O(n) solution ...
2
votes
1answer
65 views
Object-to-array flattening function
I have written a function that is designed to convert an object into an array of key/pair values ("flattening it") like so:
Input
...
3
votes
1answer
41 views
Parsing an IP address (Bit manipulation)
Given a string representing of an IP address, such as "127.43.23.59", return a 32 bit integer representation of this string. The 32 bit integer is separated into four bytes, where each byte is one of ...
5
votes
1answer
318 views
Anagram finder in F#
I've been learning F# for a month or so and I'm wondering how good my "functional" aspect of coding is. When I first started, I did this using an iterative approach with a lot of <- and mutables ...
3
votes
1answer
49 views
Merging sorted linked lists - C++
Problem from hackerrank:
You’re given the pointer to the head nodes of two sorted linked lists.
The data in both lists will be sorted in ascending order. Change the
next pointers to obtain a ...
0
votes
0answers
13 views
External / File-based mergesort (what is MAPPEDSHIFT, MAPPEDMASK, MAPPEDSIZE?) [closed]
I am currently working on a file-based merge-sort implementation and found the topic "External / File-based mergesort" in this forum.
Link: External / File-based mergesort
I tried to run the code ...
7
votes
4answers
176 views
Find the dominator in an array of integers
A zero-indexed array A consisting of N integers is given. The
dominator of array A is the value that occurs in more than half of the
elements of A.
For example, consider array A such that
...
1
vote
1answer
101 views
Calculating all possible Knight turns (Chess)
I'm creating a console application that takes as input starting column and starting row, also the ending column and the ending row and it's going to output all the possible way's to get to that point ...
3
votes
1answer
50 views
“Space and Time Efficient” way of finding all anagram groups
I have written a program to find all anagram groups in a text file. I used first 26 Prime numbers as a mapper for 26 characters for finding anagram groups (Since character_set of all anagrams of a ...
3
votes
1answer
39 views
Improving performance for Depth-first search algorithm
I am using the following Depth-first search algorithm to compute value of a property called rotation_absolute based on previous values of ...
3
votes
1answer
83 views
Lazy prime number generator
There are multiple Project Euler problems (e.g. 7, 10) that deal with prime numbers. I decided make a reusable solution that could be used for most of them.
I wrote a method to generate an infinite* ...
1
vote
0answers
49 views
Finding a Cartesian product of multiple lists
I came up with an extension method to find a Cartesian product of multiple IEnumerable sets. I was able to achieve lazy enumeration via ...
10
votes
4answers
122 views
n-queens puzzle in Python
I want to increase the efficiency and reduce the time complexity for the n-queen problem in n*n matrix chess. I am able to run only still (11*11) in normal time otherwise for the big number it is ...
-4
votes
1answer
37 views
Two similar tests on different variables [closed]
I've had a doubt about something.
Let's say I have 4 variables, A1, A2, B1, B2.
If A1 > 0 or B1 > 0, I have to check if A2/B2 is also > 0.
What I have is the following but I'm finding it a bit ...
1
vote
1answer
37 views
Cumulative transition matrix Markov Chain simulation
I have a cumulative transition matrix with probabilities for all the possible states from 1 to 5. Now the algorithm for simulating future states is following: the initial state is selected randomly, ...
0
votes
1answer
102 views
Parsing JSON in one go using state machine solution
I need to parse a simple JSON string (flat JSON, no hierarchy) for keys and values, and there is a system constraint that I cannot use any built-in JSON library and can only read a string once due to ...
4
votes
0answers
43 views
Shortest path navigation across a grid using Best First Search
The code below is an implementation of the Best First Search algorithm for navigation of the shortest path across a 2D NxN matrix. As a heuristic for the search I use the standard distance formula. ...
1
vote
2answers
130 views
Divide list into batches
Three questions: is there a more performant way, is there a more suscinct, strike that, a way of expressing this where if you read just the body it is immediately apperent what the alorithm does, and ...
3
votes
3answers
345 views
Optimizing timeline generation
I have a bunch of processes that are being executed on different virtual machines. All of those processes have a StartDate, ...
2
votes
0answers
45 views
Parallel merge sort in Java
I have rolled my own parallel merge sort. My performance figures are as follows:
Seed: 1457521330571
java.util.Arrays.sort() in 6840 ms. Sorted: true
java.util.Arrays.parallelSort() 3777 ms. ...
0
votes
2answers
48 views
Implementing permuted index in C++
I have implemented a program that produces a permuted index.
Actually it is this exercise:
http://stackoverflow.com/questions/4015016/what-is-a-permuted-index
Could anyone tell me if I did something ...
5
votes
3answers
152 views
Duplicate-preserving collection intersection
Python sets are magical things. Mutable, deduplicating data stores with handy operator overloads for &, ...
0
votes
1answer
41 views
Finding Kth Permutation Sequence
I have written a program to display the kth permutation sequence of a string made up of letters 'O' and 'Z' . I tried optimizing it but my code have not passed test cases due to timeout issues.Looking ...
2
votes
0answers
32 views
Sort Algorithms in Julia
Similar to this question here, I am trying to implement sort algorithms in Julia, as part of a package.
The code for the implementation is as follows:
...
1
vote
3answers
93 views
Logic for shuffling sliding puzzle
I'm working on a sliding puzzle, one little project as a hobby, and yesterday I thought that instead of working on an algorithm to figure out a solved puzzle, it would be easier to make an algorithm ...
2
votes
1answer
33 views
Fractional Knapsack
This is my solution to an assignment on the fractional Knapsack problem. I take as problem input the following pieces of information:
The number of item types
The total weight limit
For each item ...
6
votes
3answers
319 views
Rotation of elements in an array
We had to write a program that would perform rotation of elements in an array. The array size was entered by user, so it had to be in a sense, dynamic.
Rotation or Circular Shifting
Initial Array: ...
3
votes
0answers
38 views
Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths
I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was ...
7
votes
0answers
136 views
Decompose polarimetric SAR covariance matrices in MATLAB
I have the following code to implement the algorithm described in the article Adaptive Model-Based Decomposition of Polarimetric SAR Covariance Matrices by Arii, van Zyl, and Kim, in IEEE Transactions ...
2
votes
1answer
20 views
Printing the minuend and subtrahend in a Minimum Difference algorithm
I have a Minimum Difference algorithm, and I wanted to expand on it by printing the actual elements that were subtracted. I'm just wanting to know if this is the best way to do it.
...
3
votes
2answers
45 views
Parallel integer Quicksort in Java
Now I have that parallel Quicksort for (primitive) integer arrays.
ParallelIntQuicksort.java:
...
3
votes
1answer
54 views
DFS algorithm too slow
I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code?
The question is as ...
3
votes
2answers
51 views
Search algorithms in julia
I've been trying to implement the basic search algorithms: Sequential search for ordered and unordered arrays and the binary search algorithms, as part of a package.
So, this is the implementation:
...
2
votes
3answers
26 views
Longest Collatz sequence in Python
I came across this problem:
The following iterative sequence is defined for the set of positive
integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
...
4
votes
2answers
42 views
Storing disassembled data in a structured way
I want to store the information returned by the dis function of the dis module in a structured way, using a dict, associating the mnemonics of each code of a line to the correspondent line number.
...
2
votes
3answers
117 views
Reverse digits and add until a palindrome appears
The following code is a C solution to the following problem UVA 10018.
The Problem
The "reverse and add" method is simple: choose a number, reverse its
digits and add it to the original. If ...
3
votes
0answers
48 views
Expression parser using Shunting-yard algorithm
I've been working on a expression parser which will be part of another project (some sort of DSL). This parser basically uses the Shunting-yard algorithm, except for the case of parenthesis: here it ...
6
votes
3answers
61 views
Korean word segmentation using frequency heuristic
This a continuation of a previous question. I want to thank Joe Wallis for his help with increasing the readability of my code. Although the changes made by Joe Wallis did increase the speed of the ...
1
vote
1answer
74 views
Reading input fast in Java for competitive programming
I have been solving problems on Timus Online Judge. In the beginning, I didn't worry much about I/O operations, so I just took some code from the internet and focused more on the logic. But after ...
1
vote
2answers
49 views
An easy algorithm for encrypting and decrypting binary data using a cipher key in Java
I have this easy en-/decryption algorithm.
Disclaimer
However, I have absolutely no prior experience in information security, encryption, and so on, so bare with me.
Encryption
Encryption works ...
2
votes
2answers
198 views
Parsing JSON in one go
I need to parse a simple JSON string (flat JSON, no hierarchy) for keys and values, and there is a system constraint that I cannot use any built-in JSON library and can only read a string once due to ...
2
votes
0answers
42 views
Needleman Wunsch algorithm in Scala
The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences.
Here is an implementation in Scala:
...
