Swift solution to Leetcode “Longest Substring Without Repeating Characters” From LeetCode medium 3. Longest Substring Without Repeating Characters:

  Given a string, find the length of the longest substring without repeating characters.

  Examples:

  Given "abcabcbb", the answer is "abc", which the length is 3.

  Given "bbbbb", the answer is "b", with the length of 1.

  Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Here is my solution, but the online judge told me "Time Limit Exceeded". Is there a better solution to this problem?

private extension String
{
    subscript (index:Int) -> Character
    {
        return (self[self.startIndex.advancedBy(index)])
    }
}

class Solution
{
    func lengthOfLongestSubstring(s: String) -> Int
    {
        var str:String = ""
        var longest:Int = Int.min

        if s.isEmpty
        {
            return 0
        }

        for i in 0...s.characters.count-1
        {
            if !str.characters.contains(s[i])
            {
                str += String(s[i])
            }

            else
            {
                longest = max(longest, str.characters.count)
                str = ""

            }
        }

        return longest
    }
}

The Swift standard library does not have a built-in method to access the
n'th character of a string. It is tempting to fill that gap with a custom
extension like you did, but the problem is that

self[self.startIndex.advancedBy(index)]

is a \$ O(index) \$  operation. In contrast to other languages where a
"character" is a fixed-size object (and accessing the n'th character of
a string a  \$ O(1) \$  operation), a Swift Character represents a
"Unicode grapheme cluster" which consists of one or more Unicode scalar
values, see e.g. Strings in Swift 2 in the Swift blog.

That makes

for i in 0...s.characters.count-1 {
    // access `s[i]` with your custom subscript method
}

a O(n^2) operation where n is the number of characters in the string.
It is much more efficient to iterate over the characters with

for c in s.characters {
    // do something with `c`
}

More remarks:

The explicit type annotations in

var str:String = ""
var longest:Int = Int.min

are not necessary, the compiler can infer the type automatically.
If you start with var longest = 0 then the special case

if s.isEmpty
{
    return 0
}

becomes obsolete.
There are actually two errors in your code. If a repeating
character is found then the new substring candidate consists of
that character, i.e.

 longest = max(longest, str.characters.count)
 str = ""

should be

 longest = max(longest, str.characters.count)
 str = String(s[i])

otherwise lengthOfLongestSubstring("aabcdd") returns 3 instead
of 4.

And the longest substring length must also be updated at the end
of the string:

longest = max(longest, str.characters.count)
return longest

otherwise lengthOfLongestSubstring("aabcd") returns 1 instead
of 4.

Putting all that together, the method becomes

func lengthOfLongestSubstring(s: String) -> Int {
    var str = ""
    var longest = 0

    for c in s.characters {
        if !str.characters.contains(c) {
            str.append(c)
        } else {
            longest = max(longest, str.characters.count)
            str = String(c)
        }
    }
    longest = max(longest, str.characters.count)
    return longest
}

which should be faster than your code.

Another possible improvement is to store the characters of the
current substring in an Array or a Set instead of a String.
Which one is faster depends on the size of the strings, here is
an example with an array:

func lengthOfLongestSubstring(s: String) -> Int {
    var substringChars: [Character] = []
    var longest = 0

    for c in s.characters {
        if !substringChars.contains(c) {
            substringChars.append(c)
        } else {
            longest = max(longest, substringChars.count)
            substringChars = [c]
        }
    }
    longest = max(longest, substringChars.count)
    return longest
}

As of Swift 4, a Swift string is a collection of its characters
again, so  for c in s.characters can be simplified to for c in s.


Group lines from the CSV file I have a CSV file which looks like this:

ID | Name | Date
"1","Foo1","2013-08-03 21:00:08"
"1","Foo2","2013-08-03 21:00:08"
"2","Foo3","2013-08-03 21:00:08"
...

I need to write a method which returns a list of the lines with same ID and date, for reading the CSV file I am using OpenCSV. My question is whether or not this method can be rewritten in more elegant way.

private String[] currentWorkerLine;
private String relationIdentifier;
private String currentStartDate;
private int rowCount;

private List<String[]> getWorkers(CSVReader reader) throws Exception{
    List<String[]> workers = new ArrayList<>();
    if (currentWorkerLine == null && rowCount == 0){
        currentWorkerLine = reader.readNext();
        relationIdentifier = currentWorkerLine[0];
        currentStartDate = currentWorkerLine[2];
        workers.add(currentWorkerLine);
        rowCount++;
    }

    while ((currentWorkerline = reader.readNext()) != null) {
        if (!isRelatedLine(currentWorkerline[0]) || !isCurrentDateLine(currentWorkerline[2])){
            lastLine = currentWorkerline;
            return workers;
        }
        relationIdentifier = currentWorkerline[0];
        currentStartDate = currentWorkerline[2];
        workers.add(currentWorkerline);
        lastLine = currentWorkerline;
        rowCount++;
    }
    if (currentWorkerline == null && lastLine != null) {
        workers.add(lastLine);
        rowCount++;
        lastLine = null;
    }
    return workers;
}

private boolean isRelatedLine(String rel) {
    return rel.equals(relationIdentifier);
}

private boolean isCurrentDateLine(String date) {
    return date.equals(currentStartDate);
}

Class variables

Considering that neither the method nor the list of variables (plus what seems to be a missing private String[] lastLine) are static, I presume these belong to a class which requires instantiation for it to work.

This approach is fine - without knowing what else the class is doing - but I'm not too sure if currentWorkerLine (you have a currentWorkerline too, I'm going to assume that's just a small typo) and lastLine really needs to be 'saved' as class variables. For example, at the end of the method, is there a need to set lastLine = null?

Throwing Exceptions

The only checked Exception I can see from the method is just reader.readNext(), so you may want to replace the throws Exception part with the stricter throws IOException. This forces the method callers to explicitly deal with an I/O-related error, instead of an unusually wide Exception, which offers no (direct) hint as to what has gone wrong.

BTW, on a related note, if the code happens to deal with a malformed CSV input, the line currentWorkerLine = reader.readNext(); will cause NullPointerException should reader.readNext() return null. You may want to check for this, just to be sure.

Comparisons

While your code block is looping through the lines that have passed the identity check, there is no need to keep re-assigning relationIdentifier and currentStartDate:

while ((currentWorkerline = reader.readNext()) != null) {
    if (!isRelatedLine(currentWorkerline[0]) || !isCurrentDateLine(currentWorkerline[2])){
        lastLine = currentWorkerline;
        return workers;
    }
    // they will be the same as the past values, so why re-assign?
    //relationIdentifier = currentWorkerline[0];
    //currentStartDate = currentWorkerline[2];
    workers.add(currentWorkerline);
    lastLine = currentWorkerline;
    rowCount++;
}

Model classes

You may also want to consider having a suitable model class to give a better representation to the three-column row inputs you get over the current String[]. With a model class, you can have a custom equals() implementation that only compares the ID and date values between two 'instances' aka rows, so that the next different row will return false for the comparison. This may simplify not only your approach within the method here, but outside usage as well for the method callers to deal with the List of results.

Also, food for thought, would it be better/more efficient to return one Result object that contains an id, startDate and a List<String> of names, since the id and startDate are the same for all the names?


Extract HTML tags and its content from a string Goal

I want to extract HTML tags and its content from a string. The content (input) is queried from WordPress database.

Sample data (input)

I extract this dummy data from my WordPress database: https://www.phpliveregex.com/p/tan
I believe this should cover all the needed tags to parse.

Expectation (output)

Accepting a HTML-format string as input.
The output should be able to return a string which could be any of these:

The HTML element string itself
Attributes string of the HTML element
Text nodes, child nodes string of the HTML element

My concern

Which solutions take less execution time?
Which solutions save more server memory?
Security vulnerable of each solutions.

Solutions

I've come up with a 2 solutions by myself. It works fine, but I don't know which one is good for my case.

Regex pattern

$el = 'li'; // Ex
$match = []; // Reserving for results

/**
 * Regex - extract HTML tag and its content
 * Array map:
 * x[0] = everything
 * x[1] = open tag
 * x[2] = attributes
 * x[3] = content & end tag
 * x[4] = content only
 *
 * Note for content: including text node + children node
 */
$reg = '/(<'.$el.'(.*?)>)((\n*?.*?\n*?)<\/'.$el.'>|)/';

if (preg_match($reg, $html_str, $match)) { echo 'Moving onward!';}

Result: see demo of regex

DOM object

$dom = new DomDocument();
$content = mb_convert_encoding(
    get_the_content(null, true), # WordPress func, it gives input str
    'HTML-ENTITIES',
    'UTF-8'
);
$dom->loadHTML($content);

$el = $doc->getElementsByTagName('li');

Result: returning a DOMNodeList and I have to do few more tasks to print it to a string which can be used.

Using regex to parse valid html will work (and you might call it beautiful) until it doesn't work... then you'll bend over backwards (over and over) each time you encounter an anomaly then try to write a patch for the pattern.

Allow me to notify you of a simple, valid html occurrence that will break your sample pattern:

Demo

<link rel="stylesheet" href="/html_5/tags/html_link_tag_example.css">

It would match because your li needle is not immediately followed by a word boundary character (\b). Is this a simple thing to fix? Yes, but my point remains -- regex is an inappropriate tool for parsing valid html.

I generally rely on DomDocument for most cases and when XPath makes life simpler, I use that to perform clean, readable queries on the document.

This is one time when focussing on speed is a moot point -- speed is the least of your worries.  What good is speed if the results are bogus? The goal should be to design a robust and reliable script using DOM-aware techniques.


Locking a remote file I am using Java to modify remote files in different machines by ssh. At the same time, only one thread is allowed to modify the file in one machine.

I implement the logic like this:

public boolean executeCmd(String ip, String command, String file) throws Exception
{

    final String file = ip + " " + file;
    final String fileLock = file.intern();

    synchronized (fileLock)
    {
        logger.debug(Thread.currentThread().getName() + " " + fileLock + " get the lock");

        SSHClient sshClient = new SSHClient();

        // code to ssh to modify the file.

        logger.debug(Thread.currentThread().getName() + " " + fileLock + " release the lock");
    }
}

Then this function is called in tasks for multi-threads. Is this method satisfied for the purpose?  I tested it for some simple cases and it seems to work OK.

At first, I lock the file using shell like this:

lockdir="$1.lock"
while ! mkdir "$lockdir" >/dev/null 2>&1
do
    echo "another process is running, wait..."
    sleep 10
done

trap 'rm -rf "$lockdir"' 0

There is a problem about this way. If the shell exits unexpectedly, the $lockdir will not be deleted, and it becomes a "deadlock".

I can't solve the problem so I lock the file using Java to ensure only one thread is modifying the same file.

In the absence of different strings because of symlinks, hardlinks, multiple IPs for the same machine and hostnames instead of raw IPs, then yes, the synchronized combined with intern is thread-safe; no idea about performance, which is probably not an issue anyway.

