I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first negating the weight of all the edges?

# Tag: algorithm

## algorithm – Find all of the paths that lead to the minimum sum

“Find minimum path sum” in a 2D grid, is a very popular question which is solved by dynamic programming. But what if instead of the minimum sum value, we return all the actual paths that lead to the minimum sum path? This was an interview question which has been puzzling me.

The original problem is :

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Ex:

```
Input: grid =
((1,3,1)
,(1,5,1)
,(4,2,1))
output: 7
Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
```

But instead of 7 I want to return (1,3,1,1,1) and all other paths that lead to sum of sum (in this case there is only one path). My current solution has exponential time complexity which is not good. Does anyone has a good solution to this problem?

## python – Making This “Fancy” Sort Algorithm a Little Better

This is my code:

```
def add_to_destination_array(destination_arr, src1, iSrc1, src2, iSrc2):
temp_array_length = len(destination_arr)
while len(destination_arr) - temp_array_length < len(src1) + len(src2):
if iSrc1 < len(src1):
if iSrc2 == len(src2):
destination_arr.append(src1(iSrc1))
iSrc1 += 1
else:
if src1(iSrc1) <= src2(iSrc2):
destination_arr.append(src1(iSrc1))
iSrc1 += 1
elif src2(iSrc2) <= src1(iSrc1):
destination_arr.append(src2(iSrc2))
iSrc2 += 1
elif iSrc2 < len(src2):
if iSrc1 == len(src1):
destination_arr.append(src2(iSrc2))
iSrc2 += 1
else:
if src2(iSrc2) <= src1(iSrc1):
destination_arr.append(src2(iSrc2))
iSrc2 += 1
elif src1(iSrc1) <= src2(iSrc2):
destination_arr.append(src1(iSrc1))
iSrc1 += 1
def fancy_sort(array_to_sort):
destination_array = ()
source1 = (array_to_sort(0))
source2 = ()
iSource1 = 0
iSource2 = 0
got_first_sublist = False
first_sublist_start = 0
second_sublist_start = 0
array_sorted = False
for i in range(1, len(array_to_sort)):
if len(source1) == 0:
source1.append(array_to_sort(i))
first_sublist_start = i
elif not got_first_sublist:
if source1(i-first_sublist_start-1) <= array_to_sort(i):
# Add elements to the first sublist
source1.append(array_to_sort(i))
else:
# First sublist found, now we start finding the seconds sublist
source2.append(array_to_sort(i))
second_sublist_start = i
got_first_sublist = True
else:
if source2(i-second_sublist_start-1) <= array_to_sort(i):
# Add elements to the second sublist
source2.append(array_to_sort(i))
else:
# Start adding elements to the destination_array
add_to_destination_array(destination_array, source1, iSource1, source2, iSource2)
# Reset the variables and start over
first_sublist_start = i
source1 = (array_to_sort(i))
source2 = ()
iSource1 = 0
iSource2 = 0
got_first_sublist = False
# If it didn't completely finish "sorting"
if len(source1) > 0:
if len(source1) == len(array_to_sort):
array_sorted = True
elif len(source2) > 0:
add_to_destination_array(destination_array, source1, iSource1, source2, iSource2)
else:
for i in source1:
destination_array.append(i)
# Call the function again to continue sorting
if not array_sorted:
return fancy_sort(destination_array)
return array_to_sort
sorting_array = (31, 72, 32, 10, 95, 50, 25, 18)
print(f"Before: {sorting_array}")
sorted_array = fancy_sort(sorting_array)
print(f"After: {sorted_array}")
```

I know it’s not the best, but it still works. This algorithm is supposed to be similar to the merge sort, but it doesn’t really split the array, and then merges them together. This algorith is supposed to find two already sorted sub-arrays (or sub-lists if you want to call it that), and then “merge” them into another array (called the destination array).

Here is the info I was given to make create this algorithm:

Algorithm in Plain English

