algorithm,sorting,sequence,seq , How to go about a d-smooth sequence algorithm


How to go about a d-smooth sequence algorithm

Question:

Tag: algorithm,sorting,sequence,seq

I'm really struggling to design an algorithm to find d, which is the lowest value that can be added or subtracted (at most) to make a given sequence strictly increasing.

For example.. say seq[] = [2,4,8,3,1,12]

given that sequence, the algorithm should return "5" as d because you can add or subtract at most 5 to each element such that the function is strictly increasing.

I've tried several approaches and can't seem to get a solid technique down.

I've tried looping through the seq. and checking if seq[i] < seq[i+1]. If not, it checks if d>0.. if it is, try to add/subtract it from seq[i+1]. Otherwise it calculates d by taking the difference of seq[i-1] - seq[i].

I can't get it to be stable though and Its like I keep adding if statements that are more "special cases" for unique input sequences. People have suggested using a binary search approach, but I can't make sense of applying it to this problem.

Any tips and suggestions are greatly appreciated. Thanks!


Here's my code in progress - using Python - v4

def ComputeMaxDelta3(seq):
    # Create a copy to speed up comparison on modified values
    aItems = seq[1:] #copies sequence elements from 1 (ignores seq[0])
    # Will store the fix values for every item
    # this should allocate 'length' times the 0 value
    fixes = [0] * len(aItems)
    print("fixes>>",fixes)

    # Loop until no more fixes get applied
    bNeedFix = True
    while(bNeedFix):
        # Hope will have no fix this turn
        bNeedFix = False

        # loop all subsequent item pairs (i should run from 0 to length - 2)
        for i in range(0,len(aItems)-1):
            # Left item
            item1 = aItems[i]
            # right item
            item2 = aItems[i+1]

            # Compute delta between left and right item
            # We remember that (right >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 0):
                # Fix the right item
                fixes[i+1] -= nDelta
                aItems[i+1] -= nDelta
                # Need another loop
                bNeedFix = True

    # Compute the fix size (rounded up)
    # max(s) should be int and the division should produce an int
    nFix = int((max(fixes)+1)/2)
    print("current nFix:",nFix)


    # Balance all fixes
    for i in range(len(aItems)):
        fixes[i] -= nFix

    print("final Fixes:",fixes)
    print("d:",nFix)
    print("original sequence:",seq[1:])
    print("result sequence:",aItems)

    return

Here's whats displayed:

Working with: [6, 2, 4, 8, 3, 1, 12] 
    [0]= 6 So the following numbers are the sequence: 
         aItems = [2, 4, 8, 3, 1, 12] 

fixes>> [0, 0, 0, 0, 0, 0]
current nFix: 6
final Fixes: [-6, -6, -6, 0, 3, -6]
d: 1
original sequence: [2, 4, 8, 3, 1, 12]
result sequence: [2, 4, 8, 9, 10, 12]

d SHOULD be: 5

done!

~Note~

I start at 1 rather than 0 due to the first element being a key


Answer:

As anticipated, here is (or should be) the Python version of my initial solution:

def ComputeMaxDelta(aItems):
    # Create a copy to speed up comparison on modified values
    aItems = aItems[:]
    # Will store the fix values for every item
    # this should allocate 'length' times the 0 value
    fixes = [0] * len(aItems)

    # Loop until no more fixes get applied
    bNeedFix = True
    while(bNeedFix):
        # Hope will have no fix this turn
        bNeedFix = False

        # loop all subsequent item pairs (i should run from 0 to length - 2)
        for i in range(0,len(aItems)-1):
            # Left item
            item1 = aItems[i]
            # right item
            item2 = aItems[i+1]

            # Compute delta between left and right item
            # We remember that (right >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 0):
                # Fix the right item
                fixes[i+1] -= nDelta
                aItems[i+1] -= nDelta
                # Need another loop
                bNeedFix = True

    # Compute the fix size (rounded up)
    # max(s) should be int and the division should produce an int
    nFix = (max(fixes)+1)/2 # corrected from **(max(s)+1)/2**

    # Balance all fixes
    for i in range(len(s)):
        fixes[i] -= nFix

    print("d:",nFix) # corrected from **print("d:",nDelta)**
    print("s:",fixes)

    return

