Telegram Bot that retrieves book information from GoodReads The project below is about a Telegram bot that implements both inline and offline modes. The idea is to get a brief info about a book, searched by title(it's author, rating, short description). I decided to retrieve the info from GoodReads. Besides the parse implementation, I have trouble in correctly accessing the Telegram API. Every recommendation and criticism is welcomed!

The GoodReads access to retrieve data

import goodreads
from goodreads import client
import random

class GoodreadsBook():

  def __init__(self):
    self.client_key = "[data]"
    self.client_secret = "[data]"

  def authenticate(self):
    self.auth_client = client.GoodreadsClient(self.client_key, self.client_secret)

  def parse_book(self, book):
    return {
        'title': book_data.title,
        'author': book_data.authors[0],
        'rating': book_data.rating,
        'review': book_data.review,
        'cover': book_data.image_url,
        'link': book_data.link
    }

  def book(self):
    """ Get info about a random book """
    max_book_num = 10 000 000
    index = random.randint(1, max_book_num)
    book = self.auth_client.book(index)

    return parse_book(book)

  def book_search(self, q, page=1, search_field='all'):
    """ Get the most popular books for the given query. This will search all
        books in the title/author/ISBN fields and show matches, sorted by
        popularity on Goodreads.
        :param q: query text
        :param page: which page to return (default 1)
        :param search_fields: field to search, one of 'title', 'author' or
        'genre' (default is 'all')
    """
    books = self.auth_client.search_books(str(q), page, search_field)

    return map(parse_book, books)

Main implementation of the bot

import telebot
from telebot import types
import gd

token = '[data]'
bot = telebot.TeleBot(token)

@bot.message_handler(commands=['start'])  # greeting
def send_welcome(message):
    bot.reply_to(message.chat.id, "Hi! How are you?")

@bot.message_handler(commands=['help'])  # command list
def send_welcome(message):
    bot.reply_to(message.chat.id, "This bot can do: ")

@bot.message_handler(commands=['random']) # /random
def random(message):
    book = random_book()
    text = "Some text"
    bot.send_message(message.chat.id, text, disable_web_page_preview=False)

@bot.inline_handler(lambda query: query.query == 'text')  # inline session
def query_text(query):
    raise Http404("Poll does not exist")
    book_req = book_info(query)
    try:
        result = []
        i = 0
        for book in book_req:
            result.append(types.InlineQueryResultArticle(id=i,
                title=book[i]['title'],
                url=book[i]['link'],
                hide_url=True,
                description=book[i]['review'],
                thumb_url=book[i]['cover'], thumb_width=48, thumb_height=48
                ))
            i += 1
        bot.answer_inline_query(query.id, result)
    except Exception as e:
        print("{!s}\n{!s}".format(type(e), str(e)))

def main_loop():
    bot.polling(True)
    while 1:
        time.sleep(3)

if __name__ == '__main__':
    try:
        main_loop()
    except KeyboardInterrupt:
        print >> sys.stderr, '\nExiting by user request.\n'
        sys.exit(0)

i = 0
for book in books:
    title = book[i].title
    info_dict['title'] = title

    author = book[i].authors[0]
    info_dict['author'] = author

    rating = book[i].average_rating
    info_dict['rating'] = rating

    review = book[i].description
    info_dict['review'] = review

    cover = book[i].image_url
    info_dict['cover'] = cover

    link = book[i].link
    info_dict['link'] = link
    i += 1
    book_list.append(info_dict)

I don't really get this part, either the books objects got some weird structure, or it seems like (and most likely is) that each object in this collection got also information about the whole collection.
So this might be just replaced with:

for book in books:
    book_list.append({
        'title': book.title,
        'author': book.authors[0],
        'rating': book.rating,
        'review': book.review,
        'cover': book.image_url,
        'link': book.link
    })

which you might want to replace with list comprehession if you want to:

book_list = [{'title': book.title,
              'author': book.authors[0],
              'rating': book.rating,
              'review': book.review,
              'cover': book.image_url,
              'link': book.link
              } for book in books]

But if I'm wrong and this books got really weird structure you can simplify your code as:

for i, book in enumerate(books):
    book_data = book[i]
    book_list.append({
        'title': book_data.title,
        'author': book_data.authors[0],
        'rating': book_data.rating,
        'review': book_data.review,
        'cover': book_data.image_url,
        'link': book_data.link
    })

now your random_book function can be prettified a bit as:

def random_book():
    index = random.randint(1, 1000000)
    book = gc.book(index)

    return {
        'title': book_data.title,
        'author': book_data.authors[0],
        'rating': book_data.rating,
        'review': book_data.review,
        'cover': book_data.image_url,
        'link': book_data.link
    }

Now as we can see, these both two functions are having deal with same structure, so you might want to create a parse function. And in the end your code will be like:

import random
from goodreads import client

client_key = "[redacted]"
client_secret = "[redacted]"

gc = client.GoodreadsClient(client_key, client_secret)

def parse_book(book):
    return {
        'title': book_data.title,
        'author': book_data.authors[0],
        'rating': book_data.rating,
        'review': book_data.review,
        'cover': book_data.image_url,
        'link': book_data.link
    }

def book_info(title):
    books = gc.search_books(str(title), page=1, search_field='all')

    return map(parse_book, books)

def random_book():
    index = random.randint(1, 1000000)
    book = gc.book(index)

    return parse_book(book)

Also in random_book I would replace index = random.randint(1, 1000000) with a call that returns a number of books in goodreads (if there is such) so you wont get an error here.


Login implementation security concerns In many of my personal projects, I have a login system very similar to the one I am about to describe. I understand how difficult correctly implementing authorization systems can be. I do this as a hobby and if I can do this securely myself, I would very much like to. (At work, I avoid homebrewed login solutions). I want to know if my approach is secure, and how I can improve it. I am using PHP 5.6 and the CodeIgniter 3 framework.

On register, I use password_hash with PASSWORD_BCRYPT.
Usernames must be unique, case insensitive (john and jOhN can't both
exist).
I only allow an IP to login x amount of time in x minutes (failed or
pass because alt accounts are usually discouraged). I have similar
restrictions on registering accounts.
I set a max password length of 64 and perform trim on start and end.
On login, I use password_verify to compare database result of
username row with user input.

For completeness, here is the most relevant (but not all) parts of auth code.

This is my controller

public function login()
{
    // Check if this is ip has logged in too many times
    $ip = $_SERVER['REMOTE_ADDR'];
    $timestamp = date('Y-m-d H:i:s', time() - $this->login_limit_window * 60);
    $route_url = 'user/login';
    $check_request_results = $this->main_model->check_request_route($ip, $route_url, $timestamp);
    if (count($check_request_results) > $this->login_limit && !is_dev()) {
        echo 'Too many login attempts from this IP. Please wait ' . $this->login_limit_window . ' minutes.';
        die();
    }

    // Validation
    $this->load->library('form_validation');
    $this->form_validation->set_rules('username', 'Username', 'trim|required|max_length[32]');
    $this->form_validation->set_rules('password', 'Password', 'trim|required|max_length[64]|callback_login_validation');

    // On fail set fail message and redirect to map
    if ($this->form_validation->run() == FALSE) {
        $this->session->set_flashdata('failed_form', 'login');
        $this->session->set_flashdata('validation_errors', validation_errors());
        redirect(base_url(), 'refresh');
        return false;
    }
    // Success
    redirect(base_url(), 'refresh');
}

// Validate Login Callback
public function login_validation($password)
{
    // Get other parameters
    $username = $this->input->post('username');
    // Compare to database
    $result = $this->user_model->login($username, $password);
    // Username not found
    if (!$result) {
        $this->form_validation->set_message('login_validation', 'Invalid username or password');
        return false;
    }
    // Password does not match
    else if (!password_verify($password, $result['password'])) {
        $this->form_validation->set_message('login_validation', 'Invalid username or password');
        return false;
    }
    // Success, do login
    $sess_array = array(
        'id' => $result['id'],
        'username' => $result['username']
    );
    $this->session->set_userdata('logged_in', $sess_array);
    return true;
}

And this is my model

// Login database call
function login($username, $password)
{
   $this->db->select('*');
   $this->db->from('user');
   $this->db->where('username', $username);
   $this->db->limit(1);
   $query = $this->db->get();
   if ($query->num_rows() == 1) {
       $result = $query->result_array();
       return isset($result[0]) ? $result[0] : false;
   }
   else {
       return false;
   }
}

Not a comprehensive review, but I'll list a few things which came to my notice right away:

Define the login_limit variable as login_limit_count to keep it consistent with login_limit_window.
Instead of defining the above 2 as class attributes, define them as constants in config/constants.php file.
Use === in the condition: ($this->form_validation->run() == FALSE)
The login method inside your user_model doesn't actually log-in the user. It just fetches the user details based off of $username. No need to provide it with $password and rename it to get_user or similar. Alternatively, put the password_verify inside the model, and return a user on successful login.
A select * is very bad. You should always know what values you'd be using from the result.
Hardcoding $route_url inside each controller method, and then calling check_request_route can be avoided using $_SERVER['REQUEST_URI'] variable and defining a hook. The hooks need to be enabled first in config/config.php. This way, you can track visits to multiple pages from a single location.


Horner's rule for polynomial evaluation Any better ways to implement 'inverseIndices'? Please give me feedback regarding good coding conventions.

fun main(arg: Array<String>) {
    //− 19 + 7 x − 4 x 2 + 6 x 3
    val coefficients = arrayListOf<Int>(-19, 7, -4, 6)
    val x = 3
    var result: Int = 0
    for (i in coefficients.inverseIndices) {
        result = (result*x) + coefficients[i]
    }
    println(result)
}

val ArrayList<Int>.inverseIndices: IntProgression
    get() = (size -1).downTo(0)

I suppose you can use .reversed() or  .asReversed() to reverse the list of coefficients and iterate over it, without working with the indices:

coefficients.asReversed().forEach {
    result = (result * x) + it
}

Also, you can use the functional idiom of fold/reduce, and replace iteration with folding the list (here, .foldRight(...) is used to fold the collection from its end):

val x = 3
val result = coefficients.foldRight(0) { it, acc -> it + acc * x }


Timer class implementation I have made a timer class:

The timer should call an async method and wait between two calls.
I want to wake up the timer to skip the wait period.
When I dispose the timer from outside the timer I want to wait until the current call is completed.
I want to stop the timer from inside the timer.

public sealed class CompletionTimer : IDisposable
{
    private readonly CancellationTokenSource disposeToken = new CancellationTokenSource();
    private readonly Task runTask;
    private int requiresAtLeastOne;
    private CancellationTokenSource wakeupToken;

    public CompletionTimer(int delayInMs, Func<CancellationToken, Task> callback, int initialDelay = 0)
    {
        runTask = RunInternal(delayInMs, initialDelay, callback);
    }

    public void Dispose()
    {
        disposeToken.Cancel();

        runTask.Wait();
    }

    public void Wakeup()
    {
        ThrowIfDisposed();

        Interlocked.CompareExchange(ref requiresAtLeastOne, 2, 0);

        wakeupToken?.Cancel();
    }

    private async Task RunInternal(int delay, int initialDelay, Func<CancellationToken, Task> callback)
    {
        if (initialDelay > 0)
        {
            await WaitAsync(initialDelay).ConfigureAwait(false);
        }

        while (requiresAtLeastOne == 2 || !disposeToken.IsCancellationRequested)
        {
            try
            {
                await callback(disposeToken.Token).ConfigureAwait(false);
            }
            catch (OperationCanceledException)
            {
            }
            finally
            {
                requiresAtLeastOne = 1;
            }

            await WaitAsync(delay).ConfigureAwait(false);
        }
    }

    private async Task WaitAsync(int intervall)
    {
        try
        {
            wakeupToken = new CancellationTokenSource();

            using (var cts = CancellationTokenSource.CreateLinkedTokenSource(disposeToken.Token, wakeupToken.Token))
            {
                await Task.Delay(intervall, cts.Token).ConfigureAwait(false);
            }
        }
        catch (OperationCanceledException)
        {
        }
    }
}

The requiresAtLeastOne field is to enforce at least one run when I do something like that (in a test or so):

var timer = new CompletionTimer(10000, ct => ... );
timer.Wakeup();
timer.Dispose();

It almost works perfectly, but one time (of thousand of calls) I had a deadlock in the Dispose method, when I was calling it from within a timer. I am more confused why it does not deadlock all the time.

I'm a bit hesitant to comment on anything related to concurrency, but I'll give it a try:

Why does Dispose wait for runTask to finish? To me, that's a rather surprising side-effect. I'd expect Dispose to stop the timer, and to abort the current invocation if possible, but not to block.
Letting a callback dispose the CompletionTimer that's running it sounds like a bad idea - it seems like an inverted ownership situation.
The deadlock seems fairly straightforward: RunInternal invokes callback asynchronously, so the rest of the code is registered as a continuation and will be run when callback finishes. However, callback disposes the CompletionTimer, which waits for runTask (RunInternal) to finish. The callback and the run task are now both waiting for each other to finish.
If you want the callback to be able to stop the timer, perhaps changing its return type to Task<bool> is a better idea: the timer can then terminate its loop after the callback returns false.
The requiresAtLeastOne construction looks a little confusing, with it being compared against a few 'magic values'. A requiredInvocationsLeft field that is decremented after each invocation seems a little easier to grasp - and would also allow you to configure the number of required invocations after a wake-up.
Perhaps SkipCurrentDelay is a more descriptive name than WakeUp. WakeUp could be interpreted as the timer being in sleep mode (as in, it's paused, it's not periodically invoking its callback).
You may want to document the intended behavior of your class. As my comments may show, other people likely have different assumptions about how a timer will behave.

Creating a separate StopAndWaitForCompletionAsync method is probably a better idea if you need to wait for the last invocation to finish.


AggregateException handling How do you handle AggregateException? It is really useful in many TPL or business scenarios, but handling is a real pain. I defined the following three extensions to help myself a little bit. They can be used this way:

try
{
  throw new AggregateException(
     new ArgumentException(),
     new DivideByZeroException());
}
catch (AggregateException aex)
{
  aex
     .Handle((ArgumentException ex) =>
     {
         Console.WriteLine(ex.Message);
     })
     .Handle((DivideByZeroException ex) =>
     {
         Console.WriteLine(ex.Message);
         throw ex;
     })
     .Throw<DivideByZeroException>()
     .Throw<ArgumentException>()
     .ThrowIfNonEmpty();
}

These methods are defined on AggregateException and return AggregateException so they can be chained.

Handle invokes parameter delegate once per each inner exception instance of a specified type and returns a new copy of AggregateException without those handled exceptions. An optional exception being thrown in the delegate will be added to the resulting AggregateException.

Throw method tries to find a first inner exception instance of specified type and throws it if found. You can chain them to decide on priority.

ThrowIfNonEmpty extends an AggregateException to throw it when InnerExceptions collection is not empty.

public static class AggregateExceptionExtensions
{
    public static AggregateException Handle<TEx>(
        this AggregateException source, Action<TEx> handler)
        where TEx : Exception
    {
        var exceptions = source.Flatten().InnerExceptions.OfType<TEx>();
        var handlerExceptions = new List<Exception>();
        foreach (var exception in exceptions)
            try
            {
                handler(exception);
            }
            catch (Exception ex)
            {
                handlerExceptions.Add(ex);
            }

        return new AggregateException(source.InnerExceptions
            .Except(exceptions)
            .Concat(handlerExceptions));
    }

    public static AggregateException Throw<TEx>(this AggregateException source)
    {
        var ex = source.InnerExceptions.FirstOrDefault(e => e is TEx);
        if (ex != null)
            throw ex;

        return source;
    }

    public static void ThrowIfNonEmpty(this AggregateException source)
    {
        if (source.InnerExceptions.Any())
            throw source;
    }
}

Can you suggest any other tricks which might be useful?

I don't think it's a good idea to rethrow only the first/single exception of a particular type. Often, when done right ;-) each exception may contain different data about what went wrong, like entity validation errors may happen for multiple entities or mutliple files may not have been found etc. If you pick only the first one you won't know about the rest and you'll app crashes agian next time.

