Spinlock for C++ kernel (with x86 ASM) This is some prototype code for a spin-lock for my toy operating system.  Bear in mind this means there are no standard library routines to fall back on.  It's also for C++11 compilation and will only ever be compiled by the GNU G++ compiler.

The primary use for this is in the scheduler and other code that accesses the process table.

I think there are lots of ways of getting this wrong, and some of them aren't obvious. So it'd be great to have a second pair of eyes on it.

Firstly the locking code itself in NASM x86 asm:

; *******************************
; void spin_lock(uint32 * p);
;
global __kspin_lock
__kspin_lock:
    push ebp
    mov ebp, esp        ; we might as well the the stack frame right?

    mov eax, [ebp + 8]  ; eax contains address of uint32 used for the lock
    mov ecx, 1

.tryacquire             ; try and get the lock.
    xchg ecx, [eax]
    test ecx, ecx
    jz .acquired        ; if the lock wasn't 0 (unlocked) repeat.

.pauseloop
    pause               ; see 'About PAUSE' below
    test dword [eax], 1
    jne .pauseloop
    jmp .tryacquire

.acquired
    pop ebp
    ret

And secondly a class that wraps it a little.  (I will eventually then wrap this with an RAII class to release the lock automatically when it goes out of scope).

#pragma once
#include <std_types.h>

extern "C" {
/** These routines probably shouldn't be used directly. */
void __kspin_lock(uint32 *p);
};

/**
 * SpinLock provides a crude locking mechanism based around an atomic
 * exchange of a variable in memory.
 *
 * The SpinLock loops, swapping the value 1 for the value in lock.
 * Each time it checks to see if the value retrieved from lock is now 0,
 * if it is it knows that lock now contains 1, and it holds the lock.
 *
 * To ensure all spinlocks reside in a unique cache line the spinlock
 * is aligned to 64 bytes and is 64 bytes in size.  This avoids two
 * processes competing for ownership of the same 64 byte cache line,
 * which could be bad for performance.
 */
class __attribute__((aligned(64))) SpinLock
{
public:
    SpinLock()
        : lock_value(0)
    {}

    void lock()
    {
        __kspin_lock(&lock_value);
    }

    void release()
    {
        __kspin_lock_release(&lock_value);
    }

private:
    static void __kspin_lock_release(uint32 *p)
    {
        *p = 0;
    }

    /* Difficult to know whether it makes sense to copy a spinlock.
     * It might be practical to copy it but always 0 the lock for
     * the copy. */
    SpinLock(const SpinLock &) = delete;
    SpinLock & operator=(const SpinLock &) = delete;
    /* padded to ensure it's on a unique cache line. */
    uint32 lock_value;
    char reserved[64 - sizeof(uint32)];
};

I also think this code could use some through tests, especially on performance, but that might be rather a case of profiling in place in the kernel.  Any suggestions welcome.

Incidentally - I'm also thinking that it's going to be useful to add some additional debugging and profiling features to the code.  For example, and probably only while running a debug build:

How frequently was the lock contended.
Which thread owns the lock.
Is the lock held by this thread (this would allow functions to check that the lock is held by a calling function properly).

This is largely a duplicate of https://stackoverflow.com/questions/6935442/x86-spinlock-using-cmpxchg, https://stackoverflow.com/questions/11959374/fastest-inline-assembly-spinlock, etc.

(1) Your code works only on 32-bit x86. If you're using 64-bit (x86-64), the calling convention is totally wrong (you need to save and restore %rbp rather than %ebp, and you're looking for the argument in the wrong place). If you're implementing your own OS, I suppose you know what you're doing... but in general I think it's weird to see 32-bit x86 code these days.

(2) Useless trivia of the day: The two instructions test ecx, ecx; jz .acquired could be replaced with the single instruction jecxz .acquired. I don't know whether this is an optimization or a pessimization on your particular hardware. It would be a size optimization, at least.

(2.5) Really, consider using cmpxchg instead of xchg; test. The cmpxchg mnemonic maps more directly onto the "Compare And Swap" idiom that you're using. It will also help you when it comes time to implement "is the lock held by this thread"; you can set the word to current-thread-id instead of just 1.

(3) See 'About PAUSE' below: Unfortunately there is no "About PAUSE" below. However, it seems like you're doing the right thing there. You could definitely tighten up the code; for example I don't know why you're wasting time with that test dword [eax], 1. You should just retry the xchg as soon as the pause is over.

(4) Consider removing the stack frame; it's not doing anything useful (unless it's necessary for your debugger of choice), just slowing things down.


Retrieving statistics about URL clicks I'm pretty new to ASP/MVC but have had some prior programming experience.

I am trying to retrieve statistics about URL clicks - total clicks and unique clicks by IP address. I started with:

ViewBag.ClicksToday = context.EmailLinkClicks
     .Where(c => c.CreatedOn == DateTime.Today).Count();

ViewBag.ClicksWeek = context.EmailLinkClicks
     .Where(c => c.CreatedOn > System.Data.Entity.DbFunctions.AddDays(c.CreatedOn, -7)).Count();

ViewBag.ClicksMonth = context.EmailLinkClicks
     .Where(c => c.CreatedOn.Month == DateTime.Today.Month).Count();

ViewBag.UniqueClicksToday = context.EmailLinkClicks.Where(c => c.CreatedOn == DateTime.Today)
     .Select(c => c.IPAddress).Distinct().Count();

ViewBag.UniqueClicksWeek = context.EmailLinkClicks.Where(c => c.CreatedOn > System.Data.Entity.DbFunctions.AddDays(c.CreatedOn, -7))
     .Select(c => c.IPAddress).Distinct().Count();

ViewBag.UniqueClicksMonth = context.EmailLinkClicks.Where(c => c.CreatedOn.Month == DateTime.Today.Month)
     .Select(c => c.IPAddress).Distinct().Count();

Then I thought why not make it a function:

private static int GetClicks(AppContext context, string period, bool unique)
{
    int Clicks = 0;
    switch (period)
    {
        case "today":
            var ClicksToday = context.EmailLinkClicks
                .Where(c => c.CreatedOn == DateTime.Today);
            Clicks = unique ? ClicksToday.Select(c => c.IPAddress).Distinct().Count()
                : ClicksToday.Count();
            break;
        case "week":
            var ClicksWeek = context.EmailLinkClicks
                .Where(c => c.CreatedOn > System.Data.Entity.DbFunctions.AddDays(c.CreatedOn, -7));
            Clicks = unique ? ClicksWeek.Select(c => c.IPAddress).Distinct().Count()
                : ClicksWeek.Count();
            break;
        case "month":
            var ClicksMonth = context.EmailLinkClicks
                .Where(c => c.CreatedOn.Month == DateTime.Today.Month);
            Clicks = unique ? ClicksMonth.Select(c => c.IPAddress).Distinct().Count()
                : ClicksMonth.Count();
            break;
    }
    return Clicks;
}

But I still have to call quite a lot of code:

ViewBag.ClicksToday = GetClicks(context, "today", false);
ViewBag.ClicksWeek = GetClicks(context, "week", false);
ViewBag.ClicksMonth = GetClicks(context, "month", false);

ViewBag.UniqueClicksToday = GetClicks(context, "today", true);
ViewBag.UniqueClicksWeek = GetClicks(context, "week", true);
ViewBag.UniqueClicksMonth = GetClicks(context, "month", true);

My questions:

Is there any way to further simplify/reduce this code?

perhaps have the total & unique in one value? [total],[unique]

Is it poor practice to pass period as a string and then interrogate it?
Where should you store these kind of database queries? It currently resides in my controller and then returned to the view.

Here's the first thing I came up with. Wrote it in Notepad, so it might not compile exactly as is.

private static int GetClicks(AppContext context, Period period, bool unique)
{
    int Clicks = 0;
    switch (period)
    {
        var query = context.EmailLinkClicks.AsQueryable();
        case Period.Today:
            query = query.Where(c => c.CreatedOn == DateTime.Today);
            break;
        case Period.Week:
            query = query.Where(c => c.CreatedOn > System.Data.Entity.DbFunctions.AddDays(c.CreatedOn, -7));
            break;
        case Period.Month:
            query = query.Where(c => c.CreatedOn.Month == DateTime.Today.Month);
            break;
    }

    var ipAddresses = query.Select(c => c.IpAddress);

    if (unique)
    {
        query = query.Distinct();
    }

    return query.Count();
}

enum Period
{
    Today,
    Week,
    Month
}

Update: As to where to store these queries... Doing it in your controller isn't the worst thing in the world. There are a ton of different places you could put that code though. The Repository pattern seems to be popular. I'm not strict about that kind of thing though.

Update: if you wanted to get both the total and unique stats in the same call, you could do something like this: https://gist.github.com/alexdresko/8059762/bcf233b86869042c4b6f360f6b461999b2bf4899

Update: But what you probably want, assuming you want to create some kind of report, is this: https://gist.github.com/alexdresko/8059762/c4afa948f020e8395bb27d565269c914aad926a7

That one will allow you to simply iterate over the collections of stats in your view, display all relevant information.


Check if email address contains one of many domains from a table, ignoring the subdomain I'm trying to validate email addresses as being from certain universities. I have a table, University, which is full of university domains. University email addresses often have different subdomains, and I want to be able to tolerate any subdomain under the domains in my table.

I think the following works, but is poorly written.  Can anyone suggest ways of refactoring this, with explanations?

domain = self.email.split("@")[1]

domain_test = false

University.all.each do |d|
  if domain.include?(d.domain)
    domain_test = true
    break
  end
end

if domain_test = false
  errors.add(:email, "Sorry, no match found")
end

Looking at your current code first, I noticed the following:

You should use email.split('@').last instead of an opaque numeric index (plus, you'll always get a string this way, whereas using [1] will return nil if the address doesn't contain an "@" to begin with)
You should probably downcase the address you're trying to match (provided the university domains are similarly downcased, of course)
You never need to loop, check a condition, and set a variable + break if that condition is true. The reason you don't need to that is because you have Enumerable#detect to do it for you.
This looks like a Rails project, so it'd probably be faster to either let the database check for you, or only load the column you need, instead of loading every single University record.

For instance, to let the DB check it, you can do this

match = University.where("? LIKE CONCAT('%', domain)", self.email).any?
errors.add(:email, "Sorry, no match found") unless match

Since you're not actually loading any records doing this, I'd imagine it's pretty fast (and case-insensitive, so no need for downcasing)

As for matching things in Ruby, Nat's approach is the most straightforward one, I'd say.

I'd still do it a bit differently, though:

address = self.email.downcase

# only load the domain column values, since those are all we need here
match = University.pluck(:domain).detect { |domain| address.end_with?(domain) }

errors.add(:email, "Sorry, no match found") unless match

Of course, you should still check that the address is a valid email address in its entirety.


Trimming fgets(): strlen() or strtok() After a successful fgets(buffer, ...), it is often desirable to trim a potential End-of-Line '\n'.

