Find signal's maximum peak in window I have a 9-dimensional signal (as a csv from this Gist) that looks like this:

A signal peaks every 30 steps. I want to get the maximum values of the peaks in that 30 second window. Here's what I've hacked together so far, where sig is the signal loaded from the csv file and max_res is the desired result:

trial_num = 8
dims = 9
step = 30
max_res = np.zeros(trial_num)

tmp = sig.reshape((trial_num, step, dims))
max_dim = np.argmax(np.sum(tmp, axis=1), axis=1)

sing_dim = np.zeros((trial_num, step))
for t_i in range(trial_num):
    sing_dim[t_i] = tmp[t_i, :, max_dim[t_i]]

max_res = np.max(sing_dim, axis=1)

How can I replace the for-loop with a vectorized operation?

Instead of getting the positions of the maximum value and then retrieving the values thanks to the positions, you can directly ask numpy to retrieve the maximum values:

tmp = sig.reshape((trial_num, step, dims))
max_res = np.max(np.max(tmp, axis=1), axis=1)

I suggest you, however, to use a function to encapsulate this behaviour. It could take the amount of steps per cycle as a parameter and compute the rest from there:

def max_peak_values(data, steps_per_cycle=30):
    length, dims = data.shape
    trials = length // steps_per_cycle
    new_shape = trials, steps_per_cycle, dims

    return np.max(np.max(data.reshape(new_shape), axis=1), axis=1)

and use it like:

max_res = max_peak_values(sig, 30)


Check deep object property and find duplicate value I use the following code to find if there is duplicate value in property path:

return new Promise((resolve, reject) => {
            var data = [];
            Parser.parse()
             //configObj is the value from the screen shot
                .then((configObj) => {
                    configObj.forEach((providers) => {
                        _.each(providers, (provider) => {
                            _.each(provider, (entry) => {
                                for (var prop in entry) {
                                    if (_inArray(entry[prop].path, data)) {
                                        return reject(new Error(`Duplicate path ${entry[prop].path}`));
                                    }
                                    data.push(entry[prop].path);
                                }
                            })
                        })
                    })
                    resolve("validObject");
                }, err => {
                    reject(err);
                });

For example, this is the object configObj and as you can see I need to find duplicate in object 'replace' and object 'save' for the value in field 'path'; if they have the same value, it rejects with error; otherwise it resolves the promise. Is there is more elegant way to write it?

In this example, the path is different (test2 & command1) but it can also be the same.

update

[
  {
    "providers": [
      {
        "replace": {
          "path": "command1",
          "function": "updateResources",
          "method": "post"
        },
        "save": {
          "path": "test2",
          "function": "updateResources",
          "method": "post"
        }
      }
    ]
  }
]

A very fun question, which took way too much time to analyze ;) It would have helped tremendously if you could have given a sample JSON instead of a screenshot.

Regardless, if you are using lodash anyway, you might as well leverage it all the way. By trying the different functions provided by lodash you start thinking differently about data structures.

The code I proposes flattens the array you are getting so that you just have a list of entries. Then it gets the properties from the entries, which it flattens again to have a nice searchable array. Then it counts the paths and checks for dupes, then it checks whether any dupe was found.

Instead of having the full Promise code, I will provide the essence:

var configObj = [{
  "providers": [{
    "replace": {
      "path": "command1",
      "function": "updateResources",
      "method": "post"
    },
    "save": {
      "path": "test2",
      "function": "updateResources",
      "method": "post"
    }
  }]
}];

var providers = _.values(configObj);
var entries = _.flatMapDeep(providers, _.values);
var props = _.flatMapDeep(entries, _.values);
var counts = _.countBy(props, 'path');
var dupe = _.findKey(counts, count => {
  return count > 1;
});
console.log(dupe ? dupe : 'No dupe found');
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.14.1/lodash.min.js"></script>

The nice thing about this approach is that if you wanted to change the functionality and log all the dupes at once, you could.


Update Immutable Map How's the following function to update an immutable Map's values?

scala> def updateMap[A](map: Map[A, Set[A]], item: A, toAdd: A) = {
    map.map(x => if(x._1 == item) (x._1, (x._2 + toAdd)) else (x._1, x._2))
}

scala> val map = Map(1 -> Set(2), 3 -> Set(4))

scala> updateMap(map, 1, 5)
res1 ...= Map(1 -> Set(2, 5), 3 -> Set(4))

You iterate through the whole Map, which is O(n) and therefore slow as hell. Worse, you even recreate every element and put it into another element, which is even slower.

Why not just do:

scala> val map = Map(1 -> Set(5,3), 2 -> Set(7,3))
map: scala.collection.immutable.Map[Int,scala.collection.immutable.Set[Int]] = Map(1 -> Set(5, 3), 2 -> Set(7, 3))

scala> def updateMap[A, B](map: Map[A, Set[B]], key: A, value: B) =
         map + ((key, map.getOrElse(key, Set()) + value))
updateMap: [A, B](map: Map[A,Set[B]], key: A, value: B)scala.collection.immutable.Map[A,Set[B]]

scala> updateMap(map, 1, 9)
res0: scala.collection.immutable.Map[Int,Set[Int]] = Map(1 -> Set(5, 3, 9), 2 -> Set(7, 3))

And you probably want to introduce another type parameter B to the signature of updateMap to allow values of a different type than the one of the key.


Word Ladder JavaScript Implementation For a big dictionary, the following code gives a time limit error. I was trying to use ES6 constructs in the code. The inputs that gave TLE are here.

I have tried to use BFS for the problem, adding words in the Q only if it has not been visited and it exists in the dictionary.

function getShortestPathBetweenWords(st, end, dict) {
  if (st === end) {
    return 1;
  }
  if (st.length < end.length) {
    return 0;
  }
  let q = [];
  let isVisited = new Map();
  q.push(st);
  let level = 0;
  while (q.length!== 0) {

    level++;
    let size = q.length;
    for (let i = 0; i < size; i++) {
      let newWord = q.shift();
      if (newWord === end) {
        return level;
      }
      let listOfWords = _generateNewWords(newWord, dict);

      for (let i = 0; i < listOfWords.length; i++) {
        if (isVisited.get(listOfWords[i]) !== true) {
          q.push(listOfWords[i]);
          isVisited.set(listOfWords[i], true);
        }
      }

    }

  }
  return 0;
}
/**
 * to generate new words from given Words
 */
function _generateNewWords(word, dict) {
  let len = word.length;
  let listOfWords = [];
  let alphabhets = 'abcdefghijklmnopqrstuvwxyz'.split('');
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < 26; j++) {
      let charArray = word.split('');
      charArray[i] = alphabhets[j];
      if (checkinDictionary(charArray.join(""), dict) === true) {
        listOfWords.push(charArray.join(""));
      }
    }
  }
  return listOfWords;
}
/**
 * checkinDictionary
 */
function checkinDictionary(str, dict) {
  for (let i = 0; i < dict.length; i++) {
    if (dict[i] == str) {

      return true;
    }
  }
  return false;
}

Naming

I suggest renaming getShortestPathBetweenWords() to  findShortestLadderDistance() for the following reasons:

get is recommended as a prefix for simple lookup functions. Use another verb such as compute or find for meatier, computationally heavier functions.
You are actually computing the distance of the shortest path, not the path itself. And a ladder is a more specific word for path whose neighboring words differ by exactly one substitution.

Further naming suggestions:

Rename _generateNewWords() to generateNeighbors()
Rename level to distance
Rename st to start
Rename newWord to next
Rename q to queue
Rename listOfWords to neighbors
Rename charArray to chars

Style

Instead of while (queue.length !== 0) I suggest the more self-documenting while (queue.length > 0) as the length can never be negative.

Also, don't needlessly mix "" vs. '' for strings.

Specification

Right now you are returning a distance of 0 when there is no path and a distance of 1 if start equals end. I suggest following the common definition of path length and return Infinity and 0 instead.

You might also want to pass the alphabet as a parameter instead of having a hard-coded 'magic' constant in your _generateNewWords() function. It can easily be computed from your dictionary as alphabet = [...new Set(dict.join(""))].

Also, you currently allow any word for start while end must be part of the dictionary. I recommend allowing non-dictionary words in both cases for consistency.

Performance

Your main performance bottleneck is the checkinDictionary() function. If you keep track of a set of open words which you haven't visited yet, you can replace that function call with a simple open.has(word). Set lookup time is constant and thus much faster than iterating the whole dict array.

You then have to pass the open set to generateNeighbors(). The isVisited map is no longer needed.

Another performance drain is performing string splitting via let charArray = word.split('') in the inner loop of _generateNewWords. You can push that to the outer loop.

Also, you currently treat start.length < end.length as a special 'shortcut' case. You could generalize this to start.length != end.length.

Sample code

Applying all those modifications to your code yields:

function findShortestLadderDistance(start, end, alphabet, dict) {
  if (start === end) return 0;
  if (start.length != end.length) return Infinity;

  let queue = [start];
  let distance = 1;
  let open = new Set(dict);
  open.delete(start);
  open.add(end);

  while (queue.length > 0) {
    for (let i = 0, length = queue.length; i < length; i++) {
      let next = queue.shift();

      for (let neighbor of generateNeighbors(next, alphabet, open)) {
        if (neighbor === end) return distance;

        queue.push(neighbor);
        open.delete(neighbor);
      }
    }
    distance++;
  }
  return Infinity;
}

function* generateNeighbors(word, alphabet, open) {
  let chars = word.split("");

  for (let i = 0; i < chars.length; i++) {
    let char = chars[i];

    for (let j = 0; j < alphabet.length; j++) {
      chars[i] = alphabet[j];
      neighbor = chars.join("");
      if (open.has(neighbor)) yield neighbor;
    }
    chars[i] = char;
  }
}