If you only run all of this from a single program then it's probably okay in general, otherwise you should look into locking on the remote machines, i.e. constructing your command so that it locks on a .file.lock file or so.


Hackerrank Insertion Sort Algorithm 1 (creating duplicates to show shifting) During an interview, I was given this Hackerrank question to solve within 15 minutes but at that time I was interested in solving this without performance in my mind. I know a similar question has been asked Hackerrank Insertion Sort - Java and probably a lot in CR.
Problem Statement

Given a sorted list with an unsorted number e  in the rightmost cell, can you write some simple code to insert  into the array so that it remains sorted?
Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.
Guideline: You can copy the value of  to a variable and consider its cell "empty". Since this leaves an extra cell empty on the right, you can shift everything over until  can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with .

Input Format
There will be two lines of input:

Size - the size of the array
Arr -  the unsorted array of integers

Output Format
On each line, output the entire array every time an item is shifted in it.
Constraints

1 ≤ Size ≤ 1000
-10000 ≤ e ≤ 1000, e E Arr

Sample Input
5
2 4 6 8 3

Sample Output
2 4 6 8 8
2 4 6 6 8
2 4 4 6 8
2 3 4 6 8

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    public static void printArray(int[] array)
    {
        var b = array.Select((x) => Convert.ToString(x) + " ").Cast<string>();
        Console.WriteLine(String.Concat(b));
    }

    public static void insertionSort(int[] unsortedArray)
    {
        int unsortedElement = unsortedArray.ElementAt(unsortedArray.Count() - 1);
        int i = unsortedArray.Length - 1;
        while (i != -1)
        {
            if (i - 1 != -1)
            {
                if (unsortedArray[i - 1] > unsortedElement)
                {
                    unsortedArray[i] = unsortedArray[i - 1];
                    printArray(unsortedArray);
                }
                else
                {
                    unsortedArray[i] = unsortedElement;
                    printArray(unsortedArray);
                    break;
                }
            }
            else
            {
                unsortedArray[i] = unsortedElement;
                printArray(unsortedArray);
                break;
            }
            i--;
        }
    }
}

Any thoughts on performance, style or shortened code length?

A few points specifically for C#.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    // Method name should be in Pascal case.
    public static void PrintArray(int[] array)
    {
        // If it is known that x is an int, x.ToString() is more readable.
        // Also, rather than calling it 'b', you could give a more readable name.
        var strArray = array.Select((x) => x.ToString() + " ").Cast<string>();
        Console.WriteLine(String.Concat(strArray));
    }

    public static void InsertionSort(int[] unsortedArray)
    {
        // Why use Count() and Length in two lines?
        // You could choose the one you prefer and use it everywhere.
        // Also, if you are using var in PrintArray, you should be consistent in its use.
        var unsortedElement = unsortedArray[unsortedArray.Length];
        var i = unsortedArray.Length - 1;
        // I would prefer to keep it i >= 0, as it defines a valid range, rather than a single point.
        // There is no real difference, but it is more resilient against mistakes like having i-- statements twice.
        while (i >= 0)
        {
            // As pointed by others, i != 0 would be more readable.
            if (i > 0)
            {
                // Shift the element to right if it is bigger than unsorted element.
                if (unsortedArray[i - 1] > unsortedElement)
                {
                    unsortedArray[i] = unsortedArray[i - 1];
                    PrintArray(unsortedArray);
                }
                // Insert the element if the element at i - 1 is smaller or EQUAL to it.
                else
                {
                    unsortedArray[i] = unsortedElement;
                    PrintArray(unsortedArray);

                    break;
                }
            }
            // I prefer to keep a comment with else statements.
            // When i = 0, i.e. for the first element.
            else
            {
                unsortedArray[i] = unsortedElement;
                PrintArray(unsortedArray);

                break;
            }

            i--;
        }
    }
}


Spectrum Analysis with Discrete Fourier Transform Here is a simple implementation of the Discrete Fourier Transform:

myFourierTransform.m

function [ft] = myFourierTransform (X, n)
% Objective:
%   Apply the Discrete Fourier Transform on X.
% Input:
%   X - 1xM - complex vector - data points (signal discretisation).
%   n - 1x1 - integer scalar - number of discrete frequencies (spectrum discretisation).
% Output:
%   ft - 1xn - complex vector - "quantity of" i-th frequency in X.
% Complexity: O(n * M).
% Author:
% Date:

  ft = zeros(1, n);
  freq = @(point_index, freq_index, total_freqs)...
  exp( -2 .* pi .* j  .*(point_index - 1) .* (freq_index - 1) / total_freqs );

  for i = 1 : n

    f_i = freq(1: numel(X), i, n);

    ft(i) = dot(X, f_i);

  end

end

Here is a script file applying the above and comparing it to the built-in function fft(X, n):

applyMyFourierTransform.m

clc; clear; close all;

% Signal parameters
A = 1;                                 % signal amplitude.
f = 10;                                % frequency of the signal 10 Hz.
theta = 0.25 * pi;                     % initial phase of the signal.
measurement_rate = f * 30;             % Nyquist-Shannon Th.-rate of measurement >=2*f.

nPeriods = 7;                          % number of periods to be displayed.
tBeg = 0;
tEnd = nPeriods * 1 / f;
tStep = 1 / measurement_rate ;

t = tBeg : tStep : tEnd;
x = A * sin(2 * pi * f * t + theta);   % sine wave A= 1 V,f= 10 Hz, phi_0= pi/4 rad.
P = A^2 / 2;                           % signal power=\frac{1}{T}\int_0^T {x{^2}(t)dt}.
point_num = numel(x);

% Plot the test signal.
subplot(3, 1, 1)
plot(t, x);
xlabel('Time [sec]');
ylabel('Amplitude');
title('Test Signal.');
legend( sprintf( 'f = %.2f [Hz] \n A = %.2f [V]', f, A ) );

% Apply FFT and obtain spectrum of test signal.
freq_num = 2^10;                       % Discretise the spectrum in 1024 frequencies.
bfft = fft(x, freq_num);               % built-in Discrete Fourier Transform.

bfft = fftshift(bfft);                 % shift f(0) at the middle of the vector.

% Calculate signal power \frac{X_k * X_k^{*}}{Frequency_Discretisation * Data_size}.
power = bfft .* conj(bfft) / (freq_num * point_num);

% Frequency axis starts at: -f/2 ends at: f/2 and includes: n frequencies.
frequencies = measurement_rate * (-freq_num / 2 : freq_num/ 2 -1) / freq_num;

subplot(3, 1, 2)
plot(frequencies, power);
xlabel('Frequency [Hz]');
axis([-10*f 10*f])
set(gca, 'XTick', [-10*f : f : 10*f]);
ylabel('Power [Watt]');
title('Power Spectral Density.')
legend( sprintf( 'f = %.2f [Hz]\n P = %.2f [W].', f ,P ) )

% Apply custom implementation of Discrete Fourier Transform.
cdft = myFourierTransform(x, freq_num);
cdft = fftshift(cdft);
cpower = cdft .* conj(cdft) / (freq_num * point_num);

subplot(3, 1, 3)
plot(frequencies, cpower);
xlabel('Frequency [Hz]');
axis([-10*f 10*f])
set(gca, 'XTick', [-10*f : f : 10*f]);
ylabel('Power [Watt]');
title('Power Spectral Density.')
legend( sprintf( 'f = %.2f [Hz]\n P = %.2f [W].', f, P ) )

error = abs( sum(cdft) - sum(bfft) )

Command Line:

>> applyMyFourierTransform

Result:

>> error =   1.7346e-011

Questions

How can I estimate the validity of the values produced by the custom implementation? Is this a reasonable estimate?

error = abs( sum(cdft) - sum(bfft) )

A few things:

When you have the start, endpoint and the number of steps you want in a vector then linspace is better than colon:

t = linspace(tBeg, tEnd, measurement_rate);

It's cleaner, since you don't have to calculate the length of each step.

exp( -2 .* pi .* j  .*(point_index - 1) .* (freq_index - 1) / total_freqs );

j looks like a variable, especially since you use i as a variable later on. The recommended way to denote the imaginary unit is 1i or 1j. That way it can't be confused with a variable, and you don't risk overwriting it.

You don't need .* when multiplying by scalars. It's only needed between matrices or vectors. If you only use it between matrices then it's easy to see which variables are vectors/matrices, and which are just scalars. It's now hard to tell if point_index, freq_index and/or total_freqs are scalars or matrices.

There's only one vector in that statement (point_index), so no dots are needed.

The for loop can be vectorized, which is the MATLAB way to do something like that. I don't have MATLAB at hand, so I can't do it for you, unfortunately. If you have a version newer than R2015B, then you can do implicit matrix expansion by adding two vectors of different orientation:

[1; 2; 3] + [4, 5, 6] = [5, 6, 7;6, 7, 8;7, 8, 9]

You can do this with point_index and freq_index, then do matrix multiplication to get the final ft.

Don't use error as a variable name. It's a useful function that you can use to, well, throw errors.

You don't need a space after \n in a string, unless you actually want a space in front of the first letter in the next line:

f = %.2f [Hz] \nA = %.2f [V]'

Your variable names are very good
Your coding style is good
I don't like clear and close all in the beginning of the script, but that's up to you.


Speed performance of sqlite3 queries looped in python I have a table data stored in a database ships.db,
the data are informations of tracked ships hourly.
The table data looks like this.
time  |  shipId  |   longitude  |  latitude
---------------------------------------------------------------------
00:00:00          1              xx.xxxx       yy.yyyy
00:00:00          2              xx.xxxx       yy.yyyy
00:00:00          3              xx.xxxx       yy.yyyy
00:00:00          4              xx.xxxx       yy.yyyy
01:00:00          2              xx.xxxx       yy.yyyy
01:00:00          4              xx.xxxx       yy.yyyy
     ...                 ...                 ...                ...
23:00:00          4              xx.xxxx       yy.yyyy

Splitting the whole earth to a grid of 5-degree width and length for each cell,
I would get the number of fetched records hourly per cell of that grid.
Note that the number of records are not the same each hour because some ships are not more live therefore not fetched.
I wrote this code in python, it works but it takes large time because the database has roughly 250000 records.
Is there another method or approach to make it better and faster in python?
My script:
import sqlite3

def writeToFile(string, file):
    with open(file,"a") as ouf:
        ouf.write(string+"\n")

output = "report.txt"

