Slow image generation I build a Tower of Hanoi solver which print the solution as an image

It works as expected but generating the image is relatively slow compared to the time to calculate the answer.

Here is the code:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import argparse
from PIL import Image

def hanoi(disks, source, helper, target, steps):
    if disks > 0:
        hanoi(disks - 1, source, target, helper, steps)
        target.append(source.pop())
        steps.append([SOURCE[:], HELPER[:], TARGET[:]])
        hanoi(disks - 1, helper, source, target, steps)

def save_image(name):
    print('\nSaving image {}.png'.format(name))
    data = []
    peg = args.disks * 2
    cells = peg * 3 + 40  # 40 is to put some spaces between pegs and the border
    for step in steps:
        for _ in range(5):  # White space
            data.append([1 for _ in range(cells)])

        src = step[0]
        hlp = step[1]
        trg = step[2]
        size = max(len(src), len(hlp), len(trg))
        for _ in range(size - len(src)):
            src.append(0)
        for _ in range(size - len(hlp)):
            hlp.append(0)
        for _ in range(size - len(trg)):
            trg.append(0)
        src.reverse()
        hlp.reverse()
        trg.reverse()

        for s, h, t in zip(src, hlp, trg):
            blanksrc = peg - 2 * s
            blankhlp = peg - 2 * h
            blanktrg = peg - 2 * t
            row = [1 for _ in range(10)]
            row += [1 for _ in range(blanksrc // 2)]
            row += [0 for _ in range(s * 2)]
            row += [1 for _ in range(blanksrc // 2)]
            row += [1 for _ in range(10)]
            row += [1 for _ in range(blankhlp // 2)]
            row += [0 for _ in range(h * 2)]
            row += [1 for _ in range(blankhlp // 2)]
            row += [1 for _ in range(10)]
            row += [1 for _ in range(blanktrg // 2)]
            row += [0 for _ in range(t * 2)]
            row += [1 for _ in range(blanktrg // 2)]
            row += [1 for _ in range(10)]
            data.append(row)

        for _ in range(5):  # White space
            data.append([1 for _ in range(cells)])
        data.append([0 for _ in range(cells)])  # Black line to separate steps

    da = [bit for row in data for bit in row]
    image = Image.new('1', (cells, len(data)))
    image.putdata(da)
    image.save('{}.png'.format(name))

if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('-d', '--disks', type=int, default=4,
                        help='Number of disks, default 4')
    parser.add_argument('-f', '--filename', help='Filename', required=True)
    args = parser.parse_args()

    if not args.disks > 0:
        raise ValueError('There must be at least one disk')

    SOURCE = list(reversed(range(1, args.disks + 1)))
    TARGET = []
    HELPER = []
    steps = [[SOURCE[:], HELPER[:], TARGET[:]]]

    hanoi(args.disks, SOURCE, HELPER, TARGET, steps)

    save_image(args.filename)

As I add more disks in the problem, compared to the computation of the answer, the time taken to generate the image is longer and longer.

How can I make it faster and why it is so slow?

Like I said before, the reason why this takes a lot of time is because the number of steps is proportional to the square of the number of disks.

But there are some other improvements to be made to this code.

range

list(reversed(range(1, args.disks + 1))) can be done more easily as list(range(disks, 0, -1))

Global variables

Your image saving algorithm uses a lot of global scope (args.filename, steps,...), and with the src.reverce() even modifies these global variables, which is a sure way to introduce difficult to find bugs. If your function needs those parameters, pass them as arguments, and certainly don't change them.

You can prevent SOURCE, HELPER, TARGET to need in global scope, by passing these along in a dictionary. You can also use a namedtuple:

source = list(range(disks, 0, -1))
target = list()
helper = list()
state = dict(
    source=source,
    target=target,
    helper=helper
)
hanoi_gen(disks, source, helper, target, state)

Variable naming

I had to look really well at the code to find out what certain variables were. cells for example is the width of the image, peg is the maximum with of a peg etc. Name your variables clearly. s, h, t in zip(src, hlp, trg) is another example that can do with better names.

Immutable variables

You use lists throughout your code. The advantage of lists is that they are mutable, but this is also the disadvantage. To make sure other code doesn't inadvertently change your data, use immutable containers like tuple where appropriate. So instead of SOURCE[:], I used tuple(...).

Generator

Instead of instantiating all those lists at the same time, you can work with generators:

def hanoi_gen(disks, source, helper, target, state):
    if disks:
        yield from hanoi_gen(disks - 1, source, target, helper, state)
        target.append(source.pop())
        yield tuple(state['source']), tuple(state['target']), tuple(state['helper'])
        yield from hanoi_gen(disks - 1, helper, source, target, state)

def solve_tower(disks):
    source = list(range(disks, 0, -1))
    target = list()
    helper = list()
    yield tuple(source), tuple(target), tuple(helper)
    state = dict(
        source=source,
        target=target,
        helper=helper,
    )
    yield from hanoi_gen(disks, source, helper, target, state)

steps = tuple(solve_tower(2))
assert steps == (
    ((2, 1), (), ()),
    ((2,), (), (1,)),
    ((), (2,), (1,)),
    ((), (2, 1), ()),
)

Magic numbers

There are some magic numbers in your code, 10, 40, 5, ...

Better is to extract global constants from this:

BUFFER_PEG = 10
LINE_WIDTH = 1
BUFFER_STEP = 5
WHITE = 1
BLACK = 0

And use them like:

image_width = disks * 2 * 3 + 4 * BUFFER_PEG

BLACK and WHITE can also be done with an enum.IntEnum:

from enum import IntEnum
class Color(IntEnum):
    BLACK = 0
    WHITE = 1

DRY

Compartmentalize!

There is a lot of repeated code, which makes this hard to maintain and test:

from itertools import repeat

def whitespace(width, image_width):
    return repeat(Color.WHITE, width * image_width)

def line(width, image_width):
    return repeat(Color.BLACK, width * image_width)

Create easy to use generators to add whitespace or black lines.

Pad the disk

def pad_disk(disk_width, num_disks):
    blank_width = num_disks - disk_width
    yield from repeat(Color.WHITE, blank_width)
    yield from repeat(Color.BLACK, disk_width * 2)
    yield from repeat(Color.WHITE, blank_width)

Centrally pads a disk to twice the number of disks in play.
This can be easily tested: the portion of a disk of width 1 in a stack of 4 disks:

assert tuple(pad_disk(1, num_disks=4)) == (1, 1, 1, 0, 0, 1, 1, 1)

Format a row

def buffer_peg():
    return repeat(Color.WHITE, BUFFER_PEG)

def format_row(disks, num_disks):
    yield from buffer_peg()
    for disk_width in disks:
        yield from pad_disk(disk_width, num_disks)
        yield from buffer_peg()

This can be easily tested like this:

row = [2, 0, 1]
num_disks = 4
assert tuple(format_row(row, num_disks)) == tuple(chain(
    buffer_peg(),
    (1, 1, 0, 0, 0, 0, 1, 1,),
    buffer_peg(),
    (1, 1, 1, 1, 1, 1, 1, 1,),
    buffer_peg(),
    (1, 1, 1, 0, 0, 1, 1, 1,),
    buffer_peg(),
))

Format individual steps

Here, I use a small helper function to reverse the peg, and pad it with 0s:

def pad_left_reverse(peg, size, fillvalue=0):
    yield from repeat(fillvalue, size - len(peg))
    yield from reversed(peg)

Then all of this:

src = step[0]
hlp = step[1]
trg = step[2]
size = max(len(src), len(hlp), len(trg))
for _ in range(size - len(src)):
    src.append(0)
for _ in range(size - len(hlp)):
    hlp.append(0)
for _ in range(size - len(trg)):
    trg.append(0)
src.reverse()
hlp.reverse()
trg.reverse()

Can be replaced with:

def format_step(step, num_disks):
    pegs = map(
        lambda peg: pad_left_reverse(peg, num_disks, fillvalue=Color.WHITE),
        step
    )

And on the plus-side, this doesn't reverse the original input.

I replaced the size = max(len(src), len(hlp), len(trg)) with the number of disks, to keep all the steps equally high. If you can live with the uneven heights, size = len(max(step, key=len)) is an alternative formulation.

    for row in zip(*pegs):
        # print(row)
        yield from format_row(row, peg_width)

Replaces the next 20 lines.

step = [2, 1], [5,4,3], []
num_disks = 5
step_data = list(format_step(step, num_disks))

Outputs something like:

1111111111111111111111111111111100000011111111111111111111111111111111
1111111111111100111111111111111000000001111111111111111111111111111111
1111111111111000011111111111110000000000111111111111111111111111111111

Format the steps

def format_steps(steps, image_width, num_disks):
    for step in steps:
        yield from whitespace(BUFFER_STEP, image_width)
        yield from format_step(step, num_disks)
        yield from whitespace(BUFFER_STEP, image_width)
        yield from line(LINE_WIDTH, image_width)

This speaks for itself.

Context managers

If you open resources that need closing afterwards, like a file or a PIL.Image, use a with-statement.

The main

if __name__ == '__main__':
    num_disks = 5
    steps = solve_tower(num_disks)
    image_width = num_disks * 2 * 3 + 4 * BUFFER_PEG
    data = list(format_steps(steps, image_width, num_disks))
    with Image.new('1', (image_width, len(data) // image_width)) as image:
        image.putdata(data)
        name = 'my_hanoi.png'
        image.save(name)

All-in-all this code is slightly longer than your code, and will not necessarily be much faster, it is a lot clearer for me, and a lot more parts can be individually tested.

The full code can be found here, and some tests here.


Implementing Multi Producer Multi Consumer Simple Thread Safe Class I am learning C# and in the process I am trying to implement a multi producer consumer thread safe class. Can you please code review and point me to any mistakes I have made and improvements I can make? I understand there would be libraries and other thread safe queue objects which would provide me the functionality which I am trying to implement, but the very reason I am doing this myself is to learn how threads and thread safe queues are coded and managed. My idea is to achieve maybe an under-optimized but correctly working code.
//simple thread safe many producer many consumer class
class ProducerConsumer<Task>
{
    public delegate void ConsumerCallback(Task t);

    protected bool keepRunning = false;
    protected Queue<Task> taskQueue = null;
    protected Thread[] consumerThreads = null;
    protected ConsumerCallback clientConsumerMethodCB = null;

    public ProducerConsumer(ConsumerCallback clientConsumerMethod, int consumerThreadsCount)
    {
        keepRunning = true;
        consumerThreads = new Thread[consumerThreadsCount];
        for (int i = 0; i < consumerThreadsCount; i++)
        {
            consumerThreads[i] = new Thread(ConsumerThreadFunction);
        }

        for (int i = 0; i < consumerThreadsCount; i++)
        {
            consumerThreads[i].Start();
        }

        taskQueue = new Queue<Task>();
        clientConsumerMethodCB = clientConsumerMethod;
    }

    public void Produce(Task t)
    {
        lock (taskQueue)
        {
            taskQueue.Enqueue(t);
        }

        Monitor.PulseAll(taskQueue);
    }

    protected void ConsumerThreadFunction()
    {
        Queue<Task> holdTaskQueueItem = new Queue<Task>();
        while (keepRunning)
        {
            while (taskQueue.Count <= 0)
            {
                Monitor.Wait(taskQueue);
            }

            lock (taskQueue)
            {
                if(taskQueue.Count > 0)
                {
                    holdTaskQueueItem.Enqueue(taskQueue.Dequeue());
                }
            }

            if(holdTaskQueueItem.Count > 0)
            {
                clientConsumerMethodCB?.Invoke(holdTaskQueueItem.Dequeue());
            }
        }
    }
}

You have entered in the realm of concurrency. So there will be one or more functions which are competing to be executed. In other words there is no guarantee that your code will run in parallel.
If there is enough executor (CPU cores) then the runtime might schedule several threads to different cores. If there is not sufficient resource to be utilized then scheduler might use context switching.
Context switching will execute one portion of T1 and then it suspends T1 in order to avoid thread starvation (a single thread consumes all the available resources, while other threads remain idle). One portion of T2 is executed then it will be suspended. Now scheduler goes back to T1 to resume (hopefully finish) its current function.
These concepts are crucial to understand because these can cause strange behaviours for those that are used to program in a single threaded environment. Let me share with you a simple example:
Example

Let's suppose there is one item in the queue
Also let's assume that there are two consumers (T1 and T2) and they are both checking queue's length before they try to dequeue
So T1 and T2 are at the same line of where they are checking the queue's length
Scheduler suspends T1 after it successful checked the queue length
T2 dequeues the item from the queue
Scheduler resumes T1, which is in that belief that the queue has an item in it (which is not true, because T2 has already dequeued that)
T1 tries to dequeue item from the queue but it will fail because it could not get data from an empty queue

The problem here is that the check and the dequeue functionalities are not treated as atomic. If they were treated as atomic then T1 could not be suspended (by the scheduler or by the GC) between the two queue method calls.

Back to your code, there are several ways to improve it. (I'll respect your intent to learn so I will not suggest alternatives that are already done this)

Please do not use Task for the generic parameter name. It is a well-known structure in the .NET world. Please prefer either Job or Computation or what so ever.
As I can see you would like to use the keepRunning for signaling (either for cancellation or for completion). Unfortunately it is declared as false then set to true in the initialization phase and then it is never modified.
For locking the best practice is to introduce a private static readonly object lockObject = new object(); to avoid accidental exposure of your lock object. In your case the queue is protected, which means in a derived class it could be exposed publicly and a consumer of that derived class can add an extra lock for that. In that case the lock is out of your control.
Please prefer TryDequeue over Count check and Dequeue.
Please consider to use ConcurrentQueue or Synchronized Queue to avoid explicit locking.
5.1) As always measure implementations with different workloads, ConcurrentQueue vs Queue performance
According to my understanding holdTaskQueueItem will hold either one or zero item in it. A single Task or (Job/Computation) variable would be sufficient
Whenever you allow to your consumer to pass any function (in your case ConcumerCallback) then be very-very careful. What if it runs for minutes? What if it deadlocks because it also contains a lock inside it?


Adding, removing, and changing user names and passwords in .htpasswd with PHP Here is some code I wrote to add, remove, and change user names and passwords in .htpasswd with PHP:
function adduser($user, $pass) {

    try {

        $htpasswd = '.htpasswd';

        //$hash = '{SHA}'.crypt($pass, base64_encode($pass));

        $hash = crypt_apr1_md5($pass); //APR1-MD5

        $contents = $user . ':' . $hash;

        $lines = explode(PHP_EOL, file_get_contents($htpasswd)); // get .htpasswd

        print('
input:

'.print_r(implode(PHP_EOL, $lines),true).'
');

        $exists = false;

        foreach($lines as $line){

            $existing_user = explode( ':', $line );

            if ($existing_user[0] == $user) { //checks if user exists

                $contents = str_replace($line, $contents, $lines); //changes password for user

                $contents = implode(PHP_EOL, $contents);

                $exists = true;

                if ($pass == '') { // removes user if password is empty

                    $contents = str_replace($line, '', $lines); //removes user

                    $contents = array_filter($contents); // cleans empty space in array

                    $contents = implode(PHP_EOL, $contents);

                    $exists = true;

                }

            }

        }

        if ($exists == false) {

            $contents = implode(PHP_EOL, $lines) . PHP_EOL . $contents;
        }

        file_put_contents($htpasswd, $contents);

        print('
output:

'.print_r($contents,true).'
');

    }catch(Exception $e) {

        echo '
fail:
' . $e->getMessage();

    }

}

if(isset($_GET['user'])){

    adduser($_GET['user'], $_GET['pass']);

    echo '
success
';

}else{

    $htpasswd = '.htpasswd';

    $lines = explode(PHP_EOL, file_get_contents($htpasswd)); // get .htpasswd

    print('
.htpasswd:

'.print_r(implode(PHP_EOL, $lines),true).'
');

    echo '
no user set
';
}

I would love to streamline it and clean it up.

Here is my version based on two personal preferences: I hate scroll bars and I hate repititions. Hence I prefer everything typed once and also I like my code being fully visible in the default code area on Stack Overflow.

for this reason I removed that double spacing which just hurts my eyes
also I removed the try catch which is a cargo cult code that makes no sense. I was never able to understand what's the point in writing a try catch that's the only job is to echo the error message when without a try catch PHP will do exactly the same - echo the error message
also I removed the code repetitions such as mentioning the filename in a dozen places
also I changed the algorithm, to make it add a user line only once
I also removed that uncertainty when we can't make our mind whether we are working with an array or with a text
I also changed the function name as it doesn't only add a user
and some other improvements such as following the HTTP guidelines and the ability to choose the hashing algorithm without using inline comments

here it goes
<?php
$filename = ".htpasswd";
if (isset($_POST['user'])) {
    manage_htpasswd($_POST['user'], $_POST['pass'], $filename);
    header("Location: ".$_SERVER['REQUEST_URI']);
    exit;
}
function manage_htpasswd($user, $pass, $filename, $algo = 'crypt_apr1_md5')
{
    $lines = file($filename);
    foreach ($lines as $i => $line) {
        $existing_user = explode(':', $line);
        if ($existing_user[0] === $user) {
            unset($lines[$i]);
            break;
        }
    }
    if ($pass) {
        $lines[] = "$user:" . $algo($pass) . PHP_EOL;
    }
    file_put_contents($filename, $lines);
}
?>
<form method="post">
    User: <input type="text" name="user">

    Pass:<input type="text" name="pass">

    <input type="submit">
</form>

<?= $filename ?>:

<?= file_get_contents($filename) ?>


"The Trip" expense-equalizing challenge I've solved The trip from Programming Challenges.  My solution suffers from lack of floating-point precision, though.

The problem:

  Your job is to compute, from a list of expenses, the minimum amount of
  money that must change hands in order to equalize (within a cent) all
  the students' costs.
  Input Standard input will contain the information for several trips.
  The information for each trip consists of a line containing a positive
  integer, n , the number of students on the trip, followed by n lines
  of input, each containing the amount, in dollars and cents, spent by a
  student. There are no more than 1000 students and no student spent
  more than $10,000.00. A single line containing 0 follows the
  information for the last trip. Output For each trip, output a line
  stating the total amount of money, in dollars and cents, that must be
  exchanged to equalize the students' costs.

For example, if you have:

4
15.00
15.01
3.00
3.01

The output should be:

$11.99

My code:

#include <iostream>
#include <iomanip>

using namespace std;

float two_precision(float n){
    return n - float((n*100.0-(int)(n*100))/100.0);
}

int main(){

  int n; cin >> n;
  float *v, sum, avg, dif;

  while(n){

    sum = dif = 0.0;
    v = new float[n];
    for(int i = n-1; i >= 0; i--){
      cin >> v[i];
      sum += v[i];
    }

    avg = (1.0*sum)/n;

    for(int i = n-1; i >= 0; i--)
      if(two_precision(v[i]-avg > 0))
        dif = two_precision(dif + two_precision(v[i]-avg));

    cout << '$';
    cout << fixed << setprecision(2) << dif << endl;

  delete v;
  cin >> n;
  }

return 0;
}

I have one case to show the error:

5
15.04
15.17
30.32
39.99
78.99
0

The output should be $47.17 and my code returns $47.16.

What you need is a Money class.

class Money
{
    int   value;
    static int normalize(double dallarsAndCents)
    {
        return std::round(dallarsAndCents*100);
    }
    public:
        // Deliberately not using explicit (because I want double;s to auto convert)
        Money(double dallarsAndCents)
           : value(normalize(dallarsAndCents))
        {}

        friend std::ostream& operator<<(std::ostream& out, Money const& m)
        {
            return out << m.value / 100 << "." << std::setw(2) << std::setfill('0') << m.value % 100;
        }
        friend std::istream& operator<<(std::istream& in, Money& m)
        {
            double newValue;
            if (in >> newValue) {  // only do assignment if read works.
                m = Money(newValue);
            }
            return in;
        }

        // Define some arithmetic operations here.

};

You don't want to use new or delete in your code. If you are doing that (and you are not in the very bottom of a class doing resource management) then you are doing it wrong.

Local variables just declare locally. If you need a dyncmaically sized container of objects then use a standard container (std::vector is a good default to start with).

v = new float[n];
....
delete v;

This looks neat and tidy but is not good code. You are susceptible to a memory leak if an exception is thrown. You should be using a container that handles the memory for you.

 std::vector<float>  v(n); // Does the same thing but is exception safe
                           // Look up RIAA for why it is exception safe.

Don't use one line for multiple things.

int n; cin >> n;

This is just lazy. It reads nicer if you use more than one line.

Also read Why is “using namespace std;” considered bad practice? about using namespace;. The reason the standard library is named std and not standard is so that prefixing things is not a major burden. Prefer to use std::cin.

Again the one line thing.

float *v, sum, avg, dif;

It makes it hard to read. The * is on the wrong side because you are squishing things together. Note: The star is part of the type information not the object. This is the opposite of C style.

float*  v;
float   sum = 0.0;
float   avg = 0.0;
float   dif = 0.0;


Caesar Cipher encryption/decryption This program takes a command line argument of how many times you would like to encrypt plain text. After you compile the program, input a message you would like to have coded.  I'm new to C and curious about how to make this program more efficient.

/*
*caesar.c
*
*
*
*Encrypts user supplied messages according to a user supplied   encryption key
*
*/

#include <stdio.h>
#include <cs50.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int main(int argc, string argv[])
{

  if (argc != '\0' && argc == 2 )
  {

    //converting string input to integers
    int f= atoi(argv[1]);

    //getting string command from user
    string a = GetString();

    for(int i = 0, j = strlen(a); i < j; i++)
    {

        if ( isalpha (a[i]))
        {
            if (isupper(a[i]))
            {
                //converting capitalized chars
                char acap = (a[i] - 65);
                int ccap = (acap+f)%26;
                //final capitalized chars loop
                char ecap = ccap + 65;
                printf("%c", ecap);
            }

            else if (islower(a[i]))
            {
                //converting small chars
                char asma = (a[i] - 97);
                int csma = (asma+f)%26;
                //final small chars loop
                char esma = csma + 97;
                printf("%c", esma);
            }

       }
       else
       {
           printf("%c", a[i]);
       }

    }            printf("%c", esma);
    return 0;
}
else
{
    return 1;
}
}

This is unnecessarily complicated:

  if (argc != '\0' && argc == 2 )

This is exactly the same thing but simpler:

  if (argc == 2)

Instead of the hard-coded ASCII code 65 of "A", you could use 'A' to make the code easier to read. So instead of this:

//converting capitalized chars
char acap = (a[i] - 65);
int ccap = (acap+f)%26;
//final capitalized chars loop
char ecap = ccap + 65;
printf("%c", ecap);

You can write like this:

//converting capitalized chars
char acap = (a[i] - 'A');
int ccap = (acap + f) % 26;
//final capitalized chars loop
char ecap = ccap + 'A';
printf("%c", ecap);

I also added spaces around operators in (acap+f)%26 to make it more readable, which is a good practice.

The same goes for the number 97, it's better to use 'a' instead.

The code for handling upper case and lower case letters is practically the same, except for the constant 'A' and 'a'.
Avoid such code duplication, repetition and copy-paste coding as much as possible.
Extract the common logic to a helper function,
and reuse it by passing 'A' and 'a' as parameter.

Use more descriptive variable names.
f, acap, ccap, ecap are really not intuitive,
and your code could become much more readable if you gave these better names.

@Edward made an excellent remark in comments that I'm just going to quote verbatim:

  It's worth noting that both original and suggested changes assume a
  character encoding with a contiguous encoding for the alphabet. This
  is not actually guaranteed by the C standard. For example, EBCDIC
  systems are admittedly rare but not yet extinct.


Write a typo correction program with Levenshtein distance algorithm I'm building a typo correction program. This is the function, which compute the levenshtein distance between two words (a dictionnary word and an input word). I will call this function many times, so it should be fast. I'm looking for therefore some optimizations. I've seen some faster algorithms, but I don't know how to implement them correctly.

static size_t compute_levenshtein_distance
    (char const *const s,
     size_t const ns,
     char const *const t,
     size_t const nt)
{
#define swap(d1, d2)    \
size_t *tmp = (d1);     \
(d1) = (d2);            \
(d2) = tmp

#define max(a, b)       \
((a) > (b) ? (a) : (b)  \

#define min2(a, b)      \
((a) < (b) ? (a) : (b)) \

#define min3(a, b, c)   \
(min2(min2(a, b), c))

    size_t t1[ns+1], t2[ns+1];
    size_t *d1 = t1, *d2 = t2;

    for (size_t i = 1UL; i <= ns; ++i)
        d1[i] = i;

    for (size_t i = 1UL; i <= nt; ++i) {
        char const cCol = t[i-1];
        d2[0UL]         = i;

        for (size_t j = 1UL; j <= ns; ++j) {
            int    const nCost = s[j-1] != cCol;
            size_t const i1    = d1[j  ] + 1;
            size_t const i2    = d2[j-1] + 1;
            size_t const i3    = d1[j-1] + nCost;
            d2[j] = min3(i1, i2, i3);
        }
        swap(d1, d2);
    }
    return d1[ns];

#undef swap
#undef max
#undef min2
#undef min3
}

Do you have any ideas ?
Thanks.

I see very little space for improvements.

First, your min3 macro (btw, max is missing a closing bracket) will, in some cases, execute inside branching more than needed (i.e., if c > min2(a,b)). I'd write it directly:

#define min3(a, b, c)   \
((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))

Second, this part:

for (size_t i = 1UL; i <= nt; ++i) {
    char const cCol = t[i-1];
    d2[0UL]         = i;

can save one subtraction:

for (size_t i = 0UL; i < nt; ) {
    char const cCol = t[i];
    d2[0UL]         = ++i;

Maybe the inside loop can be made faster by using pointer arithmetic instead of indexing, but I'm not sure. So, you can try replacing

    for (size_t j = 1UL; j <= ns; ++j) {
        int    const nCost = s[j-1] != cCol;
        size_t const i1    = d1[j  ] + 1;
        size_t const i2    = d2[j-1] + 1;
        size_t const i3    = d1[j-1] + nCost;
        d2[j] = min3(i1, i2, i3);
    }

with

    size_t *d1j = d1+1, *d2j1 = d2, *d1j1 = d1;
    for (size_t j = 1UL; j <= ns; ++j) {
        int    const nCost = s[j-1] != cCol;
        size_t const i1    = *d1j + 1;
        size_t const i2    = *d2j1 + 1;
        size_t const i3    = *d1j1 + nCost;
        *d2j = min3(i1, i2, i3);
        d1j1 = d1j++;
        d2j1++;
    }


All possible combinations of colors for Mastermind Just started out with CIS 194 on Haskell and wonder what the more idiomatic way to solve this problem would have been.

This code is supposed to generate all possible combinations of 6 given colors up to a given length. It works, but I think my solution is not that elegant. The suggested solution included this hint:

  Hint: This exercise is a bit tricky. Try using a helper function that
  takes in all the codes of length n − 1 and uses it to produce all
  codes of length n. You may find the concatMap function helpful.

But I could not figure a way so I did it like this:

-- Mastermind -----------------------------------------

-- A peg can be one of six colors
data Peg = Red | Green | Blue | Yellow | Orange | Purple
         deriving (Show, Eq, Ord)

-- A code is defined to simply be a list of Pegs
type Code = [Peg]

-- List containing all of the different Pegs
colors :: [Peg]
colors = [Red, Green, Blue, Yellow, Orange, Purple]

---- Exercise 6 ----

-- Extends a given Code by prepending a Peg: extendCode [Red, Green] Blue -> [Blue, Red, Green]
extendCode :: Code -> Peg -> Code
extendCode code peg = peg : code

-- Extends a given Code by all possible Pegs, turning the Code into a list of Codes
fullyExtendCode :: Code -> [Code]
fullyExtendCode code = map (\color -> extendCode code color) colors

-- Extends a given number of Codes by all possible Pegs
fullyExtendCodes :: [Code] -> [Code]
fullyExtendCodes [] = map (:[]) colors
fullyExtendCodes codes = concatMap fullyExtendCode codes

-- Helper function for allCodes which includes the Codes list from previous recursions
aCodes :: [Code] -> Int -> [Code]
aCodes codes 0 = codes
aCodes codes l = aCodes (fullyExtendCodes codes) (l - 1)

allCodes :: Int -> [[Peg]]
allCodes l = aCodes [] l

Any suggestions from more experiened Haskell programmers?

You are looking for all of the variations (with repetitions) of a given list!

variations :: Int -> [a] -> [[a]]
variations n cs
 | n <= 0 = []
 | n == 1 = map pure cs --  map (\c -> [c]) cs
 | otherwise = variations (n-1) cs >>= \ps -> map (:ps) cs

Where the right side of the last line could be any of the following:

variations (n-1) cs >>= flip map cs . flip (:)

concatMap (\ps -> map (:ps) cs) (variations (n-1) cs)

concat . map (\ps -> map (\c -> c:ps) cs) $ variations (n-1) cs

Pick your poison. They are all equivalent. as >>= f is the same as concatMap f as, because for the list monad join is concat, and fmap is map, so bind = (>>=) is join . fmap = concat . map.

Let me demonstrate how variations is evaluated for cs = "12", n=2.

Since variations 1 "12" = ["1", "2"], we know that variations 2 "12" = concat . map (\ps -> map (\c -> c:ps) "12") $ ["1", "2"]  Let's see what each mapping does.

map (\c -> c:ps) "12" simply takes a character c from "12" and appends it to the beginning of ps. But what's ps? Let's look at the other map.

The outer map simply applies the inner function \ps -> map (\c -> c:ps) "12" to each element of ["1","2"].
As we have seen, this inner function simply takes the list cs and maps the element c to c:ps. In this case it turns "1" into ["11","21"], and "2" into ["12","22"].

So all in all we have the following.

variations 2 "12" = concat . map (\ps -> map (\c -> c:ps) "12") $ variations 1 "12"
                  = concat . map (\ps -> map (\c -> c:ps) "12") $ ["1", "2"]
                  = concat [["11","21"],["12","22"]]
                  = ["11","21","12","22"]

Hope this helps.


Multithreading, shared queue as synchronization point I have two threads, one produces images and one processes them. For the synchronization, I created a class where you can set and get images, and it always waits until an image is available or a worker thread is not busy anymore.

Additionally, a call to SetFinish stops both threads, while a call to Clear clears the currently (not yet processed) image.

Do you see any problems with this code (mainly threading issues)?

Header:

#ifndef SHARED_QUEUE_H_
#define SHARED_QUEUE_H_

#include <memory>
#include <condition_variable>

struct ImageData;

class SharedQueue {
public:
  void SetFinish();
  bool GetImage(std::shared_ptr<const ImageData> &image);
  void SetImage(std::shared_ptr<const ImageData> image);
  void Clear();

private:
  std::condition_variable image_available_;
  std::condition_variable image_processed_;
  std::shared_ptr<const ImageData> next_image_;
  bool stop_{false};
  std::mutex mutex_;
};

#endif  // SHARED_QUEUE_H_

Implementation:

#include "shared_queue.h"

void SharedQueue::SetFinish() {
  { // Store flag and wake up the thread
    std::lock_guard<std::mutex> lock(mutex_);
    stop_ = true;
  }
  image_available_.notify_one();
  image_processed_.notify_one();
}

bool SharedQueue::GetImage(std::shared_ptr<const ImageData> &image) {
  {
    std::unique_lock<std::mutex> lock(mutex_);
    image_available_.wait(lock, [this]{
      return (next_image_.get() != nullptr || stop_);
    });

    if (stop_)
      return false;

    image = next_image_;
    next_image_.reset();
  }
  image_processed_.notify_one();
  return true;
}

void SharedQueue::SetImage(std::shared_ptr<const ImageData> image) {
  { // Store image for processing and wake up the thread
    std::unique_lock<std::mutex> lock(mutex_);
    image_processed_.wait(lock, [this]{
      return (next_image_.get() == nullptr || stop_);
    });

    if (stop_)
      return;

    next_image_ = image;
  }
  image_available_.notify_one();
}

void SharedQueue::Clear() {
  {
    std::unique_lock<std::mutex> lock(mutex_);
    next_image_.reset();
  }
  image_processed_.notify_one();
}

Not a Queue!

First and foremost, your SharedQueue isn't a queue. You can only store one element in it at a time. That doesn't make it super useful - what if the producer wants to write two images?

queue.setImage(img1);
queue.setImage(img2); // blocks?

It's more of a guarantee-one-at-a-time container. A queue would be much more useful, so I'd consider actually implementing one. This is a pretty major design flaw.

Beyond that, I just have minor comments.

Move semantics

You have a lot of copies where you can do moves. For instance, in SetImage():

next_image_ = image;

should be:

next_image_ = std::move(image);

Moving is cheaper than copying (no need to incur reference counting).

Checking shared_ptr

You don't need to use .get(), you can directly check the shared_ptr:

image_processed_.wait(lock, [this]{
   return !next_image_ || stop_;
});

Clear()

You use a std::unique_lock<> to Clear() where a std::lock_guard<> is sufficient. You use the correct one in SetFinish().


Recursive maze solver Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution.

#include <iostream>
#include <vector>
#include <string>

enum { GOAL = '*', SPACE = ' ', WALL = '#', TRIED = '!', USED = '+' };

class maze {
    std::vector<std::string> data;
public:
    char &operator()(size_t x, size_t y) {
        return data[y][x];
    }

    friend std::istream &operator>>(std::istream &is, maze &m) {
        std::string temp;
        while (std::getline(is, temp))
            m.data.push_back(temp);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, maze const &m) {
        for (auto const &s : m.data)
            os << s << '\n';
        return os;
    }

    size_t y_dim() { return data.size(); }
    size_t x_dim() { return data[0].size(); }
};

bool solve(maze &m, size_t x = 0, size_t y=0) {
    if (x < 0 || y < 0 || x >= m.x_dim() || y >= m.y_dim())
        return false;

    if (m(x, y) == GOAL)
        return true;

    if (m(x, y) != SPACE)
        return false;

    m(x, y) = USED;

    bool solved
         = solve(m, x - 1, y)
        || solve(m, x + 1, y)
        || solve(m, x, y - 1)
        || solve(m, x, y + 1);

    if (!solved)
        m(x, y) = TRIED;

    return solved;
}

int main(){
    maze m;
    std::cin >> m;

    solve(m);
    std::cout << m;
}

Input is a simple text file of walls, spaces, and a goal, such as:

  #######
#    # ##
# ####  #
#      ##
# ### ###
#####  *#

Searching always commences from position 0, 0 (i.e., the top, left corner).

Try and engage the move constructor:

m.data.push_back(temp);

Because temp is a named variable it will hit the version that uses const& T. To try and get the alternative version that engages the move constructor add std::move

m.data.push_back(std::move(temp));

The input operator does not make any attempt to make sure each line is the same size.

size_t x_dim() { return data[0].size(); }

So the above may not be accurate.
You can add a fake set of cells at the top/bottom/left/right of type 'WALL' then you don't need the test if (x < 0 || y < 0 || x >= m.x_dim() || y >= m.y_dim()) as it can never reach outside the bounds of the maze (this can be forced to be true because it is part of the code and not part of the user input). This means you don't need y_dim() as that is the only use case.

My main issue is that solve() actually mutates the maze object. Some form of visitor pattern may be a more re-usable technique, or solve() would be better as a member of maze().


Fastest way to multiply two byte arrays in Java I have two byte arrays that represent unsigned 256-bit values and I want to multiply them resulting into a new value. What is the fastest ways to do this in Java? And are there other factors I should take into account?

This is my current multiply-function:

// two input values
// i.e. each 0x00000000000000000000000000000000000000000000000000000000000000ff
byte[] input1Array = new byte[32];
byte[] input2Array = new byte[32];

BigInteger input1 = new BigInteger(1, input1Array);
BigInteger input2 = new BigInteger(1, input2Array);
BigInteger result = input1.multiply(input2);

byte[] bytes = result.toByteArray();
ByteBuffer data    =  ByteBuffer.allocate(32);
System.arraycopy(bytes, 0, data.array(), 32 - bytes.length, bytes.length);

// expected 0x000000000000000000000000000000000000000000000000000000000000fe01
byte[] resultArray = data.array();

This takes ~1500ms on my PC for 10000000 iterations and something tells me this can be done faster.

Your code is somewhat hypothetical, in the example you give, it is 0 * 0, which will be pretty fast....

Still, let's put things in to perspective. You are performing 10 million loops in 1.5 seconds. A modern Intel CPU runs at 3.9GHz. In 1.5 seconds, that's about 6billion cycles (5.85 billion or so).

about 6 billion cycles for 10 million loops is about 600 cycles per loop. Now, in that loop, you are:

creating two byte arrays (OK, maybe you reuse those).
creating 2 BigInteger objects
running an add on those BigIntegers and computing a 3rd BigInteger
converting that third big-integer back to an array.
creating a ByteBuffer
copying the array content to the byte buffer
getting the byte buffer's internal array.

That is an amazing amount of work to do in 600 instruction cycles.I would expect the various object creates (three BigIntegers, two arrays, and a Buffer) are the most expensive things to do as they require multiple instructions, allocations/reservations, and registrations in the object creation, including CPU/cache management, etc.

Frankly, what you have is pretty good.

You could reduce the amount of work you are doing by completely removing the ByteBuffer from the last section. This code:

byte[] bytes = result.toByteArray();
ByteBuffer data    =  ByteBuffer.allocate(32);
System.arraycopy(bytes, 0, data.array(), 32 - bytes.length, bytes.length);

// expected 0x000000000000000000000000000000000000000000000000000000000000fe01
byte[] resultArray = data.array();

could instead be:

byte[] bytes = result.toByteArray();
if (bytes.length < 32) {
    byte[] tmp = new byte[32];
    System.arrayCopy(byte, 0, tmp, 32 - bytes.length, bytes.length);
    bytes = tmp;
}

But, what if the sum is more than 32 bytes?

Also, if you are at/near the limits, and you have negative input values, then you may end up with a negative result. I know your code appears to limit the negative impact by forcing a positive sign, but it could 'overflow' the 32 bytes.


Selecting an email template and BCC address based on the message type My code-editor "show hints" says that the method length exceeds 20 lines.  How can I refactor the setEmailTemplateBcc function?

private function setBcc($bcc)
    {
        if ($bcc) {
            $this->bcc = explode(',', $bcc);
        }
    }

    public function setType($type)
    {
        $this->setEmailTemplateBcc($type);
        return $this;
    }

    private function setEmailTemplateBcc($type)
    {
        $template = '';
        $bcc = '';

        switch ($type) {
            case self::EMAIL_NEW_SUBSCRIPTION:
                $template = DataHelper::XML_PATH_SUBSCRIPTION_EMAIL;
                $bcc = DataHelper::XML_PATH_REMINDER_EMAIL_BCC;
                break;
            case self::EMAIL_CARD_ADD:
                $template = DataHelper::XML_PATH_NEW_CARD_ADD_EMAIL;
                $bcc = DataHelper::XML_PATH_NEW_CARD_ADD_EMAIL_BCC;
                break;
            case self::EMAIL_PAYMENT_FAILED:
                $template = DataHelper::XML_PATH_PAYMENT_FAILED_EMAIL;
                $bcc = DataHelper::XML_PATH_PAYMENT_FAILED_EMAIL_BCC;
                break;
            case self::EMAIL_PROFILE_UPADATE:
                $template = DataHelper::XML_PATH_PROFILE_UPDATE_EMAIL;
                $bcc = DataHelper::XML_PATH_PROFILE_UPDATE_EMAIL_BCC;
                break;
            case self::EMAIL_REMINDER:
                $template = DataHelper::XML_PATH_REMINDER_EMAIL;
                $bcc = DataHelper::XML_PATH_REMINDER_EMAIL_BCC;
                break;
            case self::EMAIL_TOPUP_REMINDER:
                $template = DataHelper::XML_PATH_EWALLET_TOPUP_REMINDER_EMAIL;
                $bcc = DataHelper::XML_PATH_EWALLET_TOPUP_REMINDER_EMAIL;
                break;
        }

        $this->setTemplate($template);
        $this->setBcc($bcc);
    }

I would create two new static variables in your class, arrays that contain all options, like

public static $template = [
    self::EMAIL_NEW_SUBSCRIPTION => DataHelper::XML_PATH_SUBSCRIPTION_EMAIL,
    self::EMAIL_CARD_ADD         => DataHelper::XML_PATH_NEW_CARD_ADD_EMAIL_BCC,
    // and so on
];

then setting the email template will be as simple as just one line:

$template = self::$template[self::EMAIL_CARD_ADD] ?? '';

and the same goes for BCC


Random "month & day" with JS Can anyone review this?

setInterval(function() {
var days_array = [31,29,31,30,31,30,31,31,30,31,30,31];
var m = randNum(12);
var m_limit = days_array[m-1];
var d = randNum(m_limit);
$("code").html("day = "+d+"<br>month = "+m);
},1000);
function randNum(limit){var r=Math.floor(Math.random()*limit)+1;return r;}

jsFiddle

function randNum(limit){var r=Math.floor(Math.random()*limit)+1;return r;}

Can be shortened to:

function randNum(limit){return Math.floor(Math.random()*limit)+1;}

You should also declare your variables outside of the setInterval and then set them inside only if you need to (for example, the days_array never changes so only needs to be decalared once and not every second.


Scala mastermind solver, which is the most scala-ish I am trying to express the classical TDD kata of mastermind in the most idiomatic scala I can. Here is a scalatest, test suite :

package eu.byjean.mastermind

import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
import org.scalatest.FlatSpec
import org.scalatest.matchers.ShouldMatchers

@RunWith(classOf[JUnitRunner])
class MastermindSpec extends FlatSpec with ShouldMatchers {
  behavior of "Mastermid"

  it should "find no good and no misplaced for a wrong guess" in {
    Mastermind.check (guess='red)(secret='blue) should equal (0,0)
  }

  it should "find all good if guess equals secret of one" in {
    Mastermind.check('blue)('blue) should equal (1,0)
  }

  it should "find one good if guess has one good in a secret of two" in {
    Mastermind.check('blue,'red)('blue,'green) should equal (1,0)
    Mastermind.check('green,'red)('blue,'red) should equal (1,0)
  }

  it should "find two good if guess has two good in a secret of three" in {
    Mastermind.check('blue,'red,'red)('blue,'green,'red) should equal (2,0)
  }

  it should "find one misplaced blue in a guess of two" in {
    Mastermind.check('blue,'red)('green,'blue) should equal (0,1)
  }

  it should "find two misplaced in a guess of four" in {
    Mastermind.check('blue,'blue,'red,'red)('green,'yellow,'blue,'blue) should equal (0,2)
  }
  it should "find two misplaced colors in a guess of four" in {
    Mastermind.check('green,'blue,'yellow,'red)('green,'yellow,'blue,'blue) should equal (1,2)
  }
}

and my current implementation

package eu.byjean.mastermind

object Mastermind {
  def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
    val (goodPairs, badPairs) = guess.zip(secret).partition { case (x, y) => x == y }
    val(guessMiss,secMiss)=badPairs.unzip
    val misplaced=guessMiss.sortBy(_.toString).zip(secMiss.sortBy(_.toString())).filter{case (x,y)=>x==y}
    (goodPairs.size, misplaced.size)
  }

In the imperative form, some people employ a map and count for each color the number of occurences of the color in the secret and in the guess (only as far as misplaced go of course).
I tried an approach using foldLeft on the badPairs list of tuple, which lead me to variable naming problems and calling map.updated twice in the foldLeft closure which didnt seem right

Any thoughts on how to improve on the above code. It doesn't feel perfect. how would you improve it along the following axis:

bugs: have I missed something obvious ?
performance : this version with zip, unzip, sort, zip again most likely isn't the fastest
readability : how would I define an implicit ordering for Symbol so I don't have to pass _.toString ,
idiomatic scala: is there globally a more "scala-ish" way of solving this ?

Thanks

All this zipping and unzipping looks really convoluted. I think the problem here is getting too much enamored with what you can do with a Scala collection instead of focusing on the problem at hand.

One way of decreasing zip cost is to do it on a view. This way, no intermediary collection is created -- though that depends a bit on the methods being called. At any rate, zip is one of these methods.

It wouldn't work on your case, however, because you then go on to partition and unzip -- I'd be wary of calling such methods on a view, because they may end up being more expensive, not less.

I think the map approach is better, because it avoids the O(n log n) sorting. A HashMap can be built in O(n), and looked up in constant time. This is how I'd do it:

object Mastermind {
  def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
    val numOfGoodPairs = guess.view zip secret count { case (a, b) => a == b }
    val guessesForSymbol = guess.groupBy(identity).mapValues(_.size)
    val secretsForSymbol = secret.groupBy(identity).mapValues(_.size)
    val unorderedGuesses = for {
      symbol <- guessesForSymbol.keys.toSeq
      secrets <- secretsForSymbol get symbol
      guesses = guessesForSymbol(symbol)
    } yield secrets min guesses
    val numOfMisplaced = unorderedGuesses.sum - numOfGoodPairs
    (numOfGoodPairs, numOfMisplaced)
  }
}

The first line should be pretty fast -- it will iterate once through both guess and secret, counting each time they are equal.

Computing both maps is more expensive, but it should be cheaper than sorting. Note that mapValues return a view of the values -- it does not copy any data. This is particularly interesting because it will only compute the size of map elements for keys present in both guess and secret. It is a small optimization, but you gain it almost for free.

We avoid most of the complexity by simply subtracting the number of correct guesses from the number of unordered guesses.


AES-128 encryption class This is the first time I've written a class in Java to do encryption using AES. Since security is involved I would love it if someone could take a look at it and let me know if anything is wrong with my implementation. Additionally, any feedback about shortcuts I could have taken or sloppy processes I've used would be greatly appreciated!

import java.io.UnsupportedEncodingException;
import java.security.InvalidAlgorithmParameterException;
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.KeyGenerator;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;
import javax.crypto.spec.IvParameterSpec;

public class Encrypt {

    private Cipher encryptCipher;
    private SecretKey key;
    private IvParameterSpec iv;

    private byte[] clearText;

    /**
     * Encrypts data using AES-128
     * @param clearText The data to be encrypted
     */
    public Encrypt(String clearText) {

        //Generate the IV and key
        this.iv = new IvParameterSpec(this.generateIv());
        this.key = this.generateKey();

        //Create an AES cipher in CBC mode using PKCS5 padding
        try {
            this.encryptCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");

            try {
                this.encryptCipher.init(Cipher.ENCRYPT_MODE, this.key, this.iv);
            }
            catch(InvalidKeyException ex) {
                Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            }
            catch(InvalidAlgorithmParameterException ex) {
                Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        catch(NoSuchAlgorithmException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
        }
        catch(NoSuchPaddingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
        }

        //Convert the clear text passed by the user into bytes
        try {
            this.clearText = clearText.getBytes("UTF-16");
        }
        catch(UnsupportedEncodingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    /**
     * Generates a random IV to be used in the encryption process
     * @return The IV's byte representation
     */
    private byte[] generateIv() {
        SecureRandom random = new SecureRandom();
        byte[] ivBytes = new byte[16];
        random.nextBytes(ivBytes);
        return ivBytes;
    }

    /**
     * Generates a secret key to be used in the encryption process
     * @return The secret key
     */
    private SecretKey generateKey() {
        KeyGenerator keygen;
        try {

            //Java normally doesn't support 256-bit key sizes without an extra installation so stick with a 128-bit key
            keygen = KeyGenerator.getInstance("AES");
            keygen.init(128);
            SecretKey aesKey = keygen.generateKey();
            return aesKey;
        }
        catch(NoSuchAlgorithmException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

    /**
     * Encrypts the data passed during instantiation of this object
     * @return The byte representation of the encrypted data
     */
    public byte[] encrypt() {
        try {
            return this.encryptCipher.doFinal(this.clearText);
        }
        catch(IllegalBlockSizeException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
        catch(BadPaddingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

}

Here's my final implementation with the changes based on @Robert Snyder's comment:

  My first suggestion is to make refactor a little bit your constructor.
  Start by making a Method getCipherInstance() put your try catches in
  that method. Then make another method initializeCipher() This will
  make your constructor easier to read. As for your random IV generator
  you might want to consider a lesson from how Mifare Desfire passes
  enciphered data. You basically start with a IV of 0x00 and have a key
  that is known elsewhere. In the end hacking is much more difficult.

import com.sun.org.apache.xml.internal.security.utils.Base64;
import java.io.UnsupportedEncodingException;
import java.security.InvalidAlgorithmParameterException;
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.KeyGenerator;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;
import javax.crypto.spec.IvParameterSpec;

public class Encrypt {

    private Cipher encryptCipher;
    private SecretKey key;
    private IvParameterSpec iv;

    private byte[] clearText;
    private byte[] encryptedText;

    /**
     * Encrypts data using AES-128
     * @param clearText The data to be encrypted
     */
    public Encrypt(String clearText) {

        //Generate the IV and key
        this.iv = new IvParameterSpec(this.generateIv());
        this.key = this.generateKey();
        this.encryptCipher = createCipher();
        this.clearText = this.convertClearText(clearText);
        this.encryptedText = this.encrypt();
    }

    /**
     * Converts the clear text passed by the user to an array of bytes
     * @param clearText The clear text passed by the user
     * @return The byte representation of the clear text
     */
    private byte[] convertClearText(String clearText) {

        //Convert the clear text passed by the user into bytes
        try {
            return clearText.getBytes("UTF-8");
        }
        catch(UnsupportedEncodingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

    /**
     * Creates an AES cipher using CBC mode with PKCS5 padding
     * @return The cipher used to encrypt data
     */
    private Cipher createCipher() {

        //Create an AES cipher in CBC mode using PKCS5 padding
        try {
            Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
            cipher.init(Cipher.ENCRYPT_MODE, this.key, this.iv);
            return cipher;
        }
        catch(NoSuchAlgorithmException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
        catch(NoSuchPaddingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
        catch(InvalidKeyException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
        catch(InvalidAlgorithmParameterException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

    /**
     * Generates a random IV to be used in the encryption process
     * @return The IV's byte representation
     */
    private byte[] generateIv() {
        SecureRandom random = new SecureRandom();
        byte[] ivBytes = new byte[16];
        random.nextBytes(ivBytes);
        return ivBytes;
    }

    /**
     * Generates a secret key to be used in the encryption process
     * @return The secret key
     */
    private SecretKey generateKey() {
        KeyGenerator keygen;
        try {

            //Java normally doesn't support 256-bit key sizes without an extra installation so stick with a 128-bit key
            keygen = KeyGenerator.getInstance("AES");
            keygen.init(128);
            SecretKey aesKey = keygen.generateKey();
            return aesKey;
        }
        catch(NoSuchAlgorithmException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

    /**
     * Returns the initialization vector
     * @return The randomly generated IV
     */
    public IvParameterSpec getIv() {
        return this.iv;
    }

    /**
     * Returns the key used for encryption
     * @return The randomly generated secret key
     */
    public SecretKey getKey() {
        return this.key;
    }

    /**
     * Encrypts the data passed during instantiation of this object
     * @return The byte representation of the encrypted data
     */
    public final byte[] encrypt() {
        try {
            return this.encryptCipher.doFinal(this.clearText);
        }
        catch(IllegalBlockSizeException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
        catch(BadPaddingException ex) {
            Logger.getLogger(Encrypt.class.getName()).log(Level.SEVERE, null, ex);
            return null;
        }
    }

    /**
     * Returns the encrypted text as a base64 encoded string
     * @return The encrypted base64 encoded string
     */
    @Override
    public String toString() {
        return Base64.encode(encryptedText);
    }

}

Here is the most recent version of the class. One of the suggestions was to set the IV to 0x00 which I did not do. Someone correct me if I'm wrong but I'm almost positive that it is critical to have random data for the IV for each encryption operation. I've done what others have suggested and bubbled the exceptions up. The constructor has also been cleaned up quite a bit and there's now a toString() method that returns the data as a base64 encoded string.

import org.apache.commons.codec.binary.Base64;
import java.io.UnsupportedEncodingException;
import java.security.InvalidAlgorithmParameterException;
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.KeyGenerator;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;
import javax.crypto.spec.IvParameterSpec;

public final class Encrypt {

    private Cipher encryptCipher;
    private SecretKey key;
    private IvParameterSpec iv;

    private byte[] clearText;
    private byte[] encryptedText;

    /**
     * Encrypts data using AES-128
     *
     * @param clearText The data to be encrypted
     * @throws java.security.NoSuchAlgorithmException
     * @throws javax.crypto.NoSuchPaddingException
     * @throws java.security.InvalidKeyException
     * @throws javax.crypto.BadPaddingException
     * @throws java.security.InvalidAlgorithmParameterException
     * @throws javax.crypto.IllegalBlockSizeException
     * @throws java.io.UnsupportedEncodingException
     */
    public Encrypt(String clearText) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, InvalidAlgorithmParameterException, UnsupportedEncodingException, IllegalBlockSizeException, BadPaddingException {

        //Generate the IV and key
        this.iv = new IvParameterSpec(this.generateIv());
        this.key = this.generateKey();
        this.encryptCipher = createCipher();
        this.clearText = this.convertClearText(clearText);
        this.encryptedText = this.encrypt();
    }

    /**
     * Converts the clear text passed by the user to an array of bytes
     *
     * @param clearText The clear text passed by the user
     * @return The byte representation of the clear text
     */
    private byte[] convertClearText(String clearText) throws UnsupportedEncodingException {

        //Convert the clear text passed by the user into bytes
        return clearText.getBytes("UTF-8");
    }

    /**
     * Creates an AES cipher using CBC mode with PKCS5 padding
     *
     * @return The cipher used to encrypt data
     */
    private Cipher createCipher() throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, InvalidAlgorithmParameterException {

        //Create an AES cipher in CBC mode using PKCS5 padding
        Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        cipher.init(Cipher.ENCRYPT_MODE, this.key, this.iv);
        return cipher;
    }

    /**
     * Generates a random IV to be used in the encryption process
     *
     * @return The IV's byte representation
     */
    private byte[] generateIv() {
        SecureRandom random = new SecureRandom();
        byte[] ivBytes = new byte[16];
        random.nextBytes(ivBytes);
        return ivBytes;
    }

    /**
     * Generates a secret key to be used in the encryption process
     *
     * @return The secret key
     */
    private SecretKey generateKey() throws NoSuchAlgorithmException {
        KeyGenerator keygen;

        //Java normally doesn't support 256-bit key sizes without an extra installation so stick with a 128-bit key
        keygen = KeyGenerator.getInstance("AES");
        keygen.init(128);
        SecretKey aesKey = keygen.generateKey();
        return aesKey;

    }

    /**
     * Returns the initialization vector
     *
     * @return The randomly generated IV
     */
    public IvParameterSpec getIv() {
        return this.iv;
    }

    /**
     * Returns the key used for encryption
     *
     * @return The randomly generated secret key
     */
    public SecretKey getKey() {
        return this.key;
    }

    /**
     * Encrypts the data passed during instantiation of this object
     *
     * @return The byte representation of the encrypted data
     */
    private byte[] encrypt() throws IllegalBlockSizeException, BadPaddingException {
        return this.encryptCipher.doFinal(this.clearText);

    }

    /**
     * Returns the encrypted text as a base64 encoded string
     *
     * @return The encrypted base64 encoded string
     */
    @Override
    public String toString() {
        return Base64.encodeBase64String(encryptedText);
    }

}


Return values from array A in the order they are in array B So my question is the cleanest way to do #product_panels_for below:

class ProductPanel < Struct.new(:product)
end

class ProductPresenter
  def product_panels_for(selected_products)
    selected_products.map do |product|
      product_panels.find { |panel| panel.product.to_s == product }
    end.
      compact
  end

  def product_panels
    [ProductPanel.new(:iphone), ProductPanel.new(:ipad), ProductPanel.new(:ibidet)]
  end
end

ProductPresenter.new.product_panels_for(['ipad', 'iphone']) # => [<ProductPanel product=:ipad>, <ProductPanel product=:iphone>]

This is obviously simplified, but the point is #product_panels_for should return values from product_panels but in the order given in selected_panels. Maybe this is fine is just feels a bit gangly for something that seems conceptually simpler than that.

To be clear the order is defined by the business, it won't be alphabetical or anything nice.

In case anyone's thinking it, yes, I know in Ruby 2.7 I could replace .map...compact with .filter_map, but I'm not on 2.7 yet.

My previous implementation was:

def product_panels_for(selected_products)
  product_panels.select { |pp| selected_products.include?(pp) }
end

which was nice and clean but didn't preserve the order of selected_products.

If the implementation at the top can't be improved on, is there a nice way to use this previous implementation but chain something after the select that sorts the result so the order matches selected_products? I'm just generally curious about a good way to cleanly sort A so its order matches B where B is a list of values for an attributes of A.

Your solution looks good to me, I tried some alternatives but they end up being a little more verbose and not adding value that makes it worth.

Also, I don't think it is worth adding one more step to order it just to use select.

I would go with your first solution.


Parallelized web crawler using goroutines and channels As part of the "a tour of Go" section on golang.org, I was trying to make a (formerly singlethreaded) web crawler parallelized using goroutines. I got it working but it doesn't seem to "flow" right; there's a bunch of duplicated code. Looking for advice as to how it can seem a bit more Go-literate.
package main

import (
    "fmt"
    "sync"
)

type Fetcher interface {
    // Fetch returns the body of URL and
    // a slice of URLs found on that page.
    Fetch(url string) (body string, urls []string, err error)
}

type safeMap = struct {
    seen map[string]bool
    mu sync.Mutex
    remaining int
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.

func gci(url string, depth int, fetcher Fetcher, m *safeMap, fc chan string) {
    go crawl_int(url, depth, fetcher, m, fc)
}

func crawl_int(url string, depth int, fetcher Fetcher, m* safeMap, fc chan string) {
    if depth > 0 {
        body, urls, err := fetcher.Fetch(url)
        //fc <- fmt.Sprintf("Crawling %s\n", url)
        m.mu.Lock()
        defer m.mu.Unlock()

        if err != nil {
            fc <- fmt.Sprintf("%v\n",err)
        } else {
            fc <- fmt.Sprintf("found: %s %q %d\n", url, body, len(urls))
            for _, u := range urls {
                _, found := m.seen[u]
                if !found {
                    m.remaining += 1
                    m.seen[u] = true
                    defer gci(u, depth-1, fetcher, m, fc)
                }
            }
        }
    } else {
        m.mu.Lock()
        defer m.mu.Unlock()
    }
    m.remaining -= 1
    //fc <- fmt.Sprintf("finished %s remaining to %d\n", url, m.remaining)
    if (m.remaining == 0) {
        //fc <- fmt.Sprintf("closing")
        close(fc)
    }
}

func Crawl(url string, depth int, fetcher Fetcher, ch chan string) {
    // Fetches URLs in parallel.
    // Doesn't fetch the same URL twice.
    c := safeMap{seen: make(map[string]bool), remaining: 1}

    go crawl_int(url, depth, fetcher, &c, ch)
}

func main() {
    ch := make(chan string,5)
    Crawl("https://golang.org/", 4, fetcher, ch)
    for u := range ch {
        fmt.Print(u)
    }
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
    "https://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "https://golang.org/pkg/",
            "https://golang.org/cmd/",
        },
    },
    "https://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "https://golang.org/",
            "https://golang.org/cmd/",
            "https://golang.org/pkg/fmt/",
            "https://golang.org/pkg/os/",
        },
    },
    "https://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
    "https://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
}

OK, first off: back when go was first released, a lot of people criticised it for being "too opinionated". The coding style was/is very specific (indentation, brackets, etc... are all standardised). This has turned out to be a great thing. Code written by anyone, provided they've used gofmt looks very similar. This resulted in code being easy to read regardless of who wrote it. In addition to the stuff gofmt takes care of, I would strongly recommend you look at Golang Code Review comments and adopt the recommendations listed there. Function names like crawl_init should be camelCased (crawlInit). In fact, the init part should probably be omitted. Acronyms like gci (which I assume is short for "go crawl init") should be capitalised. I'll go through your code and change the names to their more idiomatic counterparts.
General comments
There's a couple of issues here. Your crawl_init function is closing the channel (fc). This is not where your channel should be closed. The rule of thumb is that channels are closed in the same scope as where they're created. Exceptions to this rule are not uncommon (e.g. closures), but 95% of the time, you'll close a channel either on the same level as where you create it, or in a function that has access to the scope creating the channel. Because you're recursively crawling URLs, it's more than likely a routine will end up reaching the point where it thinks it can close the channel, while another routine is still trying to write to it. This results in a data race, and a runtime panic. Something you'll want to avoid at all cost.
Another comment I'd have is that you're keeping track of which URL's you've already checked using a map (map[string]bool). You quite rightly use a mutex to avoid concurrent access, but you're releasing the locks you acquire only if your function/routine returns (owing to your use of defer). The result is that you can spawn countless of routines, and you could even increase the channel buffer size to an insane number, but all routines will just wait until the lock is released, and execute sequentially. I suspect this is the reason why you created this gci function, and are invoking it in your defer stack, rather than just spawning the routine in place.
Something worth noting here, too, is that bool is a type that takes up space. Not much, but it takes up memory. The language specification states that an empty struct (like s := struct{}{}) is a 0-byte value. If you need a map that keeps track of values you've already seen, then the keys are the only data that really matters. As such, using map[string]struct{} is a more efficient type.
You're also initialising the map using make(map[string]bool). There are times where you want to use make: e.g. cases where you know how big the map will need to be, and you want to cut down on the number of times the runtime will have to allocate additional memory. In those situations, you'll write something like cpy := make(map[string]struct{}, len(src)). When you don't know/care about allocation cycles, it's shorter (and more common) to just use a literal: seen: map[string]struct{}{}.
In your comments, I couldn't help notice the use of the word "parallel". It may seem like a distinction without a difference, but golang deals in concurrency, not parallelism. Some routines may actually run in separate threads, but that's not necessarily the case.
With all this out of the way, let's get down to the actual code
The code
I'll just go through the code you have, and rework it + provide some clarification as to why I'm doing so. I've omitted the fetcher interface as it's not that pertinent to the code you've shared here
package main

import (
    "context" // added this
    "fmt"
    "sync"
)

// the = sign is invalid syntax, I assume that was a typo
// type safeMap = struct {
type pathMap struct {
    URLs *sync.Map // use the sync.Map type, safe for concurrent use, and has some useful features for us
    wg   *sync.WaitGroup // your remaining field is just tracking how many routines are running, aka a waitgroup
}

Right, so this type has changed a lot. I've swapped out the mutex + map for a sync.Map. This type is designed to be safe for concurrent access, and has a nifty function: LoadOrStore. It will make it easy for us to check if we've seen a URL before, and if not, we atomically add it to the list, and can spin up a routine to crawl said URL.
The remaining counter is just a manual way of tracking whether or not we've finished checking all the links, to then close the channel. Because we've gotten rid of the mutex, we would now be concurrently accessing this field. Something we don't want to do. Instead of faffing around with the atomic package, we can simply use the purpose-built WaitGroup type to achieve the exact same thing. Well, almost the same thing. The added bonus here is that we can outsource/delegate waiting for the work to be done to our caller, who can then close the channel, safe in the knowledge that all the work is done (and thus that no routine will be writing to the channel).
So let's start crawling (logically, that means taking a look at the Crawl function):
// StartCrawl short description in this format, which automates the godoc generated documentation
// we're returning the pageMap here, back to main so it can check for the waitgroup status
// I moved Fetcher to the front, because it's kind of the critical "thing"
// I've also changed the channel argument to a directional one.
// this ensures nobody mistakenly adds code reading from this channel later on, and shows intent
// I've also added a context argument, so you can cleanly exit on receiving a kill signal
func StartCrawl(ctx context.Context, fetcher Fetcher, URL string, depth int, ch chan<- string) *pageMap {
    c := &pageMap{ // assign pointer
        URLs: &sync.Map{},
        wg:   &sync.WaitGroup{},
    }
    // start crawling
    c.wg.Add(1) // adding 1 routine to the WaitGroup

    // passing on context, fetcher, pageMap, etc...
    // renamed crawl_init to crawl, this is basically the "init" function, after all
    go crawl(ctx, fetcher, c, URL, depth, ch)
    return c
}

These changes are pretty self-explanatory, although this entire function simply passes through the arguments you already had, and now returns the pageMap back to the caller. This function is, clearly, extraneous, so we could move this all up to our main function. We'll do that at the end. If you were to try and compile this, you'll get an error where we're passing the channel. This StartCrawl function takes a chan<- string argument (a write-only channel). the crawl function still expects a bi-directional channel (chan string). This isn't allowed, obviously. Because we want to make sure this channel isn't being read from, we've restricted it, and so we have to change the functions further down the call-chain, too. Let's do that now:
// func gci(){} is removed, it's a single call, wrapped in a function. this is inefficient, and silly

// change arguments to match our previous changes
func crawl(ctx context.Context, fetcher Fetcher, m *pageMap, URL string, depth int, ch chan<- string) {
    defer m.wg.Done() // when this routine returns, update waitgroup

    body, URLs, err := fetcher.Fetch(URL)
    if err != nil {
        ch <- fmt.Sprintf("Error fetching %s: %+v", URL, err) // add some more info
        return // we don't need to continue doing this here. get rid of the else
    }

    ch <- fmt.Sprintf("URL %s - %q\n found %d URLs", URL, body, len(URLs))
    // have we reached the "deepest" level?
    if depth <= 1 {
        return // we have, exit the routine
    }

    // we still have more levels to go
    for _, URL := range URLs {
        // LoadOrStore returns true if the key (URL) already existed, if not it's added to the map
        if _, ok := m.URLs.LoadOrStore(URL, nil); !ok {
            // we have a new URL
            m.wg.Add(1) // we need to crawl this new page, so add new routine to the waitgroup
            // spin up the new routine, depth -1
            go crawl(ctx, fetcher, m, URL, depth-1, ch)
        }
    }
}

So what we have here is a function that doesn't have to faff around with a mutex, doesn't have to use defer to spawn more routines, and doesn't contain a single else. We can just end our routine if an error occurs, or if we've reached the end of the depth/URLs we need to scrape. To my eye, at least, the code instantly looks a lot cleaner. Most importantly, though: we're not closing the channel in the routine that writes to it. Remember: channels can be shared between many routines (as indeed this channel is). To determine whether or not a channel is safe to be closed in one place, without it being aware of the existence of any of the other routines is tricky at best. So how do we know when to close this channel, and how can we wait for that moment, while still printing the output?
That's quite easily done if we change our main function:
func main() {
    ctx, cfunc := context.WithCancel(context.Background())
    defer cfunc()
    done := make(chan struct{})
    ch := make(chan string, 5)
    // start waiting for values to print
    go func() {
        for s := range ch {
            fmt.Println(s)
        }
        close(done) // we're done printing
    }()
    crawler := StartCrawl(ctx, fetcher, "https://golang.org/", 4, ch)
    crawler.wg.Done() // wait for the waitgroup to hit 0, indicating the work is done
    close(ch)   // close the channel now that the work is done
    <-done      // wait for printing to be done
    // all done, return from main
}

So that's it, then. We open and close the string channel in our main routine, read and print the data on our string channel in a dedicated routine, and use a simple 0-byte, non-buffered channel to force our main function to wait until everything is done so we can safely exit our program.
You may have noticed that this done channel is created in the scope of main, but closed in a routine, despite my having just said this isn't always a good idea. The difference here is that the channel never leaves the scope of main, and is closed in a closure that has full access to the main scope. It's pretty obvious that, unless you start to pass around this very done channel around to countless other routines, this is perfectly safe.
What's next
So I've added this context argument to your code, and at the moment, it's just sitting there, doing nothing but forcing us to type more stuff. That's a bit annoying, for sure. Why, then, would we bother adding it?
Put simply, if you run an application with many routines, it's reasonable to assume execution time can be variable, and sometimes it can take quite long for the application to finish doing whatever it's doing. Sometimes you (or your OS) may want to send a KILL or TERM signal to the process. In such an event, we want to be able to cleanly exit all the same: close the channels, stop doing what we're doing, etc... This is actually a very easy thing to do by cancelling the context. The context object basically can be used to store information about the context in which your application (or a subset thereof) runs. If the main process receives a kill signal, all routines should be notified, and should stop doing what they're doing. This is what that looks like in our code:
import(
    "context"
    "fmt"
    "os"
    "os/signal"
    "sync"
)

func main() {
    ctx, cfunc := context.WithCancel(context.Background())
    defer cfunc() // this ALWAYS needs to be called, multiple calls are fine
    sig := make(chan os.Signal, 1)
    // register channel so we get notified of kill/interrupt signals
    signal.Notify(sig, signal.Kill, signal.Interrupt)
    go func() {
        defer close(sig)
        select {
        case <-sig: // we've received a signal
            cfunc() // cancel the context
            return
        case <-ctx.Done(): // app terminated normally
            return
        }
    }()

    // this is the same as before
    done := make(chan struct{})
    ch := make(chan string, 5)
    go func() {
        for s := range ch {
            fmt.Println(s)
        }
        close(done)
    }()
    // no need for StartCrawl, let's just create it all in main
    crawler := &pageMap{
        URLs: &sync.Map{},
        wg:   &sync.WaitGroup{},
    }

    crawler.wg.Add(1)

    go crawl(ctx, fetcher, crawler, URL, depth, ch)

    crawler.wg.Done()
    close(ch)
    <-done
}

So we've gotten rid of the StartCrawl function, and added some code to set our program up to register signals (interrupt and kill) from our OS. When we get such a signal, the context is cancelled. Obviously, our crawl routine doesn't know about that just yet, so we have to make a few adjustments to the code there:
// write to channel, returns false if context is cancelled
func writeChan(ctx context.Context, s string, ch chan<- string) bool {
    // wait until either the context is cancelled, or we can write to the channel
    select {
    case <-ctx.Done():
        return false
    case ch <-s:
        return true
    }
}

func crawl(ctx context.Context, fetcher Fetcher, m *pageMap, URL string, depth int, ch chan<- string) {
    defer m.wg.Done() // when this routine returns, update waitgroup

    body, URLs, err := fetcher.Fetch(URL)
    if err != nil {
        _ = writeChan(ctx, fmt.Sprintf("Error fetching %s: %+v", URL, err), ch)
        return
    }

    // depth reached, or context cancelled -> return
    if ok := writeChan(ctx, fmt.Sprintf("URL %s - %q\n found %d URLs", URL, body, len(URLs)), ch); !ok || depth <= 1 {
        return
    }

    for _, URL := range URLs {
        if _, ok := m.URLs.LoadOrStore(URL, nil); !ok {
            select {
            case <-ctx.Done():
                return // context cancelled
            default:   // carry on as usual
                m.wg.Add(1)
                go crawl(ctx, fetcher, m, URL, depth-1, ch)
            }
        }
    }
}

Now in real life, whatever this Fetcher is you're using, it's most likely going to be using an net/http.Client under the bonnet. You would pass the context to this client, or include that context in the request you're sending. Internally, the context will abort the request if the context is cancelled, so everything returns as early as possible. In that case, I wouldn't bother adding the select checking if the context is done before spawning the new routine, but I thought I'd include it here just for completeness sake.
Disclaimer
I've gone through your code a couple of times, but it's possible I didn't catch everything (the fetcher part, I've sort of ignored). All the code I wrote as part of my review was written off-the-cuff, with no testing, so it may contain bugs, typos, omissions, etc... The key thing here was to explain how I'd write this type of code, why, and provide some code snippets to serve as a decent starting point/illustration of what the code eventually would look like.
Have fun.


Filtering conversation by filter type and value I have been assigned to developed a feature that filters a conversation. For example, I want to filter the conversation by user id then export it to something either JSON or text file. In this case, I created a class that handles the filters like this.

import java.util.ArrayList;
import java.util.List;

/**
 * Represents the filter that operates the filter functions for messages
 *
 * @author Muhammad
 */
public class Filter {

    String filterType;
    String argumentValue;

    //Constructor that takes a parameter of filter type and argument value.
    public Filter(String filterType, String argumentValue) {
        this.filterType = filterType;
        this.argumentValue = argumentValue;
    }

    //Method that filters a conversation by a specific user and return filterd conversation.
    public static Conversation filterByUser(Conversation conversation, String specificUser) {
        List<Message> messageList = new ArrayList<>();
        //Filter by used id
        for (Message message : conversation.messages) {
            if (message.senderId.equals(specificUser)) {
                messageList.add(message);
                Conversation filteredConversation = new Conversation(conversation.name, messageList);
                conversation = filteredConversation;
            }
        }
        return conversation;
    }

    //Method that filters a conversation that contains a specific keywod and returns filterd conversation.
    public static Conversation filterByWord(Conversation conversation, String specificWord) {
        List<Message> messageList = new ArrayList<>();
        //Filter by keyword
        for (Message message : conversation.messages) {
            if (message.content.contains(specificWord)) {
                messageList.add(message);
                Conversation filteredConversation = new Conversation(conversation.name, messageList);
                conversation = filteredConversation;
            }
        }
        return conversation;
    }

    //Method that hides a word in a conversation by a specificword
    public static Conversation hideWord(Conversation conversation, String specificWord) {
        List<Message> messageList = new ArrayList<>();
        //Filter by used id
        for (Message message : conversation.messages) {
            if (message.content.contains(specificWord)) {
                message.content = message.content.replaceAll(specificWord, "*redacted*");
                messageList.add(message);
                Conversation filteredConversation = new Conversation(conversation.name, messageList);
                conversation = filteredConversation;
            }
        }
        return conversation;
    }
}

In another class, I used it inside a method called filter like this.

private void filter(Filter filter, Conversation conversation, String outputFilePath) throws Exception {

        String filterType = filter.filterType; //used to get the type of filter
        String argumentValue = filter.argumentValue;

        //Filterers
        switch (filterType) {
            case "filteruser":
                conversation = Filter.filterByUser(conversation, argumentValue);
                this.writeConversation(conversation, outputFilePath);
                break;
            case "filterword":
                conversation = Filter.filterByWord(conversation, argumentValue);
                this.writeConversation(conversation, outputFilePath);
                break;
            case "hideword":
                conversation = Filter.hideWord(conversation, argumentValue);
                this.writeConversation(conversation, outputFilePath);
                break;
            default:
                this.writeConversation(conversation, outputFilePath);
                break;
        }

    }

This code works, however I'd like feedback on anyways that I can improve the code as I am just a graduate.

I want to mention only one thing especially:

You're using "magic string" to choose your filter types. Instead of doing that (because it's brittle) you are probably better off with an enum:

public enum FilterType {
    USER, WORD, HIDE_WORD
}

Your code would have to adjust a little, but to give a short look into the filter method:

private void filter(Filter filter, Conversation conversation, String outputFilePath) {
    switch (filter.filterType) {
        case FilterType.USER:
            conversation = Filter.filterByUser(conversation, filter.argumentValue);
            writeConversation(conversation, outputFilePath);
            break;
        case FilterType.WORD:
            conversation = Filter.filterByWord(conversation filter.argumentValue);
            writeConversation(conversation, outputFilePath);
            break;
        // ...

This exposes another small improvement possibility in your code.

In every case you will call this.writeConversation with exactly the same arguments. You can move that to outside the switch-case block:

switch (filter.filterType) {
    // ...
}
this.writeConversation(conversation, outputFilePath);

Another last thing I want to recommend is using Path intead of String to refer to outputFilePath. This makes it blatantly obvious, that you're  actually referring to a File. Strings are .. not Paths...


Project Euler #7: What is the 10,001st prime number? By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can
  see that the 6th prime is 13.

  What is the 10 001st prime number?

How can I make this more efficient and cleaner?

public class Problem7 {

    public static void main(String[] args) {
        // a prime factor is something that can divide by only 1 and itself evenly
        int counter = 0;
        int primeNum = 0;

        for (int num = 2; num < 10000000; num++) {
            boolean isPrime = true;
            for (int factor = 2; factor < num; factor++) {

                if (num % factor == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primeNum = num;
                counter++;
            }
            if (counter == 10001) {
                break;
            }
        }
        System.out.println(primeNum);
    }
}

More efficient... look at Sieve of Eratosthenes for a huge speed up. I'm ignoring it for now, as it comes again and again.

for (int num = 2; num < 10000000; num++) {

The condition num < 10000000 is plain wrong. It works, but makes no sense. If the requirements change, the limit may be too small. Just drop it. Or better, replace it by counter < 10001 (nobody says, that you have to test num, any condition is allowed).

You surely know that 4, 6, 8, ... are no primes, so you can skip them. Iterate over odd numbers only and set the initial value of counter equal to one (accounting for the skipped prime 2). So you get something like

for (int num = 3; counter < 10001; num += 2) {

This hardly helped the speed, but doing the same thing in

for (int factor = 2; factor < num; factor++) {

surely helps. You only have to deal with odd num, so you test only odd factors.

Observe that for each factor, also num / factor is a factor and the smaller of the two is no bigger than the square root of num. So you can use

int limit = (int) Math.sqrt(num);
for (int factor = 3; factor <= limit; factor += 2) {

        if (isPrime) {
            primeNum = num;
            counter++;
        }

This looks a bit strange. It works, but you assign primeNum just in case it'll be needed. A rather useless variable as num would do, too.

Even for such a rather trivial tasks you should use methods. Write small methods and let each of them do just one thing. Especially, never mix user input or output with computation as this makes the code perfectly non-reusable. Try to write methods like

boolean isPrime(int num);
int nextPrimeAbove(int num);
int nthPrime(int n);


Solving an unwieldy inheritance framework function I have a simple inheritance framework:

class BaseValidator
{
    protected virtual void Validate()
    {
        // Base validator code .....
    }
}
class PhoneValidator:BaseValidator
{
    public override void Validate()
    {
        base.Validate();
        // custom validation logic...
    }
}
class EmailValidator:BaseValidator
{
    public override void Validate()
    {
        base.Validate();
        // custom validation logic...
    }
}

The problem is in //custom validation logic. The more custom validation logic code that is written , the more unwieldy the
Validate() function becomes. I can organize custom validation logic into separate functions, but that would be another mess.

public override void Validate()
{
    base.Validate();
    CustomValidation1();
    CustomValidation2();
    CustomValidation3();
    ...
}

What are other patterns\practices that I can use to manage the Validate() function?  Sometimes I feel this is a the problem with inheritance, but suggestions are welcome in any direction.

Take a look at the specification pattern (pdf).

In particular, Microsoft has already implemented this kind of framework as part of one of their (old) application blocks. You can look there for many related ideas.


Password generator in python Here's a password generator I created.

### THIS PROGRAM WAS CREATED FOR LEARNING PURPOSES  ###
###   AND SHOULD NOT BE USED TO CREATE PASSWORDS!   ###

import string
from enum import Enum
from random import randint, shuffle, choice

class PasswordError(Exception):
    __module__ = Exception.__module__

# Types of characters possible
class Types(Enum):
    CAP = 'CAP' # Capital
    SMA = 'SMA' # Small
    DIG = 'DIG' # Digits
    SPE = 'SPE' # Special

# Characters for each type of possible characters
type_chars = {
    Types.CAP: string.ascii_uppercase,
    Types.SMA: string.ascii_lowercase,
    Types.DIG: string.digits,
    Types.SPE: '!()-.?[]_`~;:@#$%^&*='
}

def password_generator(min_length=6, max_length=20, caps=1, small=1, digits=1, special=1):
    types = {
        Types.CAP: caps,
        Types.SMA: small,
        Types.DIG: digits,
        Types.SPE: special,
    }

    num_chars = sum(list(types.values())) # Number of mandatory characters
    min_length = max(num_chars, min_length) # In case 'num_chars' is greater

    # Number of characters required for each possible type of character
    # Is greater than maximum possible length
    if min_length > max_length:
        raise PasswordError(f'No password with the given criteria')

    length = randint(min_length, max_length)

    # List that stores the "types" of possible character
    char_list = []

    # Mandatory requirements
    for typ, val in zip(types.keys(), types.values()):
        char_list.extend([typ] * val)

    # The remaining values to fill
    for rem in range(length - num_chars):
        char_list.append(choice(list(types.keys())))

    shuffle(char_list)

    password = ''

    for typ in char_list:
        password += choice(type_chars[typ])

    return password

if __name__ == '__main__':
    min_length = int(input('Minimum number of characters required: '))
    max_length = int(input('Maximum number of characters possible: '))

    print()

    caps = int(input('Number of capital letters required: '))
    small = int(input('Number of small letters required: '))
    digits = int(input('Number of digits required: '))
    special = int(input('Number of special characters required: '))

    print()

    number = int(input('Number of passwords required: '))

    print('\n' + '-' * 50 + '\n')
    print('   Here are your passwords: \n')

    for i in range(number):
        print(password_generator(min_length, max_length, caps, small, digits, special))

You can also modify the mandatory types of characters (Like 3 caps, 2 digits, etc). Also, minimum length and maximum length can be specified.

I think this code looks a bit ugly. How do I improve this?

The other answers have great hints that you should definitely follow.

However, since we are talking about passwords here, a little bit of extra security might not hurt. Especially if it's readily available in the secrets module in Python 3. secrets uses a cryptograhically strong random number generator (in contrast to the pseudo random number generator in the normal random module). There is a special warning in that regard in the docs of random. If you want to stick to random, at least use an instance of random.SystemRandom(), which is basically what secrets does. An example:

RNG = random.SystemRandom()

def password_generator(...):
    ...
    # The remaining values to fill
    type_ = list(types.keys())
    for rem in range(length - num_chars):
        char_list.append(RNG.choice(type_))
        # alternatively
        char_list.append(secrets.choice(type_))
    ...

random.choice uses what is called a pseudo-random number generator, i.e. an algorithm that generates a deterministic "randomly looking" sequence of bytes starting from a given seed. secrets.choice uses a randomness source implemented in the OS, which likely takes electrical noise and other things into consideration to generate non-deterministic random data. random.org has a comprehensive article on the differences at https://www.random.org/randomness/. And of course, there is also the obligatory Wikipedia page about Randomness.