Finding the perfect number from 1 to n I have a program to find the perfect number from 1 to n:

How can this be reduced without changing it?

class PerfectNumber
{
    public static StringBuffer fact(int a)
    {
        StringBuffer sb=new StringBuffer(" ");
        for(int i=1;i<a;i++)
        if(a%i==0)
        {
            sb.append(i+",");
        }
        return sb;
    }
    public static String isPrime(int a)
    {
        int sum=0;
        for(int i=1;i<a;i++)
        {
            if(a%i==0)
        {
            sum+=i;
        }

        }
        if (sum==a)
        {
            return "true";
        }
        else
            return "false";
    }
    public static int perfecrNo(int a)
    {
        int sum=0;
        for(int i=1;i<a;i++)
        {
            if(a%i==0)
        {
            sum+=i;
        }

        }
        return sum;
    }
    public static void main(String[] args)
    {

        System.out.println("--------------------------------------------------------------------------");
        System.out.printf("%s%40s%15s%15s%n","NO","fact","sum","isPrime");
        System.out.println("--------------------------------------------------------------------------");
        for(int i=1;i<100;i++)
        {
            System.out.printf("%n %d %40s\b %15d %15s",i,fact(i),perfecrNo(i),isPrime(i));
        }

    }
}

Indentation

To pick one example:

        for(int i=1;i<a;i++)
        {
            if(a%i==0)
        {
            sum+=i;
        }

What's going on here? My best guess would be that you're mixing tabs and spaces with a tabstop of 8. Be consistent: tabs or spaces. Changing the tabstop shouldn't break the formatting.

Names

    public static StringBuffer fact(int a)
    public static String isPrime(int a)
    public static int perfecrNo(int a)

What do these three methods do?

The first one produces a string containing the factors. Before reading the implementation I had guessed that it calculated the factorial. Name could be more descriptive: e.g. formatFactors.
The second one tests whether the number is a perfect number or not. The name is simply wrong: it claims that the method does something different to what it does. It should be e.g. isPerfectNumber.
The third one calculates the sum of the factors. The name certainly doesn't communicate that to me. It should be e.g. sumOfFactors (or aliquotSum if you don't mind the technical term).

Factoring out common code

All three of those methods have a loop which does the same thing: find the factors of a. That should be pulled out into a single method, which should have a suitable return type (e.g. Collection<Integer>, although there's a good case for Set<Integer>, or maybe some integer stream type, but I'm not up to date on Java 8).

Then two of the methods sum the factors: that's already pulled out into a method, so the other method shouldn't duplicate it. Instead you should have a very simple method

public static boolean isPerfectNumber(int a)
{
    return a == sumOfFactors(a);
}

Rethink method signatures

Why does fact return a StringBuffer? I can't think of many situations in which it makes sense to return a StringBuffer (or a StringBuilder). Either you're appending to a StringBuffer/StringBuilder, in which case it should almost always be an argument and doesn't need to be returned, or you aren't, in which case it makes more sense to return a String.

Why does isPrime (isPerfectNumber) return a string "true" or "false"? The boolean type exists for precisely the type of things which are true or false.


count all array[index] == index occurrences The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: i == list[i] (where i is the index 0 <= i <= len(list)).

def foo_helper(lst, start, end):

    if start > end:
        # end of recursion
        return 0

    if lst[end] < end or lst[start] > start:
        # no point checking this part of the list
        return 0

    # all indexes must be equal to their values
    if abs(end - start) == lst[end] - lst[start]:
        return end - start + 1

    middle = (end + start) // 2

    print(lst[start:end+1], start, middle, end)

    if lst[middle] == middle:
        #print("lst[" , middle , "]=", lst[middle])
        return 1 + foo_helper(lst, middle+1, end) + \
    foo_helper(lst, start, middle-1)

    elif lst[middle] < middle:
        return foo_helper(lst, middle+1, end)
    else:
        return foo_helper(lst, start, middle-1)

def foo(lst):
    return foo_helper(lst, 0, len(lst)-1)

My question is: is this code's worst-case complexity log(n)?  If not, what should I do differently?

Now let's see if I understand your problem: Given a sorted list of unique numbers you want to find all instances where list[i] == i (the important part is the unique).

This means each number in the list is at least 1 larger than the previous number.
Assume that list[k] == x < k. Because the numbers are strictly increasing it must be that list[k-1] <= x-1 < k-1, list[k-2] <= x-2 < k-2, ... list[k-l] <= x-l < k-l. So if you have an index where the value is smaller than the index then this must also be the case for all previous indices.
Assume that list[k] == x > k. Because the numbers are strictly increasing it must be that list[k+1] >= x+1 > k+1, list[k+2] >= x+2 > k+2, ... list[k+l] >= x+l > k+l. So if you have an index where the value is larger than the index then this must also be the case for all following indices.

The conclusion from these points is that a list with the given properties can be divided into three parts

Start 0 <= s < ms with list[s] < s
Middle ms <= m < me with list[m] == m
End me <= e < n with list[e] > e

Your problem is to find the middle part. The number of items where list[i] == i is then me - ms.

This can be solved by finding the largest index for which list[k] < k and the smallest index for which list[k] > k (or the smallest and largest indices for which list[k] == k - depends on how you want to write the search criteria).

Using two binary searches should yield the desired results which will guarantee a worst case complexity of O(log(n))

Update: Your original implementation is effectively a binary search which will find both end and start point of the middle sequence so you implementation is O(log(n))


Multiply two columns of Census data and groupby I have census data that looks like this

    State   County  TotalPop    Hispanic    White   Black   Native  Asian   Pacific
   Alabama  Autauga     1948    0.9         87.4    7.7     0.3     0.6     0.0
   Alabama  Autauga     2156    0.8         40.4    53.3    0.0     2.3     0.0
   Alabama  Autauga     2968    0.0         74.5    18.6    0.5     1.4     0.3
   ...

Two things to note, (1) there can be multiple rows for a County and (2) the racial data is given in percentages, but sometimes I want the actual size of the population.

Getting the total racial population translates to (in pseudo Pandas):

(census.TotalPop * census.Hispanic / 100).groupby("County").sum()

But, this gives an error: KeyError: 'State'.  As the product of TotalPop and Hispanic is a Pandas Series not the original dataframe.

As suggested by this Stack Overflow question, I can create a new column for each race...

census["HispanicPop"] = census.TotalPop * census.Hispanic / 100