let start = "sand";
let end = "acne";
let dict = ["slit","bunk","wars","ping","viva","wynn","wows","irks","gang","pool","mock","fort","heel","send","ship","cols","alec","foal","nabs","gaze","giza","mays","dogs","karo","cums","jedi","webb","lend","mire","jose","catt","grow","toss","magi","leis","bead","kara","hoof","than","ires","baas","vein","kari","riga","oars","gags","thug","yawn","wive","view","germ","flab","july","tuck","rory","bean","feed","rhee","jeez","gobs","lath","desk","yoko","cute","zeus","thus","dims","link","dirt","mara","disc","limy","lewd","maud","duly","elsa","hart","rays","rues","camp","lack","okra","tome","math","plug","monk","orly","friz","hogs","yoda","poop","tick","plod","cloy","pees","imps","lead","pope","mall","frey","been","plea","poll","male","teak","soho","glob","bell","mary","hail","scan","yips","like","mull","kory","odor","byte","kaye","word","honk","asks","slid","hopi","toke","gore","flew","tins","mown","oise","hall","vega","sing","fool","boat","bobs","lain","soft","hard","rots","sees","apex","chan","told","woos","unit","scow","gilt","beef","jars","tyre","imus","neon","soap","dabs","rein","ovid","hose","husk","loll","asia","cope","tail","hazy","clad","lash","sags","moll","eddy","fuel","lift","flog","land","sigh","saks","sail","hook","visa","tier","maws","roeg","gila","eyes","noah","hypo","tore","eggs","rove","chap","room","wait","lurk","race","host","dada","lola","gabs","sobs","joel","keck","axed","mead","gust","laid","ends","oort","nose","peer","kept","abet","iran","mick","dead","hags","tens","gown","sick","odis","miro","bill","fawn","sumo","kilt","huge","ores","oran","flag","tost","seth","sift","poet","reds","pips","cape","togo","wale","limn","toll","ploy","inns","snag","hoes","jerk","flux","fido","zane","arab","gamy","raze","lank","hurt","rail","hind","hoot","dogy","away","pest","hoed","pose","lose","pole","alva","dino","kind","clan","dips","soup","veto","edna","damp","gush","amen","wits","pubs","fuzz","cash","pine","trod","gunk","nude","lost","rite","cory","walt","mica","cart","avow","wind","book","leon","life","bang","draw","leek","skis","dram","ripe","mine","urea","tiff","over","gale","weir","defy","norm","tull","whiz","gill","ward","crag","when","mill","firs","sans","flue","reid","ekes","jain","mutt","hems","laps","piss","pall","rowe","prey","cull","knew","size","wets","hurl","wont","suva","girt","prys","prow","warn","naps","gong","thru","livy","boar","sade","amok","vice","slat","emir","jade","karl","loyd","cerf","bess","loss","rums","lats","bode","subs","muss","maim","kits","thin","york","punt","gays","alpo","aids","drag","eras","mats","pyre","clot","step","oath","lout","wary","carp","hums","tang","pout","whip","fled","omar","such","kano","jake","stan","loop","fuss","mini","byrd","exit","fizz","lire","emil","prop","noes","awed","gift","soli","sale","gage","orin","slur","limp","saar","arks","mast","gnat","port","into","geed","pave","awls","cent","cunt","full","dint","hank","mate","coin","tars","scud","veer","coax","bops","uris","loom","shod","crib","lids","drys","fish","edit","dick","erna","else","hahs","alga","moho","wire","fora","tums","ruth","bets","duns","mold","mush","swop","ruby","bolt","nave","kite","ahem","brad","tern","nips","whew","bait","ooze","gino","yuck","drum","shoe","lobe","dusk","cult","paws","anew","dado","nook","half","lams","rich","cato","java","kemp","vain","fees","sham","auks","gish","fire","elam","salt","sour","loth","whit","yogi","shes","scam","yous","lucy","inez","geld","whig","thee","kelp","loaf","harm","tomb","ever","airs","page","laud","stun","paid","goop","cobs","judy","grab","doha","crew","item","fogs","tong","blip","vest","bran","wend","bawl","feel","jets","mixt","tell","dire","devi","milo","deng","yews","weak","mark","doug","fare","rigs","poke","hies","sian","suez","quip","kens","lass","zips","elva","brat","cosy","teri","hull","spun","russ","pupa","weed","pulp","main","grim","hone","cord","barf","olav","gaps","rote","wilt","lars","roll","balm","jana","give","eire","faun","suck","kegs","nita","weer","tush","spry","loge","nays","heir","dope","roar","peep","nags","ates","bane","seas","sign","fred","they","lien","kiev","fops","said","lawn","lind","miff","mass","trig","sins","furl","ruin","sent","cray","maya","clog","puns","silk","axis","grog","jots","dyer","mope","rand","vend","keen","chou","dose","rain","eats","sped","maui","evan","time","todd","skit","lief","sops","outs","moot","faze","biro","gook","fill","oval","skew","veil","born","slob","hyde","twin","eloy","beat","ergs","sure","kobe","eggo","hens","jive","flax","mons","dunk","yest","begs","dial","lodz","burp","pile","much","dock","rene","sago","racy","have","yalu","glow","move","peps","hods","kins","salk","hand","cons","dare","myra","sega","type","mari","pelt","hula","gulf","jugs","flay","fest","spat","toms","zeno","taps","deny","swag","afro","baud","jabs","smut","egos","lara","toes","song","fray","luis","brut","olen","mere","ruff","slum","glad","buds","silt","rued","gelt","hive","teem","ides","sink","ands","wisp","omen","lyre","yuks","curb","loam","darn","liar","pugs","pane","carl","sang","scar","zeds","claw","berg","hits","mile","lite","khan","erik","slug","loon","dena","ruse","talk","tusk","gaol","tads","beds","sock","howe","gave","snob","ahab","part","meir","jell","stir","tels","spit","hash","omit","jinx","lyra","puck","laue","beep","eros","owed","cede","brew","slue","mitt","jest","lynx","wads","gena","dank","volt","gray","pony","veld","bask","fens","argo","work","taxi","afar","boon","lube","pass","lazy","mist","blot","mach","poky","rams","sits","rend","dome","pray","duck","hers","lure","keep","gory","chat","runt","jams","lays","posy","bats","hoff","rock","keri","raul","yves","lama","ramp","vote","jody","pock","gist","sass","iago","coos","rank","lowe","vows","koch","taco","jinn","juno","rape","band","aces","goal","huck","lila","tuft","swan","blab","leda","gems","hide","tack","porn","scum","frat","plum","duds","shad","arms","pare","chin","gain","knee","foot","line","dove","vera","jays","fund","reno","skid","boys","corn","gwyn","sash","weld","ruiz","dior","jess","leaf","pars","cote","zing","scat","nice","dart","only","owls","hike","trey","whys","ding","klan","ross","barb","ants","lean","dopy","hock","tour","grip","aldo","whim","prom","rear","dins","duff","dell","loch","lava","sung","yank","thar","curl","venn","blow","pomp","heat","trap","dali","nets","seen","gash","twig","dads","emmy","rhea","navy","haws","mite","bows","alas","ives","play","soon","doll","chum","ajar","foam","call","puke","kris","wily","came","ales","reef","raid","diet","prod","prut","loot","soar","coed","celt","seam","dray","lump","jags","nods","sole","kink","peso","howl","cost","tsar","uric","sore","woes","sewn","sake","cask","caps","burl","tame","bulk","neva","from","meet","webs","spar","fuck","buoy","wept","west","dual","pica","sold","seed","gads","riff","neck","deed","rudy","drop","vale","flit","romp","peak","jape","jews","fain","dens","hugo","elba","mink","town","clam","feud","fern","dung","newt","mime","deem","inti","gigs","sosa","lope","lard","cara","smug","lego","flex","doth","paar","moon","wren","tale","kant","eels","muck","toga","zens","lops","duet","coil","gall","teal","glib","muir","ails","boer","them","rake","conn","neat","frog","trip","coma","must","mono","lira","craw","sled","wear","toby","reel","hips","nate","pump","mont","died","moss","lair","jibe","oils","pied","hobs","cads","haze","muse","cogs","figs","cues","roes","whet","boru","cozy","amos","tans","news","hake","cots","boas","tutu","wavy","pipe","typo","albs","boom","dyke","wail","woke","ware","rita","fail","slab","owes","jane","rack","hell","lags","mend","mask","hume","wane","acne","team","holy","runs","exes","dole","trim","zola","trek","puma","wacs","veep","yaps","sums","lush","tubs","most","witt","bong","rule","hear","awry","sots","nils","bash","gasp","inch","pens","fies","juts","pate","vine","zulu","this","bare","veal","josh","reek","ours","cowl","club","farm","teat","coat","dish","fore","weft","exam","vlad","floe","beak","lane","ella","warp","goth","ming","pits","rent","tito","wish","amps","says","hawk","ways","punk","nark","cagy","east","paul","bose","solo","teed","text","hews","snip","lips","emit","orgy","icon","tuna","soul","kurd","clod","calk","aunt","bake","copy","acid","duse","kiln","spec","fans","bani","irma","pads","batu","logo","pack","oder","atop","funk","gide","bede","bibs","taut","guns","dana","puff","lyme","flat","lake","june","sets","gull","hops","earn","clip","fell","kama","seal","diaz","cite","chew","cuba","bury","yard","bank","byes","apia","cree","nosh","judo","walk","tape","taro","boot","cods","lade","cong","deft","slim","jeri","rile","park","aeon","fact","slow","goff","cane","earp","tart","does","acts","hope","cant","buts","shin","dude","ergo","mode","gene","lept","chen","beta","eden","pang","saab","fang","whir","cove","perk","fads","rugs","herb","putt","nous","vane","corm","stay","bids","vela","roof","isms","sics","gone","swum","wiry","cram","rink","pert","heap","sikh","dais","cell","peel","nuke","buss","rasp","none","slut","bent","dams","serb","dork","bays","kale","cora","wake","welt","rind","trot","sloe","pity","rout","eves","fats","furs","pogo","beth","hued","edam","iamb","glee","lute","keel","airy","easy","tire","rube","bogy","sine","chop","rood","elbe","mike","garb","jill","gaul","chit","dons","bars","ride","beck","toad","make","head","suds","pike","snot","swat","peed","same","gaza","lent","gait","gael","elks","hang","nerf","rosy","shut","glop","pain","dion","deaf","hero","doer","wost","wage","wash","pats","narc","ions","dice","quay","vied","eons","case","pour","urns","reva","rags","aden","bone","rang","aura","iraq","toot","rome","hals","megs","pond","john","yeps","pawl","warm","bird","tint","jowl","gibe","come","hold","pail","wipe","bike","rips","eery","kent","hims","inks","fink","mott","ices","macy","serf","keys","tarp","cops","sods","feet","tear","benz","buys","colo","boil","sews","enos","watt","pull","brag","cork","save","mint","feat","jamb","rubs","roxy","toys","nosy","yowl","tamp","lobs","foul","doom","sown","pigs","hemp","fame","boor","cube","tops","loco","lads","eyre","alta","aged","flop","pram","lesa","sawn","plow","aral","load","lied","pled","boob","bert","rows","zits","rick","hint","dido","fist","marc","wuss","node","smog","nora","shim","glut","bale","perl","what","tort","meek","brie","bind","cake","psst","dour","jove","tree","chip","stud","thou","mobs","sows","opts","diva","perm","wise","cuds","sols","alan","mild","pure","gail","wins","offs","nile","yelp","minn","tors","tran","homy","sadr","erse","nero","scab","finn","mich","turd","then","poem","noun","oxus","brow","door","saws","eben","wart","wand","rosa","left","lina","cabs","rapt","olin","suet","kalb","mans","dawn","riel","temp","chug","peal","drew","null","hath","many","took","fond","gate","sate","leak","zany","vans","mart","hess","home","long","dirk","bile","lace","moog","axes","zone","fork","duct","rico","rife","deep","tiny","hugh","bilk","waft","swig","pans","with","kern","busy","film","lulu","king","lord","veda","tray","legs","soot","ells","wasp","hunt","earl","ouch","diem","yell","pegs","blvd","polk","soda","zorn","liza","slop","week","kill","rusk","eric","sump","haul","rims","crop","blob","face","bins","read","care","pele","ritz","beau","golf","drip","dike","stab","jibs","hove","junk","hoax","tats","fief","quad","peat","ream","hats","root","flak","grit","clap","pugh","bosh","lock","mute","crow","iced","lisa","bela","fems","oxes","vies","gybe","huff","bull","cuss","sunk","pups","fobs","turf","sect","atom","debt","sane","writ","anon","mayo","aria","seer","thor","brim","gawk","jack","jazz","menu","yolk","surf","libs","lets","bans","toil","open","aced","poor","mess","wham","fran","gina","dote","love","mood","pale","reps","ines","shot","alar","twit","site","dill","yoga","sear","vamp","abel","lieu","cuff","orbs","rose","tank","gape","guam","adar","vole","your","dean","dear","hebe","crab","hump","mole","vase","rode","dash","sera","balk","lela","inca","gaea","bush","loud","pies","aide","blew","mien","side","kerr","ring","tess","prep","rant","lugs","hobo","joke","odds","yule","aida","true","pone","lode","nona","weep","coda","elmo","skim","wink","bras","pier","bung","pets","tabs","ryan","jock","body","sofa","joey","zion","mace","kick","vile","leno","bali","fart","that","redo","ills","jogs","pent","drub","slaw","tide","lena","seep","gyps","wave","amid","fear","ties","flan","wimp","kali","shun","crap","sage","rune","logs","cain","digs","abut","obit","paps","rids","fair","hack","huns","road","caws","curt","jute","fisk","fowl","duty","holt","miss","rude","vito","baal","ural","mann","mind","belt","clem","last","musk","roam","abed","days","bore","fuze","fall","pict","dump","dies","fiat","vent","pork","eyed","docs","rive","spas","rope","ariz","tout","game","jump","blur","anti","lisp","turn","sand","food","moos","hoop","saul","arch","fury","rise","diss","hubs","burs","grid","ilks","suns","flea","soil","lung","want","nola","fins","thud","kidd","juan","heps","nape","rash","burt","bump","tots","brit","mums","bole","shah","tees","skip","limb","umps","ache","arcs","raft","halo","luce","bahs","leta","conk","duos","siva","went","peek","sulk","reap","free","dubs","lang","toto","hasp","ball","rats","nair","myst","wang","snug","nash","laos","ante","opal","tina","pore","bite","haas","myth","yugo","foci","dent","bade","pear","mods","auto","shop","etch","lyly","curs","aron","slew","tyro","sack","wade","clio","gyro","butt","icky","char","itch","halt","gals","yang","tend","pact","bees","suit","puny","hows","nina","brno","oops","lick","sons","kilo","bust","nome","mona","dull","join","hour","papa","stag","bern","wove","lull","slip","laze","roil","alto","bath","buck","alma","anus","evil","dumb","oreo","rare","near","cure","isis","hill","kyle","pace","comb","nits","flip","clop","mort","thea","wall","kiel","judd","coop","dave","very","amie","blah","flub","talc","bold","fogy","idea","prof","horn","shoo","aped","pins","helm","wees","beer","womb","clue","alba","aloe","fine","bard","limo","shaw","pint","swim","dust","indy","hale","cats","troy","wens","luke","vern","deli","both","brig","daub","sara","sued","bier","noel","olga","dupe","look","pisa","knox","murk","dame","matt","gold","jame","toge","luck","peck","tass","calf","pill","wore","wadi","thur","parr","maul","tzar","ones","lees","dark","fake","bast","zoom","here","moro","wine","bums","cows","jean","palm","fume","plop","help","tuba","leap","cans","back","avid","lice","lust","polo","dory","stew","kate","rama","coke","bled","mugs","ajax","arts","drug","pena","cody","hole","sean","deck","guts","kong","bate","pitt","como","lyle","siam","rook","baby","jigs","bret","bark","lori","reba","sups","made","buzz","gnaw","alps","clay","post","viol","dina","card","lana","doff","yups","tons","live","kids","pair","yawl","name","oven","sirs","gyms","prig","down","leos","noon","nibs","cook","safe","cobb","raja","awes","sari","nerd","fold","lots","pete","deal","bias","zeal","girl","rage","cool","gout","whey","soak","thaw","bear","wing","nagy","well","oink","sven","kurt","etna","held","wood","high","feta","twee","ford","cave","knot","tory","ibis","yaks","vets","foxy","sank","cone","pius","tall","seem","wool","flap","gird","lore","coot","mewl","sere","real","puts","sell","nuts","foil","lilt","saga","heft","dyed","goat","spew","daze","frye","adds","glen","tojo","pixy","gobi","stop","tile","hiss","shed","hahn","baku","ahas","sill","swap","also","carr","manx","lime","debs","moat","eked","bola","pods","coon","lacy","tube","minx","buff","pres","clew","gaff","flee","burn","whom","cola","fret","purl","wick","wigs","donn","guys","toni","oxen","wite","vial","spam","huts","vats","lima","core","eula","thad","peon","erie","oats","boyd","cued","olaf","tams","secs","urey","wile","penn","bred","rill","vary","sues","mail","feds","aves","code","beam","reed","neil","hark","pols","gris","gods","mesa","test","coup","heed","dora","hied","tune","doze","pews","oaks","bloc","tips","maid","goof","four","woof","silo","bray","zest","kiss","yong","file","hilt","iris","tuns","lily","ears","pant","jury","taft","data","gild","pick","kook","colt","bohr","anal","asps","babe","bach","mash","biko","bowl","huey","jilt","goes","guff","bend","nike","tami","gosh","tike","gees","urge","path","bony","jude","lynn","lois","teas","dunn","elul","bonn","moms","bugs","slay","yeah","loan","hulk","lows","damn","nell","jung","avis","mane","waco","loin","knob","tyke","anna","hire","luau","tidy","nuns","pots","quid","exec","hans","hera","hush","shag","scot","moan","wald","ursa","lorn","hunk","loft","yore","alum","mows","slog","emma","spud","rice","worn","erma","need","bags","lark","kirk","pooh","dyes","area","dime","luvs","foch","refs","cast","alit","tugs","even","role","toed","caph","nigh","sony","bide","robs","folk","daft","past","blue","flaw","sana","fits","barr","riot","dots","lamp","cock","fibs","harp","tent","hate","mali","togs","gear","tues","bass","pros","numb","emus","hare","fate","wife","mean","pink","dune","ares","dine","oily","tony","czar","spay","push","glum","till","moth","glue","dive","scad","pops","woks","andy","leah","cusp","hair","alex","vibe","bulb","boll","firm","joys","tara","cole","levy","owen","chow","rump","jail","lapp","beet","slap","kith","more","maps","bond","hick","opus","rust","wist","shat","phil","snow","lott","lora","cary","mote","rift","oust","klee","goad","pith","heep","lupe","ivan","mimi","bald","fuse","cuts","lens","leer","eyry","know","razz","tare","pals","geek","greg","teen","clef","wags","weal","each","haft","nova","waif","rate","katy","yale","dale","leas","axum","quiz","pawn","fend","capt","laws","city","chad","coal","nail","zaps","sort","loci","less","spur","note","foes","fags","gulp","snap","bogs","wrap","dane","melt","ease","felt","shea","calm","star","swam","aery","year","plan","odin","curd","mira","mops","shit","davy","apes","inky","hues","lome","bits","vila","show","best","mice","gins","next","roan","ymir","mars","oman","wild","heal","plus","erin","rave","robe","fast","hutu","aver","jodi","alms","yams","zero","revs","wean","chic","self","jeep","jobs","waxy","duel","seek","spot","raps","pimp","adan","slam","tool","morn","futz","ewes","errs","knit","rung","kans","muff","huhs","tows","lest","meal","azov","gnus","agar","sips","sway","otis","tone","tate","epic","trio","tics","fade","lear","owns","robt","weds","five","lyon","terr","arno","mama","grey","disk","sept","sire","bart","saps","whoa","turk","stow","pyle","joni","zinc","negs","task","leif","ribs","malt","nine","bunt","grin","dona","nope","hams","some","molt","smit","sacs","joan","slav","lady","base","heck","list","take","herd","will","nubs","burg","hugs","peru","coif","zoos","nick","idol","levi","grub","roth","adam","elma","tags","tote","yaws","cali","mete","lula","cubs","prim","luna","jolt","span","pita","dodo","puss","deer","term","dolt","goon","gary","yarn","aims","just","rena","tine","cyst","meld","loki","wong","were","hung","maze","arid","cars","wolf","marx","faye","eave","raga","flow","neal","lone","anne","cage","tied","tilt","soto","opel","date","buns","dorm","kane","akin","ewer","drab","thai","jeer","grad","berm","rods","saki","grus","vast","late","lint","mule","risk","labs","snit","gala","find","spin","ired","slot","oafs","lies","mews","wino","milk","bout","onus","tram","jaws","peas","cleo","seat","gums","cold","vang","dewy","hood","rush","mack","yuan","odes","boos","jami","mare","plot","swab","borg","hays","form","mesh","mani","fife","good","gram","lion","myna","moor","skin","posh","burr","rime","done","ruts","pays","stem","ting","arty","slag","iron","ayes","stub","oral","gets","chid","yens","snub","ages","wide","bail","verb","lamb","bomb","army","yoke","gels","tits","bork","mils","nary","barn","hype","odom","avon","hewn","rios","cams","tact","boss","oleo","duke","eris","gwen","elms","deon","sims","quit","nest","font","dues","yeas","zeta","bevy","gent","torn","cups","worm","baum","axon","purr","vise","grew","govs","meat","chef","rest","lame"];
let alphabet = [...new Set(dict.join(""))];
console.log(findShortestLadderDistance(start, end, alphabet, dict));


