httprequest to php login system I'm trying to make a login system for my website which I'll be releasing in public later on. I have inserted some main samples of my code in here and I would like some useful advise or suggestions. Also if I'm doing anything unsafe or anything which may cause problems in future please let me know. Thanks

login.inc.php:

<?php
    error_reporting(0);
    $error_message = "Website ran into an error";
    session_start();
    if (isset($_SESSION['user_id'])) {
        exit();
    }
    $parameters = json_decode(file_get_contents('php://input'), true);

    if (isset($parameters["inserted_id"]) && isset($parameters["inserted_password"])) {
        // FOR TEST USE I'M USING xampp server, localhost
        $connection = mysqli_connect("localhost", "root", "", "users") or die($error_message);
        $inserted_id = $parameters['inserted_id'];
        $inserted_password = $parameters['inserted_password'];

        $statement = mysqli_stmt_init($connection) or die($error_message);
        if (mysqli_stmt_prepare($statement, "SELECT id, account_name, password FROM user WHERE account_name=? OR email=?;")) {
            mysqli_stmt_bind_param($statement, "ss", $inserted_id, $inserted_id);
            mysqli_stmt_execute($statement) or die($error_message);
            if (($row = mysqli_fetch_assoc(mysqli_stmt_get_result($statement))) == null) {
                echo("No records found with inserted inputs");
                mysqli_stmt_close($statement);
                mysqli_close($connection);
                exit();
            } else {
                if (password_verify($inserted_password, $row['password'])) {
                    $_SESSION['user_id'] = $row['id'];
                    $_SESSION['account_name'] = $row['account_name'];
                    echo("pass");
                } else {
                    echo("Wrong password");
                }
                mysqli_stmt_close($statement);
                mysqli_close($connection);
                exit();
            }
        }
        mysqli_close($connection);
        exit();
    }
?>

login.js:

var request_sent = false;
document.querySelector("button").onclick = function () {
  if (!request_sent) {
    var inserted_id = document.getElementById("inserted_id").value;
    var inserted_password = document.getElementById("inserted_password").value;
    if (inserted_id == "" || inserted_password == "") {
      alert("Both fields need to be filed out");
    } else {
      request_sent = true;
      http_request("login.inc.php", JSON.stringify({"inserted_id":inserted_id, "inserted_password":inserted_password}));
        }
    }
}

function http_request(url, params) {
  $.ajax({
    type: "POST",
    url: url,
    data: params,
    success: function(data) {
      if (data == "pass") {
          window.open("../website", "_self", "", false);
      } else {
          alert(data);
      }
      request_sent = false;
    }
  });
}

login.html:

<html>
<head>
  <title></title>
</head>
<body>
  <input id="inserted_id" type="text" placeholder="Account Name/e-mail"/>
  <input id="inserted_password" type="password" placeholder="Password"/>
  <button>SUBMIT</button>
  <script src="login.js"></script>
</body>
</html>

isset() accepts multiple parameters, you can simplify:

if (isset($parameters["inserted_id"]) && isset($parameters["inserted_password"])) {

To

if (isset($parameters["inserted_id"], $parameters["inserted_password"])) {

When ever I read anyone's code or database schema and I see any mention of id, I immediately assume that I am dealing with a positive integer.  If the value is anything other than a positive integer, I never use id in the field/column/variable name.
I never use mysqli's init() call because it is optional.  I'll recommend objected-oriented mysqli syntax because it is less verbose.
I don't think I'd json encode/decode your form data -- it seems like unnecessary extra data handling.  See here: jQuery Ajax POST example with PHP
echo doesn't need those parentheses.
I am confident that @YourCommonSense will post a comprehensive answer containing the 3 pieces of commented advice and more, so I'll leave those recommendations to him.
You don't need to write out all those close() calls, just echo your message and let the script end naturally.  If you're going to kill the script at if (isset($_SESSION['user_id'])) { be sure to sure to echo something for consistency.
I find javascript alert() boxes to be terribly annoying and a bit trashy to be honest.  Give your site some "class" and fashion an attractive presentation for any response messages that you plan to offer.
Your .html has form fields, but no form -- that doesn't feel valid to me.  I'll recommend adding the form tags and names attributes.  Some discussions: https://stackoverflow.com/q/33370025/2943403


Get time table from 4 attributes I have an entity with opening and closing times and I have to list timetable in HTML label.

Times can be empty.
Ugly attribute names getHorarioMIni or getHorarioTFin cannot be changed due external DB relations and the auto-populating methods.

How to optimize this function:

public String getTimetable() {
    final String SEPARATOR = " - ";
    final String NEW_LINE = "
";
    StringBuilder sb  = new StringBuilder();

    if (nNoE(getHorarioMIni()))
        sb.append(getHorarioMIni());
    if (nNoE(getHorarioMIni()) && nNoE(getHorarioMFin()))
        sb.append(SEPARATOR);
    if (nNoE(getHorarioMFin()))
        sb.append(getHorarioMFin());

    if ((nNoE(getHorarioMIni()) || nNoE(getHorarioMFin())) && (nNoE(getHorarioTIni()) || nNoE(getHorarioTFin())))
        sb.append(NEW_LINE);

    if (nNoE(getHorarioTIni()))
        sb.append(getHorarioTIni());
    if (nNoE(getHorarioTIni()) && nNoE(getHorarioTFin()))
        sb.append(SEPARATOR);
    if (nNoE(getHorarioTFin()))
        sb.append(getHorarioTFin());

    System.out.println(sb);
    return sb.toString();
}

private boolean nNoE(String toCheck) {
    return  toCheck != null && !toCheck.isEmpty();
}

Expected outputs (just commenting example constructor attributes):

08:00 - 12:00
15:00 - 18:00
15:00 - 18:00
08:00 - 12:00
08:00 - 12:00
18:00

Extra
There is an easy way to achieve this? if only one of each group (T and M) filled?

08:00 - 18:00

MCVE

To test it you can copy paste in a java class named Main and execute

class Main {
    public static void main(String args[]) throws Exception {
        Silo silo = new Silo();
        System.out.println(silo.getHorarios());
    }
}

class Silo {

    public Silo() {
        // comment any time to check different outputs.
        this.horarioMIni = "8:00";
        this.horarioMFin = "12:00";

        this.horarioTIni = "15:00";
        this.horarioTFin = "18:00";
    }

    // M group (morning)
    private String horarioMIni;
    private String horarioMFin;
    // T group (evening)
    private String horarioTIni;
    private String horarioTFin;

    public String getHorarioMIni() {
        return horarioMIni;
    }
    public void setHorarioMIni(String horarioMIni) {
        this.horarioMIni = horarioMIni;
    }
    public String getHorarioMFin() {
        return horarioMFin;
    }
    public void setHorarioMFin(String horarioMFin) {
        this.horarioMFin = horarioMFin;
    }
    public String getHorarioTIni() {
        return horarioTIni;
    }
    public void setHorarioTIni(String horarioTIni) {
        this.horarioTIni = horarioTIni;
    }
    public String getHorarioTFin() {
        return horarioTFin;
    }
    public void setHorarioTFin(String horarioTFin) {
        this.horarioTFin = horarioTFin;
    }
    public String getHorarios() {
        final String SEPARATOR = " - ";
        final String NEW_LINE = "
";
        StringBuilder sb  = new StringBuilder();

        if (nNoE(getHorarioMIni()))
            sb.append(getHorarioMIni());
        if (nNoE(getHorarioMIni()) && nNoE(getHorarioMFin()))
            sb.append(SEPARATOR);
        if (nNoE(getHorarioMFin()))
            sb.append(getHorarioMFin());

        if ((nNoE(getHorarioMIni()) || nNoE(getHorarioMFin())) && (nNoE(getHorarioTIni()) || nNoE(getHorarioTFin())))
            sb.append(NEW_LINE);

        if (nNoE(getHorarioTIni()))
            sb.append(getHorarioTIni());
        if (nNoE(getHorarioTIni()) && nNoE(getHorarioTFin()))
            sb.append(SEPARATOR);
        if (nNoE(getHorarioTFin()))
            sb.append(getHorarioTFin());

        System.out.println(sb);
        return sb.toString();
    }

    private boolean nNoE(String toCheck) {
        return  toCheck != null && !toCheck.isEmpty();
    }

}

Working around 'ugly' method names

Ok, so you realized you are constrained by the getter names due to some 'configuration-by-convention' features of your application/framework. If you think this can be fixed permanently in the future, and require a short-term workaround, you can consider having wrapper methods to... remind you to have the permanent fix sooner than later?

public String getHorarioTIni() {
    return getEveningStartTime();
}

// use this instead
public String getEveningStartTime() {
    // here's hoping you get to rename the field names too
    return horarioTIni;
}

Also, you mentioned the getters only, so I guess there's no excuse for nNoE(). :) Reading it as isNotNullAndEmpty() is easier on the brains.

Avoiding code repetition

If you take a closer look at what you're doing now, it really boils down to these steps:

Define a 'duration description' (DD) as a start time, an optional separator, and an end time. The separator is required when both times are present.
Construct a DD for the AM session.
If there are DDs for both AM and PM sessions, insert the newline.
Construct a DD for the PM session.
Concatenate the DDs for both sessions with the optional newline in between.

Therefore, you can extract step 1 as a method:

// this can be made a class field
private static final String SEPARATOR = " - ";

private static String createDescription(String startTime, String endTime) {
    StringBuilder builder = new StringBuilder(Objects.toString(startTime, ""));
    if (isNotNullAndEmpty(startTime) && isNotNullAndEmpty(endTime)) {
        builder.append(SEPARATOR);
    }
    return builder.append(Objects.toString(endTime, "")).toString();
}

Objects.toString(Object, String) is used here to make the String generation slightly more expressive.

The method body is now more compact, and hopefully more readable as a result:

public String getTimetable() {
    final String NEW_LINE = "<br>";
    String morningDuration = createDescription(getMorningStartTime(), getMorningEndTime());
    String eveningDuration = createDescription(getEveningStartTime(), getEveningEndTime());
    StringBuilder builder = new StringBuilder(morningDuration);
    if (!morningDuration.isEmpty() && !eveningDuration.isEmpty()) {
        builder.append(NEW_LINE);
    }
    return builder.append(eveningDuration).toString();
}


Conversion of an array of integers to string In order to save memory space. Strings inside an embedded device are stored in a particular way. Each 32-bit location holds up to 4 chars instead of only 1 char in the usual case.

I wrote a function that convert an encoded string back to its original string. I am new to Python, so I would like to know whether or not I can simplify my code.

The string is encoded in such way that I need to reverse the order of each group of 4 chars.

#!/usr/bin/python
def arrayOfInt2string(array):
    s = ''
    for a in array:
        a = "%0.8x" % a
        b = list()
        for i in range(0, len(a), 2):
            b.append(chr(int(a[i:i+2], 16)))
        s = s + ''.join(b.reverse())
    return s

r = (
    0x33323130,
    0x37363534,
    0x00000038,
    0x00000000
)
arrayOfInt2string(r)

The output is:

"012345678"

If you are going to be playing with string representations of native types, you probably want to take a look at the struct standard library package.

With it, you can quickly process your r as follows:

>>> import struct
>>> ''.join(struct.pack('i', rr) for rr in r)
'012345678\x00\x00\x00\x00\x00\x00\x00'

And you can play with the ordering of the characters by explicitly describing the endianess of your input:

>>> ''.join(struct.pack('>i', rr) for rr in r)  # big endian
'32107654\x00\x00\x008\x00\x00\x00\x00'


Using EqualityComparer to find contained value While searching for a method in HashSet which allows me to actually find an object in \$O(1)\$ (not just Contains, I need the reference), I came across this question on Stack Overflow and specifically the latest answer drew my attention.

I reworked the answer in a more generic approach and came up with the following;

public class EqualityComparerWithValue<T> : IEqualityComparer<T>
{
    public T Value;
    public bool Equals(T t1, T t2)
    {
        if (!(t1.GetHashCode() == t2.GetHashCode())) return false;
        if (!t1.Equals(t2)) return false;
        Value = t1;
        return true;
    }

    public int GetHashCode(T t)
    {
        return t.GetHashCode();
    }
}

Then an implementation of a potential \$O(1)\$ TryGetValue() would be something like this:

public static bool TryGetValue<T>(this HashSet<T> hs, T valIn, out T valOut)
{
    if (hs.Contains(valIn))
    {
        if (hs.Comparer is EqualityComparerWithValue<T>)
            valOut = (hs.Comparer as EqualityComparerWithValue<T>).Value;
        else
            valOut = hs.First(t => t.Equals(valIn));

        return true;
    }
    else
    {
        valOut = default(T);
        return false;
    }
}

Which will find the searched object in \$O(1)\$ if the EqualityComparerWithValue is specified in the constructor, and in \$O(n)\$ otherwise.

An implementation of this would be:

var set = new HashSet<string>(new EqualityComparerWithValue<string>());
string sOut = "";
if (set.TryGetValue("searchTerm", out sOut))
{
    //do stuff
}

Now, in my eyes, this seems to be a very legit solution. However, I'm just starting out. Are there any problems this could cause which I am overlooking? Is there any way to improve TryGetValue()?

if (!(t1.GetHashCode() == t2.GetHashCode())) return false;

Even if JIT compiler generated code will/should be the same negation operator is easy ignored during source code scanning by human beings. Because !(a == b) is effectively a != b I would rewrite it as:

 if (t1.GetHashCode() != t2.GetHashCode())
    return false;

Note I also reintroduced line breaks, it helps readability and for short functions (as they should be) there is not need to reduce vertical space.

Even if you shouldn't (generally) rely on these implementation details please
note that in your equality comparer you do not need to check for hashcode again.
HashSet already does it and it has an advantage over your code: it calculates
hashcode for item you're searching for just once. In your code you have to
calculate both hashes again and again for each comparison (and it may be slow,
according to effective data type and hashing algorithm). Please note that you shouldn't (IMO!) rely on this optimization on generic comparers because you do not have any knowledge of type implementation. Think what hashcode does for integer types, is it faster to calculate hash or to perform direct comparison? What about strings with different lengths? It may be done by a container (for example because hash is used to organize items) but, I think, a generic comparer should be ignorant of this.

if (hs.Comparer is EqualityComparerWithValue<T>)
    valOut = (hs.Comparer as EqualityComparerWithValue<T>).Value;
else
    valOut = hs.First(t => t.Equals(valIn));

You first check for type and then you cast (which implicitly check for type again). It's a waste then you may simply rewrite as this:

var comparer = hs.Comparer as EqualityComparerWithValue<T>;
valOut = comparer != null ? comparer.Value : hs.First(t => t.Equals(valIn));

On the same code block you also have a return then you don't need else, save indentation and make code clearer:

   if (hs.Contains(valIn))
   {
        var comparer = hs.Comparer as EqualityComparerWithValue<T>;
        valOut = comparer != null ? comparer.Value : hs.First(t => t.Equals(valIn));

        return true;
   }

    valOut = default(T);
    return false;

However, beside these minor micro-design stuff, what I don't agree with is solution itself. I wouldn't expect an equality comparer to keep state for at least these reasons:

It would be the only one to do it. Astonishing.
When you use your hashset you have to remember to use that comparer.
It forces you to check for types (and it's something with a pretty bad smell, IMO).
You're putting helpers inside an unrelated class. O(1) search is something related to hashset not to a specific type comparer.
It doesn't work with inherited comparers (what if I want to reuse same code with my own special IEqualityComparer<T> class?)
It's not thread-safe!

However algorithm itself probably isn't for CodeReview. What I would do to mitigate some of these issues? I would accept another
IEqualityComparer<T> as input, you decorate that comparer to keep last match
but you delegate comparison to given implementation:

public sealed class EqulEqualityComparerWithValue<T> : IEqualityComparer<T>
{
    public EqulEqualityComparerWithValue(IEqualityComparer<T> comparer = null)
    {
        _comparer = comparer ?? EqualityComparer<T>.Default;
    }

    public bool Equals(T x, T y)
    {
        if (_comparer.Equals(x, y))
        {
            Value = x;
            return true;
        }

        return false;
    }

    public int GetHashCode(T obj)
    {
        return _comparer.GetHashCode(obj);
    }

    public T Value
    {
        get;
        private set;
    }

    private IEqualityComparer<T> _comparer;
}


Convert ISBN10 to ISBN13 Looking to confirm that I am doing this in the most efficient way.

func convrtisbn10(isbn: String) {
    var checkSum: Int = 0
    var completeISBN = ""
    let newISBN = "978" + "\(isbn)"
    let result = String(newISBN.characters.dropLast(1))
    var oddSum = 0, evenSum = 0
    let reversedArray = result.characters

    for (i, s) in reversedArray.enumerate() {

        let digit = Int(String(s))!

        if i % 2 == 0 {
            evenSum += digit
        } else {
            oddSum += digit * 3
        }
    }
    let total = evenSum + oddSum
    let remander = total % 10
    if (10 - remander) == 10 {
        checkSum = 0
    } else {
        checkSum = 10 - remander
        completeISBN = result + "\(checkSum)"
    }
    getBookInfo(completeISBN)

}

It is not apparent from the function name convrtisbn10 what the
function does. Does is convert from or to ISBN-10, and from or to what?
And why does a conversion function not return anything?
You are calling getBookInfo(completeISBN) at the end of the function:
Whatever that is, it should not be part of the conversion.

The validity of the input string is not verified. If the input is too
short or too long, the result will be nonsense. If the input contains
non-digits, the function will crash.

A better function definition might be

func convertToISBN13(isbn10: String) -> String?

where the argument name indicates that is is a ISBN-10 and the function
name indicates that it is converted to a ISBN-13. The return value
is an optional, so that we can return nil for invalid input.
(An alternative would be to throw an error for invalid input.)

The type annotation in

var checkSum: Int = 0

is not necessary, also variables should be declared at the narrowest
scope where they are needed.

Setting an initial value for

var completeISBN = ""

hides an error in your program:

if (10 - remander) == 10 {
    checkSum = 0
} else {
    checkSum = 10 - remander
    completeISBN = result + "\(checkSum)"
}

In the first case the checksum is not appended to the ISBN.
The compiler does not notice that because completeISBN has a
defined value.

The string interpolation in

let newISBN = "978" + "\(isbn)"

is not necessary because isbn is already a string:

let newISBN = "978" + isbn

The variables

var oddSum = 0, evenSum = 0

are not needed, all calculations can update  checkSum directly.

It is not necessary to process the characters in reverse order.
Just process them starting with the first one (and use multiplier 3
for odd indices).

As said above,

    let digit = Int(String(s))!

would abort the program execution if s is not a number, this
should be checked.

I would move the calculation of the ISBN-13 checksum to
a separate function, which can then be used independently to
calculate or verify checksums.

Putting all this together, the code could look like this:

func checksumISBN13(isbn13: String) -> Int? {
    var checksum = 0
    for (position, char) in isbn13.characters.enumerated() {
        guard let digit = Int(String(char)) else {
            return nil
        }
        if position % 2 == 0 {
            checksum += digit
        } else {
            checksum += 3 * digit
        }
    }
    let remainder = checksum % 10
    if remainder == 0 {
        return 0
    } else {
        return 10 - remainder
    }
}

func convertToISBN13(isbn10: String) -> String? {

    guard isbn10.characters.count == 10 else {
        return nil
    }
    let isbn13 = "978" + String(isbn10.characters.dropLast())
    guard let checksum = checksumISBN13(isbn13: isbn13) else {
        return nil
    }
    return isbn13 + String(checksum)
}

Finally, note that ISBNs are usually printed in groups with a separator
(e.g. "978-3-86680-192-9"), so another suggestion is to

tolerate (not require) separator characters in the input string, and
create the output string in the grouped format.

A more universal approach would be to define a ISBN type which
can be initialized from both ISBN-10 and ISBN-13 strings (with
or without checksums). Just to give you an idea:

public struct ISBN: CustomStringConvertible {
    private let digits: [Int] // 13 digits

    public init?(isbn13: String) {
        // Verify that `isbn13` has 12 or 13 characters (ignoring separators)
        // Fill `digits`.
        // If 12 digits: append checksum.
        // If 13 digits: verify checksum.
    }

    public init?(isbn10: String) {
        // Verify that `isbn10` has 9 or 10 characters (ignoring separators)
        // Remove last character (checksum) if present.
        self.init(isbn13: "978" + isbn10)
    }

    var description: String {
        // Create and return formatted string description
    }
}


Faster track to recognizing patterns in looping through nested sequences I frequently have patterns as below, usually not this simple, which require me to first code a working solution for a single test case, and then to refactor the code to make it more concise. See the first incarnation below, then the final code. I'm looking to see what other techniques some use to skip the initial step, other than suddenly being able to see the solution with experience. Or if you would approach the example below in an entirely different fashion.

Initial code:

# 4.) A Tic-tac-toe game (see http://en.wikipedia.org/wiki/Tic-tac-toe) can be
# simulated by a computer using a 3 x 3 matrix of strings. Each string has one
# of three possible values, 'X', 'O' or '' (an empty block). Moreover,
# individual move of a player can be simulated with a tuple, containing three
# values: the x-coordinate (0..2), the y-coordinate (0..2) and a string
# containing the mark of the player ('X' or 'O'). Write a procedure
# insertMoves(board, listOfMoves), which has two parameters: a 3 x 3 matrix
# board and a list of players moves as tuples. The procedure then inserts all
# moves in a list to the game board.
def insertMoves(board, list_of_moves):
    for move in list_of_moves:
        if move[0] == 0:
            if move[1] == 0:
                (board[0])[0] = move[2]
            if move[1] == 1:
                (board[1])[0] = move[2]
            if move[1] == 2:
                (board[2])[0] = move[2]
        elif move[0] == 1:
            if move[1] == 0:
                (board[0])[1] = move[2]
            if move[1] == 1:
                (board[1])[1] = move[2]
            if move[1] == 2:
                (board[2])[1] = move[2]
        elif move[0] == 2:
            if move[1] == 0:
                (board[0])[2] = move[2]
            if move[1] == 1:
                (board[1])[2] = move[2]
            if move[1] == 2:
                (board[2])[2] = move[2]
    return board

row = [''] * 3
board = [row, row[:], row[:]]
moves = [(0, 0, 'A'), (0, 1, 'B'), (0, 2, 'C'), (1, 0, 'D'), (1, 1, 'E'),
         (1, 2, 'F'), (2, 0, 'G'), (2, 1, 'H'), (2, 2, 'I')]
final_board = insertMoves(board, moves)
for row in final_board:
    print row

And the final function definition:

def insertMoves(board, list_of_moves):
    for move in list_of_moves:
        for i in range(0, 3):
            if move[0] == i:
                for j in range(0, 3):
                    if move[1] == j:
                        (board[j])[i] = move[2]
    return board

I would write the loop like this:

for i, j, move in list_of_moves:
    assert(0 <= i < 3 and 0 <= j < 3 and move in 'XO')
    board[j][i] = move

or maybe:

VALID_MOVES = 'XO'
for i, j, move in list_of_moves:
    assert(0 <= j < len(board) and 0 <= i < len(board[j]) and move in VALID_MOVES)
    board[j][i] = move

depending on how general I needed the implementation to be.

Something that you might find helpful would be to step through your code in the Python debugger. Look at each line as it is executed and check that it makes sense. For example:

>>> board = [[''] * 3 for _ in range(3)]
>>> moves = [(1,1,'X'), (0,0,'O')]
>>> import pdb
>>> pdb.run("insertMoves(board, moves)")
> <string>(1)<module>()
(Pdb) step
--Call--
> cr32933.py(1)insertMoves()
-> def insertMoves(board, list_of_moves):
(Pdb) step
> cr32933.py(2)insertMoves()
-> for move in list_of_moves:
(Pdb) step
> cr32933.py(3)insertMoves()
-> for i in range(0, 3):
(Pdb) print move
(1, 1, 'X')
(Pdb) step
> cr32933.py(4)insertMoves()
-> if move[0] == i:
(Pdb) print i
0
(Pdb) step
> cr32933.py(3)insertMoves()
-> for i in range(0, 3):
(Pdb) step
> cr32933.py(4)insertMoves()
-> if move[0] == i:
(Pdb) print i
1

At about this point (if not earlier) you should be saying to yourself, "why did I have to go round the loop in order to discover that move[0] has the value 1?"


Replacing GitHub usernames with links A user wrote an issue asking if inside the bio (or any arbitrary tag), any tagged accounts can be automatically linked like on Github.

I gave them this function:

I was going to use string.split(" "), but then I realized that if I did that I would destroy the specific formatting of the text if I used array.join(" ") after all of the formatting changes.

Ex:
Original: "I work for the coolest companies: @aws, @microsoft, and @apple"

Joined: "I work for the coolest companies: @aws , @microsoft , and @apple"

The commas are messed up.

Is there a way to slim it down and/or simplify it?  JS isn't my strongest language.

The function you want is replace:

function link_ats(text) {
    return text.replace( /@(\w+)/g, '@$1' )
}

document.getElementById("bio").innerHTML = link_ats("The coolest company to work for is @github!  There is also @aws and @microsoft.", "bio");


Find the closest number to each given number I have a program which works but it is a bit too slow with big numbers.

nbBlocs contains the size of the array, it can be up to 20000 and I enter the value inside on each position.

nbQ is the number of queries (at most 20000 queries).  For each query, it looks inside the array and tells me which is the closest value to it (by absolute difference). So, if my array is [0,2,5,11,24,32] and the query is 10, it returns 11 because absolute difference (10-11) is the smallest.

Input example

7                    (size of array)
41 32 11 17 24 8 16  (all the values inside array)
4                    (nbQ)
9 20 28 11           (four queries)

Output

8 17 24 11

Here is my code :

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int nbBlocs;
    cin >> nbBlocs;
    int dens;
    std::vector<int> tab(nbBlocs);
    for(int i=0; i<nbBlocs; i++){
        cin >> dens;
        tab[i]=dens;
    }
    sort(tab.begin(), tab.end());
    int nbQ;
    cin >> nbQ;
    int quest;
    for(int j = 0; j<nbQ; j++){
        cin >> quest;
    int valSup=-1;
    int valInf=-1;
    int reponse=-1;
        for(unsigned int i=0;i<tab.size();i++){
            if(quest < tab[i]){
                    valSup = tab[i];
                if(i!=0)
                        valInf = tab[i-1];
                    else
                         valInf = valSup;
                }

        if(i==(tab.size()-1) && valSup == -1){
            valSup = tab[tab.size()-1];
            valInf = valSup;
        }
        if(valSup != -1 && valInf != -1){
            if(std::abs(quest - valSup) < (std::abs(quest - valInf))){
                reponse = valSup;
                break;
            }
            else if (std::abs(quest - valSup) == (std::abs(quest - valInf))){
                reponse = valInf;
                break;
            }
            else{
                reponse = valInf;
                break;
            }
        }
    }
        if (reponse != -1)
        cout << reponse << endl;
    }

}

First point: every time anybody writes code with using namespace std; at global scope, a cute, furry little animal dies a horrible death. You don't want that on your conscience, so you need to stop doing it1.

Right now, you seem to be doing a linear search. Since you've sorted the numbers, you could do a binary search instead. This could use either std::lower_bound or std::upper_bound. If the target number might be duplicated in the collection, lower_bound gives the location of the first, and upper_bound gives the location of the last of those duplicates. Since it doesn't appear that duplicates would change the results you're producing, you might prefer to just remove the duplicates with std::unique immediately after sorting (but unless you really expect duplicates in the inputs, this may waste more time than it saves).

If you also sort the nbQ numbers before searching for them, you can optimize a little more by reducing the bounds within which you do successive binary searches. Given the relatively small amount of data (20000 numbers, 20000 queries) this probably won't make a huge difference, but still might be fairly noticeable.

Other than that, you could make considerably better use of the standard algorithms and containers than you do right now. For example:

int dens;
std::vector<int> tab(nbBlocs);
for(int i=0; i<nbBlocs; i++){
    cin >> dens;
    tab[i]=dens;
}

Could be turned into:

std::vector<int> tab;
tab.reserve(nbBlocs);
std::copy_n(std::istream_iterator<int>(std::cin), nbBlocs, std::back_inserter(tab));

Looking at:

for(int j = 0; j<nbQ; j++){
    cin >> quest;
int valSup=-1;
int valInf=-1;
int reponse=-1;

[... much more]

The indentation is misleading--based on the indentation, it's not immediately apparent that all the succeeding code is executed inside that loop. This doesn't affect speed in itself, but better formatting could give a better grasp of the importance of speed of the inner loop.

Although it's also unrelated to speed, my final thought would be that your variable names seem open to considerable improvement. A few (e.g., response) aren't too bad, but quite a few (e.g., nbBlocs, nbQ, quest) seem fairly meaningless.

1. Okay, seriously, it brings a large (and unknown) number of symbols into scope. We know some of those names, but the standards reserve a fair number of other classes of names (e.g., anything starting with str) so the number of other possibilities is infinite. Bottom line: it's unnecessary and dangerous.


Calculating sum of multiple columns in pandas I have data from one data provider in very thin demographic units: Adults_18_21,Adults_22_24,Adults_25_27, etc.

Then in the original data frame that is built like this:

DemoDF = pd.DataFrame({'City':['NYC','Chicago','Nash'],'Adults_18_21':    [100,50,75],'Adults_22_24':[200,300,400],'Adults_25_27':[300,100,200]})

From another data provider, we get larger buckets of advertising data, Adults_18_27.

AdvertisingDF = pd.DataFrame({'City':     ['NYC','Chicago','Nash'],'Adults_18_27':[1,2,3]})

To multiply ad rates by demographic, I am currently creating a dictionary of tuples:

Compare_Buckets = {
'Adults_18_27':('Adults_18_21','Adults_22_24','Adults_25_27')
}

Then creating new columns based on the tuples:

for key in Compare_Buckets.keys():
        DemoDF[key] = 0
        for value in Compare_Buckets[key]:
            DemoDF[key] += DemoDF[value]

I can then take the new resulting column and join it with the AdvertisingDF based on city and do any further functions I need. There are 40+ keys in the dictionary so I thought the for loop would work best. Is there a better way or a more memory efficient way?

You can do the whole filtering and sum using pandas' builtins:

for group, individuals in Compare_Buckets.items():
    DemoDF[group] = DemoDF.filter(items=individuals).sum(axis=0)


Knapsack performance issue I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.

Problem statement
There are N
items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of wi and a value of vi
Taro has decided to choose some of the N
items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W
Find the maximum possible sum of the values of items that Taro takes home.

The input is in the following form:
N W
w1 v1
w2 v2
:
wN vN

N: Number of items.
W: Max weight I can have.
wi: ith weight.
vi: ith value.
Here is my solution to it:
using System;
using System.Collections.Generic;

public static class Solution
{
  // Both s_weights and s_values will have the same length.
  private static int[] s_weights; // array holding the weights of the items.
  private static int[] s_values; // array holding the values of the items.
  private static Dictionary<(int, int), long> s_memo; // memoization dictionary.

  // NOTE: I cannot use an array instead of a dictionary here, cause it
  // will be a very large 2d array and will give OutOfMemoryException.

  public static void Main()
  {
    // Read the first line, which contains number of items and max weight.
    string[] nw = Console.ReadLine().Split(' ');
    // Parse n.
    int n = int.Parse(nw[0]);
    // Parse the max weight.
    int maxWeight = int.Parse(nw[1]);

    s_weights = new int[n];
    s_values = new int[n];
    // arbitrary high capacity dictionary to avoid resizing which is O(n).
    s_memo = new Dictionary<(int, int), long>(10000000);

    // Read each line from the input.
    for (int i = 0; i < n; i++)
    {
      string[] wv = Console.ReadLine().Split(' ');
      s_weights[i] = int.Parse(wv[0]);
      s_values[i] = int.Parse(wv[1]);
    }
    // Start the recursion with the maximum weight and all the items.
    Console.WriteLine(Solve(maxWeight, n));
  }

  private static long Solve(int weightLeft, int numberOfItemsToConsider)
  {
    // simple base case.
    if (weightLeft == 0 || numberOfItemsToConsider == 0) return 0;

    // If already calculated, get it from the dictionary.
    if (s_memo.TryGetValue((weightLeft, numberOfItemsToConsider), out var cachedValue))
    {
      return cachedValue;
    }

    // Recursive call calculating the solution if we don't take the current item.
    long dontTakeCurrent = Solve(weightLeft, numberOfItemsToConsider - 1);
    long result;

    // Can we take the current item? If yes, calculate the solution.
    if (weightLeft >= s_weights[numberOfItemsToConsider - 1])
    {
      long takeCurrent = s_values[numberOfItemsToConsider - 1] + Solve(weightLeft - s_weights[numberOfItemsToConsider - 1], numberOfItemsToConsider - 1);
      // Maximize the value between the two cases, taking or not taking the item.
      result = Math.Max(takeCurrent, dontTakeCurrent);
      // Add the result to the memo dictionary.
      s_memo.Add((weightLeft, numberOfItemsToConsider), result);
      return result;
    }
    // Here, we don't have another choice other than not taking the item.
    result = dontTakeCurrent;
    s_memo.Add((weightLeft, numberOfItemsToConsider), result);
    return result;
  }
}
```

Instead of storing the actual values in a tuple as the key in a dictionary for memoisation, multiplex them together into a single value and use that as the key. You will need to pick multiplex value that is an order of magnitude higher than the largest "numberOfItemsToConsider" you can expect. Or you could turn them into strings and concat for the key.
i.e.
var key = (weightLeft * 10_000) + numberOfItemsToConsider; // parens for readability.
// OR
var key = weightLeft.ToString() + "_" + numberOfItemsToConsider.ToString(); // parens for readability.

EDIT: Thanks @Jeff E for correcting me on this, Hashtable is slower.
Instead of a dictionary, you could use a hashtable, which is faster. i.e.
Finally, if you're chasing every little bit of time, allocate all your variables outside of any loops, so they are not continually being reallocated, which has an expense.


Is there a better, more efficient way than Dictionary(Of Tuple(), MyClass)? Suppose I have data coming from different sources that tells me information about a large group of stores that has the following (just an example):

Necessary to define what store we're dealing with:

Store_Name (String)
Location (String)

Store characteristics:

Square_Feet (Double)
No_Employees (Double)
Years_Open (Double)
... (Whatever else)

And the structure of the program I'm working with is such that we will always get the first 2 (defining) characteristics and one or more of the store-specific characteristics. My goal is to conglomerate all the characteristics for each of the specific stores together.

To do this, I have created the following class:

Public Class StoreChars
    Public Property Square_Feet as Double = 0
    Public Property No_Employees as Double = 0
    Public Property Years_Open as Double = 0
    ...
End Class

And then, in my program, I have created the following:

Dim StoreData As New Dictionary(Of Tuple(Of String, String), StoreChars)

The key being the Store_Name and Location as the defining tuple.

So, now, in my code, supposing I just got some data together with the defining characteristics for a set of stores (might be some, might be all... we don't know if we've seen these before or not even), my loop to put in that data looks as follows:

For Each PieceOfInfo in ReturnedData
   Dim TupleKey As New Tuple(Of String, String)(PieceOfInfo.Store_Name,
                                                PieceOfInfo.Location)

   If Not StoreData.ContainsKey(TupleKey) Then
        StoreData.Add(TupleKey, New StoreChars With
                                {
                                 .Square_Feet = PieceOfInfo.Square_Feet
                                     ... (whatever else we got) ...
                                })
   Else
        StoreData(TupleKey).Square_Feet = PieceOfInfo.Square_Feet
                     ... (whatever else we got) ...
   End If
Next

But this seems to be very slow and I'm wondering if it isn't overly-processor-intensive to create a tuple in each loop, check the existence as a key, etc, but I can't think of a better way to do this.

The other solution I was thinking of was to create a Dictionary(Of String, Dictionary(Of String, StoreChars)). That would eliminate having to create a Tuple with each loop, but it would mean having to check existence of the keys in 2 separate dictionaries.

If there is a better way to do this, I would LOVE to hear what it is because I find myself having to program solutions like this fairly often!

Also, even though I wrote this code in VB, I'm just as comfortable with a C# solution - I'm just currently working in a VB environment.

If you're stuck with Tuple<T1,T2> as a key, you want to provide an IEqualityComparer<Tuple<T1,T2>> implementation in the constructor of your dictionary.

If you can change the TKey type, you might want to provide a custom class that implements IEquatable<T>.

The problem with the current code is that comparison between keys of type Tuple<string, string> is not efficient.


Avoid jQuery in click event I have the following controller:

 angular.module("UserRoles")
.controller("UserRolesController", function($http, $scope){
    $scope.usersearch = "";
    $scope.users = [];
    $scope.roles = {
    }

    $scope.getusers = function(){
        $http.get("/api/finduser/"+$scope.usersearch)
            .success(function(data){
                $scope.users = data;
            });
    }
    // returns ([ [username, userid], ... ])

    $scope.getroles = function($event){
        var uid = $($event.currentTarget).find("a").data("userid");
        $http({
            "method": "GET",
            "url":"/api/rolesbyuser/",
            "params": {"user_dn": uid}
        }).success(function(data){
            console.log(data);
            $scope.roles = data;
        });
        // returns {ldapuser: ldapusername, direct_roles: [r1, r2], inheritedroles: [ir1ir2]}
    };
});

for the following HTML:

    <form ng-submit="getusers()">

            User Suchen: {{ usersearch }}
            <input ng-model="usersearch" type="text" class="form-control"
                    placeholder="username">

    </form>

                {{ user[0] }}

{{ roles.ldapuser }}

Direkte Rollen

                    {{ role }}

Vererbte Rollen

                    {{ role }}

Everything works fine:

In the form, I search for the user, then I am getting a user list in the format [[user, id] ...] . The site presents the user name and the id is saved in the data attribute of the user. If one clicks on one of the users on the left side, angular fetches the roles for the according user and displays them.

The questions are now:

My click event looks ugly (I use jQuery). What would be the angular way to perform this?

$($event.currentTarget).find("a").data("userid")

Is there an even better way to set the user to be searched for on click?
Should I really use only one controller or should I use one for user and one for roles?

$($event.currentTarget).find("a").data("userid")

You can access the data by simply passing it into your method call. So instead of passing an event to getroles, just pass the value.

Replace your template:

                {{ user[0] }}

Then update your function:

$scope.getroles = function(uid){
    $http({
        "method": "GET",
        "url":"/api/rolesbyuser/",
        "params": {"user_dn": uid}
    }).success(function(data){
        console.log(data);
        $scope.roles = data;
    });
    // returns {ldapuser: ldapusername, direct_roles: [r1, r2], inheritedroles: [ir1ir2]}
};

Using a Service

Sometimes it's good to separate your $http calls to a service. This allows you to re-use your $http calls in other controllers. It seems like overkill, but it helps with re-use. Alternatively, you could use the $resource, which will build the service for you automatically. Unfortunately, in your case, your endpoints are different, so you'll need to roll your own service.

Each method in the service will return a promise so that future controllers can customize the success conditions.

The bonus of this is that it makes it easier to test your controller as you can easily mock out the service. You could've mocked out the $http service, but then your implementation would start to leak into your tests.

I would also recommend having the userSearch being passed into getUser as a parameter. This reduces the amount of state that your controller needs to maintain.

angular.module("UserRoles")
.service("UserRolesService", function($http) {

    this.getUsers = function(userId) {
        return $http.get("/api/finduser/" + userId);
    }

    this.getRoles = function(uid) {
        return $http.get("/api/rolesbyuser/", { params : { "user_dn" : uid } });

    }
})
.controller("UserRolesController", function($scope, UserRolesService) {

    $scope.usersearch = "";
    $scope.users = [];
    $scope.roles = {};

    $scope.getUsers = function(userId) {
        UserRolesService.getUsers(userId).success( function(data) {
            $scope.users = data;
        });
    };

    $scope.getRoles = function(uid) {
        UserRolesService.getRoles(uid).success(function(data) {
            console.log(data);
            $scope.roles = data;
        });
    };

});


Haskell 99, Problems 1-10 (simple list processing) I'm just learning Haskell and I wanted to know if I'm going in the right direction with my solving of the Haskell 99 problems.  The file of interest is here which I've also reproduced below.

module OneToTen where

{-- Problem 1: Find the last element of a list. --}
myLast :: [a] -> a
myLast [] = error "Empty list."
myLast [x] = x
myLast (x:xs) = myLast xs

{-- Problem 2: Find the last but one element of a list. --}
myButLast :: [a] -> a
myButLast [] = error "Empty list."
myButLast [x] = error "One element list."
myButLast [x,y] = x
myButLast (x:xs) = myButLast xs

{-- Problem 3: Find the Kth element of a list. The first element in the list
 -- is number 1 --}
elementAt :: [a] -> Int -> a
elementAt [] _ = error "Empty list."
elementAt (x:_) 1 = x
elementAt (_:xs) n = elementAt xs (n-1)

{-- Problem 4: Find the number of elements of a list. --}
myLength :: [a] -> Int
myLength xs = myLengthAux xs 0

myLengthAux :: [a] -> Int -> Int
myLengthAux [] acc = acc
myLengthAux (_:xs) acc = myLengthAux xs (acc+1)

{-- Problem 5: Reverse a list. --}
myReverse :: [a] -> [a]
myReverse xs = myReverseAux xs []

myReverseAux :: [a] -> [a] -> [a]
myReverseAux [] acc = acc
myReverseAux (x:xs) acc = myReverseAux xs (x:acc)

{-- Problem 7: Flatten a nested list structure. --}
data NestedList a = Elem a | List [NestedList a]

flatten :: NestedList a -> [a]
flatten xs = flattenAux xs []

flattenAux :: NestedList a -> [a] -> [a]
flattenAux (List []) acc = acc
flattenAux (Elem x) acc = x:acc
flattenAux (List (x:xs)) acc = flattenAux (List xs) (acc ++ (flattenAux x []))

{-- Problem 8: Eliminate consecutive duplicated of list elements. --}
compress :: (Eq a) => [a] -> [a]
compress [] = []
compress (x:xs) = compressAux xs x [x]

compressAux :: (Eq a) => [a] -> a -> [a] -> [a]
compressAux [] y acc = acc
compressAux (x:xs) y acc | x == y = compressAux xs y acc
                         | x /= y = compressAux xs x (acc ++ [x])

{-- Problem 9: Pack consecutive duplicates of list elements into sublists. If a
 -- list contains repeated elements they should be placed in separate sublists.
 --}
pack :: (Eq a) => [a] -> [[a]]
pack [] = error "Empty list."
pack (x:xs) = packAux xs x [x] []

packAux :: (Eq a) => [a] -> a -> [a] -> [[a]] -> [[a]]
packAux [] _ xs acc = acc ++ [xs]
packAux (x:xs) y ys acc | x == y = packAux xs y (y:ys) acc
                        | x /= y = packAux xs x [x] (acc ++ [ys])

{-- Problem 10: Run-length encoding of a list.  Use the result of problem P09
 -- to implement the so-called run0length encoding data compression method. --}
encode :: (Eq a) => [a] -> [(Int,a)]
encode [] = error "Empty list."
encode xs = map (\ys -> (length ys, head ys)) (pack xs)

I'm most curious if implementing all of these auxiliary methods is standard practice?  It's easier for me to think of a recursive problem using an accumulator, consequently, I write most of them this way.  Is this correct?  Should I be writing them differently?

Solutions 1 and 2 are fine.

Solution 3: Find the Kth element of a list

The error message for 3 is a bit misleading: you can also get the error if the requested index is beyond the end of the list.  Strictly speaking, it should be an error to request a non-positive index as well.

Solution 4: Find the number of elements of a list

You should not need a helper function.

myLength :: [a] -> Int
myLength [] = 0
myLength (x:xs) = 1 + myLength xs

However, as @Franky points out, using a helper function can make it tail-recursive.

Solution 5: Reverse a list

You could write it as myReverse (x:xs) = (myReverse xs) ++ x, but it is much more efficient the way you wrote it using a helper function.  The helper should be scoped using a where clause (or let … in, which does the same thing).  It is customary to name trivial helper functions using the myReverse' convention.

myReverse :: [a] -> [a]
myReverse xs = myReverse' xs []
  where
    myReverse' []     rev = rev
    myReverse' (x:xs) rev = myReverse' xs (x:rev)

Solution 7: Flatten a nested list structure.

No helper is necessary.

data NestedList a = Elem a | List [NestedList a]

flatten :: NestedList a -> [a]
flatten (Elem x)      = [x]
flatten (List [])     = []
flatten (List (x:xs)) = flatten x ++ flatten (List xs)

Solution 8: Eliminate consecutive duplicated list elements

Again, no helper or accumulator is necessary.  Furthermore, you should avoid ++, as it works by inefficiently walking to the end of its LHS argument.

compress :: Eq a => [a] -> [a]
compress []     = []
compress (x:[]) = [x]
compress (x:y:zs)
  | x == y      = compress (y:zs)
  | otherwise   = x : compress (y:zs)

Problem 9: Pack consecutive duplicates of list elements into sublists

I don't think that packing an empty list should be an error.  Rather it should just return an empty list.

My advice is similar to the above.  I think that a helper function is needed, but not in that way.

pack :: Eq a => [a] -> [[a]]
pack [] = []
pack (x:xs) = pack' [x] xs
  where
    pack' run []  = [run]
    pack' run@(r:_) (x:xs)
      | x == r    = pack' (x:run) xs
      | otherwise = run : pack' [x] xs

Problem 10: Run-length encoding of a list

Again, I don't think that encoding an empty list should be an error.

The implementation would read more nicely, in my opinion, using a list comprehension and better naming.

encode :: Eq a => [a] -> [(Int, a)]
encode xs = [(length run, head run) | run <- pack xs]

In summary, accumulators are sometimes the right approach (as in myReverse), but often they are harmful.  Before using one, think hard about whether it is necessary and efficient.


Pythonic solution to display multi-dimensional tuple as a tree I would like to show the tree-like structure contained in a multi-dimensional tuple by using the set of graphical glyphs that exist in Unicode fonts (e.g. \u2500, \u2502, \u2514 and others). Here is an example of the kind of output, I'm talking about:

>>> showtree('(01, (02,  03, 04), 05, ((06, 07), 08), (09, (10, 11), (12, 13), 14), 15)')
┬─01
├─┬─02
│ ├─03
│ └─04
├─05
├─┬─┬─06
│ │ └─07
│ └─08
├─┬─09
│ ├─┬─10
│ │ └─11
│ ├─┬─12
│ │ └─13
│ └─14
└─15

Ideally, empty items, multi-words items, extra spaces around commas or parenthesis, as well as unbalanced parenthesis should be managed correctly, as in the following example:

>>> showtree('( A, B multi-word item , (C,D), ( E  , ,  F ), G  )'))
┬─A
├─B multi-word item
├─┬─C
│ └─D
├─┬─E
│ ├─
│ └─F
└─G

I came up with a solution that works quite well (the examples above have been generated with it) but the implemented algorithm is not very elegant, and the code not very pythonic :

def showtree(string):
    """display multidimensional tuple as a tree"""
    glyphs = ['\u252C\u2500','\u251C\u2500','\u2514\u2500','\u2502 ']
    tree, glyph, item = [], [], []
    for char in string:
        if char in ',)' and item:                                   # add glyph prefix and current item to tree
            tree.append(glyph + [''.join(item).strip()]); item = []
        if char == ',':                                             # update glyph prefix for new item in sublist
            glyph = [glyphs[3]] * (len(glyph)-1) + [glyphs[1]]
        elif char == ')':                                           # update glyph prefix for last item in sublist
            tree[-1][-2] = glyphs[2]; glyph = glyph[:-1]
        elif char == '(':                                           # update glyph prefix for first item in sublist
            glyph.append(glyphs[0])
        else:                                                       # other chars are simply added to current item
            item.append(char)
    return '\n'.join(''.join(node) for node in tree)

So I would like to get some ideas for an improved implementation, maybe using regular expressions or other advanced parsing techniques. Thank you very much for any hint...

Neither the code provided in the question or the top voted answer work correctly. This is as you're making unreasonable assumptions on how the data is formed.

>>> print(showtree('(A)'))
└─A
>>> print(showtree('(1, ((2)), (3, 4, (5)))'))
┬─1
├─┬─└─2
├─┬─3
│ ├─4
│ ├─└─5
>>> print(tree_string_to_display_string('(1, ((2)), (3, 4, (5)))'))
┬─1
├─┬─└─2
├─┬─3
│ ├─4
│ ├─└─5

Your code is also doing two things at once, parsing a string and building a tree. And so I will only take a tuple as input. If you need to take a string then you can build the parser separately.

Make the code work with one item.

To do this should be fairly simple, we take the tuple ('1',) and return ──1.

def build_tree(root):
    return '\n'.join(_build_tree(root))

def _build_tree(node):
    yield '──' + node[0]

>>> print(build_tree(('1',)))
──1

Make the code work with 1, 2 or more items.

This is fairly simple, we check node's length and use the above code if it's 1. Otherwise we make:

The first item start with ┬─.
The last item start with └─.
All other items start with ├─.

This is as simple as using tuple unpacking, and then iterating over the middle.

def _build_tree(node):
    if len(node) == 1:
        yield '──' + node[0]
        return

    start, *mid, end = node
    yield '┬─' + start
    for value in mid:
        yield '├─' + value
    yield '└─' + end

>>> print(build_tree(('1',)))
──1
>>> print(build_tree(('1', '2')))
┬─1
└─2
>>> print(build_tree(('1', '2', '3')))
┬─1
├─2
└─3

Get the code to work if you only enter a value, no tuples.

This is simple, since we're only allowing tuples as the nesting datatype, then we can just add an if not isinstance(node, tuple). We will convert this to a string now to help our future selves.

def _build_tree(node):
    if not isinstance(node, tuple):
        yield str(node)
        return

    if len(node) == 1:
        yield '──' + node[0]
        return

    start, *mid, end = node
    yield '┬─' + start
    for value in mid:
        yield '├─' + value
    yield '└─' + end

>>> print(build_tree('1'))
1

Get the code to work recursively with the same input as (2). To check this we will change the input to integers.

This is simple. We run _build_tree on all the values in node, if it's a tuple. From here we only work on these values. We know these values are going to be iterators with only one value. This means we can just use next for now.

def _build_tree(node):
    if not isinstance(node, tuple):
        yield str(node)
        return

    values = [_build_tree(n) for n in node]
    if len(values) == 1:
        yield '──' + next(values[0])
        return

    start, *mid, end = values
    yield '┬─' + next(start)
    for value in mid:
        yield '├─' + next(value)
    yield '└─' + next(end)

>>> print(build_tree((1,)))
──1
>>> print(build_tree((1, 2)))
┬─1
└─2
>>> print(build_tree((1, 2, 3)))
┬─1
├─2
└─3

Get the code working recursively.

We know all the current yields work the same way, and so this calls for a new function. This should take three values:

The value to add to the first item. (This is what we're doing right now)
The value to add on all other items.
This is important as if a node is only one large. But has nested data that is larger than one value then we will add '  ' to the output.
The nested data.

This is really simple to build:

def build_lines(first, other, values):
    yield first + next(values)
    for value in values:
        yield other + value

Finally we adjust the current yields so they are yield from functions.

def build_tree(root):
    return '\n'.join(_build_tree(root))

def _build_tree(node):
    if not isinstance(node, tuple):
        yield str(node)
        return

    values = [_build_tree(n) for n in node]
    if len(values) == 1:
        yield from build_lines('──', '  ', values[0])
        return

    start, *mid, end = values
    yield from build_lines('┬─', '│ ', start)
    for value in mid:
        yield from build_lines('├─', '│ ', value)
    yield from build_lines('└─', '  ', end)

def build_lines(first, other, values):
    yield first + next(values)
    for value in values:
        yield other + value

>>> print(build_tree(('01', ('02',  '03', '04'), '05', (('06', '07'), '08'), ('09', ('10', '11'), ('12', '13'), '14'), '15')))
┬─01
├─┬─02
│ ├─03
│ └─04
├─05
├─┬─┬─06
│ │ └─07
│ └─08
├─┬─09
│ ├─┬─10
│ │ └─11
│ ├─┬─12
│ │ └─13
│ └─14
└─15
>>> print(build_tree(('A', 'B multi-word item', ('C', 'D'), ('E', '', 'F'), 'G')))
┬─A
├─B multi-word item
├─┬─C
│ └─D
├─┬─E
│ ├─
│ └─F
└─G
>>> print(build_tree((1, ((2,),), (3, 4, (5,)))))
┬─1
├─────2
└─┬─3
  ├─4
  └───5


Caesar Encryption-Decryption Tool I'm a beginner in Python. I wrote this code which encrypts and decrypts text using Caesar chipher. I wrote it in many days and optimized it many times. But how it can be improved more?

I've used lists because they are flexible and they serve my algorithm.

print('''# This is version 1.0 Caesar Encryption-Decryption Tool.
# This tool is written by Mahmoud Naguib and it will be improved.
# You can contact me at : https://www.facebook.com/naguibarea
-----------------------------------------------------------------''')
letters_table = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
                 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

def caesar():
    # This line iterates through every letter in the string.
    for letter in range(len(text)):
        # If there is a letter which isn't an English alphabet.
        if not text[letter].isalpha():
            letters_table.append(text[letter])
        # This line locates the letter's numeric value in other words its position.
        position = letters_table.index(text[letter])
        # This line adds the key entered by the user to the letter's
        # numeric value to reach the new letter.
        step = position + key
        # if the encrypted letter's numeric value is greater than 25
        # then its new numeric value is the old numeric valuu %
        # the number of English alphabet letters.
        if step > 25:
            step %= 26
        # If step is lower than 0 then we need to add 26 to it to complete the decryption process.
        if step < 0:
            step += 26
        # If position is greater than 25 that means it's not an alphabet
        # value and it will be printed without adding the key(the letter will be printed as it is).
        if position > 25:
            step = position
        # This line locates the letter's numeric value(its position) and prints the new letter.
        # end is a keyword argument to combine all letters together.
        print(letters_table[step], end='')
    print('\n' + '-----------------------------------------------------------------')

while True:
    while True:
        # This line ask the user if he wants to encrypt or decrypt a text.
        mode = input('Type E for enryption mode or D for decryption mode : ').upper()
        if mode == 'D' or mode == 'E':
            break
        else:
            print('You must enter E or D ! ')
    # This line takes the user's text and converts it to uppercase to search for it in the letter's table.
    while True:
        text = input('Enter your text : ').upper()
        if len(text) != 0:
            break
        else:
            print('You can not leave it blank ! ')
    while True:
        try:
            # This line takes the user's key.
            key = int(input('Enter a key : '))
            if type(key) == int:
                break
        except ValueError:
            print('You must enter an integer number ! ')
    # If the user wants to encrypt a text it will call the caesar() function.
    if mode == 'E':
        caesar()
    # If the user wants to decrypt a text it will make the key value negative so that there's a reverse process
    # and it will call the caesar() function.
    elif mode == 'D':
        key = 0 - key
        caesar()

First off you if we look at the main of your code, it's mostly all the same pattern.

while True:
    text = input().upper()
    if ...:
        break
    else:
        print()

You should make that a function. And then call it.

def get_input(message, error_message, fn):
    while True:
        text = input(message).upper()
        if fn(text):
            return text
        else:
            print(error_message)

This severely reduces the amount of code needed.
The way you use this new function is:

mode = get_input(
    'Type E for enryption mode or D for decryption mode : ',
    'You must enter E or D ! ',
    lambda mode: mode in 'DE'
)

text = get_input(
    'Enter your text : ',
    'You can not leave it blank ! ',
    lambda text: text
)

If you have not come across lambda before it's a way to make small functions.
For example, the following are the same:

my_fn = lambda a: len(a) - 1

def my_fn(a):
    return len(a) - 1

You should also note that I replaced mode == 'D' or mode == 'E' to mode in 'DE'.
It's much easier to add to this if you need to.
So if you add say 'A' as a function, you can change it to mode in 'ADE'.

Also in Python you should use if text rather than if len(text) != 0.
This is as empty objects are False, and others True. E.g.

>>> bool('')
False
>>> bool('a')
True
>>> bool([])
False
>>> bool(['a'])
True

Now onto the bit that is a bit more challenging.
To make a function to check if you can change the input into a number, using int, we can't use lambda.
to do this you need to make a 'proper' function.
Alternately you can use str.isdigit. (Thanks @SuperBiasedMan)

def int_able(string):
    try:
        int(string)
        return True
    except ValueError:
        return False

key = int(get_input(
    'Enter a key : ',
    'You must enter an integer number ! ',
    int_able
))

# Or
key = int(get_input(
    'Enter a key : ',
    'You must enter an integer number ! ',
    lambda text: text.strip().isdigit()
))

When calling a function you should always pass it arguments.
caesar() is a bad design.
For a simple script like this it's alright,
however it's not a good habit to get into.
Instead, I would recommend that you call it with caesar(text, key).
I would re-write your modes to:

if mode == 'D':
    key = -key

caesar(text, key)

As I recommended you change caesar you will need to change the arguments you pass to it.

You shouldn't add to the letters_table, that should stay the same.
If you need to add more letters then you should add them in the definiton.

If you make letters_table a constant, then you can change it to a string.

You should change your loop from for letter in range(len(text)) to for letter in text.

Your algorithm can be changed to one line, and if step < 0 should never happen.

And you should probably remove the if position > 25 it's not a good idea,
just add letters to letters_table.

I would discourage print(..., end=''), instead make a string.

And so I would re-write your code to:

LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def caesar(message, key):
    caesar_text = ''
    for letter in message:
        caesar_text += LETTERS[(LETTERS.index(letter) + key) % 26]

    print(caesar_text)

Note: I don't add to LETTERS if you need to add more then hard-write them in.

To note, I didn't read your comments, there were to many,
and not meaning to be rude, but I can read Python, in fact it's more straightforward than English at times.

# If step is lower than 0 then we need to add 26,
# to it to complete the decryption process.
if step < 0:
    step += 26

I know which is easier, and faster, to read by far.

But all in all you have nice code, reduce the amount of comments, and pass argument and you'll do great.


I could use a review of my sudoku validation I'm looking for alternative ways to do it and in general parts that don't look write on this code.

using System.Collections.Generic;

namespace Algorithms
{
    public class SudokuPuzzleValidator
    {
        readonly int[,] _board;

        public SudokuPuzzleValidator()
        {
            _board = new int[9,9];
        }

        public SudokuPuzzleValidator(int[,] board)
        {
            _board = board;
        }

        public bool Validate()
        {
            const int integersInGame = 9;
            var rowSet = new HashSet<int>[integersInGame];
            InitializeSet(integersInGame, rowSet);
            var columnSet = new HashSet<int>[integersInGame];
            InitializeSet(integersInGame, columnSet);
            var subGridSet = new HashSet<int>[integersInGame];
            InitializeSet(integersInGame, subGridSet);

            for (var row = 0; row < integersInGame; row++)
            {
                for (var column = 0; column < integersInGame; column++)
                {
                    var cval = _board[row, column];
                    if (rowSet[row].Contains(cval))
                    {
                        return false;
                    }
                    rowSet[row].Add(cval);
                    if (columnSet[column].Contains(cval))
                    {
                        return false;
                    }
                    columnSet[column].Add(cval);
                    var subGridNumber = FigureOutSubGrid(row, column);
                    if (subGridSet[subGridNumber].Contains(cval))
                    {
                        return false;
                    }
                    subGridSet[subGridNumber].Add(cval);
                }
            }
            return true;
        }

        private static void InitializeSet(int integersInGame, HashSet<int>[] rowSet)
        {
            for (var i = 0; i < integersInGame; i++)
            {
                rowSet[i] = new HashSet<int>();
            }
        }

        private static int FigureOutSubGrid(int row, int column)
        {
            return column/3 + row/3*3;
        }
    }
}

Link to my post:
http://alfredoalvarez.com/blog/?p=372

This looks way overcomplicated. There are a lot of solutions on the web, for example:
https://stackoverflow.com/questions/723213/sudoku-algorithm-in-c-sharp

Regarding your code:

You have hard-coded numbers everywhere
Second ctor accepts arbitrary
array and does not check parameter for validity. It can be null or of
any size different from 9


Split a list into equal parts that using LINQ in a way that has good performance So I have a method that looks like this:

   public static List<List<List<string>>> Split(List<List<string>> source, int chunksize)
   {
       return source
           .Select((x, i) => new { Index = i, Value = x })
           .GroupBy(x => x.Index / chunksize)
           .Select(x => x.Select(v => v.Value).ToList())
           .ToList();
   }

While this is nice and elegant and readable, unfortunately that groupby is killing performance because of the implicit sort. I need a way to rewrite this to be more performant, while still being reasonably elegant.

We can make the method more generic:

public static IEnumerable<IEnumerable<T>> Split<T>(IEnumerable<T> source, int chunkSize)
{

Then we can store the current chunk in a List<T>. Using the constructor that takes the initial capacity should be good for performance:

    var chunk = new List<T>(chunkSize);
    foreach (var item in source)
    {
        chunk.Add(item);
        if (chunk.Count == chunkSize)
        {
            yield return chunk;
            chunk.Clear();
        }
    }

Finally we need to return the final (non-empty) chunk

    if (chunk.Count > 0)
    {
        yield return chunk;
    }
}

Depending on your use case, you might want to make a copy of the list and yield return chunk.ToList() instead.


Printing all the prime numbers between two bounds I keep getting a time limit exceeded for this solution to SPOJ Prime1.  I need to print all primes within a given interval (with intervals as large as 105, and numbers as large as 109).

I've tried everything I could think of to get this code to be faster but nothing works. What can I do?

#include <iostream>

bool isprime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    // Code to to print all the prime numbers between two bounds. n is the
    // number of test cases.
    int n, j, k;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::cin >> j >> k;
        while (j-- != k) {
            if (isprime(j)) std::cout << j << '\n';
        }
    }
}

When using trial division to test a number n for primality, the highest potential divisor that needs to be checked is floor(sqrt(n)). The first number that must not be checked is n itself, because that would result in a false verdict of non-primality (seeing that every number is divisible by itself). But that is precisely what happens for the code posted by user5486241 in the case n == 2:

for (int i = 2; i < std::sqrt(n)+1; ++i)
   if (n % i == 0)
      return false;

Recomputing the square root during each iteration carries a heavy runtime cost, though, unless the compiler is able to quietly correct this programming mistake. This requires the compiler to prove that the expression std::sqrt(n) is loop-invariant, which in turn requires it to prove or know that std::sqrt() is idempotent (free of observable side-effects).

The point about only scanning up to the square root is valid and important, though. Scanning up to n instead of sqrt(n) leads to an exponential increase in runtime, which is why the OP's original code is not included in the benchmarks. These benchmarks show the performance of user5486241's code (shown as 'v0') vs. the following cleaned-up version 'v1':

typedef std::uint32_t num_t;

bool v1::is_prime (num_t n)
{
   if (n < 2)
      return false;

   for (num_t i = 2, sqrt_n = num_t(std::sqrt(n)); i <= sqrt_n; ++i)
      if (n % i == 0)
         return false;

   return true;
}

The num_t typedef has no deeper purpose here, I introduced it only to facilitate experimentation without turning everything into a template (and making it thus unreadable).

The benchmarks show the time in milliseconds for scanning a maximum-width range according to the tasks SPOJ PRIME1 (n - m <= 100,000, n <= 1,000,000,000, timeout 6 s) and SPOJ PRINT (n - m <= 1,000,000, n <= INT32_MAX, timeout 1.223 s) respectively.

The first column shows the value for n, which is the upper end of the range and in the first row it is also equal to the constant n - m. The variants v2 through v6 are explained later.

*** BC++ 5.5.1 (free) 32 ***

PRIME1 10^5    v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
    100000     75     11      5      4      4      3      1      9592
   1000000    253     33     16     11     11      7      1      7224
  10000000    667     84     40     27     27     13      1      6134
 100000000   1813    228    107     73     71     30      1      5454
1000000000   4964    624    291    196    191     69      1      4832

PRINT 10^6     v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
   1000000   1834    236    114     80     79     55      6     78498
  10000000   6519    798    386    267    264    134      7     62090
 100000000  17948   2237   1083    719    709    291      6     54332
1000000000  49234   6093   2863   1955   1890    693      6     47957
2147483647  69528   8749   4078   2741   2624    939      7     46603

With bcc64 the overhead of v0 is less pronounced than with bcc32, because the 64-bit compiler can inline the square root computation with three XMM instructions instead of having to call a library function. The timings for variants v1 through v6 are noticeably worse, though (showing only the last line):

*** BC++ 7.10 (RX/Seattle) 64 *** CLANG 3.3.1 (35465.f352ad3.17344af)

2147483647  20007   9512   4781   3373   3195   1710     22     46603

Now, gcc and VC++ as examples for highly optimising compilers that can quietly correct programming mistakes. Their timings - regardless of bitness - are exactly the same, within the limits of jitter.

*** g++ 4.8.1 32 *** on MAGNUM (3.0 GHz Haswell)

PRIME1 10^5    v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
    100000     10     10      5      4      3      3      0      9592
   1000000     31     31     16     11      9      7      0      7224
  10000000     82     82     41     27     24     14      0      6134
 100000000    216    219    110     73     64     31      1      5454
1000000000    580    580    293    195    170     71      1      4832

PRINT 10^6     v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
   1000000    226    222    113     77     68     52      5     78498
  10000000    781    780    391    263    228    133      5     62090
 100000000   2104   2128   1065    706    608    294      5     54332
1000000000   5761   5824   2935   1942   1685    706      6     47957
2147483647   8221   8162   4108   2743   2379    952      6     46603

v0 ... user5486241's code
v1 ... sqrt computation hoisted out of the loop
v2 ... skipping multiples of 2
v3 ... skipping multiples of 2 and 3
v4 ... skipping multiples of 2, 3 and 5
v5 ... trial-dividing only by primes (SoE for the factors)
v6 ... simple windowed Sieve of Eratosthenes

Comparing the timings for v0 and v1 shows clearly that these two compilers managed to hoist the square root computation out of the loop all by themselves.

All these timings were taken on a 3 GHz Haswell laptop. The gcc32 timings are for a P4 build - no advanced instructions - so that I could run the same executable on a 2.8 GHz Northwood (P4), which is the kind of iron that SPOJ ran on when the limits for PRIME1 and PRINT were set:

*** g++ 4.8.1 32 *** on HELIOS (2.8 GHz Northwood)

PRIME1 10^5    v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
1000000000   2378   2324   1165    778    625    266      2      4832

PRINT 10^6     v0     v1     v2     v3     v4     v5     v6   #primes
---------------------------------------------------------------------
2147483647  32806  32679  16344  10933   8800   3549    107     46603

It can be clearly seen that division instructions are about four times as fast on current machines compared to back when the tests limits were set, since v0 through v5 are essentially limited by division performance. The sieve code (v6) profits even more from the many improvements in current processors, across the board from memory system performance to superscalar out-of-order execution.

The performance of simple, division-based primality tests is interesting because they are a perfectly adequate solution for many applications where the superior bulk performance of sieves is not necessary. Euler problem #35 (circular primes) comes to mind, where only 5460 candidates need to be checked for covering the range up to 1,000,000. The advantage of the division-based code - besides its simplicity - is that it does not need auxiliary structures like factor sieves.

One simple improvement is to skip the number 2 and its multiples, which immediately doubles performance:

bool v2::is_prime (num_t n)
{
   if (n <= 2)
      return n == 2;

   if ((n & 1) == 0)
      return false;

   num_t sqrt_n = num_t(std::sqrt(n));

   for (num_t i = 3; i <= sqrt_n; i += 2)
      if (n % i == 0)
         return false;

   return true;
}

The performance is actually slightly more than doubled because multiples of 2 get rejected faster now: before the call to sqrt() and before the loop is set up, and without requiring a division. This code already shows the complications necessary for wheel-based operations:
o special handling of the wheel primes before operations commence
o special handling for the multiples of the wheel primes
o special rules for striding through the search space, so that wheel prime multiples are skipped

Skipping the remaining multiples of 3 cuts the workload by another third. I'm showing it here because it makes the approach behind v4 easier to understand:

bool v3::is_prime (num_t n)
{
   if (n < 4)
      return n == 2 || n == 3;

   if ((n & 1) == 0 || n % 3 == 0)
      return false;

   num_t sqrt_n = num_t(std::sqrt(n));

   for (num_t i = 5, d = 2; i <= sqrt_n; i += d, d ^= 6)
      if (n % i == 0)
         return false;

   return true;
}

The step sequence for avoiding multiples of 3 as well as multiples of 2 is 2, 4, 2, 4... (when starting at 5) which I produce here with a simple xor cheat.

The step sequence gets longer when 5 is added to the wheel; it has 8 steps which are 4, 2, 4, 2, 4, 6, 2, 6 (when starting at 7). In other words, the mod 30 wheel has 8 prime-bearing spokes and numbers above are the distances between non-dud spokes when the wheel is currently positioned at 7. I couldn't find an elegant way of creating the sequence with a few arithmetic operations, so I simply stuffed it into the nibbles of a 32-bit word that gets rotated as the algorithm chugs along. For compatibility I did the rotation with a workaround instead of a non-standard compiler intrinsic or library function. This hurts performance a bit (increasing the instruction count from one to three, with attendant increase in register pressure), which is why the performance increase is slightly less than the expected 20%.

I'm also showing a different way of dealing with the wheel primes: instead of testing for equality with each of them, I use a constant as a bitmap. This allows me to deal with 32 numbers in one go. The performance of this branch is insignificant because it is taken very rarely, but the tighter code means less pressure on the instruction cache.

A similar approach could be used for discarding all multiples of 2, 3 and 5 after a single division by 30 (if (EMPTY_SPOKES & (1 << (n % 30))) return false) but this does not result in an improvement because it rejects multiples of 2 slightly more slowly than the code shown in v4, which is why performance-wise it is pretty much a wash. Hence the simpler, more pedestrian code.

template<unsigned SHIFT>  // replace with _lrotl() or similar
inline
num_t rotate_right (num_t n)
{
   return num_t( (n >> SHIFT) | (n << (sizeof(num_t) * CHAR_BIT - SHIFT)) );
}

enum
{
   PRIMES_7_TO_29 = (1<<7) | (1<<11) | (1<<13) | (1<<17) | (1<<19) | (1<<23) | (1<<29),
   PRIMES_2_TO_31 = (1<<2) | (1<< 3) | (1<< 5) | PRIMES_7_TO_29 | (1<<31)
};

bool v4::is_prime (num_t n)
{
   if (n < 32)
      return (PRIMES_2_TO_31 >> n) & 1;  // normalised to 0/1; good compilers recognise this

   if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0)
      return false;

   num_t sqrt_n = num_t(std::sqrt(n));

   for (num_t i = 7, w = 0x62642424; i <= sqrt_n; i += (w & 15), w = rotate_right<4>(w))
      if (n % i == 0)
         return false;

   return true;
}

v5 needs a vector of potential prime factors up to the square root of the upper limit. For a limit of INT32_MAX the maximum factor not exceeding the square root is 46340, and even the simplest, most-straightforward code can sieve this in less than a millisecond:

// intended to go no higher than sqrt(2^31) == 46340, hence no need for segmentation or wheeling
// (despite exceeding the L1 cache not slower than vector<bool> for gcc and lots faster for bcc)
void sieve_small_primes_up_to (unsigned limit, std::vector<num_t> &result)
{
   result.resize(0);

   unsigned max_factor = unsigned(std::sqrt(limit));   // = 215

   std::vector<char> is_composite(limit + 1);          // +1 because we're indexing with numbers

   for (unsigned i = 2; i <= max_factor; ++i)          // * 214
      if (!is_composite[i])                            // * 47
         for (unsigned j = i * i; j <= limit; j += i)
            is_composite[j] = true;

   for (unsigned i = 2; i <= limit; ++i)               // * 46339
      if (!is_composite[i])                            // * 4792
         result.push_back(num_t(i));
}

Obviously, this initialisation must be arranged to happen before the primality test function is called. In order to make v5 directly comparable to v4 I decided to handle the primes 2 to 5 in exactly the same way as v4 does. This gives v5 the same advantage as v4 has, which is fast rejection of the multiples of 2, 3 and 5 (73.3% of all numbers). Hence the wheel primes need to be removed from the vector:

sieve_small_primes_up_to(num_t(std::sqrt(INT32_MAX)), small_factors_gt_5);
// erase the wheel primes
small_factors_gt_5.erase(small_factors_gt_5.begin(), small_factors_gt_5.begin() + 3);

Normally this would all be encapsulated in a class that houses the function and its auxiliary data, guarding its invariants. Here I'm showing only the raw primality test code:

bool v5::is_prime (num_t n)
{
   if (n < 32)
      return (PRIMES_2_TO_31 >> n) & 1;  // normalised to 0/1; good compilers recognise this

   if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0)
      return false;

   num_t sqrt_n = num_t(std::sqrt(n));

   for (auto prime: small_factors_gt_5)
   {
      if (prime > sqrt_n)
         return true;

      if (n % prime == 0)
         return false;
   }

   assert("too few small_factors_gt_5[] (not initialised properly)");

   return false;
}

Older compilers and the classic (non-clang) versions of the Emborlandero compiler need some #ifdefery for replacing the range-based for loop with a normal iterator-based for loop, but I've edited that out here in order to improve readability.

And finally, some code that can beat even PRINT without breaking a sweat, with several orders of magnitude reserve regarding time and memory limits. Most of the bits and pieces are already in place; all that remains is replacing iterated calls to is_prime() with a small Eratosthenean sieve. The only tricky bit here is computing exactly where in the sieve window the sequence of hops for a given prime starts. Here I formulated this in a way that anchors the computation at the slot before the start of the sieve window (hence the apparently unmotivated -1); this has the advantage that it avoids additional branching or a double mod.

Since the code is orders of magnitude faster than the SPOJ requirements, it can simply sieve its factor primes on every call.

void v6::get_primes (num_t m, num_t n, std::vector<num_t> &result)
{
   std::vector<num_t> small_factors;

   sieve_small_primes_up_to(unsigned(std::sqrt(n)), small_factors);

   num_t window_size = n - m + 1;
   std::vector<char> is_composite(window_size);

   for (num_t prime: small_factors)
   {
      num_t first_multiple = prime * prime;  // absolute, may lie outside the window

      if (first_multiple > n)
         break;

      num_t stride = prime;                  // no need to get cute with wheely things and whatnot
      num_t i;

      if (first_multiple >= m)
         i = first_multiple - m;
      else
         i = stride - (m - 1 - first_multiple) % stride - 1;

      for ( ; i < window_size; i += stride)
         is_composite[i] = true;
   }

  result.resize(0);

   // 0 and 1 aren't composites, but they aren't primes either -> skip them if they're there
   for (num_t i = num_t((m < 1) + (m < 2)); i < window_size; ++i)
      if (!is_composite[i])
         result.push_back(m + i);
}


Toggle case of a string in Swift What is benefit of using uppercased() / lowercased() over the following approach ? (Other than making it more readable)

Any comments on perf ?

Can this be further improved ?

Example : for input : ABcDe, Expected Output is : abCdE

var solve = {(str: String) -> String in
    var arr = [Character]()
    for char in str.unicodeScalars {
        char.value > 96 ? arr.append(Character(UnicodeScalar(char.value - 32)!)) : arr.append(Character(UnicodeScalar(char.value + 32)!))
    }
    return String(arr)
}

solve("Nipun")

Compared to a solution using the upper/lowerCased() string methods,
your approach has some disadvantages:

It does not work for many letters in non-english alphabets:

print(solve("ćœßπĆŒΠ"))  // çĳ¿ΠæĲ΀

It transforms non-letters as well, to some unexpected output:

print(solve("a b,c")) // A@BLC

Even if the code is only needed for ASCII letters ("A" ... "Z", "a" ... "z"),
it can still be improved.

Defining a global function instead of a closure variable increases the
legibility. You should also use a better function name, solve() is pretty
non-descriptive:

func toggleCase(_ str: String) -> String {
    // ...
}

An alternative would be an extension method:

extension String {
    func caseToggled() -> String {
        // ...
    }
}

which resembles the existing upper/lowerCased() methods.
A disadvantage is the possibility of name conflicts if some imported
framework happens to define the same extension method.

The use of "magic numbers" – like 32 and 96 in your code – should be
avoided. At least use a constant with an explaining comment:

let delta = 32 // Difference between upper case and lower case Unicode scalar values of ASCII letters.

Better, compute it from the actual values, which makes it self-explaining:

let delta = UnicodeScalar("a")!.value - UnicodeScalar("A")!.value

A switch-case statement allows to transform only the ASCII letters,
with a well-defined behavior for other characters.

Finally, instead of creating an intermediate [Character] array,
you can append to the unicodeScalar view of the result string
directly.

Putting it together, the function could look like this:

func toggleCase(_ str: String) -> String {
    let delta = UnicodeScalar("a")!.value - UnicodeScalar("A")!.value
    var result = ""
    for ucs in str.unicodeScalars {
        switch ucs {
        case "A"..."Z":
            result.unicodeScalars.append(UnicodeScalar(ucs.value + delta)!)
        case "a"..."z":
            result.unicodeScalars.append(UnicodeScalar(ucs.value - delta)!)
        default:
            result.unicodeScalars.append(ucs) // Leave unchanged
            // Alternatively:
            // break to ignore other characters
        }
    }
    return result
}

Example:

print(toggleCase("AB c De")) // ab C dE

If you have to toggle the case of arbitrary letters (from any language) then
the upper/lowerCased() string methods must be used, as there is no
simple "arithmetic operation" which does this transformation.

If performance is the first priority then you should work on the UTF-16 view
of the string, because that is what String stores internally. (However, that
is an implementation detail and might change in the future.)

func toggleCase1(_ str: String) -> String {
    var utf16Result: [UInt16] = []
    utf16Result.reserveCapacity(str.utf16.count)
    let upperCaseA = UInt16(65)
    let upperCaseZ = UInt16(90)
    let lowerCaseA = UInt16(97)
    let lowerCaseZ = UInt16(122)
    let delta = lowerCaseA - upperCaseA

    for u in str.utf16 {
        switch u {
        case upperCaseA...upperCaseZ:
            utf16Result.append(u + delta)
        case lowerCaseA...lowerCaseZ:
            utf16Result.append(u - delta)
        default:
            utf16Result.append(u)
        }
    }
    return String(utf16CodeUnits: utf16Result, count: utf16Result.count)
}

Note how reserveCapacity() is used to avoid array reallocations.

Performance comparison: The test was done on a MacBook (Retina, 12-inch, Early 2016, 1.2 GHz Intel Core m5 processor),
with the program compiled in Release configuration:

let str = String(repeating: "abcdefghijklmnopqrstuvwsyzABCDEFGHIJKLMNOPQRSTUVWXYZ", count: 100_000)

do {
    let start = Date()
    let _ = solve(str)
    let end = Date()
    print("solve:      ", end.timeIntervalSince(start) * 1000)
}

do {
    let start = Date()
    let _ = toggleCase(str)
    let end = Date()
    print("toggleCase: ", end.timeIntervalSince(start) * 1000)
}

do {
    let start = Date()
    let _ = toggleCase1(str)
    let end = Date()
    print("toggleCase1:", end.timeIntervalSince(start) * 1000)
}

Result:

solve:       496.731996536255
toggleCase:  319.347023963928
toggleCase1: 189.152002334595


Simulating the martingale betting system with roulette I wrote a program that simulates many instances of trying the martingale betting system with roulette in Haskell.

At the answerer's suggestion I opted to leave the IO monad in main and ensure that the functions martingale and martingale', which handled the actual testing, were entirely pure, but the answerer also suggested that I could push my call to newStdGen all the way down into martingale'. I believe this would remove the requirement that my functions even require a StdGen as an argument.

My question then: Is it more natural for functions that compute random variable x to require StdGens as an argument, or for them to create StdGens and perhaps return IO x? Also, is my source code posted below reasonable and could it be improved or made more natural?

-- file: Martingale.hs
-- a program to simulate the martingale doubling system

import System.Random (randomR, newStdGen, StdGen)
import System.Environment (getArgs)
import Control.Monad (replicateM)

red = [1,3,5,7,9,12,14,16,18,19,21,23,25,27,30,32,34,36]

martingale :: StdGen -> Bool
martingale = martingale' 1 0

martingale' :: Real a => a -> a -> StdGen -> Bool
martingale' bet acc gen
  | acc >= 5     = True
  | acc <= -100  = False
  | otherwise    =
    let (randNumber, newGen) = randomR (0,37) gen :: (Int, StdGen)
    in if randNumber `elem` red
       then martingale' 1 (acc + bet) newGen
       else martingale' (bet * 2) (acc - bet) newGen

main :: IO ()
main = do
  args <- getArgs
  let iters = read $ head args
  gens <- replicateM iters newStdGen
  let results = map martingale gens
      countWins = length $ filter (== True) results
      prob = fromIntegral countWins / fromIntegral iters
  print prob

Is it more natural for functions that compute random variable x to require StdGens as an argument, or for them to create StdGens and perhaps return IO x?

I think in most cases you're going to be better off passing around a pure source of randomness or a seed value so that you can guarantee deterministic output if need be by using the same seed in multiple runs. That is, you made the right choice.

  Also, is my source code posted below reasonable and could it be improved or made more natural?

I don't think there's anything wrong per se, but it's very narrowly focused without much opportunity for reusability. You'll not often go wrong if you attempt to mirror the reality of what you're modeling in your functions and type signatures. For instance, consider that a roulette wheel is an unlimited source of randomly chosen values. One way to express this in your Haskell program would be...

wheel :: StdGen -> [Int]
wheel = randomRs (0, 37)

It's useful to encapsulate this because there's nothing about martingale betting systems that involves a random element, the system itself is entirely deterministic.

martingale :: Int        -- ^ Current bet
           -> Bool       -- ^ Result of current spin
           -> (Int, Int) -- ^ (Next bet, winnings/losings)
martingale bet True  = (1      ,        bet)
martingale bet False = (bet * 2, negate bet)

Here I've separated out just the betting system aspect of your program, because tracking winnings or choosing ranges are separate functions from determining bets. This way also you can substitute different betting strategies fairly easy as long as it has the same type signature.

You'd tie this all together with a simulation function something like this.

simulate :: (Int -> Bool)               -- ^ A picking function
         -> (Int -> Bool -> (Int, Int)) -- ^ A betting function
         -> Int                         -- ^ An initial bet
         -> (Int -> Maybe Bool)         -- ^ Decides when to leave the table
         -> [Int]                       -- ^ A wheel
         -> Bool                        -- ^ Took winnings or unacceptable loss?

This is probably way overkill to start with, but with it you could test biased wheels, or different levels of acceptable losses, or different strategies against particular wheels. At this point also you'd want to start using type aliases, newtypes, or your own data types to disambiguate what's going on. E.g., you'd end up with...

simulate :: (Slot -> Bool)
         -> (Stake -> Bool -> (Stake, Winnings))
         -> Stake
         -> (Winnings -> PlayState)
         -> [Slot]
         -> PlayState

And used like,

simulate betOnRed martingale 1 quitWhileAhead unbiasedWheel
simulate betOnLow antimartingale 50 bailBelowFifty houseBiasedWheel


RAR dictonary attack I have some old RAR files and I know the general format of passwords I used to use, so I have generated a dictionary file combining those words in a variety of ways. The dictionary file is 500mb and I've wrote a python program to use the dictionary.

The issue is that the program has been running all night and is only 1% of the way in. I've now divided the dictionary file up and I am now running multiple instances of the program, but each instance is running pretty slow.

I would love any advice on how to improve the speed. I'm very new to Python, which will be obvious by my code (but I'm really enjoying Python).

import itertools
import sys, traceback
import os

with open('dictionary.txt') as infile:
    words = [line.strip() for line in infile]
    for word1 in itertools.product(words, repeat=1):
        fword = word1[0]
        print "Attempting: " + fword

        # open unrar and test password
        output = os.popen("unrar.exe x protected.rar -p" + fword)
        outstring = output.read()
        slng = len(outstring)

        # unrar.exe returns "All OK" for correct password
        validate = outstring.find("All OK", 0, slng)
        if validate != -1:
            print "Found password: " + fword
            with open('correct_password.txt', 'w') as outfile:
                outfile.write(fword)
            sys.exit(0)
        else:
            # continue searching
            print "invalid password"

raw_input("Password was not in this dictionary!")

Sample dictionary.txt

FableLand
FableWay
FableTree
FableSpirit
FableApple

The line that jumps out at me as being a performance concern is this one:

words = [line.strip() for line in infile]

You’re generating a list that contains every word in dictionary.txt. This means a 500 MB dictionary file will create a similarly large list (which is going to be a huge structure). It also means that if the password is early on in the list, you still have the whole file as a list in memory.

This gets followed by the line

for word1 in itertools.product(words, repeat=1):
    fword = word1[0]

and I’m not sure quite why you’re getting the words out in this way. As you go through itertools.product, you get tuples, and you need to get the first element out. Using an iterable is generally good for performance, but the problem is creating the list in the first place, more than iterating over it.

The advice in How to read large file, line by line in Python is helpful here. Consider reading your file as

with open('dictionary.txt') as f:
    for line in f:
        # try that line as your password

That’s probably going to give a noticeable benefit.

Other comments:

Right now, all the functionality is tied up together. I’d separate the code which tests a password, and the code which gets an iterable of passwords from dictionary.txt. For example:

def try_password(fword, rar_file):
    print "Attempting: %s" % fword

    # open unrar and test password
    output = os.popen("unrar.exe x %s -p %s" % (fword, rar_file))
    outstring = output.read()

    # unrar.exe returns "All OK" for correct password
    validate = outstring.find("All OK", 0, len(outstring))
    if validate != -1:
        print "Found password: %s" % fword
        return 0
    else:
        # continue searching
        return 1

with open('dictionary.txt') as f:
     for line in f:
         attempt = try_password(line.strip(), 'protected.rar')
         if attempt == 0:
             break

Now you could also use the same code which gets your passwords to tackle, say, a bunch of encrypted ZIP files.

I added the return codes 0 and 1 to denote success and failure when trying a password.

What did the slng variable stand for? Anyway, it was only used once so I removed it.

There are a few other tweaks I made, but nothing very major.
Your import sys, traceback statement should really be split onto two separate lines. Quoting from PEP 8, the Python style guide:

  Imports should usually be on separate lines

Why is the final line a raw_input instead of a print statement?

Where did dictionary.txt actually come from? You say you “generated” it, so could you just bypass the step where you write the passwords out to a file and just try them directly within the generator?