Project Euler Problem 45 As a self-teaching Python beginner for almost 4 months, I have mostly been doing online challenges including Project Euler problems.

Problem 45 asks:

  Triangle, pentagonal, and hexagonal numbers are generated by the
  following formulae:

  $$
\begin{array}{lll}
\textrm{Triangle}   & T_n=n(n+1)/2  & 1, 3,  6, 10, 15, \ldots  \\
\textrm{Pentagonal} & P_n=n(3n−1)/2 & 1, 5, 12, 22, 35, \ldots  \\
\textrm{Hexagonal}  & H_n=n(2n−1)   & 1, 6, 15, 28, 45, \ldots \\
\end{array}
$$

  It can be verified that \$T_{285} = P_{165} = H_{143} = 40755\$.

  Find the next triangle number that is also pentagonal and hexagonal.

I encountered this problem and was able to write the code without much problem although most of the solutions I write are mostly brute force. However I am not satisfied with the time the coding took to find the answer as it took 530.7 seconds to find the solution with this code:

import time

startTime = time.time()

limit = 1000000
triangle = []
pentagonal = []
hexagonal = []
triangle_number = []

class Shape:
    def __init__(self, term):
        self.term = term

    def triangle(self):
        return int(self.term * (self.term + 1) / 2)

    def pentagonal(self):
        return int(self.term * (3 * self.term -1) / 2)

    def hexagonal(self):
        return int(self.term * (2 * self.term - 1))

def generate():
    for terms in range(1, limit + 1):
        product = Shape(terms)

        triangle.append(product.triangle())
        pentagonal.append(product.pentagonal())
        hexagonal.append(product.hexagonal())

def main():
    generate()

    for _, terms in enumerate(hexagonal):
        if len(triangle_number) == 3:
            break
        elif terms in triangle and terms in pentagonal:
            triangle_number.append(terms)
            print(terms)

    print(triangle_number)
    print(time.time() - startTime, "seconds")

main()

I am aware that using the class is unecessary for this problem, but I want to include it as a practice of getting used to writing solutions that require classes.

Alternatively I have re-written another solution of this problem without any classes included but keeping the same style, however it still took 328.2 seconds.

So what suggestions are there to improve the code to run faster? I have tried to review other solutions from the solution page however I do not understand how it was simplified so much to make it run more efficient.

Arithmetic

Project Euler questions are meant to educate you about both mathematics and programming.  It would be a good idea to understand what these triangular, pentagonal, and hexagonal numbers actually are, rather than blindly applying the given formulas.

