Sort array by low, medium and high I'm working on a problem to sort array by low, medium and high -- in-place tweak original array. I'm looking for advice, especially any algorithm implementation efficiency. My current bottleneck of implementation is that I have to do partition twice, by low+medium and high, then do low and medium partition on low+medium part. I'd like to do partition only once.

'''
You have an unsorted array of integers and a
function........string getCategory(integer)........
which deterministically returns 1 of three possible strings:
"low", "medium", or "high", depending on the input integer.
You need to output an array with all the "low" numbers at the bottom,
all the "medium" numbers in the middle, and all the "high" numbers at the top.
This is basically a partial sort. Within each category, the order of the numbers does not matter...
For example, you might be give the array [5,7,2,9,1,14,12,10,5,3].
For input integers 1 - 3, getCategory(integer) returns "low",
for 4 - 10 it returns "medium," and for 11 - 15 it returns "high".
You could output an array (or modify the given array) that looks like this: [3,1,2,5,5,9,7,10,14,12]
'''

def getCategory(value):
    if 1<=value<=3:
        return 'low'
    elif 4<=value<=10:
        return 'medium'
    else:
        return 'high'
def partial_sort(numbers):
    low_and_medium_index = 0
    high_index = len(numbers)-1
    while low_and_medium_index <= high_index:
        while low_and_medium_index <= high_index and \
                        getCategory(numbers[low_and_medium_index]) != 'high':
            low_and_medium_index+=1
        while low_and_medium_index <= high_index and \
                        getCategory(numbers[high_index]) == 'high':
            high_index -= 1
        if low_and_medium_index < high_index:
            numbers[low_and_medium_index], numbers[high_index] = numbers[high_index], numbers[low_and_medium_index]
        else:
            break
    low_index = 0
    medium_index = low_and_medium_index - 1
    while low_index <= medium_index:
        while low_index <= medium_index and \
                        getCategory(numbers[low_index]) == 'low':
            low_index+=1
        while low_index <= medium_index and \
                        getCategory(numbers[medium_index]) == 'medium':
            medium_index -= 1
        if low_index < medium_index:
            numbers[low_index], numbers[medium_index] = numbers[medium_index], numbers[low_index]
        else:
            break

    return numbers

if __name__ == "__main__":
    print partial_sort([5,7,2,9,1,14,12,10,5,3])

Unless you're very sure you can outperform CPython's list.sort() here I would recommend using it instead of custom algorithm whose implementation is hard to read.

And most likely CPython based implementation is going to be fast because we are removing pure Python loops. I can't say the same thing about other implementations, for example PyPy, you may have to time and compare them yourself.

Now to do this using list.sort() we will have to use its key argument, key argument is used for specifying custom comparison values.

In this we can map 'low', 'medium' and 'high' to some numbers and use those numbers for comparison. If possible you can also numbers such numbers from get_category itself to reduce one step.

def get_category(value):
    if 1 <= value <= 3:
        return 'low'
    elif 4 <= value <= 10:
        return 'medium'
    else:
        return 'high'

def partial_sort(numbers):
    category_weight = {'low': 1, 'medium': 2, 'high': 3}
    numbers.sort(key=lambda x: category_weight[get_category(x)])
    return None  # Can be omitted, but let's be explicit.

As you can see the resulting code is much short and easier to read.

Timing comparisons

>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**5
>>> %timeit partial_sort(data)
1 loops, best of 3: 347 ms per loop
>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**5
>>> %timeit partial_sort_op(data)
1 loops, best of 3: 435 ms per loop

>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6
>>> %timeit partial_sort(data)
1 loops, best of 3: 3.58 s per loop
>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6
>>> %timeit partial_sort_op(data)
1 loops, best of 3: 4.42 s per loop

Notes

Don't use camel-casing for function and variable names, in Python underscores are preferred.
Your code should be PEP-8 compliant to make it much more readable.
Read more about sorting in Python: Sorting Mini-HOW TO
If you're modifying the array in-place then it is recommended to return None instead of the array. It makes it consistent with other in-place operations we have in Python like list.append(), list.extend(), dict.update() etc. Else use sorted() with same key to get a new list and return it from your function, but creating a new list is expensive.


Indefinite article a/an I'm looking for feedback to improve this function. The purpose is to pass a noun and append the appropriate indefinite article ("a" or "an").

A known issue with this code is that it doesn't address words with a vowel sound but a consonant first letter, such as "honor" or "hour". I cannot include 'h' in the list of vowels, though; words like "home" or "horror" have a harder 'h' sound and use the article "a".

function aan ($string) {
    return (
        in_array(
            strtolower(substr($string, 0, 1)),
            array('a','e','i','o','u')
        ) ? 'an' : 'a'
    ).' '.$string;
}

Current output:

print 'Become '.aan('All-access').' member'; // Become an All-access member
print 'Become '.aan('Basic').' member'; // Become a Basic member
print 'It has been '.aan('interesting').' experience'; // It has been an interesting experience

A tiny improvement to reduce a string concatenation:

function aan ($string) {
    return (
        in_array(
            strtolower(substr($string, 0, 1)),
            array('a','e','i','o','u')
        ) ? 'an ' : 'a '
    ).$string;
}

In order to help get your logic for more cases (ie, your Honor or Hour examples), you may wish to visit the English StackExchange to get help in figuring that logic out. Then you can code that as well.


Equated Monthly Installment (EMI) for Home Loan and Amortization Schedule Any comment on my code?
Data model
public class LoanRepaymentPlan
{
    public decimal TotalRepaymentAmount { get; private set; }
    public decimal CurrentOutstandingAmount { get; private set; }
    public decimal MonthlyRepaymentInterestAmount { get; private set; }
    public decimal MonthlyRepaymentAmount { get; private set; }
    public DateTime RepaymentDate { get; private set; }

    private LoanRepaymentPlan(decimal TotalRepaymentAmount, decimal CurrentOutstandingAmount, decimal MonthlyRepaymentAmount)
    {
        this.TotalRepaymentAmount = TotalRepaymentAmount;
        this.CurrentOutstandingAmount = CurrentOutstandingAmount;
        this.MonthlyRepaymentAmount = MonthlyRepaymentAmount;
    }

    public static LoanRepaymentPlan Create(decimal TotalRepaymentAmount, decimal CurrentOutstandingAmount, decimal MonthlyRepaymentAmount)
    {
        return new LoanRepaymentPlan(TotalRepaymentAmount, CurrentOutstandingAmount, MonthlyRepaymentAmount);
    }
}

Main calculation
static void Main(string[] args)
{
    Console.WriteLine("Equated Monthly Installment (EMI) for Home Loan");

    Console.WriteLine("Total Loan Amount: ");
    var principal = Convert.ToDouble(Console.ReadLine());

    Console.WriteLine("Interest Rate Per Annum (%): ");
    var interestRatePerAnnum = Convert.ToDouble(Console.ReadLine()) / 100;

    Console.WriteLine("Loan Period (in years): ");
    var years = Convert.ToDouble(Console.ReadLine());

    Console.WriteLine("------------------------------------------------");

    Console.WriteLine("Monthly installment: " + HousingLoanInterest(principal, interestRatePerAnnum, years).ToString("C2"));

    decimal totalRepaymentAmount = 0;
    var monthlyRepaymentAmount = HousingLoanInterest(principal, interestRatePerAnnum, years);
    var tenure = years * 12;
    var principalAndInterest = CompoundInterest(principal, interestRatePerAnnum, 12, years);
    List<LoanRepaymentPlan> repaymentPlans = new List<LoanRepaymentPlan>();

    while (tenure >= 0)
    {
        totalRepaymentAmount = totalRepaymentAmount + (decimal)monthlyRepaymentAmount;
        tenure = tenure - 1;

        repaymentPlans.Add(LoanRepaymentPlan.Create(totalRepaymentAmount,
            (decimal)principalAndInterest - totalRepaymentAmount, (decimal)monthlyRepaymentAmount));
    }

    var table = new ConsoleTable("Current Outstanding Amount", "Monthly Repayment Amount", "Total Repayment Amount");
    foreach (var item in repaymentPlans)
    {
        table.AddRow(item.CurrentOutstandingAmount, item.MonthlyRepaymentAmount, item.TotalRepaymentAmount);
    }
    table.Write();
}

Helper methods
static double CompoundInterest(double principal, double interestRate, int timesPerYear, double years)
{
    // (1 + r/n)
    double body = 1 + (interestRate / timesPerYear);

    // nt
    double exponent = timesPerYear * years;

    // P(1 + r/n)^nt
    return principal * Math.Pow(body, exponent);
}

static double HousingLoanInterest(double loanAmount, double interestRate, double years)
{
    return (loanAmount * Math.Pow((interestRate / 12) + 1,
         (years * 12)) * interestRate / 12) / (Math.Pow
         (interestRate / 12 + 1, (years * 12)) - 1);
}

There are some inaccuracy of the calculation but I will try to figure out later. One thing bothers me is the Math.Pow which uses double. I have tried to convert the calculation to decimal but unable to do so at the moment.

var
Particularly given that you have accuracy issues, it's important for your own understanding of what the code does to be explicit in the following declarations:
    var monthlyRepaymentAmount = HousingLoanInterest(principal, interestRatePerAnnum, years);
    var tenure = years * 12;
    var principalAndInterest = CompoundInterest(principal, interestRatePerAnnum, 12, years);

From these lines alone, I have no idea if these are supposed to be doubles, integers, decimals, etc. Just spell out the actual type.
In-place operations
        totalRepaymentAmount = totalRepaymentAmount + (decimal)monthlyRepaymentAmount;
        tenure = tenure - 1;

can be
totalRepaymentAmount += monthlyRepaymentAmount;
tenure--;

Formatting
This could benefit from some temporary variables, but even without them,
    return (loanAmount * Math.Pow((interestRate / 12) + 1,
         (years * 12)) * interestRate / 12) / (Math.Pow
         (interestRate / 12 + 1, (years * 12)) - 1);

is more legible as
return (
    loanAmount * Math.Pow(
        interestRate / 12 + 1,
        years * 12
    ) * interestRate / 12
) / (
    Math.Pow(
        interestRate / 12 + 1,
        years * 12
    ) - 1
);

which in turn is equivalent to
double annual = interestRate / 12;
double pow = Math.Pow(
    annual + 1,
    years * 12
);
return loanAmount * pow * annual / (pow - 1);

Simpler yet:
double annual = interestRate / 12,
       pow = Math.Pow(
           annual + 1,
           -12 * years
       );
return loanAmount * annual / (1 - pow);

Please test this for equivalence.


