Prime number segmented sieve I tried to solve the SPOJ prime number problem below. The code produced correct results, but Time limit exceeded and also memory need around 970M which is not efficient(?)

How can I optimize this code under a time constraint of around few seconds?

  Problem

  Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

  Input

  The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

  Output

  For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include <cmath>
#include <vector>
#include<iostream>
using namespace std;

void simplesieve(int limit, vector<int>&prime);

void segmentedsieve() {
    int T, M, K;

    cin >> T;

    for (int t = 0; t < T; t++) {
        cin >> M >> K;
        const int limit = floor(sqrt(K)) + 1;
        vector<int> prime;
        simplesieve(K, prime);

        bool *mark = new bool[K - M];
        memset(mark, true, sizeof(bool)*(K-M));

        vector<int>::iterator it;

        for (it = prime.begin(); *it<limit; it++) {

            int lolim = floor(M / (*it))*(*it);
            if (lolim < M)
                lolim = lolim + (*it);

            for (int j = lolim; j < K; j += (*it))
            {   if(j!=*it)
                mark[j - M] = false;
            }

        }

        for (int i = M; i < K; i++) {
            if (mark[i - M] == true)
                cout << i << "\n";
        }

        delete[] mark;
    }

}

void simplesieve( int limit, vector<int>&prime) {

    bool *mark=new bool[limit + 1];

    memset(mark, true, sizeof(bool)*(limit+1));
    for (int p = 2; p*p < limit; p++) {
        if (mark[p] == true) {
            for (int i = p * 2; i < limit; i += p)
                mark[i] = false;
        }
    }
    for (int p = 2; p < limit; p++) {
        if (mark[p] == true)
        {
            prime.push_back(p);

        }

    }

}

int main()
{
    int n = 100;
    segmentedsieve();
    return 0;
}

You are computing your prime sieve multiple times, when you only need to compute it once.  You are told you will have at most 10 test cases.  You could easily store those in an array, compute the maximum upper limit, and run the sieve once.  Then loop through the stored test cases, and generate the output for each.  Could be up to a 10x speed up.
The only even prime is 2.  Treat it as a special case.  Then, when you are running the sieve, you can start with 3 and increment with p += 2 to skip the even numbers.
Since the sieve has already eliminated all multiples of smaller prime numbers, when eliminating the multiples of p, you don’t have to start at p*2; rather you can start at p*p and skip the even multiples using i += p*2.  (Consider storing p2 = p*2 to avoid the multiplication every loop iteration!)
In segmentedsieve(), if the upper limit is less than largest prime your sieve produced, you don’t need to generate the second sieve; just emit the primes in the correct range.
You can apply points #2 & #3 to the secondary sieve, but it will be slightly more complicated as you need to ensure you’ve calculated an odd starting multiple.
To get a 8x reduction in memory usage, use a bit array.  (You could get a 16x reduction, by storing flags for only odd values in the bit array, but your indexing will become more complex.)


Counting primes in given interval So, here is a Hackerearth question, regarding (more or less) counting the number of primes between a given pair of numbers (up to 106).

Then there were 3 major options available to  me:

Trial division method, and its variants.
Sieve of Eratosthenes
Segmented sieve of Eratosthenes.

As learned from this answer.

The naive method  trial division, and its variants gave "Time Limit Exceeded" errors for about 70 % test cases.

Both the Sieve of Eratosthenes and its segmented version gave "Time Limit Exceeded" error for 60 % of the test cases.

Here is my code :

import java.util.* ;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;
/*
Trial division : failed. 6 points
Sieve of Eratosthenes : failed 8 points.
Segmented sieve of Eratosthenes : failed.  8 points.
*/
public class MoguLovesNumbers
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader bro = new BufferedReader(new InputStreamReader(System.in)) ;
        int T = Integer.parseInt(bro.readLine()) ;
        for(int t=0;t<T;t++)
        {
            String[] S = bro.readLine().split(" ") ;
            int l = Integer.parseInt(S[0]) ;
            int r = Integer.parseInt(S[1]) ;
            int temp = l<r?l:r ;
            r = l<r?r:l ;
            l = temp ;

            System.out.println(segmentedSieve(l,r)) ;
        }

    }
    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)
    {
        boolean[] mark = new boolean[r+1] ;
        int counter = 0 ;
        Arrays.fill(mark,true ) ;

        for(int i=2;i<r+1;i++)
        {
            if(mark[i])
            {
                if(i>=l)
                {
                    prime.add(i) ;
                    counter++ ;
                }
                for(int j=i*2;i*i<=r && j<r+1;j+=i)
                    mark[j] = false ;
            }
        }
        // return counter ;
    }
    static int segmentedSieve(int l,int n)
    {
        int limit = (int)Math.sqrt(n)+1 ;
        List<Integer> prime = new ArrayList<Integer>() ;
        sieveOfEratosthenes(0,limit,prime) ;
        int low = limit ;
        int high = limit*2 ;
        int count = 0 ;
        while(low<n)
        {
            if(high>n)
                high = n ;
            boolean mark[] = new boolean[limit+1] ;
            Arrays.fill(mark,true ) ;
            for(int i=0;i<prime.size();i++)
            {
                int loLim = (int)(Math.ceil((float)low/prime.get(i)))*prime.get(i) ;
                for(int j=loLim;j<=high;j+=prime.get(i))
                {
                    mark[j-low] = false ;
                }
            }
            for(int i = 0;i<mark.length;i++)
                if(mark[i] && (i+low>=l)&& (i+low<=high))
                {
                    count++ ;
                }
            low+=limit ;
            high+=limit ;
        }
        if(l<=Math.sqrt(n)+1)
        {
            for(int i=0;i<prime.size();i++)
                if(prime.get(i)>=l)
                    count++ ;
        }
        return count ;

    }
}

SUBMISSIONS:

Segmented Sieve
Simple Sieve
Naive trial division

Question:

How can this code be made more efficient? The Segmented Sieve and Simple Sieve both run in O(N log(log(N))) time.

Rethinking it

The obvious change that leaps out at me immediately is to make your list of primes into an object or even class field.  Then you don't need to recreate your primes each time.  You'd create it the first time.  Later you'd just extend it.  An object field would be better programming practice, but a class field would work for this problem.

You might even read in all the input first and then create the primes list once for all of them.  Or just build it to a million before processing the input.  Of course, that would fail if they have some tests where passing means not calculating all million.  Given your current algorithm, it would be easy enough to calculate all the primes from 0 to 1000 beforehand.

Consider holding the primes in a NavigableSet.  Because what you want to know is how many primes are in a range.  So you could replace

            System.out.println(segmentedSieve(l,r)) ;

with

            System.out.println(primes.subSet(l, r).size());

That counts the primes in the set [l, r) if primes is a NavigableSet holding at least all primes less than r.

If you need to count [l, r] or (l, r), you would use the longer version with booleans for inclusiveness.

Specific advice

    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)

You never call this with l as anything but 0.  So you might as well say

    static void sieveOfEratosthenes(int r, List<Integer> prime)

Then you can get rid of the check in the loop:

                if(i>=l)

That's always true if l is zero and i is at least 2.  You don't have to check it.

You don't need the counter variable.  As is, it's equal to prime.size() and you never use it.  Eliminating it saves an operation.  The compiler might do that for you, but you don't need it.

                for(int j=i*2;i*i<=r && j<r+1;j+=i)

This could be

                for (int j = i*i; j <= r; j += i)

You only need to check from i*i.  Anything smaller than that would already be marked.  For example, you already marked everything divisible by 2, so i*2 would be marked for all i greater than or equal to 1.

You only needed to check i*i<=r once.  This still does that check, as the first iteration j equals i*i.

The j<r+1 and j <= r are equivalent if j and r are integers.


Convert a number to text This converts a "numerical number" to a text representation, for example:

  convert 1234 --> "One Thousand, Two Hundred Thirty Four"

I'd like general feedback on how it could be make more readable or idiomatic.
There are a few specific points I'd like improved as well. The word lookup functions are a little messy. Each uses a different method of looking up the name depending on how the input relates to the desired name. If they could be generalized, it would be much neater.
It's also not that efficient. It requires a few reversals, all of which are necessary with my current technique; as far as I can tell.

import Data.Char
import Data.List