The Handle and the ThrowIfNonEmpty are fine but Throw is very harmful.

Additionaly I would change the Handle to be Func<TEx, bool>:

public static AggregateException Handle<TEx>(
    this AggregateException source, Func<TEx, bool> handler)
    where TEx : Exception
{
    var exceptions = source.Flatten().InnerExceptions.OfType<TEx>();
    var handlerExceptions = new List<Exception>();
    foreach (var exception in exceptions)
    {
        try
        {
            if (!handler(exception))
            {
                handlerExceptions.Add(exception);
            }
        }
        catch (Exception ex)
        {
            handlerExceptions.Add(ex);
        }
    }
    return new AggregateException(source.InnerExceptions
        .Except(exceptions)
        .Concat(handlerExceptions));
}

so that I can for example log it and still be able to say I didn't handle it by returning false.

.Handle((ArgumentException ex) =>
{
   Console.WriteLine(ex.Message);
   return false;
})


Restricting user to one open tab in browser I had a requirement to restrict my web site's users to just one open tab in the browser. I am aware that this is not the best thing to do in terms of general user experience guidelines, but it's an internal application that doesn't play well with such a scenario so I had to do it.

The following is what I came up with:

function IsNewTab() {
  return $.cookie('TabOpen');
}

$(function() {
  if (!IsNewTab()) {
    $.cookie('TabOpen', "YES", {
      path: '/'
    });
    $(window).unload(function() {
      $.removeCookie('TabOpen', {
        path: '/'
      });
    });
  } else {
    alert('already some tab open')
      //OR
      //window.close()
  }
});

I'd like opinions on the above. Are there any loopholes (keeping in mind that the target audience isn't too technical and probably won't go hacking around with the browser console). Are there any possible improvements that can be made?

I can't think of a better approach than a session cookie. It feels safe in that you have three potential ways of leaving the page:

Navigate away
Close browser/tab
Browser crashes

So you're either going to have the option to remove the cookie on the unload event or the session cookie will expire anyway.

I would structure the code a little differently:

// Wrap in an IIFE accepting jQuery as a parameter.
(function ($) {
    var setCookie,
        removeCookie,
        // Create constants for things instead of having same string
        // in multiple places in code.
        COOKIE_NAME = 'TabOpen',
        SITE_WIDE_PATH = { path : '/' };

    setCookie = function () {
        $.cookie(COOKIE_NAME, '1', SITE_WIDE_PATH);
    };

    removeCookie = function () {
        $.removeCookie(COOKIE_NAME, SITE_WIDE_PATH);
    };

    // We don't need to wait for DOM ready to check the cookie
    if ($.cookie(COOKIE_NAME) === undefined) {
        setCookie();
        $(window).unload(removeCookie);
    } else {
        // Replace the whole body with an error message when the DOM is ready.
        $(function () {
            $('body').html('
' +
                '
Sorry!
' +
                '
You can only have one instance of this web page open at a time.
' +
                '
');
            });
    }
}(jQuery));

(code untested).


Python auth using requests I am trying to implement a custom ApiClient in Python, using requests.
The way it does authentication is by:

login(username, password) -> get back a token if valid, http error code if not
set the token in {'Authorization': token} header and use that header for all endpoints which need authentication

Can you check if the code looks OK, and if not what kind of changes would you recommend?

#!/usr/bin/env python

import requests
import json
import os
import sys

def read_file_contents(path):
    if os.path.exists(path):
        with open(path) as infile:
            return infile.read().strip()

class ApiClient():
    token = None
    api_url = 'http://10.0.1.194:1234'
    session = requests.Session()

    def __init__(self):
        self.token = self.load_token()

        if self.token:
            self.session.headers.update({'Authorization': self.token})
        else:
            # if no token, do login
            if not self.token:
                try:
                    self.login()
                except requests.HTTPError:
                    sys.exit('Username-password invalid')

    def load_token(self):
        return read_file_contents('token')

    def save_token(self, str):
        with open('token', 'w') as outfile:
            outfile.write(str)

    def login(self):
        email = '1@1.hu'
        password = 'passwd'

        headers = {'content-type': 'application/json'}
        payload = {
            'email': email,
            'password': password
        }
        r = requests.post(self.api_url + '/auth',
                          data=json.dumps(payload),
                          headers=headers)

        # raise exception if cannot login
        r.raise_for_status()

        # save token and update session
        self.token = r.json()['session']['token']
        self.save_token(self.token)
        self.session.headers.update({'Authorization': self.token})

    def test_auth(self):
        r = self.session.get(self.api_url + '/auth/is-authenticated')
        return r.ok

if __name__ == '__main__':
    api = ApiClient()
    print api.test_auth()

I don't have time to do a thorough review, but here are some comments based on a casual reading.

In read_file_contents, the function returns None if the file doesn’t exist. I’d suggest modifying this to print or return an explicit message to that effect, to make debugging easier later. For example, something like:

def read_file_contents(path):
    try:
        with open(path) as infile:
            return infile.read().strip()
    except FileNotFoundError:
        print "Couldn't find the token file!"
        return None

will make your life easier later.

Also, is this meant to be open(path, 'r')?
New-style classes should inherit from object: that is, use

class ApiClient(object):

instead of

class ApiClient():

Don't copy and paste the API URL throughout your code. Make it a variable, and then pass api_url as an input to ApiClient(). That way, you can reuse this code for other APIs, or make changes to the URL in a single place. (If, for example, the API changes.)
Don't hard code username, email and password in the login function. It makes it harder to change them later, and it's a security risk. Consider using something like the keyring module for storing sensitive information. (Should the token be stored securely as well?)
The __init__ function uses the token, and also retrieves it from the file. This can cause problems if you later get the token from somewhere else. (For example, if you used keyring.) Instead, consider passing token as an argument to __init__, and having the code to obtain the token somewhere else. Something like:

def __init__(self, api_url, token=None):
    self.api_url = api_url
    self.token = token

    if self.token is not None:
        # if you get a token
    else:
        # if you don't

and then later:

if __name__ == '__main__':
    api_token = read_file_contents('token')
    api_url = 'http://10.0.1.194:1234'
    api = ApiClient(api_token, api_url)
    print api.test_auth()


Finding permutation from given lexicographical rank I wrote the following little piece of Python code to take in some integer, and return a permutation that has that rank in the lexicographical ordering of permutations. While this works, I'm worried that the number of calls to pop() and append() might be slowing this down. This function is part of a larger program, which will call FromRank() millions of times, and any small efficiency may make a large impact down the road.

Note: The same topic for Java is here!

Input:

There are four arguments: rank, level, ordered, and perm. rank is the rank given. level is the number of uncertain digits of the permutation minus one. Hence, if the size of a permutation is 8 digits, then level is initially 7. ordered is initially list(range(size)) and is always sorted. perm keeps track of the permutation, and is initially an empty list.

Code:

def FromRank(rank,level,ordered,perm):
    fact = math.factorial(level)
    section = rank // fact
    if len(ordered) == 1:
        perm.extend(ordered)
        return perm
    elif rank % fact == 0:
        ordered.sort()
        nxt = ordered.pop(section - 1)
        perm.append(nxt)
        ordered.sort(reverse = True)
        perm.extend(ordered)
        return perm
    elif rank < fact:
        ordered.sort()
        first = ordered.pop(0)
        perm.append(first)
        return FromRank(rank,level - 1,ordered,perm)
    else:
        ordered.sort()
        nxt = ordered.pop(section)
        perm.append(nxt)
        rank = rank - (rank // fact) * fact
        return FromRank(rank,level - 1,ordered,perm)

Time Complexity Example:

While the goal of this function is to work on a single rank, I ran the following code to see how runtime would ramp up with an increasing number of permutations to handle. And, although this function would never be running on permutations larger than 20, I included a section giving the runtimes for a single permutation of increasing size.

I ran this to see how the function would respond to volume

for j in range(2,11):
    start_time = timeit.default_timer()

    for i in range(1,math.factorial(j)+1):
        x = FromRank(i,j-1,list(range(j)),[])))

    elapsed_time = timeit.default_timer() - start_time
    print("Permutations of size {} took {} seconds."\
              .format(j,elapsed_time))