Of the following 2 methods, are there any shortcomings?

#include <stdio.h>

char buffer[100];

// Method 1
while (fgets(buffer, sizeof buffer, stdin) != NULL) {
  size_t len = strlen(buffer);
  if (len > 0 && buffer[len - 1] == '\n')
    buffer[--len] = '\0';

  // use buffer
  printf("\"%s\"\n", buffer);
}

// Method 2
while (fgets(buffer, sizeof buffer, stdin) != NULL) {
  strtok(buffer, "\n");

  // use buffer
  printf("\"%s\"\n", buffer);
}

Notes:

When reading text files from alternate file systems, strtok(buffer, "\r\n") looks useful.
strtok() may incur an issue with another strtok() sequence.

For what it is worth, using strlen is much more efficient than using strtok.  I did some tests (omitting the file access) using strlen, strchr, strtok, strstr, strpbrk and strcspn:

It surprised me that to execute this neat looking thing:

s = strchr(s, '\n');
if (s) {
    *s = '\0';
}

takes nearly 50% longer than this ugly looking sucker:

size_t len = strlen(s);
if (len && (s[len-1] == '\n')) {
    s[len-1] = '\0';
}

and the beautiful

strtok(s, "\n\r");

and

strsep(&s, "\n\r");

are 10 to 20 times slower.  The latter two do of course look for \r as well as \n. But even adding \r, the strlen approach is still quicker than the strchr and still quicker then strtok and strsep by 10 to 20 times:

size_t len = strlen(s);
if (len && ((s[len-1] == '\n') || (s[len-1] == '\r'))) {
    s[len-1] = '\0';
}

Note that I wasn't exhaustive with string variations.  In fact I didn't even break a sweat.  And of course this is all quite irrelevant as the stdio call will dominate in your target code :-)

Note also from the comments below that if the first character of the search string (s in the examples above) is one of the characters in the pattern string, strtok does nothing (thanks to @chux).


Bookmarklet for selecting code snippets on Code Review The following code will add to each code block a 'Select Code' button that will select the code belonging to that block. Please review for maintainability.

In order to use this, visit http://codereviewcommunity.github.io/CodeReviewBookmarklet/

javascript: if ($('button').length === 0) {
  /* Stack Exchange does not do buttons, this does */
  $(".prettyprint").each( function()
  {
    /* Thank you http://stackoverflow.com/a/2838358/7602 */
    function selectCode(el, win)
    {
      win = win || window;
      var doc = win.document, sel, range;
      if (win.getSelection && doc.createRange)
      {
        sel = win.getSelection();
        range = doc.createRange();
        range.selectNodeContents(el);
        sel.removeAllRanges();
        sel.addRange(range);
      }
      else if (doc.body.createTextRange)
      {
        range = doc.body.createTextRange();
        range.moveToElementText(el);
        range.select();
      }
    }

    var buttonText  = 'Select Code',
        length      = buttonText.length,
        codeBlock   = this,
        $link       = $('<button type="button">' + buttonText + '</button><br>').click(function()
        {
          console.log( $(codeBlock).text().substring( length ) );
          selectCode(codeBlock);
        });
    $(codeBlock).prepend( $link );
  });
}

I have tested this on FF and Chrome and it works for me.

You inject the button using jQuery.prepend(), which inserts the button as the first child of the .prettyprint code block.  Therefore, when the bookmarklet is invoked, and it selects the contents of the code block, the "Select Code" button is inadvertently included in the selection.  I recommend using jQuery.before() instead.


List-based stack implementation in C++ I'm new to c++ and that is my list-based stack implementation.
It works, but i'm not sure that my code is good.

Please help me to improve this code, any advices are welcome.

#include <iostream>

struct Node {
    int data;
    struct Node *next;
};

class Stack {
private:
    Node *top;
public:
    Stack()
    {
        top = nullptr;
    }

    void push(int value)
    {
        Node *n = new Node;
        n->data = value;
        n->next = top;
        top = n;
    };

    void pop()
    {
        if (top != nullptr)
        {
            Node *n = top;
            top = top->next;
            delete n;
        }
    }

    bool isEmpty() {
        return top == nullptr;
    }

    int getTop()
    {
        if (top != nullptr)
            return top->data;
        else return INT32_MIN; // my value is in range [-100; 100]
    }

    void display()
    {
        Node *n = top;
        while (n != nullptr)
        {
            if (n == top) std::cout << "\t\t\tTOP ELEMENT" << std::endl;
            else {
                std::cout << "                             |" << std::endl;
                std::cout << "                            \\|/" << std::endl;
            }
            // i need to print data, address of element and address to next element
            std::cout << "---------------------------------------------------------" << std::endl;
            std::cout << "Data: " << n->data << "\t\tAddress: " << n <<"\tNext: " << n->next << std::endl;
            std::cout << "---------------------------------------------------------" << std::endl;
            n = n->next;
        }
    }
};

First, I'll show you some essential feature your class is missing, then I'll show you a way to use modern features of C++ to automate parts of your code.

Fixing your current code

Use const to have the compiler check your logic

If a method does not modify the class, then it should be declared const so that other functions can call it when acting on an instance that is not allowed to be changed. For example,

bool isEmpty() const
{
    return top == nullptr;
}

Now, a function that takes a const Stack& parameter can check if the Stack instance is empty. Similarly, the getTop() and display() methods should be marked const since neither modify the stack.

Clean up your resources

First, some sample code:

int main()
{
    int sizeOfStack;
    std::cin >> sizeOfStack; // ask user for a number
    if(sizeOfStack < 10)
    {
        Stack stack;
        for(int i = 0; i < sizeOfStack; ++i)
        {
            stack.push(i);
        }
        stack.display();
    }  // All data added to stack is leaked here
    else
    {
        std::cout << "Too large for this example.\n";
    }

    // The memory taken up by the stack cannot be released
    // until the program exits.
}

As your code is now, when your program exits a scope (a part of code that is enclosed in curly braces like a function, loop, or if-else-block), all of the data you created with new will be leaked. This means that the data will still exist and take up memory and other resources, but there will be no way to access it to clean it up.

In C++, every class that has a data member that does not have its own destructor (usually pointers) needs a destructor to manually clean it up. This is a method named like a constructor but prefixed with a tilde: ~Stack(). For your Stack class, you would need something like

~Stack()
{
    while( ! isEmpty())
    {
        pop();
    }
}

Write constructors to ensure data is always valid

In C++, a class and a struct are nearly identical concepts. The only difference is that the data in a class is private by default and data in a struct is public by default. Otherwise, anything you can write in a class you can write in a struct. So, you can write a constructor for your Node class.

Node(int inputData, Node* inputNext)
{
    data = inputData;
    next = inputNext;
}

A better way to write this is to use an initializer list:

Node(int inputData, Node* inputNext) : data(inputData), next(inputNext)
{
}

Similarly, for the Stack class:

Stack() : top(nullptr)
{
}

It's not so important with ints and pointers, but with more complex classes you'll write in the future, using intializer lists will avoid some unnecessary work.

Now that Nodes have a constructor, you can simplify your push() method.

push(int value)
{
    top = new Node(value, top);
}

The constructor of the Node class centralizes the logic of creating a new Node so you don't have to rewrite it everywhere.

Use methods and other named code to make your intent clear

Many places in your code check if top == nullptr. You should use the isEmpty() to tell readers of your code (including you in the future) what you actually care about.

void pop()
{
    if ( ! isEmpty())
    {
        Node *n = top;
        top = top->next;
        delete n;
    }
}

This goes for getTop() as well.

Decide how to handle copying and assignment

As it is now, when an instance of Stack is copied, both instances will refer to the same data and modifications to one instance may affect the other.

Stack s1;
s1.push(7);
Stack s2 = s1;
s2.push(21);
s1.display();
std::cout << "\n\n\n";
s2.display();

This will result in the following output before crashing:

                        TOP ELEMENT
---------------------------------------------------------
Data: 7         Address: 007AF1C0       Next: 00000000
---------------------------------------------------------

                        TOP ELEMENT
---------------------------------------------------------
Data: 21                Address: 007AF230       Next: 007AF1C0
---------------------------------------------------------
                             |
                            \|/
---------------------------------------------------------
Data: 7         Address: 007AF1C0       Next: 00000000
---------------------------------------------------------

Notice that both nodes with the value 7 have the same pointer address. Now that the Stack class has a destructor, copying and assignment need to be handled to avoid deleting the same pointer address more than once. The simplest way is to disallow both.

Stack(const Stack& other) = delete; // delete the copy constructor
Stack& operator=(const Stack& other) = delete; // delete the assignment operator

With these lines in your class declaration, the following code will not compile:

Stack s1;
Stack s2 = s1; // error: Stack cannot be copied
Stack s3(s1); // error Stack cannot be copied

Stack s4;
s4 = s1; // error: Stack cannot be assigned to.

If you want your Stack class to be copyable, then you need to explicitly copy all of the data from one to the other.

Stack(const Stack& other) : top(nullptr)
{
    if( ! other.isEmpty())
    {
        top = new Node(other.top->data, nullptr);
    }
    else
    {
        return;
    }

    Node* bottom = top;
    for(Node* n = other.top->next; n != nullptr; n = n->next)
    {
        bottom->next = new Node(n->data, nullptr);
        bottom = bottom->next;
    }
}

After adding the copy constructor, you can rerun the code with s1 and s2 and see that the nodes containing the value 7 are at different addresses.

I'll leave writing the assignment operator as an exercise for you.

Tell the user when a request cannot be completed

Right now, when a user calls getTop() on an empty Stack, the user still gets an answer. Unless the user of this class sees the comment that INT32_MIN is never a valid value, there's no indication that anything went wrong. You may not have need of data values outside of [-100, 100], but what about future users (including your future self)? Why should your class not be allowed to store INT32_MIN as a valid piece of data?

It is better to tell the user that there is no data to be had. One way, if you are using C++17 (which may require a compiler flag or changing an IDE option), is to return a std::optional<int> (reference).

#include <optional>

// ...

std::optional<int> getTop()
{
    if(isEmpty())
    {
        return std::nullopt;
    }
    else
    {
        return top->data;
    }
}

The other option is to throw an exception in the empty case.

This way the caller of getTop() has to check if there is any data to be had.

Other notes

In the display() method, you can use a for-loop instead of a while loop to centralize all of the looping logic.

void display()
{
    for(Node* n = top; n != nullptr; n = n->next)
    {
        // output
    }
}

One more nitpick, you don't need the keyword struct in the Node::next declaration.

struct Node {
    Node(int inputData, Node* inputNext) : data(inputData), next(inputNext) {}
    int data;
    Node* next;
};

Using modern C++ features

A great way of improving this code is to use smart pointers. The std::unique_ptr (reference) tells readers, users, and the compiler that the variable or class containing the unique_ptr is responsible for cleaning up the variable when it is no longer needed.

