Project Euler #49: Find 12-digit number concatenating a three terms sequence First of all, project Euler has been a great help for me to learn Clojure. I tried for months trying to get web projects going but ended up frustrated with and struggling with tooling and libraries more than anything else. The code below gives the solution to Problem 49 in Project Euler:

  The arithmetic sequence, 1487, 4817, 8147, in which each of the terms
  increases by 3330, is unusual in two ways: (i) each of the three terms
  are prime, and, (ii) each of the 4-digit numbers are permutations of
  one another.

  There are no arithmetic sequences made up of three 1-, 2-, or 3-digit
  primes, exhibiting this property, but there is one other 4-digit
  increasing sequence.

  What 12-digit number do you form by concatenating the three terms in
  this sequence?

;; gen-primes Taken from https://stackoverflow.com/a/7625207/466694
(defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
  []
  (let [reinsert (fn [table x prime]
                   (update-in table [(+ prime x)] conj prime))]
    (defn primes-step [table d]
      (if-let [factors (get table d)]
        (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
               (inc d))
        (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                       (inc d))))))
    (primes-step {} 2)))

(defn get-digits [num]
  (->> [num []]
     (iterate (fn [[num digits]]
                (when (> num 0)
                  [(quot num 10) (conj digits (rem num 10))])))
     (take-while some?)
     (last)
     (second)))

(defn are-permutations-of-each-other? [num1 num2]
  (= (sort (get-digits num1)) (sort (get-digits num2))))

