Hackerrank, Utopian Tree in Haskell Problem statement

  The Utopian tree goes through 2 cycles of growth every year. The first
  growth cycle occurs during the monsoon, when it doubles in height. The
  second growth cycle occurs during the summer, when its height
  increases by 1 meter.  Now, a new Utopian tree sapling is planted at
  the onset of the monsoon. Its height is 1 meter. Can you find the
  height of the tree after \$N\$ growth cycles?

  Input Format

  The first line contains an integer, \$T\$, the number of test cases.
  \$T\$ lines follow. Each line contains an integer, \$N\$, that denotes
  the number of cycles for that test case.

  Constraints

1 <= T <= 10
0 <= N <= 60

  Sample Input: #01:

2
3
4

  Sample Output: #01:

6
7

  Explanation: #01:

  There are 2 testcases.

  N = 3:
  * the height of the tree at the end of the 1st cycle = 2
  * the height of the tree at the end of the 2nd cycle = 3
  * the height of the tree at the end of the 3rd cycle = 6

  N = 4:

  the height of the tree at the end of the 4th cycle = 7

This is my accepted solution:

module Main where

import Control.Monad(mapM_)

main = do
    let base_height = 1
    n_test_cases <- readLn
    test_cases <- getList n_test_cases
    mapM_ (\i -> putStrLn $ show $ utopianTreeHeight base_height
        (test_cases !! i)) [0..n_test_cases - 1]

getList :: Int -> IO [Int]
getList n =
    if n == 0
        then return []
    else
        do
            x <- readLn
            xs <- getList (n - 1)
            return (x:xs)

utopianTreeHeight :: Int -> Int -> Int
utopianTreeHeight present_height 0 = present_height
utopianTreeHeight present_height cycles =
    if odd cycles
        then 2 * (utopianTreeHeight present_height (cycles - 1))
    else
        1 + (utopianTreeHeight present_height (cycles - 1))

So, does this solution show good Haskell style? What could be improved? I have doubts especially regarding the way I deal with the IO (which was not provided by Hackerrank), as it was the first time I read about and applied  the Haskell way of doing it.

Your solution lacks the use of higher-order functions that are an essential part of Haskell style. Instead of writing explicitly recursive functions that plumb state around (like an impoverished for-loop) seek out, create, and use constructs that have semantic meaning to your problem.

Starting from the small, the problem defines a growth cycle as a either doubling a tree's height, or increasing it by one. We can encode all of that information in Haskell.

type Height = Integer
type Cycle = Height -> Height

monsoon :: Cycle
monsoon = (* 2)

summer :: Cycle
summer = (+ 1)

Next, we know that the cycles begin with a monsoon and thereafter proceed regularly indefinitely into the future.

timeline :: [Cycle]
timeline = cycle [monsoon, summer]

cycle is a function from the Haskell Prelude module which turns a finite list into an infinite list by infinitely repeating it. Now we can take a finite sequence from the front of the list to determine all of the cycles the tree will experience over a given span of time.

-- code fragment
take n timeline :: [Cycle] -- n cycles from planting

Now given the original height of the tree and the cycles it will experience over a given span of time, we can find the resulting height of the tree.

utopian :: Int -> Height
utopian n = foldl (flip ($)) 1 $ take n timeline

We fold over the finite timeline from the left, applying each growth function to the accumulator (starting with the height of the tree at year 0).


Learning Java: Celcius to Fahrenheit Conversion This is a short Celcius to Fahrenheit conversion calculator that calculates the average of all entries before exiting. This program performs exactly to the required specification.
I have some concern about the cleanliness of the multiple variable declaration and initialization to zero in a single line. I've seen this done on a few sites, and it works, but is it conventional to see Java variables initialized in this way?
Regarding assigning everything zero, is it more or less appropriate to give a variable a value when declaring it?
I'm also concerned with the double conversion variable in the if statement, is this is scoped properly, or should conversion be declared with the other variables?
These were just a few of points I noticed myself, please review for syntax, convention, and readability.
package temperature;

import java.util.Scanner;

public class Temperature {

public static void main(String[] args) {
    int counter = 0;
    double input = 0;
    double celciusInputs, fahrenheitInputs = celciusInputs = 0;

    Scanner in = new Scanner(System.in);

    do {
      System.out.print("Enter Temp in Centigrade or <= -100.0 to quit: ");
      input = in.nextDouble();
      if (input > -100.0) {
        double conversion = ((9.0/5.0) * input) + 32.0;
        System.out.printf("Temperature: F(%.1f) C(%.1f)\n", conversion, input);
        celciusInputs += input;
        fahrenheitInputs += conversion;
        counter += 1;
      }
    } while (input > -100.0);

    // Calculate averages
    celciusInputs /= counter;
    fahrenheitInputs /= counter;

    System.out.printf("Average: Centigrade (%.1f) Average: Fahrenheit(%.1f)",
            celciusInputs, fahrenheitInputs);

    in.close();
  }
}

double celciusInputs, fahrenheitInputs = celciusInputs = 0;

Variables declared and initialized this way are hard to read. Prefer:
double celciusInputs = 0;
double fahrenheitInputs = 0;

double celciusInputs, fahrenheitInputs = celciusInputs = 0;

The Inputs in the name signals to me that it is an array of values. It is not. Prefer celciusInputsSum and fahrenheitInputsSum

System.out.print("Enter Temp in Centigrade or <= -100.0 to quit: ");

Spell out Temp as temperature to avoid confusion. Centigrade should also be worded as "Celsius" to avoid confusion (even variable names use "celsius", not "centigrade")
Why is minimum allowed temperature -100.0 °C? Absolute zero is at -273.15 °C

input = in.nextDouble();

Error handling should be added. What do you want to do when user enters foobar as input?

double conversion = ((9.0/5.0) * input) + 32.0;

From this line alone, we do not know the units. Prefer fahrenheitConverted or similar

counter += 1;

Instead of summing the inputs, perhaps consider ArrayList to store the inputs. The sum can only go so far before celciusInputs and fahrenheitInputs overflow. It also provides more flexibility if you want to do other calculations (such as calculating mode and median, along with the mean/average)

celciusInputs /= counter;
fahrenheitInputs /= counter;

Doing it like this means the variable names no longer reflect its contents. Prefer using new variables like this: double celsiusInputAverage = celciusInputs / numInputs