with sqlite3.connect("ships.db") as con:
    cur = con.cursor()
    #iterate over times from 0 to 23 (hours)
    for hour in range(0,24):  # hours: from 0 to 23
        #make each loop of time in this time format "hh:00:00"
        time = str(hour).zfill(2)+":00:00"
        #scan from longitude -180 (180 W) to +180 (180 E) each 5 degree of longitude
        for longitude in range(-180,180,5):
                #scan from latitude -90 (90 S) to +90 (90 N) each 5 degree of latitude
                for latitude in range(-90,90,5):
                    sql = f'''SELECT time, count(*) AS occurence FROM 'data'
                    WHERE time ="{time}"
                    AND latitude BETWEEN {latitude} AND {latitude+5}
                    AND longitude BETWEEN {longitude} AND {longitude+5}
                    GROUP BY time'''
                    data = cur.execute(sql).fetchone() #fetchone because group by time
                    if data != None:
                        time, occurence = data
                    else: #some cell of grid may have no ship at a hour therefore this else
                        occurence = None
                    result = [time, occurence, longitude, latitude]

                    #writing the result to output
                    writeToFile("\t".join(result), output)

There are multiple things that I would like to point out to you, just to help you improve coding style. Currently you are not noticing as performance issues as they are hidden due to you DB performance.

Fixed values: You are computing fixed list every time through 'range'. Try to store them in list. As this is unnecessary compute overhead.

File writing: You are opening and closing file per record. This can cause huge disk performance issues once you start noticing. Try to collect record in list and maybe write to file once every 'hour'.

Always try to add 'Indexes' on DB. They are made for purpose of speeding up searching.


Exercise - count binary-tree nodes with 1 leaf and 1 internal node as children I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there.

The exercise

  Write a program that counts the amount of nodes in a binary tree, that
  have an external and an internal node as children.

In the following picture, the ones with the red dot are the ones I think I have to count.

For simplification in the further text I dubbed these nodes "wanted nodes" and the method that determines if a node is a "wanted node" thus isWantedNode(). The solution to this is fairly straightforward if done recursively, but I can't find the most elegant one.

Requests

How can the recursion be simplified to avoid invoking methods unnecessarily in the first place?

I currently want to focus on doing this recursively before I jump into changing this into an iterative solution, for learning purposes on my part.

I'm certain that the recursion can be simplified, I just don't see how. The key here is to check for child-nodes being leafs or internal nodes while avoiding NullPointerExceptions when you're checking if a node is a "wanted node". My current approach is dealing with the NullPointerExceptions instead of avoiding invoking methods for null objects in the first place which I don't think is the best way to go about this.

The Code

static class TreeNode {
        TreeNode left;
        TreeNode right;

        TreeNode(TreeNode l, TreeNode r) {
            this.left = l;
            this.right = r;
        }
    }

/* Count wanted nodes */
private static int strangeCount(TreeNode h) {
    if (h == null) {
        return 0;
    }
    int result = strangeCount(h.left) + strangeCount(h.right);
    return (isWantedNode(h)) ? result + 1 : result;
}

/* Check if n is wanted node */
private static boolean isWantedNode(TreeNode n) {
    return (isLeaf(n.left) && isInternal(n.right) || (isInternal(n.left) && isLeaf(n.right)));
}

/* Check if n is leaf */
private static boolean isLeaf(TreeNode n) {
    return (n == null) ? false : (n.left == null && n.right == null);
}

/* Check if n is internal node */
private static boolean isInternal(TreeNode n) {
    return (n == null) ? false : (n.left != null || n.right != null);
}

Your comments arn't really helpful, and so I'd remove them. This is as the function names say all that you would want to know.
Using the inverse of 'split the line, change the sign', more commonly know as DeMorgan's laws, you can change isInternal to be much simpler. Rather than using \$\overline{A} \lor \overline{B}\$ your can use \$\overline{A \land B}\$.
Since isInternal is the inverse of isLeaf you can just check that isLeaf(n.left) is not the same as isLeaf(n.right), as if it's not then there is one leaf and one internal.

And so you can change isWantedNode and isLeaf to:

private static boolean isWantedNode(TreeNode n) {
    if (n.left == null || n.right == null)
        return false;
    return isLeaf(n.left) != isLeaf(n.right);
}

private static boolean isLeaf(TreeNode n) {
    return n.left == null && n.right == null;
}

You may also want to change your return statment in strangeCount from a turnery, to addition of result and a turnery.
And so I'd use:

private static int strangeCount(TreeNode h) {
    if (h == null) {
        return 0;
    }
    return strangeCount(h.left) + strangeCount(h.right) + (isWantedNode(h)?1:0);
}


DRY attack and defense I have these two methods on a class that differ only in one method call. Obviously, this is very un-DRY, especially as both use the same formula. Could anyone give me advice on how to tidy this up?

public class PlayerCharacter {
    int level;
    public int getAttack() {
        int attack = 1 + level;
        for(Equipment e : equipments)
           attack += e.getAttack();
        return attack * Math.sqrt(level);
    }
    public int getDefense() {
        int attack = 1 + level;
        for(Equipment e : equipments)
           attack += e.getDefense();
        return attack * Math.sqrt(level);
    }
}

I thought of refactoring the loop to an external method but the different method calls has me stumped.

A few things, bad messages first…

Double and Int

return Math.sqrt(level);

Math.sqrt returns a double. That is a floating point number, probably something like: \$2.352561\$. If you now "cast" that to an int (because your method says, "I only return integers"), you just cut everything behind the dot.

This can sometimes lead to funny behavior:

  \$2.7371 \mapsto 2\$
  \$2.0125 \mapsto 2\$

That's not nice…

Braces:

It's usually a very good idea to place braces, even when you could leave them out:

for (Equipment e : equipments) {
    attack += e.getAttack();
}

This is because if you want to do something else, too you need to add braces either way, and If you forget it, the results become "unpredictable"

Copy/Paste:

You should never do that, because as soon as you do, you usually can extract a method for it. But if you do it either way then at least take the bother to change the names…

public int getDefense() {
     int attack = 1 + level;

'nuff said on the bad stuff ;)

Attributes

You might want to consider changing your attribute structure to be more "generic". Consider the following code:

for (Equipment e : equipments) {
    defense += e.getAttribute(Attribute.DEFENSE);
}

or similarly for attack:

for (Equipment e : equipments) {
    attack += e.getAttribute(Attribute.ATTACK);
}

now we already can see, that if you do that twice, this wants to be a single method:

public int getPlayerAttribute(Attribute attribute) {
    int attribute = 1 + level;
    for (Equipment e : equipments) {
        attribute += e.getAttribute(attribute);
    }
    return attribute * Math.sqrt(level);
}

This would of course need a relatively large change in your code. You'd then need to change your Equipment from (wild conjecture):

public class Equipment {
    private int attack;
    private int defense;
    //getters and setters
}

to:

public class Equipment {
    private Map<Attribute, Integer> stats = new HashMap<>();
    // or a different Map implementation of your choice, like
    // EnumMap, as suggested by @ratchet freak in a comment:
    private Map<Attribute, Integer> stats = new EnumMap<>(Attribute.class);

    public int getAttribute(Attribute attribute) {
        return stats.get(attribute);
    }
}

And create a new enum to hold all the different kinds of attributes you have:

public enum Attribute {
    ATTACK, DEFENSE, HITPOINTS, WHATEVER
}


Find one duplicate in container with N+1 integers between 1 and N Time complexity is supposed to be \$O(n \cdot \log(n))\$ and space complexity is supposed to be \$O(1)\$. Neither the elements of the container nor the container should be modified.

// Copyright [2015] <none>
#include <cstdlib>
#include <cstddef>
#include <cassert>
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <random>
#include <algorithm>
#include <limits>

// #define NODEBUG

/**
 * Finds one duplicate number in container where the largest number in the
 * container is smaller than the size of the container.
 */
template <class It>
It FindOneDuplicate(It first, It last) {
  int n = static_cast<int>(std::distance(first, last) - 1);
  int range_start = 1;
  int range_end = n / 2;
  while (true) {
  next_range:
    int range_size = range_end - range_start + 1;
    int count = 0;
    for (auto current{first}; current != last; ++current) {
      int element = *current;
      if (element >= range_start && element <= range_end) {
        ++count;
        if (count > range_size) {
          n = range_end;
          range_end = (n + range_start) / 2;
          if (range_size == 1) {
            return current;
          }
          // break and continue
          goto next_range;
        }
      }
    }
    // This should never happen
    assert(range_end != n);

    range_start = range_end + 1;
    range_end = n;
  }
}

// This is just a test run
int main(int argc, char* argv[]) {
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <N>" << std::endl;
    return EXIT_FAILURE;
  }
  int n =
      static_cast<int>(std::strtol(argv[1], static_cast<char**>(nullptr), 10));
  assert(n > 0 && n < std::numeric_limits<int>::max());
  std::random_device rd;
  std::mt19937 generator(rd());
  std::uniform_int_distribution<> dist(1, n);
  std::size_t size{static_cast<std::size_t>(n + 1)};
  std::vector<int> elements(size);
  // Fill and increment except last
  std::iota(elements.begin(), elements.end() - 1, 1);
  // Fill last with random value [1..N]
  elements.back() = dist(generator);
  // Shuffle elements
  std::shuffle(elements.begin(), elements.end(), generator);
  auto duplicate = FindOneDuplicate(elements.begin(), elements.end());
  for (const auto& element : elements) {
    bool isduplicate = element == *duplicate;
    if (isduplicate) {
      // bold;red
      std::cout << "\033[1;31m";
    }
    std::cout << element;
    if (isduplicate) {
      // reset
      std::cout << "\033[0m";
    }
    if (&element != &elements.back()) {
      std::cout << ", ";
    }
  }
  std::cout << std::endl;
  return EXIT_SUCCESS;
}

Since this is my first real piece of C++ code I'd love to get some code review before I start working on any open source projects.

Note that I'm trying to follow the Google C++ style guide here.

Never use goto

There are times where you have a compelling reason to use goto. This really isn't one of them. Either make your function recursive, since it is in all but name. Or rewrite it to be iterative. Both of those would be preferred solutions. The reason I say this is because your logic is sort of logic a binary search, except the two different changes in range occur in different places and use different mechanisms. This makes it difficult to understand and, I imagine, debug.

A Better Algorithm

Add a helper function that will count the number of elements in your given range, breaking out early if you hit the amount you're going for:

template <typename It, typename V>
It find_if_extra(It first, It last, V start, V end)
{
    V count = 0;
    for (; first != last; ++first) {
        if (*first >= start && *first <= end) {
            ++count;
            if (count > end - start + 1) {
                return first;
            }
        }
    }

    return last;
}

This is basically the same thing you were doing in your loop, except substituting the return/goto pair for two returns. Now, we can just rewrite your original function to use this helper and the goto goes away:

template <class It>
It FindOneDuplicate(It first, It last) {
    using value_type =
        typename std::iterator_traits<It>::value_type;

    value_type N = std::distance(first, last) - 1;
    value_type start = 1;
    value_type end = N/2;

    for (;;) {
        auto it = find_if_extra(first, last, start, end);

        if (it != last) {
            // recurse lower unless we're done
            if (start == end) {
                return it;
            }

            N = end;
            end = (N + start) / 2;
        }
        else {
            // recurse higher
            start = end + 1;
            end = N;
        }
    }
}