So, you can change your Node class to

#include <memory>

struct Node {
    Node(int inputData, Node* inputNext) : data(inputData), next(inputNext) {}
    int data;
    std::unique_ptr<Node> next;
};

And the Stack class turns into

class Stack {
private:
    std::unique_ptr<Node> top;
// ...

Now, when a stack instance leaves the scope where it was created, the top node is automatically deleted. When top is deleted, top->next is automatically deleted, and then top->next->next, and then top->next->next->next, etc. So, you no longer need an explicit destructor (~Stack). The compiler will generate the correct destructor for you.

Now, you no longer have to call delete on any pointers. For example, the pop() method is now reduced to

void pop()
{
    if( ! isEmpty())
    {
        top = std::move(top->next);
    }
}

The std::move() call means that the contents of top->next--both the data and the pointer to the top->next->next node--will be stolen and moved into top. The previous contents of top will be deleted as this happens.

The other places where pointer manipulation changes is anywhere new is called. The push() method is now written with smart pointers as

void push(int value)
{
    top = std::make_unique<Node>(value, top.release());
};

The release() method returns the raw (non-smart) pointer held by the smart pointer and removes all responsibility for deleting it from that smart pointer. This happens so that the new smart pointer being added takes over responsibility for deleting the data when it is no longer needed. Assigning the new std::unique_ptr to top means that the Stack instance is now responsible for deleting the newly created Node.

Finally, if you don't want your Stack class to be copyable or assignable, you no longer need to delete those functions, since they will no longer be automatically generated. Instances of std::unique_ptr are not copyable or assignable, so any class they are a part of will lose those qualities as well. If you want to make your class copyable, you'll need the get() method of the std::unique_ptr. This returns the raw pointer like the release() method, but the std::unique_ptr retains responsibility for deleting the Node. This will allow your program to follow the linked list chain without copying std::unique_ptrs.


Advent of Code 2019: Day 4 Advent of Code 2019: Day 4
I'm doing Advent of Code this year. Below is my attempt at day 4:
Problem
Part One

--- Day 4: Secure Container ---
You arrive at the Venus fuel depot only to discover it's protected by a password. The Elves had written the password on a sticky note, but someone threw it out.
However, they do remember a few key facts about the password:

It is a six-digit number.
The value is within the range given in your puzzle input.
Two adjacent digits are the same (like 22 in 122345).
Going from left to right, the digits never decrease; they only ever increase or stay the same (like 111123 or 135679).

Other than the range rule, the following are true:

111111 meets these criteria (double 11, never decreases).
223450 does not meet these criteria (decreasing pair of digits 50).
123789 does not meet these criteria (no double).

How many different passwords within the range given in your puzzle input meet these criteria?

Part Two

--- Part Two ---
An Elf just remembered one more important detail: the two adjacent matching digits are not part of a larger group of matching digits.
Given this additional criterion, but still ignoring the range rule, the following are now true:

112233 meets these criteria because the digits never decrease and all repeated digits are exactly two digits long.
123444 no longer meets the criteria (the repeated 44 is part of a larger group of 444).
111122 meets the criteria (even though 1 is repeated more than twice, it still contains a double 22).

How many different passwords within the range given in your puzzle input meet all of the criteria?

Solution
from itertools import groupby

bounds = (265275, 781584)

rules = [
    # Digits are never decreasing
    lambda s: all(int(s[i]) <= int(s[i+1])
                  for i in range(len(s)-1)),
    # Two adjacent digits are equal.
    lambda s: any(s[i] == s[i+1] for i in range(len(s)-1)),
    # Two adjacent digits don't form a larger group.
    lambda s: any(len(list(v)) == 2 for _, v in groupby(s))
]

def test(num, rules):
    return all(f(str(num)) for f in rules)

def solve(bounds, rules):
    return sum(1 for i in range(bounds[0], bounds[1]+1) if test(i, rules))

def part_one():
    return solve(bounds, rules[:2])

def part_two():
    return solve(bounds, rules[::2])

print(part_one())  # 960
print(part_two())  # 626

Notes
I don't consider myself a beginner in Python, however I am not proficient in it either. I guess I would be at the lower ends of intermediate. I am familiar with PEP 8 and have read it in its entirety, thus, any stylistic deviations I make are probably deliberate. Nevertheless, feel free to point them out if you feel a particular choice of mine was sufficiently erroneous. I am concerned with best practices and readability, but also the performance of my code. I am not sure what tradeoff is appropriate, and would appreciate feedback on the tradeoffs I did make.
My style tends to over utilise functions. This is partly because I genuinely think separating functionality into functions is a good thing, but is also an artifiact of my development practices. I tend to write the program in a Jupyter notebook (the ability to execute arbitrary code excerpts in semi isolated cells is a very helpful development aid and lends itself naturally to one function per cell (with the added benefit of being able to easily test functions independently)). I would welcome thoughts on this, but unless it is particularly egregious, I am unlikely to change it.

Overall, I like this. To really nitpick, I don't really like the use of rules[::2]. [::2] conveys that we are picking out every even element of rules as if that was significant. But in this case, it is more like it just happens to be that the first and last rules are what we want to pick out and that happened to match up with choosing all even elements.

I would probably just name the rules as follows. If the visual grouping of the rules is important you could wrap them in a class as static methods.

from itertools import groupby

bounds = (265275, 781584)

def digits_never_decreasing(s):
    return all(int(s[i]) <= int(s[i+1]) for i in range(len(s)-1))

def adjacent_digits_equal(s):
    return any(s[i] == s[i+1] for i in range(len(s)-1))

def adjacent_digits_not_in_larger_group(s):
    return any(len(list(v)) == 2 for _, v in groupby(s))

def test(num, *rules):
    return all(f(str(num)) for f in rules)

def solve(bounds, *rules):
    return sum(1 for i in range(bounds[0], bounds[1]+1) if test(i, *rules))

def part_one():
    return solve(bounds, digits_never_decreasing, adjacent_digits_equal)

def part_two():
    return solve(bounds, digits_never_decreasing, adjacent_digits_not_in_larger_group)

print(part_one())  # 960
print(part_two())  # 626


Creating an array of strings from a text file I'm try to create array of strings from a text file. I need a review from experienced programmers about my program. (MinGW gcc, Win7)

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

main()
{
FILE *file;
char *fname = "lines.txt";
file = fopen(fname, "r");

if(file == NULL)
    printf("Can't read %s", fname);

char cbuff;

int nlines = 0; //counter of new lines
int chr = 0; //counter of chars (except new line char)

int maxlen = 0;
while( (cbuff = fgetc(file) - 0) != EOF )
{
    if(cbuff == '\n')
    {
        if (chr > maxlen)
        {
            maxlen = chr + 1;
        }

        chr = 0;
        nlines++;
    }

    else
    {
    chr++;
    }
}

printf( "lines: %d\nmax string len: %d\n\n", nlines, maxlen );
rewind(file);

char *list[nlines];

int buffsize = maxlen * sizeof(char);
char buff[buffsize];

int i = 0;
while(fgets(buff, buffsize, file))
{

    list[i] = malloc(strlen(buff) * sizeof(char));
    strcpy(list[i], buff);
    i++;
}

fclose(file);

int c = 0;
for(c; c < nlines; c++)
{
    printf( "%s", list[c] );
}
}//main

I'm trying to control size of array and items in array. Maybe I have errors somewhere, do not judge strictly.

If you are truly coding in C then all variables should be declared at the start of the function. This has traditionally been how the C language worked and what C coders expect.

C has also traditionally not allowed for runtime declarations of array sizes. You should malloc the list variable.

If you initialize a loop variable then just omit it in the for loop definition. In other words don't do this:

for(c; c < foo; c++)

do this:

for( ; c < foo; c++)

A char is already a byte, no need to multiple strlen by sizeof(char).

Personally I would move most of the logic into proper functions and out of main. It is just a good habit to get into.


Binding events in constructor I am trying to get familiar with OOP JavaScript, in particular working with the prototype pattern and would love some pointers/suggestions on how to improve my code.

I think I have understood the basics well, and have been able create class instances successfully.

I am however, a little unsure on how to work with events when it comes to representing these instances with a UI. Until now, I have been binding my events in the constructor before the element gets added to the DOM, but am sure this could be improved:

function Person(data) {
    var self = this;
    self.data = data;
    self.$element = $('
' +
                          '
' + data.name + '
' +
                          '
' + data.age + '
' +
                      '
');

    // bind events
    self.$element.find('.name').click(function () {
        self.speakName();
    });

    self.$element.find('.age').click(function () {
        self.speakAge();
    });

    // render element
    $('.person-container').append(self.$element);
}

Person.prototype.speakName = function () {
    alert(this.data.name);
};

Person.prototype.speakAge = function () {
    alert(this.data.age);
};

Ideally, I'd like to be able to build up a relatively complex UI of 'people', with various controls on each person to perform actions related to that person only. Apologies for the contrived example, I'm just trying to get the concept right in my head before doing anything more real-world.

I've also included a working jsfiddle incase this is easier to work with: http://jsfiddle.net/z59q2rab/.

It feels like you have muddled the model, view, and controller. With a name like Person, I would expect this object to act as a model.  Constructing a person shouldn't also make its UI.  At the least, make the UI rendering a separate explicit step.

A second potential problem is that concatenating strings into HTML without escaping can lead to JavaScript injection vulnerabilities (also known as cross-site scripting).  I recommend using $.text() to fill in the text.

function Person(data) {
    this.name = data.name;
    this.age = data.age;
}

Person.prototype.speakName = function() {
    alert(this.name);
};

Person.prototype.speakAge = function() {
    alert(this.age);
};

Person.prototype.render = function($container) {
    var $element = $(
        '

'
    );

    // Fill text and bind events
    var self = this;
    $element.find('.name')
            .text(self.name)
            .click(function () {
                self.speakName();
             });

    $element.find('.age')
            .text(self.age)
            .click(function () {
                self.speakAge();
             });

    // render element
    $container.append($element);
};

//////////////////////////////////////////////////////////////////////

var persons = [
    new Person({
        name: 'Tom',
        age: 30
    }),
    new Person({
        name: 'Dick',
        age: 25
    }),
    new Person({
        name: 'Harry',
        age: 45
    })
];

for (var i = 0; i < persons.length; i++) {
    persons[i].render($('#person-container'));
}
.person {
    border: 1px solid black;
    margin-bottom: 5px;
}


A better way to read text files into html? Currently I'm making a website that has a to-do list that will probably become quite long to write in html. So I decided to make a shorter version for me to write that I find more comfortable to read.

What I am currently doing is using ajax to read the text file from the server. Once the file has been stored into a string, it's sent to a function which formats it correctly for html. After that, it's returned into a variable that is now stored into a container div using jquery div.

This is my javascript code:

var todoListMake = function( reading ){
        var wanted =reading.split("\n");
        var newString = "";
        for( var i = 0; i < wanted.length; i ++ )
        {
            if( wanted[i] === "\n" )
                continue;
            /* Place text formatting code below */
            wanted[i] = wanted[i].replace("","");
            wanted[i] = wanted[i].replace("","");
            wanted[i] = wanted[i].replace("<c>","");
            wanted[i] = wanted[i].replace("</c>","");

            if( wanted[i].search("[X]") != -1 )
            {
                wanted[i] = "" + wanted[i].replace("[X]","") + "";
            }

            if( wanted[i].search("<ul") === -1 && wanted[i].search("</ul") === -1 )
                wanted[i] = "
" + wanted[i]; // Open the list if no ul tags

            if (i === (wanted.length-1) )
            {
                newString += wanted[i];
                break;
            }// Break early because the rest cannot be processed correctly

            if( wanted[i].search("</ul") != -1 )
                wanted[i] += "
"; // Close the list at the end of each ul

            if ( wanted[i + 1].search("</ul") != -1 )
                wanted[i] += "
";// Close the list of regular data

            //alert(wanted[i]);
            newString += wanted[i];
        }
        return newString;

};

window.onload = function(){
        $.get("textData/todoData.txt", function(data) {

 var compiledData = todoListMake( data );
            $("#todoList").append( compiledData );
        });
    };

And then read from the text file like this:

Release 1:
  Completed

Release 2:  Current Version

            Core Additions

                [X] Save Progress
                [X] <c>14</c> 9 New Levels

            Programmers Check List

                    [X] Add functionality to Level Restart
                    [X] Add checkpoint floater

            Bug Fixes

                    [X] Hanging on Slopes teleport you
                    [X] Hanging on Slopes froze the game
                    [X] Fixed Menu overlay problem

What do you mean with the variable name wanted? I don't understand what it has anything to do with what you are doing, so it's a badly chosen name.

if( wanted[i] === "\n" )
    continue;

This won't do anything. Since you split by "\n", there will be no line breaks leftover. I assume you want wanted[i] === "". Also consider .trim()ing all you lines, otherwise a stray white space will break this.

if (i === (wanted.length-1) )
    {
        // [...]
        break;
    }// Break early because the rest cannot be processed correctly

I'm not sure why you are "breaking early" here. Your condition triggers for the last line, so it's not really "early".

newString += wanted[i];

Repeated string concatenation is a slow process and uses a lot of memory. Instead just leave your strings in the array and at the end just return wanted.join();

EDIT: One more thing: Both the original div and the other ul you later add inside have the same id. That's invalid.

EDIT: Regarding the ID: In your script you have $("#todoList").append( compiledData ); so there's obviouly an element with the id todoList, but your template has the code <ul  id="todoList" class="workList"> in it, so you are creating a second element with the same ID.


Table of tournament scores Please let me know if you think I can improve the structure of his table code.

      Date

      Tournament

      Tournament Scores

      Result

      Score

Card

      Event/Scores Type

      Score

      -Par+

      R1

      R2

      R3

      R4

      R5

      Pos.

      SAR

      06-02-14

      Tourn

      (Gross)

      148

      +5

      72

      76

You have what appears to be an unnecessary break tag here.

Score

    Card


Performance problem when getting text from a context node with VTD-XML I have a structure like this:

<a>
  <b>
    <c>foo</c>
    <d>bar</d>
  </b>
  <b>
    <c>baz</c>
    <d>qux</d>
  </b>
</a>

I set /a/b as context and loop through all occurrences to get the texts of c and d:

VTDGen vg = new VTDGen();
vg.parseFile("test.xml", true);

VTDNav vn = vg.getNav();

AutoPilot ap = new AutoPilot(vn);

ap.selectXPath("/a/b");

while(ap.evalXPath() != -1) {
  String c = extractText(vn, "c");
  String d = extractText(vn, "d");
}

Currently, I use the extractText() method I've written to extract the texts of the nodes inside the loop:

public String extractText(VTDNav v, String path) throws Exception {
  VTDNav vn = v.cloneNav();
  AutoPilot ap = new AutoPilot(vn);

  ap.selectXPath(path);

  int elementIndex = ap.evalXPath();

  if(elementIndex == -1) {
    return null;
  }

  int tokenIndex = (path.contains("@"))
                    ? vn.getAttrVal(vn.toString(elementIndex))
                    : vn.getText();

  return (tokenIndex == -1) ? null : vn.toString(tokenIndex);
}

In the method, I clone the VTDNav and create a new AutoPilot instance so I don't displace the cursor of those objects of my loop when selecting the new XPath.

Furthermore, I have to check the path whether it contains an @, to see if it's an text node or an attribute (i.e. to use getText() or getAttrVal()).

My profiler shows that my extractText() method takes the most time in my huge application, so there must be a better solution here.

I've found a solution, which doesn't improve the performance, but is a lot shorter. I didn't know about the evalXPathToString() method.

protected String extractText(VTDNav v, String path) throws Exception {
  AutoPilot ap = new AutoPilot(v);
  ap.selectXPath(path);
  return ap.evalXPathToString();
}

Furthermore, the check in my old version whether the path contains a @ was buggy. It returned true for a path like /a[@b='c'] and executed getAttrVal() for it, which is wrong.


Counting Sequence Length in TIS-100 I picked up a programming game, TIS-100. Programming manual can be found on Steam as well, but I have described the relevant syntax in my question.

Basically, you're dealing with some old machine that uses its own variant of assembly. It's a gamification of learning assembly, almost.

The machine consists of nodes. Each node has pipes (UP LEFT DOWN RIGHT) that it can write and read from. When a pipe is read from, the value in the pipe disappears. It also has two registers, ACC and BAK. BAK can only be accessed with the SAV and SWP opcodes. Each node has its own code that it executes. This code is limited to 15 lines of 18 characters per node.

I've already solved this level. The goal is counting sequences:

- SEQUENCE COUNTER -
> SEQUENCES ARE ZERO-TERMINATED
> READ A SEQUENCE FROM IN
> WRITE THE SUM TO OUT.S
> WRITE THE LENGTH TO OUT.L

Short syntax run down (based on commands I used):

MOV <src> <dest> //moves from source to destination. Blocks if source is a pipe and doesn't have a value available. Blocks if dest is a pipe and already has a value.
ADD value //adds to ACC
<label>: //defines a label (for jumps)
JMP <label> //jumps execution to label
JEZ <label> //jumps to label if ACC = 0. JumpifEqualsZero
//there's also JumpifNotZero (JNZ), JumpifGreaterZero (JGZ), JumpifLesserZero (JLZ).
SAV //MOV ACC BAK
SWP //switches values of ACC and BAK

The game describes it like this:

My program is a bit unwieldy to post in full, so I'll limit it to the three main nodes.

This is the node responsible for counting the sequence length:

S: MOV LEFT ACC
JEZ E
SWP
ADD 1
SAV
JMP S
E: SWP
MOV ACC DOWN
MOV 0 ACC
SAV

This is the node responsible for summing sequences:

S: MOV UP ACC
JEZ E
MOV ACC LEFT
SWP
ADD LEFT
SAV
JMP S
E: SWP
MOV ACC DOWN
MOV 0 ACC

And this is the node I abuse as temporary storage:

MOV RIGHT ACC
MOV ACC RIGHT

What I don't like about my code is that it doesn't read very well.

The sequence counter goes like so:

START
read value to ACC
if ACC is 0, then GOTO END
swap ACC and BAK
add 1 to ACC
write ACC to BAK
GOTO START
END
swap ACC and BAK
write ACC as output
set ACC to 0
write ACC to BAK

There's duplication in here, where no matter if you are in the then or the (implicit) else case of the JEZ, you first swap ACC and BAK. Additionally, I'm abusing "swap set write" for altering BAK, but maybe that's the shortest way there is.

For the sequence summer, I don't like how I'm abusing a separate node just for temporary storage.

It works without errors.

For reference, these are histograms showing the scores of people on levels, with mine highlighted via arrow:

Unfortunately my hard drive containing my savegames crashed yesterday, so I cannot look up my solution, but I can say that the things you consider ugly are because of the limitations of that old computer system. I am abusing nodes as temporary storage all the time and my solution pretty much looked the same (if I remember correctly). As the histograms show you are not that bad (especially on cycles).

We can optimize your solution in terms of # of instructions and maybe cycles as well, though. I am focussing on optimizing the existing algorithms, instead of creating a new program. I could not test my optimized solution, because I don't have Steam on this box, but they should work none-the-less:

Your temporary storage node can be simplified to:

MOV RIGHT RIGHT

This is a valid instruction and saves you one instruction.
I only save my ACC just before it would get overridden. This removes some duplicate code (namely at least one SAV in your counter) and simplifies control flow. My rewritten algorithm is one instruction less than yours:

L:
SAV          # Save counter
MOV LEFT ACC # Next item
JEZ EZ       # End of sequence
SWP          # Restore counter
ADD 1        # Increment
JMP L        # Loop
EZ:          # End of sequence
SWP          # Restore counter
MOV ACC DOWN # Output
SUB ACC      # Clear ACC

BAK is not needed in your summing node. You only need the value from your temporary storage node and the new value. Some reordering of instructions allows you to directly add the saved sum to the new value. I again saved the ACC in the very last moment:

L:
MOV ACC LEFT  # Save sum
MOV UP ACC    # Next item
JEZ EZ        # End of sequence
ADD LEFT      # Add sum
JMP L         # Loop
EZ:           # End of sequence
MOV LEFT DOWN # Output sum
SUB ACC       # Clear ACC

Getting rid of BAK saved us 3 instructions on this one!

Conclusion: Absolutely abuse the instruction set (e.g. my first bullet point) and possibilities of the game (storing values in the pipes) to achieve good scores in the different metrics. Don't try to optimize for everything, you have got three saves per level!


Understand the dependency levels of makefiles Assume that the project has the following files, where the first files is dependent on the files under it's category in the unordered list:

main.c

global.h         (contains enumerations and #define macros)
sdlevent.h       (generic header file)

sdlevent.c   (contains implementations of sdlevent.h)

sdlshape.h       (generic header file)

sdlshape.c   (contains implementations of sdlshape.h)

Now, I have the following makefile:

CC = gcc
CFLAGS = -g -w -std=c99
LIBS = -lSDL2 -lSDL2_image -lSDL2_ttf

SRCS = main.c sdlshape.c sdlevent.c
OBJS = $(SRCS:.c=.o)
EXE = play

all: $(EXE)

.c.o:
    $(CC) -c $(CFLAGS) $<

$(EXE): $(OBJS)
    $(CC) -o $(EXE) $(OBJS) $(LIBS)

$(OBJS): global.h sdlevent.h sdlshape.h

run : all
    ./$(EXE)

clean:
    rm -f *.o *~ $(EXE)

  The target $(EXE) is dependent on the target .c.o. Do I absolutely need to define the target $(EXE) after the target .c.o?

I don't think so, because even though the target $(EXE) is dependent on the target $(OBJS), the target ($EXE) is declared before $(OBJS).

I have not divided up the header files into their .h and .c files because they are very small header files.

I would advice against this. Dividing into header and source files is just something you do. If something deserves an own source file, it also deserves an own header file. If nothing else, future readers of your code will expect .h files to only contain declarations. If you really don't want to split them up, then include the .c files instead. That's not good, but at least you're not hiding what you're doing.

Also, I don't really see the need to manually write dependencies. If your project is big, look into CMake or something. If it is small, use a generic Makefile. Here is a small example that basically contains everything you'll ever need before it's time to move on to CMake:

# Configuration

EXE = play
CFLAGS = -g -Wall -Wextra -std=c11
LDLIBS = -lm
LDFLAGS =

# Don't touch anything below

# Every .c is a source file (dough)
SRC = $(wildcard *.c)
# Every source file should be compiled to an object file
OBJ = $(SRC:.c=.o)
# Every object file should have a dependency file
DEP = $(OBJ:.o=.d)

# Link the exe from the object files
$(EXE): $(OBJ)
    $(CC) $(LDFLAGS) $^ -o $@ $(LDLIBS)

# Generate dependencies for the object files
%.o: %.c
    $(CC) -MMD -MP -c $< -o $@

# https://stackoverflow.com/q/2145590/6699433
.PHONY: clean

clean:
    $(RM) $(OBJ) $(DEP) $(EXE) *~

# Include the generated dependencies
-include $(DEP)

Note that you don't need to pass $(CFLAGS) to the CC commands. It's done automatically.

I used the above Makefile on this:

$ cat *.c *.h
/* bar.c */

#include "bar.h"
#include <math.h>

int bar(int a, int b) { return a*pow(b,3); }
/* foo.c */

#include "foo.h"
#include "bar.h"

int foo(int a, int b) { return a+bar(a,b); }
/* main.c */

#include "foo.h"

int main() { foo(1,2); }
/* bar.h */

#ifndef __BAR_H__
#define __BAR_H__

int bar(int a, int b);

#endif
/* foo.h */

#ifndef __FOO_H__
#define __FOO_H__

int foo(int, int);

#endif

I sacrificed a bit of readability to keep number of lines down. After running make I have a couple of .d files.

$ cat *.d
bar.o: bar.c bar.h

bar.h:
foo.o: foo.c foo.h bar.h

foo.h:

bar.h:
main.o: main.c foo.h

foo.h:


JUnit - Test whether object was persisted or not I am using Hibernate 4 and Spring Framework 4. I wrote a simple test to check whether object was persisted or not.

All set values in confirmationEntity are required.

In this test I relly on that, that after a new object is persisted, then it is given a new id automatically.

Is this correct way how to determine if the object was persisted or not? Or is there better way?

@Test
public void testCreated(){
    ConfirmationTypeEntity confirmationTypeEntity = confirmationTypeDao.find(1L);
    UserEntity userEntity = userDao.find(1L);

    ConfirmationEntity confirmationEntity = new ConfirmationEntity();
    confirmationEntity.setConfirmationTypeEntity(confirmationTypeEntity);
    confirmationEntity.setUserEntity(userEntity);
    confirmationEntity.setConfirmationString("5374a74e9542f");
    confirmationEntity.setConfirmationStringValidUntil(new LocalDateTime());

    confirmationDao.create(confirmationEntity);
    confirmationDao.flush();

    Assert.assertNotNull("Expected not null value.", confirmationEntity.getId());
}

I'm going to assume that you have a standard DAO setup so you should try the following.

@Test
public void testCreated(){
    ConfirmationTypeEntity confirmationTypeEntity = confirmationTypeDao.find(1L);
    UserEntity userEntity = userDao.find(1L);

    ConfirmationEntity confirmationEntity = new ConfirmationEntity();
    confirmationEntity.setConfirmationTypeEntity(confirmationTypeEntity);
    confirmationEntity.setUserEntity(userEntity);
    confirmationEntity.setConfirmationString("5374a74e9542f");
    confirmationEntity.setConfirmationStringValidUntil(new LocalDateTime());

    int countPreSave = confirmationDao.count();

    confirmationDao.create(confirmationEntity);

    /* This call has the advantage of getting Hibernate to flush the session
     * to prevent you reading stale data in your count call.
     */
    int countPostSave = confirmationDao.count();

    assertEquals("The number of confirmations doesn't match what was expected",
                  countPostSave,
                  countPreSave + 1);

There, you've just ensured that your object was saved correctly, and only 1 record was inserted. You can do similar things for update (ensure countPreUpdate and countPostUpdate match) and delete (ensure countPostDelete = countPreDelete - 1)

If you don't have a count() method, here is the Hibernate criteria implementation:

@Override
public int count() {
    Criteria criteria = getCurrentSession().createCriteria(type);
    criteria.setProjection(Projections.rowCount());
    return (Integer) criteria.uniqueResult();
}


Bank saving account class in Python (pandas) I am setting up a kids bank account class to teach them how to save, and myself how to write a class in Python. The original idea was to create a pandas DataFrame that will show how the money gains interest by loading:

<AccountName>.df

First I created the DataFrame of 365 days with datetime.date.today() + datetime.timedelta(days=236) as the indices which I guess made the looking up of index for the daily interest increment a bit cumbersome... to say the least.

class  Account:

    def __init__(self, holder, start_date):
        import datetime
        import pandas as pd

        self.df = pd.DataFrame(index=pd.date_range(start_date, start_date + datetime.timedelta(365), freq='D'), columns=['deposit', 'withdrawl', 'balance'])
        self.df.withdrawl = 0.0
        self.df.deposit = 0.0
        self.df.balance = 0.0
        self.df.dif = 0.0

        for i in self.df.index[1:]:
            self.df.loc[i,('balance')] = self.df.loc[str(datetime.datetime.strptime(str(i)[:10], '%Y-%m-%d') - datetime.timedelta(days=1))[:10], ('balance')] * (1+(0.08 / 365))

        self.history = []

        self.holder = holder

    def __str__(self):
        return 'The account of: {0}, balance is: {1} '.format(self.holder, self.df.loc[str(datetime.datetime.today())[:10], 'balance'])

    def __repr__(self):
        return '{0.__class__.__name__}(name={0.holder})(balance={1})'.format(self, self.df.loc[str(datetime.datetime.today())[:10], 'balance'])

    def get_balance(self):
        return self.df.loc[str(datetime.datetime.today())[:10], 'balance']

    def make_deposit(self, amount, date):
        self.history.append((amount, date))
        if type(date) is datetime.datetime or datetime.date:
            self.df.loc[date.strftime('%Y-%m-%d'), ('deposit')] += amount
            self.df.loc[date.strftime('%Y-%m-%d'), ('balance')] += amount
        for i in self.df.index[self.df.index.slice_locs(date + datetime.timedelta(days=1))[0] :]:
            self.df.loc[i, 'balance'] = self.df.loc[i-datetime.timedelta(days=1), 'balance']* (1+(0.08 / 365)) + self.df.loc[i, 'deposit'] - self.df.loc[i, 'withdrawl']

    def withdraw_money(self, amount, date):
        self.history.append((amount*-1, date))
        if type(date) is datetime.datetime or datetime.date:
            self.df.loc[date.strftime('%Y-%m-%d'), ('withdrawl')] += amount
            self.df.loc[date.strftime('%Y-%m-%d'), ('balance')] -= amount
        for i in self.df.index[self.df.index.slice_locs(date + datetime.timedelta(days=1))[0] :]:
            self.df.loc[i, 'balance'] = self.df.loc[i-datetime.timedelta(days=1), 'balance']* (1+(0.08 / 365)) + self.df.loc[i, 'deposit'] - self.df.loc[i, 'withdrawl']

I am looking for improvement ideas for that (also repeating in all the functions). I am also looking for a neater way, within pandas of assigning yesterday's balance + todays deposit - today's withdraw + the daily interest rate. (I know it's an extremely generous interest, but they are my kids after all and with the little pennies they manage to collect it doesn't amount to much...)

I start an account like so:

import datetime
test = Account('my_name', datetime.date.today())

I've improved my __str__ and __repr__ methods after I read all the suggestions suggested on this question, didn't do anything about privacy and properties but first thing first.

Wouldn't changing the date from the index to its own column and using integer indices make it easier to access and lookup data?

I think your design is a bit "overkill". After all, banks don't keep empty records for each day of the year, waiting for you to come along and perform a transaction.
Rather than using a DataFrame, I think you'd be better off separating the data record into a class of its own, with the increment and decrement functions.

The display functionality is not part of the data record, it would be a separate class itself, and inheritable by ATMs or a Teller/Bank Manager/technician's computer. Regardless, this is something for kids, so it's fine to violate some SOLID principals.

Regarding def __init__(self, holder, start_date): you could probably make start_date = date.today() as transactions tend to happen on the same day, unless you're performing some cheque activity (which is delayed).

As to your question, if you change the date from the index into its own column, you're shifting the column[:loc] as the lookup, essentially adding an extra step.
For using integer indices to lookup data, it's a bad idea as you should try to keep any [lookup_integer] values as defined constants - so they're not arbitrary numbers (you'd be surprised how often people make simple input mistakes when coding, and as they're usually valid integers, people are scratching their heads why a date is in the address of a decimal number (addition and subtraction would then still be valid operations, so it's not picked up immediately unless you're performing tests on data as part of your CI process, and you go live with faulty code).

Good luck!


Is this a fast implementation of reversing a string? I thought of this algorithm today. It seems fast, but how can I know?

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

/*
 * Reverse a string
 * the caller has to free dynamic memory allocated
 */
char *mon_string_rev(char *string)
{
    char *out = malloc ( strlen(string) + 1 );

    assert(out);

    int len = strlen(string);

    int i;

    int counter = 0;

    int iterations = 0;

    while(1) {
        if(len < 0) break;
        // important to only start counting after
        // determing that the loop will continue
        ++iterations;
        for(i = 0; i < len; i++) {
            // if this is the last character
            // push it onto the output string
            if(i == (len - 1)) {
                out[counter] = string[i];
                counter++;
            }
        }
        len--;
    }
    out[counter] = '\0';

    printf("Total iterations: %d\n", iterations);

    return out;

}

int main(int argc, char **argv)
{

    if(argc < 2) {
        fprintf(stderr, "Usage: %s <string>", argv[0]);
        exit(1);
    }

    char *str = mon_string_rev(argv[1]);

    printf("%s\n", str);

    free(str);

    return !1;

}

Over all, this is good, but there's unfortunately some very major performance problems, and I have a few minor design suggestions.

A string can be reversed quite trivially in linear time. Your algorithm is quadratic.

You can just do a single backwards loop over the input string instead of this convoluted nested loop.

Since mon_string_rev doesn't alter string it should be a pointer to constant character.

Instead of asserting that out isn't null, it might be better to simply return null instead. That allows the caller to handle the error instead of program termination (and when assertions are disabled, it avoids a rather nasty segfault...).

If you're using C99 or newer (and you should be), then declare variables in the tightest scope possible (i.e. declare i in the for loop).

return !1;... what? Just return 0, or, better yet, return EXIT_SUCCESS.

Any time you have an infinite loop terminated by a simple condition, just rewrite it to directly use that simple condition. Terminating 'infinite' loops are very hard to understand when you weren't the person who wrote them, so any time they can be avoided they should be.

Just to illustrate, your loop could instead be: for (; len >= 0; --len) { ... }.

It doesn't really apply here since instrumentation was clearly the main purpose, but in general it's a bad idea to have functions output anything unless their sole purpose is output. (Sorry if you already know this :).)

When it doesn't meaningful affect performance or usability, I like to have the caller manage memory. It's more flexible, and it's more explicit (no question of "wait... do I release this???").


CSS3 transitions performance enhancement I am building a website with heavy CSS3 transitions. The menu is hidden on the left and slides in on hover pushing the main content right. The menu contains transformed elements and has a semi transparent background.

I am concerned about the performance of the animations. When the animation is triggered several times (and also often on the first trigger) the frame rate goes under 30 FPS.

How can I enhance the performance of the animation and have a higher frame rate?

I tried making these animation with jQuery and it is worse.

I made a simple example that has the FPS issue here (hover the envelope icons on the left).

HTML:

body,html,ul,li {margin: 0; padding: 0;}
nav {
  width: 0; height: 100%;
  position: fixed;
  top: 0; left: 0;
  background-color: rgba(255, 145, 0, 0.8);
  -webkit-transition: width .5s ease-out;
  transition: width .5s ease-out;
}
nav:hover {
  width: 40%;
}
ul {
  list-style-type: none;
  position: absolute;
  width: 60%;
  left: 20%;
}
nav li {
  position: relative;
  margin: 0.5em 0;
  padding: 0.5em;
  min-width: 5em;
}
nav li:before {
  content: '';
  position: absolute;
  width: 100%;
  height: 100%;
  background: teal;
  z-index: -1;
  opacity: 0;
  -webkit-transform: skewX(30deg);
  -ms-transform: skewX(30deg);
  transform: skewX(30deg);
  -webkit-transition: opacity .5s ease-out;
  transition: opacity .5s ease-out;
}
nav:hover li:before {
  opacity: 1;
}
nav li * {
  vertical-align: middle;
}
nav img {
  height: 2em;
}
nav a {
  opacity: 0;
  -webkit-transition: opacity .5s ease-out;
  transition: opacity .5s ease-out;
}
nav:hover a {
  opacity: 1;
}
/* MAIN */

section {
  width: 60%;
  margin-left: 20%;
  min-height: 100%;
  background: url(http://lorempixel.com/output/nature-q-g-640-480-9.jpg);
  -webkit-transition: margin-left .5s ease-out;
  transition: margin-left .5s ease-out;
}
nav:hover +section {
  margin-left: 30%;
}

Home

About

Clients

Contact

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vivamus porta augue vitae bibendum vulputate. Nam sed pulvinar neque. Pellentesque justo neque, aliquet at risus sed, tristique mattis purus. In laoreet diam at porttitor tempor. Vestibulum ante
    ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Cras in lorem sit amet purus egestas aliquet. Cras dignissim venenatis facilisis. Suspendisse id dui consectetur, lobortis mauris nec, egestas augue. Sed dui sapien, dignissim
    in dui eget, pretium laoreet leo. Phasellus semper faucibus elit eu consequat. Maecenas aliquam nibh sit amet sapien blandit, non sagittis mi vestibulum.

  ... More content ...

I'm pretty new to CSS, but I do have a few notes:

As @Jivings said, the animation worked nicely for me.  No stutter
or anything.
I would use Font Awesome instead of your envelope .png (but keep the PNG as a fallback for cases such as some IE versions not supporting SVG).  Why?  Because now I can scale the envelope infinitely (due to SVG graphics), and customization of the image becomes a whole lot easier (size, color, drop shadow, etc.).
You should give a little bit more space between the envelope picture and the item text.

nav:hover a {
    margin-left: 5%;
    opacity: 1;
}

I think it looks nicer with the picture and text centered.

nav:hover {
    text-align: center;
    width: 40%;
}

JSFiddle with the suggested changes.


natas11 helper program Intro

I've been having fun with natas a wargame, from overthewire.

To pass a certain stage I had to do some xor'ing, in combination with base64 encoding/decoding. So I wrote a little python utility to help me pass that stage.

Any feedback on the code I've written is helpfull, but I'm especially interested in the repeated_substring() function. I don't think my function is the most optimised way of handling that.

When I run the code it should output the newly generated cookie value:

b'ClVLIh4ASCsCBE8lAxMacFMOXTlTWxooFhRXJh4FGnBTVF4sFxFeLFMK'

Code

import base64

def xor_break_cookie(cookie):
    """Breaking the key"""
    json = b'{"showpassword":"no","bgcolor":"#ffffff"}'
    return ''.join([chr(cookie[i] ^ json[i % len(json)]) for i in range(len(cookie))])

def decode_base64(data):
    """Decoding with the missing padding"""
    missing = len(data) % 4
    if missing != 0:
        data += b'=' * (4 - missing)
    return base64.decodestring(data)

def xor_gen_cookie(key):
    """Getting the new cookie value"""
    json = b'{"showpassword":"yes","bgcolor":"#ffffff"}'
    return ''.join([chr(json[i] ^ key[i % len(key)]) for i in range(len(json))])

def repeated_substring(text):
    """Gets the longest repeated xor key from text"""
    length = x = y = m = 0
    for y in range(len(text)):
        for x in range(len(text)):
            substring = text[y:x]
            if len(substring) > length and text.count(substring) >= m and len(substring) > 1:
                m, length, match = text.count(substring), len(substring), substring
    return match

if __name__ == '__main__':
    cookie = decode_base64(b'ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw')
    password = repeated_substring(xor_break_cookie(cookie))
    new_cookie = xor_gen_cookie(bytes(str.encode(password)))
    print(base64.encodestring(bytes(str.encode(new_cookie))).rstrip())

xor_break_cookie is almost exactly the same as xor_gen_cookie. I'd change them to be the same function, xor_repeat, with varing input.
Rather than using a[i] ^ b[i % len(...)] for i in range(len(...)), you can use zip, and itertools.cycle.

v ^ r for v, r in zip(value, cycle(repeater))

Rather than using str.encode('abc'), you can use 'abc'.encode(). It also doesn't make sense to use str.encode, it's un-common to see in Python, and provides no benifit here.
Rather than using bytes('abc'.encode()) you can just use 'abc'.encode().
Rather than ''.join(...).encode(), you can use bytes(...).
In decode_base64, if you merge the modifications of missing into one line you get:

missing = 4 - (len(data) % 4) if (len(data) % 4) != 0 else 0

This can be simplified if you use two modulos, rather than an if. \$(4 - i \% 4) \% 4\$.
This however can be further simplified, if you make the left hand side negative, and so you can use \$-i \% 4\$.

And so I'd use:

def decode_base64(data):
    return base64.decodestring(data + b'=' * (-len(data) % 4))

You can ensure that len(substring) > 1, if you start x at y+1.
It doesn't make sense to me to generate values, and also find the max in the same function. Split them apart.
By splitting the generating code, and the max finding code apart, you can use max:

max(_repeated_substring(text), key=lambda t: (len(t), text.count(t)))

Rather than having \$O(n^3)\$ time complexity, you can get a \$O(n^2)\$ time and \$O(n)\$ space complexity solution by using Counter.

In all I'd use something like the following. I also provide the above two ways to find the maximum:

import base64
from itertools import cycle
from collections import Counter

def xor_repeat(value, repeater):
    return bytes(v ^ r for v, r in zip(value, cycle(repeater)))

def decode_base64(data):
    return base64.decodestring(data + b'=' * (-len(data) % 4))

def _repeated_substring(text):
    for i in range(len(text)):
        for j in range(i+1, len(text)):
            yield text[i:j]

def repeated_substring(text):
    return max(_repeated_substring(text), key=lambda t: (len(t), text.count(t)))

def repeated_substring(text):
    vals = Counter(_repeated_substring(text))
    return max(vals.items(), key=lambda i: (len(i[0]), i[1]))[0]

BREAK_JSON = b'{"showpassword":"no","bgcolor":"#ffffff"}'
GEN_JSON = b'{"showpassword":"yes","bgcolor":"#ffffff"}'

if __name__ == '__main__':
    cookie = decode_base64(b'ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw')
    password = repeated_substring(xor_repeat(cookie, BREAK_JSON))
    new_cookie = xor_repeat(GEN_JSON, password)
    print(base64.encodestring(new_cookie).rstrip())


Manipulating the global address book in Outlook I am using VBA to manipulate the global address book in Outlook.  My method takes a contact and returns a complete list of everyone who reports through that person based on the Outlook org structure.

Unfortunately it takes quite some time to run, even for a single manager.  I'm not really sure what is the best way to improve the performance here - it sees the getDirectReports method takes some time, but, I don't see an easy way to determine if a user has reports prior to calling it first.

Public Sub printAllReports()

    Dim allReports As Collection
    Set allReports = New Collection

    Dim curLevelReports As Collection
    Set curLevelReports = New Collection

    Dim nextLevelReports As Collection
    Set nextLevelReports = New Collection

    Dim myTopLevelReport As ExchangeUser

    'this method returns an exchange user from their "outlook name"
    Set myTopLevelReport = getExchangeUserFromString("outlook resolvable name here")

    'add to both the next level of reports as well as all reports
    allReports.Add myTopLevelReport
    curLevelReports.Add myTopLevelReport

    Dim tempAddressEntries As AddressEntries
    Dim newExUser As ExchangeUser
    Dim i, j As Integer

    'flag for when another sublevel is found
    Dim keepLooping As Boolean
    keepLooping = False

    Dim requireValidUser As Boolean
    requireValidUser = False

    'this is where the fun begins
    Do

        'get current reports for the current level
        For i = curLevelReports.Count To 1 Step -1

            Set tempAddressEntries = curLevelReports.item(i).GetDirectReports

            'add all reports (note .Count returns 0 on an empty collection)
            For j = 1 To tempAddressEntries.Count
                Set newExUser = tempAddressEntries.item(j).getExchangeUser

                'isExchangeUserActualEmployee has some short boolean heuristics to make sure
                'the user has at least a title and an email address
                If (isExchangeUserActualEmployee(newExUser) = True Or requireValidUser = False) Then
                    allReports.Add newExUser
                    nextLevelReports.Add newExUser
                    keepLooping = True
                End If

            Next j
            Set tempAddressEntries = Nothing

        Next i

        'reset for next iteration
        Set curLevelReports = nextLevelReports
        Set nextLevelReports = New Collection

        'no more levels to keep going
        If keepLooping = False Then
            Exit Do
        End If

        'reset flag for next iteration
        keepLooping = False

    Loop

    Dim oMail As Outlook.MailItem
    Set oMail = Application.CreateItem(olMailItem)

    'do stuff with this information (currently just write to new email, could do other cool stuff)
    For i = 1 To allReports.Count
        oMail.Body = oMail.Body + allReports.item(i).name + ";" + allReports.item(i).JobTitle
    Next i

    oMail.Display

End Sub

Your printAllReports method does almost everything that's possible to do with the Outlook API (ok maybe not), except printing anything. You basically have what we call a monolith, and that's bad because as your program changes, you are tempted to just keep adding and adding and adding, until the thing becomes an unmanageable, tangled mess. If you're going to call a method printAllReports, give it a signature like this: Sub printAllReports(allReports As Collection), so its intent is clear at first glance - and then make it do one thing; print all reports.

Performance-wise, the major hit is going to be hitting the Exchange server, so your code needs to make sure it hits the server only when it's necessary. If that's already the case, chances are you've already got it as good as it gets.

I think your multiple collections and 3-layer deep nested loop approach isn't the easiest way to make your code readable and maintainable, let alone to fine-tune its performance.

HierarchicalUser

The beautiful thing about a language that allows you to define objects, is that doing so actually adds vocabulary to that language, so no matter how lame VBA/VB6 is, with your own objects you can add new nouns, and with your own methods you can add new verbs, and with enough of them you actually end up crafting a language (ok, an API) that's beautiful in its own way.

You have the concept of an ExchangeUser, that can report to another ExchangeUser, and that can have ExchangeUser underlings. I call that a hierarchy, and I'd recommend you encapsulate that ExchangeUser into your very own HierarchicalUser class, something along those lines:

private type tHierarchicalUser
    User As ExchangeUser
    Superior As HierarchicalUser
    Underlings As New Collection
end type

private this As tHierarchicalUser
Option Explicit

Public Property Get User() As ExchangeUser
    Set User = this.User
End Property

Public Property Set User(value As ExchangeUser)
    Set this.User = value
End Property

Public Property Get Superior() As HierarchicalUser
    Set Superior = this.Superior
End Property

Public Property Set Superior(value As HierarchicalUser)
    Set this.Superior = value
End Property

Public Property Get Underlings As Collection
    'DO NOT return a reference to the encapsulated collection, you'll regret it!
    Dim result As New Collection, underling As HierarchicalUser
    For Each underling In this.Underlings
        result.Add underling
    Next
    Set Underlings = result
End Property

Public Sub AddUnderling(underling As HierarchicalUser)
    Set underling.Superior = Me
    this.Underlings.Add underling 'you can use a key here to ensure uniqueness
End Sub

'almost forgot!
Public Function FlattenHierarchy() As Collection
    Dim result As New Collection

    'traverse whole hierarchy and add all items to a collection that you return

    Set FlattenHierarchy = result
End Sub

Then you'll need a way to create instances of this class, and populate them. Enter the HierarchicalUserFactory (well, I know I would put that in its own class, but that's just me) - instead of nesting code we're going to be nesting method calls, recursively:

Public Function CreateHierarchicalUser(exUser As ExchangeUser) As HierarchicalUser
    Dim result As New HierarchicalUser
    Dim entry As AddressEntry
    Dim underling As ExchangeUser

    set result.User = exUser

    For Each entry In exUser.GetDirectReports() '<< For Each won't loop if there's nothing in the collection

        'if possible, run the isExchangeUserActualEmployee logic off this 'entry' object,
        'so you can only call the expensive GetExchangeUser method if needed:
        set underling = entry.GetExchangeUser
        result.AddUnderling CreateHierarchicalUser(underling) '<<< recursive call!

    Next

    Set CreateHierarchicalUser = result
End Function

Haven't tested any of this, but I believe an approach along those lines could possibly help you reduce the amount of GetExchangeUser calls and thus increase performance... not to mention readability++ :)

So your printAllReports method could possibly look like this now:

Public Function getHierarchy(topLevelUserName As String) As HierarchicalUser
    Dim factory As New HierarchicalUserFactory
    Dim topLevelUser As ExchangeUser

    Set topLevelUser = getExchangeUserFromString(topLevelUserName)
    Set GetHierarchy = factory.CreateHierarchicalUser(topLevelUser)
End Sub

Public Sub printAllReports(hierarchy As HierarchicalUser)

    Dim reports As Collection
    Set reports = hierarchy.FlattenHierarchy()

    'do all that cool stuff you wanted to do!

End Sub

Nitpicks

When you declare an object variable and assign it to a New instance on the next line, consider combining the two statements into one: Dim X As New Y.
When you declare a Boolean, it's automatically initialized to False so your post-declaration assignments are redundant.
When you evaluate a Boolean expression in an If statement, you don't need to specify =True or =False - rather, just say If SomeBooleanExpression Then or If Not SomeBooleanExpression Then.
When looping through objects in a collection, ALWAYS use a For Each construct. This will avoid weird stuff like For i = 1 To MyCollection.Count when .Count is 0, even someone that knows the VBA/VB6 collection base rules like the palm of their hand will go "huh?". For...Next has been around since before objects even existed, that construct is for traversing arrays. Collections deserve a For Each.


PDO (MySQL) connection and query class, safety and logic For the last few day I tried to figure out how to work with MySQL and PDO. Although I've tried to read a lot about the subject, there are still a lot of things I don't understand.

Because of this lack of knowledge, I can't really judge this code (or other example code on-line) on its safety and logic, and therefore was hoping I could get some feedback on it.

The class makes a connection and returns a query:

class Connection
{
private $username = "xxxx";
private $password = "xxxx";
private $dsn = "mysql:host=host;dbname=name_db";
private $sql;
private $DBH;

function setSQL($sql){
    $this->sql = $sql; //if $sql is not set it troughs an error at PDOException
}

public function query()
{
    //the connection will get established here if it hasn't been already
    if (is_null($this->DBH))
        try {
            $this->DBH = new PDO( $this->dsn, $this->username, $this->password );
            $this->DBH->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );

            //query
            $result = $this->DBH->prepare($this->sql);
            $result->execute();
            return $result->fetch(PDO::FETCH_ASSOC);

        } catch(PDOException $e) {

            echo "I'm afraid I can't do that1.";
            //file_put_contents('PDOErrors.txt', $e->getMessage(), FILE_APPEND);
        }
}

//clear connection and variables
function __destruct(){
        $this->DBH = null;
}

}

Using the class:

$sql = "SELECT * from stock WHERE id = 302";
$test = new Connection();
$test->setSQL($sql);
echo $test->query();

1) When using PDO, you want to get the benefits of automatic parameter escaping.
By wrapping your PDO class you are limiting it's functionality. Check out this question for a better example:

https://stackoverflow.com/questions/6366661/php-pdo-parameterised-query-for-mysql

2) Every time you run a query you are making a new PDO instance. It might be better to have an application resource pool that you can call to get a preconfigured db handle.

3) You wrote some sql to be able to fetch a stock by ID, that should probably be functionality that is reusable.

