Pandoc builder system I have created a GNUMake building system for pandoc. It has grown quite a bit, I wonder if I can optimize it further. Would it be possible, for instance, that it only runs a target if the output hasn't changed since last run?

.DEFAULT_GOAL := pdf

INPUTDIR=$(CURDIR)/source
OUTPUTDIR=$(CURDIR)/output
STYLEDIR=$(CURDIR)/style
NAME = $(notdir $(shell basename "$(CURDIR)"))

FILFILES = $(wildcard style/*.py)

FILTER := $(foreach FILFILES, $(FILFILES), --filter $(FILFILES))
TEXFLAGS = --filter pandoc-crossref --filter pandoc-citeproc $(FILTER) --latex-engine=xelatex

ifeq ($(shell test -e "$(STYLEDIR)/template.tex" && echo -n yes),yes)
    TEXTEMPLATE = "--template=$(STYLEDIR)/template.tex"
endif

ifeq ($(shell test -e "$(STYLEDIR)/reference.docx" && echo -n yes),yes)
    DOCXTEMPLATE = "--reference-docx=$(STYLEDIR)/reference.docx"
endif

help:

    @echo '                                                                       '
    @echo 'Makefile for automated typography using pandoc.                         '
    @echo 'Version 1.0                        '
    @echo '                                                                       '
    @echo 'Usage:                                                                 '
    @echo '   make prepare    first time use, setting the directories     '
    @echo '   make html       generate a web version             '
    @echo '   make pdf        generate a PDF file             '
    @echo '   make docx       generate a Docx file            '
    @echo '   make tex        generate a Latex file               '
    @echo '   make beamer     generate a beamer presentation              '
    @echo '   make all        generate all files                 '
    @echo '   make update     update the makefile to last version       '
    @echo '   make            will fallback to PDF               '
    @echo '                                                                       '
    @echo 'It implies some directories in the filesystem: source, output and style'
    @echo 'It also implies that the bibliography will be defined via the yaml     '
    @echo '                                                                       '
    @echo 'Depends on pandoc-citeproc and pandoc-crossref                         '
    @echo 'Get local templates with: pandoc -D latex/html/etc                     '
    @echo '                                                                       '

all : tex docx html epub pdf

pdf:
    pandoc "$(INPUTDIR)/"*.md \
    -o "$(OUTPUTDIR)/$(NAME).pdf" \
    $(TEXTEMPLATE) \
    $(TEXFLAGS) 2>pandoc.log
    xdg-open "$(OUTPUTDIR)/$(NAME).pdf"

tex:
    pandoc "$(INPUTDIR)"/*.md \
    --filter pandoc-crossref \
    --filter pandoc-citeproc \
    -o "$(OUTPUTDIR)/$(NAME).tex" \
    --latex-engine=xelatex

docx:
    pandoc "$(INPUTDIR)"/*.md \
    --filter pandoc-crossref \
    --filter pandoc-citeproc \
    $(DOCXTEMPLATE) \
    --toc \
    -o "$(OUTPUTDIR)/$(NAME).docx"

html:
    pandoc "$(INPUTDIR)"/*.md \
    -o "$(OUTPUTDIR)/$(NAME).html" \
    --include-in-header="$(STYLEDIR)/style.css" \
    -t html5 \
    --toc \
    --standalone \
    --filter pandoc-crossref \
    --filter pandoc-citeproc \
    --number-sections
    rm -rf "$(OUTPUTDIR)/source"
    mkdir "$(OUTPUTDIR)/source"
    cp -r "$(INPUTDIR)/figures" "$(OUTPUTDIR)/source/figures"

epub:
    pandoc "$(INPUTDIR)"/*.md \
    -o "$(OUTPUTDIR)/$(NAME).epub" \
    --toc \
    --standalone \
    --filter pandoc-crossref \
    --filter pandoc-citeproc
    rm -rf "$(OUTPUTDIR)/source"
    mkdir "$(OUTPUTDIR)/source"
    cp -r "$(INPUTDIR)/figures" "$(OUTPUTDIR)/source/figures"

beamer:
    pandoc "$(INPUTDIR)/"*.md \
    -t beamer \
    -o "$(OUTPUTDIR)/$(NAME).pdf" \
    $(TEXTEMPLATE) \
    $(TEXFLAGS) 2>pandoc.log
    xdg-open "$(OUTPUTDIR)/$(NAME).pdf"

prepare:
    mkdir "output"
    mkdir "source"
    mkdir "style"

update:
    wget http://tiny.cc/mighty_make -O Makefile

clean:
    rm -f "$(OUTPUTDIR)/" *.md *.html *.pdf *.tex *.docx

.PHONY: help pdf docx html tex clean

only runs a target if the output hasn't changed since last run

Consider writing rules like this:

%.pdf: %.md
        pandoc -o $@ $<

For that to work, the current all: ... pdf would need to mention particular *.pdf files, perhaps by globbing: $(patsubst %.md,%.pdf,*.md)


Custom compression tool I have made my own compression tool for a stack-based language that uses a dictionary compression method. The code for the decompression is the following:

elif current_command == "\u201d":
    temp_string = ""
    temp_string_2 = ""
    temp_index = ""
    temp_position = pointer_position
    while temp_position < len(commands) - 1:
        temp_position += 1
        try:
            current_command = commands[temp_position]
            if dictionary.unicode_index.__contains__(current_command):
                temp_index += str(dictionary.unicode_index.index(current_command))
                temp_position += 1
                pointer_position += 2
                current_command = commands[temp_position]
                temp_index += str(dictionary.unicode_index.index(current_command))
                if temp_string == "":
                    temp_string += dictionary.dictionary[int(temp_index)].title()
                else:
                    temp_string += " " + dictionary.dictionary[int(temp_index)].title()
                temp_index = ""
            elif current_command == "\u201d":
                pointer_position += 1
                break
            elif current_command == "\u00ff":
                temp_string += str(pop_stack(1))
                pointer_position += 1
            else:
                temp_string += current_command
                pointer_position += 1
        except:
            pointer_position += 1
            break
        if debug:print(str(pointer_position) + " with " + str(hex(ord(current_command))))

    stack.append(temp_string)

The temporary variables are temp_string, temp_string_2, temp_index and temp_position. I know I should not be using names like these, but I didn't know what else to name it. This code just doesn't feel clean, and I don't know if it's just me, but it's not pleasant to look at. The code above can be found here. The dictionary.unicode_index is found here.

The best way to explain this is with an example:

For example, we want to compress the sentence Hello, World!. We first look at the index of the word Hello, which has index 2420. Since the language is 0-indexed, we need to substract 1 from this, leaving 2419. We now slice this into two pieces, 24 and 19. Then we find the corresponding indices, found here.

24 gives Ÿ
19 gives ™

The concatenation of the indices is done at this part:

temp_index += str(dictionary.unicode_index.index(current_command))

After the concatenation, we search up the index in the dictionary, which is done here:

if temp_string == "":
    temp_string += dictionary.dictionary[int(temp_index)].title()
else:
    temp_string += " " + dictionary.dictionary[int(temp_index)].title()

We append a comma, and we repeat the process for the next word, which is World. This has the index 119. Again, substract 1, which gives us the following compressed word: Œ‰. This gives us the following code for my language:

”Ÿ™,Œ‰!

And decompresses to Hello, World!, which can be verified here.

I was wondering how I can make the code look more clean, because right now, it looks like a complete mess.

You need better constants - "\u201d" is too magic - I would have no idea that it is a right double quotation mark just looking at that.

Don't use a bare except - you'll catch things you don't want to (for example, Ctrl+C).  Also, narrow the try as much as you can - if it is this big, it will be very hard to tell what caused the error. You should strongly prefer catching specific errors over all errors - errors you aren't expecting are probably bugs, and you'll want to learn about them.

Instead of calling __contains__ use in.

Don't use string concatenation the way you are - that's gonna be wasteful. Instead, use string.join.

You also don't need to forward declare all of these variables.

Using a format string will help the debug section be clearer.

You probably also want to factor out the first if branch into its own function, but given that it seems a little similar to the outer branch and the loop.  My guess is that the entire function this is in could be redesigned to be simpler and more modular, however without seeing that I can't speak exactly to it.

If you always increment pointer_position, put it in a finally block.

Overall, I'd recommend something more like this

elif current_command == "\u201d":
    compressed_strings = []
    position = pointer_position
    while position < len(commands) - 1:
        position += 1

        try:
            current_command = commands[position]
            if current_command in dictionary.unicode_index:
                position += 1
                pointer_position += 1
                next_command = commands[position]

                f = lambda x: str(dictionary.unicode_index.index(x))
                index = f(current_command) + f(next_command)

                next_string = dictionary.dictionary[int(temp_index)].title()

                compressed_strings.append(("" if not compressed_strings else " ") + next_string)
            elif current_command == "\u201d":
                break
            elif current_command == "\u00ff":
                compressed_strings.append(str(pop_stack(1)))
            else:
                compressed_strings.append(current_command)
        except Exception:
            break
        finally:
            pointer_position += 1
        if debug:
            print("{} with {}".format(pointer_position, hex(ord(current_command))))

    stack.append(''.join(compressed_strings))


Multithreading correctly done? I rarely write multithreaded code, and am on shaky ground when doing so.  I make mistakes.  I would like a sanity check of something I am going to introduce in one of my apps.

There will be exactly one running instance of the Thread class below in my application.  (It will be stored in a servlet context attribute.)  "Clients" will call one of three methods on the instance, getRunList() to get data from it, signalFreshRunListCreation() to tell the thread to generate new data, and stopThread() to signal the thread to exit.  On its own, the thread creates new data every 30 seconds.

Have I made any errors?

public class ThreadRunListDefault extends Thread {

    // This set to true signals that the thread should exit.
    private boolean _boStop = false;
    // The thread sets this to true just before it sleeps.
    private boolean _boIsSleeping = false;
    // An external client sets this to true to signal that a new run list should  be created.
    private boolean _boFreshRunListRequested = false;
    // This is a mutex to lock the run list while a fresh one is being created.
    private Object _lockRunList = new Object();
    // This is the actual data that will be returned.
    private List<BeanRunOutput> _runList;
    // This is the time the thread will sleep between refreshing the data on its own
    private long _iSleepMilliseconds = 30000;

    @Override
    public void run() {

        // Loop as long as no client has indicated the thread should stop.
        while (!_boStop) {
            // Create the data.
            this.createFreshRunList();

            // Only sleep if a refresh of the data wasn't requested while we were
            // creating a fresh run list.
            if (!_boFreshRunListRequested) {
                try {
                    // We set the sleeping flag to true so that signalFreshRunListCreation() will
                    // know whether or not to call interrupt() on the thread and wake it up.
                    _boIsSleeping = true;
                    Thread.sleep(_iSleepMilliseconds);
                } catch (InterruptedException e) { }
                _boIsSleeping = false;
            }
        }
    }

    /*
     * This is the method that will be called by run() to create new data in the _runList member variable.
     */
    private void createFreshRunList() {
        synchronized(this._lockRunList) {
            // Here we put the code that creates the run list.
            // Typically it will take 5 to 10 seconds.
            _runList = new ArrayList<BeanRunOutput>();
        }
    }

    /*
     * This is the method a client will call to get the data in _runList.
     */
    public List<BeanRunOutput> getRunList() {
        synchronized(this._lockRunList) {
            return _runList;
        }
    }

    /*
     * This is the method a client will call to signal the thread that a new run list should be created.
     * If run() is currently gathering data (_boIsSleeping is false), a flag will be set to tell run()
     * to run again immediately after it is finished, without sleeping first.  If the thread is currently
     * sleeping, it will be interrupted.
     */
    public void signalFreshRunListCreation() {
        if (_boIsSleeping) {
            // Thread is sleeping so interrupt it.
            this.interrupt();
        } else {
            // The thread is running so signal it should just run again when
            // complete (in other words not sleep).
            _boFreshRunListRequested = true;
        }
    }

    /*
     * This method allows a client to signal the thread to exit.
    */
    public void stopThread() {
        _boStop = true;
    }
}

