New answers tagged algorithm
0
Thanks @Graipher & @Peilonrayz for taking time to answer my question. Yesterday around 7PM IST I discussed this with my brilliant friend Abhay, who gave me a clue on how this can be solved with just \$O(n)\$ complexity.
To keep the question in mind:
Find the maximum product of y positive numbers which adds up to x.
This is how he explained it to me:
...
5
The comments contain two proofs that a better solution exists.
Start with an array of all ones, then repeatedly add one to the smallest number (because that gives the largest percentual increase) until you reach the maximum allowed sum. This can be fomulated as a proof by induction. – Rainer P.
This can be proven rather simply by using Python, but it can ...
6
One immediate improvement is realizing that for e.g the input 14 7, all combinations like x x x x x x 9 and above can never sum to 14, because even for the minimal case x = 1, 9 + 6*1 = 15. So you can vastly reduce the number of combinations you need to check by using
k = {i for i in combinations_with_replacement(range(1, x - y + 2), y) if sum(i) == x}
...
2
I don't understand what you mean by "the knapsack problem white fraction is allowed," not even if I assume that the word "white" should have been "while" or "what" or "where". The whole thing that makes the knapsack problem NP-hard is that you're not allowed to break up a single item into "fractions." So to understand what you meant, I tried to look at the ...
1
Since the code is not compiling, it will be hard to do a proper code review.
In my opinion, you should rename the variable cmd in both of the methods, since it can be confusing.
BinaryTree#put method
In my opinion, it's a bad choice to use the range operators (<, >, <=, >=) with the compareTo method; since you always get one of those values (-1, 0 &...
2
As per signature main function must return int value
#include "fvpalgorithm.h"
int main() {
FVPAlgorithm algorithm;
algorithm.run();
}
Task Structure: Why is taskName public? Here taskName looks like task identifier.
Will this identifier change post creation? Do you intend to support case where
task is created with name X and then later changed ...
1
Declare for-loop-variables inside for instead of reusing them.
So instead of:
int v[501][501], i, j, m, n, o, p;
cin >> m >> n >> o >> p;
for (i = o; i >= 1; i--)
v[i][p] = o - i;
for(i = o;i <= m; i++)
v[i][p] = i - o;
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++){
use (except you should also change ...
3
Some suggestions:
Use variable names that tells the reader what they are.
Dont do using namespace std; in the global namespace.
Always check that <stream> >> variable actually worked or else your program will run with uninitialized variables and cause undefined behaviour if they are read.
Use an unsigned type when dealing with subscripting.
If ...
4
Couple of small things:
Use emplace_back rather than push_back when you just have the parameters for the constructors:
longList.push_back(Task{ taskInput });
// This is better written as:
longList.emplace_back(taskInput);
The difference between the two:
push_back(Task{ taskInput });.
This creates a "Task" object as an input parameter. It then calls ...
3
Just like you I am also learning algorithms mostly in python, that I am also using to learn haskell.
I am fighting myself not to change variable names to long but readable ones! Here it use not using any folding or anything, just recursion.
bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort [x] = [x]
bubbleSort (x:y:xs)
| x < y = x : bubbleSort (y:...
3
Overall
You don't use encapsulation. Which makes your list vulnerable to incorrect initialization and accidental incorrect modification from outside the list.
You use several C based style choice rather than C++ style which make your codde harder to read.
Code Review
Only a list of int?
class Node {
public:
int value; // int only
...
1
1. You never check if head was assigned a valid pointer before dereferencing it here:
int find(struct Node *head, int n)
{
int count = 1;
//if count equal too n return node->data
if(count == n)
return head->value; // <--- here
//recursively decrease n and increase
// head to next pointer
return find(head->...
3
You have the possibility of an infinite loop.
Consider: logBase10Estimate(2147483647). Should be about 9. We need a value of \$10^i\$ which is greater than 1000000000. So, what values does x take on?
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
1410065408
1215752192
-727379968
1316134912
...
1
Algorithm in O(N^2)
The current solution will be slow for large N, because it has a complexity of O(N^2) (It checks every element in the array for every possible position of the k adjusted elements => O(N * (N-K)) => O(N^2)).
There is an O(N) solution.
Consider that as the K-element segment "slides" along the array, there are only two elements whose value ...
2
The printing should not be there :)
You don't need another variable x. You can modify the local copy n, because you won't need its original value for the entire algorithm and because it is passed by value, you won't change the value for the caller.
Also check for valid input.
static int logBase10Estimate(int n)
{
if (n <= 0) {
throw new ...
1
You can speed some things up by using more list and dict comprehensions, and by reducing your function calls. Some examples follow.
d = dict() vs d = {}: 131 ns vs 30 ns.
len_of_half_a = int(len(a)/2) vs len_of_half_a = len(a)//2: 201 ns vs 99 ns.
I used Python 3.8.1 for both tests.
Granted that this isn't much, but several of these tiny improvements ...
1
It's pretty readable, and all comments are pretty minor ones.
You can probably squeeze out a little performance increase, but not much. One thing you could do is to skip setting variables like n = len(prefix) (you also don't use n in the following line).
You could also consider collections.deque instead of list where relevant, which can sometimes give you ...
1
I start from mathematical consideration using one of the examples you provided:
Input: 10 output: 3
2,3,4,5,6,8,9,10
7
11
All the elements multiple of 2 are in the set containing 2, the other sets will always contain just one prime number like {7} and {11} : if it were not so the number would be not prime and would be contained in another previous set.
...
1
BUG: Your main loop for l in substrings(a): ... will return the first palindrome it finds inside a (stepping the indices back from the end), not just the longest one. If there are multiple longest palindromes it won't return them all, only the first it finds. Your code is overly tailored to this one example. Use other examples to tickle it, e.g. "zaba ...
3
public: is excess in a struct.
Members directly initialized in ctors are better directly initialized:
Job(int index, int time_slot, int profit)
: index(index), time_slot(time_slot), profit(profit) {}
only more complex logic should go in ctor's body, if any.
As a matter of fact,
if(cond) {
return true;
}
return false;
is actually ...
5
The Job class has public members, so it's simpler to make it an aggregate:
struct Job {
int index;
int time_slot;
int profit;
};
Then, use std::tie to simplify the comparison operators: (operands to these operators should be marked as const, which you didn't)
bool operator<(const Job& lhs, const Job& rhs)
{
return std::tie(lhs....
2
Missing-value logic
This:
try:
counts[space] += count
except:
counts[space] = count
has a few problems:
A bare except is ill-advised; you probably want to be catching KeyError
Avoid logic-by-exception; for instance:
if space in counts:
counts[space] += count
else:
counts[space] = count
Do one better by calling setdefault:
counts....
6
Going to run through this code making edits and explain as I go:
You only ever use position to find the position within the alphabet; I think it'd be clearer to just make this function's purpose more specific and call it something like index_in_alphabet.
Having narrowed and defined the purpose of this function, it can be implemented much more simply by ...
7
I think it's a nice project. I would say that the main things for you to work on is getting further acquainted with Python's standard library and with standard practices, which is what most of my advice will be surrounding.
Minor improvements
For your alphabet, you could use ascii_lowercase from string, i.e.:
from string import ascii_lowercase
alphabet = ...
6
A warning
As a toy this is fine, but please do not use it (or encourage others to use it) for real cryptographic application. It is fun as an exercise, but will not be sufficiently strong to protect you against certain common attacks.
Strings as sequences
In Python, a string is a sequence of one-character strings. So you don't need to represent it as a ...
1
I'll look at the current code first then look at algorithmic issues.
avoid using namespace std while it probably won't cause issues in a small project like this it is bad practise and can unexpected conflicts. see https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice
ceil(in.size()/2) does not do what you expect. In ...
4
As noted in a comment, I think you've got a bug, but I'll do a pass over the code for style since it works for your test case at least. These are mostly minor style points rather than addressing the overall structure of the code; my goal is going to be to make the code easier to read without doing a full rewrite from scratch or changing the way it works.
...
2
Low Hanging Fruit
I obtained a 27% speed-up with one tiny change.
For this speed-up, I didn't want to wait 2 hours for tests to run, so I used a 3x20 board. Elapsed times:
0:01:44 - before the change
0:01:16 - after the change
I'm sure you'd like to know what the change was. I can't drag it out much more, so here it is. I added this line to the Nodes ...
2
Multi-statement lines
This:
stack = []; result = []
lowlinks = {}; index = {}
# ...
if successor == node: break
is generally discouraged; just use two lines.
snake_case
This:
lowlinks
is usually spelled out, i.e. low_links.
Bare except
try:
successors = graph[node]
except:
successors = []
has an except statement that's too ...
3
Function signatures
This:
def combine(implicant_a, implicant_b):
str_a, nums_a = implicant_a
str_b, nums_b = implicant_b
should go in one of two directions:
Unpack the arguments themselves, i.e. def combine(str_a, nums_a, str_b, nums_b); or
Make some kind of named tuple:
def combine(implicant_a, implicant_b):
# Refer to implicant_a.str and ...
1
I didn't analyse your code but this code returns expected values:
const firstMissingPositive = (arr) => {
const arrSorted = arr.filter( val => val > 0 ).sort( (a,b) => a - b );
const length = arrSorted.length;
if (length === 0) return 1;
for ( let i=0; i < length; i++ ){
if ( arrSorted[i] + 1 !== arrSorted[i + 1] ) {
...
2
Be explicit about the data structure you're using, and the assumptions. For example, a comment like this would be helpful for any future readers(including yourself): "We represent a graph as adjacency list stored in a Python dictionary. The adjacency list can contain nodes that are not present in the keys of the dictionary, and they should be treated as ...
1
Datatype
The size_t size is appropriate, but int top is less. This effectively limits an entire size_t to just storing INT_MAX, and the only value that is negative is -1, the rest are wasted. gcc gave me a warning about comparing integers of different signs, but they should moreover be the same type because they are both storing indices; instead of size and ...
5
Bug
adjust_volume(0) presently results in:
UnboundLocalError: local variable 'bid_volume' referenced before assignment
since if position_size == 0: is currently indented inside the elif position_size < 0: statement, so is unreachable. (This could be a result of poor formatting when copying the code into the question post.)
Possible Bug
Some volume ...
2
I would tag your struct in addition to, if not instead of, using a typedef:
struct v2
{
int x, y;
};
// typedef struct v2 v2;
Then you can use struct v2 wherever you are using v2. This makes it clear that v2 is a structure.
I think you should create a symbolic SUBGRID_SIZE instead of using 3 here:
x0 = (pos.x / 3) * 3;
y0 = (pos.y / 3) * 3;
for (i = ...
2
Use type hints for parameters and members
def __init__(self, row, column):
self.value = 0
self.row = row
self.column = column
self.block = (row // 3) * 3 + column // 3
self.permitted_values = set([])
can be
def __init__(self, row: int, column: int):
self.value: int = 0
self.row = row
self.column = column
self.block: int ...
3
You could allow to initialize the stack locally.
Just by separating the bigger part of stack_create to separate function.
void stack_init(STACK* stack, char* mem, size_t size)
{
stack->mem = mem;
stack->size = size;
stack->top = -1;
}
char stack_mem[STACK_SIZE];
STACK stack;
stack_init(&stack, stack_mem, STACK_SIZE);
As for error ...
0
You're currently iterating over the slice each once, and then again for each value. That's understandable, but not ideal. Why not simply sort the data, and then check whether or not the next value is the same as the current one?
func distinct(values []string) int {
if len(values) == 0 {
return 0
}
// the loop doesn't count the last value
...
1
If r = number of rotations, a = int[] array, n = a.length, to rotate the array you need to
move a[r to n] to the beginning of the array
move a[0 to r] to end of array
Also r can be reduced to r % n, as for every n rotations, the array repeats.
Code:
int[] result = new int[];
r = r % n;
int count = 0;
for(int i=r;i<n;i++){
...
4
Invalid access
There are several occurrences of out-of-range access as 1201ProgramAlarm's comment pointed out:
for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;
costs[j + 1]
return costs[size_2];
This problem can be fixed by increasing the size of costs by one.
Usage of the standard library
std::vector<std::size_t> costs(...
Top 50 recent answers are included