Program looks for correct balance of ( [ and { in expression I'm still new to programming. (First exposure was school about a year ago), and for some reason this problem really gave me a lot of problems trying to solve it. Can you help me understand what I could have done different/better here?

import java.util.*;
public class Lab10 {
    public static void main(String[] args) throws Exception {
        Stack<String> stack = new Stack<>();

        Scanner input = new Scanner(System.in);
        System.out.print("Enter string: ");
        String s = input.nextLine();
        input.close();
        StringTokenizer tokens = new StringTokenizer(s, "[] () {}", true);

        while (tokens.hasMoreTokens()) {
            String token = tokens.nextToken().trim();
            //Push opening delimeter to stack
            if (token.compareTo("(") == 0 || token.compareTo("{") == 0 ||
                    token.compareTo("[") == 0) {
                stack.push(token);
            }

            //when closing delimiter is encountered pop the stack
            else if (token.compareTo(")") == 0 || token.compareTo("}") == 0  ||
                    token.compareTo("]") == 0) {
                String popped = stack.pop();
                //make sure that there is a corresponding closing delimiter   for every opening
                if (!stack.isEmpty());
                if (token.compareTo(")") == 0 && popped.compareTo("(") != 0 ||
                    token.compareTo("}") == 0 && popped.compareTo("{") != 0 ||
                    token.compareTo("]") == 0 && popped.compareTo("[") != 0)   {
                    System.out.println("Incorrect grouping pairs.");
                    break;
                }
                //if stack is empty that means every thing was correct
                else if (stack.isEmpty()){
                    System.out.println("Correct grouping pairs.");
                }

            }
        }
    }
}

if (!stack.isEmpty());

This statement does absolutely nothing. You should remove it.

else if (stack.isEmpty()){
    System.out.println("Correct grouping pairs.");
}

Just because you removed the last pair does not mean you're done. Take, for instance, this line of code:

int x = getArray(getArrayID())[[0];

Your program first says Correct grouping pairs, before complaining about the "[[ ]" not being correctly balanced.

Next, your program is hardcoded to check for (), {} and []. But what if we wanted to add <>? Then you'd have a problem, because you'd need to change the code in a lot of places.

My first thought of a solution for this is to use two strings, and then using indexOf to see if our token is in the string. It's not the best solution, I think, but it would work pretty well:

String leftHandTokens = "[{(<";
String rightHandTokens = "]})>";

Then use like so:

if(leftHandTokens.contains(token)){
   //lefthand token
} else if(rightHandTokens.contains(token)){
   //righthand token
}

Next, finding out whether the two tokens are a correct pair:

if(leftHandTokens.indexOf(popped) == rightHandTokens.indexOf(token)){

Naturally this assumes that either of them is IN the token list in the first place. Else it will say (-1 == -1) = true.

You could simplify your code a lot like that:

String leftHandTokens = "[{(<";
String rightHandTokens = "]})>";

while (tokens.hasMoreTokens()) {
    String token = tokens.nextToken().trim();
    //Push opening delimeter to stack
    if (leftHandTokens.contains(token)) {
        stack.push(token);
    } else if (rightHandTokens.contains(token)) {
        String popped = stack.pop();
        //make sure that there is a corresponding closing delimiter   for every opening
        if (leftHandTokens.indexOf(popped) != rightHandTokens.indexOf(token))   {
            System.out.println("Incorrect grouping pairs.");
            break;
        } else if (stack.isEmpty()){
            System.out.println("Correct grouping pairs.");
        }
    }
}

I removed some of your comments, because splitting up if-elseif branches with comments makes it VERY hard to understand. You'd think that if you see a statement like this

if(condition){
    doSomething();
}

//if there was no condition, we gotta handle the thingmabob...

You'd say that the if statement is just that. But then what you do...

else {
   handleThingmabob();
}

Is throw some else at the bottom! That's scary! I'd have to read to the next statement to be sure whether there isn't anything else coming! Worst, with comments in there, the distance between if and else might be huge! If you've got something to say, say it before you start your if-statement.

But we're not entirely done.

You currently handle outputting whether everything was correct inside your loop.

That's a bad idea.

What you'd want to do is wrap the whole thing in a function, and the moment you find a problem, you'd return false. And when you're out of tokens, you check whether the stack is empty. That way your program will run faster for faulty inputs and will be able to determine cases where you provide blah( as a string to be faulty.


Find all the numbers within a range whose digits add up to a certain target In an interview I was asked the following problem:

  Given a range of numbers (0 - 100) or (0 - 1000), find all the numbers whose digit add up to 5.

I started off with a brute force way to iterate over all the numbers and filter out numbers whose digits do not add up to 5. The numbers remaining will be the answer.

It seems like that wasn't the desired solution. After thinking about the problem a little bit I realized another approach would be to use recursion to generate all the numbers until a particular "digit-size".

For example, if we are asked to generate all the numbers that between 0 and 100 that add up to 5, we can generate all numbers from 'digit-size=1' to 'digit-size=3' that add up to 5.

It will be great if this approach could be reviewed.

    public class FindAllNumbersWithCertainDigitSum {
       public List<Integer> getAllNumbersThatSumToTarget(int digitSize, int target) {
          List<Integer> candidates = new ArrayList<>();
          int accumulatedSum = 0;
          helper(digitSize, target, candidates, accumulatedSum);
          return candidates;
     }

     private void helper(int digitSize, int target, List<Integer> candidates, int accumulatedSum) {
         //Base case: No more digits to consider and nothing else to add
         if(digitSize == 0 && target == 0) {
             candidates.add(accumulatedSum);
         }
       //There is nothing else to add but there are more digits to consider that will be multiples of 10
       else if(digitSize != 0 && target == 0) {
             helper(digitSize - 1, target, candidates, accumulatedSum * 10);
         }
      //The digits did not add up to the target, return without doing anything
      else if(digitSize == 0 && target != 0) {
             return;
         } else {
            //Iterate from target down to zero and recursively get the remaining digits if the first digit is the target.
             for(int current = target; current >= 0; current--) {
                 helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
             }
         }

      }

     public static void main(String[] args) {
        FindAllNumbersWithCertainDigitSum s = new FindAllNumbersWithCertainDigitSum();
        //Get all numbers from 0 - 999(maxDigitSize == 3) that add up to 5
        s.getAllNumbersThatSumToTarget(3, 5)
         .stream()
         .forEach(System.out::println);
      }
}

Just a idea...

There are 7 sets of digits that can constuct numbers that add up to 5.

a = [1, 1, 1, 1, 1]
b = [2, 1, 1, 1]
c = [2, 2, 1]
d = [3, 1, 1]
e = [3, 2]
f = [4, 1]
g = [5]

Then:
let r be the sets in (a...g) that has size < log(max)

Pad each set in r with zeroes so that all set sizes are log(max)

The answer is permutations of the sets that are in the range min - max.


on using the strategy pattern to switch between database layers I'd like to build an app in Flask that can switch between talking to a PostGresql and a Mongo DB.  As I understand it, the Strategy Pattern is about being able to switch algorithms that are referred to by some method call on the fly.  So, I think this pattern would be relevant because I want to switch out what abstract functions like create, read, update, delete do.  It sounds to me like strategy would be relevant here, but I'm not quite sure how to implement it.  Here's what I'm thinking:
I have this file to handle my routes:
from flask import Blueprint
from .models import Entity
api = Blueprint('api', __name__, url_prefix='/api')
from .models.EntityWrapper import Entity

@api.route('/entities', methods=['POST'])
def create_entity():
    entity = EntityWrapper(label="cheese")
    entity.save()
    return jsonify(entity)

@api.route('/entities')
def get_entities():
    entities = Entity.read()
    return jsonify(entities)

The save and read methods should do different things, depending on which database is being used.  The class they belong to, EntityWrapper, reads the environment variables and selects which kind of Entity class should be exported:
import os
from .Entity_mongo import Entity as MongoEntity
from .Entity_postgres import Entity as PostgresEntity
from dotenv import load_dotenv, find_dotenv

load_dotenv(find_dotenv())
DB_TYPE = os.environ.get("DB_TYPE")

Entity = None

if DB_TYPE == 'mongo':
    Entity = MongoEntity
elif DB_TYPE == 'postgres':
    Entity = PostgresEntity
else:
    raise Exception("'DB_TYPE' improperly defined in .env")

Here's Entity_posgres.py
from .Model_postgres import PostgresModel

class Entity(db.Model):
    __tablename__ = 'entities'
    id = db.Column(db.Integer, primary_key=True)
    label = db.Column(db.String(), nullable=False)

Since there are a number of methods that should all be handled "the postgres way" for any object, I'm bundling these into a class called PostgresModel. (A mimilar class would be defined for Mongo, doing this "the mongo way", but for sake of brevity I'll only show postgres).
# from .ModelABC import ModelABC
from ..extensions import postgres_db as db

# class PostgresModel(ModelABC, db.Model):
class PostgresModel(db.Model):
    def create(self, instance):
        # do some postgres create stuff
        db.session.add(instance)
        db.session.save()
    def read(self, cls):
        # do some postgres read stuff
        cls.query.all()
    def update():
        # do some postgres update stuff
        pass
    def delete():
        # do some postgres delete stuff
        pass

I can think of one way the stategy pattern might fit in here: PostgresModel could inherit from some ModelABC class, which would keep track of which strategy is currently being used to create, read, update, or delete.  It seems to be this class would look something like the following.  To tell the truth, I'm not even sure what advantages it could bring, but here's what it might look like:
from abc import ABC, abstractmethod

class ModelABC(ABC):

    def assign_strategy(self, strategy_key):
        pass

    def use_strategy(self, strategy, *args, **kwargs):
        if strategy == 'create':
            self.create_strategy(*args, **kwargs)
        elif strategy == 'read':
            self.read_strategy(*args, **kwargs)
        elif strategy == 'update':
            self.update_strategy(*args, **kwargs)
        elif strategy == 'delete':
            self.delete_strategy(*args, **kwargs)
        else:
            raise Exception('strategy name invalid')

    @abstractmethod
    def create_strategy(self):
        pass

    @abstractmethod
    def read_strategy(self):
        pass

    @abstractmethod
    def update_strategy(self):
        pass

    @abstractmethod
    def delete_strategy(self):
        pass

Am I on the right track with this strategy pattern, or is this not the right use case?

Typically you'd have two classes that implement the four methods create, read, update and delete, one for Mongo and one for PostGres. Create a factory method that determines what kind of DB you are talking to, and returns an instance of the appropriate class.
The rest of your code can interact with the class using the methods. It doesn't need to know what kind of DB you are using.


Minimalist countdown timer with C# I'm looking to add a module to one of my utility classes that functions as a countdown timer for tools that execute tasks after a certain amount of time. The code below is what I have working for PoC, but when I went to make this and check out existing examples, none really seemed this slim/simple without going all-out on lambdas, so I'm worried that I'm doing something wrong, or at the very least very inefficiently.

The time-range expected for the tool will be from 200 milliseconds to a few hours.

using System;

namespace CountdownTimer
{
    class Program
    {
        static int Main(string[] args)
        {
            int aDelay = 2000;
            CountDown(aDelay);
            return 0;
        }

        static void CountDown(int delayInMilliseconds)
        {
            bool finishedCountdown = false;
            DateTime initialTime = DateTime.UtcNow;

            while (!finishedCountdown)
            {
                DateTime timeNow = DateTime.UtcNow;
                TimeSpan timeDifference = timeNow - initialTime;

                if (timeDifference.TotalMilliseconds >= delayInMilliseconds)
                {
                    finishedCountdown = true;
                }
            }
        }
    }
}

I also have this alternative when I was futzing around with async, which I'm kind of new to in C#

using System;
using System.IO;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace CountdownTimer
{
    class Program
    {
        static int Main(string[] args)
        {
            var result = CountDownTimer(5000);
            Console.ReadKey(true);

            return 0;
        }

        async static Task CountDownTimer(int delay)
        {
            Task myDelay = AsyncDelay(delay);
            await myDelay;
        }

        async static Task AsyncDelay(int delay)
        {
            await Task.Delay(TimeSpan.FromMilliseconds(delay));
            Console.WriteLine("Done");
        }
    }
}

I think they're both pretty easy to understand, but my uncertainty with C#'s async for the second solution and the CPU cycles being used for the first worry me...

side note: Any version of .NET is available for use

Without more context it's really hard to give you a particularly helpful answer but I can suggest a couple of things.

Your first option is about as bad as it gets, it will thrash CPU because as far as the CPU is concerned that while loop is important work - it doesn't know you're just calculating a time over and over again.

Your second option isn't bad but you should accept an action to run after the delay otherwise it won't be very flexible. You should also use TimeSpan to represent an interval - an int can mean many things, a TimeSpan represents the information unambiguously.

For the sake of completeness, for this trivial example I think it's clearer without the async and await but that's just personal preference.

public static Task DoActionAfter(TimeSpan delay, Action action)
{
    return Task.Delay(delay).ContinueWith(_ => action());
}

As you're returning a Task your code can synchronously wait using .Wait() (not great) or await the result. If it doesn't need the result straight away it can just store the task and check its status later.

If you want to be able to cancel your action you should feed a CancellationToken into the method (and the delay).

Update

To actually use the method:

using System;
using System.Threading.Tasks;

namespace CountdownTimer
{
    class Program
    {
        public static void Main()
        {
            var delayInterval = TimeSpan.FromMilliseconds(5000);
            var runningTask = DoActionAfter(
                delayInterval,
                () => Console.WriteLine("Done"));

            // if you want your main method to wait for the action
            // runningTask.Wait()

            Console.ReadKey();
        }

        public static Task DoActionAfter(TimeSpan delay, Action action)
        {
            return Task.Delay(delay).ContinueWith(_ => action());
        }
    }
}


How to manipulate directories using Python I'm using the following lump of code to manage a 9.4gb dataset.  I had to divide the dataset into multiple github repositories to be able to do this. I've explained what each block of code does.

git_repo_tags = ['AB', 'C', 'DEF', 'G', 'HILMNO', 'PR', 'STW', 'X']
counter = 1

# Cloning the github repositories
print('Beginning cloning...')
for repo in git_repo_tags:
  git.Git('.').clone('git://github.com/utility-repos/' + repo)
  print('-\nCloning ' + repo)

  #Removing the .git folder from each repo
  shutil.rmtree(repo + '/.git')
  print('--Removing the .git folder ' + str(counter) + '/8')
  counter += 1

# Creating the Food-101/images directory and subdirectory if it doesn't already exist
if not os.path.exists('Food-101/images'):
    os.makedirs('Food-101/images')
    print('Created the Food-101/images')

    # Going through the repo X and moving everything a branch up
    for i in os.listdir('X'):
      shutil.move(os.path.join('X', i), 'Food-101')
      print('Moved important files to an upper branch')

    # Going through the other repos and moving everything to Food-101/images
    for directory in git_repo_tags:
      for subdirectory in os.listdir(directory):
        shutil.move(os.path.join(directory, subdirectory), 'Food-101/images')
        print('Moving ' + subdirectory + ' to Food-101/images')

#After the above code is complete, moves all test images to the Food-101/test folder and renames them
print('\n-Beginning to separate the test dataset...')
if not os.path.exists('Food-101/test'):
    os.makedirs('Food-101/test')

with open('Food-101/meta/test.txt') as test_file:
  for line in test_file:
    name_of_folder = line.split('/')[0]
    name_of_file = line.split('/')[1].rstrip()
    Path('Food-101/images/' + name_of_folder + '/' + name_of_file + '.jpg').rename('Food-101/test/' + name_of_folder + '_' + name_of_file + '.jpg')
    print('--Moved Food-101/images/' + name_of_folder + '/' + name_of_file + '.jpg to Food-101/test/')

# Moves all training images to the Food-101/images directory and renames them
print('\n-Beginning to separate the training dataset...')
with open('Food-101/meta/train.txt') as train_file:

  for line in train_file:
    name_of_folder = line.split('/')[0]
    name_of_file = line.split('/')[1].rstrip()
    Path('Food-101/images/' + name_of_folder + '/' + name_of_file + '.jpg').rename('Food-101/images/' + name_of_folder + '_' + name_of_file + '.jpg')
    print('--Moved Food-101/images/' + name_of_folder + '/' + name_of_file + '.jpg to Food-101/train/')

# Removes empty directories inside Food-101/images
with open('Food-101/meta/train.txt') as train_file:
  for folder in train_file:
    name_of_folder = folder.split('/')[0]
    if os.path.exists('Food-101/images/' + name_of_folder):
      shutil.rmtree('Food-101/images/' + name_of_folder)

# Removes empty directories
for dirs in git_repo_tags:
  shutil.rmtree(dirs)

This code works but its a mess and I have too many repeats.  What is a good way to clean this up?

Enumerate

counter = 1
for repo in git_repo_tags:
  # ...
  print('--Removing the .git folder ' + str(counter) + '/8')
  counter += 1

should be using enumerate:

for counter, repo in enumerate(git_repo_tags, start=1):

String interpolation

print('--Removing the .git folder ' + str(counter) + '/8')

can be

print(f'--Removing the .git folder {counter}/{len(git_repo_tags)}')

The 8 should not be hard-coded.

Pathlib

For basically every one of your directory and file names, and many of your file operations (rmtree being an exception), you should consider using pathlib.Path. For instance, this:

if not os.path.exists('Food-101/images'):
    os.makedirs('Food-101/images')
    print('Created the Food-101/images')

can be

image_path = Path('Food-101/images')
if not image_path.exists():
    image_path.mkdir(parents=True)
    print(f'Created {image_path}')

Path parsing

Rather than this:

name_of_folder = line.split('/')[0]
name_of_file = line.split('/')[1].rstrip()

consider at least unpacking it, i.e.

folder_name, file_name = line.rsplit('/', 1)

But it's better to again use pathlib:

line_path = Path(line)
folder_name = line_path.parent
file_name = line_path.name

Functions

Move logically-related chunks of code to subroutines for better legibility, maintainability, modularity, testability, etc.

Indentation

Use four spaces, which is more standard. You do this in some places but not others.


Download a file given an url to a restricted area and a cookie container I have a queue of jobs in an ASP.NET CORE Application. Each of the files are in a restricted area and I have to Login first, thats why I use a Cookie Container for my download request.

The Job is logging into a platform and then starts to download the file, given an URL and a Cookie Container from the Login.

The download method is looking like this and has a Func which reports the progress in 5 % steps:

public async Task DownloadFile(string url, string destination, Func<int, Task> reportStatus)
{
        await reportStatus(0);

        var request = WebRequest.CreateHttp(url);
        request.CookieContainer = m_cookieContainer;
        var response = (HttpWebResponse)await request.GetResponseAsync();
        var requestStream = response.GetResponseStream();

        using (var reader = new BinaryReader(requestStream))
        {
            using (var fileStream = File.OpenWrite(destination))
            {
                const int bufferSize = 2048;
                byte[] bytes;
                short oldPercentage = 4;
                long bytesRead = 0;
                do
                {
                    bytes = reader.ReadBytes(bufferSize);
                    await fileStream.WriteAsync(bytes, 0, bytes.Length);

                    bytesRead += bytes.Length;

                    var percentage = (short)(bytesRead * 100 / response.ContentLength);
                    if (oldPercentage < percentage)
                    {
                        await reportStatus(percentage);
                        oldPercentage = (short)(oldPercentage + 5);
                    }
                } while (bytes.Length != 0);
            }
        }

        await reportStatus(100);
}

Small problems I am currently facing:

Download speed feels quite slow in comparison to my internet connection.
I was wondering if there are better ways downloading a file from a restricted area using .NET Core functionality.

You mentioned that the download is slower than you'd expect, I'll focus on just that for a quick review.

Look at your code here:

var percentage = (short)(bytesRead * 100 / response.ContentLength);
if (oldPercentage < percentage)
{
    await reportStatus(percentage);
    oldPercentage = (short)(oldPercentage + 5);
}

Can you see why that might be slowing down your download?

await reportStatus(percentage);

You're waiting for the task reporting the status to finish before reading the rest of the stream! What if reportStatus were logging the progress to a database or doing something else really time consuming?

I think you should just execute the callback and not care when/how it finishes:

reportStatus(percentage); // Don't wait

Oh and oldPercentage is really confusing when you scan the code... I'd rename it to something like reportingThreshold.

if (percentage > reportingThreshold)
{
     reportStatus(percentage);
     reportingThreshold = (short)(reportingThreshold+ 5);
}


Building a minimal-height BST from a monotonically increasingly ordered array structure Problem statement:

  Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

Assumptions:

The array (and therefore BST) will only contain the type int. Other integral types are unsupported.

The problem statement's description is a precondition and can therefore be taken for granted. No checks of uniqueness and unsortedness will be needed.

The algorithm:

Divide and conquer. The midpoint of the array will be the root. Because BSTs are a recursive data structure, the left and right pointers of the root are also BSTs. Recurse on the (beginning, midpoint-1) and the (midpoint+1, end) of the array.

Any recommendations, tips, and corrections are welcome!

#include <iostream>
#include <vector>
#include <memory>

struct Node {
    int data;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    Node() : left(), right() {}
    Node(int data) : data(data), left(), right() {}
};

template <typename It>
It get_midpoint_iterator(It start, It end) {
    auto midpoint = std::distance(start, end) / 2;
    It mid = start;
    std::advance(mid, midpoint);
    return mid;
}

template <typename It>
void create_bst_helper(std::unique_ptr<Node>& root, It start, It end) {
    if(start >= end) {
        return;
    }

    if(!root) {
        It midpoint = get_midpoint_iterator(start, end);
        root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));
        // left subtree is [start, midpoint)
        create_bst_helper(root->left, start, midpoint);
        // right subtree is [midpoint+1, end)
        create_bst_helper(root->right, std::next(midpoint, 1), end);
    }
}

template <typename It>
std::unique_ptr<Node> create_bst(It start, It end) {
    std::unique_ptr<Node> bst = nullptr;
    if(start != end) {
        create_bst_helper(bst, start, end);
    }
    return bst;
}

int main() {
    std::vector<int> v{1,2,3,4,5,6};
    std::unique_ptr<Node> bst = create_bst(std::begin(v), std::end(v));
}

Simplified Node type

This constructor:

Node() : left(), right() {}

Can be replaced with:

constexpr Node() noexcept
    : data{}
{}

The default constructor of std::unique_ptr<>  will initialize its contained pointer to nullptr, so you do not need to explicitly call it.

All of your classes' data members have non-throwing default constructors. Thus, you can safely mark yours as noexcept.

We can mark this constructor as constexpr, because similarly, all of your data member's default constructors are constexpr. This can be useful if you want to define a static compile-time special value, such as the empty node value.

This constructor:

Node(int data) : data(data), left(), right() {}

Can be replaced with:

constexpr Node(int const data) noexcept
    : data(data)
{}

We mark the parameter as const, because it is not modified.
We remove the redundant calls to the default constructors of left and right.
We mark it as constexpr and noexcept.
We use new lines for readability.

Finally, since you can live with initializing data with zero, you can replace both constructors with a single one:

constexpr Node(int const data = 0) noexcept
//                          ^^^^^ default value
    : data(data)
{}

Simplified calls

Your get_midpoint_iterator() function can be simplified. Here is how it currently looks:

template <typename It>
It get_midpoint_iterator(It start, It end) {
    auto midpoint = std::distance(start, end) / 2;
    It mid = start;
    std::advance(mid, midpoint);
    return mid;
}

These statements:

It mid = start;
std::advance(mid, midpoint);
return mid;

Can be replaced with:

return std::next(mid, midpoint);

View the documentation here: http://en.cppreference.com/w/cpp/iterator/next

Since your function's body now looks like this:

auto midpoint = std::distance(start, end) / 2;
return std::next(start, midpoint);

You can simply erase midpoint and put the calculation at the function call location:

return std::next(start, std::distance(start, end) / 2);

You end up with a concise function that is guaranteed copy elision in C++17.

template <typename It>
It get_midpoint_iterator(It start, It end) {
    return std::next(start, std::distance(start, end) / 2);
}

As @miscco points out, this obfuscates the operation slightly, so you might also want to add a comment indicating that std::distance(start, end) / 2 is the midpoint.

Your create_bst_helper() function currently initializes a std::unique_ptr<> in the following fashion:

root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));

