Given some incoming some data in JSON format, representing unsorted train, bus, and flight tickets: ``` [{'from':'A', to:'B',...}, {'from':'C', to:'D',...}, {'from':'B', to:'C',...}]; ``` … I must sort tickets (A-B-B-C-C-D) and generate text (description) with all information about each trip (number of flight, gate, seat - it comes with JSON objects). But with some requirements: - it must be "API format". extensible code (should provide way to add information about different type of transport). - clean and easy code. I want to be honest with you, imagine that I'm junior in your team, and that I write for real project. Here is my solution. `var tickets = [ { from: "London", to: "Paris", transportType: "train", transport: { "number": "54S", "seat": "23" } }, { from: "Berlin", to: "Akrich", transportType: "bus", transport: { "number": "SR465", "seat": "56", "gate": "2A", } }, { from: "Paris", to: "Berlin", transportType: "flight", transport: { "number": "SR465", "seat": "56", "gate": "2A", "baggage": "will be automatically transferred from your last leg" } }, { from: "Moscow", to: "London", transportType: "flight", transport: { "number": "N554", "seat": "4A", "gate": "22", "baggage": "drop at ticket counter 344" } } ]; function TripSorter ( tickets ) { this.from = {}; this.to = {}; this.path = []; this.tickets = []; if ( tickets ) { this.importTickets( tickets ); } } // copy data in this.tickets. // create "from" ( contains only "from" points of route ) and "to" objects (hashMap); TripSorter.prototype.importTickets = function ( tickets ) { var self = this; self.tickets = [

The code runs fine and the algorithm is much faster than insertion sort. I built a modified bucket sort around the parameters given in the HW to sort a vector of ints with 50 iterations and 40000 items. Being new and not familiar with bucket sorts I haven't found any code examples quite like this one. So my question is about my style and possible room for optimization. How can I streamline this algorithm? ``` void intVectSort2(vector &V, int M) { // declare size for U and V int uSize = ((M * 2) + 1); int vectSize = V.size(); // allocate memory for U array and initialize to zeros int *U = new int[uSize]; for (int i = 0; i < uSize; i++) U[i] = 0; // step through M values and increment U when V is equal to M for (int j = 0; j < vectSize; j++) { int val = 0; int count = 0; int element = 0; int iterator = M; val = V[j]; while (val != iterator) iterator--; element = iterator + M; count = U[element]; count++; U[element] = count; } //load confirmed values in order back into V int index = 0; int currentSize = 0; for (int k = 0; k < uSize; k++) { int value = 0; int counter = 0; value = U[k]; if (value != 0) { while (counter < value) counter++; currentSize += counter; for (index; index < currentSize; index++) V[index] = k - M; } } // free dynamic memory delete [] U; } ```

Now that I have generated training data, I need to classify each example with a label to train a TensorFlow neural net (first building a suitable dataset). To streamline the process, I wrote this little Python script to help me. Any suggestions for improvement? classify.py: ``` # Builtin modules import glob import sys import os import shutil import wave import time import re from threading import Thread # 3rd party modules import scipy.io.wavfile import pyaudio DATA_DIR = 'raw_data' LABELED_DIR = 'labeled_data' answer = None def classify_files(): global answer # instantiate PyAudio p = pyaudio.PyAudio() for filename in glob.glob('{}/*.wav'.format(DATA_DIR)): # define stream chunk chunk = 1024 #open a wav format music wf = wave.open(filename, 'rb') #open stream stream = p.open(format=p.get_format_from_width(wf.getsampwidth()), channels=wf.getnchannels(), rate=wf.getframerate(), output=True) #read data data = wf.readframes(chunk) #play stream while answer is None: stream.write(data) data = wf.readframes(chunk) if data == b'': # if file is over then rewind wf.rewind() time.sleep(1) data = wf.readframes(chunk) # don't know how to classify, skip sample if answer == '.': answer = None continue # sort spectogram based on input spec_filename = 'spec{}.jpeg'.format(str(re.findall(r'\d+', filename)[0])) os.makedirs('{}/{}'.format(LABELED_DIR, answer), exist_ok=True) shutil.copyfile('{}/{}'.format(DATA_DIR, spec_filename), '{}/{}/{}'.format(LABELED_DIR, answer, spec_filename)) # reset answer field answer = None #stop stream stream.stop_stream() stream.close() #close PyAudio p.terminate() if __nam

I found sorting large arrays by a comparator that looks at the floating-point difference problematic, especially `-ffast-math`, (https://stackoverflow.com/questions/24442725/is-floating-point-addition-commutative-in-c.) This is intended to compare 32-bit floats exactly using integer arithmetic. Most references cited concern themselves with radix sort: - Nicholas Chapman, https://www.forwardscattering.org/post/34; - Michael Herf, http://stereopsis.com/radix.html; - Pierre Terdiman, http://codercorner.com/RadixSortRevisited.htm; - https://hbfs.wordpress.com/2010/03/09/radix-sort-on-floating-point-numbers/; - https://randomascii.wordpress.com/category/floating-point/. Using a comparison sort, like `qsort`, it only has to decide on a total order of IEEE-754 numbers by comparing two at a time. ``` #include /* EXIT_SUCCESS qsort */ #include /* printf */ #include /* assert */ #include /* clock */ #include /* INT_MAX */ #include /* C99 floating point macros */ #include /* C99 uint32_t */ struct Foo { float x; }; /** Compares float {x} values of {Foo} exactly. Assumes IEEE-754-ish 32-bit float has the same endianness as {uint32_t}. References: \cite{KimYoonKim2011FastSortFloatingPoint}, Nicholas Chapman \url{ https://www.forwardscattering.org/post/34 }, Michael Herf \url{ http://stereopsis.com/radix.html }, Pierre Terdiman \url{ http://codercorner.com/RadixSortRevisited.htm }, \url{ https://hbfs.wordpress.com/2010/03/09/radix-sort-on-floating-point-numbers/ }, \url{ https://randomascii.wordpress.com/category/floating-point/ }, \url{ https://stackoverflow.com/questions/10632237/any-c-compiler-where-evaluates-to-larger-than-one }. @implements Comparator @return Greater than, equal to, or less than 0, if the {Foo.x} pointed to by {av} is greater than, equal to, or less than the {Foo.x} pointed to by {bv}. */ static int x_cmp(const void *av, const void *bv) { const struct Foo *const a = av, *const b = bv; union { float f; uint32_t u; } ax,

