Why is my Sieve of Eratosthenes using generators so slow This is my prime sieve based on the Sieve of Eratosthenes.
import itertools
sieve = itertools.count(2)
primes = []
nprime = 0
for _ in range(10000):
    nprime = next(sieve)
    primes.append(nprime)
    sieve = filter(eval(f"lambda x: x % {nprime} != 0"), sieve)

On my computer this code takes 13.4 seconds to generate 10,000 primes.

That's not the sieve of Eratosthenes
It's rather prime trial division.
Your filter for 2 lets 1/2 of all numbers through, your filter for 3 lets 2/3 of all remaining numbers through, etc. So 1/2 * 2/3 * 4/5 * 6/7 = 22% of all numbers make it through your filters for 2, 3, 5 and 7, so your filter for 11 will have to check 22% of all numbers. The real sieve of Eratosthenes treats 11 by marking off every 11th number, i.e., only 9% of all numbers. Less than half of your percentage. And yours gets worse for the larger primes. For example your filters for the primes from 2 to 89 let ~12% of all numbers through, so your filter for 97 checks ~12% of all numbers. While the real sieve of Eratosthenes treats 97 by marking off only about 1% of all numbers.
So that's why it's slow. It's doing way too much work.
An improvement
You can make it a bit faster by not stacking filters but simply doing the trial divisions at the current number, using the primes you're collecting anyway:
from itertools import count

def primes(n):
    primes = []
    sieve = (x for x in count(2) if all(x % p for p in primes))
    for _ in range(n):
        primes.append(next(sieve))
    return primes

Or using islice:
from itertools import count, islice

def primes(n):
    primes = []
    sieve = (x for x in count(2) if all(x % p for p in primes))
    primes += islice(sieve, n)
    return primes

Demo:
>>> primes(25)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

The real thing
But here's a genuine lazy one based on the paper mentioned by trentcl. I add each prime to the list of its next multiple. When the list of the next x is empty, it's thus a prime. Otherwise, I move the primes from the list to their next multiples.
from itertools import count
from collections import defaultdict

def primes(n):
    marked = defaultdict(list)
    primes = []
    for x in count(2):
        if x in marked:
            for p in marked.pop(x):
                marked[x + p].append(p)
        else:
            primes.append(x)
            if len(primes) == n:
                return primes
            marked[x * x].append(x)

Benchmark 1
Times for n = 10000 (benchmark code at the end of the answer):
9.330 s  original
3.502 s  improved1
3.499 s  improved2
0.065 s  genuine

That said, your original and my improved version can be made much faster by using fewer filters (only up to the square root of the current number), as I've done in my later answer.
To infinity and beyond
As Eric Duminil showed, it's trivial to make the latter an infinite generator, which also makes it shorter. No need to build a result list and check whether you're done, just yield the primes:
infinite:
def primes():
    marked = defaultdict(list)
    for x in count(2):
        if x in marked:
            for p in marked.pop(x):
                marked[x + p].append(p)
        else:
            yield x
            marked[x * x].append(x)

The other solutions can similarly be turned into infinite generators, but meh, they're no good anyway. Plus in my improved1 and improved2, the primes list is not just the result but is also used for filtering, so I need to build it anyway.
As infinite generator, it's more versatile. You can still get a list of the first n if you want to:
>>> list(islice(primes(), 20))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

You can also get all primes up to a desired limit:
>>> *itertools.takewhile(72 .__gt__, primes()),
(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71)

Or if you neither know how many you need nor how big you need but you need "enough" somehow, for example enough so that their product exceeds a million:
>>> result, product = [], 1
>>> it = primes()
>>> while product < 10**6:
        p = next(it)
        result.append(p)
        product *= p

>>> result
[2, 3, 5, 7, 11, 13, 17, 19]

Or if you just want the millionth prime:
>>> next(islice(primes(), 999999, None))
15485863

Or if you have a prime and want to know the "how manyth" prime it is:
>>> from operator import indexOf
>>> indexOf(primes(), 15485863) + 1
1000000

Or if you have a prime and want to know the next larger one (granted, there are more efficient ways to do that):
>>> it = primes()
>>> 89 in it and next(it)
97

Note that in the last few cases, you don't want a list of primes at all, so building one is wasted memory.
Speaking of memory, though... the generator (and also my version) do take a lot of memory. Here are memory measurements and benchmarks for up to n=1,000,000 for the above "infinite" solution and the solutions I'll show below:
            |     time for the first...    | tracemalloc for 1,000,000
            |  10,000   100,000  1,000,000 |     size         peak
------------+------------------------------+--------------------------
   infinite | 0.068 s   0.971 s   12.450 s |  231,866,275  312,793,599
   no_lists | 0.035 s   0.574 s    8.065 s |  143,870,959  226,554,527
     lazier | 0.033 s   0.456 s    6.016 s |   36,500,174   36,535,742
  recursive | 0.032 s   0.473 s    6.116 s |       72,169      109,109
    twostep | 0.015 s   0.217 s    2.897 s |       71,986      108,926

The memory usage was measured like this:
import tracemalloc
tracemalloc.start()
it = primes()
prime = next(islice(it, 9999999, None))
size, peak = tracemalloc.get_traced_memory()

So the above "infinite" solution takes hundreds of megabytes to generate the first million primes, i.e., hundreds of bytes per prime. Quite a lot. Let's see why, by doing global marked first thing in the primes() function so we can inspect it afterwards. We'll see that almost a million composites are marked and the dictionary takes 84 MB:
>>> it = primes()
>>> next(islice(it, 999999, None))
15485863
>>> from sys import getsizeof
>>> len(marked), getsizeof(marked)
(999919, 83886176)

The lists of primes total 88 MB, and almost all of them contain only a single prime marking the composite:
>>> sum(map(getsizeof, marked.values()))
87992872
>>> from collections import Counter
>>> Counter(map(len, marked.values()))
Counter({1: 999845, 2: 69, 3: 4, 4: 1})

The marked composites take 32 MB and the marking primes take 28 MB:
>>> sum(map(getsizeof, marked))
31983680
>>> from itertools import chain
>>> sum(map(getsizeof, chain.from_iterable(marked.values())))
27999972

Together that's indeed 232 MB as reported by tracemalloc in the table above:
>>> 84 + 88 + 32 + 28
232

Since most lists of marking primes just contain a single prime anyway, let's store only the first prime at the composite. If more primes want to mark that composite, then instead move them ahead to their next multiple:
no_lists:
def primes():
    marked = {}
    for x in count(2):
        if x in marked:
            p = marked.pop(x)
            while (x := x + p) in marked:
                pass
            marked[x] = p
        else:
            yield x
            marked[x * x] = x

As the above table showed, this made it faster and saved a lot of memory.
In my other answer, I showed that prematurely setting marked[x * x] as soon as you discover a new prime x is wasteful. Let's rewrite the better version from there as an infinite generator as well. Here m is the next marking prime, and it will start marking as soon as we reach m2=m2.
lazier:
def primes():
    yield 2
    primes = [2]
    markers = iter(primes)
    marked = {}
    m = next(markers)
    m2 = m * m
    for x in count(3):
        if x == m2:
            while (x := x + m) in marked:
                pass
            marked[x] = m
            m = next(markers)
            m2 = m * m
        elif x in marked:
            p = marked.pop(x)
            while (x := x + p) in marked:
                pass
            marked[x] = p
        else:
            yield x
            primes.append(x)

This brought it down to under 37 MB, as marked got much smaller. However, it creates a primes list again, in order to update m to the next next marking prime.
Can we get the best of both worlds? Not prematurely enter marked[x * x] and not build a primes list? Yes we can!
What do we use the primes list for? Just as a more slowly used stream of primes. But that's what we're writing! A generator of primes. So we can use it recursively. Our main generator iterator of primes will use a slower generator iterator of primes. But where does that slower one get its marker primes from? From yet another even more slowly progressing one, if needed. And so on. A potentially infinite stack of infinite iterators.
recursive:
(also see the addendum at the end of the answer for better versions of this)
def primes():
    yield 2
    marked = {}
    markers = primes()
    m = next(markers)
    m2 = m * m
    for x in count(3):
        if x == m2:
            while (x := x + m) in marked:
                pass
            marked[x] = m
            m = next(markers)
            m2 = m * m
        elif x in marked:
            p = marked.pop(x)
            while (x := x + p) in marked:
                pass
            marked[x] = p
        else:
            yield x

Let's see the levels by storing each iterator's marked in a global levels list by doing levels.append(marked) right after marked = {}. Then:
>>> levels = []
>>> millionth = next(islice(primes(), 999999, None))
>>> for marked in levels:
        print(len(marked), max(marked.values()))

546 3931
18 61
4 7
2 3
1 2

We see that there are five levels of iterators. The top-level iterator, the one we're using directly, has 546 marking primes, the largest being 3931. That makes sense, as the next larger prime is 3943, which starts marking at 39432, which is larger than the millionth prime:
>>> it = primes()
>>> 3931 in it and next(it)
3943
>>> 3943**2
15547249
>>> millionth
15485863

The next-lower level so far only needed to yield the 18 primes up to 61. Which is correct, as the next-larger prime 67 will only start marking at 672=4489, well above the prime 3943 needed next by the top-level iterator. And so on, until the fifth and lowest level only needed its initial yield 2 so far.
With only a few hundred primes in all levels combined, it's no wonder this solution takes faaar less memory than our first "infinite" one, about 3000 times less, only around 100 KB. And its advantage will increase for larger numbers of primes, as the earlier solutions need O(n) memory while the recursive ones take something like O(sqrt(n)) memory (not sure how the density of primes affects it).
Last but not least, here's a little variation where I handle the prime 2 separately and then move everything twice as fast, which makes the overall solution about twice as fast (again see the table above):
twostep:
def primes():
    yield 2
    yield 3
    marked = {}
    markers = primes()
    next(markers)
    m = next(markers)
    m2 = m * m
    for x in count(5, 2):
        if x == m2:
            marked[m2 + 2*m] = 2*m
            m = next(markers)
            m2 = m * m
        elif x in marked:
            step = marked.pop(x)
            while (x := x + step) in marked:
                pass
            marked[x] = step
        else:
            yield x

Code for benchmark 1:
from timeit import repeat
from itertools import count, islice
from collections import defaultdict

def original(n):
    sieve = count(2)
    primes = []
    nprime = 0
    for _ in range(n):
        nprime = next(sieve)
        primes.append(nprime)
        sieve = filter(eval(f"lambda x: x % {nprime} != 0"), sieve)
    return primes

def improved1(n):
    primes = []
    sieve = (x for x in count(2) if all(x % p for p in primes))
    for _ in range(n):
        primes.append(next(sieve))
    return primes

