Searching a huge number of strings from Excel to a large number of Text files I have written this code to get the input string from the spreadsheet and search the string across the text files and state whether or not it is found in the Excel sheet.

Scenario:

Excel (sheet1):

ColumnA

AAA

BBB

Drive C:

C: should be give in Column D5.

It has subfolders TEMP1, TEMP2, ...

Folder C:\TEMP1\

It has these text files:

X1.txt (has content AAA)
X2.txt (doesn't have any search data)

Folder C:\TEMP2\

It has these text files:

Y1.txt (has content BBB)
Y2.txt (doesn't have any search data)

Public K As Integer
Dim fs As Object
Dim fso As Object
Public fpth As String
Public str As String

Public Sub SearchInSQSDatabase_Click()

Dim ws1 As Worksheet
Set ws1 = Sheets(1)

Dim ws2 As Worksheet
Set ws2 = Sheets(2)

K = 2

Dim i As Integer
i = 1
ws2.Cells(1, 4).Value = "Search String"
ws2.Cells(1, 5).Value = "Files"
ws2.Cells(1, 6).Value = "Comments"

Do While Cells(i, 1).Value <> ""
     'ws2.Cells(i, 1).Value = Cells(i, 1).Value
     str = Cells(i, 1).Value
     ShowFolderList (ws1.Cells(5, 4).Value)
     i = i + 1
Loop

End Sub
''''''''''''''''''''''''''''''''''''''''''''''''''''''
'Get the List of Files and folders
''''''''''''''''''''''''''''''''''''''''''''''''''''''
Sub ShowFolderList(folderspec)
   On Error GoTo local_err

 Dim f, f1, fc, s, sFldr

 Dim ws2 As Worksheet
 Set ws2 = Sheets(2)

 Set fs = CreateObject("Scripting.FileSystemObject")
 Set f = fs.GetFolder(folderspec)
 Set fc = f.SubFolders

  For Each f1 In fc
     ' If Right(f1, 1) <> "\" Then ShowFolderList f1 & "\" Else ShowFolderList f1
     If Right(f1, 1) <> "\" Then ShowFolderList f1 Else ShowFolderList f1
  Next
Set fc = f.Files
For Each f1 In fc
    ' ws2.Cells(K, 4).Value = folderspec & "\" & f1.Name
    fpth = folderspec & "\" & f1.Name
    StringExistsInFile (f1.Name)

    'K = K + 1
Next
local_exit:
     Exit Sub
 local_err:
    MsgBox Err & " " & Err.Description
    Resume local_exit
    Resume
 End Sub

 ''''''''''''''''''''''''''''''''''''''''''''''''''''''
 'Check for the String
 ''''''''''''''''''''''''''''''''''''''''''''''''''''''
Sub StringExistsInFile(fname)
Dim theString, callString As String
Dim path As String
Dim StrFile As String
Dim file
Dim line As String
Dim flag As String

Set fso = CreateObject("Scripting.FileSystemObject")
Dim ws2 As Worksheet
Set ws2 = Sheets(2)

theString = str
path = fpth
StrFile = Dir(path)

Do While StrFile <> ""

'Find TheString in the file
'If found, debug.print and exit loop

Set file = fso.OpenTextFile(path)
Do While Not file.AtEndOfLine
    line = file.ReadLine
    If InStr(1, line, theString, vbTextCompare) > 0 Then
        ws2.Cells(K, 4).Value = str
        ws2.Cells(K, 5).Value = fname
        ws2.Cells(K, 6).Value = "Srting is found"
        flag = "Y"
    End If

Loop

file.Close
Set file = Nothing
Set fso = Nothing

StrFile = Dir()
Loop
If flag = "Y" Then
   K = K + 1
 Else
  ws2.Cells(K, 4).Value = str
  ws2.Cells(K, 5).Value = fname
  ws2.Cells(K, 6).Value = "String is not Found"
   K = K + 1
  End If

  End Sub

Output:

Output should be written in sheet2:

ColumnA columnB

AAA     X1

BBB     Y1

I have updated the code to have a hyperlink in the text file name to open the text file for the strings that are found, also need to no the count of column

added the below logic at the end, I feel the below code can be written in better way

Do While ws2.Cells(K, 6).Value <> ""
    K = K + 1
 Loop

Do While j < K

If ws2.Cells(j, 7).Value <> "" Then

    ws2.Cells(j, 7).Hyperlinks.Add Anchor:=ws2.Cells(j, 7), Address:= _
    ws2.Cells(j, 7).Value, TextToDisplay:=ws2.Cells(j, 7).Value

    ' ws2.Cells(j, 7).Formula = "=HYPERLINK(" & ws2.Cells(j, 7) & ",    Address = " & ws2.Cells(j, 7).Value & ")"
    'ws2.Hyperlinks.Add Anchor:=j, _
    'Address:=ws2.Cells(j, 7).Value, TextToDisplay:=ws2.Cells(j, 7).Value

    End If
  j = j + 1
Loop

A few suggestions:

Most obvious (and simple) step is to read the entire file, and not one line at the time

Change this:

Set file = fso.OpenTextFile(Path)
Do While Not file.AtEndOfLine
    Line = file.ReadLine
    If InStr(1, Line, theString, vbTextCompare) > 0 Then
        ws2.Cells(K, 4).Value = Str
        ws2.Cells(K, 5).Value = fname
        ws2.Cells(K, 6).Value = "Srting is found"
        flag = "Y"
    End If
Loop

To this:

Set file = fso.OpenTextFile(Path)

fullFile = file.ReadAll

If InStr(1, fullFile, theString, vbTextCompare) > 0 Then
    With ws2
        .Cells(K, 4).Value2 = theString
        .Cells(K, 5).Value2 = fname
    End With
    flag = "Y"
End If

It eliminates the do-while loop. More details about .ReadAll().
Store Str and fname info into an array, then commit the entire array to the worksheet at the end, instead of writing to each cell separately.
The "Find" command in DOS might be faster and it can also provide the line number(s) where the string is found:

Find /?

Searches for a text string in a file or files.

FIND [/V] [/C] [/N] [/I] [/OFF[LINE]] "string" [[drive:][path]filename[ ...]]


Body Mass Index Calculator I created a quick calculator in Javascript and I was wondering if there was a way to make the code look prettier or make it simpler. To me, it looks really cramped and messy and I'm not sure how change that.

function calc() {
    var height = (document.getElementById('height').value) / 100;
    var weight = document.getElementById('weight').value;

    var output = document.getElementById('output');
    var bmi = Math.round((weight / Math.pow(height, 2)) * 10) / 10;

    var result = document.getElementById('result');
    var text = "";
    if (height != "" && weight != "") {
        if (bmi != "NaN" && bmi != 0) {
            if (bmi % 1 != 0) {
                output.innerHTML = bmi;
            } else {
                output.innerHTML = bmi + ".0";
            }
            if (10 <= bmi && bmi < 14) {
                text = "You are seriously underweight!";
            } else if (15 <= bmi && bmi < 18.5) {
                text = "You are slightly underweight.";
            } else if (18.5 <= bmi && bmi < 25) {
                text = "You are healthy!";
            } else if (25 <= bmi && bmi < 30) {
                text = "You are slightly overweight.";
            } else if (30 <= bmi && bmi < 40) {
                text = "You are obese!";
            } else if (40 <= bmi && bmi < 50) {
                text = "You are seriously obese!";
            } else {
                text = "You should be dead...";

            }

            result.innerHTML = text;
        }
    }
}

The reason it seems messy is because you have one function doing multiple things. So what does your function do?

It queries the DOM for elements containing the input.
It calculates the BMI based on that input
It has logic that determines what kind of output to produce
It produces output to the DOM.

There are a few problems with that:

What if you want to run this function in a different DOM? You can't, you're bound to elements with specific IDs.
What if you want just the result? You can't, because your function doesn't return anything but explicitly mutates the DOM.
It's unclear from the signature what your function needs to work (i.e. available DOM with elements with specific IDs). Functions normally declare what they need in the form of parameters.

So how can we do better? We can divide into several independent functions:

function calculateBMI(height, weight) {
  // todo
  // calculate BMI based on height and weight passed in.
  // returns a number (the BMI)
}

function bmiToHealth(bmi) {
  // todo
  // determine what text to display based on the bmi value.
  // returns a string (the text to display)
}

And use it like this:

function calculateBmiFromDOM() {
    let heightInput = document.getElementById('height');
    let weightInput = document.getElementById('weight');
    let output = document.getElementById('output');
    let result = document.getElementById('result');

    let bmi = calculateBMI(heightInput.value, weightInput.value);
    output.textContent = bmi.toPrecision(3); // 25 -> 25.0, 23.752 -> 23.7
    result.textContent = bmiToHealth(bmi);
}
let form = getFormSomehow(); // usually with getElementById or querySelector
// You can pass functions as parameters in JavaScript
form.addEventListener('submit', calculateBmiFromDOM);

And that last snippet the only thing that's specific to your current DOM, so when your DOM changes, you don't need to change all of your code, just the bit that interacts with it.

Additional notes for future snippets (just general things I've noticed):

anything != 'NaN' is pointless, nothing in your logic might return a string with the value of 'NaN'. Even if it were NaN, you can't compare it with ==, you need to use the isNaN() function.
You should always use === or !== when comparing. Using == and != can introduce unexpected behavior due to type conversion.
Functions work best when they accept values as arguments and/or return values as result.


Chaining list operations in Python I assigned the following contrived problem in a comparative programming languages course to give students practice with "streaming":

Write function that returns the top ten players by points-per-game among the players that have been in 15 games or more. The input to your function will be an object, keyed by team, with a list of player stats. Each player stat is an array with the player name, the number of games played, and the total number of points.

A sample data set is as follows:
stats = {
    'ATL': [
        ['Betnijah Laney', 16, 263],
        ['Courtney Williams', 14, 193],
    ],
    'CHI': [
        ['Kahleah Copper', 17, 267],
        ['Allie Quigley', 17, 260],
        ['Courtney Vandersloot', 17, 225],
    ],
    'CONN': [
        ['DeWanna Bonner', 16, 285],
        ['Alyssa Thomas', 16, 241],
    ],
    'DAL': [
        ['Arike Ogunbowale', 16, 352],
        ['Satou Sabally', 12, 153],
    ],
    'IND': [
        ['Kelsey Mitchell', 16, 280],
        ['Tiffany Mitchell', 13, 172],
        ['Candice Dupree', 16, 202],
    ],
    'LA': [
        ['Nneka Ogwumike', 14, 172],
        ['Chelsea Gray', 16, 224],
        ['Candace Parker', 16, 211],
    ],
    'LV': [
        ['A’ja Wilson', 15, 304],
        ['Dearica Hamby', 15, 188],
        ['Angel McCoughtry', 15, 220],
    ],
    'MIN': [
        ['Napheesa Collier', 16, 262],
        ['Crystal Dangerfield', 16, 254],
    ],
    'NY': [
        ['Layshia Clarendon', 15, 188]
    ],
    'PHX': [
        ['Diana Taurasi', 13, 236],
        ['Brittney Griner', 12, 212],
        ['Skylar Diggins-Smith', 16, 261],
        ['Bria Hartley', 13, 190],
    ],
    'SEA': [
        ['Breanna Stewart', 16, 317],
        ['Jewell Loyd', 16, 223],
    ],
    'WSH': [
        ['Emma Meesseman', 13, 158],
        ['Ariel Atkins', 15, 212],
        ['Myisha Hines-Allen', 15, 236],
    ],
}

Now in JavaScript, there is a "fluent" or method-chaining style readily apparent:
function topTenScorers(stats) {
  return Object.entries(stats)
    .flatMap(([team, players]) => players.map(player => [...player, team]))
    .filter(([, games, ,]) => games >= 15)
    .map(([name, games, points, team]) => ({ name, ppg: points / games, team }))
    .sort((p1, p2) => p2.ppg - p1.ppg)
    .slice(0, 10)
}

However, my Python solution (below) just doesn't satisfy the same way (I'm more of a JavaScript programmer). I've heard that Python list comprehensions are preferred to map and filter; I think that Python doesn't have a built-in flat_map, and, well, although you can do fancy things with itertools, Pythonic programs tend to, I think, be more favorable to computing intermediate expressions than to chaining. So I came up with the following:
def top_ten_scorers(stats):
    with_teams = [[*player, team]
                for (team, players) in stats.items()
                for player in players]
    with_ppg = [{'name': name, 'ppg': points/games, 'team': team}
                for [name, games, points, team] in with_teams
                if games >= 15]
    return sorted(with_ppg, key=lambda k: k['ppg'], reverse=True)[:10]

I'd love to know whether the code is in the style of current Python best practices. I know Python is well-loved by data scientists, and this problem, although very contrived, feels data-sciencey to me, so I figured a set of best practices would have arisen that my code might not meet. Also, I'm having trouble with names for the intermediate expressions, and am not sure whether the breakdown of steps is too coarse or too fine. I'm not sure which approach to take to clean it up.
Of course, it is not imperative that a streaming solution be found; what is most important is a solution that best fits the Zen of Python rule(s) "There should be one-- and preferably only one --obvious way to do it. Although that way may not be obvious at first unless you're Dutch."

This is more "streaming" in a sense:
from heapq import nlargest
from operator import itemgetter

def top_ten_scorers(stats):
    players = (dict(name=name, ppg=points/games, team=team)
               for team, players in stats.items()
               for name, games, points in players
               if games >= 15)
    return nlargest(10, players, key=itemgetter('ppg'))

Your with_teams and with_ppg are fully computed lists, and then sorted creates another one that it then sorts, and then you throw away all but ten elements of it.
My players is a generator iterator, computing more elements on the fly as requested. The players = ... assignment only sets up the iterator, but nothing gets processed yet.
Then nlargest consumes players one by one, keeping only the top 10 seen so far and returning them sorted (in descending order). Could also be more efficient than sorting everything, depending on the number of eligible players.
I actually found your first two steps more confusing than helpful, as your with_teams creates an intermediate result/format to understand. I think it's simpler and easier to read to just directly produce the player dicts from the stats. Then again, I might be biased towards this and away from yours because I'm used to Python, which, as you say, isn't much into chaining.
Btw, here's an old message from Guido about some forms of chaining. Not sure it relates to what we have here, but perhaps interesting anyway.
I used dict(...) just for brevity, but {...} is faster, so you might want to keep the latter:
Setup:
name, ppg, team = 'Betnijah Laney', 263/16, 'ATL'

Round 1:
  347.041 ns  dict(name=name, ppg=ppg, team=team)
  128.325 ns  {'name': name, 'ppg': ppg, 'team': team}

Round 2:
  350.576 ns  dict(name=name, ppg=ppg, team=team)
  129.106 ns  {'name': name, 'ppg': ppg, 'team': team}

Round 3:
  347.753 ns  dict(name=name, ppg=ppg, team=team)
  130.734 ns  {'name': name, 'ppg': ppg, 'team': team}


Binary search using recursion, iteration, shifted array Interview  question some engineer, asked me to write binary search in 2 ways,
Also asked me to write binary search on a shifted array (10 20 1 2 3 4).
Wrote that and then asked me to find the offset of the array in log n.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class BinarySearch
    {
        public BinarySearch()
        {
            int[] array = new int[10] { 5, 6, 7, 8, 9, 10, 12, 15, 20, 30 };
            int numberToFind = 10;
            int index = FindIndexRecursive(numberToFind, array, 0, array.Length - 1);
            Console.WriteLine("the number " + numberToFind + "is located at index: " + index);
            index = FindIndexIterative(numberToFind, array, 0, array.Length - 1);
            Console.WriteLine("the number " + numberToFind + "is located at index: " + index);
            int[] shiftedArray = new int[6]{10, 20, 1, 2, 3 ,4};

            index = FindShiftedArray(numberToFind, shiftedArray, 0, array.Length - 1);
        }

        private int FindShiftedArray(int numberToFind, int[] shiftedArray, int indexMin, int indexMax)
        {
            //we find the pivot and from there do a binary search
            int pivot = FindPivot(shiftedArray, 0, shiftedArray.Length - 1);
            //the pivot acts like the first slicing of the arrays
            if (shiftedArray[pivot] == numberToFind)
                return pivot;
            if (shiftedArray[0] <= numberToFind)
            {
                return FindIndexRecursive(numberToFind,shiftedArray, 0, pivot - 1 );
            }
            else
            {
                return FindIndexRecursive(numberToFind,shiftedArray, pivot + 1, shiftedArray.Length - 1 );
            }
        }

        private int FindPivot(int[] array, int indexMin, int indexMax)
        {

            if (indexMax < indexMin)
            {
                return -1;
            }
            if (indexMax == indexMin)
            {
                return indexMin;
            }
            int mid = (indexMin + indexMax)/2;   /*low + (high - low)/2;*/
            if (mid < indexMax && array[mid] > array[mid + 1])
            {
                return mid;
            }
            if (mid > indexMin && array[mid] < array[mid - 1])
            {
                return (mid-1);
            }
            if (array[indexMin] >= array[mid])
            {
                return FindPivot(array, indexMin, mid-1);
            }
            else
            {
                return FindPivot(array, mid + 1, indexMax);
            }
}

        public int FindIndexRecursive(int numberToFind, int[] array, int indexMin, int indexMax)
        {
            if (indexMin > indexMax)
            {
                return -1;
            }

            int mid = ((indexMax - indexMin) / 2 ) + indexMin;

            if (array[mid] < numberToFind)
            {
               return FindIndexRecursive(numberToFind, array, mid, indexMax);
            }
            else if (numberToFind < array[mid])
            {
                return FindIndexRecursive(numberToFind, array, indexMin, mid);
            }
            else
            {
                return mid;
            }
        }

        public int FindIndexIterative(int numberToFind, int[] array, int indexMin, int indexMax)
        {
            while (indexMin < indexMax)
            {
                int mid = ((indexMax - indexMin) / 2) + indexMin;
                if (array[mid] < numberToFind)
                {
                    indexMin = mid;
                }
                else if (numberToFind < array[mid])
                {
                    indexMax = mid;
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }
    }
}

If numberToFind > array[mid] then the lower bound should be set to mid + 1 as the value at array[mid] does not match. In the opposite case the upper bound should be set to mid - 1. If you don't do so, you might get stuck in an endless recursion. Say you are looking for 12 (at index 6) and you have indexMin = 5 and indexMax = 6. mid becomes 5. Now calling

FindIndexRecursive(numberToFind, array, mid, indexMax);

gives the same indexes again and array[mid] will never be 12!

I am also irritated by the test array[mid] < numberToFind. It seems more natural to me to perform the equivalent test numberToFind > array[mid]:

if (numberToFind > array[mid])
{
   return FindIndexRecursive(numberToFind, array, mid + 1, indexMax);
}
else if (numberToFind < array[mid])
{
    return FindIndexRecursive(numberToFind, array, indexMin, mid - 1);
}
else
{
    return mid;
}

mid can be found more easily with:

int mid = (indexMin + indexMax) / 2;


Fixed time step game loop I'm writing a Direct2D game in c++ / WinAPI. I need to render things 60 times every a second using fixed time step.

__int64 time_before = 0;
__int64 time_now;
__int64 frequency;
__int64 time_elapsed;
double frameTime;
if (QueryPerformanceFrequency((LARGE_INTEGER*)&frequency)) {
    frameTime = (double)frequency / 60;
    while (true) {
        //process incoming messages here
        QueryPerformanceCounter((LARGE_INTEGER*)&time_now);
        time_elapsed = time_now - time_before;
        if (time_elapsed >= frameTime) {
            //update and render things here:
            time_start = time_before;
        }
    }
}

Are there any problems, or are there any improvements that can be made?

Can't you use a
std::this_thread::sleep_for(std::chrono::milliseconds(x));
or
nanosleep()?

Using any of the two sleeps the cpu will be free to do anything else that needs doing meanwhile this process is sleeping. Also this way it can controls doing the rendering at a specific rate and it´s not a good idea to use a while(true) without any sleep because it eats up all the processing time.


Check if the website is up api.js

'use strict';
const http = require('http');

module.exports = url => {
  const options = {
    host: url,
    method: 'HEAD',
    path: '/'
  };
  const req = http.request(options);
  req.end();
  const promise = new Promise((resolve, reject) => {
    let connected = false;
    req.on('response', res => {
      connected = res.statusCode < 500;
      resolve(connected);
    });

    req.on('error', err => {
      reject(err);
    });
  });
  return promise;
};

The most confusing part for me is which status codes should be considered a valid candidate? apart from that any comments regarding code are welcome.

When the server does not exists it seems node throws an EIO error.

Now you need to make a decision, you can either reject the promise or resolve with false. From an usage point of view I would say I would prefer to resolve it false unless I need to know why the server is unavailable.

I am assuming that you just want to know if it is available or not, thus it doesn't make sense to reject the promise ever.

Your module also doesn't support Urls, in the form of

  scheme:[//[user:password@]host[:port]][/]path[?query][#fragment]

In order to support that you must parse the parameter with the existing URL module.

In order to support both the URL and the URN you can check if the protocol was specified

var http = require('http');
var url = require("url");
var Promise = require('promise');

module.exports = function (uri) {
  var address = url.parse(uri);
  var parts = uri.split('/');
  var options = {
    host: address.protocol != null ? address.host : parts[0],
    method: 'HEAD',
    path: address.protocol != null ? address.pathname : parts.slice(1).join('/')
  };
  var req = http.request(options);
  req.end();
  var promise = new Promise(function (resolve, reject) {
    var connected = false;
    req.on('response', function (res) {
      connected = res.statusCode < 500;
      resolve(connected);
    });

    req.on('error', function (err) {
      resolve(false);
    });
  });
  return promise;
};

module.exports("http://httpstat.us/200").then(function(isAvailable){
    console.log(isAvailable);
});


C++ - Radix sort implementation I have the following radix sort implementation:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstddef>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int radix = 1;
    // Largest element in unsorted array
    int max = *(std::max_element(arr.begin(), arr.end()));
    while(max / radix)
    {
        // Buckets used for sorting. Each bucket representing a digit.
        std::vector<std::vector<int>> buckets(10, std::vector<int>());
        for(const auto& num : arr)
        {
            int digit = num / radix % 10;
            buckets[digit].push_back(num);
        }
        std::size_t k = 0;
        // Take the elements out of buckets into the array
        for(std::size_t i = 0; i < 10; i++)
        {
            for(std::size_t j = 0; j < buckets[i].size(); j++)
            {
                arr[k] = buckets[i][j];
                k++;
            }
        }
        // Change the place of digit used for sorting
        radix *= 10;
    }

}

// Function to print array
void print_arr(std::vector<int>& arr)
{
    for(auto elem : arr)
    {
        std::cout << elem << "\t";
    }
    std::cout << "\n";
}

int main()
{
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the elements: " << std::endl;
    std::getline(std::cin, s);
    std::istringstream ss(s);
    int val;
    while(ss >> val)
    {
        arr.push_back(val);
    }
    std::cout << "Before sorting: \n";
    print_arr(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_arr(arr);
    return 0;
}

I pass an array to the radix_sort function. It uses a variable called radix to identify the digit in a particular place (unit, ten, hundred etc.) in the number. Based on this digit, we sort elements into buckets. Once this sorting is done, the elements are taken out based on the order of bucket (The elements in zeroth bucket comes out first, followed by those in first bucket, second bucket and so on). This is repeated until all the digits in the largest element are visited.

1) I would like to know if there is a better data structure for buckets?

2) Is there a more efficient method to find largest element in the unsorted array?

3) If possible, please provide an overall review of the code.

A vector is usually the best data structure to use unless you have a compelling reason to use something else.  Since you know how many buckets you need, one slight improvement you can make to your buckets is to use an array of vectors, rather than a vector of vectors:

std::array<std::vector<int>, 10> buckets;

This will create 10 empty vectors on the stack (without dynamically allocating those 10).

To find the largest element in an unsorted container requires looking at every element in the container.  The only way to improve on that is to change your algorithm so that it does not need to know what the maximum element is; more on that below.

There are several issues with your sort.  In its current form, it does not handle the trivial case of an empty arr as your scan for a maximum element will dereference the end iterator which is not allowed.  Nor does it does it handle negative numbers.  The % operator can return negative numbers if the numerator is negative.  This will result in an out-of-bounds array element access.  There will also be problems with really large numbers (greater than std::numeric_limits<int>::max() / 10).

One way to handle negative numbers is to make an initial pass where you split the array to sort into two groups, one with negative numbers and the other with non-negative numbers.  Then you can radix sort each group, taking care when doing the negative numbers to keep the intermediate results properly signed.

Failing that, how can you determine when to end your loop if you don't know what the maximum element is?  You can keep track as you put things into buckets.  When the num / radix calculation is 0, that element will always be placed in the first (0) bucket for the rest of the sort.  There may be a larger element earlier in the bucket (think of sorting {203, 3}) so it might still move.  But once all elements have that term 0 then you can stop sorting.

When moving the elements out of the buckets back into the array, you can use the standard algorithms rather than using your nested for loops.  The buckets[i].size() will potentially be calculated every iteration.  You can use std::copy to transfer the elements:

auto k = arr.begin();
for (auto &b: buckets)
    k = std::copy(b.begin(), b.end(), k);

You should pass the parameter to print_arr as a const &  (print_arr(const std::vector<int> &arr)).


4x4 word grid generator in Python This program should generate NxN boards where there are words going from left to right and words going from top to bottom. Words are valid if they appear in the scrabble dictionary.

For example, a valid 3x3 board would be:

ACT
TOO
EGO

as it contains ACT, TOO and EGO going across, and ATE, COG and TOO going down.

import itertools

N = 3

f = open("scrabble.txt")
words = [line.strip().upper() for line in f if len(line.strip()) == N]
words = sorted(words)
f.close()

def tuple_to_grid(t):
    for i in t:
        print(i)
    print()

found = []

for i in itertools.product(words, repeat = N):
    for j in range(N):
        down = "".join([k[j] for k in i])
        if down not in words:
            break
    else:
        tuple_to_grid(i)

N can be changed to change the size of the board. It can generate fine for 2x2 and 3x3 boards, but when it comes to 4x4 it takes hours to generate single boards.

Please comment on how to make this faster.

Your problem is here:

for i in itertools.product(words, repeat = N):

This brute-force approach is why it's taking so long. Let \$k\$ be the
number of \$N\$-letter words. For two or three letters, the time is
proportional to \$k^2\$ or \$k^3\$. Bad enough, but for four letters, it's
\$k^4\$, which is horrendous. \$k\$ is probably significantly larger for
four letters as well, depending on your word list.

So, we need to drastically prune the number of combinations to try.
There are many ways this might be done. One idea would be to prune
things a row at a time. Suppose the first row is "ACHE". Look at all
words beginning with "A". None begin with "AA" or "AQ". So the next row
can eliminate all words beginning with "A" or "Q". Similarly, second-row
second letter can't be "B" or "C" or several other things, because no
words begin with "CB" or "CC", etc. This approach should cut way down on
the combinations.


Small BM25+ implementation for probibalistic result ranking I came up with this small implementation of an Okapi BM25+ ranker using Ruby. I cooked it up in a very short time so it's very simple but I'm trying to think whether there's a better way to write it. In particular, I'm wondering if I should have something like a Ranker class -- intuitively I feel as though I should but it seems to work fine this way too.

The two classes used are Document and Collection. A Collection can contain many Documents. Very simple.

document.rb

class Document
  attr_accessor :body, :rank

  def initialize(params={:body=>'', :rank=>nil})
    @body = params[:body]
    @rank = params[:rank]
  end

  def length
    @body.length
  end

  def include?(term)
    @body.include?(term)
  end

  def term_freq(term)
    # Will need something better here to clean out the document.
    # This is temporary ;)
   @body.gsub(/[^\s\p{Alnum}\p{Han}\p{Katakana}\p{Hiragana}\p{Hangul}]/,'')
    .downcase
    .split
    .count(term)
  end
end

collection.rb

class Collection

  def initialize(params={:docs=>[], :query=>nil})
    @docs = params[:docs]
    @query = params[:query]
  end

  def containing_term(term)
    total = 0
    @docs.each do |doc|
      total += 1 if doc.include?(term)
    end
    total
  end

  def avg_dl
    doc_lengths = 0
    @docs.each do |doc|
      doc_lengths += doc.length
    end
    doc_lengths / total_docs
  end

  def total_docs
    @docs.size
  end

  def idf(term)
    numerator = total_docs - containing_term(term) + 0.5
    denominator = containing_term(term) + 0.5
    Math.log(numerator / denominator)
  end

  def bm25(params={:k => 1.2, :b => 0.75, :delta => 1.0})
    @k = params[:k]
    @b = params[:b]
    @delta = params[:delta]

    @docs.each do |doc|
      score = 0
      dl = doc.length
      query_terms = @query.split

      query_terms.each do |term|
        dtf = doc.term_freq(term)
        numerator = dtf * (@k + 1)
        denominator = dtf + @k * (1 - @b + @b * (doc.length / avg_dl))
        score += idf(term) * (numerator/denominator) + @delta
      end
      doc.rank = score
    end
    @docs
  end

  def sort_by_rank
    @docs.sort! {|a, b| a.rank <=> b.rank}
  end
end

You should use built-ins to simplify the code:

def containing_term(term)
  total = 0
  @docs.each do |doc|
    total += 1 if doc.include?(term)
   end
 total
end

Becomes:

def containing_term(term)
  @docs.count {|doc| doc.include?(term) }
end

And

def avg_dl
  doc_lengths = 0
  @docs.each do |doc|
    doc_lengths += doc.length
  end
  doc_lengths / total_docs
end

Becomes:

def avg_dl
  @docs.map(&:length).inject(:+) / total_docs
end

You are close to immutable,  make the last step

In Collection you use sort!, disallowing method chaining, sort and returning a new object would be more expected.

Use a Hash for an easy but massive optimization

The method:

def term_freq(term)
   # Will need something better here to clean out the document.
   # This is temporary ;)
  @body.gsub(/[^\s\p{Alnum}\p{Han}\p{Katakana}\p{Hiragana}\p{Hangul}]/,'')
   .downcase
   .split
   .count(term)
end

Should be a Hash lookup, where the Hash is created at init time, time complexity would become O(1) with an Hash instead of O(n).


Yet another vowel counting program Several months ago, I asked Program to count vowels, which was asking for a code review of a vowel counting function in implemented in Python.

Since I've been trying to learn Ruby, I decided to reimplement the entire program in it. I'm mainly looking for critiques on:

Naming conventions
Best practices for string iteration
do/end vs {}
Coding standards and best practices

Of course there are some slight changes in how I implemented this in ruby vs Python. The biggest being simply using a Hash since I couldn't find a suitable replacement for Python's tuples. On a unrelated side note, is there a replacement for Python's tuples in ruby?

def count_vowels(string)
    # Create a function that will receive a string. The
    # function will count each vowel in the string and
    # return a count of all the vowels, whether found or not,
    # each being a `key, value` in a Hash.
    vowels = {"a" => 0, "e" => 0, "i" => 0, "o" => 0, "u" => 0}
    string.each_char do |chr|
        if vowels.has_key?(chr)
            vowels[chr] += 1
        end
    end
    return vowels
end

You could use Enumerable#count:

string.chars.count { |char| vowels.has_key?(char) }

You very rarely need to declare a variable (i in this case), and then modify it form inside a block; there's almost always a better way in Ruby.

So while calling count and passing a block is the most direct, you could also have done something like:

string.chars.select { |char| vowels.has_key?(char) }.count

Same idea, just written out in separate filter/count steps.

You can also skip the return since that's implied at the end of a method.

I'd also use a plain array for the vowels. Looking up hash keys is faster, sure, but does it really matter that much? Nah. "Premature optimization is the root of all evil" and all that.

vowels = %w(a e i o u) # same as ["a", "e", "i", ...]

and then the block becomes:

vowels.include?(char)

If you keep the vowels array sorted, you can use bsearch if you want to speed it up a little. Or you can construct the hash in code, instead of typing all that => 0:

list = %w(a e i o u)
vowels = Hash[list.zip(list)] # => { "a" => "a", "e" => "e", ... }

Of course you could also do something funky like this: Remove all the vowels and see how much shorter the string is afterward:

def count_vowels(string)
  string.length - string.gsub(/[aeiou]/, '').length
end

This is also easily made case-insensitive:

string.length - string.gsub(/[aeiou]/i, '').length

Or instead of gsub you can use tr:

string.length - string.tr('aeiou', '').length

(or 'aeiouAEIOU' for case-insensitivity.)

Alternatively, you could extend/monkey-patch the String class a little. I wouldn't recommend it for production code, though. This is just illustrate some Ruby features:

class String
  def vowel?
    self =~ /\A[aeiou]\z/ ? true : false
  end
end

def count_vowels(string)
  string.chars.count(&:vowel?)
end

The &x syntax is a shorthand meaning "invoke x on each element in the collection", so it's equivalent to { |e| e.x }.

Again, this is mostly for fun. I just thought it made the count_vowels method nice and short. And of course, count_vowels could itself be monkey-patched onto String, so you could just call some_string.count_vowels. But again, monkey-patching - while fun - shouldn't be the first thing you reach for. Just illustrating the principle.


SQL Stored Procedure to export specified data I'm currently using a stored procedure(sproc) to export to Excel. The sproc is being passed two parameters for @month and @year. The parameters are then passed to a dynamic pivot table in order to display all the days of the month for the specified month and year.

It does currently work, however are there better ways I could improve my code in order for it be more efficient? Any help or advice would be greatly appreciated as I'm still a bit of a beginner with SQL (and C# for that matter).

Alter Procedure stpDateRange
-- Add parameters
@month int , @year int
As
Begin
Set NoCount ON

    DECLARE @Dates NVARCHAR(max);

SELECT @Dates = CONCAT(@Dates + ', ', QUOTENAME(BalDate))
FROM tblID
WHERE YEAR(BalDate) = @year
  AND MONTH(BalDate) = @month
GROUP BY BalDate
ORDER BY BalDate;

DECLARE @DynSql NVARCHAR(max);
SET @DynSql = 'SELECT *
FROM
(
 SELECT a1.IDNbr , a2.[CustName] as [Name] , (CAST(a1.BalDate AS date)) as BalDate, a1.Balance
 FROM tblID a1
 RIGHT JOIN tblCust a2 ON (a1.IDNbr = a2.IDNbr)
 WHERE MONTH(a1.BalDate) = @month
   AND YEAR(a1.BalDate) = @year AND a2.CustType != ''Inactive'') as d1
PIVOT (
 Sum(Balance)
 FOR BalDate IN ('+ @Dates +')
) piv';

DECLARE @Params NVARCHAR(500) = N'@year int, @month int';

-- SELECT @DynSql AS DynSql;

 EXECUTE sp_executesql @DynSql, @Params, @year = @year, @month=@month;

End

Test results (dates will continue until the last day of the month):

+-----------------------------------------------------------------+
| IDNbr | Name    | 1/1/2018 | 1/2/2018 | 1/3/2018 | 1/4/2018 | ..|
|-----------------------------------------------------------------|
| 52852 | CustOne | 52028.52 | 52038.59 | 52048.69 | 52058.89 | ..|
| 39512 | CustTwo | 95125.75 | 95225.75 | 95325.75 | 95425.75 | ..|
| 52852 | CustThr | 86225.95 | 87225.95 | 88225.95 | 89225.95 | ..|
| 52852 | CustFor | 12533.12 | 12543.12 | 12553.12 | 12563.12 | ..|
| 52852 | CustFiv | 69585.36 | 69685.36 | 69785.36 | 69885.36 | ..|
| ..... | ....... | ........ | ........ | ........ | ........ | ..|

Readability for the results isn't awful , so that wouldn't be a concern for me, especially with how small the program is that is running this. My main concern is the performance of the stored procedure (sproc).


Summations and products and factorials oh my The proper title of this question should be "Summations and products, and factorials oh my!".

After getting quite a bit of useful feedback on this question from @mjolka, and a comment, I decided that there were many things to be improved.

These are the following things that I've added/changed:

A factorial function which uses the product function.
Support for getting the sum, and product of sequences with no elements.
Strongly typed anonymous function parameters.

Again, for those who don't know, a summation is defined as follows:

  $$\sum_{n=a}^{b}f(n)$$

And a product is defined as follows:

  $$\prod_{n=a}^{b}f(n)$$

I'd like to know the following things, which are more or less mostly the same as the ones in the last question:

Am I writing this in a proper functional way?
How can I reduce the repetitiveness in my code?
Is there a way to improve performance? It already runs pretty fast, at approximately \$0.025\$ seconds for inputs of \$10\$).
Anything else?

