texts:
Now I'm reading C Premier Plus by Stephen Prata and there's an exercise 4 in chapter 6 which has no solution in the book, so I can't check if I did it properly. My code works like it should, but I want to know maybe there are some better or cleaner solutions.

Here's the description:

  Have a program request the user to enter an uppercase letter. Use
  nested loops to produce a pyramid pattern like this:

    A
   ABA
  ABCBA
 ABCDCBA
ABCDEDCBA

  The pattern should extend to the character entered. For example, the
  preceding pattern would result from an input value of E .

  Hint: Use an outer loop to handle the rows. Use three inner loops in a row,
  one to handle the spaces, one for printing letters in ascending order, and
  one for printing letters in descending order.

#include <stdio.h>

int main(void) {
    char ch;
    char row;
    char spaces;
    char let;
    char back;

    printf("Please, insert an uppercase letter: ");
        scanf("%c", &ch);

    for(row = 'A'; row <= ch; row++) {
        for(spaces = ch; spaces > row; spaces--)
            printf(" ");

        for(let = 'A'; let < row; let++)
            printf("%c", let);

        for(back = let; back >= 'A'; back--)
            printf("%c", back);
        printf("\n");
    }
    return 0;
}


texts: JavaScript program to count lines of Java code

texts:
I've implemented a small program in JavaScript to count the number of lines of a string of java source code.

This was done for one of the Code Kata exercise: http://codekata.com/kata/kata13-counting-code-lines/

Overall, the goal of this exercise is summarised as follow:

  The mixture of line-based things (single line comments, blank lines,
  and so on) with the stream-based block comments can make solutions
  slightly ugly. While coding your solution, consider the structure of
  your code, and see how well it fits the structure of the problem. As
  with most of these kata, consider coding multiple alternative
  implementations. Does what you learned on the first tries affect your
  approach to subsequent ones?

To be honest, I've submitted this for an interview and was told that this "lacked fundamentals by allowing errors in the code, there were issues in code construct and there were issues in choice of techniques".

Here's my simple app's source (also available in CodePen):

/**
 * Return the number of lines of code of a Java source code.
 * {@link http://codekata.com/kata/kata13-counting-code-lines/}
 * @param {string} Java source code
 * @return {number}
 */
function getJavaLineCount(source) {
    var count = 0;
    var patterns = {
        spaces: /^\s+/,
        singleLineComment: /^\/\/.*/,
        multiLineComment: /^\/\*((?!\*\/)[\s\S])*\*\//,
        code: /^.*\s*/
    };

    var readToken = function () {
        var m, type;
        if (m = source.match(patterns.spaces)) {
            type = 'spaces';
        } else if (m = source.match(patterns.singleLineComment)) {
            type = 'singleLineComment';
        } else if (m = source.match(patterns.multiLineComment)) {
            type = 'multiLineComment';
        } else if (m = source.match(patterns.code)) {
            type = 'code';
        } else {
            throw new Error("Unknown code pattern!");
        }
        var token = m[0];
        source = source.substr(token.length);

        //DEBUG
        console.log('Found token (%s): %s', type, JSON.stringify(token));
        return type;
    };

    while (source) {
        if (readToken() === 'code') {
            count++;
        }
        console.log('new source = |%s|', source);
    }

    //DEBUG
    console.log('LOC = ', count);
    return count;
}

$(function () {
  var calculateLOC = function() {
   $('#linesOfCode').text(getJavaLineCount(
    $('#source').val()
   ));
  };

    $('#source').change(calculateLOC);
  calculateLOC();
});
textarea {
  width: 50%;
}

<textarea id="source" rows="15">
/*****
 * This is a test program with 5 lines of code
 *  \/* no nesting allowed!
 //*****//***/// Slightly pathological comment ending...
public class Hello {

 @cool
 private String test = "some /* commented */ 'and' \" asd other\" " +
  "string";

    public static final void main(String [] args) { // gotta love Java
        // Say hello
      System./*wait*/out./*for*/println/*it*/("Hello/*");
    }
}
</textarea>

  n/a lines of java code.

To improve this, I could imagine writing a simple character parser to avoid using regexp, that's assuming that we consider regexps to be too slow in JS.

I know that if you provide it broken java code, it'll not work properly - but I assumed that this case would not be considered a normal scenario in this exercise.

Apart from this, I'm not sure what other kind of errors it might have.
Any suggestions?


texts:
I'm verifying South African IDs with jQuery, the code below works but Id like to know if it could be simplified in anyway or if there is a better way of doing things here?

South African IDs are verified as follows:

Using ID Number 8001015009087 as an example:
Add all the digits in the odd positions (excluding last digit).
8 + 0 + 0 + 5 + 0 + 0 = 13  .............................[1]

Move the even positions into a field and multiply the number by 2.
011098 x 2 = 22196  .....................................[2]

Add the digits of the result in [2].
2 + 2 + 1 + 9 + 6 = 20  .................................[3]

Add the answer in [3] to the answer in [1].
13 + 20 = 33  ...........................................[4]

Subtract the second digit of [4](i.e. 3) from 10. The number must tally with
the last number in the ID Number. If the result is 2 digits, the last digit is
used to compare against the last number in the ID Number. If the answer differs,
the ID number is invalid.

And the code:

var me = $("#id");
var odd = new Number();
var even_string = new String();
var even_result = new Number();
var even = new Number();
var result = new Number();

// Check length
if( me.val().length == 13 )
{
    $.each(me.val(), function(p,v){
        if (p%2 == 0 & p != 12)
        {
            odd += Number(v); // --> 1. Add all odd positions except the last one.
        }
        else
        {
            if(p != 12)
            {
                even_string += String(v); // --> 2.1 Join all even positions.
            }
        }
    });

    // 2.2 Multiply even string by two.
    even_result = (even_string * 2);

    // 3. Add the digits of the new even result in two point two.
    $.each(String(even_result), function(p,v){
        even += Number(v);
    });

    // 4. Add answer in three to the answer in one.
    result = odd+even;

    // 5. Subtract the second digit from step 4. from ten.
    result = 10 - Number(String(result).substr(1,1));

    // 6. Make sure we use the very last digit on the result.
    if( (String(result)).length > 1 )
    {
        result = Number( (String(result)).charAt( (String(result)).length-1 ) );
    }

    // 6. The final check
    if( Number(result) != me.val().substr(12,1) )
    {
        // Not a valid South African ID
        alert("Your South African ID is not valid.");
    }
};


texts:
I have implemented mergesort in C. Any advice on making it more compact? My merge function seems less than fully optimal.

//mergeSort in C

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

void merge(int [], int[], int[], int, int);
void mergesort(int[], int);

int main()
{
    int unsorted[] = {4, 1, 3, 0, 10, 2, 5, 5};
    int size = sizeof(unsorted)/sizeof(int);
    mergesort(unsorted, size);
    printf("The sorted array is: ");
    for(int i = 0; i < size; i++)
    {
        printf("%d, ", *(unsorted+i));
    }

    return 0;
}

void merge(int *original, int* first, int* second, int len1, int len2)
{
    int i = 0;
    int firPtr = 0;
    int secPtr = 0;

    while(i < (len1+len2))
    {
        if(firPtr == len1)
        {
            original[i] = second[secPtr++];
        }

        else if(secPtr == len2)
        {
            original[i] = first[firPtr++];
        }

        else if(first[firPtr] < second[secPtr])
        {
            original[i] = first[firPtr++];
        }

        else
        {
            original[i] = second[secPtr++];
        }
        i++;
    }
}
void mergesort(int unsorted[], int size)
{
    if(size <= 1 || unsorted == NULL)
    {
        return;
    }

    int *first = (int *)malloc((size/2)*sizeof(int));
    int *second = (int *)malloc((size - size/2)*sizeof(int));;

    int mid = size/2;

    for(int i = 0; i < mid; i++)
    {
        *(first+i) = *(unsorted+i);
    }

    //Common Error/Note to self: Make sure when initializing j to
    //not 0, the code block truly requires that.
    for(int j = (mid); j <  size; j++)
    {
        *(second+(j-mid)) = *(unsorted+j);
    }

    mergesort(first, mid);
    mergesort(second, size - mid);
    merge(unsorted, first, second, mid, size - mid);
    free(first);
    free(second);
}


texts: Supporting all closure options in WinForms MVC application

texts:
I have a WinForms MVC application that uses Ninject for it's Dependency Injection (DI) / IoC Container. I have build quite a nice framework that allows the main shell (which uses a Docking Container to house an manipulate windows - like Visual Studio), to manipulate IDocument types (actual documents .txt, .xlsx etc.) and ITool types (my utilities, like file system explorer tree view, Command Window etc.). I communicate from the views (which are blind and deaf to the fact the controllers exist) to their controllers via event handlers. So the architecture is like this:

IView.cs:

public interface IView
{
    string DisplayName { get; set; }
}

IController.cs:

public interface IController
{
    bool IsDirty { get; set; }
    IView View { get; }
}

IDocumentView.cs:

public interface IDocumentView : IView, IActivate, IDeactivate
{
    bool StatusBarVisible { get; set; }
}

IDocumentController.cs:

public interface IDocumentController : IController
{
    bool Handles(string path);
    DocumentView New(string fileName);
    DocumentView Open(string path);
    void Save();
    string FilePath { get; set; }
    IEnumerable<DocumentFileType> FileTypes { get; }
}

I then have an abstract DocumentView class that handles so common behaviors of all IDocument types.

DocumentController.cs:

public abstract class DocumentController : IDocumentController, IClose, IGuardClose, IDisposable
{
    // Lots of stuff...
}

IGuardClose.cs:

public interface IGuardClose
{
    void CanClose(Action<bool> callback);
}

IClose.cs:

public interface IClose
{
    bool TryClose(object sender, FormClosingEventArgs e);
}

DocumentView.cs:
    [TypeDescriptionProvider(typeof(AbstractControlDescriptionProvider))]
    public abstract class DocumentView : DockContent, IDocumentView, IViewManagment
    {
        public virtual EventHandler OnViewLoaded { get; set; }
        public virtual EventHandler OnViewClosing { get; set; }

    public virtual EventHandler<EventArgs> ViewActivated { get; set; }
    public virtual EventHandler<EventArgs> ViewDeactivate { get; set; }

    public abstract string DisplayName { get; set; }
    public virtual bool StatusBarVisible { get; set; }
}

IViewManagement.cs:

public interface IViewManagment
{
    EventHandler OnViewLoaded { get; set; }
    EventHandler<FormClosingEventArgs> OnViewClosing { get; set; }
}

They allow me to wire my controller up to listen for the loaded and losing events triggered from the view without the view knowing anything about it, but herein lies my problem.

For my actual IDocumentViews and IDocumentControllers, I inherit from DocumentView and DocumentController respectively. This works well and all is fine, I can open new documents, open from files system you name it. My issue, is to do with closure. If I click the views "X" button to close the view, I need (and do) let the controller clean up some resources it is using (a FileSystemWatcher for the opened file etc.), but I also need to be able to close the view from the controller, so the TryClose method cannot merely do View.Close() for all calls as clearly this will envolve a stack overflow, as the View.Close() request would lead to another call to the controller TryClose etc.

