Count the different positions reached in a cycle of permutations I have come across a problem on cyclic permutations. It is about swapping numbers around.
It starts out with input N < 100,000 which makes the first N natural numbers as orders: 1 2 3 ... N-1 N
Then we get the next input K < 200,000 as the period
Next N input lines are the swaps:
For example, the input is
5 4
1 3
1 2
2 3
2 4

There are 5 numbers and the swap period is 4. The first swap switches number at position 1 with position 3. The second swap is between position 1 and position 2. The third swap is between position 2 and position 3. The fourth swap is between 2 and 4. K+1th swap is same as first. K+2th swap is same as second. Etc.
The simulation for this is:
1 2 3 4 5
3 2 1 4 5
2 3 1 4 5
2 1 3 4 5
2 4 3 1 5
3 4 2 1 5
4 3 2 1 5
4 2 3 1 5
4 1 3 2 5
3 1 4 2 5
1 3 4 2 5
1 4 3 2 5
1 2 3 4 5

We can see that the original number at position 3 can go to positions 1, 2, and 3. The original number at position 1 can go to positions 1, 2, 3, 4. The original number at position 2 can go to positions 1, 2, 3, 4. The original number at position 4 can go to positions 1, 2, 3, 4. The original number at position 5 can go to positions 5.
Position 1 goes to 4 positions. Position 2 goes to 4 positions. Position 3 goes to 3 positions. Position 4 goes to 4 positions. Position 5 goes to 1 position.
Given that each output line is represented by y, the output is the number of totals positions the yth original position goes to. Output for this example is:
4
4
3
4
1

The memory limit is 256MB and the time limit is 2 seconds for noninterpreted languages such as C++ and 4 seconds for interpreted languages such as Java.

z, d = map(int, input().split())

S = []

pos = {}

for i in range(1, z+1):
  pos[i] = [i,]

permute = list(range(1, z+1))
for i in range(d):
  S.append(list(map(int, input().split())))

Flag = True

while Flag:
  Flag = False
  for i in S:
    if i[0] not in pos[permute[i[1]-1]]:
      Flag = True
      pos[permute[i[1]-1]].append(i[0])
    if i[1] not in pos[permute[i[0]-1]]:
      Flag = True
      pos[permute[i[0]-1]].append(i[1])
    permute[i[0]-1], permute[i[1]-1] = permute[i[1]-1], permute[i[0]-1]

for i in pos:
  print(len(pos[i]))

My solution takes too much space/time. Can you help me fix this?
I know this problem has DFS but I don't know what the graph to do DFS on looks like?

Naming
The question starts off talking about N and K.  Your code begins with reading in z and d.  The question text is ready-made documentation for your code; use the same names for the variables!
n, k = map(int, input().split())
Guilty, I said N and K but used n and k.  PEP 8, the Style Guide for Python Code recommends using snake_case for variables.  So we should also change S and Flag to s and flag.
But ...  what is flag?  Obviously, it is a flag, but a flag for what?  Perhaps changed would be a better name; you are looping while a change was made in the previous iteration.
Similarly, S is your list of swaps.  Why not call it swaps?
Don't relookup values
Python is an interpreted language.  It doesn't do any data-flow analysis to determine if the value of an expression will be used again.  It can't, since the meaning of operations can be changed on the fly.
In the for i in S loop, how many times is i[0] and i[1] used?  Six times each.  Each time, the interpreter looks up the object stored in i, and calls the __getitem__ method to fetch the value.  Let's fix this by looking up the value only once, and storing the values in (say) p and q:
    for p, q is swaps:
        if p not in pos[permute[q - 1]]:
            changed = True
            pos[permute[q - 1]].append(p)
        ...

That is immediately clearer.  No extra [0] and [1] to confuse the issue.
Use O(1) lookups instead of O(K) searches
You're using if thing not in container: container.append(thing).  This is a lot like a set.  A set can only contain one instance of an item.  But unlike a list, if thing not in container is O(1) on a set, where as the with a list, the entire list has to be searched to ensure the thing is not inside the list.
Two simple changes.  First, instead of pos[i] = [i,] (the comma is actually unnecessary), initialize it with pos[i] = {i}.  Second, instead of .append(), use .add() to add the value to the set.
Note: sets are more complex than lists.  This may actually slow things down and use more memory, if the number of things in the containers is small.  The sets gain their speed advantage when they contain many elements.  So profile this change, especially using larger problem sets.
Explicit is better than implicit
swaps = []
for i in range(k):
  swaps.append(list(map(int, input().split())))

What happens if an input line has more than two numbers?  The input will be split into whole bunch of terms, each term will be mapped (converted) to an integer, and stored as a list inside the swaps list!
Oops.
If the program crashes, it will happen well after this point in the code.
It is better to crash early.  You expect exactly two values.  Be explicit.
swaps = []
for i in range(k):
  swaps.append(list(map(int, input().split(maxsplit=1))))

If given more than two numbers, say 12 23 34, then split will return "12" and "23 34", and int("23 34") will raise a ValueError.  The bug will be caught earlier.
Map the problem to Python, if possible
Python uses 0-based indexing.  The problem uses 1-based indexing.  You can get rid of the +1 in range statements, and -1 in the solution code by mapping the problem into a more Pythonic version.
For example, instead of swapping numbers at positions 1 and 3, we'll swap them at positions 0 and 2.  This just requires adjusting the swap positions as we read them in:
swaps = []
for i in range(k):
  p, q = map(int, input().split())
  swaps.append([p - 1, q - 1])

Note.  The explicit maxsplit=1 went away because we are assigned the result of map to a tuple of two variables, which requires exactly two values.  Explicit is better than implicit ... especially when the it can be expressed implicitly!
Reworked Code
n, k = map(int, input().split())

pos = {}
for i in range(n):
  pos[i] = {i}

permute = list(range(n))

swaps = []
for i in range(k):
  p, q = map(int, input().split())
  swaps.append([p - 1, q - 1])

changed = True

while changed:
  changed = False
  for p, q in swaps:
    if p not in pos[permute[q]]:
      changed = True
      pos[permute[q]].add(p)
    if q not in pos[permute[p]:
      changed = True
      pos[permute[p]].add(q)
    permute[p], permute[q] = permute[q], permute[p]

for i in pos:  # Note: relies on ordered dictionary
  print(len(pos[i]))

Algorithmic improvement
1 2 3 4 5
After one iteration of swaps, you end up with this:
2 4 3 1 5
We can see we have moved

1 -> 2, 2 -> 4, 4 -> 1.  (length 3)
3 -> 3
5 -> 5

The 1 visited locations 1, 3, 2 and 4.  The 2 visited locations 2, and 1.  The 4 visited locations 4 and 2.  On subsequent iterations, the 2 will have moved into the 1's starting position and will visit 1, 3, 2 and 4, and so on.  So we have 1, 2, and 4 all visiting locations 1, 2, and 3 and 4 ... for a total of 4 locations
3 will visit 3, 1, and 2 and return to 3.
5 stays at 5.
All that is required is one pass through the swaps array to determine which positions each starting point visits, and what ending position it will have.  From that, the "rings" can be determined.  All starting positions in each ring will visit all the locations visited by every position in the ring.
With only one pass through the swaps array required, we don't need to save the swaps into a swaps list; it can be processed on the fly.  This helps the solution stay within the memory constraint.
n, k = map(int, input().split())

pos = [{i} for i in range(n)]
permute = list(range(n))

# Perform swaps, recording which values appear in which positions
for _ in range(k):
    p, q = map(int, input().split())
    p -= 1
    q -= 1

    pos[permute[q]].add(p)
    pos[permute[p]].add(q)
    permute[p], permute[q] = permute[q], permute[p]

# Implementation of final steps left to student


Which products should be purchased with the given amount of money: Hackerrank? I am writing code for the challenge given here . Below the text:

  Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they
  pool their money to buy ice cream. On any given day, the parlor offers
  a line of flavors. Each flavor has a cost associated with it. Given the value of and the of each flavor for trips to the Ice Cream
  Parlor, help Sunny and Johnny choose two distinct flavors such that
  they spend their entire pool of money during each visit. ID numbers
  are the 1- based index number associated with a cost. For each trip to the parlor, print the ID numbers for the two types
  of ice cream that Sunny and Johnny purchase as two space-separated
  integers on a new line. You must print the smaller ID first and the
  larger ID second.

  For example, there are flavors having cost = [2, 1, 3, 5, 6]. Together they have money = 5 to spend.
  They would purchase flavor ID's 1 and 3  for a cost of 2 + 3 = 5  . Use 1 based indexing
  for your response.

I have written code for the problem. However, it is running for most of the test cases except three. The error message that they show is that "Your code did not execute within the time limits". Apparently the code needs to be optimized. Can anyone please tell how may I do that?

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the whatFlavors function below.
    static void whatFlavors(int[] cost, int money) {

         int baseItem=0, comparedItem = 0,totalAmount=0, chosenFlavour1=0,
                chosenFlavour2=0,flag=0;
        for(int i = 0 ; i<(cost.length-1); i++)
        {
            baseItem = cost[i];
            for(int j = (i+1); j< (cost.length);j++)
            {
                comparedItem= cost[j];
                totalAmount = baseItem + comparedItem;

                if(totalAmount == money)
                {
                    chosenFlavour1 = i;
                    chosenFlavour2 = j;
                    flag = 1;
                    break;
                }

            }

            if(flag == 1)
            {
               break;
            }
        }

        chosenFlavour1++;
        chosenFlavour2++;
        System.out.println(chosenFlavour1+" "+chosenFlavour2);

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int money = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] cost = new int[n];

            String[] costItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int costItem = Integer.parseInt(costItems[i]);
                cost[i] = costItem;
            }

            whatFlavors(cost, money);
        }

        scanner.close();
    }
}