This works, but feels messy, it adds 6 columns unnecessarily as I just need the data for one plot.  Here is the data (I'm using "acs2015_census_tract_data.csv") and here is my implementation:

Working Code

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
%matplotlib inline

census = pd.read_csv("data/acs2015_census_tract_data.csv")

races = ['Hispanic', 'White', 'Black', 'Native', 'Asian', 'Pacific']

# Creating a total population column for each race
# FIXME: this feels inefficient.  Does Pandas have another option?
for race in races:
    census[race + "_pop"] = (census[race] * census.TotalPop) / 100

# current racial population being plotted
race = races[0]

# Sum the populations in each state
race_pops = census.groupby("State")[race + "_pop"].sum().sort_values(ascending=False)

#### Plotting the results for each state

fig, axarr = plt.subplots(2, 2, figsize=(18, 12))
fig.suptitle("{} population in all 52 states".format(race), fontsize=18)

# Splitting the plot into 4 subplots so I can fit all 52 States
data = race_pops.head(13)
sns.barplot(x=data.values, y=data.index, ax=axarr[0][0])

data = race_pops.iloc[13:26]
sns.barplot(x=data.values, y=data.index, ax=axarr[0][1]).set(ylabel="")

data = race_pops.iloc[26:39]
sns.barplot(x=data.values, y=data.index, ax=axarr[1][0])

data = race_pops.tail(13)
_ = sns.barplot(x=data.values, y=data.index, ax=axarr[1][1]).set(ylabel="")

Since you only want to use the total population values for these plots it is not worth adding these columns to your census DataFrame. I would package the plots into a function which creates a temporary DataFrame that is used and then disposed of after the plotting is complete.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
%matplotlib inline

def plot_populations(census, race):
    # Group the data
    race_pops = pd.DataFrame(data={
                                   'State': census['State'],
                                   'Pop': census[race] * census['TotalPop'] / 100
                                  }
                            ).groupby('State')['Pop'].sum().sort_values(ascending=False)

    # Plot the results
    fig, axarr = plt.subplots(2, 2, figsize=(18, 12))
    fig.suptitle("{} population in all 52 states".format(race), fontsize=18)
    for ix, ax in enumerate(axarr.reshape(-1)):
        data = race_pops.iloc[ix*len(race_pops)//4:(ix+1)*len(race_pops)//4]
        sns.barplot(x=data.values, y=data.index, ax=ax)
        if ix % 2 != 0: ax.set_ylabel('')

census = pd.read_csv("acs2015_census_tract_data.csv")

races = ['Hispanic', 'White', 'Black', 'Native', 'Asian', 'Pacific']
# current racial population being plotted
race = races[0]

plot_populations(census, race)


Outputting the names of cars, without repetitions, with the number of occurrences in order of decreasing repetitions A short while ago, I have submitted a coding exercise to a
potential employer. The response came back the next
morning and you can guess what it was from the subject
of this post.

I am not totally at loss, but I need another programmer's
perspective. Is there anything that jumps out?

The idea of the exercise is simple: I'm given an input file with
names of cars, one per line,  possibly repeated and in no
particular order.

The program should output the same names, except with no
repetitions, the number of occurrences listed next to each
car, and in order of decreasing repetitions.

Example:

Honda\n Audi\n Honda\n -> Honda 2 \n Audi 1\n

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>

using namespace std;

// helper functions ///////////////////////////////////////

// reads lines from instream
void collect_lines(istream &in, map<string, int> &lines);

// given lines->num_occurs map, reverses mapping
void reorg_by_count(map<string, int> &lines,
                    multimap<int, string> &bycount);
///////////////////////////////////////////////////////////

int main(int ac, char* av[])
{
    istream *in;
    map<string, int> *lines = new map<string, int>();
    multimap<int, string> *lines_by_count = new multimap<int, string>();

    if (ac < 2)
    {
        in = &cin;
    }
    else
    {
        in = new ifstream(av[1]);
    }

    if (!in->good()) return 1;

    collect_lines(*in, *lines);
    reorg_by_count(*lines, *lines_by_count);

    if (in != &cin)
          {
        ((ifstream *)in)->close();
        delete in;
    }

    cout << "=====================\n\n";

    multimap<int, string>::reverse_iterator it
        = lines_by_count->rbegin();

    for (; it != lines_by_count->rend(); it++)
    {
        cout << it->second << " " << it->first << '\n';
    }

    delete lines;
    delete lines_by_count;

    return 0;
}

// Read the instream line by line, until EOF.
// Trim initial space. Empty lines skipped
void collect_lines(istream &in, map<string, int> &lines)
{
    string tmp;

    while (in.good())
    {
        getline(in, tmp);

        int i = 0;

        // trim initial space (also skips empty strings)
        for (i = 0; i < tmp.length() && !isalnum(tmp[i]); i++);
        if (i >= tmp.length()) continue;
        tmp = tmp.substr(i);

        for (i = 0; i < tmp.length(); i++)
        {
            if (!isalnum(tmp[i]))
            {
                tmp[i] = ' ';
            }

            // thus, HoNdA == Honda
            if (i == 0)
            {
                tmp[i] = toupper(tmp[i]);
            }
            else
            {
                tmp[i] = tolower(tmp[i]);
            }
        }

        // and record       the counts
        if (lines.count(tmp) == 0)
        {
            lines[tmp] = 0;
        }

        lines[tmp]++;
    }
}

// given lines->num_occurs map, reverses mapping
void reorg_by_count(map<string, int> &lines,
                                                                                multimap<int, string> &bycount)
{
    map<string, int>::iterator it = lines.begin();

    for (; it != lines.end(); it++)
    {
      bycount.insert(pair<int, string>(it->second, it->first));
    }
}

Problems I see:
My problem with your code is that you are newing a lot of stuff that should just be objects.
map<string, int> *lines = new map<string, int>();
multimap<int, string> *lines_by_count = new multimap<int, string>();

Both of these should just be plain objects.
map<string, int>        lines;
multimap<int, string>   lines_by_count;

This one fact would have caused you to be rejected. I would have seen this and I would not have read any-further into your code straight onto the reject pile. This fundamental flaw in your style shows that you are not a C++ programmer.
Next the objects you new are stored in RAW pointers. This is a dead give away that you are not an experienced C++ programmer. There should practically never be any pointers in your code. (All pointers should be managed by an object). Even though you manually do delete these two it is not done in an exception safe way (so they can still potentially leak).
You are reading a file incorrectly.
while (in.good())
{
    getline(in, tmp);

This is the standard anti-pattern for reading a file (even in C). The problem with your version is that the last successful read will read upto but not past the EOF. Thus the state of the file is still good but there is now no content left. So you re-enter the loop and the first read operation getline() will then fail. Even though it can fail you do not test for that.
I would expect to see this:
while (getline(in, tmp))
{
    // Line read successfully
    // Now I can processes it
}

Next you are showing a fundamental misunderstanding of how maps work:
    if (lines.count(tmp) == 0)
    {
        lines[tmp] = 0;
    }
    lines[tmp]++;

If you use the operator[] on a map it always returns a reference to an internal value. This means if the value does not exist one will be inserted. So there is no need to do this check. Just increment the value. If it is not their a value will be inserted and initialized for you (thus integers will be zero). Though not a big problem its usually preferable to use pre-increment. (For those that are going to say it does not matter. On integer types it does not matter. But you have to plan fro the future where somebody may change the type to a class object. This way you future proof your code against change and maintenance problems. So prefer pre-increment).
You are doing extra work you don't need to:
// trim initial space (also skips empty strings)
for (i = 0; i < tmp.length() && !isalnum(tmp[i]); i++);

The streams library already discards spaces when used correctly. Also the ';' at the end of the for. This is considered bad practice. It is really hard to spot and any maintainer is going to ask did he really mean that. When you have an empty body it is always best to use the {} and put a comment in their  {/*Deliberately empty*/}
Here you are basically lower casing the string.
    for (i = 0; i < tmp.length(); i++)
    {
        if (!isalnum(tmp[i]))
        {
            tmp[i] = ' ';
        }

You could use the C++ algorithms library to do stuff like this:
std::transform(tmp.begin(), tmp.end(), tmp.begin(), ::tolower());
                           //                       ^^^^^^^^^^^ or a custom
                           //                        functor to do the task

Const correctness.
void reorg_by_count(map<string, int> &lines, multimap<int, string> &bycount)

The parameter lines is not mutated by the function nor should it be. I would expect it to be passed as a const reference as part of the documentation of the function that you are not going to mutate it. This also helps in future maintenance as it stops people from accidentally mutating the object in a way that later code would not expect.
My final thing is I did not see any encapsulation of the concept of a car. You treated it all as lines of text. If you had invented a car object you can define how cars are read from a stream and written to a stream etc. Thus you encapsulate the concept in a single location.
I would have done something like this:
Probably still overkill.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
#include <cctype>

class Car
{
    public:
        bool operator<(Car const& rhs) const {return name < rhs.name;}
        friend std::istream& operator>>(std::istream& stream, Car& self)
        {
            std::string   line;
            std::getline(stream, line);

            std::stringstream linestream(line);
            linestream >> self.name;  // This strips white space

            // Lowercase the name
            std::transform(self.name.begin(), self.name.end(), self.name.begin(), ::tolower);
            // Uppercase first letter because most are proper nouns
            self.name[0] = ::toupper(self.name[0]);
            return stream;
        }
        friend std::ostream& operator<<(std::ostream& stream, Car const& self)
        {
            return stream << self.name << "\n";
        }
    private:
        std::string   name;
};

int main(int argc, char* argv[])
{
    if (argc < 2)
    {    exit(1);
    }
    std::ifstream      cars(argv[1]);
    std::map<Car,int>  count;

    Car  nextCar;
    while(cars >> nextCar)
    {
        ++count[nextCar];
    }

    // PS deliberately left the sorting by inverse order as an exercise.
    for(auto const& car: count) {
        std::cout << car.first << ":   " << car.second << "\n";
    }
}


Draw polygons with increasing/decreasing vertices I wrote a small program in Javascript that, when given a certain number of sides, will draw a polygon with that number of sides (i.e. 3 for a triangle, 5 for a pentagon, 8 for octagon, etc.).
The program is set on an interval that will, every second, increment the number of sides, redraw the canvas, and then draw the new polygon with the new number of sides.
The code works as intended, though I'm not entirely sure if it's working most efficiently. Was wondering if there were better ways to manage variables, draw to the screen, etc.
Here is the jsFiddle
---HTML---

    <title>Circles</title>

Sides:

    <input type='button' class='dir' id='backward' value='BACKWARD' />
    <input type='button' class='dir' id='forward' value='FOWARD' />
    <input type='button' id='start' value='Start' />
    <input type='button' id='stop' value='Stop' />
    <input type='button' id='reset' value='Reset' />

    <canvas id='canvas' width='500' height='500'></canvas>

---Javascript---
class Vector {
  constructor(x = 0, y = 0) {
    this.x = x;
    this.y = y;
  }
}

class Circle {
  constructor(x, y, radius) {
    this.center = new Vector(x, y);
    this.radius = radius;
  }
}

const input = document.getElementById("sides");
const canvas = document.getElementById("canvas");
const context = canvas.getContext("2d");
const center = {
  x: canvas.width / 2,
  y: canvas.height / 2
};
const rotateAround = 3 * Math.PI / 2;

drawCanvas();

let reverse = false;
let sides = 0;
let radius = center.y * 0.8;
let shapes = [];

function reset() {
  context.rotate(-(3 * Math.PI / 2));
  context.translate(-center.y, -center.y);
  drawCanvas();
  context.translate(center.y, center.y);
  context.rotate(3 * Math.PI / 2);
}

function draw() {
  reset();
  if (reverse) {
    if (sides != 0) {
      sides -= 1;
    }
  } else {
    sides += 1;
  }
  document.getElementById('noSides').innerText = sides;
  if (sides > 0) {
    shapes = [];
    for (let i = 0; i < sides; i++) {
      shapes.push(new Circle(0, 0, 20));
    }

    for (let i = 0; i < shapes.length; i++) {
      let x1 = radius * Math.cos(Math.PI * (i / (shapes.length / 2)));
      let y1 = radius * Math.sin(Math.PI * (i / (shapes.length / 2)));

      shapes[i].center.x = x1;
      shapes[i].center.y = y1;
    }

    for (let i = 0; i < shapes.length; i++) {
      for (let j = i + 1; j < shapes.length; j++) {
        context.beginPath();
        context.lineWidth = 0.5;
        context.moveTo(shapes[i].center.x, shapes[i].center.y);
        context.lineTo(shapes[j].center.x, shapes[j].center.y);
        context.stroke();
        context.closePath();
      }
    }
  }
}

function drawCanvas() {
  context.fillStyle = "lightgrey";
  context.fillRect(0, 0, canvas.width, canvas.height);
}

let interval;
let started = false;

function update() {
  context.translate(center.y, center.y);
  context.rotate(rotateAround);

  drawCanvas();
}

update();

document.getElementById('start').onclick = function() {
  if (started === false) {
    started = true;
    interval = setInterval(draw, 1000);
  }
}

document.getElementById('stop').onclick = function() {
  clearInterval(interval);
  started = false;
}

document.getElementById('forward').onclick = function() {
  reverse = false;
}

document.getElementById('backward').onclick = function() {
  reverse = true;
}

document.getElementById('reset').onclick = function() {
    clearInterval(interval);
    reset();
    sides = 0;
}

closePath is not complement of beginPath
You are using ctx.closePath() incorrectly. ctx.closePath() is a path function, similar to ctx.moveTo(x, y). It creates a line from the current position to previous ctx.moveTo(x, y). It is not the complement of ctx.beginPath(). There is no need to use it in this case.
Keep it Simple.
Circle & Vector
You have defined Circle, and Vector objects.
When you create the circle you pass a x, y coordinate that you use to create a Vector  and assign to circle.center.
Rather pass a Vector to the Circle. eg
constructor(center, radius) {
    this.center = center;
    ...

circle = new Circle(new Vector(x, y), 10);

Just data stores
Both the Circle and Vector objects are just data stores, they do nothing else but hold some numbers. You can simplify both to much simpler forms
const Vector = (x = 0, y = 0) = ({x, y});
const Circle = (center = Vector(), radius = 20) = ({center, radius});

This saves you 11 lines of code, without changing the behavior.
Irrelevant data.
The function draw does some odd things. You create circles yet only ever use centers. As code in Code Review questions is considered to be complete. Using circle is superfluous, just use the vectors.
Cache data
Your code recalculates all the points each time you redraw, this is a waste of time. You can either

Store all the points for each shape and use existing path points or create them if they have not yet been created.
Store the 2D path calls as a Path2D.

2D rendering
When rendering to 2D canvas context always group path calls that use the same state (color, line width, etc) should be inside the same beginPath. beginPath and stroke require GPU state changes, which is where the rendering bottle neck is, on low end devices this bottle neck is very small making even simple renders slow due to poor state change calls.
The draw call has too many roles. Setting number of sides, displaying the number of sides, generating the points, all should be part of other functions. draw should only draw nothing more. Create the shape in another function and pass that data to the draw call. Displaying side count, and changing side shape can be done at a higher level.
Avoid setInterval
You should always avoid setInterval as it often makes managing timers more complex. Use setTimeout as there is no need to hold handles as it can be stopped via semaphore.
Avoid repetition
A lot of the code has very similar parts. Good code has very little repetition. This is done by using functions to do repetitive tasks.
More often than not the repetitive code will be such over many project. Writing functions for repeated code also creates a resource that can be moved from project to project saving you hours of time typing out the same thing over and over.
JavaScript supports modules that makes code reuse easy. The rewrite shows some examples,  DOM and Maths utils that would normally be in modules and imported. See rewrite comments
UI
Make the UI smart, buttons that can not or should not be used should be disabled. The disabled status of buttons also give the user feedback as to  the state of the app.
The rewrite maps the buttons to an object called actions which is in effect the interface to the app. Not only can  The user call actions, the code also uses actions to reset, and stop (when sides < 1)
Rewrite
At the top & bottom there is some commented code that shows how the utilities would be imported. The DOM utils are medium level code, if you have questions use the CR comments.

"use strict"; // not required when using modules
setTimeout(() => { // timeout only for CR snippet so that code is parse before execution
                   // Note I did not indent timeout as there is not much room for snipper

/* To use modules the imports would be. See bottom of snippet */
// import {query, listener, elements} from "./DOM/utils.jsm";
// import {constants} from "./Maths/constants.jsm";
// import {Vec2} from "./Maths/constants.jsm";

const ctx = query("#canvas").getContext("2d");
const center = Vector(ctx.canvas.width / 2, ctx.canvas.height / 2);

const rotate = - Math.PI / 2;
const shapes = [];
var sidesStep = 1;
var sides = 1;
var radius = center.y * 0.8;
var started = false;

const actions = {
    updateBtnStates() {
        btns.start.disabled = started;
        btns.stop.disabled = !started;
        btns.forward.disabled = sidesStep > 0;
        btns.backward.disabled = sidesStep < 0 && sides > 1;
    },
    start() {
        if (!started) {
            started = true;
            update();
        }
        actions.updateBtnStates();
    },
    stop() {
        started = false;
        actions.updateBtnStates();
    },
    reverse() {
        sides -= sidesStep;
        sidesStep = -sidesStep;
        actions.updateBtnStates();
    },
    forward() { actions.reverse() },
    backward() { actions.reverse() },
    reset() {
        sidesStep = 1;
        sides = 1;
        actions.stop();
        update(true);
    },
}
const btns = elements({
    start: "#startBtn",
    stop: "#stopBtn",
    forward: "#forwardBtn",
    backward: "#backwardBtn",
    reset: "#resetBtn",
});
Object.entries(btns).forEach(([name, el]) => listener(el, "click", actions[name]));

actions.reset();

function createShape(sides, r = radius) {
    const shape = [];
    var i = sides;
    while (i-- > 0) {
        const ang = (i / sides) * TAU;
        shape.push(Vector(Math.cos(ang) * r, Math.sin(ang) * r));
    }
    return shape;
}

function pathShape(points) {
    const path = new Path2D();
    var i = sides, j, p1, p2;
    while (i-- > 0) {
        j = i;
        p1 = points[i];
        while (j-- > 0) {
            p2 = points[j];
            path.moveTo(p1.x, p1.y);
            path.lineTo(p2.x, p2.y);
        }
    }
    return path;
}
function drawShape(ctx, path, pos, rotate, lineWidth = 0.5, col = "#000") {
    ctx.setTransform(1, 0, 0, 1, pos.x, pos.y);
    ctx.rotate(rotate);
    ctx.lineWidth = lineWidth;
    ctx.strokeStyle = col;
    ctx.stroke(path);
    ctx.setTransform(1, 0, 0, 1, 0, 0); // default
}
function clearCanvas(color = "lightgrey") {
    ctx.fillStyle = "lightgrey";
    ctx.fillRect(0, 0, canvas.width, canvas.height);
}

function update(once = false) {
    if (started || once) {
        !once && setTimeout(update, 1000);
        if (!shapes[sides]) { shapes[sides] = pathShape(createShape(sides)) }
        clearCanvas();
        drawShape(ctx, shapes[sides], center, rotate);
        numSidesEl.textContent = sides;
        sides += sidesStep;
        if (sides < 1) {
            sides = 1;
            sidesStep = 1;
            actions.stop();
        }
    }
}
},0); // End of timeout

/* The following would be a  Module file /DOM/utils.jsm */
const qryEl = qryEl => typeof qryEl === "string" ? query(qryEl) : qryEl;
const query = (qStr, el = document) => el.querySelector(qStr);
const listener = (eq, name, call, opt = {}) => ((eq = qryEl(eq)).addEventListener(name, call, opt), eq);
const elements = obj => (Object.entries(obj).forEach(([n, q]) => obj[n] = query(q)), obj);
// export {query, listener, elements};

/* The following would be a Module file /Maths/constants.jsm  */
// const constants.TAU = Math.PI * 2;
// export {constants};

/* The following would be a Module file  /Maths/Vec2.jsm */
// const Vec2 = (x = 0, y = 0) => ({x, y});
// export {Vec2};

/* To use modules the imports would be */
// import {query, listener, elements} from "./DOM/utils.jsm";
// import {constants} from "./Maths/constants.jsm";
// import {Vec2} from "./Maths/constants.jsm";

/* Replacements for imports constants, Vec2 */
const TAU = Math.PI * 2;
const Vector = (x = 0, y = 0) => ({x, y});

Sides:

    <button class='dir' id='backwardBtn'>BACKWARD</button>
    <button class='dir' id='forwardBtn'>FOWARD</button>
    <button id='startBtn'>Start</button>
    <button id='stopBtn'>Stop</button>
    <button id='resetBtn'>Reset</button>

    <canvas id='canvas' width='500' height='500'></canvas>

Warning Let
let in global scope is very bad.
General rule for let is. Only use it inside { blocks }, never use it in global scope.
Sorry OP the following is a little overly detailed and is in lue of the inevitable comments defending let.
A

...in 200ms expect "Hi" in console.
Another (diligent) script will crash

Another (sloppy) script can reuse b

Not crashing this script, but when the timeout (first script) callback calls b.log which is no longer a function it will throw an error.


Reservation Form in HTML I am a beginner and I have made a Reservation Form in HTML. I'm pretty sure it will look horrible to any developer out there, but hey, that's why I've posted it.

I'd like a general review of this. I'm especially concerned about the quality and enhancements of this form. What should I do to add attractive looks and to upload the input data somewhere, So that I could read it?

RESERVATION FORM

NAME<INPUT TYPE="TEXT" SIZE="20" MAXLENGTH="99" />

AGE<INPUT TYPE="TEXT" SIZE="12" MAXLENGTH="99" />

ADDRESS<INPUT

<TYPE="TEXT" SIZE="42" MAXLENGTH="99" />

EMAIL<INPUT TYPE="TEXT" SIZE="30" MAXLENGTH="99" />

TELEPHONE<INPUT TYPE="TEXT" SIZE="10" MAXLENGTH="99" />

SELECT YOUR

BERTH
<SELECT NAME="CHOICES" SIZE="3">
<OPTION>TATKAL</OPTION>
<OPTION>LADIES</OPTION>
<OPTION>GENRAL</OPTION>
</SELECT>

CITY<SELECT naME="CITY"><OPTION SELECTED>

DELHI</OPTION><OPTION>MUMBAI</OPTION><OPTION>KOLKATA</OPTION><OPTION>CHENNAI</OPTION>

<input type="submit" value="click here to submit" />
<input

type="reset" value="clear this form" />

The most obvious mistake — which makes your code malformed HTML — is the extra < before TYPE:

<P>ADDRESS<INPUT

<TYPE="TEXT" … />

The next biggest issue, in my opinion, is that your <P> tags aren't consistently being closed.  Only in the earliest days of HTML was it acceptable to use an unclosed <P> as a line break.  These days, it's generally accepted that paragraphs should lie between <P> and </P>.

The next thing you should do is to add a doctype declaration at the very beginning, which tells the browser which version of the HTML standard is being used.  Without the doctype, browsers will interpret the document in slightly non-standard ways, especially if you use CSS.  If you have no preference for any particular doctype, use HTML5:

<!DOCTYPE html>
<html>
    ...
</html>

Once you have declared a doctype, you can then run the code through an HTML validator, which will tell you everything else that is syntactially incorrect.  For example, it's OK to say

<option selected="selected">...</option

or

<option selected>...</option>

but not

<option selected="true">

HTML is case-insensitive, but you should choose either uppercase or lowercase consistently anyway.  Since XHTML mandates lowercase, I recommend using lowercase everywhere too, even if you are using HTML instead of XHTML.

Oddly, your form has no <form> tag.


Reconstruct a string, given a list of subsequence triplets I wrote a solution to this CodeWars challenge:

  There is a secret string which is unknown to you. Given a collection of random triplets from the string, recover the original string.

  A triplet here is defined as a sequence of three letters such that each letter occurs somewhere before the next in the given string. "whi" is a triplet for the string "whatisup".

  As a simplification, you may assume that no letter occurs more than once in the secret string.

  You can assume nothing about the triplets given to you other than that they are valid triplets and that they contain sufficient information to deduce the original string. In particular, this means that the secret string will never contain letters that do not occur in one of the triplets given to you.

So, for example, given triplets [['t','u','p'], ['w','h','i'], ['t','s','u'], ['a','t','s'], ['h','a','p'], ['t','i','s'], ['w','h','s']], my code would reconstruct the secret string whatisup.  My code builds a dictionary, with each character from string as a key, and possible characters that precede the key as the value.  Then, it loops through the dictionary, building the secret string a character at a time.

def recoverSecret(triplets):
    secret = ''
    secret_dict = {}
    # any better way to build a dictionary based on relationship of triplets?
    for x in triplets:
        for y in x:
            secret_dict.setdefault(y, set()).update(x[x.index(y) - 1]) if x.index(y) != 0 else secret_dict.setdefault(y, set())

    def removeChar(c) -> dict:
        '''find first char in secret'''
        #any better way to remove element from set that is value of dictionary when value in set?
        {v.remove(c) for k, v in secret_dict.items() if c in v}

    def findChar() -> str:
        '''find first char in secret when there is no char in front of it'''
        #any better way to find character when value is dictionary is empty?
        return next(k for k, v in secret_dict.items() if not v)

    while secret_dict:
        first_char = findChar()
        #any better way to rebuild dictionary when key == k?
        secret_dict = {k: v for k, v in secret_dict.items() if k != first_char}
        removeChar(first_char)
        secret = secret + first_char
    return secret

It looks like you have implemented Kahn's algorithm for topological sorting.

By PEP 8, the official Python style guide, function names should be lower_case_with_underscores.  Also, since the code would work equally well with an n-tuples as inputs, I'd rename triplets to subsequences.

For building secret_dict, I suggest:

using collections.defaultdict(set)
iterating by index, so as to avoid calling x.index(y).

The removeChar() function does not actually return a dict, as claimed — there's no return statement!  For clarity, I'd avoid the bogus use of a set comprehension that actually surreptitiously mutates secret_dict's values as a side-effect, and just write it as a loop.

I don't think that removeChar() and findChar() need to be defined as inner functions, especially since they are both short.  The functions don't really help with code clarity, since they act on secret_dict by closure.

from collections import defaultdict

def recover_secret(subsequences):
    preceding_chars = defaultdict(set)
    for subseq in subsequences:
        for i in range(len(subseq)):
            preceding_chars[subseq[i]].update(subseq[i - 1] if i else '')

    secret = []
    while preceding_chars:
        c = next(k for k, v in preceding_chars.items() if not v)
        del preceding_chars[c]
        for prec in preceding_chars.values():
            if c in prec:
                prec.remove(c)
        secret.append(c)
    return ''.join(secret)


Mixing Watir::Browser into RSpec In my previous Watir question I was making a module with session_FF accepting a block.
Now I want to make the same but via RSpec. Here is my try:

require "rspec"
require "watir"

module Session_FF
  def method_missing m, *args, &block
    @browser.send m, *args, &block
  end
  def element *args
    elements = @browser.elements *args
    case elements.size
    when 1 ; elements.first
    when 0 ; raise "found no nodes using search args: #{args}"
    else   ; raise "found #{es.size} nodes -- use #elements method or improve args"
    end
  end
end

RSpec.configure do |config|
  config.include Session_FF
  config.before{ @browser ||= Watir::Browser.new :ff}
  config.after{ @browser.quit }
end

describe "it" do
  it "is alive" do
    goto "http://example.com/"
    element(class: "userpanel").click
  end
end

I see a problem, that previously I was defining method_missing in my own module but now include may redefine RSpec::Core::ExampleGroup or smth's #method_missing if it already exists or may appear in RSpec implementation. What is a better way for method_missing approach to forward browser interaction methods into @browser?

As far as I can tell, you have 4 options:

Use the current code as-is (and, as you say, risk stepping on an existing method_missing).
You can use RSpec's config.extend to at least limit the inclusion.
You can skip method_missing in favor of creating a module explicit method declarations for anything you want to forward to @browser. This is no doubt the safest, but also the most laborious, solution. Still, I'd consider it
You can do something like below, which, admittedly, is somewhat hacky.

module Session_FF

  # Alias existing method_missing implementation when being included
  def Session_FF.append_features(target)
    if target.instance_methods.include?(:method_missing)
      target.send(:alias_method, :overriden_method_missing, :method_missing)
    end
    super
  end

  # Define your own method_missing which forwards to @browser
  # or to the previous method_missing (if any)
  def method_missing(name, *args, &block)
    if @browser.respond_to?(name)
      @browser.send(name, *args, &block)
    elsif respond_to?(:overriden_method_missing)
      overriden_method_missing(name, *args, &block)
    end
  end

  def element(*args)
    # ...
  end

end

Should work, although if @browser also relies on method_missing without a reliable respond_to?, you might have better luck simply trying to call a method @browser and rescue a NoMethodError. Not very pretty, though.

On a side-note, I think it's perhaps a little strange that the module is named _FF when the @browser could be something other than Firefox. WatirSession might be  a more inclusive name.


Simple application to look up items in a list I'm very new to the programming world and have been working exclusively with console window applications in C# thus far. I've created a program which took me way too long to produce but I'm very proud to have completed it exactly as I set out to make it. It does what I wanted it to do, however the code is separated into many different methods. Again, being a newbie, I don't know a lot about formatting my code for readability's sake, so I'd love to have some outside opinions about what you would change, if anything, about the text so that I may be pointed in the right direction for future applications I create.

class Program
{

    public static string Name { get; set; }

    public static void Main()
    {
        Console.Write("Please Enter Your Name: ");
        Name = Console.ReadLine();
        SearchBarStart(Name);
    }

    public static void SearchBarStart(string searchName)
    {
        Console.WriteLine("Welcome, {0}", searchName);
        Thread.Sleep(1000);

        SearchChecker();

    }

    public static void SearchBar(string searchName)
    {
        Console.Clear();
        Console.WriteLine("Welcome back, {0}", searchName);
        Thread.Sleep(1000);

        SearchChecker();
    }

    public static void SearchChecker()
    {
        Item Ball = new Item() { Name = "Ball", Price = 100.001F, Popularity = 1 };
        Item Book = new Item() { Name = "Book", Price = 210.1F, Popularity = 5 };
        Item Bag = new Item() { Name = "Bag", Price = 300F, Popularity = 4 };

        List<Item> items = new List<Item>();
        items.Add(Ball);
        items.Add(Book);
        items.Add(Bag);

        string userChoice = string.Empty;

        do
        {
            Console.Write("Please enter which item would you like to view: ");
            userChoice = Console.ReadLine();

            Item resultItem = items.Find(item => item.Name == userChoice);

            if (resultItem == null)
            {
                Console.WriteLine("Item name not valid");
                SearchChecker();
            }
            else
            {
                Console.WriteLine("Item Name: {0}\n" +
                    "Item Price: {1:C}\n" +
                    "Item Popularity Hits: {2}\n",
                    resultItem.Name, resultItem.Price, resultItem.Popularity);
            }
            Console.WriteLine("Would you like to continue? (yes/no)");
            userChoice = Console.ReadLine();
        }
        while (userChoice == "yes");

        Exit();
    }

    public static void Exit()
    {
        Console.WriteLine("Are you sure? (yes/no)");
        string answer = Console.ReadLine();

        if (answer == "yes")
        {
            Console.WriteLine("Press enter again to exit");
            Console.ReadLine();
        }
        else if (answer == "no")
        {
            SearchBar(Name);
        }
        else
        {
            Console.WriteLine("Sorry, I don't recognize {0}\n", answer);
            Exit();
        }

    }
}

class Item
{
    public string Name { get; set; }
    public float Price { get; set; }
    public int Popularity { get; set; }
}

First, I'm going to show you some interesting points.

1. The callstack

You're calling some methods recursively. A recursive method calls itself. See in SearchChecker() and Exit() where those methods call themselves, eg. SearchChecker() calls SearchChecker() again and Exit() calls Exit() again.

What will happen if you call it recursively? See the callstack. The picture below shows what happens when I repeatly entering wrong items. I put a break point in the line where it prints "item name not valid". I marked the callstack in a red box. See it repeatedly calling SearchChecker(). Same thing happens in second picture when Exit() is calling itself recursively by entering wrong answer (yes/no).

2. A bug when you're trying to exit the program because of recursion

This only happens if you do what I did in number 1. Add 2 lines in the Main method so it looks like:

public static void Main()
{
    Console.Write("Please Enter Your Name: ");
    Name = Console.ReadLine();
    SearchBarStart(Name);
    Console.WriteLine("Press any key...");
    Console.ReadKey(true);
}

Try these steps:

Enter name
When asked what items you want, repeat wrong answer 2 times, eg. entering "z" 2 times
Enter a correct item in the 3rd attempt, eg. "Ball"
Program shows the item information.
When asked if you want to continue, choose "no"
When asked if you are sure, choose "yes"
You're asked to press enter again. Press enter.
Program should exit, but it asked if you would like to continue again. Do step 5 till 7 till the program exits.

This bug happens because of the callstack. Your program entry point is Main() method, so it ends when Main() reaches its last line. But the callstack is long (see pic #1 and #2) and it should exit each callstack before reaching back to Main().

Here's what I did to improve your code. I add some comments to make it clearer. The idea is to make each method only do a specific task. SeachCheckerStart() is the main loop for asking items, SearchChecker() is for asking and displaying item, getUserItem() is for retrieving item, printItem() is for printing item info, getChoices() is for getting choice from user, getContinue() and getConfirmExit() are for asking if user wants to continue and confirm if they want to exit.

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

class Program
{
    public static string Name { get; set; }

    public static void Main()
    {
        // get user name
        Console.Write("Please Enter Your Name: ");
        Name = Console.ReadLine();
        Console.WriteLine("Welcome, {0}", Name);
        Thread.Sleep(1000);

        bool userConfirmExit;
        do
        {
            SeachCheckerStart();

            userConfirmExit = getConfirmExit(); // get user confirmation to exit
            if (!userConfirmExit)
            {
                Console.WriteLine("Welcome back, {0}", Name);
                Thread.Sleep(1000);
            }
        } while (!userConfirmExit); // repeat what's inside this until user confirmed that they want to end the program

        Console.WriteLine("Press enter again to exit");
        Console.ReadLine();

        Console.WriteLine("Press any key...");
        Console.ReadKey(true);
    }

    public static void SeachCheckerStart()
    {
        bool userContinue;
        do
        {
            SearchChecker(); // start search
            userContinue = getContinue(); // ask if user wants to continue
        } while (userContinue); // repeat this process as long as user chooses "yes"
    }

    public static void SearchChecker()
    {
        Item item = null;
        do
        {
            item = getUserItem(); // get item from user, return null if item is not valid
        } while (item == null); // repeat until user asks a valid item

        printItem(item); // show item info
    }

    public static Item getUserItem()
    {
        var items = new List<Item> // initialize the List<Item>
        {
            new Item { Name = "Ball", Price = 100.001F, Popularity = 1 },
            new Item { Name = "Book", Price = 210.1F, Popularity = 5 },
            new Item { Name = "Bag", Price = 300F, Popularity = 4 }
        };

        Console.Write("Please enter which item would you like to view: ");
        string userItemChoice = string.Empty;
        userItemChoice = Console.ReadLine();
        var item = items.Find(i => i.Name == userItemChoice);
        if (item == null)
        {
            Console.WriteLine("Item name not valid");
        }
        return item;
    }

    public static void printItem(Item item)
    {
        Console.WriteLine("Item Name: {0}\n" +
                "Item Price: {1:C}\n" +
                "Item Popularity Hits: {2}\n",
                item.Name, item.Price, item.Popularity);
    }

    public static string getChoices(string message, params string[] choices)
    {
        string choice = null;
        do
        {
            Console.WriteLine(message);
            choice = Console.ReadLine().ToLower();
            if (!choices.Contains(choice)) // if choice is not in choices
            {
                Console.WriteLine("Sorry, I don't recognize {0}\n", choice);
            }
        } while (!choices.Contains(choice)); // repeat if choice is not in choices
        return choice;
    }

    public static bool getContinue()
    {
        var choice = getChoices("Would you like to continue? (yes/no)", "yes", "no"); // ask if user wants to continue
        if (choice == "yes")
            return true; // return true if user wants to continue
        else
            return false; // return false if user does not want to continue
    }

    public static bool getConfirmExit()
    {
        var choice = getChoices("Are you sure? (yes/no)", "yes", "no"); // get confirmation if user wants to exit
        if (choice == "yes")
            return true; // return true if user confirms that they want to exit
        else
            return false; // return false if user does not confirms that they want to exit
    }
}

class Item
{
    public string Name { get; set; }
    public float Price { get; set; }
    public int Popularity { get; set; }
}

This time the callstack is clean. See the red box in these 2 pics.

The bug in #2 won't happen because the callstack is clean.


Lock-free bounded stack atomics I was thinking about using very basic bounded (preallocated) stack to keep track of my threads IDs in correct LIFO order. I was wondering if my implementation is thread safe:

// we use maximum 8 workers
size_t idle_ids_stack[8];
// position current write happening at
std::atomic_uint_fast8_t idle_pos(0);

// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id)
{
    std::atomic_thread_fence(std::memory_order_release);
    idle_ids_stack[idle_pos.fetch_add(1, std::memory_order_relaxed)] = thread_id;
}

// this function can be called from anywhere at anytime
void wakeup_one()
{
    uint_fast8_t old_pos(idle_pos.load(std::memory_order_relaxed));
    std::atomic_thread_fence(std::memory_order_acquire);
    size_t id;
    do
    {
        if(old_pos == 0) return; // no idle threads in stack; exit;
        id = idle_ids_stack[old_pos-1];
    }
    while (!idle_pos.compare_exchange_weak(old_pos, old_pos-1, std::memory_order_acquire, std::memory_order_relaxed));
    // wakeup single thread
    signal_thread(id);
}

Please see latest changes: Gist

Problem 1
Consider that register_idle() is equivalent to this slightly rewritten version:
// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id)
{
    std::atomic_thread_fence(std::memory_order_release);
    uint8_t pos = idle_pos.fetch_add(1, std::memory_order_relaxed);

    // What happens when this thread stops right here?

    idle_ids_stack[pos] = thread_id;
}

If the thread stops after incrementing idle_pos, but before writing the actual thread id to the stack, you will be in trouble when another thread tries to wake up the thread at the top of stack.  It will try to read a thread id from the stack that has not yet been written.
Problem 2
(Credit @MikeMB for correcting me on my previous answer)
You have a problem in wakeup_one() as well.  Suppose idle_pos is 2 and idle_ids_stack[1] is 5.  Now consider the following sequence of events:

Thread 1 runs wakeup_one() and executes id = idle_ids_stack[old_pos-1], so at this point, id is 5.  But now thread 1 sleeps for a little while.
Thread 2 runs wakeup_one(), grabs the same id (5), and returns it, setting idle_pos to 1 in the process.
Thread 3 runs register_idle(), puts its id (3) into idle_ids_stack[1] and increments idle_pos back to 2.
Now thread 1 resumes, and compare-exchanges idle_pos from 2 to 1 successfully.  But it returns id as 5 (a duplicate thread id), instead of 3 (the proper one).


How do I avoid over-using the garbage collector? I'm wondering what the best way of initializing variables so that I don't over use the garbage collector with a for-loop.  Assuming the variable is only used inside the for-loop.  Is it better to declare the variable outside of the for-loop?

public void foo() {
    String tempName;
    for (Person person : personList) {
        tempName = person.getName();

        //Do work with name
    }
}

Or inside the for-loop?

public void foo() {
    for (Person person : personList) {
        String tempName = person.getName();

        //Do work with name
    }
}

For the Garbage Collector, it doesn't matter at all. You don't create the object. You just use an object reference to it in the above code.

The String object itself is still stored in the Person class and is therefore not garbage-collected until it is changed inside the Person object, or the Person object itself is garbage collected (which will happen when the Person does not have any more references to it).

Normally, you don't need to worry about "over-using" the Garbage Collector.

However, for the sake of readability it is a good practice to declare the variable in the smallest scope as possible. Therefore, I would go with the inside the for-loop approach.


Monte Carlo errors estimation routine I would value your opinion on the following piece of code. I am rather new to both Python and Monte Carlo analysis, so I was wondering whether the routine makes sense to more experienced and knowledgeable users.

import numpy as np
import scipy.optimize
from scipy.optimize import curve_fit
from scipy.stats import kde

def MC_analysis_a():
    x = (0.001, 0.002, 0.004, 0.008, 0.016, 0.032, 0.064, 0.128)
    y_signal_a = (1.0, 0.83, 0.71, 0.62, 0.55, 0.49, 0.45, 0.42)
    x = np.array(x, dtype = float)
    y_signal_a = np.array(y_signal_a, dtype = float)
    e_signal_a = (0.06, 0.05, 0.04, 0.05, 0.04, 0.02, 0.04, 0.03)

    def func(x, a, b):
        return a * np.exp(-b * x)

    initial_guess = [1.0, 1.0]
    fitting_parameters, covariance_matrix = curve_fit(func, x, y_signal_a, initial_guess)
    print(round(fitting_parameters[1], 2))

    # ---> PRODUCING PARAMETERS ESTIMATES

    total_iterations = 5000
    MC_pars = np.array([])

    for iTrial in range(total_iterations):
        xTrial = x
        yTrial = y_signal_a + np.random.normal(loc = y_signal_a, scale = e_signal_a, size = np.size(y_signal_a))
        try:
            iteration_identifiers, covariance_matrix = curve_fit(func, xTrial, yTrial, initial_guess)
        except:
            dumdum = 1
            continue

    # ---> STACKING RESULTS

        if np.size(MC_pars) < 1:
            MC_pars = np.copy(iteration_identifiers)
        else:
            MC_pars = np.vstack((MC_pars, iteration_identifiers))

    # ---> SLICING THE ARRAY

    print(np.shape(MC_pars))
    print(np.median(MC_pars[:,1]))
    print(np.std(MC_pars[:,1]))

The output I get is apparently satisfactory and plausible.

Before starting with feedback on the actual code, I would like to share some thoughts about the style.

Chose a style, be consistent

Python comes with an official style guide called PEP8 which summarizes a whole lot of style advice and best practices generally to be used while coding Python. If you decide to stick with PEP8 or not is up to you, but if you chose a style, e.g. for variable names, stick to it. Your code has a mix of camelCase (e.g. iTrial), snake_case (e.g. initial_guess, actually most of the code is like this and also the PEP8 recommendation) and snake_swallowed_CASE_case (e.g. MC_analysis_a).

Another recommendation of PEP8 is to omit whitespace around = when used as keyword arguments to functions/methods. Incorporating the first one the line

yTrial = y_signal_a + np.random.normal(loc = y_signal_a, scale = e_signal_a, size = np.size(y_signal_a))

would become

y_trial = y_signal_a + np.random.normal(loc=y_signal_a, scale=e_signal_a, size=np.size(y_signal_a))

The same goes for np.array(...) and friends earlier in the code.

As a final note, do your future self a favor and document what you're doing in that function in a short little description right at the beginning. You might think you will remember your thoughts when looking at it in three months, but trust me, you won't. It is as simpe as:

def mc_analysis_a():
    """Running Monte Carlo analysis on some 1D sample data

    This function uses scipy.optimize.curve_fit to estimate the parameters of
    a simple x -> y timeseries.
    """

This type of documentation has the nice feature that it will be picked up by Python's built-in help(...) function.

The code itself

At the moment, there are some unused imports in your code (namely import scipy.optimize and from scipy.stats import kde, but that might be a symptom from bringing the code here on Code Review.

The next thing that caught my attention was that you do not use the estimated covariance matrix returned by curve_fit. If you really have no use for it, replace covariance_matrix by _ (underscore). This a convention used to tell yourself and others that you don't care about that (part of the) return value.

Next up comes total_iterations = 5000 as hardcoded value. If you ever try to increase or decrease that value you would have to edit your function before rerunning the experiment. A more convenient approach from my point of view would be to use it as input parameter with an default value of 5000. The same applys to initial_guess and friends. (Sidenote: if you were to use initial_guess' current value as default value and ever modified it in the function, funny things can happen. See this link for more information on this topic, since this would get to involved for this review.)

Now to the core loop of the function. While generating the noisy y values, np.size(y_signal_a) should be equal to y_signal_a.size. In your case, one could also use y_signal.shape in that spot which would then guarantee that the noise also fits the shape of the array if it was multidimensional.

Using try: ... catch: ... without specifying an exception type is considered a bad practice since it will catch all kinds of exceptions including keyboard interupts (Ctrl+C). So if you ever decide to stop the test because 5000 iterations where to much, well, you would have to kill the Python process itself. The documentation of curve_fit lists all the exceptions that might be raised while using this function. These are ValueError for bad input data or input options and Runtime Error in case the least-squares minimization failed. So these would likely be your candidates to catch, with the following construct:

try:
    ...
catch (ValueError, RuntimeError):
    continue # or handle the exception however you want

This would still stop the execution if something unexpected has happened and, as you can see, works for multiple exceptions as well.

On the same loop you're using the NumPy array MC_pars to collect the results of those iterations step by step. As you might have noticed NumPy arrays are not really comfortable to use in an expanding way since their main purpose is to allow fast vectorized operations on "fixed" size numerical data (though their use is not limited to that). At this point using a simple Python list might be a better option. This would allow you to .append(...) the results of every run very conveniently. And, as you seem to know, it's quite easy to convert Python iterables (lists, tuples) into NumPy arrays.

For reference you can find the modified version of the total script below.

import numpy as np
from scipy.optimize import curve_fit

def mc_analysis_a(total_iterations=5000):
    """Running Monte Carlo analysis on some 1D sample data

    This function uses scipy.optimize.curve_fit to estimate the parameters of
    a simple x -> y timeseries.
    """
    x = (0.001, 0.002, 0.004, 0.008, 0.016, 0.032, 0.064, 0.128)
    y_signal_a = (1.0, 0.83, 0.71, 0.62, 0.55, 0.49, 0.45, 0.42)
    x = np.array(x, dtype = float)
    y_signal_a = np.array(y_signal_a, dtype = float)
    e_signal_a = (0.06, 0.05, 0.04, 0.05, 0.04, 0.02, 0.04, 0.03)

    def func(x, a, b):
        return a * np.exp(-b * x)

    initial_guess = [1.0, 1.0]
    fitting_parameters, _ = curve_fit(func, x, y_signal_a, initial_guess)
    print(round(fitting_parameters[1], 2))

    # ---> PRODUCING PARAMETERS ESTIMATES
    mc_pars = []
    for _ in range(total_iterations):   # i was replaced by _ here, because it was not used
        x_trial = x
        y_trial = y_signal_a + np.random.normal(loc=y_signal_a, scale=e_signal_a, size=y_signal_a.shape)
        try:
            iteration_identifiers, _ = curve_fit(func, x_trial, y_trial, initial_guess)
        except (ValueError, RuntimeError):
            continue

        mc_pars.append(iteration_identifiers)

    # ---> SLICING THE ARRAY
    mc_pars = np.array(mc_pars)
    print(mc_pars.shape)
    print(mc_pars[:, 1].std())

if __name__ == "__main__":
    mc_analysis_a(5000):


PHP date reformat function I am currently working on an app and have some issues with the date handling.
Found a simple solution, and want your opinion.
First thing, that I want to achieve:

I have 2 date format inputs, one is like 2013-09-30 14:20:00 and the other is 30/09/2013 1420
Time stamp is given with no day light saving time.

So, I have to store my date/time in DB with the same format in order to compare one with each other, and also I need to adjust the time stamp +1 hour if it is in the DST period.
For this, I made the following function:

function format_date($date_string, $date_format)
{
$unix = mktime( substr($date_string, strpos($date_format, 'HH'), 2),
                (strpos($date_format, 'ii'))? substr($date_string, strpos($date_format, 'ii'), 2) : '00',
                (strpos($date_format, 'ss'))? substr($date_string, strpos($date_format, 'ss'), 2) : '00',
                substr($date_string, strpos($date_format, 'MM'), 2),
                substr($date_string, strpos($date_format, 'DD'), 2),
                substr($date_string, strpos($date_format, 'YYYY'), 4)
            ) ;
$human = date('Y-m-d H:i:s', $unix);
$dst = date('I', $unix);

return (object)array(
                'unix' => $unix,
                'human' => $human,
                'dst' => $dst
                );
}

//Usage:
$date1 = format_date('2013-09-30 14:20','YYYY-MM-DD HH:ii');
$date2 = format_date('30/09/2013 1420','DD/MM/YYYY HHii');

echo $date1->human ;
echo '
';
echo $date2->human ;
echo '
';
//  $date1->human is the same with $date1->human, also ->unix

Maybe this will help others, but if you find something not right in this function please let me know before I put it in production.

Update: (thank you Glavić)

function format_date1($date_string, $date_format)
{
$date_build = DateTime::createFromFormat ( $date_format , $date_string  );
return (object)array(
                'unix' => $date_build->format('U'),
                'human' => $date_build->format('Y-m-d H:i:s'),
                'dst' => $date_build->format('I')
                );
}
$make_date = format_date1('30/09/2013 1420', 'd/m/Y Hi');
print_r($make_date);
//returns stdClass Object ( [unix] => 1380540000 [human] => 2013-09-30 14:20:00 [dst] => 1 )
//Use: $make_date->unix | $make_date->human | $make_date->dst

Use DateTime::createFromFormat method to convert datetime strings to DateTime object:

$date1 = DateTime::createFromFormat('Y-m-d H:i', '2013-09-30 14:20');
$date2 = DateTime::createFromFormat('d/m/Y Hi', '30/09/2013 1420');

Now you can just format your output:

echo 'unix  : ' . $date1->format('U') . "\n";
echo 'human : ' . $date1->format('Y-m-d H:i:s') . "\n";
echo 'dst   : ' . $date1->format('I') . "\n";

And you don't need to adjust timestamp for +1 hour if in DST, DateTime can handle leap years and DST correctly. Set timezone when you create DateTime object, or change timezone after.


Displaying information from shops To display all the shops, I get data from a database (Firestore) and push them into array and setState, and use map to display shops from this.state{ shops }.

This is working okay, but I am wondering if there are better ways.

export default class Shop extends Component {
  constructor(props) {
    super(props);
    this.state = {
      shops: [],
    };
  }

  async componentDidMount() {
    const querySnapshot = await db.mShopsCollection().get();
    const shops = [];
    querySnapshot.forEach((doc) => {
      const shop = {
        id: doc.id,
        address1: doc.data().address1,
        address2: doc.data().address2,
        address3: doc.data().address3,
        name: doc.data().name,
        prefecture: doc.data().prefecture,
        zip_code: doc.data().zip_code,
      };
      shops.push(shop);
    });
    this.setState({ shops });
  }

  render() {
    const { shops } = this.state;
    return (
      <View>
        {shops.map((shop) => (
          <TouchableOpacity onPress={this.handleShowMap} key={shop.id}>
            <View>
              <View>
                <Text>{shop.name}</Text>
                <Text>
                  〒
                  {shop.zip_code}
                  {'\n'}
                  {shop.prefecture}
                  {shop.address1}
                  {shop.address2}
                  {'\n'}
                  {shop.address3}
                </Text>
            </View>
          </TouchableOpacity>
        ))}
      </View>
    );
  }
}
```

There are a couple of improvements you can make in your componentDidMount.

First, you create an empty array of shops, then push to it in every iteration over the querySnapshot. When constructing an array by transforming another array (or array-like collection), the appropriate method to use is Array.prototype.map. You can get an array of documents from the snapshot by accessing its .docs property.

Second, rather than calling doc.data many times repetitively, you can make an array of properties and extract each of them from the document being iterated over, putting them into a new object with Object.fromEntries:

async componentDidMount() {
  const querySnapshot = await db.mShopsCollection().get();
  const properties = ['address1', 'address2', 'address3', 'name', 'prefecture', 'zip_code'];
  const shops = querySnapshot.docs.map((doc) => {
    const data = doc.data();
    return {
      id: doc.id,
      ...Object.fromEntries(properties.map(prop => data[prop]))
    };
  });
  this.setState({ shops });
}

Lodash's pick is another method that can be used to extract certain properties from an object into a new object.


Python BruteForce Script I have to do a Bruteforce script, so mine is working, but is also very very low.
My teacher gave me a small Shadow file and from the shadow file I have to find the original password (MD5 used here). I know that my code is working but I'm looking for tips and tricks to improve it.

import hashlib
import itertools

#possible characters in user password
Alphabet = ("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_.;#@")
#minimum password value
CharLength = 6

#getting passwords and username from shadow file
with open("shadow_test", "r") as ins:
    array = []
    users = []
    passwd = []
    #getting everyline from shadow file into an array
    for line in ins:
        array.append(line)
    #saving only username and passwords
    for pw in array:
        str(pw)
        r= pw.split(":")
        users.append(r[0])
        passwd.append(r[1])
    # print(users)
    # print(passwd)

    list = []
    #removing passowrd with * or !
    for mdp in passwd:
        if mdp != '*' and mdp != '!':
            str(mdp)
            list.append(mdp)
            # trying to Bruteforce
            for _ in range(12):
                passwords = (''.join(word) for word in itertools.product(Alphabet, repeat=CharLength))

                #print(*passwords)
                for pswd in passwords:
                    hash_object = hashlib.md5(str.encode(pswd)).hexdigest()
                    # hash_object.update(*passwords.encode('utf-8'))
                    generatedpassword = '$1$' + hash_object
                    # print(generatedpassword)

                    for compare in list:
                        for user in users:
                            #print('on cherche le Mot de passe : ' + compare +' pour ' +user)
                            #print('mot de passe MD5 généré : ' +generatedpassword)
                            #print('mot de passe clair généré : ' +pswd)

                            if generatedpassword == compare:
                                print('Le Mot de passe pour' + user + ' est : ' + pswd)

Use capital letters with underscores for constants https://pep8.org/#constants
There is no need to wrap alphabet string into parentheses:

ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_.;#@"
LENGTH = 6

Expression str(pw) does nothing so you can remove it. You probably meant pw = str(pw) but it is redundant since pw already is str
You do not need array variable at all, just iterate over input file line by line. Also, unpacking is more readable:

    for line in ins:
        user, password, *rest = line.split(":")
        users.append(user)
        passwd.append(password)

Since you ignore passwords "*" and "!" it is better to filter them out when reading from file.
Since ins is not used after generating users and passwd lists you do not need to place rest of code inside with block. Actually, the first block may look like:

#getting passwords and username from shadow file
with open("shadow_test", "r") as ins:
    users = []
    passwd = []
    for line in ins:
        user, password, *rest = line.split(":")
        if password not in ('*', '!'):
            users.append(user)
            passwd.append(password)

Why do you need for _ in range(12) loop? Just to make the program 12 times slower? Remove it.
Do not use names of built-in funciton names for variables, like list. BTW, why do you need it at all? Just iterate over all possible words and look for their hash in passwd:

passwords = (''.join(word) for word in itertools.product(ALPHABET, repeat=LENGTH))
for pswd in passwords:
    # calculate hash of pswd and if it is equal to one in passwd print it

When you compare generated hash with elements of passwd you do not need to iterate over all usernames and print them all! Actually it is better to make "password hash" -> "username" dictionary so you can check if generatedpassword is one of given password hashes faster (because checking that dict has a key generally is faster than checking each element of array):

with open("shadow_test", "r") as ins:
    data = dict()
    for line in ins:
        username, password, *rest = line.split(":")
        if password not in ('*', '!'):
            data[password] = username

password_hash = md5hash("qwerty")  # assume it is a function for calculating md5
if passwod_hash in data:
    print("qwerty is password of", data[password_hash])

It is probably better to remove "$1$" from stored records rather than add it to each calculated hash:

if password not in ('*', '!'):
    assert password.startswith("$1$"), "Expect password records to begin with $1$"
    data[password[3:]] = username  # remove $1$

So the whole solution may look like:

import hashlib
import itertools

def md5hash(char_sequence):
    string = ''.join(char_sequence)
    hash_object = hashlib.md5(string.encode())
    return hash_object.hexdigest()

# possible characters in user password
ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_.;#@"
# password length
LENGTH = 6

# getting passwords and username from shadow file
with open("shadow_test", "r") as ins:
    data = dict()  # hash -> username mapping from shadow file
    for line in ins:
        username, password, *rest = line.split(":")
        if password not in ('*', '!'):
            data[password[3:]] = username  # remove $1$

# bruteforce
for word in itertools.product(ALPHABET, repeat=LENGTH):
    generated_hash = md5hash(word)
    if generated_hash in data:
        print('The password of user', data[generated_hash], 'is:', word)
```


An implementation of Levenshtein Distance algorithm in modern C++ Below is an implementation of Levenshtein Distance algorithm.

I am trying to use modern C++ features as much as I can, i.e. auto, no pointer / raw memory but I feel like it is a constant struggle.

Code:

#include <string_view>
#include <memory>
#include <vector>

namespace utils
{
    auto getLevenshteinDistance(std::string_view string_1, std::string_view string_2)
    {
        const auto size_1{ string_1.size() };
        const auto size_2{ string_2.size() };

        if (size_1 == 0) return size_2;
        if (size_2 == 0) return size_1;

        std::vector<std::size_t> costs(size_2);
        for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;

        std::size_t i{ 0 };
        for (const auto& itr_1 : string_1)
        {
            ++i;
            costs[0] = i + 1;
            auto corner{ i };

            std::size_t j{ 0 };
            for (const auto& itr_2 : string_2)
            {
                ++j;
                auto upper{ costs[j + 1] };

                if (itr_1 == itr_2)
                {
                    costs[j + 1] = corner;
                }
                else
                {
                    auto t{ upper < corner ? upper : corner };
                    costs[j + 1] = (costs[j] < t ? costs[j] : t) + 1;
                }

                corner = upper;
            }
        }

        return costs[size_2];
    }
}

For instance, I can't use auto when declaring my vector, because there is no std::make_vector (like make_tuple for instance).

Also I'm developing anxiety for implicit conversions; for instance I could have written

auto i{ 0 };

instead of

std::size_t i{ 0 };

But given that the value will be put into an array containing type std::size_t, I'd rather just have it be of the right type immediately. Lots of stuff like that is bothering me.

Even looping through the array by const auto& seems weird when I'm still having a count variable.. Doesn't advantage disappear, and I might as well just for (int i = 0; ..)

Any suggestions for improvements in the way of modern, good practice, and performance is appreciated.

Invalid access

There are several occurrences of out-of-range access as 1201ProgramAlarm's comment pointed out:

for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;

costs[j + 1]

return costs[size_2];

This problem can be fixed by increasing the size of costs by one.

Usage of the standard library

std::vector<std::size_t> costs(size_2);
for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;

Use std::iota:

std::vector<std::size_t> costs(size_2 + 1);
std::iota(costs.begin(), costs.end(), std::size_t{0}); // or 0_zu; see below

auto t{ upper < corner ? upper : corner };
costs[j + 1] = (costs[j] < t ? costs[j] : t) + 1;

Use std::min:

costs[j + 1] = std::min({upper, corner, costs[j]}) + 1;

auto

When you want the type of a variable to be deduced, auto is handy, because you don't have to write the type or expression twice.  When you want the type of a variable to be fixed, however, auto becomes cumbersome — so feel free to write

std::size_t i = 0;

An alternative is to use a user-defined literal: (there's a proposal P0330 Literal Suffix for (signed) size_t to add builtin literals for std::size_t)

namespace util_literals {
    constexpr std::size_t operator""_zu(unsigned long long number)
    {
        return static_cast<std::size_t>(number);
    }
}

So you can write:

using namespace util_literals;
auto i = 0_zu;

Also, instead of

for (const auto& itr_1 : string_1)

it is more common to access characters by value.  Also, itr is a misleading name for characters:

for (char c_1 : string_1)

Simplification

This check is redundant:

if (size_1 == 0) return size_2;
if (size_2 == 0) return size_1;

because the algorithm works well with empty strings.

Here's my version:

#include <algorithm>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <string_view>
#include <vector>

std::size_t Levenshtein_distance(std::string_view string_a, std::string_view string_b)
{
    const auto size_a = string_a.size();
    const auto size_b = string_b.size();

    std::vector<std::size_t> distances(size_b + 1);
    std::iota(distances.begin(), distances.end(), std::size_t{0});

    for (std::size_t i = 0; i < size_a; ++i) {
        std::size_t previous_distance = 0;
        for (std::size_t j = 0; j < size_b; ++j) {
            distances[j + 1] = std::min({
                std::exchange(previous_distance, distances[j + 1]) + (string_a[i] == string_b[j] ? 0 : 1),
                distances[j] + 1,
                distances[j + 1] + 1
            });
        }
    }
    return distances[size_b];
}

int main()
{
    std::string string_a;
    std::string string_b;
    while (std::cin >> std::quoted(string_a) >> std::quoted(string_b)) {
        std::cout << Levenshtein_distance(string_a, string_b) << '\n';
    }
}

Input:

kitten sitting
corporate cooperation
123 ""
"" ""

Output:

3
5
0
0

(live demo)


Read and replace URL from PDF file This is a code I wrote to find all URL within a PDF file and replace the one that matches the ID that I passed as a parameter.

It works as intended, but as I am a beginner on Java, I am sure there are some best practices that I am not following.

I am using the PDFBox library.

Here's the code:

Main.java

public class Main {

public static void main(String[] args) {
    if (args.length < 4) {
        System.err.println("Parameter missing from PHP");

    } else {
        Helper.getURL(args[0], args[1], args[2], args[3]);
    }

}
}

Helper.java

public class Helper {

public static void getURL(String oldreportid, String newreportid, String oldpdf, String newpdf) {
    PDDocument doc = null;

    try {
        doc = PDDocument.load(oldpdf);
        List allPages = doc.getDocumentCatalog().getAllPages();
        for (int i = 0; i < allPages.size(); i++) {
            PDPage page = (PDPage) allPages.get(i);
            List annotations = page.getAnnotations();
            for (int j = 0; j < annotations.size(); j++) {
                PDAnnotation annot = (PDAnnotation) annotations.get(j);
                if (annot instanceof PDAnnotationLink) {
                    PDAnnotationLink link = (PDAnnotationLink) annot;
                    PDAction action = link.getAction();
                    if (action instanceof PDActionURI) {
                        PDActionURI uri = (PDActionURI) action;
                        String oldURL = uri.getURI();

                        String reportID = oldURL.substring(oldURL.lastIndexOf("=") + 1, oldURL.length());
                        if (oldreportid.equals(reportID)) {
                            String newURI = "http://www.test.com/test.php?T=MQ==&F=" + newreportid;
                            System.out.println("Page " + (i + 1) + ": Replacing " + oldURL + " with " + newURI);
                            uri.setURI(newURI);
                        }
                    }
                }
            }
        }

        doc.save(newpdf);

    } catch (IOException e) {
        e.printStackTrace();
    } catch (COSVisitorException e) {
        e.printStackTrace();
    } finally {
        if (doc != null) {
            try {
                doc.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}
}

Naming

Helper, although very common, is too generic as class name. Imagine it in a package with two dozens of other classes, how would you have a hint on what it is supposed to do by browsing the package? If it was named something like PdfAnalyzeHelper or PdfProcessingHelper, that would be better.
Looking at the name of the method getURL(args), I was expecting to find a return value instead of void, which was confusing. The prefix get* in method names is often used for getters. Since this method does not return anything and executes some URL processing, that should be called, for example, replaceReportIdInUrls(args).

SRP

The single responsibility principle seems to be violated in this method. I see three distinct things done:

Loading a PDF file.
Reading the file and replacing values in URLs.
Saving a new PDF file.

I'd suggest to split it into three distinct methods. It will be easier to maintain and reuse, if this is intended. Or, since the I/O with PDDocument is very concise, remove it from the method body and change the signature to

public static PDDocument replaceReportIdInUrls(PDDocument doc,
                                               String reportIdOld,
                                               String reportIdNew);

try-with-resources

The I/O with finally { doc.close(); } is plain old before-Java-7 style. It can be simplified for

try (PDDocument doc = PDDocument.load(oldpdf)) {
     // method body
} catch (IOException | COSVisitorException e) {
     // multicatch is also helpful!
}

This shortens the method for at least 12 lines!

Generics

The version of PDFBox that you use seems to be a legacy one, PDDocumentCatalog.getAllPages() somehow returns an unbound List.
In order to (at least) avoid compilation warnings, type bounds should be added, for example:

List<?> allPages = doc.getDocumentCatalog().getAllPages();

According to the javadoc, the list should contain PDPage objects, so if you dare rely on it, you can try a cast to List<PDPage>.

The same comment concerns the next List of annotations. Strangely, the javadoc describes it as typed, so only <PDAnnotation> should be added to the declaration.

For Loops

The j index of the inner loop is not reused, so it would be simpler to rewrite the loop:

for (PDAnnotation annotation : annotations) { ... }

and this will make useless the call annotations.get(j);

The same is about the outer loop, but since the i index is reused for the output, it can be kept.

Validation

The line

String reportID = oldURL.substring(oldURL.lastIndexOf("=") + 1, oldURL.length());

is not secured against the case when the URL does not contain the "=" character. oldURL.lastIndexOf("=") may return -1, in such case a StringIndexOutOfBoundsException will be thrown.

By the way, no validation at all is done for the method input params. What happens if one of them is null or empty?


Computing the de Bruijn sequence I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is a power of two. So the sequence must contain every possible subsequence of length \$N\$ from \$0\$ to \$2^n\$ as a sequence of consecutive characters exactly once.

I need to use only 2 digits (0 and 1) with a length \$N \le 20\$ so \$B(2, N)\$.

The idea is quite simple, I have implemented it but I have time restriction 0.5 sec and from \$N=16\$ to \$N=20\$ I will get Time Limit Exceeded (I didn't submit the code yet because that programming contest web evaluator is not working at the moment). Using my computer I get for \$N=15\$ somewhere between \$0.2\$ to
\$0.3\$ seconds but for \$N=16\$ I get \$1.180\$ seconds which is not good at all.

  Prefer Ones rule: Write \$n\$ zeros. Then, always write a one unless it would cause the repetition of an \$n\$-length string; otherwise, write a zero.

This is my code without libraries declaration:

int construct(int n, string ans){
    int number=0, poz=0;
    for(int i=ans.length()-n; i<ans.length(); ++i, ++poz)
        if(ans[i]=='1')
            number ^= (1<<poz);
    return number;
}

int main ()
{
    int n, aux, usedN=1; // usedN counts the combinations
                         // I created in my sequence (till 2^n)
    fin>>n;
    aux=n;

    bool used[(1<<n)+1];
    string ans;
    memset(used, 0, sizeof(used));
    used[0]=1; // that's why I have usedN = 1

    while(aux--)
        ans.push_back('0');

    while(usedN!=(1<<n)) {
        ans.push_back('1'); // first I try with an '1'

        int number=construct(n, ans); // I construct as a number
                                      // the new combination created
                                      // of length N
                                      // with the last added digit, the
                                      // '1' in this case to check if I already
                                      // have it in my de Bruijn sequence (in ans)
        if(used[number]==1) {
            ans.pop_back();
            ans.push_back('0');
            used[construct(n, ans)]=1;
        } else
            used[number]=1;

        ++usedN;
    }

    cout<<ans.length()<<'\n'<<ans;
    return 0;
}

I'm mostly looking for optimizations so that my running time gets considerably slower, but feedback on all other aspects of my code would be great too!

The 'prefer-1' algorithm works by having a current word, shifting out the first bit and then appending a new bit.

Such a current word - which essentially represents the tail of the sequence constructed thus far - could be housed in a machine word (word-sized variable or register) for lengths up to 32 or 64 bits. The new bit that you decide on during each iteration can then be converted to text and appended to the answer, which would obviously have been initialised to the textual representation of the all-0 word before the loop.

Your implementation does not keep such a current word. Instead you reconstruct the current word at each step from the textual representation of the sequence, by looking at its tail.

If you remove this inefficiency then your code ought to be fast enough to beat the generous timeout.

Also, your code can benefit from a bit of refactoring - moving the code for constructing the sequence out of main() into its own function - and from a thorough spring cleaning.

E.g. the expression (1<<n) does not change during the computation but you recompute for every iteration of the outer loop. usedN looks ugly and is not very informative; what about words_found? Or change things around to

for (unsigned words_to_find = 1u << n - n; words_to_find--; )
{
   ...
}

This must work since you find exactly one new word during each iteration. The term is (1 << n) - n because n characters have already been appended to the output sequence; other loop structures are possible but then the loop logic would have to be adapted.

Try to change your code so that it reads more like a description of what you're doing. Including asserts can help clarify things both for you and the reader, and it can help finding mistakes early.

For example, the 'prefer 1' algorithm implies that if the new word with a 1 already exists, then swapping the 1 for a 0 must result in word that does not exist yet. Assuming the current new word to be housed in a variable current_word:

if (used[current_word])
   current_word &= ~1u;  // change the new bit to zero

assert(not used[current_word]);
used[current_word] = true;

ans.push_back('0' + (current_word & 1u));

Or, if you enjoy terse code:

current_word ^= used[current_word];
...

But then you need to be careful about only writing strict 1 (i.e. true) into the array. Other non-zero values would also evaluate to true in conditions but they would completely mess up the terse code.

For an example that uses an integer working variable I'm appending a simple, straightforward Delphi rendition of the code (since I need to learn Delphi ATM). It clocks about 50 ms for n = 20, and a C++ version should be even faster. The code can be made significantly faster still for higher n, by using a packed bitmap and preallocating the result string (i.e. calling reserve() in C++).

function DeBruijn_sequence (n: Cardinal): string;
var
   seen: array of Boolean;
   bits: Cardinal;
   mask: Cardinal;
   i: Cardinal;
   w: Cardinal;
begin
   bits := 1 shl n;
   mask := bits - 1;
   assert(bits <> 0);
   SetLength(seen, bits);
   result := StringOfChar('0', n);
   w := 0;
   for i := n + 1 to bits do begin
      seen[w] := true;
      w := ((w shl 1) or 1) and mask;
      if seen[w] then begin
         w := w and not 1;
         assert(not seen[w]);
      end;
      result := result + Char(Byte('0') + (w and 1));
   end;
end;


Transferring data from one file stream to another I am currently reading Clean Code and for fun and profit, I intended to refactor some of the Java Tutorials and since I wanted to improve my Exception handling, the Byte Stream one with its lots of IOExceptions seemed nice.

This code does work, but is it better now? As far as I can tell it's more readable now, though there are much more methods. Can someone more experienced with clean code tell me what to improve on this?

This code just copies bytes from one file to another:

public class Tutorial {

    public static void copyBytes() {

        FileInputStream input = getNewFileOutputStream();
        FileOutputStream output = getNewFileInputStream();

        try {
            transferBytesFrom(input, output);
        } finally {
            closeStreams(input, output);
        }
    }

    private static void closeStreams(FileInputStream input, FileOutputStream output) {
        try {
            input.close();
            output.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static void transferBytesFrom(FileInputStream input, FileOutputStream output) {
        int singleByte;

        while ((singleByte = readByteFrom(input)) != -1) {
            writeByteTo(output, singleByte);
        }
    }

    private static void writeByteTo(FileOutputStream output, int singleByte) {
        try {
            output.write(singleByte);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static int readByteFrom(FileInputStream input) {
        try {
            return input.read();
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println(e.getMessage());
        }

        return -1;
    }

    private static FileOutputStream getNewFileInputStream() {
        try {
            return new FileOutputStream("output.txt");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println(e.getMessage());
        }

        return null;
    }

    private static FileInputStream getNewFileOutputStream() {
        try {
            return new FileInputStream("xanadu.txt");
        } catch (FileNotFoundException e) {
            System.out.println("ERROR: Input file not found!");
        }

        return null;
    }
}

Work with top level classes

Currently, your code only works for file related operations, as seen by the signature of transferBytesFrom.

transferBytesFrom(FileInputStream input, FileOutputStream output)

However, such an operation ought to work for every InputStream and every OutputStream, not just for file streams.

As such, it would be preferable to make all of your methods as generic as possible and let them take Input/OutputStream as arguments, or let them return Input/OutputStream:

private static void transferBytesFrom(InputStream input, OutputStream output)

private static void writeByteTo(OutputStream output, int singleByte)

private static int readByteFrom(InputStream input)

private static InputStream getNewFileOutputStream()

// ... the same for the other methods

The important goal here is that a code as generic as possible is a code that can be reused, and also a code that can evolve more simply. If you were to change your requirement and make your class handle other types of streams (and not files), you would have to rewrite everything.

try-with-resources

Starting with Java 7, you can use the try-with-resources statement to handle the automatic closing of the resources. This will prevent you from any tricky bugs, like this one:

private static void closeStreams(FileInputStream input, FileOutputStream output) {
    try {
        input.close();  // <--- imagine this throws an exception
        output.close();
    } catch (IOException e) {
        e.printStackTrace();  // <--- we go here. Ooops! output was never closed!
    }
}

Using this statement, you can have

public static void copyBytes() {
    try (
        InputStream input = getNewFileOutputStream();
        OutputStream output = getNewFileInputStream();
    ) {
        transferBytesFrom(input, output);
    } catch (IOException e) {
        // do something meaningful here
    }
}

This will ensure that whatever happens inside the try block, each stream is properly closed.

This also means that your closeStreams isn't really needed, because it will be done automatically.

Separation of concern

Let's look at your 2 methods getNewFileOutputStream and getNewFileInputStream. Their goal, as stated by their (good!) name is to retrieve a FileOutputStream and a FileInputStream. However, they currently do more than that. They currently handle the exceptions that can happen, and return null in that case.

Returning null when there is an exception is generally a code-smell: it indicates that something wrong happened, the method where this went wrong doesn't know what to do so it returns null. This creates bugs and, in fact, you have one in that case: if the files can't be opened for reading / writing, you will throw a NullPointerException later on. This is a problem: you want to fail as fast as possible and not let your code crash a couple of methods down with an unrelated and sometimes hard to debug exception, when it could have handled it before that.

So in this case, do not return null when there is an exception. In fact, I would let the method throw the checked exception. Its concern was "get me a InputStream; if it can't do that, it should throw.

In light of that, you can refactor your method to:

private static InputStream getInputStream() throws IOException {
    return new FileInputStream("xanadu.txt");
}

There are important comments here:

The method was renamed getInputStream: the global goal here is to copy bytes between streams and this goes in-line with the first point; we don't need to restrict ourselves to files. Let's go all the way and be as generic as possible.
The method returns the generic InputStream instead of the specific FileInputStream for the same reason.
The method declares to throws IOException: it isn't its purpose to decide what to do when an input stream can't be retrieved so it lets this condition be handled by whoever is calling it. Note that in this case, it will be handled automatically by the try-with-resources introduced earlier.

Essentially, the same comments apply for your other methods, so you could have:

private static void writeByteTo(OutputStream output, int singleByte) throws IOException {
    output.write(singleByte);
}

private static int readByteFrom(InputStream input) throws IOException {
    return input.read();
}

Putting it all together

With all those modifications, you would have:

public static void copyBytes() {
    try (
        InputStream input = getInputStream();
        OutputStream output = getOutputStream();
    ) {
        transferBytesFrom(input, output);
    } catch (IOException e) {
        // do something meaningful here
    }
}

private static void transferBytesFrom(InputStream input, OutputStream output) throws IOException {
    int singleByte;
    while ((singleByte = readByteFrom(input)) != -1) {
        writeByteTo(output, singleByte);
    }
}

private static void writeByteTo(OutputStream output, int singleByte) throws IOException {
    output.write(singleByte);
}

private static int readByteFrom(InputStream input) throws IOException {
    return input.read();
}

private static OutputStream getOutputStream() throws IOException {
    return new FileOutputStream("output.txt");
}

private static InputStream getInputStream() throws IOException {
    return new FileInputStream("xanadu.txt");
}

Each method now has a clear goal and doesn't handle unnecessary exceptions. All potentials exceptions are left for the main method copyBytes to handle. Arguably, this is where it should be: this is the method responsible for organizing the work. A user calling that method shouldn't have to handle an IOException: the streams were opened and closed by this method alone, so it should be the one handling the exceptional circumstances; a caller shouldn't have to handle an exception for a scenario it didn't create in the first place.

There's still the question of what this method should do in the case of an exception. This answer really depends on your requirement then:

it could rethrow a custom exception like CopyFailedException and have as cause the IOException. The advantage is that this exception isn't coupled with the fact we're doing IO here. A caller doesn't know that we're doing IO, but it knows that we're copying something, so it makes sense to tell the caller that the copy operation failed with a custom exception.
it could log the error and do nothing else. The logging ensures that the exception is properly traced somewhere.

As a side-note, when you will reach the NIO.2 API in the Java tutorials, you will find that all of this code can be replaced with a simple call to Files.copy(source, target)

Files.copy(Paths.get("xanadu.txt"), Paths.get("output.txt"));

This method will directly copy the path "xanadu.txt" into "output.txt". It also takes a 3rd argument as a vararg that corresponds to CopyOptions. A useful one could be StandardCopyOption.REPLACE_EXISTING that tells the method to replace the target file if it already exists.