Splitting a path string I have the following C# method to split a path string.  The only thing I know is a fixed string in the path and I have to split the full path into two parts, first part should be one level below the fixed string and the rest should be the second part.

For example, if I have the following path:

 string mainText = @"C:\Abc\Fixed\MyTemp\Japan\Tokyo";

then my firstPart would be "C:\Abc\Fixed\MyTemp" and second part "Japan\Tokyo"

I want to improve this method in terms of memory and speed.

private static void SplitPath(string mainText, out string firstPart, out string secondPart)
        {
            firstPart = string.Empty;
            secondPart = string.Empty;
            if (!string.IsNullOrEmpty(mainText))
            {
                string strConstatnt = "Fixed";
                List<string> splitted = mainText.Split(new char[] { '\\' }).ToList();
                int indexToFixed = splitted.IndexOf(strConstatnt);
                StringBuilder sbFirst = new StringBuilder();
                StringBuilder sbSecond = new StringBuilder();
                if (indexToFixed >= 0)
                {
                    for (int i = 0; i < splitted.Count; i++)
                    {
                        if (i < (indexToFixed + 2))
                        {
                            sbFirst.Append(splitted[i] + "\\");
                        }
                        else
                        {
                            break;
                        }
                    }

                    for (int i = (indexToFixed + 2); i < splitted.Count; i++)
                    {
                        sbSecond.Append(splitted[i] + "\\");
                    }
                }
                if (sbFirst.Length > 0)
                {
                    firstPart = sbFirst.Remove(sbFirst.Length - 1, 1).ToString();
                }
                if (sbSecond.Length > 0)
                {
                    secondPart = sbSecond.Remove(sbSecond.Length - 1, 1).ToString();
                }
            }
        }

I took the liberty to make the exercise as well to see how our approaches differ. I don't think there are many remarks in terms of performance although StringBuilder.Remove() is a red flag in that area.

All together I think my code provides a more easily readable solution which should help in terms of human-reading efficiency. In the end I pretty much abstracted the things you do under library features.

public void SplitPath(string mainText, out string firstPart, out string secondPart)
{
  const string pivot = "Fixed";
  const char delimiter = '\\';

  var entries = mainText.Split(delimiter);
  int pivotIndex = entries.Length;
  for (var i = 0; i < entries.Length; i++)
  {
      if (entries[i] == pivot)
      {
          // Take index + 2 because linq.Take/Skip is 1-based
          // Optionally take index + 1 to avoid out-of-bounds when the pivot is the last element
          pivotIndex = (i == entries.Length) ? i + 1 : i + 2;
          break;
      }
  }

  firstPart = string.Join(delimiter.ToString(), entries.Take(pivotIndex));
  secondPart = string.Join(delimiter.ToString(), entries.Skip(pivotIndex));
}

I have tested this code with inputs C:\Abc\Fixed\MyTemp\Japan\Tokyo, C:\Abc\Fixed and C:\Abc.

If you'd want to take your approach after all, a few remarks:

Try to early return by using a negated if-statement condition.
Put your delimiter in a variable
Avoid magic values
Avoid removing data from the StringBuilder


Learning JavaScript - calculator I'm learning JavaScript and as a start I'm trying to create a calculator.

window.onload = function() {

  var numbers = document.getElementsByTagName('span');
  var result = document.querySelectorAll('.result')[0];
  var clear = document.getElementsByClassName('clear')[0];

  for (var i = 0; i < numbers.length; i += 1) {
    if (numbers[i].innerHTML === '=') {
      numbers[i].addEventListener("click", calculate(i));
    } else {
      numbers[i].addEventListener("click", addValue(i));
    }
  }

  clear.onclick = function() {
    result.innerHTML = '';
  };

  function addValue(i) {
    return function() {
      if (numbers[i].innerHTML === '÷') {
        result.innerHTML += '/';
      } else if (numbers[i].innerHTML === 'x') {
        result.innerHTML += '*';
      } else {
        result.innerHTML += numbers[i].innerHTML;
      }
    };
  }

  function calculate(i) {
    return function() {
      result.innerHTML = eval(result.innerHTML);
    };
  }
};
 * {
   margin: 0;
   padding: 0;
   box-sizing: border-box;
   font: bold 15px Arial, sans-serif;
 }
 #calculator {
   width: 312px;
   height: auto;
   margin: 100px auto;
   padding: 10px 10px 10px 10px;
   background: #0088cc;
 }
 .top span.clear {
   float: left;
 }
 .top .result {
   height: 40px;
   width: 212px;
   float: left;
   background: rgba(0, 0, 0, 0.2);
   border-radius: 3px;
   font-size: 17px;
   line-height: 40px;
   color: white;
   text-shadow: 1px 1px 2px rgba(0, 0, 0, 0.2);
   text-align: right;
   letter-spacing: 1px;
 }
 .keys,
 .top {
   overflow: hidden;
 }
 .keys span,
 .top span.clear {
   float: left;
   position: relative;
   top: 0;
   cursor: pointer;
   width: 66px;
   height: 36px;
   background: white;
   border-radius: 3px;
   margin: 0 7px 11px 0;
   line-height: 36px;
   text-align: center;
   transition: all 0.2s ease;
 }
 span.equ {
   background: #00FF19;
 }
 .top span.clear {
   background: red;
   color: white;
   font-size: 17px;
 }
 .keys span:active {
   top: 3px;
 }
 .top span.clear:active {
   top: 3px;
 }

    C

    7
    8
    9
    +

    4
    5
    6
    -

    1
    2
    3
    ÷

    0
    .
    =
    x

* {
      margin: 0;
      padding: 0;
      box-sizing: border-box;
      font: bold 15px Arial, sans-serif;
    }

You should avoid the * if possible. The issue with * is that it affects all elements on the page, yours or otherwise. Consider using normalize.css to make default element styling consistent in a non-destructive manner.

.keys,
.top

For this app, this looks fine. Putting this on another page with existing markup, you can potentially clobber other styles (or get yours clobbered) because the class names are too generic. Also, very specific CSS (nested selectors) increase specificity. CSS written like this isn't easy to override. Consider using BEM naming scheme instead. It allows you to construct low-specificity selectors as well as make them meaningful.

transition: all 0.2s ease;

Assuming you can CSS3 or don't care about older browsers. The problem with all is that it applies to all. If you happen to change another property which also happens to be transitionable, this can catch you off guard. Consider specifying the specific property to transition.

