/r/algorithms

Computer Science for Computer Scientists

Computer Science for Computer Scientists

Other subreddits you may like:

- /r/compsci
- /r/programming
- /r/coding
- /r/tinycode
- /r/programmingchallenges
- /r/dailyprogrammer
- /r/ProgrammingLanguages
- /r/compilers
- /r/kernel
- /r/osdev
- /r/systems
- /r/softwarearchitecture
- /r/softwareengineering
- /r/softwaredevelopment
- /r/datastructures
- /r/learnprogramming
- /r/AskComputerScience
- /r/csbooks
- /r/math
- /r/logic
- /r/crypto
- /r/cryptography
- /r/complexsystems
- /r/MachineLearning
- /r/datamining
- /r/quant
- /r/sysor
- /r/CScareerquestions

^{Does} ^{this} ^{sidebar} ^{need} ^{an} ^{addition} ^{or} ^{correction?} ^{Tell} ^{me} ^{here}

/r/algorithms

4

'The player starts at the location labelled “S” and wants to reach the finish, labelled “F”. Each

turn they choose one of the four cardinal directions to move. However, except for S and F the

floor is covered in frictionless ice, so they will keep sliding in the chosen direction until they

hit the wall surrounding the area, or one of the rocks (labelled “0”).'

.....0...S

....0.....

0.....0..0

...0....0.

.F......0.

.0........

.......0..

.0.0..0..0

0.........

.00.....0

I was going ahead with a* but due to the fact that we have to turn only after hitting the block, i'm getting confused now.

solution to this

Start at (10,1)

Move left to (7,1)

Move down to (7,2)

Move left to (6,2)

Move down to (6,10)

Move right to (8,10)

Move up to (8,8)

Move right to (9,8)

Move up to (9,6)

Move left to (3,6)

Move up to (3,1)

Move left to (1,1)

Move down to (1,2)

Move right to (4,2)

Move down to (4,3)

Move left to (2,3)

Move down to (2,5)

Done!

10 Comments

2024/04/22

11:13 UTC

11:13 UTC

0

this is to be done on large dataset by a computer so most efficient possible please

Simple and inefficient algorithm would be (pseudocode):

```
function greatest_common_power_2_mod(int X, int Y) -> int{
int P = 1;
loop{
if ((X mod 2^P) != (Y mod 2^P)){
return (P-1);
}
P++;
}
}
```

but i expect there is more efficient way to check this?

6 Comments

2024/04/21

17:31 UTC

17:31 UTC

0

Please provide the accurate solution of the Below problem Statement Based on Netwrok Flow.

Suppose we are given a set of boxes, each specified by its height, width, and depth in centimeters.

All three side lengths of each box lie strictly between 10cm and 20cm. As you should expect, one

box can be placed inside another if the smaller box can be rotated so that its height, width, and

depth are respectively smaller than the height, width, and depth of the larger box. Boxes can be

nested recursively. Call a box is visible if it is not inside another box.

Describe and analyze an algorithm to nest the boxes so that the number of visible boxes is as

small as possible.

2 Comments

2024/04/20

12:32 UTC

12:32 UTC

1

Im starting to sort of understand this but if B were know to be NP-Complete would that prove anything about A? I know that it doesn't prove A to be NP-Complete but could I say that A is at least NP-Hard for sure?

7 Comments

2024/04/20

04:36 UTC

04:36 UTC

1

Hey guys! I'm coding an AI for Risk: Global dominations which is a popular online implementation of the board game Risk. I'll be writing a symbolic AI which will manually calculate paths for capturing territories and bonuses. Currently I have been stuck on finding a method to find the paths which the AI should take to capture a territory bonus (pics if you are unfamiliar with the game).

I am intending to represent the board as a graph, with nodes representing territories (and their troop/player data) and edges representing the connections between these territories. Examples of the AI pathing to take territories would be this position for the green agent to take Europe, and this position for the pink agent to take Asia. In this problem, we can have multiple starting stacks, with the goal to travel to all unoccupied territories and preferably end with the troops on external border territories to guard from invasion. Note that I am only looking for ways to find these paths from multiple starting points, not the evaluation of them. Also note that each territory can only be visited once, but as shown in the pink agent example, one territory can make multiple attacks off the same territory, it just cannot be recaptured.

