Calculating travel statistics based on CSV data I took a code test for acme transport company and was rejected. That's ok. I'm still learning how to code. I didn't get much feedback so that's a bit frustrating. Can anyone here provide tips on how to optimize this python code? I thought that I had done a pretty good job with it, had the correct answers, etc. But apparently there are some fatal flaws, at least according to acme transport co!

Here's the challenge:

Parse a text file so that we know the following:

how many cars were dropped in total?
which car had the longest single trip? How long was the trip?
what car had the longest cumulative distance? How long was that.

The text file is formatted like this:

timestamp, Integer, The time in seconds since the start of the simulation
id, String, The id of the associated vehicle, e.g. JK5T
event_type, String The type of the event is one of START_RIDE, END_RIDE, DROP
x, Double, The x coordinate of the location of where the event happened in the simulation
y, Double, The y coordinate of the location of where the event happened in the simulation
user_id, Integer, The id of the associated user or NULL if the event does not have an associated user

The first few lines of the file look like this:

302,OPN1,DROP,33.28280226855614,-87.88162047789511,NULL
305,OPN1,START_RIDE,33.28280226855614,-87.88162047789511,4204
419,G2I0,DROP,-28.367411419413685,23.567421582328606,NULL
426,OPN1,END_RIDE,7.563016232237587,91.97004351346015,4204
428,LQBF,DROP,-50.50579634246066,-54.53980771216895,NULL
441,5HQH,DROP,-70.05156581770649,36.8358644984674,NULL

For my code I import a library called shapely that helps determine distances:

import csv
from shapely.geometry import Point
from collections import defaultdict

def main():
        myDict = defaultdict(dict)
        aDict = {}
        totalDrops = 0
        maxCar = None
        with open('events.txt') as f:
            reader = csv.reader(f)
            for row in reader:
                if row[2] == 'DROP':
                    totalDrops += 1
                    myDict[row[1]]['drop'] = Point(float(row[3]), float(row[4]))
                if row[2] == 'START_RIDE':
                    myDict[row[1]]['start_ride'] = Point(float(row[3]), float(row[4]))
                if row[2] == 'END_RIDE':
                    singleTripDistance = myDict[row[1]]['drop'].distance(Point(float(row[3]), float(row[4])))
                    distanceTraveled = myDict[row[1]]['start_ride'].distance(Point(float(row[3]), float(row[4])))
                    aDict[row[1]] = singleTripDistance
                    if not maxCar:
                        maxCar = row[1]
                    if 'allDistances' not in myDict[row[1]]:
                        myDict[row[1]]['allDistances'] = distanceTraveled
                    else:
                        myDict[row[1]]['allDistances'] += distanceTraveled
                    if  myDict[row[1]]['allDistances'] > myDict[maxCar]['allDistances']:
                        maxCar = row[1]
            maxSingleTrip = max(zip(aDict.values(), aDict.keys()))
            print('There are ' + '' + str(totalDrops) + ' ' + 'total Drops.' + '\n' + 'The Car that ends up furthest away from its drop is:' + ' ' + str(maxSingleTrip[1]) + ' ' + 'and the distance is:' + ' ' + str(maxSingleTrip[0]) + '\n' + 'The Car with the highest total distance traveled is:' + ' ' + maxCar + ', ' + 'and the total distance is:' + ' ' +  str(myDict[maxCar]['allDistances']))
main()

What you did well

You used the csv module for parsing the CSV file, and you processed it in one pass.  Your code is therefore reasonably efficient, and I wouldn't worry much about its performance.

Bugs

Your code reports "The Car that ends up furthest away from its drop is: …", but that is, in my interpretation, not the same as the longest single trip, which is what you were asked to calculate.

Concerns

Your data analysis code is mingled with the CSV parsing.  That makes the code hard to read and hard to maintain.

The deeply nested dictionaries are hard to understand.  What does myDict store?  Its purpose is not apparent from its name.  It's a two-level dictionary, where the first-level key is a vehicle_id, the second-level key is some attribute of that vehicle (the 'drop' coordinate, the 'start_ride' coordinate, or the 'allDistances' running total).  You would be better off with three independent dictionaries.  Better yet, as I've done below, define an Itinerary class instead.

What's aDict?  It keeps track of the distance from each car's drop point to the endpoint of its last trip.  Again, the variable name does not help.

The print() call is hard to read, in an excessively long line of code, with lots of str() casts and unnecessary string concatenations.  In this situation, I would recommend f-strings (introduced in Python 3.6), or str.format().

Suggested solution

This solution reports the car that ends up the furthest from its drop point, as you did, rather than the longest single trip as requested.

The Shapely library is overkill; subclassing namedtuple with a .distance() method is all I need for a handy Point class.  Euclidean distances can be calculated using math.hypot.

If you look at the data, you'll see that each car acts as a state machine.  It is initialized with a DROP event.  Thereafter, it alternates between START_RIDE and END_RIDE events.  No traveling is allowed when a START_RIDE occurs; the car is always the same place as its preceding DROP or END_RIDE coordinates.  In my Itinerary class, I've kept track of the .state of the car so that I can perform certain assertions, but it's only essential to keep track of the coordinates at each DROP and END_RIDE event.

The itineraries() function parses the CSV into one simple data structure: a dictionary mapping vehicle IDs to their itineraries.  I've chosen to use fileinput.input() to accept the file on the command line or through sys.stdin without hard-coding the filename.

The data analysis is accomplished using built-in functions len() and max() with generator expressions.  That is more expressive and less cumbersome than maintaining several intermediate results each time an END_RIDE event occurs.

from collections import namedtuple
import csv
import fileinput
from math import hypot
from operator import attrgetter

class Point(namedtuple('Point', 'x y')):
    def distance(self, other):
        """Euclidean distance between two points."""
        return hypot(self.x - other.x, self.y - other.y)

class Itinerary:
    def __init__(self, car, x, y):
        self.car = car
        self.coords = [Point(x, y)]
        self.state = 'DROP'
        self.cumul_dist = 0

    def start_ride(self, x, y):
        assert self.state in ('DROP', 'END_RIDE'), "Restarting unfinished ride"
        assert Point(x, y) == self.coords[-1], "Teleportation occurred"
        self.state = 'START_RIDE'

    def end_ride(self, x, y):
        assert self.state == 'START_RIDE', "Ending a ride that hasn't started"
        self.coords.append(Point(x, y))
        self.state = 'END_RIDE'
        self.cumul_dist += self.coords[-1].distance(self.coords[-2])

    @property
    def final_dist(self):
        return self.coords[-1].distance(self.coords[0])

def itineraries(f):
    cars = {}
    for timestamp, car, event_id, x, y, user_id in csv.reader(f):
        if event_id == 'DROP':
            assert car not in cars, "Dropping the same car twice"
            cars[car] = Itinerary(car, float(x), float(y))
        elif event_id == 'START_RIDE':
            cars[car].start_ride(float(x), float(y))
        elif event_id == 'END_RIDE':
            cars[car].end_ride(float(x), float(y))
    return cars

def main():
    cars = itineraries(fileinput.input()).values()
    drops = len(cars)
    furthest = max(cars, key=attrgetter('final_dist'))
    most_traveled = max(cars, key=attrgetter('cumul_dist'))
    print(f"""There are {drops} total drops.
The car that ends up furthest from its drop is {furthest.car}, at distance {furthest.final_dist}.
Car {most_traveled.car} travels the longest cumulative distance: {most_traveled.cumul_dist}.""")

if __name__ == '__main__':
    main()


Convert HTML input string to JavaScript Array literal I am trying to accept JavaScript array literals in an HTML text input.

The problem is that HTML text inputs are captured as strings,  such that an input of ['name', 'who', 1] becomes "['name', 'who', 1]".

My intention is for the following samples to yield the corresponding outputs.

"['river',"spring"]"        //  ["river","spring"]

"[{key:'value'},20,'who']"  //  [{"key":"value"},20,"who"]

The way I worked around   the problem is by using  eval  in the code snippet below:

const form = document.querySelector('.form');
    const inputField = document.querySelector('.input');
    const btnParse= document.querySelector('.btn');
    const out = document.querySelector('.out');

    form.addEventListener('submit', (e)=> {
      e.preventDefault();

      try {
        parsed = eval(inputField.value);

        if(Array.isArray(parsed)) {
          out.textContent = JSON.stringify(parsed);
        } else throw new Error('input is  not a valid array' );
      } catch(err) {
        out.textContent = `Invalid input: ${err.message}`;
      }
    });
 <form class="form">
      <fieldset>
        <legend>Enter array to parse</legend>
        <input class="input" type="text">
        <input class="btn" type="submit" value="parse">
      </fieldset>
    </form>
    <div>
      <p class="out">
      </p>
    </div>

My solution, however, allows for the execution of any Javascript code inputted into the text field, which is a huge vulnerability.

 What alternative way is there to converting JavaScript array literal HTML text inputs into JS array objects without using eval?

The answer

What you're actually trying to do is only converting objects from Javascript notation to actual javascript objects. Now what if there was a well-specified data interchange format that was named "Javascript object notation"? Oh there is?

parsed = JSON.parse(inputField.value);

You're even using JSON.stringify already...

Other general advice

Don't use classes to identify unique elements. That's exactly not what classes are intended for. Instead use IDs.
Make use of the strict evaluation mode for javascript... "use strict";
You could avoid the e.preventDefault if you didn't use a submit button, but a normal button instead or listened to 'onblur'. I personally would prefer the last method the most, possibly combined with an 'onchange' listener with a timeout.
Always put braces around your stuffs, in this case around the throw new Error. This helps avoid bugs when changing the code later.


CSS gradient transition_in javascript Do you have an idea to "transfer" this CSS Code to Javascript (maybe jQuery)?

