Vigenere Decypher in C++ I've written a Vigenere decypher and I would like to have some opinions before I try to refactor it into more OOP style with classes and such.

#include <bits/stdc++.h>
#define Rep(i,a,n) for(int i = a; i < n; i++)
#define rep(i,n) Rep(i,0,n)
using namespace std;
int main(){
    string key, line, code = "", dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", decoded = "";
    cin >> key;
    int n = dict.length();
    char** key_matrix = new char*[n];
    rep(i,n)
        key_matrix[i] = new char[n];
    rep(i,n)
        rep(j,n)
            key_matrix[i][j] = dict[(i+j)%n];
    fstream file;
    file.open("text.txt");
    while(getline(file, line))
        code += line;
    file.close();
    rep(i,code.length()){
        if(!iswspace(code[i])){
            rep(j,n)
                if(key_matrix[j][0] == key[i%key.length()]){
                    rep(k,n)
                        if(key_matrix[j][k] == code[i]){
                            decoded += key_matrix[0][k];
                            break;
                        }
                }
        }else{
            decoded += " ";
        }
    }
    cout << decoded;
}

#include <bits/stdc++.h>

This is distinctly non-portable.  The files in bits/ are internal to GCC, may change without warning, and and are probably inefficient.  Use the correct Standard C++ headers instead:
#include <cctype>
#include <fstream>
#include <iostream>
#include <string>

#define Rep(i,a,n) for(int i = a; i < n; i++)
#define rep(i,n) Rep(i,0,n)

Macros are dangerous - that's why we minimise their use, and use uppercase names for them.  In this case, they serve mainly to obfuscate the code (in particular, they tend to hide mismatches between int and the type of n; they also introduce risk of repeating operations within n).

using namespace std;

This namespace is not one of the few intended to be imported wholesale.
Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

string key, line, code = "", dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", decoded = "";

Prefer one declaration per line, and declare as close to first use as possible.  dict doesn't need to be mutable:
static const std::string dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
static const std::size_t n = dict.length();

std::string key;
std::cin >> key;

std::cin >> key;

This won't read beyond the first whitespace.  Is that made obvious to users somehow?

char** key_matrix = new char*[n];
rep(i,n)
    key_matrix[i] = new char[n];
rep(i,n)
    rep(j,n)
        key_matrix[i][j] = dict[(i+j)%n];

You'll find it easier to use a vector rather than an array of arrays here.  That will automatically fix the memory leak you have.  However, do you really need to allocate this storage?  There's a simple arithmetical relationship between each member, and I don't see that you get any benefit from storing each table, compared to processing on the fly.

std::fstream file;
file.open("text.txt");

Instead of hard-coding the file name, why not pass it as an argument?  That would make the program much more flexible.  Even better, just read from standard input, and accept the key as argument - that's much more consistent with user expectations.

std::string code = "";
std::string line;
while(getline(file, line))
    code += line;
file.close();

There's no need to read the whole of the input before starting to write any output.  The code will scale much better if you operate on reasonable-sized chunks (even a character at a time - that's why standard I/O is buffered), and write the output as it's produced.

std::string decoded = "";
for (std::size_t i = 0;  i < code.length(); ++i) {
    if (!iswspace(code[i])) {
        rep(j,n)
            if(key_matrix[j][0] == key[i%key.length()]){
                rep(k,n)
                    if(key_matrix[j][k] == code[i]){
                        decoded += key_matrix[0][k];
                        break;
                    }
            }
    } else {
        decoded += " ";
    }
}

This whole nested loops of linear search appears very inefficient.  It also drops all characters that are not spaces and not in dict - i.e. all punctuation and lower-case letters.
(It's not clear why you're using std::iswspace() instead of std::isspace() - we deal with plain char everywhere else, so why use the wide-char function here?  In any case, we need a cast to unsigned type, as char may be signed.)
I suggest a re-think of the algorithm here.  We need to be able to convert input characters to their indices in dict - I suggest a lookup table for that (with a sentinel value to indicate "not present").  We can pre-process the key by converting each character to the corresponding index before we start.  Then just iterate over input adding the current character's index to the corresponding key value, and indexing back into dict to give the output value.
We can avoid using % when indexing into dict by populating it with two copies of the alphabet.

Improved version
#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <vector>

static const std::string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

static const std::vector<int> index = []{
    std::vector<int> v(UCHAR_MAX+1, -1);
    for (auto i = 0u;  i < alphabet.length();  ++i) {
        unsigned char c = alphabet[i];
        v[c] = i;
    }
    return v;
}();

int main(int argc, char **argv)
{
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " KEY" << std::endl;
        return 1;
    }

    std::vector<int> key;
    for (char *p = argv[1];  *p;  ++p) {
        int i = index[*p];
        if (i >= 0)
            key.push_back(i);
    }

    if (key.empty()) {
        std::cerr << "Invalid key" << std::endl;
        return 1;
    }

    std::size_t keypos = 0;

    char c;
    while (std::cin >> c) {
        auto i = index[c];
        if (i < 0) {
            std::cout << c;
        } else {
            static const std::string alphabet2 = alphabet + alphabet;
            std::cout << alphabet2[i+key[keypos++]];
            if (keypos >= key.size())
                keypos = 0;
        }
    }
}

You might want instead to process chunks (perhaps lines), in which case a function like this would be more appropriate:
// decrypt using key beginning at keypos; update keypos with new position
static std::string decrypt(const std::vector<int>& key, std::size_t& keypos, std::string s)
{
    static const std::string alphabet2 = alphabet + alphabet;

    for (auto& c: s) {
        auto i = index[c];
        if (i >= 0) {
            c = alphabet2[i+key[keypos++]];
            if (keypos >= key.size())
                keypos = 0;
        }
    }

    return s;
}

This separated function also makes it easier to test functionality (I did that myself whilst writing the monolithic main() above), and it may well be a stepping-stone to creating an object-oriented version (where key and keypos would be members of the decryption object).


C++ String Non-Member Operator Overloading This is a practice for operator overloading, I am well aware that some of these don't make sense. I am seeking review only on the code/practices, not the purpose.

/* (C) 2017 ZACH HILMAN
 * PROPRIETARY/CONFIDENTIAL. ALL RIGHTS RESERVED
 *
 *
 *
 *
 *
 */
#ifndef COMPUTERSCIENCE_ENHANCED_STRING_H
#define COMPUTERSCIENCE_ENHANCED_STRING_H

#include <string>

/// Remove the first occrance of rhs from lhs.
inline std::string operator-(const std::string& lhs, const std::string& rhs) {
    auto loc = lhs.find(rhs);
    if (loc != -1) return lhs.substr(0, loc) + lhs.substr(loc + rhs.size());
    return std::string();
}

inline std::string& operator-=(std::string& lhs, const std::string& rhs) {
    return lhs = operator-(lhs, rhs);
}

/// Repeat lhs rhs times.
inline std::string operator*(const std::string& lhs, unsigned long rhs) {
    std::string out;
    while (rhs --> 0) out += lhs;
    return out;
}

inline std::string& operator*=(std::string& lhs, unsigned long rhs) {
    return lhs = operator*(lhs, rhs);
}

/// Find the number of times rhs appears in lhs.
inline unsigned long operator/(const std::string& lhs, const std::string& rhs) {
    if (rhs == "") return static_cast<unsigned long>(-1);
    unsigned long out = 0;
    for (unsigned long s_loc = 0, a; s_loc < lhs.size();) {
        if ((a = lhs.find(rhs, s_loc)) != -1) ++out, s_loc = a + 1;
        else break;
    }
    return out;
}

/// Remove all occurances of rhs from lhs.
inline std::string operator%(const std::string& lhs, const std::string& rhs) {
    if (rhs == "") return lhs;
    auto out = lhs;
    std::string::size_type pos;
    while ((pos = out.find(rhs)) != std::string::npos) out = out.replace(pos, rhs.size(), "");
    return out;
}

inline std::string& operator%=(std::string& lhs, const std::string& rhs) {
    return lhs = operator%(lhs, rhs);
}

// Subtract str from STRING_CHARSET (Not done-- will eventually be all ASCII characters).
inline std::string operator~(const std::string& str) {
    static const std::string STRING_CHARSET = "";
    return operator-(STRING_CHARSET, str);
}

// Find the intersection of characters of lhs and rhs.
inline std::string operator&(const std::string& lhs, const std::string& rhs) {
    std::string out;
    for (auto c : lhs) if (rhs.find(c) != std::string::npos) out += c;
    return out;
}

inline std::string& operator&=(std::string& lhs, const std::string& rhs) {
    return lhs = operator&(lhs, rhs);
}

/// Find the union of characters of lhs and rhs.
inline std::string operator|(const std::string& lhs, const std::string& rhs) {
    std::string out;
    for (auto c : lhs) if (out.find(c) == std::string::npos) out += c;
    for (auto r : rhs) if (out.find(r) == std::string::npos) out += r;
    return out;
}

inline std::string& operator|=(std::string& lhs, const std::string& rhs) {
    return lhs = operator|(lhs, rhs);
}

/// Find the XOR of characters of lhs and rhs.
inline std::string operator^(const std::string& lhs, const std::string& rhs) {
    std::string out;
    for (auto c : lhs) if (rhs.find(c) == std::string::npos) out += c;
    for (auto r : rhs) if (lhs.find(r) == std::string::npos) out += r;
    return out;
}

inline std::string& operator^=(std::string& lhs, const std::string& rhs) {
    return lhs = operator^(lhs, rhs);
}

/// Add rhs spaces to the front of lhs.
inline std::string operator>>(const std::string& lhs, unsigned long rhs) {
    return std::string(rhs, ' ') + lhs;
}

inline std::string& operator>>=(std::string& lhs, unsigned long rhs) {
    return lhs = operator>>(lhs, rhs);
}

/// Add rhs spaces to the end of lhs.
inline std::string operator<<(const std::string& lhs, unsigned long rhs) {
    return lhs + std::string(rhs, ' ');
}

inline std::string& operator<<=(std::string& lhs, unsigned long rhs) {
    return lhs = operator<<(lhs, rhs);
}

#endif //COMPUTERSCIENCE_ENHANCED_STRING_H

Style Advice

Do not try to do too much on one line. Constructs such as if ((a = lhs.find(rhs, s_loc)) != -1) ++out, s_loc = a + 1; are difficult to read, difficult to parse and prone to errors. Instead, let each control statement have its own block, and do not abuse the comma operator to do completely unrelated things. For example, the line I mentioned should rather be something like

if ((a = lhs.find(rhs, s_loc)) != -1) {
    ++out;
    s_loc = a + 1;
}

or, even better,

a = lhs.find(rhs, s_loc);
if (a != -1) {
    ++out;
    s_loc = a + 1;
}

