Adding two binary-coded-decimal numbers I want to make some VHDL code open source. But before I do, I want to make sure that it is as readable as possible. Things to improve upon could for example be naming and the use of comments.

The code is adding two binary-coded-decimal numbers. The algorithm behind it will come in the documentation. Note that this isn't the default way to add BCD numbers.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity BCD_adder is
    generic(
        --BCD_ADD_DEC_SIZE is the amount of decimal digits. e.g. BCD_ADD_DEC_SIZE = 4 means the highest representable integer is 9999
        BCD_ADD_DEC_SIZE : integer := 3
    );
    port(
        --input and output ports
        BCD_add_a_i, BCD_add_b_i : in STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
        BCD_add_sum_o : out STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
        BCD_add_clk_i, BCD_add_cin_i : in STD_LOGIC;
        BCD_add_cout_o : out STD_LOGIC
    );
end entity;
architecture behavioral of BCD_adder is
    signal BCD_a, BCD_b : unsigned(4*BCD_ADD_DEC_SIZE downto 0);
    signal BCD_sum : STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
    signal BCD_cout : STD_LOGIC;

    --increment6: a function to increment a 4 bit STD_LOGIC_VECTOR by 6.
    function increment6 (number : STD_LOGIC_VECTOR(3 downto 0)) return STD_LOGIC_VECTOR is
    begin
        return ((number(3) or number(2) or number(1)) & ((number(2) or number(1)) nand (number(2) nand number(1))) & not(number(1)) & number(0));
    end function;

    --decrement6: a function to decrement a 4 bit STD_LOGIC_VECTOR by 6.
    function decrement6 (number : STD_LOGIC_VECTOR(3 downto 0)) return STD_LOGIC_VECTOR is
    begin
        return ((number(3) and number(2) and number(1)) & (number(2) xor number(1)) & not(number(1)) & number(0));
    end function;
begin
    process(BCD_add_clk_i)

        --BCD_SIZE is the amount of binary digits that are needed for the BCD number. Each decimal digit is 4 bits, so 4*BCD_ADD_DEC_SIZE.
        constant BCD_SIZE : integer := 4*BCD_ADD_DEC_SIZE;
        variable cin : STD_LOGIC;
        variable a, b, sum : unsigned(BCD_SIZE downto 0);
    begin
        if rising_edge(BCD_add_clk_i) then

            --Put the inputs in the variables, add a leading '0' to store a later carry.
            BCD_a <= unsigned('0' & BCD_add_a_i);
            BCD_b <= unsigned('0' & BCD_add_b_i);
            cin := BCD_add_cin_i;
            a := BCD_a;
            b := BCD_b;

            --increment every decimal digit of operand b by 6
            for i in 0 to BCD_ADD_DEC_SIZE-1 loop
                b(4*i+3 downto 4*i) := unsigned(increment6(STD_LOGIC_VECTOR(b(4*i+3 downto 4*i))));
            end loop;

            --add a, b and the carry_in to form a temporary sum that needs to be corrected
            sum := a + b + ("" & cin);

            --correction: if the sum of two decimal digits exceeded 9, subtract 6 from the temporary sum
            for j in 0 to BCD_ADD_DEC_SIZE-1 loop
                if (sum(4*j+4) = (a(4*j+4) xor b(4*j+4))) then
                    sum(4*j+3 downto 4*j) := unsigned(decrement6(STD_LOGIC_VECTOR(sum(4*j+3 downto 4*j))));
                end if;
            end loop;

            BCD_sum <= STD_LOGIC_VECTOR(sum(BCD_SIZE-1 downto 0));
            BCD_cout <= sum(BCD_SIZE);
        end if;

        --assign outputs. If the sum has a carry out of '1', BCD_add_cout_o will be set to '1'.
        BCD_add_sum_o <= BCD_sum;
        BCD_add_cout_o <= BCD_cout;
    end process;
end behavioral;

Overall, its not too bad, but I do have some suggestions for readability. What I like to do is add white-space to make elements line up with each other. For example, for this line:

BCD_add_a_i, BCD_add_b_i : in STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
BCD_add_sum_o : out STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
BCD_add_clk_i, BCD_add_cin_i : in STD_LOGIC;
BCD_add_cout_o : out STD_LOGIC

I'd do something like this:

BCD_add_a_i    : in  STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
BCD_add_b_i    : in  STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
BCD_add_sum_o  : out STD_LOGIC_VECTOR(4*BCD_ADD_DEC_SIZE-1 downto 0);
BCD_add_clk_i  : in  STD_LOGIC;
BCD_add_cin_i  : in  STD_LOGIC;
BCD_add_cout_o : out STD_LOGIC

I think it makes large blocks of text like that a smidge easier to read.

For the increment/decrement functions, I'd split up the big or/and/nand statements with variables. It ultimately doesn't affect much synthesis-wise, but again makes a bit easier to read. I'd also be consistent on whether you use the '&' operator or 'and' operator, rather than switching throughout the statement.

For this statement:

b(4*i+3 downto 4*i) := unsigned(increment6(STD_LOGIC_VECTOR(b(4*i+3 downto 4*i))));

I'd find a way to make that a little less ugly, but I'm not strictly sure how. It might have to be one of those necessary evil type of things, but cleaning that up would be really nice. Maybe do the SLV/unsigned typecasting within the increment/decrement functions.

I'm not too fond of the sorta-Hungarian notation thing for ports and signals, but that's more a personal thing than a readability thing.


A package for outer-package communications By outer-package, I mean outside of this package - this can be the DOM or other packages.  This package has a basic event system and a basic registry.  It also has a debugger which allows you to fiddle with the DOM by removing and adding entire sets of tags.  Later it might have things which allow it to Debug /  Configure the server via ajax.

Please review all aspects of this code.

/***************************************************************************************************
    **COMS
    **  provides registry, event system, debugger ...
    **  reduces dependencies
    ***************************************************************************************************/

    (function () {
        "use strict";
        var $A,

            // public
            $P = {};

        // require utility
        (function manageGlobal() {
            if (window.$A && window.$A.pack && window.$A.pack.utility) {
                $A = window.$A;
                $A.pack.comms = true;
            } else {
                throw "comms requires utility module";
            }
        }());
        $P.Debug = (function () {
            var publik = {},
                hold = {};
            publik.addTags = function (tag) {
                if (hold[tag]) {
                    $A.someIndex(hold[tag], function (val) {
                        if (tag === 'script' || tag === 'style') {
                            document.head.appendChild(val);
                        } else {
                            document.body.appendChild(val);
                        }
                    });
                }
            };
            publik.removeTags = function (tag) {
                var styles = document.getElementsByTagName(tag),
                    i;
                hold[tag] = [];
                for (i = styles.length; i; i--) {
                    hold[tag][i] = styles[i];
                    $A.removeElement((styles[i]));
                }
            };
            publik.removeStorage = function () {
                localStorage.clear();
                sessionStorage.clear();
            };
            return publik;
        }());

        // a basic registry pattern with get/set and getMany/setMany
        $P.Reg = (function () {
            var publik = {},
                register = {};
            publik.get = function (key) {
                return register[key];
            };
            publik.set = function (key, value) {
                register[key] = value;
            };
            publik.setMany = function (o) {
                $A.someKey(o, function (val, key) {
                    register[key] = val;
                });
            };
            publik.getMany = function () {
                return register;
            };
            return publik;
        }());

        // a basic event system using an internal bus
        $P.Event = (function () {
            var publik = {},
                events = {};
            publik.add = function (name, callback) {
                if (!events[name]) {
                    events[name] = [];
                }
                events[name].push(callback);
            };
            publik.remove = function (name, callback) {
                if (name && callback) {
                    delete events[name][callback];
                } else if (name) {
                    delete events[name];
                }
            };
            publik.trigger = function (name) {
                if (events[name]) {
                    $A.someIndex(events[name], function (val) {
                        val();
                    });
                }
            };
            return publik;
        }());
        window.$A = $A.extendSafe($A, $P);
    }());

The below code would be cleaner with object literal notation :

    // a basic registry pattern with get/set and getMany/setMany
    $P.Reg = (function () {
        var publik = {},
            register = {};
        publik.get = function (key) {
            return register[key];
        };
        publik.set = function (key, value) {
            register[key] = value;
        };
        publik.setMany = function (o) {
            $A.someKey(o, function (val, key) {
                register[key] = val;
            });
        };
        publik.getMany = function () {
            return register;
        };
        return publik;
    }());

would be

    // a basic registry pattern with get/set and getMany/setMany
    $P.Reg = (function () {
        var register = {};
        return {
            get : function (key) {
                return register[key];
            },
            set : function (key, value) {
                register[key] = value;
            },
            setMany : function (o) {
                $A.someKey(o, function (val, key) {
                    register[key] = val;
                });
            },
            getMany : function () {
                return register;
            }
        };
    }());

I also note that

getMany is wrongly named, getAll perhaps ?
not sure what someKey does, is it any different from for( var key in o) ?


Player's scoring using JavaScript Description:

The questions are being showed in the console tap with player's score.
It's questioning by prompt continually until the prompt input gets 'exit'.
If the answer for each question is right then player's scores are counting up.
But, if not then it shows the same question over and over until the answer is right.

var Question = function(question,answers,correctAnswer){
  this.question = question;
  this.answers = answers;
  this.correctAnswer = correctAnswer;
}
Question.prototype.score = 0;
Question.prototype.playersAnswer;

Question.prototype.logAll = function(){
  console.log(this.question);
  for(var i = 0; i < this.answers.length; i++){
    console.log(i + " : " + this.answers[i]);
  }
}
Question.prototype.askQuestions = function(){
    Question.prototype.playersAnswer = prompt(this.question);
}
Question.prototype.checkIfRight = function (){
  if(this.correctAnswer === Question.prototype.playersAnswer){
    console.log("Correct Answer!");
    Question.prototype.score++;
    Question.prototype.logScore();
  }
  else if(Question.prototype.playersAnswer === "exit"){return 0;}
  else {
    console.log("Wrong! Try again :)");
    Question.prototype.logScore();
    return 'w';
  }
}
Question.prototype.logScore = function(){
  console.log("Your Score : " + Question.prototype.score
  + "\n---------------------------------");
}

var q1 = new Question('What is the name of the course\'s teacher?',['John','Baek','Jonas'],'2');
var q2 = new Question('Is JavaScript the coolest language in the world?',['Yes','No'],'0');
var q3 = new Question('What language are you gonna learn about after?',
                      ['C++','C','Java','Python','Node.js'],'4');
var questions = [q1,q2,q3];
function init(){
  var n = Math.floor(Math.random() * 3);
  questions[n].logAll();
  questions[n].askQuestions();
  questions[n].checkIfRight();

}

do {
  var n = Math.floor(Math.random() * 3);
  questions[n].logAll();
  questions[n].askQuestions();
  while(questions[n].checkIfRight() === 'w'){
    questions[n].logAll();
    questions[].askQuestions();
  };
}
while (q1.playersAnswer !== "exit");