Your algorithm is slow in some cases because of the time complexity O(n^2). (starting the second loop from i+1 makes it twice faster than starting from 0, but it doesn't change the time complexity which has much greater impact on performance)

To improve your time complexity you need to reduce the amount of times you look at items in the array. One way of doing it is by first sorting it (more precisely, sorting index-value pairs to keep record of the original indexing) and then iterating over the sorted array once (O(n)) while taking advantage of the fact that it is sorted. I'll leave you the task of learning about integer sorting algorithms (of time complexity O(n log n)), and only explain how to use the sorted array to find the final answer.

You can look at both edges of the array (smallest and biggest number), if their sum is too small you can increase it by advancing the lower-edge index to look at a bigger number, and if the sum is too big you can decrease it by advancing the higher-edge index to look at a smaller number. Repeat it until you reach the needed sum, then get the original indices and increment them to get the IDs you need for the output.

As @vnp hinted, there is a better solution than mine (with time complexity O(n)) using a hash table.


PHP color and image loop I did create a function which loops through the colors of a product and outputs a div with the specific color. After that it finds the image for the available colors. But I think the code can be a lot smarter.

Can someone optimize my code?

<?php
$brand_terms = get_the_terms($post, 'pa_kleur');
$brand_string = ''; // Reset string
foreach ($brand_terms as $term) : ?>
<?php

    if (($term->name) == 'Roze') {
        echo '

';

        $variations = $product->get_available_variations();
        foreach ( $variations as $key => $value ) {
    ?>
        <?php if ($value['attributes']['attribute_pa_kleur'] == 'roze') { ?>

            <?php echo $value['image']['url']; }?>

    <?php
    }
    }
    if (($term->name) == 'Grijs') {
        echo '

';

        $variations = $product->get_available_variations();
        foreach ( $variations as $key => $value ) {
    ?>
        <?php if ($value['attributes']['attribute_pa_kleur'] == 'grijs') { ?>

            <?php echo $value['image']['url']; }?>

    <?php
    }
    }
endforeach;
?>

Thanks for your time!

keeping separate actions on a different line and tabbing your code will go a long way with making your code readable.
avoid declaring single-use variables
I don't see $brand_string being used, so that declaration can be omitted.
I do not prefer the endforeach syntax.  Despite being declarative, I find it unnecessarily verbose.  Good tabbing is always enough to help me track the nesting of control structures and functions.
move all inline styling to an external stylesheet.  Using meaningful class names to assign appropriate colors is most logical here.
I expect all
 tags are display: block; by default -- I doubt this style declaration is necessary.
use a lookup array to swiftly translate $term->name values into class attribute values and eliminate the mostly redundant if blocks.
don't declare $key if you never intend to use it.
filter the variations array based on the lowercase value of $term->name and use a conditional break for best efficiency.  I am confidently assuming that there will only be one match in your variations array based on the trailing

your list item should be nested inside of a list tag (e.g.
)
remove the  tags -- they are unnecessary markup.  If you need to style the list items, style the
 tags
if you must have your data processing in the same script as your content outputting, then I recommend doing your processing first, then keeping your markup readable by referencing the generated variables

Code:

$colorClasses = [
    'Roze' => 'roze-kleur',
    'Grijs' => 'grijze-kleur',
];
foreach (get_the_terms($post, 'pa_kleur') as $term) {
    $lowerColor = lcfirst($term->name);
    $colorUrl = 'you_decide_the_url';
    foreach ($product->get_available_variations() as $row) {
        if ($row['attributes']['attribute_pa_kleur'] === $lowerColor) {
            $colorUrl = $value['image']['url'];
            break;
        }
    }

    echo '

name] ?? 'default-kleur') , '">

' , $colorUrl , '

';
 }


Init.d script for Rails managing a Rails app via Unicorn This script is to enable the remote management of a Rails app via one script.
I pieced it together from various blog posts. I am not to familiar with some of the BASH functionality that is used. It seems to work okay, but I wonder if there is anything that I have done sub-optimally in my naïveté.

#!/bin/bash
# /etc/init.d/unicorn

# ### BEGIN INIT INFO
# Provides:          unicorn
# Required-Start:    $network $remote_fs $local_fs
# Required-Stop:     $network $remote_fs $local_fs
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Stop/start unicorn
### END INIT INFO

export PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin

PROJ_ENV="staging"
RBENV_VERSION=2.2.2
RBENV_ROOT=/opt/rbenv

PROJ_NAME="myapp"

PID_FILE=/var/www/$PROJ_NAME/current/tmp/pids/unicorn.pid
OLD_PID_FILE=$PID_FILE.oldbin
PROJ_DIR=/var/www/$PROJ_NAME
TAG='[unicorn]'

UNICORN_CONFIG=$PROJ_DIR/current/config/unicorn/$PROJ_ENV.rb
DEPLOY_USER=ec2-user
[ -f $PID_FILE ] && KPID=`cat $PID_FILE`

# Start the service
start() {
     # [ is the 'test' command  -f file? -a and -n variable -d directory
    if [ -f $PID_FILE -a -n "${KPID}" -a -d "/proc/${KPID}" ]; then
          logger -sit $TAG "Process ${KPID} in PID file $PID_FILE exists. Service '${PROJ_NAME}' should be running"
        exit 1
    else
        logger -sit "$TAG" "Process doesn't exist. Trying to start server..."
        #su - $DEPLOY_USER -c "bash -c 'cd $PROJ_DIR/current ; pwd      ; /opt/rbenv/bin/rbenv exec bundle exec unicorn -v'"
        su - $DEPLOY_USER -c "bash -c 'cd $PROJ_DIR/current ; pwd       ; /opt/rbenv/bin/rbenv exec bundle exec unicorn -c $UNICORN_CONFIG -E $PROJ_ENV -D'"
        if [[ $? == 0 ]]; then
            logger -sit "$TAG" "server started"
        else
            logger -sit "$TAG" "FAILED to start server"
            exit 1
        fi
    fi
}

# Stop the service
stop() {
        su $DEPLOY_USER -c "kill -TERM $(cat $PID_FILE)"
        sleep 2
        if [[ ! -f $PID_FILE ]]; then
                logger -sit "$TAG" "Server stoped"
        else
                logger -sit "$TAG" "FAILED to stop server"
                exit 1
        fi
}

# Reload service
reload() {
    logger -sit "$TAG" "Trying to reload server"
    kill -USR2 $(cat $PID_FILE)
    sleep 1
    if [[ -f $OLD_PID_FILE ]]; then
        logger -sit "$TAG" "Server reloaded"
    else
        logger -sit "$TAG" "FAILED to reload server"
        exit 1
    fi
}

restart() {
    if [ -f $PID_FILE -a -n "${KPID}" -a -d "/proc/${KPID}" ]; then
        logger -sit "$TAG" "Restarting server"
        kill -HUP $(cat $PID_FILE)
    else
      logger -sit "$TAG" "Process doesn't exist. Running start"
       #$0 is the path of the script
      $0 start
    fi
}

### main logic ###
case "$1" in
    start)
        start
        ;;

    stop)
        stop
        ;;

    restart)
        restart
        ;;
    reload)
        reload
        ;;
    *)
        echo $"Usage: $0 {start|stop|restart|reload}"
        exit 1
esac
exit 0

Quoting command line arguments

This is not safe:

[ -f $PID_FILE ] && ...

Variables and the result of $(...) should be double-quoted to protect from parameter expansion and globbing:

[ -f "$PID_FILE" ] && ...

A longer example (fixed version, compare with your original):

if [ -f "$PID_FILE" -a -n "${KPID}" -a -d "/proc/${KPID}" ]; then
      logger -sit "$TAG" "Process ${KPID} in PID file $PID_FILE exists. Service '${PROJ_NAME}' should be running"

The lack of quoting is the most common violation in the posted code,
review carefully.
Copy-paste to https://www.shellcheck.net/, it should help.

Use $(...) instead of `...`

The backtick format is obsolete, and harder to read. Always use $(...).

Usability

The stop function waits for 2 seconds after sending the TERM signal to the process to check if the PID file still exists.
That seems a bit arbitrary, and possibly fragile.
It would be better to sleep for 1 second 5 times in a loop.
This is also pretty arbitrary, but a bit more flexible.

Pointless [ -f $PID_FILE ] && KPID=`cat $PID_FILE`

This is executed always, regardless of the sub-command.
And then most sub-commands reload the value in $PID_FILE.
It would be better to create a function for getting the PID,
and calling that function when you need it.

Signal to PID that might not exist

Some of the functions signal to $(cat "$PID_FILE"),
without making sure that PID actually exists,
or even that $PID_FILE actually exists.
It would be better to validate the state more accurately,
and raise errors as appropriate.

Recursive execution

The restart function calls $0 start to restart the script.
It would be more natural to simply call the start function directly.


Text to Brainfuck translator I just wanted to mess with my friend a little and wanted to text him in Brainfuck. Being a coder like me, I decided, why not just write a quick script to translate it for me?

Considering that most characters that I will be using in a regular English chat will be between 0-127, the algorithm will take the nearest factor of ten. Then it will add the result of the char number modulus that factor. Then I will translate that into Brainfuck.

I am ready to take all criticism so please give your opinion. Also, please test in and find any case where my algorithm will fail.

def letter_to_brainfuck(letter):
    num = ord(letter)
    return '+'*int(num / 10) + '[>++++++++++<-]>' + '+'*(num % 10)

def brainfuck_print(letter_list):
    return ''.join([i +'.>\n' for i in letter_list])

print(brainfuck_print([letter_to_brainfuck(i) for i in list(input())]))

If you pass a long text to the code generator, the resulting program will overflow its memory. This is because you do >+++.> for each character, but you never come back to clean up behind you. Instead of >+++.>, the generated code should be >+++.[-]<, which is slower but can handle arbitrary long text.

You say that your text contains mostly ASCII characters. Therefore it is probably more efficient to add or subtract the difference of the characters. In pseudo code:

curr = 0
for ch in str:
    if ch > curr:
        emit_add(ch - curr)
    if ch < curr:
        emit_sub(curr - ch)
    emit_putchar()
    curr = ch
emit_setzero()

Emitting only the difference is especially efficient for long runs of lowercase ASCII letters.

Regarding your Python code: are you sure that Python really does not have a repeat string function? The letter_to_brainfuck function would become a one-liner then.


simple python music quiz I'm currently learning python and created a simple music quiz. the rules of the game are as follows:

The user has two chances to guess the name of the song If the user guesses the answer correctly the first time, they score 3 points. If the user guesses the answer correctly the second time they score 1 point.The game repeats.The game ends when a player guesses the song name incorrectly the second time.

I developed the following but the I wasn't very pleased with the update leaderboard function as the indexing of the 2d list was confusing to code. is there an easier way to do the same thing?

start_quiz returns two variables and is there a way to sort of 'unpack' what's returned?

# 21:23 5th dec 2019
from Resources.songs import songs
from Resources.users import users
import random
import pickle

def main():
    username = login()
    print('hello', username, 'welcome to the music quiz')
    guessed_wrong_twice = False
    result = None
    while not guessed_wrong_twice:
        result = start_quiz()
        guessed_wrong_twice = result[1]
    score = result[0]
    print('you scored', score)
    leaderboard = leaderboard_updating(username, int(result[0]))
    print('The leaderboard:\n', leaderboard)

main()

def login():
    logged_in = False
    entered_username = None
    while not logged_in:
        entered_username = input("please enter username: ")
        if entered_username in users:
            entered_password = input('please enter password: ')
            if entered_password == users[entered_username]:
                logged_in = True
        else:
            print("password or username incorrect try again")
            logged_in = False

    return entered_username

def start_quiz():
    score = 0
    guessed_wrong_twice = False
    song_chosen = choosing_song()
    print('artists name is', song_chosen[1])
    first_letter = song_chosen[0][0]
    guess = input("the song begins with" + first_letter)
    if guess.lower == song_chosen[0]:
        score += 3
    else:
        guess = input("the song begins with " + first_letter)
        if guess.lower == song_chosen[0]:
            score += 1
        elif guess != song_chosen[0]:
            guessed_wrong_twice = True
    return score, guessed_wrong_twice

