Triggering based on words or phrases entered in a text box I am working on a simple loop that when a user enters text into a textbox if certain words or phrases are entered, xyz is triggered. I have my code working as needed but am looking for way to improve / optimize it.

$("#input_test").on("keyup",function(){
    var common = false;

    var inputVal = $(this).val().toLowerCase().replace(/[^a-zA-Z ]/g, "");

    var triggerWords = ['hello there','world', 'hello world', 'how do I turn this on', 'general kenobi'];

        var common = triggerWords.some(function(v){
           return inputVal.indexOf(v) !== -1;
        });

        if(common){
            $('#showme').show(300);
        }else{
            $('#showme').hide(300);
        }

});

Working JSFiddle

Performance

  I have my code working as needed but am looking for way to improve / optimize it.

If you want to improve the performances there are a few things you can do.

Testing

The first thing is that you can run tests and see how code style and logic can effect performance. Javascript testing is a little tricky. You can not just run the functions. You need to make sure you are not being tricked by the optimiser

I have added a basic Javascript performance tester to the bottom to highlight the following points.

Slow iterators

The Array iteration functions such as Array.some are generally slower than writing a standard for, for of or while loop. The reason is because functions incur a lot of additional overhead each time they are call.  They need their own memory, special structures to hold the current scope, and closure values. All this is added to the JavaScript heap and called the function's "context".

On top of that the actual function Array.some has to do some checks to make sure that the arguments you pass are correct and can be used. This all adds to the time to run the function.

For of loops are faster

Using a for...of loop avoids all that overhead and for this example is about 60% faster (on Chrome)

