Balanced parentheses using standard C++ Here is a small program for checking if the parentheses are balanced or not. I am new to the standard library, and this is my first program. How can I improve it?
Any kind of modifications or alternatives and suggestions are welcomed.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool checkParentheses(string str, stack<char> s) {
    int flag = 0;
    char top;
    for(int i=0;i<str.length();i++) {
    if(str[i] == '(' || str[i] == '{' || str[i] == '[') {
        s.push(str[i]);
    }
    else {
        if(s.empty()) {
        flag = 1;
        break;
        }
        else {
        top = s.top();
        }
        if(str[i] == ')' && top == '('){
        s.pop();
        }
        else if(str[i] == '}' && top == '{'){
        s.pop();
        }
        else if(str[i] == ']' && top == '['){
        s.pop();
        }
        else {
        flag = 1;
        break;
        }

    }

    }
    if(s.empty() && flag == 0) {
    return true;
    }
    else if (flag == 1) {
    return false;
    }
    else {
    return false;
    }

}

int main() {
    stack <char> s;
    string str;
    cout << "Enter an expression with brackets: " << endl;
    cin >> str;
    cout << str << endl;
    if(checkParentheses(str, s)) {
    cout << "Expression is valid!" << endl;
    }
    else {
    cout << "Expression is not valid" << endl;
    }
}

Avoid using namespace std; - it's a large namespace, and growing as new C++ standards appear.  Bringing all its names into the global namespace completely obviates the benefits of namespaces, and in the worst case, can silently change the meaning of a program.  Get used to using the (very short) namespace prefix std::.

When we call checkParentheses(), we have to provide a stack for it to use.  If we're not using the stack outside of the function, then it could just be a local variable.  Alternatively, we could choose to share it with the caller, so we could supply the input in chunks.  If we did that, we'd want to pass it by reference, so that the changed stack can be passed into the next call.

We're not modifying the string argument, so it makes sense to pass it as a reference to const.  When we use it, we're only interested in its characters in turn, so we can replace the for loop with a range-based for, eliminating the variable i:

for (char c: str) {
    if (c == '(' || c == '{' || c == '[') {
        s.push(c);
    }
    else

We can eliminate the flag variable, as whenever we set it, we immediately return:

        if(s.empty()) {
            return false;
        }

Before we remove it, I'll just make a small observation on the final test of flag, where we have two branches of an if test that result in the same behaviour:

else if (flag == 1) {
return false;
}
else {
return false;
}

Obviously, that could just be replaced with

else {
    return false;
}

In fact, we can simple replace that if/else with a single statement:

return s.empty() && !flag;

With the above changes, we've simplified it a bit:

bool checkParentheses(const std::string& str)
{
    std::stack<char> s;
    for (char c: str) {
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        } else {
            if (s.empty()) {
                return false;
            }

            char  top = s.top();
            if (c == ')' && top == '(') {
                s.pop();
            } else if (c == '}' && top == '{') {
                s.pop();
            } else if (c == ']' && top == '[') {
                s.pop();
            } else {
                return false;
            }

        }
    }

    return s.empty();
}

We still have some quite repetitive code where we match a closing bracket against its opening one.  We can make this simpler and also more flexible (so that we could match « with », for example), by using a fixed map from opening to closing character:

static const std::map<char,char> pairs =
    { {'(', ')'},
      {'{', '}'},
      {'[', ']'} };

We can use this to replace the chained if/else if/else by storing the expected closing character on the stack and then simply comparing:

    if (pairs.count(c)) {
        s.push(pairs.at(c));
    } else {
        if (s.empty() || s.top() != c) {
            return false;
        }
        s.pop();
    }

Finally, the presentation can be improved.  Please be a bit more generous with space around operators - it really does make the code easier to read!  The indentation looks wrong, but perhaps that's an artefact of how it was copied into Stack Exchange.  If you used tabs for indentation, that can get corrupted (as SE has tab stops every 4 positions, rather than the normal 8).

Modified code

#include <map>
#include <stack>
#include <string>

bool checkParentheses(const std::string& str)
{
    static const std::map<char,char> pairs =
        { {'(', ')'},
          {'{', '}'},
          {'[', ']'} };

    std::stack<char> s;
    for (char c: str) {
        if (pairs.count(c)) {
            s.push(pairs.at(c));
        } else {
            if (s.empty() || s.top() != c) {
                return false;
            }
            s.pop();
        }
    }

    return s.empty();
}


Automating heap dumps from an Android device or emulator I've automated the process of extracting and converting a heap dump from an Android device/emulator.

I'd appreciate any feedback and improvements regarding style, bad practices, non-idiomatic code, performance or other issues you may find.

Also, dump_heap() function tries to wait for a daemon to complete and I'm wondering if there are better ways to handle the situation.

#!/bin/bash
#
# Extracts a heap dump from a device/emulator.
# Assumes the appropriate tools (adb, hprof-conv) are included in the path.

SERIAL=""
PACKAGE=""
FILE=""

usage() {
    echo "Usage: -s <serialNumber> -p <package> -f <file>"
    exit 1
}

err() {
    local msg="$1"
    echo "$msg" >&2
    exit 1
}

create_file() {
    local file=$1
    local dir=$(dirname "$file")

    mkdir -p -- "$dir" && touch -- "$file"

    if [ ! -e "$file" ]; then
        err "File $file could not be created."
    fi
}

file_size_on_device() {
    local adbcmd="adb -s $SERIAL"
    local file="$1"
    local adbinfo="$adbcmd shell ls -l $file"

    $adbinfo | awk '{print $4}'
}

dump_heap() {
    local adbcmd="adb -s $SERIAL"
    local pid="$1"
    local file="$2"
    local dir=$(dirname "$file")

    # Remove any existing tmp files we created. Ideally, there should be none.
    local exists=$($adbcmd shell ls "$dir" | grep "$file")
    if [ -n "$exists" ]; then
        $adbcmd shell rm "$file"
    fi

    echo -n "Dumping heap "

    # Dump the heap to a tmp file on a device/emulator
    $adbcmd shell am dumpheap "$pid" "$file"

    # Beacuse the previous cmd runs as a daemon, we have to wait for it to
    # finish. The following checks the tmp file size continuously, stopping
    # when it's not changing anymore.
    sleepinterval=0.5

    s0=-1
    sleep $sleepinterval
    s1=$(file_size_on_device "$file")

    while ((s1 > s0))
    do
        echo -n "."
        sleep $sleepinterval
        let s0=$s1
        let s1=$(file_size_on_device "$file")
    done

    echo " Done"
}

extract_from_device() {
    local adbcmd="adb -s $SERIAL"

    local pid=$($adbcmd shell ps | grep $PACKAGE | awk '{print $2}')
    if [ -z "${pid}" ]; then
        err "PID for $PACKAGE not found. Is your app installed and running?"
    fi

    # Dump heap to tmp file on a device
    local file="/sdcard/hprof___tmp"
    dump_heap "$pid" "$file"

    # Extract
    local tmp="$FILE-nonconv"
    create_file $tmp
    $adbcmd pull -p $file $tmp

    # Convert
    if [ -s "$tmp" ]; then
        create_file $FILE
        hprof-conv $tmp $FILE
    else
        echo "No data to convert."
    fi

    # Finish
    $adbcmd shell rm "$file"
    rm -- $tmp

    echo "Done, converted heap extracted to $FILE"
}

while getopts ":s::p::f:" opt; do
    case $opt in
        s) SERIAL="$OPTARG";;
        p) PACKAGE="$OPTARG";;
        f) FILE="$OPTARG";;
        *) usage;;
    esac
done

if [ -z "${SERIAL}" ] || [ -z "${PACKAGE}" ] || [ -z "${FILE}" ]; then
    usage
else
    version=$(adb -s "$SERIAL" shell getprop ro.build.version.sdk | tr -d '\r')
    if [ "$version" -gt "10" ]; then
        extract_from_device
    else
        err "The target device/emulator must be API 11 or above."
    fi
fi

The above is part of Dumpey, which helps you

run the monkey on multiple devices or emulators and
make converted memory heap dumps before and after it

First of all, your code passes on http://www.shellcheck.net/# with flying colors, congrats!

Simplify variable initializations

Here you can drop all the "", it will be the same thing but easier to write:

SERIAL=""
PACKAGE=""
FILE=""

That is, like this:

SERIAL=
PACKAGE=
FILE=

Check if a regular file exists with -f instead of -e

I admire your paranoia, with all the --:

mkdir -p -- "$dir" && touch -- "$file"

if [ ! -e "$file" ]; then
    err "File $file could not be created."
fi

But I would also recommend to use -f instead of -e,
as you are really expecting a regular file,
and -e is not necessary a regular file, can be a directory too.

Avoid putting commands into variables, especially when used only once

About this code:

local adbinfo="$adbcmd shell ls -l $file"

$adbinfo | awk '{print $4}'

When the command in $adbinfo becomes anything non-trivial,
running the command with $adbinfo | ... may not work as expected.
As long as you keep that in mind, this is fine.
However, since you only use this command once in the file_size_on_device function,
I recommend to not use $adbinfo at all, but the command directly:

$adbcmd shell ls -l $file | awk '{print $4}'

Even so, just keep in mind that the same dangers exist for $adbcmd as for $adbinfo earlier. But at least we removed one layer of danger ($adbinfo),
so that's a good thing.

Simplify ls | grep, use just ls when it's good enough

In dump_heap, I'm wondering if this actually works as expected:

# Remove any existing tmp files we created. Ideally, there should be none.
local exists=$($adbcmd shell ls "$dir" | grep "$file")
if [ -n "$exists" ]; then
    $adbcmd shell rm "$file"
fi

In particular, it seems to me the rm command should be like this:

$adbcmd shell rm "$dir/$file"

Because ls "$dir" | grep "$file" suggests that $file is just a filename,
not an absolute path, inside the directory $dir.

Also, the call to grep seems unnecessary, a single ls command should do:

local exists=$($adbcmd shell ls "$dir/$file")

Simplifying conditions

Still in dump_heap,
when checking if $exists is non-empty, instead of -n "$exists",
you can just drop the -n, simply [ "$exists" ] is the same thing.

Lastly, I'm wondering if the whole thing can be simplified to:

# Remove any existing tmp files we created. Ideally, there should be none.
$adbcmd shell ls "$dir/$file" &>/dev/null && $adbcmd shell rm "$dir/$file"

Prefer printf over echo for non-trivial printing

The various flags of echo are unreliable.
Depending on your system, they might work as expected or not.
Rather than using any of the flags of echo, I prefer printf.
So instead of:

echo -n "Dumping heap "

I recommend:

printf "Dumping heap "

However, I prefer echo when printing trivial text,
without using any flags,
and when I want a terminating newline.

Prefer fewer processes

In this pipeline there are 3 processes: adb, grep and awk

local pid=$($adbcmd shell ps | grep $PACKAGE | awk '{print $2}')

Especially in cases when an awk follows a grep,
one begs the question if the task of grep can be included in the awk command.
And in this case yes:

local pid=$($adbcmd shell ps | awk -v pkg=$PACKAGE '$0 ~ pkg {print $2}')

However, a little laziness is not against the spirit of good shell scripting.
Your version with grep is shorter and simpler,
and on most days I would go with it too.
So this remark is just for the record, and for the meticulous.

Simplify condition

Instead of this:

if [ -z "${SERIAL}" ] || [ -z "${PACKAGE}" ] || [ -z "${FILE}" ]; then

I suggest to simplify like this:

if ! [ "$SERIAL" -a "$PACKAGE" -a "$FILE" ]; then


UPenn CIS 194 Homework 1: Validating credit card numbers I am working through UPenn CIS 194: Introduction to Haskell (Spring 2013). Since I am not able to take the course for real I am asking for CR (feedback) as it could be from teacher in that course.
HW1 - Validating Credit Card Numbers - Full description
A shortened problem statement:

Validate a credit card number by the following steps:

Double the value of every second digit from the right
Take the sum of the digits of the new values
Check whether the sum modulo 10 is 0.

Write the functions toDigits, toDigitsRev and doubleEveryOther for the first task, sumDigits for the second, and validate for the third.

toDigitsRev :: Integer -> [Integer]
toDigitsRev 0 = []
toDigitsRev n
  | n < 0 = []
  | n < 10 = [n]
  | otherwise = n `mod` 10 : toDigitsRev (n `div` 10)

toDigits :: Integer -> [Integer]
toDigits n = reverse (toDigitsRev n)

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zx)
  | length (x:y:zx) `mod` 2 == 0 = 2*x : y : doubleEveryOther zx
  | otherwise = x : 2*y : doubleEveryOther zx

sumDigits :: [Integer] -> Integer
sumDigits [] = 0
sumDigits (x:[]) = x
sumDigits (x:xs)
  | x < 10 = x + sumDigits xs
  | otherwise = sumDigits (toDigits x) + sumDigits xs

validate :: Integer -> Bool
validate 0 = False
validate n = (sumDigits (doubleEveryOther (toDigits n))) `mod` 10 == 0

type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c
  | n == 0 = []
  | n == 1 = (a, b) : hanoi 0 a b c
  | otherwise =  hanoi (n-1)  a c b ++ [(a, b)] ++  hanoi (n-1) c b a

You're on the right track, I think.  If I had to pick one general criticism, it would be to watch out for redundant special cases.

In my opinion, the exercise guides you towards making an unnecessary complication in toDigits and doubleEveryOther.  Actually, the list of digits from right to left, as produced by toDigitsRev, is the more natural representation to work with.  If you work with the list in left-to-right order, then doubleEveryOther needs to look ahead to see whether the list has an odd or even digit count, which is awkward.  Therefore, if given free reign, I'd define a doubleEveryOther' that expects right-to-left input instead.

toDigitsRev does not need special cases for 0 and for n < 10.  Instead of calling div and mod, use the divMod function to capture both pieces of information from the same calculation.

toDigitsRev :: Integer -> [Integer]
toDigitsRev n
  | n <= 0    = []
  | otherwise = m : toDigitsRev d
  where
    (d, m) = n `divMod` 10

As mentioned above, we can simplify doubleEveryOther by working right-to-left:

-- Doubles the second, fourth, sixth… numbers in the list
doubleEveryOther' :: [Integer] -> [Integer]
doubleEveryOther' (x:y:zs) = x : 2 * y : doubleEveryOther' zs
doubleEveryOther' (x:[])   = [x]
doubleEveryOther' []       = []

You don't need a case for sumDigits (x:[]) — it's already covered by sumDigits (x:xs), where xs is the empty list.  The way you wrote it is fine, but personally I'd prefer to write it as sum . map sumDigits' so that you can see at a glance that it's performing a sum of some transformed values.

sumDigits :: [Integer] -> Integer
sumDigits = sum . map sumDigits'
  where
    sumDigits' n
      | n < 10    = n
      | otherwise = sumDigits $ toDigitsRev n

The validate function does not need a special case for 0.  It's also more idiomatic to set up a "pipeline" of function calls using $ than to use nested parentheses.