window.onload = function() {

Nothing wrong here. Just wanted to point out that window.onload is probably the very last event to fire during the page load process. It also fires only after all images have loaded, which can take very long. Consider usign DOMContentLoaded event instead.

    clear.onclick = function() {
      result.innerHTML = '';
    };

One issue I see when doing handlers this way is that what if you want to add more handlers. Simply assigning a function to the event would only assign one at a time. In times where you want more handlers, this can be tricky. Use addEventListener instead.

var numbers = document.getElementsByTagName('span');
var result = document.querySelectorAll('.result')[0];
var clear = document.getElementsByClassName('clear')[0];

querySelectorAll has a single-element counterpart: querySelector. Use that for single-element returns. And while you're at it, you can forget the getElementsByTagName and getElementsByClassName, use querySelector and querySelectorAll for consistency. Performance losses are negligible in this case.

for (var i = 0; i < numbers.length; i += 1) {
  if (numbers[i].innerHTML === '=') {

= isn't a number. You should probably remove it from the numbers collection to avoid complexity in the code. Treat it like your clear.

Also, consider converting numbers to a proper array. This is possible using Array.prototype.slice.call(numbers). This way, you can easily use the forEach method to loop through the elements instead of constructing a fiddly for loop.

result.innerHTML = eval(result.innerHTML);

This can be tricky, not because eval is very powerful (that's a different issue), but because you're allowing execution of an arbitrary expression that may be interpretted very differently by JavaScript. One example is mentioned in the comments, where the numbers may be treated as octal. 011 + 2 isn't 13 but instead, 9 + 2 which is 11.

Since you are not separating the numbers explicitly anywhere for us to use parseFloat on each one to get the correct number representation, consider building a simple expression parser.


performance on this substring search I have the code below that gets hit several hundred times per second. I'm wondering what I can do to improve performance. It seems that there should be some way to build up a substring index. Is there some existing examples of that or an explanation on how to do this?

using System;
using System.Collections.Generic;
using System.Linq;
using Asi.Server.Interfaces.History;

namespace Asi.Server.History.AssetHistory
{
    public class TelemetrySubscriptionFilter: ITelemetryLogFilter, ITelemetryLogAutosubscriber
    {
        private readonly List<string> _shouldNotLogs = new List<string>
        {
            "Local Position Service",
            "Global Position Service",
            "PositionGroup.",
            "DKS/"
        };

        public bool ShouldNotLog(string telemetryName)
        {
            float period;
            if (ShouldAutoSubscribe(telemetryName, out period))
                return false;

            // telemetryName is longer than our filter texts
            return _shouldNotLogs.Any(s => telemetryName.IndexOf(s, StringComparison.Ordinal) >= 0);
        }

        private readonly List<string> _shouldAutoSubscribe = new List<string>
        {
            "Manual Mode",
            "Autonomous Driven",
            "Battery Voltage",
            "RPM",
            "Engine On",
            "Parking Brake",
            "Gear",
            "Stopping Distance",
            "Ready For Motion",
            "GPS Correction Sent",
            "Setpoint",
            "Dead Reckon",
            "VCU uC",
            "Feedback",
            "Off Path",
            "RMS",
            "Yaw Rate",
            "Stop Enabled",
            "Arbiter",
            "Velocity Error",
            "Processor"
        };

        public bool ShouldAutoSubscribe(string telemetryName, out float period)
        {
            period = 0.375f; // chosen somewhat arbitrarily
            return _shouldAutoSubscribe.Any(s => telemetryName.IndexOf(s, StringComparison.Ordinal) >= 0);
        }
    }
}

As with every performance question: run your code through a profiler

That said, your ShouldNotLog method can be simplified.  There is not much reason to check your auto subscribe list prior to checking your suppress list:

_shouldNotLogs is a shorter list
presumably, none of the strings in _shouldNotLogs should exist in _shouldAutoSubscribe

As a result, checking _shouldAutoSubscribe only adds extra work.  The only times you perform fewer operations is if the input name matches one of the first three elements in _shouldAutoSubscribe.  It's a wash at four.  Anything else is extra work.

This leaves us with the following:

    public bool ShouldNotLog(string telemetryName)
    {
        return _shouldNotLogs.Any(s => telemetryName.IndexOf(s, StringComparison.Ordinal) >= 0);
    }

Next, for readability, I would instead use string.Contains.  If you check the .NET source, string.Contains calls string.IndexOf internally with an Ordinal check, so it is effectively the same thing, but it declares your intent far better:

    public bool ShouldNotLog(string telemetryName)
    {
        return _shouldNotLogs.Any(s => telemetryName.Contains(s));
    }

If possible, though, an even better way of doing it would be to extract your telemetry names to some numerical ID and use enums or ints.  Number comparison will be far quicker than string comparison.  However, you state that your input names are superstrings of those appearing in your lists, so I don't know if that is feasible.


Subtract first and last nodes of linked list Problem from www.interviewbit.com.

  Problem : Given a singly linked list, modify the value of first half nodes such that :

  1st node’s new value = the last node’s value - first node’s current value

  2nd node’s new value = the second last node’s value - 2nd node’s current value,
  and so on …

  NOTE :
  If the length L of linked list is odd, then the first half implies at first floor(L/2) nodes. So, if L = 5, the first half refers to first 2 nodes.
  If the length L of linked list is even, then the first half implies at first L/2 nodes. So, if L = 4, the first half refers to first 2 nodes.
  Example :

  Given linked list 1 -> 2 -> 3 -> 4 -> 5,
  Return 4 -> 2 -> 3 -> 4 -> 5

  as
  for first node, 5 - 1 = 4
  for second node, 4 - 2 = 2

  Try to solve the problem using constant extra space.

This is my solution on the website's shell. How can this code be better?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param A : head node of linked list
    # @return the head node in the linked list
    def subtract(self, A):

        if not A.next:
            return A
        fast = A
        slow = A
        prev = None
        cnt = 0
        # reach till half
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            cnt += 1
        if fast:
            start = slow.next
        else:
            start = slow
        #reverse the latter half
        while start:
            temp = start.next
            start.next = prev
            prev = start
            start = temp

        firstA = A
        lastA = prev
        prev1 = prev
        currA = A

        # modify values of first half
        while cnt:
            currA.val = lastA.val - firstA.val
            firstA = firstA.next
            lastA = prev.next

            prev = prev.next

            currA = currA.next
            cnt -= 1

        # reverse the list again
        new_prev =None
        while prev1:
            temp = prev1.next
            prev1.next = new_prev
            new_prev = prev1
            prev1 = temp

        return A

More functions, please.

Every time you feel compelled to comment a block of code, consider factoring it out into a properly named function. For example,

def subtract(A):
    start = reach_till_half(A)
    prev = reverse(start)
    modify(A, prev)
    reverse(prev)

Of course names could (and should) be better.


Connect 4 game for AI agents This Connect 4 game will be used for implementing game-playing AI. Sample players are supplied. One takes user input, and the other plays randomly. Right now it's set for a human player to play against a randomly playing agent, but in the future I plan to try out algorithms such as Minimax and have AI agents play against themselves.

Some more features (such as notifying the players when the game is over, instead of just printing to stdout) need to be added for later work, but I'm showing this simply as a working base. I'm not so much looking for feature suggestions, since those will come later. I will be adding docstrings and comments, but for now it should be straight forward.

I'm looking for tips on: program correctness, code structure, and best practices (whether specific to Python or not).

(Python 3.2.3)

#!/usr/bin/env python

import numpy as np
from copy import copy
from abc import ABCMeta, abstractmethod

class Connect4Game():
    def __init__(self, player1, player2):
        self.player1 = player1
        self.player2 = player2
        self.player_names = {player1 : "Player1", player2 : "Player2"}
        self.board = np.zeros((6, 7), dtype=np.int8)
        self.turn = player1
        self.last_move = ()
        self.winner = None

    def gameover(self):
        if self.last_move == ():
            return False

        rind, cind = self.last_move

        row = self.board[rind, :]
        col = self.board[:, cind]
        diag1 = np.diagonal(self.board, cind - rind)
        diag2 = np.diagonal(np.fliplr(self.board), -(cind + rind - 6))

        for line in [row, col, diag1, diag2]:
            if line.shape[0] < 4:
                continue

            for four in [line[i:i+4] for i in range(len(line)-3)]:
                if sum(four == 1) == 4:
                    self.winner = self.player1
                    return True
                elif sum(four == 2) == 4:
                    self.winner = self.player2
                    return True

        if sum(self.board[0] == 0) == 0:
            return True

        return False

    def move(self, cind):
        free_index = sum(self.board[:, cind] == 0) - 1
        if free_index == -1:
            return False

        if self.turn is self.player1:
            self.board[free_index, cind] = 1
            self.turn = self.player2
        else:
            self.board[free_index, cind] = 2
            self.turn = self.player1

        self.last_move = (free_index, cind)
        return True

    def play(self):
        while not self.gameover():
            print(self.board)
            print(self.player_names[self.turn]+"'s turn.")

            self.move(self.turn.get_move(copy(self.board)))

        print(self.board)

        if self.winner is self.player1:
            print("Winner: player1")
        elif self.winner is self.player2:
            print("Winner: player2")
        else:
            print("Tie")

class BasePlayer(metaclass=ABCMeta):
    @abstractmethod
    def __init__(self, empty, me, opponent):
        pass

    @abstractmethod
    def get_move(self, board):
        pass

class HumanPlayer(BasePlayer):
    def __init__(self, empty, me, opponent):
        pass

    def get_move(self, board):
        col = input("Your move (0-6): ")
        return int(col)

class RandomPlayer(BasePlayer):
    def __init__(self, empty, me, opponent):
        pass

    def get_move(self, board):
        free_columns = np.where(board[0] == 0)[0]
        return np.random.choice(free_columns)

def main():
    player1 = HumanPlayer(0, 1, 2)
    player2 = RandomPlayer(0, 2, 1)

    game = Connect4Game(player1, player2)
    game.play()

if __name__ == "__main__":
    main()

I would advise using slightly longer names (rind should be row_ind, etc.), adding comments (while you are writing the code, not after) and avoiding counterintuitive variable names such as four. It is quite confusing when you are writing statements such as four == 2.

In addition, I would replace

self.last_move == ()

with

not self.last_move

to future-proof your code in case you switch to using lists or something else entirely.

Also, to simplify your structure, I would suggest splitting up your longer functions into other smaller functions, to make your code more digestible and reusable.

Also, instead of initializing players with tuples of seemingly random numbers, add some constants in your code for further increased readability.


Find the maximum number of consecutive zeros in an array Question: To find the maximum number of consecutive zeros in a given
  array.

  Example:

  Input: \${1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0}\$

  Output: "Maximum number of consecutive zeros : 6"

Here is what I've come up with:

public class ZeroSeriesLength {

    public static void main(String[] args) {

        int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};

        int maxLength = 0;
        int tempLength = 0;

        for (int i = 0; i < values.length; i++) {

            if (values[i] == 0) {
                tempLength++;
            } else {
                tempLength = 0;
            }

            if (tempLength > maxLength) {
                maxLength = tempLength;
            }
        }

        System.out.println("Maximum number of consecutive zeros : " + maxLength);
    }
}

Is the logic correct? Or can it be done via a simple approach?

Just a few short comments on your code:

Separation of concerns:

You should separate functionality into different parts. Currently your main method does everything. For small applications like this, that may not be a problem, but as soon as you have larger applications, it becomes more and more unpractical.

You should thus extract your "logic" into a method:

private static int countSuccessiveZeros(int[] values) {
   int maxLength = 0;
   int tempLength = 0;
   //....
   // Looping here
   return maxLength;
}

Now if you wanted to not count zeros, but twos, you could simply modify the code to the following:

private static int countSuccessive(int[] values, int target) {
   int maxLength = 0;
   int tempLength = 0;
   //Your loop here, instead of 0 use target to compare
   return maxLength;
}

This also makes your main-method more readable:

public static void main(String[] args) {
   int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};
   int successiveZeros = countSuccessive(values, 0);
   System.out.println("Maximum number of consecutive zeros : " + successiveZeros);
}

Naming:

Very nice, a compliment. Your variable names are short, clear, descriptive and follow Java conventions (camelCase). Keep it up ;)


CLRS implementation (opportunity to sort subarray) of merge sort in golang I'm reading "Introduction to Algorithms" by CLRS and I can't find an implementation of the pseudo code from the book in golang. By the original implementation I mean that we deal with extra parameters in the function to define slice of an original array. All implementations on the web deal with whole array. And that's not what Thomas Cormen wanted.
So I write this one:

package sort_merge

import (
    "math"
)

/*
CLRS implementation - we deal with slice of original array arr[p, r], indexes p and r are inclusive
*/
// arr={6, 5, 4, 3}; p=0; q=3
// arr={6, 5};       p=0; q=1
// arr={6};          p=0; q=0
func MergeSort(arr []int, p int, r int) {
    if p < r {
        q := (p + r) / 2 // last index of left array (rounding down)
        MergeSort(arr, p, q)
        MergeSort(arr, q+1, r)
        Merge(arr, p, q, r)
    }
}

func Merge(arr []int, p int, q int, r int) {
    left := make([]int, len(arr[p:q+1]))    // q+1, because right part of slice is exclusive
    right := make([]int, len(arr[q+1:r+1])) // q+1, because this is last index of left array
    copy(left, arr[p:q+1])
    copy(right, arr[q+1:r+1])          // r+1, because right part of slice is exclusive
    left = append(left, math.MaxInt64) // math.MaxInt64 used here as Infinity from original implementation
    right = append(right, math.MaxInt64)

    i, j := 0, 0
    for k := p; k <= r; k++ {
        if left[i] <= right[j] {
            arr[k] = left[i]
            i++
        } else { // left[i] > right[j]
            arr[k] = right[j]
            j++
        }
    }
}

You can run it:

package main

import "fmt"
import "./sort-merge"

func main() {
    arr := []int{6, 5, 4, 3}
    sort_merge.MergeSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

I'm reading "Introduction to Algorithms" by CLRS and I can't find an
  implementation of the pseudo code from the book in golang.

Here is my Go implementation of the pseudocode from the book.

package main

import (
    "fmt"
    "math"
)

// Introduction to Algorithms
// Third Edition
// Cormen, Leiserson, Rivest, Stein

func merge(a []float64, p, q, r int) {
    nLeft := q - p + 1
    nRight := r - q
    t := make([]float64, (nLeft+1)+(nRight+1))
    left := t[:nLeft+1]
    right := t[nLeft+1:]
    copy(left[:nLeft], a[p:])
    copy(right[:nRight], a[q+1:])
    left[nLeft] = math.Inf(0)
    right[nRight] = math.Inf(0)

    i, j := 0, 0
    for k := p; k <= r; k++ {
        if left[i] <= right[j] {
            a[k] = left[i]
            i++
        } else {
            a[k] = right[j]
            j++
        }
    }
}

// MergeSort sorts the slice a[p:r+1] in nondecreasing order.
func MergeSort(a []float64, p, r int) {
    if p < r {
        q := (p + r) / 2
        MergeSort(a, p, q)
        MergeSort(a, q+1, r)
        merge(a, p, q, r)
    }
}

func main() {
    a := []float64{9: 2, 4, 5, 7, 1, 2, 3, 6}
    fmt.Println(a)
    MergeSort(a, 9, 16)
    fmt.Println(a)
}

This is a real-world code review: Code should be correct, maintainable, robust, reasonably efficient, and, most importantly, readable.

Your code is not readable. Your code does not closely follow the pseudocode. For example, you deleted the n1 and n2 pseudocode variables:

n1 = q - p + 1
n2 = r - q

As a result, your code is very inefficient. Your code is off-by-one.

  The Go Programming Language
  Specification

  Appending to and copying
  slices

  The variadic function append appends zero or more values x to s of
  type S, which must be a slice type, and returns the resulting slice,
  also of type S. ... If the capacity of s is not large enough to fit
  the additional values, append allocates a new, sufficiently large
  underlying array that fits both the existing slice elements and the
  additional values. Otherwise, append re-uses the underlying array.

For left and right subarrays, you allocate slice with a capacity equal to the number of elements, then you immediately append a sentinel value. This allocates a new slice and copies the old values from the old slice to the new slice.

In my code, I renamed n1 and n2 to a more readable nLeft and nRight. In my code, I minimized the number and size of allocations.

A benchmark (1000 random elements) for my code

$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMSort-4  18720   64849 ns/op   98048 B/op   999 allocs/op

versus a benchmark (1000 random elements) for your code

$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMSort-4   6996  150493 ns/op  242880 B/op  3996 allocs/op


Check if is it possible to get to a point that is presented by a number Problem description from an Iranian online course, translated with the help of Google Translate:

Tired of coding, Mehdi has gone on to his childhood games. But because he doesn't know who to play with, he has to change the rules of the game and play solitaire. To begin with, he wants to play solitaire "Walnut, Break Out".
Mehdi is standing n cm from the wall and wants to reach the wall. To do this, he can extend his leg forward, or transverse his leg forward. The goal is for him to stretch his legs and move forward so that he can tangle with the wall at the end. But Mehdi doesn't code anymore, so you need to help him figure out how to win this game. That is, tell him to stretch his leg a few times and cross a few times to get the exact distance.
The problem is about checking whether we can get to a wall that is represented with a number, by horizontal and vertical moves or not. If we can, print one of the correct answers and we cant, print -1.

We have three input values: The distance to the wall \$ n \$ , the foot length \$ x\$ , and the foot width \$ y\$ . The values are restricted by
$$
1 \le n,x,y \le 100\,000 \, .
$$
We have to check if \$ n \$ is a multiple of \$ x \$ plus a multiple of \$ y \$. For example if \$n = 10 \$and \$x = 2 , y=3\$ , we can reach to \$10\$ with multiplying \$2 \cdot 2 + 3 \cdot 2 \$, or \$2 \cdot 5 + 3 \cdot 0 \$.
I wrote this code for it. I get correct answers for most of the test cases except one, and 2 errors for a time limit exceeded. I am looking for an optimized and faster solution.
#include<iostream>
using namespace std;
int main()
{
    int n,x,y;
    int x1,y1;
    cin>>n>>x>>y;
    bool flag = false;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n+1;j++)
        {
            if (x * i + j * y == n)
                {
                    flag = true;
                    x1=i;
                    y1=j;
                }
        }
         if(flag)
            break;
    }
    if(flag == false)
        cout<<"-1";
    else
    cout<<x1<<" "<<y1;

    return 0;
}