and got the following times:

Permutations of size 2 took 0.000249750356557 seconds.
Permutations of size 3 took 0.00016293644837 seconds.
Permutations of size 4 took 0.000660726542604 seconds.
Permutations of size 5 took 0.00366414564209 seconds.
Permutations of size 6 took 0.0185743274595 seconds.
Permutations of size 7 took 0.160154982071 seconds.
Permutations of size 8 took 1.48163329891 seconds.
Permutations of size 9 took 15.2436537109 seconds.
Permutations of size 10 took 177.243403105 seconds.

I then ran the following to see how the function would respond to large permutations:

for size in [10,50,100,500,1000]:
    start_time = timeit.default_timer()
    x = FromRank(size ** 2, size - 1, list(range(size)), [])
    elapsed_time = timeit.default_timer() - start_time
    print(elapsed_time)

and got the following times:

0.000118032702744
0.00074668514128
0.00260142366255
0.110989229516
0.684973282271

Style

Python has a style guide called PEP 8 which is definitly worth reading and and worth following if you do not have good reasons not to. In you case, your function name for instance is not compliant to PEP8. You'll find tools online to check your code compliancy to PEP8 in a automated way if you want to.

API / Function signature

Your function signature is a bit unclear. This situation often happens when recursive solutions are applied. A good way to solve this would be to define another function calling the complicated function with the right arguments or to use default arguments.

If I understood everything properly, the point if to get the n-th performutation from a list. A simple way to do so would be to have a function taking the rank and the lst as an argument.

Testing

In order to keep things simple, it is a good option to write a simple (even if inefficient) solution to be able to see patterns and/or write tests to ensure that your more efficient works and is indeed more efficient.

A very simple solution could be written like this :

def from_rank(rank, lst):
    sorted_perm = sorted(itertools.permutations(lst))
    return sorted_perm[rank]

And you can write some simple tests like this :

tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2])
for lst in tests_cases:
    for i in range(math.factorial(len(lst))):
        a = list(from_rank(i, lst))
        b = list(from_rank2(i, lst))
        if a != b:
            print(i, a, b)

Another more simple solution

Your solution involves both recursion and mutations of data. This can make things very hard to understand. A more simple idea could be to say that from the rank, it is easy to know which element will be the first of the permatation. Indeed, if your list has n elements, you know that there are (n-1)! permations of length n-1 and so the rank-th permutation will have for its first element the rank / ((n-1)!)-th elements. You can repeat the same thinking for a smaller list consistent of the remaining elements with the remaining part of the rank.

This can be written:

def from_rank2(rank, lst):
    my_lst = sorted(lst)
    ret = []
    while my_lst:
        fact = math.factorial(len(my_lst) - 1)
        idx, rank = divmod(rank, fact)
        ret.append(my_lst.pop(idx))
    assert rank == 0  # invalid rank - out of range
    return ret

Please note that this solution does not seem to handle very well lists with repeated elements. You can easily enhance your test suite to show it :

tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2], [2, 2, 3], [1, 2, 5, 4, 3, 2])


Horrible case statement for displaying a title This thing kills me:

     def report_subtitle
        case params[:kind]
          when 'position'   then  h("for Position: #{@current_company.positions.find_by_id(params[:id])}")
          when 'grade'      then  h("for Grade: #{params[:id]}")
          when 'location'   then  h("for Location: #{Location.find_by_id(params[:id])}")
          when 'department' then  h("for Deparment: #{@current_company.departments.find_by_id(params[:id])}")
          when 'supervisor' then  h("Employees who report to #{@employees.first.supervisor.full_name}")
          when 'eeoc'       then  h("for EEOC Code: #{params[:id]}")
    end

There are a few issues with this method:

The parameter kind is not descriptive enough. Is this a kind of report? Is it report_type?
You seem to be looking up a Location, Position and Department using the same id. I'm not sure this is possible, but if it is, you should rather use the relations rather than id-lookups.
This method is trying to generate a report's subtitle, presumably in the controller. The conditional of the case statements should be replaced by polymorphism. Something like separate classes which all respond to the same method.

I don't quite understand the context of your code, but aim for something like

class PositionReport
  # ...
  def subtitle
  end
end

class GradeReport
  # ...
  def subtitle
  end
end

Then you are reasoning about different report types, each of which handles it's own subtitles (and other logic).

Just my two cents.


CodeEval Sequence Transformation I've been working on this challenge for a week:

  There are two sequences. The first sequence consists of digits "0" and "1", the second one consists of letters "A" and "B". The challenge is to determine whether it's possible to transform a given binary sequence into a string sequence using the  following rules:

  "0" can be transformed into non empty sequence of letters "A" ("A", "AA", "AAA" etc.)
  "1" can be transformed into non empty sequence of letters "A" ("A", "AA", "AAA" etc.) or to non empty sequence of letters "B" ("B", "BB",
  "BBB" etc) e.g.

  Examples:

1010 AAAAABBBBAAAA                -> Yes
00 AAAAAA                         -> Yes
01001110 AAAABAAABBBBBBAAAAAAA    -> Yes
1100110 BBAABABBA                 -> No

Here is the first small sample to feed the program and here is the second large sample.

I have 3 working solutions, but they're painfully slow.

My first idea was to build a regex for each test case, test if it matched and map Yes or No

puts IO.readlines(ARGV[0]).map { |l| l.chomp.split(' ') }.map { |a|
  index = 0
  a[1].match(a[0].chars.to_a.inject('^') { |result, digit|
    result + (digit == '1' ? '([A|B])\\' : '(A)\\') + "#{index += 1}{0,}"
  } + '$') ? 'Yes' : 'No'
}

It works fine with the small sample, but takes forever with the large one.

So I thought about backtracking and tried it

def check_char_number(char, number)
  (number == '0' && char == 'A') || number == '1'
end

def check(string, numbers, current_char)
  return true if string.empty? && numbers.empty?
  return false if string.empty?
  return false if current_char != string[0] && !check_char_number(string[0], numbers[0])

  if string[0] == current_char
    r = check(string[1..-1], numbers, current_char)
    return r if r
  end

  return check(string[1..-1], numbers[1..-1], string[0]) if check_char_number(string[0], numbers[0])
  return false
end

puts IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|
  r = 0
  l1 = a[0].length
  l2 = a[1].length
  if l1 > l2 or l1 < 1 or l2 < 1
    r = 'No'
  else
    r = check(a[1], a[0], nil) ? 'Yes' : 'No'
    puts "finished: #{r}"
  end
  r
}

But it's still so slow

So I was getting desperate and started looking around on GitHub to see how other people did it, and found something interesting in python

I don't have any academic degree in CS I learned everything with books and MIT courses and I can't tell if what he's using is a known technique to solve this sort of problems. I feel like I barely understand it (spent a lot of time with the debugger to see what happens step by step) and I'd really love to know if a Wikipedia page could explain this better or if this is completely home-made.

I ported it ruby and my second question is: even though it is significantly faster than the previous two why is it sill five to seven times slower than his solution:

def check_number_with_partial_string(number, partial_string)
  #45% of runtime spent here!
  return !partial_string.include?('B') if number == '0'
  return !(partial_string.include?('A') && partial_string.include?('B')) if number == '1'
end

def check_matching(numbers, string, matching_matrix, row = 0, column = 0)
  return if matching_matrix[-1][-1] == true
  return if row >= matching_matrix.size or column >= matching_matrix[row].size
  return if matching_matrix[row][column]
  (column...string.length).each do |c|
    matching_matrix[row][c] = false
    if check_number_with_partial_string(numbers[row], string[column...(c + 1)])
      matching_matrix[row][c] = true
      check_matching(numbers, string, matching_matrix, row + 1, c + 1)
    end
  end
end

puts IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|
  matrix = Array.new(a[0].length).map { |b| Array.new(a[1].length) }
  check_matching(a[0], a[1], matrix)
  matrix[-1][-1] ? 'Yes' : 'No'
}

I profiled it and it seems 45% of the time is spent in the first little method

Time profiler

I focussed exclusively on your last bit of code. I'm afraid I only managed a ~1.8x speed increase. I think a lot of comes down to Ruby's itself not being the quickest thing going - at least not when it comes to this particular algorithm.

Long story short: Convert your number and letter strings to integer arrays. For whatever reason, that's where I found a performance increase. I'll leave the explanation to someone with deeper knowledge of Ruby's string handling.

