Assemble network packet on stack for iovec The recurring problem to assemble a network packet out of payload, sequence number, header, and other misc. information is mostly solved either on the heap (e.g. appending to a std::vector) or by first allocating a (hopefully large enough) buffer and then writing to that buffer. Some of the elements always stay the same or only change minimally (like the header) and therefore the scatter/gather approach offered by writev with iovec, Asio with buffer sequences or other networking interfaces allow to avoid those unnecessary copies.
There is still the problems that different parts of the message are produced in different parts of the code, especially when more than on sub-protocol is to be used. In that case we are again tempted to use dynamic memory allocation to construct the iovec.
I would like to avoid those dynamic memory allocation and potentially oversized buffers for so I came up with the following in-stack stack implementation (I named it stack_stack):
template<class T, size_t length=1>
struct stack_stack {
  using next_type = stack_stack<T, length-1>;
  using prev_type = stack_stack<T, length+1>;
  const T value;
  const next_type * next = nullptr;
  static constexpr size_t ssize = length;

  struct iterator {
    using value_type = T;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::input_iterator_tag;

    iterator& operator++() {
      ptr = static_cast<const stack_stack*>(ptr)->next;
      return *this;
    }
    bool operator==(iterator other) const {
      return ptr == *other;
    }
    bool operator!=(iterator other) const {
      return ptr != *other;
    }
    pointer operator*() {return static_cast<pointer>(ptr);}

    const void* ptr;
  };
  iterator begin() const {return iterator{this};}
  iterator end() const {return iterator{nullptr};}

  prev_type push_front(T val) const {
    return {val, this};
  }
};

It keeps track of its length using template parameters and could be used like in the following example scenario:

struct ioitem {
  char* data;
  size_t size;
};

template<class stack>
void Send(const stack& b) {
  for (auto a : b) {
    std::cout << a->data << std::endl;
  }
}

template<class stack>
void SendWithHeader(const stack& b) {
  auto header = std::string("HDX1");  // This would normally some kind of constexpr
  Send(b.push_front({header.data(), header.size()}));
}

template<class stack>
void SendWithSeqno(const stack& b) {
  auto seq_no = std::string("5");
  auto b1 = b.push_front({seq_no.data(), seq_no.size()});  // it's ok if one module addds more than one part
  auto b2 = b1.push_front({seq_no.data(), seq_no.size()});
  SendWithHeader(b2);
}

template<class stack>
void SendWithTag(const stack& b) {
  auto tag_name = std::string("my tag");  // I am just making up a protocol here
  SendWithSeqno(b.push_front({tag_name.data(), tag_name.size()}));
}

int main() {
  auto my_data = std::string("Hello World");
  auto my_Buffer = stack_stack<ioitem>{my_data.data(), my_data.size()};
  SendWithTag(my_Buffer);
}

What I would like to improve:

In the Send function I could copy the stack to a statically sized array according to the size of stack::ssize. However I did not get std::copy to work.
I don't like the hacks with the void* in the iterator.

Also: Is this a good way to approach this problem or is there a much better solution (without the heap) that got under my radar? I searched for similar implementations to mine but could not find anything.

The iterator is not behaving correctly
There are various reasons std::copy() doesn't work on stack_stack, and it all has to do with the iterator. First, you are missing difference_type. Since your iterators do not support taking the difference, set it to void:
using difference_type = void;

Second, your comparison operators are wrong. They should take a const reference to other, and you can access member variables of other directly, so:
bool operator==(const iterator &other) const {
   return ptr == other.ptr;
}

Also, while this is a trivial comparison operator, it is good to define operator!= in terms of operator==, to avoid potential mistakes:
bool operator!=(const iterator &other) const {
    return !(*this == other); // Just invert the result of operator==
}

Last, the result of operator* should be a reference to the actual data, not a pointer, so:
reference operator*() {
    return *static_cast<pointer>(ptr);
}

Now it sort of works, and std::copy() is happy. In your own code, you need to change some use of -> to . to make it print the contents of a stack, like so:
for (auto item: stack) {
    std::cout << item.data << "\n";
}

Avoiding void* hacks
Well, you have created a problem for yourself. Each element of the stack points to the next element, but it has a different type. The cleanest solution I see without changing the type system used for stack_stack is to do this:
struct iterator {
    ...
    using pointer = const stack_stack*;
    ...
    iterator& operator++() {
        ptr = reinterpret_cast<pointer>(ptr->next);
        return *this;
    }
    ...
    reference operator*() {
        return ptr->value;
    }

    pointer ptr;
};

So we removed all of the lies, except the one about the type when following ptr->next.
The cleanest approach
If you want to do it even cleaner, then you should not have a template parameter length. Maybe also don't call it a stack, it more accurately resembles one element of a singly-linked list. To keep track of the length of this list, I would create a separate type that resembles the list as a whole, and which stores the length and a pointer to the head, both of which we will update when we add elements:
template<class T>
struct stack_list {
    struct item {
        const T value;
        const item *const next;

        // Constructor which will update the head of stack_list
        item(const T &value, const item *&head): value(value), next(head) {
            head = this;
        }

        // Delete copy constructor, move and assignment operators
        item(const item &other) = delete;
        item &operator=(const item &other) = delete;
        item &operator=(const item &&other) = delete;
    };

    struct iterator {
        ... // left as an excercise to the reader
    };

    size_t size{};
    const item *head{};

    [[nodiscard]] item push_front(T value) {
        size++;
        return {value, head}
    }
}

Then you can use it like so:
auto my_data = ...;

stack_list<ioitem> sl;
auto my_buffer = sl.push_front({my_data.begin(), my_data.size()});

std::cout << "List size: " << sl.size << "\n"
          << "First element: " << sl.head->value << "\n";

Using your class for building iovecs
As you noticed you still need to convert your stack (or list) of ioitems to an array of struct iovec. So it might be better to build this array directly. If you want to do it on the stack, then the safest option is to just go with a std::array<iovec, N>, where N is large enough to handle most or all cases. If the required size can vary a lot, then you can perhaps make a class that holds a union of a std::array and a std::vector, and switches to the vector if the array is full. You might be able to use an existing library implementing small vector optimization, but since you basically always push_front(), your own implementation that starts at the back of the array might be the most efficient. It might look like:
template<size_t N = 8>
class iovec_builder {
    std::array<struct iovec, N> iov;
    size_t iovlen{};

public:
    void push_front(struct iovec item) {
        if (iovlen == N) {
            // handle array being full
        } else {
            // add starting from the back
            iovlen++;
            iov[N - iovlen] = item;
        }
    }

    struct iovec *get_iov() {
        return &iov[N - iovlen];
    }

    size_t get_iovlen() const {
        return iovlen;
    }
};

And use it like:
iovec_builder iovb;
std::string my_data("Hello World");
iovb.push_front({my_data.data(), my_data.len()});
iovb.push_front({..., ...});

struct msghdr msg{};
msg.iov = iovb.get_iov();
msg.iovlen = iovb.get_iovlen();
...
sendmsg(fd, &msg, ...);

It might waste a bit of stack space, but you'll waste more by having a linked list and having to copy it into an array.


Fastest way to clamp an integer to the range 0-255 I'm working on some image processing code that can generate pixel values outside of the normal range of 0 to 255, and I'd like to clamp them back into the valid range. I know that there are saturating SIMD instructions that make this a moot point, but I'm trying to stay within standard C++ code for the moment.

The fastest I've been able to do on my Athlon II is the following:

inline
BYTE Clamp(int n)
{
    n &= -(n >= 0);
    return n | ((255 - n) >> 31);
}

This compiles down into the following assembly with MSVC 6.0:

setns dl
neg   edx
and   eax, edx
mov   edx, 255
sub   edx, eax
sar   edx, 31
or    dl, al

Is there any improvement possible?

Try
 int x=n>255?255:n;
 ... x<0?0:x ...

I'd expect this to produce something like:
 mov     ebx, 255
 mov     eax, n
 cmp     eax, ebx
 cmovg   eax, ebx ; conditional mov instruction
 test    eax, eax
 mov     ebx, 0
 cmovl   eax, ebx

If you are using MSVC SIX, you may not get the conditional move instruction. Try switching to a modern version of visual studio.


Implementation of the undef function Write a function undef that will remove a name and a definition from the maintained by lookup and install.

Here is my solution:

void undef(char *name)
{
    struct Nlist *tmp  = hashtab[hash(name)];

    if(!strcmp(tmp->name, name)) { // delete the head node
        hashtab[hash(name)] = tmp->next;
        free(tmp->name);
        free(tmp);
        return;
    }

    for(; strcmp(tmp->next->name, name); tmp = tmp->next)
        ;

    struct Nlist *save = tmp->next; // save the desired node for deletion
    tmp->next          = tmp->next->next; // adjust the links
    free(save->name);
    free(save);
}

There are 2 main cases. The first is when we want to delete the head node, and when we want to delete a node from the rest of the list.

I will explain how my function works in the second case. The for loop will run until tmp will point to the node that precedes the desired node. Then I adjust the links and free the memory occupied by the desired node.

This approach is not good if the desired value is located at the head node, so I use a if-statement to check if the desired value is located at the head node. If it is, I adjust the head pointer and free the memory.

Here is the code for the entire program: http://ideone.com/t0bjiA.

It's not necessary to special-case the head of the list if you think about it in a different way.  In particular, each entry in your hashtable is a pointer to an Nlist structure, so if you take the address of the hashtable entry, you can treat it just like any other node.  Specifically, you can use this:

void undef(char *name)
{
    struct Nlist **tmp = &hashtab[hash(name)];
    struct Nlist *old;

    /* find our matching node */
    for ( ; *tmp && strcmp(name, (*tmp)->name); tmp=&((*tmp)->next));

    /* if we have found it, delete and adjust pointer */
    if (*tmp != NULL) {
        old = *tmp;
        free(old->name);
        free(old->defn);
        *tmp = old->next;
        free(old);
    }
}

Also note that defn was not being deleted in your original code, resulting in a memory leak.


