Load other files (from outside public_html) under index.php I wanted to load every page under index.php with a simple index.php?do=login

For example when the link index.php?do=login or /login/ is opened, the file login.php is loaded (from outside public_html), and so everything is done under index.php instead of having a separate php file in public_html for each action!

This is what I've tried already, am I doing it okay? (I'm not sure if what I'm doing has any security vulnerabilities, so please kindly advise)

index.php

<?php

// application path (outside public_html)
define('FILESPATH', APP.'../application/actions/');

// Default file
$file_name = 'home_page';

// e.g. index.php?do=login or /login/
if(isset($_GET['do'])){
    $file_name = rtrim($_GET['do'],'/');
}

// Set file path
$fpath = FILESPATH."{$file_name}.php";

// Make sure user input has valid characters a-z 0-9 _
if(preg_match('/^[A-Za-z0-9_]+$/', $file_name) !== 1 OR ! file_exists($fpath)){
    // Error
    require_once('404.php');
    die();
}

// Load the do=file
require_once($fpath);

// Nothing more comes in index.php

login.php

<?php

// Load template file header
require_once('header_template.php');

//
// Stuff that happens in login.php
// Checking if $_POST['username'] has valid chars then searching for it with pdo in db,
// password_verify() for $_POST['password'], etc...
//

// Load login's html template
// (which includes the html form submitted to /login/)
require_once('login_template.php');

// Load template footer
require_once('footer_template.php');

.htaccess

To run with site.com/login/ etc instead of site.com?do=login

<IfModule mod_rewrite.c>
    RewriteEngine On
    RewriteCond   %{REQUEST_FILENAME} !-d
    RewriteCond   %{REQUEST_FILENAME} !-f
    RewriteRule   ^((?s).*)$ index.php?do=$1 [QSA,L]
</IfModule>

You can simplify your regex pattern and you might like to combine your validation with the preparation step.  The following pattern is just like yours except it allows a single trailing slash and omits it from the capture group.

if (isset($_GET['do']) && preg_match('~^(\w+)/?$~', $_GET['do'], $valid)) {
    $file_name = $valid[1];
} else {
    $file_name = "home_page";
}

$fpath = FILESPATH . "{$file_name}.php";

if (!file_exists($fpath)) {
    // Error
    require_once('404.php');
    die();
}

It doesn't make sense to valid home_page with your pattern, you know it will pass every time. I suppose it could be possible that your home_page file may not exist in the directory.


Splitting payments in a number of installments I was reviewing today some code which gets as input a list of payments (paymentList) and a list of installments (installmentList) has to populate two other lists, respectively depositList and balanceList.

Basically it calculates the sum of all payments from paymentList and fills depositList with the amount enough to let each specific installment be payed.

If the sum of all payments is less then the total of installments it fills as many installments as it can and then sets the balanceList with the amount which is missing.

To make this clearer this is the output:

paymentList    : 1200, 1000, 400,
installmentList: 1200, 1200, 1200, 900,
depositList    : 1200, 1200, 200, 0,
balanceList    : 0, 0, -1000, -1900,

if I made a total of 3 payments for 2600$, and I had to pay 4 installments, I would be able to pay the first two completely (with balance 0) and the third only with 200$ still having to pay 1000$, and the last installment would be completely missed for a total debt of 1900$.

Seems easy enough however the code which does it stinks to me, here is a simplified version:

public class Payment
{

    public static void main(String[] args)
    {
        ArrayList<Integer> paymentList = new ArrayList<Integer>()
        {
            {
                add(1200);
                add(1000);
                add(400);
            }
        };

        ArrayList<Integer> installmentList = new ArrayList<Integer>()
        {
            {
                add(1200);
                add(1200);
                add(1200);
                add(900);
            }
        };

        printArray("paymentList    ", paymentList);
        printArray("installmentList", installmentList);

        ArrayList<Integer> depositList = new ArrayList();
        ArrayList<Integer> balanceList = new ArrayList();

        Integer settledTotalAmount = 0;
        for (Integer i : paymentList)
        {
            settledTotalAmount += i;
        }

        for (Integer currentInstallmentAmount : installmentList)
        {
            Integer settledAmount = 0;
            if (settledTotalAmount > 0)
            {
                int tmpAmount = settledTotalAmount - currentInstallmentAmount;
                if (tmpAmount > 0)
                {
                    settledAmount = currentInstallmentAmount;
                    settledTotalAmount = tmpAmount;
                    balanceList.add(0);
                }
                else
                {
                    settledAmount = currentInstallmentAmount+(tmpAmount);
                    settledTotalAmount = (currentInstallmentAmount-settledAmount)*-1;
                    balanceList.add((currentInstallmentAmount-settledAmount)*-1);
                }
            }
            else
            {
                settledAmount = 0;
                int k = (settledTotalAmount * -1)+currentInstallmentAmount;
                settledTotalAmount = k*-1;
                balanceList.add(settledTotalAmount);
            }
            depositList.add(settledAmount);
        }

        printArray("depositList    ", depositList);
        printArray("balanceList    ", balanceList);

    }

    public static void printArray(String name, ArrayList<Integer> array)
    {
        System.out.print(name + ": ");
        for (Integer i : array)
        {
            System.out.print(i + ", ");
        }
        System.out.println();
    }
}

in particular the series of if else switches seems redundant to me, is there something cleaner for the above (which seems to work for now)?
The version above actually is a simplified version, the original one I have uses BigDecimal and is even messier than that.

I tried to simplify the loop:

    int availableAsset = paymentList.stream().mapToInt(Integer::intValue).sum();

    for (Integer currentInstallmentAmount : installmentList) {
        if (availableAsset > currentInstallmentAmount) {
            balanceList.add(0);
            depositList.add(currentInstallmentAmount);
            availableAsset -= currentInstallmentAmount;
        } else {
            if (availableAsset > 0) {
                depositList.add(currentInstallmentAmount - availableAsset);
                balanceList.add(availableAsset - currentInstallmentAmount);
                availableAsset = 0;
            } else {
                balanceList.add(-currentInstallmentAmount);
                depositList.add(0);
            }
        }
    }

Since we have just this or that decisions (instead of a selection) it's not really a benefit to use polymorphism here.


Finding the longest common suffix recursively I'm getting the correct results, but my method isn't the prettiest. Is there any way to do this with less code?

var longestSuffix = function(A, B) {
    return rec(A, B, 0);

    function rec(A, B, count) {
        if (!A.length || !B.length) return '';
        if (A[A.length - count - 1] === B[B.length - count - 1]) {
            console.log(A[A.length-count-1]);
            return rec(A, B, ++count) + A[A.length - count - 2];
        }
        return rec('','');
    }
};

console.log(longestSuffix('cababa', 'cabjklaba'));

Recursive Solution Improvement
First, here's a rewrite of the answer you submitted yourself, which fixes a small bug and removes the inner function, which isn't needed.  Instead, we make the final two parameters optional:
function longestSuffix(X,Y,m,n) {
    var m = m === undefined ? X.length : m,
        n = n === undefined ? Y.length : n,
        keepGoing = X[m-1] && Y[n-1] && X[m-1] === Y[n-1];

    return keepGoing ? longestSuffix(X, Y, m-1, n-1) + X[m-1] : '';
};

Here's a different approach, slightly longer because I spelled everything out with variable names, but perhaps simpler in concept:
function longestSuffix (A, B, answer) {
    var answer = answer || '',
        aLast = A.slice(-1),
        bLast = B.slice(-1),
        A = A.slice(0,-1),
        B = B.slice(0,-1),
        done = !aLast || !bLast || aLast != bLast;

    return done ? answer : longestSuffix(A, B, aLast + answer);
};

You can make it shorter by, eg, removing aMinusLast and bMinusLast and replacing them inline with their definitions, but I like this expanded version because everything is clearly named, and the entire logic of the function can be seen at a glance in a single line.
Loop solution
A loop may be more appropriate here.  Here's a very brief implementation which takes advantage of slice, which exists on strings as well as arrays.
The only ugly part of this is that we have to treat the case when both A fully matches B as a special case in the return statement.  Otherwise note that the final slice(1) just adjusts back for the final decrement.
function longestSuffix (A, B) {
    var i = -1;
    while (A.slice(i) == B.slice(i) && i >= -A.length) i--;
    return i < -A.length ? A : A.slice(i).slice(1)
};

This could be expanded for further clarity, but I figured I'd leave this one in compressed form, because it's so short.


Is the way I use my pattern good enough? For quite a long, I have been using a pattern to make my life a bit easier. please help me evaluate how good or bad my approach is and how can I improve it.

I have a static class for just returning values:

    class ReturnValue {

            const STATUS_SUCCESS = "SUCCESS";
            const STATUS_FAIL = "FAILED";

            public static function doReturn($funtionName, $status = NULL, $value = NULL, $message = NULL) {
                if ($status == NULL) {
                    $status = self::STATUS_FAIL;
                }
                $return = array(
                action => $funtionName,
                status => $status,
                message => $message,
                returnValue => $value
            );
            return (object) $return;
        }

    }

usage example:

        function add($val, $val2) {
            if (empty($val)) {
                return ReturnValue::doReturn(__FUNCTION__, ReturnValue::STATUS_FAIL, '', 'Val must be a number');
            }
            if (empty($val2)) {
                return ReturnValue::doReturn(__FUNCTION__, ReturnValue::STATUS_FAIL, '', 'Val2 must be a number');
            }
            $sum = $val + $val2;
            return ReturnValue::doReturn(__FUNCTION__, ReturnValue::STATUS_SUCCESS, $sum, "$val + $val2 = $sum");
    }

To get the returned value:

    $add = add(1, 2);
    print $add->returnValue; // Gives 1 + 2 = 3
    print $add->message; // Gives  "Val2 must be a number"
    print $add->status; // FAILED

    //OR to make an error
    $add = add(1, ''); // an empty param is passed
    print $add->returnValue;//Gives  3
    print $add->message; // Gives   "1 + 2 = 3"
    print $add->status; // SUCCESS

I would prefer:

function add($left, $right) {
   if (!(isset($left, $right) && is_numeric($left) && is_numeric($right)))
   {
      throw new InvalidArgumentException(
          __METHOD__ . ' Left and Right arguments must be numeric.');
   }

   return $left + $right;
}

The exception can then be caught at a level where you know how to deal with it.

Usage:

try
{
   print add(1, 2) . "\n";
   print add(1, '') . "\n";
}
catch (Exception $e)
{
   echo $e->getMessage();
}

The calls to add are not mixed in with custom error handling, making it easier for other people to understand your code.  It also removes the dependency on your ReturnValue class which makes your code more reusable.  The exception allows you to let the code get back to an appropriate level where you can deal with your problem, rather than passing this information back up stack levels.


Combining CSVs using ruby to match headers I am trying to write a ruby script that will take all of the CSVs in a given directory and map their headers out so that duplicate columns will match up and columns unique to a file will have their own column in the final data file. The following code produces the output I desire, however something about it seems overly complicated and clumsy. Are there better practices or patterns I should follow to accomplish this? For example it seems to me like the master_hash variable should lose scope when I transfer it to the key_arr, but when I try to make the code reflect that I end up overwriting it each time I open a new file. Am I trying to hard to avoid "slurping" the files? Can this be done using less memory/faster? Forgive me if this question is too general in nature and if I can improve it to be more useful please let me know.