This can be more clearly expressed with:

root = std::make_unique<Node>(*midpoint);

Your create_bst_helper() function currently creates a std::unique_ptr<> instance by assigning nullptr to it:

std::unique_ptr<Node> bst = nullptr;

The default constructor of std::unique_ptr<> already does so:

std::unique_ptr<Node> bst; // equivalent to `= nullptr;`


Pascal's Triangle Generator in Python So I've been working on a generator for Pascal's triangle in Python. Now, I wouldn't call myself a Python god, so my program is a lot longer than the very confusing ones on the internet. It's more of a logical approach to creating the triangle.

Here's the program:

def double_chunker(lst):
  leng = len(lst)
  for i in range(leng):
    if i == 0:
      yield [lst[0]]
    elif i == 1:
      yield [lst[0], lst[1]]
    elif i == leng:
      yield [lst[-1]]
    else:
      yield [lst[i-1], lst[i]]
  yield [lst[-1]]

def chunk_adder(lst):
  for i in lst:
    if len(i) == 1:
      yield i[0]
    else:
      yield sum(i)

def pascal_next(lst):
  return list(chunk_adder(double_chunker(lst)))

def pascal_triangle(rows):
  end = [[1]]
  for i in range(rows):
    end.append(pascal_next(end[-1]))
  return end