React avoid code repetation I was working on a react hooks project.
I was making a form
In the form, I noticed myself writing a very wet code
Here is my code
const FormInvite = (props) => {
  const [firstName, setFirstName] = useState("");
  const [lastName, setLastName] = useState("");
  const [country, setCountry] = useState("")
  const [email, setEmai] = useState("")

  const changeSelectedCountry = (event) => {
    setCountry(event.target.value)
  }

  const changeFirstName = (event) => {
    setFirstName(event.target.value)
  }

  const changeLastName = (event) => {
    setLastName(event.target.value)
  }

  const changeEmail = (event) => {
    setEmail(event.target.value)
  }

Can someone help me/give recommendation so that I don't write those one liner, kind of representative code?

Given your form fields use appropriate names (i.e. field names match state properties), and you don't mind using a single state object you can create a single change handler that merges in each field update (similar to how a class-based component's this.setState would handle it) using the field name as the key.
const FormInvite = (props) => {
  const [state, setState] = useState({
    firstName: '',
    lastName: '',
    country: '',
    email: '',
  });

  const changeHandler = e => {
    const { name, value} = e.target;
    setState(state => ({ ...state, [name]: value }));
  }
  ...

const rootElement = document.getElementById("root");

const FormInvite = props => {
  const [state, setState] = React.useState({
    firstName: "",
    lastName: "",
    country: "",
    email: ""
  });

  const changeHandler = e => {
    const { name, value } = e.target;
    setState(state => ({ ...state, [name]: value }));
  };

  React.useEffect(() => {
    console.log('firstname changed', state.firstName);
  }, [state.firstName]);
  React.useEffect(() => {
    console.log('lastname changed', state.lastName);
  }, [state.lastName]);
  React.useEffect(() => {
    console.log('country changed', state.country);
  }, [state.country]);
  React.useEffect(() => {
    console.log('email changed', state.email);
  }, [state.email]);

  return (
    <form>

        First
        <input
          type="text"
          value={state.firstName}
          name="firstName"
          onChange={changeHandler}
        />

        Last
        <input
          type="text"
          value={state.lastName}
          name="lastName"
          onChange={changeHandler}
        />

        Country
        <input
          type="text"
          value={state.country}
          name="country"
          onChange={changeHandler}
        />

        email
        <input
          type="email"
          value={state.email}
          name="email"
          onChange={changeHandler}
        />

    </form>
  );
};

ReactDOM.render(
  <React.StrictMode>
    <FormInvite />
  </React.StrictMode>,
  rootElement
);
input {
  width: 3rem;
}

NOTE: This uses a functional state update to ensure/preserve previous state values that aren't currently being updated.
Alternatively you can create a mapping of state => setState function and use a similar change handler as before, this time though you won't need to merge in updates manually.
const FormInvite = props => {
  const [firstName, setFirstName] = React.useState("");
  const [lastName, setLastName] = React.useState("");
  const [country, setCountry] = React.useState("");
  const [email, setEmail] = React.useState("");

  const fieldSetStateMap = {
    firstName: setFirstName,
    lastName: setLastName,
    country: setCountry,
    email: setEmail
  };

  const changeHandler = e => {
    const { name, value } = e.target;
    fieldSetStateMap[name](value);
  };
  ...

const rootElement = document.getElementById("root");

const FormInvite = props => {
  const [firstName, setFirstName] = React.useState("");
  const [lastName, setLastName] = React.useState("");
  const [country, setCountry] = React.useState("");
  const [email, setEmail] = React.useState("");

  const fieldSetStateMap = {
    firstName: setFirstName,
    lastName: setLastName,
    country: setCountry,
    email: setEmail
  };

  const changeHandler = e => {
    const { name, value } = e.target;
    fieldSetStateMap[name](value);
  };

  React.useEffect(() => {
    console.log("firstname changed", firstName);
  }, [firstName]);
  React.useEffect(() => {
    console.log("lastname changed", lastName);
  }, [lastName]);
  React.useEffect(() => {
    console.log("country changed", country);
  }, [country]);
  React.useEffect(() => {
    console.log("email changed", email);
  }, [email]);

  return (
    <form>

        First
        <input
          type="text"
          value={firstName}
          name="firstName"
          onChange={changeHandler}
        />

        Last
        <input
          type="text"
          value={lastName}
          name="lastName"
          onChange={changeHandler}
        />

        Country
        <input
          type="text"
          value={country}
          name="country"
          onChange={changeHandler}
        />

        email
        <input
          type="email"
          value={email}
          name="email"
          onChange={changeHandler}
        />

    </form>
  );
};

ReactDOM.render(
  <React.StrictMode>
    <FormInvite />
  </React.StrictMode>,
  rootElement
);
input {
  width: 3rem;
}

NOTE: This can use a plain state update as each "piece of state" is fully independent of other state and the value is replaced each onChange.


How to efficently generate n different subsets of length k from List? I would like to generate n subsets from objects from a List. Each subset should have k elements. Each subset should be unique.

The output should be a List of Lists.

My (very very slow way) is to create ALL possible subsets:

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source)
{
    if (!source.Any())
        return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

    var element = source.Take(1);

    var haveNots = SubSetsOf(source.Skip(1));
    var haves = haveNots.Select(set => element.Concat(set));

    return haves.Concat(haveNots);
}

Afterwards I select the subsets with length k with the help of linq .where(x => x.Count() == k) and randomly select n of them.

This is very slow, because if the input list has 50 elements, there are 1125899906842624 different possible subsets. This is a big overhead.

How can I solve this problem more efficiently?

As noted in a comment, I did a series on my blog about interesting ways to solve this problem.  But let's think about simple ways we can modify your program to solve your problem.  We wish to produce all the subsets of source of size k, so let's add k to your method signature:

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source, int k)
{

All right, what is our base case?  Your original base case was "if the source is the empty set, then its only subset is the empty set".  We must modify that, because our new contract is that we only return subsets of size k.

Let's be efficient. If k is zero then we can just take the early out; we know ahead of time that there is a subset of size zero regardless of the contents of source:

    if (k == 0)
        return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

Now we know that k is not zero. If the source is empty, or k is negative, then there must be no solution:

    if (k < 0 || !source.Any())
        return Enumerable.Empty<IEnumerable<T>>();

All right. That's our base case.

Now we must modify your recursive case.  We now know that k is positive, and source is not empty.

There are two possibilities: either the first element is in the subset, or it is not. What are the subsets of size k that lack the first element?

    var haveNots = SubSetsOf(source.Skip(1), k);

Super. What are the subsets of size k that contain the first element? They are the subsets of size k-1 appended with that element.

    var element = source.Take(1);
    var smallerHaveNots = SubSetsOf(source.Skip(1), k-1);
    var haves = smallerHaveNots.Select(set => element.Concat(set));

And now we're done:

    return haves.Concat(haveNots);
}

A very small modification to your algorithm greatly speeds it up.  But we could make it more efficient still.  What if, instead of an IEnumerable<T> for source we had an ImmutableStack<T> for source?  The only operations that we ever perform on source are:

Is it empty?
Extract the head
Recurse on the tail

which is exactly the operations of an immutable stack. We could do this entire operation but allocation far fewer helper objects; each time you call Skip(1), that generates a new object, but there's no need to do that; you could just use the tail of the stack.

Similarly: the outputs are a sequence of possibly-empty tails that sometimes have a head pushed onto them; you can get efficiency wins by making the outputs also immutable stacks.

See if you can go from there and make a really efficient implementation of this algorithm.


Rusted days - a WolframAlfa port I wrote a silly Rust program inspired by a WolframAlpha query. I know, that's nothing serious, but if there's anything that could be made more, well, proper Rust-like, I'd love to know! Of course, general feedback is welcomed too.
For starters, here's my Cargo.toml:
[package]
name = "rusted-days"
version = "0.1.0"
authors = ["baduker"]
edition = "2018"

[dependencies]
chrono = "0.4.19"

And the code:
use std::io;
use std::io::Write;
use chrono::{NaiveDateTime, DateTime, Utc, Datelike};

fn main() {
    let prompt = "What's your date (DD/MM/YYYY)?: ";
    let date = input(prompt).expect("Something went wrong! o.O");
    show_interpretation(parse_date(date));
}

fn input(user_input: &str) -> io::Result<String> {
    print!("{}", user_input);
    io::stdout().flush()?;

    let mut buffer: String = String::new();
    io::stdin().read_line(&mut buffer)?;

    Ok(buffer.trim_end().to_owned())
}

fn parse_date(date: String) -> DateTime<Utc> {
    let naive_date = chrono::NaiveDate::parse_from_str(
        date.as_str(), "%d/%m/%Y"
    ).unwrap();

    let naive_datetime: NaiveDateTime = naive_date
        .and_hms(0, 0, 0);

    DateTime::<Utc>::from_utc(naive_datetime, Utc)
}

fn show_interpretation(date: DateTime<Utc>) {
    println!("Input interpretation: days since {}", date.format("%A, %B %d, %Y"));

    let total_days = Utc::now() - date;
    println!("Result:\n{} days have rusted away ¯\\_(ツ)_/¯", total_days.num_days());

    let years = Utc::now().year() - date.year();
    let months = Utc::now().month() - date.month();
    let days = Utc::now().day() - date.day();

    println!("Timespan:\n{} year(s), {} month(s), {} day(s)", years, months, days);
    println!("{} weeks", total_days.num_weeks());
    println!("{:.2} years", total_days.num_days() as f32 / 365_f32);
}

A sample output (you should get):
What's your date (DD/MM/YYYY): 01/01/1970
Input interpretation: days since Thursday, January 01, 1970
Result:
18567 days have rusted away ¯\_(ツ)_/¯
Timespan:
50 years, 10 month(s), 0 days
2652 weeks
50.87 years

I can't see any issues in terms of making your code idiomatic; it looks very Rust-like! I did however notice a problem with your code's logic.
Integer overflow
I tried inputting 31/12/2019 and obtained a panic when I ran it today (07/11/2020). This was because Utc::now().month() is a u32 equal to 11, and the code attempts to subtract 12:
let months = Utc::now().month() - date.month();

This leads to an overflow because we're using unsigned integers. The same story applies for the day, which is also a u32, but not the year, which is an i32 and so functions fine.
Even if we convert the relevant types to signed integers, the following isn't what you mean:
let years = Utc::now().year() - date.year();

This would tell you that 31/12/2019 and 1/1/2020 are a year apart, when in fact this isn't true. Even dividing the number of days by 365 isn't quite right because of leap years.
Making the date logic work correctly is a lot more frustrating than it sounds: the number of months passed depends on the length of each month as well as the Duration instance. That's why Duration doesn't implement anything beyond num_weeks(): it's simply a difference between two dates, so it doesn't know how to account for the varying month lengths.


N-Divisible Digits small program Heres the idea
Write a program that takes two integers, N and M, and find the largest integer composed of N-digits that is evenly divisible by M. N will always be 1 or greater, with M being 2 or greater. Note that some combinations of N and M will not have a solution.
Example: if you are given an N of 3 and M of 2, the largest integer with 3-digits is 999, but the largest 3-digit number that is evenly divisible by 2 is 998, since 998 Modulo 2 is 0. Another example is where N is 2 and M is 101. Since the largest 2-digit integer is 99, and no integers between 1 and 99 are divisible by 101, there is no solution.

I would just like some tips on what to improve

#include <iostream>
#include <stdexcept>
#include <cmath>

using std::cin; using std::cout; using std::endl; using std::runtime_error;
using std::pow;

unsigned largestNumber(unsigned num1) {
return pow(10, num1) - 1;
}

void validNums(const int num1, const int num2) {
    if (num1 < 1 || num1 > 9 || num2 < 2 || num2 > 999999999)
        throw std::runtime_error("invalid input");
}

int divisbleBy(int num1, int num2) {
    for (; num1 != 0; --num1) {
        if (num1 % num2 == 0)
            return num1;
    }
    return 0;
}