Assumptions on types

There's no reason to cast n to be an int. size_t is fine:

size_t n = std::distance(first, last) - 1;

Similarly, I would initialize element with auto. You take arbitrary iterators, what if we had a huge container of size_t? You'd overflow.

Also, avoid this construction:

auto current{first};

in favor of

auto current = first;

The former may change meaning in the future, and there's no reason to prefer it anyway.

Testing

Your test just outputs something to the screen. Ideally, you would write test that actually verify the behavior of your program.


Fibonacci sequence in C I'm very new to C, so pointing out better ways of doing things, errors, bad practices, etc would be optimal at this stage.

Code on GitHub

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

int *calculateFibonacciSequence(int n, int start)
{
  int i;

  // Allocate memory for our fibonacci sequence from the heap
  int *numbers = malloc(sizeof(int) * n);

  // Need to calculate at least one number
  if (n <= 0) {
    return 0;
  }

  // Can't start with a number under zero
  if (start != 0 && start != 1) {
    return 0;
  }

  // Get the seed values
  if (start == 0) {
      numbers[0] = 0;
      numbers[1] = 1;
  } else {
      numbers[0] = 1;
      numbers[1] = 1;
  }

  // Calculate the sequence
  for (i = 1; i < n; i++) {
    numbers[i + 1] = numbers[i] + numbers[i - 1];
  }

  return numbers;
}

int main(int argc, char *argv[])
{
  int i, n;
  int start = 0;
  int *sequence;

  // Check to see how many arguments we got
  if (argc <= 1) {
    puts("Please pass the number of iterations to run.");
    return 1;
  }

  // Get the number of iterations to run
  n = atoi(argv[1]);

  // Did they specify a start value
  if (argc > 2) {
    start = atoi(argv[2]);
  }

  // Calculate the sequence
  sequence = calculateFibonacciSequence(n, start);

  // Output the sequence
  if (sequence) {
    printf("%d", sequence[0]);

    for (i = 1; i <= n; i++) {
      printf(",%d", sequence[i]);
    }

    // Newline
    puts("");
  } else {
    puts("Error processing fibonacci sequence");
  }

  // Free memory
  free(sequence);

  return 0;
}

What you did well on:

Your program is easy to read.
You are allocating memory, even though it is unsafe in certain cases (other answers have addressed this, so I won't cover it).
You prepare for some corner cases.

Things you could improve:

You are returning 0 when your program runs into a problem (except
in one spot where there are too many parameters being entered).

return 0;

0 is typically the return code for a exiting successfully.  If we
run into a problem in our program, we should return something to
indicate we ran into a problem.  I prefer to return negative numbers.

return -1;

Also, you should return different numbers for different errors.  A user generated error such as malformed input should not return the same error code as an internal error.  This makes debugging a lot easier when you are trying to determine the cause of an error.

However, since you are returning an int*, it would be better to return NULL instead.  This is what you are doing right now, in a somewhat abnormal way by returning 0.  Just return NULL.

return NULL;

You should mark ints as unsigned if they are never going to be negative.

unsigned int start;

You are not maximizing how many Fibonacci you can produce using only an int, or even an unsigned int.  An unsigned int has a maximum value of 2147483647, where a long long unsigned int has a maximum value of 18446744073709551615.  That's 8589934562 times larger!
Declare i inside of your for loops.  This is part of the C99 standard, so you may have to adjust how you compile your program.

for (unsigned int i = 1; i <= n; i++)

I don't see the point of the start variable.  Unless this is part of some problem you are trying to solve, I would just print the whole sequence.  It would cut down on your lines of code a lot as well.
The Fibonacci series is a great place to practice recursion.

long long unsigned int fibonacci(long long unsigned int n)
{
   if (n < 2) return n;
   else return (fibonacci(n-1) + fibonacci(n-2));
}

This algorithm here is short, and gets the job done just has you did in less lines of code.  We could even shorten it a bit further if we wanted to (with ternary operators).

long long unsigned int fibonacci(long long unsigned int n)
{
    return (n < 2)? n : fibonacci(n-1) + fibonacci(n-2);
}

We have to be careful though to avoid repeating the calculation of results for previously processed inputs; to do this we should use memoization. I've implemented this in my final program.
Keep in mind that sometimes recursion will make your algorithm a bit
slower with time-complexity, which can be the case here (depending on your implementation of an iterative solution).  Here is the fastest iterative algorithm I could work up (this may still be a bit slower with the pow() function).

long long unsigned int fibonacci(long long unsigned int n)
{
    return (1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n));
}

However, using this method requires the use of doubles, and the return will make an implicit cast that could cause some rounding problems.  Therefore, we will round() the result in our final code.
You should test if you input is a number, and not some malformed input.

if (scanf("%i", &num) <= 0)
{
    puts("Invalid input.");
    return -1;
}

Final code:

Iterative: O(1)

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

long long unsigned int fibonacci(long long unsigned int n)
{
    return round((1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n)));
}

int main(void)
{
    unsigned int num = 0;

    printf("Enter how far to calculate the series: ");
    if (scanf("%i", &num) <= 0)
    {
        puts("Invalid input.");
        return -1;
    }

    for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
}

Recursion: O(n)

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

#define ARRAYLENGTH 100 // keep in mind the result must fit in an llu int (fibonacci values grow rapidly)
                        // you will run into issues after 93, so set the length at 100
long long int memoization[ARRAYLENGTH];

long long unsigned int fibonacci(long long unsigned int n)
{
    if (memoization[n] != -1) return memoization[n];

    return (n < 2)? n : (memoization[n] = fibonacci(n-1) + fibonacci(n-2));
}

int main(void)
{
    unsigned int num = 0;

    for(unsigned int i = 0; i < ARRAYLENGTH; i++) memoization[i] = -1; // preset array

    printf("Enter how far to calculate the series: ");
    if (scanf("%i", &num) <= 0)
    {
        puts("Invalid input.");
        return -1;
    }
    if (num < ARRAYLENGTH)
    {
        for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
    }
    else
    {
        puts("Input number is larger than the array length.");
        return -2;
    }
}


Clean up / refactor this store() method I'm new to Laravel and trying to figure out how I can reduce/refactor this store() call in my SessionController.

Basically, the SessionController is used to authenticate a user against an LDAP server (using wells/l4-ldap-ntlm instead of the default auth driver)

On LDAP auth success, it then checks if the user has an account/profile for this webapp. If they do not, it creates it. If they already have one, it just logs them in (user/profile only created on first login).

If LDAP auth fails, it redirects back to the login page.

I know this is a lengthy method for a controller, so I want to know the best practices for:

Refactoring this code out, so the controller is cleaner, and adhering to the "single responsibility" rule.
I need to use LDAP just for authentication, but I also want to store information for this webapp that is not stored in LDAP. Right now I am creating a User and a Profile model, but I don't know a good way to "link" them to the LDAP authenticated user once logged in.

public function store()
{
    // store credentials
    $input = Input::all();

    // attempt authentication
    $attempt = Auth::attempt([
        'username' => $input['user'],
        'password' => $input['pass']
    ]);

    if ($attempt) {
        // LDAP auth success
        $un   = Auth::user()->username;
        $role = Auth::user()->type;

        // check if user exists, creating a user and profile if they do not.
        try {
            $user = User::whereUsername($un)->firstOrFail();
        }
        catch (Illuminate\Database\Eloquent\ModelNotFoundException $e) {
            $user = User::create(['username'=>$un]);
            $user->roles()->attach( $role );
            $user->createProfile();
        }

        // redirect
        return Redirect::intended('/profile')
                        ->with('flash_message', 'welcome, ' . $un);
    }
    else {
        // LDAP auth failed.
        return Redirect::back()
                        ->with('flash_message', 'The credentials you entered were invalid. Please try again.')
                        ->withInput();
    }

}

Okay, let me get this right (I have no experience working with an LDAP): The Auth class you're first using for $attempt is actually the LDAP library you're implementing?

I don't think I understand the logic in your code. You attempt to log in to the user, and if they successfully login, you check to see if the user exists? I must be misunderstanding something.

Well, assuming you know how exactly this works, I'll just point out a couple refactor points I can see:

In terms of breaking this apart into responsibilities: your method handles both authentication and registration. I can imagine registration being handled in another method.
I doubt you need to flash forward this entire parameter: 'welcome, ' . $un. Have your Blade file check for the flash and display "welcome, ". Since you're only sending one, just pass through $un. Either that or make it an array and pass two values: type of flash, and message.
Speaking of $un. There are better variable names, give yours some meaning and quality to them.
You can manage to un-nest your code a little:

if ($attempt) {
    ...
} else {
    return Redirect...
}

This piece could really just be:

if (!$attempt) {
    return Redirect...
}

// *What used to be inside the if*


Rotate an array to the right by a given number of steps Recently, I encountered this coding exercise on codility and the idea is

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.

  Write a function:

 class Solution { public int[] CyclicRotation(int[] A, int K); }

  that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times.

  For example, given array A = [3, 8, 9, 7, 6] and K = 3

  the function should return [9, 7, 6, 3, 8].

Assume that:

  N and K are integers within the range [0..100];
      each element of array A is an integer within the range [−1,000..1,000].

My approach was if the array has zero or 1 element, the array given is returned else thne for loop is executed. I also added the new array to extract a subset of the array which was meant to be shifted and the first element of Array A is swapped with the last element. Finally, a new list is created with aim to achieve the insert the first element A[0] after being swapped.

public static int[] CyclicRotation(int[] A, int K)
    {
        //Rotate an array to the right by a given number of steps.
        // eg k= 1 A = [3, 8, 9, 7, 6] the result is [6, 3, 8, 9, 7]
        // eg k= 3 A = [3, 8, 9, 7, 6] the result is [9, 7, 6, 3, 8]

        if(A.Length== 0 || A.Length ==1)
        {
            return A;
        }
        int lastElement;
        int[] newArray = new int[A.Length];

        List<int> listOfNumbers = new List<int>();

        for (int i = 1; i < K+1; i++)
        {

            lastElement = A[A.Length - 1];
            newArray = A.Take(A.Length - 1).ToArray();
            listOfNumbers = newArray.ToList<int>();
            listOfNumbers.Insert(0, lastElement);

            A = listOfNumbers.ToArray();
            newArray = A;

        }
        return newArray;
    }

I believe there is room for improvements. Any suggestions would be appreciated.

In place solution

Jon Bentley "Programming Pearls" (1986) has this task as one of problems.

The recommended solution, instead of either:

doing K 1-element rotations, using 1 temporary variable, with O(K N) time, which is slow
using K-element temporary array, with O(N) time, which is wasteful... but only if there is requirement of doing it in place (and not returning copy, i.e. new N-element array)