Algorithms to achieve this, tips on board representation and fields of study covering similar problems would all be greatly appreciated! Cheers.

2 Comments

2024/04/20

04:45 UTC

04:45 UTC

5

I'm looking for advice on how to efficiently search a solution space under certain conditions.

The solution space is a multidimensional array of positive integers. At each point in the array I run a function that either fails or passes. Importantly, if the function passes at a point, then every point "under" it will also pass and doesn't need to be tested.

To illustrate, a 2D example would be an array of X and Y where X is 0 - 10 and Y is 0 - 15. If the point (2,3) passes then I know that (2,2), (2,1), (2,0), (1,3), (1,2), (1,1), (1,0), (0,3), (0,2) (0,1), (0,0) will also pass. Each of those points is "under" (2,3) in the sense that each element is less than or equal to it. There can be multiple “outer” pass points - for example, (1,5) could be a pass point in addition to (2,3).

Any advice is greatly appreciated, thank you!

8 Comments

2024/04/20

04:39 UTC

04:39 UTC

0

So I'm creating an application (using Excel VBA) to ingest a text file with a bunch of test results and present them in a spreadsheet in a more useful format. The text file consists of multiple log files combined, each with the same set of parameters, tested over multiple temperatures.

- 1st pass divides it up into "groups", and creates a table for each log file
- 2nd pass then takes the tables and lays them out side by side for comparison

My problem is that while each table has the same set of parameters (rows), if a test should fail for example, when it moves to the next temperature (column), the results continue on the next row as well. Not sure if that makes sense but basically the tables have the same # of parameters, but different # of rows...

So I need to compare all of the tables to each other, row by row, and if one has a value where another has a blank cell, I need to insert a blank row to match so that in the end they all have the same number of rows and each parameter lines up with its corresponding data. I created a visual aid to help better illustrate but cant seem to add it to this post.

I came up with a fix on another similar project, but it's terribly inefficient and this seems to me like a problem that has likely been solved already using some algorithm somewhere.

Looking for any suggestions/ideas on how I should approach this problem as efficiently as possible.

Thanks in advance

1 Comment

2024/04/20

02:42 UTC

02:42 UTC

0

I'm working on a project that involves implementing the MOCUS (Method for Obtaining Cut Sets) algorithm using Apache Spark and DataFrames. The MOCUS algorithm is used in fault tree analysis to generate minimal cut sets, which are the smallest combinations of basic events that can cause the top event to occur. I came across a helpful video lecture that explains the MOCUS algorithm and demonstrates the matrix method to retrieve minimum cut sets. I'm wondering if it's feasible to translate this algorithm to work with Spark DataFrames, or if it's simply not well-suited for this framework.

Here's a snippet of the code I have so far:

```
from pyspark.sql import SparkSession
from pyspark.sql.types import ArrayType, StringType, StructType, StructField
from pyspark.sql.functions import col, explode, array, when, lit, array_union, array_except
# Define the schema for the dataframe
schema = StructType([
StructField("id", StringType(), nullable=False),
StructField("gate", StringType(), nullable=False),
StructField("children", ArrayType(StringType()), nullable=False)
])
# Create the dataframe
data = [
("TOP", "And", ["E1", "E2"]),
("E1", "Or", ["A", "E3"]),
("E2", "Or", ["C", "E4"]),
("E3", "Or", ["B", "C"]),
("E4", "And", ["A", "B"])
# ("A", "Basic", []),
# ("B", "Basic", []),
# ("C", "Basic", []),
]
# spark = SparkSession.builder.getOrCreate()
df = spark.createDataFrame(data, schema).alias("events")
exploded_df = df.select(df.id, df.gate, df.children, explode(df.children).alias("child")).alias("exploded")
display(exploded_df)
joined_child_gates_df = exploded_df.join(df, col("events.id") == exploded_df.child, "left")\
.select("exploded.id", "exploded.gate", "exploded.children", "exploded.child", col("events.gate").alias("child_gate"))
display(joined_child_gates_df)
```