Here's the code:

let inline summation (f: (double -> double)) low high =
    match (low, high) with
    | (low, high) when low <> high ->
        { low .. high }
        |> Seq.map f
        |> Seq.sum
    | (low, high) when low = high -> 0.0
    | _ -> -1.0

let inline product (f: (double -> double)) low high =
    match (low, high) with
    | (low, high) when low <> high ->
        { low .. high }
        |> Seq.map f
        |> Seq.fold Checked.op_Multiply 1.0
    | (low, high) when low = high -> 1.0
    | _ -> -1.0

let inline factorial n =
    product (fun x -> x) 1.0 n

Here's a few small tests to ensure that the code works:

[<EntryPoint>]
let main argv =
    System.Console.WriteLine(summation (fun x -> x) 1.0 10.0)
    System.Console.WriteLine(product (fun x -> x) 1.0 10.0)
    System.Console.WriteLine(factorial 10.0)
    0

And here's expected output of the above tests:

55
3628800
3628800

Some comments:

    |> Seq.map f
    |> Seq.sum

is just

Seq.sumBy f

Otherwise, if perf really matters I would avoid using Seq, and probably combine the map and fold in the product case.

Also, rather than

match (low, high) with
| (low, high) when low <> high ->
    { low .. high }
    |> Seq.map f
    |> Seq.sum