combining 1 & 2 & 3 .. code would probably look better as something like this:

class ApplicationResourcePool
{
    static var $_dbHandle;

    private static $_dbConfig = array(
        'dsn'      => '',
        'username' => '',
        'password' => '',

    );
    public static getDbHandle(){
        if(self::$_dbHandle == null){
            self::$_dbHandle = new PDO(
                self::$_dbConfig['dsn'] ,
                self::$_dbConfig['username'],
                self::$_dbConfig['password']
            );
        }
        return self::$_dbHandle;
    }

}

class StockMapper
{
    protected $_dbh;
    public __construct($dbh = null)
    {
        if($dbh == null){
            $this->_dbh = ApplicationResourcePool::getDbHandle();
        } else {
            $this->_dbh = $dbh;
        }

    }
    public getStockById($stockId){

        $sth=$this->_dbh->prepare("SELECT * from stock WHERE id = :stockId");
        $sth->bindParam(":stockId", $stockId);
        $sth->execute();
        $result = $sth->fetch(PDO::FETCH_ASSOC);
        return $result[0];
    }
}

your codeBlock then becomes:

$stockMapper = new StockMapper();
$stockData = $stockMapper->getStockById('302');


Huffman tree Python implementation """
### General Idea:

Given a set of n character set C.

1. Begin with a set of |C| leaves.
2. Repeatedly using **min-priority** queue `Q`, keyed on frequencies,
   identify the two least-frequent objects to merge together.
3. Until all be merged.

### Input

List of tuple containing frequency and character.

### Output

A tree T, called Huffman tree.
"""