General remarks

This

using namespace std;

is considered bad practice, see for example Why is “using namespace std” considered bad practice? on Stack Overflow.

Consistent indenting and spacing increases the legibility of the code.

Use curly braces for if/else blocks even if they consist only of a single statement.

Enable all compiler warnings and fix them, such as

std::cout<<x1<<" "<<y1;
// Variable 'x1' may be uninitialized when used here
// Variable 'y1' may be uninitialized when used here

Choose better variable names:

bool flag = false;

does not indicate what the flag is used for.

Testing boolean values: This may be opinion-based, but I prefer

if (!flag) { ... }

over

if (flag == false) { ... }

The return statement in main() is optional, and can be omitted.

Program structure

Separating the actual computation from the I/O makes the main method short, increases the clarity of the program, and allows you to add unit tests easily. In addition, you can “early return” from the function if a solution is found, so that the flag, x1, y1 variables becomes obsolete.

As of C++17 you can return an optional which contains a value (the solution as a pair) or not.

With these suggestions, the program could look like this:

#include <iostream>
#include <optional>

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (x * i + j * y == n) {
                // Return solution:
                return std::make_optional(std::make_pair(i, j));
            }
        }
    }
    // No solution found:
    return std::nullopt;
}

int main()
{
    int n, x, y;
    std::cin >> n >> x >> y;

    auto solution = solveSteps(x, y, n);
    if (solution) {
        std::cout << solution->first << " " << solution->second << "\n";
    } else {
        std::cout << "-1\n";
    }
}

Increasing the performance

First you can increase i and j in steps of x and y, respectively. That reduces the number of iterations and save the multiplications:

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i += x) {
        for (int j = 0; j <= n; j += y) {
            if (i + j == n) {
                // Return solution:
                return std::make_optional(std::make_pair(i/x, j/y));
            }
        }
    }
    // No solution found:
    return std::nullopt;
}

The next improvement is to get rid of the inner loop: After moving  i steps of width  x you only have to check if the remaining distance is a multiple of y:

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i += x) {
        if ((n - i) % y == 0) {
            // Return solution:
            return std::make_optional(std::make_pair(i/x, (n-i)/y));
        }
    }
    // No solution found:
    return std::nullopt;
}

Another improvement would be to check if y > x. In that case it is more efficient to iterate in steps of width  y and check if the remaining distance is a multiple of x.

Mathematics

Some final remarks on how this can be solved mathematically, with links for further reading.

What you are looking for is solution \$ (i, j) \$ to the equation
$$
 n = i x + j y
$$
with non-negative integers \$ i, j \$. This is related to Bézout's identity. In particular, a solution can only exist if  \$ n  \$ is a multiple of the greatest common divisor  \$ \gcd(x, y)  \$, which is efficiently determined with the euclidean algorithm. In that case it is easy to check if a solution with non-negative numbers exists, compare e.g. Finding positive Bézout coefficients on Mathematics Stack Exchange.


Does this class-adding slow page rendering? Can you suggest ways of making this more efficient?  I don't want to repeat this example for all of my tags that need a class added, if there is a better way.

$("#menu").find("div:nth-child(2), div:nth-child(3), div:nth-child(4), div:nth-child(5), div:nth-child(6), div:nth-child(7)").addClass("menuDivs");

It's slow for the following reasons:

You're using find() which is a descendant lookup. jQuery will look for all descendants under an element and see if it's a match. If the DOM under that element is huge... you get the picture.
Additionally, you aren't really specific here. You just give it div, which makes it all the more so generic. There could be lots of <div> under that element.

What you can do:

If these elements you have are just children of #menu, then use children() which is just  searches one level down.
If the set you have contains the elements you want plus siblings, and they are in order, then you can do slice() instead. Slice is zero-indexed by the way.

$('#menu').children('div').slice(1,6).addClass("menuDivs");

Here's a demo