validate :: Integer -> Bool
validate n = 0 == (sumDigits $ doubleEveryOther' $ toDigitsRev n) `mod` 10


Product of corresponding elements in 2 arrays Given two arrays A and B, of length N and length k respectively, if we move B over A and take the sum of product of corresponding elements of A and B, then find the minimum of those sum of products.

For example, if A=[2,3,4,5] and B=[1,3], then after moving B over A, we get 3 possible values [2*1+3*3, 3*1+4*3, 4*1+3*5], max of which is 19.

I tried coding for this and reached an \$O(n^2)\$ solution. Can I reduce the algorithm's complexity here?

My code in Python:

A=[2,3,4,5]
B=[1,3]
print max([sum([A[i+j]*B[j] for j in xrange(len(B))]) for i in xrange(len(A)-len(B)+1)])

This is effectively a convolution problem. Theoretically, this can (potentially) be done faster by a conversion to the frequency domain, that is, using a fast Fourier transform (FFT) convolution.

Writing a high-performance FFT convolution isn't something I'd want to reproduce here (even if I could reproduce it, which to be perfectly honest, I couldn't). Thankfully, I don't have to: libraries like numpy and scipy provide this functionality: see scipy.signal.fftconvolve.

The only thing that we have to be careful with is that convolution reverses the second array, so we must provide that in a reversed form:

import numpy
from scipy.signal import fftconvolve

x = numpy.array([2,3,4,5])
y = numpy.array([1,3])
maximum = numpy.max(fftconvolve(x, y[::-1], mode='valid')) # reversed view of y

For small arrays, this is likely to be slower than the naïve O(n2) convolution, due to the overhead of conversions (and multiplying complex numbers). If you are in this case, then you should try scipy.signal.convolve.

For an in-depth writeup of computational complexity comparisons between the naïve convolution and the fast Fourier transform, see here.


The solution for the exercise 1-22 from the book "The C programming language" K&R2 Exercise 1-22. Write a program to "fold" long input lines into two or
more shorter lines after the last non-blank character that occurs
before the n-th column of input. Make sure your program does something
intelligent with very long lines, and if there are no blanks or tabs
before the specified column.

The key idea is that I process whitespace character by character while processing a sequence of non-blank characters block by block, i.e. I read a block then decide whether to print it in the current line or next line.
#include <stdio.h>

#define LINE_MAX_SIZE 21        /* The maximum number of columns allowed in a single line */
#define IN_NON_BLANK_SEQ 1      /* Indicate that a sequence of non-blank character are being processed */
#define TAP_STOP_DIST 5

#define NON_BLANK(ch)   (ch != '\t' && ch != '\n' && ch != ' ')

int get_next_tap_pos(int current_column) {
    // columns numbered 0, 1, 2... there is a tap stop at 0, 5, 10, 15, 20
    return current_column / TAP_STOP_DIST * TAP_STOP_DIST + TAP_STOP_DIST;
}

int main(void)
{
    char block[LINE_MAX_SIZE+1];
    int column_pos = 0;                 /* Indicate the current column in the output where the next character will be printed*/
    int index_non_blank = 0;            /* Indicate the number of the non-blank char in the next non-blank char sequence */
    int state = !IN_NON_BLANK_SEQ;      /* Indicate whether a non-blank character is being processed */

    int ch;
    while ( (ch = getchar()) != EOF) {
        if (NON_BLANK(ch)) {

            state = IN_NON_BLANK_SEQ;
            if (index_non_blank == LINE_MAX_SIZE) {
                // There is a word bigger than the size of the line
                block[LINE_MAX_SIZE] = '\0';
                // Should I print it in the current line or in the next line ?
                // Our word is as big as our line. so if current line is not empty, we can't print it here
                if (column_pos != 0)
                    putchar('\n');
                printf("%s\n", block);
                column_pos = 0;
                index_non_blank = 0;
                block[index_non_blank] = ch;
            }
            else {
                block[index_non_blank] = ch;
                ++index_non_blank;
            }
        }
        else {
            // Is there a non-blank sequence that just finished ?
            if (state == IN_NON_BLANK_SEQ) {
                // Should the current word be printed in the current line or next line ?
                block[index_non_blank] = '\0';
                int expected_column_num = column_pos + index_non_blank;
                if (expected_column_num <= LINE_MAX_SIZE) {
                    printf("%s", block);
                    column_pos = expected_column_num;
                }
                else {
                    putchar('\n');
                    printf("%s", block);
                    column_pos = index_non_blank;
                }

                state = !IN_NON_BLANK_SEQ;
                index_non_blank = 0;
            }
            // now print the whitespace character and update column position
            if (ch == '\n') {
                putchar(ch);
                column_pos = 0;
            }
            else if (ch == ' ' && column_pos < LINE_MAX_SIZE) {
                putchar(ch);
                ++column_pos;
            }
            else if (ch == '\t' && column_pos < LINE_MAX_SIZE) {
                putchar(ch);
                column_pos = get_next_tap_pos(column_pos);
            }
            else {
                putchar('\n');
                column_pos = 0;
            }
        }
    }
}

Github link

This looks pretty competent code to me.  Good to see that you've included handling for tabs.
I only have minor points to raise:

#define NON_BLANK(ch)   (ch != '\t' && ch != '\n' && ch != ' ')

If we include <ctype.h>, we should be able to use isspace() instead of this macro.  In any case, a function is preferred to a macro, especially a macro that expands its arguments more than once (we can't call this with an argument such as *++p, for example).

#define IN_NON_BLANK_SEQ 1

We only have two states, so we should use a boolean (with a better name than state).  Assuming we have <stdbool.h>, then I'd replace int state = !IN_NON_BLANK_SEQ; with
   bool in_blank_seq = false;

Actually, we might not need this at all - I think that when we have most recently seen whitespace, then index_non_blank is non-zero.

int column_pos = 0;
int index_non_blank = 0;

These two could be unsigned.  But that might not matter, given the small range of values they ever hold.

#define TAP_STOP_DIST 5
int get_next_tap_pos(int current_column) {

Spelling - that should be tab.  And what kind of terminal has tab stops every five characters?  Pretty much every terminal (and terminal emulator) I've ever used has tab stops every eight characters, at least unless specifically changed.

#define LINE_MAX_SIZE 21

Additional exercise - make this configurable, by command-line option.


Simple command-line password generator I'm very new to Haskell, I've read most of learnyouahaskell.com and played around with some simple things, but this is probably the most 'complicated' bit of Haskell I've written so far. I have an implementation in PHP that does basically the same thing, but it is much much faster.. I'm guessing my bottleneck here is that randomRIO takes a long time to return a value, is there any way to increase the speed, or get an array of values instead of grabbing them one at a time?

That aside, any other tips and/or suggestions about improving my implementation would be very helpful!

module Main where

import System.Environment
import System.Exit
import System.Random (randomRIO)
import Control.Monad (replicateM)
import qualified Data.Map as M

import Text.Regex.Posix

main :: IO ()
main = do
    args <- getArgs
    let helpOnly = "-h" `elem` args
    if helpOnly
        then putStrLn usage
        else do
        password <- generatePassword ("-w" `elem` args)
        putStrLn password
    exitSuccess

usage :: String
usage = unlines [
        "",
        "Usage: [ -w, --with-symbols ] [ -h, --help ]",
        "",
        "By default, generates a 16 character password that does not include symbols.",
        "",
        "-w, --with-symbols  include symbols",
        "-h, --help          print a brief help message"
        ]

symbols :: String
symbols = "!$%^&*()-_=+[{]};:@#~,<.>/?"

randomReplace :: String -> String -> IO String
randomReplace [] subject = return subject
randomReplace (replacement:rs) subject = do
    randomIndex <- randomRIO (0, length subject - 1) :: IO Int
    let hash = zip [0 .. length subject - 1] subject
    (randomReplace rs . map snd . M.toList .  M.insert randomIndex replacement . M.fromList) hash

generatePassword :: Bool -> IO String
generatePassword withSymbols = do
    let passwordLength = 500 -- obviously you wouldn't use 500 as a default here, but I'm just benchmarking
    numDigits <- randomRIO (1, passwordLength) :: IO Int
    digits <- replicateM numDigits (randomRIO (1, 9) :: IO Int)
    numUppercase <- randomRIO (1, passwordLength) :: IO Int
    uppercaseLetters <- replicateM numUppercase (randomRIO ('A', 'Z') :: IO Char)
    p1 <- replicateM passwordLength (randomRIO ('a', 'z') :: IO Char)
    p2 <- randomReplace (concatMap show digits) p1
    p3 <- randomReplace uppercaseLetters p2
    password <- if withSymbols
        then do
            numSymbols <- randomRIO (1, passwordLength) :: IO Int
            symbolsToReplace <- replicateM numSymbols ((randomRIO (0, length symbols - 1) :: IO Int) >>= (\x -> return $ symbols !! x))
            randomReplace symbolsToReplace p3
        else return p3
    if (password =~ "[a-z]" :: Bool) && (password =~ "[A-Z]" :: Bool) && (password =~ "[0-9]" :: Bool) -- we knows symbols are in there since it went last
        then return password
        else generatePassword withSymbols

Too much IO.
Text.Regex.Posix is too much for those simple tests. Why not any isUpper, any isLower, any isDigit?
Your program ignores --help and --with-symbols (have a look at OptParse-Applicative)
randomReplace has too many temporary structures (see below)
You use length too often. Unlike in PHP, it's quite slow (O(n) vs O(1)).

A short search for bottlenecks

  I'm guessing my bottleneck here ...

Don't guess, measure. Enable profiling to check where you're actually losing time:

$ stack install --profile random
$ stack install --profile regex-posix
$ stack exec -- ghc -O2 -prof -auto-all PWGen.hs
$ ./PWGen+RTS -s -p

If you don't use stack, make sure to enable profiling when you install the packages:

$ cabal sandbox init
$ cabal install -p random regex-posix
$ cabal exec -- ghc -O2 -prof -auto-all PWGen.hs
$ ./PWGen +RTS -s -p

This is actually fast, but not fast enough:

9,420,841,024 bytes allocated in the heap
   6,425,011,808 bytes copied during GC
       1,021,088 bytes maximum residency (2915 sample(s))
          59,672 bytes maximum slop
               4 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     15199 colls,     0 par    1.844s   1.971s     0.0001s    0.0011s
  Gen  1      2915 colls,     0 par    1.188s   1.076s     0.0004s    0.0009s

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    1.953s  (  2.001s elapsed)
  GC      time    3.031s  (  3.048s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    5.000s  (  5.050s elapsed)

  %GC     time      60.6%  (60.4% elapsed)

  Alloc rate    4,823,470,604 bytes per MUT second

  Productivity  39.4% of total user, 39.0% of total elapsed

Note: I've changed passwordLength to 5000, since it was too quick with 500. However, the times above don't give enough information where you actually lose that time. That's what -p was for. PWGen.prof contains the following data:

COST CENTRE                        MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN                               MAIN                        59           0    0.0    0.0   100.0  100.0
 main                              Main                       119           0    0.8    0.0    99.9  100.0
  generatePassword                 Main                       121           1    0.4    0.1    99.1  100.0
   randomReplace                   Main                       124        5730   69.5   62.9    98.7   99.9
    randomReplace.hash             Main                       125        5728   29.2   36.9    29.2   36.9
  main.helpOnly                    Main                       120           1    0.0    0.0     0.0    0.0

Almost all memory is allocated in randomReplace. After all, you break both the map and the list apart for every character in replacement. That's quite costly. Instead, let's try to stay on a single map as long as possible:

-- This is still not an idiomatic version, but better
randomReplace :: String -> String -> IO String
randomReplace rs subject = fmap (map snd . M.toList) $ go rs $ M.fromList $ zip [0..] subject
  where
    l = length subject
    go []     m = return m
    go (r:rs) m = do
      randomIndex <- randomRIO (0, l - 1) :: IO Int
      go rs $ M.insert randomIndex r m

What's the big difference? Well, we're not using length repeatedly, which is a big plus. length needs to traverse the whole list to get its result. Also, we're not switching between lists and maps all the time, which gets rid of all intermediate lists.

Running the benchmark again, we gain the following result:

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    0.016s  (  0.021s elapsed)
  GC      time    0.016s  (  0.011s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.031s  (  0.033s elapsed)

  %GC     time      50.0%  (32.6% elapsed)

  Alloc rate    2,105,396,736 bytes per MUT second

  Productivity  50.0% of total user, 47.7% of total elapsed

                                                                                individual     inherited
COST CENTRE                        MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN                               MAIN                        59           0    5.6    0.0   100.0  100.0
 main                              Main                       119           0    5.6    0.1    94.4   97.8
  generatePassword                 Main                       121           1   55.6   44.7    88.9   97.7
   randomReplace                   Main                       124           2    0.0   16.4    33.3   53.0
    randomReplace.l                Main                       126           2    0.0    0.0     0.0    0.0
    randomReplace.go               Main                       125        5521   33.3   36.6    33.3   36.6
  main.helpOnly                    Main                       120           1    0.0    0.0     0.0    0.0

Runtime is down to 0.03s from 5s. Keep in mind that this is for passwordLength = 5000. This is 0.6% of the original runtime. I can even crank passwordLength up to 100000 and it still takes only 0.7s total.

The reason here is (somewhat) simple. randomReplace had a bad asymptoticl complexity. If n is the length of subject and k is the length of rs, you get roughly:

k                    -- for every character in rs
  * ( n              -- get the length of subject (every time!)
      + n * log(n)   -- create the map
      + log (n)      -- insert a character at a random position
      + 2 * n        -- zip the list and zip it back
    )

Compare this to the new version:

k * (log (n))        -- for every character insert a character into a map
+ n                  -- get the length once(!)
+ n * log (n)        -- create a map once(!)
+ 2 * n              -- zip the map and zip it back

So this would be a way to improve your runtime tremendously.

Further places for improvement

generatePassword is too opaque, it's not clear what you're doing. Try to split it into several sections. For example, all those lists of symbols can be abstracted into

randomListOf :: Random g => Int -> (g, g) -> IO [g]
randomListOf n r = do
    l <- randomRIO (1, n)
    replicateM l $ randomRIO r

-- ...
generatePassword = do
    -- ...
    digits    <- randomListOf passwordLength ('0','9')
    uppercase <- randomListOf passwordLength ('A','Z')

However, you should try to make all your functions pure. That way, you can easily test them later.

Also, you can try to generate passwords that contain at least one digit. It's not possible with random by default, but you can probably achieve something similar to a modified Test.QuickCheck.frequency.


Design Pattern Question/Violating OCP Is there a design pattern I can use for a situation like below.  This is an example I made up to try and explain the situation I'm dealing with currently.  I keep having to add new DeviceScript classes to my DeviceAnalyzer as situation come up and adding logic about when to return the new type in the 'GetScriptForDevice'.

This example I have given is pretty simple but the business logic I'm having to implement for my real 'GetScriptForDevice' isn't always this easy.  Any suggestions on a pattern or an example of a better way to structure this code to follow a better pattern would be greatly appreciated.  I'm violating OCP every time I need to add a new DeviceScript and I'm trying to find a way around this because my class is getting quite long and fragile.

Thanks.

public class DeviceScript {
    public string Name { get; set; }
    public string SecurityScriptName { get; set; }
    public string BusinessScriptName { get; set; }
}

public class DeviceAnalyzer {

    public const string US_SecurityScript = "US_SecurityScript";
    public const string US_BusinessScript = "US_BusinessScript";
    public const string UK_SecurityScript = "UK_SecurityScript";
    public const string UK_BusinessScript = "UK_BusinessScript";

     private DeviceScript UnitedStates = new DeviceScript {
         Name = "US_Script",
         SecurityScriptName = US_SecurityScript,
         BusinessScriptName = US_BusinessScript
     };

     private DeviceScript UnitedKingdom = new DeviceScript {
         Name = "UK_Script",
         SecurityScriptName = UK_SecurityScript,
         BusinessScriptName = UK_BusinessScript
     };

     public DeviceScript GetScriptForDevice(IDevice device) {

         if(device.Location == Locations.US) {
          return UnitedStates;
         }

         if(device.Location == Locations.UK) {
          return UnitedKingdom;
         }

        return null;
     }

}

I would suggest something like that

public interface IDeviceScript
{
    string Name { get; }
    string SecurityScriptName { get; }
    string BusinessScriptName { get; }
    bool IsScriptApply(IDevice device);
}

public interface IDevice
{
    Locations Location { get; }
    // more methods and properties
}

[Serializable]
[AttributeUsage(AttributeTargets.Class)]
public class DeviceScriptAttribute : Attribute
{
}

[DeviceScript]
public class UnitedStatesScript : IDeviceScript
{
    public string Name
    {
        get { return "US_Script"; }
    }

    public string SecurityScriptName
    {
        get { return "US_SecurityScript"; }
    }

    public string BusinessScriptName
    {
        get { return "US_BusinessScript"; }
    }

    public bool IsScriptApply(IDevice device)
    {
        return device.Location == Locations.US;
    }
}

public IDeviceScript GetScriptForDevice(IDevice device)
{
    IEnumerable<IDeviceScript> deviceScripts =
        Assembly.GetExecutingAssembly()
                .GetTypes()
                .Where(t => t.GetCustomAttributes<DeviceScriptAttribute>().Any())
                .Select(t => Activator.CreateInstance(t))
                .Cast<IDeviceScript>();

    foreach (IDeviceScript deviceScript in deviceScripts)
    {
        if (deviceScript.IsScriptApply(device))
        {
            return deviceScript;
        }
    }

    return null;
}

Now you can add more scripts just by adding new classes to your project. No xml configs are required :)

Futher suggestions:

After calculating deviceScripts enumerable once you can store it in some static field for further use.
Name property of IDeviceScript could be moved to DeviceScriptAttribute if you don't need it in your code.
I would make GetScriptForDevice method static but unfortunately .net doesn't support statics in interfaces :(


Number-guessing game in Kotlin I am a Java developer, and I recently gave Kotlin a try.
To begin, I did a little exercise I often do when I start a new language, to verify I got the very basics: the more or less game.
The code I submit there is working fine, but of course I suspect it may be too much like Java, and I would like you to point to me how I can make my code more Kotlin.

package fr.caro

import java.util.*

fun main(args: Array<String>) {
    val min = 0
    val max = 100
    var nbAttempts = 0
    val random = SplittableRandom()
    val reader = Scanner(System.`in`)
    val goal = random.nextInt(min, max)
    var userGuess: Int

    computerSays("I chose a number between $min and $max")
    do {
        nbAttempts++
        computerSays("What's your guess?")
        userGuess = reader.nextInt()
        if (userGuess > goal) computerSays("less !")
        else if (userGuess < goal) computerSays("more !")
    } while(userGuess != goal)

    computerSays("Congratulation ! You found in $nbAttempts attemps.")
}

fun computerSays(text: String) {
    println("Computer : " + text)
}

PS: I wonder if putting the min and max values in a Pair object would be a good idea?

When statement

You could replace:

if (userGuess > goal) computerSays("less !")
else if (userGuess < goal) computerSays("more !")

and

computerSays("Congratulation ! You found in $nbAttempts attemps.")

with:

when {
    userGuess > goal -> computerSays("less !")
    userGuess < goal -> computerSays("more !")
    userGuess == goal -> computerSays("Congratulation ! You found in $nbAttempts attemps.")
}

Extension functions

You could write computerSays as:

fun String.outputAsComputer() {
    println("Computer : " + this)
}

then to output Computer: ABC you could just write:

"ABC".outputAsComputer()

Although there are good arguments for and against this, it is more a chance to get used to extension functions


Function that performs a test of whether a number is greater or less than some expected result The program that contains the function I'm asking (handle_non_exact_answer) about has several instances of a class Test, with some options the user can set that determines the behavior of the class. If the class has certain options, we handle the class differently, so I deal with these cases in a separate function, which is below.

I would like to learn a) how to better write the function (ideally in the "most pythonic" way,) and b) how to resolve a pylint warning related to this function: Unnecessary "else" after "return".

import random
class Test:
    def __init__(self):
        self.precision = None
        self.expected_result = None

def handle_non_exact_answer(test, answer):
    if test.precision not in {"less", "more", "lesser", "greater"}:
        return False
    else:
        if test.precision == "less" and answer < test.expected_result:
            print("passed")
        elif test.precision == "more" and answer > test.expected_result:
            print("passed")
        elif test.precision == "lesser" and answer <= test.expected_result:
            print("passed")
        elif test.precision == "greater" and answer >= test.expected_result:
            print("passed")
        else:
            print("failed")
    return True

def main():
    test = Test()
    test.precision = "greater"
    test.expected_result = 0
    test1 = Test()
    test1.precision = "lesser"
    test1.expected_result = 0
    test2 = Test()
    test2.precision = "more"
    test2.expected_result = 0
    test3 = Test()
    test3.precision = "less"
    test3.expected_result = 0

    tests = [test, test1, test2, test3]

    for test in tests:
        handle_non_exact_answer(test, random.randint(-10,10))

if __name__ == "__main__":
    main()

That's a very unconventional usage of the term "precision".  I think that "comparison" would be the appropriate word here.

The Test class is severely underdeveloped.  The constructor fails to construct a useful object.  Furthermore, representing the comparison as one of four magic strings is cryptic and unhelpful.  On top of that, the Test class doesn't even know how to execute its own test, forcing you to write a separate handle_non_exact_answer() function.

It's rather weird that handle_non_exact_answer() returns True or False to indicate whether the comparison was one of the four recognized magic strings.  I would consider an unrecognizable comparison as an error, and raise an exception — preferably when the Test is constructed, not when you try to perform the test.

Printing the "passed" or "failed" result limits the function's reusability.  It should return True or False instead, and let the caller decide what to do with the result.

The if-else chain is more idiomatically done using a dictionary lookup.

Your main() test isn't very effective.  You don't print the randomly chosen number, so it's hard to tell whether the results are correct.  Also, you've used test to mean two different things: the first test ("greater than 0"), and also the iteration variable (for test in tests: …), which is unnecessarily confusing.

Suggested solution

import operator
import random

class ComparisonTest:
    COMPARATORS = {
        'less': operator.lt,
        'more': operator.gt,
        'lesser': operator.le,
        'greater': operator.ge,
    }

    def __init__(self, comparison, threshold):
        try:
            self._func = lambda n: self.COMPARATORS[comparison](n, threshold)
        except KeyError:
            raise ValueError('Invalid comparison: {0}'.format(comparison))

    def __call__(self, n):
        return self._func(n)

def main():
    n = random.randint(-1, 1)
    print('n = {0}'.format(n))
    test0 = ComparisonTest('greater', 0)
    test1 = ComparisonTest('lesser', 0)
    test2 = ComparisonTest('more', 0)
    test3 = ComparisonTest('less', 0)
    for test in [test0, test1, test2, test3]:
        print("passed" if test(n) else "failed")

if __name__ == "__main__":
    main()

More compact implementation

Here's a more compact way to write ComparisonTest, using functools.partial().  (Use the same main() function as above.)

from functools import partial
import operator

def ComparisonTest(comparison, threshold):
    try:
        return partial({
            'less': operator.gt,  # Comparisons are intentionally reversed
            'more': operator.lt,
            'lesser': operator.ge,
            'greater': operator.le,
        }[comparison], threshold)
    except KeyError:
        raise ValueError('Invalid comparison: {0}'.format(comparison))


Implementation of Singly Linked List (C++) I tried to implement a singly linked list myself, sorry it is not commented but I think it should be pretty self-explanatory, if not feel free to comment. I know that using namespace std; is not optimal, but I figured it would be okay for this little example. Same goes for defining the class right in the main.cpp file (and in the declaration). I have two questions:

Is this even a correct implementation or did I miss something important? The methods worked as expected for me.
Would it make any sense to use smart pointers here? If yes, why? And what would I have to change for it to work?

Thank you for your time, I would appreciate any answers! :)
#include <iostream>

using namespace std;

struct Node
{
int32_t data;
Node* next;
};

class linked_list
{
public:

linked_list() : last{ NULL }, tmp{ NULL }, begin{ NULL } {};

~linked_list()
{
    clear();
}
void push_back(int32_t data)
{
    if (begin)
    {
        tmp = new Node;
        tmp->data = data;
        tmp->next = NULL;

        last->next = tmp;
        last = tmp;
        tmp = NULL;
    }
    else
    {
        begin = new Node;
        begin->data = data;
        begin->next = NULL;
        last = begin;
    }
}
void display_all()
{
    if (begin)
    {
        tmp = begin;
        while (tmp)
        {
            cout << tmp->data << endl;
            tmp = tmp->next;
        }
        tmp = NULL;
    }
    else
    {
        cout << "List is empty." << endl;
    }
}
void clear()
{
    while (tmp != last)
    {
        tmp = begin->next;
        delete begin;
        begin = tmp;
    }
    delete last;
    begin = NULL;
    tmp = NULL;
    last = NULL;
    }
private:
    Node* last;
    Node* begin;
    Node* tmp;
};

PS:
(Someone told me this would fit better on this site than on Stack Overflow so I am reposting.)

struct Node would benefit from its own constructor. As a side note, if you don't want to expose struct Node to the client (and trust me, you don't), better make it private to class LinkedList.

tmp doesn't deserve to be a class member. It is strictly local to each method.

DRY. push_back could and should be streamlined:
  struct Node * tmp = new Node(data);
  if (begin) {
      last->next = tmp;
  } else {
      begin = tmp;
  }
  last = tmp;

display_all should not print anything on the empty list. The caller might be greatly confused.

clear could and should be streamlined. Run the loop till nullptr:
  while (begin) {
      struct Node * tmp = begin->next;
      delete begin;
      begin = tmp;
  }
  last = nullptr;

As a side note, prefer nullptr to NULL.


Word ladder finding class I have a class that I'm using to find the shortest word ladder between two words. Each "Step" in that ladder is returned as a String element in a LinkedList. If it can't find one, it returns an empty LinkedList. The class is only intended to work with capital letters.

A step can only be formed from a word in the HashSet<String> dictionary variable.

I haven't made anything like this before, and I'm posting here because I'd appreciate help making it run faster and advice regarding how to make the code itself more easily read by other humans.

public class WordLadder {

private HashSet<String> dictionary;

public WordLadder(HashSet<String> dictionary) {

   this.dictionary = dictionary;
}

/**
 * This method finds the shortest word ladder between two words and returns
 * it as a LinkedList of Strings.
 *
 * @return LinkedList of Strings.
 */
@SuppressWarnings("unchecked")
public LinkedList<String> findLadder(String input) {

   // this method relies on deleting entries from a HashSet
   HashSet<String> tempDict = (HashSet<String>) this.dictionary.clone();

   // create LinkedLists
   LinkedList<Integer> distances = new LinkedList<>();
   LinkedList<LinkedList<String>> ladders = new LinkedList<>();
   LinkedList<String> words = new LinkedList<>();

   // split the input line into the starting and ending words
   String startWord = input.substring(0, input.indexOf(" "));
   String endWord = input.substring(input.indexOf(" ") + 1);

   // holds the shortest ladder found
   LinkedList<String> shortestLadder = new LinkedList<>();

   words.add(startWord);
   distances.add(1);

   ladders.add(new LinkedList<>(Arrays.asList(startWord)));

   while (!words.isEmpty()) {
      Integer distance = distances.pop();
      LinkedList<String> ladder = ladders.pop();
      String word = words.pop();

      // has the shortest ladder been found?
      if (word.equals(endWord)) {
            shortestLadder = ladder;
      }

      for (int i = 0; i < word.length(); i++) {

         char[] currCharArr = word.toCharArray();

         for (char c = 'A'; c <= 'Z'; c++) {
            currCharArr[i] = c;
            LinkedList<String> currentPathQueueTemp = new LinkedList<>(ladder);

            String newWord = new String(currCharArr);

            if (tempDict.contains(newWord)) {
               words.add(newWord);
               ladders.add(currentPathQueueTemp);
               tempDict.remove(newWord);
               distances.add(distance + 1);
               currentPathQueueTemp.add(newWord);
            }
         }
      }
   }

   return shortestLadder;
}

}

Fist of all, the code doesn't work. here's my test method. I get an empty response.

public static void main(String... args) {

    HashSet<String> dictionary = new HashSet<>();
    dictionary.add("abcd");
    dictionary.add("abce");
    dictionary.add("abcf");
    dictionary.add("abcg");
    dictionary.add("abch");
    dictionary.add("abxd");
    dictionary.add("abxh");

    WordLadder wd = new WordLadder(dictionary);
    System.out.println(wd.findLadder("abcd abch"));

}

However, assuming you fix this, here is my review

API definition: the api you chose is counter-intuitive. why not accept two string words?
code to the interface: if you meant words to be a LIFO stack, use the Stack interface of push() and pop().  there are two reason for that: one is that it makes the usage of words clearer to another human. more importantly - how do you that LinkedList add() is doing the same as push()?
the method violates the single responsibility principle. it is parsing the input, it searches for a word in the dictionary and all the other stuff. what if you wanted to have another data structure for the dictionary? or put it in a DB?


Build clusters from connections (virus propagation) The scenario is the following: There is a list of persons and places where those persons visit. Each person is connected to a single or multiple places. See the picture below, where O[i] represents objects (persons) and P[i] places, respectively.

I need to get the list of places connected by those persons.

Codes:

class Program
{
    static void Main(string[] args)
    {
        var Connections = new List<Tuple<string, List<string>>>()
        {
            new Tuple<string, List<string>>("O1", new List<string>(){ "P1", "P2" }),
            new Tuple<string, List<string>>("O2", new List<string>(){ "P2", "P3", "P4" }),
            new Tuple<string, List<string>>("O3", new List<string>(){ "P8" }),
            new Tuple<string, List<string>>("O4", new List<string>(){ "P5", "P11" }),
            new Tuple<string, List<string>>("O5", new List<string>(){ "P2", "P3" }),
            new Tuple<string, List<string>>("O6", new List<string>(){ "P4"}),
            new Tuple<string, List<string>>("O7", new List<string>(){ "P7", "P10" }),
            new Tuple<string, List<string>>("O8", new List<string>(){ "P5", "P6", "P7", "P12" }),
            new Tuple<string, List<string>>("O9", new List<string>(){ "P7", "P11" }),
            new Tuple<string, List<string>>("O10", new List<string>(){ "P13" }),
            new Tuple<string, List<string>>("O11", new List<string>(){ "P8", "P9" }),
        };

        var Clusters = Connections.Select(x => x.Item2).ToList();

        bool proceed = true;
        do
        {
            var pairs = Clusters.SelectMany(x => Clusters, (x, y) =>
            Tuple.Create(x, y)).Where(x => x.Item1 != x.Item2);

            proceed = false;
            foreach (var pair in pairs)
            {
                var cluster1 = pair.Item1;
                var cluster2 = pair.Item2;

                if (cluster1.Intersect(cluster2).Any())
                {
                    cluster1.AddRange(cluster2.Where(x => !cluster1.Contains(x)));
                    Clusters.Remove(cluster2);
                    proceed = true;
                    break;
                }
            }
        } while (proceed);

        foreach (var cluster in Clusters.OrderByDescending(x => x.Count()))
        {
            Console.WriteLine(cluster.OrderBy(x => x).Aggregate((i, j) => i + ", " + j));
        }
        Console.Read();
    }
}

Output:

P10, P11, P12, P5, P6, P7
P1, P2, P3, P4
P8, P9
P13

Questions:

Is this optimal way to solve the given problem for larger data?
How can I estimate the computational complexity of those operations?
Am I doing here something potentially dangerous or excessive with the collections?
Any other concerns or remarks?

Any feedback would be appreciated.

I always feel odd reviewing code like this, because there is no API. You should really pull out the clustering code into it's own method, with a nice signature, something like:

IEnumerable<IReadOnlyCollection<string>> Cluster(IEnumerable<Person> people);

This will make it reusable (and so testable).

You ask "Am I doing here something potentially dangerous or excessive with the collections?". I'm not entirely sure what you mean... but I think no. Collections are efficient, and it's hard to do anything dangerous in C# by accident. If anything, you should probably be using more powerful collections.

Tuples

What is Tuple<string, List<string>>? What are Item1 and Item2? Give it a meaningful type, with meaningful member names!

public class Person
{
    public Person(string name, IReadOnlyCollection<string> places)
    {
        Name = name;
        Places = places;
    }

    public string Name { get; }
    public IReadOnlyCollection<string> Places { get; }
}

Complexity

Never been much good at complexity... but here's an attempt at answering your second question. Take it with spoonful of salt. Hopefully someone will poke holes in it promptly.

First you need to identify the parameters you care about. Let's say n for the number of people and 'b' number of places. You iterate over pairs of people, which gives you n^2 (just to enumerate the pairs).

Inside that loop you are looking for an intersection between 2 sets of up to b elements, which can be no better than O(b) (that's the case where the hashes turn out perfectly, assuming Intersect converts one of the lists to a HashSet internally). cluster1.AddRange(cluster2.Where(x => !cluster1.Contains(x))) is O(b^2). You ought instead be using HashSets from the outset, which will get the inner working down to something more like O(b) again (i.e. HashSet<T>.UnionWith(HashSet<T>) is kind of just about linear most of the time). ... but then that matching can only happen n times... so it's a separate concern.

Then there is the outer most loop... which I don't want to think about... but in the worst case it will be run n times, giving you a worst-case complexity of O(n*n*n*b + n*n*b*b), or just about O(n*n*n*b) if you use HashSets.

I can't think how the space complexity of your code could be anything other than the input space complexity of O(b + n).

Technically, your printing out at the end has third order time complexity: O(m*k*k) in number of clusters m, and number of places per cluster k. Consider using a StringBuilder or string.Join instead of Aggregate and repeated concatenation (that will make it O(m*k)).

Disjoint Sets

Any problem like this I would solve with disjoint sets, and even a poor implementation should get you O(n*b) time-complexity (max tree-depth is O(n)) on this problem.

The basic idea is that you maintain a table pointers which describe a set of trees, each tree being an independent (disjoint) set. You can follow the pointers from any member of a set to the root member, and by assigning the parent of one root node to the root of another you join the two sets together. You can throw an implementation together in no time, with very little code.

Some very unscientific benchmarking suggests that a somewhat untested disjoint sets implementation I just threw together is a couple of orders of magnitude faster than your implementation (using HashSets and with reduced Pair count, as suggested in Paparazzo's answer) on randomly generated problems. Your implementation is taking over 10seconds on my machine to solve a problem with b=4000, which the disjoint sets solve in a few milliseconds. The disjoint set version seems to be linear in n*b (easier to scale than just b in random problems); yours is taking a while for larger problems larger than n*b=5000, and I wouldn't wish to comment on the experimental time-complexity with these few (noisy) results.

A gist of the disjoint sets implementation and cluster method is provided so that people can find juicy bugs in it: 1 bug fixed so far (2018-06-26)


Lock Using “Interlocked” vs lock Statement (“Monitor”) (Followup) This is a followup to a previous question.

Considering:

Interlocked.CompareExchange generates a memory barrier,
Intended to be used with very fast operations (like generating an
id),
SpinWait starts sleeping in milliseconds after 10 or so spins (and
does some other smart stuff),

What are characteristics (pros & cons) of this code?

public class SpinMutex
{
    const long Locked = 1;
    const long Unlocked = 0;

    long _locked;

    public SpinMutex() { _locked = Unlocked; }

    /*public*/
    void Lock()
    {
        SpinWait.SpinUntil(() => Interlocked.CompareExchange(ref _locked, Locked, Unlocked) == Unlocked);
    }

    /*public*/
    bool Lock(int millisecondsTimeout)
    {
        return SpinWait.SpinUntil(() => Interlocked.CompareExchange(ref _locked, Locked, Unlocked) == Unlocked, millisecondsTimeout);
    }

    /*public*/
    bool Lock(TimeSpan timeout)
    {
        return SpinWait.SpinUntil(() => Interlocked.CompareExchange(ref _locked, Locked, Unlocked) == Unlocked, timeout);
    }

    /*public*/
    void Unlock()
    {
        Interlocked.CompareExchange(ref _locked, Unlocked, Locked);
    }

    public IDisposable EnterScope()
    {
        return new Scope(this);
    }

    public IDisposable EnterScope(int millisecondsTimeout)
    {
        return new Scope(this, millisecondsTimeout);
    }

    class Scope : IDisposable
    {
        SpinMutex _spinMutex;
        int _millisecondsTimeout;
        bool _locked;
        bool _shouldDispose;

        internal Scope(SpinMutex spinMutex, int millisecondsTimeout = -1)
        {
            _spinMutex = spinMutex;
            _millisecondsTimeout = millisecondsTimeout < -1 ? -1 : millisecondsTimeout;
            _locked = false;
            _shouldDispose = true;

            try
            {
                if (_millisecondsTimeout < 0) _spinMutex.Lock();
                else if (!_spinMutex.Lock(_millisecondsTimeout)) throw new TimeoutException();
                else _locked = true;
            }
            catch
            {
                Dispose();
                _shouldDispose = false;
                throw;
            }
        }

        public void Dispose()
        {
            if (!_shouldDispose) return;
            if (_millisecondsTimeout < 0) _spinMutex.Unlock();
            else if (_locked) _spinMutex.Unlock();
        }
    }
}

And would be used like this:

static readonly SpinMutex MySpinMutex = new SpinMutex();

static void Process1()
{
    using (MySpinMutex.EnterScope()) { /* ... */ }
}

static void Process2()
{
    using (MySpinMutex.EnterScope()) { /* ... */ }
}

Instances of SpinMutex can be accessed from different Threads/Tasks safely.

void Unlock()
{
    Interlocked.CompareExchange(ref _locked, Unlocked, Locked);
}

So, if you try to unlock when the lock is not locked, nothing happens? That sounds like a recipe for well-hidden bugs. Instead, unlocking when not locked should throw an exception.

_millisecondsTimeout = millisecondsTimeout < -1 ? -1 : millisecondsTimeout;

Why are you making sure that negative values are changed to -1, when later on you just check whether the timeout is negative?

Anyway, the approach taken by .Net methods like SpinUntil() is that negative values other than -1 throw, so I think you should do that too to be consistent.

if (_millisecondsTimeout < 0) _spinMutex.Lock();
else if (!_spinMutex.Lock(_millisecondsTimeout)) throw new TimeoutException();
else _locked = true;

I don't like having the three branches on the same level here, because logically, they're not. I think this way makes more sense:

if (_millisecondsTimeout < 0)
{
    _spinMutex.Lock();
}
else
{
    if (!_spinMutex.Lock(_millisecondsTimeout)) throw new TimeoutException();
    else _locked = true;
}

Also, what's the purpose of the first if at all. Removing it will work the same:

if (!_spinMutex.Lock(_millisecondsTimeout)) throw new TimeoutException();
else _locked = true;

catch
{
    Dispose();
    _shouldDispose = false;
    throw;
}

Calling Dispose() here makes sense only if the lock gets locked (so TimeoutException wasn't thrown) but then an exception was thrown. But most of the time, such exceptions (e.g. ThreadAbortException) are catastrophic and the whole process is going to go down, so you don't need to care about them much.

_shouldDispose = false;

I don't understand this. If the constructor throws an exception, the caller never gets their hands on the created instance, so they won't be able to call Dispose(). This means that _shouldDispose = false here doesn't make much sense.

On the other hand, calling Dispose() more than once should work (“If an object's Dispose method is called more than once, the object must ignore all calls after the first one.”), but won't, so adding _shouldDispose = false directly into Dispose() would make sense.

I think that _locked should be set always when the lock is locked, not just under some circumstances. That would make understanding your code easier and it would also simplify code in both in the constructor and in Dispose().


Detect how long an HTML button is pressed I recently had the need to detect how long a button is pressed and perform different actions based on that. I found some examples on Stack Overflow, but the ones I looked at showed how to use timeout().

I came up with this. There are probably other ways to solve this. While searching, I found an example using IIFE in JavaScript, which I then used for this tiny example.

HTML:

<button id="button">click</button>

JavaScript:

(function(window, document, undefined){
    'use strict';
    var start;
    var end;
    var delta;
    var button = document.getElementById("button");

    button.addEventListener("mousedown", function(){
        start = new Date();
    });

    button.addEventListener("mouseup", function() {
        end = new Date();
        delta = end - start;
        if (delta > 0 && delta < 500) {
            alert("less than half second:");
        }
        if (delta > 1000) {
            alert("more than a second:");
        }
    });
})(window, document);

500 and 1000 should be constants.

Where you have them now you need to look through to find them in code when you want to change them. I know this is an example, but they're also meaningless. 500 doesn't tell you why half a second matters, but TIMEOUT tells you what the purpose of the number is. Declare your time values at the top of the function with clear names that denote what they're for.


HTML5 Schema and CSS Styling Correct? I've started my personal website with HTML5.
I would like to get it review to see if I am using the correct schema.

I am looking to get feedback about the structure of HTML5 elements. I think I am overdoing some of the things in the code.

html,
body {
  font-family: Verdana, Geneva, Tahoma, sans-serif;
  font-size: 12px;
  padding: 0;
  margin: 0;
}

a {
  cursor: pointer;
}

#container {
  margin: 0 auto;
  width: 1000px;
}

#midcontainer {
  margin: 0 auto;
  width: 1000px;
}

#midcontainer::before {
  clear: both;
}

#midcontainer::after {
  clear: both;
}

header {
  background: #ff4242;
  height: 30px;
  padding: 20px 0;
}

header span {
  color: #fff;
  float: left;
  font-size: 24px;
}

header span.your {
  font-weight: bold;
}

nav {
  line-height: 30px
}

nav ul {
  float: right;
  list-style: none;
  margin: 0;
  padding: 0;
}

nav ul li {
  display: inline;
  margin-left: 20px;
}

nav ul li a {
  color: #fff;
  text-decoration: none;
}

nav ul li a:hover {
  border-bottom: 1px solid #fff;
}

.intro {
  background: #f0f2eb;
  color: #333;
  text-align: center;
  margin-bottom: 50px;
  padding: 100px 50px;
}

.intro h2 {
  font-size: 48px;
}

.intro span {
  font-size: 32px;
  margin-top: -30px;
  margin-bottom: 20px;
  display: block;
  font-weight: bold;
}

.intro button {
  background: #f0f2eb;
  border: 2px solid #ff4242;
  font-size: 16px;
  color: #333;
  padding: 20px 30px;
  text-transform: uppercase;
}

.intro button:hover {
  background: #ff4242;
  border: 2px solid #ff4242;
  color: #fff;
}

.photography,
.code,
.graphicdesign {
  float: left;
  width: 33.3%;
  text-align: center;
}

footer {
  background: #333;
  color: #fff;
  clear: left;
  display: block;
  margin: 20px 0 0 0;
  padding: 20px 40px;
  text-align: center;
}

footer a {
  text-decoration: none;
  color: #fff;
  border-bottom: 2px solid #fff;
  padding-bottom: 3px;
}

footer ul {
  list-style: none;
}

footer ul li {
  display: inline;
  margin-right: 25px;
}

footer ul li a {
  text-decoration: none;
  color: #ff4242;
  border: none;
}

    YOURNAME

Home

About Me

Gallery

Blog

Conact

Who is this guy?

  Dude, myth or mega designer!
  <button>get to know me</button>

photography

Code

Graphic Design

Facebook

Twitter

Youtube

Instagram

Designed by your name

Your code is basically correct, but you might want to look at a few things that have changed with HTML and CSS in the last years:

Web Fonts

font-family: Verdana, Geneva, Tahoma, sans-serif;

In the bad old days you could only use fonts in web pages that were
already installed on the client system.  Because theses pre-installed fonts
differed from operating system to operating system, a list of similar looking
fonts was specified.  Here "Verdana" was typically found on windows machines, "Geneva" typically on MacOS, an "sans-serif" is a wildcard to finally
use any sans serif font, if none of the named fonts are available.

Since about 2008 browsers can load fontssee history of web typography.  Now you can specify exactly
the font you want, and maybe add the wildcard at the end in case anything breaks.
See google fonts for free fonts and for the code you need to load them.

So today you would typically write

font-family: 'Open Sans', sans-serif;

instead of the font list.

Layout

You use "float" to arrange divs side-by-side.

Since Spring 2017 you can use CSS Grid instead.

Use it to lay out the whole page on a grid. You will need fewer HTML tags and can forget about "clearfix".

Responsive Design

The Web has many different output devices.  Even if we just look at
screens, we have big differences in resolution and pixel density.

Your page is geared toward a screen width of 1024px.  On smaller displays parts of your page will only by visibly when scrolling horizontally.  On larger displays you will not use the space available in a meaningful way.

The answer to this is responsive design: start designing your page for a smartphone. Then add different CSS for larger devices using media queries.


Format names to title case So I'm writing a program to format names to title case and display them in alphabetic order.  Any advice please?  And how can i add more methods?

public static void main (String [] args)
{
    //local variables
    string name1;
    string name2;

     myLib = new Library();

     /********************   Start main method  *****************/

     //prompt user for first Name
     System.out.print("Enter First Name : ");
     name1 = Keyboard.readChar();

     //prompt user for second
     System.out.print("Enter Second Name : ");
     name2 = Keyboard.readChar();

     //Format names to Title Case
     name1.replace(0, name1.length(), name1.toString().toLowerCase());
     name2.replace(0, name2.length(), name2.toString().toLowerCase());

     name1.setCharAt(0, Character.toTitleCase(name1.charAt(0)));
     name2.setCharAt(0, Character.toTitleCase(name2.charAt(0)));

     //clear the screen
     myLib.clrscr();

     //Display names in alphabet order
     if (name1.toString().compareTo(name2.toString()) >= 0) {
         System.out.println(name2 + " " + name1);
     } else {
         System.out.println(name1 + " " + name2);
     }

     //pause the screen
     //myLib.pause();

  } //end main method

} //end