Can you review it for best coding practices?

In object-oriented design, the key to modelling is to figure out how your application will respond to messages. Messages can be requests for information, requests to do something, or notifications that something has happened.

In your example, the application could receive a message, "what is the next question?" After giving it some thought, you might decide that a Quiz object would be responsible for providing that information, in which case you would need Quiz class with a method to respond to the message.

function Quiz() {
...
}

Quiz.prototype.nextQuestion = function () {
...
};

Now, you don't really have any questions yet, so another obvious message that your application will have to handle is, "add this question with these answer choices and correct answer."

DO NOT simply rush and add a new method to Quiz to handle the new message; instead, you need to repeat the thought process and decide which object is best suited to respond. In this case, again it is a Quiz object because questions are needed to answer the previous message of, "what is the next question?" So, you update your Quiz class accordingly. (Along the way you create a structure to represent a question and an index to track the current question, thus enabling you to find the next question.)

function Quiz() {
    this.questions = [];
    this.index = 0;
}

Quiz.prototype.addQuestion = function (text, choices, answer) {
   this.questions.push(new Question(text, choices, answer));
};

Quiz.prototype.nextQuestion = function () {
    if (this.index < this.questions.length)
        return this.questions[this.index++];
    return null;
};

function Question(text, choices, answer) {
    this.text = text;
    this.choices = choices;
    this.answer = answer;
}

I will skip messages that your application might have to handle in relation to player management and get to those that will require your objects to collaborate.

Say, your application receives a message, "the player has answered to this question with this answer." Going through the same thought process as before, you decide that the Quiz object will handle that, and you add a new method.

Quiz.prototype.answer = function (player, question, answer) {
...
};

However, this time, you need to check if the answer is correct as part of responding to that message. But which object can do that? Of course, the Question structure has the knowledge of correct answer, so it becomes its responsibility. Question has just been promoted from a simple structure to a full-blown class that can also respond to messages; in this case, "is this answer correct?" Therefore--

Question.prototype.isCorrect = function (answer) {
    return this.answer === answer;
};

And--

Quiz.prototype.answer = function (player, question, answer) {
    if (question.isCorrect(answer)) {
         // score some points for player
    }
}

As you can see, object-oriented design is not just finding classes and adding methods to them. You need to think about the messages and how they are handled; in other words, messages are key--NOT classes, NOT methods.

Good luck!


Parsing version number from a Java source file I'm extracting the version number from a file like this one. It works, but I find it clumsy and longer than probably needed.
I'd also appreciate some sanity checks as long as they don't make the code noticeably longer (It's just a script, no full Java parser. Something similar to Guava's getOnlyElement would be nice).
version = {->
    def lines = file('src/main/org/h2/engine/Constants.java').readLines();
    def extract = {name ->
        lines.grep {it =~ /public static final int $name =/}[0].replaceFirst(/.*=\s*(\d+);.*/, '$1')
    }
    extract('VERSION_MAJOR') + '.' + extract('VERSION_MINOR') + '.' + extract('BUILD_ID')
}()

Since you are only looking for a single occurrence of the variable in the file you could  match the whole file at once. For example like this:

version = {->
    def text = file('src/main/org/h2/engine/Constants.java').text
    def extract = {name ->
        nameValue = text.replaceAll(/(?s)^.*public\s+static\s+final\s+int\s+$name\s+=\s*(\d+);.*$/, '$1')
        text.length() == nameValue.length() ? "Cannot find name" : nameValue;
    }
    extract('VERSION_MAJOR') + '.' + extract('VERSION_MINOR') + '.' + extract('BUILD_ID')
}()

Instead of getting the lines this script reads the file to one single String, and then uses a regular expression to replace the while text with the variable of interest.

In order to do this, we first make sure that the . in the regexp will match newlines by adding (?s) to the pattern. We then match everything from the start (^.*) up until public static final int $name, capture the value with (\d+), and then match everything to the end of the file with .*$.

Although the regular expression is slightly more involved, this way makes it easier to check whether the replacement has worked and prevents a NullPointerException. We can now simply compare the length of the original text with the length of the result. If they are the same the replacement has not succeeded and we can return a custom error-message, otherwise we found the variable of interest.


FizzBuzz in FreezeFlame This is the first question for this language, and I decided I would do a FizzBuzz.

I used a template literal as a proof of concept, same goes for the pipe (|>). The code creates a function that recreates the traditional FizzBuzz in FreezeFlame:

var fizzBuzz = (max) -> {
    for(var i = 0; i < max + 1; i++) {
        (if i % 3 === 0 || i % 5 === 0 then "#{i % 3 == 0 ? 'Fizz' : ''}#{i % 5 === 0 ? 'Buzz' : ''}" else i) |> console.log
    }
}

This is equivalent to the following in JavaScript:

var fizzBuzz = (max) => {
    for(var i = 0; i < max + 1; i++){
        console.log((i % 3===0||i % 5===0 ? `${i % 3 == 0 ? 'Fizz' : ''}${i % 5 === 0 ? 'Buzz' : ''}` : i));
    };
}

The following features are used:

FreezeFlame ternary (if ... then ... else ...)
FreezeFlame template literals (#{...})
JS ternary (... ? ... : ...)
FreezeFlame pipe (... |> ...)
FreezeFlame function ((...) ->  { ... })

My main worries are the testing.

FreezeFlame GitHub

DRY

I'm sorry to say this but this solution is needlessly complicated. You are doubling up on your divisibility checks. This is a well known interview question where the goal is to really just to check that you can order your if statements correctly. It is kind of cool that you never really do a i % 3 == 0 && i % == 5 check (or i % 15 == 0), but at what cost?

What is the purpose of this language? Is FizzBuzz really suppose to show off the language?

I hate to sound this harsh, but I am not really feeling this language. Is it probably a useful educational experience? Sure, but I:

Don't think this example really showcases anything about your language, except for maybe the pipe operator.
(Maybe better for your other question) Not sure about the goal of the language.
I feel like most of the stuff (maybe not all, but most) could be simulated with macros. Hence, instead of creating a whole new language, you could use something like SweetJS to emulate most of the stuff you have done.
Not really sure how template literals showcase anything about your language, Javascript does it nearly identical to your way.

I know this is discouraging. I remember someone saying something along the lines of getting the urge to make a programming language and then laying down for a while until the urge wears off.

Before I become too discouraging, however, maybe you should really think about code you disliked in Javascript and analyze it closely. Then write it the way you want it to look like and then consider what you want. Maybe if you want to use template literals so badly, you can find a way to describe them easier in FreezeFlame?


Game runs very slowly - optimization I've made my first simple game in HTML5. Unfortunately, it runs so slowly. But there are only few rectangles! On my PC, frame rate is between 20 and 25. I expected something like 60-70 but no 20! You can see this game here: http://mygames.jcom.pl/ (and you can see code by clicking Ctrl+Shift+C in Chrome). What can I do to speed up my game? Why my (so simple) game doesn't run as smoothly as another (bigger and prettier) games in HTML5?

var gameCanvas = document.getElementById('gameCanvas');
var ctx = gameCanvas.getContext("2d");

var mapa = loadFromFile("level1");
var gracz = new Obiekt("square", 40, 40);
var blokczarny = new Obiekt("square", 80, 80);

var FPS = 0;

var gameWidth = gameCanvas.width;
var gameHeight = gameCanvas.height;
var gameTranslationX = 0;
var gameTranslationY = 0;

// Handle keyboard controls
var keysDown = {};

var graczData = {
    posOnScreenX: gameWidth / 2,
    posOnScreenY: gameHeight / 2,
    fallSpd: 300,
    runSpd: 300,
    jumpSpd: 600,
    fell: true,
    resetjumpSpd: 600,
    isJumping: false,
    yWhenStartedJump: 0,
    kierunek: 1
};

addEventListener("keydown", function(e) {
    keysDown[e.keyCode] = true;
}, false);

addEventListener("keyup", function(e) {
    delete keysDown[e.keyCode];
}, false);

var reset = function() {
    gracz.y = 0;
    gracz.x = 0;
    ctx.setTransform(1, 0, 0, 1, graczData.posOnScreenX, graczData.posOnScreenY);
};

// Update game objects
var update = function(modifier) {
    this.zmianaX = 0;
    this.zmianaY = 0;
    if (38 in keysDown && !graczData.isJumping && graczData.fell) {// Player holding up
        graczData.isJumping = true;
    }
    if (40 in keysDown) {// Player holding down

    }
    if (37 in keysDown) {// Player holding left

    }
    if (39 in keysDown) {// Player holding right

    }
    //ochrona przed "wejsciem w sciane" X
    var newMapPosX = getPositionOnMap(gracz.x + this.zmianaX, gracz.y, blokczarny);
    if (mapa[newMapPosX[1]][newMapPosX[0]] == 0) {
        gracz.x += this.zmianaX;
    }
    //spadanie
    if (getTypeOfTile(gracz.x, gracz.y + (graczData.fallSpd * modifier), blokczarny, mapa) == 0) {
        gracz.y += graczData.fallSpd * modifier;
    } else {
        graczData.fell = true;
    }
    //skakanie
    if (getTypeOfTile(gracz.x, gracz.y - (graczData.fallSpd * modifier), blokczarny, mapa) == 0 && graczData.isJumping) {
        gracz.y -= graczData.jumpSpd * modifier;
        graczData.jumpSpd -= 500 * modifier;
        graczData.fell = false;
        if (graczData.jumpSpd < 0) {
            graczData.jumpSpd = graczData.resetjumpSpd;
            graczData.isJumping = false;
        }
    }
    //bieganie
    if (getTypeOfTile(gracz.x + (graczData.runSpd * modifier * graczData.kierunek), gracz.y, blokczarny, mapa) == 0) {
        gracz.x += graczData.runSpd * modifier * graczData.kierunek;
    } else {
        graczData.kierunek *= -1;
    }
    //document.write("GraczY: " + gracz.y + "GraczX: " +gracz.x);
};

var clear = function() {
    ctx.fillStyle = "rgb(255, 255, 255)";
    //ctx.beginPath();
    ctx.rect(0, 0, gameCanvas.width, gameCanvas.height);
    //ctx.closePath();
    ctx.fill();
}

var oldgracz = {
    x: 0,
    y: 0
}
var render = function() {

    ctx.translate(-(gracz.x - oldgracz.x), -(gracz.y - oldgracz.y));
    gameTranslationX = gracz.x - graczData.posOnScreenX;
    gameTranslationY = gracz.y - graczData.posOnScreenY;
    clear();

    console.log("FPS" + FPS);

    ctx.fillStyle = "rgb(255, 0, 0)";
    gracz.draw(ctx);
    ctx.fillStyle = "rgb(0, 0, 0)";
    drawMap(mapa, blokczarny, ctx);
    oldgracz.x = gracz.x;
    oldgracz.y = gracz.y;
}

// The main game loop
var main = function() {
    var now = Date.now();
    var delta = now - then;

    FPS = 1000 / delta;

    update(delta / 1000);
    render();

    then = now;
};

// Let's play this game!
reset();
var then = Date.now();
setInterval(main, 100);

I believe your issue is related to the setInterval, you should at least try not to use it; instead use requestAnimationFrame.

for example here is a link:
http://paulirish.com/2011/requestanimationframe-for-smart-animating/

GL!


How to make my backtraching sudoku solving algorithm in Python faster? I wrote a backtracking Sudoku solving algorithm in Python.
It solves a 2D array like this (zero means "empty field"):

[
  [7, 0, 0, 0, 0, 9, 0, 0, 3],
  [0, 9, 0, 1, 0, 0, 8, 0, 0],
  [0, 1, 0, 0, 0, 7, 0, 0, 0],
  [0, 3, 0, 4, 0, 0, 0, 8, 0],
  [6, 0, 0, 0, 8, 0, 0, 0, 1],
  [0, 7, 0, 0, 0, 2, 0, 3, 0],
  [0, 0, 0, 5, 0, 0, 0, 1, 0],
  [0, 0, 4, 0, 0, 3, 0, 9, 0],
  [5, 0, 0, 7, 0, 0, 0, 0, 2],
]

like this:

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

But for "hard" Sudokus (where there are a lot of zeros at the beginning), it's quite slow. It takes the algorithm around 9 seconds to solve the Sudoku above. That's a lot better then what I startet with (90 seconds), but still slow.

I think that the "deepcopy" can somehow be improved/replaced (because it is executed 103.073 times in the example below), but my basic approaches were slower..

I heard of 0.01 second C/C++ solutions but I'm not sure if those are backtracking algorithms of some kind of mathematical solution...

This is my whole algorithm with 2 example Sudokus:

from copy import deepcopy

def is_sol_row(mat,row,val):
  m = len(mat)
  for i in range(m):
    if mat[row][i] == val:
      return False
  return True

def is_sol_col(mat,col,val):
  m = len(mat)
  for i in range(m):
    if mat[i][col] == val:
      return False
  return True

def is_sol_block(mat,row,col,val):
  rainbow = [0,0,0,3,3,3,6,6,6]
  i = rainbow[row]
  j = rainbow[col]
  elements = {
    mat[i + 0][j + 0], mat[i + 1][j + 0], mat[i + 2][j + 0],
    mat[i + 0][j + 1], mat[i + 1][j + 1], mat[i + 2][j + 1],
    mat[i + 0][j + 2], mat[i + 1][j + 2], mat[i + 2][j + 2],
  }
  if val in elements:
    return False
  return True

def is_sol(mat,row,col,val):
  return is_sol_row(mat,row,val) and is_sol_col(mat,col,val) and is_sol_block(mat,row,col,val)

def findAllZeroIndizes(mat):
  m = len(mat)
  indizes = []
  for i in range(m):
    for j in range(m):
      if mat[i][j] == 0:
        indizes.append((i,j))
  return indizes

def sudoku(mat):
  q = [(mat,0)]
  zeroIndizes = findAllZeroIndizes(mat)
  while q:
    t,numSolvedIndizes = q.pop()
    if numSolvedIndizes == len(zeroIndizes):
      return t
    else:
      i,j = zeroIndizes[numSolvedIndizes]
      for k in range(1,10):
        if is_sol(t,i,j,k):
          newt = deepcopy(t)
          newt[i][j] = k
          q.append((newt,numSolvedIndizes+1))
  return False

mat = [
  [7, 0, 0, 0, 0, 9, 0, 0, 3],
  [0, 9, 0, 1, 0, 0, 8, 0, 0],
  [0, 1, 0, 0, 0, 7, 0, 0, 0],

  [0, 3, 0, 4, 0, 0, 0, 8, 0],
  [6, 0, 0, 0, 8, 0, 0, 0, 1],
  [0, 7, 0, 0, 0, 2, 0, 3, 0],

  [0, 0, 0, 5, 0, 0, 0, 1, 0],
  [0, 0, 4, 0, 0, 3, 0, 9, 0],
  [5, 0, 0, 7, 0, 0, 0, 0, 2],
]

# mat = [
#   [3, 0, 6, 5, 0, 8, 4, 0, 0],
#   [5, 2, 0, 0, 0, 0, 0, 0, 0],
#   [0, 8, 7, 0, 0, 0, 0, 3, 1],
#   [0, 0, 3, 0, 1, 0, 0, 8, 0],
#   [9, 0, 0, 8, 6, 3, 0, 0, 5],
#   [0, 5, 0, 0, 9, 0, 6, 0, 0],
#   [1, 3, 0, 0, 0, 0, 2, 5, 0],
#   [0, 0, 0, 0, 0, 0, 0, 7, 4],
#   [0, 0, 5, 2, 0, 6, 3, 0, 0]
# ]

print(sudoku(mat))

Your sudoku solver is missing a crucial part: the one that fills all obvious cells without backtracking.

In your example sudoku, in row 1 column 7 there must be a 1 because that's the only place in row 1 where a 1 is possible. That's because the blocks to the left already contain a 1, and columns 8 and 9 also contain a 1 further down.

With that improvement, the algorithm should get quite fast. That's probably how every other sudoku solver attacks the complexity, therefore you should have a look at the answers of related code reviews.

In 2006 I wrote a sudoku solver in C using exactly this improvement. You may have a look at it, it should be pretty fast, even when you translate it back to Python.

Since sudokus are popular, several people have already documented how they wrote a sudoku solver. I found this one via Rosetta Code.


Average of subarrays of length k in C++ I took a crack at solving the problem of finding the averages of all subarrays of length k. Here is what I came up with. I would greatly appreciate your feedback on  my code.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

vector<double> findSuseqAverages(size_t k, const vector<int>& nums) {

    vector<double> res (nums.size() - k + 1);
    auto left_it = nums.begin();
    auto right_it = next(left_it, k);
    double curr_sum = accumulate(left_it, right_it, 0);

    size_t res_index = 0;
    res.at(res_index) = curr_sum / k;

    while (right_it != nums.end()) {
        curr_sum += *right_it - *left_it;
        res.at(++res_index) = curr_sum / k;
        ++right_it;
        ++left_it;
    }

    return res;
}

int main() {
    vector<int> nums {-1, 0, 1};
    size_t k = 2;
    vector<double> averages = findSuseqAverages(k, nums);

    for (const auto& a: averages) cout << a << " ";
    cout << "\n\n";
}

Generally the code is well written, there are only a few items that need commenting on.
Avoid Using Namespace std
If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifier cout you may override within your own classes. This stack overflow question discusses this in more detail.
Use Braces Around Single Statements in Program Flow
Primarily for maintenance reasons it is a good habit to create code blocks within if statements, else clauses and within loops. Many bugs have been created during maintenance when one or more statements was added to an if statement or a loop.
From this code:
    for (const auto& a: averages) cout << a << " ";

Would be better as
    for (const auto& a: averages) {
        std::cout << a << " ";
    }

Then if someone needs to add a statement to the for loop at some point it is quite simple.
This Code Could Be Simplified
    vector<double> res (nums.size() - k + 1);
        ...

    size_t res_index = 0;
    res.at(res_index) = curr_sum / k;

    while (right_it != nums.end()) {
        ...
        res.at(++res_index) = curr_sum / k;
        ...
    }

It's not clear why it was necessary to initialize the res vector to the proper size in the previous code. Since vectors are variable sized they don't need to be initialized with a size.
    std::vector<double> res;
        ...

    res.push_back(curr_sum / k);

    while (right_it != nums.end()) {
        ...
        res.push_back(curr_sum / k);
        ...
    }

removes one variable and achieves the same result.


Minimum Value evenly divisible by all integers from 1 to n I have just started learning python and I am solving Project Euler problems alongside for practice. This is my solution for problem 5. Project Euler asks for the minimum value divisible by all numbers from 1 to 20 but I have made the program so it works from 1 to n.

I think there is a lot of room for improvement in it and I need your suggestions. Please tell me how I can improve it.

def least(x):
    """
    Variables:
    x = Argument of function and the maximum value of range.
    n = Number that is going to be tested by loops in each cycle.
    a = Number that is going to be added to "n" in each cycle of loop. It is initialized with "x".
        For example: if we check for all numbers from 1 to 10, each "n" has to be multiple of 10. So that's why
        a will be added to n in each turn.
    y = To minimize machine time, I have tried to bring argument of "least" function below 10.
        So if x is bigger than 10, y will be x - 10. And then we will do recursion and use "least" on y.

        For example: If we check from 1 to 40.
            least(40) -> n = least(30) = a                          (calls least(30) to get n and a)
                least(30) -> n = least(20) = a                      (calls least(20) to get n and a)
                    least(20) -> n = least(10) = a                  (calls least(10) to get n and a)
                        least(10) -> n = 10, a =10, (Brute Check)
                            (Brute Check)
        (At each stage "for loop" checks "n" in each loop cycle and adds "a" until value found.)
    """
    if x <= 10:
        n = x #The first number to test
        a = x #a is number that's going to be added in each turn
    else:
        y = x - 10
        n = least(y) #Recursion to minimize machine load and time
        a = n
    while True:
        d = 0
        for i in range(1,x + 1):
            if n % i == 0:
                d += 1 #counts if i evenly divides.
            else:
                break #Checks each n. If i doesn't evenly divide, skips loop cycle.
        if d == x: #if each "i" divides evenly, d will be equal to x and thus minimum value will be n.
            return n
        else:
            n += a #adds a(specified above)
minimumvalue = least(int(input("Minimum Value divisible by all integers from 1 to n.\n Specify n: ")))
print(" Minimum Value: " + str(minimumvalue))

Github Link

Your code can be more pythonic.

Names of variables and functions should be more meaningful and descriptive. Also - read PEP8.
You should encapsulate your code in smaller functions responsible
for one thing. And signal what is the purpose of each function by
it's name (= meaningful names).
Use power which python gives you. To save memory instead of range() use xrange() in every case when you only need to iterate over. range() creates a list, so if you do range(1, 99999) it creates a list in memory with 99999 elements. In contrast xrange() is a sequence object that evaluates lazily.
There are more efficient algorithms than brute-force. But even your
brute-force approach can be improved. With xranege() you don't
need recursion any more. What is more it's wiser to iterate over
dividers in decreasing order. Which is dead simple in python, just use -1 as third xrange() parameter (step).

Take a look at this example:

def smallest_common_multiple(maximal_divisor):
    for number in xrange(maximal_divisor, sys.maxsize):
        if is_common_multiple(number, maximal_divisor):
            return number

def is_common_multiple(number, maximal_divisor):
    for divisor in xrange(maximal_divisor, 1, -1):
        if number % divisor != 0:
            return False
    return True

Comment:

In smallest_common_multiple() iteration starts from maximal_divisor because smaller numbers doesn't make sense. sys.maxsize works like to infinity.

:-)