A teacher is trying to alphabetize a collection of papers. She picks up the papers in her hand and, starting at the top of her stack, works her way down until she finds the first paper out of order. That sub-stack is sorted, and is set aside. She does the same thing to find the next sorted sub-stack. These two sub-stacks are then combined into a single sorted stack that she places on the table. She continues through the original stack in her hand, combining pairs of sorted sub-stacks and putting the results on top of the stack on the table. When she is finished, only the stack on the table remains. Now she picks up the stack on the table and again searches for sorted sub-stacks. When she finds a pair of these, they are combined and placed on the table again. This process continues until again all the papers are on the table. When she picks the stack up off of the table and everything is sorted (there is only one sorted sub-stack), then she is done!

Detailed Description of the Algorithm

Start at the beginning of the array and continue until you discover the first element that is not in sorted order. This sub-array may consist of one element, or it may consist of hundreds. We will call this sub-array source1. Now, starting in the slot after source1, find the next sub-array. Again, this may consist of one element or hundreds. We will call this sub-array source2. Note that source1 and source2 are sorted individually. These two sub-arrays correspond to the small piles in the previous paragraph.Now we will combine these two sub-arrays to form a single sorted sub-array. We will not do this in place. Instead, we will move them into a new sub-array called destination. Now since the two source arrays are sorted, we can assume that the smallest element in the two arrays is at the beginning of one of the two source arrays. In other words, it is at source1(0) or source2(0). Therefore destination(0) must be filled with either source1(0) or source2(0). If, for example, source2 has the lower of the two elements, then that element is moved to destination and the index of source2 (which we will call iSource2) is incremented by one. This process is continued until each element from source1 and source2 is moved into destination.

Once the first two sorted sub-arrays are moved to the destination array, then the next two sub-arrays are identified and combined into the destination array. This process continues until each element in the source array is moved into the destination array. Here, we can say that we have completed one pass of the source array.

Note that the sort is not finished yet. We have not sorted the array when we have completed just one pass. The only thing that a single pass accomplishes is to double the size of the sorted sub-arrays. We have to do many passes until the entire destination array becomes a single sorted sub-array. At that point, we can say that the array is sorted.

I am really wanting to go down to just using the `array_to_sort`

and `destination_array`

and then just use the indices for the other stuff instead of the two different source arrays.

Here is a working example.

## Help me understand this terrain intersection algorithm

I was looking for a fast way to get a ray intersection point of a terrain defined by a heightmap and I stumbled upon this: https://publications.lib.chalmers.se/records/fulltext/250170/250170.pdf

At part 3.2, I don’t quite understand why would we get an intersection point in the beginning of the while loop since it starts with the first quadtree node which is basically the whole map thus there shouldn’t be an intersection point with the ray (expect if the ray starts out of AABB, higher than the max height of the terrain but that is never the case for me).

Thank you very much if someone could make this thing clear.

## algorithm – Assessing BigO/small o for forming a dynamic dictionary based on searched key and values pair

I am trying to create a dictionary with a file containing text based on a matched pattern. Lines containing `key_str`

should become keys and subsequent lines not matching `key_str`

should become values and get associated with keys in the dictionary. so i have below code working: But I need help and getting the Big O analysis. How could i say my logic is worth case, Best Case or good case? Also, which case is small o and which is big O

File: `file2dict.result-soa1`

```
ml1
/var
/home
cpuml2
/var
/home
```

Output

```
my_dict: {ml1: ('/var','/home'), cpuml2: ('/var','/home')}
```

Code:

```
import os
homedir = os.environ.get('HOME')
key_str = "ml"
my_dict = {}
val_list = ()
key = ''
with open(homedir + '/backup/file2dict.result-soa1') as file2dict:
for line in file2dict:
words = line.split()
for aWord in words:
if key_str in aWord:
if key:
my_dict(key) = val_list
val_list = ()
key = aWord
else:
key = aWord
else:
val_list.append(aWord)
my_dict(key) = val_list
print(my_dict)
```

## mathematical optimization – FindMaximum::eit: The algorithm does not converge to the tolerance of _4.806217383937354`*^-6_ in _500_ iterations