I have written this code for fun. I'd like to hear your suggestions about how to make it more compact and pythonic. ``` from random import shuffle class Pool(object): """ Simple object that allows to sort """ def __init__(self): """ During initalization the final grid containing ordered balls is created 1 is placeholder for Solid balls 0 is placeholder for Striped balls """ self.grid = [[1],[0,0],[1,0,1],[0,1,0,0],[1,0,1,0,1]] def create_ball_set(self): """ This function returns a list containing a shuffled pool balls set """ balls = [] [balls.append([number]) for number in range(1, 16)] for ball in balls: if ball[0] < 9: ball.append("Solid") else: ball.append("Striped") shuffle(balls) return balls def sort_ball_set(self, unsorted_balls): """ This function returns a list of sorted balls from a list of shuffled balls """ # Ball 1 always goes in 1st place self.grid[0][0] = unsorted_balls.pop(unsorted_balls.index([1, 'Solid'])) # Ball 8 always goes in the 2nd row, in the middle self.grid[2][1] = unsorted_balls.pop(unsorted_balls.index([8, 'Solid'])) # Creating an empty list for solid balls unsorted_solid_balls = [] # Same thing but for striped balls unsorted_striped_balls = [] # Now it is time to divide solid balls from striped ones for ball in unsorted_balls: if ball[1] == 'Solid': unsorted_solid_balls.append(ball) elif ball[1] == 'Striped': unsorted_striped_balls.append(ball) # Once the balls are divided it is time to put them in the grid for grid_row_index, grid_row in enumerate(self.grid): for grid_col_index, grid_col_value in enumerate(grid_row):

This code sort the string below in ascending order. I'd prefer it split-up in two or three smaller, simpler methods. I'm also wondering whether my algorithm has a decent time complexity. Given string [H, B, D, G, F, E, A, C] Output [A, B, C, D, E, F, G, H] ``` public class sortArray { public static void sort (String[] str) { int lastPos = str.length - 1; int minPos = 0; String s = ""; for (int i = 0; i < lastPos; i++) { minPos = i; for (int j = i + 1; j <= lastPos; j++) if (str[j].compareTo (str[minPos]) < 0) minPos = j; if (minPos != i) { s = str[i]; str[i] = str[minPos]; str[minPos] = s; } } } public static void main(String[] args){ String[] str = {"H", "B", "D", "G","F", "E", "A", "C"}; sort(str); System.out.println(Arrays.toString(str)); } } ```