int main()
{
    int num1 = 0, num2 = 0;
    int answer = 0;
    cout << "Enter 2 nums and we'll find biggest number possible with num1 digits and we'll then find closest number that num2 can divide by. Num1 has to be between 1-9 and num2 between 2-999-999-999" << endl;
    cin >> num1 >> num2;
    validNums(num1, num2);
    if (answer = divisbleBy(largestNumber(num1), num2))
        cout << "Largest number possible with " << num1 << " is " << largestNumber(num1) << " and the closest number to " << largestNumber(num1) << " divisible by " << num2 << " is " << answer << endl;
    else
        cout << "Invalid" << endl;
    return 0;
}

You should try to find the O(1) algorithm for this problem, instead of using your current O(M) algorithm.

For example, given the input 9 500000001, your program takes 2.3 seconds (on my laptop) to run through the half-billion integers between 999999999 and 500000001. Whereas, using the relatively obvious O(1) algorithm, it takes 0.007 seconds.

Since this looks like homework and/or a Project Euler–type problem, I won't give the spoiler here.

Stylistically,

Prefer to write out std::cin, std::cout, etc., instead of wasting space at the top of the program with a bunch of using directives. It's shorter, cleaner, and (most importantly) more idiomatic to qualify names at the point of use instead of relying on using directives to pull them into scope.
Your function validNums uses exceptions for control flow, which is frowned upon in C++. Prefer to make it a function returning bool, and have its caller do something sensible (such as print an error message) if the given numbers aren't valid.
You have a named abstraction for largestNumber, when that could just as well have been a named local variable int largestNumber = pow(...);.
You don't have a named abstraction for produceTheActualAnswer; instead, you inline a complicated test if (answer = divisbleBy(largestNumber(num1), num2)) straight into main. This makes it unnecessarily difficult to switch out your bad old algorithm for a new and better one.
Putting an assignment inside an if condition is supremely bad style — so bad that both GCC and Clang (and probably MSVC too) will emit a warning on this code. You should write either

int answer = produceTheActualAnswer(num1, num2);
if (answer != 0) {
    ...
} else {
    ...
}

or, if you really want to use "interesting" features of C++, you might write

if (int answer = produceTheActualAnswer(num1, num2)) {
    ...
} else {
    ...
}

But I don't recommend the latter.

You should also consider taking your num1 and num2 parameters via the command line, instead of reading them from stdin:

int main(int argc, char **argv) {
    if (argc < 3) {
        // maybe read them from stdin anyway
    } else {
        int m = std::atoi(argv[1]);
        int n = std::atoi(argv[2]);
        int answer = f(m, n);
        if (answer != 0) { ... } else { ... }
    }
}

This makes it easier to test your code quickly from the command line, and also makes it easy to time ./a.out 9 500000001 to see if you've beaten my 0.007 seconds yet. ;)


Arithmetic or logical right shifts Is this code correct? Is there any major improvement I can ad in terms of number of operations?

#include <stdio.h>

/* function that yields 1 when run on a machine that uses
arithmetic right shifts for int's and 0 otherwise */

/* use only << >> ! & ~ ^ and constants between 0x0 and 0xff*/

int int_what_shifts();

int main(){
    int_what_shifts();
}

int int_what_shifts(){

    int mask = (0x80 << 24);

    printf("%d\n",!!(mask>>31));

    return !!(mask >> 31);
}

Replace 24 with (sizeof(int) - 1) * CHAR_BIT. Otherwise the code would fail on a non-32-bit integer machines. Also, using -1 as a probe makes you independent of the bitness of a system:

return ((-1) >> 1) == (-1);

PS: you don't want to print anything from such a specialized routine.


Javascript collision check I have code to find images in my selections. But when nothing in selection (loop FOR) and selection is kinda big, it's kinda laggy. How can I improve my code?

  var toStageCoord = map.stageXYToCoordinates(toStage.x + selection.x1, toStage.y + selection.y1);

  var element1 = document.elementFromPoint(toStage.x + selection.x1, toStage.y + selection.y1);
  var element2 = document.elementFromPoint(toStage.x + selection.x2, toStage.y + selection.y2);
  var element3 = document.elementFromPoint(toStage.x + selection.x2, toStage.y + selection.y1);
  var element4 = document.elementFromPoint(toStage.x + selection.x1, toStage.y + selection.y2);
  var found = false;

  if(element1.localName == "image" || element2.localName == "image" || element3.localName == "image" || element4.localName == "image") {
    found = true;console.log("foundfirst");
  }

  for(var y = toStage.y + selection.y1;y < toStage.y + selection.y2 ;y++) {
    if(found){break;}

    for(var x = toStage.x + selection.x1;x < toStage.x + selection.x2;x++) {
      var element = document.elementFromPoint(x,y);

      if(element.localName === "image") {

        console.log("found");
        found = true;
        break;
      }
    }
  }

Some improvements:

var toStageCoord = map.stageXYToCoordinates(toStage.x + selection.x1, toStage.y + selection.y1);

var element1 = document.elementFromPoint(toStage.x + selection.x1, toStage.y + selection.y1);
var element2 = document.elementFromPoint(toStage.x + selection.x2, toStage.y + selection.y2);
var element3 = document.elementFromPoint(toStage.x + selection.x2, toStage.y + selection.y1);
var element4 = document.elementFromPoint(toStage.x + selection.x1, toStage.y + selection.y2);

if(element1.localName == "image" || element2.localName == "image" || element3.localName == "image" || element4.localName == "image") {
  console.log("foundfirst"); // 4
}
else { // 2
  var maxy = toStage.y + selection.y2; // 1
  var maxx = toStage.x + selection.x2;

  outerloop: // 2
  for(var y = toStage.y + selection.y1; y < maxy; y+=4) { // 1, 3

    for(var x = toStage.x + selection.x1; x < maxx; x+=4) { // 1, 3
      var element = document.elementFromPoint(x,y);

      if(element.localName == "image") { // 4
        console.log("found");
        break outerloop; // 2
      }
    }
  }
}

Comments:

These calculations were performed at every iteration of the loops, while they never changed. So, let's move them outside the loops.
Using a label, like this outerloop: one can direct break to which block/loop to exit. So, the variable found is not needed.
Depending on the images' sizes, you don't need to check every pixel. Try a larger gap, like 4 or even 10 pixels, as this would reduce the number of iterations.
In the first check the operator == is used, while in the loop === is used. As === checks the type of the value, too, it would be slower. If == yields the correct answer, too, then it should be used instead.


Logging into WebAPI 2 site from c# desktop application I'm trying to login into a webapi2 site from a desktop application.  After a lot of googling, I cobbled together a working prototype. Since we are talking about security I wanted to do a peer review. I'm just starting with security design and I'm not exactly sure about my design.

The WebAPI site that is targeted is a wepapi 2 standard template out of visual studio.

I'm mainly looking for security issuesut general issues are also greatly appreciated.

One issue I'm aware of is that SSL should be added and with that ssl validation. I haven't implemented it yet.

static internal async Task<string> GetWebAPIReguest(string siteUrl, string APIController, string userName, string Password)
{
    TokenResponseModel Token = await GetBearerToken(siteUrl, userName, Password);

    HttpClient client = new HttpClient();
    client.BaseAddress = new Uri(siteUrl);
    client.DefaultRequestHeaders.Accept.Clear();
    client.DefaultRequestHeaders.Accept.Add(new MediaTypeWithQualityHeaderValue("application/json"));
    client.DefaultRequestHeaders.Authorization = new AuthenticationHeaderValue("Bearer", Token.AccessToken);

    return await client.GetStringAsync(APIController);
}

static internal async Task<TokenResponseModel> GetBearerToken(string siteUrl, string Username, string Password)
{
    HttpClient client = new HttpClient();
    client.BaseAddress = new Uri(siteUrl);
    client.DefaultRequestHeaders.Accept.Clear();

    HttpContent requestContent = new StringContent("grant_type=password&username=" + Username + "&password=" + Password, Encoding.UTF8, "application/x-www-form-urlencoded");

    HttpResponseMessage responseMessage = await client.PostAsync("Token", requestContent);

    if (responseMessage.IsSuccessStatusCode)
    {
        string jsonMessage;
        using (Stream responseStream = await responseMessage.Content.ReadAsStreamAsync())
        {
            jsonMessage = new StreamReader(responseStream).ReadToEnd();
        }

        TokenResponseModel tokenResponse = (TokenResponseModel)JsonConvert.DeserializeObject(jsonMessage, typeof(TokenResponseModel));

        return tokenResponse;
    }
    else
    {
        return null;
    }
}

class TokenResponseModel
{
    [JsonProperty("access_token")]
    public string AccessToken { get; set; }

    [JsonProperty("token_type")]
    public string TokenType { get; set; }

    [JsonProperty("expires_in")]
    public int ExpiresIn { get; set; }

    [JsonProperty("userName")]
    public string Username { get; set; }

    [JsonProperty(".issued")]
    public string IssuedAt { get; set; }

    [JsonProperty(".expires")]
    public string ExpiresAt { get; set; }
}

I was going to make a very large post with altered code, but I don't fully understand what your code is doing so all I will suggest is that

You need to use a consistent code style. camelCase for variables/arguments, PascalCase for runtime constants (types/constants) and properties, and _camelCase for private fields on an object.
Your methods are simply doing way too much. Your 2 methods there are connecting to two different web pages, composing two URLs, parsing JSON into a POCO (and then back out again), and doing authentication on top of all of that.
You aren't managing the lifecycle of HttpClient. There is a general consensus that creating and disposing HttpClients is not the best use of a class. At the very least you should be Disposing of your HttpClients but all you're doing in your current code is letting your HttpClients leak. Consider that your functions do not need to know how to create a HttpClient, they just need to know how to connect to a Url - let the caller of the function do the heavy lifting for you.

Once again I'd give you a code sample but I just don't understand what your code is trying to do, which is my own fault, because I haven't really used much HTTP in .NET.

Here are the responsibilities of your two methods so far:

Create a HttpClient
Decode JSON into a POCO
Create authentication token
Compose url from base url, secondary url and a query string
Apply authentication token to HttpClient
Handle the response of one of the HttpClients
Prepare HttpClient headers

The majority of these should be in their own function.


Checking for culture in comma separated list, any suggestions? I have a basic class that I'd like to get some feedback on. I'm refactoring some old code but the new code looks more complex. Basically I'm passing a list of included and excluded cultures into a function that should return if the current culture should be allowed.  Exclusions win.  Any advice how to better it would be great.  Thanks

public static class CultureCheck
{
    public static bool IsCurrentCultureIncluded(string includedCultures, string excludedCultures)
    {
        if(includedCultures == null)
        {
            throw new ArgumentNullException("includedCultures");
        }

        if (excludedCultures == null)
        {
            throw new ArgumentNullException("excludedCultures");
        }

        var isIncluded = false;

        // exclusions win.
        if (IsCultureInList(excludedCultures) == true)
        {
            isIncluded = false;
        }
        else if(IsCultureInList(includedCultures) == true)
        {
            isIncluded = true;
        }

        return isIncluded;
    }