There may be a totally different way to do this, which'll be super-fast in Ruby, but I haven't investigated that. Generally, though, Ruby aims for expressiveness and readability, and this algorithm doesn't play to Ruby's strengths.

Anyway, review time! I've only changed minor stuff to make it more Ruby-like; the algorithm itself is as it ever was (for good or bad)

You'll still find that the majority of the time is spent in that first method. For one, it's being called constantly, and for another, it's doing the most work. Anything else in the code is just loops and boolean logic. But check_number_with_partial_string is the one actually doing the real checking of numbers to letters. So it's no wonder it weighs heavy on the performance.

check_number_with_partial_string

The logic's iffy. By which I mean that there is literally one if too many. The number will be either 1 or 0, so why the extra check? Also, no need to (potentially) call include?('B') twice. Store it once, use it twice.
There might also be a micro-optimization here if we flip the second return value around. If we've stored includes?('B') already and it's false, we can check that first, and, since the expression uses &&, the check for includes?('A') doesn't need to run.
Should maybe just be called partial_match?

check_matching

For the sake of line-length, I'd probably just call the matrix matrix. It's not about to be confused with anything
Favor || over or for boolean logic (here's a good explanation)
matching_matrix[row][c] = false is unnecessary since the initial value of that index is nil which is already false'y. But since check_number_with_partial_string returns a bool, we can skip a bit and just assign its return value to the index.
The overall name is a bit misleading. I'd imagine it would return something, since it's called "check" - but it doesn't.

Read loop

Right now, the entire map must run before anything is printed. You can use IO#each_line instead of loading everything into memory at once. And print for each test case. I've changed it, but the original may be faster(!)
Use do..end for multiline blocks (though if you keep the puts outside, the lower precedence of do..end compared to {...} will trip you up)
Use Array.new with a block instead of creating and then mapping an array to fill it
Pull named variables from the split string to keep things readable (no opaque array indices)

In the end, I had:

def check_number_with_partial_string(number, string)
  includes_b = string.include?(66) # ASCII 'B'
  return !includes_b if number == 0
  !(includes_b && string.include?(65)) # ASCII 'A'
end

def check_matching(numbers, string, matrix, row = 0, column = 0)
  return if matrix[-1][-1]
  return if row >= matrix.size || column >= matrix[row].size
  return if matrix[row][column]

  (column...string.length).each do |c|
    matrix[row][c] = check_number_with_partial_string(numbers[row], string[column...(c + 1)])
    check_matching(numbers, string, matrix, row + 1, c + 1) if matrix[row][c]
  end
end

File.open(ARGV[0]).each_line do |line|
  digits, string = line.chomp.split
  digits = digits.chars.map(&:to_i)
  string = string.chars.map(&:ord)
  matrix = Array.new(digits.length) { Array.new(string.length) }
  check_matching(digits, string, matrix)
  puts matrix[-1][-1] ? 'Yes' : 'No'
end

Again, as far as I can tell, any increased performance came from mapping the two strings to integers.

For some sample input I generated (where everything always matches), I got ~43 sec for the code above, versus ~83 sec for the original. That's obviously not the most rigorous test, but it seemed consistent with different input sizes.

Maybe there are more gains to be had somewhere, but I didn't find 'em (but I didn't try to do more overall restructuring either). Maybe someone else will spot something. But again (again) this just seems to me to be an algorithm that doesn't play to Ruby's strengths.


Better QOpenGLWidget by delaying GL code to initializeGL with lambda functions When I am writing OpenGL applications with the QOpenGLWidget class, deciding what code goes into the initializeGL function has always been tricky. One example is when I have a setter that requires an initialized OpenGL context, I have to make sure the OpenGL context is initialized before calling the setter, which is a huge pain.

The following snippet allows me to put GL functions anywhere in the class without worrying whether the OpenGL context is initialized. This is done by wrapping the GL functions with the delayForInit function. It checks whether the OpenGL context is already initialized. If it is, then run the GL functions immediately. If not, then delay the GL functions until initializeGL is called.

A simple usage example is shown at the bottom.

#ifndef OPENGLWIDGET_H
#define OPENGLWIDGET_H

#include <QOpenGLWidget>
#include <functional>

/**
 * @brief The OpenGLWidget class
 */
class OpenGLWidget : public QOpenGLWidget {
    Q_OBJECT
public:
    explicit OpenGLWidget(QWidget* parent = 0)
      : QOpenGLWidget(parent)
      , _isInitialized(false) {}

protected:
    virtual void initializeGL() override {
        for (auto& initFunc : _initFuncs)
            initFunc();
        _initFuncs.clear();
        _isInitialized = true;
    }
    void delayForInit(std::function<void()> func) {
        if (_isInitialized) {
            makeCurrent();
            func();
            doneCurrent();
        } else
            _initFuncs.push_back(func);
    }

private:
    bool _isInitialized;
    std::vector<std::function<void()>> _initFuncs;
};

#endif // OPENGLWIDGET_H

// usage example
class SomeWidget : public OpenGLWidget {
    Q_OBJECT
public:
    SomeWidget() {
        delayForInit([this]() {
            glClearColor(0.f, 0.f, 0.f, 0.f);
            glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
        });
    }
};

Small nitpicks:

The default value of the parameter QWidget* parent of the constructor is 0. This should be replaced with nullptr.

Either OpenGLWidget or SomeWidget would need to inherit from QOpenGLFunctions to get access to the OpenGL functions used in the example.

The implementation as-is is absolutely not thread-safe. This might not be a concern if your application is guaranteed to be single threaded, but more often than not, applications using advanced graphics end up using multiple threads.

Since the context() member function is publicly accessible, it might be appropriate to make delayForInit adhere to the same level of accessibility.

While delayForInit isn't the worst name, it doesn't really convey what it's doing. deferGLCall or withGLContext might be more fitting.

Design
It's simplicity of usage is great. However, you have no way of enforcing that it will be used at all possible call sites (where appropriate).Another possibility that comes to mind would be to use the State pattern to provide access to the OpenGL functions in form of a member, with 2 states: One that records the OpenGL calls and one that simply forwards them. The call to initializeGL then switches state from recording to forwarding, executing the recorded calls.Though also not foolproof, but which is harder to forget: "I have to use OpenGL calls in a lambda passed to this function." or "I have to use this member to get access to the OpenGL functions (as they aren't provided directly by default anyways)."?
Example (rough outline, as I currently have no Qt install at hand):
class GLState {
protected:
    QOpenGLWidget& widget;
public:
    explicit GLState(QOpenGLWidget& w) : widget(w) {}
    virtual ~GLState() {}

    // define gl functions as needed
    void glClearColor(GLclampf red, GLclampf green, GLclampf blue, GLclampf alpha) = 0;
    void glClear(GLbitfield mask) = 0;
    // ...
};

class ForwardingGLState : public GLState, public QOpenGLFunctions {
    Q_OBJECT // not sure if needed, but probably is
public:
    ForwardingGLState(QOpenGLWidget& w) : GLState(w), QOpenGLFunctions(w.context()) {}

    // gl calls implemented by QOpenGLFunctions, nothing to do here
};

class RecordingGLState : public GLState {
    std::vector<std::function<void()>> records;
public:
    RecordingGLState(QOpenGLWidget& w) : GLState(w), records() {}

    // either do execution of recorded calls during destructor (might
    // be tricky with exceptions) or implement another virtual function
    // in GLState
    virtual ~RecordingGLState() {
        if(widget.context() == nullptr) return;

        widget.makeCurrent();
        for(auto& record : records) {
            record();
        }
        widget.doneCurrent();
    }

    // record gl calls
    // might be able to simplify lambda implementation
    void glClearColor(GLclampf red, GLclampf green, GLclampf blue, GLclampf alpha) {
        records.push_back([&]() {
            widget.context()->functions()->glClearColor(red, green, blue, alpha);
        });
    }

    void glClear(GLbitfield mask) {
        records.push_back([&]() {
            widget.context()->functions()->glClear(mask);
        });
    }
};

Usage in OpenGLWidget:
class OpenGLWidget : public QOpenGLWidget {
    Q_OBJECT
protected:
    std::unique_ptr<GLState> gl;

public:
    OpenGLWidget(QWidget *parent = nullptr) : QOpenGLWidget(parent), gl(std::make_unique<RecordingGLState>(*this)) {}

protected:
    virtual void initializeGL() override {
        // if not (ab-)using the destructor, execute recorded calls here
        gl = std::make_unique<ForwardingGLState>(*this);
    }
};

class SomeWidget : public OpenGLWidget {
    Q_OBJECT
public:
    SomeWidget(QWidget *parent = nullptr) : OpenGLWidget(parent) {
        gl->glClearColor(0.f, 0.f, 0.f, 0.f);
        gl->glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    }
};

Yes, it's a lot of boiler plate code inside the GLStates, but after that its mostly done (though some of it could probably be replaced with macros if it gets too bad). Plus side: you can't really get the final usage wrong!


Bootstrap file - safe and correct Can someone take a look over my bootstrap file and see if you believe it's doing too much or the logic could be better.

<?php

    /*
    * ------------------------------------
    * Autoloader for classes/files
    * ------------------------------------
    */

    function __autoload($class) {
        if(file_exists($file = str_replace("\\","/",str_replace("baremvc\\","",$class)).".php")){
            require_once $file;
        }else{
            throw new Exception($file);
        }
    }

    /*
    * ------------------------------------
    * Get commonly used namespaces
    * ------------------------------------
    */

    use \baremvc\core\library\exception as ex;
    use \baremvc\core\configuration as config;

    /*
    * ------------------------------------
    * Enable session if set in the configuration file
    * ------------------------------------
    */

    !config::enable_sessions ?: session_start();

    /*
    * ------------------------------------
    * Enable debug information if set in the configuration file
    * ------------------------------------
    */

    error_reporting(config::debug_level);
    ini_set('display_errors', intval(config::debug_enabled));

    /*
    * ------------------------------------
    * Try and load the specified class/method
    * ------------------------------------
    */

    $router = new \baremvc\core\library\router;
    $url_object = $router->parse_request_url(@$_SERVER['REDIRECT_URL']);
    try{
        $namespace = "\\baremvc\\controllers\\{$url_object->Controller}";
        $class = new $namespace;
        if(method_exists($class,$url_object->Method)){
            if(!empty($url_object->Get)){
                call_user_func_array(array($class, $url_object->Method), $url_object->Get);
            }else{
                call_user_func(array($class, $url_object->Method));
            }
        }else{
            throw new Exception($url_object->Method);
        }
    }catch(Exception $e){
        echo ex::show_404($e->getMessage());
    }

parse_request_url takes the requested url (e.g. domain.com/this/is/my/request) and checks to see if a controller exists with that name (can be in directories or file).

Generally this is very good code, but I try to be thorough when reviewing so I've listed every minor point that I could think of.

It looks like you write OO code in other places, but you chose to make your bootstrap procedural.  Believe it or not there are benefits to an OO bootsrap!  You can define methods for different parts of the system that you want to bring up.  There will always be some procedural code required to call the bootstrap, but it could look more like this:

$bootstrap = new Bootstrap();
$bootstrap->initializeAutoload();
$bootstrap->initializeErrorReporting();
$bootstrap->initializeRouter();

As GordonM said, use spl_autoload_register.

You are tightly bound to the config class by your static calls to it.  This makes it hard to test your bootstrap.  It is understandable in the bootstrap as you have only just brought the autoload up.  Keep reading and at the end I'll tell you what I recommend on that.

Personally I don't like the error control operator @.  I find it hard to understand what will happen when your server redirect url is not defined.  This is very minor, but I would use:

if (isset($_SERVER['REDIRECT_URL']))
{
    $url_object = $router->parse_request_url($_SERVER['REDIRECT_URL']);
}
else
{
    $url_object = $router->parse_request_url('');

}

$namespace and $class are misleading to me, I would rewrite those:

$class_name = '\baremvc\controllers\\' . $url_object->Controller;
$controller = new $class_name;

ex::show_404 couples your code tightly to the ex class.  This makes it harder for you to test this code as now you require a stub for ex as well as config.  You also call new to create a variable controller class, that would make it hard to test.

Other good things that you can do in the bootstrap are:  set_error_handler, set_exception_handler, register_shutdown_function.

Now about some of the coupling in this code (to config, ex and the variable controller class).  This is an issue if you want to test this code or have it so that it is reusable (You are going to need config and ex if you want to reuse it as it is).  You may be happy enough to leave it as it is.  That would be a valid choice and one many people would take.  Many people should stop reading now (I won't be offended if you also ignore the following).

Now, if you want to get around it a little.  All static calls and calls to new bind the calling code to the class that they are calling.  Look at the following and answer for yourself how tightly they bind the code to the class:

config::enable_sessions
$object->enable_sessions
$configObject = new Config();
$configObject = $container->getNew('Config');

I believe the tightness of coupling is - High (need config class with enable_sessions), Low (need any object with enable_sessions), High (need config class), Low (need an object with getNew).

My recommendation would be that if you are going to bind your Bootstrap to anything it should be a container class, because from that you can get any other object that you need.  This means you will only have to stub one class (the container) when you test, which should be simple.


XML tags constants vs hardcoded values I have to create an XML body for a web service call. I want to use:

private void createProductBody(Product product, StringBuilder body) {
    body.append(WSConstants.WS_PRODUCT_ID_START_TAG)
            .append(product.getId())
            .append(WSConstants.WS_PRODUCT_ID_END_TAG)
            .append(WSConstants.WS_SIZE_TEXT_START_TAG)
            .append(product.getSize())
            .append(WSConstants.WS_SIZE_TEXT_END_TAG);
}

But some colleagues state that this writing is hard to read and they want us to use this:

private void createProductBody(Product product, StringBuilder body) {
    body.append("<ProductId>").append(product.getId()).append("</ProductId>")
        .append("<Size>").append(product.getSize()).append("</Size>");
}

Which are the pro and cons for using hardcoded values?

They're right. While "</Whatever>" is hard to read itself (YMMV), the constants make it even worse.

Magical constants in a code are bad and should usually be extracted as you did. But if there are many of them and each gets used just once, it's counterproductive.

The best solution would be something like

new XmlBuilder(body)
    .start("ProductId").append(product.getId()).end()
    .start("Size").append(product.getSize()).end();

or some of the million existing XML tools. If the constants get used multiple times, then something like

new XmlBuilder(body)
    .start(WSConstants.WS_PRODUCT_ID).append(product.getId()).end()
    .start(WSConstants.WS_SIZE).append(product.getSize()).end();

makes more sense. Then you may consider using static imports to keep it shorter.

The whole XmlBuilder is rather trivial, it mostly delegates to the StringBuilder and remembers the opened tags using a stack. As stated by  aetheria, it should also escape the appended values when needed.

For redundancy lovers, something like

new XmlBuilder(body)
    .start(WS_PRODUCT_ID).append(product.getId()).end(WS_PRODUCT_ID)
    .start(WS_SIZE).append(product.getSize()).end(WS_SIZE);

may be more "cool". Anyway, it's more XML-like (just don't ask me what's good for).

Note the inconsistency of "PRODUCT_ID" vs. "SIZE_TEXT", where the former means indeed "productId" while the latter means just "size". This should be fixed (like I did in my snippets).


Generating Fibonacci sequences in Scala Would you consider this to be idiomatic Scala? If not, what would you do to improve it?

def fibonaccis(max: Int): List[Int] = { fibonaccis(max, 2, 1) }
private def fibonaccis(max: Int, prev: Int, prevPrev: Int): List[Int] = prev >= max match {
  case true => List[Int](prevPrev)
  case false => prevPrev :: fibonaccis(max, prev + prevPrev, prev)
}

Naming the parameters prev and prevPrev is weird.  Why not current and prev?

You shouldn't need the curly braces here for a function that consists of a single expression:

def fibonaccis(max: Int): List[Int] = fibonaccis(max, 2, 1)

Conventionally, the Fibonacci sequence is said to start like

$$1, 1, 2, 3, 5, 8, \ldots$$

or

$$0, 1, 1, 2, 3, 5, \ldots$$

Your fibonaccis(13) would produce List(1, 2, 3, 5, 8), which I would consider to be missing the first element.

The Fibonacci sequence is an infinite sequence.  It would be a shame to limit it to a max value.  The most idiomatic way to model it in Scala would be using an infinite lazy stream, just as suggested in the documentation:

def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)
val fibonaccis = fibFrom(0, 1)

Alternative implementation:

val fibonaccis: Stream[Int] = 0 #:: 1 #:: fibonaccis.zip(fibonaccis.tail).map(
    n => n._1 + n._2
)