A simple go-through of how it works:

double_chunker() splits up a row of Pascal's triangle into the pairs of numbers you would use when adding up to determine the numbers in the next row. This algorithm is little jerry-rigged - I had to add some special exceptions for some numbers on the end of the row to make it work properly.
chunk_adder() adds together a list of chunks generated by double_chunker to determine the next row in the Pascal sequence.
pascal_next()combines both double_chunker() and chunk_adder() to, when given one row in Pascal's triangle, determine the next row in the triangle.
pascal_triangle() iteratively creates rows of Pascal's triangle using pascal_next().

So, here are some of my questions:

Is there anything in my program that seems redundant, repetitive, or can be shortened?
Is there any better code practices I should be employing and am not?

And obviously, as always, feel free to provide any other feedback you may have. Thanks in advance!

def chunk_adder(lst):
  for i in lst:
    if len(i) == 1:
      yield i[0]
    else:
      yield sum(i)

sum can happilly consume iterable of size 1, it can even consume iterable of size 0:

>>> sum([1])
1
>>> sum([])
0

So you can simplify it to:

def chunck_adder(iterable):
    for element in iterable:
        yield sum(element)

Which is simply

def chunck_adder(iterable):
    yield from map(sum, iterable)

So you could simplify pascal_next instead:

def pascal_next(lst):
    return list(map(sum, double_chunker(lst)))