I took your Python and fixed in order to operate exactly as my C# solution. I don't know Python, but looking for some reference on the web, I should have found the points where your porting was failing.

If you compare your python version with mine you should find the following differences:

  1. You saved a reference aItems into s and used it as my fixes, but fixes was meant to start as all 0.
  2. You didn't cloned aItems over itself, then every alteration to its items was reflected outside of the method.
  3. Your for loop was starting at index 1, whereas mine started at 0 (the very first element).
  4. After the check for nDelta you subtracted nDelta from both s and aItems, but as I stated at points 1 and 2 they were pointing to the same items.
  5. The ceil instruction was unnedeed because the division between two integers produces an integer, as with C#.

Please remember that I fixed the Python code basing my knowledge only on online documentation, because I don't code in that language, so I'm not 100% sure about some syntax (my main doubt is about the fixes declaration).

Regards,
Daniele.


Related:


Understanding Big-Ω (Big-Omega) notation


algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

Find column with unique values move to the first column and sort worksheets


excel,vba,excel-vba,sorting
I have 2 worksheets with the same headers in different orders. Headers are I.D, Name, Department, Sales, Start date, End Date and a few others. What I am aiming to do is search through the workbooks in which the headers may be in different orders, find the column which has...

Should checking loop conditions be counted towards total number of comparisons?


c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

Reverse ^ operator for decryption


c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

Sort multiple columns of Excel in VBA given the top-left and lowest-right cell


excel,vba,excel-vba,sorting
I am trying to sort these three columns (Sort By Col-2) in excel using VBA. Top-left (Row number and Column number e.g. 1,1) and lowest-right cell (Row number and Column number e.g. 9,3) are known. Every cell contains the values of String type. Input: Col-1 Col-2 Col-3 P1 I1 XYZ...

elastic search sort in aggs by column