(let [four-digit-primes (->> (gen-primes)
                             (drop-while #(< % 1000))
                             (take-while #(< % 10000))
                             (apply sorted-set))]
  (->> (for [i four-digit-primes
             j four-digit-primes]
         [i j])
       (remove #(apply = %))
       (filter #(apply are-permutations-of-each-other? %))
       (filter (fn [[n1 n2]]
                 (let [mx (max n1 n2)
                       mn (min n1 n2)
                       diff (- mx mn)
                       next (+ mx diff)]
                   (and (< next 10000)
                        (four-digit-primes next)
                        (are-permutations-of-each-other? n1 next)))))
       (map sort)
       (distinct)
       (map #(cons (+ (second %) (- (second %) (first %))) %))
       (map sort)
       (map #(map str %))
       (map (partial apply str))
       (second)))

For example, the last let expression is the result of tinkering for half an hour or so until I get the information I want out of it. Two questions:

I've found threading macros (especially ->>) a pure joy to work with. But, is there such a thing as a threading expression that is too long?
I know that this is throw-away coding, but what things can I do to improve this code to fit best practices? Are there things I'm doing wrong?

There's a few things that can be improved here:

First, I'm not sure if you neglected it here or if you actually aren't using it, but every file should start with a call to ns. This sets the namespace that the code following it will be in so other files can require it properly. If the code resides in src/my_thing/my_file, you would have

(ns my-thing.my-file)

At the top.

Second, unfortunately, that gen-primes function that you took from SO isn't a good example a proper practice. Unless you have an extraordinarily good reason, don't use def (and by extension, defn) to create a locally bound symbol. def creates globals that exist even once the function has returned:

(take 0 (gen-primes)) ; Run the function just so the inner defn happens
=> ()

(type primes-step)
=> irrelevant.cr2_original$gen_primes$primes_step__4224

Note how using using primes-step doesn't lead to an error. It's in scope!

To fix this, you could either just use let and define the function like was done with reinsert:

(defn gen-primes []
  (let [reinsert (fn [table x prime]
                   (update-in table [(+ prime x)] conj prime))

        primes-step (fn primes-step [table d]
                      (if-let [factors (get table d)]
                        (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
                               (inc d))
                        (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                                       (inc d))))))]

    (primes-step {} 2)))

or, since you're only defining local functions, this is a good use-case for letfn:

(defn gen-primes []
  (letfn [(reinsert [table x prime]
            (update-in table [(+ prime x)] conj prime))

          (primes-step [table d]
            (if-let [factors (get table d)]
              (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
                     (inc d))
              (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                             (inc d))))))]

    (primes-step {} 2)))

The latter doesn't have as much indentation, which is always nice.

This can be greatly simplified though if you're willing to sacrifice some performance for readability. Here's a version I threw together:

(defn gen-primes []
  ; Quick helper predicate
  ; A number is prime if there is not some number which is a factor of the number
  (letfn [(prime? [n]
            (not (some #(zero? (rem n %))
                       (range 2 (int (inc (Math/sqrt n)))))))]

    ; Drop the first two numbers from the range (because we don't care about 0 and 1
    ; Then filter all the primes
    (filter prime? (drop 2 (range)))))

Rarely do you ever actually need to use lazy-seq explicitly. lazy-seq is the fundamental, low level building block for creating lazy sequences. Fortunately, many functions like filter already return a lazy sequence. In my function above, I'm just lazily filtering out all the non-primes from an infinite range of numbers, without ever explicitly using lazy-seq.

I realized after I posted this that this is actually a bit of an "apples and oranges" comparison. My version is a naïve brute-force approach which, while terse, is inefficient. Looking at the original code again, I'm assuming it's some kind of sieve that likely performs much better than my version.

get-digits can be greatly simplified as well if you just abuse strings here:

(defn my-get-digits [num]
  (->> num
       (str) ; Have str do most of the heavy lifting
       (map str) ; Then turn each character back into a string so they can be parsed
       (map #(Long/parseLong %))
       (into '())))

They even perform identically. I was expecting mine to be slower, but it ended up being 0.1 µs faster:

(cc/quick-bench
  (get-digits 192837465))
Evaluation count : 93972 in 6 samples of 15662 calls.
             Execution time mean : 5.665620 µs
    Execution time std-deviation : 872.894028 ns
   Execution time lower quantile : 4.709602 µs ( 2.5%)
   Execution time upper quantile : 6.504343 µs (97.5%)
                   Overhead used : 4.360719 ns
=> nil

(cc/quick-bench
  (my-get-digits 192837465))
Evaluation count : 130404 in 6 samples of 21734 calls.
             Execution time mean : 5.508682 µs
    Execution time std-deviation : 485.864725 ns
   Execution time lower quantile : 4.669716 µs ( 2.5%)
   Execution time upper quantile : 5.944096 µs (97.5%)
                   Overhead used : 4.360719 ns

Where cc is an alias for the Criterium core module; a great benchmarking library.

Again, try to reuse existing constructs unless you have a good reason to get your hands dirty, or you really want the practice (although practicing reusing existing constructs is important as well).

are-permutations-of-each-other? has a little duplication, but is simple enough that that's not a big deal. If you wanted, you could use map to reduce some of the duplication. I made a var-arg function so it can accept any number of numbers to check. It's highly unnecessary, but doing so works well with use of map anyways, and doesn't change its usage. There's two nearly identical versions to choose from, depending on whether or not you want to use functions composition via comp, or just lazily map twice:

(defn are-permutations-of-each-other? [& nums]
  (->> nums
       (map (comp sort get-digits))
       (apply =)))

(defn are-permutations-of-each-other? [& nums]
  (->> nums
       (map get-digits)
       (map sort)
       (apply =)))

This isn't a big deal, but in your main threading call that ties everything together, you have

(->> (for [i four-digit-primes
               j four-digit-primes]
           [i j])

     (remove #(apply = %))
     ...)

There's certainly nothing wrong with this. I'll just point out that an alternative is just to apply filter directly in the for:

(->> (for [i four-digit-primes
           j four-digit-primes
           :when (not= i j)] ; Here
       [i j])
     ...)

for can accept three kinds of keywords like that in its binding list. :when only adds to the list if the condition is true. It's like Python's if inside of list comprehensions.

Again in the main thread, you have:

(filter (fn [[n1 n2]]
          (let [mx (max n1 n2)
                mn (min n1 n2)
                diff (- mx mn)
                next (+ mx diff)]
            (and (< next 10000)
                 (four-digit-primes next)
                 (are-permutations-of-each-other? n1 next)))))

At some point, you need to look at your anonymous function and break it off into it's own function. Not only does that neaten up the threading calls, it names the function so it's clearer what the code is actually doing.

A little down, you have

(map #(map str %))
(map (partial apply str))

Now, it doesn't matter which you choose, but consistency is nice. In the first line, you're using #(), and in the second, you're using partial; even though both can be done using either. I prefer #() unless I'm already inside a function macro since I find partial adds a lot of noise. Which you use doesn't matter though; just try to apply the same idea everywhere and be consistent in your style.

Finally, I stuck the whole main thread call into a -main function. Having code executing on the top level like that sucks if you're developing using a REPL. Every time I tried to load the function into the REPL to reflect a change I had made, the whole thing would run, which forced me to wait a couple seconds extra. In most cases, I prefer to stick everything inside functions so stuff only runs when I want it to.

Taking all that into consideration, here's what I ended up with:

(ns irrelevant.cr2-fixed)

(defn- gen-primes []
  (let [prime? (fn [n] (not (some #(zero? (rem n %))
                                  (range 2 (int (inc (Math/sqrt n)))))))]

    ; Drop the first two numbers from the range (because we don't care about 0 and 1
    ; Then filter all the primes
    (filter prime? (drop 2 (range)))))

(defn- get-digits [num]
  (->> num
       (str) ; Have str do most of the heavy lifting
       (map str) ; Then turn each character back into a string so they can be parsed
       (map #(Long/parseLong %))
       (into '())))

(defn- are-permutations-of-each-other? [& nums]
  (->> nums
       (map get-digits)
       (map sort)
       (apply =)))

(defn -main []
  (let [four-digit-primes (->> (gen-primes)
                               (drop-while #(< % 1000))
                               (take-while #(< % 10000))
                               (apply sorted-set))

        ; Give this a better name. I have no idea what you'd want to call it.
        filter-helper (fn [[n1 n2]]
                        (let [mx (max n1 n2)
                              mn (min n1 n2)
                              diff (- mx mn)
                              next (+ mx diff)]
                          (and (< next 10000)
                               (four-digit-primes next)
                               (are-permutations-of-each-other? n1 next))))]

    (->> (for [i four-digit-primes
               j four-digit-primes
               :when (not= i j)]
           [i j])
         (filter #(apply are-permutations-of-each-other? %))
         (filter filter-helper)
         (map sort)
         (distinct)
         (map #(cons (+ (second %) (- (second %) (first %))) %))
         (map sort)
         (map #(map str %))
         (map #(apply str %))
         (second)
         (println))))

(-main)
296962999629
=> nil

Hopefully that helps you out. Your code is actually quite good for someone learning the language. Keep it up!


Database fetch class The active column in the database only contains a boolean. The country column contains ISO 3166 A2 codes (2 char). Do you have any advice on improving this class?

<?php
class WebShops {
    private $database;

    public function __construct() {
            $this->database = new Database();
    }

    public function fetchAll() {
            $this->database->query("SELECT * FROM web_shops");
            return $this->database->fetchAll();
    }

    public function fetchActive($option) {
            $this->database->query("SELECT * FROM web_shops WHERE active = :option");
            $this->database->bind(':option', $option);
            return $this->database->fetchAll();
    }

    public function fetchCountry($country) {
            $this->database->query("SELECT * FROM web_shops WHERE country = :country");
            $this->database->bind(':country', $country);
            return $this->database->fetchAll();
    }
}

You could validate $option and $country before you put them in a query. One needs to be true or false, and the other should be two letters A-Z. You need some kind of error handling for that.

For the rest: This is such a simple class, and the context is missing, what would you want us to say?


Obtaining column status definition I know exactly how I would handle this in PHP, Python, JS, and AS, but I want to confirm that this is the correct approach to Enums in Java.

I have a database view which has a status column. It will only ever have one of four values (in MySQL, I would have made it an enum type column, but the type doesn't really matter in my current context). Each directly maps to one of the values defined below.

public enum StatusDefinitions {
    NOT_STARTED("not started"),
    IN_PROGRESS("in progress"),
    COMPLETE("opted out"),
    OPTED_OUT("complete");

    private String desc;

    private StatusDefinitions(String desc)
    {
        this.desc = desc.toLowerCase();
    }

    public String getDescription()
    {
        return desc;
    }

    public static StatusDefinitions getStatus( String desc )
    {
        desc = desc.toLowerCase();
        for( StatusDefinitions it: StatusDefinitions.values() )
        {
            if( it.getDescription().equals( desc ) ) return it;
        }
        return StatusDefinitions.NOT_STARTED;
    }
}

Now, in my JSP, I loop for(StatusDefinitions it: StatusDefinitions.values()) and have selected="selected" based on if(modelObjStatus == it). When pulling this from/pushing it to the db, I have status = StatusDefinitions.getStatus( rs.getString( "status" ) );. And there is where I have this sensation that I've missed something. Looping through all of the Strings and comparing them seems like I lose the benefit of the Enum. It would almost seem better to have a series of public static final Strings.

(Before anyone asks, because of the scope of this particular project, it doesn't make sense to make this an ORM.)

To start with, this is not good:

COMPLETE("opted out"),
OPTED_OUT("complete");

Otherwise, this is pretty standard code. There are two things I'd note:

If desc is coming from the database, you may have a risk of NullPointerException if it comes as null once.
Instead of looping and searching, you can create a map from description to value once and use it each time. Since your set of values is so small, performance difference is probably minimal, so this is question of taste.


Pickling cars with simple management system in Python This is my first Python program (before that I've been just poking around with the interpreter itself). I took this opportunity to do some user input and play around with pickle.

I tried to made a system that reads input from the user (a car's name, year of launch and price), and then gives the power of exporting or importing it to an external file.

Is there any way to make this looks better (something that bothered me was my printing function and my super simple regex)? Is there any way that I can make this more pythonic? I've read many articles with this "pythonic" idea, and as I'm moving from Java, I'm afraid I might be losing something.

Made with python 3 in mind.

Example of input is:

  add

  Mitsubishi Eclipse

  1999

  1300.00

Here is the code.

import re
import pickle

class Car():
    def __init__(self, carName = None, year = None, cost = None):
        self.carName = carName if carName is not None else "undefined"
        self.year = year if year is not None else "undefined"
        self.cost = cost if cost is not None else "undefined"

cars = []
canImport = True #can only import if has already exported before or at program start

def addNewCar():
    """ Reads input from user and adds a new car to the current collection of cars.
        Year/Cost numeric validation are deliberately ommited """

    usr_input = input("Enter the car's name : (protip: if can enter the whole object by typing name/year/cost)\n-> ")
    match = re.search(r"\w+/\w+/\w+", usr_input)
    if match:
        name, year, cost = splitCarAttributes(match)
    else:
        name = usr_input
        year, cost = getCarAttributes()
    cars.append(Car(name, year, cost))

def splitCarAttributes(attributes):
    return attributes.group(0).split("/")

def getCarAttributes():
    year = input("Enter the car's launching year:\n-> ")
    cost = input("Enter the car's cost:\n-> ")
    return year, cost

def printCars():
    for i, car in enumerate(cars):
        print("Car #{:d}\n{{\n\tname:{:s}\n\tyear:{:s}\n\tcost:{:s}\n}}\n---\n".format(i+1, car.carName, car.year, car.cost))

def importCars():
    if not canImport
        print("You don't have anything to import.\n\n")
        return

    fileObject = open('cars', 'rb')
    importedCars = pickle.load(fileObject)
    for car in importedCars:
        cars.append(car)
    canImport = False
    printSuccess()

def exportCars():
    fileObject = open('cars', 'wb')
    pickle.dump(cars, fileObject)
    cars = [] # clears cars
    canImport = True
    printSuccess()

def printSuccess():
    print("\n\n--- Great success!\n\n")

def main():
    opt = ""
    while (opt != "exit" and opt != "q"):
        opt = input("Would you like to:\n- import all data\n- export all data\n- print all cars\n- add a new car to the collection?\n-> ").lower()
        if opt == "import":
            importCars()
        elif opt == "export":
            exportCars()
        elif opt == "add":
            addNewCar()
            printSuccess()
        elif opt == "print":
            printCars()

if __name__ == '__main__':
    main()

Edit: I just realized I'm calling printSuccess() in different contexts. Not gonna change the code now, just a heads up to clarify that I should move all to main() and maybe do some exception handling, but that's no the point right now.

def printCars():
    for i, car in enumerate(cars):
        print("Car #{:d}\n{{\n\tname:{:s}\n\tyear:{:s}\n\tcost:{:s}\n}}\n---\n".format(i+1, car.carName, car.year, car.cost))

cars is a global variable: that should be avoided.

Use dictionaries

    if opt == "import":
        importCars()
    elif opt == "export":
        exportCars()
    elif opt == "add":
        addNewCar()
        printSuccess()
    elif opt == "print":
        printCars()

should be a dictionary.

Also I feel like all your methods should be inside the car class as they are logically connected to it.


Determine if two strings with no repeating characters are permutations of each other I've made a short program to determine if a string is permutation of another string.
Example input/output :

a) 123, 112 <- False
b) 123, 321 <- True
c) 112, 121 <- these don't count as permutations since they have duplicate characters

    private static void Main()
    {
        string a = Console.ReadLine();
        string b = Console.ReadLine();
        Console.WriteLine(IsPermutation(a, b));
        Console.ReadKey();
    }

    private static bool IsPermutation(string first, string second)
    {
        if (first.Length != second.Length)
        {
            return false;
        }
        for (int i = 0; i < first.Length; i++)
        {
            if (first.Count(t => t == second[i]) != second.Count(t => t == first[i]))
            {
                return false;
            }
        }
        return true;
    }

I wonder if it can be optimized.

You could use the SetEqual<T> helper method from this answer.
It uses a dictionary as follows:

The dictionary is filled with the items of the first collection and with their number of occurences.
Number of occurences is decreased for each item in the second collection.

Thus your method can be rewritten as:

private static bool IsPermutation(string first, string second)
{
    if (first.Length != second.Length)
    {
        return false;
    }
    return SetEqual(first, second);
}

If you are sure that strings contain only unique chars, there is a more efficient approach using the HashSet<T>:

private static bool IsPermutation(string first, string second)
{
    if (first.Length != second.Length)
    {
        return false;
    }
    HashSet<char> chars = new HashSet<char>(first);
    return second.All(chars.Contains);
}


Image download handler app I have a paid app on the app engine. At the moment, usually there is only one instance. The app has a download handler that sends an image after re-sizing it if it is too big. The problem is: if a web page contains many big images (60 or more) the app engine creates another instance. I'm trying to keep the app as cheap as possible and creating too many instances is probably not good for that.

Is there a way to improve this code? Or my concerns are just unfounded?

The application settings are:

automatic_scaling:
  min_idle_instances: 1
  max_pending_latency: 10s

The code:

class ServeHandler(blobstore_handlers.BlobstoreDownloadHandler):
  def get(self, resource):
    resource = str(urllib.unquote(resource))
    blob_info = blobstore.BlobInfo.get(resource)
    if not blob_info:
        pass
    else:
        data = blobstore.fetch_data(blob_info.key(), 0, 50000)
        img0 = images.Image(image_data=data)
        img = images.Image(blob_key=blob_info.key())
        if img0.width >= 800:
            img.resize(width=800)
            img = img.execute_transforms(output_encoding=images.JPEG)
            self.response.headers['Content-Type'] = 'image/jpeg'
            self.response.out.write(img)
        else:
            self.send_blob(blob_info)

PEP0008 says use 4 spaces for indentation, it's much clearer where one block starts and another ends that way.

This may be a placeholder but I'll assume your code posted here is real code and say that you should just use if blob_info and remove the pointless pass and else.

if not blob_info:
    pass
else:

I also think you could reformat for better whitespace to make your code more readable. You currently use none and that gives a wall of text effect. This looks nicer:

class ServeHandler(blobstore_handlers.BlobstoreDownloadHandler):

    def get(self, resource):
        resource = str(urllib.unquote(resource))
        blob_info = blobstore.BlobInfo.get(resource)

        if blob_info:
            data = blobstore.fetch_data(blob_info.key(), 0, 50000)
            img0 = images.Image(image_data=data)
            img = images.Image(blob_key=blob_info.key())

            if img0.width >= 800:
                img.resize(width=800)
                img = img.execute_transforms(output_encoding=images.JPEG)
                self.response.headers['Content-Type'] = 'image/jpeg'
                self.response.out.write(img)
            else:
                self.send_blob(blob_info)

You should also add a docstring to your class at least. I can't suggest one given my limited knowledge of your script but they're always helpful for a class.


Scraping urls asynchronous including exception handling I'm trying to understand how to work with aiohttp and asyncio. The code below retrieves all websites in urls and prints out the "size" of each response.

Is the error handling within the fetch method correct?
Is it possible to remove the result of a specific url from results in case of an exception - making return (url, '') unnecessary?
Is there a better way than ssl=False to deal with a potential ssl.SSLCertVerificationError?
Any additional advice on how i can improve my code quality is highly appreciated

import asyncio
import aiohttp

async def fetch(session, url):
    try:
        async with session.get(url, ssl=False) as response:
            return url, await response.text()
    except aiohttp.client_exceptions.ClientConnectorError as e:
        print(e)
        return (url, '')

async def main():
    tasks = []
    urls = [
        'http://www.python.org',
        'http://www.jython.org',
        'http://www.pypy.org'
    ]
    async with aiohttp.ClientSession() as session:
        while urls:
            tasks.append(fetch(session, urls.pop()))

        results = await asyncio.gather(*tasks)
        [print(f'{url}: {len(result)}') for url, result in results]

if __name__ == '__main__':
    loop = asyncio.get_event_loop()
    loop.run_until_complete(main())
    loop.close()

Update

Is there a way how i can add tasks to the list from within the "loop"? e.g. add new urls while scraping a website and finding new subdomains to scrape.

tasks = []
while urls:
    tasks.append(fetch(session, urls.pop()))

can be largely simplified to

tasks = [fetch(session, url) for url in urls]

  Is it possible to remove the result of a specific url from results in case of an exception - making return (url, '') unnecessary?

Yes, somewhat. asyncio.gather accept a return_exceptions parameters. Set it to True to avoid a single exception failing the gather call. You must filter them out afterwards anyway:

import asyncio
import aiohttp

async def fetch(session, url):
    async with session.get(url, ssl=False) as response:
        return await response.text()

async def main():
    urls = [
        'http://www.python.org',
        'http://www.jython.org',
        'http://www.pypy.org'
    ]
    async with aiohttp.ClientSession() as session:
        tasks = [fetch(session, url) for url in urls]
        results = await asyncio.gather(*tasks)

    for url, result in zip(urls, results):
        if not isinstance(result, Exception):
            print(f'{url}: {len(result)}')
        else:
            print(f'{url} FAILED')

if __name__ == '__main__':
    loop = asyncio.get_event_loop()
    loop.run_until_complete(main())
    loop.close()


Unbalanced Binary Search Tree insertion and search with random and sorted values I have created this unbalanced binary search tree in C. Can anyone say this is a true approach or not? I have two scenarios for insertion and search: in the first scenario I am inserting 10000 random values to tree, and in the second scenario I am inserting 10000 sorted values from 1 to 10000.

Am I on the right track?

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

struct BSTNode {
    int data;
    struct BSTNode *BSTLeft;
    struct BSTNode *BSTRight;
};

typedef struct BSTNode node;

node *rootNode= NULL;

void BSTInsert(int i, node **n) {
    if (*n == NULL) {
        (*n) = (node*)malloc(sizeof(node));
        (*n)->BSTLeft = NULL;
        (*n)->BSTRight = NULL;
        (*n)->data = i;
    }
    else if (i > (*n)->data)
        BSTInsert(i, &((*n)->BSTRight));
    else
        BSTInsert(i, &((*n)->BSTLeft));
}

void BSTSearch(int i, node **n) {
    if (*n == NULL)
        printf("\nValue does not exist in tree!");
    else if((*n)->data == i)
       return ;
    else if(i > (*n)->data)
        BSTSearch(i, &((*n)->BSTRight));
    else
        BSTSearch(i, &((*n)->BSTLeft));
}

void test_scenario1() {
    node *rootNode = NULL;
    const int SIZE = 10000;
    int *a = malloc(sizeof (int)*SIZE);
    clock_t start, end;
    for (int i = 1; i < SIZE; i++)
    {
        srand(time(NULL));
        a[i] = rand() % 1000;
    }
    printf("Inserting values to BST with %d random nodes...\n", SIZE);
    start = clock();
    for (int i = 0; i < SIZE; i++) {
    BSTInsert(a[i], &rootNode);
    }
    end = clock();
    printf("Done. Took %.8f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);

// Search in BST with random Values

    printf("Searching random values in BST...");
    start = clock();
    for (int i = 0; i < SIZE; i++) {
    BSTSearch(a[i], &rootNode);
    }
    end = clock();
    printf("\nDone. Took %.8f seconds\n", (double) (end - start) / CLOCKS_PER_SEC);
    free(a);
}

void test_scenario2(){
    node *rootNode = NULL;
    const int SIZE = 10000;
    clock_t start, end;
    int num;
    printf("\nInserting values to BST with %d sorted nodes...\n", SIZE);
    start = clock();
    for (num=1;num<=10000;num++){
    BSTInsert(num, &rootNode);
    }
    end = clock();
    printf("Done. Took %.8f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);

// Search in BST with sorted Values

    printf("Searching sorted values in BST...");
    start = clock();
    for (num=1;num<=10000;num++)
    BSTSearch(num, &rootNode);
    end = clock();
    printf("\nDone. Took %.8f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);
}
// Main function for these three scenarios.
int main(int argc, char ** argv)
{
    test_scenario1();
    test_scenario2();
}

The global variable rootNode is never used, and is confusing due to similar local variables, so remove it.

As we're ignoring all command-line arguments, we can use the simpler signature for main():

int main(void)

Prefer to use unsigned types for counting:

const unsigned int SIZE = 10000;
...
for (unsigned int i = 1;  i < SIZE;  ++i)

That addresses most of the compiler warnings I get for this code.  The remaining warning is best eliminated with a cast to indicate that we don't care about preserving the correct value in this signed → unsigned conversion:

    srand((unsigned)time(NULL));

Prefer to use the size of the variable than of its type when allocating memory.  This makes it easier for reviewers to confirm that the sizes match:

if (!*n) {
    *n = malloc(sizeof **n);
    (*n)->BSTLeft = NULL;
    (*n)->BSTRight = NULL;
    (*n)->data = i;
}

and

int *a = malloc(sizeof *a * SIZE);

Use a memory checker; at the moment, we leak the entire BST:

Inserting values to BST with 10000 random nodes...
==12434== Conditional jump or move depends on uninitialised value(s)
==12434==    at 0x1091FC: BSTInsert (209085.c:24)
==12434==    by 0x109388: test_scenario1 (209085.c:54)
==12434==    by 0x10956F: main (209085.c:96)
==12434==
Done. Took 3.30890200 seconds

==12434== Conditional jump or move depends on uninitialised value(s)
==12434==    at 0x10926D: BSTSearch (209085.c:33)
==12434==    by 0x10940C: test_scenario1 (209085.c:64)
==12434==    by 0x10956F: main (209085.c:96)
==12434==
==12434== Conditional jump or move depends on uninitialised value(s)
==12434==    at 0x10927B: BSTSearch (209085.c:35)
==12434==    by 0x10940C: test_scenario1 (209085.c:64)
==12434==    by 0x10956F: main (209085.c:96)
==12434==
Searching random values in BST...
Done. Took 0.00558500 seconds

Inserting values to BST with 10000 sorted nodes...
Done. Took 3.36596000 seconds

Searching sorted values in BST...
Done. Took 3.96642300 seconds

==12434== 240,000 (24 direct, 239,976 indirect) bytes in 1 blocks are definitely lost in loss record 22 of 23
==12434==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==12434==    by 0x1091B9: BSTInsert (209085.c:19)
==12434==    by 0x109388: test_scenario1 (209085.c:54)
==12434==    by 0x10956F: main (209085.c:96)
==12434==
==12434== 240,000 (24 direct, 239,976 indirect) bytes in 1 blocks are definitely lost in loss record 23 of 23
==12434==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==12434==    by 0x1091B9: BSTInsert (209085.c:19)
==12434==    by 0x1094AA: test_scenario2 (209085.c:79)
==12434==    by 0x109579: main (209085.c:97)
==12434==

Those early reports of using uninitialised values are certainly worth investigating, too.

Try to be consistent where that helps readers.  Consider this fragment:

else if((*n)->data == i)
   return ;
else if(i > (*n)->data)

See how it's easier to see the relation between the two tests if we write the operands in the same order:

else if (i == (*n)->data)
   return;
else if (i > (*n)->data)

Use the standard error stream for error messages:

if (*n == NULL)
    fprintf(stderr, "Value does not exist in tree!\n");

And prefer to write complete lines to output (especially relevant when it's connected to line-buffered devices, such as terminals and terminal-emulators).

Consider using more braces to enclose conditional commands.  It's easier to avoid silly mistakes:

if (*n == NULL) {
    *n = malloc(sizeof **n);
    (*n)->BSTLeft = NULL;
    (*n)->BSTRight = NULL;
    (*n)->data = i;
} else if (i > (*n)->data) {
    BSTInsert(i, &((*n)->BSTRight));
} else {
    BSTInsert(i, &((*n)->BSTLeft));
}

We could make that code a lot clearer by copying *n into a local variable:

void BSTInsert(int i, node **n)
{
    node *node = *n;
    if (!node) {
        *n = node = malloc(sizeof **n);
        node->BSTLeft = NULL;
        node->BSTRight = NULL;
        node->data = i;
    } else if (i > node->data) {
        BSTInsert(i, &node->BSTRight);
    } else {
        BSTInsert(i, &node->BSTLeft);
    }
}

On the other hand, in the search function, we don't need to pass by pointer, and we can use const.  We probably ought to return something, too:

const int *BSTSearch(int i, const node *n) {
    if (n == NULL) {
        fprintf(stderr, "Value does not exist in tree!\n");
        return NULL;
    } else if (i == n->data) {
       return &n->data;
    } else if (i > n->data) {
        return BSTSearch(i, n->BSTRight);
    } else {
        return BSTSearch(i, n->BSTLeft);
    }
}

Obviously, the call sites would then need to pass rootNode by value, rather than &rootNode pointer.

The parallel structure of insert and search suggests that we're missing a condition for (i == n->data) in the insert; in that block, we should avoid inserting a duplicate node and instead return early:

void BSTInsert(int i, node **n)
{
    node *node = *n;
    if (!node) {
        *n = node = malloc(sizeof **n);
        node->BSTLeft = NULL;
        node->BSTRight = NULL;
        node->data = i;
    } else if (i == node->data) {
        return;                 /* already exists */
    } else if (i > node->data) {
        BSTInsert(i, &node->BSTRight);
    } else {
        BSTInsert(i, &node->BSTLeft);
    }
}

(It might be this change that eliminated the Valgrind warning about uninitialised data - I'm not sure when that disappeared).

We're missing the check that malloc() didn't return a null pointer.  That can happen any time we call an allocation function, so we must always test the result before using it.  In particular, there's no guarantee that the subsequent use of a null pointer will crash the program, as some authors seem to think.

bool BSTInsert(int i, node **n)
{
    node *node = *n;
    if (!node) {
        *n = node = malloc(sizeof **n);
        if (!node) return false;
        node->BSTLeft = NULL;
        node->BSTRight = NULL;
        node->data = i;
        return true;
    } else if (i == node->data) {
        return true;            /* already exists */
    } else if (i > node->data) {
        return BSTInsert(i, &node->BSTRight);
    } else {
        return BSTInsert(i, &node->BSTLeft);
    }
}

Don't forget that this means that the callers of BSTInsert now need to check that it succeeded!

Lastly (and leastly), this comment is inaccurate:

// Main function for these three scenarios.

Either change the word "three" to "two" or remove the comment (it's stating the obvious, so doesn't add any value).


Better Database Connection Function I'm about a week into learning pdo.  I've created, with help from an example online, a database connection function.  I have a config file with all my info (username, pass, database, host) and a function inside a file called db.php.  Everything works great with the function below.

Though, I have to put dataConnect() on the top of every page that uses $dbo.  Since the function is included in my db.php file, I was hoping that the file was the only thing I needed to include on the page:  not both the db.php and dataConnect().

I've been searching online for a better way to do this function but most of the db examples are single use examples.

Also, having the variables from the config file as global in the function... I'm assuming is a bad thing.  I'm hoping someone can help or let me know that this is a good function.

require('config.php');

function dataConnect() {
try {
    global $dbo;
    global $dbname;
    global $dbuser;
    global $dbpass;

    $info['dbhost_name'] = $dbserver;
    $info['database'] = $dbname;
    $info['username'] = $dbuser;
    $info['password'] = $dbpass;

    $dbConnString = "mysql:host=" . $info['dbhost_name'] . "; dbname=" . $info['database'];

    $dbo = new PDO($dbConnString, $info['username'], $info['password'], array(PDO::ATTR_PERSISTENT => true));
    $dbo->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_SILENT);
    $dbo->exec("SET CHARACTER SET utf8");
    }
    catch(PDOException $e) {
        header("Location:$basehttp/error");
    exit();
    }
}

Thanks for your help!

Globals are indeed a bad thing. They are old and full of security issues as well as being nearly impossible to debug. Stay away from them at all costs. Instead, pass those variables as a parameter into any function that needs them and have the function return any modifications if necessary. Once you start learning OOP then you can use class properties in place of globals, but parameter injection is the only solution for procedural programming. Well, you could also use constants, but you don't want to go flashing your password into the global scope that way. At least, I'm pretty sure that is a bad idea. It sounds bad... My experience with security and SQL databases is a bit limited, so you might want clarification here. Database names and non-sensitive information should make fine constants though.

Speaking of constants, typically that is what config files are for. For storing site constants so that they can be reused. You define() a constant by giving it a name, conventionally in caps separated by underscores, and a value and use it almost the same way as a variable, except without the $. For example:

define( 'DB_NAME', 'name' );
//implementation
$info[ 'database' ] = DB_NAME;

Another problem here is that you are not using those globals even though you went to all the trouble of making them. Instead, you immediately wrap them into an associative array. This seems kind of redundant. What's wrong with using the variables as they are? You don't appear to be using that $info array anywhere else and besides adding clutter, you are just making your code harder to read by using longer instances of the same data.

Finally, in regards to your problem, you could use your .htaccess file to advantage, but this really depends on the situation. I would not use this for database connections as it would enforce that connnection on EVERY page, which does not seem necessary. It would be helpful in including the config file in every page though, which is why I mention it.

php_value auto_prepend_file "config.php"

As I said, I would not recommend the above for database connections. If you have a number of pages that require a database connection, I would use a "template" to create this connection, then use specific "views" to do certain tasks. This way you only have to write the code once and you can dynamically change which action is performed. For instance, here is an extremely basic, barebone example. Please don't just copy-paste this, its for demonstration purposes only. Extrapolate from it.

Template

<?php
//create db connection
$db;//db should be available in local scope
include $_GET[ 'view' ] . '.php';
?>

Sample View

<?php
$db->stuff();//do some stuff with db
//print results
?>

The template is the page you would call, but a GET parameter would define what action to perform by loading another page with the database specific actions to take. Whatever variables are in the local scope in the template will also be available in the local scope on the view. Which is why we are able to use the $db as if it were a global. Though this is typically frowned upon because, just like globals, it is hard to figure out where those variables are coming from without the proper context. Again, this is just to give you an idea.


Producer-Consumer in C++ - follow-up To expand from the changes supplied by the answer of my previous question:

#include <condition_variable>
#include <iostream>
#include <random>
#include <mutex>
#include <thread>
#include <vector>

// global variables
std::condition_variable cv;
std::mutex mtx;
std::vector<char> data;

int count = 0, buff_size = 0;

char random_char() {
    thread_local std::random_device seed;
    thread_local std::mt19937 generator(seed());
    thread_local std::uniform_int_distribution<int> dist('A', 'Z');

    return static_cast<char>(dist(generator));
}

/* Consumer

Prints out the contents of the shared buffer.

*/
void consume() {
    std::unique_lock<std::mutex> lck(mtx);

    while (count == 0) {
        cv.wait(lck);
    }

    for (const auto& it : data) {
        std::cout << it << std::endl;
    }

    count--;
}

/* Producer

Randomly generates capital letters in the range of A to Z,
prints out those letters in lowercase, and then
inserts them into the shared buffer.

*/
void produce() {
    std::unique_lock<std::mutex> lck(mtx);

    char c = random_char();
    std::cout << " " << static_cast<char>(tolower(c)) << std::endl;
    data.push_back(c);

    count++;
    cv.notify_one();
}

int main() {
    std::cout << "The Producer-Consumer Problem (in C++11!)" << std::endl << "Enter the buffer size: ";
    std::cin >> buff_size;

    // keep the buffer in-range of the alphabet
    if (buff_size < 0) {
        buff_size = 0;
    }
    else if (buff_size > 26) {
        buff_size = 26;
    }

    std::thread production[26], processed[26];

    // initialize the arrays
    for (int order = 0; order < buff_size; order++) {
        production[order] = std::thread(produce);
        processed[order] = std::thread(consume);
    }

    // join the threads to the main threads
    for (int order = 0; order < buff_size; order++) {
        processed[order].join();
        production[order].join();
    }

    std::cout << "Succeeded with a shared buffer of " << data.size() << " letters!";
}

Global variables in the best of cases are questionable, but in this case especially you have buff_size as a global variable. buff_size is only used in main() so should be a local variable there.

You can also take advantage of the fact that std::condition_variable::wait() has another overload that takes a predicate to replace:

while (count == 0) {
    cv.wait(lck);
}

with:

cv.wait(lck, []{ return count > 0; });

Although, did you really want every consumer to print out every letter every time? If buff_size were 10, you'd end up logging 55 letters. Was that intentional? If it wasn't, you could drop count entirely, switch data to be a std::queue and have your consumer be:

std::unique_lock<std::mutex> lck(mtx);
cv.wait(lck, []{return !data.empty(); });
std::cout << data.front() << std::endl;
data.pop();

On the producer front, did you really mean notify_one() and not notify_all()? Let all the consumers fight for the lock!

Lastly, this:

if (buff_size < 0) {
    buff_size = 0;
}
else if (buff_size > 26) {
    buff_size = 26;
}

is a clamp. It might be worth writing something like:

template <typename T>
T clamp(T const& val, T const& lo, T const& hi)
{
    return std::min(std::max(val, lo), hi);
}

buff_size = clamp(buff_size, 0, 26);


OOP in Rock, Paper, Scissors program This is an OOP Rock, Paper, Scissors program I wrote in Python.  I am just learning about using classes and I'd appreciate some advice on improving it.

# rock.py
# example of OOP
import random

class Rock:
    def main(self):
        self.Make_players()
        print("Best of Five - Let's play!\n")
        done  = False
        while done == False:
            self.p1.go_player()
            self.p2.go_player()
            print()
            if self.p2.go == self.p1.go:
                print("No winner!\n")
                continue
            else:
                temp = self.check(self.p1, self.p2)
            if temp == False:
                temp = self.check(self.p2, self.p1)
            print(self.message, end = " ")
            print(temp.name + " won this round.")
            temp.scored()
            print(self.p1.name + ": " + str(self.p1.score))
            print(self.p2.name + ": " + str(self.p2.score))
            if self.p1.score == 3:
                self.winner = self.p1
                done = True
            elif self.p2.score == 3:
                self.winner = self.p2
                done = True
            else:
                done = False
                input()
        print("The winner was " + self.winner.name + "!")

def __init__(self):
    print("**** Welcome to Rock, Paper, Scissors!****\n")
    self.winner = False
    self.main()

def Make_players(self):
    temp = (input("What shall we call Player 1? "))
    self.p1 = Player(temp)
    temp = (input("What shall we call Player 2? "))
    self.p2 = Player(temp)

def check(self, p_a, p_b):
    if p_a.go == "rock" and p_b.go == "scissors":
        self.message = "Rock breaks scissors."
        return p_a
    elif p_a.go == "paper" and p_b.go == "rock":
        self.message = "Paper wraps stone."
        return p_a
    elif p_a.go == "scissors" and p_b.go == "paper":
        self.message = "Scissors cut paper."
        return p_a
    else:
        return False

class Player:
    def __init__(self, name):
        self.choices = ["rock", "paper", "scissors"]
        self.score = 0
        self.name = name
        print("Player:", self.name, "created!\n")

    def go_player(self):
        self.go = random.choice(self.choices)
        print(self.name + " chose " + self.go, end = ". ")
        return self.go

    def scored(self):
        self.score += 1

# Main
game = Rock()

The best OOP advice I can give for this code is: stop writing classes.

Ideally, watch the video first (it’s not that long) and come back later. But here’s the gist:

  A class that has only one publicly called method (or less) isn’t a legitimate class. It should be a method.

Consequently, Rock shouldn’t be a class. It should be a method.

The rest is detail criticism. Most importantly, read PEP8 (the Python style guide) and adhere to it. Notably, this includes naming conventions, and using meaningful names.

Next, separate concerns clearly. go_player shouldn’t print text, its sole task should be to generate a random game choice. The printing should happen elsewhere.

Similarly (i.e. still a separation-of-concerns problem), neither all possible choices (i.e. choices) nor the current choice (i.e. go) logically belong in the Player. They are separate entities.

self.winner = False is logically wrong. The variable doesn’t contain a boolean value later on, why does it contain one now? Same goes for check – it should return None, not False.

Next, use a standard entry point. The following is pretty much an established pattern in Python that all code should follow:

def main():
    …

if __name__ == '__main__':
    sys.exit(main())

This way, the code can be executed directly or reused as a module.

And a check like while done == False is like fingernails across a blackboard for professional programmers: explicit checks against boolean literals never (!) make sense. Use while not done instead.

In summary, here’s how I’d do it:

#!/usr/bin/env python

import sys
import random

# The extended, cool rules:
# http://en.wikipedia.org/wiki/Rock-paper-scissors-lizard-Spock
CHOICES = ['rock', 'paper', 'scissors', 'lizard', 'Spock']

RULES = {
    'rock': {
        'scissors': 'blunts',
        'lizard': 'crushes'},
    'paper': {
        'rock': 'covers',
        'Spock': 'disproves'},
    'scissors': {
        'paper': 'cuts',
        'lizard': 'decapitates'},
    'lizard': {
        'paper': 'eats',
        'Spock': 'poisons'},
    'Spock': {
        'rock': 'vaporizes',
        'scissors': 'smashes'}
}

class Player:
    def __init__(self, name):
        self.name = name
        self.score = 0

    @classmethod
    def create(cls, num):
        name = raw_input('What shall we call player {}? '.format(num))
        return cls(name)

    def go(self):
        return random.choice(CHOICES)

    def scored(self):
        self.score += 1

    def __str__(self):
        return self.name

def get_winner(players, choices):
    """
    Determine winner of a rock-paper-scissors round.

    Returns a tuple of (winner, winning move) if exists, else None.
    """
    def get_rule(cs):
        return RULES[cs[0]].get(cs[1], None)

    move = get_rule(choices)

    if move is not None:
        winner = players[0]
    else:
        choices = choices[::-1]
        move = get_rule(choices)
        winner = players[1]

    if move is None:
        return None

    return (winner, (choices[0], move, choices[1]))

def game(how_many_rounds):
    if how_many_rounds % 2 == 0:
        raise RuntimeError('Rounds must be an uneven number')

    players = [Player.create(1), Player.create(2)]
    winning_score = how_many_rounds // 2 + 1

    print('Best of {} - let\'s play!\n'.format(how_many_rounds))

    while True:
        choices = [p.go() for p in players]
        for p, c in zip(players, choices):
            print p, c
        win = get_winner(players, choices)

        if win is None:
            print('No winner.\n')
            continue

        winner, move = win
        winner.scored()
        print('{} {} {}. {} won this round.'.format(
                move[0].capitalize(), move[1], move[2], winner))
        for p in players:
            print('{}: {}'.format(p, p.score))

        if winner.score == winning_score:
            break

        raw_input()

    print('The winner was {}!'.format(winner))

def main():
    game(99)

if __name__ == '__main__':
    sys.exit(main())

To be honest, I’m not entirely satisfied with this since I prefer having immutable objects as much as possible, and the player objects here are not immutable. In fact, I’d probably get rid of the Players entirely and store the game state inside the game, where it belongs.

(Proper documentation is left as an exercise for the reader. I’ve only documented get_winner since it would be incomprehensible without documentation.)


Fibonacci sequence output Here's the code I'm having trouble shortening. I am currently a beginner in Python 3.x.
from os import system

def fibonacci(terms):
    count = 0
    x = 0
    y = 1
    z = x + y
    if terms <= 0:
        print("Enter a positive integer.")
    elif terms == 1:
        print("Fibonacci sequence in " + str(terms) + " terms.")
        print(x)
    else:
        print("Printing " + str(terms) + " terms.")
        while count < terms:
            print(x)
            z = x + y
            x = y
            y = z
            count += 1

while True:
    user_input = int(input("How many terms? "))
    fibonacci(user_input)
    loop = input("Again? (Y/n) ")
    if loop == "Y" or loop == "":
        system("cls")
    else:
        exit()

I would appreciate if there will be someone who will be able to make this as efficient as possible.

Separate responsibilities
Your functions should, where possible, limit themselves to doing one thing only. This is the  single-responsibility principle. In case of fibonacci(), I expect this function to just calculate the desired Fibonacci number, and not deal with user input and output. This shortens the function and makes it easier to reason about. So:
def fibonacci(terms):
    count = 0
    x = 0
    y = 1
    z = x + y

    while count < terms:
        yield x
        z = x + y
        x = y
        y = z
        count += 1

Instead of printing the values, it yields them. To print the values, use the following:
terms = int(input("How many terms? "))
for number in fibonacci(terms):
    print(number)

You can even go futher and make fibonacci() an infinite generator, and leave it up to the caller to decide when to stop:
import itertools

def fibonacci():
    x = 0
    y = 1

    while True:
        yield x
        z = x + y
        x = y
        y = z

terms = int(input("How many terms? "))
for number in itertools.islice(fibonacci(), terms):
    print(number)

Here I used itertools.islice() to take only the first terms items from the generator.
If you want to handle invalid input gracefully, I suggest you write another function whose responsibility is asking the user for a postivive integer:
def get_positive_integer(prompt):
    while True:
        user_input = int(input(prompt))
        if ...:
            return user_input
        print("Enter a positive integer.")

Avoid using os.system()
Using os.system() to clear the screen is very inefficient and not portable. Of course it is prettier to clear the screen, but if it is not really important for your program, I would just not do it; portability is more important.


How can we optimizing Java BigInteger operations? Problem
Reduce the number to 1 in a minimal number of steps, following the rules:

If the number is even, divide it by 2.
Otherwise, increment or decrement it by 1.

Limit: s can be up to 309 digits long.
Solution
public static int solution(String s) {
    BigInteger n = new BigInteger(s);
    BigInteger one = BigInteger.ONE;
    BigInteger two = BigInteger.TWO;
    BigInteger four = new BigInteger("4");
    int count = 0;

    while (n.compareTo(one) == 1) {
        count++;

        if( n.and(one).intValue() == 0 )
            n = n.divide(two);
        else if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
            n = n.subtract(one);
        else
            n = n.add(one);
    }

    return count;
}

Is there a better way to do things binary-operations-wise for this problem?
At the moment the choice I am making among these functions:

use n.byteValue() to compare with the integer,
or use function n.equals().

What more can we improve?

Follow-up question posted here

Division of the big integers is a very expensive operation. Even a division by 2 is linear in terms of its length: all bits must be shifted. The overall complexity is \$O(n \log{n})\$.
A natural desire is to not do arithmetics at all, but simulate it. Convert the bigint to byte array, and inspect bits, pretending that you perform arithmetics. In broad strokes, run the loop (starting with cursor = 0) until the number is exhausted:
if bit(cursor) == 0
    // simulate division
    increment counter
    advance cursor
else
    peek next_bit
    if next_bit == 0
        // simulate subtraction
        increment counter by 2
        advance cursor by 2
    else
        // simulate addition
        while next_bit == 1
            increment counter
            advance cursor
            peek next_bit
        advance cursor
        set bit at cursor to 1

This touches each bit just once, driving the complexity down to \$O(n)\$. Care must be taken to correctly terminate the loop.


Compare performance of simple addition on one to many cores I read recently that ENIAC originally was capable of 5000 additions per second.  Naturally, I had to test my own laptop's capabilities and this became an instructive experiment in F#, which I suck at.

So, I am looking for feedback in two areas:

What is the most concise way to write this in F#, or at least most closely aligned with the functional paradigm?
Did I miss something for performance? Can this be done in a much more performant fashion?

module Program

open System
open System.Diagnostics

[<AutoOpen>]
module timingStuff =
    let pickRunmode() =
        Console.WriteLine("choose number of processes to spawn (default 1)")
        Console.ReadLine()

    let feedback (input : string) =
        Console.WriteLine("you picked {0}", input)
        Console.WriteLine("now running")

    let quitOrContinue() =
        Console.WriteLine("q to quit else continue with keypress")
        Console.ReadKey().KeyChar <> 'q'

    let rec addOne x stop =
        let r = x + 1
        if stop() then r
        else addOne r stop

    let finished stopticks = (fun _ -> Stopwatch.GetTimestamp() >= stopticks)
    let secondsToTicks x = x * 1000L * 10000L
    let prettyNumbers (x : int) = String.Format("{0:#,0}", x)

    let printResult result start =
        let final = (Stopwatch.GetTimestamp() - start |> TimeSpan).TotalSeconds
        let pretty = prettyNumbers result
        sprintf "performed %s operations in %f seconds" pretty final |> Console.WriteLine

    let op duration start =
        duration
        |> secondsToTicks
        |> (+) start
        |> finished
        |> addOne 0

    let opAsync duration start procs =
        [ for i in [ 1..procs ] -> async { return op duration start } ]
        |> Async.Parallel
        |> Async.RunSynchronously

[<EntryPoint>]
let main argv =
    let loop() =
        let input =
            match Int32.TryParse(pickRunmode()) with
            | true, i -> i
            | _ -> 1
        input
        |> string
        |> feedback
        |> ignore
        let start = Stopwatch.GetTimestamp()
        let result = opAsync 1L start input |> Seq.sum
        printResult result start |> ignore
        quitOrContinue()
    while loop() do
        ()
    0

So for my skill level there are some minor recommendations.
So for me Feedback would be a little bit more readable in this form:

let feedback input =
    [   sprintf "you picked %s" input
        "now running" ] |> List.iter Console.WriteLine

There are some brackets that can be reduced, so simple write.

Console.WriteLine "q to quit else continue with keypress"

And finally there is no need to ignore unit, since ignore is a code smell and you actually don not need them so just ignore them.

And that is what I changed it to:

module Program

open System
open System.Diagnostics

[<AutoOpen>]
module timingStuff =
    // no side effects
    let secondsToTicks = (*) (1000L * 10000L)

    let prettyNumbers (x:int) = String.Format("{0:#,0}", x)

    // no side effects if stop has side effect (but here it has)
    let rec addOne x stop =
        let r = x + 1
        if stop() then r
        else addOne r stop

    // with side effects
    let pickRunmode() =
        "choose number of processes to spawn (default 1)" |> Console.WriteLine
        Console.ReadLine()

    let feedback input =
        [   sprintf "you picked %s" input
            "now running" ] |> List.iter Console.WriteLine

    let quitOrContinue() =
        Console.WriteLine "q to quit else continue with keypress"
        Console.ReadKey().KeyChar <> 'q'

    let finished stopticks = fun _ -> Stopwatch.GetTimestamp() >= stopticks

    let printResult result start =
        let final = (Stopwatch.GetTimestamp() - start |> TimeSpan).TotalSeconds
        let pretty = prettyNumbers result
        sprintf "performed %s operations in %f seconds" pretty final |> Console.WriteLine

    let op duration start =
        duration
        |> secondsToTicks
        |> (+) start
        |> finished
        |> addOne 0

    let opAsync duration start procs =
        [ for i in [ 1..procs ] -> async { return op duration start } ]
        |> Async.Parallel
        |> Async.RunSynchronously

[<EntryPoint>]
let main argv =
    let loop _ =
        let input =
            match Int32.TryParse(pickRunmode()) with
            | true, i -> i
            | _ -> 1
        input |> string |> feedback
        let start = Stopwatch.GetTimestamp()
        let result =
            opAsync 1L start input
            |> Seq.sum
        printResult result start

        quitOrContinue()

    while loop() do ()
    0


Pure fixed length queue I am modeling an infectious disease with a fixed incubation period. I chose a queue to keep track of when people become symptomatic. I imagined using some operations like so:

queue' = enqueue numberOfPeopleWhoJustGotInfected queue
(numberOfPeopleWhoJustBecameSymptomatic,queue'') = dequeue queue

Since enqueue and dequeue would always be atomic and the queue length would be fixed, I wrote a fixed length queue data structure. endequeue models the atomic enqueue & dequeue sequence. I hope that it will be more efficient than the library Data.Queue.

I'd like feedback on:

Efficiency. Can it be improved?
Typeclasses. Did I use them correctly? Am I missing others which are applicable?
Test Cases. Are there other logical properties I could add?

Haskell Code:

module FixedLengthQueue
 ( endequeue
 , fromList
 , length
 , peek
 ) where

import Prelude hiding (foldl,foldl1,foldr,foldr1,length)
import Control.Applicative ((<$>),(<*>))
import Data.Array
import Data.Foldable
import Data.Functor
import Data.Maybe  (fromJust)
import Data.Monoid

type Pointer = Int
type Length  = Int

data FixedLengthQueue a = FLQ Length Pointer (Array Int a)
  deriving (Eq) -- I need to manually define, see tests

instance (Show a) => Show (FixedLengthQueue a) where
  show = ("fromList "++) . show . toList

instance Functor FixedLengthQueue where
  fmap f =  fromJust . fromList . fmap f . toList

instance Foldable FixedLengthQueue where
  foldMap f (FLQ n p arr)
    =  f (arr ! p) <> g (succMod p n)
    where
      g z
        | z /= p    = f (arr ! z) <> g (succMod z n)
        | otherwise = mempty

fromList :: [a] -> Maybe (FixedLengthQueue a)
fromList [] = Nothing -- Nonsensical empty fixed length queue
fromList xs
  = Just
  . FLQ len 0
  . array (0, len-1)
  $ zip   [0..len-1] xs
  where
    len = foldl' inc 0 xs
    inc = flip (const succ)

length :: FixedLengthQueue a -> Int
length (FLQ n _ _) = n

peek :: FixedLengthQueue a -> a
peek (FLQ _ p arr) = arr ! p

endequeue :: a -> FixedLengthQueue a -> (a,FixedLengthQueue a)
endequeue e (FLQ n p arr)
  = ( arr ! p
    , FLQ n (succMod p n) $ arr // [(p,e)]
    )

succMod n m
  | n' >= m   = n' - m
  | otherwise = n'
  where n' = succ n

Basic Tests:

module Main where

import Prelude hiding (mapM_)
import Data.Foldable
import FixedLengthQueue
import Test.QuickCheck
import Safe

main ::  IO ()
main =
  mapM_ quickCheck
  ([ \x -> fmap peek                                        (fromList x) == headMay x
   , \x -> fmap (fst . endequeue undefined)                 (fromList x) == headMay x
   , \x -> fmap (init . toList . snd . endequeue undefined) (fromList x) == tailMay x
   , \x -> let mxs = (replicate 2) <$> (headMay x) >>= fromList
           in (snd . (endequeue <$> peek <*> id) <$> mxs)                == mxs
   ] :: [[Int] -> Bool])

Your fmap function is overly complicated. Array x is a Functor and Length and Pointer are obviously preserved by fmap, so:

instance Functor FixedLengthQueue where
  fmap f (FLQ a b x) =  FLQ a b $ fmap f x

There is listArray :: Ix i => (i, i) -> [e] -> Array i e, so you don't need zipping.

foldl' inc 0 xs is just length xs:

fromList :: [a] -> Maybe (FixedLengthQueue a)
fromList [] = Nothing -- Nonsensical empty fixed length queue
fromList xs
  = Just
  . FLQ len 0
  . listArray (0, len-1)
  $ xs
  where
    len = Prelude.length xs

Note the qualified use of Prelude.length. You can use

import Prelude hiding (foldl,foldl1,foldr,foldr1);
import qualified Prelude (length)

if you want length to always mean FixedLenghtQueue.length. Prelude.length will still be available.

Since all your internal arrays are 0-based, there is no need to store Length separately, it can be always retrieved by snd . bounds or rangeSize . bounds

Your FixedLengthQueue can be thought as a special array or a special list. So you can just construct the list or the array explicitly and use existing foldMap implementations. Here is code using innerArray approach:

instance Foldable FixedLengthQueue where
    foldMap f = foldMap f . innerArray where
        innerArray (FLQ l p a) = ixmap (bounds a) (mapIdx l p) a
        mapIdx l p i = (i + l - p) `mod` l

As for performance, you should benchmark your full application before optimization. Compositional style is not necessary worse performing so you should strive to write at as high level as possible before trying optimizations.

Also there is Data.Sequence which I think will perform better than Array while keeping you away from ST monad.

A useful typeclass instance to implement is Traversable. It is also cumbersome to implement as innerArray approach will work poorly:

instance Traversable FixedLengthQueue where
    traverse f = fmap fromArray . traverse f . innerArray where
        fromArray a = FLQ (rangeSize $ bounds a) 0 a

Interestingly, Prelude uses "innerList" approach - it converts an array to a list and back:

instance Ix i => Traversable (Array i) where
        traverse f arr = listArray (bounds arr) `fmap` traverse f (elems arr)

So I think the best we can do with Traversable is to use "innerList" approach too:

instance Traversable FixedLengthQueue where
    traverse f = fmap (fromJust . fromList) . traverse f . toList

Here is an Eq instance:

instance (Eq a) => Eq (FixedLengthQueue a) where
    (FLQ l1 _ _) == (FLQ l2 _ _) | l1 /= l2 = False
    q1 == q2 = toList q1 == toList q2

Here is another approach to implement toList:

indexList p l = range (p, l - 1) ++ range (0, p - 1)

toList' (FLQ l p a) = map (a !) $ indexList p l

I'm not sure that it's much better though, but the idea can be used everywhere:

eq (FLQ l1 p1 a1) (FLQ l2 p2 a2) = l1 == l2 && comp where
    r1 = indexList p1 l1
    r2 = indexList p2 l2
    comp = Prelude.all (\(i1, i2) -> (a1 ! i1) == (a2 ! i2)) $ zip r1 r2


Implementing the Barabási–Albert model I am writing a code for Barabási–Albert(BA) model with specific node and edges.
The algorithm is almost like [1] as follows:

  1.Add m<N nodes to G.
  2.Connect nodes in G randomly until you get a connected graph.
  3.Create a new node i.
  4.Pick a node j uniformly at random from the graph G. Set p=k(j)/k_tot.
  5.Pick a real number r uniformly at random between 0 and 1.
  6.If r<p then add G(m+step_i,j)=G(j,m+step_i)=1
  7. repeat steps 4-6, k times until each new node has k edges.
  8. repeat steps 3-7 until we have N nodes.

*:The sum of elements of each row or column is the degree(number of edges connected to that node) of each node.

** : k_tot is the total degree of all nodes until step i.
and here is the my implementation in Fortran:

program BA
 implicit none
 integer, parameter :: N = 20
 integer, dimension(n,n) :: A
 double precision :: r,p,r2(2),pj
 integer :: m0,i,j,L0,N1,t,jnod,k,di
 integer :: edge_number,ii,ie,je, degree

 A = 0
 m0 = 5 ! initial nodes
 L0 = 4 ! initial edges
 ii = 0
 ! adding m0 nodes with random connections
 do while (ii < L0)
   do ie = 1, m0
     call random_number(r)
     je = r * (m0 - 1) + 1
     if (A(ie,je) == 0 ) then
       if(ii>=L0) exit
       A(ie,je) = 1
       A(je,ie) = 1
       ii = ii + 1
     endif
   enddo
 enddo

 edge_number = L0
 N1 = m0
 degree = m0
 ! adding remaining nodes with pereferential attachment
 do t = 1,N-m0
   di = 0
   N1 = m0 + t
   do while(di < degree)
     call random_number(r)
     jnod = r * (N1-2)+1
     pj = sum(A(jnod,1:N1-1))/dble(sum(A(1:N1-1,1:N1-1)))
     call random_number(r)
     if ( r<pj .and. A(N1,jnod)==0 ) then
        A(N1,jnod) = 1
        A(jnod,N1) = 1
        edge_number = edge_number + 1
        di = sum(A(N1,1:N1))
     endif
   enddo
 enddo

 do i = 1,N
    write(12,"(*(I5))") (A(i,j),j=1,N)
 enddo
end program

I think the is not efficient at all and as more nodes added, it takes more to get out of loops.Do you have a better idea to make it more efficient?

I'll put some comments inline to the code, and in the end add a complete implementation of the program, with various changes to improve the execution.

program BA
 implicit none
 integer, parameter :: N = 20

For real numbers it is advisable to introduce a real kind with selected_real_kind:

 integer, parameter :: rk = selected_real_kind(15)
 integer :: A(n,n)

Use the real kind introduced above, to declare the reals:

 real(kind=rk) :: r, p, r2(2), pj
 real(kind=rk) :: sumA_q
 integer :: sumA
 integer :: m0, i, j, L0, N1, t, jnod, k, di

Often it is better to use more than single characters for variables (for example something like iNode or iEdge, this makes it visible what the iterator is actually used for.

 integer :: edge_number, ii, ie, je, degree

 A = 0
 m0 = 5 ! initial nodes
 L0 = 4 ! initial edges
 ii = 0
 ! adding m0 nodes with random connections
 rand_cnx: do ! while is actually deprecated, you anyway use 'if exit' in the
              ! loop, so I'd stick to that one. Using a block label to allow
              ! the identification of the loop in the exit statement.
   do ie = 1, m0
     call random_number(r)

You could create a bunch of m0 random numbers all at once here, and use them then subsequently. That might be a little faster, but probably has no really big impact.

     je = r * (m0 - 1) + 1
     if (A(ie,je) == 0 ) then
       A(ie,je) = 1
       A(je,ie) = 1
       ii = ii + 1
       if (ii>=L0) EXIT rand_cnx

No need to compute another random number here, if the limit was reached, leave the loop. Use a block label to directly leave the outer loop.

     end if
   end do
 end do rand_cnx

 edge_number = L0
 N1 = m0
 degree = m0

 ! Precompute sum of submatrix up to m0-1
 sumA = sum(A(1:m0-1, 1:m0-1))

 ! adding remaining nodes with pereferential attachment
 do t = 1,N-m0
   di = 0
   N1 = m0 + t

The summation over the subarray does not depend on the random numbers (only entries outside the subarray at N1 are modified, if I am not mistaken) and can be pre-computed. As N1 is linearly increasing, we can update the sum of the submatrix up to N1, by just adding the newly filled column and row from the previous iteration.

   ! Update sum of submatrix with the previously computed column and row.
   sumA = sumA + sum(A(1:N1-1,N1-1)) + sum(A(N1-1,1:N1-2))
   sumA_q = 1.0_rk / real(sumA, kind=rk)

   do
     call random_number(r)
     jnod = r * (N1-2)+1
     pj = sum(A(jnod,1:N1-1))*sumA_q
     call random_number(r)
     if ( r<pj .and. A(N1,jnod)==0 ) then
        A(N1,jnod) = 1
        A(jnod,N1) = 1
        edge_number = edge_number + 1
        di = sum(A(N1,1:N1))
        if (di >= degree) EXIT
     end if
   end do
 end do

 do i = 1,N
    write(12,"(*(I5))") (A(i,j),j=1,N)
 end do
end program BA

With a little more memory effort, you could also precompute all sum(A(jnod,1:N1-1)), use them for the summation of the complete submatrix and in the computation of pj, instead of recalculating the sum everytime the random number picks a specific jnod. This would result in turning the di into an array of length N. Implementing this led me to find that the first additional node has to be connected to all previous nodes, as you set degree=m0. In this case no randomness seems to be involved? I catch this special case in the implementation below:

program BA
  implicit none
  integer, parameter :: N = 20

  integer, parameter :: rk = selected_real_kind(15)
  integer :: A(n,n)

  real(kind=rk) :: r, pj
  real(kind=rk) :: sumA_q
  integer :: sumA
  integer :: m0, i, j, L0, N1, t, jnod
  integer :: di(N)

  integer :: edge_number, ii, ie, je, degree

  A = 0
  di = 0

  m0 = 5 ! initial nodes
  L0 = 4 ! initial edges

  ! adding m0 nodes with random connections
  ii = 0
  rand_cnx: do

    do ie = 1, m0
      call random_number(r)
      je = nint(r * (m0 - 1)) + 1
      if (A(ie,je) == 0 ) then
        A(ie,je) = 1
        A(je,ie) = 1
        di(ie) = di(ie) + 1
        di(je) = di(je) + 1
        ii = ii + 1
        if (ii>=L0) EXIT rand_cnx
      end if
    end do

  end do rand_cnx

  edge_number = L0
  N1 = m0
  degree = m0

  ! Precompute sum of submatrix up to m0-1
  sumA = sum(di(:m0-1)) - sum(A(:m0-1,m0))

  ! adding remaining nodes with pereferential attachment
  do t = 1,N-m0
    N1 = m0 + t

    ! Update sum of submatrix with the previously computed column and row.
    sumA = sumA + sum(A(:N1-2,N1-1)) + di(N1-1)
    sumA_q = 1.0_rk / real(sumA, kind=rk)

    need_all: if (N1-1 == degree) then

      ! Need all nodes to fulfill degree, no randomness required?
      A(N1,:N1-1) = 1
      A(:N1-1,N1) = 1
      edge_number = edge_number + N1-1
      di(:N1-1) = di(:N1-1) + 1
      di(N1) = di(N1) + N1-1

    else need_all

      do
        call random_number(r)
        jnod = nint(r * (N1-2))+1
        ! Only consider not yet connected nodes.
        if (A(jnod,N1) == 0) then
          pj = di(jnod)*sumA_q
          call random_number(r)
          if ( r<pj ) then
             A(N1,jnod) = 1
             A(jnod,N1) = 1
             edge_number = edge_number + 1
             di(N1) = di(N1)+1
             di(jnod) = di(jnod) + 1
             if (di(N1) >= degree) EXIT
          end if
        end if
      end do

    end if need_all

  end do

  do i = 1,N
     write(12,"(*(I5))") (A(i,j),j=1,N)
  end do

end program BA

No guarantees, that this is in any way correct. I guess, this could be further increased by just picking the random nodes out of the not yet connected ones. This would imply that you need to keep an index list of all 0 values for the current node, and then use jnod to pick out of those. This would be more involved book-keeping but would reduce the number of guesses, you need to do.


Ruby Repository Pattern I am trying to teach myself about repository pattern in ruby. Could you please review my code.

adapter.rb

module Adapter
  class Main
    def prebuild(obj)
      self.set_table_name = obj.table_name.to_s
      variables = obj.instance_variables
      @values = []
      @keys = []

      variables.reject! { |c| c.to_s == '@table_name' }.map do |key, value|
        @keys.push(key.to_s.gsub('@', ''))
        @values.push(obj.send(@keys.last))
      end
    end

    def get_table_name
      @table_name
    end

    def get_keys
      @keys
    end

    def get_values
      @values.map { |value| "'#{value}'" }
    end

    def set_table_name=(table_name)
      @table_name = table_name
    end
  end

  class Sqlite < Main
    require 'sqlite3'

    def initialize
      @db = SQLite3::Database.new 'file.db'
    end

    def persist(obj)
      prebuild(obj)
      sql_string = "INSERT INTO #{get_table_name} (#{get_keys.join(', ')}) VALUES (#{get_values.join(', ')})"
      @db.execute sql_string
      obj.id = @db.execute "SELECT last_insert_rowid()"
      obj
    end

    def retrieve(entity, id)
      self.set_table_name = entity.table_name
      rows = @db.execute "SELECT * FROM #{get_table_name} WHERE id=#{id}"
      fields = get_fields
      new_entity = entity.new

      for i in (0..fields.size-1)
        new_entity.send("#{fields[i]}=", rows[0][i])
      end
      new_entity
    end

    def get_fields
      rows = @db.execute "PRAGMA TABLE_INFO (#{get_table_name});"

      rows.map { |name| name[1] }
    end

    def delete(obj)
      prebuild(obj)
      @db.execute "DELETE FROM #{get_table_name} WHERE id=#{obj.id}"
    end
  end
end

entity.rb

module Entity
  class Member
    attr_reader :table_name

    attr_accessor :username
    attr_accessor :email
    attr_accessor :password
    class << self
      def table_name
        @table_name ||= 'members'
      end
    end
    def table_name
      @table_name ||= 'members'
    end

    def id=(new_id)
      @id = new_id
    end

    def id
      @id
    end

    def username=(new_username)
      @username = new_username
    end

    def username
      @username
    end

    def email=(new_mail)
      @email = new_mail
    end

    def email
      @email
    end

    def password=(new_password)
      @password = new_password
    end

    def password
      @password
    end
  end
end

repository.rb

module Repository
  class Member
    def initialize(adapter)
      @adapter = adapter.new
    end

    def save(member)
      @adapter.persist(member)
    end

    def get(id)
      @adapter.retrieve(Entity::Member, id)
    end

    def delete(member)
      @adapter.delete(member)
    end
  end
end

test.rb

require './lib/entity'
require './lib/adapter'
require './lib/repository'

member = Entity::Member.new
member.username = 'ahmet'
member.email = 'ahmet@kapikiran.com'
member.password = '12345'
repository = Repository::Member.new(Adapter::Sqlite)
repository.save(member)

member = repository.get(5)

repository.delete(member)

Starting with the end: test.rb barely tests anything. Yes, it'll exercise your code, and make it crash if there's a mistake, but it doesn't actually verify that your code does what it's supposed to do.

So, I'd highly suggest you write proper unit test using one of the many test libraries out there (Ruby's own Test::Unit, minitest, rspec, etc...)

You seem to be confused about accessor methods. The purpose of attr_accessor is to have Ruby automatically generate the methods to get and set an instance variable. In your Member class, you're using attr_accessor, but you're also (redundantly) providing your own getters and setters. Since they literally just get and set, they're exactly the same as what attr_accessor has already made for you.

So Member can be reduce to this:

module Entity
  class Member
    attr_accessor :id, :username, :email, :password

    class << self
      def table_name
        @table_name ||= 'members'
      end
    end

    def table_name
      @table_name ||= 'members'
    end
  end
end

(Of course, id shouldn't be easily settable, but I can't cover everything in this review)

The whole table_name construction is odd too. If anything, this would make more sense:

module Entity
  class Member
    attr_accessor :id, :username, :email, :password

    def self.table_name
      'members'
    end
  end
end

Since table_name should probably be constant, just return a string. And don't duplicate the method for both class and instance. If anyone needs the table name from an instance, they can do some_member_object.class.table_name.

Your Main class also has some funny ideas about data access. Here, you're not using attr_reader :keys and attr_accessor :table_name although you might as well. Then you can skip the methods. The other reason to do this is that naming methods get_* or set_* is not very Ruby-like.

get_values (which should just be named values), is also problematic for a few reasons:

Main is supposed to be pretty abstract. Why does it assume that values should be returned as quoted strings? What is the derived class isn't meant for SQLite or any kind of SQL? Perhaps you just want the raw values?
Yes, in fact you do want the raw values! Poor string-quoting is the oldest attack vector in the book. For instance, what if, say, the password value is a string like this: "sup'); DROP TABLE members;"?

With your code, you'll end up running the following the current query when trying to save:

INSERT INTO members (email, username, password)
VALUES ('foo@example.com', 'foo', 'sup'); DROP TABLE members; ');

A basic SQL injection attack. As you can see from the syntax highlighting, the SQL suddenly contains TWO commands: INSERT and DROP TABLE. You insert a row... and it happens to delete your entire table. Oops.

Long story short: Use proper parameter substitution (which the sqlite3 gem has built in):

db.execute("INSERT INTO members (email, username, password) VALUES (?, ?, ?)", [email, username, password])

That let's sqlite take care of doing proper string quoting/escaping and all that. It's safe.

And you can replace the get_values method with attr_reader :values.

Of course, the only reason attr_readers make sense is that you have the prebuild method. Which doesn't really make much sense. If must be called before anything else works, so if anything it should be a constructor.

But really, it's simpler to just drop Main entirely, and instead add a superclass for Member:

class Record
  def to_hash
    instance_variables.each_with_object({}) do |hash, name|
      key = name.to_s.sub('@', '') }
      value = send(key)
      hash[key] = value;
    end
  end
end

class Member < Record
  ...
end

And then the sqlite adapter becomes:

require 'sqlite3' # require statement should be at the top of the file

class Sqlite
  def initialize
    @db = SQLite3::Database.new 'file.db' # the filename should really be an argument
  end

  # formerly named "persist", but "persist" can mean either insert *or* update
  def insert(record)
    hash = record.to_hash.delete("id")
    markers = ["?"] * hash.keys.count
    sql = "INSERT INTO #{record.class.table_name} (#{hash.keys.join(',')} VALUES (#{markers.join(','))"
    @db.execute(sql, hash.values);

    record.id = @db.execute("SELECT last_insert_rowid()")
    record
  end

  # presumably you'll only want 1 record returned when searching by id
  def retrieve(klass, id)
    columns = columns_in_table(klass.table_name)
    rows = @db.execute("SELECT * FROM #{klass.table_name} WHERE id=? LIMIT 1", id)
    return nil if rows.empty? # nothing found
    instance = klass.new
    rows.first.zip(columns).each do |key, value|
      instance.send("#{key}=", value)
    end
    instance
  end

  def delete(record)
    @db.execute("DELETE FROM #{record.class.table_name} WHERE id=#{record.id}"
  end

  private

  def columns_in_table(table)
    @db.execute("PRAGMA TABLE_INFO (#{table})").map { |info| info[1] }
  end
end

Of course, there's still a long way from here to a well-known and battle-tested implementation like Rails' ActiveRecord. For instance, you currently have to duplicate the names of columns in your objects. If an object doesn't have the same instance variables as the table's columns - or if they're named differently, or of the wrong type... - things will break.

So, in all, a good exercise, but not something I'd rely on.


How should I set a daily method as executed, from inside or from outside? I have the following code:

static void TimerElapsed(object sender, ElapsedEventArgs e)
{
    foreach (BIGService bigService in runningServices)
    {
        if (!bigService.ExecutedToday)
        {
            int executionResult = bigService.Execute();
            string serviceName = bigService.ToString();
            if (executionResult == 0)
            {
                EventLogger.WriteToEventLog("Success");
            }
            else
            {
                EventLogger.WriteToEventLog("Failure");
            }
        }
    }
}

where BIGService is an Abstract class, that has 5 descendants (5 individual service classes with this common parent).  The enclosing timer's interval is 7200. So it elapses in every 2 hours.

All services must be run only once a day. Therefore I created a bool ExecutedToday property and void SetAsExecuted method.

My question is: where do you recommend I should call the SetAsExecuted method? Which way is more subservient?  In the end of the Execute() method itself or in my copied code at the end of the if clause?

(Similar situations have happened to me several times, I just now have the time to ask other's opinion)

As your code stands now it looks to me as if the timer has some responsibilities it shouldent have.

My suggestion would be to either move all the timer information to your timer, including bigService.ExecutedToday and SetAsExecuted OR you move all that logic inside the service. I would go for the latter since that would be more in line with the "Tell dont ask" principle.

The code in the timer would look like this:

static void TimerElapsed(object sender, ElapsedEventArgs e)
{
    foreach (BIGService bigService in runningServices)
    {
           bigService.Execute();
    }
}

In your BigService method you contain the logging and wether or not that service can be run at the time it is requested.

One more thing: I would make an Enum to store the 0 value for executionResult, at a later date it might not be clear to you what 0 actually means


How can I speed up this solution to the "Rock-Paper-Scissors Tournament" As I have recently been selected to participate in my country's final preselection to the IOI -- this took me aback -- I have decided to get a bit more serious about competetitive programming.

The Rock-Paper-Scissors Tournament is an old question form the Waterloo Programming Contest 2005-09-17, available on kattis.

What it asks you to do is:

You first get two numbers n and k for the number of participants and the number of games played in the tournament.
And then you get k lines detailing every one of those games.
Using this data you have to output the winrate for each contestant in three decimal places.
A player that has not played a single game throughout the tournament should get a '-' as output.

A zero for the number of players terminates the program.

2 4
1 rock 2 paper
1 scissors 2 paper
1 rock 2 rock
2 rock 1 scissors
2 1
1 rock 2 paper
0

Should give the output

0.333
0.667

0.000
1.000

As far as I know my solution, which follows below, solves this problem perfectly, but, sadly, it is too slow.

My question is, does anyone see where I made a suboptimal choice in the datatype I used or how I calculated a result that causes my program to fail to beat the timelimit? I hope that understanding what I could have done better here allows me to become a better programmer in the future.

#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>

std::unordered_map< std::string, std::unordered_map<std::string, int> >
result(
{
   {
       "rock",
        {
            {"rock", 0},
            {"paper", -1},
            {"scissors", 1}
        }
   },
   {
        "paper",
        {
            {"rock", 1},
            {"paper", 0},
            {"scissors", -1}
        }
   },
   {

        "scissors",
        {
            {"rock", -1},
            {"paper", 1},
            {"scissors", 0}
        }
   }
});

int main() {
    int n,
        k,
        p1,
        p2;

    std::string m1,
                m2;

    while (1) {
        std::cin >> n;

        if (n == 0) {
            break;
        }

        std::cin >> k;

        std::vector<int> wins(n, 0);
        std::vector<int> losses(n, 0);

        while (k--) {
            std::cin >> p1;
            std::cin >> m1;
            std::cin >> p2;
            std::cin >> m2;

            int v = result[m1][m2];

            if (v == 1) {
                wins[p1-1]++;
                losses[p2-1]++;
            } else if (v == -1) {
                losses[p1-1]++;
                wins[p2-1]++;
            }
        }

        std::cout << std::fixed;
        std::cout << std::setprecision(3);
        for (int i = 0; i < n; i++) {
            float numOfWins = (float)wins[i];
            float numOfGames = (float)(wins[i]+losses[i]);
            if (numOfGames != 0) {
                std::cout << numOfWins/numOfGames << std::endl;
            } else {
                std::cout << '-' << std::endl;
            }
        }
        std::cout << std::endl;

    }
    return 0;
}

The choice of data structure is fundamentally sound (but more on that later).

The first thing that jumped out to me in your code is actually not directly related to performance: you could drastically improve readability by declaring variables where you use them rather than at the beginning, and by assigning better names. Don’t be afraid that declaring variables inside a loop will lead to performance degradation! First off, in most cases it doesn’t. And secondly, where it does the difference in performance is usually negligible, and will not contribute sufficiently to be noticed. If, and only if, that’s not the case does it make sense to change this.

Some more points regarding readability:

Since you’re already using uniform initialisation, use {…} instead of (…) in your initialisation of result. Writing ({…}) is pretty unusual and consequently tripped me up.
Since C++11 there’s no need to put a space between template argument list terminators (> > vs. >>).
Don’t use integer literals in place of boolean values: don’t write while (1), write while (true).
Your (C-style) casts to float are unnecessary. Remove them.
Make more variables const — in particular result! You don’t want to accidentally modify that. You will also need to change your lookup to using find then, unfortunately.

Now on to performance improvements. There are effectively two things to improve.

First off, two things about unordered_map:

Although the choice of this structure is algorithmically correct, C++’s standard library specification of it is poor due to a fault in the standard wording, which forbids efficient implementations. The structure is therefore a cache killer.
In your case a general string hash is overkill: you only need to check the first letter of each word to determine which move was played.

You could exploit the second point by providing a custom Hash template argument to std::unordered_map which only returns the first character. But given the first point, I would suggest ditching std::unordered_map altogether and just using a 256×256 array as a lookup table (or, if you want to optimise space, subtract some common value from the first character or find a perfect hash function for the letters “r”, “p” & “s”).1

And now something more mundane, since the execution time of your program is at any rate completely dominated by IO: std::cin and std::cout are by default synchronised with C’s buffered standard IO, which makes them excruciatingly slow. To fix this, put std::ios_base::sync_with_stdio(false) a the beginning of your main function. Similarly, untie standard output from standard input via std::cin.tie(nullptr). Secondly, replace std::endl with "\n". std::endl flushes the stream each time, which is slow. It’s also unnecessary to set the stream format manipulators in every loop (although I don’t expect this to change the performance).

— It’s worth noting that none of that had a measurable impact on the performance of the code on my machine. In fact, formatted input via std::cin totally dominates the runtime. This is surprising and disappointing (because there’s no reason for it: it hints at a broken standard library implementation). Using scanf is significantly faster, which should not happen. Of course using scanf also requires changing the type of m1 and m2 (you can use a static buffer of size sizeof "scissors"). It’s worth emphasising that it’s really IO that’s slow, and not the std::strings: simply replacing the std::strings with static buffers has almost no perceptible impact on runtime (likely due to SSO). It’s really std::cin vs scanf.

1 We’re in luck, and the character codes of “r”, “p” and “s” in common encodings differ in the lower two bits, so that we only need a 4×4 lookup and minimal recoding:

static int const result[4][4] = {
//    p      r   s
    { 0, 0,  1, -1},     // paper
    { 0, 0,  0,  0},
    {-1, 0,  0,  1},     // rock
    { 1, 0, -1,  0}      // scissors
};

…

int const winner = result[move1[0] & 3][move2[0] & 3];

But of course given what I said about the IO bottleneck that’s completely unnecessary obfuscation.


Describing algorithms to implement higher level operations in terms of the lower level operations My question concerns problem (b). This is my attempt:

def shift_left(D,k)
    for j = 0 to k:
      x_current = D.delete_first() //this remove and return first item
      D.insert_last(x_current)

    return D

The answer key was given the following for the solution. I am just trying to figure out if my solution is correct. I know this solution key uses recursion. Does my solution work as well?

Your code solves the problem in a desired way, it is concise which is good.
Some comments
Your design limits the shifting to k > len(D) - 1, if it is your intention, then it is perfect otherwise this could be solved by doing
def shift_left(D, k):
    k = k % len(D) #the modulus makes k to be in the positive integer domain
    if (k < 1):
        return
    x = D.delete_first()
    D.insert_last(x)
    #it could be done with a for and saves recursively comparing k each time
    shift_left(D, k-1)

An alternative
def shift_left(D, k):
    k = k % len(D)
    if (k < 1):
        return
    #avoids recursion, which saves recursive calls and passing parameters
    #(could be done using a while)
    for i in range(0,k)
        x = D.delete_first()
        D.insert_last(x)


Manipulating matrices for 3D drawing I've written a short library for manipulating matrices for 3D drawing. I've tried to strike a balance between speed and readability. Anything to improve?

%!
%mat.ps
%Matrix and Vector math routines

/ident { 1 dict begin /n exch def
    [
    1 1 n { % [ i
        [ exch % [ [ i
        1 1 n { % [ [ i j
            1 index eq { 1 }{ 0 } ifelse % [ [ i b
            exch % [ [ b i
        } for % [ [ b+ i
        pop ] % [ [ b+ ]
    } for % [ [b+]+ ]
    ]
end } def

/rotx { 1 dict begin /t exch def
    [ [ 1  0      0         ]
      [ 0  t cos  t sin neg ]
      [ 0  t sin  t cos     ] ]
end } def

/roty { 1 dict begin /t exch def
    [ [ t cos      0  t sin ]
      [ 0          1  0     ]
      [ t sin neg  0  t cos ] ]
end } def

/rotz { 1 dict begin /t exch def
    [ [ t cos  t sin neg  0 ]
      [ t sin  t cos      0 ]
      [ 0      0          1 ] ]
end } def

/.error where { pop /signalerror { .error } def } if

/dot { % u v
    2 copy length exch length ne {
        /dot cvx /undefinedresult signalerror } if
    % u v
    0 % u v sum
    0 1 3 index length 1 sub { % u v sum i
        3 index 1 index get exch % u v sum u_i i
        3 index exch get % u v sum u_i v_i
        mul add % u v sum
    } for % u v sum
    3 1 roll pop pop % sum
} bind def

% [ x1 x2 x3 ] [ y1 y2 y3 ]  cross  [ x2*y3-y2*x3 x3*y1-x1*y3 x1*y2-x2*y1 ]
/cross { % u v
    dup length 3 ne 2 index length 3 ne or {
        /cross cvx /undefinedresult signalerror } if
    % u v
    exch aload pop 4 3 roll aload pop % x1 x2 x3 y1 y2 y3
    [
        5 index 2 index mul % ... [ x2*y3
        3 index 6 index mul sub % ... [ x2*y3-y2*x3
        5 index 5 index mul % ... [ x2*y3-y2*x3 x3*y1
        8 index 4 index mul sub % ... [ x2*y3-y2*x3 x3*y1-x1*y3
        8 index 5 index mul % ... [ x2*y3-y2*x3 x3*y1-x1*y3 x1*y2
        8 index 7 index mul sub % ... [ x2*y3-y2*x3 x3*y1-x1*y3 x1*y2-x2*y1
    ]
    7 1 roll 6 { pop } repeat
} bind def

/transpose { STATICDICT begin
    /A exch def
    /M A length def
    /N A 0 get length def
    [
    0 1 N 1 sub { /n exch def
        [
        0 1 M 1 sub { /m exch def
            A m get n get
        } for
        ]
    } for
    ]
end } dup 0 6 dict put def

/matmul { STATICDICT begin
    /B exch def
    B 0 get type /arraytype ne { /B [B] def } if
    /A exch def
    A 0 get type /arraytype ne { /A [A] def } if
    /Q B length def
    /R B 0 get length def
    /P A length def
    Q A 0 get length ne {
        /A A transpose def
        /P A length def
        Q A 0 get length ne {
            A B end /matmul cvx /undefinedresult signalerror
        } if
    } if

    [
    0 1 P 1 sub { /p exch def % rows of A
        [
        0 1 R 1 sub { /r exch def % cols of B
            0
            0 1 Q 1 sub { /q exch def % terms of sum
                A p get q get
                B q get r get mul
                add
            } for
        } for
        ]
    } for
    ]

end } dup 0 10 dict put def

%u v {operator}  vop  u(op)v
%apply a binary operator to corresponding elements
%in two vectors producing a third vector as result
/vop { 1 dict begin
    /op exch def
    2 copy length exch length ne {
        /vop cvx end /undefinedresult signalerror
    } if

    [ 3 1 roll % [ u v
    0 1 2 index length 1 sub { % [ ... u v i
        3 copy exch pop get % u v i u_i
        3 copy pop get      % u v i u_i v_i
        op exch pop         % u v u_i(op)v_i
        3 1 roll            % u_i(op)v_i u v
    } for % [ ... u v
    pop pop ]

end } def

%length of a vector
/mag { 0 exch { dup mul add } forall } def

/elem { % M i j
    3 1 roll get exch get % M_i_j
} def

/det {
    dup length 1 index 0 get length ne { /det cvx /typecheck signalerror } if
    1 dict begin /M exch def
        M length 2 eq {
            M 0 0 elem
            M 1 1 elem mul
            M 0 1 elem
            M 1 0 elem mul sub
        }{
            M length 3 eq {
                M aload pop cross dot
            }{ /det cvx /rangecheck signalerror } ifelse
        } ifelse
    end
} def

As far as readability goes, maybe you'd like to add an arg1 arg2 arg3 -- result1 result2 type of comment to each function? So we know what was on the stack before invoking, and what we expect to find afterward? Almost equivalently, you might show a unit test invoking your function and verifying the result.


Refactoring 3 level depth for loops in JavaScript I'm trying to get rid of some of the horrible nested loops in the following code.
Essentially is moving TDs to top rows based on whether the current row has the current cell. You can see the execution here:
http://jsfiddle.net/Jq8sk/

How can I clean it up and avoid this level of depth. Any help is appreciated.

var trs = $('.trs');
var arr = ['n0', 'n1', 'n2'];
for (var i = 0; i < trs.length; i++) {
    for (var j = 0; j < arr.length; j++) {
        var tds = trs[i].getElementsByClassName('tds ' + arr[j]);
        if (tds.length == 0) {
           for (var x = i + 1; x < trs.length; x++) {
               var tds_offset = trs[x].getElementsByClassName('tds ' + arr[j]);
               if (tds_offset.length > 0) {
                  trs[i].appendChild(tds_offset[0]);
                  break;
               }
           }
        }
    }
}

This may not actually be any better as far as performance goes, but I believe it is equivalent to your code (and possibly more readable?).

http://jsfiddle.net/Jq8sk/1/

var arr = ['n0', 'n1', 'n2'];

$('.trs').each(function(){
   var $row = $(this);

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

        if($row.children(".tds." + arr[i]).length === 0){
            // td doesn't exist, see if any later rows have it

            var $tds = $row.nextAll(".trs").children(".tds." + arr[i]);

            if($tds.length > 0){
               $row.append($tds[0]);
            }
        }
    }
});