public static void main(String[] args) {

This line is missing indentation (2 spaces)


Small Kivy application I've written a small app using the kivy framework, which aims at reviewing your times tables. My major concern is about making this app easier to improve in the future. That is, how to organize the code to make it more clearer (by adding a User class that would store the data associated to the user, for instance). Since the code pretty straightforward, I've not added documentation to it.

The Python code:

# -*- coding: utf-8 -*-
from numpy.random import randint

import kivy
kivy.require('1.9.1-dev')
from kivy.app import App
from kivy.uix.widget import Widget
from kivy.core.window import Window
from kivy.properties import StringProperty

Window.size = (200, 100)

class MyWidget(Widget):

    help_message = StringProperty()
    question = StringProperty()
    feedback = StringProperty()

    def __init__(self):
        super(MyWidget, self).__init__()
        self.help_message = "Your answer"
        self.question = ""
        self.answer = 0
        self.points = 0
        self.attempts = 1e-10
        self.feedback = ""
        self.set_question()

    def set_question(self):
        a, b = randint(1, 11, 2)
        self.question = "{} x {} =".format(a, b)
        self.answer = a * b

    def check_answer(self, user_input):
        try:
            if int(user_input) == self.answer:
                self.points += 1
                self.feedback = "right"
            else:
                self.feedback = "{} {}".format(self.question, self.answer)
            self.set_question()
            self.attempts += 1
        except:
            self.feedback = "invalid answer"

    def set_score(self):
        score = self.points / self.attempts * 100
        self.feedback = "{:3.0f}% of right answers".format(score)

class MyApp(App):
    def build(self):
        return MyWidget()

if __name__ == '__main__':
    MyApp().run()

The .kv one:

<MyWidget>:

    canvas:
        Color:
            rgba: .93, .93, .93, 1.
        Rectangle:
            pos: self.pos
            size: self.size

    TextInput:
        size: 130, 30
        pos: 70, 30
        text: root.help_message
        background: 1., 1., 1., 1.
        font_size: 14
        multiline: False
        on_text_validate: root.check_answer(self.text); self.text = ""

    Label:
        size: 200, 30
        pos: 0, 60
        text: root.feedback
        color: .0, .0, .0, 1.
        font_size: 14

    Label:
        size: 70, 30
        pos: 0, 30
        text: root.question
        color: .0, .0, .0, 1.
        font_size: 14

    Button:
        size: 200, 30
        pos: 0, 0
        text: "Stop"
        color: .0, .0, .0, 1.
        font_size: 14
        on_release: root.set_score()

[EDIT] Mentioned code reviewer here.

Your code is very nice! There is almost nothing for me to fault.

However, your try except statement is far too large in the try and is a bare except. Let's say, for whatever reason, your .format raises an error. You could have put the correct answer, however for reason beyond your control, the program failed. And you the user gets '1 x 3 = 3', when they put 3.

To amend this you can use the else part of the try except else finally:

try:
    user_input = int(user_input)
except ValueError:
    self.feedback = "invalid answer. Please enter numbers."
else:
    if user_input == self.answer:
        self.points += 1
        self.feedback = "right"
    else:
        self.feedback = "{} {}".format(self.question, self.answer)
    self.set_question()
    self.attempts += 1

You could say that you don't want to do user_input = int(user_input).
If this were the case then you can have the try as just int(user_input),
and have the else as your old try.

If I were to improve this more:

Better class names.

MyApp is not descriptive and is definitely not my app. TimesTabelsApp could be an alternate, unless you wish to add more to it. The same as above goes for MyWidget. You could likewise call this TimesTabelsWiget.
Put almost everything in the Python 'main'.

Window.size = (200, 100), should be in the main. It will still be global!
Try to avoid large library's when python comes built in with things you need.

I don't think I should need to install NumPy, when CPython already has randint. Sure, it's not as convenient, but asking an end user to install an entire library for something so small is kinda annoying. I know numpy is pip install numpy away, but Python can do this.

from random import randint
a, b = randint(1, 11), randint(1, 11)

A single line at the begging of each function, class and module is enough to document your code entirely.

def set_question(self):
"""Set the internal question and answer."""

Sure it's something that can be understood from the code, but what if I don't want to read the code, or can't.
Finally, I don't know why you need self.attempts = 1e-10. It seems kinda strange. And gives a large answer in set_score. I think it's to not get a ZeroDivisionError in set_score.

So you could try this:

try:
    score = self.points / self.attempts
except ZeroDivisionError:
    self.feedback = "You didn't attempt any answers"
else:
    self.feedback = "{:3.0f}% of right answers".format(score * 100)


Efficient Django model for blog post I'm currently trying to create a travel blog using Django whereby users will be able to create a travel plan with the following features:

Each user can create a travel event based on the start date and end date for specific locations, with some meaningful description
He/She can also upload images for associated with specific travel event
A travel plan can consists of multiple travel events of various date

Will the following model be an efficient design?

    from django.db import models
    import datetime

    from __future__ import unicode_literals
    from django.core.urlresolvers import reverse
    from django.core.exceptions import ValidationError
    from django.utils import timezone
    from django.utils.translation import ugettext_lazy as _
    from django.conf import settings
    from django.utils.encoding import python_2_unicode_compatible

    # Create your models here.

    auth_user_model = getattr(settings, "AUTH_USER_MODEL", "auth.User")

    class Entry(models.Model):
        title = models.CharField(max_length=100)
        start_date = models.DateTimeField(_("start date"))
        end_date = models.DateTimeField(_("end date"))
        description = models.TextField(_("description"))
        accomodation = models.TextField(_("accomodation"))
        location = models.TextField(_("location"))
        images = models.ManyToManyField("Image", verbose_name=_("images"), blank=True, null=True)
        post_entry = models.ForeignKey(Post_Entry)

    class Post_Entry(models.Model):
        author = models.ForeignKey(User)
        created_by = models.ForeignKey(auth_user_model, verbose_name=_("created by"))
        categories = models.ManyToManyField("Category", verbose_name=_("categories"), blank=True)
        created_on = models.DateTimeField(auto_now_add = True)
        remarks = models.TextField(_("Remarks"))

    @python_2_unicode_compatible
    class Image(models.Model):
        title = models.CharField(max_length=60, blank=True, null=True)
        image = models.FileField(upload_to="images/")
        width = models.IntegerField(blank=True, null=True)
        height = models.IntegerField(blank=True, null=True)

        def __str__(self):
            return self.image.name

    @python_2_unicode_compatible
    class Category(models.Model):
        title = models.CharField(_('title'), max_length=255)

        def __str__(self):
            return self.title

        class Meta:
            verbose_name_plural = 'Categories'

Before thinking about making it efficient, I would worry more about making it clear, natural, intuitive. In your description you mention the notions "travel plan" and "travel event", and it's not easy to find the correspondence in the code. It would be easier to understand the overall design if the connection was more clear, for example if you had classes like TravelPlan and TravelEvent.

There are some other minor problems too with the code.

Drop this comment:

# Create your models here.

(I know it's automatically generated by Django, you're supposed to delete it after you created some models, which you already did.)

These imports are unused, so it's better to delete them:

import datetime

from django.core.urlresolvers import reverse
from django.core.exceptions import ValidationError
from django.utils import timezone

According to PEP8, you should put 2 blank lines before each class definition.

Also, classes in Python should be named CamelCase without underscores,
which is violated by Post_Entry.

It's good to declare closely related fields next to one another.
For example here:

    created_by = models.ForeignKey(auth_user_model, verbose_name=_("created by"))
    categories = models.ManyToManyField("Category", verbose_name=_("categories"), blank=True)
    created_on = models.DateTimeField(auto_now_add = True)

It would be better to move categories out from between created_by and created_on.


Up, up and away in a Retro Rocket I have seen the Writings on the wall...

Retro Rocket ASCII Art
Nested for-loop art
Print the Retro Rocket
Maybe a golfed C# answer from me

But I took this relatively serious and created a VerticalRocket class that I would like reviewed, kind of like a little "am I getting better at writing code" project/review experience (granted this was done while waiting for code to compile and queries to run).

What can I learn from this experience?

class VerticalRocket
{
    private int _FuselageSections = 2;
    public int FuselageSections
    {
        get
        {
            return _FuselageSections;
        }
        set
        {
            if (value <= 100 && value > 0)
            {
                _FuselageSections = value;
            }
        }
    }

    public List<string> rocketPartsList = new List<string>();

    private string Divider = "+=*=*=*=*=*=*+";

    private List<string> upDesigns = new List<string>
    {
          @"|../\..../\..|"
        , @"|./\/\../\/\.|"
        , @"|/\/\/\/\/\/\|"
    };

    private List<string> downDesigns = new List<string>
    {
          @"|\/\/\/\/\/\/|"
        , @"|.\/\/..\/\/.|"
        , @"|..\/....\/..|"
    };
    private List<string> NoseParts = new List<string>
    {
          @"      /\"
        , @"     /**\"
        , @"    //**\\"
        , @"   ///**\\\"
        , @"  ////**\\\\"
        , @" /////**\\\\\"
    };

    private List<string> BoosterParts = new List<string>
    {
          @"    //**\\"
        , @"   ///**\\\"
        , @"  ////**\\\\"
        , @" /////**\\\\\"
    };
    /// <summary>
    /// Creates a Generic Rocket with 2 Fuselage Sections.
    /// </summary>
    public VerticalRocket()
    {
        rocket(FuselageSections);
    }
    /// <summary>
    /// creates a rocket with specified number of Fuselage sections
    /// </summary>
    /// <param name="sections">Number of Fuselage Sections Desired</param>
    public VerticalRocket(int sections)
    {
        FuselageSections = sections;
        rocket(FuselageSections);
    }

    public List<string> Fuselage(bool diamondShape)
    {
        List<string> fuselage = new List<string>();

        if (diamondShape)
        {
            foreach (string line in upDesigns)
            {
                fuselage.Add(line);
            }
            foreach (string line in downDesigns)
            {
                fuselage.Add(line);
            }
        }
        else
        {
            foreach (string line in downDesigns)
            {
                fuselage.Add(line);
            }
            foreach (string line in upDesigns)
            {
                fuselage.Add(line);
            }
        }
        return fuselage;
    }

    public List<string> Nose()
    {
        List<string> nose = new List<string>();
        foreach (string line in NoseParts)
        {
            nose.Add(line);
        }
        return nose;
    }

    public List<string> Booster()
    {
        List<string> booster = new List<string>();
        foreach (string line in BoosterParts)
        {
            booster.Add(line);
        }
        return booster;
    }

    public void rocket(int sections)
    {
        bool wantDiamond = sections % 2 == 0 ? true : false; //this will keep the X at the bottom

        rocketPartsList.AddRange(Nose());
        rocketPartsList.Add(Divider);
        for (int i = 0; i < sections; i++)
        {
            rocketPartsList.AddRange(Fuselage(wantDiamond));
            wantDiamond = !wantDiamond;
            rocketPartsList.Add(Divider);
        }
        rocketPartsList.AddRange(Booster());
    }

    public override string ToString()
    {
        string output = "";
        foreach (string line in rocketPartsList)
        {
            output += line + Environment.NewLine;
        }
        return output;
    }

}

Note

Up-To-Date code can be found on my Github Repo

I don't like that the FuselageSections silently discards out of
bounds values, throwing an exception would be better.
Maybe there are shorter ways, but Fuselage can use AddRange as
well:

if (diamondShape)
{
    fuselage.AddRange(upDesigns);
    fuselage.AddRange(downDesigns);
}
else
{
    fuselage.AddRange(downDesigns);
    fuselage.AddRange(upDesigns);
}

wantDiamond can just be

bool wantDiamond = sections % 2 == 0;

and that (foo ? true : false or the reverse) is something I'll
always fix if I see it somewhere.
ToString can just be

return String.Join(Environment.NewLine, rocketPartsList);

instead.
Nose, Booster can all just create a copy with the List
constructor, i.e.

return new List<string>(BoosterParts);

and so on.

Otherwise looks fine; if it was actually part of a larger program I'd
move the parts itself into classes and have them output (ToString)
themselves instead.


HackerRank - Non-Divisible Subset In this problem we are asked:

Given a set, S, of n distinct integers, print the size of a maximal
subset, S', of  where the sum of any two numbers in it is not evenly
divisible by k.

Code
My idea is that the only relevant part are the remainders with respect to k. Additionally, for each number there is only one number that can sum up to k. So the problem can be reduced to counting the number of numbers with the same remainder and comparing to the count of its complement, and accumulating the one with the maximum value. The following picture explains the idea, for the following remainders and a value of k = 5, we need to count +1 for the 0, and then add the maximum between each pair to get the total size of the maximum set.

Also, the numbers whose remainder is 0 and the number which is the double of k can only be included once in the set.
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int non_divisible_subset_size(int k, std::vector<int> &v) {
    if (v.begin() == v.end()) return 0;
    // Checking the remainder allows to group different numbers which have the same influence
    std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});
    std::sort(v.begin(),v.end());
    int max_count{0};
    // Only one of the elements with remainder 0 can be added
    if (*v.begin()== 0) ++max_count;
    // Each element has only one complement that can sum up to k
    // The complement of a number betwen 0 to k/2 is located from k/2 to k-1
    // Therefore we only need to loop from (0 to k/2]
    for(auto it_lower=std::upper_bound(v.begin(),v.end(),0);
        *it_lower <= k/2;
        it_lower=std::upper_bound(v.begin(),v.end(),*it_lower))
    {
       auto it_upper = std::upper_bound(v.begin(),v.end(),*it_lower);
       int count;
       if (*it_lower*2 == k) {
           count = 1;
       }
       else {
           count = it_upper-it_lower;
       }
       int complement = k-*it_lower;
       auto it_lower_comp = std::lower_bound(v.begin(),v.end(),complement);
       auto it_upper_comp = std::upper_bound(v.begin(),v.end(),complement);
       int count_comp = count;
       if (*it_lower_comp == complement) {
           if (complement*2 == k) {
               count_comp = 1;
           }
           else {
               count_comp = it_upper_comp - it_lower_comp;
           }
       }
       max_count += std::max(count,count_comp);
    }
    return max_count;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    while(n--) {
        int x; std::cin >> x;
        v.push_back(x);
    }

    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
    return 0;
}