sorting,elasticsearch,group-by,order
I am trying to sort in elastic search in aggs, equivalent in mysql "ORDER BY Title ASC/DESC". Here is the index structure: 'body' => array( 'mappings' => array( 'test_type' => array( '_source' => array( 'enabled' => true ), 'properties' => array( 'ProductId' => array( 'type' => 'integer', 'index' => 'not_analyzed'...

EXC_BAD_ACCESS error occurring when running recursive merge sort method in a thread


c++,multithreading,sorting,recursion
I'm having trouble with my C++ code in xCode. I've tried debugging and I can't fix it. I know it's roughly when my mergeSort() method calls my mergeNumbers() method. I know it's not the method itself because I've run the method without threading and it works just fine. It's when...

Javascript sort array of objects in reverse chronological order


javascript,arrays,sorting
I have an array of objects which holds a list of jobs and I would like to sort them in reverse chronological order as they would appear on a resume for example. I came up with the below solution which 'seems' to work but I was wondering if there is...

Recursive solution doesn't iterate correctly


ruby,algorithm,search,recursion
I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off


algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

Sort arrayList based on both date and ID


java,sorting
i want to sort the list of task,first by date and then by taskID below is the code ArrayList<fullist> taskdet = new ArrayList<fullist>(); public static class fullist { public int date; public int id; public fullist(int id, int date) { this.date = date; this.id = id; } } i used...

Sorting vector of Pointers of Custom Class


c++,sorting,c++11,vector
I have vector<FPGA*> current_generation_, which I'd like to sort by FPGA member fitness_ using the sort_members function. Applicable code follows: bool sort_members (FPGA* fpga_first, FPGA* fpga_second) { return (fpga_first->fitness() < fpga_second->fitness()); }; fpga.hpp #include <vector> class FPGA { public: explicit FPGA(int input_gates, int output_gates, int normal_gates); const int fitness(); protected:...

How to give mathemarical proof or support my answer through reasoning as a general case?


algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

Knapsack with unbounded items


algorithm,dynamic-programming,knapsack-problem
I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

Identify that a string could be a datetime object


python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554


c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

Sort function giving floating point exception for a large input of 0's


c++,sorting,radix-sort,floating-point-exceptions
I have written a code for this problem: Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return...

WPF Listbox Collection custom sort


wpf,sorting,listbox,compare,collectionview
I have a listbox DropPrice MyPrice Price1 Price2 I want to sort it like this Price1 Price2 DropPrice MyPrice I mean, if there's an item that starts with the sequence "price", it gets priority, else the smallest string should get the priority. My source code: var lcv = (ListCollectionView)(CollectionViewSource.GetDefaultView(_itemsSource)); var...

Sort array by keys in custom order


php,arrays,sorting
I have the following multidimensional array Array ( [June 2015] => Array ( [LOW] => Array ( [0] => 160.50 ) [MEDIUM] => Array ( [0] => 0.00 ) [HIGH] => Array ( [0] => 60.80 ) ) [July 2015] => Array ( [MEDIUM] => Array ( [0] => 226.00...

Ranking with time weighting


python,algorithm,sorting,math
I am looking for a basic algorithm that gives more weigh to the recent reviews. So, the output value of the algorithm is mutable. For example, two reviews with exactly the same score, will have a different ranking based on the timestamp of the creation. Review_1 Score 10 creation 10/5/2014...

Sort when values are None or empty strings python


python,list,sorting,null
I have a list with dictionaries in which I sort them on different values. I'm doing it with these lines of code: def orderBy(self, col, dir, objlist): if dir == 'asc': sorted_objects = sorted(objlist, key=lambda k: k[col]) else: sorted_objects = sorted(objlist, key=lambda k: k[col], reverse=True) return sorted_objects Now the problem...

Looking for a particular algorithm for numerical integration


algorithm,numerical-methods,numerical,numerical-integration
Consider the following differential equation f(x) = g'(x) I have a build a code that spits out values of the function f(x) for the variable x, where x goes from 0 to very large. Now, I'm looking for a scheme that will analyse these values of f(x) in order to...

What is this algorithm mapping coordinates to numbers called?


algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

Binary Search - Best and worst case


algorithm,data-structures
In an exam I see a question: Which one of the following is true? For a binary search, the best-case occurs when the target item is in the beginning of the search list. For a binary search, the best-case occurs when the target is at the end of the search...

Freeing array of dynamic strings / lines in C


c,string,sorting,malloc,free
I am writing a program that is sorting the lines from the input text file. It does its job, however I get memory leaks using valgrind. #include <stdio.h> #include <stdlib.h> #include <string.h> char* getline(FILE * infile) { int size = 1024; char * line = (char*)malloc(size); int temp; int i=0;...

Dynamic programming: how to design algorithm for when there are two factors to consider?


algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

Algoritm to sort object by attribute value without allowing gaps or duplicates


python,sql,django,sorting,django-orm
I have a agenda with multiple dates, each date can contain 0 > ... items. Items can be sorted by position, positions should be Integer values without gaps and duplicates. class Item(models.Model): date = models.DateField() position = models.IntegerField() def move_to(position): qs = self.__class__.objects.filter(date=self.date) # if the position is taken, move...

Sorting in Ruby on rails


ruby-on-rails,json,sorting
I'm very new to Ruby on rails. I try to edit the following api. I want to sorting "can_go" which is true are shown at the top of list. I added this row before sending data, but the result is still order by "user_id". user_infos.sort { |a, b| - (a['can_go']<=>b['can_go'])...

Sorting jQuery dataTables by class name when there is no type or value


javascript,jquery,sorting,jquery-datatables
I'm using DataTables: https://www.datatables.net/ Heres my HTML: <div class="dataTable_wrapper"> <table class="table table-striped table-bordered table-hover center" id="dataTables-example"> <thead> <tr> <th>ID</th> <th>Title</th> <th>Actions</th> </tr> </thead> <tbody> <tr> <td>1</td> <td>title 1</td> <td><a href="./action-1"><span class="on"></span></a></td> </tr> <tr>...

Sort List of Numbers according to Custom Number Sequence


list,python-2.7,sorting
Question :A set of numbers will be passed as input. Also the redefined relationship of the digits 0-9 in ascending order will be passed as input. Based on the redefined relationship, the set of numbers must be listed in ascending order. Input Format: The first line will contain the the...

Disconnect all vertices in a graph - Algorithm


algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

Travels using graph


c++,algorithm,graph
Someone can help me to think in the better way to adapt Dijkstra's Algorithm in these conditions? All I thought didn't was good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This is a...

Explain the time complexity of these grouping functions


c++,algorithm,inheritance,time-complexity
Here I have 800 derived classes of Base and a list of 8000000 objects of these types, which can be of any order. The goal is to separate the list into the 800 types as efficiently as possible. Here I have written two functions to do that. The first is...

Best way to extract ODD digits from a binary number


algorithm,bit-manipulation
Given a 64 bit number, I need to extract every other bit from it, and convert it into a number: decimal: 357 binary: 0000 0001 0110 0101 odd bits: 0 0 0 1 1 0 1 1 decimal: 27 Any idea of a good algorithmic way to do it? And...

Formatting a Pivot Table in Python


python,sorting,pandas,format,dataframes
I am trying to reformat a table based on counts in different columns. df = pd.DataFrame({'Number': [1, 2, 3, 4, 5], 'X' : ['X1', 'X2', 'X3', 'X3', 'X3'], 'Y' : ['Y2','Y1','Y1','Y1', 'Y2'], 'Z' : ['Z3','Z1','Z1','Z2','Z1']}) Number X Y Z 0 1 X1 Y2 Z3 1 2 X2 Y1 Z1 2...

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))


c++,arrays,algorithm,recursion
I'm trying to write a recursive algorithm that returns true if at least one array[i] == i. And false if there is no array[i] = i. Also, the parameters needed are (int * arr, int start, int end). So i'll be traversing the array with a pointer. For example: int...

Sorting a HTML structure


javascript,html,sorting
Im trying to sort a div structure based on a paramter using a small javscript i found. It seems to not perform exactly as expected. I understand the sorting function is not parsing the values perfectly... This is the sorting logic is use... <script type="text/javascript"> // Sorting Logic $(function() {...

Longest Increasing Subsequence code in O(N)?


python,algorithm,time-complexity,longest-substring
Someone asked me a question Find the longest alphabetically increasing or equal string composed of those letters. Note that you are allowed to drop unused characters. So ghaaawxyzijbbbklccc returns aaabbbccc. Is an O(n) solution possible? and I implemented it code [in python] s = 'ghaaawxyzijbbbklccc' lst = [[] for i...

Algorithmic big o order of growth code


algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?


c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

Sum NA values in r


r,sorting,na
I am using a dataframe that has multiple NA values so I was thinking about sorting the attributes based on their NA values. I was trying to use a for loop and this is what I have so far: > data <- read.csv("C:/Users/Nikita/Desktop/first1k.csv") > for (i in 1:length(data) ) {...

Given an array/object of datetimes, how can I return an array/object of the times sorted by hour and times sorted by days of the week


php,arrays,sorting,datetime,laravel
PHP/Laravel, I'm getting an array of objects that includes date times for each record. I need to generate analytics on objects on an hourly basis of a day and daily basis of a week. So for example: For a date range of 1/1/2015 - 1/10/2015 I return 100 records all...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?


algorithm,go
I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

Javascript Sorting Array of Objects [duplicate]


javascript,arrays,sorting,object
This question already has an answer here: Sorting an array of JavaScript objects 14 answers (Please excuse any errors - this is my first post and I am also relatively new to Javascript) I'm trying to sort an array of objects by a specific property value in Javascript. I...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second


php,algorithm,digits
I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

3 X 3 magic square recursively


c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

Determining if a graph has a cycle without using DFS


algorithm,graph,cycle,dfs
I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

C# sorting arrays in ascending and descending order


c#,arrays,sorting
I'm having trouble writing a method that returns true if the elements of an array (numbers) are in sorted order, ascending or descending, and false, if they are not in any sorted order. I can return a correct boolean value if the array is ascending but i do not know...