| (low, high) when low = high -> 0.0

I would use an if to avoid the warning about incomplete pattern match so it would become

if low=high then 0.0
else   {low .. high} |> Seq.sumBy f


Mapping a CSV with UTF-8 encoding to JSON in Python I'm not a programmer, just a guy who needs to solve particular things using code.

I needed to create a JSON from a CSV with predefined headers. I'm downloading an attachment from JIRA (REST API), parsing the file and then mapping each value to a dictionary. The CSV has UTF-8 values.

# First I prepare my dic
    extracted_info = []
    mydic = {   'Ticket': None,
                'Dominio': None,
                'Tipo': None,
                'Ruta': None,
                'Version': None,
                'Componente': None,
                'Comentario': None
                }

    # Mapping values from CSV to Dictionary
    #
    def mappingThoseValues(d, a):
       # print i
        if d != "" :
            if a == 1 :
                mydic['Ticket'] = d
            elif a == 2:
                mydic['Dominio'] = d
            elif a == 3:
                mydic['Tipo'] = d
            elif a == 4:
                mydic['Ruta'] = d
            elif a == 5:
                mydic['Version'] = d
            elif a == 6:
                mydic['Componente'] = d
            elif a == 7:
                mydic['Comentario'] = d
                extracted_info.append(mydic.copy())

    # Parse CSV
    #
    # If URL isn't empty
    if attachment_final_url != "" :
        with open(runbookname) as csvfile:
            spamreader = csv.reader(csvfile, delimiter='\t')
            a= 0
            for row in spamreader:
                for i in row :
                    d = i.decode('iso-8859-1').encode('utf8')
                    a = a + 1
                    mappingThoseValues(d,a)
                    if a == 7 :
                        a = 0
        csvfile.close()
    else :
        status_compara_rn_jira = error_format_tab + 'ERROR: No attachments in : ' + myTicket