def double_chunker(lst):
  leng = len(lst)
  for i in range(leng):
    if i == 0:
      yield [lst[0]]
    elif i == 1:
      yield [lst[0], lst[1]]
    elif i == leng:
      yield [lst[-1]]
    else:
      yield [lst[i-1], lst[i]]
  yield [lst[-1]]

The intent is pretty much the same than the pairwise recipe from itertools. Except you want to yield the first and last element as well.

Here you have two possibilities:

either yield them manually:

import itertools

def double_chunker(lst):
    if not lst:
        return
    a, b = itertools.tee(lst)
    next(b, None)

    yield [lst[0]]
    yield from zip(a, b)
    yield [lst[-1]]

But this forces the argument to be a list, or at least to know if its empty and to implement __getitem__.
or add boundary values to your input so pairwise can work properly:

import itertools

def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

def double_chuncker(iterable):
    extended = itertools.chain([0], iterable, [0])
    return pairwise(extended)

Which I recommend because it happily consume any iterable.

def pascal_triangle(rows):
  end = [[1]]
  for i in range(rows):
    end.append(pascal_next(end[-1]))
  return end

Instead of relying on the list being constructed, I would explicitly store the current row. I would also turn this into an infinite generator because it really is and maybe provide an helper function for convenience:

def pascal_triangle():
    row = [1]
    while True:
        yield row
        row = pascal_next(row)

def pascal_triangle_up_to(n):
    return list(itertools.islice(pascal_triangle(), n))

Full code:

import itertools

def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

def double_chuncker(iterable):
    extended = itertools.chain([0], iterable, [0])
    return pairwise(extended)

def pascal_next(iterable):
    return list(map(sum, double_chuncker(iterable)))

def pascal_triangle():
    row = [1]
    while True:
        yield row
        row = pascal_next(row)

def pascal_triangle_up_to(n):
    return list(itertools.islice(pascal_triangle(), n))

if __name__ == '__main__':
    # Testing
    for row in pascal_triangle():
        print(row, end='')
        if (input()):
            break


Is this use of ConcurrentDictionary truly thread safe? I'm working on some teaching examples showing the perils of accessing the Dictionary class concurrently.  In the code below each function is designed to do a word count across a number of files.  (This isn't the best way of doing the count but it's there to make a point about Dictionary.)

The first example, using a Dictionary and no parallelism works fine.

The second example, using a Dictionary and Array.parallel can fail with an exception and also produces different results each time.  This is deliberate and is there to make the point.

The final example uses ConcurrentDictionary and seems to me to work fine.  My concern is: given this uses a delegate to do the count addition, is this version genuinely thread safe?

// Simple version:
let WordCount dirPath wildCard =

   let wordCounts = Dictionary<string, int>()

   let ProcessFile fileName =
      let text = File.ReadAllText(fileName)

      text.Split([|'.'; ' '; '\r'|], StringSplitOptions.RemoveEmptyEntries)
      |> Array.map (fun w -> w.Trim())
      |> Array.filter (fun w -> w.Length > 2)
      |> Array.iter (fun w ->
         let ok, count = wordCounts.TryGetValue(w)
         if ok then
            wordCounts.[w] <- count+1
         else
            wordCounts.[w] <- 1)

   Directory.EnumerateFiles(dirPath, wildCard)
   |> Seq.iter ProcessFile

   wordCounts
   // |> Seq.sumBy (fun kv -> kv.Value)
   |> Seq.sortBy (fun kv -> -kv.Value)

// Naive concurrent version:
let WordCount2 dirPath wildCard =

   let wordCounts = Dictionary<string, int>()

   let ProcessFile fileName =
      let text = File.ReadAllText(fileName)

      text.Split([|'.'; ' '; '\r'|], StringSplitOptions.RemoveEmptyEntries)
      |> Array.map (fun w -> w.Trim())
      |> Array.filter (fun w -> w.Length > 2)
      |> Array.iter (fun w ->
         let ok, count = wordCounts.TryGetValue(w)
         if ok then
            wordCounts.[w] <- count+1
         else
            wordCounts.[w] <- 1)

   Directory.EnumerateFiles(dirPath, wildCard)
   |> Array.ofSeq
   |> Array.Parallel.iter ProcessFile

   wordCounts
   |> Seq.sumBy (fun kv -> kv.Value)
   // |> Seq.sortBy (fun kv -> -kv.Value)

// Safe concurrent version:
let WordCount3 dirPath wildCard =

   let wordCounts = ConcurrentDictionary<string, int>()

   let ProcessFile fileName =
      let text = File.ReadAllText(fileName)

      text.Split([|'.'; ' '; '\r'|], StringSplitOptions.RemoveEmptyEntries)
      |> Array.map (fun w -> w.Trim())
      |> Array.filter (fun w -> w.Length > 2)
      |> Array.iter (fun w -> wordCounts.AddOrUpdate(w, 1, (fun _ count -> count+1 )) |> ignore)

   Directory.EnumerateFiles(dirPath, wildCard)
   |> Array.ofSeq
   |> Array.Parallel.iter ProcessFile

   wordCounts
   |> Seq.sumBy (fun kv -> kv.Value)
   // |> Seq.sortBy (fun kv -> -kv.Value)

If you just used your original code (TryGetValue followed by an indexer set) with ConcurrentDictionary, then that wouldn't be thread-safe.

But you're using the AddOrUpdate method instead, which is guaranteed to be thread-safe (i.e. atomic), so this use is thread-safe.

One other nitpick:

Directory.EnumerateFiles(dirPath, wildCard)
|> Array.ofSeq

If you don't actually want seq, but an array, Directory has a method just for that: Directory.GetFiles.


Regex for matching a US phone number I have written my first regex:

static void Main(string[] args)
{
    string phoneNumber= Console.ReadLine();

    Regex pattern = new Regex("(1-)?\\p{N}{3}-\\p{N}{3}-\\p{N}{4}\\b");

    MatchCollection collection = pattern.Matches(phoneNumber);

    Console.WriteLine(phoneNumber + " is " + (collection.Count == 1 && collection[0].ToString() == phoneNumber ? "" : "not ") + "a valid US number.");
}

It needs to match the entire input string, and it can work for any US phone number with or without country code "1-". It can most likely be improved; any suggestions?

Use of Regex Objects

If your intent is merely to validate that the input is a phone number or not, rather than trying to capture anything, you can use the static Regex.IsMatch function:

var isPhoneNumber = Regex.IsMatch(phoneNumber, "(1-)?\\p{N}{3}-\\p{N}{3}-\\p{N}{4}\\b");

That saves having to deal with creating a new object and deal with a MatchCollection

Regex Pattern

There are a few things I would change:

There is a simple character class for matching digits 0-9: \d.  \p{N} may be more appropriate if you need to match the entire Unicode number group rather than simple digits, but then I would not expect to see the explicit 1 at the start.
\b matches backspace characters, which seems a little odd in a phone number.  I would omit it.  If your phone number strings happen to have backspace characters at the end, it will still match, but I would not require it be there.
Given the backslashes necessary for character escapes, I would prefix your string with the @ symbol for readability

Also, as @miasbeck points out, if you want to match the entire input string, you need to prefix the pattern with ^ and suffix it with $.  They indicate that the match must start at the beginning and end of the string, respectively.

The end result would be something like the following:

@"^(1-)?\d{3}-\d{3}-\d{4}$"

Additionally, since there is no requirement that an area code is used for local numbers, so you may want to make it optional as well:

@"^((1-)?\d{3}-)?\d{3}-\d{4}$"

(note: The MSDN page on Regular Expression Language is always a good reference to check on when coming up with regex patterns in .NET code.)

String Formatting

Rather than concatenating the strings together, I would use a format string:

const string FMT = "{0} is {1} a valid US number.";

Additionally, instead of using "", I always tend towards string.Empty, as it is much more explicit about intent.  "" could easily be a mistake, but string.Empty is clear that you really do want an empty string.

You can then output your result as follows:

Console.WriteLine(FMT, phoneNumber, (isPhoneNumber ? string.Empty : "not "));

Bringing it Together

Taking all the suggestions together, you get the following:

static void Main(string[] args)
{
   const string FMT = "{0} is {1} a valid US number.";
   var phoneNumber= Console.ReadLine();
   var isPhoneNumber = Regex.IsMatch(phoneNumber, @"^((1-)?\d{3}-)?\d{3}-\d{4}$");
   Console.WriteLine(FMT, phoneNumber, (isPhoneNumber ? string.Empty : "not "));
}