require 'CSV'
key_arr = [] # create Key array to store the headers
master_hash = {} # create master hash to consolidate headers
# get each csv in file
Dir.glob('datasample*.csv').each do |file|
  # open each csv
  File.open(file) do |csv|
    # Create a temporary hash of the headers
    temp_hash = Hash[csv.readline.split(',').map.with_index.to_a]
    # merge temporary hash to master hash
    master_hash = master_hash.merge(temp_hash)
  end
  key_arr = master_hash.keys # Put keys from hash into array
end

CSV.open('dest.csv', 'w') do |dest_csv| # open destination file
  dest_csv << key_arr # write header row
end

Dir.glob('datasample*.csv').each do |file| # get all the csv's to be merged
  # Open destination file in append mode
  CSV.open('dest.csv', 'a', headers: true) do |dest_csv|
    # open each source file for reading
    CSV.open(file, headers: true) do |source_csv|
      source_csv.each do |row| # iterate over each row of the source file
        row_arr = Array.new(key_arr.length) # create array to hold Row
        row.each do |cell| # get each header/field combination
          # iterate over the key arr
          # (key arr is the total number of fields on the final csv)
          key_arr.length.times do |master_key_index|
            # check if the header for the selected cell matches the header
            # at the index on the key array to determine position in row array
            if cell[0] == key_arr[master_key_index]
              # set row array element to cell value if a match
              row_arr[master_key_index] = cell [1]
            end
          end
        end
        dest_csv << row_arr # Write row to dest_csv
      end
    end
  end
end

While the scale of this individual script is relatively small and performance isn't a huge concern per se, I would rather get into the habit of using the "right" tools for the job than just guessing. Also, sorry about any formatting issues here. I can put this on gist if need be.

Your overall approach seems fine (i.e. get all headers, then combine the files). However, it can be made much simpler.

Before getting into that, though, I'm slightly concerned about how you "manually" parse the headers of each file. The CSV format can have some nasty syntax, so simply splitting on commas may give you the wrong results (for instance, if the header text itself contains a comma). So I'd use the CSV methods for reliable, robust parsing of the header lines.

As for the actual "meat" of the script, it seems to me that you're working way, way too hard, using arrays, hashes, indices, and all sorts of other stuff. No need for that. In fact, you rarely ever need to muck around with low-level array/index stuff in Ruby.

And the neat thing about Ruby's CSV library is that you can reference cells by the header they belong to. So you don't need numeric indices. Instead, if you can do something like:

CSV.foreach(some_file, headers: true) do |row|
  puts row["Column A"] # grab the value from a named column in the row
end

CSV.foreach avoids reading everything all at once. Instead it reads the rows, one by one, passing them to the block. And since it's passing them as CSV::Row objects, so you can access the row cells by header name.

So here's my take:

require 'csv'

# Get input files
input_files = Dir.glob("datasample*.csv")

# Collect/combine headers
all_headers = input_files.reduce([]) do |all_headers, file|
  header_line = File.open(file, &:gets)     # grab first line
  all_headers | CSV.parse_line(header_line) # parse headers and merge with known ones
end

# Write combined file
CSV.open("out.csv", "w") do |out|
  # Write all headers
  out << all_headers

  # Write rows from each file
  input_files.each do |file|
    CSV.foreach(file, headers: true) do |row|
      out << all_headers.map { |header| row[header] }
    end
  end
end

The output file will contain all the headers, and all the data in the correct order, interspersed with blank cells where necessary. The memory usage should be really, really low, because no file is read in its entirety. We just read a single line from each to get all the headers, and afterward, we go row by row, outputting them as we read them.


Binary search attempt I've heard about the binary search in an intro class I took a couple months ago, remembered how it worked and read this article, so I attempted to write my first binary search in Python. It works, but when I look at other people's attempts in the article, their code looks cleaner and a bit different.

My two main questions are:

What can I do to optimize my code from here?
Am I even performing a true binary search?

def binsearch(mylist, keyval):
large = len(mylist)-1
small = 0
temp = (len(mylist)-1)/2
key = 'undefined'
flag = 0
while flag == 0:
    if mylist[small] == keyval:
        key = small
        flag = 1
    elif mylist[large] == keyval:
        key = large
        flag = 1
    elif mylist[temp] == keyval:
        key = temp
        flag = 1
    elif temp + 1 == large or temp -1 == small:
        flag = 1
    if keyval > mylist[temp]:
        small = temp
        temp = small + (large - small)/2
    elif keyval < mylist[temp]:
        large = temp
        temp = temp - (large-small)/2
return key

I'm afraid this code has a few bugs.

binsearch([], 1) throws an IndexError.

binsearch([2], 1) goes into an infinite loop.


Common function to check if an element exists I think there is more that is needed here. Can someone please comment on it?

What I need is to add some common functions to check if an element exists.

// Common functions
$(document).ready(function() {

    /*
    Function for creating different styling checkbox, radio input, and select
    */

    // Create pretty checkboxes and inputs

    if ($('.iCheck').length){
        $('.iCheck').iCheck({
        checkboxClass: 'icheckbox_minimal-blue',
        radioClass: 'iradio_minimal-blue',
        increaseArea: '20%' // optional
    });
    }

    // Create pretty selects and multiselect
        if(!$("html").hasClass("ie8")){
            if ($('select').length){
                $('select').attr('data-width', '100%').selectpicker();
            }

        };

     /*
      Preloader
     */
    var targetPreloader = $('[data-overlay-text]');
    targetPreloader.click(function() {
        var text = $(this).attr("data-overlay-text");
        $('.preloader-text').text(text);
        $('.preloader-window').show().fadeIn();
    });

    /*
      Fix for showing SVG
     */
    svgeezy.init('nothing', 'png');

        /*
    Form validation using Jquery validate
    */
        $('form').validate({
        highlight: function(element) {
            $(element).closest('.form-group').addClass('has-error');
        },
        unhighlight: function(element) {
            $(element).closest('.form-group').removeClass('has-error');
        },
        errorElement: 'span',
        errorClass: 'help-block',
        errorPlacement: function(error, element) {
            if(element.parent('.input-group').length) {
                error.insertAfter(element.parent());
            } else {
                error.insertAfter(element);
            }
        }
    });

});

You shouldn't even need to do a check for element exists before calling a jQuery method. All internal methods, and any plugin that follows good practices, just won't do anything at all if there are no elements in the set. So you could just simplify that part of the code down to (without the if):

$('.iCheck').iCheck({
    checkboxClass: 'icheckbox_minimal-blue',
    radioClass: 'iradio_minimal-blue',
    increaseArea: '20%' // optional
});


Decimal expansion of a rational number I wrote a program that does division and either does or doesn't show repeating groups. After designing it the first time I had to redesign it because although it worked it was unnecessarily complex. And now I am presenting to you my refined division program, for feedback and improvement ideas:

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Division
{
    public static void main(String[] args)
    {
        Pattern p = Pattern.compile("(\\d+)(/)(\\d+)");
        Scanner in = new Scanner(System.in);

        System.out.print("Enter a fraction in the form x/y: ");
        String input = in.nextLine();
        Matcher m = p.matcher(input);

        while(!m.matches())
        {
            System.out.print("Enter a fraction in the form x/y: ");
            input = in.nextLine();
            m = p.matcher(input);
        }
        in.close();

        int top = Integer.parseInt(m.group(1));
        int bottom = Integer.parseInt(m.group(3));
        System.out.println("Result: " + divide(top,bottom,true));
    }

    public static String divide(int numerator, int denominator, boolean showRepeatingGroup)
    {
        int whole = (int)numerator / denominator;
        numerator = (numerator - (whole * denominator)) * 10;
        StringBuilder result = new StringBuilder(whole + ".");
        Set<Integer> remainders = new LinkedHashSet<Integer>();

        while(remainders.add(numerator))
        {
            whole = (int)numerator / denominator;
            result.append(whole);
            numerator = (numerator - (whole * denominator)) * 10;
        }

        ArrayList<Integer> remaindersList = new ArrayList<Integer>(remainders);
        if (result.charAt(result.length() - 1) != '0' && showRepeatingGroup)
        {
            int position = remaindersList.indexOf(numerator) + 2;
            result.insert(position,  "{");
            result.append("}");
        }

        return result.toString();
    }
}

The conversion

Your program does not produce the correct output in all cases.

10000/3 produces 33{33.3} instead of 3333.{3}.

The reason is that in

int position = remaindersList.indexOf(numerator) + 2;

you assume that the integer part of the fraction is exactly one digit.
This can be (e.g.) solved by remembering the string length right after the integer part has been build:

StringBuilder result = new StringBuilder(whole + ".");
int initialLength = result.length();

120/999 produces 0.120 instead of 0.{120}

The reason is that in

if (result.charAt(result.length() - 1) != '0' && showRepeatingGroup)

the last fraction digit is checked as indicator if the fraction is
repeating or not. This does not work, you have to check if
numerator becomes zero.
2/5 produces 0.40 instead of 0.4

The reason is that you only check for a repeating remainder, but not
if the numerator becomes zero. Therefore an additional 0 is appended
to all non-repeating fractions.

Instead of a (ordered) hash set for the reminders which is converted
to a list later, I would use an (array) list in the first place.
Then you can check for repeating remainders and remember the position
to insert the group markers at the right place.

Other small things: The cast in

int whole = (int)numerator / denominator;

is not necessary, and

numerator = (numerator - (whole * denominator)) * 10;

can be simplified to

numerator = (numerator % denominator) * 10;

Taking all this into account, the divide() function becomes

public static String divide(int numerator, int denominator, boolean showRepeatingGroup)
{
    int whole = numerator / denominator;
    numerator = (numerator % denominator) * 10;

    StringBuilder result = new StringBuilder(whole + ".");
    int initialLength = result.length();

    List<Integer> remainders = new ArrayList<Integer>();
    int repeatingPos = -1;

    while (numerator > 0 && repeatingPos == -1) {
        remainders.add(numerator);
        whole = numerator / denominator;
        numerator = (numerator % denominator) * 10;
        result.append(whole);
        repeatingPos = remainders.indexOf(numerator);
    }

    if (repeatingPos >= 0 && showRepeatingGroup) {
        result.insert(initialLength + repeatingPos,  "{");
        result.append("}");
    }

    return result.toString();
}

But what I don't like is that the calculation of the fractional digits
is mixed with the conversion to a string. If we define a dedicated
DecimalFraction class then the two tasks can be separated clearly:

class DecimalFraction {
    int wholePart;      // Integer part
    List<Integer> fractionDigits; // Fractional digits
    int repeatingAt;    // Position of first repeating digit, or (-1)