def improved2(n):
    primes = []
    sieve = (x for x in count(2) if all(x % p for p in primes))
    primes += islice(sieve, n)
    return primes

def genuine(n):
    marked = defaultdict(list)
    primes = []
    for x in count(2):
        if x in marked:
            for p in marked.pop(x):
                marked[x + p].append(p)
        else:
            primes.append(x)
            if len(primes) == n:
                return primes
            marked[x * x].append(x)

funcs = original, improved1, improved2, genuine

n = 10000

expect = funcs[0](n)
for func in funcs[1:]:
    print(func(n) == expect, func.__name__)

for _ in range(3):
    for func in funcs:
        t = min(repeat(lambda: func(n), number=1))
        print('%.3f s ' % t, func.__name__)
    print()

Addendum - better recursive generators
I came up with a nicer way later, don't want to rewrite the answer using this now but want to share. This goes through the primes of the underlying generator in an outer loop and from one prime's square to the next prime's square in an inner loop. It's less code and makes the structure of the procedure clearer.
def primes():
    yield 2
    marks = {}
    i = 2
    for p in primes():
        for i in range(i+1, p*p):
            if i not in marks:
                yield i
            else:
                m = marks.pop(i)
                j = i + m
                while j in marks:
                    j += m
                marks[j] = m
        marks[p*p] = p

And a version with the paper's way of potentially storing several primes at the same common multiple:
def primes():
    yield 2
    marks = defaultdict(set)
    i = 2
    for p in primes():
        for i in range(i+1, p*p):
            if i not in marks:
                yield i
            else:
                for m in marks.pop(i):
                    marks[i+m].add(m)
        marks[p*p] = {p}


Blocking until condition is met I have a class called _NodeProcess. It consists of a mainloop (main function) which is run in a separate process and methods (start and stop) that control the mainloop. Here's the code:

class _NodeProcess:
    def __init__(self, master):
        self.master = master
        self.process = multiprocessing.Process(target=self.main)
        self.is_alive = True
        self.is_dead = False

    def start(self):
        self.process.start()

    def stop(self):
        self.is_alive = False
        while not self.is_dead:
            pass

    def main(self):
        while self.is_alive:
            task = self.master.give_task()
            self.master.grab_result({'header': 'result', 'result': self.master.function(task), 'task': task})
        self.is_dead = True

The part that worries me is the stop function. On each mainloop iteration, I check whether I should continue (self.is_alive == True), and if I shouldn't, I stop and do self.is_dead = True to confirm that i had quit the loop. Meanwile, in the stop function, after setiing self.is_alive to False, and block until self.is_dead == True.

My concern is the way in which I block:

while not self.is_dead:
    pass

I'm afraid it may eat to much resources just iterating over that loop at a very high speed. So, I considered another option, using time.sleep:

import time

while not self.is_dead:
    time.sleep(1)

But it doesn't seem like a best way to block until some condition is met (I need an extra library; I lose 0.5 seconds on average when I call the stop method, if I make the period less, I spend more resources, so it's some kind of a compromise, which has to be made each time I write code like that). Is there a better solution for this particular problem, or maybe it's better to redesign the class in some way that would allow not facing this problem at all?

You don't need a self.is_dead. You simply need to block until the thread is complete. For that, we have join():

def stop(self):
    self.is_alive = False
    self.process.join()


Implementing a queue in C++ I'm trying to implement a really basic queue (as an array) in my computer science class and want some feedback on my logic/methodology.  the queue is not circular, it just includes the basic functions of enqueue/dequeue (along with the other obvious ones.) Please criticize and give feedback so I can educate myself on the best practices.

I was given this assignment as part of an entry level CS class. I was told not to make a circular queue. So this of course is not an efficient model by any means.. just a rough idea of what queues do.