Update

As Josay points out this can be even simpler. Thanks Josay!

from itertools import count

def smallest_common_multiple(maximal_divisor):
    for number in count(maximal_divisor):
        if is_common_multiple(number, maximal_divisor):
            return number

def is_common_multiple(number, maximal_divisor):
    return all([number % divisor == 0 for divisor in xrange(maximal_divisor, 1, -1)])


A hash-signature-type which tests on comparing against normal strings I decided to throw this together today figuring it would be cool to add to my repertoire. Before we always had performed this "task" externally. Find the value we want to compare, hash it and compare with a valid hash. But my idea was to bundle this into a object which behaves nicely with string types. It then could internally compare the two and determine if they match.

I'm just curious on what you all think here and where I can improve. And if I've even done something any of you find could save time and find more usable than not.

Benefits

No generic classes I have to drag around, it is now a type with a specific purpose.
The data for the type is never stored in plain text, therefore should be safe, right?

Usage

ProtectedString ThisIsMyProtectedString1 = "";

ThisIsMyProtectedString1 = "Test";

if (ThisIsMyProtectedString1 == "Test")
    MessageBox.Show("Equal");

Le Code

public struct ProtectedString
{

    private string _Data;

    public String Data
    {
        get { return _Data; }
        private set { _Data = value; }
    }

    private const int SALT_BYTE_SIZE = 24;

    private const int HASH_BYTE_SIZE = 24;

    private const int PBKDF2_ITERATIONS = 1000;

    public ProtectedString(String value)
    {
        _Data = "";
        _Data = CreateHash(value);
    }

    public static implicit operator ProtectedString(String value)
    {
        return new ProtectedString(value);
    }

    public static bool operator ==(ProtectedString c1, String c2)
    {
        return c1.Equals(c2);
    }

    public static bool operator !=(ProtectedString c1, String c2)
    {
        return !c1.Equals(c2);
    }

    public static bool operator ==(String c1, ProtectedString c2)
    {
        return c2.Equals(c1);
    }

    public static bool operator !=(String c1, ProtectedString c2)
    {
        return !c2.Equals(c1);
    }

    public bool Equals(String value)
    {
        Boolean result = false;
        result = ValidateHash(value, _Data);
        return result;
    }

    public override bool Equals(object obj)
    {
        return base.Equals(obj);
    }

    private string CreateHash(String value)
    {
        RNGCryptoServiceProvider csprng = new RNGCryptoServiceProvider();

        byte[] salt = new byte[SALT_BYTE_SIZE];

        csprng.GetBytes(salt);

        byte[] hash = PBKDF2(value, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);

        return
            Convert.ToBase64String(salt) +
            Convert.ToBase64String(hash);
    }

    private bool ValidateHash(String value, String validHash)
    {
        byte[] full = Convert.FromBase64String(validHash);

        byte[] salt = full.Take(SALT_BYTE_SIZE).ToArray();

        byte[] hash = full.Skip(SALT_BYTE_SIZE).ToArray();

        byte[] testHash = PBKDF2(value, salt, PBKDF2_ITERATIONS, hash.Length);

        return SlowEquals(hash, testHash);
    }

    private bool SlowEquals(byte[] a, byte[] b)
    {
        uint diff = (uint)a.Length ^ (uint)b.Length;

        for (int i = 0; i < a.Length && i < b.Length; i++)
            diff |= (uint)(a[i] ^ b[i]);

        return (diff == 0);
    }

    private byte[] PBKDF2(string value, byte[] salt, int iterations, int outputBytes)
    {
        Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(value, salt);

        pbkdf2.IterationCount = iterations;

        return pbkdf2.GetBytes(outputBytes);
    }

}

private string _Data;

public String Data
{
    get { return _Data; }
    private set { _Data = value; }
}

You should make this immutable by either declaring _Data as readonly and remove the setter or by having only public readonly string Data;.
In addition you should be consitent with the style you are using. Here you use one time the alias string and one time the String object. Most C# developers use only the alias, but thats a decision for you to make. Once you have made a decision you should stick to your style.

public ProtectedString(String value)
{
    _Data = "";
    _Data = CreateHash(value);
}

the assignment of "" to _Data is only adding noise to the code. Remove it.

because it is a struct the default parameterless constructor needs to be called like so

public ProtectedString(String value)
    :this()
{
    _Data = CreateHash(value);
}

public override bool Equals(object obj)
{
    return base.Equals(obj);
}

This should be changed in way that it is really doing an Equal of the class rather then only calling the base.Equals() like so

public override bool Equals(object obj)
{
    var protectedString = obj as ProtectedString;

    if (protectedString == null) { return false; }

    return _Data.Equals(protectedString.Data);
}

It could be possible that this isn't 100% correct, because I can't test it.

private string CreateHash(String value)
{
    RNGCryptoServiceProvider csprng = new RNGCryptoServiceProvider();

    byte[] salt = new byte[SALT_BYTE_SIZE];

    csprng.GetBytes(salt);

    byte[] hash = PBKDF2(value, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);

    return
        Convert.ToBase64String(salt) +
        Convert.ToBase64String(hash);
}

RNGCryptoServiceProvider implements through its base class the IDisposable interface hence you should use a using block to proper dispose it. I would extract the generation of the salt to a separate method.

private byte[] GetSalt()
{
    using (RNGCryptoServiceProvider csprng = new RNGCryptoServiceProvider())
    {
         byte[] salt = new byte[SALT_BYTE_SIZE];

         csprng.GetBytes(salt)

         return salt;
    }
}

private string CreateHash(String value)
{

    byte[] salt = GetSalt();

    byte[] hash = PBKDF2(value, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);

    return
        Convert.ToBase64String(salt) +
        Convert.ToBase64String(hash);
}

private bool ValidateHash(String value, String validHash)
{
    byte[] full = Convert.FromBase64String(validHash);

    byte[] salt = full.Take(SALT_BYTE_SIZE).ToArray();

    byte[] hash = full.Skip(SALT_BYTE_SIZE).ToArray();

    byte[] testHash = PBKDF2(value, salt, PBKDF2_ITERATIONS, hash.Length);

    return SlowEquals(hash, testHash);
}

here you should replace hash.Length with HASH_BYTE_SIZE as the last parameter of the call to PBKDF2().

private bool SlowEquals(byte[] a, byte[] b)
{
    uint diff = (uint)a.Length ^ (uint)b.Length;

    for (int i = 0; i < a.Length && i < b.Length; i++)
        diff |= (uint)(a[i] ^ b[i]);

    return (diff == 0);
}

You should always use braces {} although they might be optional. Using braces makes your code less error prone which should have top priority for security related stuff.

private byte[] PBKDF2(string value, byte[] salt, int iterations, int outputBytes)
{
    Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(value, salt);

    pbkdf2.IterationCount = iterations;

    return pbkdf2.GetBytes(outputBytes);
}

Rfc2898DeriveBytes is implementing IDispoable through its base class too, hence you should use a using block.

private byte[] PBKDF2(string value, byte[] salt, int iterations, int outputBytes)
{
    using (Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(value, salt))
    {
        pbkdf2.IterationCount = iterations;

        return pbkdf2.GetBytes(outputBytes);
    }
}


C# class that handle MySQL db connection I've built a class that handles all my connections to a MySql database.

These are the function I use to create the connection(not really sure about the two dispose functions) :

 public class dbConnection : IDisposable
{
    public MySqlConnection conn;
    public MySqlTransaction transaction;

    private static Logger logger = LogManager.GetCurrentClassLogger();

    public dbConnection()
    {
        string host = "1.1.1.1";
        string usernameMySql = "admin";
        string pswMySql = "password";
        string nomeDb = "db1";

        string connStr = "Database=" + nomeDb + ";" +
                "Data Source=" + host + ";" +
                "User Id=" + usernameMySql + ";Password=" + pswMySql + "";
        conn = new MySqlConnection(connStr);
    }

    public void openConnection()
    {
        conn.Close();
        conn.Open();
        transaction = conn.BeginTransaction();
    }

    public void closeConnection()
    {
        transaction.Commit();
        conn.Close();
    }

    protected virtual void Dispose(Boolean disposing)
    {
        if (disposing)
        {
        }
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

These are the functions I use to read/write data:

public void ExecuteSQL(string sSql)
    {
        MySqlCommand cmd = new MySqlCommand(sSql, conn);
        cmd.ExecuteNonQuery();
    }

    public MySqlDataReader readerSQL(string sSql)
    {
        MySqlCommand cmd = new MySqlCommand(sSql, conn);
        MySqlDataReader readerSql = cmd.ExecuteReader();

        return readerSql;
    }

    protected int ExecuteSQLReturnId(string sSql)
    {
        MySqlCommand cmd = new MySqlCommand(sSql, conn);
        cmd.ExecuteNonQuery();
        return Convert.ToInt32(cmd.LastInsertedId);
    }

In others part of my project i then use

db = new dbConnection();
db.openConnection();

to create a new connection.

This code works but I'm not really sure it's the right way to handle things, Are there any improvements that can be made ?

What's the point of dbConnection? As it stands now it is a barely-there wrapper around MySqlConnection with a built-in connection string(!) and some odd behavior when you call openConnection(). You claim this works, are you sure -- because why wouldn't conn.Close(); throw an exception if there isn't an open connection?

Why do you always open a transaction? Why is your connection string hard-coded?

This code:

doesn't follow capitalization standards,
doesn't use a using statement to encapsulate classes that implement IDisposable (which should also be used when dealing with MySqlCommand and MySqlDataReader etc.),
has bad variable names like readerSql, usernameMySql,...


Hashing passwords in PHP When hashing a password, I understand it is best not to use functions such as SHA1 or MD5.

This function is working fine and I want to know if it can be improved to increase site security.

class safePassword
{
    public static function makeSafe($password)
    {
        $salt = "mySalt";
        $hash = hash("sha256", $salt.".".$password);
        return $hash;
    }
}

I understand it is best not to use functions such as SHA1 or MD5.

That is true. But sha256 is not that much better.

Problem: simple sha256

There are basically two problems with your approach:

you don't use a user-based salt, only a site-based salt (also called a pepper).
you only use simple sha256, which is way too fast.

These are serious issues.

The main problem with missing user-based salts is that an attacker only needs to hash each password once and can then compare it to the hashes of all users, instead of needing to hash the password with each salt. This speeds up cracking considerably.

The problem with the second point should be obvious. Hardware has become quite powerful over the years, and simple hashing just doesn't hold up anymore (and hasn't for quite a while). Here for example is a benchmark of 3090.3 Million guesses per second on a pretty standard PC.

If your database is ever leaked - for example because of a Code Execution or SQL Injection vulnerability - it will be quite easy for an attacker to crack a good percentage of your users passwords.

Solution: Bcrypt

What you want to use is bcrpyt. With PHP, this can be done via password_hash (which is also the first result when googling "php hash password").

Example:

// hash
$hash = password_hash("password", PASSWORD_DEFAULT);

echo $hash;

// check
echo "<br>" . password_verify("password", $hash);

User-based salts are managed automatically for you, and it uses multiple rounds of hashing, slowing the process down, and thus increasing the resources an attacker needs to crack your hashes.

You can still use a pepper with bcrypt if you want to.

For more information about password hashing in general see here.

Misc

makeSafe is not a good function name. Make safe how? hash would be more accurate.


Execute startup method asynchronously The goal is to call startManager on application start so that the manager is initialized in background without blocking application main thread.

Is it a safe implementation? Any recommendation or best practice? (use an Executor, use a synchronized block, ...)

public class FileConverter
{
    /** The Constant logger. */
    private static final Logger logger = LoggerFactory.getLogger(FileConverter.class);