For the example provided, the minimum cut sets are [['C'], ['A', 'B']].

I also came across this paper with the best efficient algorithm.

Any insights, suggestions, or examples would be greatly appreciated. Is this a feasible approach, or should I consider a different strategy for implementing MOCUS with Spark?

0 Comments

2024/04/19

15:12 UTC

15:12 UTC

1

I have a system that handles signal processing of relatively sparse timewise signals, eg a single scalar sample every 20ms or so. I want support convolution that given the historic samples and last sample of two signals, outputs a single scalar value.

Does it mean that my output is simply, for two signals f and g with N samples:

`Σ_{m=0…N} f[N-m]g[m]`

Or am I missing something crucial here?

5 Comments

2024/04/19

15:12 UTC

15:12 UTC

1

Can someone help me reason about this problem?

I came across this problem in an online assessment and it's been giving me sleepless nights because I can't figure out how to do it even days later. The problem:

There's a conference happening from time 0 to time 't'. There's only one meeting room at the conference and there are presentations scheduled for this meeting room. The *ith* presentation starts at S[i] and ends at F[i]. No presentations overlap. The times when there are no presentations scheduled are free for the attendees to network. You're given a number 'k' which is the maximum number of presentations you can move around (maintaining that they don't overlap). You need to find the largest free time for networking by moving at most 'k' presentations around.

I don't remember the examples I saw but let me know if the question needs more clarifying.

7 Comments

2024/04/18

10:33 UTC

10:33 UTC

0

Is there an algorithm to measure how addictive something is? I don’t want to reinvent the wheel if it’s already out there. I’m expecting that I can’t get YouTube/Facebook/Tick Tock, ad nauseum(?) to release their algorithms

5 Comments

2024/04/18

03:20 UTC

03:20 UTC

0

The maximum amount of edges within a graph is `n(n-n)/2`

. How do you derive this function?

I could intuit this simply by drawing it out

A graph with 4 vertices and 6 edges:

```
O----O
|\ /|
| x |
|/ \|
O----O
```

I see that `4(4-3)/2 = 6`

My guess is that:

`n`

- amount of vertices

`(n - 1)`

- this comes from the minimum amount of edges per vertex

`/2`

- Each vertex has a pairwise relationship with another vertex resulting in a duplicate
- the divde by 2 eliminates the duplicate

9 Comments

2024/04/18

02:29 UTC

02:29 UTC

0

1 Comment

2024/04/17

23:34 UTC

23:34 UTC

1

hello! i have a question relating to kruskal's algorithm in relation to MSTs. i am trying to implement it right now but i keep getting this strange result where there are numerous components which are connected but the graph as a whole is not connected and is hence, not an MST. the code is pretty lengthy so i'll leave it below. any ideas on where i might have gone wrong?

```
import java.util.*;
public class TSPGraph implements IApproximateTSP {
//class for Edges as i choose to use Kruskal's algorithm
private class Edge implements Comparable<Edge> {
int source;
int destination;
double weight;
public Edge(int source, int destination, double weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
u/Override
public int compareTo(Edge e) {
return Double.compare(this.weight, e.weight);
}
}
private class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int item) {
if (parent[item] != item) {
// path compression
parent[item] = find(parent[item]);
}
return parent[item];
}
public void union(int a, int b) {
while (parent[a] != a) a = parent[a];
while (parent[b] != b) b = parent[b];
if (rank[a] > rank[b]) {
parent[b] = a;
rank[a] = rank[b] + rank[a];
} else {
parent[a] = b;
rank[b] = rank[b] + rank[a];
}
}
}
u/Override
public void MST(TSPMap map) {
int numVertices = map.getCount();
UnionFind unionFind = new UnionFind(numVertices);
ArrayList<Edge> arr = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
for (int j = i + 1; j < numVertices; j++) {
double weight = map.pointDistance(i, j);
arr.add(new Edge(i, j, weight));
}
}
arr.sort(Comparator.comparingDouble(e -> e.weight));
int mstEdges = 0;
for (Edge edge : arr) {
int root1 = unionFind.find(edge.source);
int root2 = unionFind.find(edge.destination);
// if the roots are different, add the edge to the MST.
if (root1 != root2) {
map.setLink(edge.source, edge.destination, false);
map.setLink(edge.destination, edge.source, false);
unionFind.union(root1, root2);
}
}
map.redraw();
}
```