Avoid magic numbers. In particular, when checking the result of string::find, check whether the result is equal to std::string::npos, not -1. There even are some places in the code where you are already doing this, so please adopt it for the remaining places as well.
Prefer early return on failure. Concretely, in operator- you return an empty string only after you have checked for and possibly returned a valid result. Although this is quite minor, I would have expected the method to work the other way around, i. e.

if (loc == std::string::npos) {
    return std::string();
}
return lhs.substr(0, loc) + lhs.substr(loc + rhs.size());

which is quite a common pattern.
if (rhs == "") return static_cast<unsigned long>(-1); works but is not expressive. Prefer

if (rhs.empty()) {
    return std::numeric_limits<unsigned long>::max();
}

while (rhs --> 0) out += lhs; does nothing but obscure what is going on. --> is not an operator in C++, so you should not write it as if it were one. Write while (rhs-- > 0) ...
Remove the typo from the comment to operator-; what currently reads "occrance" should probably be "occurance".

Possible Optimizations

Although generally your code appears to work well, there are some things that you could easily implement to improve performance, mostly to avoid unnecessary copies.

While it is good practice to implement operators in terms of other operators, the way that you implemented your operation + assignment-operators incurs making additional copies of your input. For example, let's consider operator% and operator%=:

inline std::string operator%(const std::string& lhs, const std::string& rhs) {
    //...
    auto out = lhs;
    //...
    return out;
}

inline std::string& operator%=(std::string& lhs, const std::string& rhs) {

    return lhs = operator%(lhs, rhs);
}

Since operator% does not modify its inputs, it has to make a copy which is then modified and returned. However, operator%= does modify one of its inputs, in this case lhs, so making a copy, modifying it and reassigning it to lhs is unnecessary. Instead, you could approach the problem the other way around: First, implement operator%=, then implement operator% in terms of it:

inline std::string& operator%=(std::string& lhs, const std::string& rhs) {
    //perform in-place operation on lhs
    return lhs;
}

inline std::string operator%(const std::string& lhs, const std::string& rhs) {
    std::string out = lhs;
    out %= rhs;
    return out;
}


Possible memory leak in a for loop macro I was reading about similar problems to the one I am having, and my guess is that I am having a 'memory leak'. I'm not sure exactly what that means, or how to correct it.  Could you take a look at my code and help me optimize?  LastRow in this bit is a little over 70000.

start = Timer
For Row = 4 To LastRow
DoEvents
    If Original.Cells(Row, 4) <> "" Then
    Application.StatusBar = "Progress: " & Row & " out of " & LastRow & ": " & Format(Row / LastRow, "0.00%")
        'VLookUp method