what the code should do: users can add to the queue by moving forward the last element of the array, and "remove" items (they kinda still float around in memory though. remove isn't a great word) by moving the first element forward.

Class declaration:

class queueList
{
private:
    int *list;
    int queueFront;
    int queueRear;
    int maxSize;

public:
    void enqueue(const int &x);
    bool isEmpty();
    bool isFull();
    void dequeue();
    queueList(const int &x);
    int front();
    int back();
};

class implementation:

queueList::queueList(const int &x)
{
    list = new int[x];
    queueRear = 0;
    queueFront = 0;
    maxSize = x;
}
void queueList::enqueue(const int &x)
{
    if (!isFull())
    {
        list[queueRear] = x;
        //cout << list[queueRear] << endl;
        queueRear++;
    }
}
bool queueList::isEmpty()
{
    return (queueFront == queueRear);
}
bool queueList::isFull()
{
    return (queueRear == maxSize);
}

void queueList::dequeue()
{
    if (!isEmpty())
    {
        list[queueFront] = 0;
        cout << list[queueFront] << endl;
        queueFront++;
    }
}

int queueList::front()
{
    return list[queueFront];
}

int queueList::back()
{
    return list[queueRear];
}
```

Use std::size_t for container sizes and indices, not int.

std::size_t queueFront;
std::size_t queueRear;
std::size_t maxSize;

Use meaningful variable names. When I use your constructor, what does "x" mean? Something like queue_size is more meaningful. This can also be a std::size_t. This also doesn't need to be a reference, since it's likely the same size as a pointer, but feel free to continue passing as reference if you want. You just normally don't see that with primitive types.

queueList(std::size_t queue_size);

Similarly, pick a meaningful name for your enqueue function. Even something like value carries more meaning than x. This should NOT be a std::size_t, since obviously you do want to insert an int into your int array.

Handle the special case in your constructor where the passed-in size is 0 or less. It won't be less than 0 if you switch to size_t, but it can still be 0. Do you want to allow this? How do you manage the memory? Calling new int[0]; is undefined behavior. Also, use initializer lists when possible for constructors. It prevents variables from being double-assigned and objects from being double-constructed. You won't notice any speedup on this problem, but it's a good habit to get into.

queueList::queueList(std::size_t queue_size)
  : list(queue_size > 0 ? new int[queue_size] : nullptr)
  , queueRear(0)
  , queueFront(0)
  , maxSize(queue_size)
{ }

Explicitly delete your default constructor to avoid ambiguity.

queueList() = delete;

Your constructor manages a resource (memory allocated with new), so you must also declare a destructor that deletes the memory. Since you must declare a destructor, you must follow at LEAST the rule of 3 and define a copy constructor and a copy assignment operator. A best practice would be to follow the rule of 5 (same link as rule of 3) and define additionally a move constructor and move assignment operator.

They key with all of these is: what does it mean to create a copy of your queue? What does it mean to move your queue? Most of these questions will have to do with managing the underlying allocated memory.

~queueList() { delete[] list }; // destructor
queueList(const queueList& other); // copy constructor
queueList& operator=(const queueList& other); // copy assignment operator
queueList(queueList&& other); // move constructor
queueList& operator=(queueList&& other); // move assignment operator

Your queue is currently one-time-use. It can only ever hold queue_size (x in your code) elements ever. It can't hold more elements than what you initially allocate. The latter is surmountable, but you should make it a goal to allow the queue to grow (or have a policy of throwing some error, or letting the user know through documentation that excess values will be lost). The one-time usability of each data slot is CRIMINAL though. My suggestion is to allow queueRear and queueFront to wrap around the array using modulo arithmetic as they move to the right.

dequeue should return a value!!! This is a huge shock to anyone who will try to use your class. They don't always want to print the value. They likely want to use it in some future calculation. This is easy. However, your current code doesn't even print the current value. It just always overwrites it with 0, then prints 0. This also decouples your class from requiring iostream to work.

Change your dequeue to look like this:

int queueList::dequeue()
{
    if (isEmpty())
    {
        // figure out what to do here.
        // Throw an error? Seems appropriate.
        // Another option is to return a std::pair<int, bool>,
        // where the second value indicates whether there were
        // any items in the queue
    }
    int retval = list[queueFront++];
    queueFront = queueFront % maxSize; // talking about modulo arithmetic earlier
    return retval;
}

Your isEmpty() and isFull() functions can have their prototypes modified to be const, since neither modify the object:

bool isEmpty() const
{
    ...
}

bool isFull() const
{
    ...
}


A regular expression parsing library in C I've created a regular expression (regex) parsing library in C, and would like some feedback on it.  Speed is really important to me, but any and all suggestions are acceptable.

#include <ctype.h>

static int regex_matchHere(const char *regex, char *s, int *len);
static int regex_matchGroup(int c, int group);
static int regex_matchQuantity(int quant, int c, const char *regex, char *s, int *len);

int regex_match(const char *regex, char *s, int *len)
{
    char *p = s;

    /* force match from the beginning of the string */
    if (regex[0] == '^') return (regex_matchHere(regex + 1, s, len) ? 0 : -1);

    /* iterate the string to find matching position */
    do
    {
        *len = 0;
        if (regex_matchHere(regex, p, len)) return (int)(p - s);
    } while (*p++ != '\0');
    return -1;
}

static int regex_matchHere(const char *regex, char *s, int *len)
{
    int c = regex[0];

    if (regex[0] == '\0') return 1; /* end of regex = full match */
    else if (regex[0] == '$' && regex[1] == '\0') return (*s == '\0'); /* check end of string */
    else if (regex[0] == '\\' && regex[1] != '\0') /* check escaped symbol */
    {
        c = regex[1];
        if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') c = c | 0x100;
        regex = regex + 1;
    }
    /* check for special operators *,+,?,- */
    if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') return regex_matchQuantity(regex[1], c, regex+2, s, len);
    else if (*s != '\0' && regex_matchGroup(*s, c))
    {
        *len = *len + 1;
        return regex_matchHere(regex+1, s+1, len);
    }
    return 0;
}

static int regex_matchGroup(int c, int group)
{
    if ((group & 0xff) == '.') group ^= 0x100;
    if (group < 0x100) return c == group; /* a single char */
    /* a meta char, like \d, ... */
    switch (group & 0xff)
    {
        case 'd': return isdigit(c);
        case 's': return isspace(c);
        case 'D': return !isdigit(c);
        case 'S': return !isspace(c);
        case '.': return 1;
    }
    return 0;
}

static int regex_matchQuantity(int quant, int c, const char *regex, char *s, int *len)
{
    if (quant == '?')
    {
        if (regex_matchGroup(*s, c))
        {
            *len = *len + 1;
            s = s + 1;
        }
        return regex_matchHere(regex, s, len);
    }

    if (quant == '+' || quant == '*') /* match as much as possible */
    {
        char *p;
        for (p = s; *p != '\0' && regex_matchGroup(*p, c); p++) *len = *len + 1;
        if (quant == '+' && p == s) return 0;
        do
        {
            if (regex_matchHere(regex, p, len)) return 1;
            *len = *len - 1;
        } while (p-- > s);
    }
    else if (quant == '-') /* match as little as possible */
    {
        do
        {
            if (regex_matchHere(regex, s, len)) return 1;
            *len = *len + 1;
        } while (*s != '\0' && regex_matchGroup(*s++, c));
    }
    return 0;
}

What you did well

The code seems clean and logically organized.  I like your 0x100-bit hack to indicate special characters.  You could make that convention more obvious in the comments, though.

What you could improve on

The return value of regex_match() is weird.  I'd like it to return a non-zero value if the match succeeded, and a zero value if the match failed, so that I can call it like this:

if (regex_match(...)) {
    // Do stuff for successful match
} else {
    // Do stuff for failed match
}

Trying to return the position of the match just leads to confusion, reminiscent of the way PHP's strpos() returns 0 to indicate a successful match at the beginning of the subject (but FALSE to indicate a non-match).  You don't want to be like PHP, do you?

I suggest that the signature for regex_match() should look like this:

/**
 * Returns 1 if matched, 0 if not matched.
 *
 * Pass a pointer to a match_result if you care to find out the
 * details of the match (its length, position, and possibly other
 * information supported in the future, such as parenthesized
 * capture groups), or pass a NULL if you don't care about the details.
 */
int regex_match(const char *regex, const char *subject, struct match_result *result);

Alternatively, return a pointer to a new struct match_result if the match succeeded.  The caller would have to free() the result later, though, so I don't like it as much.
Regular expressions often include modifier flags, such as a case-insensitive flag or a continue-searching-where-the-previous-match-ended flag.  You might want to plan your interfaces accordingly.  (To support the latter, the struct match_result* would probably become an in-out parameter rather than an out-parameter.)
For performance, regular expressions are frequently compiled into an automaton.  You interpret the regular expressions as you go.  You may wish design the library's interface to have a regex_compile() function that transforms the expression into a struct that is meaningful to your library but opaque to the user.  For now, the "compilation" could just be the identity transformation; you can enhance it later when the need for better performance arises or when you enhance the feature set of the regular expressions.
The function name regex_matchGroup() confuses me.  "Group" implies something like parentheses, I think.  regex_matchAtom() might be a more appropriate name.
You need unit tests!


Charting daily balance I have been trying my hand at Python lately. I have been able to look at code examples and create a custom application that queries a Microsoft SQL Server, pulls out two columns (date, balance) and charts them using pyplot embedded in tkinter for future development.

Because of the "chop and change" nature in which I wrote the code, I know there are plenty of bad practices and am looking for some constructive advice!
(I have removed the SQL script as it is huge)

import pymssql
import getpass
import matplotlib

matplotlib.rcParams['toolbar'] = 'None'
matplotlib.use('TkAgg')

import numpy as np
import tkinter as Tk
import matplotlib.dates as mdates
from matplotlib.figure import Figure

from matplotlib.ticker import FuncFormatter
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg

def movingaverage(dvalues,window):
    weights = np.repeat(1.00,window)/window
    values = [float(val) for val in dvalues]
    sma = np.convolve(values, weights, 'valid')
    return sma

root = Tk.Tk()
root.wm_title("Daily balance tracker")

f = Figure(figsize=(10, 7), dpi=75)
a = f.add_subplot(111)

server = "RHYSPC"
user = "rhys"
password = getpass.getpass("Please enter password: ")
print("Loading results, please wait...")

conn = pymssql.connect(server, user, password, "RhysACC")

cursor = conn.cursor()

cursor.execute("""
SELECT Date, Balance FROM Example -- Not the actual query!
""")

results = cursor.fetchall()

x = [i[0] for i in results]
y = [i[1] for i in results]

yMA = movingaverage(y,31)

j = [0] * len(x)

conn.close()

def pounds(x, pos):
    return '£%1.0d' % x

formatter = FuncFormatter(pounds)

f.gca().xaxis.set_major_formatter(mdates.DateFormatter('%m/%Y'))
f.gca().xaxis.set_major_locator(mdates.YearLocator())
f.gca().yaxis.set_major_formatter(formatter)

a.plot(x, j, color='k', linewidth=2.0)
a.plot(x, y, color='b', linewidth=1.0)
a.plot(x[len(x)-len(yMA):], yMA, color='r', linewidth=1.5)

canvas = FigureCanvasTkAgg(f, master=root)
canvas.show()

canvas._tkcanvas.pack(side=Tk.TOP, fill=Tk.BOTH, expand=1)

Tk.mainloop()

Using % for string formatting is deprecated, you should be using str.format instead. The str.format methods also allows you to do some cool things as well. Here's an example of it in action:

# No positional or named arguments
print "{} {}".format("Hello", "world")

# Positional arguments (*args)
print "{1} {0}".format("world", "Hello")

# Named arguments (**kwargs)
print "{word1} {word2}".format(word1="Hello", word2="world")

When running the line Tk.mainloop(), you should encapsulate it in an if __name__ == "__main__": block. See this Stackoverflow question for more details.

These two lines should be moved underneath all of your imports/includes:

matplotlib.rcParams['toolbar'] = 'None'
matplotlib.use('TkAgg')

I'm also noticing your lack of comments as well. Even if this is a small utility script, I'd still recommend adding comments for clarity.

Finally, a few of your variable names confuse me. For example, f, a, and j are all good examples of names that could be better. Try seeing if you can expand on these.


Method to replace all spaces in a String with '%20' Problem statement (extracted from cracking the coding interview):

Write a method to replace all spaces in a string with'%20'. You may assume that
the string has sufficient space at the end of the string to hold the additional
characters, and that you are given the "true" length of the string. (Note: if implementing
in Java, please use a character array so that you can perform this operation
in place.)

EXAMPLE
Input: "Mr John Smith

Output: "Mr%20Dohn%20Smith"

My Solution:

public class InterviewMain {

    public static void main(String[] args){

        //Q 1.4
        String str = "Example String with spaces           ";
        replaceSpaces(str);
    }

    public static void replaceSpaces(String str){

        int trueLength = getTrueLength(str);

        char[] strChar = str.toCharArray();
        int spaceCount = 0;
        int finalLength;

        //count the number of spaces in the original string
        for (int i=0; i<trueLength; i++){
            if (strChar[i]== ' ')spaceCount++;
        }

        //get the length of final char array
        finalLength = trueLength + spaceCount*2;
        char[] finalArr = new char[finalLength];

        //update final array here
        int spaces = 0;
        char temp;
        int index;

        for (int i=0; i < trueLength; i++){
            temp = strChar[i];

            if (temp==' '){
                finalArr[getInsertIndex(i,spaces)]= '%';
                finalArr[getInsertIndex(i+1,spaces)] = '2';
                finalArr[getInsertIndex(i+2,spaces)] = '0';
                spaces++;
                continue;
            }

            index = getInsertIndex(i,spaces);
            finalArr[index] = temp;
        }

        //print results here
        for (int i=0; i < finalLength; i++){
            System.out.print(finalArr[i]);
        }
    }

    private static int getTrueLength(String str) {
        int count=0;
        int length = str.length();
        char[] strChar = str.toCharArray();

        //backtrack from end of string to count padding
        for (int i=length-1; i >=0; i--){
            if (strChar[i]!= ' ')break;
            count++;
        }
        return length-count;
    }

    private static int getInsertIndex(int i, int spaces){
        return (i + spaces*2);
    }
}

I was wondering if someone could review this and point out what I have done right and where I can improve upon. Thank you

It's important to pay attention to every bit of detail in the problem description:

  Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)

As you're implementing this in Java, your method should receive a char[] instead of a String. And if I interpret correctly, the "true" length is the length without the padding, and is an additional parameter, giving the signature:

void replaceSpaces(char[] input, int trueLength) { ... }

With this established, the implementation can be simplified:

No need for getTrueLength: it's a given
No need for calculating the final size, it's given by input.length

As @rolfl pointed out, the size of input is not 100% clear. The description only states that it has sufficient space. So indeed, we may need to calculate the final size.

The printing is unnecessary and should be removed, as it breaks the single responsibility of the method

Another improvement in the implementation is that you don't need to count the spaces. You can walk backward, tracking two positions in parallel:

The last position to write to (starts at input.length - 1)
The last position in the text (starts at trueLength - 1)

Walk backward as long as the text position is smaller than the end position. If you see a space, overwrite the the values at the position with %20. Otherwise simply copy the input.

void replaceSpaces(char[] input, int trueLength) {
    //int end = input.length - 1;
    int end = trueLength + (countSpaces(input, trueLength) * 2) - 1;
    for (int textEnd = trueLength - 1; textEnd < end; textEnd--) {
        if (input[textEnd] == ' ') {
            input[end--] = '0';
            input[end--] = '2';
            input[end--] = '%';
        } else {
            input[end--] = input[textEnd];
        }
    }
}


Reading 8 divs across the screen depending on assignment time This code takes 8 divs and races them across the screen depending on which time value the div was assigned. How can I have coded this better so my code doesn't look so amateurish?

I know I should have used something other than a hard coded 8 in my for-loop, but timeArray.length is unavailable since I am removing items from the array with splice.

$(document).ready(function() {
var timeArray = new Array(3,4,5,6,7,8,9,10);
var shortestTime = timeArray[7];
var fastestPony = {};
var index;

var pony = {
    name: "pony",
    raceTime: -1,
    selected: ""
};

//change the color of the pony when the user clicks on it
$('.pony').bind('click', function() {
    $('.pony').removeClass('selectedPony');
    $(this).addClass('selectedPony');

    //get the pony that the user selected
    pony.selected = $(this);
});

$('#startButton').click(function() {
    if (pony.selected == "") {
        alert("Please click the pony you think will win the race.");
    }
    else {
        for (i = 1; i <= 8; i++) {
           //get a random number from the timeArray
            index = Math.floor(Math.random() * timeArray.length);
            pony.raceTime = timeArray[index];

            //pull the random race time number out of the array
            //so it can't be assigned to another horse
            timeArray.splice(index, 1);

            //get the fastest pony
            if (pony.raceTime < shortestTime) {
                shortestTime = pony.raceTime;
                fastestPony = $('#pony' + i);
            }

            //award the winner after the ponies have reached the finish line
            if (i == 8) {
                fastestPony.addClass('winner').append(' - Winner!');
            }

            //send the horses on their way to race!
            $('#pony' + i).animate({left: '320px'}, pony.raceTime * 1000);
        }
    }
});

//reset the ponies back to the starting line by reloading the page
$('#resetButton').click(function() {
    document.location.reload(true);
});
});

Note: As I type "pony" and "ponies" in my code, I can't help but wonder what the hell I'm doing with my time. Never thought I'd be writing words like that in javascript...

Anyway! My first suggestion would be to make everything more flexible bynot relying on element IDs, and a set number of DIV elements. If you add or remove one, you'll have to make sure its ID is numbered correctly, and update your code to match. Much easier to just use jQuery to find and animate the DIVs, regardless of how many there are.

In fact, the elements plus jQuery can tell you everything you need to know, so there's no need to store anything along the way.

Also, the reset functionality is trivial. No need reload the entire page just for that.

Lastly, and perhaps most importantly, you code announces the winner immediately - before the poni-- ahem, the DIVs have even raced. Yes, the winner is picked right away, and it's kinda' obvious which one will reach the goal first, but still. Better to announce the winner when it crosses the finish line.

Of course, overall it'd be more fun to have something more random, where the DIVs move in fits and starts, so you can't tell who's going to win until the very end. But I'll stick to refactoring your current code.

Here's a demo of my version and here's the code:

$(function() { // just pass in a function; it's the same as using $(document).ready()
  var ponies = $(".pony"), // Again: I never thought I'd write "ponies" in code
      raceButton = $("#raceButton"); // use a single button for race and reset

  ponies.click(function (event) {
    ponies.removeClass('selected');
    $(this).addClass('selected');
    // no need to store the selection; we can always find it, now that it's got a "selected" class
  });

  // use one button for both start and reset
  raceButton.click(function() {
    // If we have a winner, the race is pretty much over
    // If we have no winner, and no elements currently animating, we're ready to race
    // Otherwise we're racing; don't do anything

    if( ponies.filter(".winner").length !== 0 ) {
      reset();
    } else if( ponies.filter(".winner, :animated").length === 0 ) {
      race();
    }
  });

  function race() {
    // check for selection
    if( ponies.filter(".selected").length === 0 ) {
      alert("Please click the pony you think will win the race.");
      return; // return here instead of having a big else-block
    }

    var times  = [], i, l;

    // disable the race button
    raceButton.prop("disabled", true);

    // build time array; don't hardcode it
    for( i = 0, l = ponies.length ; i < l ; i++ ) {
      times.push(i);
    }

    // Use .each() instead of relying on all the divs having numbered IDs.
    ponies.each(function () {
      var index = Math.floor(Math.random() * times.length),
          time  = times[index],
          pony  = $(this);

      times.splice(index, 1);

      // Use the onComplete callback to identify the winner
      pony.animate({left: '320px'}, {
        duration: (time + 3) * 1000, // only here do we set the minimum time by adding 3
        complete: function () {
          // If this was the fastest one
          if( time === 0 ) {
            pony
              .addClass("winner")
              .append("Winner!"); // use a span or something, so it's easier to remove later

            // alert the gambler and enable the reset button
            if( pony.hasClass("selected") ) {
              alert("You win tons of money or something");
            } else {
              alert("You lost. Boo-hoo");
            }
            raceButton.prop("disabled", false).val("Reset");
          }
        }
      });
    });
  }

  // just reset everything yourself; no need to reload
  function reset() {
    ponies
      .stop()                  // stop any running animations
      .removeClass("selected") // clear selection
      .removeClass("winner")   // clear winner
      .css({ left: '0px' })    // move 'em back
      .children("span").remove(); // remove the label
    raceButton.val("Race!");
  }
});

Addendum: As Sridhar points out in the comments, you there are some issues with the code above. Both are related to the state of the race, so one way to deal with it is to extract a few functions that check the state:

function raceInProgress() {
  return ponies.filter(":animated").length > 0;
}

function raceDecided() {
  return ponies.filter(".winner").length > 0
}

function raceNotStarted() {
  return !raceInProgress() && !raceDecided();
}

Now we can make sure that the gambler can't change the selection mid-race, by simply checking raceInProgress(). Plus, it's much easier to read and use than the raw jQuery selector magic.

I've made the changes in this demo rather than bothering to rewrite my original answer.


Caesar Cipher → Bzdrzq Bhogdq I wrote this Caesar cipher and decipher just for the sake of practising OOP (previous answers to my java questions all seem to point to OOPness).

What it is:

  The Caesar cipher is one of the earliest known and simplest ciphers.
  It is a type of substitution cipher in which each letter in the
  plaintext is 'shifted' a certain number of places down the alphabet.

Currently I have a Cipher interface and a CaesarCipher class: I am planning to add a Vigenère Cipher soon.

Code:

Cipher.java

public interface Cipher {

    public String cipher(String text);

    public String decipher(String cipherText);

    public char getCipheredChar(char textChar);

    public char getDecipheredChar(char cipherChar);

}

CaesarCipher.java

public class CaesarCipher implements Cipher {

    private static final int LETTERS = 'Z' - 'A' + 1;

    private int shift;

    public CaesarCipher(int shift) {
        if (shift < -LETTERS || shift > LETTERS) {
            throw new IllegalArgumentException("The value of shift: " + shift
                    + " is invalid.");
        }
        this.shift = shift;
    }

    public int getShift() {
        return shift;
    }

    @Override
    public String cipher(String text) {
        char[] result = text.toCharArray();
        for (int i = 0; i < result.length; i++) {
            result[i] = getCipheredChar(result[i]);
        }
        return new String(result);
    }

    @Override
    public String decipher(String cipherText) {
        this.shift = -shift;
        String result = cipher(cipherText);
        this.shift = -shift;
        return result;
    }

    @Override
    public char getCipheredChar(char textChar) {
        if (textChar > 'A' && textChar < 'z') {
            char result = (char) (textChar + shift);
            char compare = Character.isUpperCase(textChar) ? 'Z' : 'z';
            char lowCompare = Character.isUpperCase(textChar) ? 'A' : 'a';
            return (char) (result > compare ? result - 26
                    : (result < lowCompare ? result + 26 : result));
        }
        return textChar;
    }

    @Override
    public char getDecipheredChar(char cipherChar) {
        this.shift = -shift;
        char result = getCipheredChar(cipherChar);
        this.shift = -shift;
        return result;
    }

}

And tests!

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TestCipher {

    @Test
    public void testShift1() {
        CaesarCipher cipher = new CaesarCipher(1);
        assertEquals("AaBbCc", cipher.decipher("BbCcDd"));
        assertEquals("Bzdrzq", cipher.decipher("Caesar"));
        assertEquals("Bzdrzq Bhogdq...", cipher.decipher("Caesar Cipher..."));
    }

    @Test
    public void testShift5() {
        CaesarCipher cipher = new CaesarCipher(5);
        assertEquals("AaBbCc", cipher.decipher("FfGgHh"));
        assertEquals("Xvznvm", cipher.decipher("Caesar"));
        assertEquals("Xvznvm Xdkczm...", cipher.decipher("Caesar Cipher..."));
    }

}

Concerns:

Are my tests fine?
Is my OOP structure good?
And as usual, anything else?

A few comments about your Cipher interface:

A cipher is an algorithm to encrypt something, so your cipher method should be renamed to encrypt. To match encrypt, you should change decipher to decrypt.
getCipherChar and getDecipheredChar is only really applicable to a few ciphers and not to a general cipher. For example, in the Viginere cipher, the encrypted character depends on the relative position compared to the repeated key. Therefore you can't tell what the result will be without additional information regarding where it is in the string. Other algorithms are more complex. These methods can still be used internally in CeasarCipher, but should be removed from the Cipher interface.

Regarding CeasarCipher:

Chars aren't just A-Z and a-z, and the Cipher interface is a guarantee that you will encrypt/decrypt an arbitrary string. Currently any other character stays the same, which is not what the Ceasar cipher is. Therefore you should change your code to just increment a char's value by the shift, modulo Character.MAX_VALUE, with some care as a negative shift could lead to a negative modulo which can be fixed by calculating the final char as described in the following code:

char shiftedChar(char c, int shift):
    int ROLLOVER = Character.MAX_VALUE;
    return (((c + shift) % ROLLOVER) + ROLLOVER) % ROLLOVER;

Alternatively you could specify some sort of Alphabet type (which should be something like a List<Character>) which restricts the subset of Character's that you are interested in.


Web scraping and downloading manga I'm new to Python and decided to work on a personal project and make a program that web scrapes and downloads manga. It works as expected, however, I am sure that there is a better way to structure my code. I'd appreciate some guidance on how to better write this project. You can check it out on my GitHub here.

import threading
import requests
import os
import re
import queue

from bs4 import BeautifulSoup
from display import Display

def gen_title(link):
    """Finds title of manga and removes any illegal characters"""
    page = requests.post(link, data=dict(adult="true"))
    soup = BeautifulSoup(page.text, 'lxml')

    title = soup.find('h1', {"class": "hb dnone"}).find('a').get('title')

    # Search for invalid characters and remove them.
    return re.sub('[^A-Za-z0-9 ]+', '', title)

def get_volume(soup):
    """Finds volume num"""
    volume = soup.find('h1', {"class": "hb dnone"}).findAll('a')
    volume = volume[1].get('title')

    # Grab first number in title
    temp = re.findall('\d+', volume)
    return "Volume " + temp[0]

def write_image(image, title, volume, counter):
    """Writes image to a file"""
    # Write the image to a file in chapter directory
    imagefile = open(title + "/" + volume + "/" + str(counter) + ".png", 'wb')
    imagefile.write(image.content)
    imagefile.close()

def download_manga(start_link, end_link=""):
    """given a start link and end link from twistedhelscans.com, downloads all manga images"""
    next_link = start_link
    counter = 1

    # Deal with end link being first page
    if end_link.endswith('1'):
        end_link = end_link[:-6]

    # get title of manga
    try:
        title = gen_title(start_link)
    except:
        queue.put("Title not found")
        return

    while next_link != end_link:
        # Open initial page
        page = requests.post(next_link, data=dict(adult="true"))

        # check if end link is first page redirect
        if page.url == end_link:
            break

        queue.put(page.url)
        soup = BeautifulSoup(page.text, 'lxml')

        if not end_link:
            end_link = soup.find('h1', {"class": "hb dnone"}).find('a').get('href')

        # Find image link and vol. num
        try:
            volume = get_volume(soup)
            image = soup.find('div', {"class": "inner"}).find('img').get('src')
        except:
            queue.put("Could not find image link. Website is not Twisted Hel Scan page?")
            return

        # Download the image
        image = requests.get(image)

        # Make manga directory
        if not os.path.exists(title):
            os.mkdir(title)

        # Make volume directory
        if not os.path.exists(title + "/" + volume):
            os.mkdir(title + "/" + volume)
            counter = 1

        # Write image to file
        write_image(image, title, volume, counter)
        counter += 1

        # Find next link
        next_link = soup.find('div', {"class": "inner"}).find('a').get('href')
    queue.put("Done")

def on_click(window):
    """Fetches text from entries and calls download manga"""
    start_link = window.start_entry.get()
    end_link = window.end_entry.get()

    if not start_link.strip():
        queue.put("No start link given")
        return

    def callback():
        download_manga(start_link, end_link)

    t = threading.Thread(target=callback)
    t.start()
    display.progress.pack(fill='x')
    display.progress.start(15)

def periodic_call():
    """
    Check every 100 ms if there is something new in the queue.
    """
    display.process_incoming()
    display.root.after(100, periodic_call)

# Create window and bind go button
queue = queue.Queue()
display = Display(queue)
display.go_button.bind("<Button-1>", lambda x: on_click(display))
periodic_call()
display.root.mainloop()
os._exit(1)

Welcome to Code Review. That is pretty useful tool. :) From the GitHub link, I notice that you're using Python 3. There are a few things, I think you'd benefit from:

Reorder your imports so that Python's library is imported first, followed by 3rd party modules; followed by your local display module. Read also the PEP-8 guide for the same.
Since you're combining requests and beautifulsoup4, I would suggest looking into Kenneth's yet another awesome project requests-html. You can have a single session to download the entire chapter/volume :)
Place your display initialisation code block inside the if __name__ == "__main__" clause.
You send a request more than once for the same page. First to get the page title, and later to actually start downloading images. Doing an HTTP request is heavy work. Do it once.
This looks ugly: open(title + "/" + volume + "/" + str(counter) + ".png", 'wb'). Use the with context block, and string formatting (python 3.6+):

with open(f"{title}/{volume}/{counter}.png", 'wb') as imagefile:
    imagefile.write(image.content)


Simple python calculator I'm very new to Python, and so I'm trying to learn it by doing simple programs, like a calculator. But I don't know if this is the "Pythonic" way to do it, or if I am making beginner errors.

So could someone please tell if something is wrong with it, and how to improve it?

Here is some sample input and output:

Enter the first number: 2
Enter the second number: 10
Enter an operator (valid operators are +, -, *, / and pow): pow
1024.0

Here is the code

#A basic calculator which supports +, -, *, / and pow

def add(a, b):
    return a + b

def sub(a, b):
    return a - b

def mul(a, b):
    return a * b

def div(a, b):
    return a / b

def pow(a, b):
    return a ** b

if __name__ == "__main__":
    while True:
        try:
            number1 = float(input("Enter the first number: "))
            number2 = float(input("Enter the second number: "))
        except:
            print("That is not a number!")
            continue

        operator = input("Enter an operator (valid operators are +, -, *, / and pow): ")

        #Check if user operator is a valid one
        if operator == "+":
            func = add
        elif operator == "-":
            func = sub
        elif operator == "*":
            func = mul
        elif operator == "/":
            func = div
        elif operator == "pow":
            func = pow
        else:
            print("Invalid operator!")
            continue

        #Print result
        print(func(number1, number2))

For a beginner this is pretty good.
But, there are three glaring problems with it.

You should use a 'main' function.
You should use a dictionary.
operators

Starting with (2), a dictionary holds a key value pair.
If you've come across lists/arrays, it's like them,
apart from that you can use a lot of different types,
not just integers.

Defining one is pretty easy,
and using it will reduce your amount of code.

operators = {
    "+": add,
    "-": sub,
    "*": mul,
    "/": div,
    "pow": pow
}

This will define an object to hold all the operators that you can use.
Now all we need to do is use it.
Using operators.get it's easy.

func = operators.get(operator, None)
if func is None:
    print("Invalid operator!")
    continue

Lovely and simple.

The main function is simple, just move everything in if __name__ == '__main__':
into a function.
With the operator addition you shouldn't really need to make smaller functions,
but it may be a good idea, making a function to get user input, could be a good idea.
But it's up to you.
If you did want to do both of these, you'd do something like:

def main():
    while True:
        number1, number2, operator = get_user_input()
        func = operators.get(operator, None)
        if func is None:
            print("Invalid operator!")
            continue

        print(func(number1, number2))

if __name__ == '__main__':
    main()

Just to note, you may not want to make get_user_input.

Something that you may not know is you can use the builtin operators library.
This will allow you to remove all your definitions of add, sub, etc.
And will allow you to change operators to:

import operator

operators = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
    "pow": operator.pow
}

There's some history about Python's division, and that's why it's called truediv, but if you haven't and won't use Python2, then you don't really need to know.


Modeling and plotting neuron responses I want to assign the row of a matrix the return value of a function, but the only way I can figure out how to do this is with a for-loop. I'm assuming this is bad and vectorization would be better.

I'm trying to implement the first principle of the Neural Engineering Framework for a class. The function of the code is to get activation levels of a neuron and put them into an activities matrix.

# I'm going to use a rectified linear neuron model, because it's super easy to implement
def rec_lin_neuron(x_inter, max_fire, gain_sign, x_max=1.0):
    def rec_lin(x):
        return np.minimum(
                np.maximum(
                    np.dot(gain_sign, x) * (max_fire/(x_max-x_inter))
                    - x_inter * (max_fire/(x_max-x_inter)),
                    np.zeros(x.size)
                ),
                max_fire
            )
    return rec_lin

# We're going to make 16 neurons
n_neurons = 16

# These are the neuron attributes that will be created randomly
max_firing_rates = np.random.uniform(100, 200, n_neurons)
x_cepts = np.random.uniform(-0.95, 0.95, n_neurons)
gain_signs = np.random.choice([-1, 1], n_neurons)

# Create the neurons and stick them in a list, because I don't know how else to keep track of them
neurons = []
for i in range(n_neurons):
    neurons.append(rec_lin_neuron(x_cepts[i], max_firing_rates[i], gain_signs[i]))

# Now let's calculate the response of these neurons to an input and plot it
x_vals = np.arange(-1, 1, 0.05)
A = np.zeros((n_neurons, x_vals.size))

fig = plt.figure()
for i in range(n_neurons):
    A[i,:] = neurons[i](x_vals)
    plt.plot(x_vals, A[i,:])
plt.show()

You could start by adding the necessary imports as well:

import numpy as np
from matplotlib import pyplot as plt

Since you already said how you can improve performance here (it's not
going to be easier to read, at least not to people who don't "live"
matrixes), I'm going to sketch the idea, although at least one step
isn't clear to me as well.  Which is to say, I find the function plus
for-loop way more readable than the following.

Now, instead of computing the response one by one, just vectorise each
step in rec_lin.  With the following rewrite, which is a tiny bit more
structured:

def rec_lin_neuron(x_inter, max_fire, gain_sign, x_max=1.0):
    def rec_lin(x):
        factor = max_fire/(x_max-x_inter)
        fire = np.maximum(np.dot(gain_sign, x) * factor - x_inter * factor,
                          np.zeros(x.size))
        return np.minimum(fire, max_fire)
    return rec_lin

That would be:

diffs = np.subtract(np.repeat(1.0, n_neurons), x_cepts) # aka x_max-x_inter
factors = np.divide(max_firing_rates, diffs) # aka factor

Similarly for the rest of that function, with the exception of np.dot,
where it's not clear to me how you'd run that function element-wise
against the input array, maybe you already know the answer, otherwise
I'll try to update it later.

The maximum and minimum for the matrixes should be np.amax and
np.amin.


Return a path between graph nodes using depth-first search redo I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this (using the feedback I got from last time).

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

class Graph:
    def __init__(self):
        self.nodes = set()

    def add_node(self, id):
        new_node = Node(id)
        self.nodes.add(new_node)
        return new_node

    def get_node(self, id):
        for node in self.nodes:
            if node.id == id:
                return node
        return None

    def dfs(self, start, end):
        stack = [start]
        parents = {}
        seen = set([start])

        while stack:
            cur_node = stack.pop()
            if cur_node is not end:
                for neighbour in cur_node.neighbours:
                    if neighbour not in seen:
                        seen.add(neighbour)
                        stack.append(neighbour)
                        parents[neighbour] = cur_node
            else:
                path = self.get_path(start, cur_node, parents)
                return path
        return None

    def get_path(self, start, end, parents):
        stack = [end]
        cur_node = end
        while cur_node is not start:
            cur_node = parents[cur_node]
            stack.append(cur_node)

        path = []
        while stack:
            cur_node = stack.pop()
            path.append(cur_node)
        return path

class Node:
    def __init__(self, id):
        self.id = id
        self.neighbours = {}

    def add_neighbour(self, to, weight):
        self.neighbours[to] = weight

Honestly your code is pretty good.

There are however two things that I would change:

self.nodes to be a dictionary rather than a set. This allows you to remove the need for get_node, and changes it to \$O(1)\$ from \$O(n)\$.
In get_path you pop from one stack and append to another. Instead of doing this manually I'd use the built-in list slicing notation, stack[::-1].


Changing attributes in Django Objects outside of iteration I'm adding three attributes to a Django QuerySet that represents a hierarchical tree structure:

a display_name which is added to all objects
the id of the object's parent (or immediate_parent) which is added to all objects based on a condition
a boolean is_parent field that should be added if and only if the object has children in the hierarchy.

The first two proved to be pretty simple to add while iterating over the QuerySet. The third proved more difficult because I was trying to modify an element outside of the one in the iteration. I tried to modify using both the .get() and the .filter() methods from the QuerySet API, but it didn't work to modify the original object. You can read more about that in the original stack overflow question.

Eventually I came up with this solution that involves iterating over the QuerySet 3 times:

causelist_data = CauseHierarchy.objects.filter(cause_set_version_id=cause_set_version_id).extra(order_by=['sort_order']).prefetch_related('cause_id','parent_id')
for c in causelist_data:
    c.display_name = c.cause_id.cause_name + " (" + c.cause_id.acause + ")"
    if len(c.path_to_top_parent.split(',')) == 1:
        c.immediate_parent = c.path_to_top_parent.split(',')[-1]
    else:
        c.immediate_parent = c.path_to_top_parent.split(',')[-2]
parents = []
for c in causelist_data:
    parents.append(int(c.immediate_parent))
for c in causelist_data:
    if int(c.cause_id_id) in parents:
        c.is_parent = True

This is pretty slow. Is there any way I can modify the parent object in the original iteration? (Any other suggestions welcome as well)

Right now you are iterating over the queryset three times in order to get set the immediate_parent and later set is_parent. While it doesn't look like you can cut this down to a single iteration, you can definitely cut it down to two.

Removing the extra iteration

Right now you are iterating over your queryset three times

Set the immediate_parent on the object
Get a list of all of the parents
Set is_parent on the object

Which works, but you can actually combine the first two iterations into a single one. This is because getting the list of the parents does not require any extra knowledge that comes after the first iteration. So you end up with

Set immediate_parent and build a list of parent ids
Set is_parent on the object if it's a parent

Or in code form

causelist_data = CauseHierarchy.objects.filter(cause_set_version_id=cause_set_version_id).extra(order_by=['sort_order']).prefetch_related('cause_id','parent_id')
parents = []

for c in causelist_data:
    c.display_name = c.cause_id.cause_name + " (" + c.cause_id.acause + ")"
    if len(c.path_to_top_parent.split(',')) == 1:
        c.immediate_parent = c.path_to_top_parent.split(',')[-1]
    else:
        c.immediate_parent = c.path_to_top_parent.split(',')[-2]
    parents.append(int(c.immediate_parent))

for c in causelist_data:
    if int(c.cause_id_id) in parents:
        c.is_parent = True

Use sets where the list can only have unique values

Right now you are using a list for parents, so each time you append the parent, it gets added to the list. This means that there can be multiple ids in the list for a single parent, which doesn't make sense when we are just using it to check for the existence of the id.

You can use a set instead. This has the benefit of having a faster lookup time, so the second iteration won't take as long.

parents = set()

for c in causelist_data:
    parents.add(int(c.immediate_parent))

Use in to check if a character is in a string

Right now in your first iteration you are looking for a , in the path_to_top_parent in order to determine if there is only a single parent in the path of now. But you're doing this by splitting the string on , and checking that there is only one part (so there wasn't a ,).

if ',' in c.path_to_top_parent:

Is the same as

if len(c.path_to_top_parent.split(',')) > 1:

But it has the added benefit of making it clear why you are branching there.

Putting it all together

causelist_data = CauseHierarchy.objects.filter(cause_set_version_id=cause_set_version_id).extra(order_by=['sort_order']).prefetch_related('cause_id','parent_id')
parents = set()

for cause in causelist_data:
    cause.display_name = cause.cause_id.cause_name + " (" + cause.cause_id.acause + ")"

    if ',' in cause.path_to_top_parent:
        cause.immediate_parent = cause.path_to_top_parent.split(',')[-2]
    else:
        cause.immediate_parent = cause.path_to_top_parent.split(',')[-1]

    parents.add(int(cause.immediate_parent))

for cause in causelist_data:
    if int(cause.cause_id_id) in parents:
        cause.is_parent = True


Chess board representation in Java I'm currently working on a small chess game written in Java (on GitHub). The board is modeled as a Board object with a 2D array of Piece objects :

public class Board {

  private final int ROWS = 8;
  private final int COLS = 8;

  private Piece[][] board;
  private List<Move> moveList;

  [...]

}

At first, I tried to implement all the board's possible states / legal move generation (isCheck, isCheckMate, isStaleMate, legalMoves...) inside the Board class.

For example :

private List<Move> moves(Color color) {

  List<Move> allMoves = new ArrayList<Move>();

  for (int row = 0; row < ROWS; row++) {
      for (int col = 0; col < COLS; col++) {
            Square src = new Square(row, col);
            Piece piece = getPiece(src);

            if (piece == null || !piece.isColor(color))
                 continue;

             allMoves.addAll(piece.availableMoves(src, this));
       }
  }

  return allMoves;
}

However it ended up being about 300 lines and it was not very easy to read (especially because of the duplication of the board iteration loops).

So I decided to try another approach : I removed all the state evaluation code and replaced it with this method :

 public void accept(BoardVisitor bv) {
    for (int row = 0; row < rows; row++) {
       for (int col = 0; col < cols; col++) {
          bv.visit(board[row][col], new Square(row, col));
       }
    }
 }

I then created a set of classes to "evaluate" the different states :

public class CheckEvaluator implements BoardVisitor {

private Square kingSquare;
private Board board;
private Color color;
private boolean isCheck = false;

public CheckEvaluator(Color color, Board board) {
    this.board = board;
    this.color = color;
}

@Override
public void visit(Piece piece, Square src) {
        isCheck = isCheck || piece.canGoTo(src, kingSquare, board);
}

public boolean getResult() {
    this.kingSquare = board.findKing(color);

    board.accept(this);

    return isCheck;
}
}

I regrouped all these evaluators inside a single class :

public class BoardEvaluator {

private Board board;

public BoardEvaluator(Board board) {
    this.board = board;
}

public boolean isCheck(Color color) {
    CheckEvaluator ce = new CheckEvaluator(color, board);

    return ce.getResult();
}

public boolean isCheckMate(Color color) {
    CheckMateEvaluator cme = new CheckMateEvaluator(color, board);

    return cme.getResult();
}

public boolean isStaleMate() {
    StaleMateEvaluator sme = new StaleMateEvaluator(board);

    return sme.getResult();
}

public List<Move> legalMoves(Color color) {
    LegalMovesEvaluator lme = new LegalMovesEvaluator(color, board);

    return lme.getResult();
}

This version seems clearer and easier to me but I don't have a lot of experience and I'd be very glad to get some feedback about it:

Do you think this is a valid design?
Is my BoardVisitor a good (if simple) implementation of the Visitor pattern?

Warning! Arm Chair Quarterbacking in progress. Given that I offer this.

Game Class

Why is this Board.moveList in the Board class?  You need a "driver" for a chess game and that would be a Game class. "A game consists of (has) moves" makes more sense.

The Game gives us a conceptual framework for a richer chess game. A Game has players, may have a timer for speed chess, and can keep track of pieces removed from the board; and of course records the moves.

Board Class

The chess board is a data structure. Don't make more of it than it is; nor less.

In the Visitor Pattern the data structure has-a element that has an accept method. That element seems to be a Square. I'm not certain if it's better than the Board being visited, but certainly the point is that we're evaluating the state at that one square? I don't see a big deal in giving a board reference to each square.

OR .. maybe the Pieces are visited. To test if the piece is "inCheck" for example. This perspective makes more sense than a square is in check. Is this why your board is Piece[][] and not Square[][]?

Whether we are visiting the board and iterating the squares; or iterating the board and visiting the squares; or iterating the squares and visiting the pieces may be more than semantics. I vote for whatever best reflects intent, gives me good code expressions, and sensible building blocks.

In any case I agree with @bowmore about refactoring Piece[][] to Square[][].

Pieces

Even given a rich Piece class, I like the idea of using an enumeration for names. This makes for nicer coding  and expressability overall (and my pet peeve - it avoids strings). Maybe two enumerations. As in White.Knight and Black.Queen; or Pieces.WhiteKnight, Pieces.BlackQueen And a value to represent an empty square might be nice Pieces.none or Pieces.undefined.

Maybe Piece has a Square reference so it knows where it is. This may have a nice effect on the visit code.

Visitor Pattern

Nice call.

I agree with @MarcoForgerg, the visitors do not need to keep state. Just pass in the needed parameters and forget-about-it when done. And, instead of Singletons perhaps just static.

Nested visitors? Ok, so the board gets "visited" which in turn "visits" each square, which in turn, finally gets to Piece.accept(Evaluator xxxx). Visitors, by definition, understand their visited data structure so I'm thinking board iteration is wrapped in the board visitor, and the square visitor knows to check for an occupying piece and knows what Evaluator(s) to pass to the piece. It feels like nicely layered (code) logic to me. And note how the iteration logic is in the visitors, not the board (data structure). And subsequently all the business logic is in the visitor as well.

SO instead of this

public void accept(BoardVisitor bv) {
    for (Square square : board) {
       bv.visit(square);
    }
}

THIS - Let the Visitor do the walking and talking (decision making). And the decision to evaluate empty squares is delayed as long as possible - push details down. Note that Board, Square, Piece visiting logic is decoupled/layered.

// in Board class
public void accept(BoardVisitor bv) { bv.visit(this));}

// BoardVisitor class
public void visit (Board board) {
    // "board level" logic as needed
    for (Square square in board) {
        square.accept (this.squareVisitor);
    }
}

// Square class
public void accept (SquareVisitor sv) {
    sv.visit(this);
}

// SquareVisitor class
public void visit (Square square) {
   // "square level" logic as needed
   if(!square.isEmpty) {
       // maybe we target Evaluators for the particular piece on the square

       this.evaluator(square); // square has references to its piece and board.
         // maybe the square.piece has "visit"
   }
}


Euler #7 - 10001st prime Here is my code of project Euler #7:

from math import *
import time
start = time.time()
def isPrime(n):
    prime_fst = [2,3,5,7]
    num = round(sqrt(n))
    j=0
    while num>7:
        if num%2!=0 and num%3!=0 and num%5!=0 and num%7!=0:
            prime_fst.append(num)
        num-=1
    prime_fst.sort()
    while j < len(prime_fst):
        for i in prime_fst:
            if i!=prime_fst[j]:
                if i%prime_fst[j]==0:
                    prime_fst.remove(i)
        j+=1
    for t in prime_fst:
        if n%t==0:
            k=n%t
            return False
    return True

x=int(input())
l=1
res = [2,3,5,7]
while len(res)!=x:
    if l!=1:
        if isPrime(l):
            res.append(l)
    l+=2
print(res[-1])
end = time.time()
print(end-start)

Can you recommend what I should do with algorithm skills? How can I think effectively? Will skills develop with time? All your recommendations and help to speed up this code by explaining?

Some recommendations:

Running your code through a linter like pycodestyle, then learning what the messages mean and applying them to your code is going to make your code more idiomatic, and therefore easier to understand for Python veterans.
I would use an external command like time my_script.py to time the execution. This will shorten your code a fair bit (and besides, you would never put timing code into production code). Sure, it's a little bit less accurate, but for Euler Project questions you just want a ballpark estimate.
Use argparse rather than input(). That makes your scripts, well, scriptable, so that they can be used easier within the context of a bigger project, and they can be re-run quicker on the command line.
The only things on the top level of your script should be a shebang line like #!/usr/bin/env python3, imports, class/function definitions, and the following:

if __name__ == '__main__':
    main()

This way, anything declared in the script can be imported by other scripts without running the algorithm.
Naming is one of the most difficult but also most useful skills in programming. If you can think of any better names for n, t, num, j, etc, the program will be much easier to understand for someone without all the context you have.
You hard code the list [2, 3, 5, 7] three times in your code, but only once (at most) should be necessary.
On a related note, starting with a list of the four first primes is very arbitrary. Why not the first million? Or the first one?
isPrime (or is_prime as it should be in idiomatic Python) is a good name, but there is no explanation for which algorithm you're using to check primality. You can introduce the algorithm name in one of several ways:

As a comment.
By refactoring the entire contents of isPrime into a separate method and naming that according to the algorithm. This only really makes sense if either isPrime ends up containing something more than just the call to the other function (a "vacuous" function) or if you intend to implement multiple algorithms in your code and swap them out dynamically (for example, using the fastest algorithm based on the size of the numbers you're dealing with).
More complex means like a dispatcher, but this is not applicable in this situation.

Rather than round(sqrt(n)) you can use floor(sqrt(n)), it'll be faster half the time.
Every time you run isPrime you build up a list of primes, but it goes out of context and has to be recomputed for every number. Your code will be much faster for long lists of input if you save all the primes calculated so far for subsequent runs. For example, you could create an ErathostenesSieve class which has a field sieve which contains the primes detected so far, and it could even be a generator from which you can take an arbitrary number of primes.
If you start with l = 2 or even l = res[-1] you can remove if l!=1:.
Do not append to prime_fst until you're sure the number is prime. That way you won't ever have to sort the list or remove from it.

By the way: Don't be discouraged by the amount of suggestions! IMO this is a very good start, and learning programming is an infinite journey which can be incredibly rewarding.


Linear algebra architecture I'm using linear algebra as my basis. One very specific change I'd like to make is to allow for equality tests between points and vectors with an unequal number of components by assuming that all undefined components are zero (all points and vectors have infinite components; equality tests stop testing once a check for both components return 'undefined'). Mostly I'd like to do this just because it seems kind of cool to do, so it is not remarkably important.

But in essence, I really just want someone to rip this code apart and tell me why I'm doing everything wrong (or tell me that I'm doing things pretty alright). The goal is just to have a nice, sane Point and Vector system that is very flexible and can be understood by anyone--and used by anyone--for any purpose they'd like. Everything I'm building will rely on the following code, so I want to make sure that my design patterns are reasonable and flexible.

import math, sys, os

TOLERANCE = 0.00001

class SizeError(Exception):
    def __init__(self, *args):
        self.args = args
        print "Size Error between " + str(args)

class P(object):
    def __init__(self, *args):
        if len(args) == 1:
            try:
                self.components = tuple(args[0])
                self.size = len(args[0])
            except TypeError:
                self.components = tuple(args)
                self.size = len(args)
        else:
            self.components = args
            self.size = len(args)
    def __getitem__(self, key):
        return self.components[key]
    def __repr__(self):
        result = ""
        for i in range(0, self.size):
            result += str(self[i]) + ", "
        return "<Point (" + str(self.size) + ") : "  + result[:-2] + ">"
    def __eq__(self, other):
        if self.size != other.size:
            raise SizeError(self, other)
        for i in range(0, self.size):
            result = self[i] - other[i]
            if math.fabs(result) > TOLERANCE:
                return False
        return True
    def __add__(self, other):
        if other.size != self.size:
            raise SizeError(self, other)
        result = []
        for i in range(0, self.size):
            result.append(self[i] + other[i])
        return P(result)
    def __sub__(self, other):
        if other.size != self.size:
            raise SizeError(self, other)
        result = []
        for i in range(0, self.size):
            result.append(self[i] - other[i])
        return V(result)

class V(P):
    def __repr__(self):
        result = ""
        for i in range(0, self.size):
            result += str(self[i]) + ", "
        return "<Vector (" + str(self.size) + ") : "  + result[:-2] + ">"
    def __add__(self, other):
        if other.size != self.size:
            raise SizeError(self, other)
        result = []
        for i in range(0, self.size):
            result.append(self[i] + other[i])
        return V(result)
    def __mul__(self, scalar):
        result = []
        for i in range(0, self.size):
            result.append(self[i] * scalar)
        return V(result)
    def __neg__(self):
        return self * -1
    def dotProduct(self, other):
        result = 0
        if self.size != other.size:
            raise SizeError(self, other)
        for i in range(0, self.size):
            result += self[i] * other[i]
        return result
    def normalize(self):
        result = []
        length = self.getLength()
        if math.fabs(length) < TOLERANCE: return self.getZero()
        for i in range(0, self.size):
            result.append(self[i] / length)
        return V(result)
    def getLength(self):
        result = 0
        for i in range(0, self.size):
            result += self[i]**2
        return math.sqrt(result)
    def getZero(self):
        return self * 0
    def isZero(self):
        zero = self.getZero()
        return self == zero

import math, sys, os

TOLERANCE = 0.00001

class SizeError(Exception):
    def __init__(self, *args):
        self.args = args
        print "Size Error between " + str(args)

You shouldn't print in an exception constructor. At most, you should define a __repr__ for printing purposes. But you can probably get away with not doing that and trusting the default.

class P(object):

The name doesn't give me much clue as to what this class is.

    def __init__(self, *args):
        if len(args) == 1:
            try:
                self.components = tuple(args[0])
                self.size = len(args[0])
            except TypeError:
                self.components = tuple(args)
                self.size = len(args)
        else:
            self.components = args
            self.size = len(args)

Instead of assigning size three times, use self.size = len(self.components) at the end. In fact, consider not storing the size at all and just looking at the size of the components. I'd also suggest not accepting three different ways of passing in the parameters. Pick one and make it be used everywhere.

    def __getitem__(self, key):
        return self.components[key]
    def __repr__(self):
        result = ""
        for i in range(0, self.size):
            result += str(self[i]) + ", "

Add strings is expensive. But python has a really nice join function. So you could do:

result = ",".join(map(str,self))

And it'll actually take care of everything else for you

        return "<Point (" + str(self.size) + ") : "  + result[:-2] + ">"
    def __eq__(self, other):
        if self.size != other.size:
            raise SizeError(self, other)
        for i in range(0, self.size):

You don't need the zero.

            result = self[i] - other[i]
            if math.fabs(result) > TOLERANCE:

I'd combine those two lines

                return False
        return True
    def __add__(self, other):
        if other.size != self.size:
            raise SizeError(self, other)
        result = []
        for i in range(0, self.size):
            result.append(self[i] + other[i])

Use zip, and it'll be a bit faster to use a list comprehension:

result = [x+y for x, y in zip(self, other)]

        return P(result)
    def __sub__(self, other):
        if other.size != self.size:
            raise SizeError(self, other)
        result = []
        for i in range(0, self.size):
            result.append(self[i] - other[i])
        return V(result)

class V(P):

I wouldn't have vector inherit from point. I'd have them both inherit from some other more generic class. A vector is not a point, coding like it is one could be confusing.

    def dotProduct(self, other):

Python convention is to have names which are lowercase_with_underscores for methods.

        result = 0
        if self.size != other.size:
            raise SizeError(self, other)
        for i in range(0, self.size):
            result += self[i] * other[i]
        return result

Here I'd use

return sum(x * y for x, y in zip(self, other))

    def normalize(self):
        result = []
        length = self.getLength()
        if math.fabs(length) < TOLERANCE: return self.getZero()
        for i in range(0, self.size):
            result.append(self[i] / length)
        return V(result)
    def getLength(self):
        result = 0
        for i in range(0, self.size):
            result += self[i]**2
        return math.sqrt(result)

    def getZero(self):
        return self * 0
    def isZero(self):
        zero = self.getZero()
        return self == zero

Both of these will be inefficent implementations. They should work, but they'll be relatively slow. The fact being any Point/Vector class implemented in python will be unforgivably slow. That's why we typically implement such things in extensions like numpy.


Removing duplicate letters from list of words with Python and List Comprehensions I'm guessing this has quadratic time complexity, \$O(n^2)\$, and \$O(2n)\$ for memory complexity. I wonder if I can do something within the list comprehension to just .pop(n) something out of the list instead of relying on a second list. Thoughts?

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[[listLettersAlreadyFound.append(letter) for letter in list(word) if letter not in listLettersAlreadyFound] for word in listx]
print listLettersAlreadyFound

The reason you get \$O(n^2)\$ time complexity is due to you going through listLettersAlreadyFound, whilst checking if the new item is in that. To improve the performance, you could create another set, reducing time complexity to \$O(n)\$.

But before that, listLettersAlreadyFound is long, first list is unneeded, but lettersAlreadyFound is the same as previous_letters. And you should use snake_case rather than CamelCase.

I also find your comprehensions hard to read, you need to space the logic on different lines. Take:

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[
    [
        listLettersAlreadyFound.append(letter)
        for letter in list(word)
        if letter not in listLettersAlreadyFound
    ]
    for word in listx
]
print listLettersAlreadyFound

From this it's easy to notice that a comprehension is probably not the best choice here. You don't actually want the list, you only want the side affects from the list. This goes against the spirit of Functional Programming, which is what comprehensions are. And so you should instead just use a simple for loop.

Merging the above all together could get you some \$O(n^2)\$ time complexity code, that also has \$O(2n)\$ memory:

words = ['cat', 'dog','rabbit']
unique_letters = []
previous_letters = set()

for letter in (letter for word in words for letter in word):
    if letter in previous_letters:
        continue
    previous_letters.add(letter)
    unique_letters.append(letter)

print unique_letters

Finally if you don't care about the order of the letters, you can change the for loop to be set. And instead just use:

words = ['cat', 'dog','rabbit']

print set(letter for word in words for letter in word)

Also .pop(n) will keep the \$O(n^2)\$ time complexity, and so I'd suggest you don't use it, if you really want better memory performance, use a for loop, as it'd keep the code readable, not a list comprehension.


Optimizing a c# program that creates 2 dictionaries and searches both for a matching value I have 2 Dictionaries. I am trying to optimize this code to run as fast as possible.

This is for solving Shanks Baby Step Giant Step Algorithm
Algorithm:

Given b = a^x (mod p)
First choose n, such that n^2 >= p-1
Then create 2 lists:
    1. a^j (mod p) for 0 <= j < n
    2. b*(a(inverse)^n)^k for 0 <= k < n
Finally look for a match between the 2 lists.

public static BigInteger modInverse(BigInteger a, BigInteger n)
{
    BigInteger i = n, v = 0, d = 1;
    while (a > 0)
    {
        BigInteger t = i / a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t * x;
        v = x;
    }
    v %= n;
    if (v < 0) v = (v + n) % n;
    return v;
}

static int Main()
{
    BigInteger r = 92327518017225,
               rg,
               temp,
               two=2,
               tm,
               n = ((BigInteger)Math.Sqrt(247457076132467-1))+1,
               mod = 247457076132467;
    Dictionary<int, BigInteger> b = new Dictionary<int, BigInteger>();
    Dictionary<int, BigInteger> g = new Dictionary<int, BigInteger>();
    temp = modInverse(two, mod);
    temp = BigInteger.ModPow(temp, n, mod);
    for (int j = 0; (BigInteger)j < n; j++)
    {
        rg = r * BigInteger.ModPow(temp, j, mod);
        g.Add(j, rg);
    }
    for (int i = 0; (BigInteger)i < n ; i++)
    {
        tm = BigInteger.ModPow(2, i, mod);
        foreach (KeyValuePair<int, BigInteger> d in g)
        {
            if (d.Value.Equals(tm))
            {
                Console.WriteLine("j={0}   B*t^j(mod m) = {1}",d.Key,d.Value);
                Console.WriteLine("a^"+i+" = "+tm);
            }
        }
        b.Add(i,tm);
    }
    Console.ReadKey();
    return 0;
}

There are some really obvious optimisations.

Delete all the code relating to b. A dictionary you only insert into is a waste of time, memory, and programmer ability to understand what's going on.
Use g as a dictionary. The way to do that is to change it from a Dictionary<int, BigInteger> into a Dictionary<BigInteger, int>. Then your foreach can be replaced with a simple TryGetValue.
Ditch the cast of j to BigInteger:

int n_int = ((int)Math.Sqrt(247457076132467-1))+1;
...
n = (BigInteger)n_int

And compare j to n_int. If it doesn't fit in an int, j shouldn't be an int either.
Exploit basic arithmetic properties in loops. E.g. rather than

tm = BigInteger.ModPow(2, i, mod);

you should have

tm = 1,
...
for (int i = 0; i < n_int; i++)
{
    ...
    tm = (tm * 2) % mod;
}

PS In fact, if you'd looked at the Wikipedia page on the algorithm you'd have found pseudocode which handles all this already.


Calculating series of rows to use to play a melody on 5-row Bayan Accordion This was my first attempt at writing a program in LISP. Can anyone give any guides as to how it could be improved? The multiple loops in best-pattern seem awkward (I'd normally do that in just one loop but there doesn't seem to be a way of doing that with LOOP, although I'm told there's an iterate extension that can do it), as does the way of calculating alternatives..

(defparameter *rows* (list (list :c :ds :fs :a) (list :cs :e :g :as) (list :d :f :gs :b)))

(defun row-for-note (note)
    (position-if (lambda (row) (find note row)) *rows*)
)

(defun rows-for-notelist (notelist)
    (mapcar #'row-for-note notelist)
)

(defun possible-alternates (rowlist)
    (let ((alternatives '(())))   ;; Lots of irritating silly parentheses
        (when (> (length rowlist) 1)
           (setq alternatives (possible-alternates (cdr rowlist)))
        )
        (case (car rowlist)
            ((0) (mapcar (lambda (x) (append '(0) x)) alternatives))
            ((1) (append (mapcar (lambda (x) (append '(1) x)) alternatives)
                         (mapcar (lambda (x) (append '(-2) x)) alternatives)))
            ((2) (append (mapcar (lambda (x) (append '(2) x)) alternatives)
                         (mapcar (lambda (x) (append '(-1) x)) alternatives)))
        )
    )
)

(defun count-jumps (rowlist)
    (loop for (a b) on rowlist while b counting (> (abs (- a b)) 1))
)

(defun best-pattern (notelist)
    (let ((minval (loop for x in (possible-alternates (rows-for-notelist notelist)) minimize (count-jumps x))))
    (loop for x in (possible-alternates (rows-for-notelist notelist)) when (= (count-jumps x) minval) collect x))
)

(If you're wondering what the program does, it tries to calculate the "most efficient" series of rows to use to play a melody on 5-row Bayan Accordion.)

Done:

improved formatting and layout
instead of car and cdr, use first and rest.

Missing:

documentation strings
example

Only slight improvements.

No need to use list:

(defparameter *rows* '((:c  :ds :fs :a )
                       (:cs :e  :g  :as)
                       (:d  :f  :gs :b )))

Okay:

(defun row-for-note (note)
  (position-if (lambda (row) (find note row))
               *rows*))

(defun rows-for-notelist (notelist)
  (mapcar #'row-for-note notelist))

Compute alternatives directly, without setq. Local functions for repeated use. Use cons. Not so good: recursion limits use, because of limited stack depth.

(defun possible-alternates (rowlist)
  (let ((alternatives (if (rest rowlist)
                          (possible-alternates (rest rowlist))
                        '(()) )))
    (flet ((add (item)
             (mapcar (lambda (x) (cons item x))
                     alternatives)))
      (case (first rowlist)
        (0 (add 0))
        (1 (append (add 1) (add -2)))
        (2 (append (add 2) (add -1)))))))

(defun count-jumps (rowlist)
  (loop for (a b) on rowlist
        while b
        count (> (abs (- a b)) 1)))

Slight improvements:

(defun best-pattern (notelist)
  (let* ((alternates (possible-alternates (rows-for-notelist notelist)))
         (jumps      (mapcar #'count-jumps alternates))
         (min-jump   (loop for j in jumps minimize j)))
    (loop for a in alternates and j in jumps
          when (= min-jump j)
          collect a)))


Randomly re-partition 1Dimensional List to 2Dimensional I wrote a solution Please look at the my approach is correct? There is a better solution?

List<Tuple<object, object, object>> OneDimensionalLists = new List<Tuple<object, object, object>>();
List<Tuple<object, object, object>[]> TwoDimensionalLists = new List<Tuple<object, object, object>[]>();

int i1 = 0;
for (int i = 0; i < OneDimensionalLists.Count; i++)
{
    var random = new Random(seed);
    int next = random.Next(10, 30);
    TwoDimensionalLists.Add(new Tuple<object, object, object>[next]);
    for (int j = 0; j < next; j++)
    {
        if (OneDimensionalLists.Count == i1)
            goto go;

        TwoDimensionalLists[i][j] = OneDimensionalLists[i1++];
    }
}
go:

for (int i = 0; i < OneDimensionalLists.Count; i++)
{
    var random = new Random(seed);
    int next = random.Next(10, 30);
    ...

Have you checked the value of next on the various iterations? I can't see seed changing anywhere in this code. Assuming it remains the same, random.Next() will return the same value each time. Unless this is intentional, create the Random(seed) outside of the loop.


Key phone in Haskell Here is my solution for an exercise, which requires translation of strings to key presses on a phone keypad (for example, to get 'b' the digit '2' needs to be pressed twice).

It's taken from the book Haskell from first principles, and originally appeared in 1HaskellADay. I'd love to get feedback.

module Phone where
import Data.Char
import Data.String.Utils
import Data.List

data DaPhone = DaPhone [String]
convo :: [String]
convo =
          ["Wanna play 20 questions",
           "Ya",
           "U 1st haha",
           "Lol ok. Have u ever tasted alcohol lol",
           "Lol ya",
           "Wow ur cool haha. Ur turn",
           "Ok. Do u think I am pretty Lol",
           "Lol ya",
           "Haha thanks just making sure rofl ur turn"]

-- validButtons = "1234567890*#"
type Digit = Char
-- Valid presses: 1 and up
type Presses = Int

reverseTaps :: DaPhone -> Char -> [(Digit, Presses)]
reverseTaps (DaPhone keys) c = if isUpper c then ('*', 1) : looks else looks
    where looks = look keys (toLower c)
-- assuming the default phone definition
-- 'a' -> [('2', 1)]
-- 'A' -> [('*', 1), ('2', 1)]

look :: [String] -> Char -> [(Digit, Presses)]
look keys c = look' keys c 0

look' :: [String] -> Char -> Int -> [(Digit, Presses)]
look' [] _ _ = []
look' (x:xs) c n = if ind /= (-1) then [(head $ show n, ind + 1)] else look' xs c (n + 1)
where ind = maybe (-1) id $ elemIndex c x

cellPhonesDead :: DaPhone -> String -> [(Digit, Presses)]
cellPhonesDead = (concat .) . map . reverseTaps

-- count total presses
fingerTaps :: [(Digit, Presses)] -> Presses
fingerTaps = sum . map snd

mostPopularLetter :: String -> Char
mostPopularLetter = head . longest . group . sort

coolestLtr :: [String] -> Char
coolestLtr = mostPopularLetter . filter isAlpha . concat

coolestWord :: [String] -> String
coolestWord = head . longest . group . sort . words . join " "

longest :: [[a]] -> [a]
longest = maximumBy (\x y -> compare (length x) (length y))

phone :: DaPhone
phone = DaPhone keymap

keymap :: [String]
keymap =

                [
                    " 0",
                    "1",
                    "abc2",
                    "def3",
                    "ghi4",
                    "jkl5",
                    "mno6",
                    "pqrs7",
                    "tuv8",
                    "wxyz9"
                ]

In real code, I would consider this to be too much naming for this little code. Most of this would probably be used only once and could thus be inlined. Since the exercise required implementations for all these, it's okay.

(concat .) . map is foldMap.

\x y -> compare (length x) (length y) is comparing length.

Did you try compiling this? ind /= Nothing means that ind + 1 shouldn't work, and elemIndex takes the Char before the String.

look keys c = case asum $ zipWith (fmap . (,)) [0..] $ map (elemIndex c) keys of
  Nothing -> []
  Just (n, ind) -> [(head $ show n, ind + 1)]


Bean Machine Simulation I could not find a solution from my book's website (student-level access) but I feel that I am missing something that I'm supposed to learn from this exercise.

Instructions: Balls are dropped from the opening of the board. Every time a ball hits a nail, it has a 50% chance of falling to the left or to the right. The piles of balls are accumulated in the slots at the bottom of the board.

Book's example:

Enter the number of balls to drop: 5
Enter the number of slots in the bean machine: 7

LRLRLRR

RRLLLRR

LLRLLRR

RRLLLLL

LRLRRLR

        0
        0
      000

My attempt:

import java.util.*;

public class BeanMachine {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter number of balls to drop: ");
        int numberOfBalls = input.nextInt();
        System.out.print("Enter the number of slots in the bean machine: ");
        int numberOfSlots = input.nextInt();

        //Simulate drops
        int[] slots = new int[numberOfSlots];
        for (int i = 0; i < numberOfBalls; i++) {
            simulateDrop(slots);
        }

        //Display histogram
        for (int i = numberOfBalls; i > 0; i--) {
            for (int j = 0; j < slots.length; j++) {
                if (slots[j] >= i) {
                    System.out.print("0");
                }
                else {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    public static void simulateDrop(int[] slots) {
        StringBuilder path = new StringBuilder(slots.length);
        int slotIndex = 0;
        int numberOfNails = slots.length - 1;
        for (int i = 0; i < numberOfNails; i++) {
            int direction = (int)(Math.random() * 2);

            if (direction == 0) {
                path.append("L");
            }
            else {
                path.append("R");
                slotIndex++;
            }
        }

        System.out.println(path.toString());
        slots[slotIndex]++;
    }
}

Java has good support for OOP techniques - Using these will allow you to create a more elegant solution. Your code could be refactored with the correct use of these techniques to produce something of the form:

PegMachine sampleTest = PegMachine(500,100);
sampleTest.histogram;

This approach hides the complexities of the program and allows you to conduct tests by simply creating a PegMachine specifying the number of pegs and balls for each sample.

I noticed Aron_dc pointed out the slotIndex variable in your simulateDrop method is never used - This can be removed as it does not contribute anything to your program.

Out of curiosity I conducted a larger sample using your code to see if it produced the correct normal-distribution curve. The results were as expected; confirming your codes correctness.

Besides suggesting the use of object orientation your code seems well written and correct.