    private static RunnableFuture<OfficeManager> managerFuture;

    /**
     * Start manager.
     */
    public static synchronized void startManager()
    {
        if(managerFuture == null)
        {
            Callable<OfficeManager> callable = new Callable<OfficeManager>()
            {
                @Override
                public OfficeManager call() throws Exception
                {
                    OfficeManagerConfiguration configuration = new OfficeManagerConfiguration();
                    OfficeManager officeManager = configuration.buildOfficeManager();

                    officeManager.start();

                    logger.info("officeManager started");

                    return officeManager;
                }
            };

            managerFuture = new FutureTask<OfficeManager>(callable);
            new Thread(managerFuture).start();
        }
    }

    /**
     * Stop manager.
     */
    public static synchronized void stopManager()
    {
        if(managerFuture != null)
        {
            managerFuture.cancel(true);

            try
            {
                OfficeManager officeManager = managerFuture.get();
                if(officeManager.isRunning())
                {
                    officeManager.stop();
                }
            }
            catch(CancellationException e)
            {
                // ignore
            }
            catch(InterruptedException e)
            {
                Thread.currentThread().interrupt();
            }
            catch(ExecutionException e)
            {
                logger.warn(e.getMessage(), e);
            }
        }
    }

    /**
     * Convert.
     *
     * @param file the file
     * @param format the format
     * @return the file
     * @throws Exception the exception
     */
    public static File convert(File file, String format) throws Exception
    {
        OfficeManager officeManager = managerFuture.get();
        if(!officeManager.isRunning())
        {
            throw new IllegalStateException("officeManager is not running!");
        }

        File tempFile = File.createTempFile(FileConverter.class.getSimpleName() + "-", "." + format);
        try
        {
            if(file.getName().endsWith("." + format))
            {
                FileUtils.copyFile(file, tempFile);
            }
            else
            {
                OfficeDocumentConverter converter = new OfficeDocumentConverter(officeManager);
                converter.convert(file, tempFile);
            }

            return tempFile;
        }
        catch(Exception e)
        {
            tempFile.delete();
            throw e;
        }
    }
}

Reply to @EricStein

Right. Adding synchronyzed to stopManager() should serialize invocations.
Right. It can cause an unwanted restart.
Right. I misunderstood the InterruptedException being generated in manager thread not by future.get() itself.
This is server-side code: every time I recompile the server, it takes about 30s to startup. This implementation reduces startup time to 25s. I agree it's not worth on production, but it's a time saver on development.

before accepting your answer, I'd like to know if new Thread(managerFuture).start(); is a good way to start an asynchronous operation: it doesn't sound good to start something without preserving a reference...

There's a potential failure. If a thread invokes startManager() and then another thread immediately invokes stopManager(), stopManager() could see managerFuture as null and do nothing before startManager() gets a chance to populate it. The end result would be as if stopManager() was never called.

There's no reason for convert() to call startManager() if the manager gets started on application start.

Don't ignore InterruptedException. At the very least call Thread.currentThread().interrupt(). There are many resources out there on how to correctly handle InterruptedException, including on StackOverflow.

I also question the premise that the manager needs to start up on another thread. You should only bother if this is client-side code and this is a demonstrated bottleneck on startup.

Updated Answer

It will, but synchronized is a blunt instrument. It usually locks for longer than you need, and it's a lock on the object itself. If somebody else used your class as a lock, none of your synchronized methods could run until it was released. If you insist on going this route, you should use a private static final RentrantLock and minimize the scope to what you really need to be locked.
No, it shouldn't, but it doesn't do anything. If you call startManager() on startup, then the init thread is already running. If convert() also calls it, convert() will wait for the init thread to release its lock, then find out that it's already been initialized. OR you can do lazy-load of the manager in convert(), but then you have to wait for it to spin up the first time, which doesn't seem optimal if it takes 5 seconds.
Ok.
My point is that introducing this logic to save yourself 5 seconds on application start-up in dev is a bad tradeoff. Performance tuning is fragile and usually difficult to understand. Don't do it unless you need to. Junior programmers will get confused and muck it up by accident.
I don't think you need a reference to the thread. You have the Future .. that's what you care about. The only operation you want to perform on the thread after you start it is to interrupt it, which you can do from the future. If you need to hold onto the thread for some reason, by all means do so, but if you don't, there's no point in keeping a pointer to it.


Accurately calculating gravity for large systems I'm in the middle of a program to simulate gravity between particles for > 50000 particles. It works so far, but the way I calculate gravity seems to be a tad askew. Generally, it works. It fails when particles get too close (distance between them approaching 0, gravitational force approaching infinity). I believe this is because of how the implementation chunks up time. It can only calculate the gravity between frames, and I can shorten the time between frames but the problem still exists.

Here's the implementation:

//The time between frames
static final double planc = 0.002;

//Calculates distance^2 between two particles
public double d2(Particle p) {

    return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);

}

//Gets Vector from on particle pointing to the next
public Vector getVec(Particle p) {

    return new Vector(p.x - x, p.y - y);

}

//The function that actually (independently) moves the particles according
//to the forces acting on them
public void move() {

    //v is a Vector that represents the force (not acceleration)
    //acting on the particle
    x += v.dx * planc / m;
    y += v.dy * planc / m;

}

//Actually calculates gravity
public boolean grav(Particle p) {

    double d2 = d2(p);

    //Happens once because of how the function is used (unimportant)
    if (d2 == 0)
        return false;

    //-1000 is the G value
    double f = -1000 * m * p.m / d2;

    //Creates acceleration-vectors
    Vector v = getVec(p);
    v.normTo(f * planc, Math.sqrt(d2));//sets v's magnitude to f * planc. 2nd parameter saves a calculation
    //Basically formats a vector which represents gravitational acceleration

    //"adds" force-vector to both particles
    this.v.sub(v);
    p.v.add(v);

    return false;

}