'''''        Data.Cells(DataRow, 1).value = Original.Cells(Row, 4).value
'''''        Data.Cells(DataRow, 2).value = Original.Cells(Row, 39).value
'''''        Result = Evaluate("Vlookup('New Cost Data'!A" & DataRow & ",'PupFile Data'!B:D,3,false)")
'''''
'''''        If IsError(Result) = True Then
'''''            Data.Cells(DataRow, 3) = "No Old Cost"
'''''            DataRow = DataRow + 1
'''''        ElseIf Result = 0 Then
'''''            Data.Cells(DataRow, 3) = "No Old Cost"
'''''            DataRow = DataRow + 1
'''''        Else
'''''            Data.Cells(DataRow, 3) = Result
'''''            Data.Cells(DataRow, 4) = Format((Data.Cells(DataRow, 2) - Result) / Result, "0.00%")
'''''            DataRow = DataRow + 1
'''''        End If

    'Find() method
        Set RNGFound = Range(Pup.Cells(2, 2), Pup.Cells(Pup.Cells(Rows.count, 2).End(xlUp).Row, 2)).Find(Original.Cells(Row, 4))
        If Not RNGFound Is Nothing Then
           PupRow = Range(Pup.Cells(2, 2), Pup.Cells(Pup.Cells(Rows.count, 2).End(xlUp).Row, 2)).Find(Original.Cells(Row, 4), lookat:=xlWhole, searchorder:=xlRows, MatchCase:=True).Row
           Data.Cells(DataRow, 1).Value = Original.Cells(Row, 4).Value
           Data.Cells(DataRow, 2).Value = Original.Cells(Row, 39).Value
           Data.Cells(DataRow, 3).Value = Pup.Cells(PupRow, 4).Value
           Data.Cells(DataRow, 4) = (Data.Cells(DataRow, 2) - Data.Cells(DataRow, 3)) / Data.Cells(DataRow, 3)
        Else
            Data.Cells(DataRow, 1).Value = Original.Cells(Row, 4).Value
            Data.Cells(DataRow, 2).Value = Original.Cells(Row, 39).Value
            Data.Cells(DataRow, 3) = "No old Cost"
        End If
        DataRow = DataRow + 1
    End If
Next Row
Application.StatusBar = False
finish = Timer - start
MsgBox finish
Stop

The Vlookup() method took me about 500 seconds, but it slowed down considerably from the beginning. The find() method looked like it was taking much longer, so I am probably going with the vlookup, but what about the actual slowing down of the code? Is there something I need to change, or is slowing down over time just 'what happens'?

I wish you would have posted more of your code here. I suspect that the code you posted should be broken out into it's own subroutine and we could have made sure you're using appropriate variable declarations. That being said, I'm only going to address your vlookup method, as you only need one or the other and I don't believe the find method is a good idea.

Per my comment, this code becomes slower because each time you add a formula via Data.Cells(DataRow, 4) = Format((Data.Cells(DataRow, 2) - Result) / Result, "0.00%"), Excel will recalculate all of the formulas in the spreadsheet. Prior to executing this code, you should set calculation to manual with Application.Calculation = xlCalculationManual.

If you don't have an error handler, you will need to add one so you can ensure that calculation is always set back to automatic with Application.Calculation = xlCalculationAutomatic. If you set it to manual, and then an error happens (without a handler), your workbook could cause you some confusion because it's not updating values when you think it should. You would also want to make sure to execute Application.StatusBar = False should any error happen. You don't want the status bar to get "stuck" if an error happens.

Some other things:

I'm not a fan of the PascalCase variable names. They should be camelCase to avoid confusion with class properties.
You don't need = True in IsError(Result) = True. It can simply be If IsError(result) Then.
That same If statement contains some duplication. It can be simplified as below.

If (IsError(result)) Or (result = 0) Then
    Data.Cells(dataRow, 3) = "No Old Cost"
Else
    Data.Cells(dataRow, 3) = Result
    Data.Cells(dataRow, 4) = Format((Data.Cells(dataRow, 2) - Result) / Result, "0.00%")
End If

dataRow = dataRow + 1

Note that I also moved the variable incrementor outside of the If block. This also fixes what I believe is a bug that was causing you to skip rows. If you meant to skip rows, increment by two instead.
You're releasing the CPU to the OS at an inopportune time. Typically, DoEvents should come directly after you update the status bar. If you're concerned about saying it's at 100% while the code is still working, move the update to the end of the loop instead.
Unless you really feel like that status bar is needed, you should remove it. It's a performance hit as well. It sounds like you do need it though. Processing 70k rows takes some time and you don't want your users to think the program isn't responding.

The good stuff:

Thank you for ignoring Microsoft's recommendation to use hungarian notation!
Your variable names are clear and concise. No confusion about what is what. Well done.


Chemical scheme calculator This code implements an algorithm for calculation of chemical schemes. This code looks strange but now I have no idea how to refactor it. Can you give your feedback?

eps=0.001;

s1=new Source(1000,0.17);
mx=new Mixer(1000);
mb=new Mem(0.15,0.95);
sp=new Splitter(0.80);
s2=new Sink();
s3=new Sink();

mx.in1=s1.out1;
mx.in2=sp.out2;
mb.in1=mx.out1;
sp.in1=mb.out2;
s3.in1=sp.out1;
s2.in1=mb.out1;

for (i=0;i<50;i++){
    mx.calc();
    mb.calc();
    sp.calc();
}

function Stream(v,c){
    this.v=v||null;
    this.c=c||null;
    this.selfCheck=false;
    this.Show=function(){//how to add default values?
        return "volume="+this.v+",conc="+this.c+",selfCheck:"+this.selfCheck+"; ";
    }
}

function Source(v,c){
    this.out1=new Stream(v,c);
    this.calc=function(){};
}
function Sink(){
    this.in1=null;
    this.calc=function(){};
}

function Mixer(fixedV){
    this.fv=fixedV;
    this.in1=null;
    this.in2=null;
    this.out1=new Stream();
    this.calc=function(){
        this.out1.v=this.fv;//||this.in1.v+this.in2.v;
        this.in2.v=this.in2.v||0;
        this.in2.c=this.in2.c||0;
        this.in1.v=this.out1.v-this.in2.v;
        this.out1.c =(this.in1.v*this.in1.c+this.in2.v*this.in2.c)/this.out1.v;
        this.out1.selfCheck=Math.abs
        ((this.in1.v*this.in1.c+this.in2.v*this.in2.c)-(this.out1.v*this.out1.c))<eps;
    }
}

function Splitter(kS){
    this.in1=null;
    this.ks=kS||0.05;
    this.out1=new Stream();
    this.out2=new Stream();
    this.calc=function(){
        this.out1.v=this.in1.v*(1-this.ks);
        this.out2.v=this.in1.v*(this.ks);
        this.out1.c=this.in1.c;
        this.out2.c=this.in1.c;
    }

}

function Mem(kV,kC) {
    this.kv = kV||0.15;
    this.kc = kC||0.95;
    this.in1 = null;
    this.out1 = new Stream();
    this.out2 = new Stream();
    this.calc = function () {
        this.out1.v = this.in1.v * this.kv;
        this.out1.c = this.in1.c * (1 - this.kc);
        this.out2.v = this.in1.v * (1 - this.kv);
        this.out2.c = (this.in1.v * this.in1.c - this.out1.v * this.out1.c) / this.out2.v;
        this.out1.selfCheck = this.out2.selfCheck = Math.abs
        (this.in1.v * this.in1.c - (this.out1.v * this.out1.c + this.out2.v * this.out2.c)) < eps;

    }
}

A couple of format rules like:

Is a good practice declare first and then use it. Is not a big deal, but is a good practice.
Try to use, Pascal Case for constructors, and camelCase for methods.
You can replace some repeated function with inheritance javascript

Also, try to don´t abuse of the this. In javascript is a little tricky and can be changed depending of the context.
For default values use

var something = original Value || default Value;

also, last thing most important for your calculator, take a look to the javascript floating points troubles maybe you can get wrong results.


A "map" function that alternates between two mapping functions I am trying to solve following problem in Haskell using recursion:

  Define a recursive function funkyMap :: (a -> b) -> (a -> b) -> [a] -> [b] that takes as arguments two functions f and g and a list xs, and applies f to all elements at even positions [0, 2..] in xs and g to all elements at odd positions [1, 3..] in xs.

Example: funkyMap (+10) (+100) [1, 2, 3, 4, 5] = [(+10) 1, (+100) 2, (+10) 3, (+100) 4, (+10) 5].

I came up with following solution:

h1 p q [] = []
h1 p q ((cnt, val) : xs) = (if odd cnt then (q val) else (p val) ) : h1 p q xs

funkyMap f g xs = h1 f g ( zip [0..] xs)

If I try funkyMap (+10) (+100) [1, 2, 3, 4, 5] I get [11,102,13,104,15] which is expected.

Also funkyMap (+100) (+2) [1] gives [101]

and funkyMap (+100) (+2) [] gives []

Please review this solution and let me know your feedback.

So, like @pigworker has said your code looks functionally good to me, but you don't have to break up your solution into two parts like this or create a data structure you don't need.

You might find a better solution using a different approach (pattern matching):

funkyMap :: (a -> b) -> (a -> b) -> [a] -> [b]
funkyMap p q [] = []
funkyMap p q [x] = [p x]
funkyMap p q (x : y : xs) = p x : q y : funkyMap p q xs

The real benefit of this is you don't have to create any intermediate data structures.

The idea behind this solution is to let pattern matching do the hard work for you. Really you have 3 senarios for your function

when there are no elements in the list (where you probably just want to return the empty list)
when you have just one element in the list (where you just want to apply p to the element)
when you have 2 or more elements in the list (where you apply p and q, then use recursion to evaluate the rest of the list)

Using pattern matching lets you wrap that logic up in a really obvious way


Sum of primes program is taking too long I don't understand what is taking the program so long:

#!/bin/python

primes=[]
i=0
j=0
k=0

for i in range(2,2000000): #fill in the list
    primes.append(i)

i=0
while i<len(primes):
    j=primes[i]
    print(j)
    k=0
    while j*(j+k)<primes[len(primes)-1]: ##referred as 'line A'
        try:
            primes.remove(j*(j+k))
        except ValueError:
           k=k+1
           continue
        k=k+1
    i=i+1

sump=0
i=0
for i in range(len(primes)):
    sump=sump+primes[i]

print(sump)

I understand why the overall code is very inefficient, but line A takes 2 hours for j=2, and I don't understand why that is. Surely the list.remove(x) method is very inefficient?

I don't believe it is actually the specific Lne A that is the problem, but everything that is happening inside that loop, and most importantly, the line: primes.remove(...). From this StackOverflow answer you can see that remove(...) is an O(n) operation, thus it's performance is relative to the amount of data in the array. In this case, there's a lot.... and you are doing a lot of removes() since you are essentially removing all even values except 2.

What you should be doing is using a more efficient algorithm. You should read up on the Sieve of Eratosthenes, and introduce that algorithm here.

it will be much faster because it does not do any array-size changes. There are a number of posts here on CodeReview that have this problem solved quite nicely:

Sieve of Eratosthenes: making it quicker
Project Euler: primes in Python

(Primes in Python...)

(Sieve in other languages)


Creating a server for user Internet orders I've been learning the basics of node over the last couple of days and finally hooked up what I needed.  I'm just after someone to comment on if I have gone the right way around this task.

It creates a server which users access to get updates to Orders through server side events.
The events are published through redis which I subscribe to the queue.

var redis = require('redis'),
    http = require('http'),
    os = require("os"),
    PHPUnserialize = require('php-unserialize');

function sendServerSendEventForInternetOrders(req, res) {
    req.socket.setTimeout(0); // let request last as long as possible
    var hostname;
    if(os.hostname() == "kipos"){
        hostname = os.hostname()+".dev";
    }else{
        hostname = os.hostname();
    }
    res.writeHead(200, {
        'Content-Type': 'text/event-stream',
        'Cache-Control': 'no-cache',
        'Connection': 'keep-alive',
        'Access-Control-Allow-Origin': 'http://'+hostname
    });

    res.write('\n');

    var phpSession = req.url.match('\/internetOrders\/(.*)')[1];

    console.log(phpSession + " - created client");
    var redisClient = redis.createClient();

    // In case we encounter an error...print it out to the console
    redisClient.on("error", function (err) {
        console.log(phpSession + " - Redis Error: " + err);
    });

    var phpSession = req.url.match('\/internetOrders\/(.*)')[1];

    var taID;
    var takeaway;

    redisClient.get("PHPREDIS_SESSION:" + phpSession, function (err, reply) {
        if (reply != null || err != null) {
            taID = PHPUnserialize.unserializeSession(reply).LoggedIn.TaID;
            console.log(phpSession + " - " + taID);
            startSub();
        } else {
            res.end();
            console.log(phpSession + " - exit");
        }
    });
    function startSub() {
        redisClient.select(1, function () {
            redisClient.get(taID + "T", function (err, reply) {
                if (reply == null) {
                    res.end();
                    console.log(phpSession + " - exit");
                    return;
                }
                takeaway = JSON.parse(reply);
                console.log(phpSession + " - "+takeaway.TaWebName);
            });

            redisClient.subscribe(taID + "IOU");

            // When we receive a message from the redis connection
            redisClient.on("message", function (channel, message) {
                sendMessage(message);
            });

            req.on("close", function () {
                redisClient.unsubscribe();
                redisClient.quit();
                console.log(phpSession + " - exit");
            });
        });
    }
    function sendMessage(data){
        res.write("data: " + data + '\n\n'); // Note the extra newline
        console.log(phpSession + " - data: " + data);
    }
};

http.createServer(function (req, res) {
    console.log(req.url);
    if (req.headers.accept && req.headers.accept == 'text/event-stream') {
        if (req.url.match('\/internetOrders\/(.*)')) {
            sendServerSendEventForInternetOrders(req, res);
        }
        else if (req.url == '/windowsApp') {
            res.writeHead(404);
            res.end();
        }
        else {
            res.writeHead(404);
            res.end();
        }
    } else {
        res.writeHead(200, {'Content-Type': 'text/plain'});
        res.end("Hello Kipos!"); // Kept this in for checking node server is up!
    }
}).listen(8080);

One thing that you could change is the way that this if else statement is written

var hostname;
if(os.hostname() == "kipos"){
    hostname = os.hostname()+".dev";
}else{
    hostname = os.hostname();
}

Here you are deciding what a variables value should be using an if/else statement, this is a good spot to use a JavaScript ternary operator.

Example Ternary Statement:

var variableName = red == blue ? trueValueAssignment : falseValueAssignment;

so your code would look like this

var hostname = os.hostname() == "kipos" ? os.hostname() + ".dev" : os.hostname();


Using range minimal query for lowest common ancestor (LCA) -- part 2 Here is my code to use range minimal query to resolve the LCA problem. I applied comments from here.

Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated.

Major ideas of my idea are:

Build depth array of each node by in-order traverse
Build MRQ index for depth array built in first step
For any two nodes, their LCA are the lowest depth node between them (in depth array)

from collections import defaultdict
class TreeNode:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    def in_order_traverse(self, result, depth, node_index_map):
        if self.left:
            self.left.in_order_traverse(result, depth+1, node_index_map)
        result.append((depth, self.value))
        node_index_map[self.value] = len(result) - 1
        if self.right:
            self.right.in_order_traverse(result, depth+1, node_index_map)
class RMQ:
    def __init__(self, raw_array):
        self.rmq_index = defaultdict(tuple)
        step = 0
        for i,v in enumerate(raw_array):
            self.rmq_index[(i, step)] = v
        step += 1
        while 2 ** (step-1) <= len(raw_array):
            for i,v in enumerate(raw_array):
                if i+2**(step-1) < len(raw_array) and self.rmq_index[(i+2**(step-1), step-1)][0] < self.rmq_index[(i, step-1)][0]:
                    self.rmq_index[(i,step)] = self.rmq_index[(i+2**(step-1), step-1)]
                else:
                    self.rmq_index[(i,step)] = self.rmq_index[(i, step-1)]
            step += 1
    def rmq_query(self, i, j):
        step = 0
        while i + 2 ** step - 1 < j:
            step += 1
        step -= 1
        x = self.rmq_index[(i,step)]
        y = self.rmq_index[(j-2**step+1, step)]
        if x[0] < y[0]:
            return x[1]
        else:
            return y[1]
if __name__ == "__main__":
    root = TreeNode(1, TreeNode(2, TreeNode(4, None, None), TreeNode(5, None, None)), TreeNode(3, TreeNode(6, None, None),TreeNode(7,None,None)))
    result = []
    node_index_map = defaultdict(int)
    root.in_order_traverse(result, 0, node_index_map)
    rmq = RMQ(result)
    print rmq.rmq_query(node_index_map[4], node_index_map[5])
    print rmq.rmq_query(node_index_map[4], node_index_map[7])

advice on ... code style

Including docstrings would be good, e.g. to spell out that RMQ denotes Range Minimal Query.
But as a more pressing matter, your identifiers are much too ambiguous.
The names rmq_index or node_index_map are just not helpful as you never describe an index, and result and raw_array are even worse. At least stick to one or the other, don't use both of them to describe the same thing.
Not once did you refer to the literature (e.g. Schieber and Vishkin), nor comment on an invariant you were maintaining.

It would be helpful to include sample in/out values in the SO posting or, better, in the comments or docstrings. You regrettably ignored the advice to use flake8.

    self.value = value

This appears to be more of a unique id than some continuous value.

    for i,v in enumerate(raw_array):

This may have been clearer as for i, depth_id.

It's not clear how a step is different from a depth.

In ... self.rmq_index[(i+2**(step-1), step-1)][0] < self.rmq_index[(i, step-1)][0]: it would have been helpful to break out depth_left & depth_right and compare them.

These look like they are useful tests:

print rmq.rmq_query(node_index_map[4], node_index_map[5])
print rmq.rmq_query(node_index_map[4], node_index_map[7])

but they would be far more informative in the form of assertEqual statements in a unittest.TestCase.


getword that properly handles undersores, string constants, comments, or preprocessor control lines Our version of getword does not properly handle underscores, string constants, comments, or preprocessor control lines. Write a better version.

This is the exercise 6-1 and can be foud on K&R 2 at page 150.
http://net.pku.edu.cn/~course/cs101/2008/resource/The_C_Programming_Language.pdf

My solution:

static int isValidKeyWord(char c) {
    if(isalnum(c) || c == '_') {
        return 1;
    }
    return 0;
}

int getword(char *word, int lim) {
    int c;
    char *w = word;

    int ordinaryKeyWord = 0;
    int comment         = 0;
    int stringConstant  = 0;

    while(isspace((c = getch())))
        ;

    if(c == '#' || c == '_' || isalpha(c)) {
        ordinaryKeyWord = 1;
        *w++ = c;
    }
    else if(c == '/') {
        *w++ = c;
        c = getch();
        if(c == '*') {
            *w++ = c;
            comment = 1;
        }
        else {
            *w = '\0';
            return *--w;
        }
    }
    else if(c == '\"') {
        *w++ = c;
        stringConstant = 1;
    }
    else {
        *w++ = c;
        *w = '\0';
        return c;
    }

    for(; --lim; w++) {
        *w = getch();
        if(ordinaryKeyWord && (!isValidKeyWord(*w))) {
            ungetch(*w);
            break;
        }
        else if(stringConstant && *w == '\"') {
            w++;
            break;
        }
        else if(comment && *w == '*') {
            *++w = getch();
            if(*w == '/') {
                w++;
                break;
            }
            else {
                ungetch(*w);
                w--;
            }
        }
    }

    *w = '\0';
    return word[0];
}

There are 3 main cases:

case 1: comments, if the first two characters are / and *. In this case the function should return when the corresponding * and / are met.
case 2: string constants, if the first character is a ", then the function should return when the closing " is met.
case 3: words that begin with #, _ and letters. In this case, the program should return when a character different that _ or an alphanumeric character is met.

First, the program analyzes which case is. Based on that, "it knows" when to stop, then  it returns the first character of that word.

I don't didn't immediately see a bug in it and you're doing a lot of things well; so some minor comments.

while(isspace((c = getch())))
    ;

This will often cause a compiler warning "possible missing or empty statement". If you use a compound statement instead that may suppress that warning:

while(isspace((c = getch()))) { }

int ordinaryKeyWord = 0;
int comment         = 0;
int stringConstant  = 0;

These are mutually exclusive, so a 3-valued enum might be better.

for(; --lim; w++)

I don't think your lim testing is strict enough: for example if lim is 8 then /*this*/ would overrun (write past the end of) the input buffer; even an ordinaryKeyWord will write its last '\0' past the end of the buffer.

return *--w;

That's a bit tricky. It would be clearer to return word[0]; everywhere consistently.

    if(ordinaryKeyWord && (!isValidKeyWord(*w))) {
        ungetch(*w);
        break;
    }

That's compact (few lines) but could be expanded to make the logic clearer for a tired reviewer:

    if(ordinaryKeyWord) {
        if (isValidKeyWord(*w)) {
            continue;
        }
        ungetch(*w);
        break;
    }
    if (stringConstant) {
        ... break or continue ...

else if(c == '/') {
    *w++ = c;
    c = getch();
    if(c == '*') {
        *w++ = c;
        comment = 1;
    }
    else {
        *w = '\0';
        return *--w;
    }

You're missing ungetch in the else case.

Is there any way to show end-of-input: pressing <Ctrl>-D for EOF for example? If so, how does getword signal that?

I don't know an easy way to automate code which reads from the keyboard using getch and ungetch.

That's a pity because I'd like to see the automated unit tests which define how well your code works.

For example, this question includes its unit tests: 6 different tests of the function being coded. I was able to identify one or two bugs in the function, not by reading the function but by reviewing the set of unit tests, to find a condition (a set of input data) that wasn't being tested.

My boss wasn't a programmer but used to user-acceptance-test the software before shipping it: he said, not 'you get what you expect' but "You get what you INspect".

Especially when you're beginning you should learn to do unit testing, and take pride in constructing a good/complete set of test cases, which is able to detect bugs in the earlier versions of your software.


Finding sum of sub vector satisfying inequality I am asked to implement code that checks if there is a sub vector that has a sum, v_l, that would satisfy \$ \frac{1}{4}mn + 1 \leq v_l \leq v - \frac{1}{4} m n - 1\$.

def possible(vec, m):
    n = len(vec)     # Number of columns
    v = sum(vec)
    global R

    R = []

    num = {i: 0 for i in set(vec)}
    for i in vec:
        num[i] += 1

    solution = dfs_backtrack(num, m, n, v)

return solution

def dfs_backtrack(vec, m, n, v):

    v_l = sum([i*vec[i] for i in vec.keys()])
    R.append(vec)

    if 0.25 * m * n + 1 <= v_l <= v - 0.25 * m * n - 1:
        return vec

    for i in vec.keys():
        temp = dict(vec)
        temp[i] -= 1
        if temp[i] is 0:
            temp.pop(i)
        if temp and temp not in R :
            temp = dfs_backtrack(temp, m, n, v)
        else:
            temp = None
        if temp:
            return temp
    return None

From my analysis it would have a space and time complexity of \$O(n^{m+1} m^{-m-1})\$, where \$1 \leq m \leq n\$. What can I do to improve the space and time complexity?

Since the sum v_l changes with each iteration through your dictionary values of num, I don't know of a way to pre-compute the right-side sums before-hand. This would be a little easier if you could use external modules. That said, you might see a slight speed-up if you use more comprehensions. For example, you can get num via num = {x : vec.count(x) for x in vec}. Also, use == 0 (not is 0) to check zero equality and use is None(not == None) to check None.

Also, you are iterating through all possible combinations. In the case of using votes1 and m1, you know that m = m1 = 10 and n = len(votes1) = 30. So you know that your lower bound is cut-off at 76. Those are 76 permutations that you do not need to use. You can include a break statement at the lower bound since you are incrementing downward (temp[i] -= 1), but I would instead use this lower bound as the starting point and iterate by incrementing upward as you may find some other way to restrict the sums in the upper limit.

Lastly, the use of globals and non-descriptive variable names makes it hard to edit the code. For example, votes instead of vec, ndict instead of n, etc. Also, you can pass R into dfs_backtrack.

I personally prefer iterating over lists instead of dictionaries since you can use zip. I don't have a full solution for your problem, but it may help as a start.

def get_lower_bound(m, n):
    return m*n/4 + 1

def get_upper_bound(m, n, v):
    return v - m*n/4 - 1

def initialize_constants(m, n, votes):
    """ Pre-compute these values as they do not change."""
    size = len(votes)
    total = sum(votes)
    lower_bound = get_lower_bound(m, n=30)
    return size, total, lower_bound

def initialize_vl(votes, m):
    ## I think set look-ups are quickest, these provide unique values just like dictionaries do
    unique_votes = list(set(votes)) #keys for num
    vcounts = [votes.count(x) for x in unique_votes] #vals for num
    vl = sum([a*b for a,b in zip(unique_votes, vcounts)])
    return unique_votes, vcounts, vl

This way, you don't need to use

    temp = dict(vec)
    temp[i] -= 1
    if temp[i] is 0:
        temp.pop(i)
    if temp and temp not in R :

as you are creating temp as a copy of vec; any change to temp changes vec as well. Also, you can iterate through your unique values in list(set(...)) instead of checking if each element is in R.

Sorry I could not be of more help. Let me know if anything is unclear.


Squaring the two digits in the middle of a four-digit number I got a four-digit positive number. I need to square the two digits in middle to generate a new number on which the same procedure is applied. The numbers get saved in a list. This loops as long as there isn't an equal number generated (the list contains the number already). If a number is generated containing less than four digits, the code takes the first and middle digit.

1 23 4
23² = 529
52 9
52² = 2704
2 70 4
70² = ...

I've done the core magic within int current = (int) Math.Pow (number % 1000 / 10, 2);. Is this the most elegant way to solve this?

ArrayList<int> numbers = new ArrayList<int> ();

public void generateNumbers (int number) {

    // just in case :)
    if (number > 9999) {

        throw new ArgumentOutOfRangeException ("Number must be smaller than 10,000");

    }

    // Remove the thousands and get the times 10 fits in (you've only the two numbers in the middle left)
    int current = (int) Math.Pow (number % 1000 / 10, 2);

    // Repeat until an equal number is in the ArrayList
    if (numbers.Contains (current)) {

        return;

    } else {

        numbers.Add (current);
        this.generateNumbers (current);

    }

}

Some thoughts:

1) I would add a check to ensure that the number being passed in, is positive.

2) You don't need to use the return statement in your first if, in fact the first if does nothing. You could simply add a ! to the if statement and if it passes over it the method will terminate anyway.

// Repeat until an equal number is in the ArrayList
if (!numbers.Contains(current)){
    numbers.Add (current);
    this.generateNumbers(current);
}

3) If you decided to go with a larger number and square using more digits you could potentially run into a StackOverflowException since this uses recursion. I would use a helper method to do the actual calculation which would return a number and instead of an if statement use a while. (Of course if you're checking a cap on the number this could never happen since there can only be 100 numbers that will be added.)

How the code could look:

ArrayList<int> numbers = new ArrayList<int> ();

public void generateNumbers (int number) {

    if (number < 0 || number > 9999) {
        throw new ArgumentOutOfRangeException ("Number must be greater than 0 and less than 10,000");
    }

    // Repeat until an equal number is in the ArrayList
    do  {
        number = helper(number);
        numbers.Add(number);
    } while (!numbers.Contains(number))

}

private int helper(int number) {
    // Remove the thousands and get the times 10 fits in (you've only the two numbers in the middle left)
    return (int) Math.Pow(number % 1000 / 10, 2);

}

Now (with a bit of editing) you could extend the method to take as high of a number as the person wants and always square whats in the middle.


Merge arrays in objects in array based on property I have the following code which takes an array that might have duplicate ids and will merge the items of those duplicate, and keep only one element per id which contains all the items of all elements with the same id.

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

const mergeLines = (a) => {
  const processedIds = [];
  const finalResult = [];
  a.forEach((element) => {
    const elementId = element.id;
    if (processedIds.indexOf(elementId) === -1) {
      const occurences = a.filter((el) => el.id === elementId);
      if (occurences.length > 1) {
        const allItems = occurences.reduce((acc, curr) => {
          acc = acc.concat(curr.items);
          return acc;
        }, []);
        element = { ...element,
          items: allItems
        };
        finalResult.push(element);
      } else {
        finalResult.push(element);
      }

      processedIds.push(elementId);
    }
  });
  return finalResult;
};

console.log(mergeLines(array));

I feel this code can be optimized much further to 0(n)

A short review;

This code looks incredibly complicated for what you want to achieve, sometimes a few for loops beat the functional approach
array is a global variable (not var or set or const), that is a bad thing
If a function is not inline, I would encourage you to use the function keyword
I am not sure mergeLines is a great name, perhaps mergeIds ?

array = [{
    id: 1,
    items: [1, 2, 3]
  },
  {
    id: 2,
    items: [1, 2]
  },
  {
    id: 1,
    items: [4]
  },
  {
    id: 3,
    items: [1]
  },
];

function mergeIds(list){
  const out = [];
  for(entry of list){
    const existingEntry = out.find(o => o.id === entry.id);
    if(existingEntry){
      existingEntry.items = existingEntry.items.concat(entry.items);
    } else {
      out.push(entry);
    }
  }

  return out;
}

console.log(mergeIds(array));


Implementing parser combinators in a functional manner I am just starting on my journey of learning clojure (I have just read to the end of chapter 3 in clojure for the brave and true). So for practice, I wrote some parser combinator functions. I am quite familiar with several imperative and object oriented languages, but this is my first time using a lisp language, and my first time programming in the functional paradigms.

How can this code be improved to be more idiomatic clojure code?

How can I condense the sequential parser function? I can write it in 6 lines of python, here it's close to 40 lines.

Also, I am not really sure the commonly accepted way of formatting code, like indentation and bracket placement- is this style commonly used?

Anyways, I welcome any and all feedback.

(ns main.core
  (:gen-class))

; the error message for the parser functions
(def error false)

; Parses a single charactor
(defn lit[c]
  (fn [stream]
    (if (= (first stream) (first (seq c)))
      (list (seq c) (rest stream))
      error
      )
    )
  )

; returns first successful parse
(defn alt[& ps]
  (fn [stream]
    (reduce #(or %1 %2) error (map #(% stream) ps))
    )
  )

; Tries to parse in series, error if any have an error
; This is the python code this function was based on

; It takes in a list of parser functions, tries to run all of them in a row,
; and if any of them fail, returns an error, otherwise it returns the stream,
; which changes each time a parser is run, as well as the results of all the successful parses in a list.

; def SequenceParser(*parsers):
;     def parser(stream):
;         res = []
;         for p in parsers:
;             r, stream = p(stream)
;             res.append(r)
;         return (res, stream)
;     return parser

(defn seqn[& ps]
  (fn [stream]
    (apply
      (defn inner
        ([stm p0]
         (p0 stm)
         )
        ([stm p0 p1]
         ((fn [r0]
            (if r0
              ((fn [r1]
                 (if r1
                   (list (list (nth r0 0) (nth r1 0)) (nth r1 1))
                   error
                   )) (p1 (nth r0 1)))
              error
              )) (p0 stm))
         )
        ([stm p0 p1 & p]
         (def r0 (p0 stm))
         (if r0
           ((fn [r1]
              (if r1
                ((fn [res]
                   (list (list (nth r0 0) (nth r1 0) (nth res 0)) (nth res 1))
                   ) (apply inner (nth r1 1) p))
                error
                ))(p1 (nth r0 1)))
           error
           )
         )
        )
      stream ps)
    )
  )

; Parser that parses as many times as it can, at least once though, or it is an error
(defn many [p0]
  (fn [stream]
    ((fn inner [stm]
       ((fn [res]
          (if res
            ((fn [r1]
               (if r1
                 (list (concat (nth res 0) (nth r1 0)) (nth r1 1))
                 res
                 )
               ) (inner (nth res 1)))
            res
            )) (p0 stm))
       ) stream
     )
    )
  )

; parser that applys a function to the result of another parser
(defn func [p0 f]
  (fn [stream]
    ((fn [res]
       (list (f (nth res 0)) (nth res 1))
       ) (p0 stream))
    )
  )

(defn num-to-int [n]
  (Integer/parseInt (apply str n))
  )

(defn get-val [[res remains]]
  res
  )

(defn -main
  "Main function, this computes the number 1904 from the string '34*56'"
  [& args]

  (def digit (alt (lit "1") (lit "2") (lit "3") (lit "4") (lit "5") (lit "6") (lit "7") (lit "8") (lit "9") (lit "0")))
  (def number (func (many digit) num-to-int))
  (def mul (func (seqn number (lit "*") number), (fn [[a b c]] (* a c))))
  (println (get-val(mul "34*56")))

  )

For reference parser contaminators are functions that generate functions that parse string data. The results of the parser combinators can be combined, hence the name to easily produce complex parsing functions.

http://theorangeduck.com/page/you-could-have-invented-parser-combinators
This is a great read that explains them well if anyone is interested.

I'm going to admit right off the bat here that I've never written a parser using combinator functions before. I have quite a bit of experience with Clojure though, so I'll be primarily focusing on idiomatic Clojure, and proper functional practice.

I have a few main concerns with your code:

You're using def inside of defn! This is a very bad idea. def (and by extension, defn) create(s) globals that persist even after the function they're in has returned! Run your -main, then check what the value of digit is. You're in for a surprise. It's in scope, and has the last value that was assigned to it. From a functional perspective especially, this is bad. def carries out side effects and is leaking the internal state of your functions into the global scope. Use let instead.

Instead of writing:

(def a 1)
(def b 2)
(println (+ a b))

Write:

(let [a 1
      b 2]
  (println (+ a b)))

let creates a restricted scope, and just generally looks much cleaner.
Your brace placement is very reminiscent of imperative style curly brace placement. This is causing a lot of bloat and making your code more verbose than it needs to be.

I'm guessing you're doing this to make matching braces easier for you. If this is the case, don't make your life unnecessarily difficult! Lisps are quite difficult to write unassisted. If you're going to write Clojure, you should spend an afternoon getting familiar with Par-Infer. It infers parenthesis placement based on indentation, so you can write Clojure like it's Python. This is huge. Besides the odd edge case, I never need to manually add a closing brace, or worry about its placement.

I highly recommend IntelliJ with the Cursive plugin; both of which have free community versions. I've been using them for roughly 2 years now, and it's a phenomenal environment to write in.

Just to show the difference, this is what your many function automatically gets formatted as when I paste it into IntelliJ:

(defn many [p0]
  (fn [stream]
    ((fn inner [stm]
       ((fn [res]
          (if res
            ((fn [r1]
               (if r1
                 (list (concat (nth res 0) (nth r1 0)) (nth r1 1))
                 res))

             (inner (nth res 1)))
            res))
        (p0 stm)))
     stream)))

No more needing to carefully place trailing braces to make debugging brace placement issues easier. Just let Par-Infer handle it for you.
Your variable names are bad. Names like r1 and p0 give very little information, and are the kind of names I'd expect to see post-decompilation. For the sake of you and those who may read your code, more descriptive names are a must.
You have what appears to be documentation as comments above your functions. defn has a built-in ability to handle documentation:

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (reduce #(or %1 %2) error (map #(% stream) ps))))

You use this for -main, but nowhere else.

After taking the above suggestions into consideration (except for the variable names), your code would look more like:

(ns main.core
  (:gen-class))

(def error "The error message for the parser functions"
  false)

(defn lit
  "Parses a single charactor"
  [c]
  (fn [stream]
    (if (= (first stream) (first (seq c)))
      (list (seq c) (rest stream))
      error)))

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (reduce #(or %1 %2) error (map #(% stream) ps))))

(defn seqn
  "Tries to parse in series, error if any have an error"
  [& ps]
  (fn [stream]
    (apply
      (letfn [(inner ([stm p0] ; Letfn is the local equivilent of defn
                      (p0 stm))

                     ([stm p0 p1]
                      ((fn [r0]
                         (if r0
                           ((fn [r1]
                              (if r1
                                (list (list (nth r0 0) (nth r1 0)) (nth r1 1))
                                error)
                             (p1 (nth r0 1))))
                           error)
                        (p0 stm))))

                     ([stm p0 p1 & p]
                      (let [r0 (p0 stm)]
                        (if r0
                          ((fn [r1]
                             (if r1
                               ((fn [res]
                                  (list (list (nth r0 0) (nth r1 0) (nth res 0)) (nth res 1))
                                 (apply inner (nth r1 1) p)))
                               error)
                            (p1 (nth r0 1))))
                          error))))])

      stream ps)))

(defn many
  "Parser that parses as many times as it can, at least once though, or it is an error"
  [p0]
  (fn [stream]
    ((fn inner [stm]
       ((fn [res]
          (if res
            ((fn [r1]
               (if r1
                 (list (concat (nth res 0) (nth r1 0)) (nth r1 1))
                 res)

              (inner (nth res 1))))
            res)
         (p0 stm)))
      stream))))

(defn func
  "Parser that applies a function to the result of another parser."
  [p0 f]
  (fn [stream]
    ((fn [res]
       (list (f (nth res 0)) (nth res 1))
      (p0 stream)))))

(defn num-to-int [n]
  (Integer/parseInt (apply str n)))

(defn get-val [[res remains]]
  res)

(defn -main
  "Main function, this computes the number 1904 from the string '34*56'"
  [& args]

  (let [digit (alt (lit "1") (lit "2") (lit "3") (lit "4") (lit "5") (lit "6") (lit "7") (lit "8") (lit "9") (lit "0"))
        number (func (many digit) num-to-int)
        mul (func (seqn number (lit "*") number), (fn [[a b c]] (* a c)))]

    (println (get-val (mul "34*56")))))

These were the main things. Now I'll just comment on more nitpicky things:

nil is more commonly used to represent bad data, instead of false. Also, unless you think you may want to change the value of error later, I'd also just write nil directly instead of labeling it as error. It's generally understood that nil represents the lack of usable data, which appears to be your intent here.

list is most commonly used when writing macros to create code in the macro (because lisps are homoiconic). Consider just using a vector literal ([]) instead unless you absolutely need list behavior:

(list (seq c) (rest stream))

to

[(seq c) (rest stream)]

Some of your functions are huge! I would definitely consider breaking them down. For example, I don't see why inner is defined inside of seqn; it doesn't form a closure over any local variables. From the looks of it, it's quite complicated and makes up the majority of the functionality of seqn. I'd make it it's own function, then have seqn use it. That will leave you with two smaller, easier to test functions. Also, are you sure inner should be a giant function with multiple arities? It wouldn't be cleaner to have it with fewer arities, or even make it multiple smaller functions? Remember, when programming functionally, the function is considered the smallest unit of code. Functions should be as large as necessary, but as small as possible. If you look at my repositories, I have a ton of small, bite-sized functions that each have an extremely focused, narrow scope. This makes testing very easy, and prevents you from needing to go over a giant wall of code making up a function trying to decipher what it's doing in it's entirety.

For num-to-int, long is the native number type that Clojure uses. If you cast to int, it's just going to be converted to long somewhere down the road, and that could potentially lead to a performance hit. You might also want to make it clearer that "n" is actually a seq. Calling the parameter n then writing (apply str n) is very confusing, since I wouldn't expect n to be a sequence. I would change it to:

(defn num-to-int [n-seq]
  (Long/parseLong (apply str n-seq)))

get-val is basically just first. Unless you really like how the name helps readability, I'd just use first.

(alt (lit "1") (lit "2") (lit "3") (lit "4") (lit "5") (lit "6") (lit "7") (lit "8") (lit "9") (lit "0"))

has a ton of repetition. There's a lot of ways to fix this. I'd lean towards something like this though:

(->> "1234567890"
  (map str) ; Turn each char into a string
  (map lit) ; Turn each string into a literal f
  (apply alt)) ; Then give them to alt

Note that even though map is used twice, this only does a single iteration due to laziness! This could also be shortened using comp:

(->> "1234567890"
  (map (comp lit str)) ; Turn each char into a string, then give to lit
  (apply alt)) ; Then give them to alt

Although I find the former more readable.

I'm trusting that your constant return of anonymous functions is necessary for the algorithm. I've never seen so many functions being returned from other functions! If it's necessary, it's necessary, but while trying to debug a issue, I got a mess of an error like this:

  ArityException Wrong number of args (0) passed to: parser-review-fixed/func/fn--1421/fn--1422  clojure.lang.AFn.throwArity (AFn.java:429)

The function inside of the function inside of func threw an arity error! Good luck debugging that!

The recursive call inside of inner inside of many could/should be "optimized". Change:

(inner (nth res 1))

to

(recur (nth res 1))

Use of recur prevents Stack Overflows by essentially making use of Tail-Call Optimization (although, from what I understand, the inner workings are far more complicated than that).

I personally love threading macros (-> and ->> mainly). I'd lean towards writing your alt function as:

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (->> ps
         (map #(% stream))
         (reduce #(or %1 %2) error)))) ; %1 can just be written as %

That's nice (imho), but it's not optimized. reduce actually allows for early exit using reduced! It would be more efficient (but more verbose) to write:

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (->> ps
         (map #(% stream))
         (reduce (fn [acc x]
                   (if x
                     (reduced x)
                     acc))
                 error))))

As soon as an accumulator for reduce becomes reduced, the reduction ends, and the reduced value is returned. This prevents the entire sequence from needing to be checked if, say, the first value is truthy.

But, the core already has a function that basically does this: some. Since you don't need to do any conversion prior to testing for thruthiness though, you can use identity to "forward" the value in place of a predicate. Then alt just becomes:

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (->> ps
         (map #(% stream))
         (some identity)))) ; some returns the first truthy value

I came back to this and realized it can be reduced further! You can get rid of the call to map and make the #(% stream) the predicate of some. This makes it trivial:

(defn alt
  "Returns first successful parse"
  [& ps]
  (fn [stream]
    (some #(% stream) ps)))

Regarding your recent edit clarifying what seqn is doing, these are the two options I'd choose between:

(defn sequence-parser1 [& parsers]
  (fn [stream]
    (reduce (fn [[res acc-stream] p]
              (let [[r stream'] (p acc-stream)]
                [(conj res r) stream']))
            [[] stream]
            parsers)))

(defn sequence-parser2 [& parsers]
  (fn [stream]
    (loop [[p & rest-parsers] parsers
           acc-stream stream
           res []]
      (if p
        (let [[r stream'] (p acc-stream)]
          (recur rest-parsers stream' (conj res r)))

        [res acc-stream]))))

Both are basically the same code; just a reduction over parsers. I tend to lean towards using loop when I have multiple accumulators though, as I find constant pairing/deconstruction in the reducing function to be messy.

If you didn't need to accumulate a stream while iterating the parsers, this could be done very succinctly using map, but alas, that wouldn't work here unfortunately.

WARNING!

I have to admit, I have basically no clue what most of this code is doing, and because of the unidiomatic way that it's written, it confused the hell out of my IDE. Because of the indentation and the constant application of temporary functions, this was extraordinarily difficult to make runnable after I fixed it up. If you try to run that first "touched up" code dump I posted, you'll get an error. There's a mismatched brace somewhere in the seqn I posted, but I can't for the life of me find the issue. Use what I posted here more as a general guide instead of copying and pasting it and trying to use it.


inString() Helper Function - Check if substring is in string I've written a simple helper function for my helper class that allows me to check if a substring is in a string.

With my function, you can supply either a single needle to check for, or an array of needles to check for. There is also a parameter that allows you to select if you want to check word boundries or not, and a parameter to allow you to choose if the search should be case sensitive or not.

public function inString($needle, $haystack, $checkBoundries = false, $caseSensitive = false) {
        if(is_array($needle) && count($needle) < 2)
        {
            $needle = $needle[0];
        }
        if(is_array($needle))
        {
            $pattern = "(".implode("|", $needle).")";
            if($checkBoundries) {
                $pattern = "(\b{$pattern}\b)";
            }
            $pattern = $caseSensitive ?  "/{$pattern}/" : "/{$pattern}/i";
            return preg_match($pattern, $haystack);
        }
        $pattern = $needle;
        if($checkBoundries) {
            $pattern = "(\b{$pattern}\b)";
        }
        $pattern = $caseSensitive ?  "/{$pattern}/" : "/{$pattern}/i";
        return preg_match($pattern, $haystack);
    }

I would love some advice or pointers for my function. Thank you!

I like YourCommonSense's unconditional casting of $needle as an array.

bumperbox's advice on preg_quote() is good and necessary.

bumperbox's patterns will have the desired accuracy because word boundaries (spelled with an 'a') when used with alternatives (|) must wrap each alternative or the alternatives must be grouped.  Otherwise, if you have a pattern like: /\bdog|cat|fish\b/ then doghouse, category, scat, and blowfish will be unintentionally matched.  (Bad Pattern Demo)  In this case, /\b(?:dog|cat|fish)\b/ takes fewer steps than /\bdog\b|\bcat\b|\bfish\b/.

Capture groups () will not be necessary for this task, so use a non-capturing group (?:).  The fullstring match will contain the substring.  Unnecessary capture groups bloat the output array (although only by one element in this case).

Different from the other answers, I have built in a shortcut to a non-regex method.  The rationale behind this is the general knowledge that regex functions are notoriously/usually slower than non-regex functions.  The cost of building the path to the non-regex processes is minimal -- just 3 conditions, only the 2nd condition uses a function call.  I suspect any gains in performance to only manifest when dealing with rather large haystacks.  Regardless, I think it is worth considering.

My function performs more checks than the others to prioritize building a lean, accurate pattern.

My function will return false or the matched needle string.

*For those who might not know the behavior of alternatives in regex, the match will be the alternative found with the lowest "offset".  Regex will not prioritize matching by the order of the alternatives.

Code: (PHP Demo)

function inString($needle, $haystack, $checkBoundaries = false, $caseSensitive = false){
    $needle=(array)$needle;  // unconditionally cast $needle to be an array

    // conditional shortcut to non-regex method:
    if(!$checkBoundaries && sizeof($needle)==1){
        $needle=$needle[0];  // or current($needle) if not indexed
        if(!$caseSensitive){
            return stripos($haystack,$needle)!==false?$needle:false;
        }
        return strpos($haystack,$needle)!==false?$needle:false;
    }

    // build regex pattern
    foreach($needle as &$word){
        $word=preg_quote($word,'/');  // escape regex-sensitive characters
    }
    $pattern=implode('|',$needle);  // pipe together the alternatives
    if($checkBoundaries){
        if(sizeof($needle)>1){
            $pattern="(?:{$pattern})";  // non-capture group required
        }
        $pattern="\b{$pattern}\b";  // word boundaries required
    }
    $pattern="/{$pattern}/";  // add pattern delimiters
    if(!$caseSensitive){
        $pattern.='i';  // case-insensitive modifier required
    }
    // execute pattern and return string on true
    return preg_match($pattern, $haystack, $matches)?$matches[0]:false;
}

Alternatively, if you are seeking pattern accuracy with fewest function calls here is something new to consider:

Code #2: (Demo)

function inString($needle, $haystack, $checkBoundaries = false, $caseSensitive = false){
    $pattern='\Q'.implode('\E|\Q',(array)$needle).'\E';  // build "literal" alternatives
    if($checkBoundaries){
        $pattern="\b(?:{$pattern})\b";  // word boundaries required
    }
    $pattern="/{$pattern}/";  // wrap with pattern delimiters
    if(!$caseSensitive){
        $pattern.='i';  // case-insensitive modifier required
    }
    // execute pattern and return string on true
    return preg_match($pattern, $haystack, $matches)?$matches[0]:false;
}

Running conditional checks on $checkBoundaries and $caseSensitive is completely unavoidable for this task.  This second method will make just one function call: implode() to complete the pattern!

By utilizing an "escape sequence" (\Q and \E), I was able to remove the foreach() loop and iterated call of preg_quote()!  The addition of the escape sequence seems to have no impact on regex step count; it is just a different syntax.  The effect on the pattern is in some cases a visual improvement, and in other cases a detriment to pattern readability (though I don't think pattern readability is a focus for this task).  The above method wraps each alternative in \Q...\E whether it needs it or not.  To contrast, preg_quote() will (only as necessary) add \ before each and every character in its list . \ + * ? [ ^ ] $ ( ) { } = ! < > | : - /.  As I mentioned before either approach risks obfuscating the pattern.
In all fairness, this method builds a less lean pattern than my first method, but you can logically expect that it will construct pattern with the greatest efficiency and with minimal drag from preg_match().


Algorithm that generate all possible strings from N Tuples. Found Brute Force version, Recursive Version uses a Tree? I am trying to figure out a solution for a problem. Consider the following tuples (it could be any number of tuples, I am using four in this example):

{A, B, C, D}
{E, F, G, H}
{I, J, K, L}
{M, N, O, P}

Out of this tuples I have to construct a four-character string, but I can only choose one element from each tuple. Note that if I had \$N\$ tuples, it would be an \$N\$ character string.

The strings "AEIM", "BGLP", "DEIO" are valid examples. The string "EAIM" is not, because the A and E are in the wrong position.

I am able to brute force and get the solution, but there has to be a recursive way to do this... Because brute force does not solve for \$N\$ tuples

String[][] arr = { {"A", "B", "C", "D"}, {"E", "F", "G", "H"}, {"I", "J", "K", "L"}, {"M", "N", "O", "P"} };

String temp;
for(int i = 0; i < 4; i++){

    for (int j = 0; j < 4; j++){

        for (int k = 0; k < 4; k++){

            for (int l = 0; l < 4; l++){

                temp = arr[0][i] + arr[1][j] + arr[2][k] + arr[3][l];
                System.out.println(temp);

            }
        }
    }
}

I am aware that I could use a Tree to recursively solve this, however I do not know how to proceed... Any help is deeply appreciated!

The operation you're looking for is known as a Cartesian product on sets. An implementation of Cartesian product for Java Lists is somewhat as follows (all Lists have the same generic type T, otherwise we have to violate type safety, see below):

import java.util.Set;
import java.util.List;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

class CartesianProduct {
  // Set ensures that entries are unique
  private static <T> Set<List<T>> cartesianProduct2(Set<List<T>> accumulator, List<T> iterable) {
    // LinkedHashSet preserves insertion order, unlike HashSet
    Set<List<T>> product = new LinkedHashSet<>();
    for(List<T> elementAccumulator : accumulator) {
      for(T item : iterable) {
        // copy-on-write to ensure we don't change the arguments
        List<T> newElementAccumulator = new LinkedList<>(elementAccumulator);
        newElementAccumulator.add(item);
        product.add(newElementAccumulator);
      }
    }
    return product;
  }

  @SafeVarargs
  public static <T> Set<List<T>> cartesianProduct(List<T>... iterables) {
    // accumulator for fold
    Set<List<T>> product = new LinkedHashSet<>();
    // initialize accumulator to first iterable
    for(T item: iterables[0]) {
      // maintain the structure of the data
      List<T> elementAccumulator = new LinkedList<>();
      elementAccumulator.add(item);
      product.add(elementAccumulator);
    }
    // fold the rest of the iterables under the dyadic Cartesian product operation
    for(int i = 1; i < iterables.length; ++i) {
      product = cartesianProduct2(product, iterables[i]);
    }
    return product;
  }

  public static void main(String[] args) {
    List<String> set1 = Arrays.asList(new String[]{"A", "B", "C", "D"}),
                set2 = Arrays.asList(new String[]{"E", "F", "G", "H"}),
                set3 = Arrays.asList(new String[]{"I", "J", "K", "L"}),
                set4 = Arrays.asList(new String[]{"M", "N", "O", "P"});

    List<String> output1 = new ArrayList<>();
    for(List<String> item : cartesianProduct(set1, set2, set3, set4)) {
      output1.add(String.join("", item));
    }

    String[][] arr = { {"A", "B", "C", "D"}, {"E", "F", "G", "H"}, {"I", "J", "K", "L"}, {"M", "N", "O", "P"} };

    List<String> output2 = new ArrayList<>();
    for(int i = 0; i < 4; i++){
      for (int j = 0; j < 4; j++){
        for (int k = 0; k < 4; k++){
          for (int l = 0; l < 4; l++){
               output2.add(arr[0][i] + arr[1][j] + arr[2][k] + arr[3][l]);
          }
        }
      }
    }
    System.out.println("Actual -> Expected");
    for(int i = 0;i < Math.min(output1.size(), output2.size()); ++i) {
      System.out.println(output1.get(i) + " -> " + output2.get(i));
    }
    System.out.println(output1.size() == output2.size());
    System.out.println(output1.equals(output2));
  }
}

Unfortunately, this is more of a code dump, but this is the same thing itertools.product does in Python, and here's a more succinct Scala version of the core idea:

def cartesianProduct[S](vectors: Traversable[S]*): Traversable[Seq[_]] =
    cartesianProductMultiType(vectors)

  def cartesianProductMultiType(vectors: Traversable[Traversable[_]]): Traversable[Seq[_]] = {
    def cartesianProduct2[A, B](leftVector: IndexedSeq[IndexedSeq[A]], vector2: Traversable[B]): IndexedSeq[IndexedSeq[_]] =
      for {
        superSequence <- leftVector
        element <- vector2
      } yield superSequence :+ element

    vectors.foldLeft(IndexedSeq(IndexedSeq[Any]()))(cartesianProduct2(_, _)).distinct
  }

(This is in fact what I translated into Java, having coded this much earlier for a personal project).

This is not as memory-efficient as @coderodde's iterator version, but it is algorithmically simpler and easier to understand, I hope.

I put in a few tests in main so that you can check that this code does the same thing as yours.

Note that here you can replace the List<T> iterable and List<T>... iterables with Iterable<T> iterable and Iterable<T>... iterables to get an even more general version of the code which can find the Cartesian product of any collection of Iterables. Here, you should also swap

for(List<T> elementAccumulator : accumulator) {
      for(T item : iterable) {
          ...
      }
}

to

for(T item : iterable) {
      for(List<T> elementAccumulator : accumulator) {
          ...
      }
}

to ensure that you don't consume the iterator of iterable multiple times - creating the iterator might be expensive or slow, say reading from a file. This'll make the output come out in a different order from what you give us - it'll be a post-order traversal instead of a pre-order one (see below).

Since @coderodde has already addressed the main point of iterators and memory-efficiency, this is more educational as you were asking for a recursive solution. Although this particular solution is not recursive, it does utilize the concept of divide-and-conquer with a base case, so it should be helpful to you.

About trees: see if you can recognize the tree structure in this program.

Hint: it is a balanced \$n\$-level tree where \$n\$ is the number of tuples, with each node having \$\left|T_i\right|\$ children, where \$\left|T_i\right|\$ denotes the number of elements in tuple \$T_i\$. In fact, the \$i^\text{th}\$ level is just the elements of \$T_i\$ repeated as the children of every node of level \$i-1\$. The output of this program is a depth-first search with pre-order traversal of this tree, splitting the output into words at each backtrack (recursion unwind). The output at any given point during the execution is the path traversed in the tree till that point.

An exercise - try writing a program which explicitly makes this tree and prints every path from each root to each leaf, splitting the output into words at each backtrack.

Here's an example tree for the set of tuples {('A','B'), ('C', 'D'), ('E', 'F'})} (note how each required word is the pre-order path from the empty root to a leaf):

Also, take a look at these data structures - Trie and Suffix Tree.


Getting the smallest snippet from content containing all keywords This returns the smallest snippet from the content containing all of the given keywords (in any order). This provides the correct solution but I would like to know if it can be made more efficient.

import itertools, re

def solve(content, keywords):
    content = content.strip()
    contentWords = content.split()
    termPosition = {}
    for term in keywords:
        index = 0
        positions = []
        while index is not None:
            try:
                index = contentWords.index(term)
                positions.append(index)
                contentWords[index] = None
            except:
                index = None
        termPosition[term] = positions
    singlePositions = []
    multiplePositions = []
    for term in termPosition.keys():
        if len(termPosition.get(term)) == 1:
            singlePositions.append(termPosition.get(term)[0])
        else:
            multiplePositions.append(termPosition.get(term))
    snippet = content
    contentWords = content.split(' ')
    for element in itertools.product(*multiplePositions):
        tempList = list(element) + singlePositions
        minPos = min(tempList)
        maxPos = max(tempList) + 1
        if len(' '.join(contentWords[minPos:maxPos])) < len(snippet):
            snippet = ' '.join(contentWords[minPos:maxPos])
    return snippet

First, going over your code

import itertools, re

re is not used

contentWords = content.split()

I would be more explicit on the split, calling split(' ') so your intentions are crystal clear

index = contentWords.index(term)

Each call to this is an O(n) operation on the list, m times where m is the number of times the element occurs, x times where x is the number of keywords. So in big O (and worst case) we have O(nmx). We can be smarter about this, and do it in O(n) and in one iteration. We will use extra memory to store the keywords in a dict

So replacing this:

termPosition = {}
for term in keywords:
    index = 0
    positions = []
    while index is not None:
        try:
            index = contentWords.index(term)
            positions.append(index)
            contentWords[index] = None
        except:
            index = None
    termPosition[term] = positions

With:

# Create an empty list for each keyword
# We could achieve the same result with a defaultdict
termPosition = {keyword: [] for keyword in keywords}
# enumerate gives us the indexes of the word
for index, word in enumerate(contentWords):
    # if the word is a keyword, record the index
    if word in termPosition:
        termPosition[word].append(index)

for term in termPosition.keys():
    if len(termPosition.get(term)) == 1:
        singlePositions.append(termPosition.get(term)[0])
    else:
        multiplePositions.append(termPosition.get(term))

You don't need to work out the values from the keys. Also .append(x[0]) for a list of size one is the same as extending by that list. (You can concat lists with either += or .extend)

for positions in termPosition.values():
    if len(positions) == 1:
        singlePositions += positions
    else:
        multiplePositions.append(positions)  # Keeping it as a list of lists

    contentWords = content.split(' ')

No longer needed since we don't modify contentWords

for element in itertools.product(*multiplePositions):
    tempList = list(element) + singlePositions
    minPos = min(tempList)
    maxPos = max(tempList) + 1
    if len(' '.join(contentWords[minPos:maxPos])) < len(snippet):
        snippet = ' '.join(contentWords[minPos:maxPos])

This is going to be the main slowdown of your code as product means factorial growth. I can't think of something that does this better right now, but I'll come back if I do find one. The issue at hand is that it isn't the shortest range of indexes which contain all the keywords, it is the shortest snippet. The words might vary in length, giving each index a weight. In addition, spaces mean it isn't the smallest sum of weights, it is the min sum of weights plus number of additions used.
You could create a list of the length of each word in contentWords, and find the min sum(contentWordsLens[minPos:maxPos] + (maxPos - minPos)). The should be more performant as you are adding numbers instead of strings
As for the code, there are a couple of tricks to squeeze down the time

# The min and max from singlePositions never change
# We convert the single value to a tuple to avoid doing repeatedly in the loop

minSinglePositions = tuple(min(singlePositions))
maxSinglePositions = tuple(max(singlePositions))
minSnippetLen = len(snippet)
for element in itertools.product(*multiplePositions):
    minPos = min(element + minSinglePositions)
    maxPos = max(element + maxSinglePositions) + 1
    candidate = ' '.join(contentWords[minPos:maxPos])
    if len(candidate) < minSnippetLen:
        snippet = candidate
        minSnippetLen = len(snippet)

The main improvements come from moving any work that is constant to outside the loop. We also avoid repeating work like working out the length of the snippet. For this kind of tricking about, profiling should be done to test the function.

A final note, there are two parts to the function, getting the indexes, and checking which combination is the shortest. As such, we can move them to two functions.

A cleaner version of the submitted code:

import itertools

def get_positions(content, keywords):
    termPosition = {keyword: [] for keyword in keywords}
    # enumerate gives us the indexes of the word
    for index, word in enumerate(content):
        # if the word is a keyword, record the index
        if word in termPosition:
            termPosition[word].append(index)

    singlePositions = []
    multiplePositions = []
    # Note, if any of the positions are of len 0, the keyword isn't in the snippet
    # This should be raised. As it is currently, it returns the input snippet
    for positions in termPosition.values():
        if len(positions) == 1:
            singlePositions += positions
        else:
            multiplePositions.append(positions)  # Keeping it as a list of lists

    return singlePositions, multiplePositions

def get_shortest_snippet(content, contentWords, singlePositions, multiplePositions):
    # The min and max from singlePositions never change
    # We convert the single value to a tuple to avoid doing repeatedly in the loop
    if singlePositions:
        minSinglePositions = tuple(min(singlePositions))
        maxSinglePositions = tuple(max(singlePositions))
    else:
        minSinglePositions = tuple()
        maxSinglePositions = tuple()

    snippet = content
    minSnippetLen = len(snippet)

    for element in itertools.product(*multiplePositions):
        minPos = min(element + minSinglePositions)
        maxPos = max(element + maxSinglePositions) + 1

        candidate = ' '.join(contentWords[minPos:maxPos])
        if len(candidate) < minSnippetLen:
            snippet = candidate
            minSnippetLen = len(snippet)

    return snippet

def solve(content, keywords):
    # Input
    content = content.strip()
    contentWords = content.split(' ')

    singlePositions, multiplePositions = get_positions(contentWords, keywords)
    shortestSnippet = get_shortest_snippet(content, contentWords, singlePositions, multiplePositions)
    return shortestSnippet


Get table header name in excel I'm trying to get table header name in excel. I tried it using index, IF and MATCH. It works but I am not sure whether my formula is the best or not.

This is how my sheet looks:

And here is my formula to get produk name (E19:E22):

=INDEX(
   $C$10:$H$10,0,
      IF(IFERROR(MATCH(D19,$C$12:$C$14,0),0),1,
      IF(IFERROR(MATCH(D19,$E$12:$E$14,0),0),3,
      IF(IFERROR(MATCH(D19,$G$12:$G$14,0),0),5,0
))))

You have hard-coded the 1, 3 and 5 column index... and you don't really have a choice, given the shape of your data.

The problem is that your table is not a table: it's essentially a pivot. This would be a table:

If you can un-pivot your top table into an actual table like above, then you could have a much simpler, easier to read (and to maintain!) table formula - given a Table1 table name for the above table:

=INDEX(Table1[Category],MATCH([@Id],Table1[Id],0))

Excel likes data that's organized in rows and columns; if you have 2 levels of headings, and repeating columns under each heading, you haven't organized your data in rows and columns, and you've set yourself up for complicated lookups - as you've noticed.

By laying out your data in a table, you make a database-friendly list of records that can easily be sourced from a CSV or XML file, or directly from a database table or view.

Having 3 times the same [Id] and [Name] columns under a different heading, looks like you have 3 identical tables, with different values: by combining them into one (and adding a column to identify which of the 3 tables it's coming from), lookups become much, much simpler.

Other than that, I would add the following:

The bottom table should be turned into an actual table, so leverage table formulas. D19 would then say [@Id], which is much easier to understand.
The top table should be on its own worksheet, and adding rows in that table should not force you to update the formulas in the bottom one - as it stands, you'll have to be careful about that.
If you can't turn the top table into an actual table, consider using named ranges to abstract $C$12:$C$14 & friends behind a name. You'll still have to be careful when adding rows, that the new rows are included in the named range - but if the formulas in the bottom table refer to named ranges instead of addresses, you won't need to modify the formulas, just to verify the reference the named ranges point to.
If 1, 3 and 5 are the only valid values, you could name them:

That way you can replace the hard-coded 1, 3 and 5 by "Funding", "Lending" and "Example" in your formula, giving a meaning for these numbers:

=INDEX(
   Categories,0,
      IF(IFERROR(MATCH(D19,FundingIds,0),0),Funding,
      IF(IFERROR(MATCH(D19,LendingIds,0),0),Lending,
      IF(IFERROR(MATCH(D19,ExampleIds,0),0),Example,0
))))

But I would really push to remove the first-level heading and turn it into a column: logically, it's a piece of data - it belongs at the row level, not as a heading. Your worksheet will be much easier to extend that way.


JSON Parsing in Bash I have a json file which needs to be restructured.
The following is the code.

while IFS='' read -r line || [[ -n "$line" ]]; do
    COUNT=$(( $COUNT + 1 ))
    #echo "[$COUNT]"
    [ $COUNT -lt 5 ] && continue
    sj=`echo $line | jq ._source`
    index=`echo $line | jq ._index | tr -d '"'`
    itype=`echo $line | jq ._type| tr -d '"'`
    echo '{ "index" : { "_index" :"'$index'","_type":"'$itype'"}}' >> bulk_result.bulk
    echo $sj >> bulk_result.bulk
#echo "$COUNT lines processed from file $1"
done < "$1"
echo "$COUNT lines processed from file $1"

Basically, the program is reading  a json record for example,

{"_index":"index1","_type":"rm","_id":"AVPkyS9w","_score":1,"_source":{"timestamp":"2016-04-05T05:00:00","token":"8eb38d14","tag":"logs.rm","message":"CouchbaseConnectSuccess,bucket=srmobjects","logsource":"rm.log","RM_pw":"","component":"rm-01-NFR","RM_un":"","timeEpochMs":1459832400.248,"RM_bucket":"srmobjects","RM_eventName":"CouchbaseConnectSuccess"}}

and converting it to the following

{ "index" : { "_index" :"index1","_type":"rm"}}
{ "RM_eventName": "FcgiClose", "timeEpochMs": 1459832435.293, "component": "rm-04-NFR", "logsource": "rm.log", "message": "FcgiClose,requestIndex=0", "tag": "logs.rm", "timestamp": "2016-04-05T05:00:35" }

The file size is about 4Gb . The code is taking a lot of time (in hours) in processing it.  Is there an efficient way to make this faster ?

Bash is not well-suited for transforming JSON. But jq is. But calling jq 3 times for each line of input is certainly going to be slow.

There are several other issues too with the script. The `...` syntax is obsolete in favor of $(...); the counting can be simplified, or even better, eliminated using tail -n +5; and the repeated bulk_result.bulk would be good to put in a variable.

But none of that matters much, as it seems the entire script can be replaced with a single line:

tail -n +5 "$1" | jq -rc '{index: {_index: ._index, _type: ._type}}, ._source'


Opening a specific Outlook item quickly I have this code to open an outlook appointment item:

    Public Sub OpenOutlookAppt()
    Set myolApp = CreateObject("Outlook.Application")
    Set objExpCal = Session.GetDefaultFolder(olFolderCalendar).GetExplorer
    Set objNavMod = objExpCal.NavigationPane.Modules.GetNavigationModule(olModuleCalendar)
    Set objNavGroup = objNavMod.NavigationGroups.GetDefaultNavigationGroup(olPeopleFoldersGroup)
    MyCalendar = objNavMod.NavigationGroups.NavigationFolders("Trip Calendar")
    EntryID = Cells(ActiveCell.Row, 22)
    ReDim Newa(1 To MyCalendar.Folder.Items.count)
    r = 1
    For Each Item In MyCalendar.Folder.Items
       Newa(r) = Item.EntryID
       r = r + 1
    Next Item
    For r = 1 To UBound(Newa)
       If Newa(r) = EntryID Then
          MyCalendar.Folder.Items(r).Display
           Exit Sub
       End If
   Next r
   End Sub

This code works, but it is very slow, because it needs to loop through every single appointment item in the calendar folder. So my question is, would there be a faster way of doing this? Is there a way I can just simply reference the item I want to open without having to create a loop? I have the EntryID to reference the item, but I could just as easily store some other data from the item to reference it.

Use this code to directly reference and open:

Set NS = myolApp.GetNamespace("MAPI")
NS.Logon
Set myAppt = NS.GetItemFromID(EntryID)
myAppt.Display

Works like a dream.


Flow of Angular Promises I recently put in a submission for a small coding challenge using Angular. The challenge was to get a token and array of values using a GET request then make another GET request passing the token and sum of values within the url. I'm still getting to grips with promises and want to know if the flow in the service and controller code below can be improved. For me the problematic line is returning the helper function solveChallenge from within the getChallenge function. It works but is my use of promises good or an anti-pattern? Should I be using the success and error methods provided by $http in place of then and catch? Any other feedback on the code is definitely much appreciated.

dataservice.js

(function() {
    'use strict';

    angular
      .module('app')
      .factory('dataservice', dataservice);

    dataservice.$inject = ['$http', '$log'];

    function dataservice($http, $log) {
        var sum, token, challenge;

        return  {
            getChallenge: getChallenge
        };

        function getChallenge(url) {

            return $http.get(url)
                    .then(function(data, status, headers, config) {
                        token = data.data.token;
                        sum = sumArray(data.data.values);
                        challenge = {token, sum};
                        return solveChallenge(url, challenge);
                    })
                    .catch(function(data, status, headers, config) {
                        $log.error("The request failed. Error code: " + status);
                    });
        }

        function solveChallenge(url, challenge) {
            var sum, token, solutionUrl;

            sum = challenge.sum;
            token = challenge.token;
            solutionUrl = url + '/' + token + '/' + sum;

            return $http.get(solutionUrl)
                    .then(function(data, status, headers, config) {
                        return data.data.answer;
                    })
                    .catch(function(data, status, headers, config) {
                        $log.error("The request failed. Error code: " + status);
                    });

          }
    }

    function sumArray(items) {
        var sum = 0;
        for (var i = 0; i < items.length; i++) {
            sum += items[i];
        }
        return sum;
    }

})();

controller.js

(function() {
    'use strict';

    angular.module('app').controller('Controller', Controller);

    Controller.$inject = ['dataservice'];

    function Controller(dataservice) {
        var vm = this;

        vm.showMeTheChallenge = function() {

          dataservice.getChallenge('http://the-url/challenge')
            .then(function(response) {

              vm.challengeSolution = response;

          });

        };
        vm.resetChallenge = function() {

            vm.challengeSolution = null;

        }

    }

})();

It works but is my use of promises good or an anti-pattern?

Promises work great when using $http.

  Should I be using the success and error methods provided by $http in place of then and catch?

According to the documentation:

  Returns a promise object with the standard then method and two http specific methods: success and error. The then method takes two arguments a success and an error callback which will be called with a response object. The success and error methods take a single argument - a function that will be called when the request succeeds or fails respectively. The arguments passed into these functions are destructured representation of the response object passed into the then method.

So you should use .then(successHandler, errorHandler) or .success(successHandler) and .error(errorHandler), but .catch(errorHandler) will not work with $http! According to the docs anyway...

function solveChallenge(url, challenge) is confusing to me, is this function really solving the challenge or is it checking the solution against a server? Consider renaming to checkSolution(url, challenge)

function getChallenge(url) is also confusing, it gets the challenge, solves it, and returns an answer from a server to see if the solution was correct. Should it be renamed to getAndSolveChallenge(url)?

function sumArray(items) could be rewritten as:

function sumArray(items) {
  return items.reduce(function(previousValue, currentItem) {
     return previousValue + currentItem;
  }, 0);
}

but there is nothing wrong with your sumArray function as is.