Questions
The code works and I get the correct results, but it seems to be too slow to past the tests of the challenge, I'm not sure how could I optimize the speed or what is making my code so slow. I guess the slowest part is computing the remainders, maybe is not a good idea, I'm not sure. Any proposal or comment?

I'm not sure about what makes your code slow, but first I should point out some ways to improve its readability. Actually, it should help you to think about your code complexity to make it more readable, since performance in complex nested loops and such things is really difficult to evaluate.

To begin with a detail, I believe that:

std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});

isn't the most readable. When you iterate over the whole container, the "range-based" for is better:

for (auto& x : v) x %= k;

unless you want to make your intent yet more apparent with the transform algorithm:

std::transform(vec.begin(), vec.end(), vec.begin(), [k](auto&& i) {return i%k;});

More importantly, I think you should dissociate traversal and counting, because it makes for a code very difficult to read. Why don't you make it in two steps:

// first step: counting modulo populations
std::map<int, int> counter;
for (auto elem: v) ++counter[v%k];

// second step: traversing different modulos
auto no_duplicates = std::unique(vec.begin(), vec.end());
std::for_each(vec.begin, no_duplicates, [](auto etc) { do_something(etc); });

A last point, you can put the two special cases out of the way early, instead of dragging them along until the end. So deal with multiples of k and k/2 at the first occasion, it also allows you to get rid of a certain number of elements.

To sum it up, here's my suggestion:

int nonDivisibleSubset(int k, std::vector<int> vec) {
    // 1. check for multiples of k, multiples of half of k, and retain only one of each
    int res = 0;
    auto multiples = std::remove_if(vec.begin(), vec.end(), [k](auto&& i) { return i%k == 0; });
    if (multiples != vec.end()) ++res;
    auto half_multiples = std::remove_if(vec.begin(), multiples, [k](auto&& i) { return 2*(i%k) == k; });
    if (half_multiples != multiples) ++res;
    // 2. for each possible modulo-complementary couple, choose the one with the most occurrences
    std::transform(vec.begin(), half_multiples, vec.begin(), [k](auto&& i) {return i%k;}); // calculate modulos
    std::sort(vec.begin(), half_multiples);
    std::map<int, int> mods; // count their occurrences
    std::for_each(vec.begin(), half_multiples, [&mods](auto&& i) {++mods[i];});
    // and then examine each possible couple
    auto uniques = std::unique(vec.begin(), half_multiples);
    auto bottom_up = vec.begin();
    auto top_down = std::reverse_iterator<std::vector<int>::iterator>(uniques);
    while (bottom_up < top_down.base()) {
        if (*bottom_up + *top_down == k) { // complementary
            res += std::max(mods[*bottom_up], mods[*top_down]);
            ++bottom_up, ++top_down;
        }
        // if not complementary advance the closest from its origin
        else if (*bottom_up < k - *top_down ) {
            res += mods[*bottom_up++];
        }
        else res += mods[*top_down++];
    }
    return res;
}

P.S: I've tried to submit that code and it passes correctly.


String tokenizer design I need some tips on how I can improve the design of the following code. Everything works correctly in the program. It takes a string and shows each token, the only tokens being numbers and operators. The output shows all the tokens and what type of token they are.

public class Tokenizer {
    int pos;
    char[] expression;

    Tokenizer(String expression) {
        this.expression = expression.toCharArray();
        this.pos = 0;
    }

    enum Type { OPERATOR, NUMBER, UNKNOWN }

    class Lexeme {
        String type, token;
        Lexeme(String type, String token) {
            this.type = type;
            this.token = token;
        }
    }

    Lexeme getToken() {
        StringBuilder token = new StringBuilder();
        boolean endOfToken = false;
        Type type = Type.UNKNOWN;
        while (!endOfToken && hasMoreToken())
        {
            while(expression[pos] == ' ')
                pos++;
            switch (expression[pos])
            {
                case '+':
                case '-':
                case '*':
                case '/':
                    if(type != Type.NUMBER)
                    {
                        type = Type.OPERATOR;
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true;
                    break;
                case ' ':
                    endOfToken = true;
                    pos++;
                    break;
                default:
                    if(Character.isDigit(expression[pos]) || expression[pos] == '.')
                    {
                        token.append(expression[pos]);
                        type = Type.NUMBER;
                    }
                    else
                    {
                        System.out.println("Systax error at position: " + pos);
                    }
                    pos++;
                    break;
            }
        }
        return new Lexeme(type.name().toLowerCase(), token.toString());
    }

    boolean hasMoreToken() {
        return pos < expression.length;
    }

    public static void main(String[] args) {
        // TODO code application logic here
        String expression = "12.3 / 5 - 22";
        Tokenizer tokenizer = new Tokenizer(expression);
        while (tokenizer.hasMoreToken())
        {
            Lexeme nextToken = tokenizer.getToken();
            System.out.print("Type: " + nextToken.type + "\tLexeme: " + nextToken.token + "\n");
        }
    }
}

This code looks quite nice, actually. If this was a homework assignment, you could almost turn it in right now. I only have some minor issues with the code, plus some bugs, and would then like to talk about alternatives to structure your lexer (the words tokenizer, lexer and scanner are all equivalent here).

I don't see a single comment in your code, aside from that TODO.
hasMoreToken should be hasMoreTokens. Notice the plural-“s”. This makes reading the code more pleasant.
Each lexeme should have a Type type, not a String type. By using a string, you loose all type safety. (Apparently there is a name for this antipattern: Stringly Typed).
You should probably use toString() instead of name(). This should not happen before the type is actually printed out, i.e. only in the main.
A seasoned Java programmer will use a lot more visibility modifiers. Especially pos and expression ought to be private. but I personally don't care.
You have inconsistent formatting. You put the opening braces of class and method declarations on the same line, but you put them under the keyword for control flow statements. In Java, the braces usually open on the same line.
It looks as if your switch was outdented one level. This happens because you didn't use a block for the preceding while. Always using blocks can make code easier to read.
General style note: Place blank lines between logically seperate blocks of your code. Inside the Lexeme class, a blank line between the fields and the methods could improve readability.
This piece of code:

while(expression[pos] == ' ')
        pos++;

will attempt to access an array entry outside of the allowed range when the strings ends with whitespace. Add a bounds check here.

On an architecture level, it would be nice to make your Tokenizer an Iterable. Heck, it implicitly already is a kind of Iterator. If we clean that up, we can do:

for (Token token : new Tokenizer(expression)) {
  System.out.println(...);
}

We can turn it into an Iterator by renaming hasMoreTokens to hasNext and getToken to next. If you can't rename them, a wrapper method will do as well. We also need a dummy method remove that throws an UnsupportedOpertationException. If we want to make it Iterable, we need to add an iterator method that returns the object itself, although this may be considered hackish.

The State Machine, and Why I Don't Like It

In your getToken method, you have written a kind of state machine that performs the parsing. You have seemingly flattened it into a single state with one character lookahead, but it actually has three (plus two) different states. Here are all transitions you have written:

# transitions that consume a char are written A -- char -> B
# lookahead transitions           are written A --(char)-> B

START --(not ' ')-> UNKNOWN
START --     ' ' -> START

# the operator cases
UNKNOWN -- '+'|'-'|'*'|'/' -> OPERATOR END
NUMBER  --('+'|'-'|'*'|'/')-> END

# the whitespace case
UNKNOWN  -- ' ' -> END # unreachable
OPERATOR -- ' ' -> END # unreachable
NUMBER   -- ' ' -> END

# the default digit case
UNKNOWN  -- '0'..'9'|'.' -> NUMBER
NUMBER   -- '0'..'9'|'.' -> NUMBER
OPERATOR -- '0'..'9'|'.' -> NUMBER # unreachable

# the default error case
UNKNOWN  -- not '0'..'9'|'.' -> UNKNOWN
NUMBER   -- not '0'..'9'|'.' -> NUMBER
OPERATOR -- not '0'..'9'|'.' -> OPERATOR # unreachable

There might be a few issues with this.

You can't output good error messages, because you don't have that good of an idea where you are, and because you skip over any junk in the string, allowing for 12foobar3 to be recognized as 123. Any extensions to the lexer would therefore be backwards-incompatible.
Extending this kind of lexer is difficult with increasing number of different token types, because all possible transitions have to be considered for that type, as all transitions happen in that one switch.
It obscures the actual flow of control.
You would consider ... to be a number.
I don't feel comfortable with consuming the char in the whitespace case. It is logically separate from tokenizing a number, and therefore should be separated in your code.
The existence of an UNKNOWN type is ridiculous. This is a case where having a null type might be preferable, and complaining if it is still null at the end of the method.

It might be better to make your states more explicit as actual states in your code. Also note that single-character lookahead is sufficient for your grammar, but would have difficulties recognizing operators like <=.

Another thing worth considering would be to put the body of your while(hasMoreTokens()) loop into a seperate method – this would remove the need for the endOfToken flag, as you could simply return. First, optimize for simplicity and readability, only second for performance.

Together, I might write code like this (untested sketch, no final code):

...

boolean illegalState = false;

public boolean hasNext() {
  return pos < expression.length && !illegalState;
}

public Lexeme next() {
  if (!hasNext()) {
    throw new NoSuchElementException();
  }

  // this can be removed if we do it in the constructor,
  // as we remove all WS *after* each token.
  skipWhitespace();

  // dispatch actual tokenization based on single character lookahead
  Lexeme lexeme;
  char c = expression[pos];
  if (c == '+' || c == '-' || c == '*' || c == '/') {
      pos++;
      lexeme = new Lexeme(Type.OPERATOR, Character.toString(c));
  } else if ('0' <= c && c <= '9') {
      lexeme = tokenizeNumber();
  } else {
      illegalState = true;
      throw new java.text.ParseException("Expected operator or number", pos);
  }

  // clean up after ourselves, so that hasNext() doesn't recognize
  // trailing whitespace as another token:
  skipWhitespace();

  return lexeme;
}

private void skipWhitespace() {
  while(pos < expression.length && expression[pos] == ' ') {
    pos++;
  }
}

private Lexeme tokenizeNumber() {
  StringBuilder token = new StringBuilder();

  // effectively, this method recognizes the language specified by the regex
  // /[0-9]+(?:\.[0-9]+)?/
  // (PCRE style)

  // lex the integer part
  int posBeforeInt = pos;
  while (pos < expression.length && '0' <= expression[pos] && expression[pos ] <= '9') {
    token.append(expression[pos++]);
  }
  if (pos == posBeforeInt) {
    illegalState = true;
    throw new java.text.ParseException("Every number must have an integer part", pos);
  }

  // optional: lex decimal
  if (expression[pos] == '.') {
    token.append(expression[pos++]);

    int posBeforeDecimal = pos;
    while (pos < expression.length && '0' <= expression[pos] && expression[pos ] <= '9') {
      token.append(expression[pos++]);
    }
    if (pos == posBeforeDecimal) {
      illegalState = true;
      throw new java.text.ParseException("Number has decimal point, but no decimal digits", pos);
    }
  }

  return new Lexeme(Type.NUMBER, token.toString());
}

You may have noticed that this lexer is much more similar to a top-down parser now, which I find easier to reason about. There is no difference between a lexer and parser, both transform a list of X to Y by giving them structure. (Lexer: chars → tokens, Parser: tokens → parse tree).

An abstraction possibility that opens up is the concept of a character class – a Set of characters with common properties. E.g. '0' <= expression[pos] && expression[pos ] <= '9' ought to be written as digits.contains(expression[pos]). Also, there are dozens more whitespace characters than just the \x20 space character.


Graph implementation in c++ using adjacency matrix Here is my code for implementing Graph using adjacency matrix. The code should be Object-oriented and there is a method isPath() checking if there is a connection between two nodes. Some advice?

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

class Graph
{
protected:
    int value;
    int **graphm;

public:
    Graph(int value)
    {
        this->value = value;
        graphm = new int*[value];
        int k, j;
        for (k = 0; k < value; k++)
        {
            graphm[k] = new int[value];
            for (j = 0; j < value; j++)
            {
                graphm[k][j] = 0;
            }
        }
    }