Then, you could do fibonaccis.takeWhile(_ < 13).toList to obtain List(0, 1, 1, 2, 3, 5, 8).


Validate URL with Regex and java.net.URL I'm writing a URL validator. Firstly, it checks for special characters in the input. Secondly, it adds 'http://' and checks for validity.

    /* Returns true if url is valid */
    private static boolean isValidURL(String url) {
        boolean containsSpecialCharacters = specialCharactersExists(url);
        if ( !containsSpecialCharacters ) {
            /* Try creating a valid URL */
            try {
                new URL(String.format("%s%s", "http://", url)).toURI();
                return true;
            } catch (Exception e) {
                /* Not a valid URL */
            }
        }
        return false;
    }

    /* Returns true if url contains special characters */
    private static boolean specialCharactersExists(String input) {
        Pattern regex = Pattern.compile("[^A-Za-z0-9.-]");
        Matcher matcher = regex.matcher(input);
        return matcher.find();
    }

This serves my purpose. I'm seeking advice on how to improve the code (especially the Regex part)

Welcome to Code Review!

Bad naming

The method doesn't actually check that a URL is valid, as it allows values that are not URLs. Thus it should not be named as "isValidURL". It should be isValidAddress or similar, but not URL. URLs have a very well defined syntax.

Unnecessary variables

There is no need to store the return value of specialCharactersExists(url) to a variable. It only adds an unnecessary large if-statement. Instead, check the value and exit early. Also, the characters you check are not special, they're "illegal" or "invalid" in your implementation so change name to reflect that:

    if (illegalCharactersExist(url)) {
        return false;
    }

Missing final

Variables that are not supposed to change should be marked as final. If you decide to keep the containsSpecialCharacters variable, it should be marked as final (and named as decribed above).

final boolean containsIllegalCharacters = illegalCharactersExist(url);

Reuse Pattern

The Pattern class is thread safe. You should compile the pattern once into a static variable and reuse it in the matcher. Also, regex is not a good name. It tells what the variable is, not what it's purpose is. Naming should always reflect purpose.

    private static final Pattern ILLEGAL_CHAR_PATTERN = Pattern.compile("[^A-Za-z0-9.-]");


A single function for implementing Newton forward and backward polynomial interpolation On various websites, I've come across a lot of realizations of Newton polynomial interpolation that use separate functions for forward and backward interpolation, respectively. Such solutions seem ugly to me because the functions look pretty much the same.

For a single Newton interpolation function, I treat the backward interpolation case as forward interpolation with the data points written in reverse order. Usually the data points come already sorted in ascending order by x values, so the reverse order means simply going through the data points from right to left over an interval.

With all these in mind, my Newton interpolation function in C is:

/*
Error codes:
-2 - malloc() error
-1 - range check error
 0 - no error (success)
*/

// The necessary typedefs

typedef struct {
    int points;
    double *xList, *yList;
} DataTable;

typedef struct {
    double *coeff;
    int degree;
    double *xList;
} NewtonPoly;

// I've excluded the code for checking if the data table is filled properly.

int getNewtonPoly(DataTable *table, int nodes, NewtonPoly *poly)
{
    int n = abs(nodes);
    int points = table->points;
    if (n > points || n == 0)
        return -1;

    double *result = (double *)malloc(n * sizeof(double));
    if (result == NULL)
        return -2;
    double *tmp = (double *)malloc(n * sizeof(double));
    if (tmp == NULL)
        return -2;
    double *xList = (double *)malloc(n * sizeof(double));
    if (xList == NULL)
        return -2;

    if (nodes > 0)
        for (int i = 0; i < n; ++i) {
            xList[i] = table->xList[i];
            tmp[i] = table->yList[i];
        }
    else
        for (int i = points - 1, j = 0; i >= points - n; --i, ++j) {
            xList[j] = table->xList[i];
            tmp[j] = table->yList[i];
        }

    result[0] = tmp[0];
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= n - i - 1; ++j)
            tmp[j] = (tmp[j + 1] - tmp[j]) / (xList[j + i] - xList[j]);
        result[i] = tmp[0];
    }

    poly->degree = n - 1;
    poly->coeff = result;
    poly->xList = xList;
    free(tmp);
    return 0;
}

Are there some better approaches to this problem?

Don't cast the result from malloc()
Instead, include <stdlib.h> so that the compiler knows it returns a void*.  Also, it's a good practice to use the object name as argument to sizeof, so its type can be changed in one place (e.g. if you wanted to use float or long double instead).  It's idiomatic to test a pointer isn't null by using the ! operator on it.
double *result = malloc(sizeof result * n);
if (!result)
    return -2;

Be careful about memory leaks
I don't see a corresponding free() of result or xList - we should be clear that this is the caller's responsibility.  It's also easily missed that the function won't free an existing poly->coeff or poly->xList before overwriting - I think that's a big magnet for inviting leaks.


Laravel Pagination with haversine formula in it I'm using the haversine formula to count distance from selected post-code to desired destination.

I have the following scope in App\Models\Business.php:

public function scopeDistance($query, $latitude, $longitude, $radius)
{
    $query->getQuery()->orders = [];
    return $query->select('*')
                 ->selectRaw("( 3959 * acos( cos( radians($latitude) ) * cos( radians( latitude ) )  * cos( radians( longitude ) - radians($longitude) ) + sin( radians($latitude) ) * sin(radians(latitude)) ) ) AS distance")
                 ->having('distance', '<=', $radius)
                 ->orderBy('distance');
}

Everything seems pretty ok, except the case when I use the paginate() method instead of get() in builder.

There are solutions out there, but I couldn't get these to work or were too complicated. I came up with this solution and I would like to hear feedback in terms of performance or memory usage.

This is the query at the end:

"select count(*) as count from (select ( 3959 * acos( cos( radians(51.5872718) ) * cos( radians( latitude ) )  * cos( radians( longitude ) - radians(-0.549759) ) + sin( radians(51.5872718) ) * sin(radians(latitude)) ) ) AS distance from `businesses` having `distance` <= ?) as harversine"

and custom_pagination function:

function custom_paginator($builder, $per_page)
{
    $path = current_route();
    $current_page = \Illuminate\Pagination\Paginator::resolveCurrentPage();

    if ( ! isset($builder->getQuery()->columns[1])) $count = $builder->count();
    else
    {
        $query = clone $builder->getQuery();
        $query->columns = [ $query->columns[1] ];
        $query->orders = null;
        $count = array_get(\DB::select("select count(*) as count from ({$query->toSql()}) as haversine", $query->getBindings()), 0)->count;
    }

    return new \Illuminate\Pagination\LengthAwarePaginator(
        $builder->forPage($current_page, $per_page)->get(),
        $count, $per_page, null, compact('path')
    );
}

Is there anything I should change or improve?

I think that working with a natural language style query builder has sent your implementation a little astray. I don't understand why you need to select a count of rows from a sub-queried result set when you could just count the rows returned from the query itself, without even pulling the result set down into the application.

Outside of that, I find your code hard to read.

Don't mix use of brackets on each side of if-else conditional
Consider using PSR-2 compliant styles

putting start of brackets for functions/methods, conditionals and looping constructs on same line.
Don't mix snake_case and camelCase within your user-written code.
One instruction per line.

Limit line lengths to ~80 characters.


finished Josephus-Problem in C#, how to make this more efficient? using System;
using System.Collections.Generic;

namespace Function_JosephusSurvivor
{
    class Program
    {
        static void Main(string[] args)
        {
            //Debug purposes
            Console.WriteLine(JosSurvivor(7, 3));

            Console.ReadKey();
        }

        //Actual function:
        public static int JosSurvivor(int n, int k)
        {
            // n = amount of people(array size)
            // k = every k'th index will be yeeted

            List<int> list = new List<int>();
            int iCounter = 1; //always count till the size of the list
            int iWatcher = 1; //always count till the size of k
            for (int i = 1; i <= n; i++)
            {
                list.Add(i);
            }

            do
            {

                if (iWatcher+1 == k)
                {
                    list.RemoveAt(iCounter);
                    iWatcher = 0;
                }

                iWatcher++;
                iCounter++;

                if (iCounter == list.Count) // -1 because index
                {
                    iCounter = 0;
                }
                else if (iCounter > list.Count)
                {
                    iCounter = 1; //if one is jumped due to deleteting
                }

            } while (list.Count != 1);

            return list[0]; //winner
        }
    }
}

My question is:

how could you make this more efficient? What could I do better?

I'm trying to submit this as my solution on a practicing page. Unfortunately, it always times out. Therefore I need to make this more efficient I believe.

Thanks in advance :)!

Also feel free to add fitting Tags :)!

List<int> list = new List<int>();
        int iCounter = 1; //always count till the size of the list
        int iWatcher = 1; //always count till the size of k
        for (int i = 1; i <= n; i++)
        {
            list.Add(i);
        }

You can initialize list more elegantly:

List<int> list = Enumerable.Range(1, n).ToList();

For n = 2; k = 1 it runs infinitely?

Your counting and indexing seem ok, but are a little difficult to comprehend. It can be done a lot easier using modular operations:

static int JosSurvivor(int n, int k)
{
  List<int> positions = Enumerable.Range(1, n).ToList();
  int index = k % n - 1; // %n is important for k > n

  while (positions.Count > 1)
  {
    if (index < 0) index += positions.Count;  // when (index + k) % poisitons.Count == 0 then index becomes -1 from the line below
    positions.RemoveAt(index);
    index = (index + k) % positions.Count - 1;
  }

  return positions[0];
}

Another approach building on the same principle is to maintain a fixed array of indices and then left-shift the reminder of the indices for each found index while decrement n by 1:

static int JosSurvivor(int n, int k)
{
  int[] positions = Enumerable.Range(1, n).ToArray();
  int index = k % n - 1;

  while (n > 1)
  {
    if (index < 0) index += n;
    Array.Copy(positions, index + 1, positions, index, n - index - 1);
    n--;
    index = (index + k) % n - 1;
  }

  return positions[0];
}

There seems to be a little performance gain - but not significant.

Yet another version that uses a fixed array of flags, that are set for each found index:

static int JosSurvivor(int n, int k)
{
  int counter = 0;
  int index = -1;
  int runner = 0;
  bool[] positions = new bool[n];

  while (counter < n - 1)
  {
    runner += k;
    int temp = 0;
    do
    {
      index = (index + 1) % n;
    } while (positions[index] || ++temp < k);

    if (runner > 0 && runner % k == 0)
    {
      positions[index] = true;
      counter++;
    }
  }

  for (int i = 0; i < n; i++)
  {
    if (!positions[i])
      return i + 1;
  }

  throw new InvalidOperationException("No last position found");
}

This is very fast for small ks - even for large ns - but becomes slower when k increases.


Python Back-Up Script I wrote this script to backup some important files.  It backs up the files to a local folder as well as to an external hard drive.  It creates a new subdirectory which has its name constructed with the current date and time.  Works perfectly, but I'm just wondering if there are any Python best-practices I'm missing or if there's any way I could've made it better!

import datetime
import os
import shutil

GOOGLE_DRIVE_DIRECTORY = 'C:\\Users\\Jeff\\Google Drive\\Manifest_Destiny'
MAIN_BACKUP_DIRECTORY = 'C:\\Users\\Jeff\\Desktop\\Manifest_Destiny_Backups\\md_backup_{0}'
EXTERNAL_DRIVE_DIRECTORY = 'F:\\My Files\\Manifest_Destiny_Backups\\md_backup_{0}'

def get_backup_directory(base_directory):
    date = str(datetime.datetime.now())[:16]
    date = date.replace(' ', '_').replace(':', '')
    return base_directory.format(date)

def copy_files(directory):
    for file in os.listdir(GOOGLE_DRIVE_DIRECTORY):
        file_path = os.path.join(GOOGLE_DRIVE_DIRECTORY, file)
        if os.path.isfile(file_path):
            shutil.copy(file_path, directory)

def perform_backup(base_directory):
    backup_directory = get_backup_directory(base_directory)
    os.makedirs(backup_directory)
    copy_files(backup_directory)

def main():
    perform_backup(MAIN_BACKUP_DIRECTORY)
    perform_backup(EXTERNAL_DRIVE_DIRECTORY)

if __name__ == '__main__':
    main()

You can simplify paths using forward slashes:

GOOGLE_DRIVE_DIRECTORY = 'C:/Users/Jeff/Google Drive/Manifest_Destiny'
MAIN_BACKUP_DIRECTORY = 'C:/Users/Jeff/Desktop/Manifest_Destiny_Backups/md_backup_{0}'
EXTERNAL_DRIVE_DIRECTORY = 'F:/My Files/Manifest_Destiny_Backups/md_backup_{0}'

Instead of converting a date to a string, which may be locale dependent too, and then replacing characters in it, better to use strftime to generate exactly the format that you want:

def get_backup_directory(base_directory):
    date = datetime.datetime.now().strftime('%Y-%m-%d_%H%M')
    return base_directory.format(date)

If a variable contains a format, I would suffix it with _fmt or _format to clarify.

I don't really like global constants inside methods, so I would split copy_files like this:

def copy_files_to(srcdir, dstdir):
    for file in os.listdir(srcdir):
        file_path = os.path.join(srcdir, file)
        if os.path.isfile(file_path):
            shutil.copy(file_path, dstdir)

def copy_files(dstdir):
    copy_files_to(GOOGLE_DRIVE_DIRECTORY, dstdir)

The advantage of this is that copy_files_to is easier to unit test. I think it's also good to use more specific names for the directory variables to clarify which one is a source and destination.


Find maximum gap between elements of an array I am solving interview questions from here.

Problem : Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].
Example : A =  [3 5 4 2]  Output : 2 for the pair (3, 4)

Here is my solution:
def maximum_gap( A):
    """find maximum gap between index(j -i ) with  A[i] <= A[j]"""
    gap = 0
    A = list(map( list,enumerate(A))) # get list of [index,value]
    for item in A:
        item[0],item[1] = item[1], item[0] # swap index with value
    a = sorted(A)  # sort list A as per values

    max_index = a[0][1] # initialise max_index to first index in sorted list
    min_index = a[0][1] # initialise min_index to first index in sorted list

    for v,i in a:
        if i > max_index:  # if current > max_index, set max to current
            max_index = i
        if i < min_index:  # if current < min_index, set min to current
            min_index = i
            max_index = i  # reset max to current

        gap_new = max_index - min_index  # find the maximum gap
        if gap < gap_new:
            gap = gap_new

    return gap

Test cases:
print maximum_gap([-1,-1,2])  == 2
print maximum_gap([1,3,5,7,2,4,10])  ==  6
print maximum_gap([3,2,1]) == 0
print maximum_gap([3,2,1,4]) == 3
print maximum_gap([2,2,1,4,3])  == 4
print maximum_gap([ 0,1,2,3])  == 3
print maximum_gap([ 100,100,100,100,100])  == 4

How can I make this code better?

The code looks pretty good. Here are a few suggestions to make it more Pythonic.

Use generator expressions to their fullest

The entirety of the initialization of a can be reduced from:

A = list(map(list, enumerate(A)))  # get list of [index,value]
for item in A:
    item[0], item[1] = item[1], item[0]  # swap index with value
a = sorted(A)  # sort list A as per values

for v, i in a:
    ....

To:

for v, i in sorted((v, i) for i, v in enumerate(A)):
    ....

Use Python's builtins:

Python has the max() function that will replace

gap_new = max_index - min_index  # find the maximum gap
if gap < gap_new:
    gap = gap_new

with:

gap = max(gap, max_index - min_index)

similarly:

if i > max_index:  # if current > max_index, set max to current
    max_index = i

can be just:

max_index = max(max_index, i)

pep8

The violations were very minor, by I recommend formatting your code in accordance
with pep8.  This is important
when sharing code, as the consistent style makes it much easier for other
programmers to read your code.  There are various tools available to
assist in making the code pep8 compliant.  I use the
PyCharm IDE which will show pep8
violations right in the editor.