var triggerWords = ['hello there','world', 'hello world', 'how do I turn this on', 'general kenobi'];
for(const  word of triggerWords ){
     if(inputVal.indexOf(word) {
         $("#showme).show(300);
         return;  // all done exit the key up event
     }
}
$("#showme).hide(300);

Native power!

But the problem is still the iteration. Using JavaScript to check each string in turn is never going to utilize a modern CPU's true power. But there is a way to have the search done using pure native code.

RegExp will do the test in a fraction of the time.

Building the regular expression from array of string is expensive, so you would not use this method if the search string (triggerWords) changes each test. But if the the search is the same each time, you can build the regExp at the start and you get around a 1000% performance boost.

// create at start;
var triggerWords = ['hello there','world', 'hello world', 'how do I turn this on', 'general kenobi'];
const reg = new RegExp(triggerWords.join("|"),"gi")

// inside the key event
if(reg.test(inputVal)){
    $("#showme).show(300);
} else {
    $("#showme).hide(300);
}

The cost of libraries

The easiest way to get a performance boost is to drop the libraries.

Without jQuery the code looks like.

const wordSearch = /hello there|world|hello world|how do I turn this on|general kenobi/gi;
inputTest.addEventListener("keyup", (event) => {
    if( wordSearch.test(inputTest.value.replace(/[^a-z ]/gi,"")) ) {
         showme.classList.remove('hide');
    }else {
         showme.classList.add('hide');
    }
 });

And add a hide class to the CSS.

 .hide { display : none; }

The next snippet shows it all put together, copied from your fiddle (a page needing well over 1Mbyte of javascript to run) to a total of less than 1000bytes for all the code, css, and markup

const wordSearch = /hello there|world|hello world|how do I turn this on|general kenobi/gi;
inputTest.addEventListener("keyup", (event) => {
    if( wordSearch.test(inputTest.value.replace(/[^a-z ]/gi,"")) ) {
         showme.classList.remove('hide');
    }else {
         showme.classList.add('hide');
    }
 });
#showme{
  padding-top:15px;
}
.muted{
 padding-top:15px;
 font-size:12px;
 color:#ccc;
}
.hide {
 display : none;
}

Enter a word or phrase to search:

Search: <input id ="inputTest"  type="text" placeholder="Word / Phrase">

Indexed words / phrases:

hello there

world

hello

hello world

how do I turn this on

general kenobi

Example performance comparisons.

The snipped tests the 3 search methods Array.some, for..of and regExp

It uses the worst case scenario and runs the tests many 1000's of times. The test order is random to stop the optimizer slewing one method over another, and the result of each search are socked up by a global variable to stop the optimizer from just removing the inner loops completely

Let the test run until the mean times start to stabilize then click the page to compare the performance results.

/*===========================================================================
  Set up test data.
  One big array with

  ===========================================================================*/
const rand = (max) => Math.random() * max | 0;
const innerLoopCount = 1000;
var c = "aabbaa";
var b = "skjht kjhlvuh svrtgkj abcdef ghijklmn opqrst uvwxyz1 234567890 ";
var a = [];
for(i = 0; i < 10; i ++){ a.push(b.substr(rand(b.length -10), rand(8) + 2)) };
var reg = new RegExp(a.join("|"),"gi");
document.addEventListener("click",() => stop = true )
var stop = false;

var soak = 0; // this is to prevent optimiser removing test code. It soaks up entropy generated by the functions :P
function testA(){
    var i = 0, found;
    const now = performance.now()
    while(i++ < innerLoopCount){
      var found = a.some(function(word) {
          return c.indexOf(word) > -1;
      })

      soak += found ? 1:0;
    }
    return performance.now() - now
}
function testB(){
    const now = performance.now()
    var i = 0, found;
    while(i++ < innerLoopCount){
      found = false;
      for(const word of a){
          if(c.indexOf(word) > -1) {
              found = true;
              break;
          }
      }
      soak += found ? 1:0;
    }
    return performance.now() - now;
}
function testC(){
    const now = performance.now()
    var i = 0, found;
    while(i++ < innerLoopCount){

      found = reg.test(c);
      //for(const word of a){
      //    if(c.indexOf(word) > -1) {
      //        found = true;
      //        break;
      //    }
     // }
      soak += found ? 1:0;
    }
    return performance.now() - now;
}

const tests = [
    { count : 0, time : 0, run : testA, status : statusElementA, name : " 'Array.some' : "},
    { count : 0, time : 0, run : testB, status : statusElementB, name : " 'for...of' : "},
    { count : 0, time : 0, run : testC, status : statusElementC, name : " 'regExp' : "},
];
function testing() {
    var testsCount = tests.length;

    for(var i = 0;i < 100; i ++){
        var selTest = tests[Math.random() * testsCount | 0];
        selTest.time += selTest.run();
        selTest.count += 1;
    }
    for(const test of tests){
        test.mean = test.time / test.count;
        test.status.textContent = `${test.name} mean ${test.mean.toFixed(3)}ms over ${test.count} cycles.`;
    }
    if(!stop){

        setTimeout(testing,100);
    }else{
      tests.sort((a,b) => a.mean - b.mean);
      const slowest = tests[tests.length -1].mean;
      var win = "  Fastest";
      let test;
      for(test of tests){
          test.status.textContent += (test.mean / slowest * 100).toFixed(1) + "%"
          if( win ) {
              test.status.innerHTML += win;
              test.status.className = "champ";
              win = undefined;
          }
      }
      test.status.innerHTML += "  Slowest"
      test.status.className = "lost";
    }
}
setTimeout(testing,100);
body {
    font-family : arial;
    font size : large;
    text-align : center;
}
h4 {
   font-size : small;
}
.winner {
   color : green;

}
.looser {
   color : red;
}
.champ {
   background : #CFC;
   font-weight : 700;

   transition: all 0.5s ease-out;
}
.lost {
   background : #FCC;
   transition: all 0.5s ease-out;
}

Javascript Array.some V for...of V regExp

Click on the page to stop testing.


Adding data from multiple Excel files to two lists I have 5 nested for loops below, to add rows of data from multiple files to one of two lists.  Is there a more pythonic way of doing this?  I've come across an iterator-generator method named iteritems() -- could this be used to make this code more pythonic?

# 5 nested loops

for root,dirs,files in os.walk(src):
   files = [ _ for _ in files if _.endswith('.xlsx') ]
   for file in files:
     wb = xlrd.open_workbook(os.path.join(root,file))
     worksheets = wb.sheet_names()
     for worksheet_name in worksheets:
         if worksheet_name.rfind('7600') != -1 :
            sheet = wb.sheet_by_name(worksheet_name)
            keys = [sheet.cell(3, col_index).value for col_index in xrange(sheet.ncols)]
            for row_index in xrange(4, sheet.nrows):
               d = {keys[col_index]: sheet.cell(row_index, col_index).value
                  for col_index in xrange(sheet.ncols)}
               if file.rfind('oam') != -1 :
                  list_7600EoX.append(d)
               else:
                   list_7600EoX_OAM.append(d)

Your problem is not with 5 (or more) loops. Your problem is that you mixing code of different nature: walking over filesystem and name matching, and processing of files into single chunk of code.

Separate it into different functions calling each other:

def process_worksheet(wb, worksheet_name):
    sheet = wb.sheet_by_name(worksheet_name)
    # ...

def process_xslx(path):
    wb = xlrd.open_workbook(path)
    worksheets = wb.sheet_names()
    for worksheet_name in worksheets:
        if worksheet_name.rfind('7600') != -1 :
            process_worksheet(wb, worksheet_name)

for root,dirs,files in os.walk(src):
    files = [ _ for _ in files if _.endswith('.xlsx') ]
    for file in files:
        process_xslx(os.path.join(root, file))

Another option is to use generators to hide some details on how iteration is performed. For example, instead of walking over filesystem, let generator yield workbooks:

def walk_xlsx(src):
    for root,dirs,files in os.walk(src):
        files = [ _ for _ in files if _.endswith('.xlsx') ]
        for file in files:
            wb = xlrd.open_workbook(os.path.join(root, file))
            yield wb

for wb in walk_xlsx(src):
    # filter() is also a generator which yields only
    # worksheet names that have '7600' in their names
    worksheets = filter(lambda wn: '7600' in wn, wb.sheet_names())
    for worksheet_name in worksheets:
        # ...


In-proc event dispatching through IoC container Here is the sender and handler interfaces:
public interface ISender
{
    Task SendAsync(object e);
}

public interface IHandler<in TEvent>
{
    Task HandleAsync(TEvent e);
}

So I register in IoC container a sender service implementation, which dispatches events to all the compatible IHandler<in T> implementations. I use Autofac with a contravariance source, but there could be something else:
[Service]
public class Sender : ISender
{
    public Sender(IServiceProvider provider) => Provider = provider;
    IServiceProvider Provider { get; }

    public async Task SendAsync(object e)
    {
        var eventType = e.GetType();
        var handlerType = typeof(IHandler<>).MakeGenericType(eventType);
        var handlerListType = typeof(IEnumerable<>).MakeGenericType(handlerType);
        var method = handlerType.GetMethod("HandleAsync", new[] { eventType });
        var handlers = ((IEnumerable)Provider.GetService(handlerListType)).OfType<object>();
        await Task.WhenAll(
            handlers.Select(h =>
                Task.Run(() => (Task)method.Invoke(h, new[] { e }))
                    .ContinueWith(_ => { })));
    }
}

I think the code would be more readable and easier to maintain if there was a method that handled the main calling of the other handlers.
Unless there is a reason for provider to be a property I would make it a readonly field instead.
public class Sender : ISender
{
    private readonly MethodInfo handlerMethodInfo;
    private readonly IServiceProvider provider;

    public Sender(IServiceProvider provider)
    {
        this.provider = provider;
        Func<Task, object> handlerMethod = HandleAsync<object>;
        handlerMethodInfo = handlerMethod.Method.GetGenericMethodDefinition();
    }

    private async Task HandleAsync<TEvent>(TEvent e)
    {
        var handlers = provider.GetService<IEnumerable<IHandler<TEvent>>>();
        await Task.WhenAll(handlers.Select(h => h.HandleAsync(e)));
    }

    public async Task SendAsync(object e)
    {
        // Call the HandleAsync method
        var eventType = e.GetType();
        var method = handlerMethodInfo.MakeGenericMethod(eventType);
        await (Task)method.Invoke(this, new object[] { e });
     }
}

In the constructor just getting a reference to the method needed to call and in a way that's type safe.  Then in the SendAsync we will use reflection to call the private method to call the other classes.  Now the reflection code is a lot smaller but the main logic is still in "normal" code in the HandleAsync method.
We could turn the SendAsync into ExpressionTrees to only require reflection once but they come with a high price.  Typically code would need to be called ~500 to make up the speed hit of compiling the expression vs reflection.


Quickly Evaluating MANY matlabFunctions This post builds on my post about quickly evaluating analytic Jacobian in Matlab.

The key difference is that I am now working with the Hessian and I have to evaluate close to 700 matlabFunctions (instead of one matlabFunction like I did for the Jacobian) each time the hessian is evaluated. So there is an opportunity to do things a little differently.

I have tried to do this two ways so far and I am thinking about implementing a third. I will go through each method with a toy example, but first some preprocessing to generate these matlabFunctions:

PreProcessing:

% This part of the code is calculated once, it is not the issue
dvs = 5;
X=sym('X',[dvs,1]);
num = dvs - 1; % number of constraints

% multiple functions
for k = 1:num
    f1(X(k+1),X(k)) = (X(k+1)^3 - X(k)^2*k^2);
    c(k) = f1;
end

gradc = jacobian(c,X).'; % .' performs transpose

parfor k = 1:num
    hessc{k} = jacobian(gradc(:,k),X);
end

parfor k = 1:num
    hess_name = strcat('hessian_',num2str(k));
    matlabFunction(hessc{k},'file',hess_name,'vars',X);
end

METHOD #1 : Evaluate functions in series

%% Now we use the functions to run an "optimization." Just for an example the "optimization" is just a for loop

fprintf('This is test A, where the functions are evaluated in series!\n');
tic
for q = 1:10

    x_dv = rand(dvs,1);   % these are the design variables
    lambda = rand(num,1); % these are the lagrange multipliers

    x_dv_cell = num2cell(x_dv); % for passing large design variables

    for k = 1:num
        hess_name = strcat('hessian_',num2str(k));
        function_handle = str2func(hess_name);
        H_temp(:,:,k) = lambda(k)*function_handle(x_dv_cell{:});
    end

    H = sum(H_temp,3);

end
fprintf('The time for test A was:\n')
toc

METHOD # 2: Evaluate functions in parallel

%% Try to run a parfor loop

fprintf('This is test B, where the functions are evaluated in parallel!\n');
tic
for q = 1:10

    x_dv = rand(dvs,1);   % these are the design variables
    lambda = rand(num,1); % these are the lagrange multipliers

    x_dv_cell = num2cell(x_dv); % for passing large design variables

    parfor k = 1:num
        hess_name = strcat('hessian_',num2str(k));
        function_handle = str2func(hess_name);
        H_temp(:,:,k) = lambda(k)*function_handle(x_dv_cell{:});
    end

    H = sum(H_temp,3);

end
fprintf('The time for test B was:\n')
toc

RESULTS:

METHOD #1 = 0.008691 seconds

METHOD #2 = 0.464786 seconds

DISCUSSION of RESULTS

This result makes sense because, the functions evaluate very quickly and running them in parallel waists a lot of time setting up and sending out the jobs to the different Matlabs ( and then getting the data back from them). I see the same result on my actual problem.

METHOD # 3: Evaluating the functions using the GPU

I have not tried this yet, but I am interested to see what the performance difference is. I am not yet familiar with doing this in Matlab and will add it once I am done.

Any other thoughts?

Having 700 functions, they all fit into your memory. No need to write files and use str2func. I would use anonymous functions instead.

Modified preprocessing.

% This part of the code is calculated once, it is not the issue
dvs = 5;
X=sym('X',[dvs,1]);
num = dvs - 1; % number of constraints

% multiple functions
for k = 1:num
    f1(X(k+1),X(k)) = (X(k+1)^3 - X(k)^2*k^2);
    c(k) = f1;
end

gradc = jacobian(c,X).'; % .' performs transpose

parfor k = 1:num
    hessc{k} = matlabFunction(jacobian(gradc(:,k),X),'vars',X);
end

And the simplified code using function handles:

%% Now we use the functions to run an "optimization." Just for an example the "optimization" is just a for loop

fprintf('This is test A, where the functions are evaluated in series!\n');
tic
for q = 1:10

    x_dv = rand(dvs,1);   % these are the design variables
    lambda = rand(num,1); % these are the lagrange multipliers

    x_dv_cell = num2cell(x_dv); % for passing large design variables

    for k = 1:num
        H_temp(:,:,k) = lambda(k)*hessc{k}(x_dv_cell{:});
    end

    H = sum(H_temp,3);

end
fprintf('The time for test A was:\n')
toc

On my system the code runs roughly 4 times faster.


Go version of Advent of Code, day 5 - Dealing with runes I tried to solve the Advent of Code quiz for day 5 in Go, since my brute force algorithm wasn't efficient in Ruby. I solved the first part of the quiz with the  following Go code.

package main

import (
        "crypto/md5"
        "encoding/hex"
        "fmt"
        "strings"
)

func main() {
        fmt.Println("Password:", extractPassword("abc"))
}

func extractPassword(roomId string) string {
        position := 0
        i := 0
        password := make([]rune, 8)

        for position < 8 {
                letter := evaluateIndex(roomId, i)
                if 0 != letter {
                        fmt.Printf("Found %c for index %d\n", letter, i)
                        password[position] = letter
                        position++
                }
                i++
        }
        return string(password)
}

func evaluateIndex(roomId string, index int) rune {
        text := fmt.Sprintf("%s%d", roomId, index)
        hash := md5Hash(text)
        if strings.HasPrefix(hash, "00000") {
                return []rune(hash)[5]
        } else {
                return 0
        }
}

func md5Hash(text string) string {
        hash := md5.Sum([]byte(text))
        return hex.EncodeToString(hash[:])
}

My biggest issue was the string vs rune conflict. I'm interested in following points.

Idiomatic Go style
Usage of the Go standard library
Performance improvments, while it's fast enough yet

Your code is pretty idiomatic. The only obvious style thing I'd change is the end of the evaluateIndex function:

if strings.HasPrefix(hash, "00000") {
        return []rune(hash)[5]
}
return 0

you could also write if letter := evaluateIndex(roomId, i); letter != 0 { but it's not that important.

Now, the rune/string/byte question is the interesting one. md5 deals with []byte only; and converting strings to bytes and back is expensive (new memory allocations each time). So I'd change your code to use []byte instead of string, and byte instead of rune. The evaluateIndex function becomes faster:

var prefix = []byte("00000")

func evaluateIndex(roomId []byte, index int) byte {
    bytes := append(roomId, []byte(fmt.Sprint(index))...)
    hash := md5Hash(bytes)
    if bytes.HasPrefix(hash, prefix) {
        return hash[5]
    }
    return 0
}

func md5Hash(bytes []byte) []byte {
    rawHash := md5.Sum(bytes)
    encHash := make([]byte, md5.EncodedLen(len(rawHash)))
    hex.Encode(encHash, rawHash)
    return encHash
}

I put zeroes outside the func, to avoid converting it over and over. You still have a few conversions & allocations, but there's no way around them. The other functions can be modified easily to accommodate the type change.


Dictionary lookup of non-nullable struct into nullable destination I've got an IDictionary<SomeT, DateTime> that does not always contain the desired key-value pair. For that reason, a target method expects a DateTime? that the default TryGetValue method cannot provide a value for directly, because of the added ?.

I've written this generic extension with main emphasis on the parameter out TValue? value.

public static bool TryGetValue<TKey, TValue>(
    this IDictionary<TKey, TValue> that,
    TKey key,
    out TValue? value) where TValue : struct
{
    TValue output;
    if (that.TryGetValue(key, out output))
    {
        value = output;
        return true;
    }
    else
    {
        value = null;
        return false;
    }
}

Example use:

DateTime? nearestDateUtc; // The standard TryGetValue would not allow '?' here.
if (!nearestDatesUtc.TryGetValue(company, out nearestDateUtc)) { ... }

Based on this, my question is then; is there a more idiomatic way to extract (non-null) structs into nullable destinations than the solution I implemented? And if not, is the name TryGetValue confusing? C# developers might expect something very specific about exactly this name. In that case, what would a better name be?

An error could easily occur as the overload comes down to the presence of a single question-mark in a variable's type declaration and would mean the difference between null and default(DateTime).

General

I think I would question the value of this extension method. You've already got the same information from the existing TryGetValue method:

Could the key be found?
What is the value?

If at all possible, I'd recommend trying to modify the calling code not to need this extension:

DateTime triedNearestDateUtc;
var nearestDateUtc = nearestDatesUtc.TryGetValue(company, out triedNearestDateUtc)
    ? (DateTime?)triedNearestDateUtc
    : null;

or even do away with the nullable entirely:

DateTime triedNearestDateUtc;
if (nearestDatesUtc.TryGetValue(company, out triedNearestDateUtc))
{
    // Do something with value
}
else
{
    // Do something without value
}

If there are multiple possible sources for your value (which your if (!nearestDatesUtc.TryGetValue(...)) suggests), try:

DateTime nearestDateUtc;
var foundNearestDateUtc = nearestDatesUtc.TryGetValue(company, out nearestDateUtc);

if (!foundNearestDateUtc)
{
    foundNearestDateUtc = otherDatesUtc.TryGetValue(company, out nearestDateUtc);
}

if (!foundNearestDateUtc)
{
    nearestDateUtc = DateTime.Now;
}

Or break that part into its own method:

private DateTime FindNearestDateUtc(string company)
{
    DateTime nearestDateUtc;

    if (nearestDatesUtc.TryGetValue(company, out nearestDateUtc))
    {
        return nearestDateUtc;
    }

    if (otherDatesUtc.TryGetValue(company, out nearestDateUtc))
    {
        return nearestDateUtc;
    }

    return DateTime.Now;
}

But this is all a bit speculative on what you're using it for. Onto the bits you've actually put in your question:

DateTime

The DateTime type is a tricky customer - it tries to be all things to all people. I understand if it'd be a lot of effort and upheaval to move away from this type now, but I'd strongly recommend NodaTime as an alternative - it forces you to think clearly about exactly what kind of date and time structures you mean, and helps to prevent subtle bugs down the line.

Some interesting reading (if you find this sort of thing interesting) on the subject: Jon Skeet on DateTime

Signature

The main reason for having the bool return value as well as the out parameter is that default(DateTime) could be a valid return value. With a signature like DateTime TryGetValue(string key), you have no way of knowing whether 0001-01-01T00:00:00 was the value or the default "I don't have a value" value.

In your case, you seem to be using a null DateTime? to indicate "I don't have a value" and a "real" DateTime? to indicate the result. There's no ambiguity here, so there's no reason you can't just return the value on its own.

This also has a nice side effect of making the body of the method a bit shorter and simpler:

    TValue result;
    if (that.TryGetValue(key, out result))
    {
        return result;
    }
    else
    {
        return null;
    }

or

    TValue result;
    return that.TryGetValue(key, out result) ? (TValue?)result : null;

Naming

I'd probably give the method a rename because it behaves differently from the normal TryGetValue: Try... methods conventionally have a bool return and an out result parameter.
that isn't a good name for a variable - it doesn't tell you anything about what it is or does.

public static TValue? GetValueOrNull<TKey, TValue>(
    this IDictionary<TKey, TValue> dictionary,
    TKey key) where TValue : struct
{
    ...
}

Result

I'd go with the ternary operator over the if ... else version and end up with:

public static TValue? GetValueOrNull<TKey, TValue>(
    this IDictionary<TKey, TValue> dictionary,
    TKey key) where TValue : struct
{
    TValue result;
    return dictionary.TryGetValue(key, out result) ? (TValue?)result : null;
}


"Log in", extract number from a map, increment it, and log out Basically, you just run main and it allows the client to "log in", and extract their number from a map, increment their own number, and log out.

It all compiles and works fine, but how can I decouple this code, and make it more composable?  I'm finding it's difficult to separate concerns, ex between the logic, and the IO + State effects.

What would be a better, more idiomatic way to right this, which would allow me to add features, such as a password, or decrement option?

Possible Actions: login <ENTER> name, inc, get, logout

{-# LANGUAGE FlexibleContexts #-}

import System.IO
import Data.Map
import Control.Monad.State

import Control.Lens.Tuple
import Control.Lens.Setter
import Control.Lens.Getter

import Prelude hiding (lookup) -- Data.Map has one I want

-- Features:
--   User can login, see their number, increment it ad lib, and log out
--
--   login
--     new username --> new map entry
--     old username --> display map entry
--   inc - increment current user's entry in map
--   logout - empties the current username
--   stop - close IO
--   bad input - just ask for another action

type DB       = Map String Int
type Username = String
type AppState = (Username, DB)

db = fromList [("a", 0),
               ("b", 99),
               ("c", 152)] :: DB

-- increment a key in a map
incDB ::  String -> DB -> DB
incDB k = (update (\x -> Just (x + 1)) k)
-- λ> inc "a" $ inc "a" $ inc "a" db

-- increment current user in a State Monad
--  (Num a, Ord k, MonadState (k, (Map k a)) m) => m x
incUser :: (MonadState AppState m) => m ()
incUser = do user <- gets $ view _1
             modify $ over _2 (incDB user)
-- λ> runState incUser ("b", db)

-- 1. update logged-in user name, 2. add new entry to db if it's a new user
login :: (MonadState AppState m) => String -> m ()
login newuser = do modify $ set _1 newuser
                   modify $ over _2 $ insertWithKey (\k new old -> old) newuser 0 -- inserts new user if necessary
-- λ> runState (login "d") ("", db)
--    ((),("d",fromList [("a",0),("b",99),("c",152),("d",0)]))

-- get the number of the currently-logged-in user
getNum ::(MonadState AppState m) => m (Maybe Int)
getNum = do user <- gets $ view _1
            db <- gets $ view _2
            return $ lookup user db
-- λ> runState (do login "b"; incState; getNum) ("", db)
--    (Just 100,("b",fromList [("a",0),("b",100),("c",152)]))

-- remove the currently logged-in user from the appstate (not the db though, of course)
logout :: (MonadState AppState m) => m ()
logout = modify $ set _1 ""
-- λ> runState (do login "b"; getNum; logout ) ("", db)
--    ((),("",fromList [("a",0),("b",99),("c",152)]))
-- λ> runState (do login "b"; incUser; incUser; logout ) ("", db)
--    ((),("",fromList [("a",0),("b",101),("c",152)]))

run :: StateT AppState IO ()
run = do liftIO $ putStr "next action: "
         liftIO $ hFlush stdout
         action <- liftIO $ getLine
         case action of
           "inc"    -> do incUser
           "login"  -> do liftIO $ putStr "enter username:"
                          user <- liftIO $ getLine
                          login user
           "get"    -> do n <- getNum
                          liftIO $ putStr $ "current num: " ++ (show n) ++ "\n"
                          -- liftIO $ hFlush stdout

           "logout" -> logout
           otherwise -> return ()
         if action == "stop"
         then
             return ()
         else
             run

main = do execStateT run ("", db)

I would inline, eta-reduce and use more library functions to make the code short enough that adding another command is trivial. Perhaps give the fields names so adding another can't mess up numbering, and you need less comments because the code describes itself.

Edit: I'll use non, making the map not add a value for new users until they want to change it. This way we don't need to initialize with db . at user %= (<|> Just 0) on logging in, and we can get rid of the Just returned by the "get" action without needing to promise we already initialized. (Which we don't necessarily have, as the initial ""!)

{#- LANGUAGE TemplateHaskell, LambdaCase -#}
import Control.Lens -- batteries included
import Control.Monad.Trans.Maybe
import Control.Applicative -- (<$>), (<*>), empty, (<|>)
import qualified Data.Map as M -- Data.Map's name collisions with prelude are customarily handled by qualification

data AppState = AppState
  { _appStateUsername :: String
  , _appStateDb :: M.Map String Int
  }

makeFields ''AppState

-- Here's one we can actually outline, because it's used more than once, and it allows us to pull out the liftIO, and it shows us that we forgot the hFlush and the trailing ' ' one of the times.
prompt :: MonadIO m => String -> m String
prompt s = liftIO $ do
  putStr $ s ++ ": "
  hFlush stdout
  getLine

main = runMaybeT $ (`execStateT` AppState "" M.empty) $ forever $ do
  prompt "next action" >>= \case
    "inc" -> do
      user <- use username
      db . at user . non 0 += 1
    "login" -> do
      user <- prompt "enter username"
      username .= user
    "get" -> do
      n <- M.findWithDefault 0 <$> use username <*> use db
      liftIO $ putStrLn $ "current num: " ++ show n -- Note that this includes the Maybe, even though at this point we're always just, unless we're still the initial "".
    "logout" -> do
      username .= "" -- Note that this makes for shenanigans if someone logs in as "".
    "stop" -> empty -- MaybeT helps us out with the control flow to get rid of the special case and recursion.
    _ -> liftIO $ putStrLn $ "usage: ehhh just look at the code mmkay"


Erlang pattern matching excersise I recently started my first project with Erlang. I've been skimming documentation and various books to get the information I need, and it's going well, but now that I have something that works I want to go "back to the basics" to fill in some holes in my knowledge, and more importantly, my style. So I took a look at some exercises in the book "Programming Erlang", and this one struck me as one I could implement and post here to get feedback on one topic I feel I'm implementing "sub-optimally" to say the least.:

-module(scratch).
-author("Oak").

%% API
-export([new/0,destroy/1,write/3,read/2,match/2]).

new()-> {db,[]}.

destroy({db,_Data})->{db,[]}.

write(Key,Element,{db,Data}) -> {db,[{Key,Element}|Data]}.

read(_Key,{db,[]})-> error(no_instance);
read(Key,{db,[{CurKey,CurValue}|_Data]}) when Key =:= CurKey-> CurValue;
read(Key,{db,[{_CurKey,_CurValue}|Data]}) -> read(Key,{db,Data}).

match(_Element,{db,[]})->[];
match(Element,{db,[{CurKey,CurValue}|Data]}) when Element =:= CurValue -> [CurKey | match(Element,{db,Data})];
match(Element,{db,[{_CurKey,_CurValue}|Data]}) -> match(Element,{db,Data}).

I'd like to know if the pattern matching I'm using is in line with the style that's expected when coding in Erlang. I could think of multiple ways of doing this, but this is what comes "naturally" to me right now, I'm not sure how elegant it is. I'm looking for tips about style more than the actual "algorithm", but if there are any glaring mistakes feel free to point them out.

I see one possible mistake in your code: you do not check if a key already exists before writting a new {Key,Value} pair. This may be intentional, but in this case I think that the read(Key,Db) should return a list of value rather than a single value.

Looking at pattern matching I think that you can simplify the code like this:

read(_Key,{db,[]})-> {error,no_instance};
read(Key,{db,[{Key,CurValue}|_Data]}) -> {ok,CurValue};
% the pattern maching can be done directly, no need to use when.
% I propose to return a tuple {ok,Value} to be consistent with the previous case
% so it will be possible to use pattern matching when using the result of read/2,
% even if the value returned is {error,no_instance}!
read(Key,{db,[_Pair|Data]}) -> read(Key,{db,Data}).
% don't need to create 2 variables

match(Element,Db) -> match(Element,Db,[]).
% transform the function to be tail recursive

match(_Element,{db,[]},R)->R;
match(Element,{db,[{CurKey,Element}|Data],R}) -> match(Element,{db,Data},[CurKey|R]);
% the pattern maching can be done directly, no need to use when.
match(Element,{db,[_Pair|Data]},R) -> match(Element,{db,Data},R).
% don't need to create 2 variables


Project Euler #17: Number Letter Counts If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Here's my implementation in Python:
def number_to_word(n):
    """Assumes is an integer from 1 - 1000.
    Returns number in words ex: 122 --> one hundred and twenty-two."""
    # num_to_alpha contains the unique values for numbers that will be returned according to repetitive patterns
    num_to_alpha =\
        {1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten',
         11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen',
         18: 'eighteen', 19: 'nineteen', 20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty',
         70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'one hundred', 1000: 'one thousand'}
    # Numbers below 21 , 100, 1000 are unique words (cannot be formed using a repetitive rule)
    if 0 < n < 21 or n == 100 or n == 1000:
        return num_to_alpha[n]
    mod = n % 10
    # Numbers in range (21 - 99) have a single rule except the multiples of 10 (formed by a single word)
    if 20 < n < 100:
        if n % 10 != 0:
            return f'{num_to_alpha[n // 10 * 10]}-{num_to_alpha[mod]}'
        return num_to_alpha[n]
    # Numbers above 100 have a single rule except the following:
    if 100 < n < 1000:
        # a) multiples of 100
        if n % 100 == 0:
            return f'{num_to_alpha[n // 100]} hundred'
        # b) numbers whose last 2 digits are above 20 and are also multiples of 10
        if not n % 100 == 0 and n % 100 > 20 and n % 10 == 0:
            return f'{num_to_alpha[n // 100]} hundred and {num_to_alpha[n % 100]}'
        # c) numbers whose last 2 digits are below 20 and not multiples of 10
        if n % 100 < 21:
            second_part = num_to_alpha[n % 100]
            return f'{num_to_alpha[n // 100]} hundred and {second_part}'
        # d) numbers whose last 2 digits are above 20 and not multiples of 10
        if n % 100 > 20:
            return f'{num_to_alpha[n // 100]} hundred and {num_to_alpha[((n % 100) // 10) * 10]}-' \
                f'{num_to_alpha[(n % 100) % 10]}'
    # To prevent counting False values
    if n <= 0 or n > 1000:
        return ''

def count():
    """Cleans numbers from spaces and hyphens and returns count."""
    all_numbers = [number_to_word(x) for x in range(1, 1001)]
    numbers_without_spaces = [number.replace(' ', '') for number in all_numbers]
    clean_numbers = [number.replace('-', '') for number in numbers_without_spaces]
    total = 0
    for clean_number in clean_numbers:
        total += len(clean_number)
    return total

if __name__ == '__main__':
    print(count())

num_to_alpha =\ is not Pythonic.  If a statement is “incomplete”, there is no need to add a trailing \ to indicate the line is continued.  An “incomplete” statement is one which contains unclosed {, [, or (, so this line could be written without the trailing \ simply by moving the { up to the previous line:

num_to_alpha = {
    1: 'one', ...

The if 0 < n < 21 or n == 100 or n == 1000: test could be written more simply as if n in num_to_alpha:.  This would also handle many other simple cases where the number exists in the num_to_alpha dictionary.

You compute mod = n % 10, and then go on to test if n % 10 != 0:.  You could simply test the already computed value if mod != 0:, or since non-zero values are Truthy, if mod:.

You are testing for values which cannot possibly be true due to early tests.  For instance, once a number is above 100, you test:

if n % 100 == 0:
    return ...

This is followed by:

if not n % 100 == 0 and ...:

If n % 100 evaluated to True, the first return statement would have been executed.  Testing not n % 100 == 0 doesn’t add any value.

At the end of the function, you explicitly check if n <= 0 or n > 1000: and return the empty string.  And if THAT test fails ... what happens?  None will be returned?  If the number passed any of the above tests, and explicit return statement would have already returned the desired string, so if the end of the function is reached, does it matter what the return value is?  Could you not unconditionally return ''.  Or better: raise ValueError()

DRY: Don’t Repeat Yourself

You code is repeating the same tests.  Is the number between 1 and 20?  Are the last 2 digits of a 3 digit number between 1 and 20?

If you structured your function in the following manner, you’d repeat yourself less, and find it easy to extend into ten thousands, hundred thousands, millions and beyond:

Start with an empty string
If n >= 1000

add num_to_alpha[n // 1000] and “thousand” to the string,
n = n % 1000

If n >= 100

add num_to_alpha[n // 100] and “hundred” to the string,
n = n % 100

If n > 0 and the string is not empty,

add “and” to the string

If n > 20,

add num_to_alpha[n // 10 * 10] to the string
n = n % 10

If n > 0

add num_to_alpha[n] to the string

Return the resulting string

Since you aren’t really using the returned strings, but eventually just counting the number of letters in the resulting string, you could optimize the function to not use strings at all.  Just store the number of letters of each number in the dictionary:

num_to_length = {
    1: 3, 2: 3, 3: 5, 4: 4, ...
}

and add 8, 7, and 3 instead of the strings “thousand”, “hundred” & “and”.


Powershell for syncing Minecraft save files My code in full plus the task scheduler definition: https://gist.github.com/DaneWeber/0c5e7978bd3927734173e3afdc3d6338

This is my first non-trivial PowerShell script. This was a pretty major learning experience. I only went down this path once I discovered that xcopy wouldn't be sufficient.

My Ask: What do I not know that I don't know? That is, what about this strikes you as weird, clunky, or "not the PowerShell way"?

Problem I am solving: I want Minecraft worlds sync'ed across two (or more) computers. It doesn't seem like I should have to pay for an additional service to accomplish this.

Other solutions attempted:

Symlink/Junction of the Minecraft minecraftWorlds folder with one in OneDrive. Minecraft seemed to be unable/unwilling to see the data.
xcopy /d to update files. The problem is that Minecraft renames the files every save, so each save results in another large file, growing out of control.

Solution approach:

If any world exists in one location (local or cloud) but not the other: copy it.
If one location's world contains a file newer than all other files in the other location, replace the entire world with the newer one. (You have to be careful not to consider folders, since they have a modified date of their creation, even when you copy a folder.)
In case the script runs while the cloud service is still downloading data, copy files from the cloud if there are ones missing locally.

The script:

$minecraftSaveFolder = "minecraftWorlds"
$minecraftLocalPath = $env:LOCALAPPDATA + "\Packages\Microsoft.MinecraftUWP_8wekyb3d8bbwe\LocalState\games\com.mojang"
$minecraftLocalSave = $minecraftLocalPath + "\" + $minecraftSaveFolder
$minecraftCloudSave = $PSScriptRoot + "\MinecraftBackup"

$cloudWorlds = Get-ChildItem $minecraftCloudSave
$localWorlds = Get-ChildItem $minecraftLocalSave

$saves = Compare-Object $cloudWorlds $localWorlds -IncludeEqual

switch ($saves) {
  ( {$PSItem.SideIndicator -eq "<="}) {
    Write-Output "Copying from cloud: $($PSItem.InputObject.Name)"
    Copy-Item -Path $PSItem.InputObject.FullName -Destination $minecraftLocalSave -Container -Recurse
  }
  ( {$PSItem.SideIndicator -eq "=>"}) {
    Write-Output "Copying to cloud: $($PSItem.InputObject.Name)"
    Copy-Item -Path $PSItem.InputObject.FullName -Destination $minecraftCloudSave -Container -Recurse
  }
  ( {$PSItem.SideIndicator -eq "=="}) {
    $cloudLatest = (( Get-ChildItem ( $minecraftCloudSave + "\" + $PSItem.InputObject) -Recurse -File ).LastWriteTime | Measure-Object -Maximum)
    $localLatest = (( Get-ChildItem ( $minecraftLocalSave + "\" + $PSItem.InputObject) -Recurse -File ).LastWriteTime | Measure-Object -Maximum)
    if ($cloudLatest.Maximum -eq $localLatest.Maximum) {
      if ($cloudLatest.Count -gt $localLatest.Count) {
        Write-Output "Adding files from cloud: $($PSItem.InputObject.Name)"
        xcopy ($minecraftCloudSave + "\" + $PSItem.InputObject) $minecraftLocalSave /d /e /c /i /h /y
      }
      else {
        Write-Output "Already synchronized: $($PSItem.InputObject.Name)"
      }
    }
    elseif ($cloudLatest.Maximum -gt $localLatest.Maximum) {
      $world = $PSItem.InputObject.Name
      Write-Output "Over-writing local with $world"
      $old = Rename-Item -Path "$minecraftLocalSave\$world" -NewName ($world + "_old") -PassThru
      Copy-Item -Path "$minecraftCloudSave\$world" -Destination $minecraftLocalSave -Container -Recurse
      Remove-Item -Recurse -Force -Path $old
    }
    elseif ($cloudLatest.Maximum -lt $localLatest.Maximum) {
      $world = $PSItem.InputObject.Name
      Write-Output "Updating cloud with $world"
      $old = Rename-Item -Path "$minecraftCloudSave\$world" -NewName ($world + "_old") -PassThru
      Copy-Item -Path "$minecraftLocalSave\$world" -Destination $minecraftCloudSave -Container -Recurse
      Remove-Item -Recurse -Force -Path $old
    }
    else {
      Write-Error "Something went wrong with the folder comparison."
    }
  }
}

Looks fine for me. As a note - instead of using Write-Output for display purposes use Write-Host cmdlet.

In a nutshell, Write-Host writes to the console itself. Think of it as a MsgBox in VBScript. Write-Output, on the other hand, writes to the pipeline, so the next command can accept it as its input. You are not required to use Write-Output in order to write objects, as Write-Output is implicitly called for you.


stdin getline wrapper I'd like to read a line from stdin, excluding the newline character. I've written the function:
/* read in a line from stdin, NULL on failure
 * does not include trailing newline
 */
char*
readStdinLine() {
        char* buffer;
        size_t bufsize = 32;
        size_t characters;

        buffer = (char *) malloc(bufsize * sizeof(char));
        if (buffer == NULL)
                return NULL;

        characters = getline(&buffer, &bufsize, stdin);
        buffer[--characters] = '\0';

        char* text = (char *) malloc(characters);
        for (int i = 0; i < characters + 1; i++) {
                text[i] = buffer[i];
        }

        free(buffer);

        return text;
}

This seems inneficient, I'm essentially reading in the line twice, once in getline and once to remove the trailing newline. That doesn't seem like the most memory-efficient algorithm, and I would like to remove the newline without copying, if that is at all possible.
I'm very new to C (have used C++, Java, etc, but never a systems language without objects) so I would appreciate learning all the code style things I've done wrong as well. Thanks!

This function can be written like this:
char* readStdinLine()
{
        char*  buffer  = NULL;
        size_t bufsize = 0;
        ssize_t characters = getline(&buffer, &bufsize, stdin);
        if (characters == -1) {
            free(buffer);
            buffer = NULL;
        }
        else if (buffer[characters-1] == '\n') {
            buffer[characters-1] = '\0';
        }
        return buffer;
}

The getline() function does everything you need. You simply need to check for errors and remove the new line character)


Nesting BsonDocuments in MongoDB queries I have a MongoDB collection setup where each document's JSON looks like this:

{
    "_id" : "Stuff",
    "project_id" : "1234",
    "VehicleEntry" : [
        {
            // Irrelevant fields removed.
            "VehicleStatus" : "PASSED"
        },
        {
            // Irrelevant fields removed.
            "VehicleStatus" : "FAILED"
        }
    ]
}

I want to write a query that gives me the number of vehicles passed and failed for each project identifier. I have done so in this very long aggregation query:

var aggregate = collection.Aggregate()
    .Match(new BsonDocument
    {
        {
            "project_id", "1234"
        }
    })
    .Unwind(i => i["VehicleEntry"])
    .Group(new BsonDocument
    {
        {
            "_id", "$project_id"
        },
        {
            "passed", new BsonDocument
            {
                {
                    "$sum", new BsonDocument
                    {
                        {
                            "$cond", new BsonArray
                            {
                                new BsonDocument
                                {
                                    {
                                        "$eq", new BsonArray
                                        {
                                            "$VehicleEntry.VehicleStatus",
                                            "PASSED"
                                        }
                                    }
                                },
                                1,
                                0
                            }
                        }
                    }
                }
            }
        },
        {
            "failed", new BsonDocument
            {
                {
                    "$sum", new BsonDocument
                    {
                        {
                            "$cond", new BsonArray
                            {
                                new BsonDocument
                                {
                                    {
                                        "$eq", new BsonArray
                                        {
                                            "$VehicleEntry.VehicleStatus",
                                            "FAILED"
                                        }
                                    }
                                },
                                1,
                                0
                            }
                        }
                    }
                }
            }
        }
    });

While it works as expected, this seems very difficult to maintain and has even become unreadable. How can I improve the way this is written to be more maintainable?

If it's relevant to a better solution, I already have the Newtonsoft library in my project as I use it to convert Json to Bson.

EDIT I have been told I could serialize Bson to do this, but I am not familiar with the concept. What are some best practices for that and how can I convert this query to use serialized bson?

I found one way to simplify this which helps break up the number of rows required.

Following this StackOverflow question about converting a JSON string to Bson, I wrote part of my query as it would be in a console. I could only figure out how to do this for the match and group part:

var matchJSON = "{ project_id : '1234' }";
var groupJSON = "{ " +
    "_id : { project_id : '$project_id', date : '$VehicleEntry.@Date' }, " +
    "passed : { $sum : { $cond : [ { $eq : [ '$VehicleEntry.VehicleStatus', 'PASSED' ] }, 1, 0 ] } }, " +
    "failed : { $sum : { $cond : [ { $eq : [ '$VehicleEntry.VehicleStatus', 'FAILED' ] }, 1, 0 ] } } }";

Then I converted it to BsonDocuments:

var matchBson = MongoDB.Bson.Serialization.BsonSerializer.Deserialize<BsonDocument>(matchJSON);
var groupBson = MongoDB.Bson.Serialization.BsonSerializer.Deserialize<BsonDocument>(groupJSON);

and then ran my aggregate query just like it was previously:

var aggregate = collection.Aggregate()
    .Match(matchBson)
    .Unwind(i => i["VehicleEntry"])
    .Group(groupBson);


An explicit cast for narrowing numeric conversions Inspired by gsl::narrow_cast, I created my own implementation with the addition of a couple of features:

a static assert on the types to ensure the cast is actually narrowing (if future changes to the code mean the cast is no longer narrowing, we don't want to still have a narrow_cast there)
the version without a runtime check still has an assert, so it's checked in debug mode

#include <cassert>
#include <exception>
#include <iostream>
#include <type_traits>

namespace details {

template <typename T, typename U>
constexpr bool is_same_signedness = std::is_signed<T>::value == std::is_signed<U>::value;

template <typename T, typename U>
constexpr bool can_fully_represent =
    std::is_same<T, U>::value ||
    ( std::is_integral<T>::value && std::is_integral<U>::value &&
        ( ( std::is_signed<T>::value && sizeof(T) >  sizeof(U) ) ||
          ( is_same_signedness<T, U> && sizeof(T) >= sizeof(U) ) ) ) ||
    ( std::is_floating_point<T>::value && std::is_floating_point<U>::value && sizeof(T) >= sizeof(U) );

template <typename T, typename U>
constexpr bool static_cast_changes_value(U u) noexcept
{
    const auto t = static_cast<T>(u);

    // this should catch most cases, but may miss dodgy unsigned to signed conversion or vice-versa
    if (static_cast<U>(t) != u)
        return true;

    if (std::is_signed<T>::value != std::is_signed<U>::value && ((t < T{}) != (u < U{})))
        return true;

    return false;
}

} // namespace details

// TODO: unchecked cast for types where some loss of precision (and therefore assertion failure) is expected?
template <typename T, typename U>
constexpr T narrow_cast(U&& u) noexcept
{
    static_assert(!details::can_fully_represent<T, U>, "we shouldn't be using narrow_cast for casts that aren't actually narrowing");
    assert(!details::static_cast_changes_value<T>(u));
    return static_cast<T>(std::forward<U>(u));
}

struct narrowing_error : public std::exception {};

template <typename T, typename U>
constexpr T narrow_cast_checked(U u)
{
    static_assert(!details::can_fully_represent<T, U>, "we shouldn't be using narrow_cast for casts that aren't actually narrowing");
    if (details::static_cast_changes_value<T>(u))
        throw narrowing_error();

    return static_cast<T>(u);
}

The first thing I noticed: you only support basic arithmetic types (integral and floating point).  This isn't apparent from the name narrow_cast.  Either enforce this with a static assert, or provide a mechanism to provide extensions for user defined types.

Here's what you write:

template <typename T, typename U>
constexpr bool can_fully_represent =
    std::is_same<T, U>::value ||
    ( std::is_integral<T>::value && std::is_integral<U>::value &&
        ( ( std::is_signed<T>::value && sizeof(T) >  sizeof(U) ) ||
          ( is_same_signedness<T, U> && sizeof(T) >= sizeof(U) ) ) ) ||
    ( std::is_floating_point<T>::value && std::is_floating_point<U>::value && sizeof(T) >= sizeof(U) );

Here's what I think should be sufficient:

template <typename T, typename U>
constexpr bool can_fully_represent =
       std::numeric_limits<T>::min() <= std::numeric_limits<U>::min()
    && std::numeric_limits<T>::max() >= std::numeric_limits<U>::max();

OK, maybe I overlooked some edge cases, but that's the idea.

The unchecked version uses a forwarding reference, whereas the check version does not.  Try to keep the interface consistent.

std::is_same<T, U>::value can be simplified to std::is_same_v<T, U>.


Find largest smaller key in Binary Search Tree Given a root of a Binary Search Tree (BST) and a number num, implement
  an efficient function findLargestSmallerKey that finds the largest key
  in the tree that is smaller than num. If such a number doesn’t exist,
  return -1. Assume that all keys in the tree are nonnegative.

The Bst Class is given to me.

public class BstNode
{
    public int key;
    public BstNode left;
    public BstNode right;
    public BstNode parent;

    public BstNode(int keyt)
    {
        key = keyt;
    }
}

you can ignore the unit test code this is a just the demo.

   [TestMethod]
        public void LargestSmallerKeyBstRecrussionTest()
        {
            BstNode root = new BstNode(20);
            var left0 = new BstNode(9);
            var left1 = new BstNode(5);
            var right1 = new BstNode(12);
            right1.left = new BstNode(11);
            right1.right = new BstNode(14);
            left0.right = right1;
            left0.left = left1;

            var right0 = new BstNode(25);
            root.right = right0;
            root.left = left0;
            Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
        }

this is the code I would like you please to review, comment.

       public static int FindLargestSmallerKey(uint num, BstNode root)
    {
        if (root == null)
        {
            return -1;
        }
        int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
        if (root.key < num)
        {
            return Math.Max(root.key, temp);
        }
        return temp;
    }

Your code works correctly now (as far as I can tell). But due to

int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));

it always traverses the entire tree. This can be improved:

If root.key < num then root.key is a possible candidate for the result,
better candidates can only exist in the right subtree.
Otherwise, if root.key >= num, keys less than the given bound can only
exist in the left subtree.

That leads to the following implementation:

public static int FindLargestSmallerKey(uint num, BstNode root)
{
    if (root == null) {
        return -1;
    } else if (root.key < num) {
        int tmp = FindLargestSmallerKey(num, root.right);
        return tmp != -1 ? tmp : root.key;
    } else {
        return FindLargestSmallerKey(num, root.left);
    }
}

This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in \$ O(\log N) \$
time where \$  N \$ is the number of nodes.

The same idea can be used for an iterative solution:

public static int FindLargestSmallerKey(uint num, BstNode root)
{
    int result = -1;
    while (root != null) {
        if (root.key < num) {
            // root.key is a candidate, continue in right subtree:
            result = root.key;
            root = root.right;
        } else {
            // root.key is not a candidate, continue in left subtree:
            root = root.left;
        }
    }
    return result;
}

I would also add a more comprehensive set of unit tests. Start with
the simplest trees, for example

   10       10      10        10
           /          \      /  \
          5            15   5    15

and call your function with num from 1 to 20. That would already
have helped to find the flaws in your initial implementation.


Dynamically loading jQuery when it's not available or version isn't high enough I'm writing a script for others to use on their websites. I'd like to use jQuery in this script. Because I don't have control over what frameworks people use on their sites, I need to make sure jQuery is available and that it's version 1.8 or higher. Here's my take on it. Does anyone see anything I could/should be doing differently? Is there a better way of doing this?

//start anon function for whole script
;(function(){
    var $,
        hasOwn = ({}).hasOwnProperty,
        //get ie version returns false if ie>=11 or not ie
        ieVersion = function(){
            var v = 3,
                div = document.createElement('div'),
                all = div.getElementsByTagName('i');
            while(div.innerHTML = '<!--[if gt IE '+(++v)+']><i></i><![endif]-->', all[0]);
            return (v > 4 ? v : ('documentMode' in document ? document.documentMode : false));
        }(),
        //get which version of jQuery is currently added to the site
        jqVersion = function(){
            return 'jQuery' in window && !!window.jQuery ? parseFloat(window.jQuery.fn.jquery) : false;
        },
        //set the correct jquery version to use based on which version of ie is in use. Use an array in the case of one or more being down
        jqSrc = (!!ieVersion && ieVersion > 4 && ieVersion < 9) ? ['//ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js', '//cdnjs.cloudflare.com/ajax/libs/jquery/1.11.0/jquery.min.js', '//ajax.aspnetcdn.com/ajax/jQuery/jquery-1.11.0.min.js'] : ['//ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js', '//cdnjs.cloudflare.com/ajax/libs/jquery/2.1.0/jquery.min.js', '//ajax.aspnetcdn.com/ajax/jQuery/jquery-2.1.0.min.js'],
        //check jquery version and if it is above 1.8 use it, if not then get own version
        jqCheck = function(first){
            var version = jqVersion();
            if(!version || version < 1.8){
                getScript(jqSrc.shift(), jqCheck);
            }else{
                if(!!first){
                    $ = window.jQuery;
                }else{
                    $ = window.jQuery.noConflict(true);
                }
                load();
            }
        },
        //function to loop and load jquery script
        getScript = function(url, callback){
            var script = document.createElement('script'),
                tag = document.getElementsByTagName('script')[0],
                done = false;
            script.type = 'text/javascript';
            script.async = !0;
            script.src = url;

            script.onload = script.onreadystatechange = script.onerror = function(){
                if(!done && (!this.readyState || this.readyState == 'loaded' || this.readyState == 'complete')){
                    done = true;
                    if(typeof(callback) === 'function'){
                        callback.call(this);
                    }
                    script.onload = script.onreadystatechange = script.onerror = null;
                }
            };

            tag.parentNode.insertBefore(script, tag);
        },
        load = function(){
            //Start script
            window.myGlobalFunction = new function(){
                var privateVar = 'private',
                    privateFunc = function(){
                        return true;
                    };

                this.publicVar = 'public';

                this.publicFunc = function(){
                    return true;
                };
            };
        };

    //make sure json is avaiable, if not add it
    if(!hasOwn.call(window, 'JSON') || !hasOwn.call(JSON, 'parse') || (typeof(JSON.parse) !== 'function')){
        getScript('//cdnjs.cloudflare.com/ajax/libs/json3/3.3.1/json3.min.js', function(){
            //all functions are built start by checking for jQuery and it's builder
            jqCheck(true);
        });
    }else{
        //all functions are built start by checking for jQuery and it's builder
        jqCheck(true);
    }
})();

Before actually diving into creating a jQuery checker (nice idea by the way), you might really want to check some cases before building the code. There are several issues with your script here:

Your script assumes that there is jQuery. What if there's no jQuery at all? How would your script work? I suggest you stick to vanilla JS instead.
Documentation too long, didn't read, developer loaded your script first. It will break. You can't detect scripts because they are parsed in order. If your script came first, it cannot see the scripts loaded after it at the point of execution.
But what if a plugin already initialized with the version that came with the page? jQuery carries an internal cache for data, event handlers etc. If you switch jQuery now, they will break.
Dynamically loading a script is an async operation. You can't pause it right there. JS will continue. Therefore, while your script is loading a more recent version, plugins on your page might have already initialized using the one in your page.
Some plugins require a specific version of jQuery (like some prefer 1.4, or 1.6). Developers intentionally use them because some of these plugins use already deprecated API and weren't updated. If you load a newer version, they break.
If you really wanted IE support, why not just load the 1.x version rather than doing 2.x? This removes the need to detect IE. That's why there's a 1.x and 2.x version in the first place.


Dutch National flag solution in C++ this week I learned about QuickSort and used the technique to solve the Dutch National Flag problem. I would appreciate it if someone would review my code and give feedback.

  The Dutch national flag problem is a computer science programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

Code:

pair<int, int> Partition(vector<int> &nums, int low, int high) {
  int pivotElement = nums.at(low), lt = low, gt = high, i = low + 1;
  while (i <= gt) {
    // case of left parition
    if(pivotElement > nums.at(i)) {
      std::swap(nums.at(i), nums.at(lt));
      ++lt;
    } // below if the case of right partition
    else if (pivotElement < nums.at(i)) {
      std::swap(nums.at(i), nums.at(gt));
      --gt;
    }
    ++i;
  }
  return std::make_pair(lt, gt);
}

void DutchFlag(vector<int> &nums, int low, int high) {
  pair<int, int> p = std::make_pair(0, 0);
  if(low < high) {
    p = Partition(nums, low, high);
    DutchFlag(nums, low, p.first);
    DutchFlag(nums, p.second, high);
  }
}

int main() {
  std::vector<int> nums = {0, 1, 2, 2, 2, 1, 0, 0};
  DutchFlag(nums, 0, nums.size() - 1);
  std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
}

That's pretty good! Some small points...

Motivation

As, some of the comments point out, standard algorithms exist for std::sort and std::partition. You seem to be doing this in order to learn about algorithm implementation. That's fine and good for learning. Please be aware that in general / commercial / production code you should probably not be writing this and should use the above standard library functions instead.

Completeness

As some other comments point out, please try to post complete code. ie include the #include statements so that the code compiles and runs as posted.

Form / style / minor

It is generally discouraged to use using namespace std;; which would
be required to make your code work, because that includes a whole namespace and can cause clashes.
Generally avoid declaring more than one variable on one line.
The size() of containers returns std::size_t, which is usually an
unsigned long. If you enable -Wall -Wextra (on gcc / clang)
during compilation this will often give you warnings when you are
comparing with int. Your code as posted as actually OK on this
front, but it is still good practice to use std::size_t for those
integers which represent an index into a vector or similar  (bigger
max value too, for very large vectors). I usually write a using std::size_t to avoid having to repeat std:: for each variable declaration.
using at() is slower than operator[] because it does bounds checking. This might be what you intended, but given the "closed" nature of the algorithm it should be possible to use operator[] without errors or undefined behaviour.
You could use try using default params to DutchFlag() for low/high to avoid the caller having to specify 0, size() in the external API.
In general C++ and the STL tend to use Iterators and not vector indeces. So it would be more idiomatic for DutchFlag to take begin(), end() iterators.
C++ (like python) also uses the "one past the end" convention for a range of iterators, so DutchFlag (as written) should probably be taking 0, size() and some of your <= should change to <.

Algorithm

I am not an expert on the Dutch flag algo. Clearly a plain quicksort, which you have implemented, works. Are there some efficiencies which can be gained from the knowledge that there are lots of repeats and only 3 possible values? If there are, you should probably try to achieve some of those. Otherwise this is just quicksort? See the example code on std::partition reference page.

For example, one might imagine an algorithm where you just have a local int counts[3]{0} run through the unsorted data and counts[v]++. Then produce an answer which repeats each value count[v] number of times. This is O(N) as opposed to quicksort which is generally O(NlogN).

Something along these lines:

#include <array>
#include <iostream>
#include <iterator>
#include <vector>

using std::size_t;

void DutchFlag(std::vector<int>& nums) {
  auto counts = std::array<size_t, 3>{0};

  for (auto n: nums) ++counts[n];

  auto start = std::begin(nums);
  for (int i = 0; i < 3; ++i) {
    auto end = std::next(start, counts[i]);
    std::fill(start, end, i);
    start = end;
  }
}

int main() {
  std::vector<int> nums = {0, 1, 2, 2, 2, 1, 0, 0};
  DutchFlag(nums);
  std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
}

It depends on what your motivation is, but such an algorithm would likely be faster for very large inputs and the code is probably simpler (than implementing quicksort by hand).


Tic tac toe game using C++ I wrote this C++ code for Tic-tac-toe for an interview (The basic skeleton was pre-provided) and got rejected because the code was too complex and inefficient. I'm not an expert programmer so I'd like some ideas about how to better my code to make it more efficient. The code is as follows:

#include <iostream>

const int N = 3; // Square NxN board, win with N consecutive

int board[N][N];

class TicTacToe {

 public:

int MakeMove(int player, int row_location, int col_location){

  if(player == 1){

    if(board[row_location][col_location]==0){

      board[row_location][col_location]=1;
    /*std::cout << "Player: "<< player << "\nCurrent board:\n";
    for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
    std::cout << board[i][j];
    }
  }*/
}
else{

  std::cout<<"Invalid entry\n";
}
  }
  else if(player == 2){

if(board[row_location][col_location]==0){
  board[row_location][col_location]=2;
/*std::cout << "Player: "<< player << "\nCurrent board:\n";
for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        std::cout << board[i][j];
      }
  }*/
}
else{
  std::cout<<"Invalid entry\n";
}
  }

  int result = check_board(board);

  //std::cout << "\nResult of checkboard is: " << result << std::endl;

  return result;
}

private:

  int check_board(int board[N][N]){

bool flag = 0;
//std::cout << "\nInside checkboard function: \n";

if(flag==0)
{
for(int i=0;i<N;i++){      //Horizontal check
  for(int j=1;j<N-1;j++){
    if(board[i][j-1]==1 && board[i][j]==1 && board[i][j+1]==1){
      return 1;
      flag=1;
    break;
    }

    else if(board[i][j-1]==2 && board[i][j]==2 && board[i][j+1]==2){
      return 2;
      flag=1;
    break;
    }
  }
}
}

if(flag==0)
{

for(int j=0;j<N;j++){        //Vertical check
  for(int i=1;i<N-1;i++){

    if(board[i-1][j]==1 && board[i][j]==1 && board[i+1][j]==1){
      return 1;
      flag=1;
    break;
    }

    else if(board[i-1][j]==2 && board[i][j]==2 && board[i+1][j]==2){
      return 2;
      flag=1;
    break;
    }
  }
}
}

if(flag==0){

for(int i=1;i<N-1;i++){       //Leading diagonal check
  for(int j=i;j<N-1;j++){

    if(board[i-1][j-1]==1 && board[i][j]==1 && board[i+1][j+1]==1){
      return 1;
      flag=1;
    break;
    }

    else if(board[i-1][j-1]==2 && board[i][j]==2 && board[i+1][j+1]==2){
      return 2;
      flag=1;
      break;
    }
  }
}
}

if(flag==0){

 for(int i=N-1;i>1;i--){       //Opposite diagonal check

  for(int j=1;j<N-1;j++){

    //std::cout<<"In opposite diagonal loop\n "<<board[i+1][j-1]<<board[i][j]<<board[i-1][j+1];
    if(board[i+1][j-1]==1 && board[i][j]==1 && board[i-1][j+1]==1){

      return 1;
      flag=1;
    break;
    }

    else if(board[i+1][j-1]==2 && board[i][j]==2 && board[i-1][j+1]==2){

      return 2;
      flag=1;
      break;
    }
  }
}
}
return 0;
}
};

int main(int argc, char** argv) {

  int result;

  TicTacToe ttt;

  std::cout << "Starting test!" << std::endl;

  result = ttt.MakeMove(1,1,0);

  result = ttt.MakeMove(1,1,1);

  result = ttt.MakeMove(1,1,2);

  std::cout << "Winning Player is: " << result << std::endl;

 return 0;

}

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

Format your code

This code is messy and difficult to read.  It has inconsistent indentation, and very little whitespace, making it hard to read and understand.  There are abundant examples here of C++ code that is well formatted.

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error.  Eliminating global variables where practical is always a good idea.  In your code, there's no reason that board or N couldn't be members of the TicTacToe class instead, properly encapsulating.

Simplify your code

The code is full of duplicated code and inefficiency.  Duplicated code is a sign that you either need to refactor (for example by creating a new function) or rewrite the logic in a more compact form.  For example, there is no reason that horizontal and vertical checks couldn't be done within the same loop.  Also, only the player that just made a move could possibly win, so there's no point in checking squares which aren't marked with the current player's token.

Use better names

The variable name board is OK, but the name flag is not.  The first name explains something about what the variable means within the context of the code, but the latter is only confusing.  Also check_board is vague and unhelpful.  What is it checking?  What does it return?  Comments would help, but it's important to use descriptive names first.

Sanitize user input better

The only thing the code currently checks for is a space that's already occupied, but it does not verify that the proposed move is within bounds.

Eliminate "magic values"

The values of 1 and 2 are sprinkled through the code, but they really ought to be a named constant instead, and specifically a named constant static member of the class.

Fix the bug

The "opposite diagonal check" has these lines (formatting fixed):

for (int i = N - 1; i > 1; i--) {   //Opposite diagonal check
    for (int j = 1; j < N - 1; j++) {
        if (board[i + 1][j - 1] == 1 && board[i][j] == 1

The first time through the loop i - N - 1, but the check is looking at board[i + 1][j - 1] which will be board[N][0] the first time through the loop.  That's out of the boundary of the board and thus, a bug.

Think of the user

What happens if there is a tie game?  The board is full, but neither player has won.  The code doesn't check for or recognize this state, but it should, to avoid a frustrating experience for a user.

Study other code

One way to become a better programmer is to ask for a review of your code.  You've just done that, so good job!  Another way that helps is to read other people's code.  Look at other implementations of this game on Code Review and carefully read the answers.  It's a very simple way to learn a lot of good information.


Naming for unit tests for controller to edit posts I am relatively new to TDD and am trying to adopt better names for my tests.

I wrote the following tests abruptly and have since refactored them to the best of my ability, but despite my best efforts, the test names are still (mostly) abysmal.

I am here today to ask that you review my test names.

[Test]
public void Edit_ReturnsCorrectView()
{
    var actual = controller.Edit("dynamic-contagion-part-one") as ViewResult;

    Assert.NotNull(actual);
    Assert.That(actual.ViewName, Is.EqualTo("Edit"));
}

[Test]
public void Edit_ReturnsCorrectModel()
{
    var viewResult = (ViewResult) controller.Edit("dynamic-contagion-part-one");
    var actual = viewResult.Model as PostInputModel;

    Assert.NotNull(actual);
    Assert.That(actual.Title, Is.EqualTo("Dynamic contagion, part one"));
}

[Test]
public void Edit_NonExistentPost_ReturnsNotFound()
{
    var actual = controller.Edit("non-existent-slug") as HttpNotFoundResult;

    Assert.NotNull(actual);
    Assert.That(actual.StatusDescription,
        Is.EqualTo("You cannot edit a post that does not exist."));
}

[Test]
public void Edit_Post_ReturnsCorrectView()
{
    var actual = controller.Edit(post) as ViewResult;

    Assert.NotNull(actual);
    Assert.That(actual.ViewName, Is.EqualTo("Edit"));
}

[Test]
public void Edit_EditsPostContent()
{
    post.Content = "arbitrary content.";
    controller.Edit(post);

    var amendedPost =
        repository.Object.Posts.First(p => p.Slug == "dynamic-contagion-part-one");
    Assert.That(amendedPost.Content, Is.EqualTo("arbitrary content."));
}

[TestCase("foo", ExpectedResult = "foo")]
[TestCase("foo\r\nbar", ExpectedResult = "foo")]
public string Edit_EditsPostSummary(string content)
{
    post.Content = content;
    controller.Edit(post);

    var amendedPost =
        repository.Object.Posts.First(p => p.Slug == "dynamic-contagion-part-one");
    return amendedPost.Summary;
}

[Test]
public void Edit_EditsPostSlug()
{
    post.Title = "Hello, World";
    controller.Edit(post);

    repository.Object.Posts.First(p => p.Slug == "hello-world");
}

[Test]
public void Edit_Post_NonExistentPost_ReturnsNotFound()
{
    var model =
        new PostInputModel {Title="Non Existent Slug",Slug="non-existent-slug"};

    var actual = controller.Edit(model) as HttpNotFoundResult;

    Assert.NotNull(actual);
    Assert.That(actual.StatusDescription,
        Is.EqualTo("You cannot edit a post that does not exist."));
}

[Test]
public void Edit_InvalidModel_ReturnsCorrectModel()
{
    controller.ModelState.AddModelError("", "");
    var model = new PostInputModel();

    var actual = controller.Edit(model) as ViewResult;

    Assert.NotNull(actual);
    Assert.That(actual.ViewName, Is.EqualTo("Edit"));
    Assert.AreEqual(model, actual.Model);
}

[Test]
public void Edit_OccupiedSlug_ReturnsCorrectView()
{
    var model = new PostInputModel
    {
        Title = "Lowering in language design, part two",
        Content = "arbitrary content."
    };

    var actual = controller.Edit(model) as ViewResult;

    Assert.NotNull(actual);
    Assert.That(
        controller.ModelState[""].Errors[0].ErrorMessage,
        Is.EqualTo("You have previously published a post with this title. " +
                   "Please choose another one."));
}

I welcome all feedback regarding this segment of code but in an attempt to be more specific, something that makes me particularly nauseous are these test names:

Edit_ReturnsCorrectView
Edit_Post_ReturnsCorrectView

Here I am trying to differentiate which action method I am testing according to the HTTP verb which is clearly ambiguous and generally yucky.

I am also concerned about the Edit_EditsX convention that I have developed and wonder if there is a better approach to testing that data in my (fake) repository is updated accordingly.

Let me start out by saying that your test names are actually decent. You have already come to the conclusion that a good test name is one that can convey what is being tested without requiring someone to actually read the test.

As with many things, there are three important pieces of information about what a test is doing:

What is the thing being tested?
What is the input to the thing being tested? / In what context is the thing being tested?
What is the expected result?

If I see a test is failing and the name provides all this information, I can start formulating an idea of what the issue might be without doing more than seeing the test report.

There are a few different theories about how these three things should be ordered based on what the person feels is the focal point. But I prefer the order introduced by Roy Osherove, which matches the order I listed above. This provides us with:

[Test]
public void UnitOfWork_StateUnderTest_ExpectedBehavior()
{
  // ...
}

You don't have to be concerned with the name becoming very wordy. These are test cases and don't need to follow the same naming conventions you would use for methods in your production code. Artificially restricting yourself to HTTP verbs is preventing you from accurately describing the context that is being tested.

Additionally, try to stay away for using "correct value" as the description of the expected result. If I didn't write the code or tests, I likely don't know what the expected result is. More importantly, I won't know why that is the expected value.

Bellow are a few examples of your test case names converted into this style:

Edit_ReturnsCorrectView -> Edit_SomeSlugName_ViewNameEdit
Edit_Post_ReturnsCorrectView -> Edit_SomePost_ViewNameEdit
Edit_EditsPostContent -> Edit_PostWithAlteredContent_PostsContentUpdated

The use of Some is also taken from Roy. It is meant to indicate that there is nothing special about this value and a different arbitrary value should have the same result.

Other notes:

var actual = controller.Edit(model) as HttpNotFoundResult;
Assert.NotNull(actual);

and

var actual = controller.Edit(model);
Assert.NotNull(actual);

Are two very different things. The second case uniquely states that the result must not be null. However, the first case can fail the null check for two different reasons (the result is null or the result is of the wrong type). I suspect you are using this just ensure that the correct type is returned. If that is the case, you should be able to use the testing framework to verify the result is the correct type instead of potentially introducing a null.

Most of your tests are checking that some text field contains an expected sentence. This type of test can be very fragile. If the message displayed to the user is reworded or translated to a different language, the test would start failing. Do you actually care about the wording of the error message or is knowing that a HttpNotFoundResult instance was returned sufficient? Is there an IsError property you could test instead?

Your tests are using a mock repository that is filled with some sample data. There is nothing wrong with this. The one thing I would change would be to move all of the hard coded strings from the tests into the class that produces the mock as constants. This way, all of the data, is defined in one places and you don't have to edit this test class if a different test class requires the repository to contain something slightly different.


Text Duplicate filter in Python 3.7 I wrote this program just to remove duplicates from wordlist used for brute-force, but it can be used for every txt file i guess.
It is a pretty long program for what it does, and I'm sure there is a way I can make it easier and better for everyone to look at.
I'm still a beginner in python.

def wordcount_initial():  # count the numbre of words in the input file
    global num_words_initial

    with open(file_initial, 'r') as f:
        for line in f:
            words = line.split()
            num_words_initial += len(words)

def dupfilter():
    content = open(file_initial, "r").readlines()
    content_set = set(content)  # filter duplicates
    cleandata = open(file_final, "w+")  # write the text filtered in the new   file

    for line in content_set:
        cleandata.write(line)

def wordcount_final():  # count number of words in the new file
    global num_words_final

    with open(file_final, 'r') as f:
        for line in f:
            words = line.split()
            num_words_final += len(words)

if __name__ == '__main__':
    num_words = 0
    num_words_initial = 0
    num_words_final = 0

    ready = False
    while not ready:
        file_initial = input("What is the name of the text?")

        file_final = input("How do you want to name the filted file?")

        if file_initial and file_final != "":

            wordcount_initial()
            ready = True

    dupfilter()

    wordcount_final()

    print("Number of duplicates filtered:" + str(num_words_initial - num_words_final))
    input("\nPress <ENTER> to quit the program.")

You should not use global variables unless you really need to. Instead, pass relevant parameters as arguments to the functions and return the results. This makes them actually reusable. Currently you have two functions to count the initial and final number of words, when you could just have a word_count function:

def wordcount(file_name):
    """count the number of words in the file"""
    with open(file_name) as f:
        return sum(len(line.split()) for line in f)

def dupfilter(file_initial, file_final):
    with open(file_initial) as in_file, open(file_final, "w") as out_file:
        out_file.writelines(set(in_file.readlines()))

if __name__ == '__main__':
    while True:
        file_initial = input("What is the name of the text?")
        file_final = input("How do you want to name the filtered file?")
        if file_initial and file_final and file_initial != file_final:
            break

    num_words_initial = wordcount(file_initial)
    dupfilter(file_initial, file_final)
    num_words_final = wordcount(file_final)

    print("Number of duplicates filtered:", num_words_initial - num_words_final)
    input("\nPress <ENTER> to quit the program.")

I also used sum with a generator expression to simplify the wordcount function, used with to ensure that files are properly closed.
In addition, I replaced the while not ready loop with a while True loop and an explicit break. This is much more common in Python, especially for user input.

Note that if file_initial and file_final != "" is only incidentally the same as if file_initial != "" and file_final != "" because non-empty strings are truthy. This is why it is also equivalent to if file_initial and file_final. But for example x and y == 3 is not the same as x == 3 and y == 3.

You also don't need to call str on things to be printed, print does that for you if necessary.

Note that using set does not guarantee the same order as the original file, for that you would want to use the itertools recipe unique_everseen:

from itertools import filterfalse

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

def dupfilter(file_initial, file_final):
    with open(file_initial) as in_file, open(file_final, "w") as out_file:
        out_file.writelines(unique_everseen(in_file))


Rock, Paper, Scissors game in JavaScript I built this as part of completing the Codecademy JavaScript lesson. I wanted to perfect it, make it readable and functional, and as efficient as possible. As far as I can tell it can't be any more efficient than this. But maybe I can't tell. What do you think? I know there are little things, maybe the victory variable should have a console.log in it. Probably one or two more. But hopefully this is a good example for people who need help with writing their Rock, Paper, Scissors challenge.

//Loop ensures only valid user input is rock, paper, scissors
var i, infiniteloop;
for (i=0; i<1; infiniteloop++) //infiniteloop allows loop to continue if user is infinitely retarded
{
    var userChoice = prompt("You're playing rock, paper, scissors against the computer. Type your choice in lower case letters.")
    if (userChoice === "rock") {i=1;} //escapes loop
        else if (userChoice === "paper") {i=1;} //escapes loop
        else if (userChoice === "scissors") {i=1;} //escapes loop
        else {alert("Try again, stupid.");} //alerts, loops back to start
}

console.log("You chose " + userChoice + "!"); //announces userChoice

//generate a random computer choice, assign a string to replace it
var computerChoice = Math.random(); //random function. generates a number between 0 and 1
if (computerChoice <= .33) { computerChoice = "rock"; }
    else if (computerChoice <= .66) { computerChoice = "paper"; }
    else { computerChoice = "scissors"; }

console.log("Computer chose " + computerChoice + "!"); //announces computerChoice

var victory = "You win! A master strategist is you." //preset victory announcement
if (userChoice === computerChoice) { console.log("Tie game!"); }
    else if (userChoice === "rock" && computerChoice === "scissors") { victory }
    else if (userChoice === "paper" && computerChoice === "rock") { victory }
    else if (userChoice === "scissors" && computerChoice === "paper") { victory }
    else {console.log("You have suffered a devastating loss.");}

Here are my 2 cents to improve your code.

First of all, if you're going to be using an infinite loop anyways to check for user input, why not make it a while loop instead of a for loop?

while (i === 0)
{
    var userChoice = prompt("You're playing rock, paper, scissors against the computer. Type your choice in lower case letters.")
    if (userChoice === "rock") {i=1;} //escapes loop
        else if (userChoice === "paper") {i=1;} //escapes loop
        else if (userChoice === "scissors") {i=1;} //escapes loop
        else {alert("Try again, stupid.");} //alerts, loops back to start
}

I personally feel that a while loop is far easier to read than a for loop, and in your case you have two variables which doesn't seem necessary. By using a while loop, you won't need to have the 'infiniteloop' variable.

Also, it looks like the victory messages won't be printed to the console as you're just calling the strings after each case.
This should do the trick:

else if (...) { console.log(victory); }

Congrats on finishing a game though! It's always a great place to start :)

Best of luck for your coding journey!!

shifubear


Recursive branch and bound Knapsack solution I've got the imperative styled solution working perfectly.
What I'm wondering is how to make a recursive branch and bound.

This is my code below. Evaluate function returns the optimistic estimate, the largest possible value for the set of items which fit into the knapsack (linear relaxation).

For some inputs this outputs an optimal solution, for some it comes really close, for every input it is extremely fast, so it doesn't seem that it hangs anywhere in the search space. So, maybe I'm not branching where I have to or I did something wrong. I'm sure optVal is optimal.

def branch(items: List[Item], taken: List[Item], capacity: Int, eval: Long): (List[Item], Boolean) = items match {
  case x :: xs if x.weight <= capacity => {

    val (bestLeft, opt) = branch(xs, x :: taken, capacity - x.weight, eval)
    if (opt) (bestLeft, opt) // if solution is optimal get out of the tree
    else {
      val evalWithout = evaluate(taken.reverse_:::(xs))

      if (evalWithout < optVal) (bestLeft, opt)
      else branch(xs, taken, capacity, evalWithout)
    }
  }
  case x :: xs => branch(xs, taken, capacity, evaluate(taken.reverse_:::(xs)))

  case Nil => if ((taken map (_.value) sum) == optVal) (taken, true) else (taken, false)
}

Here is a 'wanna-be functional' solution in java which might help you (it has gone through a set of test cases so I believe it works correctly)

private double bestBound;

public Knapsack.KnapsackResult solve() {
    Cons<Knapsack.Item> list = Cons.from(items);
    bestBound = 0.0;

    double bound = calcBound(list, capacity, 0.0);
    Solution res = dfs(list, 0, capacity, bound, null);

    return buildSolution(res);
}

public Solution dfs(Cons<Knapsack.Item> list, int value, int weight, double bound,
        Cons<Knapsack.Item> taken) {
    if (bound < bestBound) {
        return null;
    }
    if (list == null) {
        bestBound = bound;
        return new Solution(bound, taken);
    }
    Knapsack.Item item = list.head();
    if (item.weight > weight) {
        return notTaking(list, value, weight, taken);
    }

    // taking the item
    Solution left = dfs(list.tail(), value + item.value, weight - item.weight,
        bound, Cons.cons(item, taken));

    // not taking the item
    Solution right = notTaking(list, value, weight, taken);

    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    if (right.bound > left.bound) {
        return right;
    } else {
        return left;
    }
}

private Solution notTaking(Cons<Knapsack.Item> list, int value, int weight,
        Cons<Knapsack.Item> taken) {
    Cons<Knapsack.Item> tail = list.tail();
    Cons<Knapsack.Item> without;
    if (taken != null) {
        without = taken.reverse().append(tail);
    } else {
        without = tail;
    }
    double newBound = calcBound(without, capacity, 0.0);
    if (newBound <= bestBound) {
        return null;
    }
    return dfs(tail, value, weight, newBound, taken);
}

public static double calcBound(Cons<Knapsack.Item> list, int k, double acc) {
    if (list == null) {
        return acc;
    }

    Knapsack.Item head = list.head();
    if (head.weight <= k) {
        return calcBound(list.tail(), k - head.weight, acc + head.value);
    } else {
        return acc + head.relativeValue() * k;
    }
}

Here I used cons for lists - so it's the same as lists in Scala. There's only one "global" variable - bestBound - which, I know, not very functional, but it was just simpler than passing it around.


Shortening boolean with if statement for document version comparison Can this be shortened to one line?

 bool areVersionsEqual = documentComparer.Equals(version, imported);

if (areVersionsEqual == false)
  {
    changedDocument.Add(imported);
   }

Sure. Use the Not operator.

if (!documentComparer.Equals(version, imported))
{
    changedDocument.Add(imported);
}

To explain a little, it's bad practice to do things like this.

bool boolean = true;
if (boolean == false)
{
//...

because it's completely equivalent to saying

if (true == false)

and can be simplified down to

if (false)


How to properly call an "upsert" using parameterized raw SQL to Postgresql in ActiveRecord? I need to call an upsert to my Category table in PostgreSQL. My current solution uses the exec_query API in ActiveRecord, using binding.

What I got so far looks like this:

VERIFY_CATEGORY_SQL = <<SQL
  WITH sel AS (SELECT id FROM categories WHERE name=$1 AND source=$2),
  ins AS (INSERT INTO categories (name, source, created_at, updated_at) SELECT
    $3, $4, 'now', 'now' WHERE NOT EXISTS (SELECT * from sel) RETURNING id)
  select id from ins union all select id from sel
SQL

VERIFY_CATEGORY_SQL = <<SQL
  WITH sel AS (SELECT id FROM categories WHERE name=$1 AND source=$2),
  ins AS (INSERT INTO categories (name, source, created_at, updated_at) SELECT
    $1, $2, now(), now() WHERE NOT EXISTS (SELECT * from sel) RETURNING id)
  select id from ins union all select id from sel
SQL

def verify_category_existence(name, source)
  ActiveRecord::Base.connection.exec_query(VERIFY_CATEGORY_SQL, 'SQL',
    [[nil, name], [nil, source]]).first['id'].to_i
end

Notes

In order to make this work I needed to add prepared_statements: true attribute to my database.yml file.
Although I need to reuse my name and source parameters, I can't and have to duplicate them as parameters $1, $3 and $2, $4 respectively (Apparently this works fine...)
The method call seems a bit hackish, and I believe maybe it was not meant as a public method, and only intended for internal uses (hence the awkward [[nil, x]...] syntax and the 'SQL' parameter, which apparently is for logging purposes)

What do you think of this solution?

Do you know of a better way to do this?

Edit:

I've received great responses to the SQL/Postgresql side of my solution, but I would love to also hear from our rubyists regarding the Ruby/ActiveRecord part of the solution - is this way correct? is there a better solution?

Edit:

Just found out that using 'now' produced unexpected results - timestamp values were re-used rather than calculated on each insert. Changed it to now(), and it works better.

Statement, formatted readably:

WITH
sel AS (
  SELECT id FROM categories WHERE name=$1 AND source=$2
),
ins AS (
  INSERT INTO categories (name, source, created_at, updated_at )
  SELECT  $1, $2, 'now', 'now'
  WHERE NOT EXISTS (SELECT * FROM sel)
  RETURNING id
)
SELECT id FROM ins
UNION ALL
SELECT id FROM sel;

Dummy table:

CREATE TABLE categories (
    id serial not null PRIMARY KEY,
    name text not null,
    source text not null,
    created_at timestamp,
    updated_at timestamp,
    UNIQUE(name, source)
);

Demo, with three concurrent psql sessions:

Session1: PREPARE q(text,text) AS WITH ...
Session2: PREPARE q(text,text) AS WITH ...
Session0: BEGIN;
Session0: LOCK TABLE categories IN ACCESS EXCLUSIVE MODE;
Session1: EXECUTE q('n', 's');
Session2: EXECUTE q('n', 's');
Session0: ROLLBACK;

One session will report:

regress=> EXECUTE q('n', 's');
 id
----
  1
(1 row)

and one will report:

regress=> EXECUTE q('n', 's');
ERROR:  duplicate key value violates unique constraint "categories_name_source_key"
DETAIL:  Key (name, source)=(n, s) already exists.

So it might be OK if you have a unique constraint on (name, source) and are willing to retry errors, but if you don't have that unique constraint:

ALTER TABLE categories DROP CONSTRAINT categories_name_source_key;

then you'll get a double insert, because your SELECT for IDs can run on both sessions before either session executes the INSERT.

If you have a unique constraint, there's no point wasting your time with all this hoop jumping. You're better off just running the insert and if it fails, querying for the ID of the existing row.