One performance improvement would be to find a way to generate successive elements of each sequence without plugging \$n\$ into the formulas, which involve division.  (Division tends to be slow.  Floating-point division, using the / instead of the // operator, is even slower, and it also causes you to have to cast the result back to an int.)

If you take the formula for pentagonal numbers \$P_n\$, you can figure out another formula for the difference between successive elements in the sequence.

$$
\begin{align}
P_n &= \frac{n(3n-1)}{2} = \frac{3n^2-n}{2} \\
P_{n+1} &= \frac{(n+1)(3(n+1)-1)}{2} = \frac{(n+1)(3n+2)}{2} = \frac{3n^2+5n+2}{2} \\
P_{n+1} - P_n &= \frac{(3n^2+5n+2)-(3n^2-n)}{2} = \frac{6n+2}{2} = 3n + 1
\end{align}
$$

If you do the same for triangular, square, and hexagonal numbers, you'll find:

$$
\begin{align}
T_{n+1} - T_n &= n+1 \\
P_{n+1} - P_n &= 3n+1 \\
H_{n+1} - H_n &= 4n+1
\end{align}
$$

Considering that square numbers would be \$S_{n+1} - S_n = 2n+1\$, you can see a pattern to produce polygonal numbers in general.

Algorithm

Your strategy is to generate a million elements of each sequence and find the elements that exist in common.

First of all, one million is an arbitrary limit.  You might need fewer than a million to find the next element in common (in which case you've wasted execution time), or you might need more than a million (in which case you would have to raise the limit and run your code again).  It would be nice if your algorithm did not have to rely on a guess.

Secondly, the millionth hexagonal number is certainly going to be much larger than the millionth triangular number.  There is no way that the millionth hexagonal number is going to coincide with anything, so that's wasted work.

Thirdly, you store the sequences as lists.  Searching a list (e.g. terms in triangle) involves inspecting every element in that list (a so-called O(n) operation).  Searching a set takes only O(1) time.  Therefore, simply changing

triangle = []
pentagonal = []
hexagonal = []

and

        triangle.append(product.triangle())
        pentagonal.append(product.pentagonal())
        hexagonal.append(product.hexagonal())

to

triangle = set()
pentagonal = set()
hexagonal = set()

and

        triangle.add(product.triangle())
        pentagonal.add(product.pentagonal())
        hexagonal.add(product.hexagonal())

brings the execution time down from hundreds of seconds down to about 2 seconds.  Better yet, your main() function could be simplified using the set intersection operator &:

def main():
    generate()
    triangle_number = triangle & pentagonal & hexagonal
    print(sorted(triangle_number))
    print(time.time() - startTime, "seconds")

Pythonicity

Be consistent with your naming.  If you write "pentagonal" and "hexagonal", then use "triangular" rather than "triangle".

The Shape class shouldn't exist at all.  It's just a very weird and cryptic way to call three functions that take a numerical parameter.

for _, terms in enumerate(hexagonal) is a nonsensical use of enumerate.  If you're going to throw away the index anyway, why not just write for terms in hexagonal?  And why is your iteration variable pluralized (terms rather than term)?

Your code would be much more expressive if you could say "give me the next pentagonal number".  A good way to do that in Python is to define a generator, so that you can write next(pentagonal_numbers).

Suggested solution

from itertools import count

def polygonal_numbers(sides):
    result = 0
    for n in count():
        yield result
        result += (sides - 2) * n + 1

tt, pp, hh = polygonal_numbers(3), polygonal_numbers(5), polygonal_numbers(6)
t = p = 0
for h in hh:
    while p < h: p = next(pp)
    while t < h: t = next(tt)
    if t == p == h > 40755:
        print(h)
        break

If you take into account that every hexagonal number is also a triangular number, you can ignore the triangular numbers altogether:

from itertools import count

def polygonal_numbers(sides):
    result = 0
    for n in count():
        yield result
        result += (sides - 2) * n + 1

pentagonal_numbers = polygonal_numbers(5)
p = 0
for h in polygonal_numbers(6):
    while p < h: p = next(pentagonal_numbers)
    if p == h > 40755:
        print(h)
        break

My last solution takes about 50 milliseconds to run on my machine.


Implementing a Stack in Java for a technical interview This code is based off the Stack implementation in Chapter 3 of Cracking The Coding Interview. I modified the code to make it compile and give me the correct output. I'd appreciate any feedback on code style and correctness, assuming that I write this code in a technical interview.

The pseudocode from Cracking the Coding Interview, which is implemented using a linked list:

class Stack {

    Node top;

    Object pop() {
        if (top != null) {
            Node item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }

    void push(Object item) {
        Node t = new Node(item);
        t.next = top;
        top = t;
    }

    Object peek() {
        return top.data;
    }
}

My code:

public class Stack {
    Node first;
    Node last;

    public Stack(Node f, Node l) {
        first = f;
        last = l;
        first.next = last;
    }

    public Stack() {
        first.next = last;
    }

    public void push(Object data) {
        if(first == null) {
            first = new Node(data, null);
        }
        else {
            last.next = new Node(data, null);
            last = last.next;
        }

    }

    public Object pop() {
        if(first == null) {
            return -1;
        }
        else {
            Object item = last.data;
            Node cur = first;
            while (cur.next.next != null) {
                cur = cur.next;
            }
            last = cur;
            return item;
        }
    }

    public Object peek() {
        if(first == null) {
            return -1;
        }
        Object item = last.data;
        return item;
    }

    public static void main(String[] args) {
        Stack stack = new Stack(new Node(1, null), new Node(2, null));
        stack.push(3);
        System.out.println(stack.peek() == 3);
        stack.pop();
        System.out.println(stack.peek() == 2);
    }

    private static class Node {
        Object data;
        Node next;

        private Node(Object d, Node n) {
            data = d;
            next = n;
        }
    }
}

A stack should not know about the first element. A stack only know about the last element that was pushed, so the Stack object itself should only have one Node called last. Because of this, the constructor should be changed as well to only take one Node ex: public Stack(Node node).

Edit: As @vnp says, Node is private, so it cannot be created outside this class. Either create a constructor which takes an Object, or don't create any constructors and always create an empty Stack.

This constructor doesn't do anything and will throw a NullPointerException:

public Stack() {
    first.next = last;
}

In pop(), you shouldn't need to do any fancy while loops. Just check if last is null and if not, get last's data and set last to last.next:

public Object pop() {
    if(last == null) {
        return -1;
    }
    else {
        Object item = last.data;
        last = last.next;
        return item;
    }
}

In push(), you should simply set last to be the new Node, and have it point to the old last as it's next:

public void push(Object data) {
    last = new Node(data, last);
}

In peek(), you can change first to last and simply return last.data:

public Object peek() {
    if(last == null) {
        return -1;
    }
    return last.data;
}

One final point: you should not give your variables one character names like d, n, l, and f. If the variables in your constructor should have the same name as the private member variables, then give them the same name and prefix the members with this to differentiate them. For example, you can change the Node constructor to:

private Node(Object data, Node node) {
    this.data = data;
    this.next = node;
}


Correctness of calculations with struct timespec I've noticed some discrepancies in timings in our system, and I'm trying to narrow down what could be causing them.

I'm reviewing out time abstraction, and as far as I can determine it's fine.

Am I missing anything, and is it portable (besides being constrained to POSIX)?

typedef struct timespec Time;
static inline Time getTime() {
    static struct timespec time;
    clock_gettime(CLOCK_MONOTONIC, &time);
    return time;
}
static inline __constant Time timeAdd(Time oldTime, Time time) {
    if (time.tv_nsec + oldTime.tv_nsec >= 1E9)
        return (Time){
            tv_sec: time.tv_sec + oldTime.tv_sec + 1,
            tv_nsec: time.tv_nsec + oldTime.tv_nsec - 1E9
        };
    else
        return (Time){
            tv_sec: time.tv_sec + oldTime.tv_sec,
            tv_nsec: time.tv_nsec + oldTime.tv_nsec
        };
}
static inline __constant Time timeDiff(Time oldTime, Time time) {
    if (time.tv_nsec < oldTime.tv_nsec)
        return (Time){
            tv_sec: time.tv_sec - 1 - oldTime.tv_sec,
            tv_nsec: 1E9 + time.tv_nsec - oldTime.tv_nsec
        };
    else
        return (Time){
            tv_sec: time.tv_sec - oldTime.tv_sec,
            tv_nsec: time.tv_nsec - oldTime.tv_nsec
        };
}
static __always_inline __constant double timeSeconds(Time time) {
    return time.tv_sec + time.tv_nsec/1E9;
}
static inline double timeSince(Time oldTime) {
    struct timespec time;
    clock_gettime(CLOCK_MONOTONIC, &time);
    return timeSeconds(timeDiff(oldTime, time));
}

I can see nothing wrong, but I think it is not optimal.  My compiler warns me
about floating point conversions of those '1E9' constants.  If I rewrite your
timeAdd as follows, the code is easier to read and the generated code is
significantly smaller:

#define BILLION 1000000000
Time timeAdd(Time t1, Time t2)
{
    long sec = t2.tv_sec + t1.tv_sec;
    long nsec = t2.tv_nsec + t1.tv_nsec;
    if (nsec >= BILLION) {
        nsec -= BILLION;
        sec++;
    }
    return (Time){ .tv_sec = sec, .tv_nsec = nsec };
}

The same goes for the other functions, I think.


Create a list of random numbers with sum = n I want to create a list of random integers in the range [0, 9], that sums up to 100 in Excel, using VBA. The list should be printed in a single column.

The routine I've written is as follows:

Sub RandomList()
    Dim arr(100) As Integer
    Dim i As Integer

    i = 0
    Do
        arr(i) = Int(10 * Rnd())
        i = i + 1
    Loop Until WorksheetFunction.Sum(arr) >= 100

    arr(i - 1) = 100 - WorksheetFunction.Sum(arr) + arr(i - 1)
    Range("A1").Resize(i, 1) = Application.Transpose(arr)

End Sub

This gives the correct result, but I'm sure there are ways to improve it:

Initializing the size to 100, seems odd. I want to use a dynamic sized array, but I can't get it to work. I've tried different approaches, but all result in a list containing only zeros (or an error).
I tried to sum all elements except the last one, but I didn't manage to make it work. Therefore I had to sum all elements, and subtract the last one. I can't believe that's optimal.
Should I delete the (100-i) last elements of the list somehow, before writing it to Excel? How and why?
Is the last line a good way of writing to Excel, or is there a better way?
I'm looking for a nice and clean way of doing this task, not necessarily the fastest way

I can do the same thing using Function RandomList() too, but as far as I can tell, that's used when I want to call the function from the worksheet.

PS! I'm not interested in some builtin function that can do the task directly, as I'm doing this to learn VBA, not to do that specific task.

This is inspired by this (bad) question on SO. There are other approaches there that can be used, but they are substantially different. I'm wondering if the way I'm doing this is a "good way" of doing it, or if it's filled with "Bad practice" code.

Your logic is hacky, and your array should be dynamic.
Then, you should generalise your function so it can be used in other circumstances.

Also, Logic Error:

You've *assumed* that you won't need more elements than your target sum. But what if Rnd() returns 100 zeroes? You'll get to i = 101, try to set the value of arr(101) and error because you only sized it for 100 elements. Hence why you need a dynamic array.

Dynamic array:

Dim dynamicArray () As Integer
ReDim dynamicArray (1 to 1)

Dim i As Long
For i = 1 to 100
    ReDim Preserve dynamicArray (1 to i)
Next i

Redim Preserve extends the dimension whilst preserving all the values already in it. It only works on the last dimension so if, for instance, you had a 2-D Array, you could only Redim Preserve the 2nd Dimension.

Better Logic:

Start a counter at 100 (call it remainder)
Add random Int from 0-9 to list
Remove Int from counter
Do until counter <= 0
Reduce the last Int by the negative amount now held by remainder

Like so:

Dim sumList() As Long
ReDim sumList(1 To 1)

Dim remainder As Long
remainder = 100

Dim i As Long
Dim rndNum As Double
Do Until remainder <= 0
    i = i + 1
    ReDim Preserve sumList(1 To i)
    rndNum = WorksheetFunction.Floor(10 * Rnd(), 0)
    sumList(i) = rndNum
    remainder = remainder - rndNum
Loop
sumList(i) = sumList(i) + remainder

Refactoring/Generalising:

Your sub is very specific (0-9, sum of 100, integers). Why not make it a function that accepts these things as parameters? Then, whenever you need any kind of random list, you can just call your function with whatever parameters
you need without writing a new one.

Parameters:

Allowed Value Range (2 parameters. A minValue and a maxValue)
targetSum
(Optional) level of precision (integers (0 DP), 1 Decimal Place, 2 etc.)

Mathematical Note:

Allowing for any value space (say, numbers from 2.7 to 3.81 with values of 3 decimal places):

First, compute the size of the space (max - min). For a range of 2 to 7, the size would be 7-2 = 5.
We then add an extra buffer so that Floor() has an equal chance of hitting the top of our value space. This will be 1 * 10 ^ (-numDecimalPlaces).
We then multiply Rnd() by the size of the space to get a random position within our value space.
Then add that value to our minValue, and Floor() to the appropriate level of precision.

Function:

Public Function RandList(ByVal minValue As Double, ByVal maxValue As Double, ByVal targetSum As Double, Optional ByVal numDecimalPlaces As Long = 0) As Double()

    sumTotal = WorksheetFunction.Floor(sumTotal, numDecimalPlaces) '/ In Case, e.g. the total is 100.24 but we're only working in whole numbers

    Dim sumList() As Double
    ReDim sumList(1 To 1)

    Dim remainder As Double
    remainder = targetSum

    Dim valueSpace As Double
    valueSpace = maxValue - minValue + 1 * 10 ^ (-numDecimalPlaces) '/ 1 * 10 ^ (-numDecimalPlaces) is our Floor() buffer so we can still hit the top of the value space.

    Dim i As Long
    Dim rndNum As Double
    Do Until remainder <= 0
        i = i + 1
        ReDim Preserve sumList(1 To i)
        rndNum = WorksheetFunction.Floor(minValue + (Rnd() * valueSpace), numDecimalPlaces)
        sumList(i) = rndNum
        remainder = remainder - rndNum
    Loop
    sumList(i) = sumList(i) + remainder

    RandList = sumList

End Function

Which you can then call like so:

Public Sub DescriptiveName()

    Dim sumList() As Double
    sumList = RandList(0, 9, 100)

    '/ Stuff to print sumList goes here

End Sub

N.B. Thanks to @arcadeprecinct and @raystafarian for suggestions and improvements.


Pascal's Triangle - Java Recursion This is a fully functional implementation of a program to ask the user for a location on Pascal's Triangle, but I kind of cheated by expanding the base case to include row 0 and the 1st and last columns. I feel like this isn't a great approach, but I'm not quite sure why. (Note: I'm not a complete beginner, but I'm definitely not an experienced programmer by any definition)

import java.util.Scanner;
public class Pascal {
    public static void main(String[] args) {
        int r, c;
        Scanner sc = new Scanner(System.in);
        System.out.println("Row #");
        r = sc.nextInt();
        while (r != -1)
        {
        System.out.println("Column #:");
        c = sc.nextInt();
        System.out.println("\n" + calcPascal(r, c));
        //Just here for the while loop
        System.out.println("\nRow #");
        r = sc.nextInt();
        }
    }

    public static int calcPascal(int row, int column)
    {
        int pasVal;
        if (column == 0 || column == row || row == 0)
        //
        {
            pasVal = 1;
        }
        else
        {
            pasVal = calcPascal(row - 1, column - 1) + calcPascal(row - 1,
            column);
        }
        return pasVal;
    }
}

Thanks for sharing your code.
Comments
Your code has (essentially) only one comment.
Comments should explain why the code is like it is. Your (first) comment is a good example.
Naming
Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers.
Please read (and follow) the Java Naming Conventions. The name of your base class starts with a lower case letter which should be upper case instead.
Avoid Single Character Names and Abbreviations
Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable or you will have to "reuse" variable names for different, possibly unrelated contexts. This makes your code hard to read and understand for other people (keep in mind that you are that other person too, if you look at your code in a few months!) The same is true for abbreviations. You might find them obvious today, while you're actively dealing with the problem, but you might have to "relearn" them if you worked on something else for a while.
On the other hand, Java's identifier names can be virtually unlimited in length. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.
Define Variables as Late as Possible
You define your variables at the beginning of main. But the variable c is used only within the loop. This makes it hard to move the coin drop code to its own method. Your IDE's automated refactoring will introduce both an extra parameter and an unneeded return value. So always declare variables just before their first use unless they are magic numbers.
Magic Numbers
Your code has some magic numbers. They are literal values with a special meaning like here:
while (r != -1)
//...
    if (column == 0 || column == row || row == 0) {
        pasVal = 1;

You should introduce constants with meaningful names:
public static final int LOWEST_INDEX = 0;
public static final int TRIANGLE_START_NUMBER = 1;
public static final int INVALID_INDEX = -1;
// ...

while (r != INDEX)
//...
    if (column == LOWEST_INDEX || column == row || row == LOWEST_INDEX){
        pasVal = TRIANGLE_START_NUMBER;


Flattening a nested record to its leaves Note, I discovered a bug after I posted this. The current implementation drops any fields that have an associative value, which is not the intended behavior.

I'm writing a Tamagotchi clone, and need to be able to save the game's state to the disk. I want to save the entire state since it contains data other than the pet data like settings. Since de/serializing nested records is a pain, I decided to "flatten the nested records to their leaves". By that I mean if I have a record representing the game settings:

(defrecord Sim-Settings [health-per-tick pain-per-tick hunger-per-tick])
(defrecord Question-Settings [pain-per-wrong food-per-right])

(defrecord Settings [sim-settings question-settings])

(def test-settings
  (->Settings
    (->Sim-Settings 1 1 1)
    (->Question-Settings 1 1)))

I want to flatten that to:

(flatten-to-leaves test-settings)

{:health-per-tick 1,
 :pain-per-tick 1,
 :hunger-per-tick 1,
 :pain-per-wrong 1,
 :food-per-right 1}

All of the intermediate keys (:sim-settings and question-settings) are removed.

After struggling for a couple hours, I finally managed to get something working, but it's not perfect. All the solutions to similar problems I could find used tree-seq, which I had never used before. It's a cool function, but I'm afraid I might be forcing its usage here.

(defn flatten-to-leaves [record]
  (into {}

    (filter
      ; ... and filter out the non-leaves.
      #(and (map-entry? %)
            (not (associative? (second %))))

      ; Turn the record into a list of nodes of the map...
      (tree-seq associative? (partial apply list) record))))

Parts of it are nice. I like how tree-seq basically just turned this into a filtering problem.

My main problem is with the filtering function though. It is, I hate to admit, a product of fiddling. It works in every test case I've thrown at it, but something about it seems off. I have a feeling it can be reduced to something simpler.

I appreciate any critique regarding this code.

If I flatten the entire state:

(defrecord Pet [satiation max-satiation health max-health])
(defrecord Question-Generator [operator-ranges])
(defrecord Sim-Settings [health-per-tick pain-per-tick hunger-per-tick])
(defrecord Question-Settings [pain-per-wrong food-per-right])
(defrecord Settings [sim-settings question-settings])

(defrecord Game-State [pet q-gen last-update settings])

I get something like:

{:max-satiation 100,
 :hunger-per-tick 0.00347,
 :pain-per-tick 0.00347,
 :satiation 100,
 :pain-per-wrong 2,
 :max-health 100,
 :health-per-tick 0.0075,
 :last-update "20170905T204200.285Z",
 :food-per-right 5,
 :health 100}

I think this is good usage of tree-seq. It's intended for walking trees, right? If your settings will have ragged depth it's probably the cleanest approach.

The only main cleanup I see is that this predicate can be pointfree if you want:

#(and (map-entry? %)
      (not (associative? (second %))))
; =
(every-pred map-entry? (comp not associative? second))

On the other hand, I don't see a huge need for records here at all, as opposed to maps.

Nested maps will de/serialize fine as-is with EDN (or JSON if there's nothing crazy in them)
They're idiomatic across the Clojure community
Define a clojure.spec spec for them if you want
Records don't give you type safety anyway, and you're not using any of their class-abilities like extending protocols.
Records are a bit faster if you're building thousands, but that doesn't look like the case here


Move up, right, left and down functions I have some code which moves the users position up, right, down or left depending on the direction entered.

function up(field, player) {
    player.column = player.column + 1;
    field[player.row][player.column] = 'P';
}

function right(field, player) {
    player.row = player.row + 1;
    field[player.row][player.column] = 'P';
}

function down(field, player) {
    player.column = player.column - 1;
    field[player.row][player.column] = 'P';
}

function left(field, player) {
    player.row = player.row - 1;
    field[player.row][player.column] = 'P';
}

The code works fine for what I need, but I was curious if there is a more efficient way of writing the 4 functions above? As in maybe use one function rather than 4?

note
Edge cases will be implemented - if the next position is greater than the dimensions of the field, etc. So I'm not sure if this will impact making it more efficient

How about

function move(field, player, dx, dy) {
    player.column = player.column + dx;
    player.row = player.row + dy;
    field[player.row][player.column] = 'P';
}

and instead of calling up(field, player), call move(field, player, 0, -1)? With your input, that would basically be

switch(input) {
case 'up':
    move(field, player, 0, -1);
    break;
case 'right':
    move(field, player, 1, 0);
    break;
case 'left':
    move(field, player, -1, 0);
    break;
case 'down':
    move(field, player, 0, 1);
    break;
}

I assume you'll have more code, like checking if the move is valid, resetting the field at the current player position, etc., which won't be duplicated this way. A more complete example might be

function move(field, player, dx, dy) {
    // Valid move?
    let newColumn = player.column + dx;
    let newRow = player.row + dy;
    if (newColumn < 0 || newColumn >= WIDTH ||
        newRow < 0 || newRow >= HEIGHT)
        return;
    // Player cannot hit wall
    if (field[newRow][newColumn] == 'X')
        return;

    // Make move
    field[player.row][player.column] = ' ';
    player.column = newColumn;
    player.row = newRow;
    field[player.row][player.column] = 'P';
}

  Edge cases will be implemented - if the next position is greater than the dimensions of the field, etc. So I'm not sure if this will impact making it more efficient

It might seem unnecessary to verify newColumn when you're making a move in the y (row) direction, but comparisons like that are extremely cheap and you shouldn't be worried about their performance.


Bencode “Parser” in Python 3 class BencodeObject:

def __init__(self,filename):
    with open(filename,'rb') as diskbytes:
        self.loads(diskbytes)

def _isdictionary(self,bits): return(bits == b"d")
def _isnumber(self,bits): return(bits > b"/" and bits < b":")
def _iscolon(self,bits): return(bits == b":")
def _isint(self,bits): return(bits == b"i")
def _islist(self,bits): return(bits == b"l")
def _isend(self,bits): return(bits == b"e")
def _isnull(self,bits): return(bits == b"")

def loads(self,bcbuffer):
    tokens = []
    null = b""
    numbuffer = null # a buffer for storing number bytes
    last = []
    while True:
        atom = bcbuffer.read(1)
        if self._isdictionary(atom): last.append(atom)
        elif self._isnumber(atom):
            numbuffer += atom
        elif self._iscolon(atom):
            tokens.append(bcbuffer.read(int(numbuffer)))
            numbuffer = null
        elif self._isint(atom): last.append(atom)
        elif self._islist(atom): last.append(atom)
        elif self._isend(atom):
            char = last.pop()
            if self._isint(char):
                tokens.append(int(numbuffer))
                numbuffer = null
        else: break
    self.bytestrings = tokens
    self.trackerURL = str(self.bytestrings[1],"utf-8")

Looking for whatever input I can get.

class BencodeObject:

Putting object inside Class names is generally not a good idea, because it doesn't tell me anything.

def __init__(self,filename):
    with open(filename,'rb') as diskbytes:
        self.loads(diskbytes)

def _isdictionary(self,bits): return(bits == b"d")

There is no need for the parens around the expression. They just clutter things

def _isnumber(self,bits): return(bits > b"/" and bits < b":")

That's a confusing way to express this. Instead use bits >= b'0' and bits <= '9'

def _iscolon(self,bits): return(bits == b":")
def _isint(self,bits): return(bits == b"i")
def _islist(self,bits): return(bits == b"l")
def _isend(self,bits): return(bits == b"e")
def _isnull(self,bits): return(bits == b"")

Its not clear how useful these functions are. You call them once, and calling them isn't shorter then just checking the string for equality in the first place. Also the pythons style guide recommends using underscores_to_seperate_words. As it is I keep reading isend as i send.

def loads(self,bcbuffer):
    tokens = []
    null = b""
    numbuffer = null # a buffer for storing number bytes

I'm not sure a constant for an empty string is neccessary. If you insist I suggest it should be a global constant.

    last = []

Last suggests, well, last. But this is more of a stack. I think it could have a better name

    while True:
        atom = bcbuffer.read(1)
        if self._isdictionary(atom): last.append(atom)

Mixing between on-the-same-line, and on-the-next lines within a string of if-elifs looks ugly and makes it harder to read. I'm generally not a fan of putting the body on the same line as the if expression. But it really doesn't work when you mix both styles.

        elif self._isnumber(atom):
            numbuffer += atom
        elif self._iscolon(atom):
            tokens.append(bcbuffer.read(int(numbuffer)))
            numbuffer = null
        elif self._isint(atom): last.append(atom)
        elif self._islist(atom): last.append(atom)

You last.append(atom) a lot. Consider or to combine the conditions

        elif self._isend(atom):
            char = last.pop()
            if self._isint(char):
                tokens.append(int(numbuffer))
                numbuffer = null
        else: break

You don't distinguish between finding invalid characters and the end of the file. In both case you just quit. I'd recommend throwing an exception if you find an invalid character.

    self.bytestrings = tokens

But the tokens also include numbers. So storing them in bytestrings is kinda odd.

    self.trackerURL = str(self.bytestrings[1],"utf-8")

Your loop follows the common pattern of building data structures over several iterations of the loop and then consuming them. Don't do that. It ends up being hard to follow the logic of the function because I've got to figure out what happens over several iterations of the loop. Instead, each iteration of the loop should handle a logical unit.

Here is how I'd approach the problem:

def read_number(bcbuffer, terminator):
    read_byte = lambda: bcbuffer.read(1)
    bytes_iter = iter(read_byte, terminator)
    text = ''.join(bytes_iter)
    return int(text)

def parse_tokens(self, bcbuffer):
    tokens = []

    while True:
        atom = bcbuffer.read()
        if atom == b'i':
            tokens.append( read_number(bcbuffer, b'e') )
        elif atom >= b'0' and atom <= b'9':
            length = read_number(bcbuffer, b':')
            tokens.append( bcbuffer.read(length) )
        elif atom in b"lde":
            pass # ignore the structure which we don't care about
        elif atom == b'':
            break
        else:
            raise IOError('Did not expect %s' % atom)

   return tokens

Notice that I don't have a collection of variables to store partial results. Because each iteration of the loop handles a single "token" I don't need to store data other then my result across the iterations. It is also much clearer, I think, what is going on in the parsing.

I've not tested this code in anyway, use at own risk. I've ignored the possiblity of invalid bencodes. read_number will end up in an infinite loop if it cannot find the terminator. non-digits before the terminator will cause int to throw a ValueError. Various methods to handle those exist. I'd probably wrap file.read() to throw an exception when trying to read past the end of the file.


extending Exception to allow for auto appending class name on exception message Got this idea from the php.net website on extending exceptions. The main thing I wanted with this was to have the exception name auto imprinted on the exception message, so I wouldn't have to write it in each message. So far its working, just wondering if this is efficient or not?

Thanks

class DataException extends Exception
{
   protected $solved;
   protected $howSolved;

   public function __construct($message, $solved = false, $howSolved = null,
                               $code = 0, Exception $previous = null)
   {
      $this->solved = $solved;
      $this->howSolved = $howSolved;

      // make sure everything is assigned properly
      parent::__construct($message, $code, $previous);
   }

   public function setSolved($isSolved)
   {
      $this->solved = $isSolved;
   }

   public function setHowSolved($howSolved)
   {
      $this->howSolved = $howSolved;
   }

}

class GeoCoordinateOutOfBoundsException extends DataException
{
   public function __construct($message, $solved = false, $howSolved = null,
                               $code = 0, Exception $previous = null)
   {
      $message = get_class($this) . "::" . $message;

      // make sure everything is assigned properly
      parent::__construct($message, $solved, $howSolved, $code, $previous);
   }
}

Changing an inherited method signature isn't a good idea. It means how you call a method changes depending on what exact class you're calling.

Exception::__construct has only 3 arguments, but the first of which can be anything. As such you could do:

class DataException extends Exception
{
   protected $solved;
   protected $howSolved;

   public function __construct($message = null, $code = 0, Exception $previous = null)
    {
    $solved = $howSolved = false;
    if (is_array($message))  {
        $solved = $message['solved']; // message is an array
        ...
        $message = $message['message']; // and now it's a string to be used/compatible with the parent
    }

Which would work whether $message was a string or an array - and without changing the method signature.

Why do you have setters for properties on a exception? Sounds like you're using exceptions for something they aren't designed.


Array of pointers data structure Does this data structure make sense? It's essentially a vector of pointers, intended to point to larger objects. In effect, it gives the benefit of a linked list, with an \$O(1)\$ lookup at the cost of maintaining an array of pointers to each element.

What edge cases am I missing, and what's the formal name of this data structure? (What's the standard data structure used in such situations?)

#include<iostream>
#include<vector>
using namespace std;
template <class T>
class pointerArray
{

    vector<void*> addresses;
    public:
    pointerArray(int initialSize=100)
    {
        addresses.resize(initialSize);
    }
    ~pointerArray()
    {
        for(unsigned int i=0;i<addresses.size();i++)
        {
            if(addresses[i]!=0)
            {
                delete (T*)addresses[i];
            }
        }
    }
    T& operator[](unsigned int pos)
    {
        if(pos >= addresses.capacity())
        {
            addresses.resize(pos*2);
        }
        if(addresses[pos] == 0)
        {
            T* ptr = new T;
            addresses[pos] = ptr;
        }
        return *(T*)(addresses[pos]);

    }
};

int main()
{
    pointerArray<string> pa(100);
    for(int i=0;i<10000;i++)
    {
        pa[i]="Hello World This Is a Very Long String";
    }
    for(int i=0;i<10000;i++)
    {
        cout<<pa[i]<<endl;
    }
}

I don't think that this data structure has any special name(vector of pointers sounds reasonable).

Now about the code itself:

I do not see any reason to use void* pointers here and cast them explicitly every time you access an element. You can just use vector<T*> addresses and get rid of all casts. You can also use smart pointers(unique_ptr looks like a good choice here). Here is my version of this class:

template<class T>
class PointerArray {
public:
    PointerArray(size_t initialSize = 100): array(initialSize) {}

    T& operator[](size_t pos) {
        if (pos >= array.size()) {
            size_t newSize = std::max(pos + 1, 2 * pos);
            array.resize(newSize);
        }
        if (!array[pos]) {
            array[pos] = std::unique_ptr<T>(new T()); // or std::make_unique in C++14
        }
        return *array[pos];
    }

private:
    std::vector<std::unique_ptr<T>> array;
};

There no need for a custom destructor anymore(unique_ptr handles it).
Note that I have added this line: int newSize = std::max(pos + 1, 2 * pos);. Why is it necessary? We need it when the initialSize is 0 and so is pos.
In this line: if(pos >= addresses.capacity()), you should be comparing pos to the vector's size, not capacity(because it is an undefined behavior to access elements of the vector beyond size).
More general notes:

using namespace std; is a bad practice. There is no need to pollute global namespace.
Binary operators are usually surrounded with whitespaces. It is also conventional to have an empty line between different functions to improve readability.

And the last one: do have good reasons to use this data structure? In my opinion, as long as a simple std::vector<T> works fine, there is no need to invent any new data structures.


Improving Async/Await Javascript Code I'm working on a data analytics dashboard in Node.js as a portfolio piece. I've built a pipeline that gets the data where it needs to be for more processing, however, I feel the below code can be improved but it overlaps with my inexperience with Node.js and async/await.
The below code looks redundant to my eye. I tried to move the second function into the first in an anonymous async function to no avail, and was wondering if the more experience members here had any suggestions?
async function readFilteredStream() {
    filteredStream = streamConnect(); //Connects to API
    const results = await readStream(filteredStream); //Reads in a sample of data and closes the connection.
    return { data: results };
}

async function respondWithSamples() {
    const results = await readFilteredStream();
    return results;
}

In ES6, when you have a variable that's going to be used as a property of an object, you can use the same variable name as the property so as to use shorthand syntax, if you want:
const data = await readStream(filteredStream); //Reads in a sample of data and closes the connection.
return { data };

You do:
filteredStream = streamConnect();

You are assigning to an outer variable named filteredStream. Do you declare and use filteredStream elsewhere? If not, then this is a bug - you're either implicitly creating a property on the global object, or (if you enable strict mode), an error will be thrown. Always declare variables before using them. You might have wanted to do:
async function readFilteredStream() {
    const filteredStream = streamConnect(); //Connects to API
    const data = await readStream(filteredStream); //Reads in a sample of data and closes the connection.
    return { data };
}

The respondWithSamples function doesn't do anything useful. It calls readFilteredStream and returns it. It would be easier and make more sense to just use readFilteredStream instead, and remove respondWithSamples - all you're doing is creating another wrapper around the Promise, one which will be resolved wherever the Promise is unwrapped.


Speeding up nested for-loop analysis code I have two matrices, the first one is mat 2000*500, the second one is 6000*500 tep
I did this code for some analysis to get another matrix that has a specific elements.

Problem is :
This code is very very slow, I need to make faster.Any suggestion to do so is welcome

mat=matrix(sample(c(0,1,2),200,replace =T),nrow=500,ncol=2000)
tep =matrix(rnorm(200,5,2),nrow=500,ncol=6000)`

The code is trying to create one matrix (500 row by 2000 col). Its elements depend on the following :
Let the new matrix is A .

if mat[1,1] = 0 then A[1,1]=tep[1,1]/(sum(tep[1,1:3]))
if mat[1,1] = 1 then A[1,1]=tep[1,2]/(sum(tep[1,1:3]))
if mat[1,1] = 2 then A[1,1]=tep[1,3]/(sum(tep[1,1:3]))
if mat[1,2] = 0 then A[1,2]=tep[1,4]/(sum(tep[1,4:6]))
if mat[1,2] = 1 then A[1,2]=tep[1,5]/(sum(tep[1,4:6]))
if mat[1,2] = 2 then A[1,2]=tep[1,6]/(sum(tep[1,4:6]))`
......

and so on..
 The one column in mat is corresponding to three columns in tep.
Every three values in three columns in matrix tep at a j row is a group we calculate from each group there will be one value according to the example above, so we will end up with a 500 row by 2000 column matrix.

allele=c(0,1,2)
A=matrix(nrow=500,ncol=2000)
 start=seq(1,6000,3)
for(k in 1:500){
for(i in 1:2000){
for(j in start){
  temp.z= mat[k,i]
  temp.pl=tep[k,j:(j+2)]
  loc=which(allele==temp.z)
  temp.pl=temp.pl[loc]/(sum(temp.pl))
  A[k,i]=temp.pl
  rm(temp.pl,temp.z,loc)

      }
   }
}

Try the following:

mat0 <- tep[, c(TRUE, FALSE, FALSE)]
mat1 <- tep[, c(FALSE, TRUE, FALSE)]
mat2 <- tep[, c(FALSE, FALSE, TRUE)]

denominator <- mat0 + mat1 + mat2
numerator   <- mat0 * (mat - 1) * (mat - 2) / (0 - 1) / (0 - 2) +
               mat1 * (mat - 0) * (mat - 2) / (1 - 0) / (1 - 2) +
               mat2 * (mat - 0) * (mat - 1) / (2 - 0) / (2 - 1)

A <- numerator / denominator


Troublesome Frog (AIO Intermediate 2013) 3.x Recently I was trying out this problem and my code got 60% of the marks, with the remaining cases returning TLEs.

  Bazza and Shazza do not like bugs. They wish to clear out all the bugs
  on their garden fence. They come up with a brilliant idea: they buy
  some sugar frogs and release them near the fence, letting them eat up
  all the bugs.

  The plan is a great success and the bug infestation is gone. But
  strangely, they now have a sugar frog infestation. Instead of getting
  rid of the frogs, Bazza and Shazza decide to set up an obstacle course
  and watch the frogs jump along it for their enjoyment.

  The fence is a series of \$N\$ fence posts of varying heights. Bazza and
  Shazza will select three fence posts to create the obstacle course,
  where the middle post is strictly higher than the other two. The frogs
  are to jump up from the left post to the middle post, then jump down
  from the middle post to the right post. The three posts do not have to
  be next to each other as frogs can jump over other fence posts,
  regardless of the height of those other posts.

  The difficulty of an obstacle course is the height of the first jump
  plus the height of the second jump. The height of a jump is equal to
  the difference in height between it's two fence posts. Your task is to
  help Bazza and Shazza find the most difficult obstacle course for the
  frogs to jump.

  Input
  Your program should read from the file. The file will describe
  a single fence.

  The first line of input will contain one integer \$N\$: the number of
  fence posts. The next \$N\$ lines will each contain one integer \$h_i\$: the
  height of the ith fence post. You are guaranteed that there will be at
  least one valid obstacle course: that is, there will be at least one
  combination of three fence posts where the middle post is strictly
  higher than the other two.

  Output
  Your program should write to the file. Your output file should
  contain one line with one integer: the greatest difficulty of any
  possible obstacle course.

  Constraints
  To evaluate your solution, the judges will run your
  program against several different input files. All of these files will
  adhere to the following bounds:

  \$3 \leq N \leq 100,000\$ (the number of fence posts)
  \$1 \leq h_i \leq 100,000\$ (the height of each post)

  As some of the test cases will be quite large,
  you may need to think about how well your solution scales for larger
  input values. However, not all the cases will be large. In particular:

  For 30% of the marks, \$N \leq 300\$. For an additional 30% of the
  marks, \$N \leq 3,000\$. For the remaining 40% of the marks, no special > constraints apply.

Hence, I was wondering if anyone could think of a way to optimize my code (below), or perhaps provide a more elegant, efficient algorithm than the one I am currently using.

Here is my code:

infile = open('frogin.txt', 'r')
outfile = open('frogout.txt', 'w')

N = int(infile.readline())

l = []

for i in range(N):
    l.append(int(infile.readline()))

m = 0
#find maximum z-x+z-y such that the middle number z is the largest of x, y, z
for j in range(1, N - 1):
    x = min(l[0: j])
    y = min(l[j + 1:])
    z = l[j]
    if x < z and y < z:
        n = z - x + z - y
        m = n if n > m else m

outfile.write(str(m))

infile.close()
outfile.close()
exit()

If you require additional information regarding my solution or the problem, please do comment below.

Without going into the algorithm I see a few things that could be improved upon

Use with open(...) as ... instead of manually opening and closing
Use max() instead of the ... if ... else ... structure
Improve naming of your variables, PEP8 is a good guideline
Use if __name__ == __main__:
List comprehension at reading input

def froggin(fences):
    maximum = 0
    for idx in range(1, N - 1):
        left = min(fences[0: idx])
        right = min(fences[idx + 1:])
        middle = fences[idx]

    if left < middle and right < middle:
        new_max = middle - left + middle - right
        maximum = max(new_max, maximum)
    return maximum

if __name__ == '__main__':
    with open('frogin.txt', 'r') as infile:
        N = int(infile.readline())
        fences = [int(infile.readline()) for _ in range(N)]

    result = froggin(fences)

    with open('frogout.txt', 'w') as frogout:
        frogout.write(str(result))


Find all integral coordinates given top left corner and bottom right corner of a rectangle Here is the problem I am working on -

  There is an \$N \times N\$ field on which missiles are being bombarded. Initially,
  all the cells in this field have the value \$0\$. There will be \$M\$ missiles
  bombarded on this field. The \$i\$th missile will have power \$P_i\$ and it will
  affect all the cells in region with \$(A_i,B_i)\$ as top-left corner and
  \$(C_i,D_i)\$ as bottom-right corner. Because of missile, value of all the
  cells in this rectangle will get XORed with \$P_i\$.

  After all the missiles have been bombarded, you have to find out
  values in each cell of this field.

Here is what I have tried -

N = 3
M = 3
missiles = [[3,3,1,3,2],
[2,2,1,2,2],
[3,1,1,2,3]]

from itertools import product
# Logic
coords = {}
for i in missiles:
    Pi, Ai, Bi, Ci, Di = i
    for j in product(*[range(Ai-1, Ci), range(Bi-1, Di)]):
        if coords.get(j):
            coords[j] ^= Pi
            #[NxN[i[0]][i[1]] ^= Pi
        else:
            coords[j] = 0 ^ Pi

def print_grid(coords, N):
    count = 0
    for i in product(*[range(N), range(N)]):
        if i in coords:
            print(coords[i], "",end="")
        else:
            print(0, "",end="")
        count+=1
        if count%N==0:
            print()

print_grid(coords, N)

Output -

3 3 3
1 1 3
3 3 0

Exactly does what I want, but I was wondering is there a way to optimize it for large inputs. Any help appreciated.

Since you commented that using numpy is OK for you, you can simplify the whole rectangle computation using its advanced slicing capabilities:

>>> # Let's define a square array
...
>>> a = np.array(range(25)).reshape((5, 5))
>>> a
array([[ 0,  1,  2,  3,  4],
       [ 5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14],
       [15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24]])
>>> # Advanced slicing allow us to extract blocks at once
...
>>> a[2:5, 1:3]
array([[11, 12],
       [16, 17],
       [21, 22]])

You just need to encapsulate this behaviour in a class for ease of use:

import numpy as np

class BattleField:
    def __init__(self, size):
        self.field = np.zeros((size, size), dtype=int)

    def receive_missile(self, power, top, left, bottom, right):
        self.field[top-1:bottom, left-1:right] ^= power

    def __str__(self):
        return str(self.field)

if __name__ == '__main__':
    missiles = [
        [3,3,1,3,2],
        [2,2,1,2,2],
        [3,1,1,2,3],
    ]
    field = BattleField(3)
    for missile in missiles:
        field.receive_missile(*missile)
    print(field)

Other points to improve from your code includes:

using more descriptive names than A, B, or C;
using functions instead of code at top-level for ease of testing/reuse;
using the if __name__ == '__main__' guard to avoid running some code when importing the file;
using direct parameters values instead of packing them in a list and unpacking them in the function call (product(*[range(N), range(N)]) => product(range(N), range(N)));
using dict.get with its default value (coords[j] = coords.get(j, 0) ^ Pi) to simplify the code.


Creating and reversing a linked list Here is my program which creates a linked list and reverses it:

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *next;
};
struct node *list=NULL;
struct node *root=NULL;
static int count=0;
struct node *create_node(int);//function to create node
void travel_list(void);
void create_list(int);
void reverse_list(void);
int main()
{
    int i, j, choice;
    printf("Enter a number this will be root of tree\n");
    scanf("%d", &i);
    create_list(i);
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    while (choice!=0){
     printf("Enter a no for link list\n");
        scanf("%d",&i);
//  printf("going to create list in while\n");
    create_list(i);
        travel_list();
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    }
    printf("reversing list\n");
     reverse_list();
     travel_list();
 }

// end of function main
void create_list (int data)
{
 struct node *t1,*t2;
 //printf("in fucntion create_list\n");
 t1=create_node(data);
 t2=list;
 if( count!=0)
 {
   while(t2->next!=NULL)
   {
   t2=t2->next;
   }
 t2->next=t1;
 count++;
 }
 else
  {
   root=t1;
   list=t1;
   count++;
  }
}
struct node *create_node(int data)
{
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
        temp->data=data;
    temp->next=NULL;
  //      printf("create node temp->data=%d\n",temp->data);
//  printf("the adress of node created %p\n",temp);
    return temp;
}
void travel_list(void )
{
 struct node *t1;
 t1=list;
 printf("in travel list\n");
 while(t1!=NULL)
 {
 printf("%d-->",t1->data);
 t1=t1->next;
 }
 printf("\n");
}
void reverse_list(void)
{
    struct node *t1,*t2,*t3;
       t1=list;
    t2=list->next;
    t3=list->next->next;
   int reverse=0;
   if(reverse==0)
   {
    t1->next=NULL;
    t2->next=t1;
    t1=t2;
    t2=t3;
    t3=t3->next;
    reverse++;

    }

    while(t3!=NULL)
     {

     t2->next=t1;
    t1=t2;
    t2=t3;
    list=t1;
    travel_list();
    t3=t3->next;
    }
    t2->next=t1;
    list=t2;
}

I am posting it for further review if there can be any improvements to the algorithm, etc.

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *next;
};
struct node *list=NULL;
struct node *root=NULL;
static int count=0;

Don't store data in global variables. It makes your code unreusable and harder to follow.

struct node *create_node(int);//function to create node
void travel_list(void);
void create_list(int);
void reverse_list(void);
int main()
{
    int i, j, choice;

Using variables like i and j only make sense if used in the sense of indexes. Otherwise, the code just gets harder to read. Choice is also not very informative.

    printf("Enter a number this will be root of tree\n");
    scanf("%d", &i);
    create_list(i);
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);
    while (choice!=0){
     printf("Enter a no for link list\n");
        scanf("%d",&i);

Use consistent indentation. Otherwise things will go downhill fast.

//  printf("going to create list in while\n");

Don't leave dead code in your code, that's what source control is for.

    create_list(i);
        travel_list();
    printf("Enter  1 to enter more numbers \n 0 to quit\n");
    scanf("%d", &choice);

Deja vu. Why isn't the previous instance doing the same thing done in the loop?

    }
    printf("reversing list\n");
     reverse_list();
     travel_list();
 }

// end of function main
void create_list (int data)

This function appends to the end of a list, it doesn't create it. Use function names that indicate what is really happening.

{
 struct node *t1,*t2;

t1 and t2 are very uninformative variable names.

 //printf("in fucntion create_list\n");
 t1=create_node(data);
 t2=list;
 if( count!=0)

This is the only place that count is used. Check whether list is null instead.

 {
   while(t2->next!=NULL)
   {
   t2=t2->next;
   }
 t2->next=t1;
 count++;
 }
 else
  {
   root=t1;

You don't ever seem to do anything with root.

   list=t1;
   count++;
  }
}
struct node *create_node(int data)
{
    struct node *temp;

The new node isn't really temporary

    temp = (struct node *)malloc(sizeof(struct node));
        temp->data=data;
    temp->next=NULL;
  //      printf("create node temp->data=%d\n",temp->data);
//  printf("the adress of node created %p\n",temp);
    return temp;
}
void travel_list(void )
{
 struct node *t1;
 t1=list;
 printf("in travel list\n");
 while(t1!=NULL)
 {
 printf("%d-->",t1->data);
 t1=t1->next;
 }
 printf("\n");
}
void reverse_list(void)
{
    struct node *t1,*t2,*t3;

This piece of code would be way easier to follow if you used real names

       t1=list;
    t2=list->next;
    t3=list->next->next;

This is going to fail for lists shorter then three elements

   int reverse=0;
   if(reverse==0)

This will always be true since you just assigned reverse = 0.

   {
    t1->next=NULL;
    t2->next=t1;
    t1=t2;
    t2=t3;
    t3=t3->next;
    reverse++;

You never use reverse again

    }

    while(t3!=NULL)
     {

     t2->next=t1;
    t1=t2;
    t2=t3;
    list=t1;
    travel_list();
    t3=t3->next;
    }
    t2->next=t1;
    list=t2;
}

My version of reverse_list (untested)

struct node * reverse_list(struct node * list)
{
    struct node *previous, *current;
    previous = NULL;
    current = list;
    while(current)
    {
        struct node * next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

}


Converting a range of integers from a string to an IEnumerable Goal

Convert the following into an IEnumerable of integers accounting for the x-y ranges:

"1,2,3,0,7,8,9,10-15"

to

{ 1, 2, 3, 0, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

Current implementation

I've written this little function and got something working, but I'm wondering if this can become more efficient or rich in features. My test cases all pass which cover positive and negative ranges.

public IEnumerable<int> GetRange(string numbers) {
    string[] items = numbers.Split(',');

    foreach (var item in items) {
        if (!string.IsNullOrWhiteSpace(item)) {
            //does it contain a -? it's a range then
            int result;
            if (item.Contains("-") && !item.EndsWith("-")) {
                int start, end;
                if (int.TryParse(item.Substring(0, item.IndexOf("-")), out start) && int.TryParse(item.Substring(item.IndexOf("-") + 1), out end)) {
                    int direction = start < end ? 1 : -1;
                    for (result = start; (direction == 1 ? result < end + direction : result > end + direction); result += direction)
                        yield return result;

                    continue;
                }
            }

            if (int.TryParse(item, out result)) {
                yield return result;
                continue;
            }

        }

        throw new InvalidCastException(string.Format("Unable to cast \"{0}\" to an int", item));
    }
}

Ok, some comments:

Code style

While there are no definitive laws about code style, most C# programmers are putting the opening brace { on a separate line. If someone else is going to read your code, they are likely to be annoyed.
Consider breaking up the method into smaller methods to clarify how it works, which is better than adding comments.

Nesting, minimizing nesting makes the code easier to read and in this case you can certainly remove a few levels, namely:

if (!string.IsNullOrWhiteSpace(item)) can be removed if you instead split the string with the parameter StringSplitOptions.RemoveEmptyEntries.
If the number cannot be parsed, you could throw the exception when TryParse returns false and keep the "happy path" code to run whenever TryParse is successful.

Error handling

Since it is TryParse that is failing, you should probably throw a FormatException to indicate invalid format or ArgumentException instead of InvalidCastException to indicate invalid input parameter. Since there is no casting that is failing within the code, this may confuse other developers when debugging the code.
Stricter validation of input data, for example, to handle the case with the method being invoked with the numbers parameter set to null.

Performance

There is always things to improve in this department, however, if the method is fast enough for you, I suggest focusing on readability.

Defect

Invoking the method with a negative range where the first number is negative will not work.


Serialize and deserialize a tree Suppose each node of a tree has maximum n children. I want to serialize and de-serialize for a tree. My current solution is doing pre-order traverse, and using # to represent None child.

I'm wondering if there are any better implementation method. My current concern for my code is if the tree has too many None node (kinds of sparse tree), there will be a lot # in the serialized string output. But I have not figured out a way to represent serialized tree better, since I think for None node, we still need some kinds of information to represent there is an empty node there.

I'm looking forward to any smart ideas on existing code and smart ideas to represent serialized tree in a better (more compact and more efficient -- for both serialize and de-serialize).

My print tree method is just for the purpose of verification. deserialize is correctly re-constructing the tree, so we can skip code review for this part.

number_of_children = 3
index = 0
class Node:
    def __init__(self, value):
        self.value = value
        self.children = [] # a list of Node

    def serialize(self, result): # serialzie a tree into a string
        result.append(str(self.value))
        for child in self.children:
            if child:
                child.serialize(result)
            else:
                result.append('#')

    def printTree(self): # print tree layer by layer
        current_level_buffer=[]
        current_level_buffer.append(self)
        current_level_count = 1
        next_level_count=0
        next_level_buffer=[]
        print_buffer=[]
        next_level_valid = 1
        while True:
            node = current_level_buffer.pop(0)
            if not node:
                print_buffer.append('#')
                current_level_count -= 1
            else:
                print_buffer.append(str(node.value))
                current_level_count -= 1
                for child in node.children:
                    next_level_buffer.append(child)
                    next_level_count += 1
                    if child:
                        next_level_valid += 1
            if current_level_count == 0:
                print ' '.join(print_buffer)
                current_level_count = next_level_count
                current_level_buffer = next_level_buffer
                next_level_count = 0
                next_level_buffer=[]
                print_buffer=[]
                if next_level_valid == 0:
                    return
                next_level_valid = 0

def deserialize(source):  # deserialize a string into a tree
    global index
    current_node = None
    if source[index] != '#':
        current_node = Node(source[index])
        for i in range(number_of_children):
            index += 1
            current_node.children.append(deserialize(source))
    return current_node

if __name__ == "__main__":
    root = Node(0)
    child11 = Node(1)
    child12 = Node(2)
    root.children.append(child11)
    root.children.append(child12)
    root.children.append(None)
    child21 = Node(3)
    child22 = Node(4)
    child23 = Node(5)
    child11.children.append(child21)
    child11.children.append(child22)
    child11.children.append(child23)
    child24=Node(6)
    child25=Node(7)
    child26=Node(8)
    child12.children.append(child24)
    child12.children.append(child25)
    child12.children.append(child26)

    leafnodes = [child21, child22, child23, child24, child25, child26]
    for leaf in leafnodes:
        leaf.children.append(None)
        leaf.children.append(None)
        leaf.children.append(None)

    root.printTree()
    result = []
    root.serialize(result)
    print result
    print ''.join(result)

    new_root = deserialize(''.join(result))
    new_root.printTree()

Your printTree function is unnecessarily long.

Also, I really don't like the output of your serialize. I was not able to parse (as a human) this back into the structure of the tree. For me it would be much better if the structure was apparent from the serialization.

Therefore I rewrote your code in the following way:

class Node:

    def __init__(self, value='#', children=None):
        self.value = value
        self.children = children if children else []

    def __nonzero__(self):
        return self.value != '#'

    def __eq__(self, other):
        return self.value == other.value and self.children == other.children

    def __str__(self):
        buf, out = [self], []
        while buf:
            # current level
            out.append(", ".join(str(node.value) for node in buf))
            if any(node for node in buf):
                # add children
                buf = [subnode if subnode else Node()
                       for node in buf
                       for subnode in node.children]
            else:
                break
        return "\n".join(out)

    def __repr__(self):
        if not self:
            return "Node()"
        children_repr = ",".join(repr(child) for child in self.children)
        return "Node({.value},[{}])".format(self, children_repr)

    def serialize(self):
        return repr(self).replace("Node", "").replace("()", "#")

    @staticmethod
    def deserialize(source):
        return eval(source.replace("#", "()").replace("(", "Node("))

if __name__ == "__main__":
    root = Node(1, [Node(2, [Node(4)]), Node(3, [Node(5), Node(6)])])
    print repr(root)
    print root
    source = root.serialize()
    root2 = Node.deserialize(source)
    print repr(root2)
    print root2
    assert root == root2

This class has the nice feature, that eval(repr(root)) is a copy of root, so repr(root) is a serialization of root.

The output of repr(root) is a bit verbose, though:

Node(1,[Node(2,[Node(4,[])]),Node(3,[Node(5,[]),Node(6,[])])])

Therefore I defined a serialize function, which just gets rid of all the Nodes. The deserialize function just puts them back in and does an eval.

Note that I used a different tree here than you. Here would be your structure:

root = Node(0, [Node(1, [Node(3, [Node(), Node(), Node()]),
                         Node(4, [Node(), Node(), Node()]),
                         Node(5, [Node(), Node(), Node()])]),
                Node(2, [Node(6, [Node(), Node(), Node()]),
                         Node(7, [Node(), Node(), Node()]),
                         Node(8, [Node(), Node(), Node()])]),
                Node()])

Or, even better to visualize:

root = Node(0, [Node(1, [Node(3, [Node(),
                                  Node(),
                                  Node()]),
                         Node(4, [Node(),
                                  Node(),
                                  Node()]),
                         Node(5, [Node(),
                                  Node(),
                                  Node()])]),
                Node(2, [Node(6, [Node(),
                                  Node(),
                                  Node()]),
                         Node(7, [Node(),
                                  Node(),
                                  Node()]),
                         Node(8, [Node(),
                                  Node(),
                                  Node()])]),
                Node()])

Example:

>>> root.serialize()
'(0,[(1,[(3,[#,#,#]),(4,[#,#,#]),(5,[#,#,#])]),(2,[(6,[#,#,#]),(7,[#,#,#]),(8,[#,#,#])]),#])'

This could be cut down even further, but at this point it becomes a balance between the processing time needed to make this string smaller and the gain in memory from that.

With this function it could become:

def serialize2(self):
    replacements = [("Node", ""), ("()", "#"),
                    ("(", ""), (")", ""), (",[", "["), (",", "")]
    out = repr(self)
    for replacement in replacements:
        out = out.replace(*replacement)
    return out

>>> root.serialize2()
'0[1[3[###]4[###]5[###]]2[6[###]7[###]8[###]]#]'

But this becomes hard to parse back into the tree and would break the setup of using __repr__ and eval. It would be possible using some fancy regular expressions, though.


Ideal FP/Scala way to vaildate rectangular list I am learning Scala and FP (Functional Programming), coming from Java, OO and a strong imperative pardigm. I am now trying to implement a small puzzle solving project so I can get some deeper hands on experience with both Scala and FP.

So, I have the following Scala class:

class Bitmap2d(rowsByColumns: List[List[Int]]) {
  if (!validateRectangular) {
    throw new IllegalArgumentException("all rows must have same length")
  }

  def validateRectangular: Boolean = {
    rowsByColumns.size == rowsByColumns.filter(_.size / rowsByColumns.first.size != 1)
  }
}

I am attempting to validate the single class constructor parameter. The requirements of a properly constructed instance of this class are:

The list is not null or empty.
The list contains at least one list which is itself not null or empty.
If the outer list contains more than a single inner list, validate all the inner lists are of identical length.

I was quite proud of figuring out how to implement validateRectangular in the FP style of immutability (my first try was the traditional Java imperative approach). However, upon further analysis, I am now not happy with it as it visits every row (as opposed to stopping the evaluation at the first row that fails to have the correct size).

So, here are my questions:

In Java, the null and non-empty checks are obvious. Do I need to perform these checks in Scala (where null seems to be quite abhored)? If so, what would be considered the idiomatically correct way to do so. If not, why must I check for it in Java, but not in Scala?
While my validateRectangular method works fine, I would prefer a fail fast test which stopped iterating as soon as a row had a size different than the first row (the first row's size is considered the baseline to which all the remaining rows must conform). So, what would be the ideal FP way to approach re-writing validateRectangular such that it properly validates all rows are the same size, but fails fast (stops iterating) as soon as the current row is of a different size?
What is the correct way to reject constructing an instance of a Scala class if the parameters are not correctly defined? In Java, I use the standard style of throwing an exception in the constructor after a parameter fails to validate. That's what I have implemented above. Is that considered idiomatic Scala?

UPDATE:

Here's the same class modified per Daniel C Sobral's suggestions:

class Bitmap2d(rowsByColumns: List[List[Int]]) {
  require(validateRectangular, "all rows must have same length")

  def validateRectangular: Boolean = {
    rowsByColumns.forall(_.size == rowsByColumns.head.size)
  }
}

In Scala, never use null unless some API requires it of you; use Option instead. If you have to interface with an API that returns null, convert the result into an Option. As long as you do that, you can ignore null checks, for they'll always be errors: you got a null from some code that shouldn't be producing it, or you forgot to convert some return value to Option, or else you didn't even know you had to.
Use exists or forall -- forall seems better suited, but either will do with the proper conditionals. Also, do not use first -- use head. Yeah, it looks weird, but head/tail is idiomatic, and faster.
There's a require function that is used for parameter validation. Either require(validateRectangular) or require(validateRectangular, "all rows must have same length") will do.

And, yes, validateRectangular was a good start, and for new comers to FP it is not obvious to implement something that will stop at the first incorrect size in functional style -- at least on a strict language like Scala. You'd either throw an exception or use recursion.


Bubblesort implementation in C++ The parameters list contain the array that is passed to and the size of the array respectively. Is there anywhere I could improve my code?

void bubbleSort(int a[], int s) {
    for (int i = 1; i < s; i++) {
        for (int j = 0; j < s - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

Performance of your implementation is \$\Theta(N^2)\$ in all cases. You can improve it by holding a boolean variable indicating whether the current pass over the array swapped at least once the neighbouring array components. If the boolean is false, the array is sorted and we can exit the sort:

void bubbleSort(int a[], int s) {
    for (int i = 1; i < s; i++) {
        bool swapped = false;

        for (int j = 0; j < s - i; j++) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }

        if (!swapped) {
            return;
        }
    }
}

The above alternative implementation runs in linear time on almost sorted arrays.

Also, as you can see above, #include <utility> offers you a swapping routine (std::swap); why not use it?

Hope that helps.


D3 stacked bar chart with linear x axis In all the examples I've come across so far, (like this, this or this) I see stacked charts in d3 have an ordinal scale. I presume this is because stacked charts are considered an extension of bar charts which are generally of ordinal scale on the one of the axis.

In my case, using sample data

{"a":[20,10],"b":[50,0],"c":[45,60],"d":[10,40]}

I need to generate a stacked chart with a linear scale x-axis like below.

(The width of each column is a scale of the sum of 2 elements of the array, and the 2 cells in each column represent the values of the array elements as a % of the height. The columns are sorted left to right on sum desc)

I tried to use d3.stack to generate such a chart using the below code, but this seems a little messy to me, as I'm accessing the data object of the stack array.

var body = d3.select('body');
var svg = body.append('svg').attr('height',200).attr('width',500);
var maing = svg.append('g');

var inputData = JSON.parse('{"a":[20,10],"b":[50,0],"c":[45,60],"d":[10,40]}')

// generate class
var colors = d3.schemeCategory10
var mysheet = document.styleSheets[0];

Object.keys(inputData).forEach(function(d,i){
  mysheet.insertRule(`.${d}{fill:${colors[i]}; opacity:0.8}`);
  mysheet.insertRule(`.${d}_h{fill:${colors[i]}; opacity:0.6}`);
});

// convert to flattened array
var vals = Array("p", "h");
var cumT = +0
var transformedData = Object.keys(inputData).map(function(d,i){
  let o = {}; o.mp = d;
  inputData[d].forEach(function(d,i){o[vals[i]]=d})
  o.t=o.p+o.h;
  return o;
}).sort(function(a,b){
  return b.t - a.t
}).map(function(d,i){
  let o = d; o.cumT = cumT += d.t
  return o;
})

var stack = d3.stack().keys(vals);
var stackData = stack(transformedData);

var g = maing.selectAll('g')
  .data(stackData).enter().append('g')

var x = d3.scaleLinear().domain([0,230]).range([0,100])  // TODO: use d3.max here
var y = d3.scaleLinear().domain([0,1]).range([0,140])    // some predefined height

g.selectAll('rect').data(function(d){return d})
  .enter().append('rect')
  .attr('x', function(d,i){return x(d.data.cumT-d.data.t)})
  .attr('y', function(d,i){return y(d[0]/d.data.t)})
  .attr('width', function(d,i){return x(d.data.t)})
  .attr('height', function(d,i){return y((d[1]-d[0])/d.data.t) })
  //.style('stroke-width', 1).style('stroke', 'black')
  .attr('class', function(d){
    return d3.select(this.parentNode).datum().key === "p" ? d.data.mp : d.data.mp+"_h";
  })
;
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Stack Dev</title>
    <style media="screen">

    </style>
  </head>
  <body>

    <script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
  </body>
</html>

What would be a better way to go about generating something like this? Especially if I have to generate many many small charts like this on a single page?

Before dealing with your main question here, which concerns the SVG rectangles, here are some advices:

Use an ordinal scale for the colors: instead of manipulating document.styleSheets and using classes, as you're doing right now, just create a proper ordinal scale...

var colorScale = d3.scaleOrdinal(d3.schemeCategory10);

... and use it to fill your rectangles, with style("fill", ...) method.
Don't call your scales x and y. Use more descriptive names, like xScale and yScale. Doing that, you avoid confusion with the x and y methods which are very common in D3, like in line generators or area generators, for instance.
Use d3.max in your yScale domain:

.domain([0, d3.max(transformedData, function(d) {
    return d.cumT
})])

The default domain in a D3 linear scale is ([0, 1]). Therefore, you don't need to set it in your yScale.

Back to your main issue:

Using a stack generator is "messy", according to you. However, "messy" is quite opinion based: for instance, I don't see anything messy here (except for those classes, which you don't need if you follow my advice about the color scale).

But if you still feel that using a stack generator creates a messy code here is my solution, using your non-stacked data array. First, pass your data array directly to the <g> elements as the data:

var g = maing.selectAll('g')
    .data(transformedData)
    .enter()
    .append('g');

Then, create the lower and upper rectangles using a each:

g.each(function(d, i){
    //code here
});

Inside the each you need two selections, one for the upper rectangles and other for the lower rectangles:

//these are the upper rectangles
var upperRect = d3.select(this).append("rect")
    .attr("x", function() {
        return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(0))
    .attr("width", function() {
        return xScale(d.t)
    })
    .attr("height", function() {
        return yScale(d.p / d.t)
    })
    .style("fill", function() {
        return colorScale(i)
    })
    .style("opacity", .8);

//and these are the lower rectangles
var lowerRect = d3.select(this).append("rect")
    .attr("x", function() {
        return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(d.p / d.t))
    .attr("width", function() {
        return xScale(d.t)
    })
    .attr("height", function() {
        return yScale(d.h / d.t)
    })
    .style("fill", function() {
        return colorScale(i)
    })
    .style("opacity", .6);

And here is the demo with those modifications:

var body = d3.select('body');
var svg = body.append('svg').attr('height', 200).attr('width', 500);
var maing = svg.append('g');

var inputData = JSON.parse('{"a":[20,10],"b":[50,0],"c":[45,60],"d":[10,40]}')

// generate class
var colorScale = d3.scaleOrdinal(d3.schemeCategory10);

// convert to flattened array
var vals = Array("p", "h");
var cumT = +0
var transformedData = Object.keys(inputData).map(function(d, i) {
  let o = {};
  o.mp = d;
  inputData[d].forEach(function(d, i) {
    o[vals[i]] = d
  })
  o.t = o.p + o.h;
  return o;
}).sort(function(a, b) {
  return b.t - a.t
}).map(function(d, i) {
  let o = d;
  o.cumT = cumT += d.t
  return o;
});

var g = maing.selectAll('g')
  .data(transformedData)
  .enter()
  .append('g')

var xScale = d3.scaleLinear()
  .domain([0, d3.max(transformedData, function(d) {
    return d.cumT
  })])
  .range([0, 100]);
// TODO: use d3.max here
var yScale = d3.scaleLinear()
  .range([0, 140]) // some predefined height

g.each(function(d, i) {
  var upperRect = d3.select(this).append("rect")
    .attr("x", function() {
      return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(0))
    .attr("width", function() {
      return xScale(d.t)
    })
    .attr("height", function() {
      return yScale(d.p / d.t)
    })
    .style("fill", function() {
      return colorScale(i)
    })
    .style("opacity", .8);

  var lowerRect = d3.select(this).append("rect")
    .attr("x", function() {
      return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(d.p / d.t))
    .attr("width", function() {
      return xScale(d.t)
    })
    .attr("height", function() {
      return yScale(d.h / d.t)
    })
    .style("fill", function() {
      return colorScale(i)
    })
    .style("opacity", .6);
})
<script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>

The colors are different from your snippet because, in your snippet, you're creating the array first and sorting later. But this is easy to change, if you want:

var body = d3.select('body');
var svg = body.append('svg').attr('height', 200).attr('width', 500);
var maing = svg.append('g');

var inputData = JSON.parse('{"a":[20,10],"b":[50,0],"c":[45,60],"d":[10,40]}');

// generate class
var colorScale = d3.scaleOrdinal(d3.schemeCategory10);

// convert to flattened array
var vals = Array("p", "h");
var cumT = +0
var transformedData = Object.keys(inputData).map(function(d, i) {
  let o = {};
  o.mp = d;
  inputData[d].forEach(function(d, i) {
    o[vals[i]] = d
  })
  o.t = o.p + o.h;
  return o;
}).sort(function(a, b) {
  return b.t - a.t
}).map(function(d, i) {
  let o = d;
  o.cumT = cumT += d.t
  return o;
});

colorScale.domain(Object.keys(inputData));

var g = maing.selectAll('g')
  .data(transformedData)
  .enter()
  .append('g')

var xScale = d3.scaleLinear()
  .domain([0, d3.max(transformedData, function(d) {
    return d.cumT
  })])
  .range([0, 100]);
// TODO: use d3.max here
var yScale = d3.scaleLinear()
  .range([0, 140]) // some predefined height

g.each(function(d, i) {
  var upperRect = d3.select(this).append("rect")
    .attr("x", function() {
      return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(0))
    .attr("width", function() {
      return xScale(d.t)
    })
    .attr("height", function() {
      return yScale(d.p / d.t)
    })
    .style("fill", function(d) {
      return colorScale(d.mp)
    })
    .style("opacity", .8);

  var lowerRect = d3.select(this).append("rect")
    .attr("x", function() {
      return xScale(d.cumT - d.t)
    })
    .attr("y", yScale(d.p / d.t))
    .attr("width", function() {
      return xScale(d.t)
    })
    .attr("height", function() {
      return yScale(d.h / d.t)
    })
    .style("fill", function(d) {
      return colorScale(d.mp)
    })
    .style("opacity", .6);
})
<script src="https://d3js.org/d3.v4.min.js"></script>

Finally, have in mind that the stack generator, despite being complicated, is the best approach if you have several rectangles per column. In my solution, I have two selections inside the each... however, if you had 5 rectangles per column, we would have 5 selections inside the each, and so on, which is a lot of duplicated code.


Python3 - Determing if a PDF is scanned or "searchable" I am in a situation where I need to determine if a PDF file is either:

Scanned
Searchable (contain text)

To do this, I am simply running the command pdffonts on the PDF file:

# Check if the resource definition indicates this is a scanned PDF
cmd = ['pdffonts', pdf_file]
proc = subprocess.Popen(
    cmd, stdout=subprocess.PIPE, bufsize=0, text=True, shell=False)
out, err = proc.communicate()

scanned = True

for idx, line in enumerate(out.splitlines()):
    if idx == 2:
        scanned = False

Imagine I have two PDF files:

scanned.pdf
notscanned.pdf

The results of above:

scanned.pdf:

name                                 type              encoding         emb sub uni object ID
------------------------------------ ----------------- ---------------- --- --- --- ---------

notscanned.pdf

name                                 type              encoding         emb sub uni object ID
------------------------------------ ----------------- ---------------- --- --- --- ---------
TNNLVN+Calibri                       TrueType          WinAnsi          yes yes yes      9  0

As you can see, the notscanned.pdf file contains font information.

In my Python script, I iterate over each line in the command line output:

for idx, line in enumerate(out.splitlines()):
    if idx == 2:
        scanned = False

And if there is a line 2, then it contains font information.

I am wondering if this approach is viable? I've been searching for a solution for quite a bit, and it seems there is no way to know 100%.

How about the PDF metadata check on '/Resources' ?!

I believe for any text in a PDF (electronic document) there are more chances of having a font, especially the PDF, whose objective is to make a portable file, so, it maintains the font definition.

If you are a PyPDF2 user, try

pdf_reader = PyPDF2.PdfFileReader(input_file_location)
page_data = pdf_reader.getPage(page_num)

if '/Font' in page_data['/Resources']:
    print("[Info]: Looks like there is text in the PDF, contains:", page_data['/Resources'].keys())
elif len(page_data1['/Resources'].get('/XObject', {})) != 1:
    print("[Info]: PDF Contains:", page_data['/Resources'].keys())

for obj in x_object:
    obj_ = x_object[obj]
    if obj_['/Subtype'] == '/Image':
        print("[Info]: PDF is image only")


extract string from body of text Trying to return the below values from an RSS feed. I have sorted out the RSS feed side of things but I am not sure if what I am doing is the best way to extract the data that I need.  I have looked at beautifulsoup and regex's, re.search but not sure what is the best way to do this.

Values that I need; (both of these values change daily obviously)

4 Nov 2013

LOW-MODERATE

This is the cut down version of the full body of text that has the data i need to get from rss feed;

Fire Danger Ratings
Bureau of Meteorology forecast issued at: Mon, 4 Nov 2013 05:30 AM

Central: LOW-MODERATE

My code to extract the rss feed and data at the moment;

import feedparser #https://wiki.python.org/moin/RssLibraries

cfa_rss_url = "http://www.cfa.vic.gov.au/restrictions/central-firedistrict_rss.xml"

d = feedparser.parse( cfa_rss_url )

#get the data from the first item only, as it is only updated daily.
data = d.entries[0].description
print (data)
print('---------')

getdate = re.compile('forecast issued at: (.*?)
')
getrating = re.compile('
Central: (.*?)
')

m = getdate.search(data)
n = getrating.search(data)

print(m.group(1))
print(n.group(1))

This is the FULL data that is returned;

Total Fire Ban Status
Today, Mon, 4 Nov 2013 is not currently a day of Total Fire Ban in the Central (includes Melbourne and Geelong) fire district.

Fire Danger Ratings
Bureau of Meteorology forecast issued at: Mon, 4 Nov 2013 05:30 AM

Central: LOW-MODERATE

 Displays when Total Fire Ban in force
Restrictions may apply

---------
Mon, 4 Nov 2013 05:30 AM
LOW-MODERATE

As you can see my code returns the correct values atm but is this the most efficient way of doing this or should I be using another command?

You can do the whole thing with a single regexp:

import re

data = """

Fire Danger Ratings

Bureau of Meteorology
forecast issued at: Mon, 4 Nov 2013 05:30 AM

Central: LOW-MODERATE

"""

rgx = re.compile("(forecast issued at: |
Central: )(.*?)
")
results = rgx.findall(data)
print results[0][1]
print results[1][1]

Output:

$ python rss_parse.py
Mon, 4 Nov 2013 05:30 AM
LOW-MODERATE

If this only runs a time or two a day, pre-compiling the regex is not important.

...
results = re.findall("(forecast issued at: |
Central: )(.*?)
", data)
print results[0][1]
print results[1][1]

We can simplify how the result is handled:

...
[when, rating] = [x[1] for x in
                  re.findall("(forecast issued at: |
Central: )(.*?)
",
                             data)]
print("%s\n%s" % (when, rating))


Generic coverter for fields in class Here is a simple implementation of generic method that get value from array in class and cast it to a type.

    private T GetReferenceFieldValue<T>(ReferenceRow referenceRow, string fieldName)
    {
        var referenceField = referenceRow.field.FirstOrDefault(x => x.name == fieldName);

        if (referenceField != null)
        {
            //Dictionary for actions with types
            var typeActions = new Dictionary<Type, Func<object>>
                {
                    { typeof(DateTime), () => { return DateTime.Parse(referenceField.Item.ToString()); } },
                    { typeof(int), () => { return int.Parse(referenceField.Item.ToString()); } },
                    { typeof(string), () => { return referenceField.Item.ToString(); } },
                    { typeof(Guid), () => { return new Guid(referenceField.Item.ToString()); } },
                };

            var fieldValue = typeActions[typeof(T)]();

            return (T)Convert.ChangeType(fieldValue, typeof(T));
        }

        return default(T);
    }

referenceRow.field

The field name does not comply with the C# naming convention for public members that should be PascalCase. It should also probably be Fields since it's apparently a collection.

typeActions

Consider changing its name to convertTo which in this context makes the usage more natural:

var fieldValue = convertTo[typeof(T)]();

Func<object>

Consider using a parameter rahter then using closures. That makes the usage even clearer.

If you define it as

Func<object, object>

and the lambdas as

{ typeof(DateTime), x => { return DateTime.Parse(x.ToString()); } },

you can call it with

var fieldValue = convertTo[typeof(T)](referenceField.Item);

if (referenceField != null)

Avoid unnecessary nesting. You can use a postive condition == null and return right away if it's nulll.

return (T)Convert.ChangeType(fieldValue, typeof(T));

This is redundant. The converted value has already the target type. It just needs to be casted and because the ChangeType boxes the value anyway, you might as well do it yourself like this:

return (T)(object)typeActions[typeof(T)]();


Tax Calculator using Java 8 and BigDecimal I am learning Java8 and BigDecimal. The following exercise involved
writing a Tax Calculator that took a salary and calculated the tax
payable based on the tax band into which the salary falls. The test
passes as the code stands but if I remove the call to

setScale(0, BigDecimal.ROUND_UP)

then the rounding does not occur and the tests fail like this >

TaxCalculator.calculateTax > 712.50

java.lang.AssertionError:  Expected: is <713>
      but: was <712.50>

I don't understand that because the 2nd parameter to the divide call
specifies that rounding should be performed.

Also, Can anyone suggest
improvements to the way this class is written please? I'm just trying
to nail down best practices with respect to the Streams API. Am I using
an appropriate way to calculate a percentage in Java?

import org.junit.Before;
import org.junit.Test;

import java.math.BigDecimal;
import java.util.HashMap;
import java.util.TreeMap;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class TaxCalculatorTest {

    private TaxCalculator taxCalculator;

    private HashMap<BigDecimal, BigDecimal> testData = new HashMap<>(); // <salary, taxPayable>
    private TreeMap<BigDecimal, BigDecimal> taxBands = new TreeMap<>(); // uses natural ordering of keys
    // Could have used LinkedHashMap to maintain order but that relies on entries being inserted in the correct order

    @Before
    public void setup() {

        testData.put(new BigDecimal("5000"), new BigDecimal("225"));
        testData.put(new BigDecimal("11000"), new BigDecimal("413"));
        testData.put(new BigDecimal("19000"), new BigDecimal("713"));
        testData.put(new BigDecimal("27000"), new BigDecimal("905"));

        taxBands.put(new BigDecimal("10000"), new BigDecimal("4.5"));
        taxBands.put(new BigDecimal("35000"), new BigDecimal("3.35"));         // TreeMap fixes the ordering
        taxBands.put(new BigDecimal("20000"), new BigDecimal("3.75")); // This entry will be inserted before the previous one

        taxCalculator = new TaxCalculator(taxBands);
    }

    @Test
    public void calculateTax(){

        testData.forEach((salary, taxPayable) -> {

            assertThat(taxCalculator.calculateTax(salary), is(taxPayable));
        }) ;
    }
}

import java.math.BigDecimal;
import java.util.HashMap;
import java.util.TreeMap;

class TaxCalculator {

    private static final BigDecimal NO_TAX = new BigDecimal("0");

    /*
     * scale > the number of digits to the right of the decimal point
     *
     * precision > the number of significant digits
     *
     * BigDecimal instances are immutable
     *
     */

    private BigDecimal ONE_HUNDRED = new BigDecimal("100");

    private final TreeMap<BigDecimal, BigDecimal> taxBands;

    TaxCalculator(TreeMap<BigDecimal, BigDecimal> taxBands) {
        this.taxBands = taxBands;
    }

    BigDecimal calculateTax(BigDecimal salary) {

        BigDecimal taxPayable = salary.multiply(getTaxRate(salary)).divide(ONE_HUNDRED, BigDecimal.ROUND_UP).setScale(0, BigDecimal.ROUND_UP);

        System.out.println("TaxCalculator.calculateTax > " + taxPayable);
        return taxPayable;
    }

    private BigDecimal getTaxRate(BigDecimal salary) {

        return taxBands.entrySet().stream()
                .filter((entry) -> salary.compareTo(entry.getKey()) < 0)
                .map(HashMap.Entry::getValue)
                .findFirst().orElse(NO_TAX);
    }
}

The rounding doesn't work the way you expect it to work for division. From documentation:

  Returns a BigDecimal whose value is (this / divisor), and whose scale is this.scale().

The product of the salary and the tax rate has two digits after the decimal point. So does the quotient.
The getTaxRate method is unnecessarily long and complicated. You're trying to find the largest entry in a TreeMap such that is less than the given value. That's exactly what the lower method does.
Printing something inside the calculateTax method is a bad idea. It makes the code less reusable (what if I want to just calculate the tax without any logging?). And violates the single responsibility principle (it calculates the tax and prints something to standard output).
This kind of comments:

/*
 * scale > the number of digits to the right of the decimal point
 *
 * precision > the number of significant digits
 *
 * BigDecimal instances are immutable
 *
 */

is even worse than useless. It clutters the code with irrelevant information. The documentation for the BigDecimal class belongs to the BigDecimal class, not to a TaxCalculator.

There several other comments in your code that repeat parts of the TreeMap class documentation. They're also gibberish. Removing all these comments will make the code cleaner.
Adding doc comments for your TaxCalculator class and its public is a good idea. They should describe what it represents, what are the pre- and post-conditions of each method (for instance, what happens if I pass a negative salary? In your case, it's garbage in- garbage out. Document that. It's obvious from the method signature itself).
You might want to add proper input validation (for instance, you can throw the exception if the salary is negative).
You can also use the valueOf static factory method to convert integers to BigDecimal's: to me, BigDecimal.valueOf(100) looks better than new BigDecimal("100"). It can also reuse frequent values.


Check which state is activated and render the JSX accordingly Just wondering how I can go about doing this more efficiently/make it more visually appealing to the user?

     switch (this.state.selected) {
  case "all":
    styled = this.state.allKeywords.map(keyword =>

           <Input key={Math.random} style={{height: "45px", marginBottom: "20px"}} onClick={this.onKeywordClick} value={keyword} onChange={this.onKeywordChange}></Input>
           <Button key={Math.random} onClick={() => this.deleteKeyword(keyword)} style={{height: "45px", marginLeft: "30px"}}>Delete</Button>

     );
    break;
  case "positive":
      styled = this.state.positive.map(keyword =>

             <Input key={Math.random} style={{height: "45px", marginBottom: "20px"}} onClick={this.onKeywordClick} value={keyword} onChange={this.onKeywordChange}></Input>
             <Button key={Math.random} onClick={() => this.deleteKeyword(keyword)} style={{height: "45px", marginLeft: "30px"}}>Delete</Button>

       );
     break;
  case "negative":
      styled = this.state.negative.map(keyword =>

             <Input key={Math.random} style={{height: "45px", marginBottom: "20px"}} onClick={this.onKeywordClick} value={keyword} onChange={this.onKeywordChange}></Input>
             <Button key={Math.random} onClick={() => this.deleteKeyword(keyword)} style={{height: "45px", marginLeft: "30px"}}>Delete</Button>

       );
     break;
  default:
    console.log("No keyword list mapped");
}

If by this question you mean you want to prettify your code then Google "javascript prettify" and you will get numerous hits. For example, I picked the first one, Online JavaScript Beautifier and it did the following to your example with a few clicks. You can adjust the parameters of the prettifier to suit your needs. BTW this web site also mentions a Chrome plugin specifically aimed at prettifying code in Stack Overflow posts.

switch (this.state.selected) {
    case "all":
        styled = this.state.allKeywords.map(keyword =>
            <
            div style = {
                {
                    display: "flex",
                    flexDirection: "row"
                }
            } >
            <
            Input key = {
                Math.random
            }
            style = {
                {
                    height: "45px",
                    marginBottom: "20px"
                }
            }
            onClick = {
                this.onKeywordClick
            }
            value = {
                keyword
            }
            onChange = {
                this.onKeywordChange
            } > < /Input> <
            Button key = {
                Math.random
            }
            onClick = {
                () => this.deleteKeyword(keyword)
            }
            style = {
                {
                    height: "45px",
                    marginLeft: "30px"
                }
            } > Delete < /Button> <
            /div>
        );
        break;
    case "positive":
        styled = this.state.positive.map(keyword =>
            <
            div style = {
                {
                    display: "flex",
                    flexDirection: "row"
                }
            } >
            <
            Input key = {
                Math.random
            }
            style = {
                {
                    height: "45px",
                    marginBottom: "20px"
                }
            }
            onClick = {
                this.onKeywordClick
            }
            value = {
                keyword
            }
            onChange = {
                this.onKeywordChange
            } > < /Input> <
            Button key = {
                Math.random
            }
            onClick = {
                () => this.deleteKeyword(keyword)
            }
            style = {
                {
                    height: "45px",
                    marginLeft: "30px"
                }
            } > Delete < /Button> <
            /div>
        );
        break;
    case "negative":
        styled = this.state.negative.map(keyword =>
            <
            div style = {
                {
                    display: "flex",
                    flexDirection: "row"
                }
            } >
            <
            Input key = {
                Math.random
            }
            style = {
                {
                    height: "45px",
                    marginBottom: "20px"
                }
            }
            onClick = {
                this.onKeywordClick
            }
            value = {
                keyword
            }
            onChange = {
                this.onKeywordChange
            } > < /Input> <
            Button key = {
                Math.random
            }
            onClick = {
                () => this.deleteKeyword(keyword)
            }
            style = {
                {
                    height: "45px",
                    marginLeft: "30px"
                }
            } > Delete < /Button> <
            /div>
        );
        break;
    default:
        console.log("No keyword list mapped");
}