Restructured Code:

def maximum_gap(A):
    """find maximum gap between index(j -i ) with  A[i] <= A[j]"""

    min_index = max_index = len(A)
    gap = 0

    for v, i in sorted((v, i) for i, v in enumerate(A)):
        if i < min_index:  # if current < min, set min & max to current
            min_index = max_index = i
        else:
            # if current > max, set max to current
            max_index = max(max_index, i)

        # find the maximum gap
        gap = max(gap, max_index - min_index)

    return gap

assert maximum_gap([-1, -1, 2]) == 2
assert maximum_gap([1, 3, 5, 7, 2, 4, 10]) == 6
assert maximum_gap([3, 2, 1]) == 0
assert maximum_gap([3, 2, 1, 4]) == 3
assert maximum_gap([2, 2, 1, 4, 3]) == 4
assert maximum_gap([0, 1, 2, 3]) == 3
assert maximum_gap([100, 100, 100, 100, 100]) == 4


Time complexity of radix sort I read time complexity of radix sort is O(wn) or O(n log n), if all n numbers are distinct. After implementation it look to me as if I have implemented radix sort which has time complexity of O(n ^2). Please take a look at my implementation and suggest, if there is some implementation problem or my observation about time complexity is wrong.

Please note: I have hard coded few values for simplicity to sort 3 digit numbers only.

private void LSBSort(int[] arr) {
    _LSBSort(arr, 1);
}

private void _LSBSort(int[] arr, int divisor) {
    Deque[] deques = new Deque[10];
    for(int i = 0 ; i < arr.length ; i++) {
        int mod = (arr[i] /divisor ) % 10;
        if (deques[mod] == null) {
            deques[mod] = new ArrayDeque<>();
        }
        deques[mod].add(arr[i]);
    }
    divisor *= 10;
    if (divisor > 1000) {
        return;
    }

    int cursor = 0;
    for (int i = 0 ; i < 10 ; i++) {
        if (deques[i] != null) {
            for (int j = 0 ; j <= deques[i].size() ; j++) {
                cursor = cursor + j;
                arr[cursor] = (int)deques[i].pollFirst();
            }
            cursor++;
        }
    }
    _LSBSort(arr, divisor);
}

First: the runtime is O(wn), as it should be for this algorithm.

Consider a single run of _LSBSort. Let n be the length of arr. Clearly the first loop is time O(n). Let si be the length of deques[i]. Then the second loop is time
$$ O(s_1) + O(s_2) + \dots + O(s_{10}) = O(s_1 + s_2 + \dots + s_{10}).$$
Noting that each element is present in exactly one of the deques, we conclude
$$s_1 + s_2 + \dots + s_{10} = n.$$
Thus the entire method runs in time O(n). As it is called w times, we conclude the entire algorithm is O(wn) time.

Second: some comments on the code.

These methods should be static.
Use an ArrayList for deque. Arrays of generics are just too ugly.
Call the list deques because it is plural.
Initialize all the deques up front. Clear and reuse between iterations.
Use extended for loops throughout.
Use loop instead of recursion.

private static void LSBSort(int[] arr) {
    List<ArrayDeque<Integer>> deques = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
        deques.add(new ArrayDeque<Integer>());
    }

    for (int d = 1; d <= 1000; d *= 10) {
        for(int i : arr) {
            deques.get((i / d) % 10).add(i);
        }

        int cursor = 0;
        for (Deque<Integer> D : deques) {
            for (Integer j : D) {
                arr[cursor++] = j;
            }

            D.clear();
        }
    }
}


Optimizing code for foreach I need to HTML table output like:

    ITEM
    ITEM
    ITEM

    ITEM
    ITEM
    ITEM

    ITEM
    ITEM
    ITEM

My code before:

<?php $i = 1;?>
<?php foreach ($items as $item): ?>
<?php if ($i == 1 || $i == 4 || $i == 7 ......): ?>

<?php endif; ?>
     CONTENT
<?php if ($i == 3 || $i == 6 || $i == 9 ......):?>

<?php endif;?>
<?php $i++ ?>
<?php endforeach; ?>

My code now:

<?php $i = 1;?>
<?php foreach ($items as $item): ?>
<?php if ($i % 3 == 1): ?>

<?php endif; ?>
     CONTENT
<?php if ($i % 3 == 0):?>

<?php endif;?>
<?php $i++ ?>
<?php endforeach; ?>

I assume the $items array is indexed by numbers, otherwise you have to change the code below to include a counter.

foreach ($items as $i => $item) {
    if ($i % 3 == 0) {
        // Do something for 0, 3, 6, 9, ...
    } elseif ($i % 3 == 1) {
        // Do something for 1, 4, 7, 10, ...
    } elseif ($i % 3 == 2) {
        // Do something for 2, 5, 8, 11, ...
    }
}

This code uses the modulo operator %.

After your edit
The following code is a more clear solution to your problem:

foreach (array_chunk($items, 3) as $chunk):
    echo '

';
    foreach ($chunk as $item):
        echo '' . $item . '	';
    endforeach;
    echo '

';
endforeach;


Recursive statement with linq I have a recursive statement that removesactivities that don't have a resource type for a certain OrganizationID. I was wondering if there was a better way to do this where I can eliminate some of the for loops and use a little more linq

    private IEnumerable<SubProjectDto> GetProjectAndActivitiesForByOrg(IEnumerable<SubProjectDto> children, Guid? organiazaitonId)
    {
        var subProjects = new List<SubProjectDto>();
        subProjects.AddRange(children);
        for (var i = 0; i < subProjects.Count; i++)
        {

            var activities = new List<ActivityDto>();
            activities.AddRange(subProjects[i].Activities);
            for (var j = 0; j < activities.Count; j++)
            {
                var resourceTypesForOrgs = activities[j].ActivityPersons.Where(x => x.ResourceType.OrganizationId == organiazaitonId).Count();

                if (resourceTypesForOrgs == 0)
                    activities.Remove(activities[j]);
            }

            subProjects[i].Activities = activities;

            if (subProjects[i].Children.Any())
                GetProjectAndActivitiesForByOrg(subProjects[i].Children, organiazaitonId);

        }
        children = subProjects;
        return children;
    }

Here's my attempt. I assume, LINQ-method based approach is allowed by your problem statement.

I have not tested the code, so please cover it by unit test(s) which you may already have.
Also, please notice that this is not a pure function in the functional sense of this term. It means, the method changes the state of the arguments passed in (which may or may not be desirable in different scenarios).

private IEnumerable<SubProjectDto> GetProjectAndActivitiesForByOrg(IEnumerable<SubProjectDto> children, Guid? organiazaitonId)
{
    return children.Select(childSubProject =>
    {
        childSubProject.Activities.RemoveAll(activity =>
                activity.ActivityPersons.All(person => person.ResourceType.OrganizationId != organiazaitonId));

        // if (childSubProject.Children.Any()) // UPD: This check is not really required
        GetProjectAndActivitiesForByOrg(childSubProject.Children, organiazaitonId);

        return childSubProject;
    });
}


Reducing memory footprint with queue of classes I hope I've asked this in the right area. I'm writing a program that deals with enqueueing a class on STL queue in C++. Initially it queues initializations of the class. Then while the queue is not empty, it performs some operations on the class and then checking if an inequality works it either pops the queue or passes the class into function that creates more versions of the class and then queues the extra versions. It then pops the original initialization.

I'm trying to change this so it suits the format, I've also changed the title. At this stage I'm looking to minimize memory footprint mainly and maximize speed as a secondary. I'm basically looking for advice on lines I can remove or where it's inefficient. int main() would also include code to initially queue Subcubes. I hope this is more what you're looking for but if not just let me know.

Vec map(const Vec &g,const int &p);      \\I haven't added these as I dont think theyre massicaly important
double pnorm(const Vec &s,const int &p);
typedef vector<double> Vec;
typedef vector<Vec> Mat;
typedef queue< Subcube>  SUBQUEUE;

void subdivide(Subcube &nw, const Subcube &f ,const Vec &t)
{
 // cout << "running subdivide" << endl;

 Vec v = t;
 v.insert(v.begin() + f.k, 0);

int n = f.e.size();
nw.e.assign(n,0);  //just to avoid runtime error
nw.hside = (f.hside/2);
nw.k= f.k;

for(int j=0;j<n;j++)
{
    nw.e.at(j) = f.e.at(j) +(f.hside/2)*v.at(j);
    }
  }

int main(){
while(!q.empty())
{
    double upperb=0;
    upperb = 2*pow(double(n),0.25)*q.front().hside;
    Vec radmap = map(q.front().e,p);   // taking the vector from front subcube and maping it radially from the l-infy to the l4 unit ball
    double temp = pnorm(a*radmap,p);   // taking  a nomrm of matrix a multiplied by radmap
    if(temp>M)
        {M=temp;
        final = radmap;}               // to see what vector maximised it at the end
    if(temp>= M*(1+e)*(1-(((p-1)/2)*pow(upperb,2)))){
        int tr = pow(2,n-1);
        for(int j =0;j<tr;j++)
        {
            q.push(subdivide(q.front(),set.at(j))); // splits subcube into 2^n-1 subcubes
        }
        counter++;                  //counts related to number of subcubes created
       }
       q.pop();}
}

class Subcube
{
  public:
    Subcube();
    void printvector(const int& n);
    void Subcubeset(const int& i,const int& n);
    vector<double> e;
    double hside;
    char k;
    virtual ~Subcube();

protected:
private:
};

As @Lstor mentions in the comments, clean up your formatting and indentation.  There should be plenty of resources online, and you can also look at other highly-developed code for ideas.  Above all, keep it clear and consistent.

Naming

This isn't a very descriptive typedef:

typedef vector<double> Vec;

There's no point in using a typedef here if you're just going to name it what it already it.  Name it based on how this type is used in your program, otherwise don't bother renaming it.
Why is this all uppercase?

typedef queue< Subcube>  SUBQUEUE;

It's a type, not a macro.  Just like you have with Vec, have it start with an uppercase, but don't use all uppercase.

Functions

I'm not sure what this is:

for(int j=0;j<n;j++)
{
    nw.e.at(j) = f.e.at(j) +(f.hside/2)*v.at(j);
    }
  }

For one thing, the second closing curly brace is for the function.  But the poor indentation makes it appear to belong to the loop.

Put some whitespace between the operators and operands within the loop statement.  This should be done everywhere for clarity.

Consider adding comments explaining what the loop is doing.  I'm not even sure what is going on inside.  Even if something seems obvious to you, it won't be obvious for everyone.  Now, if something is too obvious, then it doesn't warrant commenting.  But this does.
Many things from main() and below is very unclear.  Not only should everything inside main() be indented, but it appears that you're missing a closing brace (the one above class looks like it belongs to the while loop).