Create a List

List<String> al = new ArrayList<String();

and add (you can also use something like while(! stringRead.isEmpty()) {..} )

name = Keyboard.readChar()).toLowerCase();
al.add(name.substring(0, 1).toUpperCase() + name.substring(1));

EDIT after comment

1°) then Sort (the list is 'cloned') and print directly frome the Constructor return This solution is recommended to protect data published in a Web page.

System.out.println(new TreeSet<String>(al).toString());

2°) The List is sorted then printed

Collections.sort(al);
System.out.println(al.toString());


Learning C, basic string reversal function I am starting to write some functions while studying how to program in C.  In this small function I take a string as an argument and print it out in reverse order.

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {

    int aLen = argc;
    char *sWord = argv[aLen - 1];
    char *reversed;

    int sLen = strlen(sWord);
    int i = 0;

    reversed = reversed + sLen;    // offset pointer to the length of string
    while (i <= sLen) {
        if (sWord[i] != '\0') {    // check if character is null-terminator
            *reversed = sWord[i];  // if not, let reversed correct address
        }                          // equal letter.
        i++;
        reversed--;
    }
    printf("%s reversed is:%s\n", sWord, reversed);
    return 0;
}

I was hoping to get some tips on best practice or corrections on any errors.

Your code has a number of issues, the main one being that it doesn't work.

