Bash script to deploy a mongodb cluster on local machine I recently wrote a small script to deploy a mongodb cluster on a single machine.
The cluster is composed of :

3 configurations server that holds the same informations (they are replicas )
2 shard server wich will store the data
one mongos which manage connection to the cluster

The script parse a configuration file holding the cluster configuration,
and then starts the different member in a specific order.

Here is the config file:

#config file to store host and port

#config server list, in folowing format:
# config=<host>:<port>
# started with --dbpath /data/configX where
# X is the position of the server in the list
config=localhost:27018
config=localhost:27019
config=localhost:27020

#mongos instance in folowing format:
# mongos=<host>:<port>
mongos=localhost:27017

#shard list in folowinf format:
# shard=<host>:<port>
# started with --dbpath /data/shardX where
# X is the position of the shard in the list
shard=localhost:27021
shard=localhost:27022

and here is the script:

#!/bin/bash

# this script should be launched on the server where you want the
# mongos to run. It should be run like this:
# ./deploy.sh path/to/config.txt

# make sure that mongod, mongos and mongo are linked correctly
# you can achieved this using the following command:
# sudo ln -s /path/to/mongo/bin/mongo /bin/mongo

# host:port for config server
CONFIG=()
# host:port for shards
SHARD=()

# text colors
red=`tput setaf 1`
green=`tput setaf 2`
reset=`tput sgr0`

# clear log file
echo "" > log.txt

# ignore empty or comment line
sed '/^#/d;/^$/d' $1 |
{
while read -r line
do

    IFS='=' read -a array <<< "$line"
    val="${array[1]}"
    key="${array[0]}"

    if [ "$key" == "config" ]; then
        CONFIG+=("$val")
        echo "mongod config server: $val"
    fi
    if [ "$key" == "mongos" ]; then
        MONGOS="$val"
        echo "mongos instance: $val"
    fi
    if [ "$key" == "shard" ]; then
        SHARD+=("$val")
        echo "shard instance: $val"
    fi
done
#start config servers
index=0
for conf in "${CONFIG[@]}"
do
    # ping each host to make sure it's reacheable
    IFS=':' read -a config <<< ${CONFIG[$index]}
        mkdir /data/config$index
        echo "starting config server $index"
    mongod --configsvr --port ${config[1]} --dbpath /data/config$index --replSet conf > log.txt&
    index=$(($index + 1))
    sleep 1
done

sleep 10
echo "${green}config servers deployed${reset}"
# setup the config replica set. Only neccessary on first launch
IFS=':' read -a config0 <<< ${CONFIG[0]}
mongo --host ${config0[0]} --port ${config0[1]} --eval "rs.initiate( { _id: \"conf\", members: [ {_id: 0, host:\"${CONFIG[0]}\"}, {_id: 1, host:\"${CONFIG[1]}\"}, {_id: 2, host:\"${CONFIG[2]}\"} ]})"&

# sleep so a primary shard can be designed among config servers
sleep 15
# get mongos infos
IFS=':' read -a mongos <<< $MONGOS
#start mongos
mongos --port ${mongos[1]} --configdb "conf/${CONFIG[0]},${CONFIG[1]},${CONFIG[2]}" > log.txt&

echo "${green}mongos instance configured${reset}"

sleep 5
# start each shard and add them to the cluster
shardnb=0
for shard in "${SHARD[@]}"
do
        IFS=':' read -a sh <<< ${SHARD[$shardnb]}
        mkdir /data/shard$shardnb
        echo "starting shard $shardnb"
    mongod --shardsvr --port ${sh[1]} --dbpath /data/shard$shardnb > log.txt&
        sleep 5
        mongo --host ${mongos[0]} --port ${mongos[1]} --eval "sh.addShard(\"$shard\");"&
    sleep 5
    shardnb=$(($shardnb + 1))
    echo "${green}shard  $shard added${reset}"
done

# make sure that the sharded cluster has been deployed correctly
mongo --host ${mongos[0]} --port ${mongos[1]} --eval "sh.status();"
}

I use this to quickly deploy a cluster in a docker container in order to run automated integration test.
As this is one of my first bach script, I'm looking for advises on style / readability !

To begin with, I agree with Jesse_b that command substitution should use $(). There's no reason to use backticks in a bash script that uses arrays (that's to say, you're not particularly aiming for portability with some obscure shell).

Indentation

I didn't notice until the end of the script that the majority of your code is in a {...} block. Indenting that portion of the code more than the braces would have helped.

Reading the config file

Continuing from the previous point, the majority of your code seems to be in the block because of the pipe used for reading the file.

Avoid the pipe

You can use process substitution to avoid the pipe:

while read -r line
do
...
done < <(sed '...' file)

This way, you eliminate the pipe and the need to keep most of your code in a subshell. You can also make the comments more friendly by allowing leading spaces:

sed '/^[[:space:]]*#/d;/^[[:space:]]*$/d'

Or:

sed '/^[[:space:]]*\(#.*\)\?$/d'

Eliminate unnecessary reads and variables

That said, the code for reading the lines seems to be unnecessarily convoluted: a read first and then again to split? Why not do it in one op? You also use an array, then immediately proceed to assign the array elements to two named variables and thereafter ignore the array completely. Just set those variables via read directly;

while IFS='=' read -r key value
do
...
done < <(sed '/^[[:space:]]*\(#.*\)\?$/d' file)

Bug, again, later on you split the values read here, because they are all host-port pairs. If so, then do the splitting now, and save them in separate arrays in the first place:

declare -a CONFIG_HOSTS CONFIG_PORTS SHARD_HOSTS SHARD_PORTS
while IFS='=:' read -r key host port
do
...
done < <(...)

Repetitive if statements

Next, the chain of ifs are so repetitive that I suggest taking out the echos, by making an array out of the labels you print:

declare -A key_labels
key_labels["config"]="mongod config server"
key_labels["mongos"]="mongos instance"
key_labels["shard"]="shard instance"

Then, a single printf should do. And the block of ifs also look like they fit the role of a case statement. So:

printf '%s: %s:%s\n' "${key_labels[$key]}" "$host" "$port"
case key in
config)
    CONFIG_HOST+=("$host")
    CONFIG_PORT+=("$port")
    ;;
mongos)
    MONGOS_HOST="$host"
    MONGOS_PORT="$port"
    ;;
shard)
    SHARD_HOST+=("$host")
    SHARD_PORT+=("$port")
    ;;
esac

So, the entire config reading section becomes:

declare -a CONFIG_HOSTS CONFIG_PORTS SHARD_HOSTS SHARD_PORTS
declare -A key_labels
key_labels["config"]="mongod config server"
key_labels["mongos"]="mongos instance"
key_labels["shard"]="shard instance"

while IFS='=:' read -r key host port
do
    printf '%s: %s:%s\n' "${key_labels[$key]}" "$host" "$port"
    case key in
    config)
        CONFIG_HOSTS+=("$host")
        CONFIG_PORTS+=("$port")
        ;;
    mongos)
        MONGOS_HOST="$host"
        MONGOS_PORT="$port"
        ;;
    shard)
        SHARD_HOSTS+=("$host")
        SHARD_PORTS+=("$port")
        ;;
    esac
done < <(sed '/^[[:space:]]*\(#.*\)\?$/d' file)

Looping with an index

Here, since you need the indices for creating the directories, you can just ask bash for the indices directly. Instead of:

index=0
for conf in "${CONFIG[@]}"
do
...
    index=$(($index + 1))
done

Do:

for index in "${!CONFIG_HOSTS[@]}"
do
    mkdir /data/config"$index"
    echo "starting config server $index"
    mongod --configsvr --port "${CONFIG_PORT[index]}" --dbpath /data/config"$index" --replSet conf > log.txt &
    sleep 1
done

Other notes on this block:

Note how I eliminated the IFS=: read ... and replaced "${config[1]}" with "${CONFIG_PORT[index]}", which immediately makes the meaning of that variable clearer.
The indentation was mixed up, both in this and the other loop. Be consistent.
The echo "" > log.txt from earlier was unnecessary, since you use > log.txt here, the file will be truncated anyway.
You are losing the output from all but the last mongod process, since you use > instead of >>.
Always quote your variables.

This index method can be applied to the other loop as well. Also, every instance of IFS=: read ... <<<"$foo" can now be eliminated, and the resultant variables replaced with the arrays we created earlier, as shown in point 1 above. So, things like config0[1] become ${CONFIG_PORT[0]}.


Still pulling information from XML to insert into Word Document inside 3rd party application Follow up to This Question

I took some very good advice and changed my code around a little bit and eliminated some If statements.

I am not retrieving very much information but it looks so skinny now.

Is this a good thing?  Is there something that I should add to the code?

Dim phoneNode
Dim phoneNodeList
ReturnData = ""

Set phoneNodeList = XmlDoc.SelectNodes("/Record/Case/CaseFormsLoad/PartyLoad/Party/PartyPhones/Phone")
If phoneNodeList.Length > 0 Then
    For Each phoneNode In phoneNodeList
        If phoneNode.GetAttribute("ConfidentialFlag") = "True" Then
            ReturnData = ReturnData & phoneNode.Getattribute("PhoneNum") & VbCrLf
        End If
    Next
End If

This code is very readable and simple.  Is there anything that I can do to make it shorter, and should I make it shorter?  it is a Script and not a fully compiled code.

I see one point that seems almost obvious enough that I'm worried I might be missing something. A For Each is "smart" enough that its body isn't executed at all for an empty collection, so you can eliminate the test for the list having a length of 0:

Dim phoneNode
Dim phoneNodeList
ReturnData = ""

Set phoneNodeList = XmlDoc.SelectNodes("/Record/Case/CaseFormsLoad/PartyLoad/Party/PartyPhones/Phone")
For Each phoneNode In phoneNodeList
    If phoneNode.GetAttribute("ConfidentialFlag") = "True" Then
        ReturnData = ReturnData & phoneNode.Getattribute("PhoneNum") & VbCrLf
    End If
Next


Cleaning up a rotating image gallery I have created a nice little image gallery for the web. I set out wanting 3 things. 1. The whole gallery had a basic level responsiveness to it. 2. The gallery would take images of any size, and display them without cropping. 3. The gallery would run automatically. If you look here(JSFiddle) I have done just that. The automatic slide show is just a small bit of jQuery.

setInterval(function () {
  $(".image_background").last().animate({
        left: '-=1000'
        }, 1000, 'swing', function() {
          var top_element= $(this).detach();
          top_element.css({"left": 0});
          $(".image_gallery").prepend(top_element);
    })}, 2000);

I am quite happy with it. It's the css bit that I am not so sure about.

.main_image_gallery{
  display: inline-block;
  position: absolute;
  height: 50%;
  width: 30%;
  z-index: 2;
  top: 30%;
  left: 3%;
  background-color: #4e9ba1;
  box-sizing: border-box;
  overflow: hidden;
}
.image_background{
  background-color: #4e9ba1;
  display: inline-block;
  position: absolute;
  height: 100%;
  width: 100%;
}
.gallery_image{
  margin: auto;
  position: absolute;
  top: 0; left: 0; bottom: 0; right: 0;
  max-width: 100%;
  max-height: 100%;
}

For reference, here's the HTML