import heapq

class Node(object):
    def __init__(self, key, freq, left=None, right=None):
        self.key = key
        self.freq = freq
        self.left = left
        self.right = right

    def __cmp__(self, other):
        return cmp(self.freq, other.freq)

    def __str__(self):
        return "({0}, {1})".format(self.key, self.freq)

    def __repr__(self):
        return self.__str__()

def encode(rel_freq):
    nodes = create_leaf_nodes(rel_freq)
    heapq.heapify(nodes)
    root = build_encode_tree(nodes)
    #print_tree(root)
    return root

def create_leaf_nodes(rel_freq):
    return map(lambda (freq, key): Node(key, freq), rel_freq)

def merge(n1, n2):
    freq = n1.freq + n2.freq
    if n1.freq <= n2.freq:
        return Node(n1.key + n2.key, freq, n1, n2)
    return Node(n2.key + n1.key, freq, n2, n1)

def build_encode_tree(nodes):
    root = nodes[0]
    while len(nodes) > 1:
        n1 = heapq.heappop(nodes)
        n2 = heapq.heappop(nodes)
        root = merge(n1, n2)
        heapq.heappush(nodes, root)
    return root

# ---------------- Helpers --------------------------
def print_tree(root):
    for nodes in level_order(root):
        for node in nodes:
            print node,
        print