0 Comments

2024/04/17

18:46 UTC

18:46 UTC

1

****MUST SEE EMBEDDED IMAGES TO UNDERSTAND****

I need to create an algorithm to crop an image into a 1:1 ratio while satisfying the following conditions:**(All required Like photo dimensions and eye and head positions are already calculated and given as input)**

**The Head Height Percentage Should Be 50-69% of the total photo height**

For Example, if the head height is 500px. If we choose 50% as the Head Height Percentage the image should be cropped to include an additional 500px of height So the head can be 50% of the total height (1000px).

Image**(The Head Height Percentage Controls the scale of the crop box 50% head height percentage: Largest Box 69% head height percentage: Smallest Box)**

Image
2. **The Eye Level Height Should Be 56-69% of the total photo height**

For Example, If we choose 60% as the eye level height percentage and the total height (from the previous step) came out to be 1000px then the height from the eye level to the bottom of the crop is 600px the image should be cropped to include an additional 400px of height above the eye So the total height is 1000px

(**The Eye Level Height Percentage Controls The Y position of the crop box)**

Image

**The solution (crop box) (1:1 ratio) needs to satisfy these conditions while not exceeding the original image's dimensions and not be less than 600x600 in resolution**

Image

I have tried brute forcing every Head Height Percentage value with every Eye Level Height value until one combination fits within the image's dimensions boundaries.

it worked but it is not efficient and it's a bottleneck in the process. I need an efficient solution.

1 Comment

2024/04/17

08:09 UTC

08:09 UTC

0

Hi!

For a class that I'm taking, I need to apply or extend Wilson's paper on generating random spanning trees. A lot of what I see online are maze generators that use Wilson's algorithm, I wonder if there are any other applications that I could explore.

1 Comment

2024/04/16

15:41 UTC

15:41 UTC

0

0 Comments

2024/04/16

18:42 UTC

18:42 UTC

0

Not sure if this is the right sub, but I'm trying to improve a sorting algorithm I made, and find the average time complexity. Python pseudocode below:

```
def boochin_sort(arr):
n = length of arr
while not sorted:
bigger = []
smaller = []
for i in range(1, n):
if arr[i] > arr[i-1]:
append arr[i] to bigger
else:
append arr[i] to smaller
append arr[0] to smaller
arr = smaller + bigger
return arr
```

Worst case: O(n^(2))

Best case: O(n)

Average case: ???

It's not very fast, and it grows quadratically, but I enjoyed making it. Any improvements welcome! (Also first time writing pseudocode, sorry.)

6 Comments

2024/04/16

07:39 UTC

07:39 UTC

0

I am looking for an algorithm to sort by trending with each item having 2 factors. Hypothetically lets say, we have multiple buttons, and for each button you have 2 values: interactions and subscriptions. How would I sort the buttons by trending?

I thought about using zscore with different weight on interactions and subscriptions, but I am wondering if I can do better.

0 Comments

2024/04/15

21:26 UTC

21:26 UTC

1

Not sure if this is the right place to ask. I have a project where I need to generate 3d geometries and determine its heat conductivity (the easy part) and if it is machinable. Since there will be too many parts to check, I will need some kind of algorithm to do that for me.

8 Comments

2024/04/15

15:35 UTC

15:35 UTC

2

My brother told me he thinks of heaps as “magic box that gives me minimum of maximum of things” and he visualises trees for binary trees. I have aphantasia so I didn’t know people could visualise things, how do all of you visualise computer science concepts or data structures and algorithms?

4 Comments

2024/04/14

17:12 UTC

17:12 UTC

0

HI,

I have a task that involves finding a Pareto set in a group of data I have, for example there are some vectors and from these vectors I have to find the Pareto set. I'm new to the game, learning some C.

I see there are so many algorithms that do this, but I really don't understand how they work. I don't want the solution, I just want to know how they work.

please help.

9 Comments

2024/04/13

17:38 UTC

17:38 UTC

6