My questions:

How can I best implement Controller.TryClose() so it can be used from both the controller and the view, should I have two methods in IClose, CleanUp(), let the controller clean its business and Close() actually close the view as well as clean up?
Sometimes the user will close the main shell. Here I can to loop through all open documents and check CanClose() of IGuardClose. Assuming I can easily access the controllers from the main shell in a for loop/foreach loop, how best could I implement a close all (with safety - "some documents  are unsaved do you want to save now?")?


texts:
I am trying to create a script that shows my login modal on page load. I have a button that opens the register modal and closes the login modal if clicked.

Here is the script I am using:

$(document).ready(function(){
  $('#loginmodal').modal('show')
});

$(".hidelogopenreg").click( function()
         {
            $('#loginmodal').modal('hide')
            $('#registermodal').modal('show')
         }
 );

Even though the works correctly, I fear it's using bad practices as I have little JavaScript knowledge and don't want to have to resolve problems further down the line.

Is this correct and efficient or is there a better way of writing this?

Another problem I had is that hiding a modal causes the body to shift to the right on close, to fix this I added:

body {
padding-right:0px !important;
margin-right:0px !important;
}

Could this also cause problems for me?


texts: SQL-Server Merge Statement with .NET DataTable

texts:
Background:
I'm trying to synchronize order information between Oracle and SQL-Server databases and allow users to be able to track any changes between what has been replicated via an ASP.NET web page.  Users will be able to select which line items they want to be able to work on via this page and the remainder will be excluded going forward.  Users will also have the option to change which items have been excluded at any time until the process has been finalized.

The initial load of this order information replicates (from Oracle to SQL-Server) all of the line items and presents them for assignment to the user.  Any subsequent load of the order will compare replicated data to the original data.  I'm using the following statement to handle the replication and reconciliation based on user selections:

CREATE TABLE #tempSpecOrderReplication
(
    Ord_L_ID INT,
    Order_Number INT,
    Ord_ID INT,
    Item_Number VARCHAR(50),
    Quantity DECIMAL(18, 2),
    UOM VARCHAR(50),
    Price DECIMAL(18, 2),
    Is_Spec_Order BIT
);

INSERT INTO #tempSpecOrderReplication
([Ord_L_ID], [Ord_ID], [Quantity], [UOM], [Price],
 [Is_Spec_Order], [Item_Number], [Order_Number])
VALUES (...); --These values come from the .NET DataTable