    private static bool IsCultureInList(string cultures)
    {
        string currentCultureName = Thread.CurrentThread.CurrentCulture.Name;
        var isFound = false;

        if (cultures.IndexOf("*") != -1)
        {
            isFound = true;
        }
        else
        {
            List<string> cultureList = new List<string>(cultures.Split(','));
            if (cultureList.Where(e => e.Equals(currentCultureName, StringComparison.InvariantCultureIgnoreCase)).Any() == true)
            {
                isFound = true;
            }
        }

        return isFound;
    }
}

OLD CODE

 public static bool IsCurrentCultureIncluded(string includedCultures, string excludedCultures)
    {
        #region Exclusion Test

        // exclusions win.
        if (excludedCultures.IndexOf("*") != -1)
        {
            return false;
        }

        string currentCultureName = Thread.CurrentThread.CurrentCulture.Name;
        string[] excludedCulturesSplit = excludedCultures.Split(new char[] { ',' });
        foreach (string excludedCulture in excludedCulturesSplit)
        {
            if (string.Equals(currentCultureName, excludedCulture, StringComparison.InvariantCultureIgnoreCase))
            {
                return false;
            }
        }

        #endregion

        #region Inclusion Test

        if (includedCultures.IndexOf("*") != -1)
        {
            return true;
        }

        string[] includedCulturesSplit = includedCultures.Split(new char[] { ',' });
        foreach (string includedCulture in includedCulturesSplit)
        {
            if (string.Equals(currentCultureName, includedCulture, StringComparison.InvariantCultureIgnoreCase))
            {
                return true;
            }
        }

        #endregion

        return false;
    }

I would do it like this (WARNING - not tested):

public static void SampleUsage()
{
    IsCurrentCultureIncluded("*", "*", Thread.CurrentThread.CurrentCulture.Name);
}

public static bool IsCurrentCultureIncluded(string includedCultures, string excludedCultures, string currentCultureName)
{
    return !CheckIncl(currentCultureName, excludedCultures) &&
            CheckIncl(currentCultureName, includedCultures);
}

private static bool CheckIncl(string currentCultureName, string includedCultures)
{
    if (includedCultures.IndexOf("*") != -1)
        return true;

    var includedCulturesSplit = includedCultures.Split(new[] { ',' });
    return includedCulturesSplit.Any(includedCulture => string.Equals(currentCultureName, includedCulture, StringComparison.InvariantCultureIgnoreCase));
}


Verify that a CSV file contains a backup job for every prod job This is a list of jobs in autosys. What I have to do is make sure that every job in PROD has a accompanying job in BACKUP.

The jobs are formatted as CAPSER_JOB_01_PP. I read the list into a while loop, not sure if I should take an -r.

I take off the last two characters of the job name, and then grep twice for each area, if both are successful it prints a yes at beginning of line, otherwise it is a no.

Frankly I can't find matching documentation for the ${job%??}. I don't know what the two question marks stand for.

I tried using grep -q but it did not work. the > 2>&1 /dev/null did not work either, I had to reverse it to > /dev/null the redirect 2>&1 (as shown). The script works, it is just a clunky way of getting it done. There has to be a better way.

#!/bin/bash
#bash, version 3.2.25

IFS=,

while read area job machine script
do
if grep  ${job%??} /home/first_spreadsheet.txt | grep BACKUP >/dev/null 2>&1 && grep  ${job%??} /home/first_spreadsheet.txt | grep PROD  >/dev/null 2>&1 ; then
echo " YES $area $job $machine $script "
else
echo " NO $area $job $machine $script "
fi
sleep 1
done < /home/first_spreadsheet.txt

cat /home/first_spreadsheet.txt
BACKUP, CAPSER_JOB_01_PP, usa-penguin.com, /bin/bash -lc '/usr/bin/run.sh'
PROD, CAPSER_PROD_JOB_01_PS, usa-penguin.com, /bin/bash -lc '/usr/bin/run.sh'
BACKUP, CAPSER_JOB_02_PP, usa-penguin.com, /bin/bash -lc '$HOME/run/script02'
PROD, CAPSER_PROD_JOB_02_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script02'
BACKUP, CAPSER_JOB_03_PP, usa-penguin.com, /bin/bash -lc '$HOME/run/script03'
PROD, CAPSER_PROD_JOB_03_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script03'
BACKUP, CAPSER_JOB_04_PP, usa-penguin.com, /bin/bash -lc '$HOME/run/script04'
PROD, CAPSER_PROD_JOB_04_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script04'
PROD, CAPSER_PROD_JOB_05_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script05'
PROD, CAPSER_PROD_JOB_06_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script06'
BACKUP, CAPSER_JOB_07_PP, usa-penguin.com, /bin/bash -lc '$HOME/run/script07'
PROD, CAPSER_PROD_JOB_07_PS, usa-penguin.com, /bin/bash -lc '$HOME/run/script07'

I take off the last two characters of the job name, and then grep twice for each area, if both are successful it prints a yes at beginning of line, otherwise it is a no.

  Frankly I can't find matching documentation for the ${job%??}. I don't know what the two question marks stand for.

${job%??} takes the last two characters off the value of $job.
The ${parameter%word} syntax is explained in man bash in the Parameter Expansion section.
The valid patterns in word are shell glob patterns.
A ? in shell glob patterns means any single character.
So two ? mean any two characters.

  I tried using grep -q but it did not work.

Saying "it did not work" always invites the question "what happened?".
I'd recommend to eliminate the phrase "it did not work" from your vocabulary.
I guess one of two things happened:

The command gave an error, perhaps grep: invalid option -- 'q'

This can happen if the implementation of grep in your system does not have such option.

The command did not give an error, but output was not suppressed.

This should be impossible, so I suspect a mistake on your part. If we had the exact command you executed, and the input and output, we could probably explain the mistake.

  the > 2>&1 /dev/null did not work either, I had to reverse it to > /dev/null the redirect 2>&1 (as shown).

It's a bit difficult to understand this sentence.
In any case, > 2>&1 /dev/null is invalid syntax.
Perhaps you meant that instead of 2>&1 >/dev/null you had to write >/dev/null 2>&1 to get the desired effect.
Yes the meaning of these two ways are different.
The effect of 2>&1 >/dev/null is that stderr will be written to stdout and the original stdout will be discarded.
The effect of >/dev/null 2>&1 is that both stdout and stderr will be discarded.
This works by thinking of pointer assignments,
I can go into more detail if needed.

  The script works, it is just a clunky way of getting it done. There has to be a better way.

A couple of things can be improved:

If the file /home/first_spreadsheet.txt exists, then grep should not write anything to stderr, so no need to redirect that
It would be better to store repeatedly used values like ${job%??} and /home/first_spreadsheet.txt in helper variables
It's good limit the scope of changing the value of IFS to avoid unintended effects later in the script. You can do that by prefixing the command that needs it, in this example read
To avoid redirecting the output of individual grep commands, you could group them together and redirect the output of the grouping

Putting the above together (and then some),
you could write a bit simpler like this:

path=/home/first_spreadsheet.txt
while IFS=, read area job machine script
do
    job0=${job%??}
    if { grep $job0 "$path" | grep BACKUP && grep $job0 "$path" | grep PROD; } >/dev/null; then
        printf " YES "
    else
        printf " NO "
    fi
    echo "$area $job $machine $script"
done < "$path"


A simple Fraction class My code seems to work fine. However, I feel like it is a bit too long (fraction.cpp). I really want to create simple, readable, and efficient code.

Sample Run:

Here is the fraction.h file:

#ifndef FRACTION_H
#define FRACTION_H
#include <QString>

class Fraction {

public:
     Fraction();
     Fraction(int numberator, int denominator);
     void set(int numberator, int denominator);
     QString toString() const;
     double toDouble() const;
     int findGCD(int a, int b);
     Fraction simplify();
     Fraction add(const Fraction& other);
     Fraction substract(const Fraction& other);
     Fraction multiphy(const Fraction& other);
     Fraction divide(const Fraction& other);

private:
     int m_Numerator;
     int m_Denominator;
};

#endif // FRACTION_H

Here is the fraction.cpp file:

#include "fraction.h"

// Constructors:
Fraction::Fraction()
    :m_Numerator(0), m_Denominator(0) {}

Fraction::Fraction(int numerator, int denominator)
    :m_Numerator(numerator), m_Denominator(denominator) {
}

// Setter method
void Fraction::set(int numberator, int denominator) {
    m_Numerator = numberator;
    m_Denominator = denominator;
}

// GCD
int Fraction::findGCD(int a, int b) {
    if (a == 0)
        return b;
    return findGCD(b%a, a);
}

// Simplify
Fraction Fraction::simplify() {
    int gcd = findGCD(m_Numerator, m_Denominator);
    return Fraction::Fraction(m_Numerator / gcd, m_Denominator / gcd);
}

double Fraction::toDouble() const {
    return ((double) m_Numerator/m_Denominator);
}

QString Fraction::toString()const {
    return QString("%1 / %2 = %3")
        .arg(m_Numerator)
        .arg(m_Denominator)
        .arg(toDouble());
}

Fraction Fraction::add(const Fraction &other) {
    int numeratorTemp(m_Numerator);
    int denominatorTemp(m_Denominator);

    if (m_Denominator == other.m_Denominator) {
        numeratorTemp = m_Numerator + other.m_Numerator;
    } else {
        numeratorTemp = m_Numerator * other.m_Denominator + other.m_Numerator * m_Denominator;
        denominatorTemp = m_Denominator * other.m_Denominator;
    }
    return Fraction::Fraction(numeratorTemp, denominatorTemp);
}

Fraction Fraction::substract(const Fraction &other) {
    int numeratorTemp(m_Numerator);
    int denominatorTemp(m_Denominator);

    if (m_Denominator == other.m_Denominator) {
        numeratorTemp = m_Numerator - other.m_Numerator;
    } else {
        numeratorTemp = m_Numerator * other.m_Denominator - other.m_Numerator * m_Denominator;
        denominatorTemp = m_Denominator * other.m_Denominator;
    }
    return Fraction::Fraction(numeratorTemp, denominatorTemp);
}

Fraction Fraction::divide(const Fraction &other) {
    int numeratorTemp(m_Numerator);
    int denominatorTemp(m_Denominator);

    numeratorTemp = m_Numerator * other.m_Denominator;
    denominatorTemp = m_Denominator * other.m_Numerator;
    return Fraction::Fraction(numeratorTemp, denominatorTemp);
}

Fraction Fraction::multiphy(const Fraction &other) {
    int numeratorTemp(m_Numerator);
    int denominatorTemp(m_Denominator);

    numeratorTemp  = m_Numerator * other.m_Numerator;
    denominatorTemp = m_Denominator * other.m_Denominator;
    return Fraction::Fraction(numeratorTemp, denominatorTemp);
}

Main.cpp:

#include <QCoreApplication>
#include <iostream>
#include "fraction.h"