The specific context for this problem is placement of electrodes in the brain.

You know the specific point where you want to place the electrode in the brain, and assume you know where "danger areas" are (i.e. blood vessels, breathing, consciousness, speech). You want to drill a straight line from the surface of the skull to that point while avoiding danger areas maximally. You also want to penalize longer lines because you want to drill through as little brain as possible.

Assume the brain is a 3D matrix (you may also pretend it is a spherical shape), and "danger areas" are sets of points within the 3D matrix. The line you drill needs to be a straight line.

How can I solve this?

I can tell that it seems like an optimization problem where you want to maximize distance from danger areas, and that a good first guess would probably just be the shortest path to the given point, but I'm not sure how to approach this.

22 Comments

2024/04/12

18:19 UTC

18:19 UTC

1

An algorithm (/ˈælɡərɪðəm/ ⓘ) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

*Wikipedia - Merriam-Webster Online Dictionary.*

Speaking of how I would maybe like to think: a morphism[0] between two computational structures[1], or a system of morphisms between a number of computational structures that converge to an "output"/target resulting in the completion of a computation. And because this motivates me to define what "Computation" is and in this sense, can I say that the morphism of structures is in fact what Computation is?

Also, Computation is an empirical demonstration of ideas. Maybe labeling the subject of computation under "Ideas" is a bit too ambiguous.

Anyway, I want to come to my question. I was reading a book concerning a state automata machine for parsing grammar of let's say, a programming language. My uncle's son who is a professional programmer asked me what I was reading. I referred him to a block of text containing pseudo-code. "Look! This is the algorithm of the parsing mechanism", I said. "This is not the algorithm, but rather the implementation of the algorithm" he replied. It sounded a bit absurd to me, "if this is the implementation of the algorithm, then where is the real algorithm, I can't see it anywhere in the book".

Up until that point, I thought, an algorithm can only exist in terms of pseudo-code, as pseudo-code is almost a plain English expression of your algorithmic ideas. However, it is not **the** plain English record of the mechanism of an algorithm. Maybe the true representation of an algorithm is right to exist in a paragraph of plain English?

Then mathematical ideas exist in functions, equations, identities, theorems etc. All of these are a domain of math lingo. There has to be something similar in terms of computational ideas. [ Computer Lingo if you can call it ]. I thought pseudo-language IS the computer lingo. Where have I gone wrong?

So, where does an algorithm exist? Can we have a concrete record of an algorithm? Just like a concrete record of Ideas introduces the need of a language. But an algorithm written in a language is an implementation of the algorithm, not the algorithm itself? Is a written text of an idea an implementation of the idea, but not the idea itself. I would like your input on this question.

[0]: I don't know if I'm using category theory, I guess I'm not (probably). A morphism can constitute one of X_{n+1} = A(X_n). Or maybe, X_{n+k} = [A(X_{n - (k - 1)}), B(X_{n - (k - 2)}),..., Z(X_n))]. It presupposes k length seed.

[1]: I don't think there exists a term for "Computational structure" or if this is even accurate to term it like that. But a computational structure is not a data structure. Computational structure defines the evolution of a data structure (namely the contents) with respect to time. You can think of a data structure as space, however a computational structure is spacetime.

2 Comments

2024/04/11

19:21 UTC

19:21 UTC

1

Hello everyone, I'm trying to solve a problem and I don't know how to do it, if anyone could help me solve it with some tip or algorithm I would be extremely grateful. The problem is the following:

I need to collect a specific key list. Keys can be obtained by opening a door. Doors can be opened with one or more keys. I need to return the possible paths to obtain the keys and the keys that were obtained on the path. When I can't return when I can't get a specific key, I must return the reason.

It would be something like this:

```
const doors = [
{
door: 1,
openWith: ["a", "b"],
obtain: ["c"],
},
{
door: 2,
openWith: ["e"],
obtain: ["f", "g"],
},
{
door: 3,
openWith: ["a", "c"],
obtain: ["d", "e"],
},
{
door: 4,
openWith: ["a", "c"],
obtain: ["f", "g"],
},
{
door: 5,
openWith: ["x"],
obtain: ["y"],
},
{
door: 6,
openWith: ["a", "z"],
obtain: ["y"],
},
];
const want = ["f", "g"];
const initialKeys = ["a", "b"];
getKeys(want, initialKeys);
/**
* Output: {
* success: [
* "to get: ['f','g'] you need to open: '1 -> 3 -> 2' and you will end up with the following keys: ['a', 'b', 'c', 'd', 'e', 'f', 'g']",
* "to get: ['f','g'] you need to open: '1 -> 4' and you will end up with the following keys: ['a', 'b', 'c', 'f', 'g']"
* ]
* }
*/
const want = ["y", "f"];
const initialKeys = ["a", "b"];
getKeys(want, initialKeys);
/**
* Output: {
* success: [
* "to get: ['f'] you need to open: '1 -> 3 -> 2' and you will end up with the following keys: ['a', 'b', 'c', 'd', 'e', 'f', 'g']",
* "to get: ['f'] you need to open: '1 -> 4' and you will end up with the following keys: ['a', 'b', 'c', 'f', 'g']"
* ],
* errors: [
* "failed to get: ['y'] through door 5 because you need to provide the following keys: ['x']",
* "failed to get: ['y'] through door 6 because you need to provide the following keys: ['z']",
* ]
* ]
*
*/
```

0 Comments

2024/04/10

23:24 UTC

23:24 UTC

4

What are some learning resources that teach everything from scratch or like from first principles, very basics!? The resources you found helpful or will reccomend others.

22 Comments

2024/04/09

11:52 UTC

11:52 UTC

0

Hi,

I made an algorithm but its pretty slow and I have a feeling it can be faster.

I have a list of polygons, which is the result of a contour tracing operation in a tif-image. The task is to find out which polygons are actually holes in other polygons. This is a recursive problem, so the hole might contain an island, which then might contain a hole etc. However in the end result the islands can be separate entities.

The end result should be a list of exterior polygons, with their holes in a list of interiors

- The polygons are guaranteed to be valid (non-self-intersecting)

- Holes also guaranteed to be fully contained within their exteriors (so no overlaps)

What I have so far: The algorithm loops over every polygon to find out if it is part of some other polygon. If it isn't it's an external polygon. After that it finds every polygon that is contained in the found external polygon and puts it into a list of interiors. The next step is then to figure out which interiors are direct holes, and which ones are part of islands. the former is added to the polygon, the latter is fed to the algorithm recursively, to be added separately to the output.

I'm also happy with python optimisations (Im not super experienced in Python)

2 Comments

2024/04/09

08:42 UTC

08:42 UTC

2

Hello,

some years ago I've published an article **Simple and effective algorithm for constant state****detection in time series.**

abstract:

The article introduces simple and effective algorithm for constant state detection in time series. The algorithm, based on sliding window of variable length, searches a sections of time series with at least some given minimal length, that have difference between maximal and minimal value in the section less than some given value. It is shown that the computational complexity of aforementioned algorithm is O(N log N ), where N is the length of time series.

13 Comments

2024/04/09

01:50 UTC

01:50 UTC

0

I am trying to understand quicksort implementation from the hackerrank's video here: https://www.youtube.com/watch?v=SLauY6PpjW4&ab_channel=HackerRank

In general I do understand the quicksort algorithm, the code structure and principles of this particular implementation (there are many variations but I found this one to be straightforward and maybe the easiest to remember).

But devil is in details that I fail to wrap my head around. In particular why are some comparisons done with `less than` and `greater than` rather than `less than or equal to` and `greater than or equal to` and vice versa. Also why do I return `i` index from the partition function and not the other index that goes backward. I commented these lines in code below where I asked my self these things.

There is not much explanation in the video why these things are is done in this way so maybe someone can help me get some intuition behind them. I'd rather have a sound logical reasoning in my head than having to remember which index to return from the partition function and which if statements comparison should be `strictly less/greater` vs. `less/greater than or equal to`.