This is an extended comment about your pdf not integrating to 1.

I’ve typed in the code from the image you posted and I think it looks exactly like the image:

```
dist = ProbabilityDistribution((1 - Exp(λ*(1 - Exp(1))))^(-1) *λ*β*(γ/α)*(x/α)^(γ - 1)*
(1 - Exp(-(x/α)^γ))^(β - 1)*Exp(λ*(1 - Exp(-(x/α)^γ))^β - (x/α)^γ + (1 - Exp(-(x/α)^γ))), {x, 1, ∞},
Assumptions -> {λ > 0, β > 0, α > 0, γ > 0})
```

My result as an image:

Your image of the resulting distribution:

But if a set of parameters is tried, the pdf does not integrate to 1:

```
parms = {λ -> 2, α -> 1, β -> 1, γ -> 1};
Integrate(PDF(dist /. parms, x), {x, 1, ∞}) // N
(* 9.2468 *)
```

There is an option for `ProbabilityDistribution`

to normalize the pdf (`Method->"Normalize"`

) but the proposed pdf seems too complicated for that to work on the symbolic distribution. (In other words, doing so does not return an answer in a reasonable or unreasonable amount of time.)

## complexity theory – Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?

It is possible to do it efficiently for a set of points, but imagine that the set is described by the intersection of linear equations in high dimensional space, so the number of vertices of the set can be exponential in the number of inequalities.

Given a direction, we can easily compute the distance of furthest points along that direction using linear programming. The question is how do we find that direction?

## context free – CYK algorithm in theory of computation

For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.

Doubt: I marked it false in a national level exam.I think it should be any null-free context free grammar and not any cfg because we first have to convert cfg to cnf but only null free cfg can be converted to cnf.

Is this statement correct?

## beginner – initialize 2d array using 12 tone algorithm with Rust

a rust exercise in initalizing a 12×12 array based on the algorithm for twelve tone matrix described here: https://www.instructables.com/Create-a-Twelve-Tone-melody-with-a-Twelve-Tone-Mat/

i copy pasted description from there into a comment but the post has pictures which may help you understand.

the code doesn’t actually do anything beyond initializing the array so i’m left with looking for ideas on how this would be implemented in idiomatic rust. i was also hoping for something readable but still efficient and that creates a read only block of data. suggestions there would be welcome, i’m still new at this.

i saw multiple crates for initializing an array described here: https://www.joshmcguigan.com/blog/array-initialization-rust/

but i had trouble figuring out how to use an algorithm to initialize the array rather than some examples of repeated data or random numbers.

also i didn’t like how i needed to special case row 0 with an if statement, which needs to be seeded by the user. the rest of the matrix depends on the values in that seed row. i would’ve liked to have used prior data in the matrix itself to build up the rest of the matrix, like in a dynamic programming sort of way. so i would’ve liked to have set the first 12 values, then set the next rows based on that row and some other prior values initialized.

i filled in the data by column because that was easier for me to follow the algorithm in the post but i think the initialization could also be done via row if you believe that is necessary for a more idiomatic solution but we’d need to access 3 prior values: up and to the left, up, and to the left i think in the matrix (i didn’t try that to check and was worried i might make a mistake that way).

i didn’t put much thought into selecting the Array2D crate. i googled and the column wise initialization with a function seemed to fit the algorithm. maybe there is a better crate.

i think using this crate this way results in multiple assignments and clones in memory. i would’ve preferred just setting each element once in a read only matrix as it is calculated but in a column wise order. however, the readme of the crate suggested using a vector of vectors might be less efficient. i believe underneath the Array2D uses a single vector.