    DecimalFraction(int numerator, int denominator) {
        wholePart = numerator / denominator;
        numerator = (numerator % denominator) * 10;
        fractionDigits = new ArrayList<Integer>();
        repeatingAt = -1;

        List<Integer> remainders = new ArrayList<Integer>();
        while (numerator > 0 && repeatingAt == -1) {
            remainders.add(numerator);
            int whole = numerator / denominator;
            numerator = (numerator % denominator) * 10;
            fractionDigits.add(whole);
            repeatingAt = remainders.indexOf(numerator);
        }
    }

    String toString(boolean showRepeatingGroup) {
        StringBuilder result = new StringBuilder(wholePart + ".");
        for (int i = 0; i < fractionDigits.size(); i++) {
            if (showRepeatingGroup && i == repeatingAt) {
                result.append("{");
            }
            result.append(fractionDigits.get(i));
        }
        if (showRepeatingGroup && repeatingAt >= 0) {
            result.append("}");
        }
        return result.toString();
    }
}

This can now be used as

DecimalFraction dfrac = new DecimalFraction(numerator, denominator);
System.out.println("Result: " + dfrac.toString(true));

The main program

As already mentioned in a comment, the slash does not need a pattern group:

Pattern p = Pattern.compile("(\\d+)/(\\d+)");

The code duplication in the "read until input is valid loop" can be
avoided by using a do {  } while() :

Scanner in = new Scanner(System.in);
Matcher m;
do  {
    System.out.print("Enter a fraction in the form x/y: ");
    String input = in.nextLine();
    m = p.matcher(input);
} while (!m.matches());
in.close();

And finally, I don't see why the variables are called top/bottom
instead of numerator/denominator:

int numerator = Integer.parseInt(m.group(1));
int denominator = Integer.parseInt(m.group(2));

DecimalFraction dfrac = new DecimalFraction(numerator, denominator);
System.out.println("Result: " + dfrac.toString(true));