html { background-color: #B94FC1; }
html:before, html:after { content: ""; height: 100%; width: 100%; position: fixed; z-index: -6; }
html:before { background-image: linear-gradient(to bottom, #5856D6 0%, #C644FC 100%); animation: fgradient 5s linear 0s infinite alternate; }
html:after { background-image: linear-gradient(to bottom, #C643FC 0%, #FF5F37 100%); animation: sgradient 5s linear 0s infinite alternate; }
@keyframes fgradient { 0% { opacity: 1; } 100% { opacity: 0; } }
@keyframes sgradient { 0% { opacity: 0; } 100% { opacity: 1; } }

Fiddle.

I want a transition from a gradient to an other. My own code works well, but I want try the same with Javascript ;)

Hope somebody can help me.

using jquery:

html

css

html { background-color: #B94FC1; }
body { margin:0; }
.gradient { content: ""; height: 100%; width: 100%; position: fixed; z-index: -6; }
.gradient.one { background-image: linear-gradient(to bottom, #5856D6 0%, #C644FC 100%);}
.gradient.two { background-image: linear-gradient(to bottom, #C643FC 0%, #FF5F37 100%); display:none; }

javascript

$(function() {
    fadeToggle( $('.gradient.one') );
    fadeToggle( $('.gradient.two') );
});

function fadeToggle(el) {
    el.fadeToggle(5000,null,function() { fadeToggle(el); });
}

fiddle: http://jsfiddle.net/aMVBk/2/


"Rock, Paper, Scissors" game This is a simple "Rock, Paper, Scissors" game I made in Python 3. Feel free to critique me and give suggestions on how can I improve my newbie coding skills.

import os
from random import randint

def ask_player():
    while True:
        print("Rock, paper or scissors?")
        ans = input(">")
        if ans in ('Rock', 'Paper', 'Scissors'):
            return ans

def results_msg(x, y, result):
    message = f"{x} beats {y}. You {result}!"
    return message

def comp_play():
    comp_choice = randint(0, 2)
    if comp_choice == 0:
        comp_choice = 'Rock'
    elif comp_choice == 1:
        comp_choice = 'Paper'
    else:
        comp_choice = 'Scissors'
    return comp_choice

def results(wins, losses, draws):
    player_choice = ask_player()
    comp_choice = comp_play()
    if player_choice == comp_choice:
        print("Draw. Nobody wins or losses.")
        draws += 1
    elif player_choice == 'Rock':
        if comp_choice == 'Paper':
            print(results_msg(comp_choice, player_choice, 'lost'))
            losses += 1
        else:
            print(results_msg(player_choice, comp_choice, 'won'))
            wins += 1
    elif player_choice == 'Paper':
        if comp_choice == 'Rock':
            print(results_msg(player_choice, comp_choice, 'won'))
            wins += 1
        else:
            print(results_msg(comp_choice, player_choice, 'lost'))
            losses += 1
    else:
        if comp_choice == 'Rock':
            print(results_msg(comp_choice, player_choice, 'lost'))
            losses += 1
        else:
            print(results_msg(player_choice, comp_choice, 'won'))
            wins += 1
    return wins, losses, draws

def play_again():
    while True:
        print("\nDo you want to play again?")
        print("[1] Yes")
        print("[2] No")
        ans = input("> ")
        if ans in '12':
            return ans

def main():
    wins = 0
    losses = 0
    draws = 0
    while True:
        os.system('cls' if os.name == 'nt' else 'clear')
        print(f"Wins: {wins}\nLosses: {losses}\nDraws: {draws}")
        wins, losses, draws = results(wins, losses, draws)
        if play_again() == '2':
            break

if __name__ == '__main__':
    main()

The follow-up is ""Rock, Paper, Scissors" game - follow-up".

Welcome back! There are a lot of good things to say about your program, and a few not-so-good. First, the good:

The code is clean, well laid-out, and generally written in a Pythonic style.
You have used functions to break things down.
You have structured your program as a module, which should make it easier to test.

Here are some things that I think could be improved:

Your function names need a little work. Consider this code:

player_choice = ask_player()
comp_choice = comp_play()

The object is to get two choices, one made by the player and the other made by the computer. Why are the two names so different? ask_player doesn't sound like getting a player's choice. It sounds like a generalized function that asks the player something and gets a response (i.e., input()). On the other hand, if player is spelled out why do you abbreviate the opponent in comp_play?

Using get is not always a good thing. It's one of the times when a function or method name doesn't need a verb in it - because it is frequently implicit when you are doing is_... or has_... or get_... or set_.... I don't think you need to spell out get_player_choice and get_computer_choice, but certainly player_choice and computer_choice would be appropriate.

This same logic applies to results. Instead of calling a function named results, why not call play_once? Or one_game? It's obvious from the code in main what is going on, but the function name doesn't really match the nature of the "step" being executed.

Your code breakdown is uneven. Consider this code:

def main():
    wins = 0
    losses = 0
    draws = 0
    while True:
        os.system('cls' if os.name == 'nt' else 'clear')
        print(f"Wins: {wins}\nLosses: {losses}\nDraws: {draws}")
        wins, losses, draws = results(wins, losses, draws)
        if play_again() == '2':
            break

Let's break those lines down. The key point I want to make is to keep neighboring statements at a similar level of abstraction.

First, you initialize your variables:

wins = 0
losses = 0
draws = 0

Because you are not using a class, and are not using globals (which would be appropriate in this scenario, IMO), you are stuck with doing variable initialization here. I suggest that you make this consistent with how you update the variables after each game:

wins, losses, draws = starting_scores()

Now, starting_scores could just return 0,0,0 or it could load from a saved-game file. But it makes the initialization sufficiently abstract, and it also spells out what you are doing.

Next, you loop:

while True:
    ...
    if play_again() == '2':
        break

The while True ... break could be rewritten to use a boolean variable. That's not super-critical, since the value of that variable is determined at only a single location. I consider the break to be equivalent in this case.

However, the comparison == '2' is not acceptable! Why? Because that's a detail, and your function name play_again should take care of that detail for you! Don't ask a question and then interpret the answer. Make your question-asking code handle the interpretation for you. Obviously play_again is short for "do you want to play again?" and '2' is not a valid answer. True or False are valid answers, so the code should look like:

while True:
    ...
    if not play_again():
        break

Finally, the inside of your loop has the same problem:

os.system('cls' if os.name == 'nt' else 'clear')
print(f"Wins: {wins}\nLosses: {losses}\nDraws: {draws}")
wins, losses, draws = results(wins, losses, draws)

What are you doing here? Well, you are clearing the screen, showing a summary of the games played, and playing one more round of the game. So say that!

clear_screen()
show_statistics(wins, losses, draws)
wins, losses, draws = play_one_round(wins, losses, draws)

Use appropriate data structures.

Your main code passes three variables to your play-game code. That code then returns three data items in a tuple, which you unpack into three variables.

In fact, you never use one of those variables without also having the others at hand. This should tell you that you are dealing with one aggregate data item, instead of three independent pieces of data. If that's true, just treat the scores as a single item:

def main():
    scores = starting_scores()

    while True:
        clear_screen()
        show_statistics(scores)
        scores = rock_paper_scissors(scores)

        if not play_again():
            break

Similarly, you can treat the scores as an aggregate until you have to update them:

# NB: was `results(wins, losses, draws):`
def rock_paper_scissors(scores):
    player = player_choice()
    computer = computer_choice()
    outcome = game_outcome(player, computer)
    show_results(outcome, player, computer)
    new_scores = update_scores(scores, outcome)
    return new_scores

At this point, the "play one game" has also become a collection of abstract statements. But notice that I'm treating scores as an opaque blob that I don't need to deal with: I just pass it along to the lower levels, with another data item describing the update to make.
Be consistent!

I notice that when asking the player to choose rock, paper, or scissors, you allow them to type in an answer. But given a Yes/No question, you require a selection of either 1 or 2. That's consistently surprising. When I ran your code, I wanted to keep typing my answers. (I kept hitting 'y' to play again.)

I suggest you either present the Rock/Paper/Scissors options as a menu, or present the Yes/No options as a string input and look for 'y' or 'n'. Making the interface that much more consistent will be an improvement.
Use data, or code. Not both.

This one is a little subtle, but take a look:

if comp_choice == 'Paper':
    print(results_msg(comp_choice, player_choice, 'lost'))
    losses += 1
else:
    print(results_msg(player_choice, comp_choice, 'won'))
    wins += 1

What's significant here is that you have an if/then statement that decides whether you won or lost. And then you pass that into your results_msg function as a string parameter. The result of this is that you have a string parameter to be substituted that gives information you already knew: whether the player won or lost.

Let's look at results_msg:

def results_msg(x, y, result):
    message = f"{x} beats {y}. You {result}!"
    return message

You have to consider that Python f-strings are code. And they're a pretty compact form of code, compared to the horror of str.format(). So writing:

print(results_msg(player_choice, comp_choice, 'won'))

is not really an improvement on writing:

print(f"{player} beats {computer}. You won!")

It's not clearer. It's not shorter. It does avoid problems with changing the text of the message, although there isn't much text in the message to change.

I don't think you need to hoist the f-string up into the calling function. I do think you should not pass 'won' or 'lost' as a parameter: you already decided you won or lost. Call a separate function instead.

if ...
    win_message(player_choice, comp_choice)
else:
    lose_message(player_choice, comp_choice)

Note that this will appear to conflict with the code structure I showed above- because in that code structure, I chose to treat the result as data, not code. I'm not saying you have to use data, or that you have to use code. I'm saying that you should pick one and stick with it. If you determine your outcome as code, go ahead and hard-code the outcome. If you determine your outcome as data, go ahead and treat it as data.

And as a side note, strings with substitutions in them make it hard to do i18n. So there's nothing wrong with having an array of totally spelled out messages at the bottom. It also gives a bit more "flavor" if you customize the verbs:

"Rock breaks scissors. You won!",
"Scissors cuts paper. You won!",
"Paper covers rock. You won!",
...


Generating variables to be named, filled in and operated on the fly in Python I am very new to Python and trying to refactor my code which is ripe for error.

Currently, I manually name a bunch of arrays:

open_cost_mat_train = np.array([])
closed_cost_mat_train = np.array([])
open_cost_mat_train_1 = np.array([])
closed_cost_mat_train_1 = np.array([])
open_cost_mat_train_2 = np.array([])
closed_cost_mat_train_2 = np.array([])

I then pass them to a function that fills the arrays in differently according to their number (e.g. _1, _2, and also if their name contains open or closed):

for i in xrange(10):
    open_cost_mat_train = np.append(open_cost_mat_train,i)
    open_cost_mat_train_1 = np.append(open_cost_mat_train_1,i/3))
    open_cost_mat_train_2 = np.append(open_cost_mat_train_2,i*64))
    closed_cost_mat_train = np.append(closed_cost_mat_train,i*3)
    closed_cost_mat_train_1 = np.append(closed_cost_mat_train_1,i/5))
    closed_cost_mat_train_2 = np.append(closed_cost_mat_train_2,i*102))

I then generate output file paths which corresponds with those matrices:

open_cost_category_path = "openCostClassifier.dat"
closed_cost_category_path = "closedCostClassifier.dat"
open_cost_category_path_1 = "openCostClassifier_1.dat"
closed_cost_category_path_1 = "closedCostClassifier_1.dat"
open_cost_category_path_2 = "openCostClassifier_2.dat"
closed_cost_category_path_2 = "closedCostClassifier_2.dat"

And finally I pass those variables to a new function (not necessary to show this for sake of question:

csoaa_open = example(open_cost_mat_train,open_cost_category_path)
csoaa_closed = example(closed_cost_mat_train,closed_cost_category_path)
csoaa_open_1 =example(open_cost_mat_train_1,open_cost_category_path_1)
csoaa_closed_1 = example(closed_cost_mat_train_1,closed_cost_category_path_1)
csoaa_open_2 = example(open_cost_mat_train_2,open_cost_category_path_2)
csoaa_closed_2 = example(closed_cost_mat_train_2,closed_cost_category_path_2)

What am I doing wrong with my code and how can I improve how I do things? Because this is the way I have written a lot of my code and getting one variable wrong. Doing this, for instance, will mess up the whole of my code:

csoaa_closed_1 = example(closed_cost_mat_train_2,closed_cost_category_path_1)

Just a little something to clean up the code.

The lines inside your for loop e.g

open_cost_mat_train = np.append(open_cost_mat_train,i)

do not require an assignment on the left, np.append modifies the array being passed in. I'm not sure if that's what you want, but maybe you should inspect the arrays after the loop to ensure they contain what you expect.

If you're worried about modifying arrays by mistake or require a original copy, it may be worth cloning them before running any operations on them.

copy_array = original_array.copy() will clone a numpy array.

Another way to verify you're passing the right parameters could be to check their names. They seem to be labelled logically with a number at the end, so it seems closed_cost_mat_train_2 should always go with closed_cost_category_path_2. See here, the inspect module looks like a good choice for this.

Docs for the numpy functions:

[1] numpy.append

[2] numpy.copy


Search Function With Wildcard in Haskell I'm teaching myself how to program Haskell, and I decided to make a find function in Haskell. What it does is it takes two strings, such as "hello" and "he", and it counts how many times "he" appears in "hello". In addition, it also uses the * character as a wildcard, so searching for "he*o" in "hello" will return 1.

Latest Update

This update used pattern matching and less guards, and also outputs 1 if ssearch "blah" "*".

ssearch _ [] = 0
ssearch [] _ = 0
ssearch ('*':_) _ = error "no '*' allowed in hay"
ssearch _ ['*'] = 1
ssearch haystack ('*':needles) = ssearch haystack needles --removes '*', and then searches through hay for the char after the '*'
ssearch (hay:haystack) (needle:needles)
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles)
  | otherwise = ssearch haystack (needle:needles)
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 ('*':_) _ = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
    search2  _ ['*'] = 1
    search2 haystack ('*':needles) = ssearch haystack needles
    search2 (hay:haystack) (needle:needles)
      | needle == hay = search2 haystack needles
          | otherwise = 0

Update:

Thinking over dave4420's comments, I decided to redo the entire algorithm. I think that it fixes most of the bugs.

ssearch _ [] = 0
ssearch [] _ = 0
ssearch (hay:haystack) (needle:needles)
  | hay == '*' = error "no '*' allowed in hay" --no confusion with wildcard things
  | needle == '*' = ssearch (hay:haystack) needles --removes '*', and then searches through hay for the char after the '*'
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles)
  | otherwise = ssearch haystack (needle:needles)
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 (hay:haystack) (needle:needles)
      | hay == '*' = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
      | (needle == '*') && (needles /= []) = ssearch (hay:haystack) needles
      | (needle == '*') && (needles == []) = 1
      | needle == hay = search2 haystack needles
          | otherwise = 0

I'm wondering if there are still any bugs, and also, if there is any way I can improve this code.

Old Code

search :: String -> String -> Integer
search x y = search1 x y y 0 -- n is set to 0, because nothing has been found yet :)
  where
    search1 :: String -> String -> String -> Integer -> Integer
    search1 _ _ [] n = n -- z can't be empty
    search1 x [] z n = search1 x z z (n+1) -- if y is empty but x isn't, it means the word was found, and y needs to be reset
    search1 [] _ _ n = n --end the program, bc if x is empty, the program has searched through the entire string
    search1 (x:xs) (y:ys) z n
      | x == '*' = error "you can not enter the character '*' in the first field: the '*' character is reserved for wildcard searches"
      | (y == '*') && ((head ys) == '*') = error "You can not include two '**' in a row, that messes up the wildcard operator"
      | x == y = search1 xs (ys) z n
      | (y == '*') && (ys /= []) = if (x == (head ys)) --this section is so search "hello" "h*llo" = 1
                        then search1 (x:xs) ys z n --if the string matches up with the rest of the string, excluding the '*', then redu the query, excluding the '*'
                       else search1 xs (y:ys) z n --} --otherwise keep on searching for the wildcard thing
      | (y == '*') && (ys == []) = n + 1 -- so search "hello" "*" = 1
      | otherwise = search1 xs z z n -- don't include (y:ys), otherwise search "hihe" "hhe" = 1

Update

Yes, that's better.

Here is a version of your code that uses pattern matching more and guards less. I think it is clearer.

ssearch _ [] = 0
ssearch [] _ = 0
ssearch ('*' : _) _ = error "no '*' allowed in hay" --no confusion with wildcard things
ssearch haystack ('*' : needles) = ssearch haystack needles --removes '*', and then searches through hay for the char after the '*'
ssearch (hay:haystack) (needle:needles)
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles)
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 ('*' : _) _ = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
    search2 _ ['*'] = 1
    search2 haystack ('*' : needles) = ssearch haystack needles
    search2 (hay:haystack) (needle:needles)
      | needle == hay = search2 haystack needles
    search2 _ _ = 0
ssearch (_:haystack) needles = ssearch haystack needles

There may still be bugs, but I can't see any :-)

Original

It appears to be buggy.

I expect search "hello" "he*lo" to result in 1, but it gives me 0.
I expect search "chanchance" "chance" to result in 1, but it gives me 0.

Also

search "bobobob" "bob" results in 2, but perhaps it should result in 3. Whether or not you want your function to count overlapping matches, you should document that it does/doesn't.

You need to rethink your algorithm. (Edit: as you are learning Haskell, I presume you'd rather get your function working yourself, rather than have us spoon-feed you a working version.)
x and y are not very descriptive names. They are suitable when you are writing generic code, but this code is more specific. I would call them haystack and needle instead (from the common English phrase).
This line:

  | (y == '*') && ((head ys) == '*') = error "You can not include two '**' in a row, that messes up the wildcard operator"

ys may be [], so head ys may be an error. You should be using pattern matching instead of head (and often instead of comparing to [] as well).
Why should a second * be an error anyway? The second * should successfully match a run of 0 characters, surely?


Is this C++ quicksort program okay? I wrote a quicksort program in C++.

Is it okay to implement it this way?
Am I using pointers correctly?
Is my style okay?
Any ideas to speed it up or save memory?

void change(int *i, int *j)
{
int temp = *j;
 *j = *i;
*i = temp;
}

int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end;

    while(i<=j)
    {
    for(; *i<=*start && i<=end; i++);
    for(; *j>=*start && start+1<=j; j--);
    if (i<j) change(i++,j--);
    }

    change(start,i-1);
    return i-1;
}

void quicksort(int *start, int *end)
{
    if (start >= end) return;

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl;  //this and...

    int *temp = start;
    temp = toplace(start,end);

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl; //...this are only to "see under the hood"
    std::cout<<std::endl;

    quicksort(start,temp-1);
    quicksort(temp+1,end);

}

An example usage:

int main(int argc, char* argv[])
{
    int A[] = {5,14,8,12,1,2,11,15,6,9,7,3,13,4,10};
    int n = sizeof (A) / sizeof(A[0]);

    quicksort(A, &A[n-1]);

    for (int i =0; i<n; i++) std::cout<<A[i] <<" ";

    getchar();
    return 0;
}

produces the output:

5 14 8 12 1 2 11 15 6 9 7 3 13 4 10
1 4 3 2 5 12 11 15 6 9 7 8 13 14 10

1 4 3 2
1 4 3 2

4 3 2
2 3 4

2 3
2 3

12 11 15 6 9 7 8 13 14 10
8 11 10 6 9 7 12 13 14 15

8 11 10 6 9 7
6 7 8 10 9 11

6 7
6 7

10 9 11
9 10 11

13 14 15
13 14 15

14 15
14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

The interface to quicksort:

quicksort(A, &A[n-1]);

In C I would expect to see a pointer and a size.
In C++ I would expect to see two iterators (like above), but generally the end point is usually one past the end (if you want to be consistent with C++ idioms and the STL way of doing things).

quicksort(A, A+n); // This is what I would expect to see.

Change!
I would normally call this swap()

void change(int *i, int *j)
{
    int temp = *j;
     *j = *i;
     *i = temp;
}

Also in C++ I would pass the values to be swapped by reference. And there is already a std::swap() that works perfectly well.

Your for() loops that do nothing in the body.

for(; *i<=*start && i<=end; i++);

These are hard to read when doing maintenance. At first glance it looks like you accidentally did not indent the code correctly you need to study the code to understand it is correct. I find it best to put an empty body (maybe even with a comment /* Deliberately Empty */

for(; *i<=*start && i<=end; i++)  { /* Empty */ }

In your loops you are testing the loop variable against start and end. Should they not be tested against each other?

while(i<=j)
{
for(; *i<=*start && i<=end; i++);
for(; *j>=*start && start+1<=j; j--);

// Should be:

for(; *i<=*start && i <= j; i++) { /* Empty */ }
for(; *j>=*start && i <= j; j--) { /* Empty */ }

Your quick sort seems to work but is slightly non traditional in a couple of features.

The pivot point *start. Values that are equal seem to go into both sub buckets. Traditionally they would go into a specific bucket.

You always use the first element as the pivot point. This case leads to worst case behavior of quicksort when the list is already sorted. Either choose a random element or the one in the middle of the partition.

Currently your code works with pointers to integers. But really you are using pointers as iterators. So you should templatize it so the inputs are not pointers but are generic iterators this then allows you to use the algorithm on any container type (with the side affect that it works with any type that implements the <= operator.


How can I make this implementation of Euler's method more efficient? I have an implementation of an Euler method for solving N-many 1st order coupled differential equations, but I feel that I did not write it as efficiently as I could, due to lack of programming experience.

Here is the implementation:

def eulerMethod(f, init0, h, om, mesh):
    """
    f          - array of ODES
    init0      - intial values
    h          - step size
    om         - array of symbols
    mesh       - time mesh to evolve over

    This implements Euler's method for finding numerically the
    solution of the 1st order system of N-many ODEs

    output in form of: [t:, om0:, om1:, om2:, ... ]
    """

    numOfDE = len(f)
    t00 = mesh[0]
    soln = [[t00]]
    for i in xrange(numOfDE): # create intitial soln
        soln[0].append(init0[i])

    subVal = {} # for diff eq substituion
    for i in xrange(len(om)):
        subVal.update({om[i]:init0[i]})

    g = sympy.symbols('g0:%d'%len(om))
    s = sympy.symbols('s0:%d'%len(om))

    # set up dictionary for equations
    eqDict = {g[0]:init0[0]}
    for i in xrange(1,len(om)):
        eqDict[g[i]] = init0[i]

    for i in xrange(6): # number of steps
        for i in xrange(len(om)): # performs euler steps
            eqDict[s[i]] = eqDict[g[i]] + h*1.0*(f[i].subs(subVal))

        for i in xrange(len(om)): # set recursive values
            eqDict[g[i]] = eqDict[s[i]]

        t00 += h
        soln.append([t00])
        for i in xrange(numOfDE): # append rest of solutions
            soln[len(soln)-1].append(eqDict[s[i]])

        subVal = {} # update values to be subsititied
        for i in xrange(len(om)):
            subVal.update({om[i]:eqDict[g[i]]})

    return soln

I know my naming is sort of confusing, but I just wanted to see how solid my algorithm is. I will be using this to typically solve 1000 coupled differential equations.

Naming is confusing indeed. What is sy, om, etc?
I do not understand a need for eqDict and subVal. Using init directly is much more straightforward:

for example,

 result = [ init0[i] + h*f[i].subs(init0) for i in xrange(init0) ]
 init0 = [ x for x in result]

Updating subVal at the end of the function is meaningless.
It is very unclear why the Euler step is repeated 6 times for one time step.
Is there a reason to pass mesh, if the code only uses mesh[0]?
The description should mention that the function only addresses autonomous systems.


Shopping cart business rules A purchase order has an order ID, a customer ID, total price and line items. Line items can be a product or membership type.

Business rules:

If the purchase order contains a membership, it has to be activated in the customer account immediately.
If the purchase order contains "Comprehensive First Aid training video," then "Basic First Aid training video" is added to the purchase order

public abstract class Product
{
}
 public class BookClubMembership : Product
{
    public bool IsActivated { get; set; }
}

Using the strategy design pattern, I define the first rule as follows:

public class BookClubMembershipRule : IPurchaseOrderRule
{
    readonly ICustomerActivationService _customerActivationService;

    public BookClubMembershipRule(ICustomerActivationService customerActivationService)
    {
        _customerActivationService = customerActivationService;
    }
    public void Execute(PurchaseOrder order)
    {
        foreach(var product in order.Items) {
            if (product is BookClubMembership)
            {
                _customerActivationService.ActivateBookMembership(order.CustomerId, product as BookClubMembership);
                break;
            }
        }

    }
}

public class PurchaseOrderProcessor
{
    public IList<IPurchaseOrderRule> Rules { get; }

    public PurchaseOrderProcessor(List<IPurchaseOrderRule> rules)
    {
        Rules = rules;
    }

    public void ProcessOrder(PurchaseOrder order)
    {
        foreach (var rule in Rules)
            rule.Execute(order);
    }

I don't feel comfortable using C# is and as above. Is there a better way for me to program these rules. I was thinking of Visitor pattern but given the 2nd rule. I will need to operate on the order and the item as well.

A line item is what I call an item in an order. For example, an order can look like this:

Order No: 3344656
 Total: 48.50
 Customer Id: 4567890
 Line items:
  • Video "Comprehensive First Aid Training"
  • Book "The Girl on the train"
  • Book Club Membership

Added code for the second rule:

public class ComprehensiveVideoRule : IPurchaseOrderRule
{
    public void Execute(PurchaseOrder order)
    {
        bool addNewVideo = false;
        foreach(var item in order.Items)
        {
            if(item is Video)
            {
                var checkItem = item as Video;
                if(checkItem.Title.Contains("Comprehensive"))
                    addNewVideo = true;
            }
        }
        if(addNewVideo) order.Items.Add(new Video("Basic First Aid"));
    }
}

There's no point in an abstract class with nothing in it. I assume a product has name, description, price, a SKU (product id) at least.

  Line items can be a product or membership type.

implies that a membership is not a product yet I see

public class BookClubMembership : Product

Looks like you'll have every rule iterate the order items. I'd rather see the PurchaseOrderProcessor iterate the items; and only once.

public class PurchaseOrderProcessor {
   public IList<IPurchaseOrderRule> Rules { get; }

The Rules list should not be public. Hide state and expose functionality. If you need to add rules for example, make an Add method.

  Is there a better way for me to program these rules

The Product can have a "type" - with all the types defined in an enum. This eliminates the need for subclasses.

What is a 'line item'? If it means something I'd expect a class. Use your domain language accurately.

  ... I will need to operate on the order and the item as well.

Show me the codez!

_customerActivationService.ActivateBookMembership(order.CustomerId,

Is it a valid assumption that the membership is for the person making the purchase?


Using an AsyncTask to populate a ListView in a Fragment From a SQLite table This is the first time that I have played around with AsyncTask in Android and I wanted to make sure I'm using it correctly. The idea is I'm grabbing all the rows from a table in the database using dao and putting them into an Arraylist based off my Item class. Once finished, I added it to a custom Adapter and add it to my ListView. I wasn't sure if the placement to the AsyncTask class inside the ListFragment is correct or if I used getActivity() correctly ( would it have been better to pass it as a variable?). Any other constructive criticism is welcome as well.

package com.domain.myapp;

import java.util.ArrayList;

import android.app.Activity;
import android.os.AsyncTask;
import android.os.Bundle;
import android.support.v4.app.ListFragment;
import android.view.Menu;
import android.view.MenuInflater;
import android.view.MenuItem;
import android.view.View;
import android.widget.ListView;

import com.domain.myapp.adapters.ItemsListAdapter;
import com.domain.myapp.database.DAO;
import com.domain.myapp.models.Item;

public class ItemsListFragment extends ListFragment {

    private ItemsListAdapter falAdp;
    private OnFragmentInteractionListener mListener;

    public ItemsListFragment() {
    }

    @Override
    public void onCreateOptionsMenu(Menu menu, MenuInflater inflater) {

        inflater.inflate(R.menu.item_list_view_menu, menu);
    }

    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        getItemLists gfl = new getItemLists();
        gfl.execute();
    }

    @Override
    public void onAttach(Activity activity) {
        super.onAttach(activity);
        try {
            mListener = (OnFragmentInteractionListener) activity;
        } catch (ClassCastException e) {
            throw new ClassCastException(activity.toString()
                    + " must implement OnFragmentInteractionListener");
        }
    }

    @Override
    public void onDetach() {
        super.onDetach();
        mListener = null;
    }

    @Override
    public boolean onOptionsItemSelected(MenuItem item) {
        mListener.onFragmentInteraction(item.getItemId(), 0);
        return true;
    }

    @Override
    public void onListItemClick(ListView l, View v, int position, long id) {
        super.onListItemClick(l, v, position, id);

        if (null != mListener) {
            mListener.onFragmentInteraction(R.id.ViewItemDetails, falAdp
                    .getItem(position).getId());
        }
    }

    public interface OnFragmentInteractionListener {
        public void onFragmentInteraction(int mnuId, int Id);
    }

    private class getItemLists extends
            AsyncTask<Void, String, ArrayList<Item>> {
        @Override
        protected void onPreExecute() {
            super.onPreExecute();
        }

        @Override
        protected void onProgressUpdate(String... values) {
            super.onProgressUpdate(values);
        }

        @Override
        protected ArrayList<Item> doInBackground(Void... params) {
            DAO dao = new DAO();
            ArrayList<Item> fal = dao.ItemsGetList(getActivity());
            return fal;
        }

        @Override
        protected void onPostExecute(ArrayList<Item> result) {
            super.onPostExecute(result);

            falAdp = new ItemsListAdapter(getActivity(),
                    R.layout.fragment_list_item_text_view, result);
            setListAdapter(falAdp);
        }
    }
}

All in all, this code is great. I don't see much in the way of problems. There are a few nit-picks:

    } catch (ClassCastException e) {
        throw new ClassCastException(activity.toString()
                + " must implement OnFragmentInteractionListener");
    }

The above code takes one ClassCastException and swaps it with another. Is it necessary? If it is necessary (because the current message does not give details on the current activity), then I recommend initializing the cause of the thrown CCE:

    } catch (ClassCastException e) {
        ClassCastException tothrow = new ClassCastException(activity.toString()
                + " must implement OnFragmentInteractionListener");
        tothrow.initCause(e);
        throw tothrow;
    }

it is a pain, but you benefit from getting all the information in the stack trace. Currently you are losing some.

The only other issue I see is the extension of the AsyncTask. You have re-implemented the methods:

    @Override
    protected void onPreExecute() {
        super.onPreExecute();
    }

    @Override
    protected void onProgressUpdate(String... values) {
        super.onProgressUpdate(values);
    }

This is completely unnecessary and you can delete that code. Just let the ancestor code be.


JavaScript debounce function I built one JavaScript debounce function. I need a JavaScript expert's opinion if this is the correct way to do it, and if not, then what the flaw is in this current function.

var debounce = function(inpFun, wait) {
    var timeout;
    return function () {
        if(!timeout) {
            inpFun.apply(this, arguments);
            timeout = setTimeout(function() {
                timeout = undefined;
            }, wait);
        }
        else {
            console.log("Debouncing");
        }
    }
};

var buttonClickFunction = debounce(function (event) {
    console.log("Button Clicked");
    console.log(event.target.id);
}, 2000);

document.querySelector("#button1").addEventListener("click", buttonClickFunction);

Event rate limiter
It is important to use the correct terms when defining functions. If you are unsure it is always better to look up the literature to ensure you are using the term correctly.
Debouncing
You have not implemented a de-bounce. De-bounce delays action on an event to prevent it firing in rapid succession.
The term comes from ye old day hardware where the mechanical switch would have a tendency to bounce on the contacts, giving a series of on/off signals when only one was intended.
In Javascript we use de-bounce to prevent events that fire at high rates (eg mouse resize) from firing at a rate higher than is useful, (eg screen refresh rate.)
You could implement a de-bounce as follows
const debounce = {
    debounceTime : 33, // in ms
    timeoutHandle : undefined,
    ondebounced(event) {
        log("Resized");
    },
    event(event) {
        clearTimeout(debounce.timeoutHandle);
        debounce.timeoutHandle = setTimeout(debounce.ondebounced, debounce.debounceTime, event)
    }
}
addEventListener("resize",debounce.event);

It will wait 33ms after the last resize event before calling the de-bounced function.
Rate limiter
You have implemented a rate limiter, that forces an event to fire at a set maximum rate. The difference are minor,

De-bounce fires after the events (signal noise) while a rate limiter fire as soon as possible.
De-bounce delay is indeterminate, while rate limiting has a fixed determinate delay.

Your code
Your code is a little old school. You should keep up with the lates JS version ES8.

You should be using const when you intended variables not to change.
Use arrow functions.
Use the spread / rest tokens for passing unknown arguments. See example

You also are mixing a variable's use. The var timeout. This may not cause you trouble at the moment and seem like a good idea to reduce code size by doubling a variables meaning, (means timeoutHandle, and Block events) But will bite if in future you make changes and forget that timeout is more than just a handle.
Never mix a variables meaning without making it clear in the name
Example
The following is an example of how you could implement a rate limiter.
The functionality is encapsulated and access is only via getters and setters to prevent miss use. See comments for more. This is only an example, not a definitive how too.

    // Encapsulated rateLimit event utility
    const rateLimit = (()=>{
        const rate = 2000;  // the max rate in ms

        // the limiting functions, pass the event to call
        // returns an API for handling the events.
        return function (eventFunc){
            var handle;  // for unblock event
            var blocked = false;  // true if blocked
            var event;  // the event to call if not blocked
            // this function handles the incoming event
            const eventHandler = (...eventArgs) => {
                if(blocked){
                    log("Event blocked. Too fast.")
                }else{
                    API.block = true;
                    if (event) { event(...eventArgs) }
                }
            }

            // the API
            // block bool (write only) set to true will block events for
            // rate but only if not already blocked. Set to false to clear any blocking
            // blocked returns (read only) bool for current blocking state
            // onlimitedevent  read/write function to call on event. If not a function then clears the event
            // event read only gets the event to attach to the listener
            const API = {
                set block(value) {
                    if (value && !blocked) {
                        handle = setTimeout(()=>API.block = false, rate);
                        blocked = true;
                    } else if (!value && blocked) {
                        clearTimeout(handle); // incase unblock is from outside
                        blocked = false

                    }
                },
                get blocked() { return blocked },
                set onlimitedevent(func) { event = typeof func === "function"  ? func : undefined },
                get onlimitedevent() { return event },
                get event() { return eventHandler },

            }
            API.onlimitedevent = eventFunc;
            return API;
        };

    })();

    const clicker = rateLimit(() => {log("clicked")});
    document.body.addEventListener("click", clicker.event);
    log("Ready, click me to test.");

    function log(...data) { out.appendChild(Object.assign(document.createElement("div"),{textContent : data.toString()})) }


Adding a new record to the beginning of the approval chain from the delegation chain Table Structure

  ApprovalOrder int

  EntityCode    varchar

  CostCentre varchar

  DelegationCode    varchar

  ProjectCode   varchar

  RoleGroup varchar

  Position  varchar

  DelegationText    varchar

  DelegationAmount  money

  Active    bit

Query / Explanation

The purpose is to pull all records for a delegation chain and add a new record at the beginning of the approval chain. RowID is used when talking with an external system and is a required part of the returned results.

I'm wondering if there's a better way that I could have constructed this query instead of the approach I took below? Beyond that I'm definitely interested in general performance / formatting suggestions.

/* Define ye values */
declare @role_group as int = 55
declare @position as char(55) = 'Asset Analyst'
declare @delegation_text as int = null
declare @delegation_amount as int = 0

declare @entity as int = 1410
declare @project_code as int = 10022
declare @delegation_code as varchar(10) = 'NC'

select top 1
    '1' + cast(@entity as varchar(10)) + @delegation_code as 'RowID' ,
    1 as 'ApprovalOrder' ,
    @entity as 'EntityCode',
    CostCentre as 'CostCentre',
    @delegation_code as 'DelegationCode' ,
    @project_code as 'ProjectCode' ,
    @role_group as 'RoleGroup' ,
    @position as 'Position',
    @delegation_text as 'DelegationText' ,
    @delegation_amount as 'DelegationAmount' ,
    Active
from
    workflow.delegation_engine
where
    EntityCode = @entity
    and ProjectCode = @project_code
    and DelegationCode = @delegation_code

union
select
    de.RowID ,
    cast(de.ApprovalOrder as int) + 1 as 'ApprovalOrder' ,
    de.EntityCode ,
    de.CostCentre ,
    de.DelegationCode ,
    de.ProjectCode ,
    de.RoleGroup ,
    de.Position ,
    de.DelegationText ,
    de.DelegationAmount ,
    de.Active
from
    (
        select
            cast(de.ApprovalOrder + 1 as varchar(4))
                + cast(de.EntityCode as varchar(8))
                + cast(de.DelegationCode as varchar(12)) as 'RowID' ,
            ApprovalOrder ,
            EntityCode ,
            CostCentre ,
            DelegationCode ,
            ProjectCode ,
            RoleGroup ,
            Position ,
            DelegationText ,
            DelegationAmount ,
            Active
        from
            workflow.delegation_engine de
    ) de
where
    de.EntityCode = @entity
    and de.ProjectCode = @project_code
    and de.DelegationCode = @delegation_code

My suggestion is to create a "RowID" computed column on the workflow.delegation_engine table.

ALTER TABLE workflow.delegation_engine ADD [RowID] AS
    cast(de.ApprovalOrder + 1 as varchar(4))
    + cast(de.EntityCode as varchar(8))
    + cast(de.DelegationCode as varchar(12))

Your comment indicates that you might be ordering the query on this column.  In that case, you might also want to apply an index on this column.  I haven't tried this out, so I don't know for sure whether an index on this column is allowed, but I think it does satisfy all of the requirements.

Also, you might want/need to pad your values with leading zeros in order to ensure that your calculated RowID is unique.  In that case, you might want to try the following:

    right('0000' + cast(de.ApprovalOrder + 1 as varchar(4)), 4)
    + right('00000000' + cast(de.EntityCode as varchar(8), 8)
    + right('000000000000' + cast(de.DelegationCode as varchar(12), 12)

This would provide uniqueness and would preserve ordering (i.e. ApprovalOrder 10 comes after ApprovalOrder 2).  If you don't care about ordering, then you might not need the leading zeros; you could just insert delimiters to ensure uniqueness.

    cast(de.ApprovalOrder + 1 as varchar(4))
    + '|' + cast(de.EntityCode as varchar(8))
    + '|' + cast(de.DelegationCode as varchar(12))

This would protect against a scenario where one row has ApprovalOrder: 1, EntityCode: 'ABC', DelegationCode: 'DEF' and another row has ApprovalOrder: 1, EntityCode: 'AB', DelegationCode: 'CDEF'.  In that case, the RowID for both rows would be '2ABCDEF'.  Adding the delimiters ensures that the first row would have RowID: '2|ABC|DEF' and the second row would have RowID: '2|AB|CDEF'.

Alternatively, if you can't or don't want to put a "RowID" computed column on the table, then you should be able to just structure the query as shown below.  Note that I've included an "order by" clause that was left out of the original query.  Comments indicate that the reason for the subquery in the original query was to order by the "RowID" column.  The order by 1 clause in the query below accomplishes the same result.

select
    cast(de.ApprovalOrder + 1 as varchar(4))
        + cast(de.EntityCode as varchar(8))
        + cast(de.DelegationCode as varchar(12)) as 'RowID' ,
    cast(de.ApprovalOrder as int) + 1 as 'ApprovalOrder' ,
    de.EntityCode ,
    de.CostCentre ,
    de.DelegationCode ,
    de.ProjectCode ,
    de.RoleGroup ,
    de.Position ,
    de.DelegationText ,
    de.DelegationAmount ,
    de.Active
from
    workflow.delegation_engine de
where
    de.EntityCode = @entity
    and de.ProjectCode = @project_code
    and de.DelegationCode = @delegation_code
order by
    1


Get object in a Set that is an instance of a generically specified type Are there ways to simplify the getLoadComponent(Class<T> type) method? The call LoadComponentFX lcfx = l.getLoadComponent(LoadComponentFX.class); seams a bit clumsy to me.

Here is my code:

public abstract class LoadComponent {}

public class LoadComponentFX extends LoadComponent {}

public class Load {
    Set<LoadComponent> lc;

    public <T extends LoadComponent> T getLoadComponent(Class<T> type) {
        for (final LoadComponent l : lc) {
            if (type.isInstance(l)) {
                return (T) l;
            }
        }
        return null;
    }
}

Test code:

public class LoadTest {
    public static void main(final String[] args) {
        Load l = new PointLoad();

        LoadComponentFX lcfx = l.getLoadComponent(LoadComponentFX.class);
    }
}

As your current code now indirectly forces the set to only contain one of each component, then you could use a Map instead. This would also reduce the need for the loop

public class Load {
    Map<Class<? extends LoadComponent>, LoadComponent> lc;

    public <T extends LoadComponent> T getLoadComponent(Class<T> type) {
        return (T) lc.get(type);
    }
}

Other comments:

Make sure the Map is set to private final
lc is not a good name. There's really no need to save bytes by shortening variable names. A better name would be loadComponents
When adding items to the map, you can use loadComponents.put(obj.getClass(), obj);


Reading two csv files as dictionaries with differing key definitions My script reads two .csv files and generates one dictionary per .csv file.

import csv
# First dictionary
first_dict = {}
with open(first_file, 'r') as f:
    csvReader = csv.reader(f)
    next(csvReader, None) # skip the header
    for row in csvReader:
        key = row[0]
        first_dict[key] = row[1]
# Second dictionary
second_dict = {}
with open(second_file, 'r') as f:
    csvReader = csv.reader(f)
    next(csvReader, None) # skip the header
    for row in csvReader:
        key = " ".join(row[:3]).replace("  "," ")
        second_dict[key] = row[4]

Both reading procedures only differ in the generation of the key. While for first_dictionary the key is just the first row, it is the first three rows for second_dictionary. Is there a way to combine both procedures in one function while only setting appropriate arguments?

Higher order functions

You should define a more general function and then use higher order functions to costumize behaviour:

def csv_dict(filename, key_func, value_func):
    final_dict = {}
    with open(filename, 'r') as f:
        csvReader = csv.reader(f)
        next(csvReader, None) # skip the header
        for row in csvReader:
            key = key_func(row)
            final_dict[key] = value_func(row)
    return final_dict

def dict_one(filename):
    return csv_dict(filename,
                    lambda row: row[0],
                    lambda row: row[1])

def dict_two(filename):
    return csv_dict(filename,
                    lambda row: " ".join(row[:3]).replace("  "," "),
                    lambda row: row[4])

Naming is more important than you think

Names like first_dict = {} and second_dict = {} are ugly and should be avoided even in throw-away code.

Enumerating

You can use enumerate to reduce verbosity:

def csv_dict(filename, key_func, value_func):
    with open(first_file, 'r') as f:
        for row_number, row enumerate(csv.reader(f)):
            if row_number == 0: # Skip header
                continue
            key = key_func(row)
            first_dict[key] = value_func(row)

Only write sensible comments

# Second dictionary gives no information and is just noise.


Representation of the formula P(n) = (n!)(6^n) I'm trying to represent the following mathematical expression in Python:

$$P(n) = (n!)(6^n)$$

The program should compute the answer to expression when n = 156. I have attempted to create the program in python and it produces the correct answer (when compared with wolfram alpha's answer). The answer is approximately \$10^{397}\$.

Is there any way that I could improve the code? (I'm fairly new to programming):

import math
n=156
F = math.factorial(n)
pwr = pow(6,n)
P = F*pwr
print P


Converting a region code (short string up to 4 characters) to a 32-bit integer There is a function that converts region code strings (1 to 4 characters and null terminator) to 32 bit integers codes to be used in maps as keys or values.

Blindly casting char* to int* is bad as it can be less than 4 bytes including null terminator.

Currently the code is like this

uint32_t region_code_key(const char* region_code) {
  unsigned char buf[4] = "\0";
  strncpy(buf, region_code, 4);
  return *((int*)buf);
}

I believe that buf may be not well aligned causing problems on some platforms. Is it a valid concern?
The endianity is not a concern as such numbers are used only on local machines, only as keys.

It's a very simple function but If alignment concern is valid I see two ways to rewrite it.
Here we just convert it byte by byte

uint32_t region_code_key(const char* region_code) {
    unsigned char* region_code_iter;
    unsigned char* region_code_end = region_code+4;
    uint32_t code_as_int = 0;
    for (region_code_iter = region_code; region_code_iter!=region_code_end && (*region_code_iter); ++region_code_iter) {
        code_as_int = (code_as_int<<8) | (*region_code_iter);
    }
    return code_as_int;
}

Alternatively use union to ensure better alignment:

uint32_t region_code_key(const char* region_code) {
union {
                char[sizeof(uint32_t)] as_string;
                uint32_t as_int;
} region = {0, 0, 0, 0};
strncpy(region.as_string, region_code, sizeof (region_code));
return region.as_int;
}

Is alignment a valid concern? If so which alternative seems less ugly to you?

Even if the char array is not aligned, your *((uint32_t *)buf) will be correct: the compiler will ensure the necessary operations are performed.

Note that I used unit32_t: the C standard does not guarantee the size of an int.

One thing: since these are 4 byte integers, you can use an endianness-independent way of doing things by using htonl()/ntohl().


Left hand search in string the requirement for our search query is to look for all search words in the beginning of vehicle manufacturer, model and variant name. Case insensitive. The word being a string of characters separated by space.

E.g. when search for "AU A3 TDI" you would find a vehicle with the following attributes: Vehicle { ManufacturerName = "Audi", ModelName = "A3", Name = "2.0L TDI" }

...but would not return this vehicle:
Vehicle { ManufacturerName = "Renault", ModelName = "A3", Name = "2.0L TDI" } because no words start with au.

I'm using specification with LINQ Expression and the code I wrote works fine and is tested however I believe it smells a bit. It's not very readable IMHO but most importantly, there might be a clear performance improvement you could point out?

public string[] SearchTerms = searchText.Split();

Expression<Func<SearchVehicleVariant, bool>> expression =
c =>
SearchTerms.All(
    s =>
    string.Format(
        " {0} {1} {2}",
        c.ManufacturerName != null ? c.ManufacturerName.ToUpper() : string.Empty,
        c.ModelName != null ? c.ModelName.ToUpper() : string.Empty,
        c.Name != null ? c.Name.ToUpper() : string.Empty).Contains(
            string.Concat(" ", s.Trim().ToUpper())));

Given your requirements, it seems you would be best using String.StartsWith and a StringComparison value which ignores case (i.e., CurrentCultureIgnoreCase, InvariantCultureIgnoreCase, or OrdinalIgnoreCase).  This should be a little cleaner and faster than doing case conversions.

Expression<Func<SearchVehicleVariant, bool>> expression =
   c => SearchTerms.All (
      (c.ManufacturerName ?? string.Empty).StartsWith (s, StringComparison.InvariantCultureIgnoreCase)
      || (c.ModelName ?? string.Empty).StartsWith (s, StringComparison.InvariantCultureIgnoreCase)
      || (c.Name ?? string.Empty).StartsWith (s, StringComparison.InvariantCultureIgnoreCase));


Automatic function call on scope exit I need to add logging functionality for an existing code, based on a result of an operation. I was thinking of creating a class that, when constructed, receives a condition function and a function for execution.  Based on the result of the condition, the code will be executed.

Example:

class auto_logger{

public:
auto_logger(const std::function<bool()>& cond,
            const std::function<void()>& func): _cond(cond), _func(func) {}

virtual ~auto_logger()
{
    try {
        if (_cond()) {
            _func();
        }
    } catch (...) {

    }
}

private:
    std::function<bool()> _cond;
    std::function<void()>  _func;
};

I will use this class like this:

int existing_func()
{
    int res = FAILURE;

    // this is the only additional code
    auto_logger logger([&](){
        return res == SUCCESS;
    },
    [](){
        print_to_log();
    });

    do_some_stuff_that_may_throw();

    res = perform_operation();

    return res;

}

I would be happy to get some comments on this code.  Are there any problem I am not seeing in this solution?  Are there any better solutions?

Echoing the comments from the question, the usual design for these sort of things, often called a scope guard, is to have a function that is called when it no longer needs to be run (frequenlty called dismiss or release.

int existing_func()
{
    int res = FAILURE;

    auto_logger logger([](){
        print_to_log();
    });

    do_some_stuff_that_may_throw();

    res = perform_operation();

    dismiss_logger(logger, res);

    return res;
}

void dismiss_logger(auto_logger& logger, int result) {
    if (res != SUCCESS) {
        logger.dont_log();
    }
}

  virtual ~auto_logger()

Is the expectation that there will be derived classes destroyed via base pointers or via base references? If not, a non-virtual destructor is a common way to signal that a class is not designed to be inherited from.

  } catch (...) {

Note that Visual C++ (at least) can be configured via the /EHa switch (this is usually a misguided configuration, IMHO) to catch structured exceptions (things like access violations/segmentation faults) in a catch (...) handler.

A common technique to hedge against this configuration is to catch std::exception& under the assumption that all sensible exceptions will derive from it. Anything else being caught (e.g, an int, a structured exception) is likely indicative of a bug in the program so egregious that termination is the only safe recourse, as there's likely some corrupt state somewhere that prevents any further cleanup.

This assumption may or may not be valid. Say this code needs to work in an environment where it is normal and okay to throw and catch things that don't derive from std::exception. (E.g., a framework that has its own base exception class is being used.) If Visual C++ isn't being used of /EHa will never be used, this recommendation may come off as paranoid. :-)


Custom C++ exception class with stack trace generation I wanted to implement my own runtime error class in C++, that could provide more meaningful information on where the error occurred than std::runtime_error does.

I decided to use boost::stacktrace to generate a stack trace, appended to the exception message.

Anyway, this is my code:

/**
    \brief Represents a runtime error.

    Equivalent of std::runtime_error, but contains a stacktrace
    generated by Boost.
*/
class Exception : public std::runtime_error
{
    public:
        /**
            \brief Returns error description.

            If the backtrace was generated successfully,
            returns the message along with stack trace.
            Otherwise, behaves like std::runtime_error::what().
        */
        const char *what( ) const noexcept override
        {
            if ( has_backtrace )
                return message.c_str( );
            else
                return std::runtime_error::what( );
        }

        /**
            \brief Constructs an exception, generates a backtrace if possible.

            \param cmessage The error description.
        */
        Exception( const char *cmessage ) :
            std::runtime_error( cmessage ) // std::runtime_error will store the original message
        {
            // Attempt to generate stacktrace
            try
            {
                std::stringstream buffer;
                buffer << cmessage << std::endl << boost::stacktrace::stacktrace( );
                message = buffer.str( );
                has_backtrace = true;
            }
            catch ( std::exception &ex )
            {
                has_backtrace = false;
            }
        }

    protected:
        bool has_backtrace; //!< Determines if backtrace is present
        std::string message; //!< Contains the user message along with backtrace.
};

I can tell it works on this simple example

void foo( )
{
    throw Exception( "some message" );
}

void bar( )
{
    foo( );
}

int main( )
{
    try
    {
        bar( );
    }
    catch ( std::exception &ex )
    {
        std::cerr << ex.what( );
    }

    return 0;
}

because it generates following message:

some message
 0# Exception::Exception(char const*) in ./ex
 1# foo() in ./ex
 2# bar() in ./ex
 3# main in ./ex
 4# __libc_start_main in /lib/x86_64-linux-gnu/libc.so.6
 5# _start in ./ex

However, what I'd like to know is if my code isn't too complicated
as for an exception class and if it properly handles possible stack trace
generator exceptions and properly falls back to std::runtime_error functionality.

Also, is there some important property/method that all exception classes should have, that I had overlooked and forgot to implement? Maybe the whole idea of having such class is bad in general and I should use some other solution?

Other suggestions are obviously welcome too.

Exception( const char *cmessage ) :

I strongly recommend making this constructor explicit, so that you don't permit the user to accidentally write

void some_function(const Exception&);
...
some_function("hello world");

My impression is that most C++ experts recommend explicit on one-argument constructors; I personally hold the minority opinion that explicit should be present on all constructors by default (i.e., if you don't have a specific immediate need for implicit conversion, you should just put explicit automatically, and sort out the consequences later if necessary).

catch ( std::exception &ex )

My current employer's codebase actually does catch by non-const reference, but if you're starting from scratch, I strongly recommend catching by const reference by default. Accidentally mutating the current exception object can cause race conditions.

Also, in the Exception constructor, your catch (std::exception&) should almost certainly be catch (...), right?

As for the high-level point of what you're doing, I believe I have an outline of this sort of thing under "Mix-Ins" somewhere near the end of Template Normal Programming. (Sorry, I'm rushed right now, but I can come back and give you a real link later.) (LATER: I elided that part of the talk, but the two slides on mixins are visible very briefly here.)

The first improvement is to make your thing a template inheriting from T instead of from std::runtime_error specifically. Second, I'd make a function my::throw_with_stacktrace(T&& ex) that simply does throw Exception<std::remove_reference_t<T>>(std::forward<T>(ex));.

Gotta run, but I hope this helps a bit.


Group Anagrams Together approach in Java Given an array of words, print the count of all anagrams together in
  sorted order (increasing order of counts). For example, if the given
  array is {“cat”, “dog”, “tac”, “god”, “act”}, then grouped anagrams
  are “(dog, god) (cat, tac, act)”. So the output will be 2 3.

  Input:

  First line consists of T test case. First line of every test case
  consists of N, denoting the number of words in array. Second line of
  every test case consists of words of array.

  Output:

  Single line output, print the counts of anagrams in increasing
  order.

  Constraints:

  1<=T<=100 1<=N<=50

  Example:

    Input:

    2

    5

    act
    cat tac god dog

    3 act cat tac

    Output:

    2 3

    3

My approach:

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.util.HashMap;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Collections;
import java.lang.StringBuffer;

class GFG {

    private static void getAnagramCt (String[] words) {
        HashMap <String, Integer> anag = new HashMap<>();
        List<Integer> counts = new ArrayList<> ();
        Set<String> keys;
        String[] keyArr;

        anag.put(words[0],0);

        keys = anag.keySet();
        keyArr = keys.toArray(new String[keys.size()]);

        for (int i = 1; i < words.length; i++) {
            String elem = words[i];
            for (int j = 0; j < keyArr.length; j++) {
                if (isAnagram(elem,keyArr[j])) {
                        int ct = anag.get(keyArr[j]);
                        anag.put(keyArr[j],ct+1);
                }
                else {
                    if (j == keyArr.length - 1) {
                        anag.put(elem, 0);
                    }
                    else {
                        continue;
                    }
                }
            }
        keys = anag.keySet();
        keyArr = keys.toArray(new String[keys.size()]);
        }

        for (Map.Entry<String,Integer> entry : anag.entrySet()) {
            //System.out.println(entry.getKey() + " " + entry.getValue());
            counts.add(entry.getValue() + 1);
        }
        Collections.sort(counts);

        for (Integer elem : counts) {
            System.out.print(elem + " ");
        }
        System.out.println();
    }

    private static boolean isAnagram (String word2, String word1) {
        if (word1.length() != word2.length()) {
            return false;
        }

        StringBuffer word = new StringBuffer(word2);
        for (int i = 0; i < word1.length(); i++) {
            if (word.length() == 0) {
                return false;
            }
            else if (word.indexOf((String.valueOf(word1.charAt(i)))) == -1) {
                return false;
            }
            else {
                int ind = word.indexOf((String.valueOf(word1.charAt(i))));
                word.deleteCharAt(ind);
            }
        }

        return true;
    }

    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int numTests = sc.nextInt();

        for (int i = 0; i < numTests; i++) {
            int numWords = sc.nextInt();
            String[] words = new String[numWords];

            for (int j = 0; j < numWords; j++) {
                words[j] = sc.next();
            }
            getAnagramCt(words);
        }
    }
}

I have the following questions with regards to the above code:

How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?

Reference

for (int i = 0; i < word1.length(); i++) {

Since you never use i except to calculate word1.charAt(i), you could more easily do

        for (char current : word1.toCharArray()) {

Then you could replace word1.charAt(i) with current.

But as noted in a comment, it would actually be more efficient to use a different algorithm.  The issue is that indexOf is \$\mathcal{O}(n)\$ and of course the for loop is \$\mathcal{O}(n)\$.  Nested, they become \$\mathcal{O}(n^2)\$.  Worse, isAnagram is itself inside nested for loops.  So the overall approach is \$\mathcal{O}(m^2n^2)\$, where \$m\$ is the number of words and \$n\$ is the maximum length of each word.

If you instead normalize each string by sorting it (\$\mathcal{O}(n\log n)\$), you can then put the normalized strings in a HashMap of ArrayList (\$\mathcal{O}(1)\$ each or \$\mathcal{O}(m)\$ total).  This is only \$\mathcal{O}(m\cdot n\log{n})\$, which is much better.

Or skip the ArrayList and just use a counter.  The overall algorithm would look something like

    public static Map<String, Integer> countAnagrams(String[] words) {
        Map<String, Integer> anagramCounts = new HashMap<>();

        for (String word : words) {
            String sorted = sort(word);

            Integer count = anagramCounts.get(sorted);
            if (count == null) {
                count = 0;
            }

            anagramCounts.put(sorted, count + 1);
        }

        return anagramCounts;
    }

This expects the caller to handle the output, which is better practice (Single Responsibility Principle, as applied to methods; see also SOLID, Separation of concerns, and Don't Repeat Yourself).

The basic idea here is that the method should either generate data or display it.  That way, if you want to reuse the data generation for something else, you can.

In the original, you generate the data and then display it in the same method.  If you wanted to do something else with the data, you'd have to refactor.  This is more flexible and easier to test with automation.

Consider

public static void displayAnagramCounts(String[] words) {
    Map<String, List<String>> groups = groupAnagrams(words);
    List<Integer> counts = countValues(groups);
    Collections.sort(counts);
    displayNumbers(counts);
}

Now countValues and displayNumbers can be written in generic ways.  The former takes a Map of List and flattens it into a List of the sizes of the List elements.  The latter displays a list of numbers with spaces between them.  Both those methods can be reused and tested separately.

        for (Map.Entry<String,Integer> entry : anag.entrySet()) {
            //System.out.println(entry.getKey() + " " + entry.getValue());
            counts.add(entry.getValue() + 1);
        }

There is an argument that you shouldn't include commented out code in a code review.  Commented out code is code not ready for source control (it should either be deleted or commented in).

You don't actually need an entrySet here, as values is enough.  E.g.

        for (int value : anag.values()) {
            counts.add(value + 1);
        }

With my alternative algorithm, you wouldn't even have to add one here.


Lua program to clean up phone numbers How idiomatic is my code? Since Lua does not have classical inheritance such as in OO languages. Feedback on the test and implementation are both appreciated/welcomed.

The rules are:

If the phone number is less than 10 digits assume that it is bad number
If the phone number is 10 digits assume that it is good
If the phone number is 11 digits and the first number is 1, trim the 1 and use the first 10 digits
If the phone number is 11 digits and the first number is not 1, then it is a bad number
If the phone number is more than 11 digits assume that it is a bad number

local PhoneNumber = {}

function PhoneNumber:new(no_as_string)
  self.__index = self
  local n = "0000000000"
  n = no_as_string:gsub("[^0-9]", "")
  if (n:len() == 11 and n:sub(1, 1) == "1") then
    n = n:sub(2, 11)
  else
    if (n:len() > 10 or n:len() < 10) then
      n = "0000000000"
    end
  end
  return setmetatable({ number = n }, self)
end

function PhoneNumber:areaCode(symbol)
  return self.number:sub(1, 3)
end

function PhoneNumber:toString(symbol)
  return "("..self.number:sub(1, 3)..") "..self.number:sub(4, 6).."-"..self.number:sub(7, 10)
end

return PhoneNumber

Here is the test:

local PhoneNumber = require('phone-number')

describe("PhoneNumber()", function()
  it("cleans the number (123) 456-7890", function()
    local phone = PhoneNumber:new("(123) 456-7890")
    assert.are.equals(phone.number,"1234567890")
  end)

  it("cleans numbers with dots", function()
    local phone = PhoneNumber:new("123.456.7890")
    assert.are.equals(phone.number,"1234567890")
  end)

  it("valid when 11 digits and first digit is 1", function()
    local phone = PhoneNumber:new("11234567890")
    assert.are.equals(phone.number,"1234567890")
  end)

  it("invalid when 11 digits", function()
    local phone = PhoneNumber:new("21234567890")
    assert.are.equals(phone.number,"0000000000")
  end)

  it("invalid when 9 digits", function()
    local phone = PhoneNumber:new("123456789")
    assert.are.equals(phone.number,"0000000000")
  end)

  it("has an area code", function()
    local phone = PhoneNumber:new("1234567890")
    assert.are.equals(phone:areaCode(),"123")
  end)

  it("formats a number", function()
    local phone = PhoneNumber:new("1234567890")
    assert.are.equals(phone:toString(),"(123) 456-7890")
  end)
end)

You've a lot of unnecessary code. First off, as janos stated:

local n = "0000000000"
n = no_as_string:gsub("[^0-9]", "")

  The initialization of n is pointless here.

You can instead use just the lua pattern to match your input to desired result:

function PhoneNumber:new( Number )
    local n = string.gsub( Number, "%D", "" )
    n = n:match "^1?(%d%d%d%d%d%d%d%d%d%d)$" or "0000000000"
    return setmetatable({ number = n, __index = self }, self)
end

Notice that I've changed the input argument to Number and later use string.gsub( Number.... This way; you've the advantage of inputting direct numbers and provide flexibility.

The pattern

"^1?(%d%d%d%d%d%d%d%d%d%d)$"

is self-explanatory. In lua, if string.match failed to find any matched group; it returns nil. I've used this property to check for bad numbers.

Next thing I'd suggest that you do is store the number as an integer instead of string:

return setmetatable({ number = tonumber(n), __index = self }, self)

This is just because integers take less memory than strings. For retrieving area code etc., use mathematical operations:

function PhoneNumber:areaCode()  -- what was symbol parameter for?
    return math.floor( self.number / 10^7 )
end

Lastly, lua provides a meta-method: __tostring for conversion to strings from other types. Use it (It is the reason why I was able to use string.gsub above):

function PhoneNumber:__tostring()
    local f, n = math.floor, self.number
    local sFormat, iPart1, iPart2 = "(%d) %d-%d", f( n / 10^7 ), f( n / 10^3 % 10^4 )
    return sFormat:format( self:areaCode(), iPart1, iPart2 )
end

Now, instead of calling PhoneObject:toString(), you can do:

tostring( PhoneObject )


Get missing letters - TopCoder challenge I'm working on a TopCoder problem which seeks to find the letters preventing an input sentence from being a pangram in all caps, alphabetical order.

MissingLetters.h

#ifndef _MISSING_LETTERS_H_
#define _MISSING_LETTERS_H_

#include <string>
#include <set>
#include <utility>

class MissingLetters {
  public:
    MissingLetters() {}
    std::string getMissingLetters(std::string sentence);
};

// Find the difference between two sets, set(lowercase(sentence)) & set([a-z])

std::string MissingLetters::getMissingLetters(std::string sentence) {
   std::set<char> sentence_set;
   std::string missing_letters = "";

   // Put each letter in the sentence into a set, O(n log n)
   for(size_t i = 0; i < sentence.size(); ++i) {
      sentence_set.insert(toupper(sentence[i]));
   }

   // For each letter [A-Z], add letters that aren't in the set, O(1)
   for(char letter='A'; letter <= 'Z'; ++letter) {

      if(sentence_set.find(letter) == sentence_set.end()) {
         missing_letters+=letter;
      }
   }

   return missing_letters;
}

#endif // _MISSING_LETTERS_H_

I'd like this to be as fast as possible. My method, getMissingLetters is currently \$O(n \log{n})\$ running-time, where \$n\$ is the length of the the sentence.

Any other implementations, including different data structures, would be great if they're faster.

Any tips?

Since the size of the alphabet is fixed, you don't need a set, a boolean array will be enough:

Initialize a boolean array, with size of the alphabet, all values false
For each letter in the input string, set the flag to true for index letter - 'A'
After the entire input string is processed, iterate over the boolean array, if the value is false for an index, then append the character index + 'A' to the list of missing letters

The time complexity of this alternative algorithm is \$O(n)\$ where \$n\$ is the size of the input string, space complexity is \$O(1)\$, for the size of the alphabet.


LSH hashcode generator function For building an LSH based system in Python, I need to have a very fast calculation of the hashcode.

I won't need to explain here the LSH algorithm itself, but I need help in improving performance of the generate-Hash-Code operation:

Given a big number of features n (example: 5000 or even 50000):

multiply a dense matrix (13xn) with a sparse vector (nx1)
in the resulting vector (13x1) change to 1 if positive and 0 otherwise
generate a binary number out of the result

I tried various approaches and I put here two implementation generateCode1 and generateCode2 but both are still too heavy.

generateCode1 takes 56 seconds for 100 call (avg: 0.56 s)
generateCode2 takes 20 seconds for 100 call (avg: 0.20 s)

I am sure it is possible to do it faster but not sure how.
For you to be able to play with it, i am write a full working sample program:

import time
import numpy as np
from scipy import sparse
from scipy import stats

def randomMatrix(rows, cols, density):
    rvs = stats.norm(loc=0).rvs  # scale=2,
    M = sparse.random(rows, cols, format='lil', density=density, data_rvs=rvs)
    return M

def generateCode1(matrix, vector):
    nonzeros = np.nonzero(vector)
    temp_hashcode = []

    for i in range(matrix.shape[0]):
        d = 0
        for j in nonzeros[1]:
            d += matrix[i, j] * vector[0, j]

        temp_hashcode.append('1' if d > 0 else '0')

    return ''.join(temp_hashcode)

def generateCode2(matrix, vector):
    m = matrix * vector.T
    m [m > 0] = 1
    m [m < 0] = 0
    txt = ''.join(m.A.ravel().astype('U1'))
    return txt

features = 50000
test_count = 100

matrix = randomMatrix(13, features, 1.0)
vector = randomMatrix(1, features, 0.01)
vector = abs(vector)

methods = [ generateCode1, generateCode2 ]

for func in methods:
    print ('run {0} times of method {1}:'.format( test_count, func ) )
    time1 = time.time()
    for i in range(test_count):
        code1 = func(matrix, vector)
    time1 = time.time() - time1

    print ('\tcode: {0} - run time: '.format(code1), end="" )
    print ('{0}(s) == {1}(m) [ avergae {2}(s) ]'.format(time1, time1/60, time1/test_count) )

Note: Please don't go to parallelism and multi processing, that won't fit in my overall application (unfortunately).

There are two things I don't understand about the code in the post.

Are you really committed to using LIL (list-of-lists) format? The documentation is very clear that LIL is not suitable for computing matrix products, for example here:

  To perform manipulations such as multiplication or inversion, first convert the matrix to either CSC or CSR format.

and here:

  Disadvantages of the LIL format [...] slow matrix vector products (consider CSR or CSC).

I find that using CSR instead of LIL for matrix and vector gives an immediate 20× speedup.

Even if you have a good reason for using the LIL format in some parts of your code, you should still convert to CSR before computing the product, as suggested in the documentation.
Given that matrix is dense, why does the code represent it using a sparse matrix? This is bound to incur some overhead that could be avoided by using an ordinary np.matrix.

I find that switching matrix from CSR to np.matrix gives a further 1.5× speedup.


Checking for a win in TicTacToe It looks like it should be shortened but I can't see how.

I have my methods <= 5 lines but that's as far as I got:

def check_lines
  if horizontal?(@player) || vertical?(@player) || diagonal?(@player)
    @win=@player
  end
end

def horizontal?(player)
  ((@squares[0] == player) && (@squares[1] == player) && (@squares[2] == player)) ||
  ((@squares[3] == player) && (@squares[4] == player) && (@squares[5] == player)) ||
  ((@squares[6] == player) && (@squares[7] == player) && (@squares[8] == player))
end

def vertical?(player)
  ((@squares[0] == player) && (@squares[3] == player) && (@squares[6] == player)) ||
  ((@squares[1] == player) && (@squares[4] == player) && (@squares[7] == player)) ||
  ((@squares[2] == player) && (@squares[5] == player) && (@squares[8] == player))
end

def diagonal?(player)
  ((@squares[0] == player) && (@squares[4] == player) && (@squares[8] == player)) ||
  ((@squares[2] == player) && (@squares[4] == player) && (@squares[6] == player))
end

When all of your code is the same, just with different numbers, you want to use data-directed programming.

WINS = [
  [0, 1, 2], [3, 4, 5], [6, 7, 8],  # <-- Horizontal wins
  [0, 3, 6], [1, 4, 7], [2, 5, 8],  # <-- Vertical wins
  [0, 4, 8], [2, 4, 6],             # <-- Diagonal wins
]

def check_lines
  if WINS.any? { |line| line.all? { |square| @squares[square] == @player } }
    @win = @player
  end
end


Find numbers between 1 and 10000 whose sum of digits are prime I have the following C code that finds numbers between 1 and 10000 whose sum of digits are prime and save then to a file.

#include<stdio.h>
#include<conio.h>
int sum_of_digits(int);
int check_prime(int);
void save_to_file(int);

int main()
{
    int i, num, isPrime;
    for(i=2; i<=10000; i++)
    {
        num = sum_of_digits(i);
        isPrime = check_prime(num);
        if(isPrime)
        {
            printf("%d ", i);
            save_to_file(i);
        }
    }
    getch();
    return 0;
}

int sum_of_digits(int num)
{
    int sum = 0;
    while (num != 0)
    {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int check_prime(int num)
{
    int i;
    for (i=2; i<=num-1; i++)
    {
        if (num%i == 0)
            return 0;
    }
    if (i == num)
        return 1;
}

void save_to_file(int num)
{
    FILE *fp;
    fp=fopen("prime.txt","a+");
    fprintf(fp, "%d ", num);
    fclose(fp);
}

The sum of the digits is such a small number (9+9+9+9=36 the maximum in your case) that you can even hard-code the values which are prime or not:

//number:         1  2  3  4  5  6  7
char isPrime[] = {0, 1, 1, 0, 1, 0, 1, ...}

But lets assume you don't go that far. The next best thing would be to generate such an array at run-time before your main loop (also based on the fact that the largest number you need to check if it's a prime is very small). A popular method for doing this is the Sieve of Eratosthenes.

Thus, you can now look up if the sum of the various digits is a prime or not in constant time:

if (isPrime[sum_of_digits(i)])
{
    //...
}

As to writing the results to a file, I would keep the file open for the duration of the loop. This improves efficiency by sending bigger chunks of data to the disk thanks to buffering.


Dijkstra's algorithm is slow. (For loops) I tried to add Dijkstra's algorithm to a js game. First when I got it working it was very very Laggy (5-10 fps) and the browser would crash.. After adding a lot more improvements I got it to like 50-60 fps with 200 tiles (see GRID_SPREADING in script bellow). When I turn off this algorithm I have 120-144 fps, but I am trying to at least get 60+ fps while using 800-1000 tiles (see GRID_SPREADING in script below, I want max to be at least 800). I am not that good at coding yet so I would really be thankfull if you can help me achieve this goal... (here is the video I followed to create this: https://www.youtube.com/watch?v=0faPPgOT--E&t=934s, though, he was doing it in scratch).
Here is the laggy part:
var GRID_SPREADING = {
    dist: 80,
    b_col: 100,
    max: 400,
    show: false
}

// the main player will look and move to the direction of the nearest tile (not the direction to the nearest tile, but the dir property of the nearest tile)
const pathfindLoop = async () => { // pgrids is an object of arrays that holds all dijkstra algorithm's tiles
    if(!doPathfind || !nearestEnemy || dist4(nearestEnemy[1], nearestEnemy[2], enemyMovedPath[0], enemyMovedPath[1]) < 10) {
        await sleep(10);
        pathfindLoop();
        return;
    }
    if(Object.keys(pgrids).length > GRID_SPREADING.max){
        enemyMovedPath[0] = nearestEnemy[1];
        enemyMovedPath[1] = nearestEnemy[2];
        realPgrids = pgrids;
        pgrids = {};
    } else {

        let makeFirstP = true;
        for(let mfp in pgrids) {

            if(dist4(pgrids[mfp].x, pgrids[mfp].y, nearestEnemy[1], nearestEnemy[2]) < 50); {
                makeFirstP = false;
            }
        }
        if(makeFirstP) {
            createPathObj(nearestEnemy[1], nearestEnemy[2], 90);
        }
        for(let o in pgrids) {
            if(!(pgrids[o].checked)) {
                for(let i = 0; i < 4; i++) {
                    if(i == 3) {
                        pgrids[o].checked = true;
                    }
                    let res1 = locwxda(pgrids[o].x, pgrids[o].y, i*90, -GRID_SPREADING.dist);
                    let res = {x: res1.x, y: res1.y};
                    let go = true;

                    for(pgrid in pgrids) {
                        if(dist4(res.x, res.y, pgrids[pgrid].x, pgrids[pgrid].y) < GRID_SPREADING.dist/2.5) {
                            go = false;
                            break;
                        }
                    }
                    if(go) {

                        for(build in builds) { // builds is a large object of arrays: 50-300 properties, but removing this for loop doesn't improve much at all
                            if(dist4(builds[build][1], builds[build][2], res.x, res.y) < GRID_SPREADING.b_col) {
                                go = false;
                                break;
                            }
                        }

                    }

                    if(go) {
                        createPathObj(res.x, res.y, i*90) // a simple short function, adds an array property to object pgrids
                    }
                }
            }
        }
    }

        await sleep(10);
        pathfindLoop();
    }
    pathfindLoop();

I've done many research but I can't find the solution to solve this lag. Is there a completely different and better way to do this?

As most of the detail needed to workout what is going on, is missing, (See my comment on question) one can only review what one can see.
Your request to resolve laggy code is impossible to address without makes a lot of guesses.
Bugs.
There is no path through the function pathfindLoop that does not call its self. This will cause you problems, however your intent is unclear and the exact nature of the problem depends on your intent.
Unclear awaiting
When you call sleep you await it.
However the recursive call pathfindLoop() is not awaited. It is completely unclear if this is an error only your part (a bug) or deliberate (a problem).
Oh... the infinity of it all
Your function will crash the page as your code does not allow the call stack to pop calls when exiting pathfindLoop
To call pathfindLoop means an infinite list of calls to self.
Guessing your intention one could see this as a way of creating an ongoing polling like system (similar to setInterval or an animation loop using requestAnimationFrame). Wait 10 (what ever's) then process data and repeat.
If this is your intention it is very flawed as you fail to take into account the call stack.
Each call to pathfindLoop adds a new context to the call stack. Each promise creates a new entry on the promise stack.
As the function is async the context can not be removed from the stack until the context of async calls it has made, are resolved. This will never happen and eventually calling pathfindLoop will crash the page, well before that the page will become very unresponsive (laggy).
Maybe this is the lag you mention in your question. Though without further details one can only guess.
General points
Further points noticed when reviewing the code.

Poor naming.

JS convention is not to use snake_case for variable names. It is generally only used in js when defining names in UPPERCASE_SNAKE

Inconsistent use of semicolons.

Odd placement of semicolon. You have a semicolon at the end of an if clause. eg if (foo); {... the semi colon is ignored, but one is left to wonder as to your intent here?

Too heavily reliant on higher scope. Particularly because you mutate pgrids, and realPgrids. This may or may not be bad but again without further information one can only guess.

Unclear use of higher scoped or undefined variables. Is the variable build defined??? Will adding "use strict" to your code cause it to crash??

Unsafe use of for...in loops. In modern JS there really is no reason to use for...in  loops. Rather use for...of  loop
Example of using for of rather than for in. From your code...

for (build in builds) {
    if (dist4(builds[build][1], builds[build][2], res.x, res.y) < GRID_SPREADING.b_col) {
        go = false;
        break;
    }
 }

Assuming builds is an object
  for (const build of Object.values(builds)) {
      if (dist4(build[1], build[2], res.x, res.y) < GRID_SPREADING.b_col) {
          go = false;
          break;
      }
  }

Or assuming builds is an array
  for (const build of builds) {
      if (dist4(build[1], build[2], res.x, res.y) < GRID_SPREADING.b_col) {
          go = false;
          break;
      }
  }

  // OR

  go = builds.every(build => dist4(build[1], build[2], res.x, res.y) >= GRID_SPREADING.b_col);

ref to Array.every

Rewrite??
I can not fully rewrite your code as I can not code unknown details.
The rewrite will address the call stack problem and assumes pathfindLoop to be akin to a polling function.
"use strict"; // Always use this directive.

const pathfindLoop = () => { // do not use async here
    // ... the rest of your code here

    setTimeout(pathfindLoop, 10); // assumes 10 from sleep(10); is ms
}

Refs

strict_mode
setTimeout