MERGE Spec_Order_Replication WITH (HOLDLOCK) AS target
USING (SELECT * FROM #tempSpecOrderReplication) AS source
ON (target.Ord_L_ID = source.Ord_L_ID)
WHEN MATCHED THEN
    UPDATE SET Is_Spec_Order = source.Is_Spec_Order
WHEN NOT MATCHED THEN
    INSERT
    (Ord_L_ID, Order_Number, Ord_ID, Item_Number,
     Quantity, UOM, Price, Is_Spec_Order)
    VALUES
    (source.Ord_L_ID, source.Order_Number, source.Ord_ID, source.Item_Number,
     source.Quantity, source.UOM, source.Price, source.Is_Spec_Order);

DROP TABLE #tempSpecOrderReplication

Questions:

Is there any way I can improve the existing SQL statement?
Is there a better way that I can go about this?

I'm using SQL-Server version 2008 R2.

Please ask if you need any further information.


texts:
I'm creating a user account login with PHP and Mysql which will be used by school teachers. To login there are 3 items required : school, username and password. This will allow for 2 of "MRSMITH" in two different schools.

The database is:

schools.login_name is the school part of the login
admin_users.username this is the teacher's username
admin_users.pass_hash(&salt) is the password and its salt

// salt / hash creation - returned SALT & HASH are inserted into user MySQL table
function hash_password($password)
    {
    $return_array=array();

    $salt = mcrypt_create_iv(32, MCRYPT_DEV_RANDOM);
    $hexsalt = bin2hex($salt);

    $pass_hash = hash('sha256', $password . $hexsalt);

    $return_array['SALT'] = $hexsalt;
    $return_array['HASH'] = $pass_hash;
    return $return_array;
    }

(Note, the salt is unique and specific to each user if is is not clear from the above.)

/*
<input type='text' name='school_login_id'>
<input type='text' name='admin_login_id'>
<input type='password' name='admin_password'>

login form above, inouts from $_POST are checked for SQL inject before being passed to the function below to validate login

*/

function validate_login_details($school_login_id, $admin_login_id, $admin_password)
    {
    global $schools_table, $admin_users_table;
    $return_result = false; // invalid unless proven otherwise

    // find user and their pass hash and salt
    $query = "select S.school_id, pass_hash, pass_salt
        from $schools_table as S join $admin_users_table as A using(school_id)
        where S.login_name = '$school_login_id' and A.username ='$admin_login_id'";

    log_this($query, "loginQueries.log"); // temp debug

    $login_res = query_db($query); // wrapper function for MYSQL_QUERY - yes, i will stop using this i promise!
    if (mysql_num_rows($login_res) == 1)
        {
        $db_pass_hash = mysql_result($login_res, 0, "pass_hash");
        $db_pass_salt = mysql_result($login_res, 0, "pass_salt");

        // re-create hash from supplied password and compare to d/b
        $hash_from_entered_pass = hash('sha256', $admin_password . $db_pass_salt);
        if ($hash_from_entered_pass == $db_pass_hash)
            {
            $return_result = true;
            }
        }
    else
        {
        log_this("mysql_num_rows(\$login_res) not 1 row", "loginfails.log"); // temp debug
        }

    return $return_result;
    }

Before data is passed to  validate_login_details() it is checked against these regexps:

School and user login ID:

    if (preg_match("/[^-a-z0-9_]/i", $text) )
        {
            $error_count++;
        }

Password:

$match_list = "\x{20}-\x{5f}\x{61}-\x{7e}"; // basic ascii chars excluding backtick
$match_list .= "\x{a1}-\x{ff}"; // extended latin 1 chars excluding control chars
$match_list .= "\x{20ac}\x{201c}\x{201d}"; // euro symbol & left/right double quotation mark (from Word)
$match_list .= "\x{2018}\x{2019}"; // left/right single quotation mark (from word)

if (preg_match("/[^$match_list]/u", $text) )
    {
    $error_count++;
    }

Is this code correct and secure? I have seen many more complex has generation functions, but given that there are no credit cards or personal details involved, is this robust enough?


texts: Insert a digit to maximize the given number

texts:
Was asked in an interview today -

You are given an integer (in finite range [-N, N]) and you wish to maximize the number by inserting somewhere the digit '5'.

My solution - the idea here is going from left to right and checking if the digit is bigger than 5 or not. The first time you reach one that isn't you insert the 5 there. With the exception of negative numbers where you check and do the opposite.

I did it by converting ints to strings and vice versa.

def solution(N):
    array = str(N)
    result = []
    mod = 1
    for i in range(len(array) + 1):
        if i == len(array):
            result.append('5')
            break

        if array[i] == '-':
            mod = -1
            result.append(array[i])
            continue

        if int(array[i]) * mod > 5 * mod:
            result.append(array[i])
        else:
            result.append('5')
            result.append(array[i:])
            break

    return int("".join(result))

So - solution(128) will output 5128; solution(0) will output 50, solution(-74) will output -574 etc.


texts:
This is my attempt at an alphabet cypher in Rust. I'm unsure if iteration and pushing to a mutable is the best way to handle building the output; it seems like a good candidate for a map but I can't figure out how to do it. Can anyone help?

use std::env;

fn main() {
    let keyword = env::args().nth(1).unwrap();
    let body = env::args().nth(2).unwrap();
    let transpose_table = get_transpose_table(keyword);

    let mut output = String::new();
    for (input_idx, input_char) in body.char_indices() {
        let transpose_distance = transpose_table[input_idx % transpose_table.len()];
        let transposed_char_idx = char_to_alpha_idx(input_char) + transpose_distance;
        output.push(alpha_idx_to_char(transposed_char_idx % 26));
    }

    println!("{}", output);
}

fn get_transpose_table(keyword: String) -> Vec<usize> {
    return keyword.chars()
                  .map(|character| char_to_alpha_idx(character))
                  .collect();
}

fn char_to_alpha_idx(character: char) -> usize {
    return "abcdefghijklmnopqrstuvwxyz".find(character)
                                       .expect("Bad char for char_to_alpha_idx");
}

fn alpha_idx_to_char(loc: usize) -> char {
    return "abcdefghijklmnopqrstuvwxyz".chars()
                                       .nth(loc)
                                       .expect("Bad loc for alpha_idx_to_char");
}


texts:
I created a plot on which the y value is visible with the marker.
What's your opinion ?
I wonder if I could have done something simpler.

(code should run in a Jupyter notebook)

%matplotlib inline
fig = plt.figure()
axes = fig.add_axes((1,1,1,1))

X = np.array([3,3.2,3.5,3.8,3.9,5,5.5,5.8,5.9,5])
y = np.array([1,1,1,1,1,2,2,2,2,2])

markers = ['^', 'o']
for k, m in enumerate(markers):
   i = (y == k+1)
   flat = [1 for val in y[i]]
   axes.scatter(X[i], flat, marker=m)

axes.set_xlim([2,7])
axes.set_ylim([0,3])

The result:


texts: Can this code utilizing promises be written more succinctly?

texts:
I've written the following code to get all .txt files in a directory and read+delete them, repeating every 15 seconds.

var fs = require("fs");
var path = require("path");
var Q = require("q");
var dir = "stuff";

var analyseFile = function(fileData, callback) { ... }; // Not important.

var deleteFile = function(filePath, callback) { ... }; // Not important.

var processStuffDir = function() {
  Q.nfcall(fs.readdir, dir).then(function(files) {
    return Q.all(
      files.filter(function(file) {
        return path.extname(file) === ".txt";
      }).map(function(file) {
        var filePath = path.join(dir, file);
        return Q.nfcall(fs.readFile, filePath).then(function(data) {
          return Q.nfcall(analyseFile, data.toString());
        }).then(function() {
          return Q.nfcall(deleteFile, filePath);
        });
      })
    );
  }).then(function() {
    setTimeout(processStuffDir, 15000);
  });
};

processStuffDir();

This works, but it's my first foray into using promises. So my question is, can this be re-written in a simpler/more succinct manner? More chaining of promises would be nice, if possible.


texts: Computing the item price and vat for a given pricing, order, and exchange rate

texts:
How can I improve the readability of the below function using a list comprehension?
Also, is there a way to improve items() performance?
pricing = {'prices': [{'product_id': 1, 'price': 599, 'vat_band': 'standard'},
                      {'product_id': 2, 'price': 250, 'vat_band': 'zero'},
                      {'product_id': 3, 'price': 250, 'vat_band': 'zero'}],
           'vat_bands': {'standard': 0.2, 'zero': 0}}
order = {'order': {'id': 12, 'items': [{'product_id': 1, 'quantity': 1}, {'product_id': 2,'quantity': 5}]}}
exchange_rate = 1.1

def items():
    """
    computes the item price and vat for a given pricing, order, and exchange rate.
    returns list of items dictionaries
    """
    return [{'product_id': item['product_id'],
             'quantity': item['quantity'],
             'price': round(product['price'] * exchange_rate, 2),
             'vat': round(pricing['vat_bands']['standard'] * product['price'] * exchange_rate, 2)}
            if product['vat_band'] == 'standard' else
            {'product_id': item['product_id'],
             'quantity': item['quantity'],
             'price': round(product['price'] * exchange_rate, 2),
             'vat': 0}
            for item in order['order']['items'] for product in pricing['prices']
            if item['product_id'] == product['product_id']]

print(items())

Output:
[{'product_id': 1, 'quantity': 1, 'price': 658.9, 'vat': 131.78},
 {'product_id': 2, 'quantity': 5, 'price': 275.0, 'vat': 0}]


texts: Extracting keywords from 3 billion CSV records

texts:
I am processing around 3 billion records using this piece of code. It's pretty slow; it would be really helpful if you could suggest better ways to do this.

'''
Created on 27-Mar-2015
@author: siddarth
'''

import rake
import multiprocessing as mp
import time
import os
import csv

filename = 'Large_Input_File.csv'
outName = 'Large_Output_File.csv'
BYTES_PER_MB = 1048576

start = time.time()
def elapsed():
    return time.time() - start

''' Worker function used to call rake
    This method basically calls the rake class which returns a
    list of keywords, also each process
    writes to a different output file'''

def fileparser_worker(filename, start, end, c):
    outFileName = outName + str(c)
    outFile = open(outFileName,'w')
    with open(filename) as inFile:
        inFile.seek(start)
        lines = inFile.readlines(end-start)
        for line in lines:
            title = line.split('\t')
            try:
                keywords = rake.execute_rake(title[2])
            except:
                print('Index out of bound error due to NULL Values')
                continue
            for keyword in range(0,len(keywords)):
                outFile.write(keywords[keyword][0] + '\n')
    outFile.close()

if __name__ == '__main__':
    start = time.time()
    chunk_start = 0
    chunk_size =  512 * BYTES_PER_MB
    chunk_end = 512 * BYTES_PER_MB

    filesize = os.path.getsize(filename)

    print '\n%.3fs: file has %s rows' % (elapsed(), filesize)

    c = 0
    pause = 0
    iterations = (filesize / chunk_size) + 1
    ''' Chunk the file '''
    print(iterations)
    with open(filename) as inFile:
        while c < iterations:
            if chunk_start + chunk_size > filesize:
                chunk_end = filesize
            else:
                chunk_end = chunk_start + chunk_size

            inFile.seek(chunk_end)
            line = inFile.readline()

            if line == '':
                continue
            else:
                chunk_end = inFile.tell()

            print("Start chunk",chunk_start)
            ''' Initializing Processes '''
            proc = mp.Process(target=fileparser_worker, args = (filename,chunk_start,chunk_end, c) )
            proc.start()
            pause += 1
            print("End chunk",chunk_end)
            chunk_start = chunk_end
            c += 1

            ''' Making sure that there are atmost 4 processes
                running at a single point of time,
                cause I have a 4 core machine'''

            if pause == 4:
                proc.join() # Waits for processes to close
                pause = 0

    proc.join() # Close off any running processes
    print("TOTAL TIME TAKEN",elapsed())

Below are some metrics which may help you to understand what's going on under the hood.

File Size = 18GB

Usage Metrics:
CPU Usage = 99% ( Using 4 Processes )
RAM Usage = 30% ( May be I can use more RAM to improve performance ? )

I am not familiar with multiprocessing. I've learned about it today and wrote some sample code based on what I understood.


texts: Implementing Linked lists in Python from scratch

texts:
After finishing my ds and algorithms course I wanted to implement what I've learned through the semester so here is my try for Linked lists, both regular (one way) and double one (two way).

code:

from node import ListNode

class LinkedList():
    _length = 0

    ''' Init linked list '''
    ''' double is boolean '''
    def __init__(self, x, doubly=False):
        if x is not None:
            self.head = ListNode(x, doubly)
            self.tail = self.head
            self._length += 1
        else:
            assert False, 'User entered a None value'

    ''' representing the list '''
    def __str__(self, doubly=False):
        st = ''
        arrow = ' <-> ' if doubly else ' -> '
        p = self.head
        while p is not None:
            st += str(p.key)
            p = p.next
            if p is not None:
                st += arrow
        return st

    ''' insert to the end of the list '''
    def insert(self, x, doubly=False):
        if self.head is None:
            self.__init__(x)
            return
        p = self.head
        new_node = ListNode(x, doubly)
        self.tail.next = new_node
        if doubly:
            new_node.prev = self.tail
        self.tail = new_node
        self._length += 1

    ''' insert to the head of the list '''
    def insert_to_head(self, x, doubly=False):
        new_node = ListNode(x, doubly)
        new_node.next = self.head
        if doubly:
            self.head.prev = new_node
        self.head = new_node
        self._length += 1

    ''' delete from list and fix pointers '''
    def delete(self, x, doubly=False):
        ''' deleting first instance of x '''
        # if list is empty
        if self.head is None:
            raise Exception('List is empty')
        # else..
        p = self.head
        # if head is x, delete and fix
        if p.key == x:
            if len(self) > 1:
                if doubly:
                    p.next.prev = None
                self.head = p.next
                self._length -= 1
            else:
                self.head, self.tail = None, None
                self._length -= 1
                return
            del p
            return
        # regular delete from list
        while p.next is not None and p.next.key != x:
            p = p.next
        if p.key != x:
            return None
        tmp = p.next  # grab Node contains `x`
        if self.tail is tmp:
            self.tail = p
        p.next = p.next.next
        if doubly:
            p.next.next.prev = p
        del tmp
        self._length -= 1

    ''' search (linear time O(n)) in list '''
    def search(self, x):
        if self.head is None:
            return None
        p = self.head
        if p.key == x:
            return p
        while p.key != x and p.next is not None:
            p = p.next
        return p if p.key == x else None

class DoublyLinkedList(LinkedList):

    _length = 0

    ''' Init double linked list '''
    def __init__(self, x):
        super().__init__(x, True)

    ''' string with doublt linkedlist '''
    def __str__(self):
        return super().__str__(True)

    def __len__(self):
        return self._length

    def insert(self, x):
        super().insert(x, True)

    def insert_to_head(self, x):
        super().insert_to_head(x, True)

    def delete(self, x):
        super().delete(x, True)

    def search(self, x):
        return super().search(x)

the Node class:

class ListNode():
    def __init__(self, x, double=False):
        self.key = x
        self.next = None
        if double:
            self.prev = None

    def __str__(self):
        try:
            return str(self.key)
        except AttributeError:
            return 'No key for this Node'

thanks in advance for you code review!

Things I want to check:

is the code is understandable?
is it well organized?
is the implementation using abstract class is good or there are conventions I missed/etc ?
any other suggestions?


texts:
The task:

  Given an array of integers in which two elements appear exactly once
  and all other elements appear exactly twice, find the two elements
  that appear only once.

  For example, given the array [2, 4, 6, 8, 10, 2, 6, 10], return 4 and
  8. The order does not matter.

  Follow-up: Can you do this in linear time and constant space?

const lst = [2, 4, 6, 8, 10, 2, 6, 10];

My functional solution

const findUnique = lst => lst
  .sort((a,b) => a - b)
  .filter((x, i) => lst[i-1] !== x && lst[i+1] !== x);

console.log(findUnique(lst));

My imperative solution:

function findUnique2(lst) {
  const res = [];
  const map = new Map();
  lst.forEach(x => map.set(x, map.get(x) === undefined));
  map.forEach((val, key) => {
    if(val) { res.push(key); }
  });
  return res;
}

console.log(findUnique2(lst));

I think the imperative solution is in linear time but not constant space. How would you do it with constant space?


texts: String Matching w/o repeating the comparisons for common part of the two strings

texts:
In an attempt to think up a more efficient String Matching algorithm than the naïve \$O(n \cdot k)\$ one I came up with a slightly modified approach.

In my algorithm (code in Java), I tried a little modification of the \$O(n \cdot k)\$ approach where every time a character match starting from i fails after k positions, we start from i+1th place.

In this algo however, if matching fails at k position, I resume comparison from k-1 because we know up to k-1 the characters are common.

Below is the implementation of this approach.

I will really appreciate anyone taking a look into the code and

Confirm if things work the way I explained. My tests seem to be working fine.
What is the complexity of this approach? Is it worst case \$O(n \cdot k)\$ still?
An example of a worst case input.

Code:

public class ModifiedSearch {
    private String text;

    public ModifiedSearch(String text) {
        this.text = text;
    }

    public int findPattern(String pattern) {
        int textLength = text.length();
        int patLength = pattern.length();
        int common = 0;
        boolean broken = false;

        for (int tIndex = 0; tIndex <= textLength - patLength; broken = false, tIndex++) {
            int k = 0;

            while (tIndex + common + k < textLength && common + k < patLength) {

                if (text.charAt(tIndex + common + k) != pattern.charAt(common + k)) {
                    broken = true;
                    common = (common + k - 1 < 0) ? 0 : common + k - 1 ;
                    break;
                }

                k++;
            }

            if (!broken && common + k == patLength) {
                return tIndex;
            }
        }

        return -1;
    }
}

I have tried this with a combination of inputs large and small, but this does not seem to worse out to \$O(n \cdot k)\$. Any help greatly appreciated.


texts:
There are many ways to shuffle lists; for example, Racket's built-in shuffle assigns each list element with a random number as a sort key, then sorts the list, which provides an O(n log n) runtime. However, I'd like something that's O(n), and that's where Fisher-Yates comes in.

Fisher-Yates is designed for use with random-access data structures, like vectors. It will not behave efficiently for lists, unless copied to a vector first. That's what my implementation does. However, I micro-optimised my version in a couple of ways:

Instead of doing the normal swap (val = v[j]; v[j] = v[i-1]; v[i-1] = val), I simply do the equivalent of val = v[j]; v[j] = v[i-1]; yield val. I don't care about the values of the vector after i-1 at each iteration, so there's no point in updating the value of v[i-1]. I've described this implementation strategy here.
In accumulating each shuffled value into the result list directly, I skip the vector->list call.

Of course, these optimisations are minor; the runtime is still O(n). Anyway, here's the code (requires SRFI 27 for the random-integer procedure):

(define (fisher-yates-shuffle lst)
  (define vec (list->vector lst))
  (let loop ((result '())
             (i (vector-length vec)))
    (if (zero? i)
        result
        (let* ((j (random-integer i))
               (val (vector-ref vec j)))
          (vector-set! vec j (vector-ref vec (- i 1)))
          (loop (cons val result) (- i 1))))))

I'm looking for ways to make the code faster and/or more elegant, but correctness and performance are my top priorities. If there are ways to write this in a better style without impacting performance or correctness, I'd love to hear about those too.

My code was initially written in Racket, which you're welcome to critique too:

(define (fisher-yates-shuffle lst)
  (define vec (list->vector lst))
  (for/fold ((result '()))
            ((i (in-range (vector-length vec) 0 -1)))
    (define j (random i))
    (define val (vector-ref vec j))
    (vector-set! vec j (vector-ref vec (sub1 i)))
    (cons val result)))

(Note: using for/fold instead of for/list is a micro-optimisation: I don't care if the shuffled list is reversed, so using for/fold skips the reverse step that for/list uses behind the scenes.)


texts:
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
  count the number of ways it can be decoded.

  For example, the message '111' would give 3, since it could be decoded
  as 'aaa', 'ka', and 'ak'.

  You can assume that the messages are decodable. For example, '001' is
  not allowed.

class DailyCodingProblem7 {

    public static void main(String args[]) {
        String message = "11111111";
        int n=message.length();
        Integer[] ways=new Integer[n+1];
        int res = solution(message,n,ways);
        System.out.println(res);

    }

    private static int solution(String message,int k,Integer[] ways) {
        int n=message.length();
        if(k==0)
        {
            return 1;
        }
        if((int)message.charAt(n-k)==0)
        {
            return 0;
        }

        if(ways[k]!=null)
        {
            System.out.println(k+" : " +ways[k]);
            return ways[k];
        }
        ways[k]=solution(message,k-1,ways);
        if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
        ways[k]+=solution(message,k-2,ways);
        return ways[k];

    }

}

If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?

1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34


texts: Creating new CSS element everytime database updates

texts:
I have created a function using jQuery Ajax which create a new CSS element whenever I update the database using a form.

Is it ok?  If not, hat can be the best method to do it?

$(document).ready(function(){
    $('#statusupdater').submit(function(e) {
        updatestatus();
        e.preventDefault();
    });
});

function updatestatus()
{
$.ajax({
    type: "POST",
    url: "statusupdate.php",
    data: $('#statusupdater').serialize(),
    dataType: "dataString"
});
$('#statuscontainer').prepend( $('
').load('statusupdate.php'));
$("#statusupdater")[0].reset();
    $('.statuspop').fadeOut(300);
            $('#opacify').hide();
}

statusupdate.php

<?php include "dbcon.php";

 $status=$_POST['status'];
 $photo=$_POST['photoupload'];

 if ($status || $photo)
 {
    $date = date('m/d/Y h:i:s');
    $statusinsert = mysqli_query($con,"INSERT INTO status (st_id,statu,date_created,userid) VALUES ('','$status','$date','$id')" );
 }

 $selectstatus = mysqli_query($con,"select * from status where userid = '".$id."' order by st_id desc limit 1");
 $getstatus=mysqli_fetch_array($selectstatus);
 ?>

<?php echo $getstatus["userid"];?>

<?php echo $getstatus["statu"];?>


texts: Remapping and interpolating 255x1024 array

texts:
I have a function that accepts a \$255\times1024\$ array and remaps it to another array in order to account for some hardware related distortion (lines that should be straight are curved by the lens). At the moment it does exactly what I want, but slowly (roughly 30 second runtime).

Specifically, I'm looking at the nested for loops that take 18 seconds to run, and the interpolation that takes 10s. Is there any way to optimize/speed up this process?

EDIT: Nested for loops have been optimized as per vps' answer. Am now only interested in optimizing the interpolation function (if that's even possible).

def smile(Z):
    p2p = np.poly1d([ -3.08049538e-07,   3.61724996e-04,  -7.78775408e-02, 3.36876203e+00])
    Y = np.flipud(np.rot90(np.tile(np.linspace(1,255,255),(1024,1))))
    X = np.tile(np.linspace(1,1024,1024),(255,1))
    for m in range(0,255):
        for n in range(0,1024):
            X[m,n] = X[m,n] - p2p(m+1)
    x = X.flatten()
    y = Y.flatten()
    z = Z.flatten()
    xy = np.vstack((x,y)).T
    grid_x, grid_y = np.mgrid[1:1024:1024j, 1:255:255j]
    newgrid = interpolate.griddata(xy, z,(grid_x,grid_y), method = 'linear',fill_value = 0).T
    return newgrid


texts:
I just wrote this password validation code function that checks to see if a password will be accepted in AD or not. I'm not sure this is the best way to do it, but for now it works fine. I would love some suggestions on how to make it better.

public String validateNewPass(String pass1, String pass2){
        StringBuilder retVal = new StringBuilder();

        if(pass1.length() < 1 || pass2.length() < 1 )retVal.append("Empty fields
");

        if (pass1 != null && pass2 != null) {

            if (pass1.equals(pass2)) {
                logger.info(pass1 + " = " + pass2);

                pass1 = pass2;
                boolean hasUppercase = !pass1.equals(pass1.toLowerCase());
                boolean hasLowercase = !pass1.equals(pass1.toUpperCase());
                boolean hasNumber = pass1.matches(".*\\d.*");
                boolean noSpecialChar = pass1.matches("[a-zA-Z0-9 ]*");

                if (pass1.length() < 11) {
                    logger.info(pass1 + " is length < 11");
                    retVal.append("Password is too short. Needs to have 11 characters
");
                }

                if (!hasUppercase) {
                    logger.info(pass1 + " <-- needs uppercase");
                    retVal.append("Password needs an upper case
");
                }

                if (!hasLowercase) {
                    logger.info(pass1 + " <-- needs lowercase");
                    retVal.append("Password needs a lowercase
");
                }

                if (!hasNumber) {
                    logger.info(pass1 + "<-- needs a number");
                    retVal.append("Password needs a number
");
                }

                if(noSpecialChar){
                    logger.info(pass1 + "<-- needs a specail character");
                    retVal.append("Password needs a special character i.e. !,@,#, etc.
");
                }
            }else{
                logger.info(pass1 + " != " + pass2);
                retVal.append("Passwords don't match
");
            }
        }else{
            logger.info("Passwords = null");
            retVal.append("Passwords Null
");
        }
        if(retVal.length() == 0){
            logger.info("Password validates");
            retVal.append("Success");
        }

        return retVal.toString();

    }

**Note: These lines are to ensure a different case to handle a null vs empty string

if(pass1.length() < 1 || pass2.length() < 1 )retVal.append("Empty fields
");

        if (pass1 != null && pass2 != null) {


texts: Finding the number of inversions in an Array

texts:
I am doing a college assignment where I have to count the number of inversions in an array/list. An inversion is defined as a tuple where i<j and a[i]>a[j]. For example in this array

val arr = Array(3, 1, 2, 4)

The inversions are (3,1), (3,2). So total count of inversions is 2.

I wrote a divide and conquer algorithm to find this. it works for small arrays. but for large inputs like this one

https://github.com/abhsrivastava/ArrayInversions/blob/master/src/main/resources/inversions.txt

there is always an out of memory error. My code is below

import scala.io.Source
import Sort._

object CountInversions extends App {
  val data = Source.fromResource("inversions.txt").getLines.map(_.toInt).toList
  val inversions = countInversions(data)
  println(s"number of inversions ${inversions}")

  def countInversions(input: List[Int]): Int = {
    input match {
      case Nil => 0
      case List(a) => 0
      case _ =>
        val mid = input.size / 2
        val left = input.slice(0, mid)
        val right = input.slice(mid, input.size)
        val l1 = countInversions(left)
        val l2 = countInversions(right)
        val l3 = splitInversions(left, right)
        l1 + l2 + l3
    }
  }

  // assuming l1 and l2 are almost of same size.
  // total complexity 2(nlogn + n)
  def splitInversions(l1: List[Int], l2: List[Int]): Int = {
    val sortedL1 = mergeSort(l1) // nlogn
    val sortedL2 = mergeSort(l2) // nlogn
    (sortedL1, sortedL2) match {
      case (Nil, Nil) => 0
      case (Nil, _) => 0
      case (_, Nil) => 0
      case (_, _) if sortedL1.head > sortedL2.head =>
        val result = splitInversions(sortedL1, sortedL2.tail)
        sortedL1.size + result
      case (_, _) =>
        splitInversions(sortedL1.tail, sortedL2)
    }
  }
}

I am not posting the code for mergeSort here. it is just a simple merge sort.

My objective is to be able to determine the inversions in O(nlogn) time and be able to process the large file. I also want to keep my code functional.

How can I optimize my code?


texts:
I'm developing a small craps game in C++, and my C++ skills are a bit rusty.  I really need someone to review my code to ensure that I have correctly implemented the game according to the rules.

Game rules:

  The player or shooter rolls a pair of standard dice

  If the sum is 7 or 11 the game is won
  If the sum is 2, 3 or 12 the game is lost
  If the sum is any other value, this value is called the shooter’s point and he
  continues rolling until he rolls a 7 and loses or he rolls the point again in which
  case he wins

  If a game is won the shooter plays another game and continues playing until he
  loses a game, at which time the next player around the Craps table becomes the
  shooter

My code:

#include <iostream>
#include <ctime>

using namespace std;

bool checkWinning(int roll);

int main(int argc, const char * argv[])
{
    //create player aka shooter

    //create pair of dice
    unsigned int dice1=0;
    unsigned int  dice2 = 0;

    //create roll
    unsigned int roll = 0;

    //create game loop
    while(checkWinning(roll) == true)
    {
        dice1 =  rand() % 6 + 1;
        dice2  = rand() % 6 + 1;
        roll = dice1 + dice2;

        cout<< dice1<<" +"<< dice2<<" = "<<  roll << endl;
        //cout<< checkWinning(2) <<endl;
    }

    return 0;
}

bool checkWinning(int roll)
{
    bool winner  = true;
    if( roll == 2 || roll == 3 || roll == 12)
        return winner= false;
    else
        if(roll == 7 || roll == 11 )
        return winner;
    else
        return winner;
};


texts: Code duplication when converting DTO to String messages

texts:
In a payment application a day before and at the same time with some payments some messages(email) needs to be sent.
I have a DTO (called EscrowPayment, projected from some entity) from which I generate and send two similar `messages.

I look for advice specifically on the following issues with the code I ended up:

Copy-pasted code.
Type suffix in identifiers. eg: nominalAmountStr
Static utility methods formatInteger etc (Used application wide).
String constants in code. But because they are parameterized by position and not by name; if I extract them to a configuration file as they are,
I wouldn't know in which order I should be giving parameters to String.format.

Here is the code; it is sanitized and translated, but issues are clearly identifiable:

public class EscrowPaymentMessageServiceImpl {

    private JavaMailSender mailSender;

    // .....

    @Override
    public void escrowPaymentWillBeDone(EscrowPayment escrowPayment) throws BusinessLayerException {
        try {
            String nominalAmountStr = formatInteger(new BigDecimal(escrowPayment.getNominal()));
            String paymentDateStr = dateFormat(escrowPayment.getPaymentDate(), "dd/MM/yyyy");
            String interestRateStr = format(escrowPayment.getInterestRate(), "0.00###");
            String paymentAmountStr = format(escrowPayment.getPaymentAmount());
            String messageText = String
                    .format("BLAH BLAH some security with ID %s of nominal value EUR %s "
                            + "at date %s BLAH your account with number 1234567890 will be debited to pay "
                            + "EUR %s coupon payment for %%%s interest.",
                            escrowPayment.getSecurityId(), nominalStr, paymentDateStr,
                            interestRateStr, paymentAmountStr);

            sendMessage(messageText);
        } catch (MessagingException e) {
            getLog().error("An error occured while sending the email:", e);
            throw new BusinessLayerException("EscrowPaymentMessage.MessageCouldNotBeSent", e);
        }
    }

    @Override
    public void escrowPaymentIsDone(EscrowPayment escrowPayment) throws BusinessLayerException {
        try {
            String nominalAmountStr = formatInteger(new BigDecimal(escrowPayment.getNominal()));
            String paymentDateStr = dateFormat(escrowPayment.getPaymentDate(), "dd/MM/yyyy");
            String paymentAmountStr = format(escrowPayment.getPaymentAmount());
            String messageText = String.format("BLAH BLAH at date %s the security with ID %s of nominal value EUR %s "
                            + "BLAH your account with number 1234567890 has been debited to pay EUR %s." ,
                            paymentDateStr, escrowPayment.getSecurityId(), nominalStr, paymentAmountStr);

            sendMessage(messageText);
        } catch (MessagingException e) {
            getLog().error("An error occured while sending the email:", e);
            throw new BusinessLayerException("EscrowPaymentMessage.MessageCouldNotBeSent", e);
        }
    }

    private void sendMessage(messageText) throws MessagingException {
        //....
    }

}


texts: Reordering items which must have alphabetically ordered keys

texts:
I have a list of objects each with a unique Key and a display name (Label). The list needs to remain sorted by the keys of each object but unfortunately the keys need to be strings rather than numerical and as such 'sorted' here refers to the keys being sorted alphabetically rather than numerically. (Although the keys can be string of numbers - their actual string values don't matter so long as they're alphabetically ordered).

The list should be re-order-able but then the keys need to re-shuffle so that they're once more in alphabetical order.

Currently my implementation allows for the re-ordering of the list and then iterates over all of the objects re-assigning them fresh keys in alphabetical order - something which I feel is a bad idea as it's a lot of effort for a single swap of values.

My object looks like the following

class Item
{
    public string Key { get; set; }
    public string Label { get; set; }

    public Item(string key, string label)
    {
        Key = key;
        Label = label;
    }

    public override string ToString() => Key + ", " + Label;
}

I have added an extension method to handle the re-ordering process

static class Utils
{
    public static List<Item> MoveIndex(this List<Item> myItems, int from, int to)
    {
        Item temp = myItems[from];
        myItems.RemoveAt(from);
        myItems.Insert(to, temp);

        for (int i = 0; i < myItems.Count; i++)
        {
            myItems[i].Key = i.ToString("D2");
        }

        return myItems;
    }
}

And finally I have an example usage of the extension method

static void Main(string[] args)
{
    List<Item> myItems = new List<Item>()
    {
        new Item("0", "Zero"),
        new Item("1", "One"),
        new Item("2", "Two"),
        new Item("3", "Three"),
        new Item("4", "Four"),
        new Item("5", "Five"),
        new Item("6", "Six"),
        new Item("7", "Seven"),
        new Item("8", "Eight"),
        new Item("9", "Nine"),
        new Item("10", "Ten"),
        new Item("11", "Eleven"),
        new Item("12", "Twelve"),
    };

    myItems.MoveIndex(3, 5);

    Console.ReadKey();
}

As the code currently sits, placing a breakpoint on the Console.ReadKey() shows that the Labels are not in their original order but the Keys are - proving that it currently works.

Are there any better ways to manage the Keys when the list is being re-ordered? Perhaps ways which don't require iterating over everything in the list?

Are there any better strings which I could be using for the keys?

I know that as it sits this system has a capacity for only 100 Items before it breaks and that is OK - There will be checking in place to ensure that there are never more than this.


texts:
I just finished writing this Python script to calculate daily additions and subtractions from my git log to use in making pretty graphs. This is a rewrite of something I wrote previously in Perl. I have made an attempt to clean it up, but I feel that some of my list comprehensions are messy to say the least, and I'm abusing certain Python features.

#!/usr/bin/env python
# get-pmstats.py
# Henry J Schmale
# November 25, 2017
#
# Calculates the additions and deletions per day within a git repository
# by parsing out the git log. It opens the log itself.
# Produces output as a CSV
#
# This segments out certain file wildcards

import subprocess
from datetime import datetime
from fnmatch import fnmatch

def chomp_int(val):
    try:
        return int(val)
    except ValueError:
        return 0

def make_fn_matcher(args):
    return lambda x: fnmatch(''.join(map(str, args[2:])), x)

def print_results(changes_by_date):
    print('date,ins,del')
    for key,vals in changes_by_date.items():
        print(','.join(map(str, [key, vals[0], vals[1]])))

EXCLUDED_WILDCARDS = ['*.eps', '*.CSV', '*jquery*']

changes_by_date = {}
git_log = subprocess.Popen(
    'git log --numstat --pretty="%at"',
    stdout=subprocess.PIPE,
    shell=True)

date = None
day_changes = [0, 0]
for line in git_log.stdout:
    args = line.decode('utf8').rstrip().split()
    if len(args) == 1:
        old_date = date
        date = datetime.fromtimestamp(int(args[0]))
        if day_changes != [0, 0] and date.date() != old_date.date():
            changes_by_date[str(date.date())] = day_changes
            day_changes = [0, 0]
    elif len(args) >= 3:
        # Don't count changesets for excluded file types
        if True in map(make_fn_matcher(args), EXCLUDED_WILDCARDS):
            continue
        day_changes = [sum(x) for x in zip(day_changes, map(chomp_int, args[0:2]))]
print_results(changes_by_date)


texts:
Problem Statement

  The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

  Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

  Input Format

  The first line of the input contains T, the number of test cases. Each test case contains two lines.
  The first line of each test case contains two space-separated integers, N and K.
  The next line contains N space-separated integers, \$a_1,a_2,…,a_N\$, representing the arrival time of each student.

  If the arrival time of a given student is a non-positive integer (\$a_i≤0\$), then the student enters before the class starts. If the arrival time of a given student is a positive integer (\$a_i>0\$), the student enters after the class has started.

  Output Format

  For each testcase, print "YES" (without quotes) if the class gets cancelled and "NO" (without quotes) otherwise.

  Constraints

  $$\begin{align}
1&≤T≤10,\\
1&≤N≤1000,\\
1&≤K≤N,\\
−100&≤a_i≤100, \text{where}\ i∈[1,N]
\end{align}$$

  Note

  If a student enters the class exactly when it starts (\$a_i=0\$), the student is considered to have entered before the class has started.

  Sample Input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

  Sample Output

YES
NO

Solution

def is_on_time(a):
    return a <= 0

def class_cancelled(expected, arrival_times):
    actual = map(lambda x: 1 if is_on_time(x) else 0, arrival_times).count(1)
    return actual >= expected

def read_int():
    return int(raw_input())

def read_ints():
    return map(int, raw_input().strip().split())

if __name__ == '__main__':
    T = read_int()
    for _ in xrange(T):
        N, K = read_ints()
        A = read_ints()
        print "NO" if class_cancelled(K, A) else "YES"


texts: Bash script to share snippets of code using rsync

texts:
I just got through writing a bash script so my friend and I can share snippets of code to a central file via rsync and ssh. What it does is this;

Sets up ssh public key auth if not already working.
Makes a local "snippet file" using rsync to copy an exiting file from remote server.
Allows the user to edit the snippet file.
If user chooses, sync snippet file to remote host.

I put the project on github at https://github.com/shakabra/snippetShare

It's a pretty straight-forward script, but I wonder what could be done better.

I am really new at programming and was hoping you guys might spot some obvious mistakes that I just over-looked or don't understand.

#!/bin/bash
SERVER="dakinewebs.com"
UN=""
PORT="22"
TIME=$(date +"%c")
localSnippetFile=$HOME/snippetFile.html
remoteSnippetFile=/home/shakabra/dakinewebs.com/snippetShare/snippetFile.html

checkSsh () {
    ssh -o BatchMode=yes "$UN"@"$SERVER" 'exit'
    if [[ $? = 255 ]]; then
        echo "Local key doesn't exits"
        echo "creating local key"
        ssh-keygen -t rsa
        ssh-add
        uploadKey
    fi
}
sshConfig () {
    if [[ -z $SERVER ]]; then
        echo -e "SERVER NAME:\n"
        read SERVER
    fi

    if [[ -z $UN ]]; then
        echo -e "USERNAME:\n"
        read UN
    fi

    if [[ -z $PORT ]]; then
        echo -e "PORT:\n"
        read PORT
    fi
}
makeLocalSnippet () {
    echo "syncing with remote snippet"
    rsync -avz --progress -e ssh "$UN"@"$SERVER":"$remoteSnippetFile" "$localSnippetFile"
}

editSnippet () {
    echo -e "What's the title of the snippet?\n"
    read snippetTitle
    echo -e "<time>"$TIME"</time>\n" >> "$localSnippetFile"
    echo -e ""$snippetTitle"" >> "$localSnippetFile"
    echo "

" >> "$localSnippetFile"
    nano "$localSnippetFile"
    syncSnippet
        while [[ $? = 1 ]]; do
            syncSnippet
        done
}
syncSnippet () {
    read -p "Sync snippet file now [y/n]: " syncNow
    case $syncNow in
        y|Y|yes|YES|Yes)
        rsync -av --delete -e ssh "$localSnippetFile"  "$UN"@"$SERVER":"$remoteSnippetFile"
    ;;
        n|N|no|No|NO)
        echo "Guess we'll sync next time. Hope it wasn't too important!"
    ;;
        *)
        echo "not an answer"
        return 1
    ;;
    esac
}
uploadKey ()
{
    ssh-copy-id "$UN"@"$SERVER"
    ssh "$UN"@"$SERVER" 'exit'
    echo "Key uploaded"
}
sshConfig
checkSsh
makeLocalSnippet
editSnippet


texts:
I was finding myself frequently calling getApplication() and casting it as MyApplication so that I could call a method in MyApplication.  I decided to declare the static variable Current in MyApplication and set it in the constructor.  Now I don't have to do the casting.

Are there any pitfalls to taking this approach?

public class MyApplication extends Application {
    public static MyApplication Current;
    public MyApplication(){
        super();
        Current = this;
    }
    public void doSomething(){

    }
}

public class MyActivity extends ListActivity {
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        MyApplication.Current.doSomething();
    }
}

Below is, I think, the normal approach for getting the application and calling the method.

public class MyApplication extends Application {
    public void doSomething(){

    }
}

public class MyActivity extends ListActivity {
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        ((MyApplication)getApplication()).doSomething();
    }
}


texts: Computing intersection of 2D infinite lines

texts:
I wrote a small program to compute intersection of 2D infinite lines using Boost Geometry

A line is defined by two points in Line class. The getVector method enables to extract a direction vector.

The perp function enables to compute the perp product of two vectors. A zero value means vectors are parallel.

The intersect function checks if two lines intersect using the perp product of direction vectors. If true, it provides the intersection point by reference using parametric equation of lines.

Feel free to tell me if you know a more relevant library than Boost Geometry. Any idea to simplify and improve this code ?

Includes + namespace + typedef

#include <cmath>
#include <iostream>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

namespace bg = boost::geometry;

typedef bg::model::d2::point_xy<double> Point;
typedef bg::model::d2::point_xy<double> Vector;

Line class

class Line
{
  public:
    Line(const Point& point1,const Point& point2): p1(point1), p2(point2) {}
    ~Line() {}

    Vector getVector() const
    {
      Vector v(p2);
      bg::subtract_point(v,p1);
      return v;
    }

    Point p1;
    Point p2;
};

perp function

double perp(const Vector& v1, const Vector& v2)
{
  return bg::get<0>(v1)*bg::get<1>(v2)-bg::get<1>(v1)*bg::get<0>(v2);
}

intersect function

bool intersect(const Line& l1, const Line& l2, Point& inter)
{
  Vector v1 = l1.getVector();
  Vector v2 = l2.getVector();

  if(std::abs(perp(v1,v2))>0.)
  {
    Line l(l1.p1,l2.p1);
    Vector v = l.getVector();
    double t = perp(v,v2)/perp(v1,v2);
    inter = v1;
    bg::multiply_value(inter,t);
    bg::add_point(inter,l.p1);
    return true;
  }
  else return false;
}

Main with an example

int main(int argc, char** argv)
{
  Point p1(0.,0.);
  Point p2(1.,0.);
  Point p3(0.,1.);
  Point p4(0.,2.);
  Line l1(p1,p2);
  Line l2(p3,p4);

  Point inter;
  if( intersect(l1,l2,inter) )
  {
    std::cout<<"Coordinates of intersection: "<<inter.x()<<" "<<inter.y()<<std::endl;
  }
}


texts:
I am using this onset source code and this fft file to try to perform onset detection. Currently the code is working, but as my DSP and C skills are subpar I could use some advice on how to improve it.

My main points of insecurity are the FFT (maybe there is a more suitable method out there?) and the C code. All advice appreciated!

NB: This code will eventually being going into iPhone project.

OnsetsDS  *ods = malloc(sizeof *ods);
float* odsdata = (float*) malloc(onsetsds_memneeded(ODS_ODF_RCOMPLEX, 512, 11));
onsetsds_init(ods, odsdata, ODS_FFT_FFTW3_HC, ODS_ODF_RCOMPLEX, 512, 11, 44100);

int i;
int x;
double (*vocalData)[2] =  malloc(2 * 512 * sizeof(double));
double (*doubleFFTData)[2] =  malloc(2 * 512 * sizeof(double));

for (i = 0; i < vocalBuffer.numFrames; i=i+512){

    bool onset;
    for (x = 0; x < 512; x++){
        *vocalData[x] = (double)vocalBuffer.buffer[i+x];
    }

    fft(512, vocalData, doubleFFTData);
    float *floatFFTData = malloc(512 * sizeof(float));
    int z;
    for (z = 0; z < 512; z++){

        floatFFTData[z] = (float)*doubleFFTData[z];
    }

    onset = onsetsds_process(ods, floatFFTData);

    if (onset){
        printf("onset --> %i\n", i);
    }
}

free(ods->data); // Or free(odsdata), they point to the same thing in this case
return nil;


texts: Classes for background layer and parallax effect

texts:
I have two classes DigBackground and DigParallaxBackgroundLayer (a parallax background is a image consisting of several images that move at different scroll speeds, for games etc.).  My idea was to have the DigBackground class which is basically just a image with some added properties that can be set were it will draw itself on the screen. It just has one method currently and that is the initWithImageNamed that sets all of it properties.  Some of its properties are public, but read-only. So they can be accessed by the DigParallaxBackground class.

The DigParallaxBackground class currently also have one method at present - the initializer which takes an array of DigBackground´s as argument. And will display them on screen.

I want to know if this is decent design and how I can improve it if need be.

This is how it's used:

    DigBackground *bg1 = [[DigBackground alloc]initWithImageNamed:@"Default.png"
                                                  withScrollSpeed:1.0f
                                                  InitialOffsetOf:ccp(0, 0)
                                                         position:ccp(100, 100)
                                                         setFlipX:NO];

    DigParallaxBackgroundLayer *parallaxBg = [[DigParallaxBackgroundLayer alloc]
                                              initParallaxBackgroundWithImages:@[bg1] inOrder:kAscending];

    [self addChild: parallaxBg];

Header for DigBackground:

@property (nonatomic, readonly) float bgScrollSpeed;
@property (nonatomic, readonly) CGPoint initialOffset;

// Designated initializer
- (id) initWithImageNamed: (NSString *)image
          withScrollSpeed: (float)scrollspeed
          InitialOffsetOf: (CGPoint)offset
                 position: (CGPoint)position
                 setFlipX: (BOOL)flipX;

Header for DigParallaxBackground:

typedef enum {
    kAscending,
    kDescending
} ImagesOrder;

@interface DigParallaxBackgroundLayer : CCLayer
{
    NSArray *backgrounds;
}

// Designated initializer
- (id) initParallaxBackgroundWithImages: (NSArray *) images inOrder: (ImagesOrder) order;


texts: Benchmarking our LAMP servers with this php script

texts:
I've written a small script to benchmark our LAMP hosted servers that assess the performance based on three factors:

Disk I/O
Database I/O (mysql)
Database I/O (sqlite)

The logic is as follows:

get the type of test performed using a querystring value.
generate a big random string of 100KB.
If (disk-i/o)
write this line to a random file 500 times.
else if (mysql i/o)
insert this as record in a mysql table 500 times.
else if (sqlite i/o)
insert this as record in a sqlite table 500 times.
Write back to response all variables such as the big string ($payload), time taken to write ($wtime), etc..

The program is working fine, but the database i/o is taking way more time than the file i/o. In one test instance, file i/o took only 1.5 seconds, whilst db i/o took 43 seconds! Can you help me with streamlining this code?

<?php
//index.php
$mysqlserver = 'localhost';
$mysqlusername = 'test';
$mysqlpassword='test';
$mysqldatabase='test';

$iterations=500;
$payload=""; //generate a random string of 108KB and a random filename
$fname='';
$rtime=0; //in milliseconds
$wtime=0;
$gentime=0;
$type='';

$db = null;
$mysqli = null;

if (isset($_REQUEST['type'])) $type=$_REQUEST['type'];

//generate:
$start = microtime(true);
for($i=0;$i<108000;$i++) //generate a big string
{
    $n=rand(0,57)+65;
    $payload = $payload.chr($n);
}
$gentime=round((microtime(true) - $start)*1000);

//write test:
$start = microtime(true);
    if ($type=='sqlite') //sqlite test
    {
        $db = new SQLite3("benchmark.db");
        $db->exec('create table temp(t text)');
        $db->exec("begin");
        $stmt = $db->prepare("insert into temp values(:id)");
        for($i=0;$i<$iterations;$i++) {
            $stmt->bindValue(':id', $payload, SQLITE3_TEXT);
            $stmt->execute();
            //$db->exec("delete from temp");
            };
        $db->exec("commit");

    }
    else if ($type=='mysql') //mysql test
    {
        $mysqli = new mysqli($mysqlserver, $mysqlusername, $mysqlpassword, $mysqldatabase);
        $mysqli->query('create table temp(t varchar(108000))');
        $mysqli->query('begin transaction');
        for($i=0;$i<$iterations;$i++)
            $mysqli->query("insert into temp values('{$payload}')");
        $mysqli->query('commit');
    }
    else // Disk I/O
    {
        $fname = chr(rand(0,57)+65).chr(rand(0,57)+65).chr(rand(0,57)+65).chr(rand(0,57)+65).'.txt';
        for($i=0;$i<$iterations;$i++) file_put_contents($fname,$payload);
    }
$wtime=round((microtime(true) - $start)*1000);

//read test:
$start = microtime(true);
$result = '';
if ($type=='sqlite'){
    for($i=0;$i<$iterations;$i++) {
        $result = $db->query("select t from temp limit 1");
        $result = $result->fetchArray()['t'];
        //$db->exec("delete from temp");
    };
        //var_dump($result);
}
else if ($type=='mysql'){
    $stmt = $mysqli->prepare('select t from temp limit 1');
    if ($stmt)
    {
        for($i=0;$i<$iterations;$i++) {
            $stmt->execute();
            $stmt->bind_result($result);
            $stmt->fetch();
        };
    }
}
else
{
    for($i=0;$i<$iterations;$i++) $result = file_get_contents($fname);
}
$rtime=round((microtime(true) - $start)*1000);

//cleanup:
if ($type=='sqlite')
{
        $db->exec("drop table temp");
        $db->close();
}
else if ($type=='mysql')
{
    $mysqli->query('drop table temp');
}
else
{
    unlink($fname);
}

//return:
$result =  array(
    'type'=>($type==''?'disk':$type),
    'iterations'=>$iterations,
    'generate_time'=>$gentime,
    'write_time'=>$wtime,
    'read_time'=>$rtime,
    'server_software'=>$_SERVER["SERVER_SOFTWARE"],
    'payload'=>$result,
);

echo json_encode($result);


texts: Is the right usecase implemenation of ValueTask and Task in C#

texts:
I am trying to understand the right usage of Task vs ValueTask in .NetCore2.0(+) or C# 7.0(+)
Task -

Is a class/object types & uses heap memory
should be used in async method when the operation would complete eventually ex. network call

ValueTask -

Is a struct/value type & uses stack memory
should be used in async method when the operation output is already in memory or the operation completes immediately

Based on this is my implementation justifies both usage right?
public class Utility
{
    public async ValueTask<int> Add(int n1, int n2)
    {
        //immediately available
        return await Task.Run(() => (n1 + n2))
                     .ConfigureAwait(false);
    }

    public async Task<string> Get(string email)
    {
        //eventually available
        string user = await Task.Run(() => GetFromDb(email))
                            .ConfigureAwait(false);

         string GetFromDb(string email)
        {
            // do a database call over network
            // & get the user based on the input email
            return "User from Db";
        }

        return user;
    }
}

Please review & suggest. Thanks!


texts:
I'm trying to parse a char* into an int without using atoi(). I walk through the string, check if it's a valid digit, then add that digit to my integer by multiplying by 10 and adding the digit. I am not accepting negative integers.

Here's the code I'm using:

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

#define TRUE  1
#define FALSE 0

int main(int argc, char *argv[]) {
    if (argc < 2)
        exit(1);

    char *p = argv[1];

    int amount = 0;
    int len = strlen((const char*) argv[1]); // calculate len beforehand
    int contin = TRUE;
    for (int i = 0; contin && i < len; ++i, ++p) {
        switch (*p) {
        case '0':
            amount = (amount * 10);
            break;
        case '1':
            amount = (amount * 10) + 1;
            break;
        case '2':
            amount = (amount * 10) + 2;
            break;
        case '3':
            amount = (amount * 10) + 3;
            break;
        case '4':
            amount = (amount * 10) + 4;
            break;
        case '5':
            amount = (amount * 10) + 5;
            break;
        case '6':
            amount = (amount * 10) + 6;
            break;
        case '7':
            amount = (amount * 10) + 7;
            break;
        case '8':
            amount = (amount * 10) + 8;
            break;
        case '9':
            amount = (amount * 10) + 9;
            break;
        default:
            contin = FALSE;
            break;
        }
    }

    fprintf(stdout, "amount: %i\n", amount);
    return 0;
}

...which works nicely. But, is there a better/more idiomatic way to do this?

EDIT: Thanks to Groo, I'm able to remove the giant switch statement:

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

#define TRUE  1
#define FALSE 0

int main(int argc, char *argv[]) {
    if (argc < 2)
        exit(1);

    char *p = argv[1];

    int amount = 0;
    int len = strlen((const char*) argv[1]); // calculate len beforehand
    int contin = TRUE;
    for (int i = 0; contin && i < len; ++i, ++p) {
        /* handle negative integers */
        if (*p == '-' && i == 0) {
            fprintf(stderr, "negative integers are invalid.\n");
            exit(1);
        }

        if (*p > 0x2F && *p < 0x3A)
            amount = (amount * 10) + (*p - '0');
        else {
            contin = FALSE;
            --p;
        }
    }

    fprintf(stdout, "amount: %i\n", amount);
    return 0;
}
```


texts: Declaring arrays knowing their maximum size

texts:
I know the maximum array size is 6. So what is the best practice to declare an array?

In the following code I used it like this:

<!DOCTYPE html>

My understanding is that in this case, a memory location will be allocated at initialization time itself, and so while running, it will just assign the data to the array, which will provide some better performance. But if it will not take the 6 data, some memory space will be wasted.

And another way of implementation is:

Here memory will be allocated dynamically when assigning the variable, so memory will not be wasted.

I know declaring an array with new() constructor is not a good practice (as mentioned here)), but if we know the maximum size, I want to know about the best practice. So what is the best practice here for declaring an array in JavaScript?


texts:
I am trying to do the following. I have a list of Custom objects:

public class TestObject {
  public int Id { get; set; }
  public string Name { get; set; }
  public bool First { get; set; }
  public bool Last { get; set; }
}

I want to set the property First and Last to true at the first and last item in the list.

Side note: I am filling the list in a LinqToEntity query. Perhaps its even possible in LinqToEntity.

I have come up with the following but i doubt its the most efficient way.

var result = new List<TestObject> {
   new TestObject { Id = 1, Name = "Test1" },
   new TestObject { Id = 2, Name = "Test2" },
   new TestObject { Id = 2, Name = "Test2" }
};

foreach (var item in result)
{
   item.First = result.FirstOrDefault() == item;
   item.Last = result.LastOrDefault() == item;
}

I eventually want to display the results in a ASP.Net's ListView (webforms), where I have buttons that will be displayed based on the property.

Is there an easier or more efficient way of doing this?


texts: Removing checks that are only necessary on first pass

texts:
I've got a function that's executed in a game loop. There are a couple of checks that are really only necessary during the first pass of the game loop. How can I remove these? There is more code like this, but this is the shortest example.

public void Update(Frame rawBodyData)
{
    //Catch the first pass, where RawBody and FilteredBody are null
    //I'd like to remove this check
    if (RawBody.IsNull())
    {
        RawBody = rawBodyData;
    }
    //And this check
    if (FilteredBody.IsNull())
    {
        FilteredBody = rawBodyData;
    }

    _partiallyFilteredBody = rawBodyData;

    foreach (var filter in Filters)
    {
        //Check is a certain flag is set
        if ((_filterMethods & filter.Key) != 0)
        {
            _partiallyFilteredBody = filter.Value.Filter(_partiallyFilteredBody, FilteredBody);
        }
    }

    FilteredBody = _partiallyFilteredBody;
    RawBody = rawBodyData;
}

Other comments are certainly welcome. This is supposed to be high performance code, so I'd like to avoid things like LINQ (which ReSharper is already suggesting).


texts: Unit Test case to check if localstorage is empty once I logout of the Web app

texts:
I am trying to clear my localstorage when I am logging out of the application. I want to write a unit test case in Jasmine to check if this task is performed when logout function is run. I am writing test cases for the first time so got stuck in the approach.

In my compoment.ts file I have a logout function:

logout() {
    location.href = "/";
     localstorage.clear();
}

spec.ts file

beforeEach(function () {
        var store = {};
        spyOn(localStorage, 'getItem').andCallFake(function (key) {
            return null;
        });
    });

I don't know if this is a correct approach to write the test case for this particular requirement or which one among unit or integration test cases is actually valid for this situation.


texts:
This is an implementation of a segment tree with lazy propagation. Could you please review this code so that I can improve my Go language skills?

package main

import (
//"fmt"
)

var array []int; // Array to store initial input  like: [1,2,3,4,5,6,7,8,9,10]

/*
   This is Node structure
   val    : aggregate result (sum, min, max ...)
   lazy   : for lazy propagation
   lc, rc : left & right child
*/
type Node struct {
    val    int
    lazy   int
    lc, rc *Node
}

// This function will return middle index of left and right
func midIndx(l, r int) (mid int) {
    mid = l + (r - l) / 2
    return mid
}

// This function is used to create initial tree
func (node *Node) MakeTree(left, right int) {

    // Out of range
    if right < left {
        return
    }

    // Leaf node
    if left == right {
        node.val = array[left]; // Init value
        return
    }

    var lc, rc Node;
    mid := midIndx(left, right)
    lc.MakeTree(left, mid)       // Init left child
    rc.MakeTree(mid + 1, right)  // Init right child

    // link with parent
    node.lc = &lc
    node.rc = &rc

    // set parent value from left and right child
    if node.lc.val > node.rc.val {
        node.val = node.lc.val
    } else {
        node.val = node.rc.val
    }
}

/**
 * Query tree to get max element value within range [l, r]
 */
func (node *Node) Query(left, right, l, r int) int {

    // Out of range
    if right < l || left > r || right < left {
        return -1e18 // as query for maximum number
    }

    // This node needs to be updated
    if node.lazy != 0 {
        node.val = node.val + node.lazy  // Update it
        if left != right {  // propagate lazy value to its child
            node.lc.lazy = node.lc.lazy + node.lazy  // Mark left child as lazy
            node.rc.lazy = node.rc.lazy + node.lazy  // Mark right child as lazy
        }
        node.lazy = 0  // as lazy value is added and propagate to its child, set to 0
    }

    // current segment is totally within range [l, r]
    if left >= l && right <= r {
        return node.val
    }

    mid := midIndx(left, right)
    L := node.lc.Query(left, mid, l, r)       // query left  child
    R := node.rc.Query(mid + 1, right, l, r)  // query right child

    // return max value to parent
    if L > R {
        return L
    } else {
        return R
    }
}

/**
 * Increment elements within range [l, r] with value value
 */
func (node *Node) Update(left, right, l, r, val int) {
    // This node needs to be updated
    if node.lazy != 0 {
        node.val = node.val + node.lazy  // Update it
        if left != right {
            node.lc.lazy = node.lc.lazy + node.lazy  // Mark left child as lazy
            node.rc.lazy = node.rc.lazy + node.lazy  // Mark right child as lazy
        }
        node.lazy = 0 // Reset it
    }

    // Current segment is not within range [l, r]
    if right < l || left > r || right < left {
        return
    }

    // Segment is fully within range
    if left >= l && right <= r {
        node.val = node.val + val
        if left != right { // Not leaf node
            node.lc.lazy = node.lc.lazy + val
            node.rc.lazy = node.rc.lazy + val
        }
        return
    }

    mid := midIndx(left, right)
    node.lc.Update(left, mid, l, r, val)      // Updating left child
    node.rc.Update(mid + 1, right, l, r, val)  // Updating right child

    // Updating root with max
    if node.lc.val > node.rc.val {
        node.val = node.lc.val
    } else {
        node.val = node.rc.val
    }
    return
}

func main() {
    n := (len(array)) - 1
    var start Node
    var l, r, val int
    start.MakeTree(0, n)           // make initial tree
    start.Update(0, n, l, r, val)  // Update tree within a range
    _ = start.Query(0, n, 0, 19)   // Query within a range
}


texts: Implementing a shared array cache without locking

texts:
I am trying to implement a shared cache for arrays.  It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches.  The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes.  Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

So the fetch operation has to read the cache slot's owner field to check against its argument, and if it matches return the cache slot's value field.  The problem is, without locks, another thread could overwrite one of these fields during that operation.  This approach tries to get around that by assigning a version field to each cache slot.  It only increases.  The fetch operation reads the version (atomically) at the start of the operation and at the end; if these are not the same, something changed during the read and the result is invalid, even if the owner field apparently matched.

The code below ensures that version is always incremented before value is updated, thus preventing fetch from returning a value from a different owner.  (The functions g_atomic_... are provided by glib.) It "seems to work" - but can it be proven correct or incorrect?

struct _cache_slot
{
  void*        owner;
  gint         version;
  gdouble      value;
};

struct _cache_slot cache[SIZE];

int
point_cache_fetch(void *owner, gdouble* ret, gsize idx)
{
   struct _cache_slot *slot = &cache[idx];

   gint version_start  = g_atomic_int_get(&(slot->version));
   void* slot_owner    = g_atomic_pointer_get(&(slot->owner));
   gdouble value       = slot->value;
   gint version_finish = g_atomic_int_get(&(slot->version));

   if ((version_start == version_finish) && (slot_owner == owner))
   {
     *ret = value;
     return 1;
   }
   else
   {
     return 0;
   }
}

void
point_cache_store(void *owner, gsize idx, gdouble value)
{
   struct _cache_slot *slot = &cache[idx];

   g_atomic_pointer_set(&(slot->owner), NULL);
   slot->version++;
   g_atomic_pointer_set(&(slot->owner), owner);
   slot->value = value;
}


texts:
I wrote a string escaping function in C, and I'm trying to rewrite it to Haskell.  The C version, along with comments explaining why it does what it does, can be found on GitHub.

Here's a naïve implementation based on Data.ByteString.concatMap:

{-# LANGUAGE ViewPatterns #-}
import Data.Bits
import Data.ByteString          (ByteString)
import Data.ByteString.Char8    ()
import Data.ByteString.Internal (c2w, w2c)

import qualified Data.ByteString        as B
import qualified Data.ByteString.Lazy   as L

escapeCopyBytea :: ByteString -> ByteString
escapeCopyBytea = B.concatMap f
    where
        f (w2c -> '\\') = B.replicate 4 (c2w '\\')
        f c | c >= 32 && c <= 126 = B.singleton c
        f c = B.pack
                [ c2w '\\'
                , c2w '\\'
                , c2w '0' + ((c `shiftR` 6) .&. 0x7)
                , c2w '0' + ((c `shiftR` 3) .&. 0x7)
                , c2w '0' + (c .&. 0x7)
                ]

mapChunks :: (ByteString -> ByteString) -> L.ByteString -> L.ByteString
mapChunks f = L.fromChunks . map f . L.toChunks

main :: IO ()
main = L.getContents >>= L.putStr . mapChunks escapeCopyBytea

I'd expect this to be a few times slower than the C version.  Nope, it is 125 times slower than the C version.

Then, I tried using blaze-builder:

import Blaze.ByteString.Builder
import Data.Bits
import Data.Monoid              (mappend, mconcat, mempty)
import Data.ByteString          (ByteString)
import Data.Word                (Word8)

import qualified Data.ByteString        as B
import qualified Data.ByteString.Lazy   as L

writeBackslash :: Write
writeBackslash = writeWord8 92

escape1 :: Word8 -> Builder
escape1 92 = fromWrite $ writeBackslash
               `mappend` writeBackslash
               `mappend` writeBackslash
               `mappend` writeBackslash
escape1 c | c >= 32 && c <= 126 = fromWrite $ writeWord8 c
          | otherwise = fromWrite $ writeBackslash
                          `mappend` writeBackslash
                          `mappend` writeWord8 (48 + ((c `shiftR` 6) .&. 0x7))
                          `mappend` writeWord8 (48 + ((c `shiftR` 3) .&. 0x7))
                          `mappend` writeWord8 (48 + (c .&. 0x7))

escapeCopyBytea2 :: ByteString -> Builder
escapeCopyBytea2 = B.foldl' f mempty
    where
        f b c = b `mappend` escape1 c

main :: IO ()
main = L.getContents >>= L.putStr . toLazyByteString . mconcat
                       . map escapeCopyBytea2 . L.toChunks

This made a difference.  It's even slower, 300 times slower than the C version.  I thought blaze-builder was supposed to be really fast!

Simply summing bytes, by folding over the input in a similar fashion as I do above, is reasonably fast (takes 5 times longer than the C version of the escaping code):

import qualified Data.ByteString      as B
import qualified Data.ByteString.Lazy as L

import Data.List (foldl')

main :: IO ()
main = L.getContents >>= print . foldl' (+) 0 . map (B.foldl' (+) 0) . L.toChunks

What can I do to make this escaping function faster?  Is it possible to get anywhere near the performance of C here, or is C (or perhaps working with Ptr or Addr# directly and doing it the C way) the only viable option to make this efficient?

Edit: I wrote a much faster implementation and put it on GitHub.  However, it uses a lot of ugly buffer manipulation.  I'd still like to know if there's a simpler way to escape bytes in Haskell that isn't slow.


texts: Efficient pathfinding without heuristics?

texts:
Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A* algorithm working rather well in the grid, but the random warp point links mean that even though the systems have X,Y coordinates for where they're located on a galactic map, a system at 2,3 isn't always linked directly to a system at 2,4 and so the shortest path may actually lead away from the target before it heads back towards it. I think this limitation eliminates A* since there's almost no way to get a good heuristic figured out.

What I've done instead is a recursive node search (I believe this specific pattern is a Depth-First Search), and while it gets the job done, it also evaluates every possible path in the entire network of systems and warp points, so I'm worried it will run very slowly on larger sets of systems. My test data is 11 systems with 1-4 warp points each, and it averages over 700 node recursions for any non-adjacent path.

My knowledge of search/pathfinding algorithms is limited, but surely there's a way to not search every single node without needing to calculate a heuristic, or at least is there a heuristic here I'm not seeing?

Here's my code so far:

private int getNextSystem(StarSystem currentSystem, StarSystem targetSystem,
                          List<StarSystem> pathVisited)
{
    // If we're in the target system, stop recursion and
    // start counting backwards for comparison to other paths
    if (currentSystem == targetSystem)
        return 0;

    // Arbitrary number higher than maximum count of StarSystems
    int countOfJumps = 99;
    StarSystem bestSystem = currentSystem;

    foreach (StarSystem system in currentSystem.GetConnectedStarSystems()
                                  .Where(f=>!pathVisited.Contains(f)))
    {
        // I re-create the path list for each node-path so
        // that it doesn't modify the source list by reference
        // and mess up other node-paths
        List<StarSystem> newPath = new List<StarSystem>();
        foreach (StarSystem s in pathVisited)
            newPath.Add(s);
        newPath.Add(system);

        // recursive call until current == target
        int jumps = getNextSystem(system, targetSystem, newPath);

        // changes only if this is better than previously found
        if (jumps < countOfJumps)
        {
            countOfJumps = jumps;
            bestSystem = system;
        }
    }
    // returns 100 if current path is a dead-end
    return countOfJumps + 1;
}


texts: My own implementation of Linq SelectMany extension method

texts:
What do you think of my own implementation of the extension method SelectMany?
Motivating criticism is always welcome.

public static IEnumerable<TResult> MySelectMany<T, TResult>(this IEnumerable<T> source, Func<T, IEnumerable<TResult>> selector)
{
    var theList = new List<TResult>();

    foreach (T item in source)
    {
        foreach (TResult inneritem in selector(item))
        {
            theList.Add(inneritem);
        }
    }

    return theList as IEnumerable<TResult>;
}


texts: Efficient text to binary conversion in Java

texts:
I wrote a Java FX application that translates binary to and from String and numbers in Java. Whenever the program is translating large amounts of text to binary it takes a very long time, and leaves the application unresponsive. Could a more efficient algorithm be used to speed up the process?

    // Turns binary into text.
private void binaryToText() throws BinaryFormatException
{
    if (input.toString().length() % 8 != 0)
        throw new BinaryFormatException("Binary must be a multiple of 8");

    String input = this.input.toString();
    String _byte = "", textResult = "";

    for (int i = 1 ; i <= input.length() ; i++) {
        _byte += input.charAt(i-1);
        if (i % 8 == 0) {
            int charCode = Integer.parseInt(_byte, 2);
            textResult += (char) charCode;
            _byte = "";
        }
    }

    this.output = textResult;
}

// Turns text into binary.
private void textToBinary()
{
    String binResult = "";
    final String fourBitPrepend = "0000";
    final String twoBitPrepend = "00";
    final String bitPrepend = "0";
    byte[] charCodes = input.toString().getBytes();

    for(byte ch : charCodes) {
        String binary = Integer.toBinaryString(ch);
        switch(binary.length()) {
            case 4 : binResult += fourBitPrepend + binary; break;
            case 6 : binResult += twoBitPrepend + binary; break;
            case 7 : binResult += bitPrepend + binary; break;
            default : binResult += binary;
        }
    }

    this.output = binResult;
}


texts: VCF parser for eventual genomic data visualization

texts:
I've just started out writing an app that will visualize genomic data for anybody to understand.

When you get your genome sequenced the raw data usually comes in the form of a VCF file. I started out by drafting parser below that essentially creates a JavaScript object out of a VCF text file. Next I think want to write a schema-like JSON file (since there doesn't seem to be any database with an API that correlate genotypes to phenotypes based on GWAS) that I can query for phenotypes with the genotypes generated by the parser. For example, if I want to know if a specific genome has the genotype for lactose-intolerance, red hair or alcoholism pre-disposition, I can consult this manually written schema that maps genotypes to phenotypes.

If you have genomics background all the better, but I'm mostly looking for advice concerning my usage of OOP and any other insights. How would you go about the more downstream front-end parts of the app (the actual visualization, was thinking something like a timeline and a 'humonculus'. React? D3?)?

(function iife() {

'use strict'

const fs = require('fs');

// Output class for parsing genotype file
class Genome {
  constructor(name) {
      this.name = name
      // Find genotype by rs-ID without having to know chromosome
      this.findByRsId = (rs_id) => {
        for(var chr in this) {
          if (chr.substring(0, 1) === 'c') {
            for(var id in this[chr]) {
              if (id == rs_id) {
                return this[chr][rs_id]
              }
            }
          }
        }
      }
      // Get actual sample's genotype
      this.getSampGenotype = (rs_id) => {
        let rs = this.findByRsId(rs_id)
        switch(rs.fit) {
          case '0/0':
            return rs['genotype'][0]+rs['genotype'][0]
            break
          case '0/1':
            return rs.genotype
            break
          case '1/1':
            return rs['genotype'][1]+rs['genotype'][1]
            break
          case '0':
            return rs.genotype
            break
          case '1':
            return rs.genotype
            break
          default:
            return rs.genotype
            break
        }
      }
      // Get ref genotype
      this.getRefGenotype = (rs_id) => {
        var rs = this.findByRsId(rs_id)
        return rs.genotype
      }
  }

}

// Helpers
var handleRow = (row) => {
  // Parse row into data items
  if (row.length === 10 && row[0] != '#CHROM' && row[2].substring(0,2) === 'rs') {
    // If no chr_[num] exists, make one
    if(!myGenotypes["chr_"+row[0]]) {
      myGenotypes["chr_"+row[0]] = {}
    } else {
      // If no rs_[num] exists, make one and set it to genotype
      if (!myGenotypes["chr_"+row[0]][row[2]]) {
        myGenotypes["chr_"+row[0]][row[2]] = {
          'genotype': row[3]+row[4],
          'quality': row[6],
          'fit': row[9]
        }
      }
    }
  }
}

var handleGFGChunk = (data) => {
  // Cut up chuck into array of rows, then pass to row handler
  var lines = data.split('\n')
  var cols = lines.map((l) => l.split('\t'))
  cols.forEach( (r) => handleRow(r) )
}

var check = (obj) => {
  console.log(obj.findByRsId('rs1556032'))
  console.log(obj.getRefGenotype('rs1556032') === 'CT')
  console.log(obj.getSampGenotype('rs1556032') === 'CC')
}

/*=====================
  Parsing of VCF file
=====================*/

// Have e.g. genotypes class on the ready
var myGenotypes = new Genome('edmund')

// Read VCF
var readFromFile = __dirname + 'vcf/GFG_filtered_unphased_genotypes.vcf'
var GFGfile = fs.createReadStream(readFromFile)
GFGfile.setEncoding('utf8')

// Write Genome upon code
// var writeToFile = 'GFG.js'
// var GFGclass = fs.createWriteStream(writeToFile)

// Start the parsing!
GFGfile.on('data', handleGFGChunk)
GFGfile.on('close', d => console.log('Checked genotype class') )
GFGfile.on('end', d => check(myGenotypes) )

})()


texts:
Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution.

#include <iostream>
#include <vector>
#include <string>

enum { GOAL = '*', SPACE = ' ', WALL = '#', TRIED = '!', USED = '+' };

class maze {
    std::vector<std::string> data;
public:
    char &operator()(size_t x, size_t y) {
        return data[y][x];
    }

    friend std::istream &operator>>(std::istream &is, maze &m) {
        std::string temp;
        while (std::getline(is, temp))
            m.data.push_back(temp);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, maze const &m) {
        for (auto const &s : m.data)
            os << s << '\n';
        return os;
    }

    size_t y_dim() { return data.size(); }
    size_t x_dim() { return data[0].size(); }
};

bool solve(maze &m, size_t x = 0, size_t y=0) {
    if (x < 0 || y < 0 || x >= m.x_dim() || y >= m.y_dim())
        return false;

    if (m(x, y) == GOAL)
        return true;

    if (m(x, y) != SPACE)
        return false;

    m(x, y) = USED;

    bool solved
         = solve(m, x - 1, y)
        || solve(m, x + 1, y)
        || solve(m, x, y - 1)
        || solve(m, x, y + 1);

    if (!solved)
        m(x, y) = TRIED;

    return solved;
}

int main(){
    maze m;
    std::cin >> m;

    solve(m);
    std::cout << m;
}

Input is a simple text file of walls, spaces, and a goal, such as:

  #######
#    # ##
# ####  #
#      ##
# ### ###
#####  *#

Searching always commences from position 0, 0 (i.e., the top, left corner).