If you want to reverse a string in place then I suggest you write a function just
for that, separate from main.   The function will need a temporary variable
and will, for example:

swap first and last characters
swap 2nd and 2nd-from-last characters
swap 3rd and 3rd-from-last characters
etc

To swap the characters pointed to by a and b, you would do

char temp = *a;
*a = *b;
*b = *temp;

or if you have a pointer and a length:

char temp = a[0];
a[0] = b[len];
b[len] = temp;

So your reversal function needs to contain one of these sequences in a loop
and the loop must arrange a and b to point to the correct places.  For
example, here is a reverse function:

static char* reverse(char *str)
{
    char *s = str;
    char *end = s + strlen(s) - 1;
    for (; s < end; ++s, --end) {
        char ch = *end;
        *end = *s;
        *s = ch;
    }
    return str;
}

Then in main all you do is call the reverse function with the desired
string:

printf("'%s'\n", reverse(argv[1]));

Of course it is best to check that argv[1] exists first (remember that argv[0] is the program name and argc is always greater than or equal to 1):

if (argc == 2) {
    printf("'%s' reversed is ", argv[1]);
    printf("'%s'\n", reverse(argv[1]));
}

Notes:

In your code, aLen and sWord are unnecessary. And reversed is
not initilaised but is then used in

reversed = reversed + sLen;  // See the EDIT below