```

```
def quicksort(arr, start, end):
if end > start:
pivot = arr[(start + end) // 2] # why floor and not ceiling
index = partition(arr, start, end, pivot)
quicksort(arr, start, index - 1) # why index-1 and not index
quicksort(arr, index, end) # why index and not index+1
return arr
# returns index at which array is separated into two subarrays
def partition(arr, start, end, pivot):
i = start
j = end
while i <= j: # why <= and not strictly <
while arr[i] < pivot: i +=1 # why strictly > and not >=
while arr[j] > pivot: j -=1 # why strictly < and not <=
if i <= j:
tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
i += 1
j -= 1
return i # why return i and not return j
def print_quicksort_result(arr):
print(quicksort(arr, 0, len(arr) - 1))
print("\n--- quicksort, pivot at middle:")
print_quicksort_result([2,1])
print_quicksort_result([3,2,1])
print_quicksort_result([2,3,1])
print_quicksort_result([4,2,3,1])
print_quicksort_result([8, 10, 5, 7, 3,1, 2, 4, 3, 9, 6])
```

```

The original code in video is in c++ and this is my Python version. You can copy/paste to your code editor and test it to confirm it works as expected.

I played around trying to understand how thing works, eg. I tried to return `j` instead of `i` from the partition function, and then change parameter in recursive calls like this:

```

```
quicksort(arr, start, index)
quicksort(arr, index+1, end)
```
```

but it fails to work (either array out of bound or recursive stack overflow error happens).

Any help in improving my reasoning behind these details is greatly appreciated.

4 Comments

2024/04/08

16:00 UTC

16:00 UTC

0

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

void detectCycle(int u, int p, vector<int>& status, vector<int>& parent, vector<vector<int>>& adjlist, vector<int> &cycles) {

if (status[u] == 2) {

return;

}

if (status[u] == 1) {

int cur = p;

cycles.push_back(cur);

while (cur != u) {

cur = parent[cur];

cycles.push_back(cur);

}

return;

}

parent[u] = p;

status[u] = 1;

for (int v : adjlist[u]) {

detectCycle(v, u, status, parent, adjlist, cycles);

}

status[u] = 2;

}

void bfs(int startNode, vector<vector<int>>& adjlist, vector<int>& vis, vector<int>& res) {

queue<int> q;

q.push(startNode);

vis[startNode] = 1;

res[startNode] = -1;

while (!q.empty()) {

int node = q.front();

q.pop();

for (int neighbor : adjlist[node]) {

if (!vis[neighbor]) {

vis[neighbor] = 1;

res[neighbor] = -1;

q.push(neighbor);

}

}

}

}

void markCycleVertex(vector<int>& res, vector<vector<int>>& adjlist, vector<int> &cycles, vector<int> &vis) {

for (int i = 0; i < cycles.size(); i++) {

for (int x : cycles) {

if (vis[x] == 0) {

bfs(x, adjlist, vis, res);

}

}

}

}

int main() {

int t;

cin >> t;

while (t--) {

int N, M;

cin >> N >> M;

vector<int> cycles;

vector<vector<int>> adjlist(N + 1);

vector<int> status(N + 1, 0);

vector<int> parent(N + 1, 0);

int n1, n2;

for (int i = 0; i < M; i++) {

cin >> n1 >> n2;

adjlist[n1].push_back(n2);

}

detectCycle(1, 0, status, parent, adjlist, cycles);

status.assign(N+1,0);

parent.assign(N+1,0);

status[1] = 1;

markCycleVertex(status, adjlist, cycles,parent);

queue<int> q;

q.push(1);

while (!q.empty()) {

int node = q.front();

q.pop();

for (auto it : adjlist[node]) {

if (status[it] == 0) {

q.push(it);

status[it] = 1;

} else if (status[it] == 1) {

status[it] = 2;

q.push(it);

}

}

}

for(int i=1;i<status.size();i++){

cout<<status[i]<<" ";

}

cout<<endl;

cycles.clear();

}

return 0;

}

I'm supposed to detect all nodes in a graph that have infinite ways to be reached. Basically if there's a cycle then all the nodes on that cycle can be reached infinitely, also all the nodes connected to such nodes will also have infinite ways. print -1 for all such nodes

Other than that if a node has finite ways then print 2, else if 1 way then 1, else if 0 then 0.

I'm encountering MLE using this algo

2 Comments

2024/04/08

18:16 UTC

18:16 UTC