(note: I switch back and forth between C# and F# , so I use var more often than most - feel free to keep the explicit type declarations if you really want)


Classifying counts of repeat visits per user for a website I am trying to get number of times (or sessions) a user re-visited the website.

What I'm trying to find out-

Get the total number of users, number of sessions in the last 30days. I need to a pie chart ultimately where it shows people who revisited-

more than 100 times,
50-100 times,
less than 50 times

The problem with the current implementation I see is -

The whole set of data(like 100million rows) are being computed every time(for each query with different condition)

SELECT COUNT(A.sess) as acount, SUM(A.sess) as asum, AVG(A.sess) as aavg
FROM
(SELECT ipaddress,
        COUNT(*) AS sess
   FROM analytics
   WHERE trunc(datecreated) > getdate() - interval '30 days'
   GROUP BY trunc(datecreated), ipaddress
   HAVING COUNT(*) >= 100) AS A

UNION ALL

SELECT COUNT(B.sess) as bcount, SUM(B.sess) as bsum, AVG(B.sess) as bavg
FROM
(SELECT ipaddress,
        COUNT(*) AS sess
   FROM analytics
   WHERE trunc(datecreated) > getdate() - interval '30 days'
   GROUP BY trunc(datecreated), ipaddress
   HAVING COUNT(*) < 100 AND COUNT(*) >=50 ) AS B

UNION ALL

SELECT COUNT(C.sess) as ccount, SUM(C.sess) as csum, AVG(C.sess) as cavg
FROM
(SELECT ipaddress,
        COUNT(*) AS sess
   FROM analytics
   WHERE trunc(datecreated) > getdate() - interval '30 days'
   GROUP BY trunc(datecreated), ipaddress
   HAVING COUNT(*) < 50 ) AS C

How do I optimize the query?

MySQL version 8 supports common table expression.  If you want to differentiate between the three sub queries, use a column containing literal:

WITH SESSIONS_THIS_MONTH AS (
SELECT ipaddress,
        COUNT(*) AS sess
   FROM analytics
   WHERE trunc(datecreated) > getdate() - interval '30 days'
   GROUP BY trunc(datecreated), ipaddress
)
SELECT 'MORE THAN 100' AS CATEGORY,
       COUNT(SESSIONS_THIS_MONTH.sess) as acount,
       SUM(SESSIONS_THIS_MONTH.sess) as asum,
       AVG(SESSIONS_THIS_MONTH.sess) as aavg
FROM SESSIONS_THIS_MONTH
WHERE sess >= 100

UNION ALL

SELECT 'BETWEEN 50 AND 100' AS CATEGORY,
       COUNT(SESSIONS_THIS_MONTH.sess) as bcount,
       SUM(SESSIONS_THIS_MONTH.sess) as bsum,
       AVG(SESSIONS_THIS_MONTH.sess) as bavg
FROM SESSIONS_THIS_MONTH
WHERE sess < 100 AND sess >=50

UNION ALL

SELECT 'LESS THAN 50' AS CATEGORY,
       COUNT(SESSIONS_THIS_MONTH.sess) as ccount,
       SUM(SESSIONS_THIS_MONTH.sess) as csum,
       AVG(SESSIONS_THIS_MONTH.sess) as cavg
FROM SESSIONS_THIS_MONTH
WHERE sess < 50


Palindromes that are sum of consecutive squares I have been working on a Project Euler: 125, which took me ages to solve. The problem and source are cited below

  The palindromic number 595 is interesting because it can be written as
  the sum of consecutive squares: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 +
  12^2.

  There are exactly eleven palindromes below one-thousand that can be
  written as consecutive square sums, and the sum of these palindromes
  is 4164. Note that 1 = 0^2 + 1^2 has not been included as this problem
  is concerned with the squares of positive integers.

  Find the sum of all the numbers less than 10^8 that are both
  palindromic and can be written as the sum of consecutive squares.

I firstly tried to figure out if there were some pattern in the square sums, however i found none. My solution ended sadly up being brute force one.

1) Generate all possible palindromes
2) Generate all possible values
of square numbers

1) Is fairly fast however 2) takes (understandably) ages. The code works and gives the correct answer, but it takes ages. I think the problem is memory.

Is there any faster way of checking whether a palindrome can be written as a sum of consecutive squares?

Any other suggestions for my code are also welcome. Python 2.7

from math import floor
from itertools import count

def palindromic_square_summable(limit):
    """
        Finds all numbers p, such that
            p = n^2 + (n+1)^2 + ... + m^2
        and p is a palindrome. Eg 595 or 55.
    """
    dic = get_quadratic_sums(limit)
    pal = all_palindromes(2, limit)
    total = 0
    for key in pal:
        try:
            dic[key]
            total += key
        except:
            pass
    return total

def get_palindrome():
    """
        Generator for palindromes.
        Generates palindromes, starting with 0.
        A palindrome is a number which reads the same in both directions.
    """
    yield 0
    for digits in count(1):
        first = 10 ** ((digits - 1) // 2)
        for s in map(str, range(first, 10 * first)):
            yield int(s + s[-(digits % 2)-1::-1])

def all_palindromes(minP, maxP):
    """Get a sorted list of all palindromes in intervall [minP, maxP]."""
    palindrom_generator = get_palindrome()
    palindrome_dict = dict()
    for palindrome in palindrom_generator:
        if palindrome > maxP:
            break
        if palindrome < minP:
            continue
        palindrome_dict[palindrome] = 1
    return palindrome_dict

def get_quadratic_sums(limit):
    """Get a list of all possible square sums"""
    max_square = int(floor( limit**0.5))
    partial_sums = [0]*(max_square+1)
    dic = dict()

    for i in range(1, max_square+1):
        partial_sums[i] = partial_sums[i - 1] + i**2
        for partial in partial_sums[0:i-1]:
            val = partial_sums[i] - partial
            dic[val] = 1
    return dic

if __name__ == '__main__':
    limit = 10**3
    print palindromic_square_summable(limit)

The key problem with the performance of your code is get_quadratic_sums. This returns all sums of consecutive squares each of which is individually below the limit. But the vast majority of this work is wasted, because we are only interested in in sums of consecutive squares where the sum is below the limit.

So a very simple change to your code massively improves its performance. Where the code iterates over sums of squares:

for partial in partial_sums[0:i-1]:
    val = partial_sums[i] - partial
    dic[val] = 1

Iterate in reverse order (so that val is increasing) and stop when val is too large:

for partial in partial_sums[i-2::-1]:
    val = partial_sums[i] - partial
    if val >= limit:
        break
    dic[val] = 1

Now it runs in less than a second on my laptop:

>>> timeit(lambda:palindromic_square_summable(10**8), number=1)
0.7864874959923327

But we can do even better than that. Slicing a list in Python makes a copy of the sliced part of list. We can avoid the copy by iterating over the indices instead:

for j in xrange(i-2, -1, -1):
    val = partial_sums[i] - partial_sums[j]
    if val >= limit:
        break
    dic[val] = 1

Now it runs in less than half a second:

>>> timeit(lambda:palindromic_square_summable(10**8), number=1)
0.40678663086146116

A few more improvements:

int rounds towards zero, so you can write int(limit ** .5) instead of int(floor(limit ** .5)).
Since there have to be at least two squares in the sum, we only need to check up to int((limit / 2) ** .5).
get_quadratic_sums returns a dictionary whose keys are sums and whose values are always 1. But the values are never used, so it would make more sense to use Python's built-in sets:

def get_quadratic_sums(limit):
    """Return set of sums below limit of two or more consecutive squares."""
    max_square = int((limit / 2) ** .5) + 1
    partial_sums = [0] * max_square
    sums = set()
    _add = sums.add
    total = 0
    for i in xrange(1, max_square):
        total += i * i
        partial_sums[i] = total
        for j in xrange(i - 2, -1, -1):
            val = total - partial_sums[j]
            if val >= limit:
                break
            _add(val)
    return sums

Note the use of the local variable _add to remember the sums.add method: this avoids looking it up again on each loop iteration.
Similarly, all_palindromes can be changed to return a set instead of a dictionary:

def all_palindromes(limit):
    """Return set of palindromes below limit."""
    palindromes = set()
    _add = palindromes.add
    for p in get_palindrome():
        if p >= limit:
            break
        _add(p)
    return palindromes

Now that both of these functions return sets, you can just take their intersection, like this:

def palindromic_square_summable(limit=10**8):
    """Return the sum of palindromes below limit that are sums of two or
    more consecutive positive integers.

    """
    return sum(get_quadratic_sums(limit) & all_palindromes(limit))

This is even faster:

>>> timeit(palindromic_square_summable, number=1)
0.29244883195497096


Python script to update an existing column values in a csv from another two tables I need to update two columns: feedID and OperatID of table#1.csv with 'feed description', 'Operate description' from other CSV files. I don't have the pandas module available.

import csv
table1 = r'N:\Extracts\table1.csv'
table2 = r'N:\Extracts\table2.csv'
with open(table1,'r+')as f1:
    f1reader = csv.reader(f1)
    f1reader.next()
    f1writer = csv.writer(f1)
    for row in f1reader:
        in_fdrid = row[2]
        def get_fdrname(in_fdrid):
            with open(table2,'rU')as f2:
                f2reader = csv.reader(f2)
                for f2row in f2reader:
                    if in_fdrid == f2row[1]:
                        fdrnm = f2row[2]
                        return fdrnm
            f2.close()
        row[2].replace(in_fdrid,get_fdrname(in_fdrid))

Your code as it stands now will open and read file f2 every time you process a line from f1. This is way more work than you need to do.

I suggest you create a dictionary mapping ids to replacement values. You can then read all the lines from table2 one time, and populate the dictionary:

feed_desc = dict()

with open(table2) as tbl2:
    t2csv = csv.reader(tbl2)
    next(t2csv)  # skip headings

    for t2row in t2csv:
        feed_id = t2row[1]
        desc = t2row[2]

        feed_desc[feed_id] = desc

Once that is done, you can simply check if an id is in feed_desc, and if so provide the replacement value:

with ...
    ...
    for t1row in t1csv:
        feed_id = t1row[2]

        if feed_id in feed_desc:
            t1row[2] = feed_desc   # replace id with desc, you said.

        t1writer.writerow(t1row)

You can do a similar thing for t3 into a different dictionary. Just make sure you read both t2 and t3 before you start processing t1.


Convert a stream to Promise I need to collect all the data from the stream and resolve it as promise.

I created this stream:

class CollectToPromise extends Writable {
  constructor(options) {
    super();
    this._result = ""

    this.result = new Promise((resolve, reject) => {
      this.on('finish', resolve):w
      this.on('error', reject)
    }).then(() => this._result)

  }

  _write(chunk, encoding, callback) {
    this._result += chunk
    callback()
  }

  _writev(chunks, callback) {
    chunks.forEach(c => {
      this._result += chunk
    })
    callback()
  }

  asPromise() {
    return this.result
  }
}

and I use it like this:

var r = fs.createReadStream('secrets');
const c = new CollectToPromise()
const encrypt = crypto.createCipher(algorithm, password);
r.pipe(encrypt).pipe(c).asPromise().then((res) => console.log(res)

My questions are:

What do you think about the solution, including the naming?
How can I avoid the warning: (node:32386) Warning: Use Cipheriv for counter mode of aes-256-ctr?

I am not sure I understand why you are attempting to extend Writable here.

At the end of the day, it seems as if your pipeline is what you are REALLY wanting to have a promise interface.

Luckily this is really easy to do with recent versions of node using Stream.pipeline and Util.promisify().  There is an even an example in the Stream.pipeline documentation


Compound assignment operators in Python's NumPy library The "vectorizing" of fancy indexing by Python's NumPy library sometimes gives unexpected results.

For example:

import numpy
a = numpy.zeros((1000,4), dtype='uint32')
b = numpy.zeros((1000,4), dtype='uint32')
i = numpy.random.random_integers(0,999,1000)
j = numpy.random.random_integers(0,3,1000)

a[i,j] += 1
for k in xrange(1000):
    b[i[k],j[k]] += 1

It gives different results in the arrays 'a' and 'b' (i.e. the appearance of tuple (i,j) appears as 1 in 'a' regardless of repeats, whereas repeats are counted in 'b').

This is easily verified as follows:

numpy.sum(a)
883
numpy.sum(b)
1000

It is also notable that the fancy indexing version is almost two orders of magnitude faster than the for loop.

Is there an efficient way for NumPy to compute the repeat counts as implemented using the for loop in the provided example?

Ben,

The following modification to your code is a more accurate reflection of my larger problem:

    from timeit import timeit
    import numpy

    # Dimensions
    ROWS = 10000000
    SAMPLES = 10000
    COLS = 4

    # Number of times to run timeit
    TEST_COUNT = 100

    # Matrices
    a = numpy.zeros((ROWS, COLS), dtype='uint32')
    b = numpy.zeros((ROWS, COLS), dtype='uint32')
    c = numpy.zeros((ROWS, COLS), dtype='uint32')

    # Indices
    i = numpy.random.random_integers(0, ROWS - 1, SAMPLES)
    j = numpy.random.random_integers(0, COLS - 1, SAMPLES)

    # Fancy
    def fancy():
        a[i,j] += 1
    print "Fancy:", timeit("fancy()", setup="from __main__ import fancy", number=TEST_COUNT)

    # Loop
    def loop():
        for k in xrange(SAMPLES):
            b[i[k],j[k]] += 1
    print "Loop:", timeit("loop()", setup="from __main__ import loop", number=TEST_COUNT)

    # Flat
    def flat():
        flatIndices = i*COLS + j
        sums = numpy.bincount(flatIndices)
        c.flat[:len(sums)] += sums

    print "Flat:", timeit("flat()", setup="from __main__ import flat", number=TEST_COUNT)

    # Check that for_loop and custom are equivalent
    print "Equivalent:", (c == b).all()

With the exception that there are probably few samples that are actually repeated in this version. Let's ignore that difference for now. On my machine, your code gave the following timings:

    Fancy: 0.109203100204
    Loop: 7.37937998772
    Flat: 126.571173906
    Equivalent: True

This slowdown is largely attributable to the large sparse array output by bincount().


Get the last two digits of a string What would be the most performant way to get the last 2 digits of a string?

For example: getLastTwoDigits("a1b2cd3e4ghi5jk") must return "45";

I had already asked how to get the first two digits of a string. But now I need a performant way to get the last two digits.

I've adapted the answer I received in the other question and I could make it work using the code below. However, I know that I've defeated the purpose of StringBuilder when I used sb.insert(0, char).

private static String getLastTwoDigits(String s) {
    if(s==null)
        return null;

    StringBuilder sb = new StringBuilder(2);

    char charArray[] = s.toCharArray();
    for (int i = charArray.length-1; i>=0; i--) {
        if (Character.isDigit(charArray[i])) {
            sb.insert(0, charArray[i]);
            if (sb.length() == 2)
                break;
        }
    }

    return sb.toString();
}

I imagine that StringBuider is not the right tool for this case. So what would be the most performant solution?

sb.insert(0, charArray[i]);
            if (sb.length() == 2)
                break;
        }
    }

    return sb.toString();