In the line

int sLen = strlen(sWord);

strlen returns the length as a size_t, not int

EDIT

When you declare a variable local to a function, the compiler sets aside a
space on the stack.  It does not write anything there unless you declare
the initial value for the variable.  So in your code, reserved contains
whatever happens to be at that location on the stack and, as reserved is a
pointer, it therefore points to some unknown (unplanned) location in memory.
If you are unlucky that location will be writeable, your accesses 'work'
and you won't see the problem (or not immediately - in a larger program you
will probably encounter strange behaviour later on while the code is executing
because your accesses have overwritten something important); if you are
lucky and the location is unwritable you will see the problem the first
time you run the program.

The moral is always to initialise variables, just to be safe.  Zero (NULL) is
a good value for pointers.  With C99 you are not restricted to defining them at
the start of a function, so it is often best to define a variable only at the
point where you need it and have a useful value with which to initialise it.


Updating only certain fields on a database row I have data that I want to insert in a database.  Sometime a piece of data is already in the database, so I just want to update the fields that changed.

For example, if I insert these rows one after the other:

id | field1 | field2 | field3
1  | foo    | NULL   | bar
1  | baz    | hello  | NULL

I want to end up with:

id | field1 | field2 | field3
1  | baz    | hello  | bar

I use this query:

INSERT INTO `device` (`device_id`, `model`, `manufacturer`, `version`, `vendor_id`, `osd_name`)
VALUES (....)
ON DUPLICATE KEY UPDATE `version` = IFNULL(VALUES(`version`), `version`), `vendor_id` = IFNULL(VALUES(`vendor_id`), `vendor_id`), `osd_name` = IFNULL(VALUES(`osd_name`), `osd_name`)

Note that not all fields have to be updated. Is this the best way to do it?

I think it is.

What you are asking for is known as UPSERT - a portmanteau of UPDATE and INSERT. Some databases support UPSERT intrinsically, but some don't. A quick search for "MySQL UPSERT" suggests that MySQL does not support an UPSERT keyword or the concept directly. However, as you discovered, the ON DUPLICATE KEY construct will simulate it.

That seems the best way to do it in MySQL. (In SQL Server you would probably use MERGE.)