-- Global names
places  = ["","Thousand","Million","Billion","Trillion","Quadrillion","Quintillion"]
ones    = ["One","Two","Three","Four","Five","Six","Seven","Eight","Nine"]
teens   = ["Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
tens    = ["A 1 made it to getTens","Hundred","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]

-- Word lookup functions
getPlaceName :: Int -> String
getPlaceName place = places !! place

getOnes :: Char -> String
getOnes '0' = ""
getOnes n = let index = (digitToInt n) - 1 in
    ones !! index

getTeens :: String -> String
getTeens n = let r = read n :: Int in
    head $ [x | (i,x) <- (zip [10..] teens), i == r]

getTens :: Char -> String
getTens '0' = ""
getTens n   = let index = (digitToInt n) in
    tens !! index

--Takes a string rep. of a number, reverses it, and groups it into 3-groups
-- 12,000 -> ["000", "21"]
cutIntoGroups :: String -> [String]
cutIntoGroups = reverse . cut [] . reverse
    where
        cut acc []      = acc
        cut acc rest    = let (next,rest') = splitAt 3 rest in
            cut (next : acc) rest'

-- Applies the "rules" to each sub-chunk
applyLocalRules :: String -> String
applyLocalRules revChunk = hund ++ tensNOnes
    where
        (ones,tens,hunds) = toTriple revChunk '0'
        tensNOnes = if tens == '1' then (getTeens [tens,ones])
                        else (getTens tens) ++ (getOnes ones)
        hund = if hunds == '0' then ""
                    else (getOnes hunds) ++ "Hundred"

-- Succeedes each formatted chunk with the place name
applyRules :: [String] -> [String]
applyRules = reverse . map (\(i,g) -> let pName = getPlaceName i in
    applyLocalRules g ++ pName) . zip [0..]

toTriple :: [a] -> a -> (a,a,a)
toTriple [] def = (def,def,def)
toTriple xs def = case xs of
    [x,y,z] -> (x,y,z)
    [x,y]   -> (x,y,def)
    [x]     -> (x,def,def)
    _       -> error "List greater then 3"

addCommasAndConcat :: [String] -> String
addCommasAndConcat = concat . map (\chunk -> chunk ++ ",")

-- Adds spaces before words
addSpaces :: String -> String
addSpaces [] = []
addSpaces left = (h : pre) ++ " " ++ addSpaces post
    where
        (h:t)       = left
        (pre,post)  = break isUpper t

-- Loosely stolen from SO
trim :: String -> String
trim = let t = reverse . dropWhile (not . isAlpha) in
    t . t

-- Main function
convert :: Int -> String
convert = trim . addSpaces . addCommasAndConcat
    . applyRules . cutIntoGroups . show

It should be noted that this is very unsafe in its current form, so I'm only looking for comments regarding the algorithm itself (it crashes ungracefully on negative numbers, non-numbers, and too-large of numbers). I think I'm going to use this module to test out the Either Monad later to fix its safety.

I added the following test code to investigate. It does an exhaustive check from 1 to 999 and then a few more cases.

import Data.Monoid
import Control.Monad
import Test.Hspec

specTest n w = it ("converts " <> show n) $ convert n `shouldBe` w

oneToNine = words "One Two Three Four Five Six Seven Eight Nine"
zeroToNineEndings = "" : map ("-"<>) oneToNine
oneToNinetyNine = oneToNine
    <> words "Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen"
    <> [decade <> ending | decade <- words "Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety", ending <- zeroToNineEndings]

main = hspec $ do
  zipWithM_ specTest [1..]
    $ oneToNinetyNine
    <> mconcat
      [[d <> " Hundred"] <> map ((d <> " Hundred ") <>) oneToNinetyNine
      | d <- oneToNine
      ]

  specTest 1000 "One Thousand and "
  specTest 1001 "One Thousand and One"
  specTest 1234 "One Thousand and Two Hundred Thirty-Four"
  specTest 1234567 "One Million, Two Hundred Thirty-Four Thousand and Five Hundred Sixty-Seven"

Note that 1000 converts to 'One Thousand and ' which is probably wrong. Also, your original question claims 1234 converts to 'One Thousand, Two Hundred Thirty Four' but in fact it comes out as 'One Thousand and Two Hundred Thirty-Four'.

I am not sure your rules for adding 'and' and commas in are correct, however I'm from the UK where we typically put an 'and' between the hundreds and tens (e.g. 'two hundred and thirty-four') and I'm aware that this isn't how things are done in the US. I'd recommend adding some more test cases as I've shown above to make sure you're getting things as you expect.

The code seems idiomatically ok, although the mixture of CamelCase and use_of_underscores is a little jarring. hlint offers some good advice on the use of idiom and reports this, a few unnecessary parentheses and $s and identifies that concat . intersperse can be written as intercalate. Nothing major.


Finding palindromic strings of even length Given a string of digits. Find the length of longest substring of even length i.e. 0,2,... which is a palindrome or which can be rearranged to form a palindrome (see example below).

Here is my code:

def is_palindrome(string):
    length=len(string)
    new_d=[' ']*length
    #For rearranging the substring
    for i in range(length/2):
        new_d[i]=string[i]
        if string[i] in string[i+1:]:
            sindx=length-1-(string[::-1].index(string[i]))
            new_d[-(i+1)]=string[sindx]
    string1=('').join(new_d)
    return string1==string1[::-1]

def substring(number):
    subs=[]
    length=len(number)
    for i in range(length):
        for j in range(i+2,length+1,2):
            #print(number[i:j])
            yield number[i:j]

def count_palindromes(number):
    palindromes=[]
    palindromes.extend(filter(is_palindrome,substring(number)))
    #print(palindromes)
    if len(palindromes):
        lengths=[]
        for i in palindromes:
            lengths.append(len(i))
        lengths.sort(reverse=True)
        return lengths[0]
    else:
        return 0

number=raw_input()
length=count_palindromes(number)
print(length)

Input: String of numbers(0-9)
Ouput:Length of longest palindromic substring of even length

Example
Input:12345354987
Longest palindromic even length substring: 345354
On rearranging: 345543
Output:6

Notes

Your is_palindrome function has a bug. is_palindrome('1101') returns True.
Be careful with your function names. count_palindromes doesn't count palindromes, it returns the length of the largest one.
substring returns a generator of substrings. It should be plural.
If palindromes is a list of palindromes, you can use a list comprehension to get their respective lengths: [len(p) for p in palindromes].
You don't need to sort a list to find its max: max(palindromes, key=len).
There's also no need to define an empty list and extending it. You can use list(filter(is_palindrome,substring(number))) or [s for s in substring(number) if is_palindrome(s)].

Theory

If you write a generator which iterates over every even substrings in your string in decreasing length, all you need to check is that every digit appears an even number of time.

Code

from collections import Counter

def all_even_substrings(string):
    n = len(string)
    even_n = n + (n % 2)
    for l in range(even_n, 0, -2):
        for i in range(n + 1 - l):
            yield string[i:i + l]

def could_be_palindrome(substring):
    return all(count % 2 == 0 for count in Counter(substring).values())

def largest_possible_palindrome(string):
    return next((s for s in all_even_substrings(string) if could_be_palindrome(s)), None)

print(largest_possible_palindrome('12345354987'))
# 345354
print(largest_possible_palindrome('12334455987'))
# 334455
print(largest_possible_palindrome('123456789'))
# None

It's concise and pretty straightforward. If no palindrome is possible at all, the function returns None.

Substrings examples

Here's an example for all_even_substrings:

print(list(all_even_substrings('1234')))
# ['1234', '12', '23', '34']
print(list(all_even_substrings('12345')))
# ['1234', '2345', '12', '23', '34', '45']

If you ever need every substring:

def all_substrings(string):
    n = len(string) + 1
    for l in range(n, 0, -1):
        for i in range(n - l):
            yield string[i:i + l]

print(list(all_substrings('123')))
# ['123', '12', '23', '1', '2', '3']
print(list(all_substrings('1234')))
# ['1234', '123', '234', '12', '23', '34', '1', '2', '3', '4']


Basic string compression counting repeated characters My task was to implement a method which performs basic string compression by counting sequences of repeating characters. Given "aaabbbccc" it should return "a3b3c3". I have included some sample tests I made up. Please let me know if I have missed any cases. I am looking for the fastest implementation possible with the most concise code. I'm looking to cut down on if else statements or give them simpler logic if possible.

public class StringCompression {
    public String compress(String str){
        int count = 1;
        StringBuilder builder = new StringBuilder();

        for(int i = 1; i<str.length(); i++){

            if(str.charAt(i) == str.charAt(i-1) && i < str.length()-1){
                count++;
            }
            // case when the last letter is in the sequence preceding it. Add that sequence to
            // the compressed string
            else if(i == str.length()-1 && str.charAt(i) == str.charAt(i-1)){
                count++;
                builder.append(str.charAt(i));
                builder.append(count);
            }

            // case where the last letter is NOT in the sequence preceding it. Add it to string.
            else if(i == str.length()-1 && str.charAt(i) != str.charAt(i-1)){
                builder.append(str.charAt(i-1));
                builder.append(count);
                count = 1;
                builder.append(str.charAt(i));
                builder.append(count);
            }
            else{
                // appending the character and THEN appending the count works.
                builder.append(str.charAt(i-1));
                builder.append(count);
                count = 1;
            }

        }

        str = builder.toString();
        System.out.println(str);

        return str;
    }

    public static void main(String[] args){
        StringCompression test = new StringCompression();

        test.compress("aabcccccaaa");
        test.compress("aaaaa");
        test.compress("aaaabbb");
        test.compress("aaabbbccc");
        test.compress("abc");
        test.compress("a");
        test.compress("");
    }
}

As @vnp said, don't print the result for "testing". Convert each statement in the main method to proper unit tests, for example:

@Test
public void test_aabcccccaaa() {
    assertEquals("a2b1c5a3", compress("aabcccccaaa"));
}

@Test
public void test_a5() {
    assertEquals("a5", compress("aaaaa"));
}

Once this is done, you can go ahead and safely refactor the rest of the code,
having an easy way to repeat the tests.

Being aware of, and working knowledge of unit testing should definitely score you extra points in a job interview, or might be even required.

Bug

For single letter inputs, the method seems to return an empty string. That looks incorrect. Judging by that for "abc" it returns "a1b1c1", it would seem that for "a" it should return "a1" instead of an empty string

Simplify

The algorithm can be simplified to these steps:

Loop over the characters, from the 2nd till the end
If the current character is the same as the previous, increment the count
If different, append the count and append the previous character
After the end of the loop, append the count

The implementation can be something like this:

public String compress(String str) {
    if (str.isEmpty()) {
        return "";
    }

    char[] chars = str.toCharArray();
    StringBuilder builder = new StringBuilder();

    int count = 1;
    char prev = chars[0];
    for (int i = 1; i < chars.length; i++) {
        char current = chars[i];
        if (current == prev) {
            count++;
        } else {
            builder.append(prev).append(count);
            count = 1;
        }
        prev = current;
    }
    return builder.append(prev).append(count).toString();
}


Using IDisposable to stripe a table What are your thoughts on using an IDisposable to stripe an HTML table like so? It's a blatant abuse of IDisposable but this allows you to use the counter in a using(){} block which gives you a clear block in the markup.

public class StripeCounter : IDisposable
{
    private string cssClass = "stripe";

    private int counter = 0;

    public StripeCounter(){}

    public StripeCounter(string cssClass)
    {
        this.cssClass = cssClass;
    }

    public MvcHtmlString Stripe()
    {
        return MvcHtmlString.Create(counter++ % 2 == 1 ? cssClass : string.Empty);
    }

    public void Dispose() { }
}

And then the markup

@using (var counter = new StripeCounter())
{
    foreach (var item in Model)
    {

            ...

       ...

    }
}

Regarding comments on using JavaScript to stripe the table:

JavaScript is for behaviour and the striped rows of a table aren't behaviour; they are style, so while it is possible to do so on the client, it seem to me to be something that should be done on the server. For example, if someone has scripts disabled, they would still see the CSS striping, but not JavaScript striping.

Don't do the striping on the server. Don't do the striping with JavaScript. Since it's styling, do the striping with CSS.


Assembly 8086 program to input a 16-bit signed number (in string form) and output its binary equivalent I'm working on an exercise using Assembly 8086 which inputs a number (in string form) then output the binary form. Here is what I did (tested on emu8086 by the way):

Convert the string to numeric form: I simply iterated through the string, and for each new value I simply multiply the old value by 10, then add by the new value. But there are some checks for overflow which was annoying: I have to check in both the multiplication and addition part, and since in this part I simply ignored the negative part (for simplicity) I had to check for a special case: a 16-bit signed number goes from \$-2^{15} = -32768\$ to \$2^{15} - 1 = 32767\$, so if the input is -32768 then there would be an error, so I had to check for that case specifically.
From numeric to binary: I simply left-shifted the number (which is now stored in AX) consecutively and printed the most significant bit.

Please give some feedback, because I'm not sure if the overflow part is ok.

;Written by Dang Manh Truong
.stack      100h
.data
base10_string       dw      "-32799$"
biggest_16bits_signed       equ      7FFFh
special_16bits_signed       equ      8000h
special_16bits_signed_str   dw       "1000000000000000$"
error_overflow      dw      "Arithmetic overflow encountered. Abort$"
error_not_a_number  dw      "Not a number. Abort$"
base10      equ     10
tmp         dw      0
is_negative dw      0
.code
main        proc
;Initialization
    mov     ax,@data
    mov     ds,ax

;;;part 1: convert string to value
    mov     ax,0 ;number = 0;
    lea     si,base10_string
;check if positive or negative
    mov     bl,[si]  ;bl = value
    cmp     bl,'+'
    jne     check_if_negative
    add     si,1    ;start from after the "+" sign
    mov     ax,0
    jmp     while_loop
check_if_negative:
    cmp     bl,'-'
    jne     check_if_not_a_number
    mov     ax,1
    mov     is_negative,ax
    mov     ax,0
    add     si,1    ;start from after the "-" sign
    jmp     while_loop
check_if_not_a_number:
    cmp     bl,'0'
    jge     keep_checking
    jmp     not_a_number
keep_checking:
    cmp     bl,'9'
    jle     while_loop
    jmp     not_a_number
while_loop:
    mov     bl,[si]  ;bl = value
    ;check if end of string
    cmp     bl,'$'
    je      end_while
    ;check if not a number
check_:
    cmp     bl,'0'
    jge     keep_checking_
    jmp     not_a_number
keep_checking_:
    cmp     bl,'9'
    jle     add_to_number
    jmp     not_a_number
add_to_number:
    and     bx,000Fh ;'0'-> 0, '1' -> 1,...
    mov     dx,base10
    ;try
    mul     dx       ;number = number*10
    ;catch (Exception ArithmeticOverflow)
    jo      overflow
    ;try
    add     ax,bx    ;number = number*10 + value
    ;catch <Exception ArithmeticOverflow)
    ;jo      overflow
    cmp     is_negative,1
    jne     _perform_check
    cmp     ax,special_16bits_signed
    jne     _perform_check
    jmp     _aftercheck_overflow
_perform_check:
    ;jo      overflow
    cmp     ax,0
    jl      overflow
_aftercheck_overflow:
    add     si,1     ;next value
    jmp     while_loop
end_while:
;is negative?
    cmp     is_negative,1
    jne     begin_part2
    neg     ax
begin_part2:
;;;part 2: print base-2 number
    mov     cx,16
    mov     bx,ax
    mov     ah,2
print_:
    cmp     cx,0
    je      after_print
    shl     bx,1
;if bit == 1
    jnc     print_0
;then print_1
    mov     dl,'1'
    int     21h
    jmp     add_counter
;else print_0
print_0:
    mov     dl,'0'
    int     21h
add_counter:
    dec     cx
    jmp     print_
after_print:

    jmp     return_to_dos
overflow:
    lea     dx,error_overflow
    mov     ah,9
    int     21h
    jmp     return_to_dos
not_a_number:
    lea     dx,error_not_a_number
    mov     ah,9
    int     21h
    jmp     return_to_dos
return_to_dos:
    mov     ah,4ch
    int     21h
main        endp
    end     main

One of the most problematic things to deal with in assembly and even other higher languages but to a lesser degree, is spaghetti code. The logic of the program becomes lost in scrolling back and forth through hundreds of lines, SO concise documentation of what is going in is essential.

Working from the inside out is a method that has worked very effectively for me.

; Read ASCII NULL terminated string and convert input to packed BCD.

      GetNext:    lodsb                  ; Read next character into AL
                  or      al, al         ; Teminator ?
                  jz      Done

                 .......

                 jmp     GetNext

       Done:

Sometimes you may even want to think of efficiency in terms of time. The most probable scenario is that you'd be encountering digits 0 to 9.

      GetNext:    lodsb                  ; Read next character into AL
                  cmp     al, '0'
                  jae     @F
                  cmp     al, '9'
                  jbe     @F
                  cmp     al, 0
                  jz      Done

    ; At this point we know our entry is invalid or alternately we might
    ; want to check for things like '+', '-' or in this case just ignore
    ; extraneous input.

                 jmp     GetNext

            @@:  ; This is peculiar to MASM and is a local label.
                 ; NASM it could be preceded with a period like .L0:

                 .......

                 jmp     GetNext

       Done:


Construct the Array from HackerRank This is my answer for
https://www.hackerrank.com/challenges/construct-the-array/problem
(Passes all the test cases)

Problem

  Your goal is to find the number of ways to construct an array such
  that consecutive positions contain different values.

  Specifically, we
  want to construct an array with \$n\$ elements such that each element
  [contains a value] between \$1\$ and \$k\$, inclusive.
  We also want the first and last
  elements of the array to be \$1\$ and \$x\$. Given \$n\$, \$k\$ and \$x\$, find
  the number of ways to construct such an array.

  Since the answer may be
  large, only find answer modulo \$10^9 + 7\$

  For example, for \$n=4\$, \$k=3\$ and \$x=2\$ there are \$3\$ ways

Solution

public class Solution {
    public static final long MOD = 1_000_000_007L;

    public static long countArray(int n, int k, int x) {
        if (n < 3 || k < 2) return 0;
        if (n == 3 && x == 1) {
            return k - 1;
        }
        if (n == 3) {
            return k - 2;
        }
        long countOne = k - 1, countOther = k - 2, temp;
        for (int i = 4; i < n; i++) {
            temp = countOther * (k - 1) % MOD;
            countOther = (countOne % MOD + countOther * (k - 2) % MOD) % MOD;
            countOne = temp;
        }
        if (x == 1) {
            return countOther * (k - 1) % MOD;
        }
        return (countOne % MOD + countOther * (k - 2) % MOD) % MOD;
    }
}

"Impossible" check

Per task description, k >= 2 and n >= 3. But nevertheless you're performing this "impossible" check:

if (n < 3 || k < 2) return 0;

Redundant check

I don't understand why you're checking cases n == 3 separately. You could remove these 2 checks and have this case handled in your for loop quite easily as below (please note that the values of i, countOne and countOther have changed):

long countOne = 0, countOther = 1, temp;
for (int i = 3; i < n; i++) {
    temp = countOther * (k - 1) % MOD;
    countOther = (countOne % MOD + countOther * (k - 2) % MOD) % MOD;
    countOne = temp;
}

Variable naming

countOne or countOther are not a good way to call your variables - their names don't convey their purpose. I'll leave it up to you to come up with better names.

Excessive modulo operation

You don't have to perform a modulo operation more times than is needed. Given you task constraints, your can perform a modulo operation twice per iteration as below:

temp = countOther * (k - 1) % MOD;
countOther = (countOne + countOther * (k - 2)) % MOD;
countOne = temp;

Reduce scope of temp

As @Barmar correctly pointed out, your temp variable should be local to the for loop. It's not needed anywhere out of it.

Simplify return statements

You don't have to calculate countOne or countOther once you leave the for loop. You can do it all there, just fix your loop condition from i < n to i <= n and swap countOne with countOther in your return statements.

for (int i = 3; i <= n; i++) {
    long temp = countOther * (k - 1) % MOD;
    countOther = (countOne + countOther * (k - 2)) % MOD;
    countOne = temp;
}

if (x == 1) {
    return countOne;
}

return countOther;

Final Code

public static long countArray(int n, int k, int x) {

    long countOne = 0, countOther = 1;
    for (int i = 3; i <= n; i++) {
        long temp = countOther * (k - 1) % MOD;
        countOther = (countOne + countOther * (k - 2)) % MOD;
        countOne = temp;
    }

    return x == 1 ? countOne : countOther;
}


Random playlists program This is the first program I've created without help from a tutorial.  Written in Python 3.4, it gathers a specified number of media files and opens them in the default player (I use VLC on Windows 8.1). Python is my first language I have been learning mostly through trial and error. I am posting here to see what I can improve and to learn as much as I can.

import os, random, sys

completed_media = (r"C:\Users\user_000\Desktop\Completed Media")

all_media = []
playlist_ = []

def create_media_list():
    for path, subdirs, files in os.walk(completed_media):
        for file in files:
            if file.lower().endswith(('.mkv', '.mp4', '.divx', '.avi')):
                all_media.append(os.path.join(path, file))

def random_selection_from_media():
    random_selection = random.choice(all_media)
    if random_selection not in playlist_:
        playlist_.append(random_selection)
    else:
        pass

def get_selections():
    for i in range(number):
        random_selection_from_media()
    print_playlist_()
    playlist_confirmation()

def number_of_selections():
    while True:
        try:
            global number
            number = int(input('How many files would you like to add to playlist? >>> '))
            break
        except ValueError:
            print('Enter a number.')

def print_playlist_():
    print('\n-------In playlist-------\n')
    print('[{0}]'.format('\n-------------------------\n'.join(str(i) for i in enumerate(playlist_, 1))))
    print('\n-------End playlist------\n')

def remove_selection():
    while True:
        try:
            to_remove = int(input('To remove a selection enter the number of the selection you want removed here. >>> '))
            if to_remove <= len(playlist_):
            break
        except ValueError:
            print('Enter a number.')
            remove_selection()
        try:
            playlist_.pop((to_remove - 1))
            break
        except (IndexError, UnboundLocalError):
            print('Enter a vaild number')
            remove_selection()
    clear()
    print_playlist_()
    playlist_confirmation()

def playlist_confirmation():
    ok = input('This list ok? >>> ').lower()
    if ok == 'yes' or ok == 'y':
        play_playlist_()
    elif ok == 'no' or ok == 'n':
        while True:
            new = input('Get new list or remove a specific selection? >>> ').lower()
            if new == 'new list' or new == 'n':
                del playlist_[:]
                clear()
                get_selections()
                break
            elif new == 'specific selection' or new == 's':
                remove_selection()
                break
            else:
                 print('Enter \'new\' or \'selection\'')
    else:
        playlist_confirmation()

def play_playlist_():
    for i in playlist_:
        play_cmd = "rundll32 url.dll,FileProtocolHandler \"" + i + "\""
        os.system(play_cmd)

def clear():
    os.system('cls')

def main():
    create_media_list()
    number_of_selections()
    get_selections()

if __name__=="__main__":
    main()

Pretty good for a self-taught beginner, keep going like this and you're golden!

Recursion and infinite loop

This is probably the worst part of the script:

def remove_selection():
    while True:
        try:
            to_remove = int(input('To remove a selection enter the number of the selection you want removed here. >>> '))
            if to_remove <= len(playlist_):
                break
        except ValueError:
            print('Enter a number.')
            remove_selection()
        try:
            playlist_.pop((to_remove - 1))
            break
        except (IndexError, UnboundLocalError):
            print('Enter a vaild number')
            remove_selection()

An infinite loop, a misused exception handling,
an incorrect error handling, and recursive calls...
This is confusing and more complicated than it needs to be.

You can replace the recursive calls with continue.

Exception handling for converting the input to integer is appropriate, because there is no better way. It is not appropriate for validating the input is within range, because a better way exists using conditionals.

Also, it's not enough to check that the index is less than the length of the list, you also need to check that it's 0 or greater.

UnboundLocalError is thrown when trying to access a variable that hasn't been assigned. That's not an exception to catch, it indicates a problem in the logic that needs to be fixed.

Here's one way to address these issues:

while True:
    try:
        to_remove = int(input('To remove a selection enter the number of the selection you want removed here. >>> '))
    except ValueError:
        print('Enter a number.')
        continue
    if not (0 < to_remove <= len(playlist_)):
        print('Enter a valid number (within range: 1..{})'.format(len(playlist_)))
        continue
    playlist_.pop(to_remove - 1)
    break

Global variables

Try to avoid global variables as much as possible.

For example, instead of this:

def number_of_selections():
    while True:
        try:
            global number
            number = int(input('How many files would you like to add to playlist? >>> '))
            break
        except ValueError:
            print('Enter a number.')

It would be better to make the function return the number:

def number_of_selections():
    while True:
        try:
            return int(input('How many files would you like to add to playlist? >>> '))
        except ValueError:
            print('Enter a number.')

And then adjust the callers appropriately to pass the number as parameter where needed, for example instead of:

number_of_selections()
get_selections()

Write:

get_selections(number_of_selections())

Adjust the rest of the code accordingly, and try to eliminate the other global variables too, all_media and playlist_.
For these two, another good alternative will be to create a class, where these variables will be member fields.

Simplifications

Instead of this:

if ok == 'yes' or ok == 'y':

A bit simpler way to write:

if ok in ('yes', 'y'):

Optimizing imports, and coding style

The script is not actually using sys, so you can drop that import.

And the style guide recommends to import one package per line, like this:

import os
import random

Do read the style guide, it has many other recommendations that apply to your script.


"Sequence full of colors" challenge on HackerRank This is the challenge:

You are given a sequence of N balls in 4 colors: red, green, yellow and blue. The sequence is full of colors if and only if all of the following conditions are true:

There are as many red balls as green balls.
There are as many yellow balls as blue balls.
Difference between the number of red balls and green balls in every prefix of the sequence is at most 1.
Difference between the number of yellow balls and blue balls in every prefix of the sequence is at most 1.
Your task is to write a program, which for a given sequence prints True if it is full of colors, otherwise it prints False.

and this is my solution:
import Control.Monad (replicateM, foldM)

main :: IO ()
main = do
  n <- getLine
  list <- replicateM (read n :: Int) getLine
  mapM_ (print . isgood) list

isgood :: String -> Bool
isgood = isValidFinal . foldM step (0,0)
  where
    step (x,y) c
      | c == 'R' = wrapValidInJust (x - 1, y)
      | c == 'G' = wrapValidInJust (x + 1, y)
      | c == 'Y' = wrapValidInJust (x, y - 1)
      | c == 'B' = wrapValidInJust (x, y + 1)
    isValid (x,y) = abs x <= 1 && abs y <= 1
    wrapValidInJust xy = if isValid xy then Just xy else Nothing
    isValidFinal (Just x) = x == (0,0)
    isValidFinal Nothing = False

I'm kind of happy with main and isgood, but the step function seems very hard to read.
Any feedback?

step does two things: (1) step to the next state, and (2) check that the state is valid. Its name suggests only the first meaning. The repetition of wrapValidInJust suggests that they can be separated.

Instead of == you can use pattern-matching.

isgood :: String -> Bool
isgood = isValidFinal . foldM (check . step) (0, 0)
  where

    step (x, y) 'R' = (x-1, y)
    step (x, y) 'G' = (x+1, y)
    step (x, y) 'Y' = (x, y-1)
    step (x, y) 'B' = (x, y+1)

    check (x, y) = if abs x <= 1 && abs y <= 1 then Just (x, y) else Nothing

    ...

Another reason step is hard to read is that you need to keep track of differences, which complexifies the meaning of x and y. You can just as easily count the four colors independently and compute the difference only in check. This is also the opportunity to use a record or a map to make the update syntax more uniform:
data RGBY = RGBY { r, g, b, y :: Int }

isgood :: String -> Bool
isgood = isValidFinal . foldM (check . step) (RGBY 0 0 0 0)
  where

    step x 'R' = x { r = r x + 1 }
    step x 'G' = x { g = g x + 1 }
    step x 'Y' = x { y = y x + 1 }
    step x 'B' = x { b = b x + 1 }

    check x = if abs (r x - g x) <= 1 && abs (y x - b x) <= 1
      then Just (x, y) else Nothing

    ...


Resource caching in Java with soft references I'd like to cache some heavy resources locally. The goal of this implementation is to have be able to load resources for an unknown amount of time and then keep them in memory and finally evict them upon needs. So there is no "time-based" evictions needed: only "memory-based" ones.

As written in comment, I'm writing this code in the scope of a small library using only Guava as dependency, and currently, Guava doesn't support the single-element cache.

I've developped the following code:

Resource.java

import com.google.common.io.ByteSource;
import java.io.UncheckedIOException;
import java.lang.ref.SoftReference;
import java.util.function.Supplier;

public class Resource<T> implements Supplier<T>, AutoCloseable {

  private final ByteSource source;
  private final ResourceLoader<T> loader;
  private SoftReference<T> reference;

  Resource(ByteSource source, ResourceLoader<T> loader) {
    this.source = source;
    this.loader = loader;
    reference = new SoftReference<>(null);
  }

  @Override
  public T get() throws UncheckedIOException {
    // Double-checked locking
    T object = reference.get();
    if (object == null) {
      synchronized(this) {
        object = reference.get();
        if (object == null) {
          object = this.loader.uncheckedLoad(this.source);
          this.reference = new SoftReference(object);
        }
      }
    }
    return object;
  }

  @Override
  public void close() {
    synchronized(this) {
      this.reference = new SoftReference<>(null);
    }
  }
}

ResourceLoader.java

import com.google.common.io.ByteSource;
import java.io.IOException;
import java.io.UncheckedIOException;

public interface ResourceLoader<T> {

  public default <T> T uncheckedLoad(ByteSource source) throws UncheckedIOException {
    try {
      return this.load(source);
    } catch (IOException ex) {
      throw new UncheckedIOException(ex);
    }
  }

  public <T> T load(ByteSource source) throws IOException;
}

I've also written the test:

import static org.hamcrest.Matchers.is;
import static org.hamcrest.Matchers.sameInstance;
import static org.junit.Assert.assertThat;
import static org.mockito.Matchers.any;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.times;
import static org.mockito.Mockito.verify;
import static org.mockito.Mockito.when;

public class ResourceTest {

  @org.junit.Test
  public void shouldCacheInstanceAndReturnIt() throws java.io.IOException {
    ResourceLoader<String> loader = mock(ResourceLoader.class);
    String abc = new String("abc"); // Force a specific address to avoid javac optimization
    when(loader.uncheckedLoad(any())).thenReturn(abc);
    when(loader.load(any())).thenReturn(abc);

    Resource<String> resource = new Resource(null, loader);

    assertThat(resource.get(), is(sameInstance(abc)));
    assertThat(resource.get(), is(sameInstance(abc)));

    verify(loader, times(1)).uncheckedLoad(any());
  }
}

My various questions regarding this code are the following:

Is this implementation appropriate for a cache?
Is the double-checked locking the right way to use this? A priori, various calls to Resource::get should return identical object (not especially in regard to Object::equals or ==, but mostly in regards to what the final user sees).
How can I properly test this implementation? I see it's working: my test passes, but how can I simulate a soft reference eviction? Can I simply call my close() method?

Double-checked
Double-checked locking does not work. There are some complicated reasons for this, but, it's enough to say that the Java specification allows the Java runtime to legitimately reorder some of the checking code in a way that makes the sync lock out-of-alignment with the checks you think you are checking. (See: Double checked locking pattern: Broken or not? )
AutoClosable
Now, about the AutoClosable.
Why?
What does that get for you? You forcefully "forget" a reference that was allowed to be garbage collected anyway. Additionally, it does not close the instance at all, it just makes it refresh later. The AutoClose is a shim, that's not a very useful one at that.
SoftReference
Here's a paradox with caching. What are you caching here? The instance of the resource that you read from the ResourceLoader, or the Resource class itself? It would be preferable to cache the Resource instance itself, but you cache the underlying data. Additionally, you re-load it if the cache is cleared by the GC.
My problem is that anything that has a strong reference to the Resource instance probably wants to find the content again at some point.... otherwise it would not need to hold the reference. Thus, if you have memory problems, it is possibly just better to reload the resource each time, than to possibly hang on to it.
Are you sure that you want a SoftReference?
If yes, why don't you have a ReferenceQueue? A reference queue allows you to back-reference a SoftReference to the Resource that owns it. It works as follows:

create a sub-class of SoftReference (not a wrapper, but an actual "extends" instance).
put a strong-reference back to the Resource that the SoftReference comes from
register the SoftReference on a queue

Then, in a separate thread, pull GC'd items off the queue, and process them. This allows you to get an ahead-of-time peek at data that has been de-cached.
It also allows you to have a colleciton of Resources that are held in, for example, a Map, and you can clear the Resources out of the map as they are cleared out by the GC.


Find zeroes in a matrix I am looking for the elements that are zeroes in a square matrix (of size n), as a list of pair. I don't really like the following code, some condition seems rendundant but my knowledge of OCaml is limited and I can't find an elegant way to refactor it:

let find_zeroes input_matrix n =
    let rec aux i j n =
        if(i == n) then []
        else begin
            if(input_matrix.(i).(j) == 0) then begin
                if(j < n-1) then (i,j)::(aux i (j+1) n)
                else (i,j)::(aux (i+1) 0 n)
            end else begin
                if(j < n-1) then (aux i (j+1) n)
                else (aux (i+1) 0 n)
            end
        end
    in aux 0 0 n
;;

Actually, the n arugment is optional:

let find_zeroes input_matrix =
    let rec aux i j n =
        if(i == n) then []
        else begin
            if(input_matrix.(i).(j) == 0) then begin
                if(j < n-1) then (i,j)::(aux i (j+1) n)
                else (i,j)::(aux (i+1) 0 n)
            end else begin
                if(j < n-1) then (aux i (j+1) n)
                else (aux (i+1) 0 n)
            end
        end
    in aux 0 0 (Array.length input_matrix)
;;

I would try to decouple the idea of traversing the matrix to collect information about its content and the actual definition of find_zeros. This way you can reuse the same traversal to implement other functions too.

This leads to something like this (I don't assume that the matrix is a square one): indexedTraversal takes a function add and an initial value ini for the accumulator we will use when traversing the matrix mat. add updates the accumulator given the position of the current cell and its content.

type 'a matrix = 'a array array

let indexedTraversal
    (add : int -> int -> 'a -> 'b -> 'b)
    (ini : 'b)
    (mat : 'a matrix)
    : 'b =
  let m = Array.length mat     in
  let n = Array.length mat.(0) in
  let rec aux (i : int) (j : int) (acc : 'b) =
    let acc' = add i j mat.(i).(j) acc in
         if j < n - 1 then aux i (j + 1) acc'
    else if i < m - 1 then aux (i + 1) 0 acc'
    else acc'
  in aux 0 0 ini

(nota: I don't check that m > 0 here so Array.length mat.(0) might raise an error. You can (and should!) add the test to handle that edge case)

You can then implement find_zeros by defining an appropriate testElt and calling indexedTraversal with the empty list as the inital accumulator. Here I call List.rev because otherwise the result is actually the reverse of what you had implemented. If you don't care about the order in which the elements are listed, you can just do away with it.

let find_zeros (m : int matrix) : (int * int) list =
  let testElt i j x ijs = if x == 0 then (i,j)::ijs else ijs
  in List.rev (indexedTraversal testElt [] m)

We can try it on a simple example and it works:

utop # find_zeros [| [|0;1|]; [|1;0|]|];;
- : (int * int) list = [(0, 0); (1, 1)]


Counting Fermat witnesses and liars We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem.

Fermat’s little is used to identify whether a possible prime number is composite. It’ll find a number/numbers called Fermat witness then. The other numbers are Fermat liars unless Fermat’s little doesn’t find any witness. Then the number is possibly prime.

# coding=utf-8

"""Basic usage:
$ python fermat.py 7
(0, 0)
$ python fermat.py 9
(6, 2)
"""

import argparse

def main():
    """Prints out the results of fermat_witness_liar_count().
    fermat_witness_liar_count() takes a non-optional integer as an argument.
    """

    parser = argparse.ArgumentParser()
    parser.add_argument('possible_prime', type=int)
    args = parser.parse_args()

    if args.possible_prime > 1 and args.possible_prime % 2 == 1:
        print(fermat_witness_liar_count(args.possible_prime))
    else:
        print("Please enter an odd integer > 1.")

def fermat_witness_liar_count(possible_prime):
    """Counts the amount of Fermat witnesses and liars
    for a number 1 <= test_num <= possible_prime.
    Basic usage:
    >>> fermat_witness_liar_count(3)
    (0, 0)
    >>> fermat_witness_liar_count(9)
    (6, 2)
    >>> fermat_witness_liar_count(31)
    (0, 0)
    >>> fermat_witness_liar_count(33)
    (28, 4)
    >>> fermat_witness_liar_count(437)
    (432, 4)
    """

    witness_count = 0
    liar_count = 0
    temp_liar_count = 0

    for test_num in range(1, possible_prime):
        if fermat_witness(test_num, possible_prime):
            witness_count += 1
        else:
            temp_liar_count += 1

    # When there are Fermat witnesses, all test_num’s that aren’t are Fermat liars
    if witness_count != 0:
        liar_count = temp_liar_count

    return witness_count, liar_count

def fermat_witness(test_num, possible_prime):
    """Basic usage:
    >>> fermat_witness(2, 3)
    False
    >>> fermat_witness(8, 9)
    False
    >>> fermat_witness(30, 31)
    False
    >>> fermat_witness(3, 33)
    True
    >>> fermat_witness(6, 437)
    True
    """

    if pow(test_num, possible_prime-1) % possible_prime != 1:
        # test_num is a Fermat witness, possible_prime composite
        return True

    # possible_prime may be prime
    return False

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()

I think it would be worth explaining the terms you are using : what is a liar ? what is a witness ?

Except for that, the code is well presented and well tested (so many thanks for that).

Making code more simple in fermat_witness

You could easily rewrite fermat_witness: return pow(test_num, possible_prime-1) % possible_prime != 1.

Making code more simple in fermat_witness_liar_count

You could also rewrite fermat_witness_liar_count with less variables because you can get rid of liar_count by writing :

if witness_count != 0:
    return witness_count, temp_liar_count
return 0, 0

You can also get rid of temp_liar_count by writing :

witness_count = 0
for test_num in range(1, possible_prime):
    if fermat_witness(test_num, possible_prime):
        witness_count += 1
if witness_count != 0:
    return witness_count, possible_prime - witness_count - 1
return 0, 0

Then, you can use the fact that non-zero integers are considered as true values and try to write a single return:

return witness_count, possible_prime - witness_count - 1 if witness_count else 0

Finally, if you want to count, you can use sum and simply write :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))

The whole function becomes :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))

# When there are Fermat witnesses, all test_nums that arent are Fermat liars
return witness_count, possible_prime - witness_count - 1 if witness_count else 0

pow is a pow-erful builtin

pow handles what you are trying to do in a more efficient way :

  if z is present, return x to the power y, modulo z (computed more
  efficiently than pow(x, y) % z)

fermat_witness becomes :

return pow(test_num, possible_prime-1, possible_prime) != 1

Then, I guess more mathematical optimisations could be performed but I haven't tried at all.


Matrix problem, the path that is the flattest So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being limited to down and right.
Also, the path needs to be chosen in such way that the differences in altitude are the smallest, basically finding the path that has the smallest sum of differences in altitude.
I think I am using dynamic programming in my solution.(I am still a beginner, I am not so sure of this)

First I begin by creating another matrix that has the sums of the differences in altitude of the edges of the matrix, being the easiest to calculate because there is a single way that those sums can be computed. (S is the new matrix, while A is the matrix that is given)

 S[0][0]=0;
 for(int i=1;i<=n-1;i++)
        {S[0][i]=S[0][i-1]+abs(A[0][i]-A[0][i-1]);
        S[i][0]=S[i-1][0]+abs(A[i][0]-A[i-1][0]);}

Secondly, I am traversing the matrix by comparing the sums of the already calculated paths(the edges at first)+ the two ways (up or down). Whichever one is smallest, will be put in the new matrix.

for(int i=1;i<=n-1;i++)
    for(int j=1;j<=n-1;j++)
        if(S[i-1][j]+abs(A[i][j]-A[i-1][j])<S[i][j-1]+abs(A[i][j]-A[i][j-1]))
                S[i][j]=S[i-1][j]+abs(A[i][j]-A[i-1][j]);
        else
                S[i][j]= S[i][j-1]+abs(A[i][j]-A[i][j-1]);

This problem worked for the examples that I tried, but I am wondering if there is a more efficient way. Also, i could have made a mistake (or many :) ), so please feel free to tell me if you think it is a good solution, a bad one and if you have any advice for me.

Thank you for the attention anyways!

The complete code:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");

int A[21][21],n,S[21][21],D[42][4];

int main()
{   //reading the matrix
    fin>>n;
    for(int i=0;i<=n-1;i++)
        for(int j=0;j<=n-1;j++)
            fin>>A[i][j];
    //computing the edges of the new matrix
    S[0][0]=0;
    for(int i=1;i<=n-1;i++)
        {S[0][i]=S[0][i-1]+abs(A[0][i]-A[0][i-1]);
        S[i][0]=S[i-1][0]+abs(A[i][0]-A[i-1][0]);}
    //comparing the sums
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=n-1;j++)
            if(S[i-1][j]+abs(A[i][j]-A[i-1][j])<S[i][j-1]+abs(A[i][j]-A[i][j-1]))
                S[i][j]=S[i-1][j]+abs(A[i][j]-A[i-1][j]);
            else
                S[i][j]= S[i][j-1]+abs(A[i][j]-A[i][j-1]);

//a new matrix to identify the path and memorize the down/right moves
    int i,j,x;
    i=n-1;
    j=n-1;
    x=1;
    D[0][0]=A[n-1][n-1];
    while(i!=0&&j!=0)
    {if(S[i-1][j]<S[i][j-1])
        {
        D[x][0]=A[i-1][j];
        D[x][1]=1;   //1 for down
        x++;
        i=i-1;}
    else
    {
        D[x][0]=A[i][j-1];
        D[x][1]=2;    //2 for right
        x++;
        j=j-1;
    }}
    if(S[1][0]>S[0][1])
        D[x][1]=2;
    else
        D[x][1]=1;
    D[x][0]=A[0][0];

 //showing the path
fout<<"The path:"<<endl;
    for(i=x;i>=0;i--)
        { fout<<endl<<D[i][0];
        if(i!=0)
           {if(D[i][1]==1)
                fout<<endl<<"down";
            else
                if(D[i][1]==2)
                fout<<endl<<"right";}
        }

    return 0;
}

Don't take this the wrong way, but my first thought when I looked at your code was "ugh do I really want to read this?"  You have (probably) been thinking a lot about A, S, n, and D over the last few hours, but if you look at this again in 2 years, it will look like nonsense.  So your number one goal should be to fix readability.  Then you can start thinking about correctness and performance.

I would recommend reading through a C++ style guide for general tips.  Here is one, but there are many others.  I'll still list a few of the biggest mistakes:

You should avoid single letter variable names
Try to express your logic in functions
Don't use global variables
Indent consistently (or better yet, automatically with help from your IDE)

All of these have been written about extensively in style guides, programming manuals, other code reviews, etc...

fin>>n;

What if n > 21?  If you have some reason to believe it cannot be, then you should assert(n < 22).  But in this case, it's easy enough to support any n with std::vector.

i<=n-1

The canonical way to write this is i < n.

`S[i-1][j]+abs(A[i][j]-A[i-1][j])`

I think this section is correct, but I have more style comments!

This is complicated looking for no reason.  You're making yourself think harder than you have to which means you will accomplish less stuff with your mental bandwidth.  How about something like costOfStep(i-1, j)?
This gets exactly repeated twice and a very similar statement is also repeated twice.  That's a telltale sign you should at least use a variable or better yet write a function to compute this.

Isn't the snipped below easier to read?

for(int i = 1; i < n; i++) {
    for(int j = 1; j < n; j++) {
        int costOfStepDown = costOfStep(i - 1, j);
        int costOfStepRight = costOfStep(i, j - 1);
        minCosts[i - 1][j] = std::min(costOfStepDown, costOfStepRight);
    }
}

//a new matrix to identify the path and memorize the down/right moves
int i,j,x;
i=n-1;
j=n-1;
x=1;

From this point on, I think you are using more time/memory than necessary.  I believe you can refactor your code so that you only store one matrix for both the input array and one for the cumulative array (or two matrices if it's clearer, but not more).  And you can store your path as a 1D vector.  Doing two passes leads to unnecessary code which leads to pointless bugs and wasted time.  Keep it minimal!  You were following a decently minimal algorithm until this part...

Also, here are my thoughts while reading this snippet:

Nice a comment... Where is the new matrix?
Oh some single named variables.  No idea what these do.  Hopefully I can figure it out.
Huh they are not initialized.  I hope the author was careful not to use uninitialized values.

That's a lot of thinking for not very much action.  How about this:

Matrix path;
path[0][0] = inputMatrix[size - 1][size - 1];
for (int i = 0, j = 0; i < size && j < size; /*increment in body*/) {
    ...

This is more of a general tip than a specific comment.  I hope you find it useful.

Many dynamic programming problems are easy to solve with recursion.  Here's some pseudo-code for this problem:

// return the min cost of traveling from pos to the bottom-right of inputMatrix
int minCost(Matrix const& input, Position const pos = top-left) {
    if (pos == bottom-right) {
        return 0;
    }
    return std::min(minCost(input, pos.right), minCost(input, pos.down));
}

Position could be std::pair<int, int> and Matrix could be std::vector<std::vector<int>>.

This function will calculate the correct answer, but it is slow because it repeatedly calculates the min cost of the same position many times.  Fix that:

int minCostHelper(Matrix const& input, Position const pos, Cache cache) {
    if (cache.hasSeen(pos)) {
        return cache.valueOf(pos);
    }
    if (pos == bottom-right) {
        return 0;
    }
    auto result = std::min(minCost(input, pos.right), minCost(input, pos.down));
    cache.insert(pos, result);
    return result;
}

int minCost(Matrix const& input) {
    Cache cache;
    return minCostHelper(input, top-left, cache);
}

Cache could be an std::map.

The technical term for "fix" in this case is "memoize."  I think this style is easier to read/debug than manually creating arrays.  It's a question of personal preference though.

Here is a challenge: can you write a function that will memoize another function?

template <typename Function>
Function memoize(Function);


How to make Map expendible(?) safely in java I am building some statistic counter in Java.
Each metric could have flexible depth so the implementation should able to explore the depth when value insert or update.
So I implement like below (with Test)
public class TestRecursiveMap {

    private void recursiveRegister(Map<String, Object> target, String[] keys, int curr) {
        if(curr > keys.length -1) return;
        String currKey = keys[curr];
        if(target.containsKey(currKey)) {
            Object currVal = target.get(currKey);
            if(curr >= keys.length -1) {
                int value = (int) currVal;
                target.put(currKey, value + 1);
            } else {
                Map<String, Object> subMap = (Map<String, Object>)currVal;
                recursiveRegister(subMap, keys, curr + 1);
            }
        } else {
            if(curr >= keys.length -1) {
                target.put(currKey, 1);
            } else {
                Map<String, Object> emptyMap = new HashMap<>();
                target.put(currKey, emptyMap);
                recursiveRegister(emptyMap, keys, curr + 1);
            }
        }
    }

    // result looks like
    // {a={b={c=1}}}
    // {a={b={c=2}}}
    @Test
    public void testRecursive(){
        Map<String, Object> originMap = new HashMap<>();
        String[] keys = {"a", "b", "c"};
        recursiveRegister(originMap, keys, 0);
        System.out.println(originMap);
        recursiveRegister(originMap, keys, 0);
        System.out.println(originMap);
    }
}

The code is so unsatisfied because of

casting in recursive logic - Map<String, Object> is very flexible but need to cast object to map or integer in every level

while casting there are bunch of possibilities of exceptions

How could I implement this safe and fast?
=====================================
Use case #1.
Actually this is an api counter. When you have an API call, it will counting the mount of the request.
For instance,
/api/user/1 and /api/v1/user/1 then it will have some value like below (in JSON form)
{
    "api" : {
        "user" : {
            "1" : 1
        },
        "v1" : {
            "user" : {
                "1" : 1
            }
        }
    }

}

So the basic logic is

if there is a key in the map, it will increase the number
if not, it will assign new k,v set and the initial value is 1

It took a long time just to understand what your program is doing and how it might be useful.
You were concerned about the unchecked casting, and that's a valid concern, but maybe it's not a problem if you make that behaviour clear, for instance, by including a failure scenario in the test case or JavaDoc, in which case you are just stating it's the responsibility of the other code that makes use of this to only pass valid arguments.
Here's a version of the same thing that's hopefully a bit better at describing what it does. With things a bit more plain to read, you can decide if you want your program to behave differently in the failure case -- maybe it should throw a checked exception instead of ClassCastException or maybe you want to actually support these cases?
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
 * I am building some statistic counter in Java. Each metric could have flexible
 * depth so the implementation should able to explore the depth when value
 * insert or update.
 *
 */
public class StatisticsCounter {

    private Map<String, Object> rootMap = new HashMap<>();

    public void increment(String... paths) {
        recursiveIncrement(rootMap, paths, 0);
    }

    private void recursiveIncrement(Map<String, Object> targetMap, String[] pathToTarget,
            int pathIndex) {

        final int targetDepth = pathToTarget.length - 1;
        final String counterName = pathToTarget[pathIndex];

        if (pathIndex == targetDepth && targetMap.containsKey(counterName)) {
            // assume objects at the target depth are int
            targetMap.put(counterName, (int) targetMap.get(counterName) + 1);
        } else if (pathIndex == targetDepth) {
            // at the target depth, put ints
            targetMap.put(counterName, 1);
        } else if (targetMap.containsKey(counterName)) {
            // assume object is a map, recur into it for the next counter name
            recursiveIncrement((Map<String, Object>) targetMap.get(counterName),
                    pathToTarget, pathIndex + 1);
        } else {
            // create a new map and recur into it for the next counter name
            Map<String, Object> emptyMap = new HashMap<>();
            targetMap.put(counterName, emptyMap);
            recursiveIncrement(emptyMap, pathToTarget, pathIndex + 1);
        }
    }

    public String toString() {
        return rootMap.toString();
    }

    @Test
    public void test() {
        StatisticsCounter counters = new StatisticsCounter();
        counters.increment("USA", "California", "Los Angeles");
        counters.increment("USA", "California", "Los Angeles");
        counters.increment("USA", "California", "San Diego");
        counters.increment("USA", "California", "Bay Area", "San Francisco",
                "Financial District");
        counters.increment("USA", "Tennessee", "Memphis");
        counters.increment("USA", "Tennessee", "Memphis");
        counters.increment("Italy", "Venice");
        counters.increment("Italy", "Rome");
        counters.increment("Italy", "Venice");
        counters.increment("Vatican City");
        counters.increment("Vatican City");

        try {
            counters.increment("USA", "California");
            fail("Cannot increment a key that already has subcounters");
        } catch (ClassCastException expectedException) {
            assertEquals("java.util.HashMap cannot be cast to java.lang.Integer",
                    expectedException.getMessage());
        }

        try {
            counters.increment("USA", "Tennessee", "Memphis", "Graceland");
            fail("Cannot add subcounters to a key that already has a count");
        } catch (ClassCastException expectedException) {
            assertEquals("java.lang.Integer cannot be cast to java.util.Map",
                    expectedException.getMessage());
        }

        System.out.println(counters);
        // {USA={Tennessee={Memphis=2}, California={San Diego=1, Bay Area={San
        // Francisco={Financial District=1}}, Los Angeles=2}}, Italy={Rome=1, Venice=2},
        // Vatican City=2}
    }
}


Basic Caesar Cipher Code Could I have a couple people look over my code for a general readability check?  Just make sure it is following Python standards.

def casear_cipher(letter, num):
    """ This function acts like a Casear Cipher.

    Replaces an input letter with another letter a fixed

    number of spaces farther down the alphabet

    Args:

    * letter (string) - any upper case or lower case letter

    * num (integer) - any integer value to shift to a new letter
        """

    #Range 65 to 91 is ASCii values for uppercase alphabet
    if ord(letter) in range (65, 91):
        x = ord(letter) - ord('A')
        num_mod_26 = (x + num) % 26
        final_output = chr(ord('A') + num_mod_26)
        return final_output

    #Range 97 to 123 is ASCii values for lowercase alphabet
    elif ord(letter) in range (97, 123):
        x = ord(letter) - ord('a')
        num_mod_26 = (x + num) % 26
        final_output = chr(ord('a') + num_mod_26)
        return final_output

First of all welcome to Codereview.

Good

You have a decent function.
You even have a nice docstring to describe what it does!
You have decent descriptive names.

Overall your code is good, well done!

Improvements

Make the starting_ascii value more generic, no more duplicated code.
Rais an appropriate exeption if no letter is given, you might want to handle that differently.

Revised code

def casear_cipher(letter, num):
    """This function acts like a Casear Cipher.

    Replaces an input letter with another letter a fixed
    number of spaces farther down the alphabet

    Args:
    * letter (string) - any upper case or lower case letter
    * num (integer) - any integer value to shift to a new letter"""

    if letter.isupper():
        starting_ascii = ord('A')
    elif letter.islower():
        starting_ascii = ord('a')
    else:
        raise ValueError('Input is not a letter')

    alpha_index = ord(letter) - starting_ascii
    mod_26 = (alpha_index + num) % 26
    return chr(starting_ascii + mod_26)


Sort a linked list with merge sort in C This is my version of a linked list in C. The function mergeSort requires a reference to the first and to the last nodes, as well as the indices of the first and the last node and a comparator.

You need to compile this source code using C99 standard in order to get it working.

#include <stdio.h>
#include <stdlib.h>

typedef struct List {
    int val;
    struct List *next;
} List;

List *new(int value)
{
    List *list = malloc(sizeof(List));
    list->next = NULL;
    list->val = value;

    return list;
}

void freeList(List *list)
{
    List *node = list;
    while(node != NULL) {
        List *n = node->next;
        free(node);
        node = n;
    }
}

void print(List *list)
{
    for(List *node = list; node != NULL; node = node->next) {
        printf("%d ", node->val);
    }
    printf("\n");
}

List *merge(List *part1, List *part2, int (*cmp)(const void *, const void *))
{
    List *temp;

    if(cmp(&part1->val, &part2->val) < 0) {
        temp = part1;
        part1 = part1->next;
    }
    else {
        temp = part2;
        part2 = part2->next;
    }

    List *current = temp;

    while(part1 != NULL && part2 != NULL) {
        if(cmp(&part1->val, &part2->val) < 0) {
            current->next = part1;
            part1 = part1->next;
        }
        else {
            current->next = part2;
            part2 = part2->next;
        }
        current = current->next;
    }

    while(part1 != NULL) {
        current->next = part1;
        current = current->next;
        part1 = part1->next;
    }

    while(part2 != NULL) {
        current->next = part2;
        current = current->next;
        part2 = part2->next;
    }

    return temp;
}

List *mergeSort(List *start,
                List *stop,
                int startIndex,
                int stopIndex,
                int (*cmp)(const void *, const void *))
{
    if(start != stop) {
        int mid = (startIndex + stopIndex) / 2;
        int i = startIndex;

        List *midNode = NULL;
        for(List *node = start; node != stop; node = node->next) {
            if(i == mid) {
                midNode = node;
            }
            i++;
        }
        List *midNodeNext = midNode->next;

        List *part1 = mergeSort(start, midNode, startIndex, mid, cmp);
        List *part2 = mergeSort(midNodeNext, stop, mid + 1, stopIndex, cmp);

        return merge(part1, part2, cmp);
    }

    start->next = NULL;
    return start;
}

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

List *push(List *list, List *node)
{
    List *last;
    for(List *node = list; node != NULL; node = node->next) {
        if(node->next == NULL) {
            last = node;
        }
    }
    last->next = node;

    return node;
}

int main()
{
    List *list = new(9);

    push(list, new(4));
    push(list, new(3));
    push(list, new(2));
    push(list, new(1));
    List *stop = push(list, new(8));

    list = mergeSort(list, stop, 0, 5, cmp);

    print(list);

    freeList(list);

    return 0;

}

Merging tails effectively wastes cycles. The nodes are already linked correctly.

    if (part1 != NULL) {
        current->next = part1;
    }

    if (part2 != NULL) {
        current->next = part2;
    }

is enough.
A single most important feature of merge sort is stability: elements compared equal remain in the original order. A comparison

    if(cmp(&part1->val, &part2->val) < 0)

makes your sort unstable. A correct comparison is either one of

    if(cmp(&part2->val, &part1->val) > 0)
    if(cmp(&part1->val, &part2->val) <= 0)

Less indentation is easier to follow. I recommend to invert a recursion termination condition:

    if (start == stop) {
        start->next = NULL;
        return start;
    }
    ...

Avoid naked loops. The

    for(List *node = start; node != stop; node = node->next) {
        if(i == mid) {
            midNode = node;
        }
        i++;
    }

should be factored out into a function

    List * advance(List * start, int steps);


Split Java ArrayList into equal parts I have seen this question asked a few times, but I do not entirely understand the solutions provided.
Below is a bit of code I came up with for splitting up an arraylist into five parts. I have tested and changed the array size from 0 to 16 and it works fine.

I am sure there is a "better" way of doing this, so I would like to see what others think.

public static void main(String[] args)
{
    ArrayList<String> arrayList = new ArrayList<String>();
    arrayList.add("A");//1
    arrayList.add("B");//2
    arrayList.add("C");//3
    arrayList.add("D");//4
    arrayList.add("E");//5
    arrayList.add("F");//6
    arrayList.add("G");//7
    arrayList.add("H");//8
    arrayList.add("I");//9
    arrayList.add("J");//10
    arrayList.add("K");//11
    arrayList.add("L");//12
    arrayList.add("M");//13
    arrayList.add("N");//14
    arrayList.add("O");//15
    arrayList.add("P");//16
    arrayList.add("X");//17

    int i1 = (int) Math.ceil(arrayList.size()/5.0);

    List<String> sublist = new ArrayList<String>();
    int x=0;
    for(int p=0; p<i1; p++)
    {
        if(arrayList.size()>=(x+5))
        {
            sublist = new ArrayList<String>(arrayList.subList(x, x+5));
            x+=5;
        }
        else
            sublist = new ArrayList<String>(arrayList.subList(x, arrayList.size()));
        for(String slist : sublist)
        {
            System.out.println("i:"+slist);
        }
    }
}

It seems like you are mixing up the number of segments and the number of elements per segment. In your example, both are the same, so the result is correct, but in other cases it will not be. For instance, i1 is created as the number of elements per segment, with the number of segments being hard-coded as 5.0. Then, in the loop, you treat i1 as the number of segments, while the number of elements per segment is hard-coded as 5. Mistakes like this will be easier to spot if you use properly named variables, like numSegments or segmentSize instead of i1 or integer constants.

Also:

no need to wrap the sublists into new ArrayList
you can just count by increments according to the number of elements per sublist instead of using two counters, for the current sublist and the offset
you could use a ternary ... ? ... : ... instead of that if/else

How about this:

public static void main(String[] args) {
    List<String> arrayList = new ArrayList<String>();
    for (int i = 0; i < 23; i++) {
        arrayList.add(String.valueOf(i));
    }

    int size = 5;
    for (int start = 0; start < arrayList.size(); start += size) {
        int end = Math.min(start + size, arrayList.size());
        List<String> sublist = arrayList.subList(start, end);
        System.out.println(sublist);
    }
}

Here, size is the number of elements in each sublist. So instead of counting the segment of the list and increasing a second counter by 5 each time, you can just increase the first counter by five in the third argument of the for loop. Also, you can use the result of subList directly, without passing it to a constructor first. And you can get rid of the if-else by using min to determine the end index.

Output:

[0, 1, 2, 3, 4]
[5, 6, 7, 8, 9]
[10, 11, 12, 13, 14]
[15, 16, 17, 18, 19]
[20, 21, 22]

If instead of sublists with 5 elements you wanted five sublists, then use this (same result for the given example, but different for other list sizes):

int size = (int) Math.ceil(arrayList.size() / 5.0);


Is 'try / finally' the best way for me to handle (and close) this long-running IMAP4 connection? I'm writing a script to archive email messages from one IMAP folder to another. It looks, more or less, like the following. I've obfuscated about 30 lines unrelated to this question:

import imaplib
import getpass

def main():
    user = getpass.getuser() + '@mymailbox.com'
    mailbox = imaplib.IMAP4_SSL('mymailbox.com', 993)
    try:
        mailbox.login(user, getpass.getpass())
    except imaplib.IMAP4.error:
        raise RuntimeError('Credential error.')
    mailbox.select('my_mailbox')

    # Here lies some 30 lines not relevant to the question, but which
    # find mailbox messages, copies them to another folder, and
    # sets the delete flag in 'my_mailbox'.

    try:
        mailbox.close()    # which also expunges the mailbox
    except:
        pass
    mailbox.logout()

After working with my IMAP server for a while, I've discovered a fair amount of unexpected error conditions arising from its implementation of RFC 3501. No matter what, however, I always want to attempt mailbox.close() and mailbox.logout().

It sounds like a good occasion for a try / finally block, and that usage is supported by other examples. All the same, it feels unnatural to wrap some 40 lines of main() execution in a try-block:

def main():
    user = getpass.getuser() + '@mymailbox.com'
    mailbox = imaplib.IMAP4_SSL('mymailbox.com', 993)
    try:
        try:
            mailbox.login(user, getpass.getpass())
        except imaplib.IMAP4.error:
            raise RuntimeError('Credential error.')
        mailbox.select('my_mailbox')

        # Here lies some 30 lines not relevant to the question, but which
        # find mailbox messages, copy them to another folder, and
        # set delete flags in 'my_mailbox'.
    finally:
        try:
            mailbox.close()    # which also expunges the mailbox
        except:
            pass
        mailbox.logout()

Is that a common pattern? I could also write my own context manager; perhaps that's the better way to go. What's the best practice for long-running connections like this?

Move the working logic into its own function

def process_mailbox(mailbox):
    user = getpass.getuser() + '@mymailbox.com'
    try:
        mailbox.login(user, getpass.getpass())
    except imaplib.IMAP4.error:
        raise RuntimeError('Credential error.')
    mailbox.select('my_mailbox')
    #whatever else

def main():
    mailbox = imaplib.IMAP4_SSL('mymailbox.com', 993)
    try:
        process_mailbox(mailbox)
    finally:
        try:
            mailbox.close()    # which also expunges the mailbox
        except:
            pass
        mailbox.logout()


MemoryWriter Helper class I have created this memory writer helper to ease the write into memory process and I want your suggestions regarding it. I am very new to C++ but have 6 years knowledge of .NET languages like VB and C#.

#include <wtypes.h>

class MemoryWriter {
private:
    USHORT _currentIndex;
    LPVOID _targetAddress;
    template<typename T>
    static void editMemory(DWORD address, T data)
    {
        DWORD oldProtection;
        VirtualProtect((LPVOID)address, sizeof(T), PAGE_EXECUTE_READWRITE, &oldProtection);
        *((T*)address) = data;
        VirtualProtect((LPVOID)address, sizeof(T), PAGE_EXECUTE_READWRITE, NULL);
    }
public:
    MemoryWriter(DWORD address) {
        _currentIndex = 0;
        _targetAddress = (LPVOID)address;
    }
    template<typename T>
    void write(T data)
    {
        editMemory<T>(((DWORD)_targetAddress + _currentIndex), data);
        _currentIndex += sizeof(T);
    }
    template<typename T>
    void write(LPVOID address, T data)
    {
        editMemory<T>((DWORD)address, data);
        _currentIndex = (DWORD)address;
    }
    void reset(LPVOID newAddress = NULL)
    {
        _currentIndex = 0;

        if (newAddress)
            _targetAddress = newAddress;
    }
};

A general physical layout guideline: Put all public members, functions as well as variables, first, followed by protected members, and private members at the end. You want users to see public members first, followed by protected members. Hopefully, they don't have to see private members at all.

I added white spaces around functions to make them more readable.

class MemoryWriter {

   public:

      MemoryWriter(DWORD address) {
         _currentIndex = 0;
         _targetAddress = (LPVOID)address;
      }

      template<typename T>
         void write(T data)
         {
            editMemory<T>(((DWORD)_targetAddress + _currentIndex), data);
            _currentIndex += sizeof(T);
         }

      template<typename T>
         void write(LPVOID address, T data)
         {
            editMemory<T>((DWORD)address, data);
            _currentIndex = (DWORD)address;
         }

      void reset(LPVOID newAddress = NULL)
      {
         _currentIndex = 0;

         if (newAddress)
            _targetAddress = newAddress;
      }

   protected:

   private:

      USHORT _currentIndex;
      LPVOID _targetAddress;

      template<typename T>
         static void editMemory(DWORD address, T data)
         {
            DWORD oldProtection;
            VirtualProtect((LPVOID)address, sizeof(T), PAGE_EXECUTE_READWRITE, &oldProtection);
            *((T*)address) = data;
            VirtualProtect((LPVOID)address, sizeof(T), PAGE_EXECUTE_READWRITE, NULL);
         }
};


Add 100 to all values in nested dictionary I want to change all values in a multidimensional dictionary. I have written this line of code, which does what I want it to do and I am trying to find out if this is the optimal way or just some convoluted solution I came up with:

 dict_data = dict([x,dict([y, dict_data[x][y]+100] for y in dict_data[x])] for x in dict_data)

If you're using both keys and values from a dictionary, then using the items method:

... for key, val in dct.items() ...

is neater than iterating over the keys and including dct[key] everywhere. In Python 2.7+, you can use a dictionary comprehension (see e.g. the tutorial) rather than pass a list comprehension to dict:

dict_data = {key: {key_: val_+100 for key_, val_ in val.items()}
             for key, val in dict_data.items()}

Note that using key, val and the _ versions also makes it clearer what's happening than x and y.


Python odd number diamond I worked up a quick diamond program that takes only odd numbers while returning an error with even numbers or 0.

The code looks rather ugly to me, especially with the recurring int(). I haven't found out how to clean that up with my ENTER to quit.

while True:
    number = raw_input("Enter an odd number or hit ENTER to quit program: ")
    if number == "":
        print "\nQuitting program...\n"
        break
    elif int(number) == 0:
        print "\nCannot print symbols for a zero value, try again.\n"
    elif int(number) % 2 == 0:
        print "\nThat's an even number, try again.\n"
    else:
        for i in range((int(number))+1):
            if i % 2 == 0:
                None
            else:
                print ("*" * i).center(int(number))

        for i in range((int(number))-1):
            if i % 2 == 0:
                None
            else:
                print ("*" * ((int(number)) - (i + 1))).center(int(number))

You can test for emptiness of number by just if not number
After testing for emptiness, you could go straight to an int by adding number = int(number)
Inside the loops, when you test for i % 2 == 0:, and then put None as the loop body (that should really be pass), you could just test for if i % 2 != 0:, and replace None with the else body, and remove the else.
0 is even, so you can remove that test.
You can replace int(number) % 2 == 0 with not int(number) % 2.
Looking at the for loops, the range could be changed to range(1, number-1, 2), removing the need for an if statement.
You can also invert the last range, so the subtracting from number and 1 is not needed.
Python automatically adds newlines, so the \ns aren't really needed.

That leaves us with (after removing a few useless brackets):

while True:
    number = raw_input("Enter an odd number or hit ENTER to quit program: ")
    if not number:
        print "Quitting program..."
        break
    number = int(number)
    if not number % 2:
        print "That's an even number, try again."
    else:
        for i in range(1, number + 1, 2):
            print ("*" * i).center(number)
        for i in range(number - 2, 0, -2):
            print ("*" * i).center(number)

If you want to go functional, you can move your user input checking into a function. In this function you could also check if the user inputs a non-number, such as abc, by catching the exception or using str.isdigit:

def get_input():
    while True:
        number = raw_input("Enter an odd number or hit ENTER to quit program: ")
        if not number:
            return  # return None when the user wants to quit
        if number.isdigit() and int(number) % 2:
            return int(number)  # return the number, as its odd
        print "That's not a valid input (must be an odd integer), try again."

With this function, the rest of your program reduces to:

for number in iter(get_input, None):
    for i in range(1, number + 1, 2):
        print ("*" * i).center(number)
    for i in range(number - 2, 0, -2):
        print ("*" * i).center(number)

print "Quitting program..."

iter calls the function and gives its value until the function returns None (the sentinel value).

On a stylistic note:

You should always have spaced around operators, so range(int(number)+1) should be range(int(number) + 1) (that's PEP8).
You may want to add a big fat comment at the start of your program describing what it does.

Also, nice use of str.center, it avoided having too many loops!


Check whether a number is positive, negative, or zero I have a program which generates a number between 0 and 4 for both the player and the computer.  If the number is positive the player wins, and if it is negative the computer wins.

if dif == 1 or dif == 2 or dif == 3 or dif == 4:
    print 'Player wins!'
elif dif == -1 or dif == -2 or dif == -3 or dif == -4:
    print 'Computer wins!'
else:
    print 'Player and computer tie!'

How can I make the if and elif statments simpler?

We should use the comparison operators.  Greater than, less than.

if dif > 0:
    print 'Player wins!'
elif dif < 0:
    print 'Computer wins!'
else:
    print 'Player and computer tie!'

Another option, which I'm led to believe is "more Pythonic" (although, I'm not a Python dev, so don't take my word for it...), looks like this:

def tie():
    print 'Player and computer tie!'

def player():
    print 'Player wins!'

def computer():
    print 'Computer wins!'

options = {
     0 : tie,
     1 : player,
     2 : player,
     3 : player,
     4 : player,
    -1 : computer,
    -2 : computer,
    -3 : computer,
    -4 : computer
}

options[dif]()

If explicit values are important, than this solution is probably good.  However, if you really only care whether a value is greater than, less than, or equal to a specific value, than a simple if/elif/else as I first demonstrated is a good option.

Note that this bottom option will run into a KeyError if dif is not in the range of expected values.  The if/elif/else will work for any number.


Finding the number of permutations of an integer array with equaling difference (not in order) The array size is <= 16. The difference is defined as:

diff[i] = array[i+1] - array[i];

I need to find the number of permutations of the original array, which have a difference that is a permutation of the difference of the original array.

This is my code:

public class Main {
    Scanner scan = new Scanner(System.in);
    int N;
    int [] array_base;
    int [] first_diff;
    int result;

    public static void main(String[] args) {
        Main main = new Main();
        main.read();
        main.run();
    }

    void read() {
        N = scan.nextInt();
        array_base = new int [N];
        for (int i = 0; i<N; i++) {
            array_base[i] = scan.nextInt();
        }
        first_diff = first_difference();
    }

    int [] first_difference() {
        int [] temp = new int [N-1];
        for (int i=0; i < N-1; i++) {
            temp[i] = array_base[i+1] - array_base[i];
        }
        return temp;
    }

    void run() {
        permute(array_base,0);
        System.out.println(Integer.toString(result));
    }

    public void permute(int[] array, int k)
    {
        for(int i=k; i<array.length; i++)
        {
            int temp;
            temp = array[i];
            array[i] = array[k];
            array[k] = temp;
            permute(array, k+1);
            int temp2;
            temp2 = array[i];
            array[i] = array[k];
            array[k] = temp2;
        }
        if (k == array.length-1)
        {
            calculate(array);
        }
    }

    void calculate(int [] array) {
        int [] diff_values = new int [array.length-1];
        for (int i = 0; i < array.length-1; i++) {
            diff_values[i] = array[i+1] - array[i];
        }
        compare(diff_values);
    }

    void compare(int [] values) {
        boolean [] used_new = new boolean [values.length];
        boolean [] used_first = new boolean [values.length];
        for (int i = 0; i < values.length; i++) {
            used_new[i] = false;
            used_first[i] = false;
        }
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length; j++) {
                if (used_new[j]) {
                }
                else if (first_diff[i] == values[j]) {
                        used_new[j] = true;
                        used_first[i] = true;
                        break;
                }
            }
            if (used_first[i] == false) break;
        }
        if (areAllTrue(used_new) && areAllTrue(used_first)) {
            result += 1;
        }
    }

    public boolean areAllTrue(boolean[] array)
    {
        for(boolean b : array) if(!b) return false;
        return true;
    }

}

I do, however, see that this code is not fast as it could be. Could anyone give me some advice on how to speed it up?

You are using a class just to be able to able to mess with some kind of global values. This makes your code very hard to understand. It took me a while to unroll it all and get the following code :

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        run(read());

        run(fake_read());
    }

    static int[] fake_read() {
        int[] a = {1, 4, 2, 5, 7, 6, 9, 8, 3};
        return a;
    }

    static int[] read() {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int [] array = new int [N];
        for (int i = 0; i<N; i++) {
            array[i] = scan.nextInt();
        }
        return array;
    }

    static int [] first_difference(int[] array) {
        int N = array.length;
        int [] temp = new int [N-1];
        for (int i=0; i < N-1; i++) {
            temp[i] = array[i+1] - array[i];
        }
        return temp;
    }

    static void run(int[] array) {
        int [] first_diff = first_difference(array);
        int n = permute(array,0, first_diff);
        System.out.println(Integer.toString(n));
    }

    static public int permute(int[] array, int k, int [] first_diff)
    {
        int result = 0;
        for(int i=k; i<array.length; i++)
        {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
            result += permute(array, k+1, first_diff);
            temp  = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
        if (k == array.length-1)
        {
            result += calculate(array, first_diff);
        }
        return result;
    }

    static int calculate(int [] array, int [] first_diff) {
        int [] diff_values = new int [array.length-1];
        for (int i = 0; i < array.length-1; i++) {
            diff_values[i] = array[i+1] - array[i];
        }
        return compare(diff_values, first_diff);
    }

    static int compare(int [] values, int [] first_diff) {
        int result = 0;
        boolean [] used_new = new boolean [values.length];
        boolean [] used_first = new boolean [values.length];
        for (int i = 0; i < values.length; i++) {
            used_new[i] = false;
            used_first[i] = false;
        }
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length; j++) {
                if (!used_new[j] && first_diff[i] == values[j]) {
                        used_new[j] = true;
                        used_first[i] = true;
                        break;
                }
            }
            if (!used_first[i]) break;
        }
        if (areAllTrue(used_new) && areAllTrue(used_first)) {
            result += 1;
        }
        return result;
    }

    static public boolean areAllTrue(boolean[] array)
    {
        for(boolean b : array) if(!b) return false;
        return true;
    }
}