Roll your own widget factory So for practice with Javascript, I wrote this lightweight widget factory which is similar in functionality (okay, that's a bit of a stretch) to jQuery's UI Widget factory. I was hoping I could get some pointers as far as idiom usage and also if there are any glaring problems with the below code.

var _CreateWidget = function(namespace, implementation) {
    _Widget = {
        _create: function() {},
        _destroy: function() {},
        _set: function() {},
        _get: function() {},
        options: {},
        context: undefined,
        namespace: namespace,
        apply: function(element) {
            this.context = element;
            element[namespace] = this;
            this._create();
        }
    };

    for (var item in implementation) {
        if (implementation.hasOwnProperty(item)) {
            _Widget[item] = implementation[item];
        }
    }

    return _Widget;
}

Widget = function(namespace, implementation) {
    return function(element) {
        var instance = _CreateWidget(namespace, implementation);
        instance.apply(element);
        return instance
    };
}

An example widget would be defined as follows:

//Example widget
Page = Widget("page", {
    _create: function() {
        //initialization code here
    },
    _destroy: function() {

    },
    _set: function() {

    },
    _get: function() {

    },
    request: function() {
        //custom function
    },
    options: {
        url: ''
    }
});

And the widget would be applied to an element like so:

myElement = document.getElementById("myUniqueId");
appliedPageReference = Page(myElement);

myElement.page.request(); //One way to call the custom request() function;
appliedPageReference.request(); //Another way to call the custom request() function;

Although DOM elements can be used like normal JavaScript objects, I'd avoid attaching JavaScript other than handlers. The problem is when they form circular references. In browser garbage collectors, they won't collect garbage if something still references them. If you accidentally form circular references, this will lead to memory leaks (unfreed memory)

jQuery avoids this by creating objects in an internal cache and assigns an ID to the element. That way, you are assigning a primitive to the element, not an object. This is how jQuery collects and manages event handlers, data attributes, and others.

So a general tip is: What is from JavaScript, stays in JavaScript. (And not cross over to the DOM)
In jQuery's case, the functions are not actually attached to the element. That's the purpose of the "jQuery object". In a gist, a jQuery object is just an array-like object (let's call it "pseudo-array" from this point on), that contains DOM elements. The prototype of the jQuery object is where the functions live. These functions operate on each value in the collection.

Executing a function in a jQuery object is not like this:

someElement.doSomething();

But rather, something like this:

collectionOfStuff.forEach(function(DOMElement,i,arr){
  //do something for each in the collection
});

Widget in your code is some function that manufactures "widget templates" which are used to bind to your elements. Rather than having Widget return the template, why not make Widget your namespace. You can then create a function that attaches to the namespace.

It would be synonymous to doing jQuery.fn.extend(function(){...})

//define widget
Widget.defineWidget('Page',function(){

  //local stuff, aka "private"
  var privateVar = 'foo';
  function privateFn(){...}

  //anything attached to `this` is "public"
  //we will execute this function, providing an object as `this`
  this.publicVar = 'bar';
  this.publicFn = function(){...}

});

//access widget
var reference = Widget.Page(bindingTarget);

defineWidget define a creator function into the namespace that uses the widget definition to build instances, something like:

Widget.defineWidget = function(name,fn){

  //store
  wigetCache[name] = fn;

  //attach to namespace
  Widget[name] = function(){

    //BaseClass could be some constructor with prototype containing
    //all functions that widgets should have
    var instance = new BaseClass();

    //run the instance through the definition to attach the internals
    return fn.call(instance);
  }
}


Database Design for representing category relationships So I am new to Databases.Recently I was asked this question in an interview where they expected me to come with a schema for storing and retrieving categories for an E-commerce website in an RDBMS. Each category could have many sub-categories. But each sub-category could have just one parent category. So this is the idea that I gave them:
First I created the table like so:

create table category(category_id TEXT PRIMARY KEY,
category_name TEXT,parent_id TEXT);

Then I created an index on the parent_id, like so:

 Create index idx_category_table on category(parent_id);

Then I used the following queries to get the parent and child queries:

Select B.category_name as CategoryName from category A,
category B  where A.category_id='3' and
A.parent_id = B.category_id;

Select B.category_name as CategoryName from category A,
category B  where A.category_id='1' and A.category_id = B.parent_id;

I was rejected from the interview. However, I am curious to know how to better this.

I have a small concern about your approach that I think you should have addressed during the interview because it could raise potential issues in your design.

Do you want/need nested product categories?

As it currently stands you're allowing nested categories and even allowing loops of categories where a category can reference itself or one of it's own subcategories.

If you don't want nested categories then one of your restrictions will have to be that category with a parent should check it's parent doesn't also have a parent. The easiest way to do this is with two extra virtual columns(not stored), the first will simply say if a table has a parent(parent_id IS NOT NULL) and the second defines the value we need to create said relationship(namely that the value should be 0).

CREATE TABLE category(
    category_id TEXT PRIMARY KEY,
    category_name TEXT,
    parent_id TEXT,
    is_subcategory INT GENERATED ALWAYS AS (parent_id IS NOT NULL) VIRTUAL,
    can_be_child_of_subcategory INT GENERATED ALWAYS AS (0) VIRTUAL,
    FOREIGN KEY (parent_id, can_be_child_of_subcategory) REFERENCES category(category_id, is_subcategory) ON UPDATE RESTRICT
);

And now without changing the definition of the virtual columns we can't add a subcategory to a subcategory.

That said there's a few less major issues that might be worth considering in a bit more detail:

You should be using a foreign key, not an index:

FOREIGN KEY(parent_id) REFERENCES category(category_id)

You appear to be using TEXT as the field type, but accessing it with integers. If you're using a text type it's worth making it clear it's a GUID, either way you should use the right type for the field.

category_id INT
category_id = :sub_category_id
-- OR
category_id CHARACTER(32)
category_id = :sub_category_guid

It's ANSISQL standards to write keywords in upper case, obviously you don't need to keep to that standard as every SQL language supports lower or mixed case, but almost every documentation will have keywords in all caps so it's worth keeping to the convention:

CREATE TABLE category(category_id CHARACTER(32) PRIMARY KEY,
category_name TEXT,parent_id CHARACTER(32));

I also suggest making things not null

CREATE TABLE category(category_id CHARACTER(32) NOT NULL PRIMARY KEY,
category_name TEXT,parent_id CHARACTER(32));

I'd also suggest adding a bit more whitespace and at least for an interview document choices

CREATE TABLE category(
    category_id CHARACTER(32) NOT NULL PRIMARY KEY,
    category_name TEXT,
    parent_id CHARACTER(32),
    FOREIGN KEY (parent_id)
        REFERENCES category(category_id) ON UPDATE RESTRICT
);

Finally I'm really not a fan of your naming on the aliases for the table. Much nicer to use a descriptive name to make it easier to understand:

-- Fetch all child subcategories for a given category
SELECT
    SubCategory.category_name AS CategoryName
FROM category ParentCategory,
     category SubCategory
WHERE
    ParentCategory.category_id = :parent_category_guid
    AND
    ParentCategory.parent_id = SubCategory.category_id
;

-- Fetch the parent category for the child
SELECT
    ParentCategory.category_name AS CategoryName
FROM category ParentCategory,
     category SubCategory
WHERE
   SubCategory.category_id = :sub_category_guid
   AND
   ParentCategory.category_id = SubCategory.parent_id
;


Change case the data inside a column I created a code that import the data regularly into a selected workbook. The code run well, it takes less than 20 seconds before the data is imported successfully.

How does it work?

I get a monthly data with Excel format. I want the data to be imported into my workbook to be analysed further.

Step by step

The first part of my code run to copy the data from monthly workbook to analysis workbook.

The second part is a macro that will copy the content from the new data imported into a template table analysis based on the header. The code will only copy the content of columns if the header between 2 tables match.

Finally, I decided to add in the middle of the body of code, only for client's name column, before the macro copies all the rows at that column. I asked it to change the case of the value for each row to be UPPERCASE.

After adding this one line of code, my code run for 20 minutes.

Can someone help me to give another solution for the code to change the case to be "UPPERCASE" and also to reduce the runtime?

Option Explicit

    Dim lastRow As Long, LastTemp As Long 'lasttemp is "last row for table template
    Const StartRowTemp As Byte = 1
    Dim c As Byte 'number of columns
    Dim GetHeader As Range 'find

    Call Entry_Point 'to prevent screen updating and display alert, the value is False

'    On Error GoTo Handle

    'pick files to import - allow multiselect
    FiletoOpen = Application.GetOpenFilename _
    (FileFilter:="Excel Files (*.xlsx), *.xlsx", Title:="Select Workbook to Import", MultiSelect:=True)

    If IsArray(FiletoOpen) Then
        For FileCnt = 1 To UBound(FiletoOpen)
        Set SelectedBook = Workbooks.Open(Filename:=FiletoOpen(FileCnt))
        ShDataN.Cells.Clear
        SelectedBook.Worksheets("Client").Cells.Copy
        ShDataN.Range("A1").PasteSpecial xlPasteValuesAndNumberFormats
        SelectedBook.Close

        'locate last empty row in Monthly Table
        lastRow = ShMN.Cells(Rows.Count, 1).End(xlUp).Row + 1

        'locate last row in the new data
        LastTemp = ShDataN.Cells(Rows.Count, 1).End(xlUp).Row

       'delete the content from Analysis table

        ShMN.Rows("2:" & ShMN.Rows.Count).ClearContents

        'do while to find matching headers before copy paste
        c = 1
        Do While ShMN.Cells(1, c) <> ""

        Set GetHeader = ShDataN.Rows(StartRowTemp).Find _
        (What:=ShMN.Cells(1, c).Value, LookIn:=xlValues, MatchCase:=False, lookat:=xlWhole)
        If Not GetHeader Is Nothing Then
            ShDataN.Range(ShDataN.Cells(StartRowTemp + 1, GetHeader.Column), ShDataN.Cells(LastTemp, GetHeader.Column)).Copy
            ShMN.Cells(2, c).PasteSpecial
            ShMN.Rows("2:" & ShMN.Rows.Count).ClearFormats
            Call Range_Case
             'to change the case on column Client's name after copying
'
'                Set myrange = ShMN.Range("B2", "B" & Cells(Rows.Count, 1).Row)
'
'                For Each cell In myrange
'
'                cell.Value = UCase(cell)
'
'                Next cell

        End If 'get Header
        c = c + 1
       Loop

        Next FileCnt
        MsgBox "Data imported sucessfully", vbInformation, "General Information"

    End If 'isArray
    ShDataN.Cells.Clear

    With ShNote
        .Select
        .Range("A1").Select
    End With

    Call Exit_Point

'Handle:
'    If Err.Number = 9 Then
'    Else
'    MsgBox "An error has occured"
'    End If

Call Exit_Point

End Sub

For testing your code following assumption are made

Sub Entry_Point was disabling screen updating, events and display alerts.
Sub Exit_Point was enabling screen updating, events and display alerts.
It is being used for importing data from multiple files and to be finally placed in SheetShMN one below another

according to the above assumption following modification was done

1 Sheet ShMN is being cleared with in loop For FileCnt = 1 To UBound(FiletoOpen) with line ShMN.Rows("2:" & ShMN.Rows.Count).ClearContents. I pulled out the line out of the For loop for testing purpose.

2.The line  ShMN.Cells(2, c).PasteSpecial modifed to ShMN.Cells(lastRow, c).PasteSpecial for placing data from each file one below another (This to avoid 1st files data to be overwritten by subsequent files data).

Finally as the cause of slow performance, it is found the Case Changing codes are placed inside header finding loop.So it is executing Number of files X Number of columns times. I pulled it out of even file loop and placed just after completion of Data import.
Myrange was defined "B2:B" & Rows Count. I change it to Set MyRange = ShMN.Range("B2:B" & ShMN.Cells(Rows.Count, 2).End(xlUp).Row)

For Testing purpose, I used 5 files consisting same Data of 500 rows X 52 Columns with header. I have not used Calculation mode manual, Screen update disable etc (as I generally don't prefer these). You may use the techniques as per your requirement. It takes around 50 seconds to import all 5 files data and only another 3 odd seconds to change the case of B column (in my old laptop)

My test code:

Option Explicit
Sub test()
Dim Tm As Long
Dim FiletoOpen As Variant, ShDataN As Worksheet, ShMN As Worksheet
Dim FileCnt As Long, SelectedBook As Workbook, MyRange As Range, cell As Range
Tm = Timer
Set ShDataN = ThisWorkbook.Sheets(1)
Set ShMN = ThisWorkbook.Sheets(2)

    Dim lastRow As Long, LastTemp As Long 'lasttemp is "last row for table template
    Const StartRowTemp As Byte = 1
    Dim c As Byte 'number of columns
    Dim GetHeader As Range   'find

    'Call Entry_Point 'to prevent screen updating and display alert, the value is False
    'Application.ScreenUpdating = False
    'Application.EnableEvents = False
    Application.DisplayAlerts = False
'    On Error GoTo Handle

    'pick files to import - allow multiselect
    FiletoOpen = Application.GetOpenFilename _
    (FileFilter:="Excel Files (*.xlsx), *.xlsx", Title:="Select Workbook to Import", MultiSelect:=True)

    If IsArray(FiletoOpen) Then
    'delete the content from Analysis table
    ShMN.Rows("2:" & ShMN.Rows.Count).ClearContents   ' moved out of For foleCnt loop

        For FileCnt = 1 To UBound(FiletoOpen)
        Set SelectedBook = Workbooks.Open(Filename:=FiletoOpen(FileCnt))
        ShDataN.Cells.Clear
        SelectedBook.Worksheets("Client").Cells.Copy
        ShDataN.Range("A1").PasteSpecial xlPasteValuesAndNumberFormats
        SelectedBook.Close False

        'locate last empty row in Monthly Table
        lastRow = ShMN.Cells(Rows.Count, 1).End(xlUp).Row + 1

        'locate last row in the new data
        LastTemp = ShDataN.Cells(Rows.Count, 1).End(xlUp).Row

        'do while to find matching headers before copy paste
        c = 1
        Do While ShMN.Cells(1, c) <> ""

        Set GetHeader = ShDataN.Rows(StartRowTemp).Find _
        (What:=ShMN.Cells(1, c).Value, LookIn:=xlValues, MatchCase:=False, lookat:=xlWhole)
        If Not GetHeader Is Nothing Then
            ShDataN.Range(ShDataN.Cells(StartRowTemp + 1, GetHeader.Column), ShDataN.Cells(LastTemp, GetHeader.Column)).Copy
            ShMN.Cells(lastRow, c).PasteSpecial               ' row 2 modified to lastRow
            ShMN.Rows("2:" & ShMN.Rows.Count).ClearFormats
'            Call Range_Case
             'to change the case on column Client's name after copying

        End If 'get Header
        c = c + 1
       Loop

        Next FileCnt

Debug.Print Timer - Tm
Dim MyArr As Variant, FinalArr() As Variant, i As Long
                Set MyRange = ShMN.Range("B2:B" & ShMN.Cells(Rows.Count, 2).End(xlUp).Row)

                'For Each cell In MyRange
                'cell.Value = UCase(cell)
                'Next cell

                MyArr = MyRange.Value
                ReDim FinalArr(LBound(MyArr, 1) To UBound(MyArr, 1))
                For i = LBound(MyArr, 1) To UBound(MyArr, 1)
                FinalArr(i) = UCase(MyArr(i, 1))
                Next

                MyRange.Value = FinalArr

        'MsgBox "Data imported sucessfully", vbInformation, "General Information"

    End If 'isArray
    ShDataN.Cells.Clear

    'With ShNote
    '    .Select
    '    .Range("A1").Select
    'End With

    Application.ScreenUpdating = True
    Application.EnableEvents = True
    Application.DisplayAlerts = True

Debug.Print Timer - Tm
End Sub

Finally I tried the case changing with arrays to minimize excel cell operations as my ethic. You may use your process (commented out). it hardly affect performance in this case.


One try with multiple catch blocks vs nested try I am creating program which will parse .csv file and I am using FileReader and Scanner classes from java API.

FileReader throws FileNotFoundException, IOException.

Scanner's method hasNextLine() and nextLine() throw IllegalStateException and NoSuchElementException.

Should I use 1 try and 4 multiple catch blocks? Or try block nested in another try block(which has 2 catch blocks) with 2 catch blocks?

Code 1:

import java.io.*;
import java.util.Scanner;
import java.util.NoSuchElementException;
import java.lang.IllegalStateException;

public class App {
    public static void main(String[] args) {
        try (FileReader file = new FileReader("Doc.csv")) {
            Scanner sc = new Scanner(file);
            while (sc.hasNextLine()) {
                System.out.println(sc.nextLine());
            }
        } catch (IllegalStateException e) {
            System.out.println(e);
        } catch (NoSuchElementException e) {
            System.out.println(e);
        } catch (FileNotFoundException e) {
            System.out.println(e);
        } catch (IOException e) {
            System.out.println(e);
        }
    }
}

Code 2:

import java.io.*;
import java.util.Scanner;
import java.util.NoSuchElementException;
import java.lang.IllegalStateException;

public class App {
    public static void main(String[] args) {
        try (FileReader file = new FileReader("Doc.csv")) {
            Scanner sc = new Scanner(file);
            try {
                while (sc.hasNextLine()) {
                    System.out.println(sc.nextLine());
                }
            } catch (IllegalStateException e) {
                System.out.println(e);
            } catch (NoSuchElementException e) {
                System.out.println(e);
            }
        } catch (FileNotFoundException e) {
            System.out.println(e);
        } catch (IOException e) {
            System.out.println(e);
        }
    }
}

By the way, I know that System.out.println(e) is not best practice for logging exception. So, please don't write about it

If you are not going to handle each exception differently just use a multicatch:

public static void main(String[] args) {
    try (FileReader file = new FileReader("Doc.csv")) {
        Scanner sc = new Scanner(file);
        while (sc.hasNextLine()) {
            System.out.println(sc.nextLine());
        }
    } catch (IllegalStateException | NoSuchElementException | IOException e) {
        System.out.println(e);
    }
}

The FileNotFoundException is not catched since alternatives in a multi-catch statement cannot be related by subclassing (FileNotFoundException is a subclass of IOException).


Python π = 1 + (1/2) + (1/3) + (1/4) - (1/5) + (1/6) + (1/7) + (1/8) + (1/9) - (1/10) ...1748 Euler I wrote this code to show that my reddit post is correct.

  After the first two terms, the signs are determined as follows: If the denominator is a prime of the form 4m − 1, the sign is positive; if the denominator is a prime of the form 4m + 1, the sign is negative; for composite numbers, the sign is equal the product of the signs of its factors.

  Basically it's the harmonic series minus the non-Gaussian prime reciprocals and reciprocals which factors are an odd multiple of the non-Gaussian primes- beautifully embodying quadratic reciprocity.

This is a very, very inefficient way to calculate π. However, I believe it's the most beautiful. Which is a hard sell, because π algorithms are pretty much the most harmonious things.

This formula for π is my favorite because it clearly shows how a circle is related to the harmonic series, and how that series is related to the prime number theorem and quadratic reciprocity.
I love all algorithms for π, this is for its 'insight' it provides in relating π, primes, and quadratics.

Something to note is that swapping the logic here from n%4==1 to n%4==3 results in the sum = π/2 , and converges a bit faster.

import decimal
iters = int(input('Number of Iterations: '))
D = decimal.Decimal
decimal.getcontext().prec = 100
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
s = D(0)
for x in range(1, iters):
    clist = [int(i) for i in prime_factors(x)]
    plist = [n for n in clist if n%4==1]
    if len(plist)%2!=0:
        s-=1/D(x)
    else:
        s += 1/D(x)
    print(s)

What you are approximating is
$$ \pi =\sum_{m=1}^{\infty}\frac{(-1)^{s(m)}}{m},$$
where \$s(m)\$ counts the number of appearances of primes of the form \$4k+1\$ in the prime decomposition of \$m\$, compare

How can we prove \$\pi =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}-\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\cdots\,\$?

on Mathematics Stack Exchange.

The computation of the factor \$ (-1)^{s(m)} \$ can be done more efficiently: Instead of creating a list of all prime factors of \$m \$, then filtering the list for prime factors of the form \$4k+1\$, and finally counting the filtered list, you can compute the sign while factoring the number:

def sign_for_pi_series(n):
    """ Returns sign for 1/n in the pi series.

    The sign is -1 if n has an odd number of prime factors of the form 4k+1,
    and +1 otherwise.
    """
    s = 1
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i % 4 == 1:
                s = -s
    if n > 1 and n % 4 == 1:
        s = -s
    return s

The summation then simplifies to

sum_pi = sum(D(sign_for_pi_series(x))/D(x) for x in range(1, iters + 1))
print(sum_pi)


Generic Comparator Using Class Fields & Lambda Java I have a grid in which i have to display some/all fields of a Java Class,
this grid displays the List of elements of that class type.

I have to sort this list provided:

Class type of the List item
Field name of the class to be sorted

to get field from a class by field name

private static <T> Field getField(Class<T> clazz,String fieldName){
    Field field = null;
    try {
        field = clazz.getDeclaredField(fieldName);
    }catch(java.lang.NoSuchFieldException e){
        e.printStackTrace();
    }
    return field;
}

and the comparator method using lambda, providing class type, field name to sort, and sort order

public static <T> Comparator<T> getGenericComparatorLambda(Class<T> clazz,
        String fieldName,boolean orderByAsc){

    //get field from class
    final Field field = getField(clazz, fieldName);
    field.setAccessible(true);

    //Lambda comparator
    Comparator<T> orderByComparator = (f1, f2) -> {

        Comparable compA = null;
        Comparable compB = null;

        // getting fields from object f1,f2
        try {
            compA =(Comparable) field.get(f1);
            compB =(Comparable) field.get(f2);
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }

        // handling null comparators
        if(compA == null)
            return -1;
        else if(compB == null)
            return 1;

        return compA.compareTo(compB);
    };

    //reverse comparator if order is descending
    if (orderByComparator != null && !orderByAsc)
        orderByComparator = orderByComparator.reversed();

    return orderByComparator;
}

As the code consists of Lambda as well as generics of java,
I want an overall analysis of the code, improvements where needed, how much is the performance penalty when using generics with long lists.

If you want suggestions for improvement, here is one:

The following code:

private static <T> Field getField(Class<T> clazz,String fieldName){
    Field field = null;
    try {
        field = clazz.getDeclaredField(fieldName);
    }catch(java.lang.NoSuchFieldException e){
        e.printStackTrace();
    }
    return field;
}

is best rewritten as follows:

private static <T> Field getField(Class<T> clazz,String fieldName) {
    try {
        return clazz.getDeclaredField(fieldName);
    }catch(java.lang.NoSuchFieldException e){
        throw new RuntimeException(e);
    }
}

The following code:

//Lambda comparator
Comparator<T> orderByComparator = (f1, f2) -> {

    Comparable compA = null;
    Comparable compB = null;

    // getting fields from object f1,f2
    try {
        compA =(Comparable) field.get(f1);
        compB =(Comparable) field.get(f2);
    } catch (IllegalAccessException e) {
        e.printStackTrace();
    }

    // handling null comparators
    if(compA == null)
        return -1;
    else if(compB == null)
        return 1;

    return compA.compareTo(compB);
};

is best rewritten as follows:

Comparator<T> orderByComparator = (f1, f2) -> {
    Comparable compA, compB;
    try {
        compA = (Comparable) field.get(f1);
        compB = (Comparable) field.get(f2);
    } catch (IllegalAccessException e) {
        throw new RuntimeException(e);
    }
    return Objects.compare(compA, compB, Comparator.naturalOrder());
};

in short:

lose the useless comments; a comment is only useful if it says something that is not immediately obvious by looking at the code
do not initialize variables to nonsensical values, because then the compiler will not warn you when you forget to assign something meaningful to them
if you do not know what to do with an exception, do not print a stack trace, throw a runtime exception instead.

Generics and lambdas have no impact on performance.


Replace space with %20 This is not very memory-efficient. Can you please suggest a better way or improvement?

public class Test{

    public static void main(String[] args) {
        System.out.println(replaceSpace("All men must die"));
    }

    public static String replaceSpace(String s) {
        String[] stringArray = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for(String s3 : stringArray) {
            sb.append(s3);
            sb.append("%20");
        }
        // if the last character is not space then, don't append %20.
        if(s.charAt(s.length()-1) != ' ') {
            return sb.substring(0, sb.length()-3).toString();
        }

        return sb.toString();
    }
}

Don't do this yourself. Instead use java.net.URLEncoder or another library implementation of url encoding. You'll also get support for other characters as well besides space.


Editing a playlist configuration file What I'm trying to do here is first set the first eight variables to the proper default values. That's the first area I'm thinking there might be a way to optimize. Is there anyway to set both variables at once for example I know in PHP I could do $title=$d_title="value"; Is there any way to consolidate that section? (The variables prefixed with d_ will not change, but the same variable without the d_ may be changed.)

Then the rest of the snippet should do the following:

If the second argument is NOT "config"

Look in the file to see if the a line with the format ${sfile}_variablename="*" exists.

If it does, use sed to replace the contents of the quotes with the new variable
If it does not, append the line in its entirety

If the second argument IS "config"

If a line exists that contains ${sfile}_variablename, read in what's between the quotes and assign it to the variablename
If not, set the variablename to the default value

Below is how I was achieving that. Is there any way to do this in a more simplified or compact manner?

In this case, sdir is a base path I define elsewhere, and sfile is another prefix. Those are hard-coded into the top of the script, so those will always be correct.

d_finddir=${2:-"${sdir}/music/trine_soundtrack/"}
finddir=${d_finddir}

d_title=${3:-"Random Tangent"}
title=${d_title}

d_desc=${4:-"Random Tangent Playlist"}
desc=${d_desc}

d_rand=${5:-"randomize"}
rand=${d_rand}

if [ ! "${finddir}" = "config" ]; then
    if egrep -q "${sfile}_finddir" "${sdir}/config.cfg"; then
        sed -r -i "s,(${sfile}_finddir=).*,\\1\"${finddir}\"," "${sdir}/config.cfg"
    else
        printf "%s_finddir=\"%s\"\n" "${sfile}" "${finddir}" >>"${sdir}/config.cfg"
    fi

    if egrep -q "${sfile}_title" "${sdir}/config.cfg"; then
        sed -r -i "s,(${sfile}_title=).*,\\1\"${title}\"," "${sdir}/config.cfg"
    else
        printf "%s_title=\"%s\"\n" "${sfile}" "${title}" >>"${sdir}/config.cfg"
    fi

    if egrep -q "${sfile}_desc" "${sdir}/config.cfg"; then
        sed -r -i "s,(${sfile}_desc=).*,\\1\"${desc}\"," "${sdir}/config.cfg"
    else
        echo "${sfile}_desc=\"${desc}\"">>"${sdir}/config.cfg"
        printf "%s_desc=\"%s\"\n" "${sfile}" "${desc}" >>"${sdir}/config.cfg"
    fi

    if egrep -q "${sfile}_mode" "${sdir}/config.cfg"; then
        sed -r -i "s,(${sfile}_mode=).*,\\1\"${rand}\"," "${sdir}/config.cfg"
    else
        printf "%s_mode=\"%s\"" "${sfile}" "${rand}" >>"${sdir}/config.cfg"
    fi
else
    if egrep -q "${sfile}_finddir" "${sdir}/config.cfg"; then
        finddir=$(egrep "${sfile}_finddir" "${sdir}/config.cfg" | egrep -o "\".+\"" | sed 's/\"//g')
    else
        finddir=${d_finddir}
    fi

    if egrep -q "${sfile}_title" "${sdir}/config.cfg"; then
        title=$(egrep "${sfile}_title" "${sdir}/config.cfg" | egrep -o "\".+\"" | sed 's/\"//g')
    else
        title=${d_title}
    fi

    if egrep -q "${sfile}_desc" "${sdir}/config.cfg"; then
        desc=$(egrep "${sfile}_desc" "${sdir}/config.cfg" | egrep -o "\".+\"" | sed 's/\"//g')
    else
        desc=${d_desc}
    fi

    if egrep -q "${sfile}_mode" "${sdir}/config.cfg"; then
        rand=$(egrep "${sfile}_mode" "${sdir}/config.cfg" | egrep -o "\".+\"" | sed 's/\"//g')
    else
        rand=${d_rand}
    fi
fi

Using sed to its fullest

sed is surprisingly powerful tool. For example:

finddir=$(sed -n -E /"${sfile}_finddir"'/s/[^"]*\"([^"]*).*/\1/p' "${sdir}/config.cfg")
[ -z ${finddir} ] && finddir=${d_finddir}

achieves the desired effect without any egrep.

Explanation: The last line ([ -z ]) tests whether finddir has zero length (meaning that sed didn't find the line in interest) and if so (&&) assigns it a default value.

Editing the config file

I am not sure I understand the decision to edit the config file via the script. It is much more natural (at least within the context provided) to edit it manually.


ASP.NET Core singleton with a thread-safe property that can be changed Thanks to ASP.NET Core dependency injection, there's no need to follow the Singleton pattern; any class will do.
What I want to do is to have a class that will store a value that'll be used by another methods inside the app. A specific class is in charge of updating this value. What I'm concerned is the problem of a thread reading the value while the specific class updates it, given that I haven't done enough concurrency to feel confident.
So I came up with this. Is it correct for what I want it to do?
public class DynamicValueStore
{
    private readonly object _lock_obj;

    private string _value;

    public string Value
    {
        get
        {
            lock (_lock_obj)
            {
                return _value;
            }
        }
    }

    public DynamicValueStore()
    {
        _lock_obj = new object();
        _value = string.Empty;
    }

    public void UpdateValue(string value)
    {
        if (string.IsNullOrWhiteSpace(value))
        {
            throw new ArgumentNullException(nameof(value));
        }
        lock (_lock_obj)
        {
            _value = value;
        }
    }
}
```

That will lock it down for sure.  If you know you will have more reads then writes, which is common, you should look at the ReaderWriterLockSlim class.   What you have will only allow one read and one write and they all queue up in line waiting their turn.  The ReaderWriterLockSlim class will still only allow one write at a time but allow multiple reads at a time.


GreetingCard problem with Coordinates This is a practice problem on Kattis

I have exceeded the time limit for the 5th out of 11 test case. Can anyone inspire me what could be done to optimize the code?

Problem Description

  Quido plans to send a New Year greeting to his friend Hugo. He has
  recently acquired access to an advanced high-precision plotter and he
  is planning to print the greeting card on the plotter.

  Here’s how the plotter operates. In step one, the plotter plots an
  intricate pattern of n dots on the paper. In step two, the picture
  in the greeting emerges when the plotter connects by a straight
  segment each pair of dots that are exactly 2018 length units
  apart.

  The plotter uses a special holographic ink, which has a limited
  supply. Quido wants to know the number of all plotted segments in the
  picture to be sure that there is enough ink to complete the job.

  Input

  The first line of input contains a positive integer n specifying the
  number of plotted points. The following n lines each contain a pair of
  space-separated integer coordinates indicating one plotted point. Each
  coordinate is non-negative and less than 2^31. There are at most
  10^5 points, all of them are distinct.

  In this problem, all coordinates and distances are expressed in
  plotter length units, the length of the unit in the x-direction and in
  the y-direction is the same.

  Output

  The output contains a single integer equal to the number of pairs of
  points which are exactly 2018 length units apart.

Sample input

4
20180000 20180000
20180000 20182018
20182018 20180000
20182018 20182018

Output

4

Here is my code

import java.util.*;

class Coordinates {
    int x;
    int y;

    public Coordinates(int x,int y) {
        this.x=x;
        this.y=y;
    }

    public double distanceWith(Coordinates z) {
        return Math.hypot((x-z.x),(y-z.y));
    }
}

class GreetingCard {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<Coordinates> set = new HashSet<>();
        int count = sc.nextInt();
        int total = 0;
        for (int i=0;i<count;i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            Coordinates curr = new Coordinates(x,y);
            if (i!=0) {
                total+=findDistances(curr, set);
            }
            set.add(curr);
        }
        System.out.println(total);
    }

    public static int findDistances(Coordinates curr, HashSet<Coordinates> set) {
        int total = 0;
        for (Coordinates inside : set) {
            if (inside.distanceWith(curr)==2018) {
                total+=1;
            }
        }
        return total;
    }
}

Calculating the distance between each pair of points is expensive. Since the coordinates are all integers, you can first calculate which delta-x and delta-y can lead to the distance 2018 at all. Define a function candidates(point, set) that filters the possible candidates. To do this efficiently, group the points by their x coordinate. Then, for a given x, you only have to look at a few of these groups.

Grouping the points improves performance because grouping has complexity around \$\mathcal O(n)\$, where \$n\$ is the number of points.

Afterwards, finding the candidate points is a simple lookup: for each delta in (-2018, -1680, -1118, 0, 1118, 1860, 2018) you need one lookup, which again sums up to \$\mathcal O(n)\$.

In summary, the number of comparisons will be much less than the \$n\cdot n\$ from your current code.


Where are my downvotes? I've been thinking my posts aren't that great, and so I've been wanting to improve them.
One sure fire way to do this is to look at all of my downvoted posts.
Not knowing if Stack Exchange allows you to do this already, I decided I should learn SQL, and wrote a SEDE query.
The query, downvoted posts by user, takes a single parameter which is the user id.
And returns a list of downvoted posts, with a link to the post, its score, and the amount of downvotes.

I've never written a line of SQL before, and so I'm unsure if my query is any good.
I think using GROUP BY is a bit weird to get a sum of all the downvotes, is there a better way to do this?
And having looked at various other SEDE queries, I don't know if my style is any good either.

declare @user_id int = ##UserId:int##

SELECT
    p.Id as [Post Link],
    p.Score,
    sum(case when p.Id = v.PostId then 1 else 0 end) as [Downvotes]
FROM
    Posts p
inner join
    Votes v on p.Id = v.PostId
WHERE
    p.OwnerUserId = @user_id
and v.VoteTypeId=3
GROUP BY
    p.Id, p.Score
ORDER BY 'Downvotes' DESC, Score DESC

If this is actually your first SQL you're quite good in learning new languages.

Some remarks:

The Group By is not weird, it's the SUM, you apply a conditional aggregation but the result is the same as a simple COUNT(*) (you can always get the same result using different ways in SQL).

The ORDER BY 'Downvotes' DESC will not work as expected, because single quotes specify strings in SQL, so this is not sorting by the actual number of downvotes, but by the string 'Downvotes' (which of course is the same for all rows). In your case you can simply use Downvotes, [] ([Downvotes]) or better Standard SQL double quotes ("Downvotes") are only needed for names including spaces or non-standard characters, like "foo bar?"

declare @user_id int = ##UserId:int##

SELECT
    p.Id as "Post Link",
    p.Score,
    count(*) as Downvotes
FROM
    Posts p
inner join
    Votes v on p.Id = v.PostId
WHERE
    p.OwnerUserId = @user_id
and v.VoteTypeId=3
GROUP BY
    p.Id, p.Score
ORDER BY Downvotes DESC, Score DESC


Vectorizing the product of an array of complex numbers I am trying to write fast/optimal code to vectorize the product of an array of complex numbers.  In simple C this would be:

#include <complex.h>
complex float f(complex float x[], int n ) {
  complex float p = 1.0;
  for (int i = 0; i < n; i++)
    p *= x[i];
  return p;
}

However, gcc can't vectorize this and my target CPU is the AMD FX-8350 which supports AVX.  To speed it up I have tried:

typedef float v4sf __attribute__ ((vector_size (16)));
typedef union {
  v4sf v;
  float e[4];
} float4;
typedef struct {
  float4 x;
  float4 y;
} complex4;
static complex4 complex4_mul(complex4 a, complex4 b) {
  return (complex4){a.x.v*b.x.v -a.y.v*b.y.v, a.y.v*b.x.v + a.x.v*b.y.v};
}
complex4 f4(complex4 x[], int n) {
  v4sf one = {1,1,1,1};
  complex4 p = {one,one};
  for (int i = 0; i < n; i++) p = complex4_mul(p, x[i]);
  return p;
}

Can this code be improved for AVX and is it as fast as it can get?

I was wondering if the compiler would more easily be able to vectorize it without the union-within-struct and the potential type punning of the e member (which doesn't seem to be used).

How about this?

typedef float v4sf __attribute__ ((vector_size (16)));
typedef struct {
  v4sf x;
  v4sf y;
} complex4;

static inline v4sf complex4_mul_r(v4sf a_r, v4sf a_i, v4sf b_r, v4sf b_i) {
  return a_r*b_r -a_i*b_i;
}
static inline v4sf complex4_mul_i(v4sf a_r, v4sf a_i, v4sf b_r, v4sf b_i) {
  return a_r*b_i + a_i*b_r;
}

complex4 f4(v4sf x_r[], v4sf x_i[], int n) {
  v4sf one = {1,1,1,1};
  v4sf p_r = one;
  v4sf p_i = one;
  v4sf p_r_temp;
  for (int i = 0; i < n; i++)
  {
     p_r_temp = complex4_mul_r(p_r, p_i, x_r[i], x_i[i]);
     p_i = complex4_mul_i(p_r, p_i, x_r[i], x_i[i]);
     p_r = p_r_temp;
  }
  return (complex4){p_r, p_i};
}

Looking at the assembly on https://godbolt.org/ it seems it gets fully vectorized. I can't get the godbolt sharing links to work.

I'm thinking about whether it might be possible to stick both the real and imaginary parts in the same vector, and use __builtin_shuffle() to permute them as necessary. Can't quite work it out.


Brainfuck compressor in Python Just for fun, I created a script called TinyBF which can compress Brainfuck programs into a format half their size. For example, take a famous hello world program clocking in at 78 bytes:

--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.

When put into TinyBF format, it is only 39 bytes:

7#!00"7!'!7?,,,?#B!?.>!$,.>?!.

The steps for encoding are:

Translate all characters in the input using the following dictionary: {'>': '2', '<': '3', '+': '4', '-': '5', '.': '6', ',': '7', '[': '8', ']': '9'}.
Split the string into chunks of two characters each - pad the last item with a trailing zero if it is only one digit long.
Make a string using the resultant charcodes of the previous list.

Without further ado, here's the compress and decompress methods (tinybf.py):

def compress(code):
    """compress(code): Compress a string of Brainfuck code into TinyBF format."""
    translated = code.translate({62: 50, 60: 51, 43: 52, 45: 53, 46: 54, 44: 55, 91: 56, 93: 57})
    return "".join(chr(int(translated[pos:pos + 2].ljust(2, "0"))) for pos in range(0, len(translated), 2))

def decompress(code):
    """decompress(code): Decompress a string of TinyBF code into Brainfuck format."""
    translated = "".join(str(ord(c)) for c in code).translate({50: 62, 51: 60, 52: 43, 53: 45, 54: 46, 55: 44, 56: 91, 57: 93})
    return translated.rstrip("0")

And here's the script/output I used to test it:

import tinybf

original_code = "--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+."
compressed_code = tinybf.compress(original_code)

print(compressed_code) # 7#!00"7!'!7?,,,?#B!?.>!$,.>?!.
print(len(original_code), len(compressed_code)) # 78 39

new_code = tinybf.decompress(compressed_code)
print(new_code == original_code) # True

Any advice on the code or improvements I could make? I'm also looking for name advice if possible - I settld on TinyBF for this question, but I also considered Braincrunch and Tinyfuck, so if you have thoughts on those, that'd be great.

Since you seem to want code golf over readable code this may not be the answer you want. All the suggestions I make are things I would prefer, but I don't think it's that uncommon for others to disagree. The outcome either way is still pretty ugly.

Your code isn't PEP 8 compliant, and is generally pretty hard to read.
Your one-line docstrings are quite poor, docstring wise. Contrast with:

"""Compress Brainfuck code to TinyBF"""

Use str.maketrans rather than manually make the translation table.

COMPRESS_TABLE = str.maketrans({'>': '2', '<': '3', '+': '4', '-': '5', '.': '6', ',': '7', '[': '8', ']': '9'})

Alturnately you can define both from a common string.

_COMPRESS_STR = '>2 <3 +4 -5 .6 ,7 [8 ]9'
COMPRESS_TABLE = str.maketrans(dict(_COMPRESS_STR.split()))
DECOMPRESS_TABLE = str.maketrans(dict(_COMPRESS_STR[::-1].split()))

I would prefer itertools.zip_longest over manually zipping and justifying.
You can split decompress over multiple lines to make the code more readable.

import itertools

_COMPRESS_STR = '>2 <3 +4 -5 .6 ,7 [8 ]9'
COMPRESS_TABLE = str.maketrans(dict(_COMPRESS_STR.split()))
DECOMPRESS_TABLE = str.maketrans(dict(_COMPRESS_STR[::-1].split()))

def compress(code: str) -> str:
    """Compress Brainfuck code into TinyBF"""
    return "".join(
        chr(int(a + b))
        for a, b in itertools.zip_longest(
            *2*[iter(code.translate(COMPRESS_TABLE))],
            fillvalue="0",
        )
    )

def decompress(code: str) -> str:
    """Decompress TinyBF into Brainfuck"""
    return (
        "".join(str(ord(c)) for c in code)
            .translate(DECOMPRESS_TABLE)
            .rstrip("0")
    )


Implementation of Stack using Linked List Please review my code and help me to improve it. I have written this code using template. Can I use more C++11? Is using top in this code is necessary?

#include <iostream>

template<class T>
class Stack{
 struct Node{
 T data;
 Node *next;
 Node(T val):data(val),next(nullptr) {}
 };
 Node *head;
 int top;

 public:
     Stack(){
     top=-1;
     head=nullptr;
     }
    ~Stack();
     bool stack_empty();
     void push(T);
     T pop();

     void display(std::ostream& out = std::cout) const
     {
       Node *node=head;
       while(node!=nullptr){
        out<<node->data<<" ";
        node=node->next;
       }
     }
};
template<class T>
bool Stack<T>::stack_empty(){
  if(top==-1)
    return true;
  else
    return false;
}

template<class T>
void Stack<T>::push(T val){

  if(top>=-1){
    top++;
    Node *node=new Node(val);
    Node *tmp=head;
    if(tmp==nullptr) head=node;
    else{
        while(tmp->next!=nullptr)
            tmp=tmp->next;
        tmp->next=node;
    }
  }
  else
    std::cout<<"Overflow"<<std::endl;
}

template<class T>
T Stack<T>::pop(){
  if(stack_empty()==true)
    std::cout<<"Underflow"<<std::endl;
  else{
    top--;
    Node *node=head;
     while(node->next!=nullptr){
        node=node->next;
     }
    return node->data;
  }
}

template<class U>
std::ostream & operator <<(std::ostream& os, const Stack<U>& s){
s.display(os);
return os;
}

template<class T>
Stack<T>::~Stack(){
Node *tmp=nullptr;
  while(head){
    tmp=head;
    head=head->next;
    delete tmp;
  }
  head=nullptr;
}
int main()
{
 Stack<int> stack1;

 stack1.push(3);
 stack1.push(4);
 stack1.push(11);
 stack1.push(30);
 std::cout<<stack1<<std::endl;
 std::cout<<stack1.pop()<<std::endl;
    return 0;
}

You leak every single node you pop. You need to delete the node.

You should add move and emplace push overloads. So that non-copyable T can be stored.

you check against "overflow" by testing top is less than -1. However signed overflow is undefined behavior and if you ever had more than 2 billion items in your stack you probably ran out of ram earlier. You can check if the stack is empty by testing if head is nullptr. So top isn't really necessary.

For every operation you seek the end of the stack, that is not necessary at all.

template<class T>
void Stack<T>::push(T val){
    top++;
    Node *node=new Node(val);
    node->next = head;
    head=node;
}

template<class T>
T Stack<T>::pop(){
  if(stack_empty()==true)
    std::cout<<"Underflow"<<std::endl;
  else{
    top--;
    Node *node=head;
    head = node->next;
    T tmp = std::move(node->data);
    delete node;
    return tmp;
  }
}


Sort digits in Python Given an integer, sort the digits in ascending order and return the
  new integer.

  Ignore leading zeros.

  Parameters:

  Input: num {Integer}
  Output: {Integer}

  Constraints:

  Do not convert the integer into a string or other data type.
  Time: O(N) where N is the number of digits.
  Space: O(1)

  Examples:

  8970 --> 789
  32445 --> 23445
  10101 --> 111

My code (as follows) works similar to the counting sort:

def sort_digits(n):
    digit_counts = {}
    result = 0

    while n > 0:
        digit = n % 10
        digit_counts[digit] = digit_counts.get(digit, 0) + 1
        n /= 10

    power = 0
    for i in range(10, -1, -1):
        if i in digit_counts:
            while digit_counts[i] >= 1:
                result +=  i * (10 ** (power))
                power += 1
                digit_counts[i] -= 1

    return result

1) Use collections.Counter

from collections import Counter. Counter is a subclass of dict that helps keep tallies. This way, you don't need .get(digit, 0) or if i in digit_counts, making your code look a bit cleaner.

2) Iterate in increasing order

Right now, you need a power variable to track which position to place the next digit in. If you iterated in the opposite direction (i.e. range(10)), you could do result *= 10 in each loop.

3) Use a for loop instead of while

Whenever you are iterating and incrementing/decrementing, you have the opportunity to use a for loop. In this case, for while digit_counts[i] >= 1 you don't care about the number of iterations, so you can use the _ as a "throwaway variable".

4) Code localization

Move result = 0 down so that it's just above where it starts being used. Code localization improves readability - depending on your source, the human brain can only remember 4-7 things at once. The fewer variables your reader has to track, the better.

Final Result

from collections import Counter

def sort_digits(n):
  digit_counts = Counter()

  while n > 0:
    digit_counts[n % 10] += 1
    n /= 10

  result = 0
  for i in range(10):
    for _ in range(digit_counts[i]):
      result = 10 * result + i

  return result


Responsive buttons for post navigation I have tried to make two buttons to be used for post navigation below each post on a blog:

It works, however - it feels like to much code and classes for so little. I'm using Bootstrap 4, alpha 6. Is there any easier way to make something like this?

HTML:

    <button type="button" class="btn btn-secondary btn-navigation mr-2 bg-gray-900 text-muted border-0 rounded-0">Previous

      The title of the previous post
   </button>

    <button type="button" class="btn btn-secondary btn-navigation bg-gray-900 text-muted border-0 rounded-0">Next

      The title of the next post. It might be long. Very very long
   </button>

CSS:

.wordwrap {
  white-space: normal;
}

.bg-gray-800 {
  background-color: #dfdfdf;
}

.bg-gray-900 {
  background-color: #efefef;

}

CodePen with the code

Having an a element inside a button element is not valid. You can’t nest "interactive" elements.

As these are links (navigating to resources) and not buttons (changing state), you should use the a element instead of the button element.

When using a, you could use the next and prev link types.

Using the br element in this context is possibly not appropriate. It must only be used for meaniningful line breaks. But if you can’t use a colon to separate the label from the title (e.g., for text browser users), using br might make sense.

You could use the cite element for the titles of the linked posts.

So the plain HTML could look like this:

Previous: The title of the previous post
Next: The title of the next post. It might be long. Very very long

If you need additional elements for your font-based icons, you should use the span element instead of the i element. The meaning of i doesn’t cover decorative icons.


Converts data in a HashMap to a custom object I have a HashMap and I want to convert data in it to a Response object, but I do not find it clean and optimized. Is there a better way to achieve this?

class Converter{

   public static void main(String[] args) {

      Map<String, Long> map = new HashMap<String, Long>();
      map.put("111", 80) // first
      map.put("1A9|ppp", 190) // second
      map.put("98U|6765", 900) // third
      map.put("999|aa|local", 95) // fourth

      List<Response> responses = new ArrayList<>();
      for(String key : map.keySet()){
        Response response = new Response();
        String[] str  = key.split("\\|");
        response.id = str[0] //id is always present in key i.e 111, 1A9, 98U,999
        if(str.length == 2) {
             if(str.matches("-?\\d+(\\.\\d+)?");){ // check if is numeric
                  response.code = str[1]; // 6765
             }
             else{
                  response.city = str[1]; //ppp
             }
        }
         if(str.length == 3){
                  response.client = str[1]; //aa
                  response.type = str[2];   // local
         }
        response.qty = map.get[key];
        responses.add(response);
      }
   }
}

class Response{

String id;
String city;
Long code;
String client;
String type;
Long qty;
// getters and setters

}

As dustytrash already mentioned in a comment, it would be much more sensible to simply use the Response object as the map key and be done.

If this is not possible due to unknown external constraints, move the translation to and from String into the Response object.

class Response {
    public static Response fromString(String s) {
        // ... do the parsing here
    }

    @Override
    public String toString() {
        // generate "98U|6765" or whatever
        // debatable: maybe don't use the overridden toString for the technical representation
    }
}

This encapsulates the nitty-gritty details of conversion in the class itself.

The converson then boils down to

map.keySet().stream()
    .map(Response::fromString)
    .collect(Collectors.toList());


Shuffling chunks of ints in an array The shuffle method in ShuffleMethods.java takes an array of ints and shuffles them by chunks of ints in another array. So for example, if we had an array of ints called nums comprising of 0,1,2,3,4,5 and a chunks of ints of 2,1,3. The method reads the first element of the chunks array which is 2. The shuffle method then gets the first two elements of the nums array 0 & 1 and puts them at the end of the array to give this result: 2,3,4,5,0,1, Then for the next chunks of 1 the number is 2 is selected and put on top of the 0,1 giving this result 3,4,5,2,0,1. And then finally the last chunks of 3 selects 3, 4, 5 and puts them on top of the 2 giving this result 3,4,5,2,0,1.

The shuffle method algorithm complexity is currently \$O(n^3)\$. I am looking to get it down to \$O(n)\$. Also, I am hoping to improve the pairs method which finds the number of consecutive numbers from the original deck that are still together in the shuffled deck.

ShuffleApp.java

package Shuffle;

import java.util.Arrays;
public class ShuffleApp{

public static void main(String[] args){
      ShuffleMethods test = new ShuffleMethods();
      int[] test1 = {2, 1, 3};

     test.makeNew(6);
     test.shuffle(test1);
     test.pairs();
     test.print();
   }

}

Shuffle.java

package Shuffle;
public interface Shuffle{
    public void makeNew(int size);
    public int[] getCurrent();
    public void shuffle(int[] chunks);
    public int pairs();
}

ShuffleMethods.java

package Shuffle;
import java.util.*;

public class ShuffleMethods implements Shuffle{

    private int[] nums;
    private int[] numsCopy;

    /**Fills nums with ints based on user parameter from 0 to size-1**/
    public void makeNew(int size){
        nums = new int[size];
        for(int i = 0; i < size; i++){
            nums[i] = i;
        }
        numsCopy = nums.clone();
    }

    public int[] getCurrent(){
        return nums;
    }

    /**Shuffles the ints**/
    public void shuffle(int[] chunks){

        int temp = 0;
        int count = 0;
        int endIndex = nums.length;

            count = 0;
            while(chunks[i] > count) {

                temp = nums[0];

                for(int k = 1; k < endIndex; k++) {

                    //Move all the elements back
                    nums[k-1] = nums[k];

                }

                nums[endIndex-1] = temp;

                count++;

            }
            endIndex -= chunks[i];

        }
    }

    /**Returns the number of pairs of consecutive numbers in the shuffled deck that were together in the original**/
    public int pairs(){

       ArrayList<Integer> pairList = new ArrayList<Integer>();
        int pairs = 0;

        for(int i = 1; i < numsCopy.length; i++) {

            if (numsCopy[i-1] == numsCopy[i] - 1  && !pairList.contains(numsCopy[i-1]) && !pairList.contains(numsCopy[i])) {
                pairList.add(numsCopy[i-1]);
                pairList.add(numsCopy[i]);
            }
        }

         for(int i = 1; i < nums.length; i++) {

           if (nums[i-1] == nums[i] - 1 && pairList.contains(nums[i-1]) && pairList.contains(nums[i])) {
             pairList.remove(Integer.valueOf(nums[i-1]));
             pairList.remove(Integer.valueOf(nums[i]));
                pairs++;
            }

         }
       System.out.println("Number of pairs " + pairs);
        return pairs;

}

pairs is overcomplicated indeed. Notice that a block of size k contributes k-1 pairs, and no other pair exists. So the total is a sum of (k - 1) taken over all blocks. Final observation is that the sizes of blocks add up to the size of array, therefore pairs = num.size() - blocks.size() is all you need.
shuffle can be performed in linear time (strictly speaking, in \$O(kn)\$, where k is number of blocks) in place (\$O(1)\$ space complexity). The key algorithm is known as rotate. One possible implementation is

void rotate(int[] array, int first, int mid, int last) {
    reverse(array, first, mid);
    reverse(array, mid, last);
    reverse(array, first, last);
}

There also is an arguably faster implementation, where each element is moved exactly once. Try to figure it out yourself.


Finding all words without a certain character I am doing some exercises in this book. I've been trying to avoid Regex so far in my mission to teach myself computer science, as it makes my head hurt. That said - one of the exercises is to find all words without the letter 'e'.

I have:

/\b([^e ]+)\b/

There must be a better way using Regex to find all words that don't contain a certain character.

Here is an example:

toMatch = /\b([^e ]+)\b/;
testArr = ["platypus", "elvis", "javascript", "stackoverflow"];

for (str in testArr)
  console.log(testArr[str] + " has no e -> " + toMatch.test(testArr[str]));

If just looking for a single character in a set of strings, I would think basic string manipulation would be sufficient.

What is not clear to me from your question is why you are using word boundaries in your regex definition when the array itself is just single words.  Is your intent to analyze individual words in each of the array strings (with string perhaps consisting of multiple words) or are you only truly going to have single word string in the array?

For now, I will provide answer given the assumption of an array of single words.

To do that, I would simply use Array.filter() in combination with String.indexOf().

var needle = 'e';
var haystack = ["platypus", "elvis", "javascript", "stackoverflow"];
var filtered = haystack.filter( str => (str.indexOf(needle) === -1) );

Based on your comment that array entries could have multiple words, I would suggest using Array.reduce() to build all array of all words across all entries that do not have have the needle character in them.

var needle = 'e';
// note global flag here to get all matches
var regex = new RegExp('\\b([^' + needle + ']+)\\b', 'g');
var haystack = ["platypus", "elvis", "javascript", "stackoverflow", "some multi-word string"];
var result = haystack.reduce(
    (aggregator, str) => {
        while (match = regex.exec(str) !== null) {
            aggregator.push(match[1]);
        }
    },
    []
);
console.log(result); // ["platypus", "javascript", "multi-word", "string"]


Basic android calculator So this is my code and I would like to add subtraction, multiplication and division. If you have any suggestions on algorithms to use I would be very happy to see it. I do not wish to copy the code, I just want an outline of how to simply, and efficiently create a calculator. I want to make a calculator for KIDS with a friendly UI maybe showing dogs, cats, food etc. as the buttons. With 1 dog/cat for the 1 button and so on.....
I wish to put ads in this application, but I want the ads just to be under a donation/ad tab.

Tell me what you think, questions, comments and concerns would be very much appreciated to help develop my app :)

package com.nickmarcoose.addingcalculatorfree;

import android.app.Activity;
import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class Addition extends Activity
{
  EditText amount1;
  EditText amount2;
  TextView views;
  Button Addition1;
  double a;
  double b;
  double c;

  @Override
  public void onCreate(Bundle savedInstanceState)
  {

    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);
    initControls();
  }

  private void initControls()
  {
    amount1=(EditText)findViewById(R.id.amount1);
    amount2=(EditText)findViewById(R.id.amount2);
    views=(TextView)findViewById(R.id.view);
    Addition1=(Button)findViewById(R.id.start);
    Addition1.setOnClickListener(new Button.OnClickListener()
    {
      public void onClick (View  view) { calculate();}
    });
  }

  private void calculate()
  {

    a=Double.parseDouble(amount1.getText().toString());
    b=Double.parseDouble(amount2.getText().toString());
    c=b+a;
    views.setText(Double.toString(c));
  }
}

Not very familiar with Android development, so some of this may be totally off the rails.

Depending on how educational you want this to be, you could visually demonstrate simple algorithms to teach how various operations work (e.g. animations). Also, since you're targeting little kids, I'm not sure double is necessary.

Kid-friendly algorithms you could demonstrate below. You could step through each stage of an operation, e.g. by moving animals from pile to pile. You could skip demonstrations if the numbers are large, or make them run in the background/interruptable.

public int add(int left, int right)
{
    if (right == 0)
    {
        return left;
    }
    return add(left + 1, right - 1);
}

public int subtract(int left, int right)
{
    if (right == 0)
    {
        return left;
    }
    return subtract(left - 1, right - 1);
}

public int multiply(int left, int right)
{
    if (left == 0 || right == 0)
    {
        return 0;
    }

    if (left == 1)
    {
        return right;
    }
    else if (right == 1)
    {
        return left;
    }

    if (left < right)
    {
        return multiplyByAdding(right, left, 0);
    }

    return multiplyByAdding(left, right, 0);
}

private int multiplyByAdding(int baseNumber, int timesLeft, int productSoFar)
{
    if (timesLeft == 0)
    {
        return productSoFar;
    }

    return multiplyByAdding(baseNumber, timesLeft - 1, productSoFar + baseNumber);
}

//division by zero needs to be handled at UI level to explain why it doesn't work
//you might want to do something other than throwing an exception here
public int divide(int dividend, int divisor) throws ArithmeticException
{
    if (divisor == 0)
    {
        throw new ArithmeticException();
    }
    return divideBySubtracting(dividend, divisor, 0);
}

private int divideBySubtracting(int dividend, int divisor, int quotientSoFar)
{
    divident -= divisor;
    if (dividend <= 0)
    {
        return quotientSoFar;
    }
    return divideBySubtracting(divident, divisor, quotientSoFar + 1);
}

//division explains this, so we can cheat here
public int modulo(int dividend, int divisor)
{
    return dividend % divisor;
}

In the code you posted, you have UI and logic mixed together. You probably want to separate them into different modules to keep them clean.

The following is rough pseudocode for how I might organize things. I've left out a lot of stuff that would need to be filled in to make this work, of course.

public enum Operation
{
    Addition,
    Subtraction,
    Multiplication,
    Division
}

public class Calculator
{
    public int calculate(int left, int right, Operation op)
    {
        switch(op)
        {
            case Operation.Addition:
                return add(left, right);
            case Operation.Subtraction:
                return subtract(left, right);
            case Operation.Multiplication:
                return multiply(left, right);
            case Operation.Division:
                return divide(left, right);
            default:
                throw new UnsupportedOperationException(operation.toString() + " not implemented.");
        }
    }
}

public class MyActivity extends Activity
{
    Operation operation;

    //...

    void calculate()
    {
        a = calculator.parse(leftAmount);
        b = calculator.parse(rightAmount);
        answer = calculator.calculate(operation, a, b);
        if (operation == Operation.Division)
        {
            remainder = calculator.modulo(a, b);
        }
        update();
    }

    //called when leftOp, rightOp, and/or answer change
    //numbers greater than 10 could just be printed numbers
    void update(int leftOp, int rightOp, int answer)
    {
        remainderView.clear();

        if (leftOp != previousLeftOp)
        {
            leftView.setContent( ImageFactory.getImageByNumber(leftOp), leftOp );
        }

        if (rightOp != previousRightOp)
        {
            rightView.setContent( ImageFactory.getImageByNumber(rightOp), rightOp );
        }

        if (answer != previousAnswer)
        {
            answerView.setContent( ImageFactory.getImageByNumber(answer), answer );
            if (operation == Operation.Division && remainder != 0)
            {
                remainderView.setContent( ImageFactory.getImageByNumber(remainder), remainder );
            }
        }
        previousLeftOp = leftOp;
        previousRightOp = rightOp;
        previousAnswer = answer;
    }
}


Short and Messy Polybius Square I attempted to recreate the Polybius square, also called the Polybius checkerboard, which was used in Ancient Greece for cryptography. Since it is an uncommon cipher, it is nowhere on Code Review.

Although the program technically works, it ended up very messy.

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iterator>
#include <unordered_map>

std::string getChoice();
std::vector<std::string> getCoords();

int main(){
    std::string choice = getChoice();

    if(choice == "e"){
        std::cout << "Input string: ";
        std::string input;
        std::getline(std::cin, input);
        input.erase(remove_if(input.begin(), input.end(), isspace), input.end());

        std::unordered_map<char, unsigned int> alphaToInt = {
            {'A', 11},
            {'B', 12},
            {'C', 13},
            {'D', 14},
            {'E', 15},
            {'F', 21},
            {'G', 22},
            {'H', 23},
            {'I', 24},
            {'J', 24}, // same as I
            {'K', 25},
            {'L', 31},
            {'M', 32},
            {'N', 33},
            {'O', 34},
            {'P', 35},
            {'Q', 41},
            {'R', 42},
            {'S', 43},
            {'T', 44},
            {'U', 45},
            {'V', 51},
            {'W', 52},
            {'X', 53},
            {'Y', 54},
            {'Z', 55},
        };

        for(int i = 0; i < input.length(); ++i){
            std::cout << alphaToInt[input[i]] << ' ';
        }
    } else{
        std::vector<std::string> coords = getCoords();
        std::string output;

        const std::string squareIJ[5][5] = {
            {"A", "B", "C", "D", "E"},
            {"F", "G", "H", "I", "K"},
            {"L", "M", "N", "O", "P"},
            {"Q", "R", "S", "T", "U"},
            {"V", "W", "X", "Y", "Z"},
        };

        for(int i = 0; i < coords.size(); ++i){
            std::string coord = coords[i];
            output.append(squareIJ[coord[0] - '1'][coord[1] - '1']);
        }

        std::cout << output;

    }

    std::cout << '\n';
    return 0;
}

std::string getChoice(){
    std::string choice;
    do{
        std::cout << "Encrypt or decrypt [e/d] = ";
        std::getline(std::cin, choice);
        if(choice == "E") choice = "e";
        std::transform(choice.begin(), choice.end(), choice.begin(), ::tolower);
    } while(choice != "e" && choice != "d");

    return choice;
}

std::vector<std::string> getCoords(){
    std::cout << "Coordinates (separate with spaces): ";
    std::string strCoords;
    std::getline(std::cin, strCoords);
    std::stringstream streamCoords(strCoords);
    std::istream_iterator<std::string> begin(streamCoords);
    std::istream_iterator<std::string> end;
    std::vector<std::string> coords(begin, end);
    return coords;
}

The Polybius square is a simple way to assign characters numbers, and then "encrypt" and "decrypt" based off of those numbers. As shown in the unordered map and char array, the numbers correspond to the row and column on a 5x5 square:

The getChoice() function simply gets the e or d character to choose encryption or decryption.

The getCoords() function gets a string, and then tokenizes the string into a vector of strings, each corresponding to the coordinates of a character.

Example of "encryption":

Encrypt or decrypt [e/d] = e
Input string: BAT
12 11 44

Example of "decryption":

Encrypt or decrypt [e/d] = d
Coordinates (separate with spaces): 12 11 44
BAT

This code, in my opinion, is quite messy. How can I improve it?

It's not that messy IMO, but there are a few things which you could have done better:

Always compile code with every warning turned on, and fix them. When compiled with -Wall, your code produces 2 same warnings:

warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

You should fix them.
Your choice variable really wants to be an enum instance:

enum class mode {
    encrypt, decrypt
};

You have some redundant code:

if(choice == "E") choice = "e";
// redundant if in the next line your lower casing every character in 'choice'

const correctness: alphaToInt can and should be const, as you're not going to modify it no matter what.
getCoords can be reduced considerably (it looks too bloated otherwise IMO):

std::vector<std::string> getCoords(){
    std::cout << "Coordinates (separate with spaces): ";
    std::string strCoords;
    std::getline(std::cin, strCoords);

    std::stringstream streamCoords(strCoords);
    return{ std::istream_iterator<std::string>{ streamCoords }, std::istream_iterator<std::string>{} };
}

squareIJ doesn't have to be a std::string[5][5], it can be a simple char[5][5]. Don't allocate memory if you don't have too (this might actually not allocate memory for the std::string, due to SSO actually).
Use auto to simply some variable definitions if you want to:

// std::vector<std::string> coords = getCoords();
auto coords = getCoords();

// ...

Use ranged-based loop instead of index loop. For example,

for(int i = 0; i < coords.size(); ++i){
    std::string coord = coords[i];
    output.push_back(squareIJ[coord[0] - '1'][coord[1] - '1']);
}

becomes

for (const auto& coord : coords)
    output.push_back(squareIJ[coord[0] - '1'][coord[1] - '1']);

Include every necessary headers, you forgot <cctype> for std::isspace.
If you expect every character to be upper case, either (1) tell the user (not recommended) or (2) upper case the string yourself:

std::transform(input.begin(), input.end(), input.begin(), ::toupper);


Java AES file encryption/decryption I've written a simple Java class to encrypt and decrypt files using AES. The code works and I'm able to encrypt and decrypt files.

However, I understand this is an easy way of implementing AES and far from the most secure (my usage of ECB mode for example).

I'm looking to improve the strength of encryption this code provides.

import javax.crypto.Cipher;
import javax.crypto.spec.SecretKeySpec;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.security.Key;

class Crypto {

    // Process a file (Encrypts or decrypts depending on cipherMode)
    private void processFile(boolean encrypt, File inputFile, String inputKey, File outputFile) throws Exception {
        // Convert key into bytes
        Key key = new SecretKeySpec(inputKey.getBytes(),"AES");

        // Get cipher instance
        Cipher cipher = Cipher.getInstance("AES");

        if(encrypt) {
            cipher.init(Cipher.ENCRYPT_MODE,key);
        }
        else {
            cipher.init(Cipher.DECRYPT_MODE,key);
        }

        // Read input file into byte array
        FileInputStream fileInputStream = new FileInputStream(inputFile);
        byte[] inputBytes = new byte[(int)inputFile.length()];
        fileInputStream.read(inputBytes);

        // Process the byte array from the input file
        byte[] outputBytes = cipher.doFinal(inputBytes);

        // Write the output byte array to the output file
        FileOutputStream fileOutputStream = new FileOutputStream(outputFile);
        fileOutputStream.write(outputBytes);

        // Close file streams
        fileInputStream.close();
        fileOutputStream.close();
    }

    // Encrypts a file
    void encrypt(File inputFile, String inputKey, File outputFile) throws Exception {
        processFile(true,inputFile,inputKey,outputFile);
    }

    // Decrypts a file
    void decrypt(File inputFile, String inputKey, File outputFile) throws Exception {
        processFile(false,inputFile,inputKey,outputFile);
    }

}

The encrypt() and decrypt() methods are there purely for easy of use and readability when using the code.

As far as security goes, rather than just using "AES" for your algorithm, from the documentation:

  Every implementation of the Java platform is required to support the
  following standard Cipher transformations with the keysizes in
  parentheses:

  AES/CBC/NoPadding (128)
  AES/CBC/PKCS5Padding (128)
  AES/ECB/NoPadding (128)
  AES/ECB/PKCS5Padding (128)
  AES/GCM/NoPadding (128)
  DES/CBC/NoPadding (56)
  DES/CBC/PKCS5Padding (56)
  DES/ECB/NoPadding (56)
  DES/ECB/PKCS5Padding (56)
  DESede/CBC/NoPadding (168)
  DESede/CBC/PKCS5Padding (168)
  DESede/ECB/NoPadding (168)
  DESede/ECB/PKCS5Padding (168)
  RSA/ECB/PKCS1Padding (1024, 2048)
  RSA/ECB/OAEPWithSHA-1AndMGF1Padding (1024, 2048)
  RSA/ECB/OAEPWithSHA-256AndMGF1Padding (1024, 2048)

Likewise, here's more documentation on the subject of what is supported.

If you're unsure which one to choose, this answer will shed some light. Here's the summary:

  In general, stick with CBC or CTR, with PKCS#7 where necessary (you don't need padding on stream cipher modes) and use an authenticity check (HMAC-SHA256 for example) on the ciphertext. Both CBC and CTR come recommended by Niels Ferguson and Bruce Schneier, both of whom are respected cryptographers.

What's the difference between PKCS5 and PKCS7?

  ... fundamentally PKCS#5 padding is a subset of PKCS#7 padding for 8 byte block sizes. Hence, PKCS#5 padding can not be used for AES ...

  Some cryptographic libraries such as the SUN provider in Java indicate PKCS#5 where PKCS#7 should be used - "PKCS5Padding" should have been "PKCS7Padding". This is a legacy from the time that only 8 byte block ciphers such as (triple) DES symmetric cipher were available.

However, that doesn't stop you from using PKCS#5 with AES.

Given the answers to the question linked above, I would suggest using the following:

"AES/CBC/PKCS5Padding"

After that, reading erikson's answer will tell you most of what you need to know about how to write this code in a relatively secure manner.


Find whether two (or 'n') particular values are present in a binary tree I have a solution to find if two values are present in a binary tree (not a BST).

I would like to know if there is

a more efficient way to do this?
a more elegant way to this?
specific improvement for the parts I've marked with comments?
a better way to generalize the solution if we have to check if some 'n'
values (all of them) are present in tree or not?

I have a working solution mentioned in the code below but I think the same could be achieved using a more elegant and efficient code.

Note : Please assume that CheckIfValuesPresentInTree() is an API that I need to implement, so I can't change the underlying data structure.

/*The structure of a Node is as follows:
struct Node {
    int data;
    Node * right, * left;
};*/

void IsPresent(Node* p, int n1, int n2, bool& f1, bool& f2);

bool CheckIfValuesPresentInTree(Node* root, int n1, int n2) {
    auto f1 = bool{false};
    auto f2 = bool{false};

    IsPresent(root, n1, n2, f1, f2);

    return f1&&f2;
}

void IsPresent(Node* p, int n1, int n2, bool& f1, bool& f2) {
// Too many arguments passed to the function.
    if (!p) {
        return;
    }

    if (p->data == n1) {
        f1 = true;
    }

    if (p->data == n2) {
        f2 = true;
    }

    IsPresent(p->left, n1, n2, f1, f2);
    IsPresent(p->right, n1, n2, f1, f2);
// Second recursive call might not be needed if both n1 and n2 are found
// in 1st call.
// We can write something like below : but is there a better way ?
/*
    IsPresent(p->left, n1, n2, f1, f2);
    if (f1 && f2) {
        return;
    }
    IsPresent(p->right, n1, n2, f1, f2);
*/
}

Reading the title, you want a solution that covers N values. Looking at your code, it doesn't meet that expectation. Not do I see you writing all variants from 1 to N.

As API, you have 2 options: compile time N or runtime.
If you go for the compile time, use variadic templates in the call. Otherwise, go for std::vector. As I always mess up the ..., I'll continue with the vector.

Your current approach makes good use of cache locality. Really interesting if the tree is big. Alternatively, you could check each element 1 by 1, really good for a big number of values if you expect a lot of miss matches.

What I would suggest is the following:

bool CheckIfValuesPresentInTree(Node* root, const std::vector<int> & n) {
     auto f = std::vector<bool>{};
    f.resize(n.size(), false);
    IsPresent(root, n, f);

    return std::all_of(f.cbegin(), f.cend());
}

void IsPresent(Node* p, const std::vector<int> &n, std::vector<bool> &f) {

    if (!p) {
        return;
    }

    for (size_t i = 0; i < n.size(); ++i)
    {
      if (p->data == n[I])
           f[I] = true;
    }

    IsPresent(p->left, n, f);
    IsPresent(p->right, n, f);
}

About your question on whether to stop searching once everything if found. Ain't an easy question, given the existing API, I wouldn't bother as it might be more expensive to check.

It can however be done by changing the way you indicate if the value is found. Instead of using the bool, you could use the n to keep track of values you still need to search.

void IsPresent(Node* p, std::vector<int> &n) {

    if (!p) {
        return;
    }

    for (auto it = n.cbegin(); it != n.cend(); /**/)
    {
      if (p->data == *it)
           it = n.erase(it);
     else
           ++it;
    }

    if (n.empty())
        return;

    IsPresent(p->left, n);

    if (n.empty())
         return;
    IsPresent(p->right, n);
}

The advantage of this, is that the amount of values you are checking reduces while searching. The check on whether you need to terminate becomes really cheap, at the expense of some bookkeeping.


Python priority queue class wrapper I'm trying to incorporate the advice found in https://docs.python.org/3.5/library/heapq.html in order to make a priority queue implementation (see corresponding section) in a class priorityQ. Not going to reinvent the wheel so i use the the python's heapq implementation

class priorityQ():
    import heapq
    import itertools

    def __init__(self,mylist):

        self._entry_finder = {}               # mapping of tasks to entries
        self._counter = itertools.count()     # unique sequence count
        self.REMOVED = '<removed-task>'      # placeholder for a removed task

        if mylist:
            self.data = []
            for element in mylist:
                priority, count, task = element[0], next(self._counter), element[1]
                entry = [priority,count,task]
                self._entry_finder[task] = entry
                heapq.heappush(self.data,entry)
        else:
            self.data = []

    def add_task(self,task,priority):
        if task in self._entry_finder:
            self.remove_task(task)
        count = next(self._counter)
        entry = [priority,count,task]
        self._entry_finder[task] = entry
        heapq.heappush(self.data, entry)

    def remove_task(self,task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self._entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        while self.data:
            priority, count, task = heapq.heappop(self.data)
            if task is not self.REMOVED:
                del self._entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')

The code as it is seems to solve the implementation challenges listed in 8.5.2 in the link I gave. I just wonder if this is a clean implementation of such a candidate class. Is it better to just implement with the procedural style suggested in the manual and incorporate it in whatever project i'm working on or is it a better practice to make use of a class like the above (or a more refined version of that).

PS: I know it's slightly off-topic for this stack exchange site, but i wonder if there is a way around the side effect of having a bunch of deleted-entries residing in the queue after doing a set of priority updates in existing tasks. (Something different than copying/cleaning the entire queue every fixed period of time)

1. Review

The code in the post does not work:

>>> q = PriorityQueue(())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr152757.py", line 8, in __init__
    self._counter = itertools.count()     # unique sequence count
NameError: name 'itertools' is not defined

The problem is that itertools was imported in class scope (not at top level) so you need self.itertools (or to move the imports to the top level).
The class has no docstring. How am I supposed to use this class?
The __init__, add_task and pop_task methods have no docstrings. What arguments do I pass? What do they return?
The objects in the queue are described as "tasks" but priority queues can be used for all sorts of different things — for example, the A* search algorithm uses a priority queue containing unexpanded search nodes. I would use a more generic name like "item" or "element", and change add_task to add, remove_task to remove and pop_task to pop.
The Python style guide (PEP8) recommends that

  Class names should normally use the CapWords convention.

So I would call the class PriorityQueue. You're not obliged to follow this guide, but it will make it easier for you to collaborate with other Python programmers if you do.
If a class has no superclasses, then you can omit the parentheses from the class declaration.
The constructor has a required argument mylist. It would be better if this argument was optional, and if omitted then the constructed queue is empty. This would match the behaviour of other class constructors like queue.PriorityQueue() and collections.deque() which construct empty queues if given no argument.
There is a test if mylist: but this is unnecessary because if mylist is an empty list, then both branches have the same behaviour (setting self.data to the empty list). So you might as well omit the test.
Once you omitted the test on mylist, it doesn't have to be a list any more – any iterable would do. So I would name this argument iterable.
It is perverse that the argument to __init__ must be a list of pairs (priority, task) but when calling add_task you have to supply the arguments (task, priority). This seems likely to be the cause of errors.
The need for _counter is slightly tricky (it's necessary to break ties in case the items cannot be compared for order), so a comment would be a good idea.
self.REMOVED is always the same, so it could be a member of the class. Also, it is only needed for use internally by the class so PEP8 recommends using a name starting with an underscore.
Similarly, self.data ought to have a name starting with an underscore.
Instead of using element[0] and element[1] here:

for element in mylist:
    priority, count, task = element[0], next(self._counter), element[1]
    entry = [priority,count,task]

use tuple unpacking:

for priority, item in iterable:
    entry = [priority, next(self._counter), item]

(But see the next item.)
The code in __init__ duplicates the code in add_task. So it would be simpler if the former called the latter:

for priority, item in iterable:
    self.add(item, priority)

The docstring for remove_task is written from the implementer's point of view: it says, "Mark an existing item as REMOVED". But the user does not need to know how removal is implemented: that's an internal detail of the class which the documented API should hide.
In pop_task you unpack all the elements of the popped entry:

priority, count, item = heapq.heappop(self._data)

but priority and count are not used. It is conventional to use the variable name _ for values that go unused.

2. Revised code

import heapq
import itertools

class PriorityQueue:
    """Collection of items with priorities, such that items can be
    efficiently retrieved in order of their priority, and removed. The
    items must be hashable.

    """
    _REMOVED = object()         # placeholder for a removed entry

    def __init__(self, iterable=()):
        """Construct a priority queue from the iterable, whose elements are
        pairs (item, priority) where the items are hashable and the
        priorities are orderable.

        """
        self._entry_finder = {} # mapping of items to entries

        # Iterable generating unique sequence numbers that are used to
        # break ties in case the items are not orderable.
        self._counter = itertools.count()

        self._data = []
        for item, priority in iterable:
            self.add(item, priority)

    def add(self, item, priority):
        """Add item to the queue with the given priority. If item is already
        present in the queue then its priority is updated.

        """
        if item in self._entry_finder:
            self.remove(item)
        entry = [priority, next(self._counter), item]
        self._entry_finder[item] = entry
        heapq.heappush(self._data, entry)

    def remove(self, item):
        """Remove item from the queue. Raise KeyError if not found."""
        entry = self._entry_finder.pop(item)
        entry[-1] = self._REMOVED

    def pop(self):
        """Remove the item with the lowest priority from the queue and return
        it. Raise KeyError if the queue is empty.

        """
        while self._data:
            _, _, item = heapq.heappop(self._data)
            if item is not self._REMOVED:
                del self._entry_finder[item]
                return item
        raise KeyError('pop from an empty priority queue')