That's an odd place to declare the class.  It should be put into a separate header file, with this file including the header.  If you're going to have main() defined after everything else (which is good), make sure it is the last thing in the file.

Subcube

I'm not sure if you already have the implementation elsewhere and haven't included it here, but make sure you have something for it.  It would be helpful to see how those data members are used and how those member functions perform.
Everything is crammed into public, and there are some things that shouldn't be there.  The data members (k, hside, and e) should be under private.  The functions and constructor should stay public, unless some shouldn't be used by outside code.  If you're not using protected, just get rid of it.  It doesn't need to be there for nothing.
In printvector() and Subcubeset(), you don't need to pass the ints by const&.  Passing an int is relatively cheap, so just pass them by value.
printvector() should be const as it shouldn't be modifying any data members:

void printvector(const int& n) const;

Subcubeset() should use camelCase naming as it's a function.


Subclassing Flask for Permissions with Google App Engine I'm trying to set up a very lightweight permission system using Google App Engine and Flask.

The end result I am hoping for is that each individual view is its own permission, and in an admin panel you can assign the views each user is allowed to see.

How would I set this up better? It works fine, but I'm going to be querying ndb on operator for each and every view everytime a page loads.

from google.appengine.api import users
from google.appengine.ext import ndb
import logging
from flask import Flask, redirect, make_response, request

def user_authorized(rule):
    user = users.get_current_user()
    username = str(user)
    user_info = Operators.query(Operators.username == username).get()
    if not user_info:
        return False
    if rule in user_info.permissions:
        return True
    else:
        return False

def forbidden_view():
    return make_response(
        'You do not have permission or this user does not exist. Login'.format(users.create_login_url(request.url)),
        403
    )

class FlaskWithPermissions(Flask):
    def route(self, rule, **options):
        def decorator(f):
            endpoint = options.pop('endpoint', f.__name__)
            if user_authorized(rule):
                self.add_url_rule(rule, endpoint, f, **options)
                return f
            else:
                self.add_url_rule(rule, endpoint, forbidden_view, **options)
        return decorator

app = FlaskWithPermissions(__name__)

class Operators(ndb.Model):
    username = ndb.StringProperty()
    permissions = ndb.StringProperty(repeated=True)

@app.route('/')
def index():
    return 'OK /'

@app.route('/test')
def test():
   return 'OK /test'

@app.route('/testfail')
def testfail():
    return 'OK /testfail'

The test data I have in the database is:

Operators(username='test@example.com', permissions=['/', '/test']).put()

And then log in as test@example.com, of course.

The first thing that comes to mind is just to cache user permissions in memcache, but that might or might not be necessary. I'd try this way first and see if you run into issues.

A simpler approach would be to define each user's key to be their username, then use get_by_id(). That has the advantage of being automatically memcached by ndb and being faster (I think).


More efficient way of doing this hide()/show() jQuery I currently have the following jQuery code, which does work, but I know there is a better way of doing it without having to repeat myself so much:

Basically, when a button is clicked, I need to show the additional div for that content type and hide the rest. If it's just a Post, then all of the divs are hidden as there is no specific div for the post type.

The HTML looks like this:

  <button id="btn-post" class="btn btn btn-primary active" type="button">Post</button>
  <button id="btn-game" class="btn btn btn-primary" type="button">Game</button>
  <button id="btn-video" class="btn btn btn-primary" type="button">Video</button>
  <button id="btn-giveaway" class="btn btn btn-primary" type="button">Giveaway</button>

game stuff

video stuff

giveaway stuff

What's the more efficient way of writing that jQuery?

Try this:

http://jsfiddle.net/VYSXn/

Change your HTML to (note the data attributes):

  <button id="btn-post" class="btn btn btn-primary active" type="button">Post</button>
  <button id="btn-game" data-target="game_container" class="btn btn btn-primary" type="button">Game</button>
  <button id="btn-video" data-target="video_container" class="btn btn btn-primary" type="button">Video</button>
  <button id="btn-giveaway" data-target="giveaway_container" class="btn btn btn-primary" type="button">Giveaway</button>

game stuff

video stuff

giveaway stuff

and now your javascript can just be:

$(document).ready(function() {

    $('.container').hide();
    $('.btn-group button').click(function(){
        var target = "#" + $(this).data("target");
        $(".container").not(target).hide();
        $(target).show();
    });

});


Hackerrank: Fraudulent Activity Notifications I'm having trouble on a question from Hackerrank, this solution works for smaller lists but seems to collapse when the list grows to 200,000 where I get the error "Wrong Solution". The problem is here so you could reproduce it. Im not sure if there is an error in my code whereby it would fail. Is there anyway to improve the efficiency of my solution?
When I encounter these sort of issues where it fails at very high lists or anything of the sort, how should I react? What kind of issue should I expect to solve?
Problem text  (Incase link doesnt work):
If the amount spent by a client on a particular day is greater than or equal to 2x the client's median spending for a trailing number of days, they send the client a notification about potential fraud.
The bank doesn't send the client any notifications until they have at least that trailing number of prior days' transaction data (d) for a period of n days. Determine the number of times the client will receive a notification over all n days.
The following is the whole Hackerrank Code required to run the problem, I wrote the functions "Median" and "activityNotifications":
#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

double Median(vector<int> arr)
{
    int d = arr.size();

    double Even = (arr[(d/2)-1] + arr[((d/2)+1)-1]) / (double)2;
    double Odd = arr[((d+1)/2)-1];

    return (d%2==0)? Even: Odd;
}

int activityNotifications(vector<int> expenditure, int d) {

    int Notices = 0;

    vector<int> SpendData = vector<int>(expenditure.begin(),expenditure.end());
    sort(SpendData.begin(),SpendData.end());

    vector<int> SpendDataMedian = vector<int>(SpendData.begin(),SpendData.begin() + d);

    for (int i = d; i < expenditure.size();++i)
    {
        if ((Median(SpendDataMedian)*2) <= expenditure[i])
            {Notices++;}

        SpendDataMedian.erase(SpendDataMedian.begin());
        SpendDataMedian.push_back(SpendData[i]);

    }
    return Notices;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int d = stoi(first_multiple_input[1]);

    string expenditure_temp_temp;
    getline(cin, expenditure_temp_temp);

    vector<string> expenditure_temp = split(rtrim(expenditure_temp_temp));

    vector<int> expenditure(n);

    for (int i = 0; i < n; i++) {
        int expenditure_item = stoi(expenditure_temp[i]);

        expenditure[i] = expenditure_item;
    }

    int result = activityNotifications(expenditure, d);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

Sample input is:
9 5
2 3 4 2 3 6 8 4 5

Expected output is:
2

Yes, deciding for each day in isolation is easy enough. And produces reusable and well-defined abstractions.
Unfortunately, it costs you. Specifically, it needs too long. Use a running-total, thus each day needs only subtracting one trailing day, adding the last day, and comparing to that day. The cost is pretty independent of the number of trailing days considered. It is easily adapted to streams.
Additionally, you really should avoid floating-point, not necessarily due to its runtime cost, but its design cost. Or do you have the time and inclination to prove conclusively whether your handling of floating point rounding is right?
I won't go into all the bad habits hackerrank encourages, like using <bits/stdc++.h>, using namespace std;, all the useless copies, ...
If you are interested, it's repeated enough times already.


Bubble sort in Haskell The following code is part of my practice in implementing algorithms in Haskell. I'm aware that bubble sort is a bad choice for sorting sequences in real applications.

import Test.QuickCheck
import Data.List (sort)

-- Going from left to right, swaps two adjacent elements if they are not in order.
-- After the first go, the largest element in the list has bubbled up to the end
-- of the list. In the next go, we start swapping from the first element to the
-- penultimate element and so forth.
bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = go xs (length xs -1)
  where go xs limit | limit > 0 = let swapped = swapTill xs limit in
                                  go swapped (limit -1)
                    | otherwise = xs

-- Swaps adjacent elements in a list if they are not in order, until a limit.
-- After this, the largest elements, from limit to (length xs),
-- are sorted at the list's end.
swapTill :: (Ord a, Num p) => [a] -> p -> [a]
swapTill xs limit = go xs 0
  where go xs count | count < limit = swap xs
                    | otherwise = xs
                      where swap [x] = [x]
                            swap (x:y:xs) | x < y     = x : (go (y:xs) (count +1))
                                          | otherwise = y : (go (x:xs) (count +1))

-- Tests
bubbleSortWorks :: [Int] -> Bool
bubbleSortWorks xs = bubbleSort xs == sort xs

runQuickCheck = quickCheck bubbleSortWorks

I'd very much appreciate hints on how to make this implementation shorter (maybe using a fold) and/or more readable.

Here's your shortening including a fold.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = foldr swapTill xs [1..length xs-1]

swapTill :: Ord a => Int -> [a] -> [a]
swapTill 0 = id
swapTill count = \(x:y:xs) -> min x y : swapTill (count-1) (max x y:xs)

Reordering the swaps to sort a growing suffix of the list banishes Int.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort = foldr swapTill []

swapTill x [] = [x]
swapTill x (y:xs) = min x y : swapTill (max x y) xs


Text processing program I have written a Python program to loop through a list of X files, open each one, read line by line, and write (append) to an output file. Being that these files are several GB each, it is taking very long.

I am looking for suggestions to improve the performance of this program. I have no formal CS training so it's likely I am missing the "obvious solution" to this problem; I have done some research but again, my limited knowledge (and other higher priority tasks) limits my ability to implement such.

for name in PR_files:
    with open(PR_path + name, 'r') as f:
        line = f.readline()
        while line:
            with open(PR_out_path, 'a') as g:
                g.write(line + '\n')
                line = f.readline()
    f.close()

The program will work but will have a blank line between each line in the output text file; this is because the first line of the next file began on the last line of the previous file (my solution to this problem was to add '\n' to each line being written to the output file. For that reason I wrote another block to remove all blank lines in the output file (yes I know, very inefficient).

# this removes all blank lines from out put file
with open(PR_out_path) as this, open(PR_out_path_fix, 'w') as that:
    for line in this:
        if not line.strip():
            continue
        that.write(line)

PLEASE NOTE: I attempted to do this, as oppose to reading line by line but I received a MemoryError.

with open(PR_out_path, 'a') as g:
    for name in PR_files:
        with open(PR_path + name, 'r') as f:
            g.write(f.read())

Your original code:

with open(PR_out_path, 'a') as g:
    for name in PR_files:
        with open(PR_path + name, 'r') as f:
            g.write(f.read())

works but, as you found, has problems if the entire file can't be read into memory.  The solution to that problem is to read the input file in chunks:

with open(PR_out_path, 'a') as g:
    for name in PR_files:
        with open(PR_path + name, 'r') as f:
            while True:
                data = f.read(ChunkSize)
                if not data:
                    break
                g.write(data)

where ChunkSize is something like 1GB.

But if speed is your only requirement why not use the tools offered by the operating system, as others have noted?