is the Aha! solution of using reversals, with the following pseudocode

reverse(A, 0, K-1);
reverse(A, K, A.length()-1);
reverse(A, 0, A.length()-1);

assuming that reverse(A, I, J) operation reverses elements of array A from I-th element to J-th element, inclusive, that is, if $$A=\{a_0,a_1,...,a_i,a_{i+1}...,a_j,a_{j+1}...,a_{N-1}\}$$ then $$\text{reverse}(A, i,j)=\{a_0,a_1,...,a_j,...,a_{i+1},a_i,a_{j+1},...,a_{N-1}\}$$

  For example, given array A = [3, 8, 9, 7, 6] and K = 3,
  the function should return [9, 7, 6, 3, 8].

Steps, corrected for the account of different meaning for K, namely whether it is number of elements to move from left to right ("Programming Pearls"), or from right to left (an example):

[3, 8,| 9, 7, 6] - original array
[8, 3,| 9, 7, 6] - reversed first part
[8, 3,| 6, 7, 9] - also reversed second part
[9, 7, 6,| 3, 8] - the solution

The idea by @forsvarir, namely:

  You're currently rotating the array by 1 over and over again. Instead, think about where each element will end up at the end of N rotations. It's end position should be something like (startPos + numberOfRotations) modulus array size.

is another possible algorithm for an in-place rotation in "Programming Pearls". It can be written in an elegant way, but coming up with correct implementation is a bit more tricky. Though it does twice less operations than the reverse based one, each operation is more complex; also it doesn't play well when N is large enough that swap must be used (nowadays probably not a problem).

Return copy solution

If you are returning a copy, you don't need a temporary K-element array. The solution is to create a result by copying appropriate parts.

In pseudocode (and in programming languages where you can do whole (sub)array copy) it would look like this:

Anew = allocate(N)
Anew[0:K-1] = A[N-K-1:N-1]
Anew[K:N-1] = A[0:N-K-1]

Here I assume that K means number of elements from the end to move to beginning, and that A[0:K-1] means array slice (a(1:K) in Fortran).

Note: I have not checked this solution - beware off-by-one errors here.


Duplicate like a weapon, arrays like heaven Challenge:

  Find the duplicated entry.

Specifications:

  Your program should accept as its first argument a path to a filename.
  Each line in this file is one test case.

  Each line begins with a positive integer(N), the size of the array,
  then a semicolon followed by a comma separated list of positive numbers
  which range from 0 to N-2, inclusive.

  The array contains exactly one duplicated entry which appears exactly twice.
  Print out the duplicated entry, each one on a new line.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class ArrayAbsurdity {
    public static void main(String[] argument) throws FileNotFoundException {
        Scanner input = new Scanner(new File(argument[0]));
        String[] args;

        while (input.hasNextLine()) {
            args = input.nextLine().split(";");
            printDuplicate(args[0], args[1].split(","));
        }
    }

    private static void printDuplicate(String size, String[] nums) {
        boolean[] absurd = new boolean[Integer.parseInt(size)];
        int value;
        Arrays.fill(absurd, false);

        for (int i = 0; i < absurd.length; i++) {
            value = Integer.parseInt(nums[i]);

            if (absurd[value]) {
                System.out.println(value);
                break;
            }

            absurd[value] = true;
        }
    }
}

Sample Input:

  5;0,1,2,3,0
  20;0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16,18,17,14

Sample Output:

  0
  4

I usually write two auxiliary methods, but this time I did some of the work within main's loop, and only wrote one print method. Does the print method do too much? With and without considering its name.

I was going to use two arrays and/or two loops at first, but considering all that was given the question's purpose surely is to create the most efficient solution and thanks to learning of Arrays.fill on one of my previous answers, courtesy of @rolfl, I came up with this. Is it optimal?

For anyone interested, I maintain my current implementation here, and the implementation of the accepted answer here, also the source for the title since a few people asked in chat.

@tim suggested a way to do this with less memory by sorting the array. There's another way to do it with less memory without needing to sort.

Let's say that \$k\$ is the duplicate value in the array. Then we know that the sum of the elements in the array is equal to

\begin{align}
0 + 1 + 2 + 3 + \cdots + (n - 2) + k = \frac{(n - 2)(n - 1)}{2} + k,
\end{align}

where we're using the identity

\begin{align}
1 + 2 + 3 + \cdots + n = \frac{n (n + 1)}{2}.
\end{align}

So if sum is the sum of the values in the array, the duplicate value will be sum - (n - 2) * (n - 1) / 2.


Reading three rows of six tab-separated numbers I've just posted this solution in my review of @adrienlucca's question, which is to read three rows of six tab-separated doubles.

#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>

struct Sexdoublet {
    double x, y, d, m, c, t;

    friend std::istream &operator>>(std::istream &in, Sexdoublet &r) {
        return in >> r.x >> r.y >> r.d >> r.m >> r.c >> r.t;
    }

    friend std::ostream &operator<<(std::ostream &out, const Sexdoublet &r) {
        return out << "[ x = " << r.x
                   << ", y = " << r.y
                   << ", d = " << r.d
                   << ", m = " << r.m
                   << ", c = " << r.c
                   << ", t = " << r.t << " ]";
    }
};

std::vector<Sexdoublet> import(std::istream &in) {
    std::vector<Sexdoublet> data;
    Sexdoublet s;
    do {
        in >> s;
    } while (in && (data.push_back(s), true));
    return data;
}

int main(int argc, char *argv[]) {
    // If the first command-line argument is not "-", treat it as the filename
    // from which to read the input.  Otherwise, read from STDIN.
    const char *filename = (argc >= 2 && 0 != strcmp("-", argv[1])) ?
                                argv[1] : NULL;
    std::ifstream f;
    std::istream &in = filename ? (f.open(filename), f) : std::cin;
    if (!f) {
        std::cerr << "Error opening " << filename << ": "
                  << strerror(errno) << std::endl;
        return 1;
    }

    std::vector<Sexdoublet> data = import(in);
    std::for_each(data.begin(), data.end(), [](const Sexdoublet &s) {
        std::cout << s << std::endl;
    });
    return 0;
}

I ended up using the comma operator twice — both times as a "workaround" for the fact that a function I call returns void:

(data.push_back(s), true) — I have to check whether the istream extractions succeeded before adding an element to the result.
(f.open(filename), f) — I like the ternary operator because it expresses the fact that in is going to be assigned to one value or another.  Also, the in reference has to be initialized immediately and irrevocably, right?

It is my impression that the comma operator is rarely used in C and C++.  So, I'd like to ask, are these reasonable uses of the comma operator?  Or too clever?  Or too dumb, because I've missed an entirely better solution?

the first use can be replaced with:

while(in >> s) {
    data.push_back(s)
}

the second case is much more readable with a simple if else:

std::ifstream f;
if(argc >= 2 && 0 != strcmp("-", argv[1])) {
    f.open(argv[1]);
    if (!f) {
        std::cerr << "Error opening " << argv[1] << ": "
                  << strerror(errno) << std::endl;
        return 1;
    }

}
std::istream &in = f.is_open() ? f : std::cin;


Trim() every string in a JavaScript object? We have a database with fixed width columns. The API is really simple and returns everything the database does with little to no actual processing. This results in some unnecessarily long strings in the model. The model has child objects who have grandchildren and can get quite large at times.

I've written this function to clean up a model right after it's received from the API and right before the rest of the client does anything with it:

function DeepTrim(obj) {
    for (var prop in obj) {
        if (obj.hasOwnProperty(prop)) {
            if (typeof obj[prop] == 'string') {
                obj[prop] = obj[prop].trim();
            } else if (typeof obj[prop] == 'object') {
                DeepTrim(obj[prop]);
            }
        }
    }
}

I know browsers don't really pay attention to consecutive spaces, but this is causing problems when we determine if a field has any valuable content. We can't simply check for a falsey from the string because being filled with spaces makes it just as true as it being filled with an address, phone numbers, or other meaningful data.

