Create 'worst case test' data for compression test I am going to prepare some test data for a compression test.  One of the them is the 'worst case test', which should make the compressor work worst.  Use random number to generate such a file is an idea, but there still contain some kind of patterns in the data.  Using 7zip to compress such a file, I get a output file which is a little bit smaller than input file.

So I make a small piece of code to generate a file, which does not contain any repeated two bytes.  To make life difficult, I shuffle those byte pairs in special order, hope the compressor will have more difficulty to find any match, even with predication.

#include <iostream>
#include <fstream>

int main(int argc, char* argv[])
{
    const char* filename = "c:\\_Test\\hard.dat";

    std::ofstream ofs(filename, std::ios::binary | std::ios::out);
    if (ofs.bad())
    {
        std::cerr << "fail to open file\n";
        return -1;
    }

    for (unsigned int i = 0; i < 0x10000; ++i)
    {
        unsigned int t = (i * 0xc369) & 0xFFFF;
        ofs.write((char*)&t, 2);
    }
    std::cout << "job done\n";

    return 0;
}

It's running in windows, and I think it's easy to change filename to make it work on other system, or even use command line argument as filename, but that's not the point.

I tried use 7zip to compress it, both format (7z and zip) created file bigger than original file.  I have some other compressors, will test them later.

Any suggestions and help are appreciated.

This is a cool idea! Here are some thoughts I had:
What are these magic numbers?
You have 4 magic numbers in your main loop: 0x10000, 0xc369, 0xFFFF, and 2. What do they mean? It looks like 0x10000 is the number of 2-byte words you're writing to the file. It's also the limit of a 16-bit number. It would be nice if there were a named constant for that. Perhaps something like:
const int kWordsPerFile = 0x10000;

or
const int kMax16BitValue = 0x10000;

Or something along those lines. (Technically it's 1 more than the max, so maybe something more descriptive.)
Honestly, I can live with 0xFFFF but it wouldn't hurt to give it a name like kLSWMask (where LSW is least significant word) or something similar.
You could get rid of the 2 by making t be a uint16_t and then using sizeof(t).
That leaves 0xc369. I have no idea what it is. I assume this is some sort of linear congruential pseudo-random number generator, but I'm not really well versed in such things. How is it derived? What significance does it have? Give it a name so it's understandable to someone else 6 months from now.
Comments
I'm a big fan of self-documenting code. However, in this case, it would be nice to have at least a sentence explaining what the loop does. Coming across this code in the code base I work on would leave me scratching my head. I'd have to go back through source control comments to see if there was any clue of what it was about. Maybe just a comment like:
// Generate some pseudo-random numbers where no 2 bytes are repeated

would really help a lot! And if you have a link or a short sentence to explain the algorithm, that would be nice, too.


C Doubly Linked List It works, but it seems a bit long winded. I'd like some critiquing.

#include <stdio.h>
#include <stdlib.h>

struct node
{
  int data;
  struct node * previous;
  struct node * next;
};

struct linked_list
{
  struct node * first;
  struct node * last;
};

struct linked_list * init_list(struct node * node)
{
  struct linked_list * ret = malloc(sizeof(struct linked_list));
  ret->first = node;
  ret->last = node;
  return ret;
}

struct node * create_node(int data)
{
  struct node * ret = malloc(sizeof(struct node));
  ret->data = data;
  ret->previous = NULL;
  ret->next = NULL;
  return ret;
}

void destroy_list(struct linked_list * list)
{
  struct node * node = list->first, *next = NULL;
  while(node != NULL)
  {
    next = node->next;
    free(node);
    node = next;
  }
  free(list);
}

void push_front(struct linked_list * list, struct node * node)
{
  if(list->first != NULL)
  {
    node->next = list->first;
    list->first->previous = node;
  }
  else list->last = node;
  list->first = node;
}

void push_back(struct linked_list * list, struct node * node)
{
  if(list->last != NULL)
  {
    node->previous = list->last;
    list->last->next = node;
    list->last = node;
  }
  else push_front(list, node);
}

void insert_after(struct node * node, struct node * to_add)
{
  to_add->previous = node;
  to_add->next = node->next;
  node->next = to_add;
}

void remove_node(struct node * node)
{
  node->previous->next = node->next;
  node->next->previous = node->previous;
  free(node);
}

As mentioned in the comments this code is not long winded at all.  It is very clean in general.  Too clean in fact as you will see below.

You cannot create an empty linked list with your init_list.  However, in other parts of your code you assume list may be empty.  It is useful to be able to create an empty linked list since you may not know what you want your first node to be in advance.  I'd suggest changing init_list.
I personally like symmetry in linked list code.  You can always create the dual of one function by swapping all prevs with nexts and all heads with tails.  I don't think your push_back code should call push_front.  You can handle the else condition just like you did in push_front except by swapping variable names.
insert_after is incomplete.  Remember this is a doubly linked list.  Also the function doesn't handle the case when you insert after the current list->last.  You need to add the linked list to the function arguments.
remove_node does not handle all cases.  What if node was the head of the list?  What if it was the tail of the list?  What if it was both the head and the tail?  You don't actually have to write three different cases to handle this but you can.
As simply a style choice I would rename previous to prev
I am ignoring that you never check for your pointers being NULL

Edit:

This code actually can produce an empty list by passing NULL in as an argument to init_list


Return the first word with the greatest number of repeated letters I'm learning JavaScript and have written a function that accepts a string and returns the first word with the greatest number of repeated letters. For example:

Input:"Hello apple pie" - Output:"Hello"
Input:"Hello apple pie yelllow" - Output:"yelllow"

I've tried to keep it as concise as possible. I wonder whether later on in the code it starts to become more verbose. The answer it returns seems to be correct for all tests.

Could someone give some advice about improving my code? Or is it not bad?

function whichWord(str) {

// 1. split into array with words - EG if var str = "wodrd sy hello";
var arr = str.split(' '); // puts str into array ["wodrd", "sy", "hello"]
var mdArr = arr.map(function(el){ return el.split('') }); // puts str into MD array [["w","o","d","r","d"],["s","y"],["h","e","l","l","o"]]

// 2. get each unique letter (remove duplicates)
function removeDuplicates(a) {
 return Array.from(new Set(a))
}
var letters = mdArr.map(removeDuplicates);

// 3. count # of each letter occurrences
var temp = [];
var numbers = [];

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

for(k=0;k < letters[i].length;k++) {temp.push(mdArr[i].filter(function(c2){return c2==letters[i][k]}).length)}

numbers.push(temp);
temp=[];

}

var letterCount = letters.map((innerArr, i) => innerArr.map((letter, ii) => ({letter: letter, instances: numbers[i][ii]}))); // puts into MD array with objects:
/* returns: [
    [{letter: "w", instances: 1},{letter: "o", instances: 1},{letter: "d", instances: 2},{letter: "r", instances: 1}],
    [{letter: "s", instances: 1},{letter: "y", instances: 1}],
    [{letter: "h", instances: 1},{letter: "e", instances: 1},{letter: "l", instances: 2},{letter: "o", instances: 1}]
] */

// 4. return word from index with largest number, & first instance if matching numbers
var highestNumbers = letterCount.map((outerArr,i) => Math.max.apply(Math,outerArr.map((innerArr,ii) => innerArr.instances)));

var highestNumber = Math.max.apply(Math,highestNumbers);

var indexToReturn = highestNumbers.findIndex(function(c) { return c == highestNumber } );

return arr[indexToReturn];

}