    void newEdge(int head, int end)
    {
        if (head > value || end > value || head < 0 || end < 0)
        {
            cout << "Invalid edge!\n";
        }
        else
        {
            graphm[head - 1][end - 1] = 1;
            graphm[end - 1][head - 1] = 1;
        }
    }

    void display()
    {
        int i, p;

        for (i = 0; i < value; i++)
        {
            for (p = 0; p < value; p++)
            {
                cout << graphm[i][p] << "   ";
            }
            cout << endl;
        }
    }

    void isPath(int head, int end)
    {
        int k, o;
        ofstream fullstore("Test.txt");

        cout << graphm[head - 1][end - 1];
        cout << endl;
        if (!fullstore.is_open())
        {
            cout << "File can't be open";
        }

        if (graphm[head - 1][end - 1] == 1)
        {
            cout << "There is an edge between " << head << " and " << end << "\n";
            fullstore << head << ", " << end;
            fullstore.close();
        }
        else
        {
            cout << "Edge not found\n";
        }
    }
};

int main()
{
    int vertex, numberOfEdges, i, head, end;
    cout << "Enter number of nodes: ";
    cin >> vertex;
    numberOfEdges = vertex * (vertex - 1);
    Graph g1(vertex);
    for (int i = 0; i < numberOfEdges; i++)
    {
        cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> head >> end;
        if ((head == -1) && (end == -1))
        {
            break;
        }
        g1.newEdge(head, end);
    }
    g1.display();
    cout << endl;
    g1.isPath(1, 3);

    return 0;
}

Avoid using namespace std;.

Why are you using raw pointers?  Use smart pointers, or (better yet) standard containers like std::vector.  Since vector constructs its elements, much of your initialization code can be eliminated.

Make use of the member initializer list in your constructor.  There's no real difference with fundamental types like int, but with more complicated objects it can be a big help or outright necessity (to initialize a reference).