I feel like there is a simpler way to do it. Any thoughts on how I can clean it up, maybe improve the responsive aspects?

For the css part, I started from the updated fiddle @cimmanon provided. I basically agree with all the things he added. I also went ahead and turned your markup into a ul as he (or she) correctly suggested. I would like to provide my own insights as well:

You are closing your img tags, however they can never contain any content so the closing tags are redundant (and perhaps even invalid). You can either make them self-closing (<img ... />) or just omit them in html5.
You are using a lot of different classes in your markup. There is no real need for that; all it does is make your code longer and harder to read. I would go for selectors like .image-gallery img instead of .gallery_image. I admit that in theory this is slightly less performant, but I doubt you'll be able to see, or even measure, the difference. And it makes your markup a lot easier to maintain (less code when adding slides, and less chance of making typos in all those class names).
I would definitely not animate the left property, but go for a transform: translate3d in stead. It is a lot better for performance as explained here.
I would use css transitions, instead of the jQuery animate. It is again better for performance, and it I believe it makes your code a lot better structured. If you decide to change anything in your animation, you just have to update your css and you don't have to start digging into your javascript. I'm a big fan of only using Javascript for thing that can't be done through css.

I went ahead and applied my suggestions to the fiddle, which you can find here: http://jsfiddle.net/eL0vaL44/3/


Find every possible pair of numbers that sum up to n number I have this following code which find every possible pair of numbers that sum up to n number

lst = [int(input()) for i in range(int(input()))]
num = int(input()) #Amount to be matched
cnt = 0
lst = list(filter(lambda i: i <= num, lst)) #Remove number that more than `num`
for i in lst:
    for j in lst:
        if i+j == num:
            cnt += 1
print(int(cnt/2))

For example, if I enter

5 #How many numbers
1 < #Start of number input
4 <
5
7
1 < #End of number input
5 #Amount to be matched

It will return 2 because there is two pair that their sum is equal to 5 (1,4) and (4,1) (The number I marked with < ).

The problem is the complexity is O(n2) which will run slow on large input. I wanted to know if that is there a way to make this run faster?

Another example:

10 #How many numbers
46 #Start of number input
35
27
45
16
0 <
30 <
30 <
45
37 #End of number input
30 #Amount to be matched

The pair will be (0, 30) and (0, 30) which will return 2.

Removing numbers greater than the target affects the correctness of this program - they could be added to negative numbers to reach the target.

You could get a performance improvement by finding the difference between each element and the target, then looking to see if that difference is in the list.  This doesn't in itself reduce the computational complexity (it's still O(n²)), but we can build on that: if the list is first sorted, and we then use a binary search to test membership we get to O(n log n); if we convert to a structure with fast lookup (such as a collections.Counter, which has amortized O(1) insertion and lookup), then we come down to O(n).

If we have a Counter, then we can account for all combinations of that pair by multiplying one count by the other (but we'll need to consider the special case that the number is exactly half the target).

We could do with some auto tests.  Consider importing the doctest module and using it.  Some good test cases to include:

1, [] → 0
1, [1] → 0
1, [0, 1] → 1
0, [-1, 1] → 1
0, [0, 1] → 0
4, [1, 4, 3, 0] → 2
4, [1, 1, 3, 3] → 4
4, [2, 2, 2, 2] → 6


Finding the prime factors of a positive number I have an assignment to write on the standard output the prime factors of a positive number displayed in ascending order and separated by '*'. My code works, but I need help reviewing it before I submit my work. Allowed functions: write, printf, atoi.

void    find_factors(int n)
{
    int i;
    int separated;

    i = 3;
    separated = 0;
    if (n <= 1)
        return ;
    while (n % 2 == 0)
    {
        if (separated)
            printf("*");
       printf("%d", 2);
       separated = 1;
        n = n / 2;
    }
    while (i <= n)
    {
        while(n % i == 0)
        {
            if (separated)
                printf("*");
            printf("%d", i);
            separated = 1;
            n = n / i;
        }
        i += 2;
    }
    if (n > 2)
    {
      if (separated)
            printf("*");
      printf("%d", n);
    }
}

1) The reasons for 2 loops while (n % 2 == 0) and while (i <= n) is to optimize division by 2 and allow the next prime candidate to be found with += 2.

As printing is a sink-hole of time, these small savings could be ignored and code changed to one loop.

int i = 2;
while (i <= n) {
   while(n % i == 0) {
      ...
      printf("%d", i);
      separated = 1;
      n = n / i;
   }
   i += i==2 ? 1 : 2;
}

2) Negative numbers are a problem and not well supported here, nor do they need to be.  Recommend unsigned than int.

3) As an alternative to a flag and repeated test code for the "*", perhaps

char *separator = "";
...
while (...) {
   printf("%s%d", separator, 2);
   separator = "*";
   ...
}

4) Code fails for the following.  OP did say "prime factors of a positive number", so 0 and negative numbers are excusable to some degree.

  find_factors(INT_MAX);  // infinite loop
  find_factors(1);        // no output
  find_factors(0);        // infinite loop
  find_factors(negative)  // no output

5) Initialize at the same time as declaration.

// int i;
// int separated;
// i = 3;
// separated = 0;
int i = 3;
int separated = 0;

6) Consider bool for boolean variables

#include <stdbool.h>
// int separated = 0;
bool separated = false;

7) Wavy formatting

    if (separated)
        printf("*");
   printf("%d", 2);
   separated = 1;
    n = n / 2;

8) Careful passing a string to printf() as a format string as it might someday contain %.

// printf("*");
fputs("*", stdout);
// or
fputc('*', stdout);
//
putchar('*');

// OP did say  "write, printf, atoi.", so could use the following, which is a bit pedantic.
printf("%s", "*");

9) Efficiency.  For large values of n, code does n/2 loops.  Better to terminate at about the sqrt(n).  At n % i time, also calculate qu = n / i.  This can often be had for free, depending on the processor.  Once i>qu, code is done.


Getting rid of extra test during initialization of loop/recursion I'm reluctant to ask this question.  My code below works, it's intelligible, and it seems reasonably efficient.  It's just that there's a trivial, nitpicky issue that's driving me crazy.  The function maxes below collects all elements of a sequence that are "maximum" according to some criterion.

;; Example of use of maxes
;; Collect all maps with the maximum value for `:a`:
(maxes :a [{:a 1 :b 2} {:a 4 :b 5} {:a 5 :b 5} {:b 3 :a 5}])
;;=> [{:b 5, :a 5} {:b 3, :a 5}]

(defn- maxes-helper
  "Helper function for maxes."
  [f s best-val collected]
  (if (empty? s)
    collected
    (let [new-elt (first s)
          new-val (f new-elt)]
      (cond (== new-val best-val) (recur f (rest s) best-val (conj collected new-elt))
            (>  new-val best-val) (recur f (rest s) new-val  [new-elt])
            :else                 (recur f (rest s) best-val collected)))))

(defn maxes
  "Returns a sequence of elements from s, each with the maximum value of (f element)."
  [f s]
  (if (empty? s)
    nil
    (let [new-elt (first s)
          new-val (f new-elt)]
      (maxes-helper f (rest s) new-val [new-elt]))))

What's really bugging me that I have to test for emptiness of the input collection s both in the top-level function and in the tail-recursive helper function.  I also want to add a custom exception when (f new-elt) is non-numeric, and so I need to test that twice, both for new-val and for first call to (f new-elt) that becomes the first best. So I've got a trivial amount of duplication of code, and I keep thinking that there must be a way to get rid of the duplication.  But I can't see how to do this (without testing that best is numeric on every iteration).  Am I missing something obvious (or non-obvious)?