I solved what I needed, but I would like to learn how to do this properly, and maybe someday become a real programmer.

The CSV has 7 columns. In order to identify which one I'm parsing, I've added the variable a which increments each time. When I reach the 7th column I reset the value to 0, until the end of the file.

The CSV file doesn't contain headers for each column.

What you have done follows a coding anti-pattern (a coding pattern that is to be avoided). It's ok, you are learning. This anti-pattern is called loop-switch sequence. The essence of this antipattern is that a clear set of steps is done with a loop and a switch statement (or a series of if and else).

In your case, the steps are not even that different to require a distinct statement each. What you essentially want is for the first value in a row to be assigned to the first key, the second value to the second key etc.

You do not need the function mappingThoseValues, nor the variable a. Here's how you can do your job in Python. First, have the names of your dictionary keys in a list.

key_names = ['Ticket', 'Dominio', 'Tipo', 'Ruta', 'Version', 'Componente', 'Comentario']

Then you can read your csv row values and fill in the dictionary in one simple loop.

extracted_info = []
with open(runbookname) as csvfile:
    spamreader = csv.reader(csvfile, delimiter='\t')
    for row in spamreader:
        d =  {}
        for key, value in zip(key_names, row):
            d[key] = value.decode('iso-8859-1').encode('utf8')
        extracted_info.append(d)

The important thing here is to understand the function zip and how we can use it in loops. There is plenty of educational material you can find online (example). A few other things to notice in the new code:

No need for the global variable mydic (in general, you should
avoid using global variables to exchange data between methods).
No need to create copies of your dictionary to append them in the
list, because each time in the loop we create a new dictionary (in
your code you did need to copy mydic because it was a global variable)
No need for the call to close(), because you are using the with clause (close
will be automatically called)

Update based on comments: You can make the code even more succinct and pythonic by employing a dictionary comprehension. This might seem strange/difficult at your experience stage. Don't worry, you can come back to it later. The important bit is to understand the previous points I raised, but I'll include the dictionary comprehension here for reference.

List and dictionary comprehensions is a pythonic way to replace (some) loops by making the loop expression more succinct and also faster. Here's how it would work for your code:

extracted_info = []
with open(runbookname) as csvfile:
    spamreader = csv.reader(csvfile, delimiter='\t')
    for row in spamreader:
        d =  {key: value.decode('iso-8859-1').encode('utf8') for (key, value) in zip(key_names, row) }
        extracted_info.append(d)

Worth mentioning that there is also a csv.DictReader class that can directly read a csv file into a directory. You can provide the names of the keys in one of the argument called fieldnames, or if you do not define any fieldnames it will use the first row of the file as names for the fields/keys. However, my preference is to use this in very common csv format (like excel), as I have found it somewhat cumbersome to define delimiters. You will still need to loop through every row of this reader to get the dictionaries, and you would still need to do any manipulations you want (like your decoding and encoding) as everything is stored in strings. So the regular reader works equally well, and produces equally succinct code.

Finally, let me comment on decoding and encoding Unicode characters. You need of course to decode the bytes you read from your file. When you decode them they become Unicode strings (in Python 2.x they are called "Unicode strings", in Python 3.x they are called "strings", they are the same thing). Instead of immediately encoding these unicode strings to another byte format (as you do) you could simply store these unicode strings to your dictionary. You encode to another byte format only when you need to write it to another file or make it a stream of bytes in any way. In fact, this is the recommended thing to do. Quoting from the linked page:

  The most important tip is: Software should only work with Unicode
  strings internally, decoding the input data as soon as possible and
  encoding the output only at the end.

I hope this helps.


Procedure to determine minimum number of stamps to make up a given monetary value I'm following the Udacity intro to CompSci, and I don't know why my answer isn't quite correct:

Question:

  Define a procedure, stamps, which takes as its input a positive
  integer in pence and returns the number of 5p, 2p and 1p stamps (p is
  pence) required to make up that value. The return value should be a
  tuple of three numbers (that is, your return statement should be
  followed by the number of 5p, the number of 2p, and the nuber of 1p
  stamps).

  Your answer should use as few total stamps as possible by first using
  as many 5p stamps as possible, then 2 pence stamps and finally 1p
  stamps as needed to make up the total.

My attempt

def stamps(targetvalue):
    currentvalue = 0
    fives = 0
    twos = 0
    ones = 0
    while True:
        if targetvalue == currentvalue:
            return fives, twos, ones
        if targetvalue - currentvalue >= 5:
            fives = fives + 1
            currentvalue = currentvalue + 5
        if targetvalue - currentvalue < 5:
            if targetvalue - currentvalue >= 2:
                twos = twos + 1
                currentvalue = currentvalue + 2
            if targetvalue - currentvalue == 1:
                ones = ones + 1
                currentvalue = currentvalue + 1
            else:
                return fives, twos, ones

Let me start by saying that a while True: loop with a return embedded is a bad idea. It works, yes, but the train of logic becomes more complicated to follow the more branches are within the loop. Now if you had, say, 10p, 20p & 50p coins, this would become more and more complicated until it reached a point where you would want to rewrite it in a more sensible way.

With that out of the way, let's get on with the review.

Hard-code as little as possible. Try to use more parameters. All those 5's are for a specific use-case. Try accepting them as parameters in your function.
Return a dict instead of a tuple - it associates each price with a count of stamps of that price and makes the returned value more general with respect to prices.
while True: is a bad idea, as explained above.
Your code style and formatting is OK as per the PEP8 style guide for Python.