You could change this to

             sb.append(charArray[i]);
             if (sb.length() >= digitCount) {
                 break;
             }
         }
     }

     return sb.reverse().toString();

Then you're using your StringBuilder as intended.  Appending rather than constantly inserting.

Changing 2 to digitCount allows you to alter the number of digits to find easily.

I prefer to always use the block form of control structures, even when the statement form would work.


Optimizing an Anagram Solver I've built an anagram solver in Python 2.7. It goes through a text file with over 100,000 words and checks if any permutations of the input matches the line. It works great, except it is very slow. I've tried making the text file a list with each line as a list item, but the text file is too big to do that. This is the text file that I am using (it's saved on my flash drive).

# import permutations module
from itertools import permutations as prm

num_of_cases = int(raw_input("Input number of words needed to be unscrambled: "))
# take input
counter = 1
while counter <= num_of_cases:
   scrambled_word = list(str(raw_input("Input scrambled word: ")))

# empty lists that will be appended to later
   prm_list = []
   possible_words = []

# takes each permutation of the input and puts in a list
   for i in prm(scrambled_word):
      prm_list.append("".join(i))

   def check(x, y):

   # open list of words
      dictionary = file('E:\MRP\Text_Files\dictionary.txt')

      # check each line in the dictionary against each item
      # in the list of permutations and add it to another empty list if it's a match
      for line in dictionary:
         for i in x:
            if i+'\n' == line:
               y.append(i)

   check(prm_list, possible_words)

# delete duplicates
   possible_words = list(set(possible_words))

# print out possible words
   if len(possible_words) == 0:
      print "No matches found"
   else:
      for i in possible_words:
         print "Possible Word for Scrambled Word #" + str(counter) + ": " + i

# add to the counter
   counter+=1

If you test it out you can see that is very slow, especially as the words get larger. Is there anything I can do to improve the performance of this program?

Your first comment is misleading (it's the itertools module not the permutations module) and useless anyway. Remove it.

There's absolutely no reason to rename permutations to prm. Don't do it.

num_of_cases would be better called num_cases, simply because it's more conventional.

Your take input comment is misplaced. It should be at the place it refers to.

counter is too vague: what are you counting? I would call it num_matched_anagrams.

You don't need to convert scrambled_word to a list. permutations accepts any iterable. You don't need to call str on the output of raw_input; it already returns a string.

The prior improvements make the comment take input really obvious, so you can remove that.

The later comments are often misaligned. Have them in line with the text.

prm_list can be generated with just list(permutations(scrambled_word)). This removes two comments.

prm_list should just be called word_orders or similar; don't bother naming things by their type.

check is badly named; it should be called something like find_anagrams.

check should not use file, which is deprecated, but open. It should also use with to handle the file.

check should save the dictionary between runs. In fact, this shouldn't really be check's job at all.

The words should have their newlines trimmed, not the other way around.

check should only return anagrams, not deal with appending.

check should have sensibly named parameters.

check should just call permutations itself.

You do

possible_words = list(set(possible_words))

but why bother having possible_words as a list at all?

Instead of if len(possible_words) == 0, do if not possible_words. I would also switch the if around.

num_matched_anagrams+=1 should have spaces: num_matched_anagrams += 1. The comment is obvious, so remove it.

Now to deal with speed.

words should be a set (since it's a set of words) and you loop over the permutations first. This allows a check of:

def find_anagrams(scrambled_word, words):
    for word_order in permutations(scrambled_word):
        potential_word = ''.join(word_order)

        if potential_word in words:
            yield potential_word

which is much faster.

We can improve this further by doing all the work upfront by making a cannonical, sorted version. This generates a mapping:

sorted word → [list of words that sort to this word]

This can be generated like so:

from collections import defaultdict

word_anagrams = defaultdict(set)

with open('dictionary.txt') as dictionary:
   for word in dictionary:
      word = word.rstrip()

      word_anagrams[sorted(word)].add(word)

This then makes find_anagrams just word_anagrams[sorted(scrambled_word)]. This has high initial overhead (0.5 seconds for me with 170k words) but makes subsequent lookups insanely fast.

This gives the code:

from collections import defaultdict

word_anagrams = defaultdict(set)

with open('dictionary.txt') as dictionary:
   for word in dictionary:
      word = word.rstrip()

      word_anagrams[''.join(sorted(word))].add(word)

num_cases = int(raw_input("Input number of words needed to be unscrambled: "))

num_matched_anagrams = 1
while num_matched_anagrams <= num_cases:
   scrambled_word = raw_input("Input scrambled word: ")
   sorted_word = ''.join(sorted(scrambled_word))

   if word_anagrams[sorted_word]:
      for word in word_anagrams[sorted_word]:
         print "Possible Word for Scrambled Word #" + str(num_matched_anagrams) + ": " + word

   else:
      print "No matches found"

   num_matched_anagrams += 1

The loop can be replaced with for num_matched_anagrams in range(1, num_cases+1).

The whole thing should be put into a main function.

The dictionary parsing could be extracted to another function.

The print should use formatting and I'd add brackets for Python 3 compatibility:

print("Possible Word for Scrambled Word #{}: {}".format(num_matched_anagrams, word))

To complete Python 3 compatibility, add this to the top:

try:
   input = raw_input
except NameError:
   pass

This gives:

from collections import defaultdict

try:
   input = raw_input
except NameError:
   pass

def parse_dictionary(filename):
   word_anagrams = defaultdict(set)

   with open(filename) as dictionary:
      for word in dictionary:
         word = word.rstrip()

         word_anagrams[''.join(sorted(word))].add(word)

   return word_anagrams

def main():
   word_anagrams = parse_dictionary("dictionary.txt")

   num_cases = int(input("Input number of words needed to be unscrambled: "))

   for num_matched_anagrams in range(1, num_cases+1):
      scrambled_word = input("Input scrambled word: ")
      sorted_word = ''.join(sorted(scrambled_word))

      if word_anagrams[sorted_word]:
         for word in word_anagrams[sorted_word]:
            print("Possible Word for Scrambled Word #{}: {}".format(num_matched_anagrams, word))

      else:
         print("No matches found")

if __name__ == "__main__":
   main()

Note that this is the same technique as Prashant gave.


tcl script to parse C++ source code for type identifiers Experimenting with vera++ to validate some C++ source files.
https://bitbucket.org/verateam/vera/wiki/Home

vera++ is expandable by providing your own rules in tcl. To interface with the vera++ parser the following interface is provided:
https://bitbucket.org/verateam/vera/wiki/ScriptAPI

Using the above I have written a rule to look for type identifiers and validate that they have an initial uppercase letter.

#!/usr/bin/tclsh
# Check that Type identifiers have an initial uppercase letter.

# namespace TypeName
# class TypeName
# struct TypeName
# enum TypeName {  EnumTypeName1, EnumTypeName2 }
#
# Will ignore `using clauses`
#   using <Stuff> ;
#
# Thus when "using" stuff from other namespace we don't check (as they don't belong to us)
# Also it allows you to convert any external types to local names.
#
#   #include <sys/socket.h>
#   #include <sys/types.h>
#   // STUFF
#           sockaddr_in serv_addr;
#           // STUFF
#           if (::connect(socket, reinterpret_cast<struct sockaddr*>(&serv_addr), sizeof(serv_addr)) < 0)
#                                                   ^^^^^^^^^^^^    this fails.
# But you can write it like this:
#
#           using SockAddr = struct sockaddr;   // Allowed because >using <stuff>;< is ignored.
#           if (::connect(socket, reinterpret_cast<SockAddr*>(&serv_addr), sizeof(serv_addr)) < 0)
#

set state "start"
foreach f [getSourceFileNames] {
    foreach t [getTokens $f 1 0 -1 -1 {}] {
        set tokenName [lindex $t 3]
        set checkTypeName 0
        if {$tokenName == "space"} {
            #ignore space
        } else {
            if {$state == "start" && $tokenName == "namespace"} {
                set state "CheckIdnetifier"
            } elseif {$state == "start" && $tokenName == "class"} {
                set state "CheckIdnetifier"
            } elseif {$state == "start" && $tokenName == "struct"} {
                set state "CheckIdnetifier"
            } elseif {$state == "start" && $tokenName == "using"} {
                set state "using"
            } elseif {$state == "using" && $tokenName == "semicolon"} {
                set state "start"
            } elseif {$state == "using"} {
                #ignore
            } elseif {$state == "start" && $tokenName == "enum"} {
                set state "enum"
            } elseif {$state == "enum" && $tokenName == "identifier"} {
                set checkTypeName 1
            } elseif {$state == "enum" && $tokenName == "leftbrace"} {
                set state "enumOpen"
            } elseif {$state == "enumOpen" && $tokenName == "identifier"} {
                set checkTypeName 1
            } elseif {$state == "enumOpen" && $tokenName == "comma"} {
                # ignore
            } elseif {$state == "enumOpen" && $tokenName == "rightbrace"} {
                set state "start"
            } elseif {$state == "CheckIdnetifier" && $tokenName == "identifier"} {
                set checkTypeName 1
                set state "start"
            } else {
                set state "start"
            }
        }
        if {$checkTypeName} {
            set identifier [lindex $t 0]
            set firstLetter [string index $identifier 0]
            if {[expr ! [string is upper $firstLetter]]} {
                set lineNumber [lindex $t 1]
                report $f $lineNumber "Objects >$identifier< (Type) should have an initial upper case letter"
            }
        }
    }
}

You are checking 5 times if $state equals to "start" and several times for the other "states". You should compact this and maybe a switch would be better.

You have a spelling error CheckIdnetifier which should be corrected.