def level_order(node):
  """Given Binary Tree gives list nodes in each level."""
  current_level = [node]
  while current_level:
    yield current_level
    next_level = []
    for node in current_level:
      if node.left:
        next_level.append(node.left)
      if node.right:
        next_level.append(node.right)
    current_level = next_level

import unittest

class TestHuffmanEncoding(unittest.TestCase):
    def test_single_char(self):
        rel_freq = [(24, 'A')]
        actual = str(encode(rel_freq))
        self.assertEqual(actual, "(A, 24)")

    def test_valid_encoding(self):
        #expected = [('A', '0'), ('B', '100'), ('C', '101'), ('D', '110'), ('E', '111')]
        rel_freq = [(24, 'A'), (12, 'B'), (10, 'C'), (8, 'D'), (8, 'E')]
        expected = "(AEDCB, 62)"
        actual = str(encode(rel_freq))
        self.assertEqual(actual, expected)

        rel_freq = [(45, 'A'), (13, 'B'), (12, 'C'), (16, 'D'), (9, 'E'), (5, 'F')]
        expected = "(ACBFED, 100)"
        actual = str(encode(rel_freq))
        self.assertEqual(actual, expected)

if __name__ == '__main__':
    unittest.main()

Note:

The code do generate the Huffman tree but I am more interested in finding the encoding of each character, the basic approach what I think is traversing each path from root to leaf such that moving left adds 0 to the path and moving right adds 1. Hopefully I would post the solution soon in another review.