I'll be honest with you, I was hoping that once this was done, I'd be facing something somewhat easier to understand but it is not the case (the poor documentation and the function names do not help at all). I guess one could find a simpler (and faster ?) solution but the thing is that I don't even understand what is expected. The question might need clarification.


String Operation to Split on Punctuation I've a function to split text on punctuation and leave the rest of the string (including whitespace in other items of the list):

import unicodedata

def split_on_punc(text):
    chars = list(text)
    i = 0
    start_new_word = True
    output = []
    while i < len(chars):
        char = chars[i]
        if is_punctuation(char):
            output.append([char])
            start_new_word = True
        else:
            if start_new_word:
                output.append([])
            start_new_word = False
            output[-1].append(char)
        i += 1
    ##print(output)
    return ["".join(x) for x in output]

def is_punctuation(char):
    return True if unicodedata.category(char).startswith("P") else False

E.g.

split_on_punctuation("This, this a sentence. with lotsa' puncts!?@ hahaha looo world")

[out]:

['This',
 ',',
 ' this a sentence',
 '.',
 ' with lotsa',
 "'",
 ' puncts',
 '!',
 '?',
 '@',
 ' hahaha looo world']

It looks like a very complicated way to check through each character and then keep track of whether it's a start of a new word or not.

I'm looking for improvements in speed and simplicity.

Billy Mays here for the regex library!

It's API-compatible with the standard Python re module. It's powered by open source, and it's safe for colored fabrics and carpets!

The regex library offers things like \p{Punctuation}, which is actually a shorthand form of p{Punctuation=Yes} which is really a shortening of p{General_category=Punctuation}.

If you can make a Unicode query, regex supports it. Identifiers, Categories, Blocks, Diacritical Marks - it even does Coptic!

It cleans! It brightens! It eliminates odors! All at the same time!

test_data = "This, this a sentence. with lotsa' puncts!?@ hahaha looo world"
print(f"Test data: '{test_data}'")

import regex

PUNCT_RE = regex.compile(r'(\p{Punctuation})')

print(PUNCT_RE.split(test_data))

The output looks like:

Test data: 'This, this a sentence. with lotsa' puncts!?@ hahaha looo world'
['This', ',', ' this a sentence', '.', ' with lotsa', "'", ' puncts', '!', '', '?', '', '@', ' hahaha looo world']

regex converts your code from a whopping 21 lines to a 1-line method call-- a 2000% reduction! But you gotta call now!

Here's how to order:

pip install regex