def choosing_song():
    song_chooser = random.randint(1, 3)
    song_artist = songs[song_chooser][1]
    song_name = songs[song_chooser][0]
    return song_name, song_artist

# index 0 of each 'sub list' is the users name index 1 is their highest score

def leaderboard_updating(username, score=0):

    leaderboard = pickle.load(open("leaderboard.pickle", "rb"))

    index_row_list = [leaderboard.index(row) for row in leaderboard if username in row]
    index_row = int(index_row_list[0])
    if leaderboard[index_row][1] < score:
        leaderboard[index_row][1] = score

    leaderboard = sorted(leaderboard, key=lambda x: x[1])

    pickle.dump(leaderboard, open("leaderboard.pickle", "wb"))
    return leaderboard

Note: Not an answer, an extended comment.

There's no way your code can work the way you intend it to.

Your leader board doesn't work when the user isn't already in the leader board.

The second line will IndexError in these cases:

index_row_list = [leaderboard.index(row) for row in leaderboard if username in row]
index_row = int(index_row_list[0])

You can never score more than 3 points on the leader board.

while not guessed_wrong_twice:
    result = start_quiz()
    guessed_wrong_twice = result[1]
score = result[0]

You can never enter a correct song.

if guess.lower == song_chosen[0]:

Looks innocent enough, but it's never true. Unless song_chosen[0] is str.lower. In which case it's always true.

>>> 'abc'.lower == 'abc'
False

Now 1 & 2 are pretty minor, so if your code only contained them I'd just answer. But 3 means it's impossible for your code to work.

Given that start_quiz was the last function I reviewed I have a half written review for you. Please fix the above problems for it.


Making a Battleship game I'm making a Battleship game using python 2.7.  However, how to make it is not currently my issue.  The main aspect that I'm asking about is the style and method of making the code.  Am I following best (or even good) practice? Are the comments too much, too little, unclear? If someone could give me some pointers based on my code on how to make it more readable and standard, it would be highly appreciated.

from random import randint

# Adds the board to use as a list later
board = []

# Numbering my rows and columns
row_num = ["0", "1", "2", "3", "4"]

# "0" string begins a space as the row numbering pushed in the output text.  Could the space be better implemented in print board?
columns = ["  0", "1", "2", "3", "4"]

for x in range(5):
    board.append(["-"] * 5)

# Function for making the board.  Added tabs to make it more in the middle and clearer.
def print_board(board):
    row_num = 0
    print "\t\t", "   ".join(columns)
    for row in board:
        print "\t\t", row_num, "   ".join(row)
        row_num += 1

print "Let's play Battleship!"
print_board(board)

# Functions for playing agasint the computer
def random_row(board):
    return randint(0, len(board) - 1)

def random_col(board):
    return randint(0, len(board[0]) - 1)

print "Would you like to play agasint the computer or against a friend?"

# Choosing the location of the battleship and data validation of raw_input
def game_type(game_input):
    global ship_row
    global ship_col
    if game_input == 1:
        ship_row = random_row(board)
        ship_col = random_col(board)
    elif game_input == 2:
        ship_row = int(raw_input("Choose a Row to place your battleship:"))
        ship_col = int(raw_input("Choose a Column to place your battleship:"))
    else:
        print "That is not a valid input.  Please try again"
        game_type(int(raw_input("To play against the computer press 1, to play against a friend press 2: \n")))

game_type(int(raw_input("To play against the computer press 1, to play against a friend press 2: \n")))

# Printing the sollution for easy testing
print ship_row
print ship_col

# Starts the actual game
for turn in range(4):
    turn
    print "Turn", turn + 1

    guess_row = int(raw_input("Guess Row:"))
    guess_col = int(raw_input("Guess Column:"))

    if guess_row == ship_row and guess_col == ship_col:

        print "Congratulations! You sunk my battleship!"
        board[guess_row][guess_col] = "X"
        print_board(board)
        break
    # Data Validation for the inputs.  Maybe this shouldn't make a player miss but rather allow to retry
    else:
        if (guess_row < 0 or guess_row > 4) or (guess_col < 0 or guess_col > 4):
            print "Oops, that's not even in the ocean."
        elif(board[guess_row][guess_col] == "O"):
            print "You guessed that one already."
        else:
            print "You missed my battleship!"
            board[guess_row][guess_col] = "O"
            if turn == 10:
                print "Game Over"
                break
        print_board(board)

Reduce global variables

The game_type function can return the ship row and column, there is no need to modify them as global variables, my suggestion is easy to implement:

def game_type(game_input):
    if game_input == 1:
        ship_row = random_row(board)
        ship_col = random_col(board)
    elif game_input == 2:
        ship_row = int(raw_input("Choose a Row to place your battleship:"))
        ship_col = int(raw_input("Choose a Column to place your battleship:"))
    else:
        print "That is not a valid input.  Please try again"
        return game_type(int(raw_input("To play against the computer press 1, to play against a friend press 2: \n")))
    return ship_row, ship_col

ship_row, ship_col = game_type(int(raw_input(
    "To play against the computer press 1, to play against a friend press 2: \n")))

Also, columns is only ever used inside print_board so I would define it as a default parameter, to make it clear that the rest of the program does not need it:

def print_board(board, columns = ["  0", "1", "2", "3", "4"]):
    print "\t\t", "   ".join(columns)
    for row_num, row in enumerate(board):
        print "\t\t", row_num, "   ".join(row)

First define, then "do stuff"

Organization is a nice property  of code. Now you mix function definitions and code that "does things" (namely code that interacts with the user).

I would define at first all of the functions, and then run them.

Write a function for input checking

The main logic (now incorporated into main battleship_game function) is full of checks to make sure that the input is valid, abstracting the input checking to another function will condensate the top-level logic.

Costumize

After you define a battleship_game function, you can have fun customizing it by passing all kinds of different parameters: the board size, the number of turns, whether to run in debugging mode or not...

This will allow you to play slightly different battleship games by using the same code.

Use enumerate

99% of the times manually incrementing a counter is not needed in Python:

def print_board(board, columns = ["  0", "1", "2", "3", "4"]):
    print "\t\t", "   ".join(columns)
    for row_num, row in enumerate(board):
        print "\t\t", row_num, "   ".join(row)

Using built-ins is usually simpler than writing your own.

Avoid do-nothing lines

In Python the line:

value

Where value may be anything, does nothing. In your code the line

turn

Does nothing at all, remove it to simplify the code.

List comprehension + _

A list comprehension is preferred over append in simple cases, _ signifies that you are not interested in the value.

board = [["-"] * 5 for _ in range(5)]

Remove unused definitions

row_num is defined but never used, so delete the line:

row_num = ["0", "1", "2", "3", "4"]

Use the range that fits your needs best

>>> help(range)
Help on class range in module builtins:

class range(object)
 |  range(stop) -> range object
 |  range(start, stop[, step]) -> range object
 |
 |  Return a sequence of numbers from start to stop by step.
 ...

Using the second version of range will avoid incrementing afterwards:

for turn in range(1, 5):
    print "Turn", turn

I also find it more obvious this way that turns are 1-indexed.


Encapsulated state in clojure While going through SICP and trying to implement the code in clojure, I've found that while I can get the code in chapter 3 to work, it seems to go against Clojure idioms, but I can't quite imagine the "Clojure way" to do it either.

Take for example, the digital circuit simulator. This is my implementation:

(declare call-each)
(defn make-wire []
  (let [signal-value (atom 0)
        action-procedures (atom '())
        set-my-signal (fn [new-value]
                        (if-not (= @signal-value new-value)
                          (do (reset! signal-value new-value)
                              (call-each @action-procedures))
                          'done))
        accept-action-procedure! (fn [proc]
                                   (swap! action-procedures
                                          conj proc)
                                   (proc))
        dispatch (fn [m]
                   (cond (= m 'get-signal) @signal-value
                         (= m 'set-signal) set-my-signal
                         (= m 'add-action) accept-action-procedure!
                         :else (error "Unknown operation -- WIRE" m)))]
    dispatch))

(defn call-each [[proc & rest :as procedures]]
  (if (empty? procedures)
    'done
    (do (proc)
        (call-each rest))))

(defn get-signal [wire]
  (wire 'get-signal))
(defn set-signal! [wire new-value]
  ((wire 'set-signal) new-value))
(defn add-action! [wire action-procedure]
  ((wire 'add-action) action-procedure))

As you can see, it has an internal signal-value and action-procedures as state. Is this the natural way to do this in Clojure, and if not, how would you do it?

There are a few problems.

You should not read the value from an atom and update it conditional on its value, as in set-my-signal. It's value may have changed in between those two calls. In this case refs instead of atoms may need to be used.
Do not use unbounded recursion as in call-each.

Instead of:

(defn call-each [[proc & rest :as procedures]]
  (if (empty? procedures)
    'done
    (do (proc)
        (call-each rest))))

You can do:

(defn- call-each [procedures]
  (doseq [proc procedures] (proc)))

error is not a clojure function. So you should have implemented in clojure with throw... Just use throw instead. It would read something like: (throw (UnsupportedOperationException. (str "Unknown operation -- WIRE " m) nil)). Or instead of throwing an exception you can return nil. So it would be easier to extend (add new messages by decorating) the make-wire constructor.
Case analysis (cond) on a constant symbols is someone does a lot in Scheme. Clojure maps are more readable though. Also using keywords :get-signal instead of symbols 'get-signal is more conventional in accessing the fields of a map, record, so on..

make-wire would be read something like this, if I wrote it in Clojure:

(defn make-wire []
  (let [signal-value (ref 0)
        action-procedures (ref '())]
    {
     :get-signal (fn [] @signal-value)
     :set-signal (fn [new-value]
                   (dosync
                     (when-not (= @signal-value new-value)
                       (ref-set signal-value new-value)
                       (call-each @action-procedures))))
     :add-action (fn [proc]
                   (dosync
                     (alter action-procedures conj proc)
                     (proc)))
     }))

The point of encapsulation as taught in SICP is that you can combine components independent of their implementation details.

So you might want to define a protocol explicitly for a wire:

(defprotocol Wire
  (get-signal [w])
  (set-signal! [w new-value])
  (add-action! [w action-procedure]))

Then whether you implement it using a record:

(defrecord WireRec [signal-value action-procedures]
  Wire
  (get-signal [_] @signal-value)
  (set-signal! [_ new-value]
    (dosync
      (when-not (= @signal-value new-value)
        (ref-set signal-value new-value)
        (call-each @action-procedures))))
   (add-action! [_ proc]
     (dosync
       (alter action-procedures conj proc)
       (proc))))

(defn make-wire2 []
  (WireRec. (ref 0) (ref '())))

Or a map:

(defn make-wire3 []
  (let [m (ref {
                :signal-value 0
                :action-procedures '()
                })]
  (reify Wire
    (get-signal [_] (:signal-value @m))
    (set-signal! [_ new-value]
          (dosync
            (when-not (= (:signal-value @m) new-value)
              (alter m assoc :signal-value new-value)
              (call-each (:action-procedures @m)))))
    (add-action! [_ proc]
      (dosync
        (alter m update-in [:action-procedures] conj proc)
        (proc))))))

should not matter.


Choose a color with probability proportionate to its weight in a group of colors Input: An array of colors with weights. e.g [['red', 10], ['blue', 20], ['green', 30]]

Output: A random color from the array, based on it's proportion to the other colors. So for the example above, red should show up 1/6 of the time, blue 2/6, green 3/6.

I was asked this during an interview. After talking to that interviewer I went from an O(n2) solution to this, which runs in O(n). I feel like there should be a better way?

def random_color(colors_with_weights)
  probabilities = {}
  count = 0
  colors_with_weights.each do |color_weight|
    probabilities[count..count+color_weight[1]] = color_weight[0]
    count = count + color_weight[1]
  end
  random_number = rand(count)
  random_range = probabilities.keys.find { |k| k.include?(random_number) }
  probabilities[random_range]
end

colors_with_weights = [['red', 10], ['blue', 20], ['green', 30]]
puts random_color(colors_with_weights)

I can't think of a better algorithm.  There is a minor bug, though: you are using inclusive-inclusive ranges, when they should be inclusive-exclusive ranges.  That means that you've overweighted red by \$\frac{1}{60}\$ and underweighted green by \$\frac{1}{60}\$.

The way it the algorithm is expressed could be tweaked a bit.

The count isn't counting elements; it's more of a sum.
The block could accept two parameters |color, weight| to automatically destructure |color_weight|.
The hash isn't really being used for a lookup, so I would just keep it as an array.

def random_color(colors_with_weights)
  sum = 0
  colors_with_cumul_weights = colors_with_weights.collect do |color, weight|
    [color, sum ... (sum += weight)]
  end
  rand_num = rand(sum)
  colors_with_cumul_weights.find { |color, range| range === rand_num }.first
end

In an interview situation, I'd just accept your code as a fine answer.


Determining a salary for buying a house in 36 months I did this programming challenge. Part C of the challenge, is to find the salary you have to save every month to be able to buy a house in 36 months.

This is my first time using bisection search so I just want to make sure that I did it correctly. I question the efficiency of my program because in test case 2 for part C, the supposed number of guesses is 9, but my program guesses 13 times.

annual_salary = int(input('Enter your annual salary.'))
total_cost = 1000000
semi_annual_raise = .07
portion_down_payment = total_cost * 0.25
current_savings = 0
r = 0.04
guesses = 1
low = 0
high = 1

while abs(portion_down_payment-current_savings) > 100:
    portion_saved = (low + high) / 2
    salary = annual_salary
    current_savings = 0

    for month in range(1, 37):
        if month % 6 == 1 and month != 1:
            salary += salary*semi_annual_raise
        current_savings += current_savings*r/12
        current_savings += salary/12 * portion_saved

    if current_savings >= portion_down_payment:
        high = portion_saved
    elif current_savings < portion_down_payment:
        low = portion_saved

    portion_saved = (low+high)/2
    guesses += 1

print(portion_saved, guesses)

I don't think your code is an inefficient bisection search.  The example which needed fewer iterations could simply be getting lucky and getting within the $100 terminal condition on one of its earlier steps.  That said, here are a couple of implementation pointers:
Don't recalulate salary
The salary used in the loop, increases every six months.  But it does not change based on savings rate, so is the same for every guess.  Therefore calculate it once before starting the guessing.  It could look something like this:
monthly_salary = [annual_salary / 12]
for month in range(2, 37):
    monthly_salary.append(monthly_salary[-1])
    if month % 6 == 1:
        monthly_salary[-1] *= (1 + semi_annual_raise)

Or using itertools, something like this:
import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))

Consider using itertools.accumulate()
The loop which sums up the savings can be done using itertools.accumulate().  Basically you define a function which is passed the previous total and an element from an iterable.  Then returns the next total.
def accum(total, salary):
    return total * (1 + r / 12) + salary * portion_saved

Then the function, and an iterable is passed to accumulate:
*_, current_savings = it.accumulate(monthly_salaries, accum)

Finally the *_, current_savings = ... can be used to gather the last item in an iterable.
The *_ is rather cryptic.  The _ is just a variable name that is often used in Python to indicate that it is unneeded.  The * is used for variable expansion.  See Pep 448 for more details.
Revamped code:
annual_salary = 150000
total_cost = 1000000
semi_annual_raise = .07
portion_down_payment = total_cost * 0.25
current_savings = 0
r = 0.04
guesses = 0
low = 0
high = 1

import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = [0] + list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))

portion_saved = (low + high) / 2
while abs(portion_down_payment - current_savings) > 100:

    def accum(total, salary):
        return total * (1 + r / 12) + salary * portion_saved

    *_, current_savings = it.accumulate(monthly_salaries, accum)

    if current_savings >= portion_down_payment:
        high = portion_saved
    else:
        low = portion_saved

    portion_saved = (low + high) / 2
    guesses += 1

print(portion_saved, guesses)


Testing Terminal Text Game with Classes and Game Loop I am making a super simple and dumb terminal text game to try out unittest in python. I have ran into a problem. When I run the test, the game loop is ran, and I have to manually insert input to continue to the tests.

Is there a way to not run the game loop when I run my tests, so I can test the class methods only?

Any other advice on the code in general would be helpful appreciated as well.

Game concept: Player is prompted to build, gather, recruit, or attack every turn and when someone's castle health is <= 0, game is over.

import os, random

class Player():
    def __init__(self):
        self.castle = 1
        self.villagers = 1
        self.warriors = 0
        self.food = 0
        self.stone = 0

    def takeTurn(self):
        action = 0
        action = int(input("1) Build\n2) Gather\n3) Recruit\n4) Attack\n"))
        if action == 1:
            self.build()
        elif action == 2:
            self.gather()
        elif action == 3:
            self.recruit()
        elif action == 4:
            self.attack()
        else:
            self.takeTurn()

    def build(self):
        if self.stone >= 1:
                self.castle += 1
                self.stone -= 1
        else:
            os.system('clear')
            if self.__class__.__name__ == "Player":
                print("You don't have enough stone!\n")
                printMenu()
            self.takeTurn()

    def gather(self):
        self.food += self.villagers
        self.stone += self.villagers

    def recruit(self):
        if self.food >= 1:
                self.warriors += 1
                self.food -= 1
        else:
            os.system('clear')
            if self.__class__.__name__ == "Player":
                print("You don't have enough food!\n")
                printMenu()
            self.takeTurn()

    def attack(self):
        if self.warriors >= 1:
            if self.__class__.__name__ == "Player":
                ai.castle -= self.warriors
            elif self.__class__.__name__ == "AI":
                player.castle -= self.warriors

class AI(Player):
    def __init__(self):
        super().__init__()

    def makeMove(self):
        action = 0
        # Win if player castle weak
        if player.castle == self.warriors:
            player.castle -= self.warriors
        # Build if castle weak
        elif self.castle == player.warriors:
            if self.stone >= 1:
                self.castle += 1
            else:
                action = random.randint(2, 4)
        else:
            action = random.randint(1, 4)

        if action == 1:
            super().build()
        if action == 2:
            super().gather()
        if action == 3:
            super().recruit()
        if action == 4:
            super().attack()

player = Player()
ai = AI()

def printMenu():
    print("You:\nCastle: " + str(player.castle) + " Food: " + str(player.food) + " Stone: " + str(player.stone) + " Villagers: " + str(player.villagers) + " Warriors: " + str(player.warriors) + "\n")
    print("Computer:\nCastle: " + str(ai.castle) + " Food: " + str(ai.food) + " Stone: " + str(ai.stone) + " Villagers: " + str(ai.villagers) + " Warriors: " + str(ai.warriors) + "\n")

def gameLoop():
    # MAIN LOOP
    playing = False
    if playing:
        printMenu()

        player.takeTurn()
        ai.makeMove()

        if ai.castle <= 0:
            playing = False
            print("You Win!\n")
        elif player.castle <= 0:
            playing = False
            print("You Lose!")
        else:
            os.system('clear')

gameLoop()

import unittest

from game.main import Player

class TestPlayer(unittest.TestCase):
    def setUp(self):
        self.player = Player()

    def test_build(self):
        # Should fail
        self.player.castle = 2
        self.player.stone = 1
        self.player.build()
        self.assertEqual(self.player.castle, 1)

if __name__ == '__main__':
    unittest.main()

You already have the answer to your "bug" given in the comments, but I will try to give you a more in-depth review. Nevertheless, I will repeat the aforementioned solution: to avoid the program auto-running on import, but your main call inside of a if __name__ == "__main__" (read more here if interested).

For your __init__ method, having your method initializers as (default) arguments tend to give more flexibility down the road as the project grows:

    def __init__(self, castle=1, villagers=1, warriors=0, food=0, stone=0):
        self.castle = castle
        self.villagers = villagers
        self.warriors = warriors
        self.food = food
        self.stone = stone

For your first real method, I would recommend staying with the Python standard of snake_case over camelCase. Furthermore, initialising the variable action to 0 doesn't really do you anything since you overwrite it in the following line. And since you rely on that input I think you should figure out what to do when you don't get an int, or if you get something like 11 (because 11 here would likely be a typo, given the options).

This, quite naturally, leads on to the purpose of testing (yay!). A nice thing about tests is that they allow you to think about what exactly you want to happen when you create an object or call on a function. For your takeTurns function, that would maybe be that you're only allowed to enter digits, and if you don't enter a single digit in the range 0–5 it throws an exception or it asks for another input. You would then basically implement your function (after the tests) to meet all the requirements you set forth in the beginning. You may then also find that maybe you were thinking about it the wrong way; in this case it could be that maybe take_turns (I renamed it for you...) shouldn't be asking for input() but rather be accepting an argument take_turns(user_choice).

To finalise, I'll add some smaller pieces of advice.

Instead of self.__class__.__name__ == "Player": you could (and should) use isinstance(self, Player).
Instead of action = random.randint(1, 4) coupled with 4 if-statements, there's a handy little function in random called choice (have a look here). You could also make your AI class much smaller by rethinking how the AI differs (or doesn't differ) from a Player.
f-strings are super nice. Instead of print("You:\nCastle: " + str(player.castle) + " Food: " + str(player.food) + " Stone: " + str(player.stone) + " Villagers: " + str(player.villagers) + " Warriors: " + str(player.warriors) + "\n"), you could have (and notice that I removed str() since you don't need it):

print(f"""You:
Castle: {player.castle}
Food: {player.food}
Stone: {player.stone}
Villagers: {player.villagers}
Warriors: {player.warriors}""")


Table Driven Test in Java using Junit4 I was creating some solving algorithm and write test for it. this is the tests :

    @Test
    public void test1(){
        boolean expected = true;
        int n = 7;
        DigitIncreasing digitIncreasing = new DigitIncreasing();
        assertEquals(expected,digitIncreasing.isDigitIncreasing(n));
    }

    @Test
    public void test2(){
        boolean expected = true;
        int n =36;
        DigitIncreasing digitIncreasing = new DigitIncreasing();
        assertEquals(expected,digitIncreasing.isDigitIncreasing(n));
    }

    @Test
    public void test3(){
        boolean expected = true;
        int n = 984;
        DigitIncreasing digitIncreasing = new DigitIncreasing();
        assertEquals(expected,digitIncreasing.isDigitIncreasing(n));
    }

    @Test
    public void test4(){
        boolean expected = true;
        int n = 7404;
        DigitIncreasing digitIncreasing = new DigitIncreasing();
        assertEquals(expected,digitIncreasing.isDigitIncreasing(n));
    }

    @Test
    public void test5(){
        boolean expected = false;
        int n = 37;
        DigitIncreasing digitIncreasing = new DigitIncreasing();
        assertEquals(expected,digitIncreasing.isDigitIncreasing(n));
    }

So from here I got some idea to write the test using Table driven approach like this :

     public class testObject {
        private int input;
        private boolean expected;

        public testObject(int input, boolean expected) {
            this.input = input;
            this.expected = expected;
        }

        public int getInput() {
            return input;
        }

        public boolean isExpected() {
            return expected;
        }
    }

    public void DigitIncreasing(int input, boolean expected){
        try{
            DigitIncreasing digitIncreasing = new DigitIncreasing();
            assertEquals(expected,digitIncreasing.isDigitIncreasing(input));
        }catch (AssertionError ex){
            System.out.println("input = "+input);
            System.out.println("expected = "+expected);
            ex.printStackTrace();
        }

    }

    @Test
    public void testTable(){
        testObject[] testObjects = new testObject[]{
                new testObject(7,true),
                new testObject(36,true),
                new testObject(984,true),
                new testObject(7404,true),
                new testObject(37,false),
       };

        for (testObject test : testObjects){
            DigitIncreasing(test.getInput(),test.isExpected());
        }
    }

Using Table Driven test makes me easily add another test case. any better approach or idea? since I'm adding the catch exception to get failed test.

You can find source code here.

JUnit 4 has a Parameterized test runner that does most of the work for you. For your tests, it would look like:

import maharishi.DigitIncreasing;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class DigitIncreasingTest {

    @Parameters(name = "Test {index}: isDigitIncreasing({0})={1}")
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][] {
              { 7, true }, { 36, true }, { 984, true }, { 7404, true }, { 37, false }
        });
    }

    private int input;

    private boolean expected;

    private DigitIncreasing digitIncreasing = new DigitIncreasing();

    public DigitIncreasingTest(int input, boolean expected) {
        input = input;
        expected = expected;
    }

    @Test
    public void test() {
        assertEquals(expected, digitIncreasing.isDigitIncreasing(input));
    }
}

This is easier to understand (in my opinion) than your formulation, where you shadow the name of the class under test, and actually runs each case as a separate test.


Generating Cartesian product of strings in R Sometimes I need to create character vectors like this one:

datanames <- c(
  "europe_co2_min",
  "europe_co2_max",
  "europe_temperature_min",
  "europe_temperature_max",
  "asia_co2_min",
  "asia_co2_max",
  "asia_temperature_min",
  "asia_temperature_max"
)

Notice that this is actually the Cartesian product of the character vectors joined together with a _:

c('europe', 'asia')
c('co2', 'temperature')
c('min', 'max')

I came up with this helper function:

combine <- function(..., prefix='', sep='_') {
  combine.inner <- function(lx, ...) {
    if (length(c(...)) > 0) {
      sapply(sapply(lx, function(x) paste(x, combine.inner(...), sep=sep)), c)
    } else {
      lx
    }
  }
  paste(prefix, combine.inner(...), sep='')
}

It handles arbitrary number of character vector parameters of arbitrary lengths. The prefix parameter is for convenience.  It's similar to having a single element vector as the first parameter, except the common separator sep will not be applied after it.

Is there an easier way that exists in R and I missed?
Is there anything smelly about this code?

Your approach is an example of good R code. However, there is a base function that allows creating a cartesian product of strings, interaction. This function creates a factor, and the levels are equivalent to the cartesian product.

Furthermore, instead of paste(..., sep = "") you can use paste0(...).

If you use these functions, your code will be much shorter:

combine <- function(..., prefix = "", sep = "_") {
  paste0(prefix, levels(interaction(..., sep = sep)))
}

Examples:

s1 <- c('europe', 'asia')
s2 <- c('co2', 'temperature')
s3 <- c('min', 'max')

combine(s1)
# [1] "europe" "asia"
combine(s1, s2)
# [1] "europe_co2"         "europe_temperature" "asia_co2"           "asia_temperature"
combine(s1, s2, s3)
# [1] "europe_co2_min"         "europe_co2_max"         "europe_temperature_min"
# [4] "europe_temperature_max" "asia_co2_min"           "asia_co2_max"
# [7] "asia_temperature_min"   "asia_temperature_max"


Ensure that a directory reflects a specified Git commit I have a method that looks like the method below, and I can't help but shake the feeling that it can be improved. It doesn't really "read" well, and it seems like checkout could be called only once, somehow.

def ensure_correctness
  if exist?
    unless correct_version?
      delete!
      checkout
    end
  else
    checkout
  end
end

def checkout
  run_command(['git', 'clone', '--depth', '1', url, path])
end

def exist?
  Dir.exist?(path)
end

def delete!
  FileUtils.rm_rf(path)
end

def correct_version?
  commit_sha_short == desired_commit_sha_short
end

The best I could come up with is moving the code from failing correct_version? to a new method (which probably isn't a terrible idea, but I wonder if I can do better).

I feel like I'm missing something really obvious here...

The two calls to checkout look well to me.  They are simple method calls to self with no arguments, and I can easily see that both calls are the same.  You avoid making two identical calls to run_command(['git', 'clone', ...]).

The "something really obvious" might be a return:

def ensure_correctness
  if exist?
    return if correct_version?
    delete!
  end
  checkout
end


Check string having unique character or not without additional data structure Here is my code without using additional data structures. Assuming all the characters are alphabetical and character checks are case-insensitive.

public static boolean isRepeated(String s) {
    if (s == null) {
        return true;
    }
    int length = s.length();
    for (int i = 0; i < length; i++) {
        if (!checkChar(i, s.toUpperCase())) {// making all character to upper case.
            return false;
        }
    }

    return true;

}

private static boolean checkChar(int i, String s) {
    char charAtI = s.charAt(i);
    //check all the character before that index;
    for (int k = 0; k < i; k++) {
        if (s.charAt(k) == charAtI)
            return false;
    }
    //check all the character after that index;
    for (int l = i + 1; l < s.length(); l++) {
        if (s.charAt(l) == charAtI)
            return false;
    }
    return true;
}

But it takes \$O(n^2)\$. Is there better way to do it, or some improvement?

To save complexity, I am using the other way, i.e. using an array.

public static boolean isRepeatedUsingArray(String s) {
        int[] charArray = new int[26];
        for(char c:s.toUpperCase().toCharArray()) {
            if(charArray[(int)c - 65] == 1) {
                return false;
            }
            charArray[(int)c - 65] = 1;
        }
        return true;

    }

Let me know your comments on this one as well.

1. Function name seems to be misleading. It returns true if no repeating character is found, so I find isNonRepeatedUsingArray to be more appropriate.

2. Basic input checks - when I began trying your function, I set up a few tests (included in the final code) and some of them crashed. Your code should handle at least basic input values such as null, empty string, string with spaces.

public static boolean isNonRepeatedUsingArray(String inputStr) {
    if(inputStr == null || inputStr.isEmpty())
        return false;

    String s = inputStr.replaceAll(" ", "").toUpperCase();

    // other character stripping may be put here

3. Checking for duplicates - The algorithm itself can be improved by thinking in terms of set. I am not very familiar with Java language and I have used HashMap data structure, but the bottom idea is the following:

if current element is already in the set, it is a duplicate. Else add it to the set.

This solution also has the advantage that avoids hardcoding the number of allowed characters (26).

    Map<Character, Boolean> charDict = new HashMap<Character, Boolean>();
    for (int i = 0; i < s.length(); i++) {
        Character c = s.charAt(i);
        if (charDict.containsKey(c))
            return false;

        charDict.put(c, true);
    }

HashMap operations have a complexity of O(1), so function's overall complexity is O(n), where n is string length.

[edit]
Based on Bobby's correct observation, a HashSet is a better choice (elements only, no key and values):

    HashSet<Character> charSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++) {
        Character c = s.charAt(i);
        if (charSet.contains(c))
            return false;

        charSet.add(c);
    }

4. Tests - it is a good habit to accompany a function with a test suite. It is particularly efficient when the code changes much (regressive testing) and helps to cover scenarios that are usually missed when developing (developers have a tendency to think in terms of making it work, not making it fail).

private static void printTestResult(String s) {
    boolean testRes = isNonRepeatedUsingArray(s);
    System.out.println("Repeating result for " + s + " is " + testRes);
}

public static void main(String []args){
    printTestResult("a");
    printTestResult("abcde");
    printTestResult("some random text");
    printTestResult("repeating");
    printTestResult(null);
}

The final code

import java.util.*;

public class HelloWorld{

    public static boolean isNonRepeatedUsingArray(String inputStr) {
        if(inputStr == null || inputStr.isEmpty())
            return false;

        String s = inputStr.replaceAll(" ", "").toUpperCase();

        Map<Character, Boolean> charDict = new HashMap<Character, Boolean>();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (charDict.containsKey(c))
                return false;

            charDict.put(c, true);
        }

        return true;
    }

    private static void printTestResult(String s) {
        boolean testRes = isNonRepeatedUsingArray(s);
        System.out.println("Repeating result for " + s + " is " + testRes);
    }

    public static void main(String []args){
        printTestResult("a");
        printTestResult("abcde");
        printTestResult("some random text");
        printTestResult("repeating");
        printTestResult(null);
    }
}


Simple application in Python using OpenCV for face I have been working on a simple Python application for face recognition with OpenCV. My code does its work and gets the job done, but I'm wondering if there's a 'better' way to do this. I hope I can get some tips on how to structure or approach this task.

See my full code 1 and 2.

while True:
    (_, im) = webcam.read()
    gray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)

    persons = face_cascade.detectMultiScale(gray, 1.3, 5)
    for (x,y,w,h) in persons:

        cv2.rectangle(im,(x,y),(x + w,y + h),(0, 255, 255),2)
        face = gray[y:y + h, x:x + w]
        rescaling_the_face = cv2.resize(face, (width, height))

        prophecy = model.predict(rescaling_the_face)
        cv2.rectangle(im, (x, y), (x + w, y + h), (0, 255, 255), 2)

        if prophecy[1]<400:
           cv2.putText(im,'%s' % (names[prophecy[0]]),(x + 10, (y + 22) + h), cv2.FONT_HERSHEY_PLAIN,1.5,(20,205,20), 2)

        else:
          cv2.putText(im,'STRANGE_PERSON',(x + 10, (y + 22) + h), cv2.FONT_HERSHEY_PLAIN,1.5,(65,65, 255), 2)

    cv2.imshow('OpenCV Face Recognition -  esc to close', im)
    key = cv2.waitKey(10)

if key == 27:

Some notes only:

Instead of

(_, im) = webcam.read()

is more common not to use parentheses:

_, im = webcam.read()

(and similarly in other places of your code).

Too many blank lines. In the PEP 8 - Style Guide for Python Code repeatedly occurs the word "sparingly" for the Blank Lines usage.

(Correcting English only):

Instead of

print("Webcam is open? ", webcam.isOpened())

use

print("Is the webcam open? ", webcam.isOpened())

Magic numbers in your code, as in this statement

if key == 27:

Why not use names for such constants, e. g.

ESC_KEY = 27               # Near the start of your code
...
...
if key == ESC_KEY:


Comparing a string using a stack Let L be the language defined as follows:

The words are made up of strings of a’s followed by b’s.
The number of a’s is always equal to the number of b’s.
Examples of words that belong to L are: ab, aabb, aaabbb etc...

One way to test if a word w belong to this language is to use a stack to check if the number of a’s balances the number of b’s.

This is what I though of doing:

Check if the length string is even
If it is send input to the function
Divide length by two and push the a's onto a stack
Reverse the string
Divide length by two and push the b's onto a stack
While the stack isn't empty pop each and store the count of each
Compare the count and if they are equal then return 0 or if not return 1

Please see below for the program I implemented:
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

int count1 = 0;
int count2 = 0;

bool isInLanguageL (string w);

int main()

{
    string input;

    cout << "Input any string; ";
    getline(cin,input);

    if (input.length() % 2 != 0)
        cout <<"Pattern entered does not match the language ";
    else
        isInLanguageL(input);

    return 0;
}

bool isInLanguageL (string w)
{
    stack<string> word1, word2;
    string a, b;

        for (unsigned i = 0; i < w.length()/2; i++)
    {
           a = w.at(i);
           word1.push(a);

    }

    reverse(w.begin(), w.end());

    for (unsigned i = 0; i < w.length()/2; i++)
    {
           b = w.at(i);
           word2.push(b);

    }

while(!word1.empty() && !word2.empty())
{

    word1.pop();
    count1 = count1++;
    word2.pop();
    count2 = count2++;

}

if(count1 == count2)
    return true;
else
    return false;

}

The issue I have with this is despite it working correctly I would appreciate and opinion on it as I feel they may have been another way to approach handling the strings although after racking my brains this was the best solution I could come up with.
What seems a bit silly to me is where I am comparing counts of the two stacks as it's pretty obvious based on the fact that I am not allowing odd numbers to pass into the function that the counts will always be equal which would also be due to the division by 2 in each iteration which clearly rules out the counts ever not being equal.
Also, it's all good and well that I am using the stacks to compare counts but I'm not really doing a check here on whether or not the string matches a pattern. In my mind I would have used the approach of checking a pattern but as the question just wants to see whether a's and b's balance I thought this approach wouldn't be bad.
Any advice on how else to approach this question would be appreciated.
Thanks

At least to me, this seems like an excessively complex design.

I'd guess the intent is to create something on the order of a pushdown automata. In other words, the code processes a stream of incoming characters one at a time, with no global view of all the incoming data, and (almost) no memory other than the stack.

The obvious way to do this would be to read a character of input. If it's an 'a', push it onto the stack, and repeat. If it's a 'b', pop one 'a' from the stack, and repeat:

stack<char> inputs;

char ch;

while ((ch = getinput()) == 'a')
    inputs.push(ch);

while (ch == 'b') {
    if (inputs.empty())
        error("Mismatch: more 'b's than 'a's");
    inputs.pop(ch);
    ch = getinput();
}

if (!inputs.empty())
    error("mismatch: more 'a's than 'b's");

Note that we're not really using any of the data we push onto the stack though--we're basically just using its depth (which can lead to an even simpler design, but on that doesn't appear to fit the specifications).


VBA Automatic insert in a Excel Spreadsheet Since I'm new at this site I will try to start with something very simple.

I'm making an "Automatic insert" in a Excel Spreadsheet and my code is working correctly, but I'm not so sure about my way of coding. Does the code follow good VBA programming practices?

Here is my code:

Option Explicit

Sub inserisciAutomatico()
Application.ScreenUpdating = False
Application.EnableEvents = False

Dim KitNr As String
Dim KitNrAppoggio As String
Dim kitNrSecondoAppoggio As String
Dim provaFormula As Range
Dim primoValore As String
Dim numeroID As String
Dim descrizione As String
Dim gruppo As String

Dim concatena As String
Dim disegno As String
Dim treD As String
Dim distinta As String
Dim immagine As String
Dim formulaCopy As String

Dim cell As Range
Dim risultato As Range
Dim risultatoAppoggio As Range

Dim valore As String
Dim appoggio As String

Dim provissima As Integer

valore = Worksheets("CODICI").ComboBox1.Value
appoggio = "fine"

Set cell = Worksheets("CODICI").Range("D4:D250").Find(valore)

'Debug.Print cell.Address

Set risultato = Worksheets("CODICI").Range("D4:D250").Find(appoggio, LookIn:=xlValues, After:=cell)
Set risultatoAppoggio = Worksheets("CODICI").Range("D4:D250").Find(Worksheets("CODICI").ComboBox1.Value, LookIn:=xlValues)

'Debug.Print risultato.Address
'Debug.Print risultatoAppoggio.Address

'kitNr = risultato.Offset(0, -2)
kitNrSecondoAppoggio = risultatoAppoggio.Offset(-1, -3)

Set provaFormula = Worksheets("CODICI").Range("Z1")

provaFormula.FormulaArray = "=MAX(IF(LEFT(B7:B250,1)=""" & kitNrSecondoAppoggio & """, B7:B250))"

KitNr = Worksheets("CODICI").Range("Z1").Value

Debug.Print provaFormula.FormulaArray

KitNrAppoggio = KitNr + 1

'Application.WorksheetFunction.Max (Range("a:a"))

Range(risultato.Address).EntireRow.Insert

primoValore = risultato.Offset(-1, -3).Address
numeroID = risultato.Offset(-1, -2).Address
descrizione = risultato.Offset(-1, 0).Address
gruppo = risultato.Offset(-1, 1).Address
concatena = risultato.Offset(-1, 2).Address
disegno = risultato.Offset(-1, 3).Address
treD = risultato.Offset(-1, 4).Address
distinta = risultato.Offset(-1, 5).Address
immagine = risultato.Offset(-1, 6).Address
formulaCopy = risultato.Offset(-2, 2).Address

Range(primoValore).Value = "T0"

Range(numeroID).Value = KitNrAppoggio
Range(numeroID).Borders(xlEdgeBottom).LineStyle = XlLineStyle.xlContinuous
'Range(numeroID).Borders(xlEdgeBottom).Weight = xlHairline
Range(numeroID).Font.Bold = False
Range(numeroID).Font.Name = "Calibri"
Range(numeroID).Font.Size = 10

Range(descrizione).Font.Bold = False
Range(descrizione).Font.Name = "Calibri"
Range(descrizione).Font.Size = 10
Range(descrizione).Value = Worksheets("CODICI").TextBox1.Value
Range(descrizione).Borders(xlEdgeBottom).LineStyle = XlLineStyle.xlContinuous
'Range(descrizione).Borders(xlEdgeBottom).Weight = xlHairline

Range(gruppo).NumberFormat = "@"
Range(gruppo).Value = Worksheets("CODICI").ComboBox2.Value
Range(formulaCopy).Select
Selection.Copy
Range(concatena).PasteSpecial xlPasteFormulas
'Range(concatena).Value = "T0" + KitNrAppoggio + Worksheets("CODICI").ComboBox2.Value

Range(disegno).Value = ".dwg"
Range(treD).Value = ".asm"
Range(distinta).Value = ".xls"
Range(immagine).Value = ".jpg"

The comments I have fall into three categories that relate to general programming practices that would be applicable to any language, not just VBA.

Raw Strings
Don't Repeat Yourself (DRY)
Single Responsibility Principle (SRP)

Raw Strings:
There are a lot of raw strings (examples: "CODICI", "Z12", "fine") in the code.  I'm guessing that the ease of Copy-Paste made it simple to paste Worksheet("CODICI") in the 10 places where a reference to sheet "CODICI" is needed.  However, should you ever change the name of this sheet someday (and chances are excellent that you will want to), by then there will be at least 10 places to get wrong - and the compiler/interpreter will not help you find them.  By adding a module level variable for the worksheet and assigning it once, you avoid this maintenance issue and reduce the volume of text in your subroutine.  There is a performance improvement here as well, but it will not be noticeable - performance is not the motivation for the change.  Raw strings like "CODICI" are generally to be avoided within your code for the above reasons.  Strings that never change for you subroutine are excellent candidates to be declared as module level constants.  And, when you want to change the name of the worksheet "CODICI", you only need to change your code in a single place (easy to get right!).

DRY:
DRY is important from both readability and maintenance of your code.  Eliminating repeated blocks of code by writing small, focused, methods to eliminate the repeated code is the typical example of DRY.  However, repeatedly writing raw strings or copy-pasting multiple line expressions falls under this principle as well.

SRP:
A simple search will provide you a better definition of SRP better than I can/will provide here.  As the name implies, SRP encourages that each  subroutine, function you write (in VBA or anything else) only does one thing.  A good criteria for SRP is this: a subroutine (or function) has a single responsibility if it has only one reason to change.  Your code has as single subroutine.  Consequently, it contains many reasons to change because it does everything.  Some of the reasons to change have been mentioned above within the DRY section.  Full disclosure: I regularly fail to achieve SRP my own code, but it is certainly a good principle to aspire to.

Sub inserisciAutomatico() is the macro entry point for the code - I would suggest that it's  responsibility is to declare constants, initialize the necessary module level variables and call a sequence of operations to accomplish the task.  The rewrite provided below does not accomplish this goal completely, but hopefully does so to a degree that is useful as an example.

By consolidating these tasks/responsibilities to smaller, single responsibility methods - you will make your code far easier to understand and maintain.  As you have already done, declaring Option Explicit at the top of your module is a good practice.  It forces the explicit declaration of all variables used.  A good indicator that Sub inserisciAutomatico() is doing 'too much' is the long list of variables it has declared.  Creating smaller focused subroutines and functions to accomplish the macro's goal will make many of these disappear.

The rewrite below removes many of raw strings by declaring them as constants.  It also reduces the number of local variable declarations needed by calling subroutines focused on the tasks associated with the original variable.  It also moves the remaining local variable declarations closer to their usage (generally a good practice).  I'll apologize in advance for my lack of any skills in Italian.  Some of the subroutines are named a bit strangely.  The names were chosen to identify the principle that motivated their creation.

Option Explicit

Private Const TheMainWorksheetName As String = "CODICI"
Private Const DefaultFont As String = "Calibri"
Private Const DefaultFontSize As Long = 10
Private Const Appoggio As String = "fine"
Private Const ProvaFormulaRange As String = "B7:B250"
Private Const ValoreRange As String = "D4:D250"
Private Const DWG As String = ".dwg"
Private Const ASM As String = ".asm"
Private Const XLS As String = ".xls"
Private Const JPG As String = ".jpg"
Private Const ProvaFormulasAddress As String = "Z1"
Private Const PrimoValoreT0 = "T0"

'DRY - use a variable (needs a better name) to avoid
'repeating the expression 'Worksheets("CODICI")'
Private theMainWorksheet As Worksheet

Sub inserisciAutomatico()

    Application.ScreenUpdating = False
    Application.EnableEvents = False

    Set theMainWorksheet = Worksheets(TheMainWorksheetName)

    Dim risultati As Range
    Set risultati = theMainWorksheet.Range(ValoreRange)

    'Dim valore As String
    'ComboBox1 needs a meaningful name to indicate what
    'value it is providing - for this example, it has been named 'valoreComboBox'
    'valore = theMainWorksheet .ComboBox1.value

    'Renaming ComboBox1 eliminates variable 'valore' and there is no longer
    'any uncertainty what is provided by the control
    Dim cell As Range
    Set cell = risultati.Find(theMainWorksheet .valoreComboBox.value)

    Dim risultato As Range
    Set risultato = risultati.Find(Appoggio, LookIn:=xlValues, After:=cell)

    Dim risultatoAppoggio As Range
    Set risultatoAppoggio = risultati.Find(theMainWorksheet .valoreComboBox.value, LookIn:=xlValues)

    Dim kitNrSecondoAppoggio As String
    kitNrSecondoAppoggio = risultatoAppoggio.Offset(-1, -3)

    Dim provaFormula As Range
    Set provaFormula = theMainWorksheet.Range(ProvaFormulasAddress)
    provaFormula.FormulaArray = "=MAX(IF(LEFT(" & ProvaFormulaRange & ",1)=""" & kitNrSecondoAppoggio & """, " & ProvaFormulaRange & "))"

    Range(risultato.Address).EntireRow.Insert

    SRP_SetupPrimoValore risultato.Offset(-1, -3).Address, PrimoValoreT0

    'KitNR was originally declared as a String, so the original KitNr + 1 operation below acted like integer addition
    'because VBA implicitly converts KitNr to a number.  Declare KitNr as an actual number type and eliminate any confusion
    Dim KitNr As Long
    KitNr = CLng(theMainWorksheet.Range(ProvaFormulasAddress).value)
    'The subrouting wants a string...so explicitly provide it...again to eliminate any confusion
    SRP_SetupNumeroID risultato.Offset(-1, -2).Address, CStr(KitNr + 1)

    'TextBox1 needs a meaningful name to indicate what it is providing
    SRP_SetupDescrizione risultato.Offset(-1, 0).Address, wksht.TextBox1.value

    'ComboBox2 needs a meaningful name to indicate what it is providing
     SRP_SetupGruppo risultato.Offset(-1, 1).Address, wksht.ComboBox2.value

    SRP_SetupTheFormula risultato.Offset(-1, 2).Address, risultato.Offset(-2, 2).Address

    Range(risultato.Offset(-1, 3).Address).value = DWG
    Range(risultato.Offset(-1, 4).Address).value = ASM
    Range(risultato.Offset(-1, 5).Address).value = XLS
    Range(risultato.Offset(-1, 6).Address).value = JPG

End Sub

Private Sub SRP_SetupPrimoValore(ByVal addr As String, ByVal value As String)
    Range(addr).value = value
End Sub

Private Sub SRP_SetupNumeroID(ByVal addr As String, ByVal kitNrAppoggio As String)
    Range(addr).value = kitNrAppoggio
    DRY_AvoidRepeatingTheFormattingOfNumeroIDAndDescrizione Range(addr)
End Sub

Private Sub SRP_SetupDescrizione(ByVal addr As String, ByVal value As String)
    Range(addr).value = value
    DRY_AvoidRepeatingTheFormattingOfNumeroIDAndDescrizione Range(addr)
End Sub

Private Sub SRP_SetupGruppo(ByVal addr As String, ByVal comboBox2Value As String)
    Range(addr).value = comboBox2Value
    Range(addr).NumberFormat = "@"
End Sub

Private Sub SRP_SetupTheFormula(ByVal addr As String, ByVal formulaAddress As String)
    Range(formulaAddress).Select
    Selection.Copy
    Range(addr).PasteSpecial xlPasteFormulas
End Sub

Private Sub DRY_AvoidRepeatingTheFormattingOfNumeroIDAndDescrizione(ByRef theCell As Range)
    theCell.Font.Bold = False
    theCell.Font.Name = DefaultFont
    theCell.Font.Size = DefaultFontSize
    theCell.Borders(xlEdgeBottom).LineStyle = XlLineStyle.xlContinuous
End Sub

The 'raw' numbers within the Offset(...) statements are still a maintence issue waiting to happen.  I would consider creating a small ClassModule or UserDefinedType (UDT) to host the rowOffset and columnOffset values.  After creating the Class or UDT, create module level variables with names for each Offset pair to identify what the offsets mean (for example, "risultatoToNumerIDOffset").  The result is that risultato.Offset(-1, -2) becomes something like risultato.Offset(risultatoToNumerIDOffset.Columns, risultatoToNumerIDOffset.Rows) and the offset values are no longer spread throughout the code.


Calculating an object's stopping distance I'm trying to smooth the movement of a cursor which has a set acceleration and max speed. I wrote this function to calculate the stopping distance of an object given its speed and acceleration, and it works, but it seems a little ridiculous.

function getStoppingDist(speed, accel) {
  var dist = 0;
    while (speed > 0) {
    dist += speed;
    speed -= accel;
  }
  return dist;
}

If the speed is 5 and acceleration is 1, its stopping distance is 5+4+3+2+1 = 15.

Surely there's a better way of doing this. What am I missing?

Considering this as a uniformly accelerated linear motion problem with given velocity and (negative) acceleration, you could use:

function getStoppingDist(speed, accel) {
  var dist = 0.5*Math.pow(speed,2)/accel;
  return dist;
}


Binary search feedback and improvements I implemented the binary search algorithm. Input vector is sorted by < than operator implemented by type T. The less than operator is expensive so we want to use it as few times as possible.

I would like to know if there are any stupid mistakes, bad practices that I used and how I can improve the code.

template<class T>
long binary_search(const std::vector<T>& v, const T& key){

    if(v.empty()) { return -1; }

    long lo = 0;
    long hi = v.size() - 1;
    long mid = (long) floor((lo + hi ) / 2);
    long pmid = -1;  // prev mid

    while(lo < hi && pmid != mid){

        if(v[mid] < key){
            lo = mid;
        }
        else{
            hi = mid;
        }

        pmid = mid;
        mid = (long) floor((lo + hi) / 2);
    }

    if(!(v[mid] < key) && !(key < v[mid])){
        return mid;
    }

    if(mid - 1 >= 0){
        if( !(v[mid - 1] < key) && !(key < v[mid - 1])){
            return mid - 1;
        }
    }

    if(mid + 1 <= v.size()){
        if(!( v[mid + 1] < key) && !(key < v[mid + 1] )){
            return mid + 1;
        }
    }

    return -1;
}

You don't need to floor the result of an integer division: the result is exactly the same without it.

When getting the mid value, this is safer:

mid = lo + (hi - lo) / 2;

This way you'll be safe from integer overflows, which can happen when adding two very large integers. (Or long, you get the point)

As you notice, there is some redundancy in the logic of seeing the mid before the main while loop and then again inside the loop, and also in the conditions within the loop and after it. Probably you can refactor this without redundancies, with most logic inside the loop, and almost nothing outside. There should be a return statement inside the loop when the element is found. The empty check will become unnecessary, as the loop condition will never be true for empty input.

template<class T>
long binary_search(const std::vector<T>& v, const T& key){
    long lo = 0;
    long hi = v.size();

    while (lo < hi) {
        long mid = lo + (hi - lo ) / 2;

        if (v[mid] == key) {
            return mid;
        }
        if (v[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}


The correct way to calculate MIPs of a function on a microcontroller I want to calculate MIPs of a function on a microcontroller. Here is how I do it.
1. keil setting. Use Simulator and Xtal = 25MHz

Run simulator in debug mode.

As you can see, it takes 200ms to run fun() once.
200ms(0.2s) * 25MHz = 5M. Does it mean that running fun() takes 5MIPs?
One thing to note that the MIPs of fun() is independent of platform or crystal's oscillation frequency.
Thank you.

As you may know, MIPS means Mega Instructions Per Second.
So the formula would be

CHIP_MIPS = number_of_mega_instructions / number_of_seconds.

If your chip is running at 25 MHz, it means that it performs 25 mega instructions per seconds, so knowing the number of seconds and the CHIP_MIPS, the formula would be

number_of_seconds * CHIP_MIPS = number_of_mega_instructions

So fun needs 5 Mega Intructions


My Hangman game in Python I've been trying to practice more Python recently so I decided to try and make different simple text-based game programs. I'd hope anybody could help me see how to make the code neater or more efficient in any aspect.

import random

words = []
guessed_letters = []
word_guess = []
joined_word = None

def fill_list():
    f = open('words.txt', 'r')
    for line in f:
        if len(line.strip()) > 3:
            words.append(line.strip())
    f.close()

def reset(secret):
    for letter in secret:
        word_guess.append('_')

def random_word(word_list):
    chosen = random.choice(word_list)
    return chosen

def guess_letter():
    while True:
        letter = input('Guess a letter a-z: ').lower().strip()
        if len(letter) != 1:
            print('Enter a single character only')
        elif not letter.isalpha():
            print('Enter only alphabetical characters')
        elif letter in guessed_letters:
            print('Already guessed {}'.format(letter))
        else:
            return letter

def print_opening():
    print('Welcome to Hangman!\n'
          'Try to guess a random word one letter at a time\n'
          'Good luck and have fun!\n')

def play_again():
    again = input().lower()
    if again.lower().startswith('y'):
        return True
    return False

def play():
    fill_list()
    tries = 5

    while True:
        print_opening()
        secret_word = random_word(words)
        reset(secret_word)

        while tries != 0 and '_' in word_guess:
            print('You have {} tries left'.format(tries))
            joined_word = ''.join(word_guess)
            print(joined_word)

            player_guess = guess_letter()
            for index, letter in enumerate(secret_word):
                if player_guess == letter:
                    word_guess[index] = player_guess

            guessed_letters.append(player_guess)

            if player_guess not in secret_word:
                print('Wrong!')
                tries -= 1

        if '_' not in word_guess:
            print('You win!\n{} was the word!\n'.format(secret_word))
        else:
            print('You lose!\nThe word was {}'.format(secret_word))

        print('Would you like to play another game? y/n')

        if play_again():
            word_guess.clear()
            tries = 5
        else:
            print('Thanks for playing!')
            break

if __name__ == '__main__':
    play()

One thing I would do is wrap this up in a hangman class. That way you could just toss away the hangman instance for a new one if the user ever decided to play again rather than resting all global variables. It would also decouple the handling of user input from the actual game. If the game size would grow this would make catching bugs a lot easier.

But lets focus on some smaller things that are easier to change

chosen = random.choice(word_list)
return chosen

Here your variable has no purpose, I would do

return random.choice(word_list)

Similar kind of story here

if again.lower().startswith('y'):
        return True
    return False

to

return again.lower().startswith('y')

Next is avoid magic constants at all costs, for example

if len(line.strip()) > 3:

What is 3? Why is 3 important here? You should replace this with a global ALL_CAPS variable to represent what 3 is.


Classifying the aspect ratio of the screen dimensions In my project, I have three different userforms to display, optimized for three different aspect ratios. I need my code to call the screen resolution of the user's monitor, then check to see which category it belongs to, and finally choose the appropriate userform.

I've gotten as far as categorizing, but I'm self-taught and have been using absolutely horrendous code. I've just taken every aspect ratio available on our machines and put it into an if  then statement; when the correct if statement is triggered, it populates the variable Asp.

I'm absolutely certain there's a better way to do this. I would like to;

find a mathematical way to represent a "range" of ratios, as not every resolution in the 16:9 category, for example, is exactly 16/9, and
clean up the validation system that picks the right category for the user's setup. Possibly an array or a Case statement?

Declare Function getsystemmetrics32 Lib "User32" _
    Alias "GetSystemMetrics" (ByVal nIndex As Long) As Long

Sub callAspectRatio()

Dim w As Long
Dim h As Long
Dim Asp As String

w = getsystemmetrics32(0)
h = getsystemmetrics32(1)

If w = 1920 And h = 1080 Then Asp = "16:9"
If w = 1680 And h = 1050 Then Asp = "16:9"
If w = 1600 And h = 900 Then Asp = "16:9"
If w = 1366 And h = 768 Then Asp = "16:9"
If w = 1360 And h = 768 Then Asp = "16:9"
If w = 1280 And h = 720 Then Asp = "16:9"
If w = 1280 And h = 600 Then Asp = "16:9"

If w = 1440 And h = 900 Then Asp = "8:5"
If w = 1280 And h = 1024 Then Asp = "8:5"
If w = 1280 And h = 960 Then Asp = "8:5"

If w = 1600 And h = 1200 Then Asp = "4:3"
If w = 1400 And h = 1050 Then Asp = "4:3"
If w = 1280 And h = 1024 Then Asp = "4:3"
If w = 1280 And h = 960 Then Asp = "4:3"
If w = 1152 And h = 864 Then Asp = "4:3"
If w = 1024 And h = 768 Then Asp = "4:3"
If w = 800 And h = 600 Then Asp = "4:3"

MsgBox Asp

End Sub

The firs thing worth pointing out is that you are ignoring a lot of special meaning with your current approach. Aspect ratios are a function determined by Width : Height and thus we can use an aspect ratio and an inputted Width and Height to get the aspect we want, instead of looking through a list that are just saying the same thing in different ways.

I took your original code and calculated each aspect ratio in order. Here are the results:

'    1.77777777777778 16:9
'    1.6 16:9
'    1.77777777777778 16:9
'    1.77864583333333 16:9
'    1.77083333333333 16:9
'    1.77777777777778 16:9
'    2.13333333333333 16:9
'    1.6 8:5
'    1.25 8:5
'    1.33333333333333 8:5
'    1.33333333333333 4:3
'    1.33333333333333 4:3
'    1.25 4:3
'    1.33333333333333 4:3
'    1.33333333333333 4:3
'    1.33333333333333 4:3
'    1.33333333333333 4:3

A reduced list would look like this:

'1.77... ' 16:9
'1.6     ' 16:9
'1.778   ' 16:9
'2.133   ' 16:9
'1.6     ' 8:5
'1.25    ' 8:5
'1.33... ' 8:5
'1.33... ' 4:3
'1.25    ' 4:3

Aside from the couple of instances of a single ratio being matched to two different aspects, they are fairly consistent. So then I checked each of the original aspects and their results:

?16/9
 1.77777777777778
?8/5
 1.6
?4/3
 1.33333333333333

In turn, we have a very simple function to get an aspect ratio from a width and height:

Public Function GetAspectRatio(ByVal Width As Long, ByVal Height As Long) As String
    Select Case Round(Width/ Height, 3)
    Case Is <= 1.33
        GetAspectRatio = "4:3"
    Case Is <= 1.6
        GetAspectRatio = "8:5"
    Case Is > 1.6
        GetAspectRatio = "16:9"
    Case Else
        ' Error : Ratio not pre-defined.
    End Select
End Function

Then your original code becomes this:

Declare Function GetSystemMetrics32 Lib "User32" _
    Alias "GetSystemMetrics" (ByVal nIndex As Long) As Long

Sub DisplayAspectRatio()
    Dim Width As Long
    Width = GetSystemMetrics32(0)

    Dim Height As Long
    Height = GetSystemMetrics32(1)

    MsgBox "Your aspect ratio is : " & GetAspectRatio(Width, Height)
End Sub

We could improve this a bit further by employing the use of constant values and such, but overall this will point you in the right direction.

Note that, with the improved code, I made sure to use clear variable names. Most users will understand what h means in context, but Height is clear to any user. Even better would be WindowHeight so that, even if your reader was completely dumb to reading code, they would know what that variable was. Same goes for naming Functions, and Subroutines.

Best of luck!


Right-justifying a number with dot leaders I'm working on a small library to help me format numbers easier as my current project deals with a lot of them.  I want to be able to just supply the value, precision, width, and fillchar to a method and have it do all the work for me.

Based on the standard way of doing things with rjust()…

print '{:.2f}'.format(123.456).rjust(10, '.')
# ....123.46

… I could write:

def float_rjust(value, width, precision=2, fillchar=' ', separator='', sign=''):
    #[sign][#][0][width][,][.precision][type]
    spec = '{{:{1}{2}{3}.{4}f}}'.format(
        sign,
        width,
        separator,
        precision
    )
    return spec.format(value).rjust(width, fillchar)

However, I have found that the format() method actually allows for justifications in it:

print '{:.>10.2f}'.format(123.456)
# ....123.46

… so I could also write it this way:

def float_rjust(value, width, precision=2, fillchar=' ', separator='', sign=''):
    #[[fill]align][sign][#][0][width][,][.precision][type]
    spec = '{{:{0}>{1}{2}{3}.{4}f}}'.format(
        fillchar,
        sign,
        width,
        separator,
        precision
    )
    return spec.format(value)

My main question is, should I used the [[fill]align] formatting spec in format() to do justification, or is it more Pythonic to use format().rjust()?

In terms of efficiency, the second form is probably slightly better, as it creates fewer string objects:

def float_rjust(value, width, precision=2, fillchar=' ', separator='', sign=''):
    #[sign][#][0][width][,][.precision][type]
    spec = '{{:{1}{2}{3}.{4}f}}'.format(  # 1
        sign,
        width,
        separator,
        precision
    )  # 2
    value = spec.format(value)  # 3 - slight refactor for clarity
    return value.rjust(width, fillchar)  # 4

vs.

def float_rjust(value, width, precision=2, fillchar=' ', separator='', sign=''):
    #[[fill]align][sign][#][0][width][,][.precision][type]
    spec = '{{:{0}>{1}{2}{3}.{4}f}}'.format(  # 1
        fillchar,
        sign,
        width,
        separator,
        precision
    )  # 2
    return spec.format(value)  # 3

In general terms, I would use e.g. rjust only where that was the only formatting I required; it seems awkward to split the formatting into two steps.

However, I would probably rearrange this completely. You have combined two steps that I think should probably be separate: creating a specification, and applying it to an object.

Using format(value, spec) rather than spec.format(value) (i.e. the format function vs. the str.format method) lets you simplify the spec (getting rid of the extra braces):

def float_spec(width, precision=2, fillchar=' ', separator='', sign=''):
    """Create a specification for formatting floats."""
    return '{}>{}{}{}.{}f'.format(fillchar, sign, width, separator, precision)

You can now inline the format call:

>>> print format(123.456, float_spec(width=10, fillchar='.'))
....123.46

For greater efficiency, as float_spec would return equal (but not identical) strings for the same inputs, you could add memoization/caching. You could also add validation (of either the parameters or created specs) to ensure that it outputs a valid specification for format.


Performance of the String searching algorithm I am trying to solve a string matching question mentioned here. I recently learned the Knuth–Morris–Pratt algorithm and tried to implement it to solve this question. But I am getting a TLE for this code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Gogl {
    static int count=0;
    public static void main(String[] args)
    {
        MyScannergogl sc=new MyScannergogl();//used own input function
        String text=sc.next();
        String pattern=sc.next();
        KMP(text,pattern);

            System.out.println(count);

    }
    static int[] computeTempArray(String pattern)
    {
        int lsp[]=new int[pattern.length()];
        int index=0;
        int i;
        for(i=1;i<pattern.length();)
        {
            if(pattern.charAt(i)==pattern.charAt(index))
            {
                lsp[i]=lsp[index]+1;
                i++;
                index++;
            }
            else
            {
                if(index!=0)
                {
                    index=lsp[i-1];
                }
                else
                {
                    lsp[i]=0;
                    i++;
                }
            }
        }
        return lsp;
    }
    public static void KMP(String text,String pat)
    {
        int lsp[]=computeTempArray(pat);
        int i=0;
        int j=0;
        while(i<text.length() )
        {

            if(text.charAt(i)==pat.charAt(j))
            {
                i++;
                j++;
            }
            else
            {
                if(j!=0)
                {
                    j=lsp[j-1];
                }
                else
                {
                    i++;
                }
            }
            if(j==pat.length())
            {
                count++;
                j=0;
            }
        }

    }

}

I couldn't understand where am I wrong. Whether I have not properly implemented the algorithm or is there some other problem I am not aware of. As I know that KNP is really fast so should have crossed the time limit.

int i;
    for(i=1;i<pattern.length();)
    {
        if(pattern.charAt(i)==pattern.charAt(index))
        {
            lsp[i]=lsp[index]+1;
            i++;
            index++;
        }
        else
        {
            if(index!=0)
            {
                index=lsp[i-1];
            }
            else
            {
                lsp[i]=0;
                i++;
            }
        }
    }

That's a while loop. There's no need to use for here.

    int i = 1;
    while(i<pattern.length())
    {
        if(pattern.charAt(i)==pattern.charAt(index))
        {
            lsp[i]=lsp[index]+1;
            i++;
            index++;
        }
        else
        {
            if(index!=0)
            {
                index=lsp[i-1];
            }
            else
            {
                lsp[i]=0;
                i++;
            }
        }
    }

You might want to use more descriptive variables in your code, because I have the hardest time trying to understand what lsp is. The i and j variables aren't helping either: are you traversing two collections? In what way?

Your class names are weird, what does Gogl mean?

More descriptive variables and classnames will help you when you view your code at a later point in time. If you don't feel like explaining the algorithm in code, at least put the name of the algorithm together with a link as a comment in the code.