Reading input keys from a shell I was cleaning up some old code and came across this (it's to read input from a terminal):
static public int read_input_key() {

    /*
    F1 ESC O P [27 79 80]
    F2 ESC O Q [27 79 81]
    F3 ESC O R [27 79 82]
    F4 ESC O S [27 79 83]
    Up ESC [ A [27 91 65]
    Down ESC [ B [27 91 66]
    Left ESC [ D [27 91 68]
    Right ESC [ C [27 91 67]
    Home ESC [ 1 ~ [27 91 49 126]
    F5 ESC [ 1 5 ~ [27 91 49 53 126]
    F6 ESC [ 1 7 ~ [27 91 49 55 126]
    F7 ESC [ 1 8 ~ [27 91 49 56 126]
    F8 ESC [ 1 9 ~ [27 91 49 57 126]
    End ESC [ 4 ~ [27 91 52 126]
    Page-up ESC [ 5 ~ [27 91 53 126]
    Page-down ESC [6 ~ [27 91 54 126]
    Insert ESC [ 2 ~ [27 91 50 126]
    F9 ESC [ 2 0 ~ [27 91 50 48 126]
    F10 ESC [ 2 1 ~ [27 91 50 49 126]
    F11 ESC [2 2 ~ [27 91 50 50 126]
    F12 ESC [ 2 3 ~ [27 91 50 51 126]
    */

    //

    try {

        if (System.in.available() != 0) {

            int c = System.in.read();
            if (c == 27) {

                switch (System.in.read()) {
                case 79:
                    switch (System.in.read()) {
                    case 80:
                        return VK_F1;
                    case 81:
                        return VK_F2;
                    case 82:
                        return VK_F3;
                    case 83:
                        return VK_F4;
                    }
                case 91:
                    switch (System.in.read()) {
                    case 65:
                        return VK_UP;
                    case 66:
                        return VK_DOWN;
                    case 68:
                        return VK_LEFT;
                    case 67:
                        return VK_RIGHT;
                    case 49: {
                        switch (System.in.read()) {
                        case 126:
                            return VK_HOME;
                        case 53:
                            return System.in.read() == 126 ? VK_F5 : 0;
                        case 55:
                            return System.in.read() == 126 ? VK_F6 : 0;
                        case 56:
                            return System.in.read() == 126 ? VK_F7 : 0;
                        case 57:
                            return System.in.read() == 126 ? VK_F8 : 0;
                        }
                    }
                    case 52:
                        return System.in.read() == 126 ? VK_END : 0;
                    case 53:
                        return System.in.read() == 126 ? VK_PAGE_UP : 0;
                    case 54:
                        return System.in.read() == 126 ? VK_PAGE_DOWN : 0;
                    case 50: {
                        switch (System.in.read()) {
                        case 126:
                            return VK_INSERT;
                        case 48:
                            return System.in.read() == 126 ? VK_F9 : 0;
                        case 49:
                            return System.in.read() == 126 ? VK_F10 : 0;
                        case 50:
                            return System.in.read() == 126 ? VK_F11 : 0;
                        case 51:
                            return System.in.read() == 126 ? VK_F12 : 0;
                        }
                    }
                    }
                }
            } else {
                return c;
            }
        }
    } catch (IOException e) {
        // restore terminal?
        e.printStackTrace();
    }

    return 0;
}

It work's fine, but I feel like it can be done really different. To explain the long comment (I should atleast refactor that), this for example:
    F1 ESC O P [27 79 80]

Means when you press the F1 key you will get the sequence ESC O P, which is represented by the following ascii keys, 27 79 80.

I think you will be able to implement this in a cleaner way by representing the key codes as data instead of control flow. Not only will the resulting code be shorter, but it will be more abstract. If you need to add new sequences or support multiple sets of sequences, you will be able to use the same basic logic.
More specifically, a trie data structure is a good match for your problem. The mapping process is simple: start at the root, input a character, and follow the corresponding branch. If there is no branch, fail. This must be modified slightly to output the original character if it is the sequence does not start with 27.
There is no trie in the Java collections framework, so you will have to build your own. The signature should be something like
class AsciiTrie {
  AsciiTrie[] children;
  int data;
}

Given this data structure, your new algorithm is the following
private static int readInputKey(AsciiTrie t) {
  if (System.in.available() == 0) {
    return 0;
  }

  int c;
  int depth = 0;
  while (t != null) {
    try {
      c = System.in.read();
    } catch {
      // handle error properly
    }

    t = t.children[c];
    depth += 1;

    if (t.data != 0) {
      return t.data;
    }
  }

  if (depth == 1) {
    return c;
  } else {
    return 0;
  }
}

I have not included code to build or populate the trie. But it is quite similar to traversal.


Is my Encryption Module Secure? I have a simple encryption module that is used to "encrypt" a text file because it contains some passwords. I only need to encrypt it because I need those passwords in my program (they are used to send an automated bug-report email), but I don't want the end-user to be able to see them.

My "encryption" function is VERY simple and straightforward: it replaces each character in the file with a two-character sequence (either two numbers, two letters, or a number and a letter - these are mapped using a dictionary). The "decryption" function simply reverses the dictionary ({v: k for k, v in _encrypt_key.items()}), then reads the file two-characters at a time and replaces each pair with the corresponding letter. All of this works fine. The file just looks like a bunch of random numbers and letters, so it can't be "read" without the decryption algorithm by any normal end-user.

I used Cython to convert my encryption module (which is a basic Python, .py file), to a .pyd file, so the module itself cannot be read by a normal text-editor.

The problem occurs if the end-user has any Python experience.

For example, it is a very basic task to open the Python console, import the module, open the text file, and decrypt it using the module's "decrypt" function. To prevent this, I used the __main__ module:

import __main__ as main
if hasattr(main, '__file__'):
    # define functions here

Now, it cannot be used interactively in a Python console, because the functions simply won't be defined if it is not being imported from an actual Python program.

To "secure" the key, I made the encryption key local to both functions (both the "encrypt" and "decrypt" functions have a copy of a different variable with the same data). Thus, the user cannot view the key directly.

Finally, I made sure that only certain modules can import it:

import __main__ as main
if hasattr(main, '__file__'):
    path = os.path.basename(main.__file__)
    if path in # tuple of specific files:
        # define functions here

The only loophole I can think of is if the main program itself is edited - other than the encryption module (which is packaged as a .pyd, so I'm not considering it as "open-source"), everything is open-source. If the end-user knows any Python, (s)he can simply open the main program and add a single line, which would show the passwords: print(EXTRA_DATA).

I thought of one way to prevent this:

from __future__ import print_function
print = lambda *args: None # prevent any printing, since my program itself doesn't require it

Of course, the user could always remove this, so it doesn't really fix it.

So, my overall questions are: Can I make this any more secure (make the data and module inaccessible by end-users), and can I prevent any way to print variables in my main program? I want to keep it as open-source if possible.

Manual attack

First of all, your encryption scheme is very weak and easily exploitable. Given a few hundred characters of ciphertext, even a novice cryptanalyst can crack this cipher in less than 30 minutes with only pen and paper. I recommend you stick to industrial-strength ciphers.

Security by obscurity

The obfuscations you are talking about (making a .pyd file and so on) will do little if anything to stop a serious attacker. The closest analogy I can think of is putting your door mat over the key, instead of just leaving the key in plain sight outside your door. It doesn't work very well. Any true encryption scheme needs to adhere to Kerchhoff's Principle, which states that a cryptosystem must be secure even if all parts of it (apart from the encryption key) are known by the attacker.

Wrong approach

In other words, you are approaching the problem from the wrong angle. For example, obfuscating the files won't help, because if an attacker has access to the computer the program is run on, he/she can access the memory directly to view the cleartext and/or key. Even worse, the attacker may even have a keylogger running. You need to design an algorithm that is so secure that having a completely open-source program isn't a problem. That is exactly what the people behind e.g. GPG have done. However, securing such a program against a malicious user isn't practically possible.

The problem is that cryptography is really, really hard. Some of the brightest people on the planet are continuously working to create new, unbreakable ciphers -- and still those ciphers are often broken.

What to do instead

I recommend reading about common cryptography principles and theory, and how basic ciphers are often broken. Don't bother with securing your program against a user - instead presume the program is running on a secure computer and make the ciphertext as secure as possible instead. Instead, write a cipher that is resistant to common techniques like frequency analysis and similar lexical attacks.

Finally, if you want easy and completely uncrackable encryption, I recommend looking into one-time pads. They are cryptographically secure, but they require a key that is at least as long as the plaintext.


Wait for a static value to appear In my program I need to monitor the state of a static string value that can be changed from different threads in different parts of the system. I came up with the following simple function that, once called, waits 5 seconds to get the value, and if the value is not set, returns null:

// Waits 5 seconds for value to appear and returns this value or null
public async Task<string> GetStringValueOrNull()
{
    var delayTask = Task.Delay(5000);
    var getValueTask = Task.Run(async () =>
    {
        while (true)
        {
            if (!string.IsNullOrEmpty(ExternalValueContainer.Value)) // ExternalValueContainer.Value is 'public static string'
                return ExternalValueContainer.Value;
            await Task.Delay(500);
        }
    });

    var firstCompletedTask = await Task.WhenAny(getValueTask, delayTask);
    if (firstCompletedTask == getValueTask)
    {
        return await getValueTask;
    }
    else
    {
        return null;
    }
}

The function is used like this:

string stringValue = await GetStringValueOrNull();
if (stringValue != null)
    DoSomething(stringValue);
else
    DoSomethingElse();

Can the logic in GetStringValueOrNull be somehow simplified?

Some other improvements:

Check ExternalValueContainer.Value synchronously first. If it already exist then you can return early, and there is no reason to await anything. (Note eurotrash's point about thread safety).
If value is never set, getValueTask never returns. Instead of waiting for delayTask separately, you should check the timeout inside getValueTask's body and return once timeout is exceeded.

In general I feel like proper unit tests should not use delays and should not rely on them. Not only because those 5s delays quickly add up if you run this method multiple times, but also because the behavior of unit tests becomes unpredictable. The same test can fail on one machine and pass on another, simply because on one machine GetStringValueOrNull() timed out, while on the other - it did not. IMHO you should take it as signal, that you design is flawed and should be changed. If you own ExternalValueContainer, then you should probably modify its API so consumer can wait for the value (using async methods, events, observables or any other suitable tool). If you do not own ExternalValueContainer then you should wrap it in non-static service and mock this service in your tests.


Parsing a text file of nested structures using a state machine My goal is to have something really simple with as small an amount of code as possible.  The real code is used to parse a text file of nested structures. This code is highly simplified but is the general way that the state machine would work.

Is there a replacement for the global?

# python doesn't support enums but can do this way
class state:
    OUT = 0
    DNARRAY = 1            # under "DN array" heading
    CSTA_REQUEST = 2       # aPDU-rose : invoke :
    CSTA_RESPONSE = 3      # aPDU-rose : retResult :
    END_OF_FILE   = 4

currentstate = state.OUT

def do_out():
    print "doing OUT - transitioning to DNARRAY"
    global currentstate
    currentstate = state.DNARRAY

def do_dnarray():
    print "doing dn array - transitioning to csta request"
    global currentstate
    currentstate = state.CSTA_REQUEST

def do_csta_request():
    print "doing csta request - transitioning to csta response"
    global currentstate
    currentstate = state.CSTA_RESPONSE

def do_csta_response():
    print "doing csta response - transitioning to END_OF_FILE"
    global currentstate
    currentstate = state.END_OF_FILE

statemap = {state.OUT : do_out,
           state.DNARRAY : do_dnarray,
           state.CSTA_REQUEST : do_csta_request,
           state.CSTA_RESPONSE : do_csta_response,
}

def decisions():
    while(currentstate != state.END_OF_FILE):
        statemap[currentstate]()

    print "done!"

decisions()

The obvious answer is to make currentstate an explicit return value from your functions, for example:

def do_out():
    print "doing OUT - transitioning to DNARRAY"
    return state.DNARRAY

Then handle it appropriately in the final loop:

def decisions():
    currentstate = state.OUT
    while(currentstate != state.END_OF_FILE):
        currentstate = statemap[currentstate]()
    print "done!"


Handling SMS replies to register/unregister phone numbers I'm working on a Django Twilio app, and I believe it's coming along well. I just want to improve my code writing skills. How can I improve the below code?

def save_number(request):
    from_number = request.POST.get('From', '')
    try:
        obj = SaveNumber.objects.get(phone_number=from_number)
        if obj == obj:
            subscribe = request.POST.get('Body', )
            if subscribe.lower().strip() == "stellar":
                enter = SaveNumber.objects.get(phone_number=from_number)
                enter.subscribed = True
                enter.save()
                r = twiml.Response()
                r.message("You're in. Always text outtahere, and we'll remove you.")
                return r
            elif subscribe.lower().strip() == "outtahere":
                remove = SaveNumber.objects.get(phone_number=from_number)
                remove.subscribed = False
                remove.save()
    except SaveNumber.DoesNotExist:
        obj = SaveNumber(phone_number=from_number)
        obj.save()
        r1 = twiml.Response()
        r1.message("Reply with stellar and you're in! :-)")
        return r1

Here is my alternative. Your original code calls the DB for the same record twice (potentially) -- the get_or_create does the same as your try/except and creates the record.

def save_number(request):
    from_number = request.POST.get('From', '')
    subscribe = request.POST.get('Body', '').lower().strip()
    obj, created = SaveNumber.objects.get_or_create(phone_number=from_number)
    response = twiml.Response()

    if created:
        response.message("Reply with stellar and you're in! :-)")
    else:
        if subscribe == "stellar":
            obj.subscribed = True
            obj.save()
            response.message("You're in. Always text outtahere, and we'll remove you.")
        elif subscribe == "outtahere":
            obj.subscribed = False
            obj.save()
            response.message("You're out")
    return response

Disclaimer: i didnt actually test it theyre may be bugs


Assembling a user agent descriptor, implemented using StringBuilder vs String I think performance won't be a big issue here as the concatenation only happens once (2-3 at worse because of multiple threads). Out of the two methods, which one would you prefer, in terms of readability and performance? Is there any better way to accomplish the task of calculating desired string:uaInfo?

 public static string GetUserAgentInfo()
    {
        if (_uaInfo == null)
        {
            string carrier = DeviceNetworkInformation.CellularMobileOperator ?? "(No Network)";
            var sb = new StringBuilder();
            sb.Append("device-type=mobile");
            sb.Append(";os=Windows Phone");
            sb.Append(";os-version=" + Environment.OSVersion.Version);
            sb.Append(";app-name:" + GetAppName());
            sb.Append(";app-version=" + GetVersion());
            sb.Append(";carrier=" + HttpUtility.UrlEncode(carrier));
            sb.Append(";locale=" + Locale);
            _uaInfo = sb.ToString();
        }
        return _uaInfo;
    }

    public static String GetUserAgentInfoOld()
    {
        if (_uaInfo == null)
        {
            string carrier = DeviceNetworkInformation.CellularMobileOperator ?? "(No Network)";
            string temp = "";
            temp += String.Format("{0}={1};", "device-type", "mobile");
            temp += String.Format("{0}={1};", "os", "Windows Phone");
            temp += String.Format("{0}={1};", "os-version", Environment.OSVersion.Version);
            temp += String.Format("{0}={1};", "app-name", GetAppName());
            temp += String.Format("{0}={1};", "app-version", GetVersion());
            temp += String.Format("{0}={1};", "carrier", HttpUtility.UrlEncode(carrier));
            temp += String.Format("{0}={1}", "locale", Locale);
            _uaInfo = temp;
        }
        return _uaInfo;
    }

For a method like this, don't worry about performance until you have evidence that performance is a problem. Either way will almost certainly be fast enough.

I would suggest instead for readability that you separate the data (key-value pairs) from the construction of the string.

If the order of the pairs is not important, you can write

var data = new Dictionary<string, string>
{
    { "device-type", "mobile" },
    { "os", "Windows Phone" },
    ...
};
return string.Join(";", data.Select(kvp => kvp.Key + "=" + kvp.Value));

If order is important, use the slightly more verbose

var data = new[]
{
    new KeyValuePair<string, string>("device-type", "mobile"),
    new KeyValuePair<string, string>("os", "Windows Phone"),
    ...
};
return string.Join(";", data.Select(kvp => kvp.Key + "=" + kvp.Value));


All permutations of integer vector I have spent a decent amount of (waaay too much) time trying to write the below function and get my head around recursion. The aim was to return all permutations of an int vector (assuming no duplications of input). I would like to know people's thoughts on my code. One downfall that I can identify is that it is pretty demanding of space since I am copying choice and out vectors many times.

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

void uni_permutes(std::vector<int> in, std::vector<int> out, std::vector<int> choice)
{
    int size = choice.size();
    //complete when all ints in choice have already been used
    if(size == 0) {
        for(int i : out) {
        std::cout << i << std::endl;
    }
        std::cout << '\n' << std::endl;
        return;

    }
    std::vector<int> newo = out;
    std::vector<int> newc = choice;
    for (int i : choice) {
        newo.push_back(i);
        //remove i from choice      newc.erase(std::remove(newc.begin(), newc.end(), i), newc.end());
        uni_permutes(in,newo, newc);
        newc = choice;
        newo = out;
}
    return;
}

int main()
{
    std::vector<int> v1 = {0, 1,2,3};
    std::vector<int > out;
    uni_permutes(v1,out,v1);

    return 0;
}

Here are my comments:

You should be passing in and choice as const reference to avoid unnecessary copies.
size should be of type size_t. In general, make sure you take care of whatever warnings the compiler throws at you.
Before we even come to algorithmic performance: are you sure this code works? I just did a bit of mental debugging, and it seems like you'll have an infinite recursion, since choice's size will never be zero. I'll assume for now that you accidentally commented out the line that erases from choice.
You have a defect in the code: consider a vector of [1, 1, 2, 2]. You'll return two permutations of [1, 2] [2, 1], while presumably you need [1 1 2 2] [1 2 1 2] etc. etc. This is because you delete all members of the same value from the vector rather than just delete at one index.
Indeed, there's way too much copying going on. If your goal is just to print all the permutations, or send them to some kind of consumer, then you should preallocate a single out vector, and replace members at given positions as you go through your recursion.


Splitting a string on delimiter outside of quotes while returning item-by-item One of the more recent functions I've needed for personal and work purposes is to split a string on a delimiter, but while ignoring the delimiter when inside a quote. Just as well, if within a quote then two adjacent double-quotes ("") should be treated as a double-quote escape, and as such should be output directly into the resultant string.

  Input:

"\"Doe, \"\"John\"\" Johnathan\", \"Doe, James\"".QuotedSplit(",")

  Output:

"Doe, \"\"John\"\" Johnathan", "Doe, James"

This actually posed a larger challenge than I originally anticipated, but in the end it was resolved pretty swiftly.

Obviously I want comments on all facets, but especially the idea of the performance of the method, and anything related to the yield return nature of it. I want it to be as lazy as possible, after all that's what good framework developers do, but I also want it to be robust.

The code is actually surprisingly long, but I think that's my fault for not abstracting it to a class, and I really do not want to abstract this to a class.

The method is as follows:

public static IEnumerable<string> QuotedSplit(this string s, string delim)
{
    var esb = new ExtendedStringBuilder(s.Length);

    bool inQuote = false;
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '\"')
        {
            if (i < s.Length - 1 && s[i + 1] == '\"')
            {
                esb += s[i++];
                esb += s[i];
            }
            else
            {
                inQuote = !inQuote;
                esb += s[i];
            }
        }
        else if (!inQuote)
        {
            if (s[i] == delim[0])
            {
                var split = true;
                for (int j = 0; j < delim.Length; j++)
                {
                    if (s.Length - 1 <= i + j)
                    {
                        split = false;
                        break;
                    }

                    if (s[i + j] != delim[j])
                    {
                        split = false;
                        break;
                    }
                }

                if (split)
                {
                    yield return esb;
                    esb.Length = 0;
                    i += delim.Length - 1;
                    split = true;
                    continue;
                }
            }

            esb += s[i];
        }
        else if (inQuote)
        {
            esb += s[i];
        }
    }

    if (esb.EndsWith(delim))
    {
        esb.Length -= delim.Length;
    }

    yield return esb;
}

The unique advantage of this method is that it can take a string as the delimiter, and will lazily evaluate it, without creating a weird method structure (like string.Split does).

I haven't noticed any bugs with it, though I guess it's possible that there are some. I've used it in the production environment it's part of for a while with no issues.

You can simplify your logic a bit.  Once in a quote you don't need to check for anything until you either at the end of the string or find another quote.

I also didn't use the ExtendedStringBuilder since I don't have that code and just used the StringBuilder class

From limited testing it returns the same as your function and from using Stopwatch class building a string of 10,000,000 random char it's a bit faster but nothing that couldn't be attributed to noise.

First I would create another method to just read ahead.  It makes it easier to see if we equal the delimiter passed in

private static IEnumerable<char> ReadNext(string str, int currentPosition, int count)
{
    for (var i = 0; i < count; i++)
    {
        if (currentPosition + i >= str.Length)
        {
            yield break;
        }
        else
        {
            yield return str[currentPosition + i];
        }
    }
}

I switch the for loop into a while so I can mess with the counter.  While you can change a counter in a for loop I generally frown on that as a developer I would not normally expect that.  With a while loop I would

public static IEnumerable<string> QuotedSplit2(string s, string delim)
{
    const char quote = '\"';

    var sb = new StringBuilder(s.Length);
    var counter = 0;
    while (counter < s.Length)
    {
        // if starts with delmiter if so read ahead to see if matches
        if (delim[0] == s[counter] &&
            delim.SequenceEqual(ReadNext(s, counter, delim.Length)))
        {
            yield return sb.ToString();
            sb.Clear();
            counter = counter + delim.Length; // Move the counter past the delimiter
        }
        // if we hit a quote read until we hit another quote or end of string
        else if (s[counter] == quote)
        {
            sb.Append(s[counter++]);
            while (counter < s.Length && s[counter] != quote)
            {
                sb.Append(s[counter++]);
            }
            // if not end of string then we hit a quote add the quote
            if (counter < s.Length)
            {
                sb.Append(s[counter++]);
            }
        }
        else
        {
            sb.Append(s[counter++]);
        }
    }

    if (sb.Length > 0)
    {
        yield return sb.ToString();
    }
}

SequenceEqual isn't known to be fast but unless you have a large string you using as a delimiter I wouldn't worry about it.  If you do, then it might be worth changing the IEnumerable<char> into a string using String.Concat and comparing the string from String.Concat directly to the delim variable.

Test

static void Main(string[] args)
{
    var random = new Random();
    var str = String.Concat(Enumerable.Range(1, 10000000).Select(_ => (char) random.Next(32, 122)));
    var timer = new Stopwatch();
    timer.Start();
    var result2 = QuotedSplit2(str, "1\\").ToArray();
    timer.Stop();
    Console.WriteLine(timer.ElapsedMilliseconds);
    timer.Reset();

    timer.Start();
    var result = QuotedSplit(str, "1\\").ToArray();
    timer.Stop();
    Console.WriteLine(timer.ElapsedMilliseconds);
    timer.Reset();

    Console.WriteLine(result2.SequenceEqual(result));
    Console.WriteLine(result2.Length);

    Console.ReadLine();
}


Suggesting "safe enum" class for ISO C There are quite some questions and answers about how to make enum really type-safe and I didn't find a solution that ensures both type safety and valid values. So I took some ideas and extended it to my own generic solution, somehow resembling to enum classes used in some other languages.

My solution adds the overhead of a pointer dereference for getting the actual enum value, but I think this is a fair deal for situations where you would otherwise have to check for the valid range in a lot of places. Comparing values works naturally with the == operator because there is only one global constant instance of each enum value.

I'm posting it here for review and comments if you like -- please tell me if you spot a bug or any other weakness in my idea. Is there anything I overlooked?

The "implementation" is just a header file:

csafenum.h

#ifndef CSAFENUM_H
#define CSAFENUM_H

#ifndef __GNUC__
#define __attribute__(x)
#endif

#include <assert.h>

/* declare an enum type: CSAFENUM_DECL(TypeName); */
#define CSAFENUM_DECL(tname) struct tname##_struct; \
    typedef const struct tname##_struct * tname; \
    const char *tname##_name(tname e) __attribute__((nonnull(1))); \
    int tname##_val(tname e) __attribute__((nonnull(1)))

/* declare an enum member: CSE_DECL(TypeName, MemberName); */
#define CSE_DECL(tname, name) extern const struct tname##_struct * const name

/* define an enum type: CSAFENUM_DEF(TypeName); */
#define CSAFENUM_DEF(tname) struct tname##_struct { \
    int val; \
    const char * const name; \
}; \
const char *tname##_name(tname tname##_cannot_be_null) \
{ \
    assert(tname##_cannot_be_null); \
    return tname##_cannot_be_null->name; \
} \
int tname##_val(tname tname##_cannot_be_null) \
{ \
    assert(tname##_cannot_be_null); \
    return tname##_cannot_be_null->val; \
} \
struct tname##_struct

/* define an enum member: CSE_DEF(TypeName, MemberName, IntegerValue); */
#define CSE_DEF(tname, name, v) \
    static const struct tname##_struct name##_memb = { v, #name }; \
    const struct tname##_struct * const name = &name##_memb

#endif

Example usage:

fruit.h

#ifndef FRUIT_H
#define FRUIT_H

#include <csafenum.h>

CSAFENUM_DECL(Fruit);

CSE_DECL(Fruit, Apple);
CSE_DECL(Fruit, Banana);
CSE_DECL(Fruit, Pear);
CSE_DECL(Fruit, Strawberry);

#endif

fruit.c

#include "fruit.h"

CSAFENUM_DEF(Fruit);

CSE_DEF(Fruit, Apple, 0);
CSE_DEF(Fruit, Banana, 1);
CSE_DEF(Fruit, Pear, 2);
CSE_DEF(Fruit, Strawberry, 3);

main program

#include <stdio.h>
#include "fruit.h"

int main()
{
    Fruit a, b, c, d;

    a = Apple;
    b = Banana;

    printf("a = %s (%d)\n", Fruit_name(a), Fruit_val(a));
    printf("b = %s (%d)\n", Fruit_name(b), Fruit_val(b));

    c = Apple;

    if (c == a) puts("c == a");
    if (c == b) puts("c == b");

    d = 0;

    printf("d = %s (%d)\n", Fruit_name(d), Fruit_val(d));

    return 0;
}

Output

  a = Apple (0)
  b = Banana (1)
  c == a
  example: fruit.c:3: Fruit_name: Assertion `Fruit_cannot_be_null' failed.
  zsh: abort      ./example/example

As pointed out by DarkDust, this does not work in switch blocks -- pointers aren't allowed to switch on. After thinking about this issue for a while, I get the feeling better not to try solving this, because it would either weaken or overcomplicate (or both) the whole thing.

The whole code is on GitHub.

Another problem with making the enum values pointers, is that it changes the in-memory representation of an enum. There are many situations where it's necessary for the enum to be an int (such as reading/writing structs to/from files).

If you need type-checked enums, it is better to use C++.


Pythonic Prime Generation I am using a sieve to return all primes under N:

def prime_gen(n):
    a = [x for x in range(2, n+1)]
    for b in range(2, round(n**.5)):
        c = 2
        while b*c <= n:
            if b*c in a:
                a.remove(b*c)
            c += 1
    return(a)

Is the conditional if b*c in a iterating through the list again? Without using a different algorithm entirely, how do I make this code more efficient and pythonic?

Use Python's math library

You can either import the whole math library, or just import the modules you need.

from math import sqrt, floor

Use a dictionary instead of a list

Yes, if b*c in a iterates through the list. However, if you use a dictionary, it takes only a single operation to look up any value. This is because Python stores dictionary keys and values as a hash table.

You can use Python's dict comprehension syntax.

d = {key: value for (key, value) in iterable}

The result looks like this:

from math import sqrt, floor

def prime_gen(n):
    a = {k: 0 for k in range(2, n+1)}
    for b in range(2, floor(sqrt(n))):
        c = 2
        while b*c <= n:
            if b*c in a:
                a.remove(b*c)
            c += 1
    return(a)


Second project Euler solution The things I'm interested the most from the review are:

The performance of the code
Overall review of the code structure, styling rules and naming conventions.

Problem: 2

  By considering the terms in the Fibonacci sequence whose values do not
  exceed four million, find the sum of the even-valued terms.

import math
import itertools
#----------------------------------------------------------------------------------
def calc_fibonacci_num(n):
    """Calculates the fibonacci number at the given index.

    Arguments:
        type:<int> - Index value of the fibonacci sequence
    Return:
        type:<int> - Fibonacci number at the given index.
    """
    return int(((1 + math.sqrt(5))**n -(1 - math.sqrt(5))**n)/(2**n*math.sqrt(5)))

#----------------------------------------------------------------------------------
def calc_fibonacci_seq(n):
    """Generates the fibonacci sequence with the highest
    value equal to or less then the number provided by the user.

    Arguments:
        type:<int> - Thrshold value for the fibonacci sequence.
    Return:
        type:<arr> - An array holding the fibonacci sequence.
    """
    return [calc_fibonacci_num(x) for x in itertools.takewhile(lambda x: calc_fibonacci_num(x) <= n, itertools.count())]

#----------------------------------------------------------------------------------
def calc_fibonacci_sum(n, d = 0):
    """Calculates the sum of the numbers in fibonacci sequence.
    Filtering of the numbers to be added is controled with the module operator.

    Arguments:
        type:<int> - Thrshold value for the fibonacci sequence.
        type:<int> - Division value for module operation.
    Return:
        type:<int> - The sum of the numbers in the fibonacci sequence.
    """
    if d > 1 :
        return sum(x for x in calc_fibonacci_seq(n) if x % d == 0)
    return sum(x for x in calc_fibonacci_seq(n))

#----------------------------------------------------------------------------------
def main():

    print(' Fibonacci-seq : {}'.format(calc_fibonacci_seq(4000000)))
    print(' Fibonacci-sum : {}'.format(calc_fibonacci_sum(4000000, 2)))

#----------------------------------------------------------------------------------
if __name__ == "__main__":
    main()

Your code looks good and is well documented. I have a few suggestions anyway.

Naming

calc_fibonacci_num is a long name for such a function. The calc_ prefix is probably not useful and neither is the _num.

The expression fibonacci(5) is probably explicit enough without additional information.

The same kind of comment applies to the other function names.

Domain definition (and default value)

It seems a bit "un-natural" to handle d=0 as a special case for calc_fibonacci_sum.
It may be clearer to explain that d is expected to be a strictly positive integer.

Then you'd just need to give d the default value 1 and everything would work just fine.

Function called twice

In return [calc_fibonacci_num(x) for x in itertools.takewhile(lambda x: calc_fibonacci_num(x) <= n, itertools.count())], you call the same function with the same argument twice. You can easily check this by adding a print(n) at the beginning of calc_fibonacci_num.

A solution to this issue is to rewrite the function:

def calc_fibonacci_seq(n):
    return itertools.takewhile(lambda x: x <= n, (calc_fibonacci_num(x) for x in itertools.count()))

This fixes another issue you had which is the fact you were building an actual list in memory when you just need a generator to go through the different lists.

An easier way to generate successive fibonacci numbers

The formula you've used is fairly efficient to generate the n-th fibonacci number without generating all the numbers before. However, in our case, we do need to compute them anyway. Thus, a naive solution would probably be faster. I'd suggest the following generator:

def fibo(f=1, g=1):
    """Yields Fibonacci numbers."""
    while True:
        yield f
        f, g = g, f + g


Magic square functions I'm writing a program for magic square and I'm a relative beginner to C++ and programming. I was hoping someone could help me find alternate or better ways to implement my code. This is the main function. I also entered a function to check if the input is odd, max 19, and to quit.

Is there a way to not have back-to-back for  and if statements?

#include <iostream>
#include <limits>
#include <iomanip>

using namespace std;
int oddfunction(int &a);
int endfunction(int &exit);
int maxfunction();
int main()
{
    int r, c, d, e, z=0;
    int *f = new(nothrow) int;
    int *g= new(nothrow) int;
    int magic[120][120];
    cout << "EML 2032 Final Project: Magic Square (odd numbers) " << endl;

    while(*g != 0)
    {
        cout << "\n\nMagic Squares for integers less than 20. ";
        for ( r=0 ; r<120 ; r++ )
        for ( c=0 ; c<120 ; c++ )
        magic[r][c] = 0;
        *f = oddfunction(*f);
        z = *f;
        cout <<"\n\n";
        d = 0 ;
        e = (z-1) / 2;
        magic[d][e] = 1;
        for ( r=2 ; r <= z * z ; r++ )
        {
            d--;
            e++;
            if ( d < 0 && e == z )
            {
                d  = d + 2;
                e--;
            }
            if ( d < 0 ) { d = z - 1; } if ( e >= z ) { e = 0; } if ( magic[d][e] != 0 )
            {
                d = d + 2;
                e = e - 1;
            }
            magic[d][e] = r;
        }
        for(r=0;r < z;r++)
        {
            for(c = 0; c < z; c++)
            {
                cout << setw(4) << magic[r][c];
            }
            cout << endl;
        }
        endfunction(*g);
   }
   cout << endl;
   cout << "Have a nice day!        THE END \n";
   system("pause");
   return 0;
}

int maxfunction()
{
    int c=0;
    cin >> c;
    while(c >= 20)
    {
        cin.clear();
        cin.ignore(numeric_limits<int>::max(),'\n');
        cout << "Input an odd integer up to 19.\n";
        cin >> c;
    }
    return c;
}
int oddfunction(int &a)
{
    int cont=0;
    while(cont == 0)
    {
        cout << "Input an odd number: " << endl;
        a = maxfunction();
        if(a % 2 == 0 )
        {
            if(a % 2 == 0 )
            {
                cout << "That wasn't odd! (odd numbers aren't divisible by 2)\nEnter any number to continue:" << endl;
                a = maxfunction();
            }
            else
            {
                a = maxfunction();
                cont++;
            }
        }
        else
        {
            cont++;
        }
    }
    return a;
}
int endfunction(int &exit)
{
    int h=0;
    int i=2032;
    h = exit;
    cout << "\n-Input 2032 to quit... \n-Input any other number to continue..." << endl;
    cin >> h;
    if(h == i)
    {
        exit = 0;
        return exit;
    }
    else
    {
        exit = 1;
        return exit;
    }
}

Naming

Avoid single-letter identifiers. r, c, d, e, z - who are those guys? What's their purpose? I need to thoroughly study the code to understand that, and then I'd immediately forgot them. Make my life easier.

oddfunction is really get_odd_number
Spacing

if ( d < 0 ) { d = z - 1; } if ( e >= z ) { e = 0; } if ( magic[d][e] != 0 )

is not possible to read. Sparing lines will not make your program run any better, but makes understanding and maintaining it much harder. I hope it is a copy-paste problem.
Redundancy

f and g do not have a right to exist. Especially they do not have right to exist as pointers. Also, you should make up your mind and return the result e.g. of oddfunction either by reference or by return value.
Separation of responsibilities

oddfunction prompts for an odd number, and calls maxfunction, which also prompts for an odd number, this time stating the limit. Double maintenance problem right away. Make one function to deal with IO (prompt and read), and another with business logic (validation). The same validation function shall recognize 2032 as a termination condition.

Along the same line, separate output from the calculations.
The algorithm is not reviewed, mostly due to the naming problem. An introductory comment (or a link to the algorithm) would also be helpful.


Getting the program's first argument as a number I want to get the first argument as a number, if there is any. This does not feel quite right, but I don't know yet what the Rust way would be.

I'm not searching for a args-framework or something, I just want to get a grip on doing stuff with Rust.

fn limit_from_args(args: env::Args) -> i32 {
    let args: Vec<String> = args.collect();
    if args.len() > 1 {
        match args[1].parse::<i32>() {
            Ok(i) => i + 1,
            Err(_) => 101,
        }
    } else {
        101
    }
}

There's always multiple ways to solve a problem, but if we keep your function signature unchanged, I'd probably write something like:

use std::env;

fn limit_from_args(mut args: env::Args) -> i32 {
    args.nth(1).and_then(|v| v.parse().ok()).unwrap_or(101)
}

fn main() {}

Notable things with your first solution:

There's no need to specify the String type when collecting; you can just use Vec<_>.
Since only one argument is needed, the code will be more efficient if that's all we look at. If there were thousands of arguments, there's no need to allocate space for 99% of them and then throw that away.
If you did have a slice or a vector, you can combine the range check and getting the value into one call with slice::get. This avoids the extra overhead of checking the index against the range:

match args.get(1) {
    Some(val) => ...,
    None => ...,
}

There's probably no need to specify the type for parse, it should be inferred from the return type.
Since the error codes are repeated, they should probably be extracted to a constant with a meaningful name. Even if they weren't repeated, 101 looks like a magic number.


Wall-following program I'm taking an AI Class and I managed to get my algorithm to work it's not complex since the robot is surrounded and placed by the wall. However, in my opinion, the code doesn't look so clean and I would like to have multiple functions in my Wall_Following() to make it look nicer. I've never programmed in Python before so I don't have much experience. I would like my function to look something like this:

def Wall_Follow(self)
 forward()
 if( front sensor > 150) # turns left if the front hits a wall
   Turn_left()
 elif(right sensor < 150) # turns right if too far away from wall
   Turn_Right()
 return left, right

This is my original code. Any feedback would be most appreciated on whether I'm just making this too complicated for myself.

def Wall_Follow(self):
 # default left/right values:
 left = self.MAX_SPEED * 0.8
 right = self.MAX_SPEED * 0.8

 if(self.ps_val[0] > 150
 or self.ps_val[7] > 150):
  left = -self.MAX_SPEED/2   #turn left

 elif(self.ps_val[2] < 150):
  right = -self.MAX_SPEED/2   #turn right

 return left,right

def run(self):

# Main loop
 while True:
  # Perform a simulation step of 64 milliseconds
  # and leave the loop when the simulation is over
   if self.step(self.TIME_STEP) == -1:
     break

   # functions to read sensor data
   self.read_sensors()

   # Process sensor data here.
   left, right = self.Wall_Follow()

   # Enter here functions to send actuator commands

   self.setSpeed(left, right)

controller = PyController()
controller.run()

I'd suggest that you "translate" the comparisons into meaningful names:

if self.BlockedInFront():
    left = -self.MAX_SPEED/2

if self.BlockedRight():
    right = -self.MAX_SPEED/2


Computing features over the same dataframe The following code computes three different features over the same dataset. I'm not sure if the filter_by_day_segment function can be made tidy or there's a more efficient/short but still readable way of refactor my code.

library(dplyr)

filter_by_day_segment <- function(data, day_segment){
  if(day_segment == "daily"){
    return(data %>% group_by(local_date))
  } else {
    return(data %>% filter(day_segment == local_day_segment) %>% group_by(local_date))
  }
}
compute_metric <- function(data, metric, day_segment){
  if(metric == "countscans"){
    data <- filter_by_day_segment(data, day_segment)
    return(data %>% summarise(!!paste("sensor", day_segment, metric, sep = "_") := n()))
  }else if(metric == "uniquedevices"){
    data <- filter_by_day_segment(data, day_segment)
    return(data %>% summarise(!!paste("sensor", day_segment, metric, sep = "_") := n_distinct(value)))
  }
  else if(metric == "countscansmostuniquedevice"){
    data <- data %>% group_by(value) %>%
      mutate(N=n()) %>%
      ungroup() %>%
      filter(N == max(N))
    data <- filter_by_day_segment(data, day_segment)
    return(data %>% summarise(!!paste("sensor", day_segment, metric, sep = "_") := n()))
  }

}

data <- read.csv("test.csv")

day_segment <- "daily"
metrics <-  c("countscans", "uniquedevices", "countscansmostuniquedevice")

features = data.frame()
for(metric in metrics){
  feature <- compute_metric(data, metric, day_segment)
  if(nrow(features) == 0){
    features <- feature
  } else{
    features <- merge(features, feature, by="local_date", all = TRUE)
  }
}

print(features)

A test CSV file

"local_date","value"
"2018-05-21","FC:44"
"2018-05-21","FC:58"
"2018-05-21","FF:7E"
"2018-05-21","F8:77"
"2018-05-21","F8:77"
"2018-05-22","FB:F1"
"2018-05-22","FC:62"
"2018-05-22","FE:D4"
"2018-05-22","FE:D4"
"2018-05-22","FC:F1"
"2018-05-23","F8:77"
"2018-05-23","F8:77"
"2018-05-23","FF:13"
"2018-05-23","F8:3F"
"2018-05-23","F8:3F"
"2018-05-23","F8:3F"
"2018-05-23","FC:B6"
"2018-05-24","FC:0D"
"2018-05-24","F8:3F"
"2018-05-24","F7:B6"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-24","F6:96"
"2018-05-25","FC:A8"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-25","FC:44"
"2018-05-26","FC:F1"
"2018-05-26","FC:A8"
"2018-05-26","FF:89"
"2018-05-26","FF:89"
"2018-05-26","FF:89"

If I was reviewing this code professionally, my first comment would be that you should stick to a style guide. This will govern things like spacing between statements, brackets, operators etc. It can be seen as a kind of nitpicky remark (I certainly did at first) but having a consistent style massively aids readability for you and for others.

The second (style) comment would be that your code is halfway between very pipe-based code and "standard" R style (lots of assignment). This makes it difficult to read. If you're going to go with pipes, stick with it.

Also, when using an ifelse with more than 2 conditions, it's often clearer to use a switch block. This reduces the potential for massive nested ifs, and should also discourage you from doing much branching within the if.

I don't really like how similar the summarise calls are in each case. Ideally I would refactor that, but I think that is somewhat tricky due to how dplyr handles n and n_distinct.

This is how I would rewrite your code, though I would also consult the tidyverse style guide to see their recommendations -- I generally try to avoid programming with dplyr so I'm not that familiar with the style.

filter_by_day_segment_refactor <- function(data, day_segment) {
  ## Minimise the amount done within the if/else clause (also reduces duplication)
  if (day_segment == "daily") {
    fun <- identity
  } else {
    fun <- function(x) filter(x, day_segment == local_day_segment)
  }
  data %>% fun() %>% group_by(local_date)
}

compute_metric_refactor <- function(data, metric, day_segment) {
  ## 3 case switch block with just 1 pipe each,
  ## rather than 3 conditionals with a mix of
  ## pipes and assignment
  switch(metric,
    "countscans" = {
      data %>%
        filter_by_day_segment(day_segment) %>%
        summarise(!!paste("sensor", day_segment, metric, sep = "_") := n())
    },
    "uniquedevices" = {
      data %>%
        filter_by_day_segment(day_segment) %>%
        summarise(!!paste("sensor", day_segment, metric, sep = "_") := n_distinct(value))
    },
    "countscansmostuniquedevice" = {
      data %>% group_by(value) %>%
        mutate(N = n()) %>%
        ungroup() %>%
        filter(N == max(N)) %>%
        filter_by_day_segment(day_segment) %>%
        summarise(!!paste("sensor", day_segment, metric, sep = "_") := n())
    }
  )
}


Algorithm for competing cells of 0s and 1s I'm working on a practice algorithm problem, stated as follows:

  There are eight houses represented as cells. Each day, the houses compete with adjacent ones. 1 represents an "active" house and 0 represents an "inactive" house. If the neighbors on both sides of a given house are either both active or both inactive, then that house becomes inactive on the next day. Otherwise it becomes active. For example, if we had a group of neighbors [0, 1, 0] then the house at [1] would become 0 since both the house to its left and right are both inactive. The cells at both ends only have one adjacent cell so assume that the unoccupied space on the other side is an inactive cell.

  Even after updating the cell, you have to consider its prior state when updating the others so that the state information of each cell is updated simultaneously.

  The function takes the array of states and a number of days and should output the state of the houses after the given number of days.

  Examples:

  input: states = [1, 0, 0, 0, 0, 1, 0, 0], days = 1
  output should be [0, 1, 0, 0, 1, 0, 1, 0]
  input: states = [1, 1, 1, 0, 1, 1, 1, 1], days = 2
  output should be [0, 0, 0, 0, 0, 1, 1, 0]

Here's my solution:

def cell_compete(states, days):
    def new_state(in_states):
        new_state = []
        for i in range(len(in_states)):
            if i == 0:
                group = [0, in_states[0], in_states[1]]
            elif i == len(in_states) - 1:
                group = [in_states[i - 1], in_states[i], 0]
            else:
                group = [in_states[i - 1], in_states[i], in_states[i + 1]]
            new_state.append(0 if group[0] == group[2] else 1)
        return new_state

    state = None
    j = 0
    while j < days:
        if not state:
            state = new_state(states)
        else:
            state = new_state(state)
        j += 1
    return state

I originally thought to take advantage of the fact they are 0s and 1s only and to use bitwise operators, but couldn't quite get that to work.

How can I improve the efficiency of this algorithm or the readability of the code itself?

EDIT: Thanks to @benrg pointing out a bug of the previous algorithm. I have revised the algorithm and moved it to the second part since the explanation is long.

While the other answer focuses more on coding style, this answer will focus more on performance.

Implementation Improvements

I will show some ways to improve the performance of the code in the original post.

The use of group is unnecessary in the for-loop. Also note that if a house has a missing adjacent neighbour, its next state will be the same as the existing neighbour. So the loop can be improved as follows.

for i in range(len(in_states)):
    if i == 0:
        out_state = in_states[1]
    elif i == len(in_states) - 1:
        out_state = in_states[i - 1]
    else:
        out_state = in_states[i - 1] == in_states[i + 1]
    new_state.append(out_state)

It is usually more efficient to use list comprehensions rather than explicit for-loops to construct lists in Python. Here, you need to construct a list where: (1) the first element is in_states[1]; (2) the last element is in_states[-2]; (3) all other elements are in_states[i - 1] == in_states[i + 1]. In this case, it is possible to use a list comprehension to construct a list for (3) and then add the first and last elements.

new_states = [in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1)]
new_states.insert(in_states[1], 0)
new_states.append(in_states[-2])

However, insertion at the beginning of a list requires to update the entire list. A better way to construct the list is to use extend with a generator expression:

new_states = [in_states[1]]
new_states.extend(in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1))
new_states.append(in_states[-2])

An even better approach is to use the unpack operator * with a generator expression. This approach is more concise and also has the best performance.

# state_gen is a generator expression for computing new_states[1:-1]
state_gen = (in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1))
new_states = [in_states[1], *state_gen, in_states[-2]]

Note that it is possible to unpack multiple iterators / generator expressions into the same list like this:

new_states = [*it1, *it2, *it3]

Note that if it1 and it3 are already lists, unpacking will make another copy so it could be less efficient than extending it1 with it2 and it3, if the size of it1 is large.

Algorithmic Improvement

Here I show how to improve the algorithm for more general inputs (i.e. a varying number of houses). The naive solution updates the house states for each day. In order to improve it, one needs to find a connection between the input states \$s_0\$ and the states \$s_n\$ after some days \$n\$ for a direct computation.

Let \$s_k[d]\$ be the state of the house at index \$d\$ on day \$k\$ and \$H\$ be the total number of houses. We first extend the initial state sequence \$s_0\$ into an auxiliary sequence \$s_0'\$ of length \$H'=2H+2\$ based on the following:

$$
s_0'[d]=\left\{\begin{array}{ll}
s_0[d] & d\in[0, H) \\
0      & d=H, 2H + 1\\
s_0[2H-d] & d\in(H,2H] \\
\end{array}\right.\label{df1}\tag{1}
$$

The sequence \$s_k'\$ is updated based on the following recurrence, where \$\oplus\$ and \$\%\$ are the exclusive-or and modulo operations, respectively:
$$
s_{k+1}'[d] = s_k'[(d-1)\%H']\oplus s_k'[(d+1)\%H']\label{df2}\tag{2}
$$

Using two basic properties of \$\oplus\$: \$a\oplus a = 0\$ and \$a\oplus 0 = a\$, the relationship (\ref{df1}) can be proved to hold on any day \$k\$ by induction:

$$s_{k+1}'[d] = \left\{
\begin{array}{ll}
s_k'[1]\oplus s_k'[H'-1] = s_k'[1] = s_k[1] = s_{k+1}[0] & d = 0 \\
s_k'[d-1]\oplus s_k'[d+1] = s_k[d-1]\oplus s_k[d+1]=s_{k+1}[d] & d\in(0,H) \\
s_k'[H-1]\oplus s_k'[H+1] = s_k[H-1]\oplus s_k[H-1] = 0 & d = H \\
s_k'[2H-(d-1)]\oplus s_k'[2H-(d+1)] \\
\quad = s_k[2H-(d-1)]\oplus s_k[2H-(d+1)] = s_{k+1}[2H-d] & d\in(H,2H) \\
s_k'[2H-1]\oplus s_k'[2H+1] = s_k'[2H-1] = s_k[1] = s_{k+1}[0] & d = 2H \\
s_k'[2H]\oplus s_k'[0] = s_k[0]\oplus s_k[0] = 0 & d = 2H+1
\end{array}\right.
$$

We can then verify the following property of \$s_k'\$
$$
\begin{eqnarray}
s_{k+1}'[d] & = & s_k'[(d-1)\%H'] \oplus s_k'[(d+1)\%H'] & \\
s_{k+2}'[d] & = & s_{k+1}[(d-1)\%H'] \oplus s_{k+1}[(d+1)\%H'] \\
       & = & s_k[(d-2)\%H'] \oplus s_k[d] \oplus s_k[d] \oplus s_k[(d+2)\%H'] \\
       & = & s_k[(d-2)\%H'] \oplus s_k[(d+2)\%H'] \\
s_{k+4}'[d] & = & s_{k+2}'[(d-2)\%H'] \oplus s_{k+2}'[(d+2)\%H'] \\
       & = & s_k'[(d-4)\%H'] \oplus s_k'[d] \oplus s_k'[d] \oplus s_k'[(d+4)\%H'] \\
       & = & s_k'[(d-4)\%H'] \oplus s_k'[(d+4)\%H'] \\
\ldots & \\
s_{k+2^m}'[d] & = & s_k'[(d-2^m)\%H'] \oplus s_k'[(d+2^m)\%H']  \label{f1} \tag{3}
\end{eqnarray}
$$

Based on the recurrence (\ref{f1}), one can directly compute \$s_{k+2^m}'\$ from \$s_k'\$ and skip all the intermediate computations. We can also substitute \$s_k'\$ with \$s_k\$ in (\ref{f1}), leading to the following computations:

$$
\begin{eqnarray}
d_1' & = & (d-2^m)\%H' & \qquad d_2' & = & (d+2^m)\%H' \\
d_1 & = & \min(d_1',2H-d_1') & \qquad d_2 & = & \min(d_2', 2H-d_2') \\
a_1 & = & \left\{\begin{array}{ll}
s_k[d_1] & d_1 \in [0, L) \\
0 & \text{Otherwise} \\
\end{array}\right. &
\qquad a_2 & = & \left\{\begin{array}{ll}
s_k[d_2] & d_2 \in [0, L) \\
0 & \text{Otherwise} \\
\end{array}\right. \\
& & & s_{k+2^m}[d] & = & a_1 \oplus a_2 \label{f2}\tag{4}
\end{eqnarray}
$$

Note that since the sequence \$\{2^i\%H'\}_{i=0}^{+\infty}\$ has no more than \$H'\$ states, it is guaranteed that \$\{s_{k+2^i}\}_{i=0}^{+\infty}\$ has a cycle. More formally, there exists some \$c>0\$ such that \$s_{k+2^{a+c}}=s_{k+2^a}\$ holds for every \$a\$ that is greater than certain threshold. Based on (\ref{f1}) and (\ref{f2}), this entails either \$H'|2^{a+c}-2^a\$ or \$H'|2^{a+c}+2^a\$ holds. If \$H'\$ is factorized into \$2^r\cdot m\$ where \$m\$ is odd, we can see that \$a\geq r\$ must hold for either of the divisibilty. That is to say, if we start from day \$2^r\$ and find the next \$t\$ such that \$H'|2^t-2^r\$ or \$H'|2^t+2^r\$, then \$s_{k+2^t}=s_{k+2^r}\$ holds for every \$k\$. This leads to the following algorithm:

Input: \$H\$ houses with initial states \$s_0\$, number of days \$n\$
Output: House states \$s_n\$ after \$n\$ days
Step 1: Let \$H'\leftarrow 2H+2\$, find the maximal \$r\$ such that \$2^r\mid H'\$
Step 2: If \$n\leq 2^r\$, go to Step 5.
Step 3: Find the minimal \$t, t>r\$ such that either \$H'|2^t-2^r\$ or \$H'|2^t+2^r\$ holds.
Step 4: \$n\leftarrow (n-2^r)\%(2^t-2^r)+2^r\$
Step 5: Divide \$n\$ into a power-2 sum \$2^{b_0}+2^{b_1}+\ldots+2^{b_u}\$ and calculate \$s_n\$ based on (\ref{f2})

As an example, if there are \$H=8\$ houses, \$H'=18=2^1\cdot 9\$. So \$r=1\$. We can find \$t=4\$ is the minimal number such that \$18\mid 2^4+2=18\$. Therefore \$s_{k+2}=s_{k+2^4}\$ holds for every \$k\geq 0\$. So we reduce any \$n>2\$ to \$(n-2)\%14 + 2\$, and then apply Step 5 of the algorithm to get \$s_n\$.

Based on the above analysis, every \$n\$ can be reduced to a number between \$[0, 2^t)\$ and \$s_n\$ can be computed within \$\min(t, \log n)\$ steps using the recurrence (\ref{f2}). So the ultimate time complexity of the algorithm is \$\Theta(H'\cdot \min(t, \log n))=\Theta(H\cdot\min(m,\log n))=\Theta(\min(H^2,H\log n))\$. This is much better than the naive algorithm which has a time complexity of \$\Theta(H\cdot n)\$.


Validating user-provided control points for a Bézier curve I have made some code which will validate user input for getting 4 control points for a bezier curve. It works fine however I was just wondering If I could make this code any more compact or efficient?

p = [] #empty points array

#gets 4 control points from user input
def get_points():
    #loops through 4 times to get 4 control points
    points = ["Start Point(P0)", "Control Point 1(P1)", "Control Point 2(P2)", "End Point(P3)"]
    for i in range(4):
        while True:
            #user input
            p_input = input("Enter X,Y Coordinates for "+ points[i]+":")
            #splits the string into x and y coordinates
            p_components = p_input.split(',')
            #checks to see if user hasnt entered two coordinates
            if len(p_components) != 2:
                print("Missing coordinate please try again.")
                p_input = input("Enter X,Y Coordinates for "+ points[i]+":")
                p_components = p_input.split(',')
            #checks to see if the values can not be converted into floats
            try:
                x = float(p_components[0])
                y = float(p_components[1])
            except ValueError:
                print("Invalid coordinates", p_components, "please try again.")
            else:
                #makes sure user is not entering coordinates that will not appear on the screen.
                if(x > 1020 or x < 10) or (y > 760 or y < 10):
                    print("Invalid coordinates, please try again.")
                else:
                    #appends the x and y coordinates as a 2 dimensional array
                    p.append([float(p_components[0]), float(p_components[1])])
                    break

There are things that can be improved:

You could return the points instead of asigning the global variabel p
You could split the function in two functions:

get_four_bezier_points
get_point

it probably would be better to return float values instead of string values.
You could inform the user that the input x and y values should be between certain values and must be separated with a comma.
the error checking logic's could be restructured such that the second input statement can be removed.

Putting these together as an example:

def get_point(description):
    while True:

        p_input = input("Enter X,Y Coordinates for " + description + ": ")
        p_components = p_input.split(',')

        if len(p_components) != 2:
            print("Not two comma seperated values, please try again")
            continue # (jumps to the beginning of the while loop)

        try:
            x = float(p_components[0])
            y = float(p_components[1])
        except ValueError:
            print("No float values, please try again.")
            continue

        if(x > 1020 or x < 10) or (y > 760 or y < 10):
            print("Values out of bounds.")
            continue

        # oke values are good
        return [x,y]  # jumps out of the function and while loop

def get_four_bezier_points():
    p = []
    print("Enter four bezier points with x in [10,1020] and y in [10,760]")
    points = ["Start Point(P0)", "Control Point 1(P1)", "Control Point 2(P2)", "End Point(P3)"]
    for description in points:
        p.append(get_point(description))
    return p

p = get_four_bezier_points()


Speeding up Python depth-first search in large graph I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word objects, which have methods for determining whether e.g. a Word rhymes with another Word instance.

At each level of the search, I filter the successor nodes to those that match user-supplied constraints - for example, "first word in sequence must rhyme with last word in sequence", so lines of poetry with different poetic devices can be built from the Markov chain.

The code I have works, but with large amounts of text (27412 unique words, 160892 edges between words) for certain combinations of constraints, especially rhyming ones, it takes a very long time to come up with a sequence that satisfies the constraints, if there is a possible sequence in the chain. Here's an example:

>>> vg = VerseGenerator(some_very_long_text)
>>> cs = [Constraint(Word.rhymeswith, [0, 3])]
>>> vg.build_sequence(4, [], cs)
[Word(among), Word(the), Word(white), Word(young)] - 204ms via IPython %timeit
>>> cs = [Constraint(Word.rhymeswith, [0, 9])]
>>> vg.build_sequence(10, [], cs) - Doesn't terminate for at least 10 minutes

Can anyone see a way I could speed this up, if any? I'm experimenting with Cython, but it will be a while before I get up to speed on it. Perhaps there is some clever graph theory property or algorithm I could use to preprocess it, or something?

The code in its entirety is available at my Github. I'm using Python 3. I hope I have explained it clearly enough, but if not please point out what other information I should include.

def build_sequence(self, length, predicates, constraints, order='roulette'):
    ''' Traverse the graph in depth first order to build a sequence
    of the given length which fits the supplied predicates. If a
    matching sequence is not found, return partially constructed
    sequence. Begins with a randomly selected word from the graph
    '''

    # If there are any multiple-word constraints that begin at
    # this level, we need to create predicates so they can be
    # applied at future search levels
    def apply_constraints(cands, path, level, preds, cons):
        cs = [c for c in cons if c.indices[0] == level]
        search_nodes = []
        for can in cands:
            new_preds = []
            for con in cs:
                curried = partial(con.method, can)
                sub = con.indices[1:]
                new_preds.extend([Predicate(curried, i) for i in sub])
            rec = {'word': can, 'parent': path, 'level': level,
                   'preds': preds + new_preds}
            search_nodes.append(rec)
        return search_nodes

    stack = []
    level = 0

    # Get candidate starting nodes
    apply = [p.partial for p in predicates if p.index == level]
    cands = self.filter_words(self.chain.nodes(), apply)
    random.shuffle(cands)
    branches = apply_constraints(cands, None, level, predicates, constraints)
    stack.extend(branches)

    while stack and level < length:
        path = stack.pop()
        prev = path['word']
        level = path['level'] + 1
        preds = path['preds']

        # Filter nodes following previous word to get candidates for
        # the next word in the sequence.
        apply = [p.partial for p in preds if p.index == level]
        succ = self.shuffled_successors(prev, order=order)
        cands = self.filter_words(succ, apply)

        branches = apply_constraints(cands, path, level, preds, constraints)
        stack.extend(branches)

    # Walk backward through final recursive record to build the
    # resulting sentence
    result = []
    for i in range(level):
        result.append(path['word'])
        path = path['parent']

    return reverse(result)

Can anyone see a way I could speed this up

The predicate filtering approach is correct, but slow. It offers little guidance on which branches are worth exploring deeply.

Switch from hard boolean to a scoring approach, so you can sort candidate scores into rank order, which allows deeper exploration of more promising nodes earlier.


Batcher using Microsoft.Tpl.Dataflow What do you think?  In particular, I'm not sure about my exception handling approach to raise errors when posting objects; but I couldn't come up with anything better.

public class Thing
{
    public Thing(int number)
    {
        Number = number;
    }

    public int Number { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        var thingBatcher = new Batcher<Thing>(ProcessBatch, 100, TimeSpan.FromSeconds(30));

        try
        {
            for (var i = 0; i < int.MaxValue; i++)
            {
                thingBatcher.Post(new Thing(i));
            }
        }
        catch (Exception ex)
        {
            Console.WriteLine("Here:" + ex.Message);
            throw;
        }

        Console.ReadLine();
    }

    private static void ProcessBatch(IEnumerable<Thing> things)
    {
        Console.WriteLine("Batch found: " + things.Count());

        if (things.Any(thing => thing.Number == 400))
        {
            throw new InvalidOperationException("Something bad happened");
        }
    }
}

public class Batcher<T>
{
    private BufferBlock<T> _buffer;

    private ActionBlock<IEnumerable<T>> _actionBlock;

    public Batcher(
        Action<IEnumerable<T>> processBatch,
        int batchSize,
        TimeSpan maxTimeWaitingForBatch)
    {
        Initialize(batchSize, processBatch, maxTimeWaitingForBatch);
    }

    private void Initialize(int batchSize,
        Action<IEnumerable<T>> processBatch,
        TimeSpan maxTimeWaitingForBatch)
    {
        _buffer = new BufferBlock<T>();

        var batchStockEvents = new BatchBlock<T>(batchSize);

        // Use a timer to make sure that items do not remain in memory for too long
        var triggerBatchTimer = new Timer(delegate { batchStockEvents.TriggerBatch(); });

        // Use a transform block to reset the timer whenever an item is inserted to avoid unnessary batches
        var timeoutBlock = new TransformBlock<T, T>((value) =>
        {
            triggerBatchTimer.Change(maxTimeWaitingForBatch, TimeSpan.FromMilliseconds(-1));
            return value;
        });

        _actionBlock = new ActionBlock<IEnumerable<T>>(processBatch);

        _buffer.LinkTo(timeoutBlock);
        timeoutBlock.LinkTo(batchStockEvents);
        batchStockEvents.LinkTo(_actionBlock);

        _actionBlock.Completion.ContinueWith(x =>
        {
            // todo log exception here
            Console.WriteLine(x.Exception.Message);

        }, TaskContinuationOptions.OnlyOnFaulted);
    }

    public void Post(T someObject)
    {
        if (_actionBlock.Completion.IsCompleted)
        {
            throw new InvalidOperationException("The batcher is not accepting new objects as it is in a failed state");
        }

        _buffer.Post(someObject);
    }
}

var batchStockEvents = new BatchBlock<T>(batchSize);

I think that batchStockEvents is a weird name for a BatchBlock. It sounds like it's a collection of events, or something like that.

new Timer(delegate { batchStockEvents.TriggerBatch(); });

While using delegate this way allows you to ignore the parameter, I think it's cleaner (and shorter) to use lambda and use _ as the parameter name to indicate it's ignored:

new Timer(_ => batchStockEvents.TriggerBatch());

// Use a transform block to reset the timer whenever an item is inserted to avoid unnessary batches

Wouldn't it be enough to reset the timer whenever a batch is triggered? It would be more efficient and you would have one less block.

Also, the comment has a typo, it should be "unnecessary".

What's the purpose of the _buffer block? Couldn't Post() post directly to timeoutBlock?

  In particular, I'm not sure about my exception handling approach to raise errors when posting objects; but I couldn't come up with anything better.

Yeah, you can't rely on that check in Post() because by the time the failure happens, all items could have been posted. But if you just want to stop doing useless work by trying to Post() items that can never be processed, then I think this is the right approach.