    Graph(int value): value(value) {

(That will initialize the member value with the parameter value.)  Then get rid of the this->value = value line.

Define variables as late as possible, with their first use if possible.  Make use of this in your for statements.

for (int k = 0; k < value; ++k)

In newEdge, your parameter validation accepts 0 as a valid edge index, but you then subtract one from it for the subscripting, resulting in Undefined Behavior and a possible crash.

display and isPath should be const (void display() const.  isPath does not validate its parameters like newEdge does.


Pythonish integer range in C++ Python has that range:

>>> range(10, -20, -3)
[10, 7, 4, 1, -2, -5, -8, -11, -14, -17]

I have this C++ implementation of exactly the same facility:

range.h:

/*
 * File:    range.h
 * Author:  Rodion "rodde" Efremov
 * Version: (Nov 30, 2015)
 */

#ifndef RANGE_H
#define RANGE_H
#include <stdexcept>

namespace coderodde {

    template<typename Int = int>
    class range {
    private:
        Int m_start;
        Int m_end;
        Int m_step;

        class range_iterator {
        private:
            Int    m_value;
            Int    m_step;
            size_t m_count;

        public:
            range_iterator(Int value,
                           Int step,
                           size_t count) : m_value{value},
                                           m_step{step},
                                           m_count{count} {}

            int  operator*() { return m_value; }
            bool operator!=(range_iterator& other) { return m_count != other.m_count; }
            void operator++() { m_value += m_step; ++m_count; }
        };

    public:
        range(Int start, Int end, Int step) : m_start{start},
                                              m_end{end},
                                              m_step{step} {}

        range(Int start, Int end) : range(start, end, 1) {}

        range_iterator begin() { return range_iterator(m_start, m_step, 0); }

        range_iterator end() {
            if (m_step == 0) throw std::runtime_error("The step is zero.");

            if (m_start <= m_end)
            {
                if (m_step < 0)
                {
                    return range_iterator(0, 0, 0);
                }

                return range_iterator(m_start, m_step,
                                     (m_end - m_start) / m_step +
                                   (((m_end - m_start) % m_step) ? 1 : 0));
            }
            else
            {
                if (m_step > 0)
                {
                    return range_iterator(0, 0, 0);
                }

                m_step = -m_step;
                return range_iterator(m_start, m_step,
                                     (m_start - m_end) / m_step +
                                   (((m_start - m_end) % m_step) ? 1 : 0));
            }
        }
    };
}

#endif  /* RANGE_H */

With demo main.cpp:

#include <iostream>
#include "range.h"

using std::cin;
using std::cout;
using std::endl;
using coderodde::range;

int main(int argc, char* argv[])
{
    while (true)
    {
        int start = 0;
        int end   = 0;
        int step  = 0;

        cout << ">> ";

        if (not (cin >> start >> end >> step))
        {
            break;
        }

        try
        {
            for (auto i : range<>(start, end, step))
            {
                cout << i << endl;
            }
        }
        catch (std::runtime_error& err)
        {
            cout << "Error: " << err.what() << endl;
        }
    }

    cout << "Bye!" << endl;
}

I tried hard to make my range act exactly the same way is in Python (2.7). For instance, if step is 0, an exception is thrown.

I do not have much experience in C++, so any critique is much appreciated.

Keeping a Count

You implemented range_iterator to keep a count which you use for equality comparisons. This works, but involves a really awkward formula for getting the count right. Instead, it would be simpler to just round end to be one past the last one, so that range(0, 11, 2) sets start to 0 and end to 12. This would make range_iterator only require two members, and operator!= to just compare the m_value's.

Wrong Type

range_iterator dereferences to int, but should be Int.

Usage

This is awkward:

for (auto i : range<>(start, end, step))
//                 ^^^

Rather than having it be up to the user to provide the correct type, you could instead take advantage of template deduction:

template <typename Int>
Range<Int> range(Int start, Int end, Int step) { ... }

You'll have to rename your class template to get this to work. Even better would be to make the function a friend of the class, and make the constructors private.

Keep begin() and end() simple

Once we rewrite range() to be a function template that returns an object, you can move all of the logical checking into it:

template <typename Int>
Range<Int> range(Int start, Int end, Int step) {
    if (step == 0) throw ...;

    if (start <= end) {
       if (step < 0) {
           return {0,0,0};
       }
       return {start, (end + step - 1) / step * step};
    }
    else {
       // etc.
    }
}

This means that begin() just returns range_iterator{m_start, m_step} and end() just returns range_iterator{m_end, m_step}.

Other Overloads

Python also allows for something like range(10), so that's just:

template <class Int>
Range<Int> range(Int end) {
    return {0, end, 1};
}

Iterator Interface

Even though it won't be fully utilized in the simple example of for (auto i : range(10)), you should prefer to provide a complete interface for range_iterator. You're missing operator== and postfix-increment. Prefix-increment (and postfix-increment) should return references to this.

Additionally, you should inherit from std::iterator<std::forward_iterator_tag, int, std::ptrdiff_t, int, int> just in case somebody wants to use range() as a normal container somewhere else.

For example, it'd be nice to support the following:

auto r = range(10);
std::vector<int> v(r.begin(), r.end());

which currently will fail to compile.


Calculate the difference between the elements in a list So I have two lists which have the same size. One is called roadS and the second one is called simTime. My aim is to calculate the difference between two indexes which lie next to each other and divide them with the difference of the other list. On the picture above you see what I mean.

This is my current function:

public List<Double> getSpeedS(List<Double> simTime, List<Double> roadS){
    List<Double>  speedS = new ArrayList<>();
    for(int idx = 1; idx < roadS.size();idx++){
        double curSpeedS = (roadS.get(idx)-roadS.get(idx-1))/(simTime.get(idx)-simTime.get(idx-1));
        speedS.add(curSpeedS);
    }
    return speedS;
}

Now although the function is quite short, I aim to find a better or faster solution.

For eg. in phyton you could you pantas library and do this:

player.df['speedS'] = player.df.roadS.diff().shift(-1) / player.df.simTime.diff().shift(-1)

My aim is to solve this problem more efficient. Does Java or another library maybe provide such functions where I can for calculate the differences

Your implementation is good and easy to understand.

When using List<Double> for input data, be sure to use an efficient implementation. Otherwise you could get really bad read performance. E.g., when you access elements by index, ArrayList<Double> will be much faster than LinkedList<Double> (\$O(n)\$ vs. \$O(n^2)\$ for your getSpeedS).

If you must support arbitrary types of List<Double> you would probably better off when you use Iterators instead of element access by index.

If you use an ArrayList and know its final size in advance, always construct it with the capacity needed (new ArrayList<>(size)). This avoids reallocation and copying of the internal array that holds the elements while adding elements.

If you need maximum performance, then use arrays (double[]) instead of lists. For large data sets they can speed up the creation of the input in-memory objects by factors greater than two. Additionally they may give you a significant advantage in read performance due to better utilization of processor caches compared to list implementations.


Integer to Alphabet string ("A", "B", ...."Z", "AA", "AB"...) So this question is prompted by two things.

I found some code in our source control doing this sort of things.
These SO questions:

https://stackoverflow.com/questions/297213/translate-an-index-into-an-excel-column-name
https://stackoverflow.com/questions/837155/fastest-function-to-generate-excel-column-letters-in-c-sharp
https://stackoverflow.com/questions/4075656/how-to-get-continuous-characters-in-c/4077835#4077835
https://stackoverflow.com/questions/1011732/iterating-through-the-alphabet-c-sharp-a-caz

So when I thought about this problem this popped into my head almost immediately.

class Util
{
    private static string[] alphabetArray = { string.Empty, "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
    public static IEnumerable<string> alphaList = alphabetArray.Cast<string>();

    public static string IntToAA(int value)
    {
        while (Util.alphaList.Count() -1 < value)
        {
            Util.IncreaseList();
        }

        return Util.alphaList.ElementAt(value);
    }

    private static void IncreaseList()
    {
        Util.alphaList = Util.alphabetArray.Take(1).Union(
            Util.alphaList.SelectMany(currentLetter =>
               Util.alphabetArray.Skip(1).Select(innerLetter => currentLetter + innerLetter)
            )
        );
    }
}

My question is this: Is this approach a better solution (performance wise)?
 or is a recursive / computed value better (eg. this answer )?

Math! Simple math is certainly the nicest way, no lists to deal with, just old fashion ASCII and math. If you want to be able to toggle the capitalization of this method, simply use a ternary operator like this isCapital ? 'A' : 'a' I just left it capital as that is how the OP seemed to want it. Jeff Mercado's Answer explained well enough the differences between calculated, recursive and such... I mostly wanted to provide a simplistic calculated answer that did not involve using lists.

public static string IntToLetters(int value)
{
    string result = string.Empty;
    while (--value >= 0)
    {
        result = (char)('A' + value % 26 ) + result;
        value /= 26;
    }
    return result;
}

Edit: To meet the requirement of A being 1 instead of 0, I've added -- to the while loop condition, and removed the value-- from the end of the loop, if anyone wants this to be 0 for their own purposes, you can reverse the changes, or simply add value++; at the beginning of the entire method.


Optimize RecvData wrapper How can I improve the string RecvData() function?

std::string Socket::RecvData() {
    std::string strBuffer;
    do{
        char buffer;
        int recvInt = recv(s_, &buffer, 1, 0);
        if (recvInt == INVALID_SOCKET)
        {
            return "";
        }
        if (recvInt == SOCKET_ERROR)
        {
            if (errno == EAGAIN) {
                return strBuffer;
            }
            else {
                // not connected anymore
                return "";
            }
        }

        strBuffer += buffer;
        if (buffer == '\n')  return strBuffer;
    } while (true);
}

recv() is a system call, which has relatively high overhead.  You should avoid calling recv() just to read one byte at a time.  Instead, read a reasonable sized buffer (something like the size of an IP packet).  Your wrapper object should maintain a buffer of bytes that have been returned by a previous call to recv() but that have not yet been returned to the caller (bytes after a newline character).

In implementing such a buffered interface, you would be forced to use the return value of recv() correctly.  recv() returns the number of bytes read, or -1 if an error occurred.  The error code is stored in the errno global variable, not the return value of recv().


Recursive merge sort in python I'm very new to python, however not new to programming as I've been doing C for some time.

So here is my practice of a merge sort, I looked at other questions however they were many more lines compared to mine. Which leaves me to believe I'm doing something wrong.

I come here to look for best practices in python, and I mean the best of the best. I want to know all the little details! Most importantly if there is anyway to shorten code without sacrificing efficiency.

#!/usr/bin/python

def merge_sort(array):
    ret = []
    if( len(array) == 1):
        return array;
    half  = len(array) / 2
    lower = merge_sort(array[:half])
    upper = merge_sort(array[half:])
    lower_len = len(lower)
    upper_len = len(upper)
    i = 0
    j = 0
    while i != lower_len or j != upper_len:
        if( i != lower_len and (j == upper_len or lower[i] < upper[j])):
            ret.append(lower[i])
            i += 1
        else:
            ret.append(upper[j])
            j += 1

    return ret

array = [4, 2, 3, 8, 8, 43, 6,1, 0]
ar = merge_sort(array)
print " ".join(str(x) for x in ar)
#>>> 0 1 2 3 4 6 8 8 43

Thanks CR.

First of all, there is a bug in the code - if an array is empty, you'll get a "maximum recursion depth exceeded" error. Improve your base case handling:

if len(array) <= 1:
    return array

Other improvements:

the merging logic can be simplified - loop while where are elements in both arrays and append what is left after the loop
extract the merging logic into a separate merge() function
improve the variable naming - e.g. use left_index and right_index as opposed to i and j, result instead of ret
no need to enclose if conditions into outer parenthesis
Python 3 compatibility:

use print() as a function instead of a statement
use // for the floor division

Improved version:

def merge(left, right):
    """Merge sort merging function."""

    left_index, right_index = 0, 0
    result = []
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    result += left[left_index:]
    result += right[right_index:]
    return result

def merge_sort(array):
    """Merge sort algorithm implementation."""

    if len(array) <= 1:  # base case
        return array

    # divide array in half and merge sort recursively
    half = len(array) // 2
    left = merge_sort(array[:half])
    right = merge_sort(array[half:])

    return merge(left, right)


Regex for curly quotes and apostrophes After years of fear and procrastination I decided to learn regular expressions. This is the result:

CoffeScript:

str = "
#{chapter.title}
\n\n#{chapter.content}\n\n"

str.replace(/>([^>]+)</g, (r) ->
  r.replace(/(>|\s)"/g, "$1“")
   .replace(/"/g, "”")
   .replace(/("|\s)'/g, "$1‘")
   .replace(/'/g, "’")
)

JavaScript:

var str = "
" + chapter.title + "
\n\n" + chapter.content + "\n\n";

str.replace(/>([^>]+)</g, function(r) {
  return r.replace(/(>|\s)"/g, "$1“")
          .replace(/"/g, "”")
          .replace(/("|\s)'/g, "$1‘")
          .replace(/'/g, "’");
});

As you can see, the code turns all "straight" quotation characters (plus apostrophe) to “curly” ones. It was a bit hard because the input had stuff like this:

"Yes," he said, "I met her. She's very 'friendly.'"

So I had to make sure the quotes inside the HTML tags were not being included. And make the code know that quotations wouldn't always be preceded by a space (sometimes by an >).

I welcome any suggestion to make the code shorter, more efficient/readable.

Since you know that the double quotes will always be matched, you might try this instead of your first two replaces:

r.replace(/"([^"]*)"/g, "“$1”")

I think that's a little stronger.  The unmatched single quotes are harder, and I think what you have is reasonable.  I might try this tack though if JavaScript has the \w for word letters.  (If not, use [a-zA-Z].)

.replace(/(\w)'(\w)/g, "$1’$2")
.replace(/'([^']*)'/g, "‘$1’")


One Time Pad algorithm for encryption and decryption I have written my own one time pad algorithm for encryption and decryption, but I would like to listen to your opinions about its correctness and eventually how could I improve it. My idea was to keep it readable, but not so bad in terms of performance. I have also written some tests.

Here's the code:

from random import choice
import string

def convert_to_bits(s):
    """Converts string s to a string containing only 0s or 1s,
    representing the original string."""
    return "".join(format(ord(x), 'b') for x in s)

def gen_random_key(n):
    """Generates a random key of bits (with 0s or 1s) of length n"""
    k = []
    for i in range(n):
        k.append(choice(["0", "1"]))
    return "".join(k)

def xor(m, k):
    """Given strings m and k of characters 0 or 1,
    it returns the string representing the XOR
    between each character in the same position.
    This means that m and k should be of the same length.

    Use this function both for encrypting and decrypting!"""
    r = []
    for i, j in zip(m, k):
        r.append(str(int(i) ^ int(j)))  # xor between bits i and j
    return "".join(r)

if __name__ == "__main__":
    ls = []

    for i in range(100):
        for i in range(100):
            ls.append(choice(string.ascii_letters))

        s = "".join(ls)

        bits = convert_to_bits(s)
        key = gen_random_key(len(bits))
        cipher = xor(bits, key)
        original = xor(key, cipher)

        if original != bits:
            raise Exception("Something wrong with the implementation...")

I have a few suggestions regarding performance:

Choosing between 2 things n times is slow, especially when factoring in the fact that you are appending to an array n times.

I would take advantage of the random module's getrandbits method like so:

def gen_random_key(n):
"""Generates a random key of bits (with 0s or 1s) of length n"""
return bin(getrandbits(n))[2:].zfill(n)

A full explanation:

bin produces a binary string from an integer
getrandbits(n) produces an integer from n random bits
[2:] cuts out the '0b' that is put at the start of the string by bin
.zfill(n) pads the resulting string with 0's to force a length of n

With shorter strings you won't notice the performance difference but with a larger string the speed difference is immense.

I used timeit to get the following timings on my machine:

10000 bits, called 100 times:
1.12 seconds vs 0.003 seconds

100000 bits, called 100 times:
11.5 seconds vs 0.003 seconds

As you can see, my method is orders of magnitudes faster.

For xor, you can use a similar approach:

def xor(m, k):
"""Given strings m and k of characters 0 or 1,
it returns the string representing the XOR
between each character in the same position.
This means that m and k should be of the same length.

Use this function both for encrypting and decrypting!"""
a = int(m, base=2)
b = int(k, base=2)
return bin(a ^ b)[2:].zfill(len(m))

Now ignoring that, let's discuss your general approach.

You convert a string of characters into a string of 0's and 1's. This is actually wasteful, as you are multiplying your memory usage immensely. The reason is that most characters take many bits to store. Thus, you are replacing one character with many 0 or 1 characters. Assuming pure ASCII, you might be using up to 7x the memory, and it will be quite a bit worse with arbitrary Unicode characters.

There's also another issue. Once you have your ciphertext, there isn't really a good way to recover the original string. Sure you can get the original bits back, but how do you know which how many or which bits correspond to which letter? You could solve this with padding, but that is an ugly solution that wastes even more memory.

Instead I propose the following solution:

Generate a string of characters (ASCII is fine, doesn't really matter too much) as a key. The key should have the same number of characters as the string. Then xor the ord of the characters in the same spot and make a new character with the result (by using chr). Join all these characters to form the cipher text.

My version of this (without comments/tests) is this:

def gen_key(string):
    return "".join(choice(string.printable) for _ in s)

def encrypt(string, key):
    return "".join(chr(ord(i) ^ ord(j)) for (i, j) in zip(string, key))

def decrypt(ciphertext, key):
    return encrypt(ciphertext, key)


GIF/PPM to greyscale converter This is my take on an image → greyscale converter.

#greyscale.py -- Converts an image file to greyscale

from tkinter.filedialog import askopenfilename, asksaveasfilename
from graphics import *

def displayimage(imagefile):
    #Open image to get width and height
    image2convert = Image(Point(0, 0), imagefile)
    imgwidth = image2convert.getWidth()
    imgheight = image2convert.getHeight()

    #Set window size to image size and draw image to window
    win = GraphWin("Greyscale Converter", imgwidth, imgheight)
    image2convert.move(imgwidth/2, imgheight/2)
    image2convert.draw(win)

    return image2convert, win

def convert(image2convert, win):
    width = image2convert.getWidth()
    height = image2convert.getHeight()

    #For each row of pixels
    for pixelx in range(width):
        #For each column of pixels
        for pixely in range(height):
            print("Converted pixel: x:{0} y: {1}".format(pixelx, pixely))
            #Get Pixel Colour, calculate greyscale, set Pixel to calculated colour
            r, g, b = image2convert.getPixel(pixelx, pixely)
            brightness = int(round(0.299 * r + 0.587 * g + 0.114 * b))
            image2convert.setPixel(pixelx, pixely, color_rgb(brightness, brightness, brightness))
        #See progress for each row
        win.update()
    return image2convert

def main():
    imagefile = askopenfilename(filetypes=[("GIF-Image", ".gif"), ("PPM-Image", ".ppm")])

    image2convert, win = displayimage(imagefile)

    #convert after click
    win.getMouse()
    image2convert = convert(image2convert, win)

    #save new image
    outFile = asksaveasfilename(filetypes=[("GIF-Image", ".gif"), ("PPM-Image", ".ppm")])
    newImg = image2convert.save(outFile)

    #close file and window after click
    win.getMouse()
    image2convert.close()
    win.close()

main()

Opinions/Suggestions/Ideas? It is pretty slow, but I don't think that this approach can be much faster.

There are some very good things about this code.

It makes good use of library functionality, which is one of the big strengths of Python. A lot of programmers spend unnecessary amounts of time rewriting things that others have already done, so it's good to see the habit of just using things like askopenfilename as provided.

I also like the use of comments. There are two traps that people fall into with comments: one is not writing any, and the other is writing comments that just say what the code is already saying. A comment like "Update the window" before win.update() would be pointless, whereas your comment "See progress for each row" explains clearly and concisely what the intention behind that update is.

That said, I am slightly confused by two of your comments. It's almost midnight here and I may be misreading the code, but it looks to me as if the first for loop is going from left to right one column at a time, and the second for loop is going one row at a time. If so, those comments are the wrong way round. It's important to make sure that comments are kept up to date and accurate, or they can mislead the person reading the code (even if it's future you.)

You mention it running quite slowly. Now the general rule is that when something runs slowly, you use a tool called a profiler to work out which bits of the code are taking time. I haven't run one on this code, but in my experience that print line is probably taking a surprising amount of time. We always assume that text is easy for computers, which it kind of is, but if you think about it the computer has to set maybe a couple of thousand pixels to update that text for every one pixel that it's doing the greyscale calculation for. Although it's really useful to have such lines while developing something, it's usually worth taking them out once they have served their purpose.

Finally, I'll rattle through a few python best practices that are generally worth bearing in mind.

Your function displayimage does two jobs. It first loads an image from a file, and then creates a window and puts it on the screen. Now, you have made good use of python's multi-return functionality to let you do that cleanly, but usually best practice is that every function should do one thing and do it well. I would suggest cutting that function in half: one function could take a file name and return an image, and a second function should take an image and set up a window for it.
Python programmers usually prefer naming things with snake_case for variable names and function names, which means join lowercase words with underscores. That is purely a convention, but sticking to conventions helps to read code more fluently.
It is generally discouraged to use import *. That is because it is not clear what comes from where. If I want to look at the documentation for, say, Image then I don't know whether to look at the graphics documentation or somewhere else. Even worse, there's a whole bunch of stuff in packages that you're not using, and it can trip you up if you don't realise it's there. For example you could imagine that your graphics module could also have a function called asksaveasfilename. (Ok, probably not that one, but it serves for an example) Then when you call asksaveasfilename you get all sorts of confusion because it could call the wrong one. Even worse, if you update your packages then graphics which didn't have asksaveasfilename before might have it now, and the behaviour of your program changes in entirely unexpected ways.

I hope this is helpful.

Josiah


Simple Random Password Generator in Python I've made a password generator that works fine. It takes alphabetic, numeric, and punctuation characters and randomly generates a 8-16 character password.

import sys
import string
import random

def PasswordGenerator():
    Name = input("What is your name? ")
    if Name.isalpha():
        GeneratePassword = input(Name + " would you like to generate a random password? ")
        YesOptions = ["Yes", "yes", "Y", "y"]
        NoOptions = ["No", "no", "N", "n"]
        PasswordCharacters = string.ascii_letters + string.digits + string.punctuation
        while GeneratePassword in YesOptions:
            Password =  "".join(random.choice(PasswordCharacters) for i in range(random.randint(8, 16)))
            print(Password)
            GeneratePasswordAgain = input("Would you like to generate another random password? ")
            while GeneratePasswordAgain in YesOptions:
                Password =  "".join(random.choice(PasswordCharacters) for i in range(random.randint(8, 16)))
                print(Password)
                GeneratePasswordAgain = input("Would you like to generate another random password? ")
                break
            while GeneratePasswordAgain in NoOptions:
                print("Good bye!")
                sys.exit()
                break
            while GeneratePasswordAgain not in YesOptions or NoOptions:
                print("Not a valid response! Try again.")
                GeneratePasswordAgain = input("Would you like to generate another random password? ")
                break
        while GeneratePassword in NoOptions:
            print("Good bye!")
            sys.exit()
        while GeneratePassword not in YesOptions or NoOptions:
            print("Not a valid response! Try again.")
            PasswordGenerator()
            while GeneratePassword in YesOptions:
                Password =  "".join(random.choice(PasswordCharacters) for i in range(random.randint(8, 16)))
                print(Password)
                GeneratePasswordAgain = input("Would you like to generate another random password? ")
                while GeneratePasswordAgain in YesOptions:
                    Password =  "".join(random.choice(PasswordCharacters) for i in range(random.randint(8, 16)))
                    print(Password)
                    break
                    GeneratePasswordAgain = input("Would you like to generate another random password? ")
                while GeneratePasswordAgain in NoOptions:
                    print("Good bye!")
                    sys.exit()
                    break
                while GeneratePasswordAgain not in YesOptions or NoOptions:
                    print("Not a valid response! Try again.")
                    GeneratePasswordAgain = input("Would you like to generate another random password? ")
                    break
        while GeneratePassword in NoOptions:
            print("Good bye!")
            sys.exit()
    while Name is not Name.isalpha:
        print("Not a valid response! Try again.")
        PasswordGenerator()

PasswordGenerator()

I found a bug. If the initial response to "Do you want to..." is neither yes-like or no-like, it prompts for the username again. Also, you have large sections of dead code that will never execute.

Avoid duplicating code.

Several prompts are exactly the same as each other, even with the same logic after them. Refactor the code so that each possibility only occurs once.
Avoid duplicating variables

The GeneratePassword and GeneratePasswordAgain variables serve the same purpose: to get user input and determine if it should continue. and should be unified.
Keep the code reusable.

Avoid calls like sys.exit() that prevent this snippet of code from being used elsewhere.
Use the language features properly.

You know how to use while loops -- so why are you making multiple unnecessary recursive calls, each of which performs the same task as a while loop?
Separate logic and user-interface. Separate the code into modules.

Write the function that generates the password and does nothing else. Something like

 def RandomPassword(passwordCharacters, minLetters, maxLetters):
    return "".join(random.choice(PasswordCharacters) for i in range(random.randint(minLetters, maxLetters)))

 def DefaultRandomPassword():
     passwordCharacters = string.ascii_letters + string.digits + string.punctuation
     return RandomPassword(passwordCharacters, 8, 16)

Write another function that takes a prompt, displays it, waits for the user to type something, and then does it again if it was not a valid yes-no answer. Then return either yes or no. Call this function multiple times.


Asyncronous Function Calls I am writing a node.js inspired C++ library for asynchronous function calls.

How efficient and stable does my code look?

If you want, you can see some WIP code and demonstration code here.
(net.hpp is for POSIX sockets and is far from done. It does not have any IO functions written)

/* ASYNC.HPP
 * Defines some functions for calling other functions in the background
 * This gives the ability to create callback based functions easily,
 * similar to node.js (But I hate javascript so I wrote this library for c++)
 */

#ifndef ASYNC_H
#define ASYNC_H
#include <thread>
#include <vector>

std::vector<std::thread> asyncCalls; // Don't have to deal with threads leaving scope since this vector is global
#define asyncCall asyncCalls.emplace_back // Whenever someone calls asyncCall this constructs a new std::thread which calls their function

void finishAsync(){ //Call to block until all running asyncronous functions return
while(!asyncCalls.empty()){ //Loop until the vector is empty
        asyncCalls.back().join(); //Get the thread from the back and join it to block
                //^ I feel like this line might throw an exception, but in my testing it hasn't thrown anything.
        asyncCalls.pop_back(); //Pop it and get a new one
}
} // Infinite running threads will block forever

#ifdef _GLIBCXX_CHRONO //Include <chrono> before this header for this function

void sleep(uint32_t millis){ //I just realized while adding comments that I could do this with a define. Oh well
    std::this_thread::sleep_for(std::chrono::milliseconds(millis));
}

#endif // End chrono function

#endif //End header guard

std::vector<std::thread> asyncCalls;

This creates a global variable (so, you know, don't do that) — and it creates the global variable in every .cpp file that imports this header file. So unless you only have one .cpp file in your project, you're going to get linker errors when you try to link your project.

What you wanted to do was put this variable definition in a .cpp file and put a declaration of it (using extern) in your .hpp file.

Alternatively, as of C++17, you could have made it an inline variable:

inline std::vector<std::thread> asyncCalls;

However, global variables are terrible; don't do anything like this. Maybe what you want is some notion of "thread pool":

class ThreadPool {
    std::vector<std::thread> asyncCalls;
    // ...
};

#define asyncCall asyncCalls.emplace_back // Whenever someone calls asyncCall this constructs a new std::thread which calls their function

This is a preprocessor macro (so, you know, don't do that). What you meant was

class ThreadPool {
    std::vector<std::thread> asyncCalls;

public:
    template<typename... Args>
    void asyncCall(Args&&... args) {
        asyncCalls.emplace_back(std::forward<Args>(args)...);
    }
};

void finishAsync(){ //Call to block until all running asyncronous functions return
while(!asyncCalls.empty()){ //Loop until the vector is empty

Two things:

Please indent your code. Four-space indents would be nice.
Who do you expect to call this function? and how do you know that nobody else is going to be calling emplace_back at the same instant that that guy is calling empty? Looks like you have a huge thread-safety problem here.

#ifdef _GLIBCXX_CHRONO //Include <chrono> before this header for this function

Don't do this. For one thing, your code won't do the right thing on Clang with libc++ (or MSVC, or basically any non-libstdc++ distribution). What you meant was

#include <chrono>

This way, your header includes all the headers it depends on, recursively, and you never have to worry about whether your caller included something else before you or not.

As far as "would this code be a good idea if it worked": a resounding no. Your asyncCall function isn't really doing anything that std::async wouldn't do on its own; and std::async on its own is a bad idea because if you call it too many times you'll eventually run out of threads and start getting "Resource temporarily exhausted" errors. If you're going to be writing programs that use asynchrony as their primary implementation technique, the last thing you want to do is run out of threads. You need to figure out some way to queue up "tasks" without tying up a whole std::thread per (stalled) task.


Object array with identifier: use index to quickly access elements by id? I must access the elements of an object array very often by an identifier id, i.e.

[
{id:1, value:“test“, cat:2},
{id:2, value:“test“, cat:2},
{id:3, value:“test“, cat:2}, ...
]

To do so I use find, for example to fetch the value of object with id 3:

  SomeVal = myArray.find(x => x.id === 3).value

However, as I would never change the initial array after creation, and as the id of each item is well defined (I fetch the objects from my sql db), I was thinking to use the array index as identifier. I would use splice to create such array initially and I would start with id 1. I have around 5k objects.

This way I must not use find, but instead could access the array by the index directly:

 SomeVal = myArray[3].value

As my id starts with 1, the array would be of same size in the end.

I would think that’s an enormous performance boost, yet I have never seen anyone going such an approach when accessing elements by an identifier. What do you think?

Your implementation is basically a Map or Object that revolves around a very specific rule. That rule being the id directly correlates to the index in the array. The advantage an Array has over other data structures, with superior search speeds, is the fact that they are ordered. If order doesn't matter and you're purely using it to leverage search, Sets and Maps do a better job


Limit HTTP request rate for spray/akka-http I want to limit the request rate in a spray/akka-http route. I'm not an expert with both scala and spray/akka but learning. So I came up with the following custom directive:

  trait RequestRateLimiter[T] {
    def check(ctx: RequestContext, realIp: Option[RemoteAddress], proxiedIp: Option[RemoteAddress]) : RequestRateResult[T]
  }

  sealed trait RequestRateResult[T]
  case class Pass[T](result: T) extends RequestRateResult[T]
  case class Block[T](rejection: Rejection) extends RequestRateResult[T]

  def limit[T](requestRateLimiter: RequestRateLimiter[T]): Directive1[T] = {
    def remoteAddress: Directive1[Option[RemoteAddress]] = optionalHeaderValuePF { case `Remote-Address`(address) ⇒ address }
    def xForwardedFor: Directive1[Option[RemoteAddress]] = optionalHeaderValuePF { case `X-Forwarded-For`(Seq(address, _*)) ⇒ address }
    extract(identity) flatMap { ctx =>
      remoteAddress.flatMap { realIp =>
        xForwardedFor.flatMap { proxiedIp =>
          requestRateLimiter.check(ctx, realIp, proxiedIp) match {
            case Pass(result)     => provide(result)
            case Block(rejection) => reject(rejection)
          }
        }
      }
    }
  }

The custom directive takes an instance of an RequestRateLimiter which keeps track of the request rate based on the RequestContext and RemoteAddress. The RequestRateLimiter then decides if the request should be passed or blocked.
I'm not quiet happy with the RequestRateLimiter because it's too generic. It can be anything that either provides something or rejects.

I also posted a Gist (feel free to share, use and improve).

What do you think of the directive? Anything that could be improved?

I think you could rewrite your limit function like this :

def limit[T](requestRateLimiter: RequestRateLimiter[T]) = {
  def remoteAddress = optionalHeaderValuePF { case `Remote-Address`(address) ⇒ address }
  def xForwardedFor = optionalHeaderValuePF { case `X-Forwarded-For`(Seq(address, _*)) ⇒ address }

  for {
    ctx <- extract(identity)
    realIp <- remoteAddress
    proxiedIp <- xForwardedFor
  } yield requestRateLimiter.check(ctx, realIp, proxiedIp) match {
    case Pass(result) => provide(result)
    case Block(rejection) => reject(rejection)
  }
}

Here are the two main changes that I've done :

Changed your flatMaps for a "for comprehension" (which imho is more readable)
Removed the types on the declaration of the two variables.

Overall, I find it more readable.


Algorithmic complexity of this algorithm to find all ordered permutations of length X I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars.

For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'a'], ['b', 'b'], ..., ['d', 'd']]

I'm not sure about its algorithmic complexity though (at least I know it's pretty horrible). I would say it's something around:

O(X * N^(L + X))

(where L is the number of different chars, 4 here because we have 'A', 'B', 'C', 'D', and X the length of the permutations we want to generate). Because I have 2 nested loops, which will be run X times (well, X-1 because of the special case when X = 1). Is it correct?

def generate_permutations(symbols, permutations_length):
    if permutations_length == 1:
        return [[symbol] for symbol in symbols]

    tails = generate_permutations(symbols, permutations_length-1)
    permutations = []

    for symbol in symbols:
        for tail in tails:
            permutation = [symbol] + tail

            permutations.append(permutation)

    return permutations

print(generate_permutations(['a', 'b', 'c', 'd'], 2))

By the way: I know this is not idiomatic Python and I apologize if it's ugly but it's just some prototyping I'm doing before writing this code in a different, less expressive language. And I also know that I could use itertools.permutations to do this task. By the way, I'd be interested if someone happens to know the algorithmic complexity of itertool's permutations function.

def generate_permutations(symbols, permutations_length):

These are not permutations. They are Cartesian products. In addition, calling the function generate_something suggests that what's returned might be a generator, which is probably what you want for a function which returns a stupendously large data structure, but is not what you get from this function.

    for symbol in symbols:
        for tail in tails:
            permutation = [symbol] + tail

            permutations.append(permutation)

If you use extend instead of append then you give better hints as to how much underlying buffers might need to be increased:

    for tail in tails:
        result.extend([symbol] + tail for symbol in symbols)

Performance: with an alphabet of size \$L\$ let \$T_L(X)\$ be the cost of calling this function for products of length \$X\$. Then \$T_L(1) = L\$ and \$T_L(X+1) = T_L(X) + L L^X (X+2)\$ assuming that constructing the list [symbol] + tail takes time proportional to its length and extending the list of results take amortised constant time per element added. This gives \$\Theta(L^{X}X)\$ complexity.

The same complexity but much better memory efficiency can be achieved with a true generator approach which is based on the fact that all you really need to do is count to \$L^X\$ and convert into base \$L\$.


Creating an iOS form with many similar text field cells I'm using multiple instances of an object creating a form:

{...
BPFormInputTextFieldCell *nameCell = [[inputTextFieldClass alloc] init];
    nameCell.backgroundColor = cellBgnd;
    nameCell.textField.placeholder = @"business_name";
    nameCell.mandatory = YES;
    nameCell.textField.delegate = self;
    nameCell.customCellHeight = 40.0f;

    BPFormInputTextFieldCell *addressCell = [[inputTextFieldClass alloc] init];
    addressCell.backgroundColor = cellBgnd;
    addressCell.textField.placeholder = @"contact_name";
    addressCell.mandatory = YES;
    addressCell.textField.delegate = self;
    addressCell.customCellHeight = 40.0f;

    BPFormInputTextFieldCell *dobCell = [[inputTextFieldClass alloc] init];
    dobCell.backgroundColor = cellBgnd;
    dobCell.textField.placeholder = @"address";
    dobCell.mandatory = YES;
    dobCell.textField.delegate = self;
    dobCell.customCellHeight = 40.0f;

    BPFormInputTextFieldCell *sexCell = [[inputTextFieldClass alloc] init];
    sexCell.backgroundColor = cellBgnd;
    sexCell.textField.placeholder = @"city";
    sexCell.mandatory = YES;
    sexCell.textField.delegate = self;
    sexCell.customCellHeight = 40.0f;

    BPFormInputTextFieldCell *contexturaCell = [[inputTextFieldClass alloc] init];
    contexturaCell.backgroundColor = cellBgnd;
    contexturaCell.textField.placeholder = @"region";
    contexturaCell.mandatory = YES;
    contexturaCell.textField.delegate = self;
    contexturaCell.customCellHeight = 40.0f;

    self.formCells = @[@[nameCell, addressCell, dobCell, sexCell, contexturaCell, pesoCell, estaturaCell, actividadCell, deseoCell, cuantosKilosCell, cuantoTiempoCell, ...];
 ...}

As you can see, I need to refactor this badly.  The objects should also go into the array.  What is the best approach?

As far as I can tell, the only difference between these objects is the placeholder text, right?  I'm not sure how valuable it is that we have so many text fields and don't have a way of accessing them individually (to know what the user input in each... but nonetheless...).

So all we need is an array with the placeholder strings, and a for in loop.

NSArray *placeholders = @[@"business_name", @"contact_name", @"address", @"city", @"region"];

NSMutableArray *textFields = [NSMutableArray arrayWithCapacity:placeholders.count];

for (NSString *placeholder in placeholders) {
    BPFormInputTextFieldCell *textField = [[inputTextFieldClass alloc] init];
    textField.backgroundColor = cellBgnd;
    textField .textField.placeholder = placeholder;
    textField.mandatory = YES;
    textField.textField.delegate = self;
    textField.customCellHeight = 40.0f;
    [textFields addObject:textField];
}

self.formCells = textFields;

So much copy-and-pasting should almost always be a red flag for needing a loop.


Finding number of solutions nqueens 14 by 14 chessboard I have written a code to solve the N-Queen problem for a 14 by 14 chessboard. There are preplaced queens (see below for the sample input and output). The lines of sample input (after the 3) represent the positions of the preplaced queens. For example, "1 1 2 9 3 6 4 10" refers to the 4 preplaced queens are at (1st row 1st column), (2nd row, 9th column), (3rd row 6th column), (4th row, 10th column).
I am hoping that it will return me the number of solutions. But when I tried running the code, I got time limit exceeded, even for the sample input.
I will try the list of tuples method, but let me know if there is a more efficient implementation. Thanks in advance
[![Question screenshot][1]][1]
Sample Input
3
1 1 2 9 3 6 4 10
1 9 12 8 8 5 2 7
2 10 10 3

Sample Output
39
32
2414

import sys

def nQueens(n, pre_placed_rows, pre_placed_cols, N, state=[], col=1):
    if col > n: return [state]
    res = []

    for i in range(1, n+1):
        if invalid(state, i): continue
        for sol in nQueens(n, pre_placed_rows, pre_placed_cols, N, state + [i], col+1):
            if N == 2: # 2 preplaced queens
                if sol[pre_placed_cols[0]-1] == pre_placed_rows[0] and sol[pre_placed_cols[1]-1] == pre_placed_rows[1]:
                    res.append(sol) #[sol]
            elif N == 3:  # 3 preplaced queens
                if sol[pre_placed_cols[0]-1] == pre_placed_rows[0] and sol[pre_placed_cols[1]-1] == pre_placed_rows[1] and sol[pre_placed_cols[2]-1] == pre_placed_rows[2]:
                    res.append(sol)
            else: # 4 preplaced queens
                if sol[pre_placed_cols[0]-1] == pre_placed_rows[0] and sol[pre_placed_cols[1]-1] == pre_placed_rows[1] and sol[pre_placed_cols[2]-1] == pre_placed_rows[2] and sol[pre_placed_cols[3]-1] == pre_placed_rows[3]:
                    res.append(sol)
    return res

def invalid(s, r2): # is it safe to put the queen
    if not s:
        return False
    if r2 in s:
        return True
    c2 = len(s) + 1
    return any(abs(c1-c2) == abs(r1-r2) for c1, r1 in enumerate(s, 1))

num_case = int(sys.stdin.readline())
for _ in range(num_case):
    s = sys.stdin.readline().split()
    N = len(s) // 2
    pre_placed_rows = []
    pre_placed_cols = []
    n = 14
    for i in range(N):
        pre_placed_rows.append(int(s[2*i]))
        pre_placed_cols.append(int(s[2*i+1]))

    print(len(nQueens(n, pre_placed_rows, pre_placed_cols, N)))

Here's my take on it.
Translate columns 1-14 to 0-13 for internal use and translate back on output.
state keeps track of where the queens are.  state[0] is the row of the queen in column 0, etc.  A None indicates the column is empty.
nQueens() searches state for an empty column and then checks each row in that column for a valid move.  If a move is valid, state is updated and nQueens() is called with the new state. After the recursive call is made, revert the change in state. That avoids the need to make a copy of the state.
The code yields the solutions rather than keeping a list.
printboard() is just to help with visualizing what is going on.  Uncomment some of the calls if you're curious...but only do one of the smaller test cases because there is a lot of output.
I think your imvalid() might be off?
Put the driver code in main().
SIZE = 14

def nQueens(state):
    #printboard(state)

    # find an empty column (row==None)
    for col, row in enumerate(state):
        if row is None:
            break

    # all columns filled. so it is a solution
    else:
        yield state

    for row in range(SIZE):
        # check if row taken
        if not valid(state, row, col):
            continue

        # make the move
        #print(f"col[{col+1}] = {row+1}")
        state[col] = row
        yield from nQueens(state)

        # revert the move to continue the search
        state[col] = None

def valid(state, row, col):
    # is there a queen in this row
    if row in state:
        return False

    # is there a queen on a diagonal
    for c,r in enumerate(state):
        if r is None:
            continue

        if col-row == c-r or col+row == c+r:
            return False

    return True

def printboard(state):
    print('  '+' '.join(str(i%10) for i in range(1, SIZE+1)))
    for r in range(SIZE):
        print((r+1)%10, end=' ')
        for c in range(SIZE):
            if state[c] == r:
                print('Q', end=' ')
            else:
                print('.', end=' ')
        print()

def main(data):
    num_cases = int(data.readline())

    for case_num in range(num_cases):
        # initialize state to all Nones.
        # None means the corresponding column is empty
        state = [None]*SIZE

        # fill in the preset queens
        preset = data.readline().split()
        while preset:
            row = int(preset.pop(0)) - 1
            col = int(preset.pop(0)) - 1
            state[col] = row

        #printboard(state)

        # count the number of solutions
        for n,sol in enumerate(nQueens(state)):
            #printboard(sol)
            pass

        print(n+1)

Test it like so:
test = """
3
1 1 2 9 3 6 4 10
1 9 12 8 8 5 2 7
2 10 10 3
""".strip()

main(io.StringIO(test))

Or call it like:
main(sys.stdin)


Truck class constructor Is there a better way to pass variables into a class?

public class Truck
{
    private int _wheels;
    private string _color;
    private bool _loaded;
    public int wheels { get { return _wheels; } }
    public string color { get { return _color; } }
    public bool loaded { get { return _loaded; } }

    public Truck(int wheels, string color, bool loaded)
    {
        this._wheels = wheels;
        this._color = color;
        this._loaded = loaded;
    }
}

Truck dumpTruck = new Truck(6, "yellow", false);

I have learned C# by error code and there has got to be a better way to do this. I am stuck on Framework 2.0.

A few observations.

Properties should be PascalCase.

public class Truck
{
    // ...
    public int Wheels { get {return _wheels; } }

    // ...
}

The this keyword is not needed here.  by having the '_' in front of your class variables, you are differentiating them from the local variables.

Now, to answer your question, you could use Automatic Properties, which would change your class to be something like:

public class Truck
{
    public int Wheels { get; private set; }
    public string Color { get; private set; }
    public bool Loaded { get; private set; }

    public Truck(int wheels, string color, bool loaded)
    {
        Wheels = wheels;
        Color = color;
        Loaded = loaded;
    }
}

As for your question of having a better way: the only other way to set them is to make the property's set method public and set them through that.  Personally, I like passing them through the constructor better, it makes it easier to make the the class immutable.


Determine whether any permutation of a string is a palindrome The task:

  Given a string, determine whether any permutation of it is a
  palindrome.

  For example, "carrace" should return true, since it can be rearranged to
  form "racecar", which is a palindrome. "daily" should return false, since
  there's no rearrangement that can form a palindrome.

My solution:

const isPalindrome = str => {
  const letterOccurrences = str
  .split("")
  .reduce((acc, x) => {
    acc[x] = acc[x] ? acc[x] + 1 : 1;
    return acc;
  }, {});

  let numberOfOddOccurrences = 0;
  const isMaxOneOddNumberLetter = x => x % 2 === 0 || ++numberOfOddOccurrences <= 1;
  return Object.values(letterOccurrences).every(isMaxOneOddNumberLetter);
};

console.log(isPalindrome("carrace"));

Is it possible to write the function isMaxOneOddNumberLetter without mutation resp. side effects?

This is similar to a previous question of yours, Find the elements that appear only once, and the same advice applies: use a Set and maintain a flag instead of a count.  If your Set ends up with size of zero or one, it's a palindrome.  Otherwise no.

const isPalindrome = s => s.split("").reduce(
    (once, x) => (once.delete(x) || once.add(x), once),
    new Set()
  ).size <= 1

If inputs are constrained to 26 letters, you can map each letter to a unique power of 2 and replace the set with a bit vector (aka an "integer"), using XOR to track which bits appear an odd number of times.  This may or may not be faster than a Set but it will certainly use less memory.  I'll leave the implementation as an exercise for the reader.