Merging is a thing a node and only a node does, using that function on a non-node is meaningless so include it in the node class:

class Node:
    ...
    def merge(self, other_node):

Now the person that uses your code knows that merge works for nodes and nothing else and the code has more structure.


Cleaner Way to Test for Types? I defined a function that multiplies its argument by 3:

coffee> foo = (x) -> x * 3
[Function]

We can call it with an input of 1:

coffee> foo(1)
3

However, when I tried with a non-Number type:

coffee> foo("3")
9

This behavior appears wrong to me since a String cannot be multiplied by a Number.

To fix it, I'd add something like this:

foo = (x) ->
  if typeof x is 'number'
    x * 3
  else
    throw new Error("not a number:"  + x)

Is there a cleaner way to do this in CoffeeScript?

CoffeeScript is, in the end, just JavaScript with a nicer syntax. So the string-interpreted-as-number behavior is expected and normal. You write:

  This behavior appears wrong to me since a String cannot be multiplied by a Number.

Yet, due to type coercion in JavaScript, a string can be multiplied by a number just fine. And, importantly, the result is correct!

Your options with regard to strict type-checking are:

Using typeof and throwing an exception (or handling it some other way), as you do now.
Doing nothing.

You're still writing JavaScript, so option #2 is a valid solution to most type concerns. For instance, most (all?) the functions in the Math object accept numerical strings just as well as numbers.