Isn't this Interest-ing? This is the fifth project in my CS1 class.  It's a bit more drab than my past projects, so my titles are getting worse unfortunately. :(

  Write a program that computes the annual after-tax cost of a new house
  for the first year of ownership.  The cost is computed as the annual
  mortgage cost minus the tax savings.  The input should be the price of
  the house and the down payment.  The annual mortgage cost can be
  estimated as \$ 3\% \$ of the initial loan balance credited toward
  paying of the loan principal plus \$ 6\% \$ of the initial loan
  balance in interest.  The initial loan balance is the price minus the
  down payment.  Assume a \$ 35\% \$ marginal tax rate and assume that
  interest payments are tax deductible.  So, the tax savings is \$ 35\% \$
  of the interest payment.  Your program should use at least two
  function definitions and should allow the user to repeat this
  calculation as often as the user wishes.

I may have cheated a bit with my required two function definitions...

mortgage.cpp:

/**
 * @file mortgage.cpp
 * @brief Computes the annual after-tax cost of a new house
 * @author syb0rg
 * @date 10/9/14
 */

#include <cctype>
#include <iostream>
#include <limits>

/**
 * Makes sure data isn't malicious, and signals user to re-enter proper data if invalid
 */
long double getSanitizedDouble()
{
    long double input = 0.0L;
    while(!(std::cin >> input) || input < 0)
    {
        // clear the error flag that was set so that future I/O operations will work correctly
        std::cin.clear();
        // skips to the next newline
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        std::cout << "Invalid input.  Please enter a positive number: ";
    }
    return input;
}

/**
 * Safetly grabs and returns a lowercase version of the character (if the lowercase exists)
 */
char32_t getSanitizedChar()
{
    // absorb newline character (if existant) from previous input
    if(std::cin.peek() == '\n') std::cin.ignore();
    return std::tolower(std::cin.get());
}

int main()
{
    do
    {
        long double housePrice = 0.0L;
        long double downPayment = 0.0L;

        // get input for house price, re-read input if not a positive number
        std::cout << "Enter the price of the house: $";
        housePrice = getSanitizedDouble();

        // get input for down payment, re-read input if not a positive number
        std::cout << "Enter the down-payment: $";
        downPayment = getSanitizedDouble();

        long double loanBalance = housePrice - downPayment;
        long double interest = .06 * loanBalance;
        long double annualMortgage = (.03 * loanBalance) + interest;
        long double savings = .35 * interest;
        long double totalCost = annualMortgage - savings;

        std::cout << "The annual after-tax cost of the house is $" << totalCost << std::endl;

        std::cout << "Run the program again (y/N): ";  // signify n as default with capital letter
    } while ('y' == getSanitizedChar());
}

Some minor changes I would recommend:

Replace the magic numbers with symbolic constants. It will be easier to
modify your program when these rates change.

constexpr long double ANNUAL_MORTGAGE_COST = 0.03;
constexpr long double LOAN_PRINCIPAL_PLUS = 0.06;
constexpr long double MARGINAL_TAX_RATE = 0.35;

Instead of doing the calculations inside main() I would suggest
putting it into a function.

long double totalPayment(long double housePrice, long double downPayment){

    long double loanBalance = housePrice - downPayment;
    long double interest = LOAN_PRINCIPAL_PLUS * loanBalance;
    long double annualMortgage = (ANNUAL_MORTGAGE_COST * loanBalance) + interest;
    long double savings = MARGINAL_TAX_RATE * interest;
    long double totalCost = annualMortgage - savings;

    return totalCost;
}


Inserting command output into multiline string I'm writing a bash script to that picks up a user password from an environment variable, hashes this, and inserts the results into a postgres database.

What I have works and looks fairly readable to me but I'm no expert on bash.  Are there better conventions I could be following for what I'm doing?

#!/bin/bash
HASHED=$(echo -n $GUAC_PASSWORD | sha256sum | head -c 64)

PGPASSWORD=$POSTGRES_PASSWORD psql -U postgres << EOF
INSERT INTO guacamole_entity (name, type) VALUES ('guacadmin', 'USER');
INSERT INTO guacamole_user (entity_id, password_hash, password_salt, password_date)
SELECT
    entity_id,
    decode('${HASHED}', 'hex'),
    null,
    CURRENT_TIMESTAMP
FROM guacamole_entity WHERE name = 'guacadmin' AND guacamole_entity.type = 'USER';
EOF

Edit: I thought up a way to do it without sed feels neater to me.

Update: Thanks @OhMyGoodness and @TobySpeight!  The conversations about passwords being in the clear got me twitchy enough to use docker secrets.  So now I have the passwords in a file, not environment variables. PGPASSWORD isn't actually needed as

  The PostgreSQL image sets up trust authentication locally so you may notice a password is not required when connecting from localhost

The finalized script looks like this now:

#!/bin/bash
hashed=$(tr -d '\n' < /run/secrets/guac_password | sha256sum | tr -dc a-f0-9)

psql -U postgres << EOF
INSERT INTO guacamole_entity (name, type) VALUES ('guacadmin', 'USER');
INSERT INTO guacamole_user (entity_id, password_hash, password_salt, password_date)
SELECT
    entity_id,
    decode('${hashed}', 'hex'),
    null,
    CURRENT_TIMESTAMP
FROM guacamole_entity WHERE name = 'guacadmin' AND guacamole_entity.type = 'USER';
EOF

If GUAC_PASSWORD is a string like -e foo or /etc/*, that's going to create problems.

Quote the input and avoid echo altogether.  While you're at it, whitelist the checksum output, making head redundant:

HASHED=$( tr -d '\n' <<<"$GUAC_PASSWORD" | sha256sum | tr -dc a-f0-9 )

edit: suppress newline added by <<<


Threadsafe DBContext in singleton I found out the hardway that access to DbContext in .NET is not threadsafe. I have a singleton for logging things using a dbcontext. The original version uses something like

public Logger{
  private MyContext context;
  private static Logger instance = new Logger();

  private Logger(){
    //init stuff, including context
  }

  public static Logger Instance {
      return this.instance;
  }

  public void someMethod(){
    //do something with this.context
  }
}

I'm thinking of a few solutions:

one would be is not making this a singleton at all, but instantiate a logger each time I need one.

I can think of added overhead as a disadvantage for this way, and simplicity as an advantage.

another one is locking (on the context or type) for each public method:

public void someMethod(){
  lock(this.context){
    //do something with this.context
  }
}

This adds extra maintenance complexity.

a third one could be one context per thread in a form of

private ConditionalWeakTable<Thread, MyContext> contexts = new ConditionalWeakTable<Thread, MyContext>();

private MyContext Context{
  get {
    return contexts.GetValue(Thread.CurrentThread, createContext());
  }
}

private MyContext createContext(){
  //instantiate a context
}

Pro: fairly consice, complexity is isolated
Con: batshit insane? Using System.Runtime.CompilerServices for something fairly mondaine, which also isn't what it's meant for.

Am I overlooking any arguments? What would you do?

General rules of thumb:

In order to take advantage of connection pooling (and you should), database connections should be as short lived as possible. Create, use, then immediately destroy.
Single instance objects should always be agile (defined as not holding system resources e.g. db connections, file handles, etc.).
If you need a single instance object to handle a system resource, it should be done in a protected manner using a named mutex (naming makes a mutex available to all threads across the computer) or Monitor. Within the protected block of code, if the resource is a db connection, apply rule 1.
When using object locking, you should create your locks around an arbitrary object, not the current object's instance e.g.:

private static readonly object _lockObject = new object();

...

try {
    Monitor.Enter(_lockObject);
    // Do protected stuff...
}
finally {
    Monitor.Exit(_lockObject);
}


Write a Kotlin function "commonPrefix" Task description:
Write a function commonPrefix, which takes two strings as parameter and returns the common prefix.
Example: parameters abcdef and abc1gv would return abc.
My implementation:
fun commonPrefix(str1: String, str2: String): String {
    var sRet = ""
    var i = 0
    val length = if (str1.length >= str2.length)
        str1.length else str2.length

    while (i < length) {
        if (str1.take(i + 1) != str2.take(i + 1)) {
            return sRet
        }

        sRet += str1[i++]
    }

    return sRet
}

val first = "abcdef"
val sec = "abc1ef"

println(commonPrefix(first, sec))

Is my implementation done in a good way? Where could it be optimized?

The first thing which stands out to me is that it's typically better to use standard functions than to roll-your-own even for trivial things. For example
val length = if (str1.length >= str2.length)
    str1.length else str2.length

could be better written as
val length = maxOf(str1.length, str2.length)

People often talk in circles about this thinking about efficiency, but that's generally a red herring. Modern compilers are pretty good at optimising, and the differences are likely to be minimal if they exist at all.
Instead, the number one reason for using a named function is readability. In the former example, I have to stop and piece together what it's actually doing. In the latter, I can see at a glance and continue to read the code fluently.
Following on from that, I can now see that it's the wrong check. Logically, a common prefix cannot be longer than the shorter of the two strings. So now that I can clearly see that the existing code is equivalent to a maxOf call, I realise it should probably instead be a minOf call.

The second thing that jumps out at me is the efficiencies of your loop. Every time you go through the loop, you are (1) comparing the whole prefix and (2) updating your return value. That is, the first time you're comparing "a" against "a" which is fine. By the third time round you're comparing "abc" against "abc", and so redoing the work of comparing "a" and "b". Then, you're taking your previous sRet object "ab", copying it and the "c" into a new string object, and assigning it back to sRet. If you're familiar with big O notation, that means that your overall function becomes O(n2) in the length of the prefix. It also means that you wind up creating and throwing away a lot of little temporary objects.
You don't need to do either. By the time you get to the third step in the loop, you already know that "ab" matches "ab" so you don't need to check again. Instead of using take to get the prefix, use get to get the actual letter. Then you can just check "c" against "c".
As to the problem of loads of throwaway sRet objects, the usual advice is to use a StringBuilder. Unlike a string, a StringBuilder is specifically made with the idea that you'll change it as you go. It's much more efficient for that purpose. However, in this case you don't need to do that because you don't need sRet at all! After all, both str1 and str2 contain the prefix you're after. You already have (and have used!) a function to get the prefix out. So just count along the two strings, comparing one character at a time. Once you know the number of characters that are the same, take it.

The final thing that I'd mention is testing. You've given one example pair of inputs to your function. That's a good thing, and it helps illustrate the problem. It's also worth thinking about what other examples are worth checking. In general for a function like this, I'd suggest it's worth testing at least the following:

str1
str2
reason

abc
xyz
It's easy to have a bug which messes up when the prefix is empty

a
b
It's easy to have a bug which messes up single character inputs

a
a
Same as above

abc
abc
It's easy to have a bug which breaks strings that are identical

abxyz
abc
You're trying to support inputs of different lengths, so this should be tested.

abc
abxyz
Same as above

abcde
abc
One string being a prefix of the other

Empty strings cause no end of problems and need to be tested

abc
Same as above


Altering contents when loading iframes I am quite new to JavaScript and I wonder if you experts can see any obvious mistakes in this working code, and if any, suggest good improvements.

// add iframes to page
var normal_sortables = document.getElementById('normal-sortables');
normal_sortables.innerHTML = normal_sortables.innerHTML + '

';

// declaring all variables
var code_to_be_inserted = '',
textarea_content = document.getElementById('content'),
iframe_upload = document.getElementById('iframe_upload'),
iframe_images = document.getElementById('iframe_images'),
iframe_pdf_documents = document.getElementById('iframe_pdf_documents');

// upload iframes of images and pdf documents when file is uploaded
iframe_upload.onload = function () {
iframe_images.src = 'images.php';
iframe_pdf_documents.src = 'pdf.php';
}

// add image to content editor
iframe_images.onload = function () {
    var images = iframe_images.contentWindow.document.getElementsByTagName('img');
    for (var i = 0; i < images.length; i++) {
        images[i].onclick = function () {
            code_to_be_inserted = '\n\n';
            textarea_content.value = code_to_be_inserted + textarea_content.value;
        }
    }
}

// add pdf documents to content editor
iframe_pdf_documents.onload = function () {
    var pdf_documents = iframe_pdf_documents.contentWindow.document.getElementsByTagName('a');
    for (var i = 0; i < pdf_documents.length; i++) {
        pdf_documents[i].onclick = function () {
            code_to_be_inserted = '\n\nClick here to open ' + this.innerHTML + '';
            textarea_content.value = textarea_content.value + code_to_be_inserted;
            alert ('testar');
            return false;
        }
    }
}

If you wanted to retain any event handlers that were already attached to your elements, you could change the first piece of code like this an avoid one of the dangers of setting innerHTML on an element that already has a bunch of HTML in it:

// add iframes to page
var normal_sortables = document.getElementById('normal-sortables');
// create container div
var newDiv = document.createElement("div");
newDiv.className = "postbox";
// put content into container div
newDiv.innerHTML = '';
// add container div to the sortables
normal_sortables.appendChild(newDiv);


A quartic polynomial in four variables, for numerical integration About half year ago, I derived a integral of a piecewise polynomial, which was a complex formula. Below is one of that formula:

Obviously, the above formula has relationship with four varibles \$u_i,\cdots u_{i+3}\$.

In the begining, I implement it in Wolfram Mathematica with the help of Compile[] technique and corresponding option like CompilationTarget -> "C". The screenshot as shown below:

Recently, I would like to rewrite it to C to achieve more higher performance.

#include <math.h>
#include <stdio.h>
//calc_A()
double calc_A(int i, const double *U) {
    double u0, u1, u2, u3;
    double res;
    u0 = U[i];
    u1 = U[i+1];
    u2 = U[i+2];
    u3 = U[i+3];
    //implementation of the explicit formula
    res = 3 * pow(u1, 4) + 3 * pow(u1, 3)*(u2 - 2 * u3) +
        pow(u1, 2)*(3 * pow(u2, 2) - 7 * u2*u3 + 3 * pow(u3, 2)) +
        u1*u2*(3 * pow(u2, 2) - 8 * u2*u3 + 4 * pow(u3, 2)) +
        pow(u2, 2)*(3 * pow(u2, 2) - 9 * u2*u3 + 8 * pow(u3, 2)) +
        pow(u0, 2)*(8 * pow(u1, 2) + 3 * pow(u2, 2) + 4 * u1*(u2 - 5 * u3) - 10 * u2*u3 +
        15 * pow(u3, 2)) - u0*(9 * pow(u1, 3) + pow(u1, 2)*(8 * u2 - 19 * u3) +
        u1*(7 * pow(u2, 2) - 22 * u2*u3 + 10 * pow(u3, 2)) +
        u2*(6 * pow(u2, 2) - 19 * u2*u3 + 20 * pow(u3, 2)));
    return res;
}

int main() {
    double U[] = { 0., 0., 0., 0., 0.2, 0.25, 0.4, 0.6, 0.8, 1., 1., 1., 1. };
    int i;
    double res;
    //calculate A[2]~A[6]
    for (i = 2; i <= 6; i++) {
        res = calc_A(i, U);
        printf("%f\n", res);
    }
    system("pause");
    return 0;
}

where, \$\mathbf U=\{u_0,\cdots,u_m\}\$

TEST

According to my experience, the code for res is inefficient, but I don't know how to deal with it by myself.

The compiler (when -fastmath or equivalent is active) will do a lot of optimizations for you, benchmark the current code and see if it's fast enough for your purposes. This means that the relative amount of time spent in that code is too small for speedups in that part to yield better results.

First step is to replace the pow calls with explicit (cached) multiplication. pow expects 2 floating point values and is a complex formula though it will most likely have a fast path for integer exponents (which after inlining will result in the same but I have little faith in compiler optimizations):

double calc_A(int i, const double *U) {
    double u0, u1, u2, u3;
    double res;
    u0 = U[i];
    u1 = U[i+1];
    u2 = U[i+2];
    u3 = U[i+3];

    double u0_2 = u0*u0;
    double u1_2 = u1*u1;
    double u1_3 = u1_2*u1;
    double u1_4 = u1_2*u1_2;
    //...
    res = 3 * u1_4 + 3 * u1_3*(u2 - 2 * u3) +
        u1_2*(3 * u2_2 - 7 * u2*u3 + 3 * u3_2) +
        u1*u2*(3 * u2_2 - 8 * u2*u3 + 4 * u3_2) +
        //...
}

Looking at the use case (calling it for every index in an array) it would pay to SIMD the function if your cpu supports double precision vector math (modern cpus almost certainly do).

This will mean using intrinsics for the math which will be less clear code but will probably be faster.


Comparing each property to the same value My code keeps some int value about the date range, and there is a method to check if all of it is zero. Is there a better way to do it than doing this?

public bool IsAllDayZero
{
    get
    {
        return
            Today == 0 &&
            Days1_2 == 0 &&
            Days3_6 == 0 &&
            Days7_10 == 0 &&
            Days11_15 == 0 &&
            Days16_30 == 0 &&
            Days31_45 == 0 &&
            Days46_60 == 0 &&
            Days60Plus == 0
            ;
        }
}

The question is: Why do you want to change it?

I bet you can get a shorter form with some use of xor, and, or etc. functions but I believe it's not worth it. For example:

public bool IsAllDayZero
{
    get
    {
        return
            (Today | Days1_2 | Days3_6| Days7_10 | Days11_15 |
             Days16_30 |  Days31_45 | Days46_60 | Days60Plus) == 0;
        }
}

It's indeed shorter but no way that it's more clear for some other person about what this code tries to achieve.

Or you can get a faster version that will revert the conditions and then execute only few conditions without a need to check them all but again I doubt that clarity of the code will worth such a changes.

However your current implementation is clear, complete and does exactly what it has to do without some extra noise and I just recommend not to change it.


Saving and Loading data with SQLite I'm in the process of learning SQLite in C# and I've come up with some generic methods for finding and updating data. I would appreciate any pointers with the design of my methods and/or my SQL syntax.

FYI: I'm using System.Data and Mono.Data.SqliteClientfor C# Mono 2.0 (Unity3D).

Here is an example of the database used for this post. Let's also assume that I check for null prior to obtaining/updating data.

Info - Table name

    | display_name | coins | total_score |
    |    Michael   |  100  |    1356     |
    |     John     |   50  |     904     |

Below is my FindData method, which is used to lookup data in a specified table.

    public object FindData (string tableName, string selectHeader, string whereHeader, object whereValue)
    {
        using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
        {
            dbConnection.Open ();

            using (var dbCommand = dbConnection.CreateCommand ())
            {
                dbCommand.CommandText = string.Format ("SELECT {0} " +
                                                       "FROM {1} " +
                                                       "WHERE {2} = @whereValue", selectHeader, tableName, whereHeader);

                SqliteParameter whereParam = new SqliteParameter ("@whereValue", whereValue);
                dbCommand.Parameters.Add (whereParam);

                using (var dbReader = dbCommand.ExecuteReader ())
                {
                    while (dbReader.Read ())
                    {
                        if (dbReader.GetValue (0) != null)
                            return dbReader.GetValue (0);
                    }
                }
            }
        }
        return null;
    }

I attempted to have SQL Injection prevention parameters for tableName, selectHeader and whereHeader, however, it kept throwing an error saying the syntax was wrong. I'm assuming this can't be done then.

That method can be used like so:

int coins = (int)FindData ("Info", "coins", "display_name", "Michael");

This attempts to obtain the value under column coins, from the table Info where the display_name column is equal to Michael

Next I have the UpdateData method. This is used to update/save the data in the specified table.

public void UpdateData (string tableName, string whereHeader, object whereValue, string setHeader, object setValue)
{
    using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
    {
        dbConnection.Open ();

        using (var dbCommand = dbConnection.CreateCommand ())
        {

            dbCommand.CommandText = string.Format ("UPDATE {0} " +
                                                   "SET {1} = @setValue " +
                                                   "WHERE {2} = @whereValue",
                tableName, setHeader, whereHeader);

            SqliteParameter setParam = new SqliteParameter ("@setValue", setValue);
            SqliteParameter whereParam = new SqliteParameter ("@whereValue", whereValue);

            dbCommand.Parameters.Add (setParam);
            dbCommand.Parameters.Add (whereParam);

            Debug.Log (dbCommand.CommandText);

            dbCommand.ExecuteNonQuery ();
        }
    }
}

This method can be used like so:

UpdateData ("Info", "display_name", character.displayName, "coins", character.coins);

This method attempts to update the Info table, based on the column displayName, which equals character.displayName, which then updates the coins column based on the character.coins variable

Can anyone provide any criticism/advice on these generic methods for saving and loading data from a Sqlite database.

SqliteParameter setParam = new SqliteParameter ("@setValue", setValue);
        SqliteParameter whereParam = new SqliteParameter ("@whereValue", whereValue);

        dbCommand.Parameters.Add (setParam);
        dbCommand.Parameters.Add (whereParam);

instead of doing this, you could actually do this

dbCommand.Parameters.AddWithValue("@setParam", setValue);
dbcommand.Parameters.AddWithValue("@whereValue", whereValue);

that is how I would do with with SQL Server, I don't think it is any different with SqlLite.

also,  I would do this a little differently as well

using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
{
    dbConnection.Open ();

    using (var dbCommand = dbConnection.CreateCommand ())
    {

I would instead write it like this

using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
using (var dbCommand = dbConnection.CreateCommand ())
{
    dbConnection.Open ();

it looks a lot cleaner and removes some of the nesting.

also, try to limit what you do inside the using statements, to whatever you actually need in the using statements and not more than that.

Another thing, don't spread your string onto 3 lines like that, it looks messy.

pull your SQL statement out of the using statements, and make it a simple string, then pass it into the constructor of the dbCommand.

this:

public void UpdateData (string tableName, string whereHeader, object whereValue, string setHeader, object setValue)
{
    using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
    {
        dbConnection.Open ();

        using (var dbCommand = dbConnection.CreateCommand ())
        {

            dbCommand.CommandText = string.Format ("UPDATE {0} " +
                                                   "SET {1} = @setValue " +
                                                   "WHERE {2} = @whereValue",
                tableName, setHeader, whereHeader);

            SqliteParameter setParam = new SqliteParameter ("@setValue", setValue);
            SqliteParameter whereParam = new SqliteParameter ("@whereValue", whereValue);

            dbCommand.Parameters.Add (setParam);
            dbCommand.Parameters.Add (whereParam);

            Debug.Log (dbCommand.CommandText);

            dbCommand.ExecuteNonQuery ();
        }
    }
}

should look more like this

public void UpdateData (string tableName, string whereHeader, object whereValue, string setHeader, object setValue)
{
    var sql = string.Format ("UPDATE {0} SET {1} = @setValue WHERE {2} = @whereValue", tableName, setHeader, whereHeader);
    Debug.Log (sql.ToString());

    using (var dbConnection = new SqliteConnection ("URI=file:" + Application.dataPath + connection))
    using (var dbCommand = dbConnection.CreateCommand (sql, dbConnection))
    {
        dbConnection.Open ();

        dbCommand.Parameters.AddWithValue("@setParam", setParam);
        dbcommand.Parameters.AddWithValue("@whereValue", whereValue);

        dbCommand.ExecuteNonQuery ();
    }
}


BrainF**k interpreter in python Here's what I've come up with:

def bf_interpreter(code: str) -> str:
    """
    Interprets BrainF**k code

    Examples:
        ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
        Hello World!

        +++++>++++[<+>-]++++++++[<++++++>-]<.
        9

    """

    outputs = []

    ptr = 0

    values = [0]
    length = 1

    brackets = []

    index = 0
    code_length = len(code)

    while index < code_length:
        char = code[index]

        while length <= ptr:
            length += 1
            values.append(0)

        if char == '>': ptr += 1
        if char == '<': ptr -= 1

        if char == '+': values[ptr] = (values[ptr] + 1) % 256
        if char == '-': values[ptr] = (values[ptr] - 1) % 256

        if char == '[':
            brackets.append(index)

        if char == ']':
            if values[ptr] == 0:
                brackets.pop()
            else:
                index = brackets[-1]

        if char == '.':
            outputs.append(chr(values[ptr]))

        if char == ',':
            values[ptr] = ord(input())

        index += 1

    return ''.join(outputs)

How do I make this look better? (More consistent, as well as strictly following PEP 8 conventions)

All of your if char == '>': ptr += 1 and similar checks should use elif after the first check. By using if for all of the checks, you're forcing them all to run, even once you've found a match. This is wasteful because the checks are necessarily exclusive of each other. Once one check is true, none of the other checks can be. For example, you should have:

if char == '>': ptr += 1
elif char == '<': ptr -= 1

elif char == '+': values[ptr] = (values[ptr] + 1) % 256
elif char == '-': values[ptr] = (values[ptr] - 1) % 256

Now the checks stop once a match is found which prevents unnecessary equality checks.

I'd also try to break this down into a few functions to help testing. Right now, you can only test bf_interpreter as one whole. You could have a function that takes the current character, and the state of the program (the brackets, ptr, outputs...), and returns a new state. That way you can easily test for a given state if a certain command produces a correct new state.

I'm assuming this loop is just to add padding so you don't go off the end of the slots?:

while length <= ptr:
    length += 1
    values.append(0)

You could make that a little neater by just using math and some concatenation. You could also just get rid of length and use len(values):

needed = ptr - len(values)
values += [0] * needed

ptr - len(values) calculates how many slots are needed, then [0] * needed produces that many 0s, and += adds them to values. If needed is negative, [0] * needed will produce [], and essentially cause no change.

If you want to avoid the temporary list that [0] * needed creates, you could replace that with:

values += (0 for _ in range(needed))

Now += just pulls from a generator that produces values as needed.

And then, just like how you don't need length, you don't need code_length either. len(code) is fine; len runs in constant time. You don't need to cache it for performance reasons.

Here's some timings to show the difference in runtime this can cause:

import timeit

TEST_CODE = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."

>>> timeit.timeit(lambda: bf_interpreter_orig(TEST_CODE), number=int(2e5))  # Two hundred thousand tests
77.3481031  # Takes 77 seconds

>>> timeit.timeit(lambda: bf_interpreter_len(TEST_CODE), number=int(2e5))
88.93794809999997

Where bf_interpreter_orig is your original code, and bf_interpreter_len is your original code but using len.

Yes, there's a difference. Note though, that's a ~11 second difference across 200,000 calls. That works out to roughly 58 microseconds per call to the interpreting function.

Unless you're calling bf_interpreter hundreds of thousands of times in a tight loop, the difference is unlikely to matter. This also likely has nothing to do with the fact that you're requesting a length, and more to do with one extra function call. Function calls aren't super fast in Python. Likely any extra call to any function would have similar effects.


Calculate questions per day on CodeGolf.SE I wrote a short script in Python 3 that connects to the Stack Exchange API, gets all questions on Programming Puzzles & Code Golf over the past two weeks, and determines the average number of questions per day as well as the average number of answers per question.

The number of questions per day is intended to match that on Area 51, which it does. Obviously it's much easier to just scrape Area 51 directly, but I wanted to figure it out myself for practice.

I'm not an expert with Python or with web APIs, so I was hoping you fine Code Review folks can help me improve my practices.

import requests, datetime, time

def seconds_since_epoch(dt):
    epoch = datetime.datetime(1970, 1, 1, tzinfo=datetime.timezone.utc)
    return int((dt - epoch).total_seconds())

today = datetime.datetime.now(datetime.timezone.utc)

params = {
    "site": "codegolf",
    "fromdate": seconds_since_epoch(today - datetime.timedelta(days=14)),
    "todate": seconds_since_epoch(today),
    "pagesize": 100,
    "page": 1
}

base_url = "https://api.stackexchange.com/2.2"

results = []

while True:
    req = requests.get(base_url + "/questions", params=params)
    contents = req.json()
    results.extend(contents["items"])
    if not contents["has_more"]:
        break
    if "backoff" in contents:
        time.sleep(contents["backoff"])
    params["page"] += 1

questions_per_day = len(results) / 14
answers_per_question = sum([q["answer_count"] for q in results]) / len(results)

print("Over the past 2 weeks, PPCG has had...")
print(round(questions_per_day, 1), "questions per day")
print(round(answers_per_question, 1), "answers per question")

My approach is to build the query using a dict and make the request to the API using the requests module. I set the page size to the maximum to reduce the number of requests made so that the daily quota isn't exhausted quite so fast.

The code is hosted on GitHub, should you want to fork and adapt it for your own purposes, assuming it isn't too terrible.

Your seconds_since_epoch function has a built-in Python equivalent, datetime.timestamp.

Your namespaces would be cleaner if you did from datetime import datetime, timezone.

You use a base_url variable, but do not use urllib.parse.urljoin. Either use a hardcoded URL, or properly join the base URL with the fragment.

results is better named as questions.

In sum([q["answer_count"] for q in results]) the [] is superfluous and inefficient.

Instead of printing 3 times in a row create a multiline format string and print once.

You never create a function that returns the questions, and do not define a main function. I suggest printing in the main function, that calls a function that gets and returns the question information.

This is how I would program it:

import requests
import time
from datetime import datetime, timezone, timedelta

def get_question_info(site, start, stop):
    API_URL = "https://api.stackexchange.com/2.2/questions"
    req_params = {
        "site": site,
        "fromdate": int(start.timestamp()),
        "todate": int(stop.timestamp()),
        "pagesize": 100,
        "page": 1
    }

    questions = []
    while True:
        req = requests.get(API_URL, params=req_params)
        contents = req.json()
        questions.extend(contents["items"])

        if not contents["has_more"]:
            break
        req_params["page"] += 1

        if "backoff" in contents:
            time.sleep(contents["backoff"])

    return questions

def get_area51_estimate(site):
    now = datetime.now(timezone.utc)
    fortnight_ago = now - timedelta(days=14)
    questions = get_question_info(site, fortnight_ago, now)
    avg_questions = len(questions) / 14
    avg_answers = sum(q["answer_count"] for q in questions) / len(questions)
    return avg_questions, avg_answers

if __name__ == "__main__":
    msg = """Over the past 2 weeks, PPCG has had...
{:.1f} questions per day
{:.1f} answers per question"""
    print(msg.format(*get_area51_estimate("codegolf")))


Menu for pictures average program I made a little script that takes images and averages / aligns them.

The script grew and now I have different options bound to the program, it can calculate the average for RGB or gray scale pictures and can create test data set to check if it works on different machines.

At the beginning I define the help message, yet isn't there a better way to store it?

def main(argv):
    help_message  = "---------------- HELP ----------------\n"
    help_message += "Usage:\n"
    help_message += "pythong main_avg.py -d path/to/folder/ -cd -cdrgb -avg -avgrgb -graph\n"
    help_message += "  -d | --directory: path to any directory, the program will generate the dataset, or calculate the average in the folder.\n"
    help_message += "  -cd: creates gray scale dataset.\n"
    help_message += "  -cdrgb: creates rgb scale dataset.\n"
    help_message += "  -avg: calculates the alignment and average of the picture in greyscale mode.\n"
    help_message += "  -avgrgb: calculates and outputs a rgb average, needs the data from -avg.\n"
    help_message += "  -graph: calculates and outputs the movement and angles graphs, needs the data from -avg.\n"
    help_message += "  -s: sound at the end of process.\n"
    help_message += "  -h, --help: prints this.\n"

Then I print the starting script, just because

    path, name, ext = get_pathname(argv[0])
    print("Script:", name + ext, "started")

Then I process the arguments

    # get the arguments
    opts = argv[1:]

    folder = ""
    create_dataset = False
    create_rgb_dataset = False
    avgerage_gray = False
    average_rgb = False
    produce_graphs = False
    sound_of_silence = False

    if len(opts) == 1 and opts in ('-h', '--help'):
        print(help_message)
    else:
        nopt = 0
        while nopt < len(opts):
            opt = opts[nopt]
            if opt in ("-d", "--directory"):
                try:
                    nopt += 1
                    folder = opts[nopt]
                except IndexError:
                    pass
            if opt == "-cd":
                create_dataset = True
            if opt == "-cdrgb":
                create_rgb_dataset = True
            if opt == "-avg":
                avgerage_gray = True
            if opt == "-avgrgb":
                average_rgb = True
            if opt == "-graph":
                produce_graphs = True
            if opt == "-s":
                sound_of_silence = True
            nopt += 1

The program checks if one option is chosen, and if so it start the subroutine.

    inopt = [create_dataset, create_rgb_dataset, avgerage_gray, average_rgb, produce_graphs]

    if isdir(folder):
        if all(opt == False for opt in inopt):
            print("No options chosen")
            print("")
            print(help_message)
        if create_dataset:
            run_create_test_dataset(folder)

        if create_rgb_dataset:
            run_create_rgb_dataset(folder)

        if avgerage_gray:
            run_average_gray(folder)

        if average_rgb:
            run_average_rgb(folder)

        if produce_graphs:
            run_produce_graphs(folder)

        if sound_of_silence:
            import winsound
            Freq = 2500 # Set Frequency To 2500 Hertz
            Dur = 1000 # Set Duration To 1000 ms == 1 second
            winsound.Beep(Freq,Dur)
    else:
        print("-d option is not a folder")
        print("")
        print(help_message)

Is the first time I build a argumented main, so I would love any suggestions!

I personally would suggest using argparse.
To make a simple one would be fairly easy, and could only require add_argument.
You only really need to know:

The first to arguments store a single letter argument such as -d, and a long version such as --directory.
It takes an argument of action='store_true' to make the variable a flag.
It takes help as the help text.

And so you could use:

import argparse

parser = argparse.ArgumentParser(prog='main avg')
parser.add_argument('-d', '--directory',
                    help='path to any directory, the program will generate the dataset, or calculate the average in the folder.')
parser.add_argument('--cd', action='store_true',
                    help='creates gray scale dataset.')
parser.add_argument('--cdrgb', action='store_true',
                    help='creates rgb scale dataset.')
parser.add_argument('--avg', action='store_true',
                    help='calculates the alignment and average of the picture in greyscale mode.')
parser.add_argument('--avgrgb', action='store_true',
                    help='calculates and outputs a rgb average, needs the data from -avg.')
parser.add_argument('--graph', action='store_true',
                    help='calculates and outputs the movement and angles graphs, needs the data from -avg.')
parser.add_argument('-s', action='store_true',
                    help='sound at the end of process.')

args = parser.parse_args()
if args.cd:
    run_create_test_dataset(args.directory)
elif args.cdrgb:
    run_create_rgb_dataset(args.directory)
...
else:
    print('No options chosen')

After this, you may want to look into add_mutually_exclusive_group, if they're mutually exclusive.


Refactor array for loop result types = [
    { name: "Feature"}
    { name: "Enhancement"}
    { name: "Bug"}
    { name: "Spike"}
  ]

buildIndex = (source, property) ->
  array = []
  array[prop[property]] = prop for prop in source
  array

buildIndex types, 'name'

Result:

[Feature: Object, Enhancement: Object, Bug: Object, Spike: Object]
  Bug: Object
  Enhancement: Object
  Feature: Object
    name: "Feature"
  Spike: Object

This is my ugly code.  How to refactor this?  My problem is the buildIndex function.  Iyt works, but  it isn't elegant.

There's something fishy here. You're creating an array, but you're not using it as one. You're simply adding named properties to it, like you can with any object. In the end, you're left with an array that still has a length of zero. So I'm betting you don't actually want an array at all.

And in that case, I'd rewrite it to this

buildIndex = (source, property) ->
  obj = {}
  obj[prop[property]] = prop for prop in source
  obj

No more array-nonsense. However, if this is indeed what you're going for, then that's pretty much it. I agree it doesn't look particularly elegant, but it's about as good as it gets with basic CoffeeScript.

However, you could use reduce, if you're targeting browsers that support it (or Node.js):

buildIndex = (source, property) ->
  source.reduce (obj, item) ->
    obj[item[property]] = item
    obj
  , {}

but as you can see, the callback-first style of reduce means you end up with a dangling comma and argument instead, which isn't terribly neat either.

Alternatively, if you're using something like underscore.js, you can use a groupBy function to do this for you

buildIndex = (source, property) ->
  _.groupBy source, (item) -> item[property]

Looks better, although it's merely hiding the same code as above.


Create Action in Rails 3.2 I posted a question last week about refactoring an after_create callback. The code in this question is for the create action. I'm using Stripe to handle credit card payments and am roughly following the railscast on Stripe integration.

Here's my create action on the Payment model:

def create
  @unpaid_subs = Subscription.where(:user_id => current_user.id).unpaid.includes(:course)
  @payment = Payment.new(params[:payment])

  @payment.user_id = current_user.id
  @payment.email = current_user.email
  @payment.kind = @payment.determine_kind
  @payment.amount = calculate_cost(@unpaid_subs)

  if @payment.save_with_payment
    redirect_to dashboard_url, :notice => "Thank you for Paying!"
  else
    render :action => 'new'
  end
end

I am going to change the model associations so that payment belongs_to :user, so setting the user_id and email will go away. Here's the save_with_payment method:

def save_with_payment
  if valid?
    charge = Stripe::Charge.create(amount: amount, description: "Charge for #{email}", card: stripe_card_token, currency: "usd")
    save!
  end
rescue Stripe::InvalidRequestError => e
  logger.error "Stripe error while creating charge: #{e.message}"
  errors.add :base, "There was a problem with your credit card."
  false
end

determine_kind is a simple if conditional for setting the kind attribute. calculate_cost is in a module right now and included where needed.

def calculate_cost(unpaid) # Used to return amount total in cents for payment
  @amount_in_pesos = BigDecimal.new(unpaid.size) * COURSE_COST
  @amount_in_cents = (@amount_in_pesos.div(EXCHANGE_RATE, 10).round(2) * 100).to_i
  @amount = @amount_in_cents
  @amount
end

So, I'm mainly wanting general suggestions for improvement of this code. I was a little confused as to where calculate_cost should go (maybe as a method on the Payment model, even though it doesn't use an instance of Payment). Is there any better way to handle the call to the Stripe API?

Most of the following can be summed up as the ol' Rails rule-of-thumb: Skinny controller, fat model

1. Move logic to the model, and make it automatic

If you're doing this:

@payment.kind = @payment.determine_kind

it means that the logic should move to the model itself. If the model's doing the logic already and the result is saved to the very same model, why involve the controller at all?

Instead, you should do this:

class Payment < ActiveRecord::Base
  before_create :set_kind # determine and set the :kind attribute
  # ...

  private

  def set_kind
    self.kind = ... code ...
  end
end

However, there may be an even cleaner solution. As far as I can tell, determine_kind probably relies solely on information already in the payment record.

If that's the case, there may not be a reason to have a kind attribute/column at all. Just add a kind method to the Payment model:

class Payment < ActiveRecord::Base
  # ...
  def kind
    # same code as `determine_kind`
  end
  # ...
end

Now you can say some_payment.kind and get the kind without storing it in the database at all.

Note: this won't work if kind must be "kind as determined at the time of creation" or if you're doing database queries that involve the kind column. If either of those is the case, you can still use the before_create approach above.

2. Add calculate_cost to the collection

Here's what I'd do:

First, I'd move COURSE_COST to a COST constant on the Course model (accessible as Course::COST). That seems the most logical place to keep it. It'd probably be smart to also move EXCHANGE_RATE to Payment::EXCHANGE_RATE while you're at it.
Oh, and "exchange rate" is a little ambiguous: It's the rate from what to what? Pesos to USD? Or the other way around? Would be good to make the name more descriptive.

Then, assuming "user has_many subscriptions", you can first of all do this:

@unpaid_subs = current_user.subscriptions.unpaid.includes(:course)

but it also means that you can define modules that should be added to the collection. In your case, you make a module like so:

# in app/modules/subscription_collection.rb
module SubscriptionCollection
  def cost
    pesos = count * Course::COST
    usd   = pesos / Payment::EXCHANGE_RATE
    (usd * 100).round
  end
end

(I skipped the BigDecimal stuff because I didn't think it necessary, but as covered in the comments, it might be. I'll leave the code as is, though. BigDecimal or not, the procedure's the same.)

And then include that module in the relation declaration

class User < ActiveRecord::Base
  has_many :subscriptions, :extend => SubscriptionCollection
  # ...
end

Now, whenever you get a collection of subscriptions via a user model you can simply call cost on the collection itself, and get the total cost.

Now you should be able to say:

def create
  @unpaid_subs = current_user.subscriptions.unpaid.includes(:course)
  @payment = current_user.payments.new(params[:payment])

  @payment.amount = @unpaid_subs.cost

  if @payment.save_with_payment
    redirect_to dashboard_url, :notice => "Thank you for Paying!"
  else
    render :action => 'new'
  end
end

Last little thing: This is just me, but the name save_with_payment is a little iffy, since the model's already called payment. So, "save payment with payment" seems semantically messy. I'd suggest something like charge_and_save instead. You might also want to raise an exception if someone tries to call the method on an already-charged payment. You don't want to accidentally charge people multiple times!


Find duplicates for mixed type values in dictionaries Following these two SO questions:

Find duplicates for mixed type values in dictionaries
Group similar dict entries as a tuple of keys

I came to the conclusion that the solution I proposed is mature enough to be reviewed here.

The idea is to find duplicates in a dictionary such as example below, but with extended support for mixed type content (seq/mapping/scalars):

d = collections.defaultdict(set)
[d[k].add(v) for k, v in s]

Here's my solution:

import copy
import collections

def faithfulrepr(ds):
    """Returns a plain-text representation of a mixed seq/mapping/scalar
    type data structure.

    The datastructure is recursively ordered (ordereddict) then a
    dataset representation is returned.

    Args:

        ds  Dataset (mixed seq/mapping/scalar data structure)

    Returns:

        Sorted plain-text representation of the input dataset.
    """
    ds = copy.deepcopy(ds)
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict()
        for k, v in sorted(ds.items()):
            res[k] = faithfulrepr(v)
        return repr(res)
    if isinstance(ds, list):
        for i, v in enumerate(ds):
            ds[i] = faithfulrepr(v)
        return repr(ds)
    return repr(ds)

def tupelize_dict(ds):
    """Group identical values of a dictionary under the same key. The keys
    become a tuple of all the duplicate keys.

    Args:

        ds: Input dictionary

    Example::

        ds = {23: 'foo',
              25: 'bar',
              28: 'foo',
              30: 'bar',
              33: 'foo'}

        >>>tupelize_dict(ds)
        {
            (23,28,33): 'foo',
            (25,30): 'bar'
        }
    """
    taxonomy = {}
    binder = collections.defaultdict(list)
    for key, value in ds.items():
        signature = faithfulrepr(value)
        taxonomy[signature] = value
        binder[signature].append(key)
    return {tuple(keys): taxonomy[s] for s, keys in binder.items()}

I am open for any better name for tupelize_dict :)

Your code reads well, and has good documentation. It is pretty pleasant to read.

You could just simplify a bit faithfulrepr by using generator expression and removing the need for the deepcopy:

def faithfulrepr(ds):
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict(
            (k, faithfulrepr(v)) for k, v in sorted(ds.items())
        )
    elif isinstance(ds, list):
        res = [faithfulrepr(v) for v in ds]
    else:
        res = ds
    return repr(res)

However this method will fail when fed dictionaries that have variable types as their keys (like {1: 'one', 'two': 2}).

An other take on the problem would involve more computations but can compare elements with the equality operator (which seems to be what you are really interested on). It involves maintaining two lists, one for the list of keys and one for the values, and searching in the list of values if the current one already exist. This is done using index which, unfortunately, is \$O(n)\$ but compares using __eq__:

def tupelize_dict(ds):
    keys, values = [], []
    for key, value in ds.items():
        try:
            index = values.index(value)
        except ValueError:
            values.append(value)
            keys.append([key])
        else:
            keys[index].append(key)
    return dict(zip(map(tuple, keys), values))
    # or the more readable return {tuple(k): v for k, v in zip(keys, values)}


Looking for all numbers where each digit is bigger than the previous digit This is the "Increasing Number problem", where we are looking for all numbers with \$n\$ digits where each digit is bigger than the digit before it. Or in Mathematical therms where:

$$\mathit{IncreasingNumber} = c_n \times 10^n + c_{n-1} \times 10^{n-1} + \cdots + c_1 * 10 + c_0$$

and \$c_i < c_{i-1}\$.

Examples: 123456789 or 123 or 569 or 139 or 45 or 12379. Goal: Give out all numbers that fullfill these properties depending on the number of digits \$n\$. This is my brute force code:

Sub AllIncreasingNumbers(N As Integer)
Dim Number As Long
Dim i As Long
Dim j As Integer
Dim lastdig As Integer
Dim remainder As Long
Dim thisdig As Integer

For i = (1 * 10 ^ (N - 1)) To 10 ^ (N)
    remainder = i
    lastdig = 0
    For j = (N - 1) To 0 Step -1
        thisdig = (remainder \ (10 ^ j))
        If Not (lastdig < thisdig) Then
        GoTo NotPass
        End If
        lastdig = thisdig
        remainder = remainder Mod (10 ^ j)
    Next j
    Debug.Print i
NotPass:
Next i
End Sub

If you haven't guessed it, it functions as following: go through all Numbers with N digits and check if they are increasing Numbers, if yes print them.

For \$n\$ = 2 to 6 it is reasonably fast but for \$n\$ = 8 or 9 it is really slow despite \$n=9\$ only having one solution 123456789. I think there could be a recursive algorithm to solve this but I can't figure it out. I used VBA because thats the language I am most familiar with but actually I am more intrested in the recursive algorithm to solve this. As soon as I have the algorithm I am able to implement it.

Instead of searching all numbers and checking them one by one, why not construct the numbers from the rule. In other words, start with the smallest digit being 1, then the next digit being 2 and so on. The digits can then be increased right to left as long as the rule holds.

For example, finding all 8 digit numbers:

Start with each digit increasing by 1 left to right:

12345678

Add one to the final digit:

12345679

Run out of digits so increase the digit to the left:

12345689
12345789
12346789
...
23456789

EDIT for further explanation:

For smaller numbers, you then need to repeat this process recursively. For example:

123 -> 124 -> 125 ... 129

You would now need to "reset" the second digit and any following it to one above what it was:

129 -> 134 -> 135 -> 136 ... 139
139 -> 145 -> 146 -> 147 ... 149
149 -> 156 -> 157 -> 158 -> 159

And so on.

You are still effectively working backwards through the digits, recursively increasing them right to left.

Hope that helps.


Map-reduce implementation for splitting strings I have been changing this code and I don't get to make it much better. I changed a little bit the structure, reimplemeted a new function for splitting Strings which is more efficient, etc. I have been tested with MR-Unit (it's part of map-reduce code).

I'm testing the code with 1.5 millions calls. It takes about 35 seconds on my computer, but in the real environment, it could be called with much more data, so, any optimization could be great. I'm worry about a little part of the code which I call around 7 times each iteration.

The parameters of my function are a map with the values what I want to replace, and another string which is a expression. It could be something like hard-code (I won't have to do any processing) or a expression like ${0} or something more complex like ${0}_${3}.

My idea now, since it's map-reduce code, is to do some of this code out of the mapper, and it should execute just once. The code could be more complex but I would only have once for the matchers and the split. I don't know if that could improve the performance.

private static final Pattern PATTERN = Pattern
            .compile("\\$\\{.+?\\}");
private static final Pattern PATTERN_DOLLAR = Pattern
            .compile("^.*\\$.*$");

public static String replaceVariables(final String expression,
            final Map<String, String> vars) {
        String tmpExp = expression;
        Matcher matcher = PATTERN.matcher(tmpExp);

        while (matcher.find()) {
            final String group = matcher.group();
            //${4} --> 4, ${2,8} --> 2,8
            final String prop = group.substring(2, group.length() - 1);
            // If the property has a comma, special case.
            final String[] props = split(prop, ',');

            //I get the value from the Map
            String sValue = vars.get(props[0]);
            if (sValue != null) {
                //Special case, I could write ${0,3}, field 0, only the first 3 characters.
                if (props.length > 1) {
                    final int cut = Integer.parseInt(props[1]);
                    if (sValue.length() > cut) {
                        sValue = sValue.substring(0, cut);
                    }
                }
                Matcher matcherDollar = PATTERN_DOLLAR.matcher(sValue);
                if (matcherDollar.matches()) {
                    tmpExp =
                            matcher.replaceFirst(sValue.replace("$", "\\$"));
                } else {
                    tmpExp = matcher.replaceFirst(sValue);
                }
            } else {
                tmpExp = matcher.replaceFirst("");
            }
            matcher = VAR_PATTERN.matcher(tmpExp);
        }
        return tmpExp;
    }

The split function:

public static String[] split(final String s, final char delimeter) {
        int count = 1;
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) == delimeter)
                count++;

        String[] array = new String[count];
        int a = -1;
        int b = 0;

        for (int i = 0; i < count; i++) {
            while (b < s.length() && s.charAt(b) != delimeter)
                b++;

            array[i] = s.substring(a + 1, b);
            a = b;
            b++;
        }
        return array;
    }

The possible input it could be:

Expression:

  Hi {0,2}

Map:

  0=test, 1=test1, 2=test2, ...

Usually, the expressions are pretty simple; just a hardcode of one or two variable expressions (e.g. {0,1}_{2} or even simpler). Although it's possible to find more complex expressions, it's not so common.

What about the following code. I've improved it by not using regular expressions (except one call of String.split, perhaps you already improved this by your own function split).

private final static char EXPR_VAR = '$';
private final static char EXPR_START = '{';
private final static char EXPR_END = '}';
private final static char EXPR_SPLIT = ',';

public static String replaceVariables(final String expression, final Map<String, String> vars) {
    if (expression == null) {
        throw new IllegalArgumentException("The expression may not be null!");
    }

    if (vars == null) {
        throw new IllegalArgumentException("The vars map may not be null!");
    }

    int firstIndex = expression.indexOf(EXPR_VAR);

    if (firstIndex == -1) {
        // nothing to replace, just return the expression
        return expression;
    }

    final StringBuffer sb = new StringBuffer();
    String tmpExp = expression;
    int lastIndex;
    String group;
    String parts[];

    while (firstIndex != -1) {
        // check if char after '$' is '{'
        if (tmpExp.charAt(firstIndex + 1) != EXPR_START) {
            continue;
        }

        // find ending sign '}'
        lastIndex = tmpExp.indexOf(EXPR_END, firstIndex);

        if (lastIndex > -1) {
            // complete pattern "${...}" found, append previous chars
            sb.append(tmpExp.substring(0, firstIndex));

            // get value inside pattern
            group = tmpExp.substring(firstIndex + 2, lastIndex);

            if (group.indexOf(EXPR_SPLIT) > -1) {
                // we have a pattern like "${xxxxx,xxxxxx}"
                parts = split(group, EXPR_SPLIT);

                if (vars.containsKey(parts[0])) {
                    sb.append(vars.get(parts[0]).substring(0, Integer.valueOf(parts[1])));
                } else {
                    throw new IllegalArgumentException("Key [" + parts[0] + "] not found in variable map!");
                }
            } else {
                // we have a pattern like "${xxxxx}"
                if (vars.containsKey(group)) {
                    sb.append(vars.get(group));
                } else {
                    throw new IllegalArgumentException("Key [" + group + "] not found in variable map!");
                }
            }

            // cut off previous chars from expression
            tmpExp = tmpExp.substring(lastIndex + 1);
        } else {
            // assuming, that if no right parenthesis is found, there is nothing
            // more to replace in this expression. So just get out of here!
            return sb.append(tmpExp).toString();
        }

        // find next pattern
        firstIndex = tmpExp.indexOf(EXPR_VAR);
    }

    // append rest of expression and return it as String
    return sb.append(tmpExp).toString();
}

With the following example values:

final String expression = "Hello! This is a ${1} ${0,2} of foo bla.";
final Map<String, String> vars = new HashMap<>();
vars.put("0", "Foo");
vars.put("1", "funny");

I have a benchmark of (1 million replaces):

// Original (yours):  1872 ms
// Improved (mine):    500 ms

So it's a bit more than three times faster than your implementation.
And the more values like {1,3} are in the input expression, the faster it is in relation:

Input:

final String expression = "${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ";

Benchmark:

// Original:   17455 ms
// Improved:    2855 ms

So, here it is more than six times faster!

Probably, it can be much more improved. But I just wanted to show you a possible direction so far!


Converting "a(b(cd)e(fg))" into a tree This was actually asked in an interview. I have made it in the best possible way I could and would like to optimize it if there is any chance of doing it.

The input is:

a(b(cd)e(fg))

The output should be:

                            a
                           / \
                          b   e
                         / \ / \
                        c  d f  g

My current code is:

#include<stdio.h>
#include<malloc.h>
#include<string.h>

struct node
{
    char x;
    struct node *left;
    struct node *right;
}*root;

char a[30];
int i=0,n;

void tre(struct node * p) //function that I am using to convert the string to a tree
{
        if(a[i]=='(')
        {
            i++;
            struct node *temp=malloc(sizeof(struct node));
            temp->x=a[i];
            temp->left=temp->right=NULL;
            i++;
            if(p->left==NULL)
            {
                p->left=temp;
                tre(p->left);
            }
            if(a[i]!='('&&a[i]!=')')
            {
                struct node *tempp=malloc(sizeof(struct node));
                tempp->x=a[i];
                i++;
                p->right=tempp;
                tre(p->right);
            }
        }
        else
        if(a[i]==')')
        {
            i++;
        }

}

void inorder(struct node *p)//inorder traversal of the tree made
{
    if(p!=NULL)
    {
        inorder(p->left);
        printf("%c ",p->x);
        inorder(p->right);
    }
}

main()
{
    printf("Enter the string : ");
    scanf("%s",a);
    struct node *temp=malloc(sizeof(struct node));
    temp->x=a[i];
    temp->left=temp->right=NULL;
    i++;
    root=temp;
    tre(root);
    inorder(root);
}

void tre(struct node * p) //function that I am using to convert the string to a tree
{
        if(a[i]=='(')
        {

I recommend not using such short variable names

            i++;
            struct node *temp=malloc(sizeof(struct node));
            temp->x=a[i];
            temp->left=temp->right=NULL;

You basically repeat these three lines three times. If you instead do this at the beginning of tre you can avoid the duplication.

            i++;
            if(p->left==NULL)

Given the way your code is structured, won't p->left always be null? The value passed to tre is always a freshly created node

            {
                p->left=temp;
                tre(p->left);
            }
            if(a[i]!='('&&a[i]!=')')

Why do you need to check for this? Wouldn't this indicate an invalid input? If so, perhaps you should report the error somehow.

            {
                struct node *tempp=malloc(sizeof(struct node));
                tempp->x=a[i];
                i++;
                p->right=tempp;
                tre(p->right);
            }

        }
        else
        if(a[i]==')')
        {
            i++;
        }

Again, in what situation will this be called?

}

How I'd approach that function

stuct node * tre()
{
     struct node * node = malloc(sizeof(struct node));
     node->x = a[i++];
     if(a[i] == '(')
     {
          node->left = tre();
          node->right = tre();
          assert(a[i++] == ')');
     }
     else
     {
          node->left = node->right = NULL;
     }
     return node;
}

Unless I'm missing something, your example output and code do not match. So I'm not going to comment on that.