This is fast but sacrifices accuracy. Is there a better way to calculate gravity for large n-body systems (that doesn't screw over performance)?

Gravity for small distances

I've seen two simple ways that are used to fix this problem:

Add a small amount to each distance:

double d2 = d2(p);

d2 += EPSILON_DIST;

Use a minimum distance:

double d2 = d2(p);

if (d2 < MIN_DIST)
    d2 = MIN_DIST;

Either way will prevent small distances from causing huge accelerations.  Since d2 is in units of distance squared, your EPSILON_DIST and MIN_DIST should also be squared distances.

More efficient gravity computation

Your gravity calculation could be improved a little.  I answered another almost identical question here, so you can take a look at the solution I came up with there.  The main point is that you can reduce the number of divisions to only one in grav() and zero in move().  Although it doesn't exactly match your Particle class, I think you can extrapolate from it.  Here is the code, pasted from that other question:

public void interact(Body other) {
    double dx = other.getX() - x;
    double dy = other.getY() - y;
    double r  = calculateDistance(dx, dy);
    double inv_r3 = 1.0 / (r * r * r);

    /* Precalculate force component (1/r^2) times direction (dx/r) = dx / r^3 */
    dx *= inv_r3;
    dy *= inv_r3;

    /* calculate accelerations for both bodies */
    vx += other.getMass() * dx;
    vy += other.getMass() * dy;
    other.addToVx(mass * -dx);
    other.addToVy(mass * -dy);
}

public void update() {
    x += vx;
    y += vy;
}


Generating a tabula recta I want an experienced Haskeller to critique my code and offer changes/suggestions (so I can learn the idioms of the language and culture around Haskell).

I've been using a Tabula Recta for my passwords and used a Python script someone wrote to generate the table and do table traversal.

I've been wanting to learn Haskell and decided to take on building the same program but in Haskell.

I'm new to Haskell but not functional programming (I have Scheme and Erlang under my belt - Erlang I use in production on a daily basis). I feel like I kept compositional style but I doubt I adhered to idiomatic Haskell.

{-# LANGUAGE BangPatterns #-}
{- |
Module      :  tabula.hs
Description :  Generates a tabula recta
Copyright   :  (c) Parnell Springmeyer
License     :  BSD3

Maintainer  :  ixmatus@gmail.com
Stability   :  experimental

Generates and manipulates a tabula recta.
-}

module Main where

import Control.Monad.CryptoRandom
import Crypto.Random

import Data.String.Utils
import Data.List.Split

main :: IO()
main = do
    values <- tabulay ['A'..'Z']
    putStrLn $ "    " ++ join " " (chunksOf 1 ['A'..'Z'])
    putStrLn $ "  + " ++ (take 52 $ cycle "- ")
    putStrLn $ join "\n" (reverse values)

tabulay :: [Char] -> IO [[Char]]
tabulay cmap = tabulay' cmap []
    where tabulay' [] acc    = do return acc
          tabulay' (x:xs) acc = do
            chars <- tabulax 26
            let formatted = [x, '|'] ++ chars
                spaced = join " " (chunksOf 1 formatted)
            tabulay' xs $! (spaced:acc)

tabulax :: Int -> IO [Char]
tabulax cint = tabulax' cint []
    where tabulax' 0 acc    = do return acc
          tabulax' iint acc = do
            val <- randomChoice characterMap
            tabulax' (iint-1) $! (val:acc)

characterMap :: [Char]
characterMap =
    let
        cmap = ['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9']
        symb = [',', '.', '/', '?', '~', '`', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '_', '+', '=', '{', '[', ']', '}', '\\', '|', ':', ';', '"', '\'']
    in cmap ++ symb

randVal :: Int -> IO Int
randVal len = do
    g <- newGenIO :: IO SystemRandom
    let Right (int, _) = crandomR (0, len-1) g :: Either GenError (Int, SystemRandom)

    -- This MUST be strict - otherwise this function will keep too many file handles open
    return $! int

randomChoice :: [Char] -> IO Char
randomChoice ls = do
    randomIndex <- randVal (length ls)
    let val = ls !! randomIndex
    return val

Yet another problem is the usage of lists. !! is O(N) operation. Use Data.Array instead.

As for randoms, you should call newGenIO only once and use the cryptographically secure generator it returned after that instead of creation of new generators each time you need a random character.

Your randVal function should look something like this:

randVal :: Int -> SystemRandom -> (Int, SystemRandom)
randVal len g = fromRight $ crandomR (0, len-1) g

It accepts old generator state and returns the new state to use in subsequent generations. To simplify passing the generator state around you can use a state monad. But there is already such monad - the CRand monad and corresponding CRandT monad transformer to combine random number generation with other monadic computations.

The example from the documentation for CRand fails to typecheck because of monomorphism restriction - getRandPair looks like a value but it isn't, so the compiler detects a potential problem. You can disable it for now by adding {-# LANGUAGE NoMonomorphismRestriction #-} before module Main where line.

Also, it is not clear how the SystemRandom generator works. It is secure, but I think it's not adviced to drain system entropy source. I'd rather use it just to seed HashDRBG from Crypto.Random.DRBG, which is SHA512-based RNG.

Here is a hint:

type Gen a = CRand HashDRBG GenError a

randValM :: Int -> Gen Int
randValM len = getCRandomR (0, len-1)

randomChoice :: [a] -> Gen a
randomChoice ls = do
    randomIndex <- randValM (length ls)
    return $ ls !! randomIndex

Your tabulax function will remain the same, but will operate in a different monad, so it's type will change to randomChoice :: [a] -> Gen a. Note also that I used getCRandomR from Control.Monad.Crypto.Random to make use of the monadic helper to implicitly pass the cryptogenerator around and perform error checking.

Your main will change too:

printGenerated values = do
    putStrLn $ "    " ++ join " " (chunksOf 1 ['A'..'Z'])
    putStrLn $ "  + " ++ (take 52 $ cycle "- ")
    putStrLn $ join "\n" (reverse values)

fromRight (Right a) = a

generate = evalCRand $ do
    a <- tabulay ['A'..'Z']
    return a

main = do
    g <- newGenIO :: IO HashDRBG
    printGenerated $ fromRight $ generate g

The idea is that we extracted generate - a pure function which accepts a generator and returns generated data. evalCRand is used to extract the inner a value from monadic Gen a value. It accepts two arguments: a monadic computation in Gen monad and initial state of random generator. There is also runCRand function which returns the final state of the generator in addition to the value, but we don't need the final state here.

I abused the do-notation here to help you understand code better. I would write generate and main shorter:

generate = evalCRand $ tabulay ['A'..'Z']

main = newGenIO >>= printGenerated . fromRight . generate

Your tabulatex' function is already there in the standard library. It is Control.Monad.replicateM:

import Control.Monad hiding (join)

tabulax :: Int -> Gen [Char]
tabulax cint = replicateM cint $ randomChoice characterMap

tabulatey' is also there in Control.Monad, it's mapM:

tabulay :: [Char] -> Gen [[Char]]
tabulay = mapM $ \x -> do
            chars <- tabulax 26
            let formatted = [x, '|'] ++ chars
                spaced = join " " (chunksOf 1 formatted)
            return spaced

Next step is to use immutable arrays:

import Data.Array.IArray

tabulax :: Int -> Gen [Char]
tabulax cint = replicateM cint $ randomChoiceA arrMap

arrMap :: Array Int Char
arrMap = listArray (0, (length characterMap) - 1) characterMap

randomChoiceA ls = do
    randomIndex <- randValM $ 1 + snd (bounds ls)
    return $ ls ! randomIndex

Now randValM seems to be perverted: we convert bounds from tuple to size and back. Eliminating the extra conversion we get rid of randValM completely, as getCRandomR and bounds perfectly fit each other:

randomChoiceA ls = do
    randomIndex <- getCRandomR $ bounds ls
    return $ ls ! randomIndex

Now we can shorten it by desugaring do-notation and using function composition and infix operator sections:

randomChoiceA ls = getCRandomR (bounds ls) >>= return . (ls !)

And even more using <$> from Control.Applicative (which is the same as fmap):

randomChoiceA ls = (ls !) <$> getCRandomR (bounds ls)

Finally, we can extract separate = join " " . chunksOf 1 as it is used 2 times and shorten tabulay just for fun:

tabulay :: [Char] -> Gen [[Char]]
tabulay = mapM $ \x -> separate <$> ([x, '|'] ++) <$> tabulax 26

and get rid of ugly -1 in array bounds:

arrMap :: Array Int Char
arrMap = listArray (1, length characterMap) characterMap

So the final source is:

{-# LANGUAGE NoMonomorphismRestriction #-}
module Main where

import Control.Monad.CryptoRandom
import Crypto.Random.DRBG
import Data.String.Utils
import Data.List.Split
import Control.Monad hiding (join)
import Control.Applicative
import Data.Array.IArray

printGenerated values = do
    putStrLn $ "    " ++ separate ['A'..'Z']
    putStrLn $ "  + " ++ take 52 (cycle "- ")
    putStrLn $ join "\n" (reverse values)

fromRight (Right a) = a

generate = evalCRand $ tabulay ['A'..'Z']

main = newGenIO >>= printGenerated . fromRight . generate

separate = join " " . chunksOf 1

tabulay :: [Char] -> Gen [[Char]]
tabulay = mapM $ \x -> separate <$> ([x, '|'] ++) <$> tabulax 26

tabulax :: Int -> Gen [Char]
tabulax cint = replicateM cint $ randomChoiceA arrMap

arrMap :: Array Int Char
arrMap = listArray (1, length characterMap) characterMap

randomChoiceA ls = (ls !) <$> getCRandomR (bounds ls)

characterMap :: [Char]
characterMap =
    let
        cmap = ['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9']
        symb = ",./?~`!@#$%^&*()-_+={[]}\\|:;\"'"
    in cmap ++ symb

type Gen a = CRand HashDRBG GenError a


Maximum absolute difference of array elements I am trying to solve a question from array section:

  You are given an array of N integers, A1, A2 ,…, AN. Return maximum
  value of f(i, j) for all 1 ≤ i, j ≤ N.
        f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

  For example

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

  So, we return 5.

I solved the problem correctly, however my solution is not the optimized one. Here is my solution:

public int maxArr(List<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int i = 0; i<A.Count; i++)
    {
        for (int j= A.Count-1; j>i;j--)
        {
            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum > maxSum) maxSum = sum;
        }
    }

    return maxSum;
}

So I understand with bigger lists or arrays nested loops might not be a good idea, but what can I do to optimize this solution?

Update: I also tried removing nested loops

public int maxArr(List<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int k = 0; k<(A.Count)*(A.Count); k++)
    {
        int i = k/A.Count;
        int j = k%A.Count;

            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum > maxSum) maxSum = sum;

    }

    return maxSum;
}

Still this exceeds time limit.

There is a (simple) linear time (and by necessity space) solution. My thanks to 'random person next to me' for being a Rubber Duck in this process.

It's really very simple: observe that |Ai - Aj| + |i - j| is just the maximum of 4 other functions: + Ai + i - Aj - j, + Ai - i - Aj + j, - Ai + i + Aj - j, - Ai - i + Aj + j.

Knowing this, we can compute one half of each of these (e.g. + Ai + i) for each value in linear time and store them in an array. Now the half-clever bit is this: if we 'look' at point j, we know that if our best partner (i) is to the left of us (i.e. i <= j) that it is the i to the left of us with either the largest + Ai + i or - Ai - i, to which we will add - Aj - j or + Aj - j to compute the result. The same is true for the j to our left, (excluding our current j), and for the j next to him, etc. This means we can compute the 'best' is for the js to their right all at the same time (linear) and then just look them up when we compare them to each j. The same can be said for j < i.

Duly, we can compute 4 arrays, one for each of the 4 functions that we need to find the maximum of, but only containing the Ai and i components, and replace any element smaller than any element to the right (or left) with the greatest element to it's right (or left):

With these 4 arrays built (in linear time) we can loop through the array, computing the other half (e.g. - Aj - j) and find the max of adding each half to it's corresponding other half. Our solution is then just the max of these sums.

In actuality, this can be implemented very cleanly as just 1 pass over the original array, where we keep track of the largest + Ai + i and - Ai + i, and compare it to the current Aj and j sums (we can argue from symmetry that going the other way is pointless - we know that the optimal has a 'left' and a 'right', we only need to look at one of them).

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
public static int SimpleSuperiorMaxArr(int[] A)
{
    int best = 0; // known lower bound

    int bestPosi = 0;
    int bestNegi = 0;
    bool first = true;

    for (int i = 0; i < A.Length; i++)
    {
        int posi = A[i] - i;
        int negi = -A[i] - i;

        if (first || posi > bestPosi)
        {
            bestPosi = posi;
        }

        if (first || negi > bestNegi)
        {
            bestNegi = negi;
        }

        int posj = -A[i] + i;
        int negj = A[i] + i;

        int pos = bestPosi + posj;
        int neg = bestNegi + negj;

        int m = Math.Max(pos, neg);

        if (m > best)
        {
            best = m;
        }

        first = false;
    }

    return best;
}

owing to the algorithms simplicity, we can implement it in Excel without any trouble at all!

All of the functions are as on the left, with the 'best' rows being the max of the current value and the previous (or just current for the first column). Note that it works left-to-right, so the 'best' rows never decrease in value to the right. The 'ans' is just the max of all of the bottom pair of rows.

Edit: old code kept for posterity:

This code isn't the highest quality code ever, but it seems to work.

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
public static int SuperiorMaxArr(int[] A)
{
    // Computes the array of Ai * ac + i * ic
    int[] ComputeInfoArray(int ac, int ic) // for our case, ic and direction are equal
    {
        int direction = -ic; // if we are adding i, then we are the 'right' array, otherwise we are 'left' array
        int[] iarr = new int[A.Length];

        bool first = true;
        int b = 0; // current best

        int s = direction > 0 ? 0 : A.Length - 1;
        int e = direction > 0 ? A.Length : -1;

        for (int i = s; i != e; i += direction)
        {
            int t = A[i] * ac + i * ic;

            if (first || t > b)
            {
                first = false;
                b = t;
            }

            iarr[i] = b;
        }

        return iarr;
    }

    int[] LeftLow = ComputeInfoArray(1, -1); // + Ai - i
    int[] LeftHigh = ComputeInfoArray(-1, -1); // - Ai - i
    int[] RightLow = ComputeInfoArray(1, 1); // + Ai + i
    int[] RightHigh = ComputeInfoArray(-1, 1); // - Ai + i

    int best = 0; // known lower bound

    for (int j = 0; j < A.Length; j++)
    {
        int ll = LeftLow[j] + j - A[j];
        int lh = LeftHigh[j] + j + A[j];
        int rl = RightLow[j] - j - A[j];
        int rh = RightHigh[j] - j + A[j];

        // in truth, we can just compute ll + lh

        int max = Math.Max(Math.Max(ll, lh), Math.Max(rl, rh));

        if (max > best)
            best = max;
    }

    return best;
}