The  _boStop and the _boIsSleeping fields are accessed by multiple threads, so you should synchronize them. You could use volatile fields or AtomicBooleans too.

Make sure that you do read operations in synchronized blocks too, not just writes:

  [...] synchronization has no effect unless both read and write operations are synchronized.

From Effective Java, 2nd Edition, Item 66: Synchronize access to shared mutable data.
A possible bug: _boFreshRunListRequested is never set to false.
Using _ prefixes (and sometimes this.) to access fields it's not really necessary and it's just noise. Modern IDEs use highlighting to separate local variables from instance variables.
You could eliminate some comments, for example:

// Loop as long as no client has indicated the thread should stop.
while (!boStop) {

This could be

while (!threadStop) {

Another example:

   // Create the data.
   this.createFreshRunList();

Here you could rename the method to createData or createFreshData.

A good reading in this topic is Clean Code by Robert C. Martin and Code Complete, 2nd Edition by Steve McConnell.
It mainly depends on your requirements, but I'd consider renaming the class to DataRefresherImpl and implementing two interfaces: DataRefresherService and  DataRefresher. The first would be used only in the servlet/container initializer. The second is for the clients to get their data and to request new data creation. It would prevent clients to call the stopThread method accidentally.
OldCurmudgeon has already mentioned the getRunList method is dangerous. You could use Collections.unmodifiableList here. Furthermore, make sure that the BeanRunOutput objects are also immutable or handle the modifications. See also: Effective Java, 2nd Edition, Item 39: Make defensive copies when needed

Finally, here is an refactored version with the queue which was suggested by OldCurmudgeon.

public interface DataRefresherService {
    void shutdown();
}

public interface DataRefresher {
    List<BeanRunOutput> getRunList();
    void signalFreshRunListCreation();
}

public class DataRefresherImpl implements Runnable,
        DataRefresherService, DataRefresher {

    private final AtomicBoolean threadStop = new AtomicBoolean(false);

    private final ReentrantReadWriteLock listLock = new ReentrantReadWriteLock();

    private static final long REFRESH_INTERVAL_IN_MILLIS = 3000;

    private final ArrayBlockingQueue<String> refreshQueue =
        new ArrayBlockingQueue<String>(1);

    private List<BeanRunOutput> runList;

    public DataRefresherImpl() {
    }

    @Override
    public void run() {
        while (!threadStop.get()) {
            createFreshRunList();
            sleepAndWakeOnRequest();
        }
    }

    private void createFreshRunList() {
        listLock.writeLock().lock();
        try {
            runList = new ArrayList<BeanRunOutput>();
        } finally {
            listLock.writeLock().unlock();
        }
    }

    private void sleepAndWakeOnRequest() {
        try {
            refreshQueue.poll(REFRESH_INTERVAL_IN_MILLIS, TimeUnit.MILLISECONDS);
        } catch (InterruptedException ignored) {
        }
    }

    @Override
    public List<BeanRunOutput> getRunList() {
        listLock.readLock().lock();
        try {
            return runList;
        } finally {
            listLock.readLock().unlock();
        }
    }

    @Override
    public void signalFreshRunListCreation() {
        refreshQueue.offer("refresh");
    }

    @Override
    public void shutdown() {
        threadStop.set(true);
        refreshQueue.offer("shutdown");
    }
}

(I've not tested this too much.)


Feedback Request on Title Capitalization Function Converted From JavaScript to PHP I have a function in JavaScript that converts a string value to title case using APA style:

function titleCase(str, options) {
  const stopwords = 'a an and at but by for in nor of on or so the to up yet'
  const defaults = stopwords.split(' ')

  const opts = options || {}

  if (!str) return ''

  const stop = opts.stopwords || defaults
  const keep = opts.keepSpaces
  const splitter = /(\s+|[-‑–—])/

  return str
    .split(splitter)
    .map((word, index, all) => {
      if (word.match(/\s+/)) return keep ? word : ' '
      if (word.match(splitter)) return word

      if (
        index !== 0 &&
        index !== all.length - 1 &&
        stop.includes(word.toLowerCase())
      ) {
        return word.toLowerCase()
      }

      return capitalize(word)
    })
    .join('')
}

function capitalize(str) {
  return str.charAt(0).toUpperCase() + str.slice(1)
}

Credits of above JS functions

I converted the above to PHP:

function APATitle($title, $keepSpaces = false, $stopWords = array())
{
    if (!is_string($title)) {
        return false;
    }

    if (!is_array($stopWords) || count($stopWords) < 1) {
        $stopWords = array('a', 'an', 'and', 'at', 'but', 'by', 'for', 'in', 'nor', 'of', 'on', 'or', 'so', 'the', 'to', 'up', 'yet'); //Must all be lowercase!
    }

    $regexWordSplit = '/(\s+|[-‑–—])/';
    $words = preg_split($regexWordSplit, $title, -1, PREG_SPLIT_DELIM_CAPTURE);

    foreach ($words as $i => $currWord) {
        if (preg_match('/\s+/', $currWord) === 1) {
            if (!$keepSpaces) {
                $words[$i] = ' ';
            }
            continue;
        }

        if (preg_match($regexWordSplit, $currWord) === 1) {
            continue;
        }

        $currWordLower = strtolower($currWord);
        if ($i != 0 && $i != count($words) - 1 && in_array($currWordLower, $stopWords)) {
            $words[$i] = $currWordLower;
            continue;
        }

        if (strlen($currWord) > 0) {
            $currWord[0] = strtoupper($currWord[0]);
            $words[$i] = $currWord;
        }
    }

    return implode('', $words);
}

Everything works well (as far as I can tell). I'm looking for feedback on the above conversion and also general feedback on the PHP code (which it's maybe too much of a JS translation).

Some el cheapo testing for the PHP code:

$tests = array(
    array('in' => '', 'out' => '', 'keepSpaces' => false),
    array('in' => 'this is a test', 'out' => 'This Is a Test', 'keepSpaces' => false),
    array('in' => 'why sunless tanning is A hot trend', 'out' => 'Why Sunless Tanning Is a Hot Trend', 'keepSpaces' => false),
    array('in' => 'Satin Sheets are a Luxury you Can Afford', 'out' => 'Satin Sheets Are a Luxury You Can Afford', 'keepSpaces' => false),
    array('in' => 'the Dangers Of Hiking Without Proper Shoes', 'out' => 'The Dangers of Hiking Without Proper Shoes', 'keepSpaces' => false),
    array('in' => 'an hour or so', 'out' => 'An Hour or So', 'keepSpaces' => false),
    array('in' => 'Of the meaning Of Of', 'out' => 'Of the Meaning of Of', 'keepSpaces' => false),
    array('in' => 'Thing With     Extra Spaces', 'out' => 'Thing With Extra Spaces', 'keepSpaces' => false),
    array('in' => 'Thing with     extra spaces', 'out' => 'Thing With     Extra Spaces', 'keepSpaces' => true),
    array('in' => 'Observations of isolated pulsars and disk-fed X-ray binaries.', 'out' => 'Observations of Isolated Pulsars and Disk-Fed X-Ray Binaries.', 'keepSpaces' => false)
);

$ok = 0;
foreach ($tests as $currTest) {
    $currRes = APATitle($currTest['in'], $currTest['keepSpaces']);
    if ($currRes === $currTest['out']) {
        ++$ok;
    }
}
echo $ok == count($tests) ? 'All tests OK' : 'Test bad';

First things first: You definitely don't need to be making multiple regex function calls while looping the elements generated by a splitting regex function.  Time for an almost complete rewrite.  preg_replace_callback() is the tool that I recommend to do all the heavy lifting.

Normally, I like to do everything in a single regex expression, but the retaining of the multiple spaces is a simple operation that is sensibly set apart.

There WILL be other fringe cases that other reviewers may shout out (e.g. handling multibyte characters or calling preg_quote() on the incoming blacklist words to avoid any regex pattern conflicts with special characters, and let's not forget about troublesome Mr McGee) but I am going to only focus on the quality of data that you have presented.

There will be other ways to write the pattern but I have a high appreciation for the clarity of (*SKIP)(*FAIL) it basically consumes substrings that should be disqualified and then discards them.  The pipe after the skip-fail non-capturing group will match qualifying consecutive letters. The fullstring matches are passed to the custom function where the first letter is converted to uppercase, then returned.  Finally the fully modified string is returned from the preg_replace_callback().

My regex pattern uses negative lookaheads with the start and end of string anchors (^ & $) to implement the rule regarding capitalizing the first and last word.  Word boundaries (\b) are a great way to isolate a whole word (or parts of a hyphenated word).

Code: (Demo)

$tests = [
    ['this is a test', 'This Is a Test', false],
    ['why sunless tanning is A hot trend', 'Why Sunless Tanning Is a Hot Trend', false],
    ['Satin Sheets are a Luxury you Can Afford', 'Satin Sheets Are a Luxury You Can Afford', false],
    ['the Dangers Of Hiking Without Proper Shoes', 'The Dangers of Hiking Without Proper Shoes', false],
    ['an hour or so', 'An Hour or So', false],
    ['Of the meaning Of Of', 'Of the Meaning of Of', false],
    ['Thing With     Extra Spaces', 'Thing With Extra Spaces', false],
    ['Thing with     extra spaces', 'Thing With     Extra Spaces', true],
    ['Observations of isolated pulsars and disk-fed X-ray binaries.', 'Observations of Isolated Pulsars and Disk-Fed X-Ray Binaries.', false]
];

function APATitle($title, $keepMultipleSpaces = false, $blackList = [])
{
    if (!is_string($title)) {
        return false;
    }

    $blackList = $blackList
        ? array_map('strtolower', (array)$blackList)
        : ['a', 'an', 'and', 'at', 'but', 'by', 'for', 'in', 'nor', 'of', 'on', 'or', 'so', 'the', 'to', 'up', 'yet'];

    if (!$keepMultipleSpaces) {
        $title = preg_replace('~\s+~', ' ', $title);
    }

    return preg_replace_callback(
        '~(?!^)\b(?:' . implode('|', $blackList) . ')\b(?!$)(*SKIP)(*FAIL)|\b[a-z]+\b~',
        function ($m) {
            return ucfirst($m[0]);
        },
        strtolower($title)
    );
}

foreach ($tests as [$input, $expectedOutput, $keepMultipleSpaces]) {
    $output = APATitle($input, $keepMultipleSpaces);
    echo ($output === $expectedOutput ? 'SUCCESS' : 'FAILURE') . ":\t\"{$input}\" became \"{$output}\"\n";
}

Output:

SUCCESS:    "this is a test" became "This Is a Test"
SUCCESS:    "why sunless tanning is A hot trend" became "Why Sunless Tanning Is a Hot Trend"
SUCCESS:    "Satin Sheets are a Luxury you Can Afford" became "Satin Sheets Are a Luxury You Can Afford"
SUCCESS:    "the Dangers Of Hiking Without Proper Shoes" became "The Dangers of Hiking Without Proper Shoes"
SUCCESS:    "an hour or so" became "An Hour or So"
SUCCESS:    "Of the meaning Of Of" became "Of the Meaning of Of"
SUCCESS:    "Thing With     Extra Spaces" became "Thing With Extra Spaces"
SUCCESS:    "Thing with     extra spaces" became "Thing With     Extra Spaces"
SUCCESS:    "Observations of isolated pulsars and disk-fed X-ray binaries." became "Observations of Isolated Pulsars and Disk-Fed X-Ray Binaries."


Google Kickstart Round A 2019 - Training Problem: Training

  As the football coach at your local school, you have been tasked with
  picking a team of exactly P students to represent your school. There
  are N students for you to pick from. The i-th student has a skill
  rating Si, which is a positive integer indicating how skilled they
  are.

  You have decided that a team is fair if it has exactly P students on
  it and they all have the same skill rating. That way, everyone plays
  as a team. Initially, it might not be possible to pick a fair team, so
  you will give some of the students one-on-one coaching. It takes one
  hour of coaching to increase the skill rating of any student by 1.

  The competition season is starting very soon (in fact, the first match
  has already started!), so you'd like to find the minimum number of
  hours of coaching you need to give before you are able to pick a fair
  team.

  Input

  The first line of the input gives the number of test cases, T. T test
  cases follow. Each test case starts with a line containing the two
  integers N and P, the number of students and the number of students
  you need to pick, respectively. Then, another line follows containing
  N integers Si; the i-th of these is the skill of the i-th student.

  Output

  For each test case, output one line containing Case #x: y, where x is
  the test case number (starting from 1) and y is the minimum number of
  hours of coaching needed, before you can pick a fair team of P
  students.

  Limits

  Time limit: 15 seconds per test set.
  Memory limit: 1 GB.
  1 ≤ T ≤ 100.
  1 ≤ Si ≤ 10000, for all i.
  2 ≤ P ≤ N.
  Test set 1 (Visible)
  2 ≤ N ≤ 1000.
  Test set 2 (Hidden)
  2 ≤ N ≤ 105.

  Sample

  Input

3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

  Output

Case #1: 14
Case #2: 0
Case #3: 6

  In Sample Case #1, you can spend a total of 6 hours training the first
  student and 8 hours training the second one. This gives the first,
  second and third students a skill level of 9. This is the minimum time
  you can spend, so the answer is 14.

  In Sample Case #2, you can already pick a fair team (the first and
  second student) without having to do any coaching, so the answer is 0.

  In Sample Case #3, P = N, so every student will be on your team. You
  have to spend 6 hours training the third student, so that they have a
  skill of 7, like everyone else. This is the minimum time you can
  spend, so the answer is 6.

My solution

#include <iostream>
#include <vector>
#include <algorithm>

void getData(int &p, std::vector<int> &skills) {
    int n;
    std::cin >> n >> p;
    skills.reserve(n);
    for (int i = 0; i < n; i++) {
        int skill = 0;
        std::cin >> skill;
        skills.emplace_back(skill);
    }
}

int minTrainingTime(std::vector<int> &skills, int p) {
    std::sort(skills.begin(), skills.end());
    int low = 0, high = p - 1;

    int currentResult = 0;
    for (int i = 0; i < high; i++) {
        currentResult += skills[high] - skills[i];
    }

    int minResult = currentResult;
    int remainingPossibilities = skills.size() - p;
    for (int i = 0; i < remainingPossibilities; i++) {
        currentResult -= skills[++high] - skills[low++];
        currentResult += p * (skills[high] - skills[high - 1]);
        minResult = std::min(minResult, currentResult);
    }

    return minResult;
}

int main() {
    int t = 0;
    std::cin >> t;
    for (int testCase = 0; testCase < t; testCase++) {
        int p;
        std::vector<int> skills;
        getData(p, skills);

        std::cout << "Case #" << testCase + 1 << ": " << minTrainingTime(skills, p) << std::endl;
    }
}

Analysis

Time complexity: \$O(n\log n)\$, dominated by sorting

Space complexity: \$O(1)\$, not counting the original data given by the problem

First of all, this looks good to me! I have some minor comments.

General comments

Consider compiling with -Wconversion. It will give you a couple of hints where you implicitly convert between std::vector::size_type (usually std::size_t) and int. Whether you work with unsigned data types for skills and quantities might be a matter of taste, but I think you should be aware of the conversion issue. Also, this compiler flags gives you (on my machine)

  implicit conversion loses integer precision: unsigned long to int [-Wshorten-64-to-32]

int remainingPossibilities = skills.size() - p;

which should definitely worth tackling even if the problem description specifies input characteristics that make a digit loss impossible.
Not that this will be an issue for this example, but when you want to be as fast as possible, don't use <iostream>, but <cstdio> instead.

Input handling/parameter types

When retrieving the input data, don't pass non-const references, but prefer returning by value instead. (N)RVO will make sure there is no overhead. As you have more than one value, define a small, custom type for this. So, I'd suggest going with

struct TestCaseInput {
   int nToChoose;
   std::vector<int> skills;
};

TestCaseInput getData();
int minTrainingTime(TestCaseInput& input);

cf. the Core Guidelines on this topic, F.20 and F.21
std::vector::emplace_back makes sense when you can in-place construct an object with given parameters, but when you pass the already existing object to this function, it's probably clearer to use push_back. In the case of an integral value, it doesn't matter anyhow whether you move-construct or copy it. As an alternative, you could also

std::vector<int> skills(n); // Allocates and set all values to zero

for (int i = 0; i < n; i++)
    std::cin >> skills[i]; // No temporary variable required

And also have a look at the combination of std::copy_n and std::istream_iterator that @papagaga suggests to eliminate the manual loop here.

Main function minTrainingTime

In the first loop, you read skills[high] in every iteration, even though this value doesn't change. Instead, just read it once and save it in a variable. Or, leave it as it is and verify that the compiler optimizes this away anyway.
You can also replace this whole first loop by including <numeric> and using std::accumulate with an initial value high*skills[high] and std::minus<>{} as the binary operation parameter.
If you can const-qualify a variable, do so:

const int remainingPossibilities = skills.size() - p;

But if can alternative reduce the scope of such a variable and by that even eliminate another one (the loop counter i), do so instead (as long as the negative influence on the readability is not too big, which I think is ok here):

// remainingPossibilities is now superfluous, just use the for loop for
// the initialization and count differently:
for (int n = skills.size() - p; n != 0; n--) { /* ... */ }

You might want to consider an additional level of indirection for the function minTrainingTime here, as it can equally well operate on random access iterators instead of indices. This way, you eliminate the dependency of this function on the actual value type that you are using (which also considerably reduces the number of -Wconversion warnings at one go), as well as the dependency on the container type. Using some of the above hints, the resulting function template looks e.g. like this:

template <class RandomAccesIt, class T>
auto minTrainingTime(RandomAccesIt first, RandomAccesIt last, T p)
{
    using value_type = typename RandomAccesIt::value_type;
    auto low = first, high = std::next(first, p - 1);
    const value_type init = std::distance(low, high)*(*high);

    value_type currentResult = std::accumulate(first, high, init, std::minus<>{});
    value_type minResult = currentResult;

    for (auto n = std::distance(first, std::prev(last, p)); n != 0; --n) {
        currentResult -= *++high - *low++;
        currentResult += p*(*high - *std::prev(high));
        minResult = std::min(minResult, currentResult);
    }

    return minResult;
}

and can be deduced and invoked by minTrainingTime(skills.begin(), skills.end(), p).


Java diamond with numbers I have an assignment to code a method that will print values in a diamond pattern. For example, if the method is called like printNumberDiamond(2), then the results should look like:

"  0  "
" 010 "
"01210"
" 010 "
"  0  "

I have spent a ton of time on writing the code that does this, but I am sure that it's not the most efficient/clean way. I am hoping to learn new strategies for accomplishing this, because this was very difficult for me to complete, and I almost just gave up, but I got it to work:

public static void printNumberDiamond(int diaCenter)
{
        printNumberDiamondTop(diaCenter);
        printNumberDiamondBottom(diaCenter);
}

public static void printNumberDiamondTop(int diaCenter)
{
    int maxAscendingRows = diaCenter + 1;
    int maxColumnLength = diaCenter * 2 + 1;
    int highestNbrForRow = 0;

    for(int row = 0, rowCtr=0;row<=diaCenter;row++)
    {
        int thisColumnLength = 0;
        int thisColumnMaxLeftSpaces = 0;

        if(row >= maxAscendingRows)
        {
            thisColumnMaxLeftSpaces = (maxColumnLength - rowCtr) / 2;
            rowCtr--;
        }
        else
        {
            thisColumnLength = maxColumnLength - row;
            thisColumnMaxLeftSpaces = (thisColumnLength - row) / 2;
            rowCtr++;
        }

        int nbrWritten = 0;
        int nbrDescendingWritten = 0;
        for(int col = 0;col < maxColumnLength;col++)
        {
            if(col < thisColumnMaxLeftSpaces)
            {
                System.out.print(" ");
            }
            else if(nbrDescendingWritten == 0 && nbrWritten > row)
            {
                System.out.print(" ");
            }
            else if(nbrWritten <= highestNbrForRow)
            {
                System.out.print(nbrWritten++);
                nbrDescendingWritten = nbrWritten - 1;
            }
            else if(nbrWritten > highestNbrForRow)
            {
                System.out.print(--nbrDescendingWritten);
            }
        }
        ++highestNbrForRow;
        System.out.print("\n");
    }
}

public static void printNumberDiamondBottom(int diaCenter)
{
    int maxColumnLength = diaCenter * 2 + 1;
    int highestNbrForRow = 0;
    for(int row = diaCenter;row>0;row--)
    {
        highestNbrForRow = row - 1;
        int thisColumnMaxLeftSpaces = (maxColumnLength - highestNbrForRow * 2) / 2;
        int nbrWritten = 0;
        int nbrDescendingWritten = 0;

        for(int col = 0;col < maxColumnLength;col++)
        {
            if(col < thisColumnMaxLeftSpaces)
            {
                System.out.print(" ");
            }
            else if(nbrDescendingWritten == 0 && nbrWritten > highestNbrForRow)
            {
                System.out.print(" ");
            }
            else if(nbrWritten <= highestNbrForRow && nbrWritten >= 0)
            {
                System.out.print(nbrWritten++);
                nbrDescendingWritten = nbrWritten - 1;
            }
            else if(nbrWritten > highestNbrForRow)
            {
                System.out.print(--nbrDescendingWritten);
            }
        }
        ++highestNbrForRow;
        System.out.print("\n");
    }

Before going into any coding I would give you a quick hack for the diamond problem . Instead of making so many for looping and columns and keeping track of variables the diamond problem is a variant of a maths problem.
HERE

1*1 = 1
11*11 = 121
111*111 = 12321
1111*1111 = 1234321

and so on. SO if you use this formula you just need one for loop for spaces and one for increasing your num*10 +1 where num is 1 and then squaring it and you will get the diamond pattern. If you want I can code it for you but since you asked for an easier method this is the best you can get.


Dice game login system The end result of this is to allow a user to log in and/or register themselves for a dice game. Please post some suggestions for improvement.

import pickle

logged_in = False

with open('users.pickle', 'rb') as a_file:
    users = pickle.load(a_file)

login_or_signup = input('do you want to login or signup? ')

# sign up (creating new account)
if login_or_signup.lower() == "signup":

    create_username = input("enter a new username: ")
    create_password = input("enter a new password (Your password cannot be the same as your username !!!!!!!): ")

    if create_password in users:
        create_password = input("password taken re-enter: ")

    users[create_username] = create_password

username = input('please enter username: ')

if username in users:
    password = input("enter password: ")
    if password == users[username]:
        print("access granted")
        logged_in = True

else:
    print("access denied")

with open("users.pickle", 'wb') as f:
    pickle.dump(users, f, pickle.HIGHEST_PROTOCOL)

You are introducing this requirement of not having a password being the same as a username, but the problem is the way you check for it:

create_password = input("enter a new password (Your password cannot be the same as your username !!!!!!!): ")

if create_password in users:

The problem arises when my password matches someone else's username.

I think you meant to just compare create_username with create_password values.

In general, there is rarely a case when you should try writing your own login system except that for learning purposes. You may though improve your current setup by introducing hashing of the passwords, to avoid storing them in plain text: Salt and hash a password in python; as well as more password strength requirements: Checking the strength of a password.


Combining None and lists in one line Suppose we have variables, num and let, that may be (possibly nested) list, tuple, or None. The combination is to be such that:

Neither == None -> num + let
num == None -> let
let == None -> num
Both == None -> None
Return type is list or None
1-5 should hold for any number of variables, including one, and >2
Be a one-liner (one statement)

My approach, with test:

def join(_vars):
    return [x for v in _vars if v for x in v] or None

num = ((1, 2), None, [1, (2, 3)], None)
let = (('a', 'b'), ['a', ('b', 'c')], None, None)
vars_all = (let, num)

for i, _vars in enumerate(zip(*vars_all)):
    print(f"Case {i + 1}:", join(_vars))

Case 1: ['a', 'b', 1, 2]
Case 2: ['a', ('b', 'c')]
Case 3: [1, (2, 3)]
Case 4: None

Any better way to accomplish this? E.g. shorter, or more readable, or more intuitive than nested comprehensions.

(For readability I'd opt for less abstract naming: [x for var in _vars if bool(var) for x in var]. Parentheses should also help, though unsure if can insert without changing results.)

As you mentioned, the nested comprehension is not very intuitive. I had to write it out for understanding.

I am also not sure I understood your requirements correctly. Please correct any wrong assumptions. These are the attempts:

from itertools import chain

def join(vars_):
    filtered = (element for element in vars_ if element)
    return chain.from_iterable(filtered)

num = ((1, 2), None, [1, (2, 3)], None)
let = (('a', 'b'), ['a', ('b', 'c')], None, None)
vars_all = (let, num)

for i, vars_ in enumerate(zip(*vars_all), start=1):
    print(f"Case {i}:", join(vars_))

It returns

Case 1: <itertools.chain object at 0x00000221C73F3940>
Case 2: <itertools.chain object at 0x00000221C73F3940>
Case 3: <itertools.chain object at 0x00000221C73F3940>
Case 4: <itertools.chain object at 0x00000221C73F3940>

So not what you really asked for. However, the chain object behaves like a normal list in most circumstances. It supports the Sequence interface (but not the MutableSequence interface):

from collections.abc import MutableSequence, Sequence
from itertools import chain

def join(vars_):
    filtered = (element for element in vars_ if element)
    return chain.from_iterable(filtered)

num = ((1, 2), None, [1, (2, 3)], None)
let = (("a", "b"), ["a", ("b", "c")], None, None)
vars_all = (let, num)

for i, vars_ in enumerate(zip(*vars_all), start=1):
    print(f"Case {i}:", list(join(vars_)))
    print("\tIs Sequence:", isinstance(vars_, Sequence))
    print("\tIs MutableSequence:", isinstance(vars_, MutableSequence))
    print(
        "\tIs MutableSequence (cast to list):", isinstance(list(vars_), MutableSequence)
    )

will print

Case 1: ['a', 'b', 1, 2]
        Is Sequence: True
        Is MutableSequence: False
        Is MutableSequence (cast to list): True
Case 2: ['a', ('b', 'c')]
        Is Sequence: True
        Is MutableSequence: False
        Is MutableSequence (cast to list): True
Case 3: [1, (2, 3)]
        Is Sequence: True
        Is MutableSequence: False
        Is MutableSequence (cast to list): True
Case 4: []
        Is Sequence: True
        Is MutableSequence: False
        Is MutableSequence (cast to list): True

So if a caller requires a list, they can cast to that type specifically. It is perhaps more pythonic to not do that in the function already (duck-typing).

Another point to note is that if both elements are None, an empty iterable is returned. This will still behave similar to None in boolean contexts. It allows for simpler code and maybe more predictable returns. See if that still fulfills your requirements. If not, this final suggestion will fulfill your tests as specified:

from itertools import chain

def join(vars_):
    if not any(vars_):
        return None
    filtered = (element for element in vars_ if element)
    return list(chain.from_iterable(filtered))

num = ((1, 2), None, [1, (2, 3)], None)
let = (("a", "b"), ["a", ("b", "c")], None, None)
vars_all = (let, num)

for i, vars_ in enumerate(zip(*vars_all), start=1):
    print(f"Case {i}:", join(vars_))

will return

Case 1: ['a', 'b', 1, 2]
Case 2: ['a', ('b', 'c')]
Case 3: [1, (2, 3)]
Case 4: None

for Python 3.8.1.
I hope you agree that this is more readable, intuitive and also debuggable.
The early return makes it easier to understand. The additional itertools import is very cheap.

Finally, a one-liner version of the above is

def join(vars_):
    return list(chain.from_iterable(elem for elem in vars_ if elem)) or None

Lastly, two notes:

notice the start keyword for enumerate
leading underscores denote (private) implementation details; use trailing underscores for variable names that otherwise shadow built-ins; better to avoid these all-together, though


Basic querying on Python 2D arrays Background

Today at work, I had to bring a component that used to load CSV data into MySQL, and perform calculations as result of SQL queries. I was tasked with replicating that in a programming language.

The general example is like:

There's a 2D array (a table) with columns "Name", "Age", "Grade" and "Total". Produce counts like "Unique Ages", "Unique Ages & Grade", "Unique Ages for which Grade = 3" etc.

My Work

So, I chose Python to do this job. There's a class that takes two parameters: 2D array and columns, and allows for performing some very basic querying capability.

Environment: Python 2.x

class From:
    def __init__(self, array, columns):
        self.columns = columns
        self.array = array

    def where(self, column, data):
        return From(filter(lambda x: x[self.columns.index(column)] == data, self.array), self.columns)

    def whereNot(self, column, data):
        return From(filter(lambda x: x[self.columns.index(column)] != data, self.array), self.columns)

    def select(self, *columns):
        return From([[arrayItem[self.columns.index(col)] for col in columns] for arrayItem in self.array], columns)

    def unique(self, *columns):
        # This function filters those rows which have a unique combination of the columns
        # specified as parameter. If there are 2+ rows with same combination of values
        # under the column, then the last one will be chose. Example use case: Extract a
        # subset of rows that have a unique combination of "first name" & "second name"
        # Invocation: From(<array>,<cols>).unique("first_name","second_name")
        return From({tuple(row[self.columns.index(col)] for col in columns): row for row in self.array}.values(), self.columns)

    def length(self):
        return len(self.array)

    def get(self):
        if len(self.columns) == 1:
            return [x[0] for x in self.array]
        return self.array

Example Usage:

>>> array = [
... ["ben", "son", 23, 10, 93],
... ["gun", "dad", 21, 9,  99],
... ["sam", "mom", 19, 11, 92]
... ]
>>> cols = ["name1","name2", "age", "grade", "marks"]
>>> From(array, cols).where("name1","sam").get()
[['sam', 'mom', 19, 11, 92]]

The querying that is being done in the real code is quite complex beyond the scope of this question. The From class works, for now.

Questions

Can this be improved, maybe made more pythonic from an overall perspective (Please excuse those ugly filter/lambda expressions. I know they are just not pythonic.)?
The From.unique(..) function looks like a dirty hack. Is there any cleaner way to do it? (Please check my comment under the unique function declaration.)
Is there any non-edge case when the above will not work? Anywhere it might just go wrong?
Am I reinventing the wheel?

I totally agree with liuyu that a proper in-memory database like sqlite3 will be much more efficient and useful than what you have here.

But just reviewing your code as it is:

There's no documentation. How are we supposed to use this class?
There are no test cases. You could use the doctest module to make your example code into a runnable test case.
You don't follow the Python style guide (PEP8). In particular, if you kept to the maximum line length of 79 columns, then we could read your code here without having to scroll the window.
From is a poor name: it doesn't clearly communicate the meaning of the class. An instance of the From class represents an table of records, so I would give the class a name like Table.
Unless you have a particular reason to make an old-style class, you should write:

class From(object):

so that you get a new-style class which is portable to Python 3. See "new-style and classic classes" in the docs.
Instead of providing methods length to get the length of the table, and get to get the table itself, why not make your class into a sequence? That is, instead of length you'd provide __len__ and instead of get you'd provide __iter__ and __getitem__. Then callers could just iterate over your From items in the usual way:

for record in From(...):

If you derived your class from the abstract base case collections.Sequence, you'd also get __contains__, __iter__, __reversed__, index, and count methods for free.
It would be most natural to return each record as a collections.namedtuple object, so that the caller can refer to the columns by name:

for record in From(...).select('description', 'count'):
    print('Part: {0.description}. Number: ${0.count}'.format(record))

The special case in get seems like a bad idea. It is generally best for functions to have simple and clear specifications. If you want a convenient method for returning a single column as a list, then you should write that as a separate method.
The index method on a list has to scan along the whole list comparing with each element in turn. You should consider building a dictionary in which you can look up the column name and get its index. (Or if you use namedtuple you can write getattr(row, column).)
There's very little error checking. For example, in __init__, wouldn't it be worth checking that the array has the right number of columns?
There are a couple of problems with your unique method: (i) The comment should be a docstring; (ii) by using a dictionary you don't guarantee to get the records out in the order they went in. I would use collections.OrderedDict to ensure that order of rows is preserved.

So I'd write something like this:

from collections import namedtuple, OrderedDict, Sequence

class Table(Sequence):
    """Table(name, data, columns) represents a 2-dimensional table of data
    whose column names are given by the columns argument.

        >>> from operator import attrgetter
        >>> planets = Table('Planet', [
        ...     ('Mercury',   58,    88),
        ...     ('Venus',    108,   225),
        ...     ('Earth',    150,   365),
        ...     ('Mars',     228,   687),
        ...     ('Jupiter',  779,  4333),
        ...     ('Saturn',  1433, 10759),
        ...     ('Uranus',  2877, 30799),
        ...     ('Neptune', 4503, 60190)],
        ...     ('name', 'semi_major_axis', 'period'))

    Iterating over the table yields the rows as namedtuple objects:

        >>> max(planets, key=attrgetter('semi_major_axis'))
        Planet(name='Neptune', semi_major_axis=4503, period=60190)

    You can filter the table to get a subset of the rows:

        >>> planets.filter(lambda p: p.period > 10000)
        ... # doctest: +NORMALIZE_WHITESPACE
        Table('Planet',
              [Planet(name='Saturn', semi_major_axis=1433, period=10759),
               Planet(name='Uranus', semi_major_axis=2877, period=30799),
               Planet(name='Neptune', semi_major_axis=4503, period=60190)],
              ['name', 'semi_major_axis', 'period'])

    Or select a subset of the columns:

        >>> planets.select('name')
        ... # doctest: +NORMALIZE_WHITESPACE
        Table('Planet',
              [Planet(name='Mercury'),
               Planet(name='Venus'),
               Planet(name='Earth'),
               Planet(name='Mars'),
               Planet(name='Jupiter'),
               Planet(name='Saturn'),
               Planet(name='Uranus'),
               Planet(name='Neptune')],
              ['name'])

    If you just want the values from a column, use the column method:

        >>> ' '.join(planets.column('name'))
        'Mercury Venus Earth Mars Jupiter Saturn Uranus Neptune'

    """
    def __init__(self, name, table, columns):
        self.name = name
        self.columns = list(columns)
        Row = namedtuple(self.name, self.columns)
        self.column_set = set(self.columns)
        self.table = [Row(*row) for row in table]

    def __len__(self):
        return len(self.table)

    def __getitem__(self, key):
        return self.table[key]

    def __iter__(self):
        return iter(self.table)

    def __repr__(self):
        return '{0}({1.name!r}, {2!r}, {1.columns!r})'.format(
            self.__class__.__name__, self, list(self))

    def column(self, column):
        """Generate the values in the given column."""
        assert(column in self.column_set)
        for row in self:
            yield getattr(row, column)

    def filter(self, condition):
        """Return a new Table containing only the rows satisfying
        condition.

        """
        return Table(self.name, filter(condition, self), self.columns)

    def where(self, column, value):
        """Return a new Table containing the rows from this table for which
        the given column has the given value.

        """
        assert(column in self.columns)
        return self.filter(lambda row: getattr(row, column) == value)

    def whereNot(self, column, value):
        """Return a new Table containing the rows from this table for which
        the given column does not have the given value.

        """
        assert(column in self.columns)
        return self.filter(lambda row: getattr(row, column) != value)

    def select(self, *columns):
        """Return a new Table consisting only of the given columns of this
        table.

        """
        assert(all(c in self.columns for c in columns))
        return Table(self.name,
                     ((getattr(row, c) for c in columns) for row in self),
                     columns)

    def unique(self, *columns):
        """Return a new Table containing one row for each unique combination
        of values in the given columns. (If there are multiple rows
        with the same combination of values, the last one is
        included.)

        """
        assert(all(c in self.columns for c in columns))
        result = OrderedDict((tuple(getattr(row, c) for c in columns), row)
                             for row in self)
        return Table(self.name, result.values(), self.columns)


Efficient visualization of large number of particles using openGL I have been looking into using some software to perform industrial-scale DEM simulations. These type of simulations will require millions of particles to be simulated.

Currently, the software I would like to use has some notable performance issues when visualizing the results during the simulation when using openGL. It turns out the part of the code responsible for drawing the particles is this:

void Draw_ParticleGeometry_Sphere()
{
  SetColor_Ramp();

//if(m_OpenGL.Debug_Lines==1)
//{
//  Gl_WireframeP = true;
//}

  for( int i=0; i<m_num_KParticleObjects; i++ )
  {
     glNewList(10+i,GL_COMPILE);

    if(m_OpenGL.color_type==0)
    {
     glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, Col[i]);
     glMaterialfv(GL_FRONT, GL_SPECULAR, materialSpecular);
     glMaterialfv(GL_FRONT, GL_EMISSION, materialEmission);
     glMaterialf(GL_FRONT, GL_SHININESS, shininess);
    }
          glPushMatrix();

          glutSolidSphere(m_KParticleObject[i].radius,20,20);

          if(Gl_WireframeP)
          {

                 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, Col[6]);
                 glMaterialfv(GL_FRONT, GL_SPECULAR, materialSpecular);
                 glMaterialfv(GL_FRONT, GL_EMISSION, materialEmission);
                 glMaterialf(GL_FRONT, GL_SHININESS, shininess);
            glutWireSphere(m_KParticleObject[i].radius*1.02f,15,15);
          }
          glPopMatrix();

     glEndList();

  }

}

To be fair I'm new to openGL, but it seems to me that this piece of code loops over all particles, assigns them attributes and add them to a list. Generally, looping like this is not very efficient for a large number of elements. I have been reading up in visualizing particles in openGL and it seems instancing would be a better fit. My questions are:

Is looping over all particles like this an efficient way of handling such large systems of particles in openGL?
Is there an alternative to looping over all particles?
How could this code be improved?

Basic optimizations

There are a number of possible optimizations you could apply to your problem. Particle simulation real-time rendering is a well researched topic and I think you will be able to find a lot of material on the subject. In particular, look into game development-related research. Games make heavy use of real-time particles. The GPU Pro series might be a good place to start.

The first basic optimization to unlock would be to port your code to modern, shader-based OpenGL (starting from GL version 3 and above). Note that I use the term port. It will be a major change from the legacy OpenGL used in your example, but it is the only way you can take full advantage of the current graphics hardware on the market.

Start by changing your rendering code to use Vertex Buffers. This by itself will make things more efficient by reducing CPU/GPU traffic and the number of API calls. A full explanation on Vertex Buffers would be beyond the scope of this answer, plus it is a common introductory subject on modern OpenGL, so you can find dozens of tutorials out there.

Once you have your Vertex Buffers and shaders set up, you might consider reviewing the way you are drawing the particles. Rendering a full sphere for each particle is very inefficient. They are far too small to require a large number of vertices, in general. All real-time applications and games "fake" particles by drawing a textured quadrilateral per particle that always faces the viewer/camera. When you add alpha blending to the texture, results look quite convincing, even with the simplest of approaches. You can find some samples at my website.

After you have made these major conversions, remember to look into view-dependent culling. It is likely that for any given view of your scene, some or even most particles will not be visible. It is usually more efficient to spend some time testing for the potentially visible geometry and them culling the non-visible parts than to just submit everything to the GPU at every frame. The simplest form of viewport culling is the frustum culling.

Going further

Once you have looked into the above, it might still not be enough for the throughput you need. It will then be the time to start looking into Instanced Rendering and Transform Feedback. Using Compute Shaders might also help accelerating things if you can perform some of the simulation in the GPU as well as the rendering.

I hope these pointers can give you some perspective and a rough roadmap to follow. To know more about each of the topics, I suggest searching the StackOverflow and GameDev.SE sites, as well as good ol Google.


Made an Object pool in C++ I'm making a Minecraft clone and have made an Object Pool. Looking for some advice on how I have implemented it.

Uses m_availableObjects as a O(1) way of searching for the next available object.

Thank you in advance.

constexpr int INVALID_OBJECT_ID = -1;

//Internal Use - Object Pool
template <class Object>
struct ObjectInPool : private NonCopyable
{
    ObjectInPool(int ID)
        : object(),
        inUse(false),
        ID(ID)
    {}
    ObjectInPool(ObjectInPool&& orig) noexcept
        : object(std::move(orig.object)),
        inUse(orig.inUse),
        ID(orig.ID)
    {
        orig.ID = INVALID_OBJECT_ID;
        orig.inUse = false;
    }
    ObjectInPool& operator=(ObjectInPool&& orig) noexcept
    {
        object = std::move(orig.object);
        inUse = orig.inUse;
        ID = orig.ID;

        orig.ID = INVALID_OBJECT_ID;
        orig.inUse = false;
        return *this;
    }
    ~ObjectInPool() {}

    Object object;
    bool inUse;
    int ID;
};

//External Use - Object Pool
template <class Object>
class ObjectPool;
template <class Object>
struct ObjectFromPool : private NonCopyable
{
    ObjectFromPool(ObjectInPool<Object>* objectInPool, std::function<void(int)> func)
        : objectInPool(objectInPool),
        m_func(func)
    {
        if (objectInPool)
        {
            objectInPool->inUse = true;
        }
    }
    ~ObjectFromPool()
    {
        if (objectInPool)
        {
            objectInPool->object.reset();
            objectInPool->inUse = false;

            m_func(objectInPool->ID);
        }
    }
    ObjectFromPool(ObjectFromPool&& orig) noexcept
        : objectInPool(orig.objectInPool),
        m_func(orig.m_func)
    {
        orig.objectInPool = nullptr;
    }
    ObjectFromPool& operator=(ObjectFromPool&& orig) noexcept
    {
        objectInPool = orig.objectInPool;
        m_func = orig.m_func;

        orig.objectInPool = nullptr;

        return *this;
    }

    Object* getObject() const
    {
        return (objectInPool ? &objectInPool->object : nullptr);
    }

private:
    ObjectInPool<Object>* objectInPool;
    std::function<void(int)> m_func;
};

using std::placeholders::_1;

//Object Pool
template <class Object>
class ObjectPool : private NonCopyable, private NonMovable
{
public:
    ObjectPool(int visibilityDistance, int chunkWidth, int chunkDepth)
        : m_objectPool()
    {
        //Added a little bit more than neccessary due to how the inifinite map generates
        int x = visibilityDistance / chunkWidth;
        x += x += 1;
        int z = visibilityDistance / chunkDepth;
        z += z += 1;

        m_objectPool.reserve(x * z);
        for (int i = 0; i < x * z; ++i)
        {
            m_objectPool.emplace_back(i);
            m_availableObjects.push(i);
        }
    }

    ObjectFromPool<Object> getNextAvailableObject()
    {
        if (!m_availableObjects.empty())
        {
            int ID = m_availableObjects.top();
            m_availableObjects.pop();
            assert(ID < m_objectPool.size());
            return ObjectFromPool<Object>(&m_objectPool[ID], std::bind(&ObjectPool<Object>::releaseID, this, _1));
        }
        else
        {
            return ObjectFromPool<Object>(nullptr, std::bind(&ObjectPool<Object>::releaseID, this, _1));
        }
    }

private:
    std::stack<int> m_availableObjects;
    std::vector<ObjectInPool<Object>> m_objectPool;

    void releaseID(int ID)
    {
        assert(ID != INVALID_OBJECT_ID);
        m_availableObjects.push(ID);
    }
};

This looks way too overengineered. Is there really a need for all the complexity? Use the KISS principle!

I'm assuming you have this pool because you want to avoid the cost of constructing and destructing Objects, and possibly to allocate a lot of instances of Object up front to avoid latency later on. If that's the case, I would instead write the pool like so:

template<typename Object>
class ObjectPool: private NonCopyable
{
    std::deque<std::unique_ptr<Object>> m_objects;

public:
    ObjectPool(size_t count = 0) {
        for(size_t i = 0; i < count; ++i) {
            auto object = std::make_unique<Object>();
            enqueue(object);
        }
    }

    std::unique_ptr<Object> dequeue() {
        if (m_objects.empty()) {
            return std::make_unique<Object>();
        } else {
            auto object = std::move(m_objects.back());
            m_objects.pop_back();
            return object;
        }
    }

    void enqueue(std::unique_ptr<Object> &object) {
        m_objects.emplace_back(std::move(object));
    }
};

First, the constructor of this object pool just takes the initial size of the pool as a single value, so it doesn't have to know the specifics of chunk sizes.

Second, the dequeue() function creates a new object for you automatically if the pool is empty. Maybe that is not desired, in which you could return an empty std::unique_pointer instead.

Last but not least, instead of leaving it up to the destructor of an ObjectFromPool to return the object back to the pool it came from, there is now a counterpart to dequeue(): enqueue(). It simply returns an object back to its pool. This avoids having to wrap objects in custom classes.

The only issue with this solution might be that you forget to return an object to its pool, but on the other hand it will still safely destruct itself once its lifetime ends.


Handling Enum flags for a copy operation I've just set up a bit of code to try and make things neater, but all I've really done, is add a whole bunch of nested if statements:

public void Copy(Copy copyType)
{
    FrmProjectChooser frm = null;
    if (copyType.HasFlag(Copy.Single))
    {
        if (copyType.HasFlag(Copy.Estimations) && copyType.HasFlag(Copy.SubItems))
        {
            // Single item, with sub items and estimations
            List<WB> items = new List<WB> { (WB)treeWBS.GetDataRecordByNode(treeWBS.FocusedNode) };
            items.AddRange(_WBSManager.GetAllChildren(items[0].idWBS));
            List<CTREstimation> estimations = new List<CTREstimation>();
            foreach (WB wbs in items)
                estimations.AddRange(CTREstimationsManager.Instance.GetEstimationsForWBS(wbs.idWBS));
            frm = new FrmProjectChooser(items, estimations);
        }
        else if (copyType.HasFlag(Copy.Estimations))
        {
            // Single item, with estimations.
            WB wbsItem = treeWBS.GetDataRecordByNode(treeWBS.FocusedNode) as WB;
            if (wbsItem != null)
                frm = new FrmProjectChooser(new List<WB> { wbsItem },
                    CTREstimationsManager.Instance.GetEstimationsForWBS(wbsItem.idWBS));
        }
        else if (copyType.HasFlag(Copy.SubItems))
        {
            // Single item, with sub items
            List<WB> items = new List<WB> { (WB)treeWBS.GetDataRecordByNode(treeWBS.FocusedNode) };
            items.AddRange(_WBSManager.GetAllChildren(items[0].idWBS));
            frm = new FrmProjectChooser(items);
        }
        else
        {
            // Single item
            WB wbsItem = treeWBS.GetDataRecordByNode(treeWBS.FocusedNode) as WB;
            if (wbsItem != null)
                frm = new FrmProjectChooser(new List<WB> {wbsItem});
        }
    }
    else if (copyType.HasFlag(Copy.All))
    {
        if (copyType.HasFlag(Copy.Estimations))
        {
            // All items, with estimations.
            List<WB> wbsItems = _WBSManager.GetWBSForProject(CurrentProject.idProjects);
            List<CTREstimation> estimations = new List<CTREstimation>();
            foreach (WB wbs in wbsItems)
                estimations.AddRange(CTREstimationsManager.Instance.GetEstimationsForWBS(wbs.idWBS));
            frm = new FrmProjectChooser(wbsItems, estimations);
        }
        else
        {
            // All items
            frm = new FrmProjectChooser(_WBSManager.GetWBSForProject(CurrentProject.idProjects));
        }
    }

    if (frm != null)
        frm.ShowDialog();
}

[Flags]
private enum Copy
{
    None = 0,
    Single = 1, // Straight copy of single item
    SubItems = 1 << 1, // Include any children in the copy
    Estimations = 1 << 2, // Include estimations in the copy
    All = 1 << 3 // Copy all items
}

The code will pull "Items" from a TreeList. "Sub Items" are of the same type as "Items", but Estimations are a different type. I don't think it's very neat. I've tried googling similar titles to this question but I can't really find anything that helps.

Is there anything I can do to make this neater?

For an aesthetic point of view, you could define some constants:

AllEstimations = Copy.All | Copy.Estimations
SingleEstimations = Copy.Single | Copy.Estimations
etc.

You could then check the value against these constants and create a single level if statement:

if (copyType == SingleEstimationsSubItems)
{}
elseif (copyType == SingleEstimations)
{}
elseif (....

I'm not claiming this will improve performance, but it will make the code more readable.


Find change in XML and print node This code has been developed with help on Stack Overflow. It is designed to compare two XML files and print the node for any differences (i.e if a entry appears in A.xml and not B.xml and vice versa).

#include "pugixml.hpp"

#include <iostream>
#include <unordered_map>

struct string_hasher
{
    unsigned int operator()(const char* str) const
    {
        // Jenkins one-at-a-time hash (http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-time)
        unsigned int result = 0;

        while (*str)
        {
            result += static_cast<unsigned int>(*str++);
            result += result << 10;
            result ^= result >> 6;
        }

        result += result << 3;
        result ^= result >> 11;
        result += result << 15;

        return result;
    }

    bool operator()(const char* lhs, const char* rhs) const
    {
        return strcmp(lhs, rhs) == 0;
    }
};

typedef std::unordered_map<const char*, pugi::xml_node, string_hasher, string_hasher> xml_node_map;

int main()
{
    pugi::xml_document doca, docb;
    xml_node_map mapa, mapb;

    if (!doca.load_file("a.xml") || !docb.load_file("b.xml"))
        return 1;

    for (auto& node: doca.child("site_entries").children("entry"))
        mapa[node.child_value("id")] = node;

    for (auto& node: docb.child("site_entries").children("entry"))
        mapb[node.child_value("id")] = node;

    for (auto& ea: mapa)
        if (mapb.count(ea.first) == 0)
        {
            std::cout << "Removed:" << std::endl;
            ea.second.print(std::cout);
        }

    for (auto& eb: mapb)
        if (mapa.count(eb.first) == 0)
        {
            std::cout << "Added:" << std::endl;
            eb.second.print(std::cout);
        }
}

I was wondering if I could get some feedback on how it is designed, most notably if this is the optimal approach in terms of performance, since this has to sort hundreds of thousands of entries.

Example XML file:

<entry> <id><![CDATA[90007316]]></id> <url>< [CDATA[http://www.site.co.uk/cgi-bin/tr.cgi?tid=70952276]]></url> <content><![CDATA[Giant Sport Offroad Bike]]></content> <title><![CDATA[Bike]]></title> <price><![CDATA[£100]]></price> <date><![CDATA[11-AUG-15]]></date> <display_reference><![CDATA[2146433-50142933_370647]]></display_reference> <location><![CDATA[City of London]]></location> <category><![CDATA[Bike]]></category> </entry>

Your code is somewhat simplistic in that all it is doing is ensuring that the same id values appear in each document. XML is a lot more complicated than that, though, and you may have problems when:

you have multiple entries with the same id
you have entries without an id
the content in entries with the same ID in different documents is wildly different.

In terms of the algorithm, the code is clear, and so on. The string_hasher logic concerns me a bit simply because I am not that familiar with C++ (I am more familiar with XML)..... but, I have the following concerns there:

Why return int for the hash? It is specified to return size_t.
why have the struct at all?

If you convert the const char* ID to be a std::string then you can just make it a map of std::string and use the default values for the hashing and equalities in the template.

Funally, as a small optimization, you can probably save half your memory if you us a 'subtraction' type algorithm for comparing the document structures. Consider )note, I always use braces for code blocks, even if they have just one line):

for (auto& node: doca.child("site_entries").children("entry")) {
    mapa[node.child_value("id")] = node;
}

Then, in the next loop, do the following instead:

for (auto& node: docb.child("site_entries").children("entry")) {
    const char* nid = node.child_value("id");
    if (!mapa.erase(nid)) {
        mapb[nid] = node;
    }
}

Now, at this point, there is no need to perform an intersection on the maps... the values in mapa we know ae not in mapb, and visa versa. You can just print the contents of the two maps without any further processing...

Putting all these suggestions together, your code would look something like:

int main() {
    pugi::xml_document doca, docb;
    std::map<string, pugi::xml_node> mapa, mapb;

    if (!doca.load_file("a.xml") || !docb.load_file("b.xml"))
        return 1;

    for (auto& node: doca.child("site_entries").children("entry")) {
        const char* id = node.child_value("id");
        mapa[new std::string(id, strlen(id))] = node;
    }

    for (auto& node: docb.child("site_entries").children("entry"))
        const char* idcs = node.child_value("id");
        std::string id = new std::string(idcs, strlen(idcs));
        if (!mapa.erase(id)) {
            mapb[id] = node;
        }
    }

    for (auto& ea: mapa) {
        std::cout << "Removed:" << std::endl;
        ea.second.print(std::cout);
    }

    for (auto& eb: mapb) {
        std::cout << "Added:" << std::endl;
        eb.second.print(std::cout);
    }

}


Showing unapproved comments in a discussion system In my project (which is a discussion system) there are approved and unapproved comments. There's a class that tells if unapproved comments should be shown. But I cannot think of a good name for this class. Right now it's named ShowUnapproved but doesn't that sound like a Boolean? (Rather than a configuration setting.)

Is the name ShowUnapproved clear to you? Or can you think of a better name?

Here is the class:

sealed abstract class ShowUnapproved {
  def shallShow(post: Post): Boolean // a "post" is e.g. a comment
}

object ShowUnapproved {

  case object None extends ShowUnapproved {
    override def shallShow(post: Post) =
      post.someVersionApproved
  }

  case object All extends ShowUnapproved {
    override def shallShow(post: Post) = true
  }

  case class WrittenByUser(userId: String) extends ShowUnapproved {
    override def shallShow(post: Post) =
      post.userId == userId
  }
}

Here're two examples of how to use it:

PageReneder.renderPage(page, ShowUnapproved.All)
PageReneder.renderPage(page, ShowUnapproved.WrittenByUser(userId))

And what would you call instances of this ShowUnapproved class?

I'm currently naming them showUnapproved which definitively sounds like a Boolean to me, and might be confusing:

val showUnapproved = ...  // sounds like a Boolean but it is not

val anyPendingApprovalText: NodeSeq =
  if (showUnapproved.shallShow(post)) makePendingApprovalText(post)
  else Nil
  // does `showUnapproved.shallShow` above sound good to you?

What about something like this:

sealed abstract class CommentVisibility {
  def shallShow(comment: Comment): Boolean
}

object CommentVisibility {
  case object HideUnapproved
  case object ShowUnapproved
  case class ShowAllByUser(userId)
}

Usage:

renderPage(page, CommentVisibility.ShowUnapproved)

That's easy to understand :-) And can be amended to include e.g. showing/hiding comments with too many flags. (One would add another case class, perhaps using the Composite design pattern)

And reminds of CSS I think: "visibility: hidden / visible"


Symmetric Tree Check in Python Inspired by This LeetCode Question.

Instead of checking if every layer is symmetric, it instead checks if any aren't. This allows the program to leave early is an early layer fails the test. I'm looking for performance mostly, as I loop through each element in the list, instead of each layer. All feedback is appreciated and considered.

"""
This program determines if a given binary
tree is a mirror of itself

Example:

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3
"""

def is_symmetric(tree: list) -> bool:
    """
    Returns if the passed tree is symmetric

    :param tree: A list representing a binary tree
    """

    interval = 2
    start = 0
    end = 1
    for _ in range(len(tree)):
        # Find next layer
        layer = tree[start:end]

        # Determine if layer isn't mirror
        if layer != list(reversed(layer)):
            return False

        # Setup for next layer
        start = end
        end = (2 ** interval) - 1
        interval += 1

    return True

if __name__ == '__main__':

    assert is_symmetric([1, 2, 2, 3, 4, 4, 3]) # True
    assert not is_symmetric([1, 2, 2, None, 3, None, 3]) # False

Two things:

The function may fail for a tree with an incomplete last layer.  For example:

is_symmetric([1, 2, 2, 3, 4, 3])  returns True, but it should be False.

This can be fixed by checking if layers have the expected length.

if len(layer) != (end - start) or layer != list(reversed(layer)):
        return False

The for loop iterates more times than needed.  The loop only needs to run for each layer in the tree, not for each node.  A tree with n layers has 2**n - 1 nodes. It may not matter for small trees, but a tree with 20 layers has over a million nodes.  Replace the for loop with a while loop:

while start < len(tree):
...

Okay, three things.  interval isn't needed.  Use:

end = 2 * end + 1

The revised routine:

def is_symmetric(tree: list) -> bool:
    """
    Returns if the passed tree is symmetric

    :param tree: A list representing a binary tree
    """

    start = 0
    end = 1

    while start < len(tree):
        # Find next layer
        layer = tree[start:end]

        # Determine if layer isn't mirror
        if len(layer) != (end - start) or layer != list(reversed(layer)):
            return False

        # Setup for next layer
        start = end
        end = 2 * end  + 1

    return True

if __name__ == '__main__':
    tests = [
        ([1], True),
        ([1, 2, 2, 3, 4, 4, 3], True),
        ([1, 2, 2, None, 3, None, 3], False),
        ([1, 2, 2, 3, 4, 3], False)
        ]

    for n, (test, answer) in enumerate(tests):
        result = is_symmetric(test)
        print(f"Test {n} {'Pass' if answer==result else 'FAIL'}: is_symetric({test})")


Reading text from 2 files I've got 2 simple text files:

besede.txt
To je vsebina datoteke z besedami. V njej so razlicne besede ki imajo lahko pomen ali pa tudi ne.

skrivno.txt
4 3 19 2 3 2 4 3

I wrote a program which receives these 2 files' names as arguments. It finds pairs of numbers in skrivno.txt and the first number in the pair is the index of the word in besede.txt; the second number in the pair is the index of the letter in that word.
So in this case I get:

4th word, 3rd letter - T
19th word, 2nd letter - E
3rd word, 2nd letter - S
4th word, 3rd letter - T

So, TEST.
Here is my program that does this. I'm open to suggestions on what I could improve and do better, etc.
public class meow {
    public static void main(String args[]) throws Exception{
        Scanner sc1 = new Scanner(new File(args[0])); //besede.txt
        Scanner sc2 = new Scanner(new File(args[1])); //skrivno.txt
        int inW = 0, inL = 0; //index of word, index of line
        String text = "", code = "";
        while(sc1.hasNext()){
            text += sc1.next() + " ";
        }
        String[] text2 = text.split(" ");
        while(sc2.hasNext()){
            inW = sc2.nextInt();
            inL = sc2.nextInt();
            if(inW == 0 && inL == 0){
                code += " ";
            }
            code += text2[inW-1].charAt(inL-1);
        }
        System.out.printf("%s\n", code);
    }
}

There are quite some things you can improve here, this list may not cover everything that could be improved though:

Adhere to the Java naming conventions. Classes are named in PascalCase for example, so it would be public class Meow. On other places it seems fine.
Use proper indentation everywhere, this definately applies to the main method inside public class meow, as all items should be intended one to the right. This may also apply to the while loops, I would prefer to write while(sc1.hasNext()){ as while (sc1.hasNext()) { for readability.
Variable names are not expensive. sc1, sc2 are dubious, but could be ok. However inW and inL are plain alarming, the fact that you need to comment to explain them is a bad sign. My suggestions are wordIndex and lineIndex.
Consider using a StringBuilder over dealing with raw strings. This means for example that:

String text = "", code = "";
while(sc1.hasNext()){
     text += sc1.next() + " ";
}

could be rewritten as:

StringBuilder sb = new StringBuilder();
while (sc1.hasNext()) {
        sb.append(sc1.next()).append(' ');
}
String text = sb.toString();

You have a bug in your second while-loop. You check for sc2.hasNext() and you take two times sc2.nextInt(). Your hasX() and nextX() calls should always match. This means that in the loop per iteration in total there should be two hasNextInt() calls with two nextInt() calls.
The same deal about StringBuilder applies here to your second while-loop for building code.
In the future you can consider switching to using the java.nio.Path API, over the old java.io.File API. I will not show more code here on how to do it, as it would completely change the structure of the program and is best used in conjunction with Java 8, which is not in the scope of this answer.


Removing duplicates from unsorted LinkedList Removing Duplicates:

/**
 * Remove duplicates without using a buffer.
 *
 * @param head
 */
public static void removeUnsortedDuplicatesWithoutBuffer(final LinkedListNode head) {

    //if the linked list is empty
    if(head == null) {
        throw new RuntimeException("linked list is empty");
        //return;
    }
    LinkedListNode current = head;
    LinkedListNode runner = null ;
    LinkedListNode previous = null ;
    boolean flag = false ;

    while(current != null) {
        runner = head;
        while(runner != current) {
            if(current.getData() != runner.getData()) {
                runner = runner.getNext();
                flag = false;
            } else {
                previous.setNext(current.getNext());
                current = previous.getNext();
                flag = true;
                break;
            }
        }
        if(!flag) {
            previous = current;
            current = current.getNext();
        }
    }
}

LinkedListNode:

class LinkedListNode {
    private int data;
    private LinkedListNode next ;

    public LinkedListNode(final int data) {
        this.data = data;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public LinkedListNode getNext() {
        return next;
    }
    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    public void appendAtTail(final int data) {
        LinkedListNode newNode = new LinkedListNode(data);
        LinkedListNode current = this;
        while(current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
}

Test Case:

@Test
public void testRemoveDuplicatesFromUnsortedSortedLL() {
    LinkedListNode head = new LinkedListNode(30);
    head.appendAtTail(20);
    head.appendAtTail(20);
    head.appendAtTail(30);
    head.appendAtTail(10);
    head.appendAtTail(50);
    head.appendAtTail(10);
    head.appendAtTail(10);
    head.appendAtTail(20);
    head.appendAtTail(50);
    head.appendAtTail(50);
    head.appendAtTail(100);
    RemoveDuplicates.removeUnsortedDuplicatesWithoutBuffer(head);
}

I wrote this code recently to remove duplicates from linked list without using buffer and was trying to analyze its complexity :
Time taken for traversing is O(n)
For each operation we need to move runner node n times to remove duplicates
Total Complexity : O(n2).
Is this correct ??
I guess not because this is no better than using two for loops and comparing each element with the rest of the elements in the LinkedList .
What am I doing wrong here?

Yes, this looks \$O(n^2)\$: when all elements are unique,
the program will compare all elements with all other elements.

A better solution will be to use a Set to keep track of the already seen items.
You will still have to iterate over all items,
but you won't have to compare to all other elements,
but simply do a lookup in the Set,
which in case of a HashSet will be \$O(1)\$ complexity.
Of course, when all elements are unique,
then this method will use twice as much memory as your original.
That's a trade-off you'll have to consider.

Unfortunately you didn't provide the implementation of LinkedListNode so it's not easy to play with this code.
But looking at it I'm wondering if it correctly removes all duplicates,
for example will it turn 1->2->2->2->2->3 into 1->2->3.
(Maybe it does, a bit hard to decipher, but I suggest to do a quick test.
And maybe next time include enough code so that reviewers can test run easily.)

UPDATE

As you remarked in your last comment,
another way, without using a buffer / Set is to sort the list first,
and remove the duplicates after.
That would have \$O(n\log n)\$ complexity.
However, keep in mind that the elements will be reordered with that approach (if they were not ordered to begin with).
Depending on your use case, that may be perfectly acceptable, of course.


Collecting company data from accident reports name = company_location
for i, j in enumerate (list):
    if j == 'Last 10 Accidents':
        last = i
        try:
            date1 = list[last+28]
            employee1 = list[last+31]
            days_lost1 = list[last+49]
            days_paid1 = list[last+43]
            with open("report.csv","a+") as report:
                report.write(str(name)+", "+str(date1)+", "+str(employee1)+", "+str(days_lost1)+", "+str(days_paid1))
            report.close()
        except (ValueError, TypeError, IndexError):
            with open("report.csv","a+") as report:
                report.write(str(name)+"\n")
            report.close()

        try:
            date2 = list[last+50]
            employee2 = list[last+53]
            days_lost2 = list[last+71]
            days_paid2 = list[last+65]
            with open("report.csv","a+") as report:
                report.write(", "+str(date2)+", "+str(employee2)+",     "+str(days_lost2)+", "+str(days_paid2))
            report.close()
        except (ValueError, TypeError, IndexError):
            with open("report.csv","a+") as report:
                report.write("\n")
            report.close()

        try:
            date3 = list[last+72]
            employee3 = list[last+75]
            days_lost3 = list[last+93]
            days_paid3 = list[last+87]
            with open("report.csv","a+") as report:
                report.write(", "+str(date3)+", "+str(employee3)+", "+str(days_lost3)+", "+str(days_paid3))
            report.close()
        except (ValueError, TypeError, IndexError):
            with open("report.csv","a+") as report:
                report.write("\n")
            report.close()

for i, j in enumerate (list):

You can't iterate through list because it is a type, so I am assuming that list is the name of a variable that you defined earlier on.  Don't do that.  When you use the name of something built-in for something else, you are overriding the variable that was previously defined.  If, for instance, you wanted to iterate through a list of tuples, but you actually wanted a list of lists, you could do for sub in map(list, tuples):, but with list redefined, you can't do that.  Besides that, it may confuse future readers of your code to be using list there when you can't iterate through a type.  Instead, use a name that not only says what type of object it is, but describes what is inside.

You have quite a bit of duplicate code in that if j == 'Last 10 accidents': block.  You should instead use a for loop iterating through different starting points.  That is, for start in (28, 50, 72): and use date = list[last + start], employee = date[list + start + 3], ...  You should be using a more descriptive name than list anyway, but I outlined that above.

with open("report.csv","a+") as report:
    report.write(str(name)+", "+str(date1)+", "+str(employee1)+", "+str(days_lost1)+", "+str(days_paid1))

Using a long string (no pun intended) of concatenations doesn't seem very good, does it?  Instead, use .join():

info = (name, date1, employee1, days_lost1)
report.write(", ".join(map(str, info)) + "\n")

That shortens the code and makes it a little easier to see what you are doing.

report.close()

The with statement will take care of closing the file so you don't need that line.

Your modified program would look like this:

name = company_location
for i, j in enumerate(reports):
    if j == 'Last 10 Accidents':
        last = i
        for start in (28, 50, 72):
            try:
                date = reports[last + start]
                employee = reports[last + start + 3]
                days_lost = reports[last + start + 21]
                days_paid = reports[last + start + 15]
                info = (date, employee, days_lost, days_paid)
                with open("report.csv","a+") as report:
                    report.write(", ".join(map(str, info)) + "\n")
            except (ValueError, TypeError, IndexError):
                with open("report.csv","a+") as report:
                    report.write(str(name)+"\n")


Python-style string multiplication When people migrate from Python to C++, they're often bothered by the fact that C++ strings don't support multiplication like Python's strings do.

std::string does have a constructor that supports creating a string with one character repeated a specified number of times. But, if the pattern to be repeated is more than one character long, C++ provides no convenient solution.

This is an attempt at providing such a solution:

#include <string>

std::string operator*(std::string const &in, size_t m) {
    std::string ret;

    for (size_t i = 0; i < m; i++)
        ret += in;
    return ret;
}

std::string operator*(size_t m, std::string const &in) {
    std::string ret;

    for (size_t i = 0; i < m; i++)
        ret += in;
    return ret;
}

For example, using these, the typical "print a Christmas tree of asterisks" task could be written something like this:

int main() {
    using namespace std::literals;

    std::cout << "Width: ";
    int width;

    std::cin >> width;

    for (int i = 1; i < width; i+=2)
        std::cout << " "s * ((width - i-1)/2) << "*"s * i << "\n";
}

[Of course, in this particular case, we're only multiplying single-character strings, so the std::string ctor would work as well.]

Note that the trailing s to make the string literal an std::string rather than a char const * is necessary--at least one operand of a user-defined operator must be a class or enumeration (or reference to a class or enumeration).

Code duplication:

There is a code duplication in the overloads of the operator. I believe that the second should call the first with parameters swapped, or vice versa.

Last feature:

The last thing I would add, aside from what @Justin mentioned, is some support for std::basic_string<>. Although it will introduce abundance of template parameters, the code will be more or less generic.

Do note that in this case reserving might make sense.


Palindrome program needs improvement Here a string is taken as input and the program suppose to check whether the string is palindrome or not.
Is there any way the code can be improved? Is it okay to use foreach to break the string into character.

class Program
{
    static void Main(string[] args)
    {
        //input a string
        string orginalStr = Console.ReadLine().ToLower(); ;

        //call the palindrome method

        Console.WriteLine(CheckPalindrome(orginalStr)
            ? "This is palindrome"
            : "This is not palindrome");

        Console.ReadKey();
    }

    static bool CheckPalindrome(string orginalStr)
    {
        //call the string reverse method
        var reversedStr = ReverseString(orginalStr);

        if (reversedStr.Equals(orginalStr))
            return true;

        return false;
    }

    static string ReverseString(string orginalStr)
    {
        string reversedStr = "";

        foreach (char ch in orginalStr)
        {
            reversedStr = ch + reversedStr;
        }

        return reversedStr;
    }
}

All in all this code does, what you want it to do and you separate responsibility by splitting the code in meaningful functions.

I don't like that CheckPalindrome(...) expects the input to be in a certain format (case). In other words: it should do the preparation of the originalStr by it self and check for invalid input:

 static bool CheckPalindrome(string orginalStr)
 {
    if (string.IsNullOrEmpty(originalStr)) return false;

    originalStr = originalStr.ToLower();

    //call the string reverse method
    var reversedStr = ReverseString(orginalStr);

    if (reversedStr.Equals(orginalStr))
        return true;

    return false;
 }

The palindrome check by comparing the original string with its reversed string is rather inefficient. Instead you can compare each char from the start of the string with the same position from the end of the string. You then only have to iterate through the half of it:

static bool IsPalindrome(string word)
{
  if (string.IsNullOrWhiteSpace(word)) return false;

  word = word.ToLower();

  for (int i = 0; i < word.Length / 2; i++)
  {
    if (word[i] != word[word.Length - i - 1])
      return false;
  }

  return true;
}

EDIT

If you go multilingual, you may find this approach useful:

static bool IsPalindrome(string word)
{
  if (string.IsNullOrEmpty(word)) return false;

  StringInfo stringInfo = new StringInfo(word.ToLower());
  int length = stringInfo.LengthInTextElements;

  for (int i = 0; i < length / 2; i++)
  {
    if (stringInfo.SubstringByTextElements(i, 1) != stringInfo.SubstringByTextElements(length - i - 1, 1))
      return false;
  }

  return true;
}

Disclaimer: I have only tested it on Latin strings, so don't hang me if...


Tools for transferring data from an API to a database I explain everything on my current code but this question is more general "HOW TO" work correctly with this in this case but even next time.

I have 4 methods in my class, each does something but in general this code just takes data from some API and insert it to another database in the right format:

// Getting data from API
public function getData()
{
    $url = manufacturerEndpoint;
    $data = array('token' => apiToken);

    // use key 'http' even if you send the request to https://...
    $options = array(
        'http' => array(
            'header'  => "Content-type: application/x-www-form-urlencoded\r\n",
            'method'  => 'POST',
            'content' => http_build_query($data),
        ),
    );
    $context  = stream_context_create($options);
    $result = file_get_contents($url, false, $context);

    return $result;
}

// Truncate oild data in new table
private function truncate() {
    try{
        $con = new PDO( DB_HOST, DB_USER, DB_PASS );
        $con->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
        $sql = "truncate r_vehicle_manufacturer CASCADE";
        $stmt = $con->prepare( $sql );
        $stmt->execute();
        }catch(PDOExeption $e){
            echo $e->getMessage();
            echo $con->errorInfo();
        }
}

// Inset new data to database
public function insertToDb($code, $name)
{
    try {
        $con = new PDO( DB_HOST, DB_USER, DB_PASS );
        $con->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
        $sql = "INSERT INTO r_vehicle_manufacturer(code, name, country_code) VALUES(:code, :name, :country_code)";
        $stmt = $con->prepare( $sql );
        $stmt->bindValue( 'code', $code, PDO::PARAM_STR );
        $stmt->bindValue( 'name', $name, PDO::PARAM_STR );
        $stmt->bindValue( 'country_code', 'CZE', PDO::PARAM_STR );
        $stmt->execute();
        }
    catch( PDOException $e ) {
            echo $e->getMessage();
        }
}
// Last method which basicly just call others:
        public function workWithData()
    {
        // Truncate data from last month
        $this->truncate();
        $json = $this->getData();
        $json_output = json_decode($json);
        foreach ( $json_output as $data )
        {
            $this->insertToDb($data->AX_CODE, $data->NAME);
        }
    }

I'm not sure if this is correct way but until now it seems right for me. But now I just have to change $url (call this method with multiple URL base on user INPUT) sometimes but it's not easy to edit if I don't want to pass the same argument to 2 methods.

My question is how should I correctly design methods to avoid as many changes as I can while respecting the fact I will have to change something in feature?

Styling and readability
Your indentation and use of whitespace is all over the place. Make sure to use consistent indentation. If you decide to add whitespace somewhere, use the same rules for whitespace elsewhere. In particular, pay attention to where you place your braces. Sometimes you put them on a new line, sometimes you do not. Sometimes you put the closing brace before a corresponding catch, sometimes you place a newline. Sometimes you indent it, sometimes you do not. Choose a style, and use it for all function definitions, for-loops, try-catch blocks etc.
Many connections
For each action you make a separate connection. You can improve the performance of your script by creating one connection, and make every query use that connection instead.
General bugs
file_get_contents(..) returns FALSE on failure. The documentation is not concise about this, but I assume that a timeout will cause it to fail. Your script should do something sensible in this case instead of trying to decode it as json.
json_decode(..) returns NULL if the result cannot be decoded properly (e.g. someone replaced the resource to "Use v.77.2 you silly goose") or the recursion limit is exceeded. You do not check for this condition.
If one of the inserts fails, do you really want to just ignore that insert and continue inserting? Do you really not want to retry it at the very least (in case of a failed connection for example).
Maintainability
You are using magic values in some places. The table name r_vehicle_manufacturer is one example of that. $url = manufacturerEndpoint; looks weird to me and might be an other one if that is your way of anonymizing the code.
This seems to be an (incomplete) class definition. I feel that the function to retrieve data from an api and the functions to interact with the database should not be in the same class.


CSS Styling: Should I specify the element type? Which of the following is better code:

div#style1{

}

or

#style1{
}

Also, should the element type be specified for classes or not?

It depends what you mean by "better".

Because of the way the style system matches rules, #style1 is faster than div#style1 (and the same goes for classes). For this reason, conventional wisdom is that the former, less-qualified selector is better.

However, it may be that div#style1 is more easily understood by the next person1 editing the CSS than #style1 (in the specific case you give, probably not - but, for example, the meaning of a selector like a.external is immediately obvious to anyone reading it in a way that a bare .external isn't).

In cases like that, you have to decide which is more important: making your CSS as straightforward as possible to maintain, or making it (perhaps only very slightly) faster to render.

1 Maybe you in eighteen months, maybe someone else entirely.