Optimizing PHP script fetching entire HTML pages The following script should get links which are stored in a text file (line by line), then put them into an array and finally scan each links' source code for a certain line. If this line is found, it will be pasted into a CSV file.

It works fine so far, but it takes ages to finish, since each link is 'opened' and the complete source code for that link is scanned for this specific line.

I'm looking for ideas on how to optimize the code to run faster.

Here is my code:

$filename = "products.txt";
$writecsv = "notavailable.csv";
global $products;

$ch = curl_init();
curl_setopt($ch, CURLOPT_COOKIEJAR, "/tmp/abCk.txt");
curl_setopt($ch, CURLOPT_URL,"https://www.websitegoeshere.com");
curl_setopt($ch, CURLOPT_POST, 1);
curl_setopt($ch, CURLOPT_POSTFIELDS, "Login=USERNAME&Password=PASSWORD");

ob_start();      // prevent any output
curl_exec ($ch); // execute the curl command
ob_end_clean();  // stop preventing output

curl_close ($ch);
unset($ch);

$ch = curl_init();
curl_setopt($ch, CURLOPT_RETURNTRANSFER,1);
curl_setopt($ch, CURLOPT_COOKIEFILE, "/tmp/abCk.txt");

// Open the file
$fp = @fopen($filename, 'r') or die("products.txt not found");

// Add each line to an array
if ($fp) {
   $products = explode("\n", fread($fp, filesize($filename)));
}

fclose($fp);

$fpcsv = fopen($writecsv, 'w') or die("notavailable.csv not found");

foreach($products as $key => $val) {
    curl_setopt($ch, CURLOPT_URL,$val);
    $buf2 = curl_exec ($ch);
    $html = htmlentities($buf2);
    if (strpos($html, "/extension/silver.project/design/sc_base/images/available_yes.gif") !== false) {
        fputcsv($fpcsv, "available");
    } else {
        fputcsv($fpcsv, "not available");
    }
}

fclose($fpcsv);

curl_close ($ch);
echo "csv written successfully."

Any help is really welcomed. Thanks in advance!

Performing this task in parallel would help greatly although PHP is not the best language to do so in.