Given an integer array A and a range, find a subarray within the range with a minimum sum Problem

HackerRank Range query:

  You are given an array A of n integers. You have to perform m
  queries on the array. The queries are of two types:

  Modify the ith element of the array.
  Given x, y, print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}.

  Note: A brute force solution may not work; Try using an efficient data structure. Use fast I/O to avoid TLE.

  Input Format

  The first line contains an integer t denoting the number of test
  cases.

  The next line consists of an integer n.

  The following line contains n integers representing the array A.

  The next line contains an integer m denoting the number of queries.

  The following m lines contain integers of the form given below.

  0 x y: modify Ax into y
  1 x y: print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}

  Constraints

    1 ≤ t ≤ 100

    1 ≤ n ≤ 50000

    -10000 ≤ Ai ≤ 10000

    0 ≤ m ≤ 50000

  Output Format

  For each query print the output as specified.

My Solution

Algorithm

Calculate prefix sums prefix_sums for the given array.
For the given interval, move from left to right and keep track of the largest encountered value max_prefix_sum of prefix_sums and the minimum subsum min_subsum (min_subsum = min(prefix_sums[i] - max_prefix_sum) for left=<i<=right). In the end, min_subsum is the answer.
If some value of the initial array is updated then prefix_sums must be updated accordingly.

The overall time complexity of the algorithm is O(n2). The space complexity is O(n). I know that for a O(n2) time complexity solution I don't need any additional array and there's a more elegant solution for this based on Maximum Subarray Problem. However, it feels like with prefix sums I have a better chance of having a O(nlogn) or O(n1.5) time complexity solution.

Code

import itertools

class MinSumRangeQuery:
    prefix_sums = None

    def __init__(self, array):
        self.prefix_sums = list(itertools.accumulate(array))

    def update(self, index, value):
        diff = value - array[index]
        for i in range(index, len(self.prefix_sums)):
            self.prefix_sums[i] += diff

    def min_subarray_sum(self, left, right):
        if left == right:
            return self.prefix_sums[left]

        min_subsum = 99999999
        max_prefix_sum = self.prefix_sums[left - 1]
        for i in range(left, right + 1):
            current_subsum = self.prefix_sums[i] - max_prefix_sum

            if min_subsum > current_subsum:
                min_subsum = current_subsum

            if max_prefix_sum <= self.prefix_sums[i]:
                max_prefix_sum = self.prefix_sums[i]

        return min_subsum

for _ in range(int(input())):
    n = int(input())
    array = [int(i) for i in input().split()]
    array.insert(0, 0)
    minSumRangeQuery = MinSumRangeQuery(array)

    for _ in range(int(input())):
        a, x, y = [int(i) for i in input().split()]
        if a == 1:
            print(minSumRangeQuery.min_subarray_sum(x, y))
        elif a == 0:
            if array[x] != y:
                minSumRangeQuery.update(x, y)

Question

Given the constraints above, the code times out for all but a default test case. What's a more efficient way to solve the problem?

Introduction
I have come up with a more efficient solution in terms of the time complexity, although it's still not passing all the test cases. Nevertheless, I decided to post the solution, because it may help someone with a similar problem in the future.
Explanation
The idea is to divide an initial array into segments of size √n, and for each segment to pre-calculate 4 helper arrays - sum of elements, minimum sum of elements, minimum prefix sum (minimum sum starting from the first element of the bucket) and minimum suffix sum (minimum sum ending at the last element of the bucket).
In such case, there are 3 possible use cases when calculating the min sum:

Sum range is within the same bucket. Then, to calculate the minimum subsum there, do it brute force.

Sum range starts in one bucket and ends in a neighbouring bucket. Again, do brute force.

Sum range covers more than 2 buckets. That's the hardest case, and that's what for all the additional arrays are built. The minimum sum in the range can happen to be a minimum subsum in some bucket, or a minimum prefix, or a suffix, or a sum of the min suffix and prefix (both buckets are in the range), or a sum of all elements in the current bucket and "special" sum from previous matching buckets. The "special" sum is either a min suffix from the preceding matching bucket or sum of elements starting from some min suffix. Please see the code for more details.

When a value is updated, all 4 helper arrays have to be updated too, and that is done in O(√n) time.
Code
import math
import sys

class MinSumRangeQuery:
    size = None
    array = None

    bucket_size = None
    bucket_sums = None
    min_prefix_sums = None
    min_suffix_sums = None
    min_subarray_sums = None

    def __init__(self, array):
        self.size = len(array)
        self.array = array

        self.bucket_size = int(math.sqrt(self.size))
        self.bucket_sums = [None] * (self.bucket_size)
        self.min_prefix_sums = [None] * (self.bucket_size)
        self.min_suffix_sums = [None] * (self.bucket_size)
        self.min_subarray_sums = [None] * (self.bucket_size)

        left = 0
        for i in range(self.bucket_size):
            right = left + self.bucket_size

            # sum of elements in a bucket
            self.bucket_sums[i] = sum(self.array[left:right])
            # calculate a min sum starting from the left position
            self.min_prefix_sums[i] = self.find_min_prefix(left, right)
            # calculate a min sum ending at the right position
            self.min_suffix_sums[i] = self.find_min_suffix(left, right)
            # calculate a min sum within the bucket
            self.min_subarray_sums[i] = self.find_min_subsum(left, right)
            left += self.bucket_size

    def find_min_prefix(self, left, right):
        min_prefix = self.array[left]
        current_prefix = min_prefix
        for i in range(left + 1, right):
            current_prefix += self.array[i]
            if current_prefix < min_prefix:
                min_prefix = current_prefix

        return min_prefix

    def find_min_suffix(self, left, right):
        min_suffix = self.array[right - 1]
        current_suffix = min_suffix
        for i in range(right - 2, left - 1, -1):
            current_suffix += self.array[i]
            if current_suffix < min_suffix:
                min_suffix = current_suffix

        return min_suffix

    def find_min_subsum(self, left, right):
        current_min_subsum = 0
        min_subsum = sys.maxsize

        for i in range(left, right):
            current_min_subsum = min(current_min_subsum + self.array[i],
                                     self.array[i])
            if current_min_subsum < min_subsum:
                min_subsum = current_min_subsum

        return min_subsum

    def find_min_in_range(self, left, right):
        current_bucket_id = int(left / self.bucket_size)
        end_bucket_id = int(right / self.bucket_size)
        current_right = min((current_bucket_id + 1) * self.bucket_size, right)

        current_min_subsum = self.find_min_suffix(left, current_right)
        min_sum = self.find_min_subsum(left, current_right)

        current_bucket_id += 1
        while current_bucket_id < end_bucket_id:
            min_prefix = self.min_prefix_sums[current_bucket_id]
            min_subsum = self.min_subarray_sums[current_bucket_id]
            min_suffix = self.min_suffix_sums[current_bucket_id]

            min_sum = min(min_sum, min_prefix + current_min_subsum)
            min_sum = min(min_subsum, min_sum)

            current_min_subsum = min(current_min_subsum + self.bucket_sums[current_bucket_id],
                                     min_suffix)
            min_sum = min(current_min_subsum, min_sum)

            current_bucket_id += 1

        current_left = current_bucket_id * self.bucket_size
        #if current_left < right:
        min_prefix = self.find_min_prefix(current_left, right)
        min_sum = min(current_min_subsum + min_prefix, min_sum)
        min_sum = min(self.find_min_subsum(current_left, right), min_sum)

        return min_sum

    def update(self, index, value):
        bucket_index = int(index / self.bucket_size)
        if bucket_index < self.bucket_size:
            self.bucket_sums[bucket_index] += (value - self.array[index])
        self.array[index] = value
        if bucket_index < self.bucket_size:
            left = bucket_index * self.bucket_size
            right = left + self.bucket_size
            self.min_suffix_sums[bucket_index] = self.find_min_suffix(left, right)
            self.min_prefix_sums[bucket_index] = self.find_min_prefix(left, right)
            self.min_subarray_sums[bucket_index] = self.find_min_subsum(left, right)

tests = int(input())

for i in range(tests):
    size = int(input())

    array = [int(i) for i in input().split()]

    minSumRangeQuery = MinSumRangeQuery(array)

    queries = int(input())

    for _ in range(queries):
        a, x, y = [int(i) for i in input().split()]
        x -= 1

        if a == 1:
            print(minSumRangeQuery.find_min_in_range(x, y))
        elif a == 0 and array[x] != y:
            minSumRangeQuery.update(x, y)

Algorithm Complexity
Time complexity of the algorithm is O(n√n), and space complexity is O(√n) because 4 arrays for each bucket have to be maintained.


Find two equal substrings in a string I have various strings that contain codes, e.g. like this:

"file = new JarFile(new File()" + "\nSystem.out.println(file"

but also

"args"

Now I want to find the substring that is in the beginning and in the end of the string. E.g. in the first case the result would be file. In the second example the result has to be args

I now wrote the following method:

public static String findWord(String text) {
        String result = null;
        boolean found = false;
        for (int i = 0; i < text.length(); i++) {
            for (int j = 0; j < text.length(); j++) {
                String first = text.substring(0, i*j);
                String last = text.substring(text.length() - i*j, text.length());
                if (first.equals(last) && first.length() > 0) {
                    result = first;
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }
        return result;
    }

This seems to work for the test cases I tested, but I'm not sure if it works for all cases. Additionally, I'm not sure if there isn't a simpler solution. I need two loops and ugly break statements. So how could I improve that?

I'm not completely sure about the requirements, but what about the following?

public static String findWord2(final String text) {
    for (int i = text.length() - 1; i > 0 ; i--) {
        final String first = text.substring(0, i);
        final String last = text.substring(text.length() - i);
        if (first.equals(last)) {
            return first;
        }
    }
    return text;
}

Here are my tests:

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class FindWords2Test {

    private final String expected;
    private final String input;

    public FindWords2Test(final String expected, final String input) {
        this.expected = expected;
        this.input = input;
    }

    @Parameters
    public static Collection<String[]> data() {
        //@formatter:off
        final String[][] data = new String[][] {
                {"file", "file = new JarFile(new File()\nSystem.out.println(file"},
                {"file ", "file = new JarFile(new File()\nSystem.out.println(file "},
                {"file = new JarFile(new File()\nSystem.out.println(",
                    "file = new JarFile(new File()\nSystem.out.println("},
                {"args", "args"},
                {"", ""},
                {"a", "a"},
                {"a", "aa"}};
        //@formatter:on
        return Arrays.asList(data);
    }

    @Test
    public void testFindWords() throws Exception {
        assertEquals(expected, FindWords2.findWord2(input));
    }
}


Website user password verification I have a login web page where a user enters their email and password and I need to check if:

the entered email exists in the DB and
the entered password matches the hashed one from the db.

The password in the DB was hashed with

$pw = password_hash($_POST["pw"], PASSWORD_BCRYPT);

and is stored in a VARCHAR(255) column.
Email is set to primary and unique in the DB so there cannot be a duplicate record for this.

To achieve the above I came to the below which works as intended for me.
However, since I am new to this and because of the double DB connection I was wondering if there is a way to shorten or otherwise improve this code.

$email = $_POST["email"];
$pw = $_POST["pw"];

$stmt = $conn->prepare("SELECT email FROM Users WHERE email = ?");
$stmt->bind_param('s', $email);
$stmt->execute();
$result = $stmt->get_result();
if(mysqli_num_rows($result) == 0){
    echo "Email has not been registered yet";
}else{
    $stmt = $conn->prepare("SELECT pw FROM Users WHERE email = ? LIMIT 1");
    $stmt->bind_param('s', $email);
    $stmt->execute();
    $result = $stmt->get_result();
    $pwHashed = $result->fetch_assoc();
    if(password_verify($pw, $pwHashed["pw"])){
        echo "Password correct";
    }else{
        echo "Password incorrect";
    }
}

You really don't need two queries to do this. You can just use your second query, and if it doesn't return any results, report that. Eg:

$stmt = $conn->prepare("SELECT pw FROM Users WHERE email = ? LIMIT 1");
$stmt->bind_param('s', $email);
$stmt->execute();
$result = $stmt->get_result();

if(mysqli_num_rows($result) == 0){
    echo "Email has not been registered yet";
}

$pwHashed = $result->fetch_assoc();
if(password_verify($pw, $pwHashed["pw"])){
    echo "Password correct";
}else{
    echo "Password incorrect";
}

Other than this, your code looks good. You use prepared statements, so it's secure, and your style is consistent and easy to read. I would probably write pw as password as it's more readable, but otherwise everything looks good.


Finding the keys of map with the highest values (equality may occur) I am currently implementing a Poker game, I have created all the logic for getting the rank of a hand, and I now have to determine the winner of a given hand.

Due to this being Poker, there may be multiple winners in a round. I, therefore, need to find all the keys (Player) that have the best hand (regardless of how many there are).

   public Map<Player, Hand> determineWinner(Map<Player, Hand> hands) {
        // Initialize worst possible hand (any hand beats this) - less verbose than
        // having to get a random element form the map
        Hand currentBestHand = new Hand(RankType.HIGH_CARD, CardRank.DEFAULT, new ArrayList<>(), new ArrayList<>());
        Map<Player, Hand> bestHands = new HashMap<>();
        for (Map.Entry<Player, Hand> playerAndHand : hands.entrySet()) {
            int comparisonValue = playerAndHand.getValue().compareTo(currentBestHand);
            if (comparisonValue > 0) {
                currentBestHand = playerAndHand.getValue();
                bestHands.clear();
                bestHands.put(playerAndHand.getKey(), playerAndHand.getValue());
            } else if (comparisonValue == 0) {
                bestHands.put(playerAndHand.getKey(), playerAndHand.getValue());
            }
        }
        return bestHands;
    }

However, I am using Java 8 and thus a lot of streams. I couldn't figure out a (pretty) way to implementing the above in streams, and therefore ended up coding it in a loop. I welcome any suggestions, especially those related to writing it succinctly and efficiently using Java 8 streams.

To use streams you'd have to make the score part of the object (at least on an intermediate level) so that you can find the maximum based on the score.

Here's a little example based on a string/string map and String.length() as score replacement (as I don't have your original objects). Should be sufficient to illustrate the idea:

    Map<String, String> m = ...

    Map<Integer, List<Entry<String, String>>> intermediateByScore = m.entrySet().stream()
        .collect(Collectors.groupingBy(e -> e.getValue().length()));

    Entry<Integer, List<Entry<String, String>>> highest = intermediateByScore.entrySet().stream()
        .sorted((e1, e2) -> e2.getKey().compareTo(e1.getKey()))
        .findFirst()
        .get();

    Map<String, String> result = highest.getValue().stream()
        .collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue()));

... or, after a few inlines of intermediate variables:

    Map<String, String> result = m.entrySet().stream()
        .collect(Collectors.groupingBy(e -> e.getValue().length()))
        .entrySet().stream()
        .sorted((e1, e2) -> e2.getKey().compareTo(e1.getKey()))
        .findFirst()
        .get().getValue().stream()
        .collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue()));

Is this better than the loop: I don't personally think so. My advice: stick to your loop or revise your data structures to better support this approach.


Refactor foreach loops I have 2 objects and I am comparing them to see which fields are equal and which are different.

But I am not sure my loop is 100% correct. Does this look ok?  If so, what other ways could this be coded to make it 'neater'.  e.g. using LINQ

I want to: loop through each DocumentType in both objects, and for each documentType - I want to loop through each DocumentTypeVersion and compare this.

foreach (DocumentType documentType in documentTypes)
{
    foreach (DocumentType importDocumentType in importedDocumentTypes)
    {

        if (documentType.Id == importDocumentType.Id)//ensure its the same documentType we are comparing
        {
            foreach (DocumentTypeVersion version in documentType.Versions)
            {
                foreach (DocumentTypeVersion importedVersion in importDocumentType.Versions)
                {
                    if (version.Id == importedVersion.Id)//ensure its the same documentTypeVersion we are comparing
                    {
                        //check if the versions are equal
                        bool areVersionsEqual = Equals(version, importedVersion);

                    }

                }
            }
        }
    }
}

An option would be to create two IEqualityComparers; one for DocumentType and one for DocumentTypeVersion. You could then easily call Intersect() and get the correct ones.

public class DocumentTypeIdComparer : IEqualityComparer<DocumentType>
{
    public bool Equals(DocumentType docType1, DocumentType docType2)
    {
        return !(docType1 == null || docType2 == null) && docType1.Id == docType2.Id;
    }
}

public class DocumentTypeVersionComparer : IEqualityComparer<DocumentTypeVersion>
{
    public bool Equals(DocumentTypeVersion docTypeVersion1, DocumentTypeVersion docTypeVersion2)
    {
        return !(docTypeVersion1 == null || docTypeVersion2 == null) && Object.Equals(docTypeVersion1, docTypeVersion2);
    }
}

You will then be able to reduce your code to this;

var equalDocumentsById = documentTypes.Intersect(importDocumentTypes, new DocumentTypeIdComparer());
var equalVersions = documentTypes.Versions.Intersect(importDocumentTypes.Versions, new DocumentTypeVersionComparer());
var equalDocuments = equalDocumentsById.Where(doc => doc.Versions.Intersect(equalVersions, new DocumentTypeVersionComparer()).Any());

And then process equalDocuments as you please. If you want the documents which are not equal, simply switch .Count > 0 with .Count == 0.


Leaderboard in Python3 Could someone tell me their opinion on my leaderboard system?

library

#!/usr/bin/env python3
def write_score(score, name, scores, filename, splitter=','):
    """writes a score with a name to a file, in a specified format"""
    score_tuple = (score,name)
    scores.append(score_tuple)
    with open(filename,'w') as f:
        for s in scores:
            f.write(str(s[0]) + splitter + s[1] + '\n')
        f.close()

def read_scores(filename, splitter=','):
    """reads scores and names from a file, and returns a list of each"""
    with open(filename) as f:
        raw_scores = f.read().strip().split('\n')
        f.close()

    scores = []
    names = []

    for score in raw_scores:
        score_split = score.split(splitter)
        scores.append(int(score_split[0]))
        names.append(score_split[1])
    return scores, names

def sort_scores(scores, names,reverse_bool=True):
    """sorts the scores from greatest to least and returns in a list of tuples format"""
    zipped = sorted(list(zip(scores,names)), reverse=reverse_bool)
    return zipped

def print_scores(score_list, seperator=' ', top_amount=5):
    """prints the number of leaderboard scores stated"""
    for score_tuple in score_list[:top_amount]:
        print(str(score_tuple[0]) + seperator + score_tuple[1])

def has_better_score(score, scores, leaderboard_len=5):
    """returns if the score should be written to a file"""
    if (len(scores) > leaderboard_len and score >= scores[leaderboard_len - 1][0]) or len(scores) <= leaderboard_len:
        return True
    return False

leaderboard.txt

123 | jimmy
16 | bill
12 | Pete
10 | Jim2
10 | Jim
6 | henry is cool
5 | Bob
3 | Jane
223 | billy

Small Program

import leaderlib as ll
if __name__ == '__main__':
    try:
        while True:
            scores, names = ll.read_scores('leaderboard.txt',' | ')
            sorted_scores = ll.sort_scores(scores, names)
            ll.print_scores(sorted_scores, ' = ', 5)

            new_name = input('Name > ')
            new_score = int(input('Score > '))
            if ll.has_better_score(new_score, sorted_scores, 5):
                ll.write_score(new_score, new_name, sorted_scores, 'leaderboard.txt', ' | ')
            else:
                print('not on the leaderboard...')
            print('\n\n\n')
    except KeyboardInterrupt:
        exit()

The customary name for what you called splitter would be delimiter or sep (the letter is used e.g. in split, the former for example in numpy). Regardless of what you choose, you should be consistent, right now you use both splitter and then later separator.

When using the with..as construct (as you should), you don't need to manually close the file. This is one of the reasons of why you should use it in the first place.

In your function write_score, you should use str.join.

In read_scores you can directly iterate over the lines of the file, which is a lot more memory-efficient. You can also use tuple assignment to make it clearer what is what.

In sort_scores, you can use sorted directly on zip, there is no need to cast it to a list first. You can also return the result right away.

In has_better_score you can just return the result of the comparisons.

In print_scores you can use str.join again.

#!/usr/bin/env python3

def write_score(score, name, scores, filename, splitter=','):
    """writes a score with a name to a file, in a specified format"""
    scores.append((score, name))
    with open(filename,'w') as f:
        for s in scores:
            f.write(splitter.join(map(str, s)) + '\n')

def read_scores(filename, splitter=','):
    """reads scores and names from a file, and returns a list of each"""
    scores = []
    names = []

    with open(filename) as f:
        for score in f:
            score, name = score.strip().split(splitter)
            scores.append(int(score))
            names.append(name)
    return scores, names

def sort_scores(scores, names, reverse_bool=True):
    """sorts the scores from greatest to least and returns in a list of tuples format"""
    return sorted(zip(scores,names), reverse=reverse_bool)

def print_scores(score_list, splitter=' ', top_amount=5):
    """prints the number of leaderboard scores stated"""
    for score_tuple in score_list[:top_amount]:
        print(splitter.join(map(str, score_tuple)))

def has_better_score(score, scores, leaderboard_len=5):
    """returns if the score should be written to a file"""
    return (len(scores) > leaderboard_len and score >= scores[leaderboard_len - 1][0]) or len(scores) <= leaderboard_len:

In your "small program", catching KeyboardException and then just exiting is not really different from letting the exception rise all the way to the top. Also, exit() should only be used in the interactive session, use sys.exit() in a script instead (because it allows passing of a return value).