int main() {
    using namespace std;

    Fraction frac1(1, 2);
    Fraction frac2(5, 2);

    cout << "Addition: 1/2 + 5/2 = " << frac1.add(frac2).simplify().toString().toUtf8().constData() << "\n";
    cout << "Substraction: 1/2 - 5/2 = " << frac1.substract(frac2).simplify().toString().toUtf8().constData() << "\n";
    cout << "Divide: 1/2 : 5/2 = " << frac1.divide(frac2).simplify().toString().toUtf8().constData() << "\n";
    cout << "Multiplication: 1/2 * 5/2 = " << frac1.multiphy(frac2).simplify().toString().toUtf8().constData() << "\n";
}

Output: https://i.stack.imgur.com/cnT9A.png

One thing that would help simplify your implementation is to fall back to already implemented code. For example, you could implement subtraction as addition using the negative of the second fraction. Likewise you could implement division as multiplication with the reciprocal of the second fraction.
Another point about readability: because you are implementing a mathematical notion which fits well with the standard arithmetic operations, consider adding +, *, etc as operators. As above, these operators could simply call the add, multiply, etc functions you already have. E.g. Fraction operator+(const Fraction& other) {return add(other);}
Consider adding helper methods for negation and reciprocal. These could be private, and used only by the simplified subtract and divide as above, or they could be exposed as potentially useful to the class consumer.
Another simplification would be to avoid coding special cases when the general case works just as well. For example, when adding, you don't need to first check whether the denominators match.
To help avoid the numbers getting out of hand, you could call simplify as a matter of course when doing these operations.
Consider moving some of your functions into the private section of the class definition. Generally, things that are intended to be used by the class and are not intended to be used from outside should be private. findGCD looks like a good candidate for moving. (One advantage of doing this to readability is that someone who wants to use your class knows they're only meant to look at the public methods, so they don't get drowned in irrelevant options.)
Consider getting rid of the set function completely. According to everything else, Fraction objects are immutable and cannot be changed. Instead, each operation returns a new Fraction object. Having set breaks this convention, and actually isn't that helpful a feature.
Consider marking all your member functions const if they don't change the current Fraction object. For example, Fraction simplify() const;
Consider marking all your functions (and your constructors) constexpr if you are using c++14 or greater. This tells the compiler that it's allowed to do some calculations at compile time if it knows the inputs, saving you having to do them at runtime.
As a point of efficiency, int numeratorTemp(m_Numerator); is unnecessarily setting a variable that will then be immediately overwritten. Hopefully an optimising compiler would simply pretend that never happened, but you might as well jump straight to const int numeratorTemp = m_Numerator * other.m_Denominator; or as appropriate.
You could do with some checks against illegal numbers. In particular, any fraction with zero as a denominator including 0/0 as given in your default constructor is undefined, and you should probably throw an exception. (For the same reason, I'd make the default constructor return 0/1.)
Nitpicks.
Although you should make your classes fit with the convention of your broader codebase, all things being equal it's probably better to have toString in a generic class produce a standard string rather than a <QString>.
You have a typo in multiply as multiphy. You also want numerator instead of numberator and subtract instead of substract.
When calling a constructor, don't qualify it. E.g Fraction(n, d); rather than Fraction::Fraction(n, d);


Writing successive function calls I have a Ruby function which generates and saves a report. I'm looking for a Clean Code way of writing this:

def generate
  violations = relevant_violations
  comments = convert_to_cleaned_up_comments(violations)
  text = convert_to_text(comments)
  save_to_file(text)
end

But I hate single-use low-semantic-value variables like these. So here's my first re-write:

def generate
  save_to_file(
    convert_to_text(
      convert_to_cleaned_up_comments(
        relevant_violations)))
end

And even though the flow is now in the reverse order, I find this quicker to grasp. There's less junk getting in the way.

But maybe a map/reduce or block style of programming would provide the same clarity but show data flow in the direction written, top to bottom.

EDIT: I re-wrote it so that the code can be read mostly top-to-bottom, not bottom-to-top:

corpus.rake — the reporting script

def generate_and_save
  save_to_file Violation
    .select(&:within_past_30_days?)
    .map(&:to_corpus_friendly_comment)
    .join "\n"
end

def save_to_file(text)
  File.open(LOCAL_PATH, 'w') { |f| f.write text }
end

violation.rb — the Violation class

  def to_corpus_friendly_comment
    facts
      .downcase
      .gsub(/\b(\d+f?|\w|pic|inspection)\b/, ' ')
      .gsub(/\W/, ' ')
      .gsub(/(foods?|please|days|use)/, '')
      .gsub(/  +/, ' ')
      .strip
  end

  def within_past_30_days?
    date > 30.days.ago
  end

...enabled by object-oriented refactoring; moving the functions into the Violations object enabled method chaining. One part I don't like is that .join "\n" is a lower level of abstraction than the other lines in generate_and_save.

I honestly think your first version is the best one. It's readable, and makes more sense at a glance than the refactorings. That said, I would consider a couple of things.

def generate
  violations = relevant_violations
  comments = convert_to_cleaned_up_comments(violations)
  text = convert_to_text(comments)
  save_to_file(text)
end

The comments and text temp variables represent a transitional state. I would ask myself if I will use them in any other form. If not, and if their entire reason for existence is to transition to text, I would do away with them and have one entry point for clean, or savable text.

I would consider if generating the report is the Violation class responsibility. The report is a presentational concern, and I feel it should have its own class.

class ViolationsReport
  attr_reader :violations, :file

  def initialize(violations, file)
    @violations = violations
    @file = file
  end

  def generate
    save_to_file formatted_violations
  end

private

  def formatted_violations
    convert_to_comments violations
  end

  def save_to_file(text)
    file.open(LOCAL_PATH, 'w') { |f| f.write text }
  end

  # more methods here to do the job
end

The idea is to isolate presentation logic that is only needed for the report, in the report class itself. You then have cleanly defined responsibilities for each class.


Text font size adapting to space In order to practice my programming skills, I am trying to implement a Button class, to use in pygame. I know there are libraries like PGU, I do this to improve in programming.

I spent a bit of time creating a function to find a good font size for the text inside the button, depending on the length of the text and the dimensions of the button.

I came to this result, it's close enough to what I want. However, I am looking for advice to improve this function that looks wobbly:

def balanced_text_size_button(length, width, height):
    # sqrt(length) / length -> The higher the length is, the smaller this value become,
    # it decrease slower and slower as length increase (never reach 0).
    # pow(....., 1.6) -> The resulting value is multiplied,
    # the impact is more important on high value
    # (I don't think it makes much sense I found this empirically).
    length_factor = math.pow((math.sqrt(length) / length), 1.6)

    # If there is a lot of horizontal space for the text, the font will be big,
    # but if there is a lot of char to write it will be smaller.
    font_size = width * length_factor

    # This way the font is not too high
    if font_size > height:
        font_size = height * 0.9

    return int(font_size)

A preview of what it looks like:

Firstly I'd simplify your maths:

$$
\text{font_size} = \text{width} * (\frac{\sqrt{\text{length}}}{\text{length}}) ^ {1.6}\\
(\frac{\sqrt{x}}{x})^{1.6} = \frac{1}{x^{0.8}}\\
\text{font_size} = \frac{\text{width}}{\text{length}^{0.8}}
$$

After this we're left with your if, personally I think using min would be better here, min(font_size, height * 0.9).
That way we know the maximum is \$\text{height} * 0.9\$ rather than \$\text{height}\$, and makes the font_size not jump.
This is up to you, but a jump in the font size is ugly in my opinion.

If we look at the affect of not using min and using min:

>>> balanced_text_size_button(1, 89, 100)
89
>>> balanced_text_size_button(1, 91, 100)
91
>>> balanced_text_size_button(1, 100, 100)
100
>>> balanced_text_size_button(1, 101, 100)
90
>>> balanced_text_size_button_min(1, 89, 100)
89
>>> balanced_text_size_button_min(1, 91, 100)
90
>>> balanced_text_size_button_min(1, 100, 100)
90
>>> balanced_text_size_button_min(1, 101, 100)
90

The above makes much more sense.
And so I'd change your function to:

def balanced_text_size_button(length, width, height):
    return int(min(width / math.pow(length, 0.8), height * 0.9))

And if you want to keep your description I'd use comments.
I wouldn't use a doc-string as the implementation details aren't needed by the end user.
I'd either use a heavy comment like you did:

def balanced_text_size_button(length, width, height):
    # Decide the font size by getting a desired with and height font size.
    # For text to not go out of the box, the smallest of the two wanted sizes is taken.
    # The width size is found by dividing the width by an exponential of the text.
    # An exponent is used to have a reduced affect on larger values.
    # The exponent 0.8 seems to give the best results.
    # The height is decided by picking a font size of 90% of it.
    return int(min(width / math.pow(length, 0.8), height * 0.9))

Or as the code is easy to understand, you can just say why you're using a magic variable.

def balanced_text_size_button(length, width, height):
    # The exponent 0.8 seems to give the best results.
    return int(min(width / math.pow(length, 0.8), height * 0.9))


Generating a unique ID for a filename This function generates a unique id for my files, which will be stored in the database to reference them. It returns the id if unique, if not, it generates a new one. My separate file server can then use these ids to locate and retrieve a file.

I'm planning on storing thousands upon maybe millions of files uploaded by users in the future, so this needs to be robust and futureproof.

from django.utils.crypto import get_random_string
from .models import Media

def generateUID():
    uid = get_random_string(length=16, allowed_chars=u'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789')
    date = datetime.datetime.now()

    result = '%s-%s-%s_%s' % (date.year, date.month, date.day, uid)
    print(result)

    try:
        obj = Media.objects.get(uid=result)
    except Media.DoesNotExist:
        return uid
    else:
        return generateUID()

The Media model is a parent which stores the uid. There is an image model that Media can relate to.

For example:

Media uid = 'test':

Image name = 't200x200'
Image name = 'original'

When the files are created, they are stored like this:

Let's say the ID is, for example:

2016-9-14_cKYT96osstPB8z2F

and the filename for the file that we want to get is:

avatars_2016-9-14_cKYT96osstPB8z2F_t200x200.png

Then the file would be saved like this in my file server:

media/avatars/2016/9/14/c/K/Y/cKYT96osstPB8z2F/t200x200.png

This ensures that there will be no collisions, and the file system is split and doesn't have thousand of files in one folder, which will damage performance.

Is there any way I can make this perform better or be more reliable? Avoiding collisions and performance issues is a must.

Code review:

Well, your code seems ok, it can be improved:

You can replace the letters by string.ascii_letters
You can remove obj since it is not used.
You can format your date using the format method, i.e. ˋ"{0:%Y/%j}".format(date)`.  That way, you can have a directory by year and a subdirectory by day in the year.

Analyze:

Instead of creating an UID and then writing a file, I usually process in reverse order and use tempfile.mkstemp.

  [It] Creates a temporary file in the most secure manner possible…

That way, you avoid collisions. Then, I use the newly created file name as an ID.

You speak about performance: note that the more you have subdirectories, the more you have inodes. This can decrease performance when you want to access the files.

To summarize:

Create a directory for each day using the format "{0:%Y/%j}".format(date)
Create a temporary file in that directory
Use the relative path and the filename to construct your UID. For instance, replace "/" and dots by underscore.

Generating UUID

If, for any reason, you can't rely on the file system temporary files, and you must create an UID yourself, I suggest you to consider using UUIDs (Universally Unique IDentifier).

See the Python module uuid available for Python 2 and 3.

For instance, you can use uudi.uuid1:

  Generate a UUID from a host ID, sequence number, and the current time. If node is not given, getnode() is used to obtain the hardware address. If clock_seq is given, it is used as the sequence number; otherwise a random 14-bit sequence number is chosen.

Example:

>>> import uuid

>>> # make a UUID based on the host ID and current time
>>> uuid.uuid1()
UUID('a8098c1a-f86e-11da-bd1a-00112444be1e')

If you want folders, you only need to replace "-" by "/".


Using goto with DataReader to get sproc return value I want to get a second-opinion on my use of goto.

SqlCommand and SqlDataReader only read the RETURN-value of a Stored Procedure after the SqlDataReader has been closed. This is a problem if you want to interrogate the return-value to make a decision regarding how you want to read the data.

In my case, the stored procedure I'm calling returns multiple output data tables followed by an integer return value. The number of output data tables is variable.

// ret is a POCO domain entity object: a strongly-typed representation of the sproc's returned data
using( DbDataReader rdr = cmd.ExecuteReader() ) {

    if( !rdr.Read() )
        goto readReturnValue;

    ret.Foo  = ReadFoo( rdr );

    //////////

    if( !rdr.NextResult() )
        goto readReturnValue;

    List<Bar> bars = new List<Bar>();
    while( rdr.Read() ) bars.Add( ReadBar( rdr ) );
    ret.Bars = bars.ToArray();

    //////////

    if( !rdr.NextResult() )
        goto readReturnValue;

    ret.Qux = ReadQux( rdr );

    //////////

    if( !rdr.NextResult() )
        goto readReturnValue;

    List<Blargh> blarghs = new List<Blargh>();
    while( rdr.Read() ) blarghs.Add( ReadBlargh( rdr, ) );
    ret.Blarghs = blarghs.ToArray();

    // repeat a few more times...
}

readReturnValue:
Int32 returnValue = (Int32)returnParameter.Value;
switch( returnValue ) {
    case 0: // do stuff
    case 1: // do other stuff
    case ...
}

The first alternative that comes to mind is to remove the negation operator (!) from each if( !rdr.NextResult() ) and move each subsequent operation to a branch under the if, but this results in code many layers deep as there's about 8 or more result sets.

Another alternative is to replace goto readReturnValue with a throw and throw my own custom exception, e.g. throw new NoNextResultException() and in the catch block that surrounds the using I would swallow the exception and have the return-value interrogation code in the finally block, or in code immediately following the try block:

try {
    using( DbDataReader rdr = cmd.ExecuteReader() ) {

        if( !rdr.Read() )
            throw new NoNextResultException();

        ret.Foo  = ReadFoo( rdr );
        ...
    }
} catch(NoNextResultException) {
}
Int32 returnValue = (Int32)returnParameter.Value;
switch( returnValue ) {
...

But the problem with that is that throw statements don't define where the exception lands: so removing the catch statement means the program will compile, but crash due to an unhandled exception when it runs, whereas removing the goto label readReturnValue means the program won't compile, which is safer. Furthermore it avoids the expensive cost of throwing and catching exceptions as well as sticking to the mantra of "use exceptions for exceptional circumstances, not for program flow" - which is what it would be if I did convert it to a try/throw/catch.

Is my use of goto then justified?

Is my use of goto then justified?

First of all, let me push back on the question. A goto does not require a justification any more than any other language feature requires a justification.

That said, a goto is widely considered to be a sign that the code is inelegant, confusing or hard to maintain.  It is definitely a sign that you should be thinking hard about how the control flow of the code works, and whether there is a refactoring that would make it more clear.

You are doing that, and that's excellent.  The problem is that you've only identified two alternatives to a goto: refactoring into nested "if" statements, which as you note may be harder to read than the goto version, and using "throw" to simulate a goto. That's a bad practice; throw should be used to indicate an unexpected error condition, not as a very expensive way to simulate a goto.

You missed the preferred way to remove a goto: turn it into a return.

void DoTheFirstThing()
{
  using( DbDataReader rdr = cmd.ExecuteReader() )
  {
    if( !rdr.Read() ) return;
    ret.Foo  = ReadFoo( rdr );
    if( !rdr.NextResult() ) return;
    List<Bar> bars = new List<Bar>();
    while( rdr.Read() ) bars.Add( ReadBar( rdr ) );
    ret.Bars = bars.ToArray();
    if( !rdr.NextResult() ) return;
    ret.Qux = ReadQux( rdr );
    if( !rdr.NextResult() ) return;
    List<Blargh> blarghs = new List<Blargh>();
    while( rdr.Read() ) blarghs.Add( ReadBlargh( rdr, ) );
    ret.Blarghs = blarghs.ToArray();
    ...
   }
}

void DoTheSecondThing()
{
  Int32 returnValue = (Int32)returnParameter.Value;
  switch( returnValue ) {
    case 0: // do stuff
    case 1: // do other stuff
    case ...
  }
  ...
}

void DoTheThings()
{
  DoTheFirstThing();
  DoTheSecondThing();
}

There, no gotos required, and your program is now refactored into smaller methods that each do one task well, rather than one god method that tries to create the whole universe in one go.

While we are criticizing your code, I note that this also looks a bit dodgy:

    if( !rdr.NextResult() ) return;
    List<Blargh> blarghs = new List<Blargh>();
    while( rdr.Read() ) blarghs.Add( ReadBlargh( rdr, ) );
    ret.Blarghs = blarghs.ToArray();

Suppose NextResult is false, and so we take the return. What now is the value of the blarghs field of object ret?  Is it null?  Is it intended to be null?  Is the user of this field supposed to understand that it can and will be null if the reader ran out of results, and that if it is not null, then it is a non-empty array?  This is a lousy contract. It is much better to say "blarghs will be a non-null array that might be empty", and not "blarghs is either null or a non-empty array".  I would be inclined to re-think your deserialization strategy here so that more of the deserialized object is in a good state:

IEnumerable<Bar> ReadBars(Reader rdr)
{
    if( !rdr.NextResult() ) yield break;
    while( rdr.Read() )
      yield return ReadBar( rdr );
}

IEnumerable<Blargh> ReadBlarghs(Reader rdr)
{
    if( !rdr.NextResult() ) yield break;
    while( rdr.Read() )
      yield return ReadBlargh( rdr );
}

void DoTheFirstThing()
{
  using( DbDataReader rdr = cmd.ExecuteReader() )
  {
    // Move the check for the goodness of the reader into ReadFoo,
    // readQux, etc.

    ret.Foo  = ReadFoo( rdr );
    ret.Bars = ReadBars( rdr ).ToArray();
    ret.Qux = ReadQux( rdr );
    ret.Blarghs = ReadBlarghs ( rdr ).ToArray();
   }
}

OMG look at how much better that code reads now.

BUT WAIT THERE'S MORE. Let's make this an extension method and parameterize it with a function:

static class Extensions
{

  public static IEnumerable<T> ReadThings<T>(this Reader rdr, Func<Reader, T> f)
  {
    if( !rdr.NextResult() ) yield break;
    while( rdr.Read() )
      yield return f( rdr );
  }
  public static Foo ReadFoo(this Reader rdr)
  {
     if (!rdr.Read) return DefaultFoo;
     ...
  }
  // Similarly for ReadQux ...
}
...
void DoTheFirstThing()
{
  using( DbDataReader rdr = cmd.ExecuteReader() )
  {
    ret.Foo  = rdr.ReadFoo();
    ret.Bars = rdr.ReadThings(ReadBar).ToArray();
    ret.Qux = rdr.ReadQux();
    ret.Blarghs = rdr.ReadThings(ReadBlargh).ToArray();
  }
}

Isn't that about a million times nicer to read than what you wrote?  Look at how in this code the meaning shines through. In your code it looks like the most important thing is the reader and managing whether it is done or not. In this code it looks like the most important thing is that we are reading a Foo, some Bars, a Qux and some Blarghs.  Which way do you think will be easier to understand and maintain?

We've used higher level functions and extension methods for the win. You could be making this code tiny and super easy to read, compared to its present enormous sprawling repetitive goto-laden spaghetti.

Think about where this refactoring gets you. Now if you want to someday in the future say hey, you know, I actually only want to deserialize the frobby bars:

    ret.Bars = rdr.ReadThings(ReadBar).Where(bar => IsFrobby(bar)).ToArray();

DONE.

Or, you know what, we serialized out a bunch of bars, but what we need in memory is actually a bunch of fubars:

    ret.Fubars = rdr.ReadThings(ReadBar).Select(bar => MakeFubar(bar)).ToArray();

Nice. You want to make a change like that, you make it in one place with clear, self-documenting code.

And now you see the true power of thinking "is this goto a bad idea?"  By thinking it through carefully you can take the intuition that the goto is inelegant and manage to refactor your program into something that is small, powerful, and cheap to change when requirements change. So by all means, keep on thinking about whether those gotos are inelegant -- just think the problem all the way through, rather than stopping on some not-actually-better solution like using a throw or a break or a continue to simulate a goto.


Consuming chunks from ConcurrentQueue I need to implement a queue of requests which can be populated from multiple threads. When this queue becomes larger than 1000 completed requests, these requests should be stored into a database.

public class RequestQueue
{
    private static BlockingCollection<VerificationRequest> _queue = new BlockingCollection<VerificationRequest>();
    private static ConcurrentQueue<VerificationRequest> _storageQueue = new ConcurrentQueue<VerificationRequest>();

    private static volatile bool isLoading = false;
    private static object _lock = new object();

    public static void Launch()
    {
        Task.Factory.StartNew(execute);
    }

    public static void Add(VerificationRequest request)
    {
        _queue.Add(request);
    }

    public static void AddRange(List<VerificationRequest> requests)
    {
        Parallel.ForEach(requests, new ParallelOptions() {MaxDegreeOfParallelism = 3},
            (request) => { _queue.Add(request); });
    }

    private static void execute()
    {
        Parallel.ForEach(_queue.GetConsumingEnumerable(), new ParallelOptions {MaxDegreeOfParallelism = 5}, EnqueueSaveRequest );
    }

    private static void EnqueueSaveRequest(VerificationRequest request)
    {
        _storageQueue.Enqueue( new RequestExecuter().ExecuteVerificationRequest( request ) );
        if (_storageQueue.Count > 1000 && !isLoading)
        {
            lock ( _lock )
            {
                if ( _storageQueue.Count > 1000 && !isLoading )
                {
                    isLoading = true;

                    var requestChunck = new List<VerificationRequest>();
                    VerificationRequest req;
                    for (var i = 0; i < 1000; i++)
                    {
                        if( _storageQueue.TryDequeue(out req))
                            requestChunck.Add(req);
                    }
                    new VerificationRequestRepository().InsertRange(requestChunck);

                    isLoading = false;
                }
            }
        }
    }
}

Is there any way to implement this without lock and isLoading?

Static class

As proposed by eurotrash I would not implement the class as static class because it has some disadvantages:

It is only possible to use one class per application
It is not possible to mock the class (e.g. for unit test / alternative implementations)
It is not possible to use it with DI.
It is not very common to have a statefull static classes - therefore it may confuse other developer

Naming

isLoading should be renamed to _isLoading
execute should be renamed to Execute or even better to some more descriptive name (e.g. StartConsumingTask)

Logic

  Is there any way to implement this without lock and isLoading?

Currently your solution uses up to 5 tasks that process the items from the _queue and put them into the _storageQueue. If the _storageQueue has more than 1000 items, one of the 5 tasks writes them to the repository.

If the last part (write the items to the repository) is executed by a separate single task, the lock and the isLoading flag could be dropped.

The lock and the isLoding flag can be dropped if the last part (writing the items to the repository)

Tasks

If you have long running tasks (like the one in the method Launch), it is better to start it with option TaskCreationOptions.LongRunning. Otherwise the thread for the task is taken from the threadpool and therefore blocks them for executing short-running procedures.
_queue.Add (in method AddRange) is such a fast operation. I don't see a reason why to use Parallel.For here - just add the item in the current thread.
Parallel.For in method execute makes sense if ExecuteVerificationRequest is realy time consuming - otherwise it adds only overhead and complexity.

Code with the suggestions above applied:

public class RequestQueue
{
    private BlockingCollection<VerificationRequest> _queue = new BlockingCollection<VerificationRequest>();
    private ConcurrentQueue<VerificationRequest> _storageQueue = new ConcurrentQueue<VerificationRequest>();

    private RequestQueue() { }

    public void Launch()
    {
        Task.Factory.StartNew(StartConsumingTask);
        Task.Factory.StartNew(StartPersistingTask);
    }

    public void Add(VerificationRequest request) => _queue.Add(request);
    public void AddRange(List<VerificationRequest> requests) => requests.ForEach(r => Add(r));

    private void StartConsumingTask()
    {
        Parallel.ForEach(_queue.GetConsumingEnumerable(), new ParallelOptions { MaxDegreeOfParallelism = 5 }, EnqueueSaveRequest);
    }

    private void EnqueueSaveRequest(VerificationRequest request)
    {
        _storageQueue.Enqueue(new RequestExecuter().ExecuteVerificationRequest(request));
    }

    private async Task StartPersistingTask()
    {
        while (true)
        {
            if (_storageQueue.Count > 1000)
            {
                var requestChunck = new List<VerificationRequest>();
                VerificationRequest req;
                for (var i = 0; i < 1000; i++)
                {
                    if (_storageQueue.TryDequeue(out req))
                        requestChunck.Add(req);
                }
                new VerificationRequestRepository().InsertRange(requestChunck);
            }
            else
            {
                await Task.Delay(100);
            }
        }
    }

    private static RequestQueue _instance = new RequestQueue();
    public static RequestQueue Instance => _instance;
}


Getting functional Common Lisp code for handling state in a SDL animation The following code draws a red rectangle bouncing between the borders of a white display. I'm not particularly happy with the update function:

(require 'lispbuilder-sdl)

(defun update-h-speed (state h-border top-left-border)
  (if (or (< (cdr (assoc 'h-coord state)) top-left-border) ;;if too left
      (> (cdr (assoc 'h-coord state)) h-border))       ;;if too right
      ;; negate the horizontal speed
      (acons 'h-speed (- (cdr (assoc 'h-speed state))) state)
      state))

(defun update-v-speed (state v-border top-left-border)
  (if (or (< (cdr (assoc 'v-coord state)) top-left-border) ;;if too high
      (> (cdr (assoc 'v-coord state)) v-border))       ;;if too low
      ;; negate the vertical speed
      (acons 'v-speed (- (cdr (assoc 'v-speed state))) state)
      state))

(defun update-coords (state)
  (acons 'h-coord (+ (cdr (assoc 'h-coord state))
               (cdr (assoc 'h-speed state)))
       (acons 'v-coord (+ (cdr (assoc 'v-coord state))
                  (cdr (assoc 'v-speed state))) state)))

(defun update (state width height size)
  (let ((h-border (- width (/ size 2)))
    (v-border (- height (/ size 2)))
    (top-left-border (/ size 2)))
    (update-coords
     (update-h-speed
      (update-v-speed state v-border top-left-border) h-border top-left-border))))

(defun game (&optional (width 320) (height 240) (speed 2) (size 20))
  (let ((decoy (pairlis (list 'h-coord 'v-coord 'h-speed 'v-speed)
            (list (/ width 2) (/ height 2) speed speed))))
    (sdl:with-init ()
      (sdl:window width height :title-caption "My game")
      (setf (sdl:frame-rate) 60)
      (sdl:with-events ()
    (:quit-event () t)
    (:key-down-event (:key key)
             (when (sdl:key= key :sdl-key-escape) (sdl:push-quit-event)))
    (:idle ()
           ;; update state
           (setq decoy (update decoy width height size))
           (sdl:clear-display sdl:*white*)
           ;; draw the rectangle according to the updated state
           (sdl:draw-box (sdl:rectangle-from-midpoint-*
                  (cdr (assoc 'h-coord decoy)) (cdr (assoc 'v-coord decoy)) size size)
                 :color sdl:*red*)
           (sdl:update-display))))))

In fact, the big-bang function in Racket made such things quite easy. With big-bang, I usually created a structure to hold every object (just coordinates and speeds of the rectangles) and modified each part of the structure with separate functions.

Please note that this is not a question about making this animation work.

1) I would like to get advice about, how to refactor such programs to make the update function more functional, so that it is easier to expand (add new features) and debug.

2) I'm particularly confused about whether I should prefer special variables to hold the structures, or prefer to create them locally as is the case. Do you prefer one over the other during different cycles of programming (like development and distribution)?

Note: I preferred an assoc list in place of a hash table, because of the few number of pairs, and the acons enables a sort of history feature, if this thing will ever going to work.

I would use CLOS for that. The game state is an CLOS object then. If the thing needs a history, then I would add the history to the CLOS object.

Named slots of something in the history of Lisp:

assoc lists (ca. 1960)
hash-tables
structures (70s)
classes (70s/80s...)

If you look at your update a few things don't look nice:

progn is not needed
way to many SETQs, construct a return value instead
the use of an association list, where a CLOS object should have been used
no explicit return value

(defun update-coords (state)
  (acons 'h-coord (+ (cdr (assoc 'h-coord state))
                     (cdr (assoc 'h-speed state)))
         (acons 'v-coord (+ (cdr (assoc 'v-coord state))
                            (cdr (assoc 'v-speed state)))
                state)))

Sometimes I would want to get rid of the nesting in above function.

(defun update-coords (state)
  (list* (cons 'h-coord (+ (cdr (assoc 'h-coord state))
                           (cdr (assoc 'h-speed state))))
         (cons 'v-coord (+ (cdr (assoc 'v-coord state))
                           (cdr (assoc 'v-speed state))))
         state))

Alternatively you can use the backquote notation. , evaluates. ,@ evaluates and splices the result in.

(defun update-coords (state)
  `((h-coord . ,(+ (cdr (assoc 'h-coord state))
                   (cdr (assoc 'h-speed state))))
    (v-coord . ,(+ (cdr (assoc 'v-coord state))
                   (cdr (assoc 'v-speed state))))
    ,@state))

I would add Practical Common Lisp by Peter Seibel to the reading list. It teaches a larger subset of more idiomatic Common Lisp than for example On Lisp.

With CLOS the code looks much simpler. Example without history:

(defclass game-state ()
  (h-coord v-coord h-speed v-speed))

(defmethod update-coords ((state game-state))
  (with-slots (h-coord h-speed v-coord v-speed)
      state
    (incf h-coord h-speed)
    (incf v-coord v-speed))
  state)


Calculating factorial using Stirling's approximation I've used Stirling's approximation to compute a factorial but I want to know if it is a cleaner and more concise way to solve this kind of problem.

Here is my code:

from numba import jit
from decimal import Decimal
from math import pi

getcontext().prec = 128

@jit
def stirling(n):
    return Decimal((2.0*n+1.0/3.0)*pi).sqrt()*Decimal(n**n)/Decimal(n).exp()

if __name__ == "__main__":
    print(stirling(255144))

Also , how can I get rid off decimal.Overflow error?

The biggest problem of your code (while being very short itself) is that hard to read and complicated formula. One way to improve readability of the formula is by using meaningful variables to name parts of the formula. This also makes it easier to find errors, because you can first look in what part of the formula the error occurs, and debug more easily.

Furthermore, adding spaces around operators inside the formula makes it more readable.

However, Python already has a solution for that in the standard library. Since your question implies that your goal is not to implement Stirling's approximation, but rather a pythonic solution, I suggest the following:

from math import factorial

print(factorial(1337))

This is probably the most pythonic way of doing it. Using math.factorial from the standard library, your code becomes more readable and you get around hard to find errors by avoiding complicated formulas.


Count Characters Function PHP As part of studying algorithms, I needed to make a function to count occurrences of characters in a string. My solution is below. I'd like some feedback about how I did - could the implementation be cleaner? Are there any conceptual gaps my code suggests?

<?php
function ra_count_chars($str){
    $dict = str_split(strtolower(str_replace(' ', '', $str)));

    foreach($dict as $key=>$value){
        $dict[$value] = 0;
        unset($dict[$key]);
    }

    for($i = 0; $i < strlen($str); $i++){
        $dict[$str[$i]] += 1;
    }

    return $dict;
}

print_r(ra_count_chars('ccaaat'));

You can do it with a more reduced code, taking advantage of the PHP count_chars() function:

function ra_count_chars($str) {
    foreach (count_chars(str_replace(' ', '', $str), 1) as $char => $count) {
        $result[chr($char)] = $count;
    }
    return $result;
}

This method has pros and cons:

pro: the characters are alphabetically sorted in $result
pro or con (depends on your need): upper- and lower-case are counted separately

In the other hand, as noticed by @insertusernamehere, this doesn't work for multibyte characters.

Last point: due to the above limitation, you might choose to omit not only spaces but also any character other than A-Z and a-z.
To achieve it merely change str_replace(' ', '', $str) into preg_replace('/[^A-za-z]/', '', $str).


Program that finds the longest word not containing one of the disallowed characters Problem definition

Find the longest word that doesn't contain any of the following characters:

gkmqvwxz

Input comes from a file named words.txt and contains one word per line. A word is anything that is not a whitespace.

The twist

My C++ implementation posted below is surprisingly slow, taking 1.7 seconds to run, whereas my javascript implementation (link, will obviously be slower because it's online) takes only 55ms. Is it possible to somehow optimize my C++ implementation?

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdint>

#include "TimeUtil.h"

int main()
{
    uint64_t begin_time = currentTimeNanoseconds();

    std::string longestAcceptableWord; // Variable to contain the longest word

    std::string currentLine;
    const char badLetters[] = { 'g', 'k', 'm', 'q', 'v', 'w', 'x', 'z' };

    std::ifstream in;
    in.open("words.txt");
    while (!in.eof()) // Loop through the entire file (466 544 lines, 4 749 kB).
    {
        getline(in, currentLine);

        if (currentLine.length() <= longestAcceptableWord.length())
        {
            continue;
        }

        // If the word contains one of the bad letters, don't accept it.
        for (unsigned int i = 0; i < sizeof(badLetters); i++)
        {
            if (currentLine.find(badLetters[i]) != std::string::npos)
            {
                continue;
            }
        }

        // If the word is longer than the current longest word found,
        // and doesn't have any bad letters, make it the new longest
        // word found.
        longestAcceptableWord = currentLine;
    }
    in.close();

    std::cout << "[" << (double) ((currentTimeNanoseconds() - begin_time) / 1000) / 1000.0f << "ms] " << longestAcceptableWord << std::endl;

    return 0;
}

I see a number of things that may help you improve your program.

Fix the bug

There is a subtle bug in the original implementation.  It contains these lines:

// If the word contains one of the bad letters, don't accept it.
for (unsigned int i = 0; i < sizeof(badLetters); i++) {
    if (currentLine.find(badLetters[i]) != std::string::npos) {
        continue;
    }
}

The intent is, of course, to escape the for loop and go on if a bad letter is found in a candidate word.  However, what actually happens is that first letter is checked, and the loop continues no matter if the letter was found or not.  That's a bug and one reason I don't much like continue.  It's too easy to make this kind of error.

Don't loop on eof()

It's almost always incorrect to loop on eof() while reading a file.  The reason is that the eof indication is only set when an attempt is made to read something from the file when we're already at the end.  So instead of this:

while (!in.eof()) {
    getline(in, currentLine);
    // ...
}

write this:

while (getline(in, currentLine)) {
    // ...
}

See this question for more details on why using eof is usually wrong.

Initialize variables on declaration

The best practice is to initialize variables as soon as they're created.  In C++, this most often means initializing them in the same line as the declaration.  So instead of this:

std::ifstream in;
in.open("words.txt");

write this:

std::ifstream file2{wordsFile};

Note, too, that I use the C++11 uniform initializer syntax (with the {}) to make it clear to both the compiler and the reader that this is an initialization and not a function call.  See Stroustrup's description for more details on that.

Allow the user to specify input files

The words file name is currently hardcoded which certainly greatly restricts the usefulness of the program.  Consider using argc and argv to allow the user to specify file names on the command line.

Prefer newer structures to plain arrays

Instead of a plain array as with badLetters, one could instead use an std::array or std::string.  If your compiler has C++17 support, std::string_vew might be an even better choice.

const std::array<char, 8> badLetters = { 'g', 'k', 'm', 'q', 'v', 'w', 'x', 'z' };

Use standard algorithms

Instead of searching with a for loop for all badLetters, we can use std::find_first_of() instead.  The result would look like this:

while (getline(in, currentLine)) {
    if (currentLine.length() > longestAcceptableWord.length()
        && (std::find_first_of(currentLine.begin(),
                            currentLine.end(),
                            badLetters.begin(),
                            badLetters.end()) == currentLine.end())
    ) {
        longestAcceptableWord = currentLine;
    }
}

Note that I prefer to avoid continue and instead rely on the short-circuit evaluation of the if clauses to cause the same effect.

Don't use std::endl if you don't really need it

The difference between std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream.  This can be time-consuming in a program with a lot of I/O and is rarely actually needed.  It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one.  Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.


Finding the similarity between the two movies using Pearson correlation coefficient I am trying to find the similarity between the two movies using Pearson correlation coefficient. The programs is working well for small inputs but for large inputs (like 100000 lines) it takes forever. My professor said it would take few minutes, but my program is executing forever.

The input format: user|movie|rating.

If two or more users watch two movies, we will find similarity between them based on rating.

# -*- coding: utf-8 -*-
"""
Created on June 06, 2016

@author: Praveen Allam
"""

from mrjob.job import MRJob
from mrjob.step import MRStep
from itertools import combinations
from itertools import izip
from math import sqrt

class PearsonCorrelation(MRJob):
    def steps(self):
        return [
            MRStep(mapper=self.mapper1,
                  reducer=self.reducer1),
            MRStep(mapper=self.mapper2,
                  reducer=self.reducer2)
        ]

    def mapper1(self, _, line):

        ##yield each line to first mapper
        user,movie,rating=line.split('|')
        yield None,[user,movie,rating]

    def reducer1(self, _, value):

        ##yield all combinations to second mapper
        for item1,item2 in combinations(value,2):
            yield item1,item2

    def mapper2(self,value1,value2):

        ##yield movie1,movie2 and corresponding ratings of user.
        if(value1[0]==value2[0]):
            yield [value1[1],value2[1]],[float(value1[2]),float(value2[2])]

    def reducer2(self,movies,ratings):
        rating=[]
        for item in ratings:
            rating.append(item)

        ##extract using izip only if there are more than one instance.
        if(len(rating)>1):
            v1,v2=izip(*rating)

            ##calculate the pearson coefficient
            corr=self.pearsonCoefficient(v1,v2)

            ##yield the result
            yield "The Similarity between "+movies[0]+" and "+movies[1]+" is: " , corr
    def pearsonCoefficient(self,a,b):
        n=len(b)
        value=range(n)

        #sums of individual lists
        sum_x=sum([float(a[i]) for i in value])
        sum_y=sum([float(b[i]) for i in value])

        #sum of the squares of each lists
        sum_xSq=sum([a[i]**2.0 for i in value])
        sum_ySq=sum([b[i]**2.0 for i in value])

        #sum of the products
        sumP=sum([a[i]*b[i] for i in value])

        #Calculate Pearson coefficient
        numerator=sumP-(sum_x*sum_y/n)
        denominator=((sum_xSq-pow(sum_x,2)/n)*(sum_ySq-pow(sum_y,2)/n))**0.5

        if denominator == 0: return 1

        result=numerator/denominator
        return result

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

So many problems!

All the outputs of mapper1 have the same key, so the first mapping step is wasted.
reducer1 generates all pairs of records, but most of these pairs will be worthless because they have different users and so will be discarded by mapper2
The similarity between movie A and movie B can end up being computed twice on half the data.

These problems are really easy to see if you work through a simple example by hand to see what your code will do.

For example, suppose the data is:

Haruko|Koyaanisqatsi|8
Natsuko|Powaqqatsi|9
Haruko|Powaqqatsi|7
Natsuko|Koyaanisqatsi|10
Natsuko|Naqoyqatsi|8
Haruko|Naqoyqatsi|6

Then mapper1 generates the following key–value pairs:

Key   Value
----  --------------------------------
None  ['Haruko', 'Koyaanisqatsi', 8]
None  ['Natsuko', 'Powaqqatsi', 9]
None  ['Haruko', 'Powaqqatsi', 7]
None  ['Natsuko', 'Koyaanisqatsi', 10]
None  ['Natsuko', 'Naqoyqatsi', 8]
None  ['Haruko', 'Naqoyqatsi', 6]

Since these all have the same key (None) all the values get collected into a single list and passed to one instance of reducer1. So the mapping step was wasted — there's no parallelism here.

Next, reducer1 generates the following key–value pairs:

Key                                Value
--------------------------------   --------------------------------
['Haruko', 'Koyaanisqatsi', 8]     ['Natsuko', 'Powaqqatsi', 9]
['Haruko', 'Koyaanisqatsi', 8]     ['Haruko', 'Powaqqatsi', 7]
['Haruko', 'Koyaanisqatsi', 8]     ['Natsuko', 'Koyaanisqatsi', 10]
['Haruko', 'Koyaanisqatsi', 8]     ['Natsuko', 'Naqoyqatsi', 8]
['Haruko', 'Koyaanisqatsi', 8]     ['Haruko', 'Naqoyqatsi', 6]
['Natsuko', 'Powaqqatsi', 9]       ['Haruko', 'Powaqqatsi', 7]
['Natsuko', 'Powaqqatsi', 9]       ['Natsuko', 'Koyaanisqatsi', 10]
['Natsuko', 'Powaqqatsi', 9]       ['Natsuko', 'Naqoyqatsi', 8]
['Natsuko', 'Powaqqatsi', 9]       ['Haruko', 'Naqoyqatsi', 6]
['Haruko', 'Powaqqatsi', 7]        ['Natsuko', 'Koyaanisqatsi', 10]
['Haruko', 'Powaqqatsi', 7]        ['Natsuko', 'Naqoyqatsi', 8]
['Haruko', 'Powaqqatsi', 7]        ['Haruko', 'Naqoyqatsi', 6]
['Natsuko', 'Koyaanisqatsi', 10]   ['Natsuko', 'Naqoyqatsi', 8]
['Natsuko', 'Koyaanisqatsi', 10]   ['Haruko', 'Naqoyqatsi', 6]
['Natsuko', 'Naqoyqatsi', 8]       ['Haruko', 'Naqoyqatsi', 6]

You can see that most of the output of this step is useless because it consists of records for different users.

Then the mapper2 step filters key–value pairs that have the same user, getting:

Key                               Value
-------------------------------   --------
['Koyaanisqatsi', 'Powaqqatsi']   [8, 7]
['Koyaanisqatsi', 'Naqoyqatsi']   [8, 6]
['Powaqqatsi', 'Koyaanisqatsi']   [9, 10]
['Powaqqatsi', 'Naqoyqatsi']      [9, 8]
['Powaqqatsi', 'Naqoyqatsi']      [7, 6]
['Koyaanisqatsi', 'Naqoyqatsi']   [10, 8]

The values are collected under the different keys and passed to four instances of reducer2:

Key                               Values
-------------------------------   -----------------
['Koyaanisqatsi', 'Powaqqatsi']   [[8, 7]]
['Koyaanisqatsi', 'Naqoyqatsi']   [[8, 6], [10, 8]]
['Powaqqatsi', 'Koyaanisqatsi']   [[9, 10]]
['Powaqqatsi', 'Naqoyqatsi']      [[9, 8], [7, 6]]

Notice that there should be only three pairs of movies, but one of the pairs appears twice.

So, how should you go about fixing the code? Your best bet, I think, is to leave the code alone for the moment, and to work out (on paper, or in a text editor) exactly what the data needs to look like after each step, using a small example (like I did above). When you're happy with the design of each step, then it should be trivial to program it.

I recommend giving the mappers and reducers names that describe what they do. This will make the code easier to understand. See the examples in the MRJob documentation which have names like mapper_get_words and reducer_count_words.