```
use array2d::Array2D;
/*
This Instructable demonstrates the procedure for composing twelve-tone melodies using a twelve-tone matrix.
This technique was developed by Arnold Schoenberg in 1921, and its purpose is to compose music in which each of the twelve pitches are heard equally. This technique prevents the emphasis of any one note, thereby avoiding any sense of key or tonality.
After learning this technique, you will be able to quickly write melodies for your compositions without emphasizing any particular tonality. With practice, creating a Twelve-Tone matrix is a breeze, taking less than five minutes to complete.
To complete the matrix, you will need to be able to add and subtract numbers between 1 and 12. Writing melodies from this matrix will require a basic understanding of music notation.
Items needed for this task include a 12 by 12 grid (as shown below) and a pen or pencil. To write melodies from the matrix, you will need staff paper or software for writing music.
To hear what this type of music can sound like, follow this link for an example of Schoenberg's twelve-tone music. www.youtube.com/watch
Add TipAsk QuestionCommentDownload
Step 1: Write Numbers in the Top Row
Write each of the whole numbers from 1 through 12 across the top row of the grid such that each number appears exactly once.
The order of the numbers can be either completely arbitrary or carefully planned. The intervals between these numbers will become the number of half-steps between the pitches of your melody. With this knowledge, you can place the numbers in the first row of this matrix at predetermined intervals for musical effect. I have placed numbers in the top row, as shown.
Add TipAsk QuestionCommentDownload
Step 2: Populate the First Column
While the notes in the first row could have been written in any order you chose, the first column depends entirely upon the first row, so you should not select numbers for this column in the same manner as you selected numbers for the first row.
Begin by determining the difference between the first two elements of the top row. In the example below, the difference between the first two elements is -2, since 1 - 3 = -2.
The opposite of the difference between the first two elements of the top row should be the difference between the first two elements of the first column. For example, since the difference between the first two elements of the first row is -2, the difference between the first two elements of the first column should be +2. This is achieved by adding 2 to the first element. Since 3 + 2 = 5, the second element is 5.
Follow the same procedure for each subsequent set of adjacent elements. Continuing with the example below, observe that the difference between 9 and 1 is +8. Therefore, the difference between the second and third elements of the first column should be -8. Subtracting 8 from 5 yields - 3. Note that -3 is not between 1 and 12. Whenever you encounter a result that is not between 1 and 12, add or subtract 12 to that number as needed to make the result between 1 and 12. In this case, -3 + 12 = 9, so a 9 appears as the third element of the first column.
An image of the completed first row and first column of our example also appears below.
Check your work. One way to verify that you have not made any mistakes is to make sure that each whole number from 1 through 12 appears exactly one time in the first column.
Add TipAsk QuestionCommentDownload
Step 3: Fill in the Second Row
Once the first row and column are complete, the cells in the second row can be populated. Like the first column, the remaining cells are dependent upon the first row.
Determine the difference between the first elements of the first and second rows. Continuing with our example, we can see that the difference between the first two elements is 2, since 5 - 3 = 2. Fill in the remaining elements of the second row such that the difference between each second row element and the first row element immediately above it is the same as the difference you have just determined. In the example below, this means that the second element of the second row should be 3, because 1 + 2 = 3, and the third element should be 11, since 9 + 2 = 11.
As in the previous step, if you encounter a number less than 1 or greater than 12, add or subtract 12 as needed so that the number you write in the matrix is in the range from 1 through 12.
An image of the completed second row of our example is shown.
Check your work. Make sure that each number from 1 through 12 appears only once in the row. If this is not the case, then you have made a mistake.
Add TipAsk QuestionCommentDownload
Step 4: Fill in the Remaining Rows
The remaining rows should be completed in the same manner as the second row was populated.
Determine the difference between first element of the lowest row that is not completed and the first element of the row immediately above it. This difference should be replicated throughout the rest of the row. Returning to our example, we can observe that the difference between 9 and 5 is 4, so each element of the third row should be 4 greater than the element in the cell above it.
Each subsequent row of our example has been completed in this manner, and the resulting completed matrix appears below.
You can check your work once again by verifying that each number from 1 through 12 appears only once in each row and each column.
One final way to verify that the matrix is properly completed is to look along the diagonal that runs from the top left corner of the matrix to the bottom right corner. The number in each of these cells should be the same. In our example, this is the case; the number 3 appears in each cell of the diagonal.
Add TipAsk QuestionCommentDownload
Step 5: Translate the Numbers to Pitches
Translate the Numbers to Pitches
Now that the matrix is complete, you can select a few rows or colums and "translate" them into music. Each number corresponds to a specific pitch according to this list.
C 1
C# / Db 2
D 3
D# / Eb 4
E 5
F 6
F# / Gb 7
G 8
G# / Ab 9
A 10
A# / Bb 11
B 12
Select one or more rows or columns from the matrix and translate them to pitches. You can read the rows from left to right or from right to left, and the columns can be read from top to bottom or from bottom to top.
Returning to our example, the seventh row, read from left to right, was chosen for the first half of a melody. The tenth column, read from bottom to top, was chosen for the second half of the melody. The row and column are translated as follows.
Row 7:
10 8 4 12 11 1 3 2 7 5 6 9
A G D# B Bb C D Db Gb E F Ab
Column 10:
11 2 3 1 6 5 7 9 8 4 12 10
Bb C# D C F E Gb Ab G Eb B A
Add TipAsk QuestionCommentDownload
Step 6: Write Music!
Write Music!
Make a melody from the pitches. Make sure that you don't change the orders of the pitches, as changing the order of the pitches defeats the purpose creating the matrix.
Recall that the pitches generated in step 5 were as follows:
A G D# B Bb C D Db Gb E F Ab
Bb C# D C F E Gb Ab G Eb B A
I have completed our example by writing music from these pitches.
Pick your time signature, rhythms, and dynamics in any way you like. Note that using a key signature is not necessary because your melodies were not derived with any sense of key or tonality. 20th Century composers are known for writing specific dynamic, articulation, and tempo markings, so you can imitate this style by specifically spelling out these factors as well. I have done this in the example below.
Your finished melodies will be atonal and consistent with the methodologies employed by Arnold Schoenberg and other 20th Century composers.
*/
fn generate_matrix(seed_row: (i32; 12)) -> Array2D<i32> {
let mut counter = 0;
let mut last = 0;
let next = || {
let row = counter % 12;
let result = if row == 0 {
seed_row(counter / 12)
} else {
(last + seed_row(row - 1) - seed_row(row) + 12) % 12
};
last = result;
counter += 1;
if result == 0 {
12
}
else {
result
}
};
Array2D::filled_by_column_major(next, 12, 12)
}
fn main() {
const SEED_ROW: (i32; 12) = (3, 1, 9, 5, 4, 6, 8, 7, 12, 10, 11, 2);
let matrix: Array2D<i32> = generate_matrix(SEED_ROW);
// sample result (3, 1, 9, 5, 4, 6, 8, 7, 12, 10, 11, 2, 5, 3, 11, 7, 6, 8, 10, 9, 2, 12, 1, 4, 9, 7, 3, 11, 10, 12, 2, 1, 6, 4, 5, 8, 1, 11, 7, 3, 2, 4, 6, 5, 10, 8, 9, 12, 2, 12, 8, 4, 3, 5, 7, 6, 11, 9, 10, 1, 12, 10, 6, 2, 1, 3, 5, 4, 9, 7, 8, 11, 10, 8, 4, 12, 11, 1, 3, 2, 7, 5, 6, 9, 11, 9, 5, 1, 12, 2, 4, 3, 8, 6, 7, 10, 6, 4, 12, 8, 7, 9, 11, 10, 3, 1, 2, 5, 8, 6, 2, 10, 9, 11, 1, 12, 5, 3, 4, 7, 7, 5, 1, 9, 8, 10, 12, 11, 4, 2, 3, 6, 4, 2, 10, 6, 5, 7, 9, 8, 1, 11, 12, 3)
println!("{:?}", matrix)
}
```

## the algorithm for implementing the smell?

I can’t make an algorithm to implement this function: I need the player to leave behind a smell every time he clicks on the arrows.

I think it would work if you assign the smell the coordinates of the player and create it every time it moves.