Suppose we need to sort a sequence and we know that every sequence component is within \$d\$ steps from its correct position. In such a case we can use a local heapsort: we take \$d\$ as an argument and set \$w = d + 1\$ (window width). We load the heap with \$w\$ first sequence components after which we pop the heap and add the next component to the heap (a sliding window). Finally, we dump the leftovers to the end of the range to be sorted: local_heapsort.hpp ``` // Created Apr 5, 2017 by Rodion "rodde" Efremov #ifndef CODERODDE_UTIL_LOCAL_HEAPSORT #define CODERODDE_UTIL_LOCAL_HEAPSORT #include #include #include #include namespace coderodde { namespace util { template void local_heapsort(RandomIt begin, RandomIt end, Cmp cmp, size_t max_distance) { using value_type = typename std::iterator_traits::value_type; size_t range_distance = std::distance(begin, end); max_distance = std::min(max_distance, range_distance); size_t window_width = max_distance + 1; auto window_end = begin; std::advance(window_end, window_width); std::priority_queue, Cmp> heap; auto current_iterator = begin; auto next_iterator = begin; std::advance(next_iterator, window_width); for (auto iter = current_iterator; iter != next_iterator; ++iter) { heap.push(*iter); } while (next_iterator != end) { *current_iterator = heap.top(); heap.pop(); heap.push(*next_iterator); ++current_iterator; ++next_iterator; } while (!heap.empty()) { *current_iterator = heap.top(); heap.pop(); ++current_iterator; }

The task is: Given an array A of size N, find all combinations of four elements in the array whose sum is equal to a given value K. The specific requirements are: - The combinations must be distinct - Each quadruple is separated by a delimiter "$", and must be printed in ascending order Here are some test cases highlighting the points above: - Case #1 - size of Array A: 5, K: 3, Array A: 0 0 2 1, Answer: 0 0 1 2 $ - Case #2 - size of Array A: 7, K: 23, Array A: 10 2 3 4 5 7 8, Answer: 2 3 8 10 $2 4 7 10 $3 5 7 8 $ I solved this task, but my solution involves a whole bunch of data structures...which may or may not be necessary. Additionally, at one point in time I generated all the possible combinations, which I think has a horrifying run-time of O(n4) :( ``` import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.Scanner; /** * Given an array A of size N, finds all combinations of four elements in the array whose * sum is equal to K. * @param args */ public class FindAllFourSumNumbers implements Comparable { private int first; private int second; private int third; private int fourth; private int[] m_arr; /** * A constructor function which stores four arguments in increasing order * @param args */ public FindAllFourSumNumbers(int one, int two, int three, int four) { int[] temp = {one, two, three, four}; Arrays.sort(temp); this.m_arr = temp; this.first = temp[0]; this.second = temp[1]; this.third = temp[2]; this.fourth = temp[3]; } /** * Getter function to get the array */ public int[] getArr() { return this.m_arr; } /** * Making 2 objects equal so long as their m_arr contain the same elements */ @Override public boolean equals(Object other) { if (other == null) { return false; }

I'm currently looking into the quickest way to sort an almost sorted array: Given an array of \$n\$ elements, where each element is at most \$k\$ away from its target position, devise an algorithm that sorts in \$O(n \log k)\$ time. I've implemented a sorting function which "slides" through an input list, pushes the element from a sliding window into a min heap (using the `heapq` built-in module), pops the minimum element which is collected in the `result` list: ``` from typing import List from heapq import heappush, heappop def sort_almost_sorted(a: List[int], k: int) -> List[int]: if not a: return [] length = len(a) if k >= length: return sorted(a) # apply built-in "timsort", designed to be quick on almost sorted lists result = [] min_heap = [] # maintain a min heap for a sliding window for slice_start in range(0, length, k + 1): # sliding window # push the next slice to min heap for index in range(slice_start, min(slice_start + k + 1, length)): heappush(min_heap, a[index]) result.append(heappop(min_heap)) # put the rest of the heap into the result for _ in range(len(min_heap)): result.append(heappop(min_heap)) return result ``` It works on my sample inputs. Do you think I'm using the minimum heap appropriately and this implementation is \$O(n \log k)\$? What would you improve code-quality or code-organization wise?

A sorting algorithm i have written. Pros - Gives each element a position once. - Few comparisons needed. Cons - For certain sets of data, large amount of extra storage is needed. - Only works with integers. The main reason i post the algorithm here is to learn if it already exists or not. From the research i have done i can't find anything similar. Though i am sceptical it would be very fun to know if it is new or not. What i mostly want to know however is if the algorithm could be useful and if my implementation of it is reasonable. Algorithm: Basic idea: When you divide the number you want to sort with the largest number of the set you get a percentage. This percentage gives a rough position where in the sorted list that number should be. Because it is difficult to know how the data is distributed the mean/average is used. By dividing the mean-value with the amount of unique values in the set, you can decide how much of the data set is above and below the mean-value. Then by using the above idea on all the elements, each element can get a position and be put in a new sorted list. Some lists with a high amount of clustering or small number of elements with large values, can have the same position calculated from different elements. Therefore all the elements are first put in a larger array to lessen the amount of collisions and if a collision occur the element is moved sligthly up/down. Bacause the new array is larger, elements can be moved up and down without causing problems with insertion of new ones. Duplicates are handled by counting the collisions of each element. When all elements have been placed in the larger array it is then collapsed into an array of the correct size. Exampel: [4, 20, 6, 4, 4] min = 4, max = 20, mean = 8 Calculating the possible amout of unique elements: (max - min + 1) = (20 - 4 + 1) = 17 Calculating a percentage for the mean: (1 - (mean-min)/unique) = (1 - (8-4)/17) = 0.76 This tells us roughly how la