This approach seems a bit overly-complicated - there are multiple loops over the word just to remove duplicates, count the letters, etc. I would suggest a simple loop over each word to count the number of repeated numbers, maintaining the max count so far, and then using a simple object mapping (or a Set could be used) to look up the max counts for each word. See the rewritten code below for an example of this.
Additionally, the indentation could be greatly improved. Perhaps the first level inside whichWord in your code was lost because of pasting it into the question. However, most JavaScript code is indented by 2 or 4 spaces inside each block.
I noticed that arrow functions are being used (e.g. letters.map((innerArr, i) => innerArr.map((letter, ii).... This is a feature of ecmascript-6 and thus other features from that standard could be used, such as const for any variable that is never re-assigned and let for any variable that needs to be reassigned (e.g. iterator variables, cumulative counts, etc.), as well as the spread syntax instead of using function.apply().
Rewritten code
Below is my first take at simplifying the code. It can be compared for performance in this jsPerf.

function maxMode(word) {
  if (word.length == 1) {
    return 0;
  }
  const counts = {};
  for (const letter of word) {
    counts[letter] = (counts[letter] ?? 0) + 1;
  }
  return Math.max(...Object.values(counts));
}
const whichWord = str => {
  const arr = str.split(' ');
  const mappings = arr.reduce((mapping, word) => {
    mapping[word] = maxMode(word);
    return mapping;
  }, {});
  const mappingCounts = Object.values(mappings);
  const highestNumber = Math.max(...mappingCounts);
  const indexToReturn = mappingCounts.findIndex(c => c == highestNumber);
  return Object.keys(mappings)[indexToReturn];
};
const strings = ['Hello a apple pie yellow', 'axaya zza'];
for (const string of strings) {
  console.log('whichWord('+string+'):', whichWord(string));
}

1https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String#Character_access
2https://stackoverflow.com/a/4051431/1575353


Find numbers with same number of divisors I tried to resolve this task:

  The integers 14 and 15, are contiguous (1 the difference between them,
  noticeable) and have the same number of divisors.

14 ----> 1, 2, 7, 14 (4 divisors)
15 ----> 1, 3, 5, 15 (4 divisors)

  The next pair of contiguous integers with this property is 21 and 22.

21 -----> 1, 3, 7, 21 (4 divisors)
22 -----> 1, 2, 11, 22 (4 divisors)

  We have 8 pairs of integers below 50 having this property, they are:

[[2, 3], [14, 15], [21, 22], [26, 27], [33, 34], [34, 35], [38, 39], [44, 45]]

  Let's see now the integers that have a difference of 3 between them.
  There are seven pairs below 100:

[[2, 5], [35, 38], [55, 58], [62, 65], [74, 77], [82, 85], [91, 94]]

  Let's name, diff, the difference between two integers, next and prev,
  (diff = next - prev) and nMax, an upper bound of the range.

  We need a particular function, count_pairsInt(), that receives two
  arguments, diff, and nMax and outputs the amount of pairs of integers
  that fulfill this property, all of them being smaller (not less or
  equal) than nMax.

  Let's see it more clearly with examples.

count_pairs_int(1, 50) -----> 8 (See case above)
count_pairs_int(3, 100) -----> 7 (See case above)

Source: codewars.com

My code:

def count_pairs_int(diff, n_max)
  (1..n_max - diff).select { |n| getDivisors(n) == getDivisors(n + diff) }.count
end

def getDivisors(num)
  (1..num).select { |n| (num % n).zero? }.count
end

There is a problem with time of execution code:

  The process terminated. It took longer than 8000ms to complete

Initial tests are passed (first 10). Any ideas on how I can optimize the code?

You are not interested in the divisors themselves, only how many there are.
This can be calculated if the prime factors are known. For example, 12 has two 2' s and one 3 (12 = 2*2*3). The divisors are the product of 0,1 or 2 2's and 0 or 1 3's. So six divisors. The primes themselves are irrelevant, what matters is how many of each there are.

If only Ruby shipped with a method to do this prime division...

require 'prime' # delivers the prime_division method

class Integer
  def tau
    self.prime_division.map(&:last).inject(1){|prod,i| prod *= i+1}
  end
end

def count_pairsInt(diff,  nMax )
  (1..nMax-diff).count{|n| n.tau == (n+diff).tau}
end

Note: Probably this can be faster by memoizing (storing) the last diff tau (divisor count) calculations, to avoid calculating them twice.


Replacing the vowels of a string with the letter "X" This code replaces every vowel of the string with "X":

def vowel_censor(sentence)
    vowels = "aeiou".chars
    result = []
    sentence.chars.each do |charachter|
      if vowels.include?(charachter)
        result << "X"
      else
        result << charachter
      end
    end
    result.join("")
end

puts "---------Vowel Censor----------"
puts vowel_censor("Let's order a pizza") == "LXt's XrdXr X pXzzX"
puts vowel_censor("Nitwit, blubber, oddment, tweak") == "NXtwXt, blXbbXr, XddmXnt, twXXk"
puts vowel_censor("Supercalifragilisticexpialidocious") == "SXpXrcXlXfrXgXlXstXcXxpXXlXdXcXXXs"

Look into regular expressions, which Ruby is very good at:

def vowel_censor(string)
  string.gsub(/[aeiou]/i, "X") # case-insensitive
end

Or, even easier, more low-level and more efficient, use String#tr:

def vowel_censor(string)
  string.tr("aeiou", "X") # lowercase only; use "aeiouAEIOU" to handle both upper- and lowercase
end

For your current code:

The Ruby convention is 2 spaces of indentation. Not 4 spaces, not tabs
Your code doesn't handle uppercase vowels
join doesn't need an argument in this case
charachter is misspelt
Don't create a variable (result in this case) and modify it from inside a block unless you really, really have to. Do something like this instead:

sentence.chars.reduce([]) do |result, char| # reduce is also aliased as #inject
  result << vowels.include?(char) ? "X" : char
end.join

or (building a string instead of an array)

sentence.chars.reduce("") do |result, char|
  result += vowels.include?(char) ? "X" : char
end

or (using a method similar to reduce)

sentence.chars.each_with_object([]) do |result, char|
  result << vowels.include?(char) ? "X" : char
end.join


Processing user input for a form I'm still learning PHP OOP, so I'd like to seek for some expert advice or criticism regarding this code I created.

In this script, I created the objects I need to process the user input from a form. While the $homepage object is responsible for displaying the whole webpage.

My questions are:

Is this consider clean code?
Can I completely hide the fact that I actually include the autoload and the configuration files?
Any recommendation or tips to improve my code?

<?php

/**
*
* OOP practice
* @author Joey
*/

require_once 'config/autoload.php';
require_once 'config/config.php';

// Database credentials

$host = $config['host'];
$dbname = $config['dbname'];
$username = $config['username'];
$password = $config['password'];

// Short variable names

$fname = isset($_POST['fname']) ? clean_data($_POST['fname']) : null;
$lname = isset($_POST['lname']) ? clean_data($_POST['lname']) : null;
$your_question = isset($_POST['question']) ? clean_data($_POST['question']) : null;

try {

    // Page object

    $homepage = new Page('Questions and Answers', 'QA', '', 'You ask, we answer');

    // Author object

    $author = new Author($fname, $lname);

    // Question object

    $question = new Question($your_question, $author);

    // Database object

    $pdo = new DbConnect($host, $dbname, $username, $password);

    // Connect to the database

    $pdo->open_connection();
} catch (Exception $e) {
    echo $e->getMessage(), '
';
    exit;
} catch (PDOException $e) {
    echo $e->GetMessage(), '
';
    exit;
}

if (isset($_POST['submit'])) {
    // Insert the user input into the database

    $pdo->execute_query('INSERT INTO author (first_name, last_name) VALUES (?, ?)', array($author->getFirstName(), $author->GetLastName()));
    $pdo->close_connection();
    $homepage->content = '
Your question

Hello ' . $author->getFirstName() . ' ' . $author->getLastName() . '!' . '

';
    $homepage->content .= '
You ask: ' . $question->getQuestion() . '

';
    $homepage->content .= 'Do you want to ';
    $homepage->content .= 'Ask another question?' . ' ' . '
';
} else {
    // Display the form

    $homepage->content = <<<_END

Your question here

    <form action="{$_SERVER['PHP_SELF']}" method="post" role="form">
        Enter your first name

     <input type="text" id="fname" name="fname" size="30">

        Enter your last name

        <input type="text" id="lname" name="lname" size="30">

        What is your question?

        <textarea id="question" name="question" rows="10" cols="70"></textarea>

        <input type="submit" name="submit" value="Submit">
    </form>
_END;
}

// Display the webpage using the Page class

$homepage->display();

function clean_data($data)
{
    $data = trim($data);
    $data = strip_tags($data);
    $data = addslashes($data);
    return $data;
}

A short list of issues I've noticed after a first glance at your code:

Pokemon exception handling (gotta catch 'em all): wrapping everything in a huge try-catch block is considered bad practice. What makes your code stand out even more is the pointless second catch
pointless second catch: a PDOException is a custom exception class, which is to say: PDOException extends Exception, therefore, your catch (Exception $e) block will catch instances of PDOExceptions, too. As a result, the second catch block is obsolete. Pointless. Code-smell. Noise. Get rid of it.
clean_data is not great. It's bad even. I can understand the strip_tags call, but addslashes is really rather pointless here. And a possible source of bugs. If you forget to call addslashes when inserting a password, or in some other piece of code that handles login information, the passwords in the DB won't match, even though the user has filled out the form correctly. You're using prepared statements, no need to add slashes. If anything, it does more harm than good
From the variable name ($pdo), it's quite obvious what kind of class DbConnect is. And, like I've posted on this site so many times (links below): it's evil. PDO offers a clean, well balanced, easy to use and powerful, fully object oriented API. You can't wrap it into something and end up with a better tool. Far from it. The only thing that you can do with it is to use it as a base in a fully-fledged DBAL like doctrine. And since doctrine already exists, writing it yourself is, basically, reinventing the wheel.
Generally, I don't like PHP code that strings together markup. It's error prone, and hard to maintain. That's why I didn't pay much attention to the HTML bit, but as tim pointed out: $_SERVER['PHP_SELF'] is a bad idea. If the form should be processed by the same script (or on the same url) that spawned it, just don't specify an action attribute. The default behavior is to post the form back to the same url anyway.

Links to previous answers explaining why you shouldn't try to wrap PDO:

Class for reducing development time
OOP PDO Database Connection
A PDO connection classto initiate multiple connection and easy access
Extendable PDO Wrapper Class
Check my profile, I'm pretty sure there are a lot more answers that deal with the matter, but I can't be bothered to look for every single one of them.


wait for the UI thread to complete or cancel the wait using System;
using System.Diagnostics;
using System.Threading;

class Program
{
  public static void Main()
  {
     ThreadPool.QueueUserWorkItem(() => {
        Thread.Sleep(10000);
        PressAnyKey.Cancel();
     });
     Console.WriteLine("Press Any Key or don't...");
     PressAnyKey.WaitOne();
  }
}

internal class PressAnyKey
{
  private static Thread inputThread;
  private static AutoResetEvent getInput;
  private static AutoResetEvent gotInput;
  private static CancellationTokenSource cancellationtoken;

  static PressAnyKey()
  {
    // Static Constructor called when WaitOne is called (technically Cancel too, but who cares)
    getInput = new AutoResetEvent(false);
    gotInput = new AutoResetEvent(false);
    inputThread = new Thread(ReaderThread);
    inputThread.IsBackground = true;
    inputThread.Name = "PressAnyKey";
    inputThread.Start();
  }

  private static void ReaderThread()
  {
    while (true)
    {
      // ReaderThread waits until PressAnyKey is called
      getInput.WaitOne();
      // Get here
      // Inner loop used when a caller uses PressAnyKey
      while (!Console.KeyAvailable && !cancellationtoken.IsCancellationRequested)
      {
        Thread.Sleep(50);
      }
      // Release the thread that called PressAnyKey
      gotInput.Set();
    }
  }

  /// <summary>
  /// Signals the thread that called WaitOne should be allowed to continue
  /// </summary>
  public static void Cancel()
  {
    // Trigger the alternate ending condition to the inner loop in ReaderThread
    if(cancellationtoken== null) throw new InvalidOperationException("Must call WaitOne before Cancelling");
    cancellationtoken.Cancel();
  }

  /// <summary>
  /// Wait until a key is pressed or <see cref="Cancel"/> is called by another thread
  /// </summary>
  public static void WaitOne()
  {
    if(cancellationtoken==null || cancellationtoken.IsCancellationRequested) throw new InvalidOperationException("Must cancel a pending wait");
    cancellationtoken = new CancellationTokenSource();
    // Release the reader thread
    getInput.Set();
    // Calling thread will wait here indefiniately
    // until a key is pressed, or Cancel is called
    gotInput.WaitOne();
  }
}

Is there any reason you don't just use the cancellation token to stop the thread? I'm also wondering why you're using an explicit thread at all. This is asynchronous programming the hard way. async-await and Tasks are the idiomatic way to do this for the last several versions of the language & framework.

I'm imagining your code looking something like this. (Totally untested. Might not compile.)

public static void Main()
{
    var cts = new CancellationTokenSource();
    var token = cts.Token;

    Task.Run(()=>
    {
        while (!Console.KeyAvailable)
        {
            if (token.IsCancellationRequested)
            {
                token.ThrowIfCancellationRequested();
            }

            await Task.Delay(50);
        }

        token.Cancel();
     }, token);

     Console.WriteLine("Press Any Key or don't...");

     await Task.Delay(50000, token);
     token.Cancel(); //task is still running, best to shut it down too
 }


Min Heap Implementation Min Heap Implementation

As an exercise, I wanted to implement a min heap using JavaScript.

I'm not terribly familiar with JavaScript best practices, so I wanted to get feedback on my approach.

Notes

I decided to implement the min heap using an array.

I filled the first element with a null value to make some of the math a little easier (in my opinion) - I know this is slightly more memory, but I thought the tradeoff was worth it

The actual MinHeap function is effectively a factory function (and not a constructor) that creates objects representing min heaps that wraps the underlying array implementation in closure.

The idea here was to minimize the public API (i.e. "privatize" as much of the internal implementation details as possible).
I explicitly named functions so that if any errors occurred, it would be easier to identify in the stack trace - I don't know if this preferred / matters

In the future, I could see this heap implementation expanding past a min heap to take a custom comparator, but I decided to keep it simple for the time being and simply use <.
I decided to write this in ES5 - I'll probably refactor this to use ES6 conventions in the future.

Questions

The questions I have are

Is the factory function approach sound?
Are there any JavaScript best practices that I've violated or ignored?
Is my implementation flawed in any way?

Implementation

var MinHeap = function() {
  var values = [null];

  function getParentIndex(childIndex) {
    return Math.floor(childIndex / 2);
  }

  function getChildIndices(parentIndex) {
    var leftChild = parentIndex * 2;

    return {
      leftChild: leftChild,
      rightChild: leftChild + 1,
    };
  }

  function swap(firstIndex, secondIndex) {
    var firstValue = values[firstIndex];

    values[firstIndex] = values[secondIndex];
    values[secondIndex] = firstValue;
  }

  function getSmallestNode(firstIndex, secondIndex) {
    var firstValue = values[firstIndex];
    var secondValue = values[secondIndex];

    if (firstValue > secondValue) {
      return {
        value: secondValue,
        index: secondIndex,
      };
    }

    return {
      value: firstValue,
      index: firstIndex,
    };
  }

  function add(value) {
    var valueIndex,
        parentIndex,
        parentValue;

    values.push(value);

    valueIndex = getSize();
    parentIndex = getParentIndex(valueIndex);
    parentValue = values[parentIndex];

    while (parentValue > value && parentIndex >= 1) {
      swap(parentIndex, valueIndex);

      valueIndex = parentIndex;
      parentIndex = getParentIndex(valueIndex);
      parentValue = values[parentIndex];
    }
  }

  function remove() {
    var firstValue = values[1],
        lastValueIndex = values.length - 1,
        lastValue = values.splice(lastValueIndex, 1)[0];

    if (getSize() > 0) {
      values[1] = lastValue;
      lastValueIndex = 1;

      var childIndices = getChildIndices(lastValueIndex);
      var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

      while (lastValue > smallestNode.value) {
        swap(lastValueIndex, smallestNode.index);
        lastValueIndex = smallestNode.index;

        var childIndices = getChildIndices(lastValueIndex);
        smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
      }
    }

    return firstValue;
  }

  function getFirst() {
    return values[1];
  }

  function getSize() {
    return values.length - 1;
  }

  return {
    add: add,
    remove: remove,
    getFirst: getFirst,
    getSize: getSize,
  };
};

Questions

  Is the factory function approach sound?

Yes it is by far the best for objects that will have more than one long lived instance. Not so good for many short lived instances in which case use prototyped factory to reduce instantiation overheads, but lose some flexibility when protecting state.
For single instance object use a singleton.

Freeze

For added state safety freeze the returned object so that it can not have its state mutated

return Object.freeze({add, remove, getFirst, getSize});

Internal reference

It is often the case that you need to reference the factory object from within the factory function. We can think of the factory functions closure as the object state and the returned object as the interface.

Because in JS the token this is unsafe we need to create a safe reference to the returned object that can be used from within the factory.

What that name is, is up to you, I would personally have called it interface however that is a reserved token in JS so I have taken to standardize the returned object name to API which works well and replaces the this token with the visually easier capitalized name.

Thus you can use the following (see below for details on getters)

const API = Object.freeze({
    add, remove,
    get first() { return  values[1] },
    get size() { return values.length - 1 },
});

return API;

Then from within the factory you can acess the interface as follows

// you had
if (getSize() > 0) {
// becomes
if (API.size > 0) {

Q2

  Are there any JavaScript best practices that I've violated or ignored?

Use const for variables that do not change.
Use object shorthand property notation. See below
Reduce GC overhead and by using preallocation and result object as optional argument. See below
Hoist var declarations to the top of the function.
Don't use line seperated declarations.  See below
Use getters and setters to simplify the interface.
Protect state and freeze the returned factory object.
null is to be avoided. undefined is better. Ignoring the DOM null is seldom used in JS and represents a defined placeholder.
Use shorter function form that is arrow functions.
The JS author's regret was to tokenize function rather than func which spurred the push and adoption of arrow functions. Use common abbreviations when possible, less to read is quicker to read and easier to comprehend. Source code is not an english literature dissertation, you don't need to double space for examiners notes.
JS has one number type (double AKA 64 bit floating point), however almost all implementations have a variety of under the hood number types. Signed 32 integer is the fastest and can be forced by using any of the bitwise operators. If working with known integer types (eg indices) use bitwise operations to ensure internal number type is int32
Don't add inferable names to variable names. You had function getParentIndex(childIndex) { return Math.floor(childIndex / 2); } is just as effective as const parentIdx = idx => idx >> 1; and makes one wonder why you need a function to perform a single operator?

Q3

  Is my implementation flawed in any way?

Not if the user of it is careful.

I do know that you can implement it without the need for the first item in the heap without adding complexity.

You do need to prevent your code from creating invalid states. Such as if you add a string as a number heap.add("1") your determination as to which is greater will false eg "11" > "2" evaluates to false. To prevent that from happening you need to convert added values to Number type. (see rewrite)

Also you do not want to accept values that are not numbers. You can throw a range error or ignore such values.

You do not protect against removing more than available and thus you can mutate the state to unusable. You should first check if there is anything to remove before doing so (see rewrite)

More info on above notes

Line separated declarations

Bad

var valueIndex,
    parentIndex,
    parentValue;

Better

var valueIndex;
var parentIndex;
var parentValue;

Best

var valueIndex, parentIndex, parentValue;

Shorthand property notation

Shorthand notation reduces the source code size, and thus is a major player in reducing to occurance of bugs.

eg creating an object from defined variables

var foo = someVal();
var bar = someOtherVal();

// old school ES notation
var obj = {foo : foo, bar : bar};

// ES6 + shorthand property notation
var obj = {foo, bar};

When you return the factory object

return {
    add: add,
    remove: remove,
    getFirst: getFirst,
    getSize: getSize,
};

You can return using shorthand

return {add, remove, getFirst, getSize};

Memory smart functions.

Memory smart functions aim to reduce the overhead that GC (Garbage collection) incurs by reducing needless memory allocations. It also has an additional benefit as it reduces the allocation and creation overheads associated with new objects and or arrays.

For example the function...

function getChildIndices(parentIndex) {
    var leftChild = parentIndex * 2;

    return {
      leftChild: leftChild,
      rightChild: leftChild + 1,
    };
}

...creates and returns a new object each time it is called. You ate just interested in the 2 64bit numbers (if ints then 32bit numbers), but an object requires much more than 2 64bit values, and it need to invoke memory management, and when done with the object it is added to the GC workload.

You call it as follows

  var childIndices = getChildIndices(lastValueIndex);  // creates new object
  var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

  while (lastValue > smallestNode.value) {
      swap(lastValueIndex, smallestNode.index);
      lastValueIndex = smallestNode.index;

      var childIndices = getChildIndices(lastValueIndex); // Creates it again each iteration
      smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
  }

The function can be changed to be able to remove that overhead using the following pattern

function getChildIndices(parentIndex, result = {}) {  // result is the returning object. If not passed it is created
    var leftChild = parentIndex * 2;
    result.leftChild = leftChild;
    result.rightChild = leftChild + 1;
    return result;
}

Then your calling function uses it as follows

  const childIndices = getChildIndices(lastValueIndex);  // creates new object as default parameter
  var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

  while (lastValue > smallestNode.value) {
      swap(lastValueIndex, smallestNode.index);
      lastValueIndex = smallestNode.index;

      getChildIndices(lastValueIndex, childIndices); // reuses the object, saving time, memory and GC overhead
      smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
  }

Read only properties using getters

You have the following functions that are equivalent to getters (hint they have get at the start of the name)

function getFirst() {
    return values[1];
}

function getSize() {
    return values.length - 1;
}

return {
    add: add,
    remove: remove,
    getFirst: getFirst,
    getSize: getSize,
};

Should be defined as getters

return Object.freeze({
    add, remove,
    get first() { return  values[1] },
    get size() { return values.length - 1 },
});

A rewrite

I have added some additional state protection to the interface. Done some renaming, and reduced memory management overheads. The whole thing is now 50 lines that easily fits a display meaning the whole function can be understood without any device interaction

const MinHeap = () => {
    const heap = [undefined];
    const childIdxs = (idx, res = {}) => (res.right = (res.left = idx << 1) + 1, res);
    const swap = (idxA, idxB) => {
        const temp = heap[idxA];
        heap[idxA] = heap[idxB];
        heap[idxB] = temp;
    }
    const smallestNode = (idxs, res = {}) => {
        res.idx = heap[idxs.left] > heap[idxs.right] ? idxs.right : idxs.left;
        res.val = heap[res.idx];
        return res;
    }
    const API = Object.freeze({
        add(val) {
            if (isNaN(val)) { throw new RangeError("Can only add numeric values") }
            var idx, parentIdx, parentVal;
            heap.push(Number(val));
            idx = API.size;
            parentIdx = idx >> 1;
            parentVal = heap[parentIdx];
            while (parentVal > val && parentIdx >= 1) {
                swap(parentIdx, idx);
                parentIdx = (idx = parentIdx) >> 1;
                parentVal = heap[parentIdx];
            }
        },
        remove() { // returns undefined if heap is empty
            if (API.size) {
                let lastVal = heap.pop();
                const first = heap[1];
                if (API.size > 0) {
                    let lastIdx = 1;
                    const indices = childIdxs(lastIdx);
                    const smallest = smallestNode(indices);
                    heap[1] = lastVal;
                    while (lastVal > smallest.val) {
                        swap(lastIdx, smallest.idx);
                        lastIdx = smallest.idx;
                        smallestNode(childIdxs(lastIdx, indices), smallest);
                    }
                }
                return first;
            }
        },
        get first() { return heap[1] },
        get size() { return heap.length - 1 },
    });
    return API;
}


Non-recursive filter to smoothen saw tooth wave I'm currently writing some of my first assembly code for a new project, I am applying a small non-recursive filter algorithm to some saw tooth wave data held in memory, in order to blunt the edges.

Using thumb2 instruction set on a cortex m3.

The algorithm being used is:

y[0] = x[-2]/8 + x[-1]/8 + x[0]/4 + x[1]/8 + x[2]/8

I have spent a long time looking at my code but cannot seem to optimize it any further.
The Assembly code I have written is in a loop for the length of data and I have applied the algorithm as so:

  LDMIA r0,{r5-r9}     ; get the next 5 data values to be filtered
  ADD r5,r5,r9         ; sum x[-2] with x[2]
  ADD r6,r6,r8         ; sum x[-1] with x[1]
  ADD r9,r5,r6         ; sum x[-2]+x[2] with x[-1]+x[1]
  ADD r7,r7,r9,LSR #1  ; sum x[0] with (x[-2]+x[2]+x[-1]+x[1])/2
  MOV r7,r7,LSR #2     ; form (x[0] + (x[-2]+x[-1]+x[1]+x[2])/2)/4
  STR r7,[r3],#4       ; save calculated filtered value
  ADD r0,r0,#4         ; move pointer address forward
  SUBS r4,r4,#1        ; decrement loop counter

Can any one see anywhere I could have better optimized this?

Full Code if needed

You need to realize that as you are passing over the input, you will be dividing each input by 8 four times and dividing each input by 4 once. You will also calculate the sum of each adjacent input twice. We can try to get rid of this redundancy.

First lets rewrite the filter:

y[0] = x[-2]/8 + x[-1]/8 + x[0]/4 + x[1]/8 + x[2]/8

like so:

y[0] = (x[-2] + x[-1] + x[0] + x[1] + x[2])/8 + x[0]/8 + (1 if x[0] odd, 0 otherwise)

Multiply both sides by 8:
8*y[0] = (x[-2] + x[-1] + x[0] + x[1] + x[2]) + x[0] + 8*(x[0]&1)

Assuming integers, if the input is floating point, just skipp the odd/even bit.

Notice how you now have a sliding sum? That's effective to compute.

I'm not well versed in assembly but I can give you pseudo C-code which you can translate to assembly:

void computeSample(int slidingSum, int midSample){
   return (slidingSum + midSample + (midSample & 1) * 8)/8;
}

void filter(int *input, int *output, int len) {
    const int width = 2;

    if (len < width*2 + 1) { return; }

    int slidingSum = 0;
    for (int i = 0; i < width*2 + 1; ++i) {
        slidingSum += input[i];
    }

    output[width] = computeSample(slidingSum, input[width]);
    for (int x0 = width + 1; x0 < len - width; ++x0) {
        slidingSum -= input[x0 - (width+1)];
        slidingSum += input[x0 + width];
        output[x0] = computeSample(slidingSum, input[x0]);
    }
}

You need to figure out how to handle the edges of the signal (repeating, zero extending, no-data etc).

Hope this helps!


Grading Students - Hackerrank Here is my solution to Grading Students courtesy of HackerRank. My code passes all tests in the testing suite but I feel like there could be a better implementation of it. But nonetheless, what are some pros/cons of my current implementation?
Thank you for answering.

def gradingStudents(grades):
    rounded_grades = []
    for grade in grades:
        if grade < 38:
            rounded_grades.append(grade)
        else:
            if grade % 5 == 0:
                rounded_grades.append(grade)
            else:
                difference = 0
                new_grade = grade
                while grade % 5 != 0:
                    difference += 1
                    new_grade += 1
                    if new_grade % 5 == 0:
                        break
                if difference < 3:
                    rounded_grades.append(new_grade)
                else:
                    rounded_grades.append(grade)
    return rounded_grades

Your code is pretty good. Nice job.
I'd personally change the first else to an elif so you don't have as much indentation.
Rather than using that while loop you can just use one % per number.

For each number if you get the modulo then you can find out how much to add. 7 % 5 is 2. Where 5 - 2 is not less than 3.

And so you can easily change the while to just difference = 5 - grade % 5
You can merge grade % 5 == 0 into the else.
You can change the order and content of the ifs. This is as we don't need to call list.append three times, just mutate grade.

def gradingStudents(grades):
    rounded_grades = []
    for grade in grades:
        if grade >= 38:
            difference = 5 - grade % 5
            if difference < 3:
                grade += difference
        rounded_grades.append(grade)
    return rounded_grades

Since we know the range that anything modulo 5 is 0-4, we can just make a small lists that holds how much to round.

ADDITIONS = [0, 0, 0, 2, 1]

def gradingStudents(grades):
    rounded_grades = []
    for grade in grades:
        if grade >= 38:
            grade += ADDITIONS[grade % 5]
        rounded_grades.append(grade)
    return rounded_grades

You can also change the code to a list comprehension if you're that way inclined.

ADDITIONS = [0, 0, 0, 2, 1]

def gradingStudents(grades):
    return [
        grade if grade < 38 else grade + ADDITIONS[grade % 5]
        for grade in grades
    ]


SQL design for representing a two-level hierarchy of objects with containment I am trying to represent questions in quizzes.
The database is Mysql but I am using fairly generic sql.  The assumption is that varchar cannot handle more than 255 though, so I am supporting longer text by having multiple text components.

There are four primitive kinds of questions: multiple choice, multiple answer, fill in the blank, and editText.  Multiple choice have multiple answers, with one being right.  Multiple anwer have multiple answers, with some being wrong and some being right.  The student is expected to pick multiple answers and avoid getting incorrect ones.  Fill in the blank allows a string answer which is compared against the answer (or answers).  For editText, a block of text is loaded and must be modified by the student.  An edittext can exceed 255 characters, so cannot use a single varchar.

In addition to the base types, there are also multi-part questions where each part can be a question.

My approach is as follows:

A Quiz is a collection of CompoundQuestions in a particular order.  This table is not included because it is not relevant to the rest of the question.

A CompoundQuestion is a sequence of text, graphics, and questions.  Some compound questions could have zero questions (text only) while other CompoundQuestions could have many.  Most will have just one.

CREATE TABLE CompoundQuestion(
  cqid integer(8) primary key
);

CREATE TABLE CompoundQuestionText(
  cqid integer(8),
  seq  integer(4),
  primary key (cqid, seq),
  text varchar(255),
  imgname varchar(255)
);

CREATE TABLE Questions (
  qid integer(8) primary key,
  qtype integer(4),
  cqid integer(8),
  seq  integer(4)
);

CREATE TABLE QuestionText (
  qid integer(8),
  seq integer(4),
  primary key(qid,seq),
  text varchar(255)
);

CREATE TABLE Answers (
  qid integer(8),
  aid integer(4),
  primary key (qid,aid),
  text varchar(255),
  img varchar(255)
);

Is this a reasonable approach?
Is there a better way to handle columns larger than 255 characters?  Blobs add complication and can't be searched, right?

Suppose more types are added.  Do extra fields just get added in new tables and joined to the base question table?  If so, every kind of question then requires a different query.  Is there any better way to do that?

Ideally, I would like to be able to write a stored procedure that loads all questions in a particular quiz.

The two approaches that occur to me are selecting each question and based on the type, creating the object, or selected all the objects of each type.  If the system expands to 10-20 different types of questions, what would be the best way to implement this query?

According the the MySQL reference for character types, varchar is limited to 65,535 characters (regular char is limited to 255).

There is also a text type which, according to the reference comes in 4 styles. The longest goes up to 4GB, which should be more than enough.


Python Regex to validate an email I have written this regex to validate an email. It seems to work fine. Can someone advise on the regex used? Does it work properly or can be done in a better way?
pattern=r"^[A-Za-z]+[-_$.A-Za-z]*@[A-Za-z]*\.[A-Za-z]+$"
x=re.search(pattern,"abc.xyz@gmail.com)
print x

Note: I have used x and print as Code Review needs minimum 3 lines of code.

That regex will not properly validate the format of an email address. Many web sites get it wrong when validating email addresses.
According to RFC5322, the local part of an address (the part before the @) can contain one or more text strings separated by .s.  The test strings can include letters, numbers, and any of these characters: ! # $ % & ' * + - / = ? ^ _ { | } ~ " or a back tick.  Alternatively, the local part can be a quoted string.  There can be comments in () and possibly whitespace in some places.
That's just for the local part using only US-ASCII characters.  There are other RFCs that describe the domain (after the @) and addresses with non-ASCII (e.g., Unicode) characters.


Have a class that holds all the interfaces I seriously didn't know how to write this in Google, there must be an answer lying around. Here it goes:

I'm using Ninject (IoC) and ASP.NET MVC 5. I have a business layer with a couple of classes. Is it ok if I have one class that holds all these classes? Like this:

    public class BusinessLayer : IBusinessLayer
{
    public IOrganizerLogic OrganizerLogic { get; }
    public IParticipantLogic ParticipantLogic { get; }
    public IPaymentLogic PaymentLogic { get; }
    public ITournamentLogic TourmanetLogic { get; }

    public BusinessLayer(IOrganizerLogic organizerLogic, IParticipantLogic participantLogic,
        IPaymentLogic paymentLogic, ITournamentLogic tournamentLogic)
    {
        OrganizerLogic = organizerLogic;
        ParticipantLogic = ParticipantLogic;
        PaymentLogic = PaymentLogic;
        TourmanetLogic = TourmanetLogic;
    }

}

Of corse you could do that, but I think that it breaks some ideas of dependency injection:

You can see the dependencies of a class by looking of the constrcutor (in your case, that is not possible)
You can test classes by mock the dependencies passed to the contructor (in your case you have to mock more because the dependencies are not evident)
You decople dependencies by passing only what you need (also not given in your case)

Instead of creating some granular dependencies of needed objects, your proposal is to create lots of dependencies from a container object that provides a set of objects. I see also the risk, that such a container object tends to grow so it makes the life easier (but conflicts with the idea behind DI).


Video playback loop using promise chaining and setTimeout Well this could seem redundant given the numerous topic about interaction between Promises and setTimeout but I can't find an answer that exactly fit my case (or that I am capable of interpreting !)

In the case of a Video player API usage, I need to loop on a sequence, and exit the loop when a certain condition is reached.

The following code works, but I was wondering if there was a sexier way, using Promise chaining instead of this :

export class LoopStep {
// looping from 0 to 5 seconds in the video
this.duration = 5;
this.start = 0;

onStart() { // entry point
    return this.onLoop();
}

onLoop() {
    return new Promise((resolve) => {
        this.loopAndResolve(resolve);
    });
}

loopAndResolve(resolve) { // start loop
    if(this.isLooping) { // exit condition when turned to false
        this.player.setTime(this.start);
        this.player.play();
        setTimeout(this.loopAndResolve.bind(this, resolve), this.duration * 1000); // callback
    } else {
        resolve();
    }
}
}

// Anywhere else
loopStep.onStart.then(()=> console.log('exiting loop successfully')); // OK

Actually I would find more appropriated to avoid passing the "resolve" function as a parameter (only because I have a feeling that this could be wrong, or at least not "the most efficient/sexy").

You could try something like this:
export class LoopStep {
    public onStart(): Promise<void> { // entry point
        return this.onLoop();
    }

    private onLoop(): Promise<void> {
        return this.loopAndResolve();
    }

    private loopAndResolve(): Promise<void> { // start loop
        if (this.isLooping) { // exit condition when turned to false
            this.player.setTime(this.start);
            this.player.play();
            setTimeout(() => this.loopAndResolve(), this.duration * 1000);
        } else {
            return Promise.resolve();
        }
    }
}

// Anywhere else
loopsStep.onStart().then(() => console.log('exiting loop successfully')); // OK

One of the best things of Typescript is the type safety. It's easier to keep track of the promises you're passing from one function to another if you declare them in the return type.
In your case, where you just want a cleaner way to resolve a Promise, you can use Promise.resolve();. It's pretty straightforward to use and very useful. DOCS
(Don't forget the parenthesis when calling onStart!)


Indexing and searching an list of rectangles to see if they contain a point I have a flat list of rectangles, in the following format (id, x co-ord, y co-ord, height and width):
[ { id: 4206, x: 360, y: 700, width: 60, height: 50 } ,
   { id: 6621, x: 1260, y: 1100, width: 60, height: 50 } ]

I want to index this by range of X values, and then use that indexed object to speed up a search for a point inside.
My full code is here:

// arbitrary setup, no need to review
const grid = [];
const height = 50;
const width = 60;
let index = 0;
for (let row = 0; row < 300; row++) {
  for (let col = 0; col < 300; col++) {
    grid[index] = {
      id: index,
      x: width * col,
      y: height * row,
      width,
      height
    };
    index++;
  }
}
// try and find these points
const points = [{
  x: 400,
  y: 700
}, {
  x: 1300,
  y: 1105
}]

// body - please review approach, style less important

const indexedGrid = grid.reduce((acc, curr) => {
  if (curr.x === undefined) return acc;
  if (acc[curr.x]) {
    acc[curr.x].shapes.push(curr);
    acc[curr.x].endEdge = Math.max(acc[curr.x].endEdge, curr.width + curr.x)
  } else acc[curr.x] = {
    shapes: [curr],
    startEdge: curr.x,
    endEdge: curr.width + curr.x
  };
  return acc;
}, {})
const indexedEdges = Object.values(indexedGrid).map(val => ({
  start: val.startEdge,
  end: val.endEdge
}));
const shapesContainingPoints = points.map(
  (point) => ({
    point,
    xRange: indexedEdges.filter(
      edge => (point.x >= edge.start && point.x < edge.end)
    )
  })
).map(
  pointWithRange => indexedGrid[pointWithRange.xRange[0].start].shapes.filter(
    shape => {
      return (pointWithRange.point.y >= shape.y && (pointWithRange.point.y < (shape.y + shape.height)))
    }
  )
);

//footer - purely to show results in the this question, no need to review
console.log(shapesContainingPoints)

I'm fully aware this code could be tidied up a lot, but the main thing I was hoping to ascertain, is if this 'index and search' pattern suits the following use case.
I'm drawing a load of rectangles in a html canvas element, and I want to be able to find which rectangle was clicked on using the x, y co-ords of the mouse. So I plan to create a flat list of the squares, and then index them by their X value. And from that X value, look along the row, filtering by Y value.
Currently the data only includes perfectly tiling rectangles, but in the future I may have to handle an alternating offset (every other row is shifted by a small value) or other less standard layouts.
Here are some example grids (all right angled) that I need to handle:
https://algorist.com/images/figures/bin-packing-R.png
https://i.stack.imgur.com/JG3iT.png
https://codeincomplete.com/articles/bin-packing/packed.png
I have no plans to have the number, size or position of the rectangles to change over time. I don't have a good grasp of quite how many total rectangles I will need to look over, but I'm expecting anything from 4 to 4000 say.
But it feels very clunky (overly complicated, and thus hard to comprehend/maintain), and that there should be a better approach to this problem? I'm also interested in performance, but that's secondary to maintainability at the moment.
If there is not a better alternative, is there anyway of improving my current approach?

One way to solve the problem with trees
A simplified look at binary trees

the rectangles are static

[the rectangles] should never overlap

As such we can build a simple tree.
Before looking at 2d points we can look at a solution for 1d points.
Say we have the following line segments. Beginnings are inclusive ends are not.

A: 0 - 2
B: 2 - 3
C: 3 - 4
D: 4 - 8

We could describe the values as a really simple binary tree.

With the example I gave we can reduce the amount of leaf nodes to just 4.

We do need to assign multiple leaves to the same node at times.
For example if we had the following line segments:

A: 0 - 3
B: 3 - 8

An algorithm for the above
As such we can just use a simple binary tree.
With two major changes:

We need to make the intermediary nodes when building the leaves.
We may need to add multiple leaf nodes to account for the end of the rect.

As such we can build a simple algorithm:

When building the nodes we need to know the index of the node.
Each node has a range for the values the children can be.
In our above 8 leaf node tree, the the values for node 4 can range from 0-8.
Where the 2 node's range is 0-4 and the 5 node's range is 4-6.

If the range of the line segment is greater than the range of the node we can stop recursing.

Otherwise we need to recursively append to the left or right child node. (Can be both.)

If the start of the line segment's range is less than the node's index we recurse left.
If the end of the line segment's range is greater than the node's index we recurse right.

Before recursing:

Build the child node if one doesn't exist.
The index will be:
Left: (node's index + node's start) // 2
Right: (node's index + node's end) // 2

We also need to adjust one of the start or end of the child node's range.
Left: The end of the child node's range is the current node's index.
Right: The start of the child node's range is the current node's index.

We then recurse into the children.

Here is an example implementation of such a binary tree in Python:
from __future__ import annotations

import dataclasses
import textwrap
from typing import Iterator, Optional, TypeVar, Generic

T = TypeVar("T")

@dataclasses.dataclass
class Node(Generic[T]):
    index: int
    left: Optional[Node[T]] = None
    right: Optional[Node[T]] = None
    value: Optional[T] = None

    def get_point(self, point: int) -> Optional[T]:
        if self.value is not None:
            return self.value
        child = self.left if point < self.index else self.right
        return child.get_point(point)

    def add_range(
        self,
        value: T,
        range_start: int,
        range_end: int,
        node_start: int,
        node_end: int,
    ) -> None:
        if range_start <= node_start and node_end <= range_end:
            self.value = value
            return
        if range_start < self.index:
            if self.left is None:
                self.left = Node((self.index + node_start) // 2)
            self.left.add_range(value, range_start, range_end, node_start, self.index)
        if self.index < range_end:
            if self.right is None:
                self.right = Node((self.index + node_end) // 2)
            self.right.add_range(value, range_start, range_end, self.index, node_end)

    # So I can show the code works
    def tree_format(self, join="──", top="  ", bottom="  ") -> Iterator[str]:
        if self.left is not None:
            for value in self.left.tree_format("┌─", bottom="│ "):
                yield top + value
        if self.value is None:
            yield f"{join}{self.index}"
        else:
            yield f"{join}{self.value}"
        if self.right is not None:
            for value in self.right.tree_format("└─", top="│ "):
                yield bottom + value

class Tree(Generic[T]):
    _size: int
    _root: Node

    def __init__(self, size: int) -> None:
        self._size = size
        self._root = Node(size // 2)

    def __str__(self) -> None:
        return "\n".join(self._root.tree_format())

    def add_range(self, value: T, start: int, stop: int):
        self._root.add_range(value, start, stop, 0, self._size)

    def get_point(self, point: int) -> Optional[T]:
        try:
            return self._root.get_point(point)
        except AttributeError:
            return None

if __name__ == "__main__":
    print("Tree1:")
    tree_1 = Tree(8)
    tree_1.add_range("A", 0, 2)
    tree_1.add_range("B", 2, 3)
    tree_1.add_range("C", 3, 4)
    tree_1.add_range("D", 4, 8)
    print(tree_1)
    print(3, "==", tree_1.get_point(3))

    print("\nTree2:")
    tree_2 = Tree(8)
    tree_2.add_range("A", 0, 3)
    tree_2.add_range("B", 3, 8)
    print(tree_2)
    print(3, "==", tree_2.get_point(3))

    print("\nTree3:")
    tree_3 = Tree(8)
    tree_3.add_range("A", 0, 3)
    tree_3.add_range("B", 4, 8)
    print(tree_3)
    print(3, "==", tree_3.get_point(3))

Tree1:
    ┌─A
  ┌─2
  │ │ ┌─B
  │ └─3
  │   └─C
──4
  └─D
3 == C

Tree2:
    ┌─A
  ┌─2
  │ │ ┌─A
  │ └─3
  │   └─B
──4
  └─B
3 == B

Tree3:
    ┌─A
  ┌─2
  │ │ ┌─A
  │ └─3
──4
  └─B
3 == None

We can abstract the binary tree (1D) to a quad tree (2D) and perform the same algorithm.
The quad tree will have a top-left, top-right, bottom-left and bottom-right but otherwise would work the same way.
Problems
The above solution isn't just rainbows and sunshine

The tree's size must never change.
If the tree ever needs to resize you must build one from scratch again.

Currently the tree cannot have overlapping boxes.
Adding the capability doesn't seem impossible however.

You would need to change Node.value to a list and append to the list in Node.add_range.
Adjust Node.get_point to not eagerly exit and return the children's values (if applicable) along with the current node's values.

Your tree can have lots of cruft leaf nodes because of bad index selection.
(node_end + self.index) // 2

Say you want to put 9 equally sized squares into a 3x3 grid, you won't have a nice 9 leaf nodes.
You'd have 36 leaf nodes.
We see a less severe version of the problem in "Tree2".
Had we selected 3 to be the first index to split on, rather than 4, we'd only have 2 nodes not 4.
  ┌─A
──3
  └─B

To solve the issue I'd move the index generation code out into a separate binary or quad tree.
For example we could abstract the index generation as:
class IndexNode:
    def __init__(self, index, start, end):
        self.index = index
        self.start = start
        self.end = end

    def left(self):
        start, end = self.start, self.index
        return Node((start + end) // 2, start, end)

    def right(self):
        start, end = self.index, self.end
        return Node((start + end) // 2, start, end)

We can now easily change the index generation for the 3x3 grid without having to mangle the other tree.
We could also manually define the tree.
But you'd have to manually build the entire tree.
Or have a hybrid where you define the top nodes and let the class generate the rest.

Maintainability

I'm aiming for maintainability over performance

As you can probably see using a tree can get you better performance.
Since the tree could find the rects in \$O(\log(n))\$ time.
To improve the performance and to get good memory usage may require more thought; depending on the intricate patterns you use.
However do you really get much from building an intricate quad-tree?
Even my simple binary tree is double your line count.
If you have come on CR without caring about speed then I can't imagine your current solution is performing poorly.
As such the cost to maintainability doesn't really seem worth the gain in speed at the moment.


Structure of API wrapper I'm building an API wrapper for a bookkeeping SOAP API.

I have some questions regarding bast practice for structure of the wrapper and for error handling.

For now i've structured it like this:

EconClient.php

class EconClient {

    public function __construct()
    {
        $wsdlUrl = 'https://api.e-conomic.com/secure/api1/EconomicWebservice.asmx?WSDL';
        $this->client = new SoapClient($wsdlUrl, array("trace" => 1, "exceptions" => 1));
    }

    public function connectWithToken($token, $appToken)
    {
        $this->client->ConnectWithToken(array('token' => $token, 'appToken' => $appToken));
    }

    public function debtor()
    {
        $this->debtor = new Debtor($this->client);
        return $this->debtor;
    }

    public function debtorGroup()
    {
        $this->debtorGroup = new DebtorGroup($this->client);
        return $this->debtorGroup;
    }
}

Debtor.php

class Debtor {

    public function __construct($client)
    {
        $this->client = $client;
    }

    public function get($param, $value)
    {
        return $this->client->Debtor_GetData(array('entityHandle' => $this->getHandle($param, $value)))->Debtor_GetDataResult;
    }

    public function getHandle($param, $value)
    {
        switch ($param) {
            case 'number':
                return $this->client->Debtor_FindByNumber(array('number' => $value))->Debtor_FindByNumberResult;
                break;
            case 'email':
                return $this->client->Debtor_FindByEmail(array('number' => $value))->Debtor_FindByEmailResult;
    }
}

Is there any way i could structure this so i would'nt have to pass in the $client into the resource classes?

The only response i can get from the SOAP client except from data in case of success is exceptions. If i'm trying to fetch an ID that doesn't exist i will get an exception too. Should i try and catch these exceptions in for example Debtor.php? Or how could i structure error handling?

First off:

  The only response i can get from the SOAP client except from data in case of success is exceptions.

Of course, if your call wasn't successful, there's something wrong, and an exception should be thrown. If you query for an ID that doesn't exist, don't catch the exception. That means the user has provided your client with invalid data, and its that user who must deal with the problem. Not You.
An API doesn't really deal with that many exceptions. In fact, I'm one of those people who think that a well written, bug free API-wrapper doesn't need exception handling. If the wrapper/client's code is properly put together, exceptions are the result of either bad usage or exceptions being returned by the webservice. Both types of errors should be dealt with by the user.

If you don't want to pass the client to all those classes, the answer is simple: inheritance:

class BaseClient
{
    protected $client = null;//declare your properties!!!
    protected $config = null;
    //use type hints, default = null means you don't HAVE to pass the argument
    public function __construct(\SoapClient $client = null)
    {
        $this->client = $client;
    }
    //lazy-loading getter
    protected function getClient()
    {
        if ($this->client === null)
        {//set client only when it's required
            $this->setClient(
                new \SoapClient($this->config['wsdl'], $config['options']
            );
        }
        return $this->client;
    }
    //public to allow injection
    protected function setClient(\SoapClient $client)
    {
        $this->client = $client;
        return $this;//makes your api chainable
    }
}

Then define all the classes you'll actually be using along these lines:

class DebptorClient extends BaseClient
{
    protected $config = array(//optional
        'wsdl' => 'the specific wsdl',
        'options'=> array()//defaults
    );

    public function get($param, $value)
    {
        $client = $this->getClient();//loads if not yet loaded
        return $client->Debtor_GetData(
            array(
                'entityHandle' => $this->getHandle($param, $value)
            )
        )->Debtor_GetDataResult;
    }
}

And so on.

Now, some actual code-review:

Declare your properties

From the wrapper tag wiki:

  A wrapper is an OOP technique where an object encapsulates (wraps) another object, hiding/protecting the object and controlling all access to it.

By not declaring $this->client, client is effectively added later on in your objects life, which means property lookups will be slower, but more importantly: $this->client will be a public property. If $this->client is public, then you don't have a wrapper because:

  A wrapper [...] encapsulates another object, hiding/protecting the object and controlling all access to it.

Thus, $this->client has to be protected or private.
Next.

Seeing this code worries me:

public function getHandle($param, $value)
{
    switch ($param) {
        case 'number':
            return $this->client->Debtor_FindByNumber(array('number' => $value))->Debtor_FindByNumberResult;
            break;//unreachable statement, btw
        case 'email':
            return $this->client->Debtor_FindByEmail(array('number' => $value))->Debtor_FindByEmailResult;
}

You're expecting the people who are to use your api to know that $param and $value are expected to be. $param has only 2 valid options: number or email. anything else is invalid, yet at no point to you bother to validate the data you're being passed.
When developing an API wrapper, it's not a bad idea to create Argument models:

namespace Soap\Data;
class Argument
{
    private $type = null;
    private $value = null;
    public function __construct($type, $value)
    {
        $setter = 'set'.ucfirst(trim($type));//email becomes setEmail
        if (!method_exists($setter, $this))
        {
            throw new \InvalidArgumentException($type.' is not a valid type for '.__CLASS__);
        }
        $this->{$setter}($value);
    }
    public function setEmail($email)
    {
        if (!filter_var($email, \FILTER_VALIDATE_EMAIL))
        {
            throw new \InvalidArgumentException($email.' is not a valid email address');
        }
        $this->value = $email;
        return $this;
    }
}

This allows you to define methods like this:

public function getByType(Argument $value)

and the Argument class ensures that the data you'll receive is validated properly.

Now, error handling.
That very much depends on how you see your code being used. Is it supposed to be a sort of "module" to be included into various projects, in which case, I'd just throw my exceptions out for the caller to deal with them. Code that is used as a dependency shouldn't have to anticipate all sorts of errors that might occur, that's the users job.

If you want this code to work sort of in the background, You could write your own exceptions (extending from either the base Exception class, or SoapFault) if you wanted to.
You could then register your own exception/error handler and unset/restore the old at lib, and quietly log the exceptions. The user, who will then be left clueless as to what actually went wrong will hate you for this. Having to check the logs constantly is a pain when developing, so add some manual overrides, too

class BaseClient
{
    protected static $exceptions = false;
    public function __construct()
    {
        if (static::$exceptions === false)
        {//static to avoid setting handler more than once
            static::$exceptions = true;
            set_exception_handler(array($this, 'exceptionHandler'));
    }
    public function exceptionHandler(\Exception $e)
    {
        //handle
    }
    public function freeExceptions()
    {
        if (static::$exceptions)
        {
            restore_exception_handler();
            static::$exceptions = false;
        }
    }
    public function __destruct()
    {
        $this->freeExceptions();
    }
}

That's one way of going about your business. Generally, though, I use the occasional try-catch block, if I've created a method that strings together a series of Soap calls, for example, but most of the time I consider Exceptions best handled by the code that invoked the method where the exception is thrown, not by the code that throws the exception.


Parsing large CSV in Perl I am getting Out of Memory errors when I try to parse through a large CSV file (2.5Gb). My computer has 32Gb of Memory but Perl uses all of it up. The CSV has 2 columns.  The first is the time in epoch and the second is a 10000+ line XML file as a single-line. There are around 13k rows. I then use XML::XPath to retrieve the customer name and save the XML to [customername]-[time].xml. If there is an error, it is because the XML is invalid and I skip it.

Is there any way to make my code run more efficiently and look better?

#!/usr/bin/perl

use strict;
use warnings;
use XML::XPath;
use XML::XPath::XMLParser;
use File::Slurp;

my $file = '../FILENAME.csv';
open my $info, $file or die "Could not open $file: $!";
my $count = 0;
$| = 1;

while( my $line = <$info>)  {
    next if ++$count == 1; #Ignore headers
    my ($time, $report) = ($line =~ /(\d+),(.*)$/); # time, XML file
    eval {
        my $xp = XML::XPath->new(xml => $report);
        our $ext = $xp->getNodeText('/report/customer') . "-" . $time . ".xml";
        write_file($ext, $report);
    };
    if ( $@ ) {printf "ERROR ";}
    else {printf "$count ";}
}

close $info;

I am suspicious of this line here:

my ($time, $report) = ($line =~ /(\d+),(.*)$/); # time, XML file

That line needs to scan and group the entire XML doc, but my instinct is that a 2-limited split (see note on LIMIT) would be more efficient:

my ($time, $report) = split /,/, $line, 2;

Apart from that, really, everything looks sane, and far better than a typical perl hack. I am impressed.

About perl using all your memory... are you sure? perl may just be struggling to allocate more than it is allowed. Do you have a ulimit condition that is constraining memory allocation? Are there problems with heavily fragmented memory? (You're not running 32-bit, are you... just checking?)

As it happens, for a task like this, you may find that everything is better with a language other than perl. Not to dismiss perl as incapable, but with the XPath expressions and other items your code looks surprisingly complicated. 2.5gig files are way beyond the normal I would consider for perl performance.


Window-size-dependent content toggler for an HTML form I had to build a responsive component which allows the user to display specific content in a page. I called it the contentToggler.

Here is my component in action

HTML Structure of togglers & contents :
On small screens : <select> with <option>
On big screens :
 containing <buttons>

<select id="paymentMethodSelector">
    <option class="js-card-selector-option" value="Carte bancaire">Carte bancaire</option>
    <option class="js-money-transfer-selector-option" value="Virement">Virement</option>
    <option class="js-check-selector-option" value="Chèque">Chèque</option>
</select>

        <input type="radio" class="js-card-selector-radio" id="radio-checkout-selector-1" checked>
        Carte bancaire

        <input type="radio" class="js-money-transfer-selector-radio" id="radio-checkout-selector-2">
        Virement

        <input type="radio" class="js-check-selector-radio" id="radio-checkout-selector-3">
        Chèque

content1

content2

content3

Associated JS which works however it makes my eyes bleed by its horrifying redundance.

var paymentMethod = {
  selectorOptionWrapper: $('#paymentMethodSelector'),
  card: {
    selectorOption: $('.js-card-selector-option'),
    selectorRadio: $('.js-card-selector-radio'),
    content: $('#paymentCardContent')
  },
  moneyTransfer: {
    selectorOption: $('.js-money-transfer-selector-option'),
    selectorRadio: $('.js-money-transfer-selector-radio'),
    content: $('#paymentMoneyTransferContent')
  },
  check: {
    selectorOption: $('.js-check-selector-option'),
    selectorRadio: $('.js-check-selector-radio'),
    content: $('#paymentCheckContent')
  }
}

function updateCheckoutContent() {
  paymentMethod.selectorOptionWrapper.on('change', function() {
    if(paymentMethod.card.selectorOption.is(':selected')) {
      paymentMethod.card.content.siblings().addClass('u-hide')
      paymentMethod.card.content.removeClass('u-hide');
    }
  });
  paymentMethod.card.selectorRadio.on('change', function() {
    if($(this).is(':checked')) {
      paymentMethod.card.content.siblings().addClass('u-hide')
      paymentMethod.card.content.removeClass('u-hide');
    }
  });

  paymentMethod.selectorOptionWrapper.on('change', function() {
    if(paymentMethod.moneyTransfer.selectorOption.is(':selected')) {
      paymentMethod.moneyTransfer.content.siblings().addClass('u-hide')
      paymentMethod.moneyTransfer.content.removeClass('u-hide');
    }
  });
  paymentMethod.moneyTransfer.selectorRadio.on('change', function() {
    if($(this).is(':checked')) {
      paymentMethod.moneyTransfer.content.siblings().addClass('u-hide')
      paymentMethod.moneyTransfer.content.removeClass('u-hide');
    }
  });

  paymentMethod.selectorOptionWrapper.on('change', function() {
    if(paymentMethod.check.selectorOption.is(':selected')) {
      paymentMethod.check.content.siblings().addClass('u-hide')
      paymentMethod.check.content.removeClass('u-hide');
    }
  });
  paymentMethod.check.selectorRadio.on('change', function() {
    if($(this).is(':checked')) {
      paymentMethod.check.content.siblings().addClass('u-hide')
      paymentMethod.check.content.removeClass('u-hide');
    }
  });
}

updateCheckoutContent(paymentMethod);

What you could do is define in the markup the following:

A data attribute for option to indicate it's a toggle.
A data attribute for radios to indicate it's a toggle.
A data attribute for option to indicate the content it corresponds.
A data attrubute for radios to indicate the content it corresponds.

The data attributes could be selectors or any attribute you can use to target the content.

This way, your script can pick up these elements by class, get their data attribute, and toggle their corresponding contents. This is essentially how Bootstrap allows you to define modals, accordions and such without ever writing scripts. They just look for certain selectors, pick up data, and find the target selectors.

Here's a sample of how the markup would look like:

<select data-component="select-toggle">
  <option value="foo" data-content="#foo">foo</option>
  <option value="bar" data-content="#bar">bar</option>
  <option value="baz" data-content="#baz">baz</option>
</select>

<input type="radio" value="foo" data-component="radio-toggle" data-content="#foo" >
<input type="radio" value="bar" data-component="radio-toggle" data-content="#bar" >
<input type="radio" value="baz" data-component="radio-toggle" data-content="#baz" >

foo

bar

baz

And the script will look like the following. My jQuery is fuzzy at best, but you get the idea:

$('[data-component="select-toggle"]').on('change', function(){
  var contentSelector = $('option:selected', this).data('content');
  $(contentSelector).show().siblings().hide();
});

$('[data-component="radio-toggle"]').on('change', function(){
  var contentSelector = $(this).data('content');
  $(contentSelector).show().siblings().hide();
});


OpenMP parallelization of a for loop with function calls Using OpenMP, is it correct to parallelize a for loop inside a function "func" as follows?

void func(REAL coeff, DATAMPOT *dmp, int a, int la, int b, int lb, REAL L)
{
    int i,j,k;
    REAL dx,dy,dz;
    REAL dx2,dy2,dz2;
    REAL r;

    #pragma omp parallel for default(shared) private(k,i,j,dx,dy,dz,dx2,dy2,dz2,r) reduction(+:deltaE)
    for(k=0; k<la*lb; ++k){
        j=k/la+b;
        i=k%la+a;

        dx=fabs(part[i].x-part[j].x);
        dy=fabs(part[i].y-part[j].y);
        dz=fabs(part[i].z-part[j].z);
        dx2=(dx<0.5?dx*dx:(1-dx)*(1-dx));
        dy2=(dy<0.5?dy*dy:(1-dy)*(1-dy));
        dz2=(dz<0.5?dz*dz:(1-dz)*(1-dz));
        r=L*sqrt(dx2+dy2+dz2);

        deltaE += coeff*((dmp+NSPES*part[i].s+part[j].s)->npot>1?
mpot(r,dmp+NSPES*part[i].s+part[j].s,((REAL)rand())/RAND_MAX):
(dmp+NSPES*part[i].s+part[j].s)->pot[0](r,(dmp+NSPES*part[i].s+part[j].s)->dp ) );

    }

}

Where:

REAL is double (#define REAL double)
DATAMPOT *dmp is a pointer to a struct containing (among others) some pointers to functions, such as pot[0]
part is a global array of struct
deltaE (variable for summation-reduction) is a REAL global variable

I know that, for a correctness, a special treatment of function rand() is also required;
but apart from that, are there some other important (conceptual) correction to do on the above parallelization? Which is limited at only one directive row?

Try to come up with a better function name than func().  You are the one who understands this code the most, so you should know how to give it a relevant name.
Try not to use single-character names, unless they're for a simple for-loop.  It's hard to tell what they're for, especially without comments.  If this ends up making the #pragma line even longer, then you can just split it into separate lines with a \ at the end of each line.
It's a little hard to read lines lacking whitespace:

dx2=(dx<0.5?dx*dx:(1-dx)*(1-dx));

It's difficult to see the entire ternary statement, so add more whitespace:

dx2 = (dx < 0.5 ? dx*dx : (1-dx)*(1-dx));

This concept should be applied everywhere, especially each statement in the loop.

Going back to the ternary, consider using an if/else here instead.  Sure, this is a short ternary, but that doesn't mean it should always be used, especially if it's harder to read carefully.

if (dx < 0.5)
{
    dx2 = dx * dx;
}
else
{
    dx2 = (1-dx) * (1-dx);
}

This formatting is a bit hard to read:

        deltaE += coeff*((dmp+NSPES*part[i].s+part[j].s)->npot>1?
mpot(r,dmp+NSPES*part[i].s+part[j].s,((REAL)rand())/RAND_MAX):
(dmp+NSPES*part[i].s+part[j].s)->pot[0](r,(dmp+NSPES*part[i].s+part[j].s)->dp ) );

At least reformat it to something like this:

deltaE += coeff*((dmp+NSPES*part[i].s+part[j].s)->npot>1
        ? mpot(r,dmp+NSPES*part[i].s+part[j].s,((REAL)rand())/RAND_MAX)
        : (dmp+NSPES*part[i].s+part[j].s)->pot[0](r,(dmp+NSPES*part[i].s+part[j].s)->dp));

However, this may still be too lengthy for a ternary.  You could still use a plain if/else if it would help more with readability.


transform list to array Q: Write a method that transforms a list into an array (don't use
  collections or already implemented methods in lists, make your own
  method)

I've come with this solution:

public static Object[] toArray(List<Object> list) {

    Object[] arr = new Object[list.size()];
    for (int i = 0; i < list.size(); ++i) {
        arr[i] = list.get(i);
    }
    return arr;
}

I've read this Convert a generic list to an array, and seems like they overcomplicated the solution. Why they choose to use generics? Is there something wrong with my approach?

I think, as per your solution, in every case you'll get a list of objects not the list of actual class you need. If you want to use this array you have to cast the object to your desired class. To do that you have to check if you can cast the object to your desired class as the down casting can cause error if you don't use instanceOf.
In short you have to do all this by your self every time you want to use this method for any kind of list. On the other hand the generic code will always return you the array of your class not object.  I think the generic code has 2 advantage over your code which are:

No casting needed
Can be used any where with any kind of list.


Python program to calculate what pawns are safe In chess there are eight rows numbered from 1 to 8 and 8 columns a-h. Pawns which are on the lowest row are always in danger to be captured. The objective of the program is to calculate which pawns are saved.

Given the coordinates of seven pawns return the number of pawns which are safe.

For example:

safe_pawns({"b4", "d4", "f4", "c3", "e3", "g5", "d2"}) == 6
safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e5"}) == 1
safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e3"}) == 2

The code:

def safe_pawns(pawns: set) -> int:
    row_numbers = []
    list_of_pawns = list(pawns)
    letters_string = "abcdefgh"
    safe_pawns_list = []

    #check if there are neighbors which protect you
    for pawn in list_of_pawns:
        if pawn[0] == "a":
            if letters_string[1] + str(int(pawn[1])-1) in list_of_pawns:
                safe_pawns_list.append(pawn)
        elif pawn[0] == "h":
            if letters_string[6] + str(int(pawn[1])-1) in list_of_pawns:
                safe_pawns_list.append(pawn)
        else:
            if ((letters_string[letters_string.index(pawn[0]) + 1] + str(int(pawn[1]) - 1))
            in list_of_pawns):
                 safe_pawns_list.append(pawn)
            elif (letters_string[letters_string.index(pawn[0]) - 1] + str(int(pawn[1]) - 1)
            in list_of_pawns):
                safe_pawns_list.append(pawn)

    #delete the pawns which belong to the lowest row number
    for pawn in list_of_pawns:
        row_numbers.append(pawn[1])

    lowest_row_indexes = []

    for i, row_number in enumerate(row_numbers):
        if row_number == min(row_numbers):
            lowest_row_indexes.append(i)

    for i, lowest_row_index in enumerate(lowest_row_indexes):
        del list_of_pawns[lowest_row_index - i]
        del row_numbers[lowest_row_index - i]

    return len(safe_pawns_list)

How could this be improved?

Playing with the code a bit, give insight in how we can optimize your code.

Unused computation

Note that the following part has no effect on the return value and can be removed:

    #delete the pawns which belong to the lowest row number
    for pawn in list_of_pawns:
        row_numbers.append(pawn[1])

    lowest_row_indexes = []

    for i, row_number in enumerate(row_numbers):
        if row_number == min(row_numbers):
            lowest_row_indexes.append(i)

    for i, lowest_row_index in enumerate(lowest_row_indexes):
        del list_of_pawns[lowest_row_index - i]
        del row_numbers[lowest_row_index - i]

Integer and String conversions

The lookup in the loop is expensive, as each time we convert strings to integers and vice versa. We make a mapping to integer once, prior to the loop.

def safe_pawns(pawns: set) -> int:
    letters_string = "abcdefgh"
    safe_pawns_list = []

    pawns = list(map(lambda x: (letters_string.index(x[0]), int(x[1])), pawns))

    # check if there are neighbors which protect you
    for pawn in pawns:
        if pawn[0] == 0:
            if (letters_string[1], pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
        elif pawn[0] == 8:
            if (letters_string[6], pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
        else:
            if (pawn[0] + 1, pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
            elif (pawn[0] - 1, pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)

    return len(safe_pawns_list)

Using Numpy

The following is less fast (at least for these small amounts of pawns), however the logic is arguably more clear.

def intersect2d(a1, a2):
    # https://stackoverflow.com/questions/8317022/get-intersecting-rows-across-two-2d-numpy-arrays
    rows, ncols = a1.shape
    dtype = {'names': ['f{}'.format(i) for i in range(ncols)],
             'formats': ncols * [a1.dtype]}

    a3 = np.intersect1d(a1.view(dtype), a2.view(dtype))

    # This last bit is optional if you're okay with "C" being a structured array...
    a3 = a3.view(a1.dtype).reshape(-1, ncols)
    return a3

def safe_pawns_np(pawns: set) -> int:
    letters_string = "abcdefgh"

    np_pawns = np.array(list(map(lambda x: (letters_string.index(x[0]), int(x[1])), pawns)))

    safe_spots_right = np_pawns.copy()
    safe_spots_right[:, 0] += 1
    safe_spots_right[:, 1] += 1

    safe_spots_left = np_pawns.copy()
    safe_spots_left[:, 0] -= 1
    safe_spots_left[:, 1] += 1

    safe_spots = np.vstack((safe_spots_right, safe_spots_left))

    return len(intersect2d(np_pawns, safe_spots))


Cumulative counts of items in a Pandas dataframe i'm using a dataframe full of headers/field names to develop a schema and I need unique values for each header - but each header should be represented. I want to loop though the dataframe list of fields and the second time I come across a field name, I want to add an ever increasing number to it. The order is important.

e.g.

headers['name'] =pd.DataFrame['vegetable', 'fruit', 'meat', 'dairy', 'meat', 'fruit', 'fruit']

I need the output to be:

name      | name+count
vegetable | vegetable
fruit     | fruit
meat      | meat
dairy     | dairy
meat      | meat1
fruit     | fruit1
fruit     | fruit2

for header in headers['names']:
       row = headers.loc[headers['names'] == header].index
       if len(row) > 1:
           for i in range(2, len(row)):
               headers['name+count'][row[i]] = headers['names'][row[i]] + str(i-1)
               print(headers['name+count'][row[i]])

You can group by the name and then append an increasing number to it:

import pandas as pd

def add_count(x):
    return x + ([""] + list(map(str, range(1, len(x)))))

df = pd.DataFrame(['vegetable', 'fruit', 'meat', 'dairy', 'meat', 'fruit', 'fruit'],
                  columns=["name"])
x = df.groupby("name", as_index=False)["name"].apply(add_count)
df["name2"] = x.reset_index(level=0, drop=True)
print(df)
#         name       name2
# 0  vegetable   vegetable
# 1      fruit       fruit
# 2       meat        meat
# 3      dairy       dairy
# 4       meat       meat1
# 5      fruit      fruit1
# 6      fruit      fruit2

This avoids manually iterating over rows or columns, something that is usually a good thing when dealing with pandas dataframes.


Edit Distance Implementation I was doing some reading on the Wagner Fischer algorithm algorithm for computing the edit distance on strings. None of the examples in the literature I have read showed how to recover the edit sequences from the final populated matrix. The examples only showed total number of edits.

The logic I am using is simply calling min() on the 4 x 4 submatrix of matrix L that ends L[m][n] until I reach L[0][0]. It seems like the logic should be to compare the value returned by min() and compare it to the current L[i][j] to recover the edit at that position. Then we simply append this to an array that represents the total edit operations and finally reverse the list.

I have tested this code and compared it against the Python Levenshtein module on pypi.org and it looks to be OK. However, I wanted to get some feedback on this methodology of how to output the actual edit sequence. Is there some boundary case I might be missing?

def edit_distance(x, y):

    m = len(x)
    n = len(y)

    L  = [ [0] * (n+1) for i in xrange(m+1) ]

    for i in range(0, m+1):
        L[i][0] = i

    for j in range(0, n+1):
        L[0][j] = j

    for i in range (1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                L[i][j] = L[i-1][j-1]
            else:
                L[i][j] = min(L[i][j-1], L[i-1][j], L[i-1][j-1]) + 1

    edits = []

    i = m
    j = n

    while i > 0 and j > 0:
        back = min(L[i][j-1], L[i-1][j], L[i-1][j-1])
    if back == L[i-1][j-1]:
        if back == L[i][j]:
            edits.append('NOOP')
        elif back == L[i][j] - 1:
                edits.append('SUBST')
        i -= 1
        j -= 1
    elif back == L[i][j-1]:
        edits.append('INSERT')
        j -= 1
    elif back == L[i-1][j]:
        edits.append('DELETE')
        i -= 1

    print x
    print edits[::-1]
    print y

I've written this in python2 because the question is posed in python2. It is advised that users switch over to python3, as it is reaching end-of-life at the end of 2019.

The algorithm

I don't see anything really glaring as far as the algorithm is concerned. The major edge case I can see is with lists/strings of length 1, but you handle that case fine

Pre-allocating your matrix

Without trying to use something like numpy, your pre-allocation step can be simplified a bit. You iterate twice over the whole list, once to fill it with zeros, and once over your respective ranges n and m. The n loop can be done with a simple slice assignment:

# use xrange for initialization here
# that way you aren't allocating a list into memory
L = [[0] * (n + 1) for i in xrange(m + 1)]

# Use a slice to assign the first row
# with a range, since that assigns a list to slice
L[0][:] = range(n + 1)

# then you only have one other for loop to do
# again, just use xrange here
for i in xrange(m + 1):
    L[i][0] = i

i and j

I'm not sure the following step really does anything and is necessary:

i = m
j = n

Furthermore, the while loop is more pythonic if you rely on the truthiness of nonzero integers:

while m and n:
    # do things

while loop

There are continuous index lookups. While lookups by index are fast, doing them over and over impairs readability, even if the penalty incurred is minor

while m and n:
     current, back_y, back_x, back_both = L[m][n], L[m][n-1], L[m-1][n], L[m-1][n-1]
     back = min(back_y, back_x, back_both)
     # rest of loop

Now you can use these as your placeholders for your if logic

while m and n:
    current, back_y, back_x, back_both = L[m][n], L[m][n-1], L[m-1][n], L[m-1][n-1]
    back = min(back_y, back_x, back_both)

    if back == back_both:
        if back == current:
            edits.append('NOOP')
        elif back == current - 1:
            edits.append('SUBST')
        m -= 1
        n -= 1

    elif back == back_y:
        edits.append('INSERT')
        n -= 1

    elif back == back_x:
        edits.append('DELETE')
        m -= 1

Timing

Looking at the timing differences between the two:

original

python -m timeit -s 'from otherfile import edit_distance, revised_edit; x = range(4); y = range(3,7)' 'edit_distance(x, y)'
10000 loops, best of 3: 29.3 usec per loop

revised

python -m timeit -s 'from otherfile import edit_distance, revised_edit; x = range(4); y = range(3,7)' 'revised_edit(x, y)'
100000 loops, best of 3: 10.1 usec per loop

A 65% speedup for small lists. Let's see about (relatively) larger ones

original

python -m timeit -s 'from otherfile import edit_distance, revised_edit; x = range(400); y = range(300,700)' 'edit_distance(x, y)'
10 loops, best of 3: 152 msec per loop

revised

python -m timeit -s 'from otherfile import edit_distance, revised_edit; x = range(400); y = range(300,700)' 'revised_edit(x, y)'
1000 loops, best of 3: 1.31 msec per loop

The difference is starting to diverge, two entire orders of magnitude here. Whether or not you would use this on large lists is I suppose an implementation detail, but worth a look. Not to imply that a 400 element list is big, but it's an improvement for sure.

The timing does not include the time required to reverse edits using a edits[::-1] because that is going to be a constant, and looking at slicing a 400 element list in this way, the time is insignificant compared to the rest of the algorithm (1000000 loops, best of 3: 0.967 usec per loop for range(400), if you were curious).

return edit

You never return edits! print does not return. It's also advisable to change print val to print(val), as the latter is portable across python 2 and 3, and it's recommended you be on python3 already anyways. So at the end of your function, be sure to include:

    return edits[::-1]


Buy once and sell once for maximum profit Suppose we have stock price history, and we are allowed to buy only once and sell only once. The problem is to find the maximum profit we can make. Here is my code that I tested for basic test cases. I'm wondering if there are possible improvements for logic correctness.

My major idea is to keep record of in history minimal price, and determine if sell today (with the purchase of historical minimal price), whether we can make a larger profit.

prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
result = 0
minSofar = prices[0]
for i in range(1, len(prices)):
    minSofar = min(minSofar, prices[i])
    result = max (result, prices[i] - minSofar)

print result

profit would be a better name than result.

This could be simplified to a one-liner using itertools.combinations()

profit = max(sell - buy for buy, sell in itertools.combinations(prices, 2))


Polyglot function to sum all the numbers in an array in Javascript and PHP This, again, is a very simple code.

This is my 2nd polyglot question and this time I've tried to do something that I miss sometimes in Javascript.

PHP has the array_sum() function, but Javascript has no direct equivalent.

So, I decided to make one that works with both languages!

Here is the code:

function sum_array()
{
    if( $javascript = '\0' == "\0" )
    {
        $vars = new Object();
        $vars['args'] = arguments;
        $vars['l'] = arguments.length;
    }
    else
    {
        $vars = Array();
        $vars['args'] = func_get_args();
        $vars['l'] = func_num_args();
    }

    for( $vars['sum'] = $vars['i'] = 0; $vars['i'] < $vars['l']; $vars['i']++ )
    {
        $vars['m'] = $javascript ? $vars['args'][$vars['i']].length : count($vars['args'][$vars['i']]);

        for( $vars['j'] = 0; $vars['j'] < $vars['m']; $vars['j']++ )
        {
            $vars['sum'] += ( $vars['args'][$vars['i']][$vars['j']] / 1 ? $vars['args'][$vars['i']][$vars['j']] : 0 );
        }
    }

    return $vars['sum'];
}

Usability is really easy:

Simply pass multiple arrays as arguments. In PHP, it is required to be an array with only numeric keys. This is due to the limitations of Javascript.

Example of usage:

sum_array([1,2,3,4,5],[15]); //should return 30 in Javascript and PHP 5.4+

To avoid 'poisoning' the window object, I only created 2 variables and use one of them as an array (The other is just to save if we are running in Javascript or PHP).

Was this a good decision?

What else can I improve on my code?

Interesting question.

You are trying to avoid poisoning the window object.. Now consider writing several functions like this. You just moved the poisoning from window to $vars. I would not do this because it reduces readability a lot.

$vars['args'][$vars['i']] should be in a helper variable to increase readability. (Regardless of whether you keep $vars)

I would have put this in a function called get_array_length:
$javascript ? $vars['args'][$vars['i']].length : count($vars['args'][$vars['i']]);

Then I would change the top to

if( $javascript = '\0' == "\0" )
{
    $vars = new Object();
    $vars['args'] = arguments;
}
else
{
    $vars = Array();
    $vars['args'] = func_get_args();
}
$vars['l'] = get_array_length($vars['args'])

Still, all in all because you need to maintain compatibility this is okay as an art excercise but this is by no means (because of  it's nature) production or high quality code.