This seems to function properly for the few cases I've tried, but it's slow for large objects, especially in IE9 (the oldest browser we're supporting).

Performance is all I care about. It won't be running a thousand times a second, but it might get large, deep objects.  Is there any way to speed this up?

I see a bug for a null property case as typeof null == "object". You should check if it's not null or an object :)

Another less important? bug is you can't use the key hasOwnProeprty on any of your objects. You can get around this by using Object.prototype.hasOwnProperty.call(obj, key)

Only obvious optimization I see is to move the hasOwnProperty check after the typeof check. hasOwnProperty is a relatively expensive function so you will probably see some gains off that. I expect this should be even faster than doing Object.keys which is known to be faster than your for in has loop...

I assume you're polyfilling trim for older browsers right?

function DeepTrim(obj) {
    for (var prop in obj) {
        var value = obj[prop], type = typeof value;
        if (value != null && (type == "string" || type == "object") && obj.hasOwnProperty(prop)) {
            if (type == "object") {
                DeepTrim(obj[prop]);
            } else {
                obj[prop] = obj[prop].trim();
            }
        }
    }
}


Program finds the first almost matching string in a list - Advent Of Code 2018 Day 2 Part 2 Advent of Code 2018, day 2, part 2:

  The [two IDs you are looking for] differ by exactly one character at the same position in both strings. For example, given the following IDs:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

  The IDs fghij and fguij differ by exactly one character, the third (h and u). Those must be the correct IDs.

The code checks a list of strings to find two that match apart from a character at one position. So "abc" and "abz" would match.

I'm very green with Clojure, so feedback about any aspect of this code is appreciated.

(require 'clojure.set)

(def not-empty? (complement empty?))

(def input-lines (line-seq (clojure.java.io/reader "input.in")))

;; Given a string
;; Return a set of similar strings, with an asterisk replacing each character
;; eg "abc" gives #{[\* b c] [a \* c] [a b \*]}
(defn get-match-patterns [id]
  (set (map #(assoc (vec id) % \*) (range (count id)))))

((fn [ids seen-patterns]
  (when (empty? ids)
    (throw (Exception. "Didn't find match")))

  (let [[next-id & other-ids] ids
        match-patterns (get-match-patterns next-id)
        matches (clojure.set/intersection match-patterns seen-patterns)]
    (if (not-empty? matches)
      (prn (apply str (filter #(not= \* %) (first matches))))
      (recur other-ids (apply conj seen-patterns match-patterns))))) input-lines #{})

Sample input:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

Sample output:

fgij

There isn't a whole lot of code here, so I'll just point out what I see top-to-bottom. I'll note though that I'm exceedingly tired and don't fully understand what the problem you're solving is, so I'll just be commenting on aspects of language usage:

Your file starts as (require 'clojure.set). Every Clojure file should start with a call to the ns macro that creates a namespace matching your file's position under the source file of the project. If this file was at PROJECTFOLDER/src/subfolder/my_file.clj, the file should start with

(ns subfolder.my-file)

This allows your file to be properly included by other files.

You have a call to require also though. This can neatly be added to the ns call:

(ns subfolder.my-file
  (:require [clojure.set]))

You aren't even taking advantage of the require though; you can call clojure.set/intersection even without the require. With the require, you can write set/intersection. That's not as nice as it could be though. If you use :as, you can shorten the uses further:

(ns subfolder.my-file
  (:require [clojure.set :as s])) ; Aliasing the set namespace as s

(s/intersection ...) ; Works!

(def not-empty? (complement empty?))

You seem to already be familiar with functional languages. Do you know Haskell? While it's certainly OK to write this function like this, as a complement of another, after a lot of messing around, I've found it's better to just write it out fully in most cases:

(defn not-empty? [coll]
  (not (empty? coll)))

Why? Because now when you ctrl+q it in a good IDE, you get a nice documentation summary that includes the parameter names. For a case like this, most people will immediately know what not-empty? does. For more complicated cases though, you may find that writing out the full defn leads to easier to understand code and generated documentation. Remember the mantra: "code is read more often than it's written". Don't make code harder to understand just to save a few keystrokes.

Really though, do you need this at all? (not (empty? coll)) is arguably just as readable as (not-empty? coll). You also only use it once, and can simply reverse the bodies of the if where it's used. I remember reading that negations (not) should be avoided when possible, as they're slightly hard to comprehend. Even if you did want to have the if bodies in that particular order, you could use (if-not (empty? coll)...) instead.

Nice idiomatic naming though. Your use of dash-naming and ? suffixes are completely appropriate here and idiomatic.

(def input-lines (line-seq (clojure.java.io/reader "input.in")))

Nothing overly wrong here. Of course, hard coding the file path right inside the def isn't necessarily ideal, but for a toy program like this, it's understandable.

This makes your program impossible to test on my end though, as I have no clue what data you're using. I'm unable to run your program, so I'll simply be "translating" between concepts that should be equivalent.

Your IIFE (Immediately invoked function expression; a term from Javascript) is a little odd here. I can't say I've ever seen code like this. This has a few downsides:

Lisp writers can get a little off-put by seeing ((. Often, two opening brackets beside each other either means some fancy is going on, or you have a bug waiting to be run. In this case, it's the former, but it doesn't look ideal.
This entire chunk of code has no name associated with it at all! You have the entire main part of your program top-level as a self-calling anonymous function call. This gives no hints as to what this chunk of code is doing
Having top level expressions that do a lot of work is a problem when developing with a REPL. When I load this into IntelliJ, every time I reload the file, the whole thing runs! Ideally, you should be manually invoking code from the file instead of having the code in the file run when the file is simply loaded.

I would, at the very least, change this to:

(defn main-routine [ids seen-patterns]
  (when (empty? ids)
    (throw (Exception. "Didn't find match")))

  (let [[next-id & other-ids] ids
        match-patterns (get-match-patterns next-id)
        matches (s/intersection match-patterns seen-patterns)]
    (if (not-empty? matches)
      (prn (apply str (filter #(not= \* %) (first matches))))
      (recur other-ids (apply conj seen-patterns match-patterns)))))

(defn main []
  (main-routine input-lines #{}))

Now you have a little more control regarding when your program actually executes.

While straight recursion is usually fine, Clojure has loop that makes ""recursion"" simpler in some cases. Your code looks like it could be rewritten as:

(defn main-routine [ids seen-patterns]
  (loop [[next-id & other-ids] ids]
    (if next-id ; next-id will be nil if ids is empty
      (let [match-patterns (get-match-patterns next-id)
            matches (s/intersection match-patterns seen-patterns)]
        (if (not-empty? matches)
          (prn (apply str (filter #(not= \* %) (first matches))))
          (recur other-ids (apply conj seen-patterns match-patterns))))

      ; This should be a more specific exception.
      ; It also might just be appropriate to return nil, indicating failure.
      (throw (Exception. "Didn't find match")))))

The gain in this scenario isn't huge though, if there's any at all. I just wanted to point out the existence of loop since I often see it ignored, even though it's exceedingly helpful when doing complicated, multi-accumulator reductions.

This is very good code though, especially for someone new to the language. Except for your lack of ns (and even that isn't necessary here), everything I saw is mostly nitpicking. I look forward to seeing more review requests from you.


OpenGL forward-compatible context creation on Windows Is this the proper method for creating an OpenGL 3.3+ forward-compatible context?

// Create window
WNDCLASSEX wc;
ZeroMemory( &wc, sizeof( wc ) );
wc.cbSize = sizeof( wc );
wc.lpfnWndProc = _eventHandler;
wc.hInstance = GetModuleHandle( NULL );
wc.hIcon = LoadIcon( NULL, IDI_APPLICATION );
wc.hIconSm = LoadIcon( NULL, IDI_APPLICATION );
wc.hCursor  = LoadCursor( NULL, IDC_ARROW );
wc.lpszClassName = "OpenGL 3.3";
if ( !RegisterClassEx( &wc ) ) Error( "Failed to register window class!" );
if ( !( _window = CreateWindowEx( WS_EX_CLIENTEDGE, "OpenGL 3.3", "OpenGL 3.3", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, 800, 600, NULL, NULL, GetModuleHandle( NULL ), NULL ) ) )
    Error( "Failed to create the window!" );
if ( !( _hdc = GetDC( _window ) ) ) Error( "Failed to retrieve device context!" );

// Choose pixel format
int pixelFormat;
PIXELFORMATDESCRIPTOR pfd;
ZeroMemory( &pfd, sizeof( pfd ) );
pfd.nSize = sizeof( pfd );
pfd.nVersion = 1;
pfd.dwFlags = PFD_DOUBLEBUFFER | PFD_SUPPORT_OPENGL | PFD_DRAW_TO_WINDOW;
pfd.iPixelType = PFD_TYPE_RGBA;
pfd.cColorBits = 32;
pfd.cDepthBits = 32;
pfd.iLayerType = PFD_MAIN_PLANE;
if ( !( pixelFormat = ChoosePixelFormat( _hdc, &pfd ) ) ) Error( "Failed to find suitable pixel format!" );
if ( !SetPixelFormat( _hdc, pixelFormat, &pfd ) ) Error( "Failed to set pixel format!" );

// Create temporary context and make sure we have support
HGLRC tempContext = wglCreateContext( _hdc );
if ( !tempContext ) Error( "Failed to create temporary context!" );
if ( !wglMakeCurrent( _hdc, tempContext ) ) Error( "Failed to activate temporary context!" );

int major, minor; glGetIntegerv( GL_MAJOR_VERSION, &major ); glGetIntegerv( GL_MINOR_VERSION, &minor );
if ( major < 3 || minor < 2 ) Error( "OpenGL 3.2 is not supported!" );

// Create forward compatible context
int attribs[] =
{
    WGL_CONTEXT_MAJOR_VERSION_ARB, major,
    WGL_CONTEXT_MINOR_VERSION_ARB, minor,
    WGL_CONTEXT_FLAGS_ARB, WGL_CONTEXT_FORWARD_COMPATIBLE_BIT_ARB,
    WGL_CONTEXT_PROFILE_MASK_ARB, WGL_CONTEXT_CORE_PROFILE_BIT_ARB,
    0
};
PFNWGLCREATEBUFFERREGIONARBPROC wglCreateContextAttribsARB = (PFNWGLCREATEBUFFERREGIONARBPROC)wglGetProcAddress( "wglCreateContextAttribsARB" );
if ( !wglCreateContextAttribsARB ) Error( "Failed to find pointer to wglCreateContextAttribsARB function!" );
if ( !( _context = wglCreateContextAttribsARB( _hdc, 0, (UINT)attribs ) ) ) Error( "Failed to create forward compatible context!" );

// Remove temporary context and activate forward compatible context
wglMakeCurrent( NULL, NULL );
wglDeleteContext( tempContext );
if ( !wglMakeCurrent( _hdc, (HGLRC)_context ) ) Error( "Failed to activate forward compatible context!" );

// Show window
ShowWindow( _window, SW_SHOW );
UpdateWindow( _window );

It seems to work (gives GL_INVALID_OPERATION when using glBegin), but I just want to make sure this is the right way to go about it.

This looks right to me. I am a bit tired right now and usually use GLFW.

You might be interested in this page on the OpenGL wiki describing setting up the context after 3.1 which is essentially the same work.


Fetching data through HTTP and caching JSON result in a file The task is to fetch some JSON data from an API with a GET request. If the location is not available for any reason, read a cache file. Otherwise write the cache file for future use.

The following function works but it is clumsy due to:

The nested try/except, which is difficult to read
It's difficult to figure out what the error is (I am catching both HTTPError and the JSONDecodeError to avoid further nesting
I don't dare to use a context manager for opening the file (with) due to a further nesting level within a try/except clause

Have you got any ideas for improvement?

def fetch_list(location=MY_LOCATION, cache_file=CACHE_FILE):
    """Goes to the default location and returns
    a python list
    """
    http = urllib3.PoolManager()
    try:
        r = http.request("GET",
                         location)
        raw_data = r.data.decode("utf-8")
        data = json.loads(raw_data)
    except (urllib3.exceptions.HTTPError, JSONDecodeError):
        logger.error("Cannot access Intranet List Location - fetching cache")
        try:
            data = json.loads(open(cache_file).readlines())
        except (IOError, JSONDecodeError):
            logger.error("Cache File not found or broken")
            raise
    else:
        with open(cache_file, "w") as f:
            f.write(raw_data)

    return data

If your logger object is derived from the logging module, use the logger.exception which'll log the traceback information as well. The docs (linked above) also specify this behaviour:

  Exception info is added to the logging message. This function should
  only be called from an exception handler.

You can avoid nesting try-except block by just passing in first exception and place the write to cache inside the first try block itself:

def fetch_list(location=MY_LOCATION, cache_file=CACHE_FILE):
    """Goes to the default location and returns a python list.
    """
    try:
        http = urllib3.PoolManager()
        request = http.request("GET", location)
        raw_data = request.data.decode("utf-8")
        data = json.loads(raw_data)
        with open(cache_file, "w") as cache:
            cache.write(raw_data)
        return data
    except (urllib3.exceptions.HTTPError, JSONDecodeError) as exc:
        logger.exception("Cannot access Intranet List Location - fetching cache")
    try:
        data = json.loads(open(cache_file).readlines())
        return data
    except (IOError, JSONDecodeError):
        logger.exception("Cache File not found or broken")
        raise


Disjoint cycles of a permutation Given an element of the permutation group, expressed in Cauchy notation, it is often useful to have it expressed in disjoint cycles (for example to apply the permutation to the keys of a dictionary).

The code below provides a possible answer to the problem: how to go from the Cauchy notation to the disjoint cycle and backward?

What I could not answer is: how to make it more efficient? Should this be made recursive?  Why or why not?

E.g.
Cauchy notation

p = [[1,2,3,4,5,6], [3,1,2,6,5,4]]

means permute 1 with 3, 3 with 2, 2 with 1 and 4 with 6, leaving 5 alone.

Corresponding disjoint cycles are:

c = [[1,3,2], [4,6]]

I proposed the same code here and here.

def is_valid_permutation(in_perm):
    """
    A permutation is a list of 2 lists of same size:
    a = [[1,2,3], [2,3,1]]
    means permute 1 with 2, 2 with 3, 3 with 1.
    :param in_perm: input permutation.
    """
    if not len(in_perm) == 2:
        return False
    if not len(in_perm[0]) == len(in_perm[1]):
        return False
    if not all(isinstance(n, int) for n in in_perm[0]):
        return False
    if not all(isinstance(n, int) for n in in_perm[1]):
        return False
    if not set(in_perm[0]) == set(in_perm[1]):
        return False
    return True

def lift_list(input_list):
    """
    List of nested lists becomes a list with the element exposed in the main list.
    :param input_list: a list of lists.
    :return: eliminates the first nesting levels of lists.
    E.G.
    >> lift_list([1, 2, [1,2,3], [1,2], [4,5, 6], [3,4]])
    [1, 2, 1, 2, 3, 1, 2, 4, 5, 6, 3, 4]
    """
    if input_list == []:
        return []
    else:
        return lift_list(input_list[0]) + (lift_list(input_list[1:]) if len(input_list) > 1 else []) \
            if type(input_list) is list else [input_list]

def decouple_permutation(perm):
    """
    from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    to   [[1,3], [2,4], [3,5], [4,2], [5,1]]
    """
    return [a for a in [list(a) for a in zip(perm[0], perm[1]) if perm[0] != perm[1]] if a[0] != a[1]]

def merge_decoupled_permutation(decoupled):
    """
    From [[1,3], [2,4], [3,5], [4,2], [5,1]]
    to   [[1, 3, 5], [2, 4]]
    """
    ans = []
    while len(decoupled):
        index_next = [k[0] for k in decoupled[1:]].index(decoupled[0][-1]) + 1
        decoupled[0].append(decoupled[index_next][1])
        decoupled.pop(index_next)
        if decoupled[0][0] == decoupled[0][-1]:
            ans.append(decoupled[0][:-1])
            decoupled.pop(0)
    return ans

def from_permutation_to_disjoints_cycles(perm):
    """
    from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    to   [[1, 3, 5], [2, 4]]
    """
    if not is_valid_permutation(perm):
        raise IOError('Input permutation is not valid')
    return merge_decoupled_permutation(decouple_permutation(perm))

def from_disjoint_cycles_to_permutation(dc):
    """
    from [[1, 3, 5], [2, 4]]
    to   [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    """
    perm = [0, ] * max(lift_list(dc))
    for cycle in dc:
        for i, c in enumerate(cycle):
            perm[c-1] = cycle[(i + 1) % len(cycle)]
    return [list(range(1, len(perm) + 1)), perm]

The input validation

is_valid_permutation() does not verify if the elements in the two lists
are unique. As an example

is_valid_permutation([[1, 1, 1, 2], [2, 2, 2, 1]])

returns True (and

from_permutation_to_disjoints_cycles([[1, 1, 1, 2], [2, 2, 2, 1]])

aborts later with a ValueError because some index is not found).
This can for example be fixed by checking

len(in_perm[0]) == len(in_perm[1]) == len(set(in_perm[0]))

instead of

len(in_perm[0]) == len(in_perm[1])

Restricting the input to lists of integers seems unnecessary to me,
the conversion from the Cauchy notation to cycles works perfectly with arbitrary values (as long as they are hashable):

>>> print(from_permutation_to_disjoints_cycles([["a", "b", "c", "d"], ["b", "a", "d", "c"]]))
[['a', 'b'], ['c', 'd']]

For invalid input, ValueError seems more
appropriate to me, IOError is meant for I/O related failures, such
as reading or writing data.

From Cauchy notation to cycles

decouple_permutation() can be simplified to

def decouple_permutation(perm):
    """
    from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    to   [[1,3], [2,4], [3,5], [4,2], [5,1]]
    """
    return [list(a) for a in zip(perm[0], perm[1]) if a[0] != a[1]]

the check for perm[0] != perm[1] is not necessary.

However, I would suggest to use a dictionary instead of a list of lists
to store the mappings. Dictionary lookup is much faster than a (linear)
search in a list (what index() does). This leads to the following
implementation:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) if a != b }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles

For each initial value which has not been handled, we build a complete
cycle by dictionary lookups. pop() retrieves the next element of a
cycle and removes the pair from the dictionary, so that it will not be
handled again. Apart from appending to the cycles, no list modifications
are done.

(Remark: My initial suggestion did not work correctly. This new version
does essentially what the “pseudo code” in Acccumulation's answer
describes. The implementation however is different.)

In my test this was significantly faster for large permutations (benchmark
below).

Finally, your code does not return cycles with a single element:

>>> from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3]]

As a consequence, the reverse conversion gives not the original permutation:

>>> from_disjoint_cycles_to_permutation([[1, 2, 3]])
[[1, 2, 3], [2, 3, 1]]

With the dictionary approach, this can be fixed by removing the if a != b condition:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles

Now

>>> from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3], [4]]

>>> from_disjoint_cycles_to_permutation([[1, 2, 3], [4]])
[[1, 2, 3, 4], [2, 3, 1, 4]]

Benchmark

A primitive benchmark, for the permutation which reverses the first 1000
integers (without the input validation):

import time

perm = [[x for x in range(1, 1001)], [x for x in reversed(range(1, 1001))]]

start = time.time()
c = from_permutation_to_disjoints_cycles(perm)
end = time.time()
print((end - start) * 1000)

Result (on a 1,2 GHz MacBook):

Your code: 20 milliseconds,
My code: 0.8 milliseconds.

From cycles to Cauchy notation

The conversion from the Cauchy notation to cycles works with arbitrary
(distinct) integers (or even arbitrary values), but the reverse
conversion assumes that the values are consecutive integers starting
at 1:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[1, 2, 3, 4, 5, 6], [0, 3, 2, 0, 6, 5]

An alternative approach would be to zip() each cycle with a rotation
of itself, to get the list of mapping pairs:

def from_disjoint_cycles_to_permutation(dc):
    """
    from [[1, 3, 5], [2, 4]]
    to   [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    """
    pairs = [(a, b) for cycle in dc for a, b in zip(cycle, cycle[1:] + cycle[:1])]
    return [list(i) for i in zip(*pairs)]

(The transposition method is taken from Transpose list of lists on Stack Overflow.)

Now the reverse conversion works as expected:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[2, 3, 5, 6], [3, 2, 6, 5]]

and the function is not limited to integers anymore.

Using Sympy

The Permutation
class from Sympy provides functions to convert between the
different representations.

Example (the permutations elements are zero-based integers):

>>> from sympy.combinatorics import Permutation

>>> p1 = Permutation([2, 0, 1, 5, 4, 3])
>>> p1.cyclic_form
[[0, 2, 1], [3, 5]]
>>> p1.full_cyclic_form
[[0, 2, 1], [3, 5], [4]]

>>> p2 = Permutation([[0, 2, 1], [3, 5]])
>>> p2.array_form
[2, 0, 1, 5, 4, 3]


Text reading and string inputting program The Main program. This program pulls from a .txt document with two separate strings, and outputs a  .cs program that will display those two string via console when run. It uses a structure.txt file for the code it inputs the strings into.

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

namespace ConsoleApplication3
{
class Program
{
    static void Main(string[] args)
    {

        //structure.txt contains the program we will enter our values into.
        String filePath = "Structure.txt";

        WriteToFile(filePath);

    }

    public static void WriteToFile(string filePath)
    {
        //create a string array to gather our text file information.

        StreamReader reader = new StreamReader(filePath);
        StreamReader info = new StreamReader("Structure.txt");

        StreamWriter writer = new StreamWriter("Hello.cs", true);
        String temp = String.Empty;

        while (!info.EndOfStream)
        {
            String tempstring = String.Empty;
            tempstring = reader.ReadLine();

            while (!reader.EndOfStream)
            {

                temp = reader.ReadLine();
                writer.WriteLine(temp);
                if (temp == "//break")
                {
                    writer.WriteLine($"String1 = {tempstring}");

                }
                else if (temp == "//break 2") {
                    writer.WriteLine($"String2 = {tempstring}");
                }

            }
        }
        reader.Close();
        info.Close();

        writer.Close();
    }

}
}

structure.txt is just a basic program that prints the two strings gathered from the main program unto the console.

using System;
namespace HelloWorld
{
class Hello
{
    static void Main()
    {
//break

//break 2

    Console.WriteLine(string1);

        // Keep the console window open in debug mode.
        Console.WriteLine("Press any key to continue.");
        Console.ReadKey();

    Console.WriteLine(string2);
    Console.ReadKey();
    }
}
//end
}

This program runs, but I am wanting to improve the code and increase its efficiency.

I wonder if you even have tested this program:

This:

  while (!info.EndOfStream)
  {
    String tempstring = String.Empty;
    tempstring = reader.ReadLine();

    while (!reader.EndOfStream)
    {

will run forever because info is never read from and will never reach EOS.

In the context this:

   while (!info.EndOfStream)    {
     String tempstring = String.Empty;
     tempstring = reader.ReadLine();

is not understandable. Do you have the tempstring that is going to be written instead of the placeholders in the top of the structure.txt-file?

You open the same file twice:

public static void WriteToFile(string filePath)
{
  //create a string array to gather our text file information.

  StreamReader reader = new StreamReader(filePath);
  StreamReader info = new StreamReader("Structure.txt");

because the argument filePath is also "Structure.txt". Why open the same file more than once for the same operation?

StreamReader and StreamWriter implement IDisposable and should be disposed off like:

using (StreamReader reader = new StreamReader(filePath))
using (StreamWriter writer = new StreamWriter("helle.cs"))
{
   ...
}

You shouldn't hardcode string literals in a method but provide them as arguments:

public static void WriteToFile(string inputFile, string outputFile)
{
   ...
}

Instead of:

 while (!reader.EndOfStream)
 {

    temp = reader.ReadLine();

it is better to do:

string line = null;
while ((line = reader.ReadLine()) != null)
{
   ...
}

  StreamWriter writer = new StreamWriter("Hello.cs", true);

you set the append argument to true, but I'm quite sure you mean to overwrite the existing file?


Simple linked hash map in JS (Node/browser) I needed a simple data structure to cache the most recent few directory contents for this project I was working on. I thought a linked hash map would be the right approach since we will cache only one item per path (the key) and keep only X recent items. We will store the timestamp and directory contents as the "payload" for each node.

/**
 * A linked-list with key-based map. Use case: recent items cache, storing the
 * last X items with linear-time lookup and removal (constant average cost per
 * operation)
 *
 * - Adding an item to head will remove any existing items with that key
 * - Adding to head will remove an item from tail if needed to prevent
 *   exceeding max length
 */

function LinkedHashMap(maxLength) {
  this.map = {};
  this.head = null;
  this.tail = null;
  this.length = 0;
  this.maxLength = maxLength;
}

LinkedHashMap.prototype = {
  get: function(key) {
    var item = this.map[key] || {};
    return item.payload;
  },

  addHead: function(key, payload) {
    this.remove(key);
    if (this.length === this.maxLength) {
      this.removeTail();
    }
    var item = {
      key: key,
      prev: null,
      next: this.head,
      payload: payload
    };
    if (this.head) {
      this.head.prev = item;
    }
    this.head = item;
    if (!this.tail) {
      this.tail = item;
    }
    this.map[key] = item;
    this.length += 1;
  },

  removeTail: function() {
    if (this.tail) {
      this.removeItem(this.tail);
    }
  },

  // remove item by key
  remove: function(key) {
    var item = this.map[key];
    if (!item) return;
    this.removeItem(item);
  },

  // this removes an item from the link chain and updates length/map
  removeItem: function(item) {
    if (this.head === item) {
      this.head = item.next;
    }
    if (this.tail === item) {
      this.tail = item.prev;
    }
    if (item.prev) {
      item.prev.next = item.next;
    }
    if (item.next) {
      item.next.prev = item.prev;
    }
    delete this.map[item.key];
    this.length -= 1;
  }
};

This is good code! I don't have many suggestions, and those that I do have are mostly minor.

First of all, just consider the general naming. I don't mind the names as they are, but you could consider other names as well. Here are two sets of alternate names for addHead and removeTail:

add / remove — The simple approach. I sort of prefer something a little more explicit.
push / pop — I like this more. It conveys the stack-like nature of the data structure but is more concise.

Now for some more substantive suggestions. None of these functions (except, of course, get) return anything! This is okay, but not ideal. JavaScript lends itself quite well to chaining, and it would be nice to be able to do something like this:

map.push('foo', 'bar')
   .push('baz', 'qux')
   .push('one', 'two')
   .push('red', 'blue');

Make addHead/push return the map!

Next, also add return values for remove and pop/removeTail. These should each return the value removed from the map. This also makes it easy to determine if a removal actually removed something or not.

Also, should maxLength really be required? What if I want an unbounded map? Under your current implementation, I could just pass in null or undefined or -1, but it might be nice to make this functionality more explicit.

Now for some suggestions for additions.

First of all, add some kind of length or size method. Using Object.defineProperty, you could even implement length as a "magic" property a-la array.length.

Second, having access to the actual underlying list seems a little important if you're using this to display anything. The obvious answer would be to add some sort of iterator support, but JavaScript doesn't really have native support for iterators (pre-ES6). For simplicity's sake, a simple keys function that returned the list of keys in list order would be convenient.

Also, you might want to add peekHead and peekTail to complement the existing set of functions, since even with keys, shorthand access is convenient.

Consider adding some error checking. While this is called LinkedHashMap, JavaScript objects only support string keys. This isn't really a problem, and building a more general solution in pure JS would be nontrivial (another thing coming in ES6!). Unfortunately, it wouldn't be unreasonable for someone to accidentally try to use an object as a key. I'd recommend throwing an exception on insertion for non-string keys. Force explicit calls to toString to avoid confusing errors down the line.

Other odds and ends:

Why is removeItem part of the public API? Make it internal. Don't expose it.
Add some inline comments! Most of this code is fairly self-explanatory, so you don't need to write any essays. Just adding something like // insert item at head of list would break up the code and make it easier to follow by dividing it into chunks.
Add tests! Something like this is a textbook candidate for extensive unit testing. Something like a data structure should not go untested.


Is this the wrong way to handle AggregateException with Tasks I'm seeing a lot of code like this at my new site

        try
        {
            Task.Factory.StartNew(() =>
            {
            ...
            });
        }
        catch (AggregateException ex)
        {
            ex.Handle((x) =>
            {
                Log.Write(x);
                return true;
            });
        }

From what I've read, as Wait(), Result or Exception are not called the AggregateException will not have been marshalled. Also the Task may not even of started yet.
I'm thinking of using Joe Albahari's extension method that uses a continuation as these are mainly fire and forget Tasks

public static void PrintExceptions (this Task task)
{
       task.ContinueWith (t => { var ignore = t.Exception; },
       TaskContinuationOptions.OnlyOnFaulted);
}

Am I on the right track?

You are quite right. These exception handling blocks will never catch any task exceptions. The code should be modified to check the Task.IsFaulted flag in the continuation and check the Task.Exception property for the actual exception.

In fact, should an exception occur it will remain unhandled and your application will crash unless you attach an exception handler to TaskScheduler.UnobservedTaskException.

You should definitely check the "Exception Handling (Task Parallel Library)" article in MSDN for the proper ways to handle Task exceptions.

You should also take a look at the Async CTP for C#. It has a production license even though it is technically a CTP and it will make coding with Tasks a lot easier and safer, as you can see from the snippet I found here:

private async void FetchData()
{
    using (var wc = new WebClient())
    {
        try
        {
            string content = await wc.DownloadStringTaskAsync(
                new Uri("http://www.interact-sw.co.uk/oops/"));

            textBox1.Text = content;
        }
        catch (WebException x)
        {
            textBox1.Text = "Error: " + x.Message;
        }
    }
}

You can use the CTP just by adding a reference to the appropriate DLL. The resulting code will certainly be safer that what you posted here, CTP or not.


Critique of Cardinal Direction Enum I'm working on a simple game in which I need to track the cardinal direction of an object. I experimented with using the enum's ordinal value, as well as using switches for the rotation, but both seemed wrong. This is what I ended up with. Is the following an adequate solution?

// Defines cardinal direction
public enum Direction {
    NORTH(0) {
        @Override
        public String getMessage() {
            return getDegrees() + " degrees due north";
        }
    },
    EAST(90) {
        @Override
        public String getMessage() {
            return getDegrees() + " degrees due east";
        }
    },
    SOUTH(180) {
        @Override
        public String getMessage() {
            return getDegrees() + " degrees due south";
        }
    },
    WEST(270) {
        @Override
        public String getMessage() {
            return getDegrees() + " degrees due west";
        }
    };

    private final int degrees;

    public abstract String getMessage();

    private Direction(final int degrees) {
        this.degrees = degrees;
    }

    public int getDegrees() {
        return degrees;
    }

    private static final Map<Integer, Direction> lookup = new HashMap<Integer, Direction>();

    static {
        for (Direction d : EnumSet.allOf(Direction.class))
            lookup.put(d.getDegrees(), d);
    }

    public static Direction get(int degrees) {
        return lookup.get(degrees);
    }

    public Direction rotateRight() {
        return Direction.get((degrees + 90) % 360);
    }

    public Direction rotateLeft() {
        return Direction.get((degrees + 270) % 360);
    }

}

Conceptually it is a great solution. I can suggest some changes, but in reality they are minor. It would also be 'fun' to tune it  abit, but in the bigger picture the changes would be miniscule... still...

My biggest observation is that the constructors can be simplified a lot. Instead of having each Enum member create a unique method implementation (and that method builds a String each time - though the compiler will probably fix that), you could simplify it a lot with:

private final int degrees;
private final String message;

private Direction(final int degrees, final String name) {
    this.degrees = degrees;
    this.message = degrees + " degrees due " + name;
}

public int getDegrees() {
    return degrees;
}

public String getMessage() {
    return message;
}

With the change to the constructor, you have:

no abstract methods to implement
simple message which is a constant, instead of re-creating it each time you call getMessage()
Your enums are initialized in a simpler way:

NORTH(0, "North"),
EAST(90, "East"),
SOUTH(180, "South"),
WEST(270, "West")

Apart from this, the code is pretty good, but, there is a way you can 'play' with the lookup system to use the ordinals only.... consider the following code (I'll leave it to you to figure out.... ;-):

public static Direction get(final int degrees) {
    int ordinal = ((degrees % 360) / 90) - ( 4 * (degrees % 90));
    return ordinal < 0 ?  null : values()[ordinal];
}


Efficiency of nested LINQ foreach loops I've been working on an older project with framework is 3.5 as the target. There is a new user control that displays a list of data from a web service. I hit the web service (Soap/XML) and deserialize the data into a list of a custom model/class (this is in a helper class outside the user control).

Back in the user control code behind, I'm looping through the data and displaying it using a HtmlTextWriter. Here is an example of some of the code (simplified):

        var sb = new StringBuilder();
        using (var writer = new HtmlTextWriter(new StringWriter(sb)))
        {
            foreach  (
                var month in
                    courses.SelectMany(x => x.Offerings)
                        .Where(x => !string.IsNullOrEmpty(x.StartDate))
                        .Select(x => DateTime.Parse(x.StartDate))
                        .Select(x => new DateTime(x.Year, x.Month, 1))
                        .Distinct()
                        .OrderBy(x => x.Year)
                        .ThenBy(x => x.Month)
                        .ToList())
            {

            //some display code using the writer

                foreach (var offering in
                    courses.SelectMany(x => x.Offerings)
                        .Where(x => !string.IsNullOrEmpty(x.StartDate))
                        .Where(
                            x =>
                                DateTime.Parse(x.StartDate).Year == month.Year
                                && DateTime.Parse(x.StartDate).Month == month.Month)
                        .OrderBy(x => DateTime.Parse(x.StartDate))
                        .ToList())
                {
                    //more display code using the writer
                }
            }
        }
        thisisadiv.InnerHtml = sb.ToString();

The HTML markup is a design that was already in place somewhere else so I chose not to change it at all in the interest of time.

Is there a more efficient way of looping through the classes/data that I could benefit from? I'm currently not seeing any speed issues but want to make sure I'm using an adequate technique.

Actually reviewing your question again it looks like what you are trying to do is to group all offerings by the same year and month and then iterate over each offering. Hence a GroupBy query is probably what you want:

foreach (
    var offerings in
        courses.SelectMany(x => x.Offerings)
            .Where(x => !string.IsNullOrEmpty(x.StartDate))
            .Select(x =>
                    new {
                        Offer = x,
                        StartDateMonth = new DateTime(DateTime.Parse(x.StartDate).Year, DateTime.Parse(x.StartDate).Month, 1)
                    })
            .GroupBy(x => x.StartDateMonth)
            .OrderBy(g => g.Key))
{

    //some display code using the writer
    // offerings will be a group of offerings which have the StartDate in the same year/month

    foreach (var offering in offerings.Select(o => o.Offer))
    {
        // iterate over all offers in the group
    }
}

Not sure if there is a nice effective way to avoid the double parsing.