(BTW I wrote another version using reduce, but it's about twice as slow, according to Criterium.)

You don't really need the helper function, the original maxesis pretty much equivalent to call maxes-helper with a sensible MIN_VALUE and empty sequence, so I refactored and joined both for you leveraging multi-arity

   (defn maxes
      "Returns a sequence of elements from s, each with the maximum value of (f element)."
      ([f s]
       (maxes f s Double/NEGATIVE_INFINITY '()))
      ([f s best-val collected]
      (if (empty? s)
        collected
        (let [new-elt (first s)
              new-val (f new-elt)]
          (cond (>  new-val best-val) (recur f (rest s) new-val  [new-elt])
                (== new-val best-val) (recur f (rest s) best-val (conj collected new-elt))
                :else                 (recur f (rest s) best-val collected))))))

Edited to replace nil by Double/NEGATIVE_INFINITY as suggested by @fmikes


Is there a route to the end of the jump table? I'm currently learning about Dynamic Programming and solving a "coding question" related to the topic.

Given an array of non-negative integers, you are initially positioned
at the first index of the array.
Each element in the array represents your maximum jump length at that
position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Example 2:
Input: [3,2,1,0,4]
Output: false

Here's my code:
    def canJump(nums: List[int]) -> bool:
        memo = {len(nums) - 1: True}
        def canJumpPos(pos):
            if pos >= len(nums):
                return False
            elif pos in memo:
                return memo[pos]
            else:
                for i in range(nums[pos], 0, -1):
                    if canJumpPos(i + pos):
                        return True
                memo[pos] = False

        return canJumpPos(0)

I'm having trouble reasoning about the time/space complexity of my approach. My understanding is that without memoization, this approach would be exponential. But, with memoization, this becomes a linear time algorithm? Is this correct? How would you recommend I calculate time complexity in the future when I'm dealing with dynamic programming?

All paths do not return

    def canJumpPos(pos):
        if pos >= len(nums):
            return False
        elif pos in memo:
            return memo[pos]
        else:
            for i in range(nums[pos], 0, -1):
                if canJumpPos(i + pos):
                    return True
            memo[pos] = False
            # Missing Return

This means canJump([3,2,1,0,4]) returns None, not False!  A violation of your declared -> bool return.

No memoization of True

When this code returns True:

                if canJumpPos(i + pos):
                    return True

memo[pos] is never set to True.  This means that if canJumpPos(pos) is called called with the same pos value, it will have to redo all the work it has already done to return the same True value!

Eschew offset additions, assiduously

            for i in range(nums[pos], 0, -1):
                if canJumpPos(i + pos):

Here, you are always using i + pos, never i by itself.
Instead of repeating this addition over and over again,
you could roll that addition into the range() end-points.

            for i in range(nums[pos] + pos, pos, -1):
                if canJumpPos(i):

Any and All

Looping over some condition until you find a True condition:

            for i in range(nums[pos] + pos, pos, -1):
                if canJumpPos(i):
                    return True
            # ...

is often better performed using any(...):

            if any(canJumpPos(i) for i in range(nums[pos] + pos, pos, -1)):
                return True
            # ...

The any(...) will terminate when the first True is found, and return True.  If no True value is found, it will return False.

There is a similar function all(...), which will terminate at the first False returning False.  If no False value is found, it returns True.


Modify singly linked list such that all even numbers appear before odd numbers I want to improve this code using STL or with better logic. I have not written code for delete function or for copy constructor or move constructor. My aim to learn to exchange even and odd elements.

#include <iostream>
#include <utility>
#include <cassert>

class LinkedList
{
  struct Node
  {
    int data;
    Node * next = nullptr;
    Node(int value)   : data(std::move(value)), next(nullptr) {}
  };
  Node *head;

public:
  LinkedList() : head(nullptr) {}
  ~LinkedList()
  {
    Node *tmp = nullptr;
    while (head)
    {
      tmp = head;
      head = head->next;
      delete tmp;
    }
    head = nullptr;
  }

  void insert(int);
  void exchangeEvenOdd();
  void printList() const;

private:
  static void advance(Node*& node)
  {
    assert (node != nullptr);
    node = node->next;
  }

  Node* getLastNode()
  {
    Node *node = head;
    while (node->next != nullptr)
           node = node->next;

    return node;
  }

  bool isOdd(int num)
  {
    if (num % 2 != 0)
        return true;
    else
        return false;
  }
};

void LinkedList::insert(int value)
{
 Node *node = new Node(std::move(value));
 Node *tmp = head;
 if (tmp == nullptr)
 {
   head = node;
 }
 else
 {
   tmp = getLastNode();
   tmp->next = node;
 }
}

void LinkedList::exchangeEvenOdd()
{
  Node *node = nullptr;
  Node *lastNodeToTest = getLastNode();
  Node *tail = lastNodeToTest;

  while (isOdd(head->data) == true)
  {
    node = head;
    advance(head);
    tail->next = node;
    advance(tail);
  }

  Node *tmp = head;
  Node *curr = head;

  while (tmp->next != lastNodeToTest)
  {
    if (isOdd(curr->next->data) == true)
    {
      node = curr->next;
      curr->next = node->next;
      tail->next = node;
      advance(tail);
    }
    else
    {
      //advance "curr" and "tmp" only when next node to it is even
      advance(curr);
      advance(tmp);
    }
  }

  if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
  {
    node = lastNodeToTest;
    curr->next = lastNodeToTest->next;
    tail->next = lastNodeToTest;
    advance(tail);
  }
  tail->next = nullptr;
  lastNodeToTest = nullptr;
  node = nullptr;
}

void LinkedList::printList() const
{
  if (head == nullptr)
  {
    std::cout << "Empty List \n";
    return;
  }

  Node *node = head;

  while (node != nullptr)
  {
    std::cout << node->data << " ";
    advance(node);
  }

  std::cout << "\n";
}

int main()
{
  LinkedList ll1;
  ll1.insert(1);
  ll1.insert(2);
  ll1.insert(3);
  ll1.insert(4);
  ll1.insert(5);
  ll1.insert(6);
  ll1.insert(7);
  std::cout << "Original List : ";
  ll1.printList();

  ll1.exchangeEvenOdd();
  std::cout << "New List : ";
  ll1.printList();
}

There are two different things in your code: an implementation of a single-linked list, and an algorithm to make even numbers appear before odd numbers in a list.

Optimally, those two concerns should be separated. It is easier to do one thing well, so your list should focus on providing data management services (inserting, deleting, data access, memory safety, etc.) and your algorithm should use those services to accomplish its task of reordering elements. If you do so, your list's interface will be more concise and your algorithm more general.

The algorithm you're writing is actually a partitioning algorithm, that is one that puts elements satisfying a predicate before elements that don't. It's used in sorting algorithms for example. You can find the following implementation in the reference:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last) return first;

    for(ForwardIt i = std::next(first); i != last; ++i){
        if(p(*i)){
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

You can see from this example implementation that you only need a way to iterate over the elements in your list one after the other, and a way to extract the value at a current position, to make your list interface powerful enough.

The hard but correct way to provide this interface is to provide an iterator class, and two iterator instances, begin and end. Then your list is fully compatible with most STL algorithms (some of them require more powerful iterators than those a single-linked list can expose) and you don't even need to implement the partition algorithm.

The quick and dirty way is to implement the algorithm directly on top of your list's nodes, given that they provide the two necessary functionalities via data and next.

P.S: your exchangeEvenOdd function should return the partition point. It's a valuable information that you have to compute anyway. By the way, the name could be more evocative.


How do I optimize this Java cube root function for BigInteger? I find that this function is one of the biggest causes of slow program execution. I can write a square root version with BigInteger only, but with the cube root, the algorithm sometimes gets caught in an endless loop unless I also use BigDecimal, because the values of r and s never reach equilibrium. I've already used tricks like leftShift to multiply by 2 and s.multiply(s) in place of s.pow(2) to make it faster, but having to use BigDecimal is still slowing it down. Any idea how I could approach this problem?

public static BigDecimal THREE_D=BigDecimal.valueOf(3);

public static int UP=BigDecimal.ROUND_HALF_UP;

// other statements

public static BigInteger cbrt(BigInteger n)
{
 BigDecimal m=new BigDecimal(n);                          // BigDecimal copy
 BigInteger r=BigInteger.ZERO.setBit(n.bitLength()/3);    // initial estimate
 for(BigDecimal s=BigDecimal.ZERO;                        // different from r
     !r.equals(s.toBigInteger());                         // loop test: does r=s?
     s=new BigDecimal(r),r=new BigDecimal(r.shiftLeft(1)) // Convert to BigDecimal,
      .add(m.divide(s.multiply(s),UP))                    // do the tricky division,
      .divide(THREE_D,UP).toBigInteger());                // and convert back.
 return r;                                                // return the value
}

Edit: Followup to this question can be found here.

Your current code is totally unreadable and very hard to understand.
For vs. While
You've literally packed everything inside a for-loop without a body. WHY!?
This would be a lot more readable using a while-loop.
BigDecimal s = BigDecimal.ZERO;
while (!result.equals(s.toBigInteger())) {
    s = new BigDecimal(result);

    // Convert to BigDecimal, do the tricky division,
    // and convert back.
    BigDecimal temp0 = new BigDecimal(result.shiftLeft(1));
    BigDecimal temp1 = temp0.add(valueCopy.divide(s.multiply(s), UP));
    BigDecimal temp2 = temp1.divide(THREE_D, UP);
    result = temp2.toBigInteger();
    iterations++;
}

The temp0, temp1, and temp2 stuff can be written on one line, but I thought it deserved to be broken up among a few lines to be more readable.

Comments
Some unnecessary comments:
// other statements
// BigDecimal copy
// return the value

Please don't add comments about what you're doing, add comments for explaining why you are doing it. The code often tells us what you're doing.
Explaining what you're doing is OK for totally non-understandable parts though, these comments are helpful:
// Convert to BigDecimal,
// do the tricky division,
// and convert back.

Variable names
BigDecimal s;
BigInteger r;
BigDecimal m;

Please don't use one-letter variable names!
Explain what you're variable name is used for r seems to be for result, which is a much better variable name than r. I don't understand what s and m are used for exactly so I can't come up with a better name for those. Admittedly, my tempX names used above are also bad names, I hope you can come up with better ones.

Another approach:
Your code is already faster than anything I would be able to write by hand. I don't know if you're aware of it already or not, but there is however an in-built Java method you can use for this job - If you're willing to drop some precision for huge numbers.
I tried to compute the cubic root of 4.781260832191688e49
One in-built method call returns 3.6295056667577016E16.
Your code returns 36295056667577090
So there's a difference of 74, for a number of the order 4*10^49 I think that's pretty good.
The correct result with a lot of precision is:
3.6295056667577090244467986066615526182629927485862843007... × 10^16

So what's the secret method call then you ask?
Math.pow(4.781260832191688e49, 1.0 / 3.0);


Powershell Interaction with Excel (Highlighting Cells) I'm using Powershell to compare two, large csv files and output the rows which don't match.  Once the two output files are made (one for the differences on each), I bring them up on Excel.  Now I want to highlight the mismatching fields for the output to be easily read by my customer.  Starting where I open the files in Excel, my current code is:

$excel= New-Object -ComObject "excel.application"
$excel.Visible=$true
$ocomp1=$excel.Workbooks.Open("C:\Users\aja3885.BUD\Desktop\agclink-data-mining\agclink-data-mining\test1.csv")
$ocomp2=$excel.Workbooks.Open("C:\Users\aja3885.BUD\Desktop\agclink-data-mining\agclink-data-mining\test2.csv")
$comp1=$ocomp1.worksheets.item(1)
$comp2=$ocomp2.worksheets.item(1)
$Row=$comp1.UsedRange.rows.count
$Column=$comp1.UsedRange.columns.count
$comp1.UsedRange.EntireColumn.AutoFit()|out-null
$comp2.UsedRange.EntireColumn.AutoFit()|out-null
$i=1
for($i=2; $i -le $row; $i++)
{if($comp1.cells.item($i,1).value2 -eq 'pntval'){if($comp1.cells.item($i,8).value2 -eq 'VALUTYPE=1'){$comp1.cells.item($i,4).interior.colorindex=3} elseif($comp1.cells.item($i,8).value2 -eq 'VALUTYPE=2'){$comp1.cells.item($i,6).interior.colorindex=3} elseif($comp1.cells.item($i,8).value2 -eq 'VALUTYPE=3'){$comp1.cells.item($i,5).interior.colorindex=3} elseif($comp1.cells.item($i,8).value2 -eq 'VALUTYPE=4'){$comp1.cells.item($i,7).interior.colorindex=3}}}

for($i=2; $i -le $row; $i++)
{if($comp2.cells.item($i,1).value2 -eq 'pntval'){if($comp2.cells.item($i,8).value2 -eq 'VALUTYPE=1'){$comp2.cells.item($i,4).interior.colorindex=3} elseif($comp2.cells.item($i,8).value2 -eq 'VALUTYPE=2'){$comp2.cells.item($i,6).interior.colorindex=3} elseif($comp2.cells.item($i,8).value2 -eq 'VALUTYPE=3'){$comp2.cells.item($i,5).interior.colorindex=3} elseif($comp2.cells.item($i,8).value2 -eq 'VALUTYPE=4'){$comp2.cells.item($i,7).interior.colorindex=3}}}

This code works, but the part which highlights the fields (the for loops on bottom) is cripplingly slow.  How can I speed this up?

While this isn't a direct way to speed up PowerShell interaction with Excel, I suspect most people having this problem will find this helpful.  I ended up writing a VBA macro ("Sides") that opens in a third workbook, along with the two of interest.  I then call it from Powershell.  All together, I came up with:

$excel= New-Object -ComObject "excel.application"
$excel.Visible=$true
$ocomp1=$excel.Workbooks.Open($WorkingDirectory+"Discrepancies1.csv")
$ocomp2=$excel.Workbooks.Open($WorkingDirectory+"Discrepancies2.csv")
$macro=$excel.Workbooks.open("\\dshfs03.dgoz.dccz.ccnz\psst\Aram\Highlighter.xlsm")
$excel.run("Sides")

This runs really smoothly and does exactly what I want.  Granted, you have to know a little VBA, but that wasn't a problem for me.


Converting binary value from BitArray to an int and back in C# What I am creating is essentially a binary clock face with touch input for setting values as well as displaying - so I need to convert both ways between an int and a binary sequence in a BitArray.

I cobbled this together (borrow and modifying a bit from a couple different examples I found):

    public class BinaryConverter
    {
        public static BitArray ToBinary(int numeral)
        {
            BitArray binary = new BitArray(new int[] { numeral });
            bool[] bits = new bool[binary.Count];
            binary.CopyTo(bits, 0);
            return binary;
        }

        public static int ToNumeral(BitArray binary, int length)
        {
            int numeral = 0;
            for (int i = 0; i < length; i++)
            {
                if (binary[i])
                {
                    numeral = numeral | (((int)1) << (length - 1 - i));
                }
            }
            return numeral;
        }
    }

It isn't especially verbose, but in my head before I started it should have been a couple of lines per method, perhaps better leveraging some .NET classes like System.Convert (though, I can't quite see how to do that). Is there a cleaner way to do this? Do you have any other suggestions for improvement?

You've made it much more complicated than necessary.

The conversion to a BitArray needlessly copies the values to the bool array bits.  You could instead use that on the conversion back to int.

public static class BinaryConverter
{
    public static BitArray ToBinary(this int numeral)
    {
        return new BitArray(new[] { numeral });
    }

    public static int ToNumeral(this BitArray binary)
    {
        if (binary == null)
            throw new ArgumentNullException("binary");
        if (binary.Length > 32)
            throw new ArgumentException("must be at most 32 bits long");

        var result = new int[1];
        binary.CopyTo(result, 0);
        return result[0];
    }
}


How do I dynamically create Python unit tests in a readable way? I have Django unit tests that are pretty much the following format:

class Tests(unittest.TestCase):
    def check(self, i, j):
        self.assertNotEquals(0, i-j)

for i in xrange(1, 4):
    for j in xrange(2, 6):
        def ch(i, j):
            return lambda self: self.check(i, j)
        setattr(Tests, "test_%r_%r" % (i, j), ch(i, j))

A function that returns a lambda that is bound as a method via setattr, which is an eyesore and as unreadable as you can get in Python without really trying to obfuscate.

How can I achieve the same functionality in a more readable way, preferably without lambda?

For reference, see the original SO question about the subject.

Don't bother with generating tests:

class Tests(unittest.TestCase):
    def check(self, i, j):
        self.assertNotEquals(0, i-j)

    def test_thingies(self):
        for i in xrange(1, 4):
            for j in xrange(2, 6):
                self.check(i,j)

It would be nicer to generate individual tests, but do you really get that much benefit out of it?

Or write a reusable function:

data = [(i,j) for i in xrange(1,4) for j in xrange(2,6)]
add_data_tests(TestClass, data, 'check')


Everything you might want to know about an element I am working with a lot of DOM manipulation and need to know several values of an element to determine its position within the DOM and I have written the following to help scrape several of the bits of information I need to proceed.

To me this looks very heavy and there might be some room to help improve the speed / accuracy of returning this information.

Any help in speeding this up or helping with the redundancy issues would be most helpful.

jsFiddle

$.fn.info = function(){
    var $el = this,
        obj = {
            _css: {},
            $win: $(window),
            $doc: $(document),
            x: Math.floor($el.offset().left),
            y: Math.floor($el.offset().top),
            w: Math.floor($el.width()),
            h: Math.floor($el.height()),
            tag: $el.prop("tagName").toLowerCase(),
            computedCss: function(){
                var css = ["width", "height", "float", "color", "font-size", "position", "top", "right", "bottom", "left", "margin-top", "margin-right", "margin-bottom", "margin-left", "color", "display", "visibility"];
                for(var i = 0; i < css.length; i++){
                    if(css[i].indexOf("-") > -1){
                        var temp = css[i].replace("-", "_");
                        this._css[temp] = $el.css(css[i]);
                    }else{
                        this._css[css[i]] = $el.css(css[i]);
                    };

                };
                return this;
            },
            checkVisibility: function(){
                this.visible = (((this.y + this.h) <= (this.top + this.winH)) && (this.y >= this.top));
                this.partial = ((this.y <= (this.top + this.winH)) && ((this.y + this.h) >= this.top));
                return this;
            },
            init: function(){
                this.winH = Math.floor(this.$win.height());
                this.winW = Math.floor(this.$win.width());
                this.docH = Math.floor(this.$doc.height());
                this.docW = Math.floor(this.$doc.width());
                this.top = this.$win.scrollTop();

  /* :compute the box-modal a,b,c,d with {x,y} values: */
  /* a----b */  this.a = { x:this.x, y:this.y };
  /* |    | */  this.b = { x:this.x+this.w, y:this.y };
  /* |    | */  this.c = { x:this.x, y:this.y+this.h };
  /* c----d */  this.d = { x:this.x+this.w, y:this.y+this.h };

                this.computedCss();
                this.checkVisibility();
                return this;
            }
        }.init();

    return obj;
};

I have written the following to help scrape several of the bits of information I need to proceed.

If this is for development purposes, for gathering information about an element and not actually related to your application, then you won't need this at all. The browser dev tools has a watch panel (F12 -> Sources -> First panel on the right side). You can simply pop in expressions and get their value there.

Now if it is for development, then this plugin is just the opposite of performant. Every time you call jquery.info(), all of these calculations run. That's fine if you actually use all of them, but if not then everything is unnecessary. I would suggest that you just create utility functions and call on a need-to-know basis.

Whenever you call $('.selector').info(), the this inside your function is actually a jQuery set that may contain zero or more matched items. But your logic only assumes one item in the set. How so?

Take $el.offset().left. When the set is empty, the return of offset will not be an object. This means accessing left will throw an error. As shown in the following:

// Access property left of undefined... or something not an object.
$('.non-existent-element').offset().left

Also, the order of the elements in the set is not to be relied upon. You might be aiming for a specific element, but there might accidentally be another element that matches your selector and jQuery might pick it up first. What's the problem? Methods like offset only pick up data from the first item in the set. If your element isn't that item, you might be grabbing the wrong data.

// Returns 8px top when black is clearly 200px down...
// That's because there's 4 other divs you didn't expect.
alert($('.color').offset().top);
.color{
  width: 50px;
  height: 50px;
}

.invi{
  visibility: hidden;
}

Red

Blue

Green

Yellow

Black

  /* :compute the box-modal a,b,c,d with {x,y} values: */
  /* a----b */  this.a = { x:this.x, y:this.y };
  /* |    | */  this.b = { x:this.x+this.w, y:this.y };
  /* |    | */  this.c = { x:this.x, y:this.y+this.h };
  /* c----d */  this.d = { x:this.x+this.w, y:this.y+this.h };

Your a, b, c and d, width, height, x and y can be retrieved from getBoundingClientRect.

this.winH = Math.floor(this.$win.height());
this.winW = Math.floor(this.$win.width());
this.docH = Math.floor(this.$doc.height());
this.docW = Math.floor(this.$doc.width());
this.top = this.$win.scrollTop();

This will return false data when the function was called, then the window is resized or scrolled.


Create Binary, Balanced Tree Attempt #2 Previously, I posted an incorrect implementation of making a binary, balanced tree from a list of a's.

Here's my second implementation:

data Tree a = Leaf
              | Node Integer (Tree a) a (Tree a)
              deriving (Show, Eq)-- where Integer is the height (bottom = 0)

-- make balanced, binary tree (height diff is 1 at most)
foldTree :: [a] -> Tree a
foldTree []     = Leaf
foldTree xxs@(x:xs) = Node level (foldTree first) x (foldTree rest)
     where (first, rest) = splitInHalf xs
           level         = getBinTreeHt xxs

splitInHalf :: [a] -> ([a], [a])
splitInHalf xs = splitAt mid xs
    where mid = length xs `div` 2

-- Get the total height of a tree given a list of [a] to create a Tree
getBinTreeHt :: [a] -> Integer
getBinTreeHt = floor . (logBase 2) . fromIntegral . length

Testing

Note that prettyTree's implementation is excluded from this question since it's a library for visually representing a tree. Credit to this answer for prettyTree.

*Main> (putStrLn . prettyTree . foldTree) [0..15]
        15
      14
    12
      13
  8
      11
    9
      10
0
      7
    5
      6
  1
      4
    2
      3

I'd suggest:

If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.


jQuery plugin authoring: Vertical Center example I am fairly new at writing jQuery plugins. Moreover, I am a huge fan of best practice.

I have written a plugin which centers an element inside its parent. I would love some feedback on how I could have written it better.

(function( $ ){

  $.fn.verticalCenter = function(options) {

    var settings = $.extend({
      min: 0, // Minimum width of the viewport for the centering to take effect
      max: 10000 // Maximum width of the viewport
    }, options);

    var center_element = function(element, parent){
      var elementHeight = element.height();
      parent.css({
        position:'relative'
      });
      element.css({
        position: 'absolute',
        top: "50%",
        marginTop:-elementHeight/2
      });
    }

    var remove_style = function(element, parent){
      parent.css({ position:'' });
      element.css({ position: '', top: '', marginTop: '' });
    }

    var determine_action = function(element, parent){

      $(window).on('load resize orientationchange', function() {

        var windowWidth = window.innerWidth

        if (windowWidth > settings.min && windowWidth < settings.max) {
          center_element(element, parent);
        }
        else {
          remove_style(element, parent);
        }

      });

    }

    return this.each(function(){

      var $elementToCenter = $(this);
      var $parent = $elementToCenter.parent();

      determine_action($elementToCenter, $parent);

    });

  };

})( jQuery );

The plugin is supposed to be responsive, and it allows the user to pass in viewport min and max values. These values determine if the centering should occur.

Interesting question, from a once over:

Consider a 'use strict' after (function( $ ){
You are mixing lowerCamelCase and snake_case, you should stick to lowerCamelCase
I am not a fan of remove_style, it might cause all kinds of unintended consequences, it would be better to store the original values of element and parent and then restore them if we don't center.
I am also not a fan of having 1 listener function per element ( however, if you were to keep the original css info in a closure, then that's fine )
The code would probably be cleaner if you let center_element determine the parent.
The newlines before closing curly braces make the code a bit too sparse towards the end

I would probably try something like this:

(function($){
  'use strict';
  $.fn.verticalCenter = function(options) {

    var settings = $.extend({
      min: 0,    // Minimum width of the viewport for centering to take effect
      max: 10000 // Maximum width of the viewport
    }, options);

    var centerElement = function(element,parent){

      parent.css({ position:'relative' });
      element.css({
        position: 'absolute',
        top: "50%",
        marginTop:-element.height() / 2
      });
    };

    var determine_action = function(element){

      var parent = element.parent(),
          originalParentStyle = parent.style(['position']),
          originalElementStyle = element.style(['position','top','marginTop']);

      $(window).on('load resize orientationchange', function() {

        var windowWidth = window.innerWidth;

        if (windowWidth > settings.min && windowWidth < settings.max) {
          centerElement(element, parent);
        }
        else {
          parent.css(originalParentStyle);
          element.css(originalElementStyle);
        }
      });
    };

    return this.each(function(){
      determine_action($(this));
    });
  };
})(jQuery);


TicTacToe endgame feedback in C# I'm learning C# and currently having an assignment on Tic Tac Toe. I'd love to have some feedback on where I can improve.

I've managed to create the end game functions but I feel it could be improved. I'm just not sure how to do it and was hoping someone here could help me.

I hope the information I've provided is enough, this.cells is a multidimensional array containing the Cell objects:

/// <summary>
/// Contains info about what kind of cell we're dealing with
/// </summary>
public enum Cell {
  Empty,
  Circle,
  Cross
}

Below is the part I'm searching feedback on. Too many if statements? What could I have done different or better?

/// <summary>
/// Check all possible combinations for the target cell
/// of winning the game (row, column, or slope).
///
/// Returns true if there is a win condition, false if there isn't.
/// </summary>
private bool IsGameOver(Cell cell) {
    // Row 1
    if (this.cells[0, 0] == cell && this.cells[0, 1] == cell && this.cells[0, 2] == cell) {
        return true;
    }

    // Row 2
    if (this.cells[1, 0] == cell && this.cells[1, 1] == cell && this.cells[1, 2] == cell) {
        return true;
    }

    // Row 3
    if (this.cells[2, 0] == cell && this.cells[2, 1] == cell && this.cells[2, 2] == cell) {
        return true;
    }

    // Clm 1
    if (this.cells[0, 0] == cell && this.cells[1, 0] == cell && this.cells[2, 0] == cell) {
        return true;
    }

    // Clm 2
    if (this.cells[1, 0] == cell && this.cells[1, 1] == cell && this.cells[1, 2] == cell) {
        return true;
    }

    // Clm 3
    if (this.cells[2, 0] == cell && this.cells[2, 1] == cell && this.cells[2, 2] == cell) {
        return true;
    }

    // Horizontal line 1
    if (this.cells[0, 0] == cell && this.cells[1, 1] == cell && this.cells[2, 2] == cell) {
        return true;
    }

    // Horizontal line 2
    if (this.cells[0, 2] == cell && this.cells[1, 1] == cell && this.cells[2, 0] == cell) {
        return true;
    }

    return false;
}

Naming

The enum Cell defines Empty, Circle and Cross. This values aren't cells in terms of an object, they are more like types.

For example: Empty is not a cell, but a cell can be empty

You can rename Cell to CellType to make it more clear.

Comments

Comments are a good documentation. You did a great job with the <summary>-tag. But the comments like // Row 1, // Row 2, // Clm 3 are not so good..

Robert C. Martin, who wrote the book "Clean Code" and many more, sad

  Don’t Use a Comment When You Can Use a Function or a Variable

Introduce Methods

We can wrap the if-statements into methods

bool IsFirstRowComplete(CellType cellType) {
    if (this.cells[0, 0] == cellType && this.cells[0, 1] == cellType && this.cells[0, 2] == cellType) {
        return true;
    }
    return false;
}

bool IsSecondRowComplete(CellType cellType) {
    if (this.cells[1, 0] == cellType && this.cells[1, 1] == cellType && this.cells[1, 2] == cellType) {
        return true;
    }
    return false;
}

// ...

Make them less complex

Since these methods return a Boolean we can return the boolean-expression itself

bool IsFirstRowComplete(CellType cellType) {
    return this.cells[0, 0] == cellType
           && this.cells[0, 1] == cellType
           && this.cells[0, 2] == cellType
}

bool IsSecondRowComplete(CellType cellType) {
    return this.cells[1, 0] == cellType
           && this.cells[1, 1] == cellType
           && this.cells[1, 2] == cellType
}

// ...

Remove Duplication

The new methods IsFirstRowComplete and IsSecondRowComplete looks very similar. We can extract the main logic and wrap it into its own method.

bool IsRowComplete(CellType cellType, int row) {
    return this.cells[row, 0] == cellType
           && this.cells[row, 1] == cellType
           && this.cells[row, 2] == cellType
}

// ...

If you like you can now wrap this method into IsFirstRowComplete and so on

bool IsFirstRowComplete(CellType cellType, int row) {
    return IsRowComplete(cellType, 0);
}

// ...

Introduce more Methods

We could finish here.. But we can make the code more clear if we wrap each check into a method

bool IsARowComplete(CellType cellType) {
    return IsFirstRowComplete(cellType, 0)
           || IsSecondRowComplete(cellType, 1)
           || IsThirdRowComplete(cellType, 2);
}

bool IsAColumnsComplete(CellType cellType) {
  return IsFirstColumnComplete(cellType, 0)
         || IsSecondColumnComplete(cellType, 1)
         || IsThirdColumnComplete(cellType, 2);
}

// ...

After the Refactoring

bool IsGameOver(CellType cellType) {
    return IsARowComplete(cellType)
           || IsAColumnComplete(cellType)
           || IsAHorizontalComplete(cellType)
}

Maybe a Bug

If the method isGameOver gets called with a CellType of type Empty it could return true

So maybe you need to check if the cellType is not Empty


Identify valid 8 card poker straight Write an improved code to identify a valid straight of eight cards, e.g. 4H,5S,AC,7C,8H,AH,0S,JC. Note that the card combination may include Wilds (as we see in our example, with the Ace of Clubs standing in for a Six and the Ace of Hearts standing in for a Nine), but must include at least two "natural" cards (i.e. non-Wild cards). Note also that the sequence of the cards is significant for this group type, and that 4H,5S,AC,8C,7H,AH,AS,AC, e.g., is not a valid straight of eight, as it is not in sequence. Aces are the only wild cards and must represent another card. Duplicate cards are allowed.
Card inputs are in a list of 2 value strings with the value:

2 to 9 - for 2 to 9
0 - for 10
J - for Jack
Q - for Queen
K - for King
A - for Ace

The suits are shown with values S(spade), C(club), H(heart), D(diamond)

Example input to be checked: 4H,5S,AC,7C,8H,AH,0S,JC
Output: True
Example input to be checked: AH,5S,AC,7C,AH,AH,AS,AC
Output: True
Example input to be checked: 4H,5S,AC,8C,7H,AH,AS,AC
Output: False

Here is my code:
group = input().split(",")
if len(group) == 8:
    #check for ace
    ace = [0 for card in group if card[0] == 'A']
    run_vals = {"0": 10, "J": 11, "Q": 12, "K":13}
    if len(ace) < 6:
        miss_count = 0
        for index in range(len(group)-1):
            if group[index][0]  == "A":
                miss_count += 1
                if group[index+1][0]  == "A" and index == len(group)-2:
                    miss_count += 1
                    continue
                else:
                    continue

            if group[index+1][0]  == "A" and index == len(group)-2:
               miss_count += 1
               continue
            if group[index+1][0]  == "A" and index <len(group)-2:
               continue

            if group[index+1][0] in run_vals:
                num1 = run_vals[group[index+1][0]]
            else:
                num1 = int(group[index+1][0])

            if group[index][0] in run_vals:
                num2 = run_vals[group[index][0]]
            else:
                num2 = int(group[index][0])

            if (num1 - num2) != 1:
                miss_count += 1

        if miss_count == len(ace):
            print(True)
        else:
            print(False)

    elif len(ace) == 6:
        ace_in_between = 0
        range_limits = [card for card in group if card[0] != "A"]
        for index in range(len(group)):
            if index > group.index(range_limits[0]) and index< group.index(range_limits[1]):
                ace_in_between += 1
        range_limits = [run_vals[val[0]] if val[0] in run_vals else val[0] for val in range_limits]
        if ace_in_between + 1 == (int(range_limits[1]) - int(range_limits[0]) ):
            print(True)
        else:
            print(False)
    else:
        print(False)
else:
    print(False)

Good news!  There's lots of room for improvement in your code!  (How's that for a positive spin?)
Counting Aces
    ace = [0 for card in group if card[0] == 'A']

This code creates a list (ace), which only contains 0 elements equal in number to the number of aces in group.  The contents of the list is never used, only the length.  Finally, the length of the list is queried twice.
That is a very heavy implementation for a simple count of the number of aces:
    aces = sum(card[0] == 'A' for card in group)

Or slightly less obliquely:
    aces = sum(1 for card in group if card[0] == 'A')

Decoding Cards
    run_vals = {"0": 10, "J": 11, "Q": 12, "K":13}
    ...
            if group[index+1][0] in run_vals:
                num1 = run_vals[group[index+1][0]]
            else:
                num1 = int(group[index+1][0])

            if group[index][0] in run_vals:
                num2 = run_vals[group[index][0]]
            else:
                num2 = int(group[index][0])
    ...
        range_limits = [run_vals[val[0]] if val[0] in run_vals else val[0] for val in range_limits]
        if ace_in_between + 1 == (int(range_limits[1]) - int(range_limits[0]) ):

I'm seeing a lot of in run_vals tests and int(...) casts.  Imagine how much cleaner your code could look if you simply filled in all of the run_vals?
    run_vals = {"A": 1,
                "2": 2, "3": 3, "4": 4, "5": 5,
                "6": 6, "7": 7, "8": 8, "9": 9,
                "0": 10, "J": 11, "Q": 12, "K":13}

I've added "A" mapping to 1 just for completeness.  It would allow you to test all(card[0] in run_vals for card in group) to check that all the cards have a valid rank, such that nobody sneaks in a "1 of Spades" for example.
For that matter, you could check for valid suits too, such as all(card[1] in {'C', 'D', 'H', 'S'} for card in group), to avoid someone sneaking in the "7 of Pentacles".
A Straight
The problem would be dead simple if there was no wild cards.  You could write:
    rank = [run_vals[card[0]] for card in group]
    start = rank[0]
    for idx in range(len(rank)):
        if rank[idx] != start + idx:
            return False
    return True

Supporting wild cards would be easy too, if we knew the first card was not an ace.  We could just add an exception for the aces:
    for idx in range(len(rank)):
        if rank[idx] != start + idx and rank[idx] != 1:
            return False

Starting Value
What happens if the ace is the first card?  Well, the second card (assume it was not an ace) would dictate the start was one rank lower.  Or if that was an ace, then the third card would, and so on:
    for idx in range(len(rank)):
        if rank[idx] == 1:
            start = rank[idx] - idx
            break
    else:
        return False     # Only aces exist!

Functions!
Your code is one complex script without any functions.  If you haven't learned how to write them yet, learn.  If you have learned, use them!
Reworked Code
The following code is a reimplementation of some of the above ideas.  However, the loops like for idx in len(range(list)) have been replaced with more Pythonic for idx, value in enumerate(list) loops.  Loops which return a False if one iteration produces a False result have been replaced with an all(...) statement with a generator expression.  It also demonstrates some type-hints, """docstrings""" (including the use of (doctest) to help write code which is more understandable to others, and contain built-in unit tests.
Another improvement is the problem statement states there must be at least 2 "natural" cards.  Instead of testing for the number of aces is less than or equal to 6 -- a number which appears nowhere in the problem statement -- it directly tests against the given value 2.
RANK = dict(zip("A234567890JQK", range(1, 14)))
WILD = RANK['A']

def straight_of_eight(card_string: str) -> bool:
    """
    Determine if a string of cards is an ascending straight,
    with at least 2 natural cards.

    >>> straight_of_eight("4H,5S,AC,7C,8H,AH,0S,JC")
    True

    >>> straight_of_eight("4H,5S,AC,8H,7C,AH,0S,JC")
    False
    """

    ranks = [RANK[card[0]] for card in card_string.split(',')]

    if len(ranks) != 8:
        return False   # Were not given exactly 8 cards

    if sum(rank != WILD for rank in ranks) < 2:
        return False   # Not enough natural cards

    # Determine starting rank for the straight
    start = next(rank - idx for idx, rank in enumerate(ranks) if rank != WILD)

    return 2 <= start <= 6 and all(rank == idx or rank == WILD
                                   for idx, rank in enumerate(ranks, start))

if __name__ == '__main__':
    import doctest
    doctest.testmod()

    group = input()
    print(straight_of_eight(group))


Filtering vector of maps based on a blacklist Given a vector of maps:

(def my-list
  [{:a 1 :b 2 :c 3}
    {:a 1 :b 5 :c 6}
    {:a 7 :b 8 :c 12}
    {:a 10 :b 11 :c 12}])

and a blacklist:

(def blacklist
  [{:a 1 :c 3}
    {:a 10 :c 12}])

the expected output is:

[{:a 1 :b 5 :c 6}
  {:a 7 :b 8 :c 12}]

I came up with:

(defn not-excluded?
  [blacklist item]
  (not-any? (fn [exclusion-item]
              (and (= (:a item) (:a exclusion-item))
                   (= (:c item) (:c exclusion-item))))
            blacklist))

(filter (partial not-excluded? blacklist) my-list)

but there is probably a more idiomatic Clojure way.

We want to exclude from the vector (more generally a sequence) the maps of which any map in the blacklist is a sub-map. Let's define a function that tests whether its first argument is a sub-map of its second argument:

(defn submap? [a b]
  (every? (fn [[k v]] (= v (b k)))  a))

For instance,

=> (map #(submap? {1 2} %) [{} {1 1} {1 2}])
(false false true)

So far, so good. Let's use submap? to define function clean that takes a blacklist and a sequence of maps as arguments, excluding any supermaps of any map in the blacklist from the sequence:

(defn clean [blacklist ms]
  (filter
    (fn [m] (not-any? #(submap? % m) blacklist))
    ms))

For example,

=> (clean blacklist my-list)
({:a 1, :b 5, :c 6} {:a 7, :b 8, :c 12})

submap? could be careful about absent keys. If you have nil values, you need to fix this.


Counting Characters from an HTML File with Python I just completed level 2 of The Python Challenge on pythonchallenge.com and I am in the process of learning python so please bear with me and any silly mistakes I may have made.
I am looking for some feedback about what I could have done better in my code. Two areas specifically:

How could I have more easily identified the comment section of the HTML file? I used a beat-around-the-bush method that kind of found the end of the comment (or the beginning technically but it is counting from the end) and gave me some extra characters that I was able to recognize and anticipated (the extra "-->" and "-"). What condition would have better found this comment so I could put it in a new string to be counted?

This is what I wrote:
from collections import Counter
import requests

page = requests.get('http://www.pythonchallenge.com/pc/def/ocr.html')

pagetext = ""
pagetext = (page.text)
#find out what number we are going back to

i = 1
x = 4
testchar = ""
testcharstring = ""

while x == 4:
    testcharstring = pagetext[-i:]
    testchar = testcharstring[0]
    if testchar == "-":
        testcharstring = pagetext[-(i+1)]
        testchar = testcharstring[0]
        if testchar == "-":
            testcharstring = pagetext[-(i+2)]
            testchar = testcharstring[0]
            if testchar == "!":
                testcharstring = pagetext[-(i+3)]
                testchar = testcharstring[0]
                if testchar == "<":
                    x = 3
            else:
                i += 1
                x = 4
        else:
            i += 1
            x = 4
    else:
        i += 1
print(i)

newstring = pagetext[-i:]

charcount = Counter(newstring)

print(charcount)

And this is the source HTML:

  <title>ocr</title>
  <link rel="stylesheet" type="text/css" href="../style.css">

recognize the characters. maybe they are in the book,
but MAYBE they
are in the page source.

General tips:

Use the hints. They are helpful, most of the times.

Investigate the data given to you.

Avoid looking for spoilers.

Forums: Python Challenge Forums,
read before you post.

IRC: irc.freenode.net #pythonchallenge

To see the solutions to the previous level, replace pc with pcc, i.e. go
to: http://www.pythonchallenge.com/pcc/def/ocr.html

'

I don’t have enough reputation to comment, so I must say this in an answer.
It looks clunky to use
    while x == 4:

and then do
    x = 3

whenever you want to break out of the loop.
It looks better to do
    while True:

and when you want to break out of the loop do
    break

Cheers!


Building a unique array of db fields This is stripped down from a project I'm working on:

let userFields = {
    id: {
        dbFields: 'id',
    },
    email: {
        dbFields: 'email',
    },
    first_name: {
        dbFields: 'first_name',
    },
    last_name: {
        dbFields: 'last_name',
    },
    name: {
        dbFields: ['first_name', 'last_name'],
        resolve: user => [user.first_name, user.last_name].filter(n => n.length).join(' '),
    }
};

let selectFields = ['name', 'first_name', 'email'];

let dbFields = new Set();
selectFields.forEach(f => {
    if(userFields[f].dbFields) {
        if(userFields[f].dbFields instanceof Array) {
            userFields[f].dbFields.forEach(x => dbFields.add(x));
        } else {
            dbFields.add(userFields[f].dbFields);
        }
    }
});

console.log(Array.from(dbFields)); // [ 'first_name', 'last_name', 'email' ]

I don't like that big selectFields.forEach or the fact that Set doesn't appear to have an addMany method.

Is there any way I can compact this a bit more?

You can run this with babel-node if you need to (npm install -g babel).

Taking advantage of Array.prototype.flat()
 we might compact this a bit.

Basically, we filter all of our fields, making them an array if they are not already, getting out an array of arrays (nested only one level). After that, we can easily flatten it, so we iterate each element and we can just add it to our set.

let userFields = {
    id: {
        dbFields: 'id',
    },
    email: {
        dbFields: 'email',
    },
    first_name: {
        dbFields: 'first_name',
    },
    last_name: {
        dbFields: 'last_name',
    },
    name: {
        dbFields: ['first_name', 'last_name'],
        resolve: user => [user.first_name, user.last_name].filter(n => n.length).join(' '),
    }
};

let selectFields = ['name', 'first_name', 'email'];

let dbFields = new Set();
selectFields.map(key => {
    let field = userFields[key].dbFields;
    return (field instanceof Array) ? field : [field]
  })
  .flat()
  .forEach(v => dbFields.add(v));
console.log(Array.from(dbFields));


Check if two strings are permutation of each other private String sort(String word) {
    char[] content = word.toCharArray();
    Arrays.sort(content);
    return new String(content);
  }

  private boolean isPermutation(String s1, String s2) {
    s2 = s2.toLowerCase();
    if (s1.length() != s2.length()) {
      return false;
    }
    if (s1.equals(s2)) {
      return true;
    }
    return sort(s1).equals(sort(s2));
  }

Could the above solution can be optimized(in space and time)?
I think the worst case running time would be: \$O(nlog)\$

For short strings, this algorithm and the implementation is good.

If your strings are longer than a few 100 characters and if they only contain ASCII characters, it may be more efficient to count how many times each character appears and then compare if all these counts are equal. This algorithm has complexity \$O(n)\$, but the (invisible) constant factor is larger.

If your strings contain arbitrary Unicode code points, using a simple array for the counts becomes impractical, since that array needs to have 0x11_0000 entries. Looping over these entries and comparing them is \$O(1)\$, but nevertheless it is slow.

Therefore, for practical purposes and the general case, your code looks perfect. There might be some improvements if you know more about the string's contents, but these are on the implementation level, not on the algorithm complexity level.


small ticker class to execute a function at a regular inverval I have written the following ticker class. You can find a description and example usage in its comments. However, it kind of feels like I am using too many thread synchronization tools (std::atomic, std::mutex and std::condition_variable). Is there a way to simplify this?

#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstdint>
#include <iostream>
#include <thread>

// Executes a function f in a fixed interval (given in microseconds).
// Call ticker::start() to run.
// The ticker stops when ticker::stop() is called
// or the instance runs out of scope.
//
// Example usage:
//
// void say_hi()
// {
//     std::cout << "hi " << std::endl;
// }
// int main()
// {
//     ticker hi_ticker( say_hi, 2 * 1000 * 1000 );
//     hi_ticker.start();
//     std::this_thread::sleep_for( std::chrono::milliseconds( 4500 ) );
// }
class ticker
{
public:
    typedef std::function<void()> function;
    void start()
    {
        if ( running_flag_ )
        {
            return;
        }
        running_flag_ = true;
        thread_ = std::thread( [this]() { thread_function(); } );
    }
    ticker( const function& f, std::int64_t interval_us ) :
        f_( f ),
        interval_us_( interval_us ),
        running_flag_( false ),
        thread_(),
        stop_mutex_(),
        stop_cv_()
    {}
    void stop()
    {
        if ( !running_flag_ )
        {
            return;
        }
        running_flag_ = false;
        {
            std::lock_guard<std::mutex> lock( stop_mutex_ );
            stop_cv_.notify_all();
        }
        if ( thread_.joinable() )
        {
            thread_.join();
            thread_ = std::thread();
        }
    }
    ~ticker()
    {
        stop();
    }
private:
    void thread_function()
    {
        auto last_time = std::chrono::high_resolution_clock::now();
        while ( running_flag_ )
        {
            auto current_time = std::chrono::high_resolution_clock::now();
            const auto wake_up_time =
                last_time + std::chrono::microseconds{ interval_us_ };
            while ( current_time < wake_up_time )
            {
                const auto sleep_time = wake_up_time - current_time;
                std::unique_lock<std::mutex> lock( stop_mutex_ );
                stop_cv_.wait_for( lock, sleep_time );
                current_time = std::chrono::high_resolution_clock::now();
                if ( !running_flag_ )
                {
                    return;
                }
            }
            const auto elapsed = current_time - last_time;
            last_time = current_time;
            const auto elapsed_us =
                std::chrono::duration_cast<std::chrono::microseconds>(
                    elapsed).count();
            f_();
        }
    }
    const function f_;
    const std::int64_t interval_us_;
    std::atomic<bool> running_flag_;
    std::thread thread_;
    std::mutex stop_mutex_;
    std::condition_variable stop_cv_;
};

edit: Here is the improved version, based on the excellent reviews here: https://gist.github.com/Dobiasd/99f3b5b0632d57d1f66c94658760c986

I have some doubts about you member variable running_flag_ and its use in ticker::start(). If its purpose is to avoid calling ticker::start() from the same thread then it can be just bool, not std::atomic<bool>. If its purpose is to avoid calling ticker::start() from the different threads for the same object then you seem to have a data race when two threads might both see running_flag_ equal to false and go ahead with creating two threads  later:

    if ( running_flag_ )
    {
        return;
    }
    running_flag_ = true;
    thread_ = std::thread( [this]() { thread_function(); } );

As far as I know std::atomic::compare_exchange_weak must be used in order to avoid such data race when using atomic variable. However as far as I understand you do not expect high contention in ticker::start() and ticker::stop(). So it seems that a more simple approach could be to have running_flag_ as bool

class ticker {
    // ...
    const function f_;
    const std::int64_t interval_us_;
    bool running_flag_;
    std::thread thread_;
    std::mutex stop_mutex_;
    std::condition_variable stop_cv_;

and rewrite functions in this way:

void start() {
    std::lock_guard<std::mutex> lock( stop_mutex_ );
    if (running_flag_ )
        return;
    thread_ = std::thread( [this]() { thread_function(); } );
    running_flag_ = true;
}

void stop() {
    std::unique_lock<std::mutex> lk(std::mutex);
    if (!running_flag_)
        return;
    running_flag_ = false;
    lk.unlock();
    stop_cv_.notify_one(); // why all? notify_one seems to be enough
    thread_.join();
}

Next, why you write explicitly thread_(),stop_mutex_(), stop_cv_()? It is unnecessary.

Then thread_function() seems to be little bit complicated. I have choosen using a predicate in order to stop:

void thread_function() {
    auto last_time = std::chrono::steady_clock::now();
    while ( true ) {
        const auto wake_up_time = last_time + std::chrono::microseconds{ interval_us_ };
        const auto sleep_time = wake_up_time - last_time;
        std::unique_lock<std::mutex> lk(stop_mutex_);
        if (!running_flag_)
            break;
        stop_cv_.wait_for(lk, sleep_time, [this](){return !running_flag_;});
        if (!running_flag_)
            break;
        lk.unlock();
        last_time = wake_up_time;
        f_();
    }
}

And finally. I think you should use std::chrono::steady_clock instead of std::chrono::high_resolution_clock since they cannot be adjusted and according to http://en.cppreference.com/w/cpp/chrono/steady_clock:

  This clock is not related to wall clock time (for example, it can be
  time since last reboot), and is most suitable for measuring
  intervals.


Generate strings of random characters I've a function to generate random characters from a set of alphabets. This function would be called multiple times and thus I'm trying to make it use same set of variables, i.e. have same seed so that strings don't repeat as long as possible.

#include <iostream>
#include <random>
#include <string>

std::string generateRandomChar(const unsigned int _len)
    {
        std::string result;
        result.reserve(_len);

        static constexpr char alphanum[] = "0123456789"
                                           "abcdefghijklmnopqrstuvwxyz"
                                           "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, 61);

        for (int i = 0; i < _len;
            result += (alphanum[dis(gen)]);
        }
        return result;
    }

int main(){
    for(int i = 0; i < 10; ++i){
        std::cout << generateRandomChar(10) << std::endl;
    }
}

Unfortunately I don't have any expertise with C++11 <random> functions and I was only using srand and friends earlier, so I might be making lots of mistakes here. Currently it works and generates tons of strings without repeating, but I'm sure I could make either of:

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 61);

static variable too, so that it isn't calculated each time the function is called because that would be waste right?

So which one should be static here? Are there any mistakes/improvements that you see here?

Ideone

Wherever you place static will change the behaviour of your program tremendously. In the end, we have \$2^3 = 8\$ combinations, so let's check some of them.

A random_device may fall back to a pseudorandom engine if no hardware-device for random numbers is available. If you don't use static on random_device in this case, all your strings may end up the same, as the pseudorandom engine may get initialized with a implementation defined fixed seed, e.g.

 std::random_device a;
 std::random_device b;
 assert(a() == b());  // worst case if no hardware-device or a low-effort implementation is used

In this case, a mt19937 would get seeded with the same value all the time, and we end up with the same string in every call. This changes if either mt19937 or random_device is static, and may change if dist is static, as a uniform_int_distribution can use several calls to the generator for its internal state.

Of course, if mt19937 is static, you may as well change random_device to a static variant, as it will get evaluated only once. This is the closest your get to a single srand() call at the start of your program. Your uniform_int_distribution still loses its internal state, though.

In the end, it depends on whether we want two generateRandomChar calls to correlate to each other. If they shall not correlate at all, we need to reseed our PRNG with a new non-deterministic number and cannot use static at all.

Or, to put it in another way: if we use static for all three values, then

generateRandomChar(10) + generateRandomChar(10)

is the same as
    generateRandomChar(20)
If we use static on mt19937, then both may be the same, depending on both _len and dist.

Either way, if you want to have more control over the generation, you can just provide a generator in your function:

template <typename Generator>
std::string generateRandomChar(Generator & gen, const unsigned int _len)
    {
        ...
    }

Same holds for the distribution.

Other than that, I'd use sizeof instead of 61 to make sure that I don't accidentally change the pool of possible characters without changing the number bounds in dist's constructor:

static constexpr char alphanum[] = "0123456789"
                                   "abcdefghijklmnopqrstuvwxyz"
                                   "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, sizeof(alphanum) - 1);


Send Data from DynamoDB to Lambda (C#) and to Azure Queue I am a beginner and trying to send data from AWS DynamoDB to Azure Queues. Note that this code will be invoked 10,000 and alot more. Can you guys review it once.

using System;
using System.IO;
using System.Text;

using Newtonsoft.Json;

using Amazon.Lambda.Core;
using Amazon.Lambda.DynamoDBEvents;
using Amazon.DynamoDBv2.Model;
using Microsoft.Azure.ServiceBus;
using System.Threading.Tasks;

    // Assembly attribute to enable the Lambda function's JSON input to be converted into a .NET class.
    [assembly: LambdaSerializer(typeof(Amazon.Lambda.Serialization.Json.JsonSerializer))]

namespace Lambda
{
    public class Function
    {
        private static readonly JsonSerializer _jsonSerializer = new JsonSerializer();

        public async Task FunctionHandler(DynamoDBEvent dynamoEvent, ILambdaContext context)
        {
            context.Logger.LogLine($"Beginning to process {dynamoEvent.Records.Count} records...");

            foreach (var record in dynamoEvent.Records)
            {
                context.Logger.LogLine($"Event ID: {record.EventID}");
                context.Logger.LogLine($"Event Name: {record.EventName}");

                string streamRecordJson = SerializeStreamRecord(record.Dynamodb);
                await Send(streamRecordJson);
                context.Logger.LogLine($"DynamoDB Record:");
                context.Logger.LogLine(streamRecordJson );
            }

            context.Logger.LogLine("Stream processing complete.");
        }

        private static async Task Send(string stream)
        {
            const string connectionString = "QUEUE END POINT";
            string queueName = "QUEUE NAME";
            ServiceBusConnectionStringBuilder svc = new ServiceBusConnectionStringBuilder(connectionString);
            ServiceBusConnection svc1 = new ServiceBusConnection(svc);
            var client = new QueueClient(svc1, queueName, ReceiveMode.PeekLock, RetryPolicy.Default);
            var message = new Message(Encoding.UTF8.GetBytes(stream));
            await client.SendAsync(message);
        }

        private string SerializeStreamRecord(StreamRecord streamRecord)
        {
            using (var writer = new StringWriter())
            {
                _jsonSerializer.Serialize(writer, streamRecord);
                return writer.ToString();
            }
        }
    }
}

If the connection and queue name are not changing per record then there is no reason to be creating a new client for each record in the loop. Especially for the amount of times stated in the original post.

Move that to the constructor of the class.

public class Function {
    private static readonly JsonSerializer _jsonSerializer = new JsonSerializer();
    private readonly IQueueClient client;
    private const string connectionString = "QUEUE END POINT";
    private const string queueName = "QUEUE NAME";

    public Function() {
        ServiceBusConnectionStringBuilder builder = new ServiceBusConnectionStringBuilder(connectionString);
        ServiceBusConnection connection = new ServiceBusConnection(builder);
        client = new QueueClient(connection, queueName, ReceiveMode.PeekLock, RetryPolicy.Default);
    }

    public async Task FunctionHandler(DynamoDBEvent dynamoEvent, ILambdaContext context) {
        var logger = context.Logger;
        logger.LogLine($"Beginning to process {dynamoEvent.Records.Count} records...");

        foreach (var record in dynamoEvent.Records) {
            logger.LogLine($"Event ID: {record.EventID}");
            logger.LogLine($"Event Name: {record.EventName}");

            string streamRecordJson = SerializeStreamRecord(record.Dynamodb);
            await SendAsync(streamRecordJson);

            logger.LogLine($"DynamoDB Record:");
            logger.LogLine(streamRecordJson);
        }

        context.Logger.LogLine("Stream processing complete.");
    }

    private Task SendAsync(string body) {
        var message = new Message(Encoding.UTF8.GetBytes(body));
        return client.SendAsync(message);
    }

    private string SerializeStreamRecord(StreamRecord streamRecord) {
        using (var writer = new StringWriter()) {
            _jsonSerializer.Serialize(writer, streamRecord);
            return writer.ToString();
        }
    }
}


Maximum score, using only elements near the beginning or end of a list Input list has n elements, each element has a score. The goal is to assemble a group (of size ‘team’) of elements together and to find their total score.
Inputs:

score [] of size n,
team which is the team size,
m tells us how to slice the list

Selection of elements from the list is done in the following way:

During each selection, we have to choose an element with the highest score among either the first m in available elements or the last m available elements in the list. The element is then removed from the list and added to the team total score.
If there are multiple elements with the same highest score among the first or last in available elements, the element closest to the start of the line is picked.
If there are less than in available elements. then we pick the highest scored element from all available elements.

Sample Input and Output:
Sample 1
n:9, score:[17,12,10,2,7,2,11,20,8,],team:3,m:4
OUTPUT : 49

Sample 2
n:8,score:[18,5,15,18,11,15,9,7],team:5,m:1
OUTPUT : 60

Need an optimal solution for this Python code. I am getting the desired output. But I am looking for a better solution.
def teamFormation(score, team, m):
    total_score = 0
    for _ in range(team):
        if len(score) < 2*m:
            total_score += score.pop(score.index(max(score)))
        elif max(score[:m]) > max(score[-m:]):
            total_score += score.pop(score[:m].index(max(score[:m])))
        else:
            total_score += score.pop(score[-m:].index(max(score[-m:]))-m)
    return total_score

1. Analysis

(The code in the post was edited after I wrote this analysis, so the list of operations does not correspond to the latest version of the code. But the asymptotic result is the same.)

I'll write \$n\$ for the length of the score list, and \$k\$ for the number of team members.

On each iteration of the loop we have these operations:

slices score[m] and score[-m:];
a list concatenation score[m] + score[-m:];
a call to max on the concatenated list;
a call to score.index;
a call to score.pop.

Operations 1–3 take time proportional to \$m\$, and operations 4–5 take time proportional to \$n\$. The loop executes \$k\$ times, so the overall runtime is proportional to \$k(m + n)\$.

In the worst case, \$k\$ and \$m\$ are both \$Θ(n)\$, and so the overall runtime is \$Θ(n^2)\$, that is, quadratic in the size of the input.

We can demonstrate this behaviour by timing some random test cases:

from random import random
from timeit import timeit

def test(n, f=teamFormation):
    score = [random() for _ in range(n)]
    return timeit(lambda:f(score, n, n // 2 - 1), number=1)

and plotting the timings:

2. Better algorithm

In order to improve the performance of the code, we need to rewrite the code so that within the main loop, we avoid operations that take time proportional to the length of the slices, \$m\$, or to the length of the whole list, \$n\$.

What we'd like to do is to maintain a data structure containing the \$2m\$ values from the two ends of the list. The data structure must allow us to efficiently find and extract the maximum value. Then we can repeatedly extract the maximum value, and then replace it with the next value from the appropriate end of the remainder of list (the left end if the maximum value came from the left side, and right end otherwise).

The data structure we need for this is a heap, and Python provides us with the heapq module for manipulation of heaps.

I'll give the revised code below; read it and see if you can figure out how it works.

from heapq import heapify, heappop, heappush, nlargest

def best_team_score(score, k, m):
    """Return the maximum sum of k elements from the sequence score,
    subject to the condition that only the first m and last m can be
    selected at each stage.

    """
    n = len(score)
    if n < k:
        raise ValueError("Not enough scores to make a team.")
    if n <= 2 * m:
        return sum(nlargest(k, score))

    # Heap of (-score[i], i) pairs. The score is negated because
    # Python's heaps are min-heaps, but we want the maximum score. By
    # pairing with the index we can ensure that the leftmost score is
    # returned in case of a tie, and that we can tell whether the
    # maximum score came from the left or the right side.
    heap = [(-score[j], j) for i in range(m) for j in (i, n - i - 1)]
    heapify(heap)

    # score[left:right] are the elements of score that have not yet
    # been added to the heap.
    left = m
    right = n - m

    total = 0
    for _ in range(k):
        # Leftmost maximum score in the heap.
        s, i = heappop(heap)
        total -= s
        if right <= left:
            # All scores are now in the heap.
            pass
        elif i < left:
            # Maximum score came from left side.
            heappush(heap, (-score[left], left))
            left += 1
        else:
            # Maximum score came from right side.
            assert right <= i
            right -= 1
            heappush(heap, (-score[right], right))
    return total

We can check that this is correct by testing against the original code:

from itertools import product
from random import random
from unittest import TestCase

class TestBestTeamScore(TestCase):
    def test_best_team_score(self):
        for n in range(50):
            score = [random() for _ in range(n)]
            for k, m in product(range(1, n + 1), repeat=2):
                found = best_team_score(score, k, k)
                # teamFormation modifies score, so take a copy.
                expected = teamFormation(score[:], k, k)
                self.assertEqual(expected, found, score)

The heappush and heappop functions take time proportional to the logarithm of size of the heap, which is at most \$2m\$ so we expect the runtime to be propertional to \$k\log 2m\$, and since \$k\$ and \$m\$ are \$O(n)\$, the overall runtime is \$O(n\log n)\$:

3. Appendix: plotting

In case you're interested in how I drew the plots:

from functools import partial
import matplotlib.pyplot as plt
import numpy as np

def plot1():
    emin, emax = 1, 5
    x = 10 ** np.arange(emin, emax + 1)
    y = np.vectorize(test)(x)
    plt.xlabel("n")
    plt.ylabel("t (seconds)")
    a, = np.linalg.lstsq(x[:, np.newaxis] ** 2, y)[0]
    xx = 10 ** np.arange(emin, emax, 0.01)
    plt.loglog(xx, a * xx**2, label="least squares fit to $t = an^2$")
    plt.loglog(x, y, 'r+', label="data")
    plt.legend()
    plt.grid(alpha=0.25)
    plt.show()

def plot2():
    emin, emax = 2, 7
    x = 10 ** np.arange(emin, emax + 1)
    y = np.vectorize(partial(test, f=best_team_score))(x)
    plt.xlabel("n")
    plt.ylabel("t (seconds)")
    a, = np.linalg.lstsq((x * np.log(x))[:, np.newaxis], y)[0]
    xx = 10 ** np.arange(emin, emax, 0.01)
    plt.loglog(xx, a * xx * np.log(xx),
               label="least squares fit to $t = an\log n$")
    plt.loglog(x, y, 'r+', label="data")
    plt.legend()
    plt.grid(alpha=0.25)
    plt.show()


Bubblesort using Writer monad I still consider myself a newbie to functional programming, and I still have some trouble wrapping my head around a lot of functional concepts. Anyway, here goes:

import Control.Monad.Writer
import Data.Monoid

bubblesort' :: (Ord a) => [a] -> Writer All [a]
bubblesort' (x:y:xs)
  | x > y = tell (All False) >>
    (y:) <$> bubblesort' (x:xs)
  | otherwise =
    (x:) <$> bubblesort' (y:xs)
bubblesort' xs = return xs

bubblesort :: (Ord a) => [a] -> [a]
bubblesort xs
  | ok = ys
  | otherwise = bubblesort ys
  where (ys, All ok) = runWriter (bubblesort' xs)

That's a reasonable implementation if you want to use Writer. Keep in mind that Writer is lazy in the monoid, so you can end up with a space leak.

Also, bubblesort doesn't look at the last element after the first iteration, e.g.

for i = N to 1
  for j = 1 to i - 1                    -- <<
    if data[j] > data[j + 1]
      swap data[j] data[j + 1]

Either way, as an exercise, I suggest you to write bubblesort and bubblesort' without Writer.

Note that Mergesort is a lot simpler to implement in Haskell.


Validating files and returning errors messages/boolean values I am writing simple file validator for my java ee app and I am stack with my class api. I need specific error descriptions, but also I would like to have boolean values indicating whether file is valid or not. Please give me some hints how to do it 'smart'.

package pl.poznan.put.ims.business.attachments;

import java.util.List;
import java.util.ArrayList;

import com.google.inject.Inject;

import pl.poznan.put.ims.business.entities.Attachment;
import pl.poznan.put.ims.business.exceptions.AttachmentValidationException;
import pl.poznan.put.ims.settings.IFileSystemSettings;

public class AttachmentValidator implements IAttachmentValidator
{
      IFileSystemSettings messageSettings;
      private List<String> errors;

    @Inject
    public AttachmentValidator(IFileSystemSettings messageSettings)
    {
        this.messageSettings = messageSettings;
        this.errors = new ArrayList<String>();
    }

    @Override
    public boolean validate(List<Attachment> attachments) throws AttachmentValidationException
    {
        for (Attachment attachment : attachments) {
            validate(attachment);
        }

        if(attachments.size() > messageSettings.getMaxFilesCount())
            errors.add("Attachments max number exceeded.");

        if(!errors.isEmpty())
            throw new AttachmentValidationException(errors);

        return true;
    }

    @Override
    public boolean validate(Attachment attachment)
    {
        boolean isValid = validateLimitExceeded(attachment);
        isValid &= validateNull(attachment);

        return !isValid;
    }

    private boolean validateLimitExceeded(Attachment attachment)
    {
        boolean exceeded = attachment.getFileSize() > messageSettings.getMaxFileSize();
        if(exceeded)
            errors.add("Max file size limit exceeded. File: " + attachment.getFileDisplayName() + ". Size: "+ attachment.getFileSize()/1024/1024 + "MB.");

        return exceeded;
    }

    private boolean validateNull(Attachment attachment)
    {
        if(attachment == null) {
            errors.add("No attachment.");
            return false;
        }

        return true;
    }

    @Override
    public List<String> getErrors()
    {
        return errors;
    }

    @Override
    public long getTotalMaxFilesSize() {
        return messageSettings.getMaxFilesCount() * messageSettings.getMaxFileSize();
    }
}

Some notes:

The boolean validate(...) method never returns false so it should be void method.
I'd pass immutable ValidationResult objects to the clients. The clients could check the results and could signal to their clients if there is an error or prints the messages etc.
I'd omit the &= operator, it's really hard to read.
getTotalMaxFilesSize() should be in the FileSystemSettings class. (Feature or data envy smell.)

After a few refactoring steps the following came out:

AttachmentValidatorService.java

import java.util.List;

public interface AttachmentValidatorService {

    ValidationResult validate(List<Attachment> attachments);

    ValidationResult validate(Attachment attachment);

    long getTotalMaxFilesSize();
}

ValidationResult.java

import static com.google.common.base.Preconditions.checkNotNull;

import java.util.ArrayList;
import java.util.List;

import javax.annotation.concurrent.Immutable;

@Immutable
public class ValidationResult {

    private final List<String> errors;

    public ValidationResult(final List<String> errors) {
        checkNotNull(errors, "errors cannot be null");
        this.errors = new ArrayList<String>(errors);
    }

    public boolean isValid() {
        if (errors.isEmpty()) {
            return true;
        }
        return false;
    }

    public List<String> getErrors() {
        return new ArrayList<String>(errors);
    }

    // If lots of the clients use this
    //  public void checkErrors() {
    //      if (!isValid()) {
    //          throw new ...
    //      }
    //  }
}

AttachmentValidatorServiceImpl:

import static com.google.common.base.Preconditions.checkNotNull;

import java.util.Collections;
import java.util.List;

public class AttachmentValidatorServiceImpl implements
        AttachmentValidatorService {
    private final FileSystemSettings messageSettings;

    public AttachmentValidatorServiceImpl(
            final FileSystemSettings messageSettings) {
        this.messageSettings = checkNotNull(messageSettings,
                "messageSettings cannot be null");
    }

    @Override
    public ValidationResult validate(final List<Attachment> attachments) {
        final AttachmentValidator attachmentValidator = new AttachmentValidator(
                messageSettings, attachments);
        return attachmentValidator.getValidationResult();
    }

    @Override
    public ValidationResult validate(final Attachment attachment) {
        return validate(Collections.singletonList(attachment));
    }

    @Override
    public long getTotalMaxFilesSize() {
        return messageSettings.getMaxFilesCount()
                * messageSettings.getMaxFileSize();
    }
}

AttachmentValidator.java

import static com.google.common.base.Preconditions.checkNotNull;

import java.util.ArrayList;
import java.util.List;

public class AttachmentValidator {

    private final List<String> errors = new ArrayList<String>();

    private final FileSystemSettings messageSettings;

    public AttachmentValidator(
            final FileSystemSettings messageSettings,
            final List<Attachment> attachments) {
        this.messageSettings = checkNotNull(messageSettings,
                "messageSettings cannot be null");
        checkNotNull(attachments, "attachments cannot be null");
        for (final Attachment attachment : attachments) {
            validate(attachment);
        }

        validateSize(attachments);
    }

    private void validate(final Attachment attachment) {
        validateNull(attachment);
        validateLimitExceeded(attachment);
    }

    private void validateSize(final List<Attachment> attachments) {
        if (attachments.size() > messageSettings.getMaxFilesCount()) {
            errors.add("Attachments max number exceeded.");
        }
    }

    private void validateLimitExceeded(final Attachment attachment) {
        if (attachment == null) {
            return;
        }
        final int fileSize = attachment.getFileSize();
        final boolean exceeded = fileSize > messageSettings
                .getMaxFileSize();
        if (exceeded) {
            final String fileDisplayName = attachment
                    .getFileDisplayName();
            final int fileSizeInMegaBytes;
            if (fileSize == 0) {
                fileSizeInMegaBytes = 0;
            } else {
                fileSizeInMegaBytes = fileSize / 1024 / 1024;
            }
            final String errorMsg = "Max file size limit exceeded. File: "
                    + fileDisplayName
                    + ". Size: "
                    + fileSizeInMegaBytes + "MB.";
            errors.add(errorMsg);
        }
    }

    private void validateNull(final Attachment attachment) {
        if (attachment == null) {
            errors.add("No attachment.");
        }
    }

    public ValidationResult getValidationResult() {
        return new ValidationResult(errors);
    }

}

Feel free to ask if you have any questions.