For other types, the GIGO principle usually applies: Garbage In, Garbage Out. I.e. if the user of your code passes something completely incompatible, like an object, they'll get NaN back. And that's their problem, really. Same as if you do Math.floor({}) or something.

However, if type-checking is absolutely necessary, you can at least slim your code down a bit:

foo = (x) ->
  throw new TypeError unless typeof x is 'number'
  x * 3

Note that the code throws a TypeError, which is more appropriate for this situation, and that, since it throws, execution of the function is halted just as effectively as writing return. So there's no need for if...else branches.

You can generalize it a bit with a function, if you need to do this more often:

assertNumber = (value) ->
  unless typeof value is 'number'
    throw new TypeError("Expected a Number")

Or, better yet, check whether the value is numeric:

assertNumeric = (value) ->
  if isNaN Number(value)
    throw new TypeError("Expected a numeric value")

And use it like so:

foo = (x) ->
  assertNumeric x
  x * 3


Minimum Absolute Distance I solved this problem

  Given three sorted arrays A, B and C of not necessarily same sizes.

  Calculate the minimum absolute difference between the maximum and
  minimum number from the triplet a, b, c such that a, b, c belongs
  arrays A, B, C respectively. i.e. minimize | max(a,b,c) - min(a,b,c)
  |.

  Example :

  Input:

  A : [ 1, 4, 5, 8, 10 ] B : [ 6, 9, 15 ] C : [ 2, 3, 6, 6 ]

  Output:

  1

  Explanation:

  We get the minimum difference for a=5, b=6, c=6 as |
  max(a,b,c) - min(a,b,c) | = |6-5| = 1.

The idea behind my solution was if at each iteration we have the closest triplets we will be able to get the optimal absolute minimum.

I  couldn't find a clean way to implement this logic. And my solution is this.

int Solution::solve(vector<int> &A, vector<int> &B, vector<int> &C) {
    int answer = INT_MAX;
    int a = 0, b = 0, c = 0;
    while(a < A.size() || b < B.size()  || c < C.size() )
    {
        // cout << a << ' ' << b << ' ' << c << endl;
        int MinVal = min(min(A[a], B[b]), C[c]);
        int MaxVal = max(max(A[a], B[b]), C[c]);
        bool na = false, nb = false, nc = false;
        answer = min(answer, abs(MaxVal - MinVal));
        if(a + 1 < A.size() && A[a + 1] <= MaxVal)
        {
            ++a;
        }
        else if(b + 1 < B.size() && B[b + 1] <= MaxVal)
        {
            ++b;
        }
        else if(c + 1 < C.size() && C[c + 1] <= MaxVal)
        {
            ++c;
        }
        else
        {
            // cout << "Next Max\n";
            int next_a = a + 1 < A.size() ? A[a + 1] : INT_MAX;
            int next_b = b + 1 < B.size() ? B[b + 1] : INT_MAX;
            int next_c = c + 1 < C.size() ? C[c + 1] : INT_MAX;
            // cout << next_a << ' ' << next_b << ' ' << next_c << endl;
            if(next_a <= min(next_b, next_c) && next_a != INT_MAX)
            {
                ++a;
            }
            else if(next_b <= min(next_a, next_c) && next_b != INT_MAX)
            {
                ++b;
            }
            else if(next_c < min(next_a, next_b) && next_c != INT_MAX)
            {
                ++c;
            }
            else
            {
                break;
            }

        }
    }
    return answer;
}

Could you please suggest how to avoid excessive if-else statements in the solution. Also, this solution wouldn't be scaleable for more array's so a more general approach would be helpful as well

Headers and namespace

We're missing headers

#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>

Also, it appears the code assumes using namespace std.  Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Code the solution, and adapt it to fit

The use of the Solution class appears to be an artefact of your test environment.  Since the function doesn't need any state, prefer to write it as you normally would:

// we'll change this signature later
static int minimum_range(const std::vector<int> &A,
                         const std::vector<int> &B,
                         const std::vector<int> &C);

And then provide Solution as a thin wrapper around it, like:

int Solution::solve(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
    return minimum_range(a, b, c);
}

We can then call minimum_range from our test program much more simply:

int main()
{
    return
        + (0 != minimum_range(std::vector{5}))
        // add more tests here
        + (1 != minimum_range(std::vector{1, 4, 5, 8, 10}, std::vector{6, 9, 15}, std::vector{2, 3, 6, 6}));
}

We might make an exception to this general advice in the case of competitive performance-oriented programming; but then code review goes out of the window entirely, as speed trumps style and maintainability there.

Algorithm

The method is basically sound; it scales well to large vectors, but doesn't scale well to many vectors (as you note in the description).

For general code, prefer to think in iterators rather than indexes.  The code will be equivalent, but usable with more types than just vectors and arrays.

If we keep a collection of iterators (one for each of the arrays), then at each step, we want to advance the one that points to the smallest element (added complication - we need to tie-break by choosing the one that advances the least).  We have finished when that one reaches the end of its array; that means we also need to remember the end iterator for each array.  That means we end up storing a range for each input vector.

template<typename Iter>
struct range
{
    Iter current;
    Iter const end;
};

template<typename T>
range<typename std::vector<T>::const_iterator> make_range(const std::vector<T> &v)
{
    return {v.begin(), v.end()};
}

Now we can transform the vectors into ranges:

static int minimum_range(const std::vector<int> &A,
                         const std::vector<int> &B,
                         const std::vector<int> &C)
{
    auto range = { make_range(A), make_range(B), make_range(C) };

    auto minmax_range = std::minmax_element(range.begin(), range.end());

For the std::minmax_element() call to work, we'll need a suitable < operator in our range.  Add this:

bool operator<(const range& other) const
{
    if (current == end) return false;
    if (other.current == other.end) return true;
    auto a = *current, b = *other.current;
    if (a != b) return a < b;

    // it's a draw - which one advances least?
    if (current+1 == end) return false;
    if (other.current+1 == other.end) return true;
    a = current[1], b = other.current[1];
    return a < b;
}

Now let's go back to the algorithm and make it iterate:

auto minmax_range = std::minmax_element(r.begin(), r.end());
auto& min_range = minmax_range.first;
auto& max_range = minmax_range.second;
int best = **max_range - **min_range;

while ((++*min_range).current != min_range->end) {
    minmax_range = std::minmax_element(r.begin(), r.end());
    best = std::min(best, **max_range - **min_range);
    if (best == 0) {
        break;   // we can't improve on zero
    }
}

There's some stuff to explain there.  We create aliases for the minmax_range, which is a pair of iterators to range objects.  We use the dereference operator, which needs defining in range to give the current first element of the range:

auto operator*() const { return *current; }

The loop control starts by incrementing the lowest range - that needs an implementation:

range& operator++() { ++current; return *this; }

If that produced a range that has reached the end, then we've considered all the possibilities.

Inside the loop, we find the new min and max (remember that min_range and max_range still alias the members of minmax_range), and update best if required.

Extension to many inputs

We can now use a std::initializer_list to supply an arbitrary number of collections of any kind of (comparable) element.  I'll use C++17 for this (so we can write an implicit constructor for range, using a deduction guide).

#include <algorithm>
#include <vector>

template<typename Iter>
struct range
{
    Iter current;
    Iter const end;

    template<typename T>
    range(const T& v)
        : current{v.begin()},
          end{v.end()}
    {
    }

    explicit operator bool() const { return current != end; }

    auto operator*() const { return *current; }

    range& operator++() { ++current; return *this; }

    bool operator<(const range& other) const
    {
        return *this && (!other || *current < *other.current);
    }
};

// deduction guide
template<typename Container>
range(Container c) -> range<typename Container::const_iterator>;

template<typename Iter>
static auto minimum_range(std::initializer_list<range<Iter>> containers)
{
    using std::begin;
    using std::end;

    // Copy initializer list to read/write container
    std::vector r(begin(containers), end(containers));

    auto minmax_range = std::minmax_element(begin(r), end(r));
    auto& min_range = minmax_range.first;
    auto& max_range = minmax_range.second;
    auto best = **max_range - **min_range;

    while (++*min_range) {
        minmax_range = std::minmax_element(begin(r), end(r));
        best = std::min(best, **max_range - **min_range);
    }

    return best;
}

// convert containers to ranges and forward
template<typename... Args>
static auto minimum_range(const Args&... args)
{
    return minimum_range({range(args)...});
}

#include <list>
int main()
{
    return
        + (0 != minimum_range(std::list{5}))
        + (0.5 != minimum_range(std::vector{0.0}, std::vector{0.0}, std::vector{0.5}))
        + (6 != minimum_range(std::vector{6,30}, std::vector{10,12}, std::vector{6,15,30}, std::vector{12}))
        + (1 != minimum_range(std::vector{0, 6, 10}, std::vector{5}, std::vector{5}))
        // add more tests here
        + (1 != minimum_range(std::list{1, 4, 5, 8, 10}, std::list{6, 9, 15}, std::list{2, 3, 6, 6}));
}

I was unable to construct a test that proves the need for the tie-break in operator<, so I removed that code.  I shouldn't have written it in the first place without a test to exercise it, of course...