I would do so by spawning PHP processes by POSTing to other PHP scripts (asynchronously), possibly posting to them the links they should get. You would need to store whether the line is available or not in a database, I would use SQLite in this case (it doesn't need a server to be setup).

So a possible setup could look something like:

Master Process: Splits the main link file into n parts then POSTs the parts to the child pages. It would need to know when the child processes are finished, it could do so by having a polling loop that checks if the number of rows in the database is equal to the number of links, you would need to make sure you put in a sleep function so it doesn't poll too often. When the child processes are done and the polling breaks out, you could then take the data in the database and convert it to CSV.

Child Processes: This page receives a set of links via POST, it then goes through each one checking if it contains the string and marking the result down in the database.

I would not use this for production code, PHP is not made for this and there are lots of things that could go wrong. If it was possible I would do this sort of thing in languages with built in parallelism such as Golang or Clojure.


Python app-level document/record locking (eg. for MongoDB) MongoDB does not provide means to lock a document (like SELECT FOR UPDATE in RDBMS).

There is a recommended approach to Isolate Sequence of Operations, which is sometimes called optimistic locking, but there are scenarios when this approach seems to be overly complicated or even inefficient (that is why pessimistic locks are still in use).

Task

I am trying to implement generic (can be used with various databases) document (or record) locking at application level. Assuming I have only one application working with collection (or table). And my application is multi-threaded.

Usage scenario:

with DocumentLock(doc_id):
  # make sure no other thread interferes
  doc=db.doc_collection.find_one(doc_id)
  ... # analyse and update the document
  db.doc_collection.save(doc)

Solution

Here is my DocumentLock class:

class DocumentLock(object):

  _lock=RLock() # protects access to _locks dictionary
  _locks=WeakValueDictionary()

  def __init__(self, doc_id):
    self.doc_id=doc_id

  def __enter__(self):
    with self._lock:
      self.lock=self._locks.get(self.doc_id)
      if self.lock is None:
        self._locks[self.doc_id]=self.lock=RLock()
    self.lock.acquire()

  def __exit__(self, exc_type, exc_value, traceback):
    self.lock.release()
    self.lock=None # make available for garbage collection

So basically I have a dictionary of RLocks, one RLock per accessed document. I use weak references to get rid of unused locks.

DocumentLock can be subclassed for every collection (or table) that needs record locking.

Question

This all seems to work (although not tested under concurrency) but I am publishing it here for review and advise. Do you see any weaknesses or mistakes in this code? Is there a better approach to do this kind of things in Python?

The above code will fail with multiple worker nodes (or processes).
To achieve atomic find-and-update, mongodb provides native solution (findOneAndUpdate, findAndModify, updateOne, updateMany).


Finding ideal sport based on weighted attributes The program takes weighted strengths of the human body (arms/legs/core/mind) based on the required attributes for a sport, then tells you the resulting sport. The program is obviously really ugly. Is there a way I could use dictionaries and a lambda function to find a max instead? This latter part is what I don't know how to do.

print("Welcome to What's your ideal sport! Answer the following questions on a scale from 1-10.")

leg_strength = int(input("How good is your leg strength / speed?"))
arm_strength = int(input("How good is your arm strength?"))
core_strength = int(input("How strong are your abs?"))
mental_strength = int(input("How intelligent are you?"))
reaction_time = int(input("How fast are your reactions?"))

# Sports are: Soccer, Football, Tennis, Swimming, Basketball, Track, Gymnastics, and Chess.

sports = []

soccer = (arm_strength*5) + (reaction_time*2) + (mental_strength) + (arm_strength) + (core_strength)
sports.append(soccer)
chess = mental_strength * 10
sports.append(chess)
football = (arm_strength*4) + (core_strength*3) + (leg_strength*3)
sports.append(football)
tennis = (reaction_time*3) + (arm_strength*4) + (core_strength*2) + (mental_strength)
sports.append(tennis)
swimming = reaction_time + (core_strength*3) + (arm_strength*3) + (leg_strength*3)
sports.append(swimming)
basketball = (leg_strength*2) + (arm_strength*5) + (mental_strength*2) + core_strength
sports.append(basketball)
track = (leg_strength*6) + (arm_strength*2) + (reaction_time) + (mental_strength)
sports.append(track)
gymnastics = (leg_strength*3) + (arm_strength*3) + (core_strength*3) + mental_strength
sports.append(gymnastics)

print(sports)

best = max(sports)
sports.index(best)

indices = []

for sport in sports:
    if sport == best:
        indices.append(sports.index(sport))

result = []

for index in indices:
    if index == 0:
        result.append("Soccer")
    elif index == 1:
        result.append("Chess")
    elif index == 2:
        result.append("Football")
    elif index == 3:
        result.append("Tennis")
    elif index == 4:
        result.append("Swimming")
    elif index == 5:
        result.append("Basketball")
    elif index == 6:
        result.append("Track")
    elif index == 7:
        result.append("Gymnastics")

    print("Your best olympic sport(s) are: {0}.".format(result))

Perhaps you could represent the weightings of each trait as a tuple of multipliers, which are applied to the input values.

Here you have a list of weightings, to which it's trivial to add entries.

from operator import itemgetter, mul
from itertools import groupby, starmap

print("Welcome to What's your ideal sport! "
      "Answer the following questions on a scale from 1-10.")

traits = ('leg', 'arm', 'core', 'mental', 'reaction')

questions = ["How good is your leg strength / speed? ",
             "How good is your arm strength? ",
             "How strong are your abs? ",
             "How intelligent are you? ",
             "How fast are your reactions? "]

responses = [int(input(q)) for q in questions]

print("weights: ")
for t, a in zip(traits, responses):
    print("%s strength = %d" % (t, a))

weightings = [
    # sport, (legs, arms, core, mental, reactions)
    ('soccer',     (5, 2, 1, 1, 1)),
    ('chess',      (1, 1, 1, 10, 1)),
    ('football',   (3, 4, 3, 1, 1)),
    ('tennis',     (1, 4, 2, 1, 3)),
    ('swimming',   (3, 3, 3, 1, 1)),
    ('basketball', (2, 5, 1, 2, 1)),
    ('track',      (6, 2, 1, 1, 1)),
    ('gymnastics', (3, 3, 3, 1, 1))
]

def calcscore(weights, answers):
    ''' calculate the score for a given set of weights and answers, by
        multiplying each answer by the matching weight and adding them
        all together.
    '''
    return sum(weight * answer for (weight, answer) in zip(weights, answers))
    # more esoteric implementation.
    #return sum(starmap(mul, zip(weights, answers)))

# results prior to sorting
result = [(name, calcscore(traits, responses)) for (name, traits) in weightings]

# sorted results prior ordered by score descending
sresult = sorted(result, key=itemgetter(1), reverse=True)

# group and take first group. It should never be empty.
grouper, group = next(groupby(sresult, key=itemgetter(1)))

print('results:')
print("with score %d" % grouper)
print("we have the sports")
for name, score in group:
    print('%s - %d' % (name, score))

Some of the values in the weightings should probably be zero rather than one. To represent an absence of this trait from the calculation. It will be straightforward for the op to modify these themselves. I am demonstrating the concept.


Calculating golf score against course par This PHP script will translate shots on 18 holes to a total under par or E which is 0.

$course = array(0, 4, 5, 4, 3, 5, 3, 4, 4, 4, 4, 4, 4, 4, 3, 5, 3, 4, 5);

if ($totalpar == 0) {
    $score = 'E';
    $played = 0;
} else {
if(!empty($h1)) {
 $h1score = $course[1] - $h1;
} else {
 $h1score = 0;
 }
if (!empty($h2)) {
 $h2score = $course[2]- $h2;
} else {
 $h2score = 0;
 }
if (!empty($h3)) {
 $h3score = $course[3] - $h3;
} else {
 $h3score = 0;
 }
if (!empty($h4)) {
 $h4score = $course[4] - $h4;
} else {
 $h4score = 0;
 }
if (!empty($h5)) {
 $h5score = $course[5] - $h5;
} else {
 $h5score = 0;
 }
if (!empty($h6)) {
 $h6score = $course[6] - $h6;
} else {
 $h6score = 0;
 }
if (!empty($h7)) {
 $h7score = $course[7] - $h7;
} else {
 $h7score = 0;
 }
if (!empty($h8)) {
 $h8score = $course[8] - $h8;
} else {
 $h8score = 0;
 }
if (!empty($h9)) {
 $h9score = $course[9] - $h9;
} else {
 $h9score = 0;
 }
if (!empty($h10)) {
 $h10score = $course[10] - $h10;
} else {
 $h10score = 0;
 }
if (!empty($h11)) {
 $h11score = $course[11] - $h11;
} else {
 $h11score = 0;
 }
if (!empty($h12)) {
 $h12score = $course[12] - $h12;
} else {
 $h12score = 0;
 }
if(!empty($h13)) {
 $h13score = $course[13] - $h13;
} else {
 $h13score = 0;
 }
if(!empty($h14)) {
 $h14score = $course[14] - $h14;
} else {
 $h14score = 0;
 }
if (!empty($h15)) {
 $h15score = $course[15] - $h15;
} else {
 $h15score = 0;
 }
 if(!empty($h16)) {
 $h16score = $course[16] - $h16;
}else {
 $h16score = 0;
 }
if(!empty($h17)) {
 $h17score = $course[17] - $h17;
}else {
 $h17score = 0;
 }

if(!empty($h18)) {
 $h18score = $course[18] - $h18;
}else {
 $h18score = 0;
 }
}

$scoresum = ($h1score + $h2score + $h3score + $h4score + $h5score + $h6score + $h7score + $h8score + $h9score + $h10score + $h11score + $h12score + $h13score + $h14score + $h15score + $h16score + $h17score + $h18score) * -1;

if ($scoresum != 0) {
    $score = $scoresum;
}
else {
    $score = 'E';
}

The big thing worth mentioning here is:  Use an array for your scores.

The instant you do that, the code size shrinks dramatically.

$course = array(0, 4, 5, 4, 3, 5, 3, 4, 4, 4, 4, 4, 4, 4, 3, 5, 3, 4, 5);
$scores = array();

// $shots is your array of scores.  $shots[1] is the first hole, $shots[2] the second,
// etc.  If you remove the 0 at the beginning of `$course`, then $scores[0] will be
// the first, $scores[1] the second, etc, which is how arrays often look.  But with
// the zero, you can use the hole number as array index -- which might be more useful
// if these numbers are coming from an HTML form.

foreach ($course as $hole => $par) {
    if (!empty($shots[$hole])) {
        $scores[$hole] = $par - $shots[$hole];
    }
}

$scoresum = array_sum($scores);

if ($scoresum != 0) {
    $score = $scoresum;
}
else {
    $score = 'E';
}

But you could do even better than that, if you don't need those intermediate scores.

$course = array(0, 4, 5, 4, 3, 5, 3, 4, 4, 4, 4, 4, 4, 4, 3, 5, 3, 4, 5);
$score = 0;

foreach ($shots as $hole => $total) {
    if (!empty($total)) {
        $score += $course[$hole] - $total;
    }
}

if (empty($score)) $score = 'E';

And because this seems uncommon knowledge, and will simplify your life if these values are indeed from a form, you can get PHP to build your array for you by giving your inputs arrayish names.  Like so:

<form>
    <input type="text" name="shots[1]">
    <input type="text" name="shots[2]">
    <input type="text" name="shots[3]">
    <input type="text" name="shots[4]">
    <input type="text" name="shots[5]">
 </form>

(You can even leave out the index, if you don't mind the auto-number indexes PHP does.)

When this form is submitted, $_POST['shots'] will be an array of all the inputs.  Do something like:

$shots = array_map('intval', $_POST['shots']);

and you have an array containing the score entered for each hole (or 0 if the entered value didn't make sense as a number).


Bitcoin address validator in C Here is a Bitcoin address validator I am looking to have reviewed in C.  Normally I would have the enum and function prototypes declared in a header file, but I decided for the purpose of this question to integrate them into one for easy copying and compilation.

/**
 * @file bitcoin.c
 * @brief Bitcoin address validation
 */

#include <stdio.h>
#include <string.h>
#include <openssl/sha.h>

typedef enum {VALID, BAD_CHAR, BAD_LENGTH, BAD_DIGEST} BitcoinAddressState;

/**
 * @fn BitcoinAddressState unbase58(const char *s, unsigned char *out)
 * @brief Takes a base58 encoded address and decodes it into the receiver. Errors are returned if the argument is not valid base58 or if the decoded value does not fit in the 25 byte address.
 * @param addr The Bitcoin address
 * @param out The receiver of the decoded address
 * @return The state of decoding the Bitcoin address
 */
BitcoinAddressState unbase58(const char *addr, unsigned char *out)
{
    /* A bitcoin address uses a base58 encoding, which uses an alphabet of the characters 0 .. 9, A ..Z, a .. z, but without the four characters 0, O, I and l. */
    const char *tmpl = "123456789"
                       "ABCDEFGHJKLMNPQRSTUVWXYZ"
                       "abcdefghijkmnopqrstuvwxyz";
    const char *p;

    memset(out, 0, 25);
    for (int i = 0; addr[i]; ++i)
    {
        if (!(p = strchr(tmpl, addr[i]))) return BAD_CHAR;

        size_t c = p - tmpl;
        for (int j = 25; --j; )
        {
            c += 58 * out[j];
            out[j] = c % 256;
            c /= 256;
        }
        if (c) return BAD_LENGTH;
    }
    return VALID;
}

/**
 * @fn BitcoinAddressState validateAddress(const char *s)
 * @brief Takes a Bitcoin address as argument, and checks whether or not the address is valid.
 * @param addr The Bitcoin address
 * @return The state of the Bitcoin address
 */
BitcoinAddressState validateAddress(const char *addr)
{
    unsigned char dec[32];
    unsigned char d1[SHA256_DIGEST_LENGTH];
    unsigned char d2[SHA256_DIGEST_LENGTH];
    BitcoinAddressState val = unbase58(addr, dec);

    if (val) return val;

    SHA256(SHA256(dec, 21, d1), SHA256_DIGEST_LENGTH, d2);

    if (memcmp(dec + 21, d2, 4)) return BAD_DIGEST;

    return VALID;
}

int main (void) {
    const char *addresses[] =
    {
        "1EYDqUKuLKF9di1pSEtEfNA8pj2CgL7Wne", // my actual Bitcoin wallet address
        "1EYDqUKuLKF9di1pSEtEfNA8pj3CgL7Wne", // bad digest
        "1EYDqUKuLKF9di1pSEtEfNA8pj2CgL0Wne", // bad char
        "1EYDqUKuLKF9di1pSEtEfNA8pj2cgL7Wnef", // bad length
        0
    };
    for (int i = 0; addresses[i]; ++i)
    {
        printf("%s: ", addresses[i]);
        switch (validateAddress(addresses[i]))
        {
            case VALID:
                puts("Okay");
                break;
            case BAD_CHAR:
                puts("Invalid character in address");
                break;
            case BAD_LENGTH:
                puts("Address length is incorrect");
                break;
            case BAD_DIGEST:
                puts("Bad digest");
                break;
            default:
                puts("An unknown error occurred");
                break;
        }
    }
}

It would be nice to include a link to an authoritative reference. Until then, no comment on the algorithm compliance is possible.
Instead of switch I'd rather have a table of strings indexed by BitcoinAddressState values.
In C, main must return a value explicitly.


Feedback On How I Can Clean Up My Code I am new to coding for ~1 week. I know that I learn best by doing, and so I decided to work on a small and simple project while utilizing various online sources to learn as I go.
Anyway, I decided to write a little program that asks the user to input their age and then prompts the user to enter an age they wish to be while providing them with the difference and a few little exceptions along the way.
Since I am still new and am learning on my own, I decided to reach out to this forum and see if I can get any suggestive feedback on how I can improve my code and learn some new techniques. Thank you!
Points of interest:

I have it so the code loops back until integers are inputted.

The program can be recalled by the user to enter different values.

I am still working on making it so that negative values can not be inputted.

The Code:
# This program will prompt you to state your age and then will proceed to
# calculate how long till __ age

# Introduction
print("Hello. ")

# Defining Functions
def main():
    while True:
        try:
            myAge = int(input("Please enter your age: "))
        except ValueError:
            print("I'm sorry, please enter your age as a numeric value.")
            continue
        else:
            break

    def secondV():
        while True:
            try:
                global desiredAge
                desiredAge = int(input())
                print("Do you wish to be " + str(desiredAge) + "?")
                choose()
            except ValueError:
                print("Please enter a numeric value.")
                continue
            else:
                break

    def desiredFuture():
        while True:
            try:
                global desiredAge
                desiredAge = int(input())
                while True:
                    if desiredAge < myAge:
                        print(
                            "Silly, time does not move backwards. Learn how to embrace the future, not fear it.")
                        print('Please input an age you wish to be in the FUTURE now...')
                        desiredFuture()
                        break
                    if desiredAge == myAge:
                        print("You are already " + str(desiredAge))
                        break
                    else:
                        print("Do you wish to be " + str(desiredAge) + "?")
                        choose()
                        break
            except ValueError:
                print("Please enter a numeric value.")
                continue
            else:
                break

    def choose():
        global yourWish
        yourWish = input()
        while yourWish.lower() == ("yes" or "y"):
            print("Okay... calculating...")
            import time
            time.sleep(1)
            print()
            print("To be " + str(desiredAge) + ", you would have to wait " + str(desiredAge - myAge) + " years. ")
            print()
            reDo()
            break
        else:
            print("Erm... please input your desired age now:")
            secondV()

    def reDo():
        print('Would you like to try again?')
        runBack = input()
        while True:
            if runBack.lower() in {'y', 'yes'}:
                print()
                main()
            else:
                print("Okay... Goodbye!")
                break

    print("You are " + str(myAge) + ".")
    print("What is your desired age? ")
    desiredFuture()
    choose()
    print()

main()

You can try this:
import time, sys
# This program will prompt you to state your age and then will proceed to
# calculate how long till __ age

# Introduction
print("Hello. ")

# Defining Functions
def main():
    while True:
        try:
            myAge = int(input("Please enter your age: "))
        except ValueError:
            print("I'm sorry, please enter your age as a numeric value.")
            continue
        break

    def secondV():
        while True:
            try:
                global desiredAge
                desiredAge = int(input())
                print(f"Do you wish to be {desiredAge}?")
                choose()
            except ValueError:
                print("Please enter a numeric value.")
                continue
            break

    def desiredFuture():
        while True:
            try:
                global desiredAge
                desiredAge = int(input())
                while True:
                    if desiredAge < myAge:
                        print("Silly, time does not move backwards. Learn how to embrace the future, not fear it.")
                        print('Please input an age you wish to be in the FUTURE now...')
                        desiredFuture()
                        break
                    if desiredAge == myAge:
                        print(f"You are already {desiredAge}")
                        break
                    else:
                        print(f"Do you wish to be {desiredAge}?")
                        choose()
                        break
            except ValueError:
                print("Please enter a numeric value.")
                continue
            break

    def choose():
        global yourWish
        yourWish = input()
        while yourWish.lower() == ("yes" or "y"):
            print("Okay... calculating...")
            time.sleep(1)
            print()
            print(f"To be {desiredAge} you would have to wait {desiredAge - myAge} years.")
            print()
            reDo()
            break
        else:
            print("Erm... please input your desired age now:")
            secondV()

    def reDo():
        print('Would you like to try again?')
        runBack = input()
        while True:
            if runBack.lower() in {'y', 'yes'}:
                print()
                main()
            else:
                print("Okay... Goodbye!")
                sys.exit("goodbye")
                break

    print(f"You are {myAge}.")
    print("What is your desired age? ")
    desiredFuture()
    choose()
    print()

main()

Use f strings instead of + it's more convenient.
And in the try except, you can just do break at the end, not put it in else. And it doesn't exit, so you can import sys and use sys.exit()
And do import time at the first line.