The way you do it - you are reimplementing division and remainder from scratch with a loop. This is, well, useless.

The way you're doing it right now is OK if you can't use the above (course restrictions?), which would have helped a lot in this case - you could have used it to get rid of the while loop altogether, just looping over the allowed prices.

What can be done for your code is moving out the part which reimplements division and remainder into functions and using them, but then there remains no difference between the way I do it and the way I suggest for you to do it here.

(Note that the extraction into functions is necessary for reducing code duplication and extending your code to support more prices).

Here is my take:

def stamps(targetValue, prices):
    currentValue = targetValue
    sortedPrices = list(reversed(sorted(prices)))
    stampCounts = []
    for price in sortedPrices:
        stampCounts.append(currentValue // price) # note floor division
        currentValue = currentValue % price # remainder
    return dict(zip(sortedPrices, stampCounts)) # return a dict for caller's convenience


Basic prime summation I wrote basic Python code for the summation of n primes. It works but I wanted to find out how I could improve it and what shortcuts I missed.

    """ So this program is designed to add up the first 'b' primes
    ==> Prime number is defined as a number only divisible by itself or 1"""

def is_prime(a):
    """ This function determines if a number is prime"""

    pri = True
    n = 2
    while n < a:
        if a % n == 0:
            pri = False
        n += 1
    return pri

def addition_of_primes(b):
    """ This function will find the first b primes.
        It stores each one in a list and then we take
        the sum of that list"""

    primes = []
    candidate = 2
    while len(primes) < b:
        if is_prime(candidate):
            primes.append(candidate)
        candidate += 1
    return sum(primes)

print addition_of_primes(1000)

Ignoring the 'use a different algorithm' approach. (Even though the Sieve of Eratosthenes is better).

There are two very common optimisations you missed in the prime checker.

You can increment by 2, so you skip all the even numbers.
You can return False early to avoid waisted CPU cycles.

There is another less common optimisation.

Going to the square root of n.

There is also a rare algorithm, that goes in steps of 6.
But that's uncommon, and if you need that speed, use the Sieve.

As for your addition_of_primes function,
I would not build up an intermarry list.

One way to do that is:

amount = 1
total = 2
candidate = 3
while amount < b:
    if is_prime(candidate):
        amount += 1
        total += candidate
    candidate += 2

return total

Or if you want this all in one line:

import itertools
return sum(itertools.islice(itertools.ifilter(is_prime, itertools.count(2)), b))

If you add the optimisations to is_prime, you should get:

def is_prime(num):
    if num == 2:
        return True

    if num % 2 == 0:
        return False

    for div in xrange(3, int(num ** 0.5) + 1, 2):
        if num % div == 0:
            return False
    return True


FTP Download Helper Method I'm currently using an Open Source FTP library in all my projects as I've never managed to code a decent FTP Helper Library based on the C# 4.0 API.

What do you think about this approach? I'm not quite versed in TDD but ideally I'd like to make this class as testable as possible.

public void DownloadFile(string host, string file, string user, string pass, string path)
{
    if (!String.IsNullOrWhiteSpace(host) && !String.IsNullOrWhiteSpace(file))
    {
        Uri addr = new Uri(host + file);

        using (WebClient client = new WebClient())
        {
            if (!String.IsNullOrWhiteSpace(user) && !String.IsNullOrWhiteSpace(pass))
            {
                client.Credentials = new NetworkCredential(user, pass);
            }

            if (!String.IsNullOrWhiteSpace(path))
            {
                client.DownloadFile(addr, path);
            }
        }
    }
}

Unit testing means that automated tests can run in isolation from any dependencies (such as other classes, but also the environment).

The DownloadFile method has a hard-coded dependency on WebClient and thus on the environment. It can't be used without using the network and (presumably) a remote service. Even if you decide to hit localhost, you'll need to set up an FTP server on your own machine, and that counts as an external dependency as well. Thus the method can't be unit tested as is.

One possible remedy is to hide WebClient behind an appropriate interface (you could call it IWebClient) and inject that into the class holding the DownloadFile method.

In general, however, such methods are better left as Humble Objects and perhaps subjected to integration tests.


Monge Array - leftmost minimum for each row This implementation is the result of solving exercise 4-6 "Monge Arrays" from the book Introduction to algorithms.

Definition of a Monge Array:

  An m x n array A of real numbers is a Monge array if for all \$i\$,
  \$j\$, \$k\$, and \$l\$ such that \$1 \le i \lt k \le m\$ and \$1 \le j \lt l \le n\$, we have \$A[i, j] + A[k, l] \le A[i, l] + A[k, j]\$.

  Relevant parts of problem 4-6:

  d. Here is a description of a divide-and-conquer algorithm that
  computes the left- most minimum element in each row of an m x n Monge
  array A:

  Construct a submatrix A' of A consisting of the even-numbered rows of
  A. Recursively determine the leftmost minimum for each row of A'. Then
  compute the leftmost minimum in the odd-numbered rows of A. Explain
  how to compute the leftmost minimum in the odd-numbered rows of A
  (given that the leftmost minimum of the even-numbered rows is known)
  in \$O(m + n)\$ time.

  e. Write the recurrence describing the running time of the algorithm
  described in part (d). Show that its solution is \$O(m + nlog(m))\$.

I am especially interested in making my code more idiomatic and clean although any improvements to the algorithm are also welcome.

fn min(monge: &Vec<i32>, from: usize, to: usize) -> usize{

    let mut min = monge[from];

    (from + 1..to).fold(from, |m,i| {

        if(monge[i] < min){
            min = monge[i];
            i
        } else{ m }
    })
}

fn minimums(monge: &Vec<i32>, leftmost: & mut Vec<usize>, rows: usize, columns: usize, factor: usize)
{

    if rows == 1 {
        leftmost[0] = min(monge, 0, columns) % columns;
    }
    else {

        let mid = rows - (rows / 2);
        minimums(monge, leftmost, mid, columns, 2 * factor);

        let get = |i, j| (i * columns) + j;

        for row in (0..)
                       .map(|x| factor * (2 * x + 1))
                       .take_while(|&x| x < (rows - 1)) {

            leftmost[row] =  min(monge,
                                 get(row ,leftmost[row - factor]),
                                 get(row, leftmost[row + factor] + 1)) % columns;
        }

        if rows % 2 == 0 {

            let row = factor * (rows - 1);
            leftmost[row] = min(monge,
                                get(row , leftmost[row - factor]),
                                get(row, columns)) % columns;
        }

    }
}

fn main() {

    let row = 7;
    let x = vec!
    [10,17,13,28,23,
     17,22,16,29,23,
     24,28,22,34,24,
     11,13,6,17,7,
     45,44,32,37,23,
     36,33,19,21,6,
     75,66,51,53,34];

    let mut leftmost = vec![0;row];

    minimums(&x, &mut leftmost, row,5, 1);

    for x in leftmost {
        println!("{}", x);
    }

}

Read compiler warnings and fix them:

src/main.rs:7:11: 7:27 warning: unnecessary parentheses around `if` condition, #[warn(unused_parens)] on by default
src/main.rs:7         if(monge[i] < min){
                        ^~~~~~~~~~~~~~~~

Spaces before braces

fn min(...) -> usize{ // No
fn min(...) -> usize { // Yes

Be consistent about brace indentation

// No
if {
    1
} else { 2 }

// Yes
if {
    1
} else {
    2
}

mut is stuck to the &

& mut Vec<usize> // No
&mut Vec<usize> // Yes

else lives on the same line as the previous curly brace

// No
if true {
    1
}
else {
    2
}

// Yes
if true {
    1
} else {
    2
}

No need to leave blank space at the beginning of a block

// No
fn foo() {

    let a = 1;

// Yes
fn foo() {
    let a = 1;

Keep the macro braces attached to the macro name, and indent the body if it's going to be multiline. Leave a trailing comma, and use spaces after the comma

let x = vec![
    10, 17, 13, 28, 23,
    17, 22, 16, 29, 23,
    24, 28, 22, 34, 24,
    11, 13,  6, 17,  7,
    45, 44, 32, 37, 23,
    36, 33, 19, 21,  6,
    75, 66, 51, 53, 34,
];

Leave spaces after commas in function calls as well, but not before

// No
get(row ,leftmost[row - factor]),

// Yes
get(row, leftmost[row - factor]),

A single space around =

leftmost[row] =  min(...); // No
leftmost[row] = min(...); // Yes

Never take a &Vec<T> as an argument, use a &[T] instead. This allows more types to be provided
Your min function is poorly named. The name seems to suggest it will return the minimum value, when it actually returns the index of the minimum value. Rename it to something intention-revealing. Maybe index_of_minimum
Space after a ; in an array or vector

vec![0;row]; // No
vec![0; row]; // Yes

Instead of having multiple lines in a for x in y clause, create a variable to store that in.

// Poor name because I'm not sure what it really is
let x_rows = (0..)
    .map(|x| factor * (2 * x + 1))
    .take_while(|&x| x < (rows - 1));

for row in x_rows {

Eventually, min_by will be stabilized, and you can use it:

// May be off-by-one errors here
let (min_index, _) =
    monge.iter()
    .enumerate()
    .skip(from)
    .take(to - from)
    .min_by(|&(_, v)| v)
    .unwrap();
min_index

I'm sure there's more that can be suggested, but my brain is tired for now ^_^.

fn index_of_minimum(monge: &[i32], from: usize, to: usize) -> usize {
    let mut min = monge[from];

    (from + 1..to).fold(from, |m,i| {
        if monge[i] < min {
            min = monge[i];
            i
        } else {
            m
        }
    })
}

fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) {
    if rows == 1 {
        leftmost[0] = index_of_minimum(monge, 0, columns) % columns;
    } else {
        let mid = rows - (rows / 2);
        minimums(monge, leftmost, mid, columns, 2 * factor);

        let get = |i, j| (i * columns) + j;

        let x_rows = (0..)
            .map(|x| factor * (2 * x + 1))
            .take_while(|&x| x < (rows - 1));

        for row in x_rows {
            leftmost[row] = index_of_minimum(monge,
                                get(row, leftmost[row - factor]),
                                get(row, leftmost[row + factor] + 1)) % columns;
        }

        if rows % 2 == 0 {
            let row = factor * (rows - 1);
            leftmost[row] = index_of_minimum(monge,
                                get(row, leftmost[row - factor]),
                                get(row, columns)) % columns;
        }
    }
}

fn main() {
    let row = 7;
    let x = vec![
        10, 17, 13, 28, 23,
        17, 22, 16, 29, 23,
        24, 28, 22, 34, 24,
        11, 13,  6, 17,  7,
        45, 44, 32, 37, 23,
        36, 33, 19, 21,  6,
        75, 66, 51, 53, 34,
    ];

    let mut leftmost = vec![0; row];

    minimums(&x, &mut leftmost, row, 5, 1);

    for x in leftmost {
        println!("{}", x);
    }
}


Sudoku Solver Optimization I am currently working on a Sudoku solver that should be able to solve a 25 x 25 grid. However, I am experiencing problems optimizing it to run quick enough to actually get a result with any grid bigger than 9 x 9. I was wondering if anyone could take a look at my code and give me some ideas on how to optimize it.

public class SudokuGrid {
    private String[][] grid;

    /**
     * Constructs an empty 9x9 Sudoku Grid.
     */
    public SudokuGrid() {
        this(16);
    }

    /**
     * Constructs an empty, square Sudoku grid.
     * @param boardSize the length of each row & column
     */
    public SudokuGrid(int gridSize) {
        this.grid = new String[gridSize][gridSize];
        for (int r = 0; r < this.grid.length; r++) {
            for (int c = 0; c < this.grid.length; c++) {
                this.grid[r][c] = "-";
            }
        }
    }

    /**
     * Constructs a partially filled Sudoku grid.
     * @param str the contents of the grid (using '-' for blank)
     */
    public SudokuGrid(String str) {
        String[] contents = str.split("\\s+");
        int gridSize = (int)Math.sqrt(contents.length);

        this.grid = new String[gridSize][gridSize];
        for (int i = 0; i < contents.length; i++) {
            this.grid[i/gridSize][i%gridSize] = contents[i];
        }
    }

    /**
     * Fills the Sudoku grid with numbers using recursive backtracking.
     * @return whether the grid was successfully filled
     */

    public boolean fillGrid(){
        return fillGrid(0,0);
    }

    private boolean fillGrid(int row, int col){
        if (col >= this.grid.length) {
            col = 0;
            if (++row >= this.grid.length)
                return true;
        }
        if (!this.grid[row][col].equals("-")){
            return fillGrid(row , col + 1);
        }
        for (int i = 1; i <= this.grid.length; i++) {
            String temp = ""+i;
            if (isValidValue(row, col, temp)) {
                this.grid[row][col] = temp;
                if (fillGrid(row, col + 1)){
                    return true;
                }
            }
        }
        grid[row][col] = "-";
        return false;
    }

    private boolean isValidValue(int row, int col, String val) {
        for (int i = 0; i < this.grid.length; i++){
            if (val.equals(this.grid[i][col])){
                return false;
            }
        }

        for (int j = 0; j < this.grid.length; j++){
            if (val.equals(this.grid[row][j])){
                return false;
            }
        }

        double squareRootVal = Math.sqrt(this.grid.length);
        int rowOffset = (row / (int)squareRootVal) * (int)squareRootVal;
        int colOffset = (col / (int)squareRootVal) * (int)squareRootVal;
        for (int i = 0; i < squareRootVal; i++) {
            for (int j = 0; j < squareRootVal; j++){
                if (val.equals(this.grid[rowOffset + i][colOffset + j])){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Constructs a String representation of the grid.
     * @return the grid in a displayable row/column format
     */
    @Override
    public String toString() {
        String output = "";
        for (int r = 0; r < this.grid.length; r++) {
            for (int c = 0; c < this.grid.length; c++) {
                output += grid[r][c] + " ";
            }
            if (r < this.grid.length-1) {
                output += "\n";
            }
        }
        return output;
    }
}

isValidValue() is needlessly simple – you check all 9 values for every field always. Instead, try implementing "pencil marks" that humans use when solving sudoku. For every field without a value, you should explicitly store which values can still be entered into this field. (In say a boolean[rows][cols][value]).

Then, when you place a number, remove it as a candidate value from other fields in the row/col/box, and add it again as you backtrack out of that try.

Other techniques humans use can also be implemented in software. Once you track pencil marks, Hidden Single should be fairly straightforward. (In fact it might be better to try that one before a backtracking search.) You could also try to speed up the search by filling in squares with the fewest possible candidates first, and by trying the digits you've already placed the most first. (I'm less certain that these will help a software solver, but they might reach a conflict that will cause a backtrack earlier.)


Searching values of range X in range Y This allows me to search each cell J4:J6525 in range K4:K6525. If it is found it will paste the values in Offset(0, 2) (column M).

I run it for files with more than 60000 lines, and sometimes much bigger. It takes a long time to complete. How can I make this run faster?

Sub Finder()

Dim WhereToSearch As Range, WhatToSearch As Range, ValueFound As Range, ValueSearched As Range

Set WhereToSearch = ActiveSheet.Range("K4:K6525")
Set WhatToSearch = ActiveSheet.Range("J4:J6525")

For Each ValueSearched In WhatToSearch

Set ValueFound = WhereToSearch.Find(What:=ValueSearched, LookIn:=xlValues, LookAt:=xlWhole, SearchOrder:=xlByRows, SearchDirection:=xlNext, MatchCase:=False, SearchFormat:=False)

If Not ValueFound Is Nothing Then

ValueFound.Offset(0, 2) = ValueFound

End If
Next
End Sub

It's hard to beat the performance of standard Excel WorksheetFunctions.
This will find the matches.

  Range("M4:M6525").Formula = "=IF(ISNA(MATCH(J4,$K$4:$K$6525,0)),"""",INDEX($K$4:$K$6525,MATCH(J4,$K$4:$K$6525,0), 1))"

Then if you want to remove the formulae use this

  Range("M4:M6525").Value =Range("M4:M6525").Value


Winforms Mathematical Operator Label I wrote a custom class which (atm) displays the +, -, =, x, and ÷ operators inside a circle. Apart from the issue of some symbols not appearing in the exact center (everything except + looks a bit off) it works great. It uses an enum to select the symbol to make using the ÷ symbol easier.

public enum Operators { Plus = '+', Minus = '-', Divide = '÷', Multiply = 'x', Equal = '=' };

class MathematicalOperator : Control
{
    private Operators op;
    public Operators Operator
    {
        get { return op; }
        set
        {
            if (value == op) return;
            op = value;
            Invalidate();
        }
    }

    private Color background;
    public Color Background
    {
        get { return background; }
        set
        {
            if (value == background) return;
            background = value;
            Invalidate();
        }
    }

    private Color foreground;
    public Color Foreground
    {
        get { return foreground; }
        set
        {
            if (value == foreground) return;
            foreground = value;
            Invalidate();
        }
    }

    public MathematicalOperator(Operators op)
    {
        SetStyle(ControlStyles.SupportsTransparentBackColor, true);
        BackColor = Color.Transparent;
        TabStop = false;
        Operator = op;
        Foreground = Color.Black;
        Background = Color.White;
        Width = 35;
        Height = 35;
    }

    public MathematicalOperator()
        : this(Operators.Equal)
    { }

    protected override void OnPaint(PaintEventArgs e)
    {
        base.OnPaint(e);

        Graphics graphics = e.Graphics;
        Rectangle rc = this.ClientRectangle;
        graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
        Font font = new Font("Arial", rc.Height * 0.65f, FontStyle.Bold, GraphicsUnit.Pixel);
        StringFormat sf = new StringFormat();
        sf.Alignment = StringAlignment.Center;
        sf.LineAlignment = StringAlignment.Center;

        using (var background = new SolidBrush(Background))
        using (var foreground = new Pen(Foreground, 2.0f))
        using (var text = new SolidBrush(Foreground))
        {
            graphics.FillEllipse(background, rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);
            graphics.DrawEllipse(foreground, rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);
            graphics.DrawString(((char)Operator).ToString(), font, text, rc, sf);
        }
    }
}

The OnPaint Method

I would refactor your OnPaint method a little to use more descriptive variable names, and store the new values added to the Rectangle in another variable, just to make things more maintainable. (And perhaps a little quicker, as well.)

Start with:

protected override void OnPaint(PaintEventArgs e)
{
    base.OnPaint(e);

    Graphics graphics = e.Graphics;
    Rectangle rc = this.ClientRectangle;
    graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
    Font font = new Font("Arial", rc.Height * 0.65f, FontStyle.Bold, GraphicsUnit.Pixel);
    StringFormat sf = new StringFormat();
    sf.Alignment = StringAlignment.Center;
    sf.LineAlignment = StringAlignment.Center;

    using (var background = new SolidBrush(Background))
    using (var foreground = new Pen(Foreground, 2.0f))
    using (var text = new SolidBrush(Foreground))
    {
        graphics.FillEllipse(background, rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);
        graphics.DrawEllipse(foreground, rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);
        graphics.DrawString(((char)Operator).ToString(), font, text, rc, sf);
    }
}

And work towards:

protected override void OnPaint(PaintEventArgs e)
{
    base.OnPaint(e);

    Graphics graphics = e.Graphics;
    Rectangle controlBounds = this.ClientRectangle;
    graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
    Font operatorFont = new Font("Arial", controlBounds.Height * 0.65f, FontStyle.Bold, GraphicsUnit.Pixel);
    StringFormat stringFormatter = new StringFormat();
    stringFormatter.Alignment = StringAlignment.Center;
    stringFormatter.LineAlignment = StringAlignment.Center;

    RectangleF outsideBounds = new RectangleF(controlBounds.Left + 1.5f, controlBounds.Top + 1.5f, controlBounds.Width - 4.0f, controlBounds.Height - 4.0f);

    using (var backgroundBrush = new SolidBrush(Background))
    using (var foregroundPen = new Pen(Foreground, 2.0f))
    using (var textBrush = new SolidBrush(Foreground))
    {
        graphics.FillEllipse(backgroundBrush, outsideBounds);
        graphics.DrawEllipse(foregroundPen, outsideBounds);
        graphics.DrawString(((char)Operator).ToString(), operatorFont, textBrush, controlBounds, stringFormatter);
    }
}

This should help maintainability in the future. Yes, things are much more verbosely named, but variable/parameter/method name lengths only affect compilation performance, not run-time.

Qualifying Names

I would also consider fully-qualifying the names of the member variables of the class. I.e. this.Operator instead of Operator. Yes, it makes it much more verbose again, but it's also clearly expressing exactly where things are coming from. The idea is to be able to skim the code and know it immediately. (Not that you can't do that with the original, but it does remove ambiguities.)

If we make that last change as well, we end up with:

protected override void OnPaint(PaintEventArgs e)
{
    base.OnPaint(e);

    Graphics graphics = e.Graphics;
    Rectangle controlBounds = this.ClientRectangle;
    graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
    Font operatorFont = new Font("Arial", controlBounds.Height * 0.65f, FontStyle.Bold, GraphicsUnit.Pixel);
    StringFormat stringFormatter = new StringFormat();
    stringFormatter.Alignment = StringAlignment.Center;
    stringFormatter.LineAlignment = StringAlignment.Center;

    RectangleF outsideBounds = new RectangleF(controlBounds.Left + 1.5f, controlBounds.Top + 1.5f, controlBounds.Width - 4.0f, controlBounds.Height - 4.0f);

    using (var backgroundBrush = new SolidBrush(this.Background))
    using (var foregroundPen = new Pen(this.Foreground, 2.0f))
    using (var textBrush = new SolidBrush(this.Foreground))
    {
        graphics.FillEllipse(backgroundBrush, outsideBounds);
        graphics.DrawEllipse(foregroundPen, outsideBounds);
        graphics.DrawString(((char)this.Operator).ToString(), operatorFont, textBrush, controlBounds, stringFormatter);
    }
}

Comments on 'Magic Values'

You should also consider specifying what some of the floating values are set in the manner they are for via comments. I.e. on the using (var foreground = new Pen(Foreground, 2.0f)) line it would not hurt to add a comment indicating why the width of the Pen is 2.0f. This is merely to help remind yourself in the future for if (when) you come back to the code.

Hardcoded 'Magic Values'

You should also consider adding a custom RectangleF TextPadding property that defaults to new RectangleF(1.5f, 1.5f, 4.0f, 4.0f) to remove those hard-coded values. This will also increase extensibility and reuse-ability greatly for the future. (We want to reuse this class in another programme, don't we?)

You could then write an extension method to add two rectangles together or similar. This bit is up to you, but it could definitely ease maintainability and reuse-ability.

Field Naming

I also, personally, would not name the private Operators field op. Generally speaking, fields should be the camelCase variant of the property they back (operator in your case). Though, personally, I don't use that idea, and instead I use the backing field name as equivalent to the property name but prefixed with an underscore (_Operator in your case). Both these options are open, and generally increase meaningfulness.

All of these suggestions are mostly for consistency and conventions so that if you have to go back into the code two years from now, it's very easy to follow. These are based on my personal flavours of writing code, and are no way concrete.

Take them all as you would like. :)


Computation of inter-grid distance array for 2D lattice I have a 2D lattice with U × U number of grids. My goal is to create an array – of shape U^2 × U^2 – where each entry denotes the least-distance between each grid and any other grid.

Currently, for U=60, my Python script takes ~5 minutes to complete. As a novice programmer, I suspect there must be a more efficient approach – I've read about performance issues related to numpy loops. My objective is to handle U=1000.

import numpy as np
np.random.seed(13)
import matplotlib.pyplot as plt
import time

start_time = time.time()

U = 60

def FromGridToList(i_, j_):
    return i_*U + j_

def FromListToGrid(l_):
    i = np.floor(l_/U)
    j = l_ - i*U
    return np.array((i,j))

Ulist = range(U**2)

dist_array = []
for l in Ulist:
    print l, 'of', U**2
    di = np.array([np.abs(FromListToGrid(l)[0]-FromListToGrid(i)[0]) for i, x in enumerate(Ulist)])
    di = np.minimum(di, U-di)

    dj = np.array([np.abs(FromListToGrid(l)[1]-FromListToGrid(i)[1]) for i, x in enumerate(Ulist)])
    dj = np.minimum(dj, U-dj)

    d = np.sqrt(di**2+dj**2)
    dist_array.append(d)

dist_array = np.vstack(dist_array)
print time.time() - start_time, 'seconds'

1. Introduction

Veedrac is totally correct: you can't expect to compute a \$ 1000^2 \$ by \$ 1000^2 \$ array of distances: this would have \$ 10^{12} \$ elements, and if each element is a double-precision floating-point number then that would require 8 terabytes of memory.

So you need to reconsider your approach to whatever it is you are trying to do. You're going to have to compute these distances when you use them, instead of precomputing an array. Unfortunately, you haven't explained what you are trying to do, so we can't help. The only thing we can do, given what you've presented, is show you how to compute your result a bit faster and a bit tidier.

2. Review

There are no docstrings or comments. What do your functions compute? What is the meaning of variables like U? It's very hard to provide advice about code like this when the purpose is unclear.
The use of the print statement means that the code is not portable to Python 3. Better to use the print function.
Python has a built-in module timeit for timing execution of code. It's better to use this instead of writing your own.
Code at the top level of a module makes it hard to test a program or time its execution. It would be better to put this code into a function, for example:

def dist_array(U=60):
    Ulist = range(U**2)
    a = []
    ...
    return np.vstack(a)

Then in the interactive interpreter you could run:

>>> from timeit import timeit
>>> timeit(dist_array, number=1)
554.5194303740282

3. Performance

As always when speeding up NumPy code, you should scrutinize every Python loop—that is, every for, while, generator and comprehension—to see if the computation can be vectorized, that is, transformed into a sequence of NumPy whole-array operations. The usual approach is to start by removing the innermost loops and work outwards.

So let's start with the group of lines:

di = np.array([np.abs(FromListToGrid(l)[0]-FromListToGrid(i)[0])
               for i, x in enumerate(Ulist)])
di = np.minimum(di, U-di)
dj = np.array([np.abs(FromListToGrid(l)[1]-FromListToGrid(i)[1])
               for i, x in enumerate(Ulist)])
dj = np.minimum(dj, U-dj)
d = np.sqrt(di**2+dj**2)

I'm going to give speedups in terms of percentages of the runtime for the original version of the code.

Note that x is unused, so we don't need the enumerate, we can just write for i in range(len(Ulist)) which is the same as for i in Ulist. This saves about 2%, bringing the runtime down to 98%.
Expand the function FromListToGrid inline:

di = np.array([np.abs(np.floor(l / U) - np.floor(i / U))
               for i in Ulist])
di = np.minimum(di, U - di)
dj = np.array([np.abs(l - np.floor(l / U) * U - i + np.floor(i / U) * U)
               for i in Ulist])
dj = np.minimum(dj, U - dj)
d = np.sqrt(di ** 2 + dj ** 2)

This brings the runtime down to 32%.
Note that l does not depend on i so some of the computation can be moved out of the loops:

zi = np.floor(l / U)
di = np.array([np.abs(zi - np.floor(i / U)) for i in Ulist])
di = np.minimum(di, U - di)
zj = l - zi * U
dj = np.array([np.abs(zj - i + np.floor(i / U) * U) for i in Ulist])
dj = np.minimum(dj, U - dj)
d = np.sqrt(di**2+dj**2)

This brings the runtime down to 22%.
Avoid the list comprehensions altogether using NumPy whole-array operations:

Uarray = np.arange(U ** 2)
zi = np.floor(l / U)
di = np.abs(zi - np.floor(Uarray / U))
di = np.minimum(di, U - di)
zj = l - zi * U
dj = np.abs(zj - Uarray + np.floor(Uarray / U) * U)
dj = np.minimum(dj, U - dj)
d = np.sqrt(di ** 2 + dj ** 2)

This brings the runtime down to 0.4%.
Move the computation of anything that does not depend on l out of the loop over l. Also, use numpy.hypot instead of np.sqrt(di ** 2 + dj ** 2):

a = []
Uarray = np.arange(U ** 2)
Ui = np.floor(Uarray / U)
Uj = Ui * U - Uarray
for l in Uarray:
    zi = np.floor(l / U)
    di = np.abs(zi - Ui)
    di = np.minimum(di, U - di)
    zj = l - zi * U
    dj = np.abs(zj + Uj)
    dj = np.minimum(dj, U - dj)
    d = np.hypot(di, dj)
    a.append(d)

This brings the runtime down to 0.2%.
Now we can start to remove the loop over l. This can be done in stages, lifting one line at a time out of the loop (and checking that the results are correct as we go). To show how this works, let's lift the computation of di out of the loop. We have:

for l in Uarray:
    zi = np.floor(l / U)
    di = np.abs(zi - Ui)
    di = np.minimum(di, U - di)
    # etc.

We can easily compute all the values of zi at once, like this:

Zi = np.floor(Uarray / U)
for l in Uarray:
    di = np.abs(Zi[l] - Ui)
    di = np.minimum(di, U - di)
    # etc.

Now we observe that Zi is just the same as Ui, so that becomes:

for l in Uarray:
    di = np.abs(Ui[l] - Ui)
    di = np.minimum(di, U - di)
    # etc.

Next we lift Ui[l] - Ui out of the loop. This expression computes the pairwise differences between Ui[l] and all elements in Ui. NumPy's "broadcasting" mechanism means that we can do this in one step, for all values of l, just by indexing Ui in two different ways, like this:

Ui.reshape(-1, 1) - Ui.reshape(1, -1)

In fact, broadcasting means that we don't even need the second reshape; this is the same as:

Ui.reshape(-1, 1) - Ui

Putting that together, we now have:

di = np.abs(Ui.reshape(-1, 1) - Ui)
di = np.minimum(di, U - di)
for l in Uarray:
    # etc.

We can keep applying this process to lift all the computation out of the loop (I won't go into the details), resulting in this:

def dist_array(U=60):
    Uarray = np.arange(U ** 2)
    Ui = np.floor(Uarray / U)
    di = np.abs(Ui.reshape(-1, 1) - Ui)
    di = np.minimum(di, U - di)
    Uj = Ui * U - Uarray
    dj = np.abs(Uarray.reshape(-1, 1) - Ui.reshape(-1, 1) * U + Uj)
    dj = np.minimum(dj, U - dj)
    return np.hypot(di, dj)

There's probably a little bit more time to be squeezed out by using NumPy's out= parameter to reduce the memory usage, but I'll stop here.

This is more than 500 times as fast as the original code, and computes the U=60 case in about a second on my laptop.

4. Simplifying

The computation of dj now looks like this:

    Uj = Ui * U - Uarray
    dj = np.abs(Uarray.reshape(-1, 1) - Ui.reshape(-1, 1) * U + Uj)

If we do the multiplication before the reshape, this becomes:

    dj = np.abs((Uarray - Ui * U).reshape(-1, 1) + Uj)

which is:

    dj = np.abs(-Uj.reshape(-1, 1) + Uj)

and since we're taking the absolute value, that's:

    dj = np.abs(Uj.reshape(-1, 1) - Uj)

which is symmetric with the computation of di.
We have:

    Uarray = np.arange(U ** 2)
    Ui = np.floor(Uarray / U)
    Uj = Ui * U - Uarray

but this is the same as:

    Uarray = np.arange(U ** 2)
    Ui, Uj = divmod(Uarray, U)

and this is the same as:

    Ui, Uj = np.mgrid[:U, :U]
    Ui = Ui.reshape(-1)
    Uj = Uj.reshape(-1)

(see numpy.mgrid).
Now that the computation of di and dj is so similar, it makes sense to extract the common code into a function, like this:

def dist_array(U=60):
    def d(i):
        i = np.abs(i.reshape(-1, 1) - i.reshape(-1))
        return np.minimum(i, U - i)
    i, j = np.mgrid[:U, :U]
    return np.hypot(d(i), d(j))


Minimum sum of numbers The code reads an input with numbers and find the sum with the minimum difference of the first two big numbers. The sums are three.

Is there is any way to make the code cleaner? (Note that I don't need to take any restrictions such as NULL parameters, etc)

Moreover, there is an int in my program pA = -1 with that value. Now, because the pA used as pointer you see below that I have the statement ProfitA = array[pA];, that statement doesn't give any problems, but I just wanted to point it out in case you could clean my code a bit.

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

#define TRUE 1
#define FALSE 0
#define min(ProfitA, ProfitB, ProfitC) ProfitA > (ProfitB > ProfitC ? ProfitB : ProfitC) ? ProfitA : (ProfitB > ProfitC ? ProfitB : ProfitC)

int main() {

    FILE* input = fopen("share.in","r");
    int bestMin = INT_MAX;
    int N = 0;
    fscanf(input,"%d",&N);

    int *array = malloc(N * sizeof(int));

    int pA = -1, pB = N - 1;
    int ProfitA = 0, ProfitC = 0, ProfitB = 0;

    for (int i = 0; i < N; i++) {
        fscanf(input,"%d",&array[i]);
        ProfitB += array[i];

    }

    ProfitB = ProfitB - array[pA] - array[pB];
    ProfitA = array[pA];
    ProfitC = array[pB];

    fclose(input);

    short flag = TRUE;
    int check_L = 0, check_R = 0;

    while ((pB - pA != 1) && (flag == TRUE)) {
        flag = FALSE;

        check_L += ProfitA + array[pA + 1];
        check_R += ProfitC + array[pB - 1];

        if (check_L < check_R) {

            ProfitA = check_L;
            ProfitB -= array[pA + 1];
            pA++;
            flag = TRUE;

        }
        else {

            ProfitC = check_R;
            ProfitB -= array[pB - 1];
            pB--;
            flag = TRUE;
        }
      check_R = 0, check_L = 0;

        printf("k1 = %d, k3 = %d, k2 = %d\n",ProfitA,ProfitB,ProfitC);

           int  currentMin = min(ProfitA, ProfitB, ProfitC);

            if (currentMin < bestMin) {
                bestMin = currentMin;
            }

    }
    printf("%d\n",bestMin);

    return 0;
}

You definitely can make your code cleaner :

Your function main does all the job, that's usually quite bad. You can, at least, separate two aspects : reading the input (and store it in an array) and processing the input. That would be a little bit easier to read
Use comments ! Not even one here, that's pretty bad.
Better use of new lines : you really tend to use way too much of them. Multiple new lines should be used to separate parts of code that do quite different things, but in no case you should use two just after an if
Better variable naming : just one example, but it's because it's very common : i . I really don't like it, because by reading the index, you don't know through what you iterate. The best example for that are matrices, i and j are far less understandable than iRow and iCol
The indentation is also quite bad, especially at the end
You don't free the memory you have allocated.
Have you tried removing your condition on flag in your while ? You set it to false, then there's an if/else, and in both cases, it's set to true again.


A big ng-repeat to display the progress of builds I'm looking to improve the speed my ng-repeat or find an alternative way to do it, because it takes too long to load when it has to manage a lot of data.

{{::build._buildTypeId}}

Running on: {{::build.agent._name}}

Version: {{::build._number}}

Run by: {{::build.user._name}}

 5  ,'progress-bar-warning': build._percentageComplete <= 6}">
                     5" class="sr-only"> {{build._percentageComplete}}% Completed

= 50"> in : {{build.timeInfo}} Minutes

If it is performance you are after, the scroll till you drop directive by Angular UI may help.

A common mistake is to throw too many array members inside your DOM via ng-repeat, but you are already limiting your input...

You may consider using custom filter instead and making sure it is fast.


Sorting an array of objects by a property which may be missing Problem

I am sorting an array of objects. Each element may have a property called reference or it may be undefined. When defined, it is a user-provided string (which is why I use String.localeCompare()).

If the reference is not available, that element's relative position in the final list is irrelevant save that all blank references must appear grouped together at the end.

Implementation

function sort(searchResult) {
    const hasReference = searchResult
        .filter(taskCard => typeof taskCard.reference !== "undefined");

    const missingReference = searchResult
        .filter(taskCard => typeof taskCard.reference === "undefined");

    hasReference.sort(
        (tc1, tc2) => tc1.reference.localeCompare(tc2.reference)
    );

    return hasReference.concat(missingReference);
}

My Concerns

Is this an efficient way of solving this problem in terms of time?
I'm currently iterating over the initial array twice. Is there an elegant ES6 way to do this in a single pass that I'm not seeing?
I believe memory to be less of a concern (because I exactly double the amount of memory used while processing by generating two new arrays that together are the size of the original); am I correct?
Are there any scalability pitfalls doing it this way?
As usual, any other comments are welcome.

Here's a single-pass example. Very similar to @janos' code (which has a good complexity analysis). The only difference is in how various cases with undefined are treated.

function sort(searchResult) {
  return searchResult.sort((tc1, tc2) => {

    const tc1RefUndefined = tc1.reference == null;
    const tc2RefUndefined = tc2.reference == null;
    if (tc1RefUndefined || tc2RefUndefined) {
      if (tc1RefUndefined && tc2RefUndefined) {
        return 0;

        // or if consistency in grouping (within the groups) is necessary:
        // return tc1.otherProperty comparedTo tc2.otherProperty
      } else if (tc1RefUndefined) {
        return -1;
      } else {
        return 1;
      }
    }

    return tc1.reference.localeCompare(tc2.reference);
  });
}


Updating the icon of every JLabel in a JLabel ArrayList I want to update every icon of a JLabel ArrayList, to its own individual icon based off of an outside ArrayList. The outside ArrayList is called _board_, and the JLabel ArrayList is called _tiles_. I want to update every icon to its corresponding item in _board_. How can I do that efficiently? I need it to update every icon of a huge list, we're talking like 100 - 200 items long. Right now, at a hundred items long, it takes about 4 seconds before displaying all of the icons at the same time:

for (int i = 0; i < board.size(); i++) {
    //this is all one line:
    tiles.get(i).setIcon(resizeIcon(displayTile(board.get(i),
    tiles.get(i).getHeight(), tiles.get(i).getHeight()));
}
//this resizes the ImageIcon and returns the risized icon:
public static ImageIcon resizeIcon(ImageIcon i, int x, int y) {
    Image image = i.getImage();
    Image newimg = image.getScaledInstance(x, y, java.awt.Image.SCALE_SMOOTH);
    i = new ImageIcon(newimg);
    return i;
}
//this returns an ImageIcon based off of the number that is put in:
public static ImageIcon displayTile(int num) {
    if (num != 0) {
        ImageIcon i = new ImageIcon("src/resources/" + num + ".png");
        return i;
    }
    ImageIcon i = new ImageIcon("src/resources/0.png");
    return i;
}

We will start by cleaning up the code:

First, let's make the for loop cleaner to read. A compiler is able to inline variables that are only used once in a scope.

for (int i = 0; i < board.size(); i++) {

    final ImageIcon tileToDisplay = displayTile(i);

    final int height = tiles.get(i).getHeight();
    final ImageIcon resizedTileToDisplay = resizeIcon(tileToDisplay,height,height);
}

Second, in displayTile(int num), StringBuilder is more efficient when concatenating strings. Also, if(num != 0) is redundant because you apply the same logic in both cases.

public static ImageIcon displayTile(int num) {

    final StringBuilder pathBuilder = new StringBuilder("src/resources/");
    pathBuilder.append(num);
    pathBuilder.append(".png");

    return new ImageIcon(pathBuilder.toString());
}

Lastly, resizeIcon changes the parameter i; methods should not change the parameters that they receive:

public static ImageIcon resizeIcon(ImageIcon icon, int x, int y) {

    Image resizedImage = icon.getImage().getScaledInstance(x,y,java.awt.Image.SCALE_SMOOTH));
    return new ImageIcon(resizedImage);
}

Now, let's deal with performance:

You are loading 100 - 200 images from a file, resizing each one and then placing it on a screen. This is a resource intensive task and you need to optimise it. Here are some suggestions

Use a ThreadPool to load the images asynchronously on start up. Cache them in memory and use them as needed.
Only load images as needed. For example, the board may have 200 tiles, but only 10 are visible at a given time. So load the first ten tiles. Anticipate which tiles will be needed and load them as necessary
If resizing is a one time operation, perhaps saved the resized images to disk so that you won't have to resize them after the first time.
BufferedImage offers getSubimage. You could have one big image with all 100-200 tiles. Load this one big image once, and then show only the relevant part of the image using getSubimage. This is a concept known as Sprites and you can find a clearer example here.


Extracting tuples from Excel sheet My code have too much nested option processing which makes it ugly. But it has an advantage it has no side effect and typesafe.

package repos

import java.io.{InputStream, File}
import org.apache.poi.hssf.usermodel.HSSFWorkbook
import org.apache.poi.ss.usermodel.{Cell, Row, Workbook, Sheet}
import org.apache.poi.xssf.usermodel._
import scala.collection.JavaConversions._

object ExcelRepo{

  def read(binary: InputStream, filename: String) = {
    val excelExtension = "([^\\s]+(\\.(?i)(xls|xlsx))$)"
    val excelData = if(filename.matches(excelExtension)) {

      val xlsExtension = "([^\\s]+(\\.(?i)(xls))$)"
      val xlsxExtension = "([^\\s]+(\\.(?i)(xlsx))$)"

      val workbook:Option[Workbook] = if (filename.matches(xlsExtension)) {
        println("XLS")
        Some(new HSSFWorkbook(binary))
      } else {
        println("XLSX")
        Some(new XSSFWorkbook(binary))
      }

      val data = workbook match {
        case Some(wb: Workbook) =>
          val sheet = Option(wb.getSheetAt(0))
          sheet match {
            case Some(s: Sheet) =>
              val titleRow = Option(s.getRow(0))
              titleRow match {
                case Some(tr:Row) =>
                  val titleCell = Option(tr.getCell(0))
                  val priceCell = Option(tr.getCell(1))
                  (titleCell, priceCell) match {
                    case (Some(tc: Cell), Some(pc:Cell)) =>
                      if (pc.getStringCellValue == "price" && tc.getStringCellValue == "title") {
                        val list:List[(String, Double)] = sheet.get.tail.map{
                         r => (r.getCell(0).getStringCellValue, r.getCell(1).getNumericCellValue)}.toList
                        list
                      } else {
                        List()
                      }
                    case (_,_) => List()
                  }
                case None => List()
              }
            case None => List()
          }
        case None => List()
      }
      data
    } else {
      List()
    }
    excelData
  }

}

This function reads Excel file assuming that it is not null, and returning the List of tuples with (price, title), or empty list if workbook or row or cell is empty.

Is it actually ugly? Should I refactor it? If I should what is the clear and concise way to deal with match Option → getting new Option → match it again → getting new Option ...

You are doing the same thing in case of failure at any stage - returning an empty list.  You should use a for comprehension to chain these stages; if any one stage returns None, then the other stages will not be followed.  If you do something like this:

  for {
    wb <- workbook;
    sheet <- Option(wb.getSheetAt(0));
    titleRow <- Option(sheet.getRow(0));
    titleCell <- Option(titleRow.getCell(0)) if titleCell.getStringCellValue == "title";
    priceCell <- Option(titleRow.getCell(1)) if priceCell.getStringCellValue == "price";
  } yield { sheet.get.tail.map{r => (r.getCell(0).getStringCellValue, r.getCell(1).getNumericCellValue)}.toList
  }

This will return Option[List[(String, Double)]], containing either a real list or None.  If any of those stages returns None, the following stages will not be executed and you just get your None back early.  You can pattern match against this output to return the contents of Some(list) or List() if the output is None.

Note: I took the annotated val list out of there, so you would either need to have specified the return type for a val to which you assign the output of the for comprehension or put it back into the yield block.

Note how I turned your if...else expression into guards.  Can you see just how much simpler the code is and how each conditional is paired with the appropriate object? Particularly since the else was just returning another empty list.  This way, it fails and returns None.

"for comprehensions" can be overused in Scala, but this really is where they shine.  You correctly chose Option, but possibly the best thing about Option for any Java coder is the way it can remove boilerplate and defensive coding.  Your code still has the defensive coding, while the for comprehension just throws all that away. Learn to be free ;)


Converting a c# enum into a list to be sent to the client I want to use the enum on the client for a dropdown list.  Does this make sense, or is there a smarter way of doing this?

public class clientEnum
{
    public string Value { get;set;}
    public int Key { get; set; }
}

public static List<clientEnum> EnumToclientEnum <T>(T enumType) where T : Type
{
    List<clientEnum> list = new List<clientEnum>();

    foreach (var value in Enum.GetValues(enumType))
    {
        var name = value.ToString();
        var number = (byte)Enum.Parse(enumType, name);
        list.Add(new clientEnum { Key = (int)number, Value = value.ToString() });
    }
    return list;
}

Yes, use linq extensions:

public static List<clientEnum> EnumToclientEnum<T>()
{
    var type = typeof(T);
    if (!type.IsEnum) throw new NotSupportedException();
    return Enum.GetValues(type).Select(x => new clientEnum { Key = (int)x, Value = x.ToString() }).ToList();
}

In your original code (as well as in Abbas's answer) enum value is being converted to string and then this string  is parsed back to get the value. That makes no sense.