Simple console JSON formatter I am writing simple formatter for valid JSON. Is reads JSON data from stdin and writes formatted output to stdout.

Goals:

given valid input produce valid formatted JSON output
constant memory usage
minimal viable program (smallest program that solves a particular problem)
feature free
easy to read and understand
be C99 compatible

Non-goals:

validating JSON
handling arguments

I am not aiming JSON validation right now (as said "formatter for valid JSON").

I tried adding arguments (like setting placeholder string with -p) but faced several issues:

unclear what arguments must be implemented
I don't feel comfortable yet writing argument parsing code.

So I skipped these for now.

Latest file in GitHub: https://github.com/sineemore/juu/blob/master/juu.c

#include <stdio.h>
#include <stdlib.h> /* EXIT_SUCCESS */

#define BUF_SIZE (1024 * 4)

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

    char buf[BUF_SIZE];
    const char placeholder[] = "  ";
    unsigned int indent = 0;
    unsigned int i = 0;
    unsigned int k = 0;
    char is_string = 0;
    char escaped = 0;
    char ch;
    size_t n;

    while (0 < (n = fread(&buf, sizeof(char), BUF_SIZE, stdin))) {
        for (k = 0; k < n; k++) {
            ch = buf[k];

            if (is_string) {
                /* Inside quoted string */
                putchar(ch);
                if (! escaped) {
                    if (ch == '"') {
                        /* Unescaped quote, string just ended */
                        is_string = 0;
                    } else if (ch == '\\') {
                        escaped = 1;
                    }
                } else {
                    escaped = 0;
                }
                continue;
            }

            switch (ch) {

            case ' ':
            case '\t':
            case '\n':
            case '\r':
                /* Ignoring original formatting */
                break;

            case '{':
            case '[':
                putchar(ch);
                putchar('\n');
                i = ++indent;
                while (i-- > 0) fputs(placeholder, stdout);
                break;

            case '}':
            case ']':
                putchar('\n');
                i = --indent;
                while (i-- > 0) fputs(placeholder, stdout);
                putchar(ch);
                if (indent == 0) putchar('\n');
                break;

            case ',':
                putchar(',');
                putchar('\n');
                i = indent;
                while (i-- > 0) fputs(placeholder, stdout);
                break;

            case ':':
                putchar(':');
                putchar(' ');
                break;

            case '"':
                /* String/property key start, see if clause on top (line 20) */
                putchar('"');
                is_string = 1;
                break;

            default:
                /* Numbers, true, false, null */
                putchar(ch);
                break;
            }
        }
    }

    return EXIT_SUCCESS;
}

Example output:

$ wget -qO- 'https://xkcd.com/info.0.json' | juu
{
  "month": "4",
  "num": 1979,
  "link": "",
  "year": "2018",
  "news": "",
  "safe_title": "History",
  "transcript": "",
  "alt": "HISTORIANS: We've decided to trim the past down to make things more manageable. Using BCE/CE, would you rather we lose the odd-numbered or even-numbered years?",
  "img": "https://imgs.xkcd.com/comics/history.png",
  "title": "History",
  "day": "11"
}

UPDATE:

I missed ALL ferror() calls, fixing this part.
Also program doesn't handle SIGPIPE, therefore it may be killed. Just tested it. I don't see a clear solution, should I set SIG_IGN?

We'll have a look at your code from the top to the bottom. The proper indentation makes that easy.

Magic numbers and defines

First of all, it's great that you've used BUF_SIZE instead of magic numbers, e.g.

char buf[1024 * 4]; // bad!

However, #defines can be error prone. You've used parentheses, which are often necessary. Furthermore, BUF_SIZE doesn't exist in your compiled program anymore, which can lead to some confusion if you want to debug. So consider the possible alternatives. In this case, a #define is fine. But there is no need for abbreviation:

//! Buffer size for reading from stdin.
#define BUFFER_SIZE (1024 * 4)

While we're at it, add some documentation. BUFFER_SIZE and buf[BUFFER_SIZE] are only some lines away from each other, but that might change later. The ! after // is Doxygen specific, you can ignore it if you don't use Doxygen.

Declarations and initializations

You use C99 and therefore can declare variables as late as you want. Whenever you declare a variable but set it a lot later, try to rewrite it as initialization at the right point. For example, ch isn't used until ch = buf[k]. We should keep it's scope limited. That way we cannot accidentally reuse variables.

If we follow this suggestion then i, k and ch get limited in their scope. We will have a look at that later, though. And since we already renamed BUF_SIZE to BUFFER_SIZE, we could also rename buf to buffer. You can of course choose other names, but again: there is no need to abbreviate. Disk space isn't expensive anymore, so choose names that you still understand after several months or years when someone calls you in the middle of the night.

Input and sizeof usage

fread(...,..., SIZE ,...) may not return SIZE. That can either happen if you're at the end of the file or if an error happens. You should check the FILE* with feof or ferror if that happens.

We stay at fread. While it's unlikely that you change buffer's type, it's usually good practice to use sizeof(*buf) or sizeof(buf[0]). If you ever change char buffer[BUFFER_SIZE] to mychar buffer[BUFFER_SIZE], you don't have to remember to change sizeof(char) to sizeof(mychar).

State machines and repetition

Your loop is essentially a state machine. The state machine itself looks fine. However, there is a lot of repetition. We have

while (i-- > 0) fputs(placeholder, stdout);

four times. That really asks for a function:

/**
 * \brief Puts the given \c str \c count times on \c stream.
 * \param str null-terminated character string to be written
 * \param count number of times \c str shall be written
 * \param stream output stream
 * \returns a non-negative value on success
 * \returns EOF on error and sets the error indicator
*/
inline void fputs_repeat(const char * str, size_t count, FILE * stream) {
    int value = 0;
    while (count-- > 0) {
        value = fputs(str, stream);
        if (value == EOF) {
            return EOF;
        }
    }
    return value;
}

Now we can just use fputs_repeat(placeholder, indentation, stdout) wherever you've used while (i-- > 0) .... We would now end up with the following variant:

#include <stdio.h>
#include <stdlib.h> /* EXIT_SUCCESS */

#define BUFFER_SIZE (1024 * 4)

inline void fputs_repeat(const char * str, size_t count, FILE * stream) {
    int value = 0;
    while (count-- > 0) {
        value = fputs(str, stream);
        if (value == EOF) {
            return EOF;
        }
    }
    return value;
}

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

    char buffer[BUF_SIZE] = {0};
    const char placeholder[] = "  ";
    unsigned int indent = 0;
    char is_string = 0;
    char escaped = 0;
    size_t n;

    while (0 < (n = fread(&buffer, sizeof(buffer[0]), BUFFER_SIZE, stdin))) {
        // exercise: add error handling
        for (unsigned int k = 0; k < n; k++) {
            char ch = buffer[k];

            if (is_string) {
                /* Inside quoted string */
                putchar(ch);
                if (! escaped) {
                    if (ch == '"') {
                        /* Unescaped quote, string just ended */
                        is_string = 0;
                    } else if (ch == '\\') {
                        escaped = 1;
                    }
                } else {
                    escaped = 0;
                }
                continue;
            }

            switch (ch) {

            case ' ':
            case '\t':
            case '\n':
            case '\r':
                /* Ignoring original formatting */
                break;

            case '{':
            case '[':
                putchar(ch);
                putchar('\n');
                fputs_repeat(placeholder, ++indent, stdout);
                break;

            case '}':
            case ']':
                putchar('\n');
                fputs_repeat(placeholder, --indent, stdout);
                putchar(ch);
                if (indent == 0) putchar('\n');
                break;

            case ',':
                putchar(',');
                putchar('\n');
                fputs_repeat(placeholder, indent, stdout);
                break;

            case ':':
                putchar(':');
                putchar(' ');
                break;

            case '"':
                /* String/property key start, see if clause on top */
                putchar('"');
                is_string = 1;
                break;

            default:
                /* Numbers, true, false, null */
                putchar(ch);
                break;
            }
        }
    }

    return EXIT_SUCCESS;
}

Output

You use putchar quite often. In some instances multiple calls can get replaced by puts or fputs. For example, instead of

putchar(',');
putchar('\n');

you could just use

puts(",");

and instead of

putchar(':');
putchar(' ');

you could use

fputs(": ", stdout);

Either way, if you're striving for performance, you want to keep the number of function calls low, so consider an output buffer if your current variant isn't fast enough for your liking. But first measure your program before you change it.

Goals

Let's revisit your goals and check them now.

  given valid input produce valid formatted JSON output

Since you don't introduce additional characters in strings and never remove characters from the original JSON except whitespace (outside of strings), you've reached that goal.

  constant memory usage

As there is only a single buffer, you've reached that goal too, although fputs might buffer.

  minimal viable program (smallest program that solves a particular problem)

Ah, that's a definition problem. What's minimal? What's "smallest"? Your program is short, but a single additional function removed some repetition which can lead to a technical debt. That function won't increase the size of your program, though.

  feature free

Check.

  easy to read and understand

The ! escaped logic took a little bit, but apart from that, goal reached.

  be C99 compatible

Yes, but use those features I've mentioned above (inline functions, late declarations).

  Also program doesn't handle SIGPIPE, therefore it may be killed. Just tested it. I don't see a clear solution, should I set SIG_IGN?

If the input pipe is broken, the JSON input will suddenly end and you have invalid JSON. Do you need to handle invalid JSON at that point? It's a non-goal, as you said.


Adding input strings and finding occurrences of certain prefixes A user inputs data using a keyword add word and when he wants to find  words with particular prefix then he enters find keyword.

Example input:

4
add hack
add hacker
find hac
find hak

Output:

2
0

Although the code is working fine but for bigger cases it takes too much time.Please help me in reducing its time complexity.

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
vector<string> v;
vector<string>::iterator i;
//char  *a;
string a,b;
int n;
cin>>n;
while(n--)
{

    cin>>a>>b;
      //char *Split = strtok (a," ");
    //vector<char*> Split = a.split_cstr(" ");
    if(a=="add")
{
    v.push_back(b);sort(v.begin(),v.end());}
    else if(a=="find")
    {  int mycount=0;
         //mycount = std::count (v.begin(), v.end(),find(b));
        //strncmp(string1, string2, strlen(string2))
        //          cout<<mycount<<endl;
        std::string prefix(b);

        //std::set<std::string>::iterator i;
        for (i = v.begin(); i != v.end(); ++i)
        {
           if ((*i).compare(0, prefix.length(), prefix) == 0)
              mycount++;
            else if((*i).compare(0, prefix.length(), prefix) == 1)
              break;
        }
        cout<<mycount<<endl;
    }

 }

}

Let us just assume for simplicity that the upper bound for word length is some constant, so we can do some string operations on words, like checking if string a is prefix of b in constant time (i.e. \$O(1)\$). We will have N queries in total.

Naive solution

if (a == "add")
{
    v.push_back(b);
}
else if (a == "find")
{
    ...
    for (string word : v)
        if (is_prefix(prefix, word))
            mycount++;
    ...
}

Let us calculate time complexity for the worst case.

add operation: \$O(1)\$*

find operation: O(N) (assuming there are already N words added, we need to check each of them if it starts with prefix)

In total: \$N * (O(1) + O(N)) = O(N^2)\$

Your solution

add operation: \$O(N log N)\$ (for sorting)

find operation: \$O(N)\$ (even though we stop the search after the last matching word, it does not help in worst case, in which we have to check all the words)

In total: \$O(N^2 log N)\$

Even though the complexity seems to get worse, you are on the right track!

Possible improvement

Let K be the largest possible number of words find operation could find.
We can modify the solution to iterate only through words that start with prefix (K words at most). Because the vector is kept sorted, with binary search, that has \$O(log N)\$ complexity, we can find the first matching word without iterating through all the words from the beginning. In C++ std::lower_bound can do that job for you.

find operation: \$O(log N) + O(K)\$

Now let us improve add operation. It turns out, if we just replace std::vector with std::set, that is always sorted and has pretty good insertion/deletion complexity. The complexity for find will not change but add will be faster.

add operation: \$O(log N)\$

In total: \$N * (O(log N) + O(K) + O(log N)) = O(N log N + N * K)\$

It would be an improvement if K was some small constant. But as I now see that we are not even asked to output those words but only number of words, from my experience I would say we should not assume that K is small. The solution is probably checked against worst-case scenario that should look like this:

add aaa1
add aaa2
add aaa3
... (continue N/2 times)
find aaa
find aaa
find aaa
... (continue N/2 times)

If each find iterates through all the words, we get \$O(N/2 * N/2) = O(N^2)\$. This is not good. That probably means that we cannot event iterate through all matching words during find operation.

Better solution

Use prefix tree. Again, assuming constant word length, inserts will be constant:

add operation: \$O(1)\$

We will be able to find a subtree for all matching words in constant time too. Now we need to count words that belong to that subtree. Iterating trough all the children would be too slow. We will modify our tree to make each node store number of children. That number will be equal to the number of words that start with the prefix. It is possible to modify add operation to keep that number updated without changing the complexity of add.

find operation: \$O(1)\$

In total: \$O(N)\$


Java 8 use streams for a "group by" feature I am writing a Java function that checks if the items of a list are unique (depending of an id member).

I have a Java 7 implementation that works, but it is not using streams, filter and joins. I think the code can be improved.

Case 1: empty list => OK

Case 2: all ids are different => OK

+---------+-------+
| baf18c4 | Item1 |
| c5e4623 | Item2 |
| bf1932f | Item3 |
+---------+-------+

No message expected.

Case 3: one id is duplicate (3 times each) => message expected

+---------+-------+
| baf18c4 | Item1 |
| c5e4623 | Item2 |
| baf18c4 | Item3 |
| baf18c4 | Item4 |
+---------+-------+

Expected message:

  Some of the items are sharing the same code: 'baf18c4' used by {Item1, Item3, Item4}

Case 4: two ids is duplicate (2 times each) => message expected

+---------+-------+
| baf18c4 | Item1 |
| c5e4623 | Item2 |
| baf18c4 | Item3 |
| bf1932f | Item4 |
| c5e4623 | Item5 |
+---------+-------+

  Some of the items are sharing the same code: 'baf18c4' used by {Item1, Item3}, 'c5e4623' used by {Item2, Item5}

Code

package tmp;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.stream.Collectors;

import org.junit.Test;

public class Snippet {
  private static String verifyItems(List<Item> items) {
    Map<String, List<Item>> map = new HashMap<>();
    for (Item item : items) {
      String key = item.getCode();
      List<Item> list;
      if (map.containsKey(key)) {
        list = map.get(key);
      }
      else {
        list = new ArrayList<>();
        map.put(key, list);
      }
      list.add(item);
    }
    boolean isFirst = true;
    StringBuilder sb = new StringBuilder();
    for (Entry<String, List<Item>> e : map.entrySet()) {
      if (e.getValue().size() > 1) {
        if (isFirst) {
          sb.append("Some of the items are sharing the same code: ");
        }
        else {
          sb.append(", ");
        }
        isFirst = false;
        sb.append("'" + e.getKey() + "' used by ");
        sb.append(e.getValue().stream().map(i -> i.getDescription())
            .collect(Collectors.joining(", ", "{", "}")));
      }
    }
    return sb.toString();
  }

  @Test
  public void testEmpty() throws Exception {
    assertEquals("", verifyItems(Collections.emptyList()));
  }

  @Test
  public void testOk() throws Exception {
    List<Item> items = Arrays.asList(
        new Item("baf18c4", "Item1"),
        new Item("c5e4623", "Item2"),
        new Item("bf1932f", "Item3"));
    assertEquals("", verifyItems(items));
  }

  @Test
  public void testDuplicate() throws Exception {
    List<Item> items = Arrays.asList(
        new Item("baf18c4", "Item1"),
        new Item("c5e4623", "Item2"),
        new Item("baf18c4", "Item3"),
        new Item("baf18c4", "Item4"));
    assertEquals("Some of the items are sharing the same code: 'baf18c4' used by {Item1, Item3, Item4}", verifyItems(items));
  }

  @Test
  public void testDuplicate2() throws Exception {
    List<Item> items = Arrays.asList(
        new Item("baf18c4", "Item1"),
        new Item("c5e4623", "Item2"),
        new Item("baf18c4", "Item3"),
        new Item("bf1932f", "Item4"),
        new Item("c5e4623", "Item5"));
    assertEquals("Some of the items are sharing the same code: 'baf18c4' used by {Item1, Item3}, 'c5e4623' used by {Item2, Item5}", verifyItems(items));
  }

  public static class Item {
    private String code;
    private String description;

    public Item(String code, String description) {
      super();
      this.code = code;
      this.description = description;
    }

    public String getCode() {
      return code;
    }

    public String getDescription() {
      return description;
    }
  }
}

Thank you for a nicely formulated and formatted first question! :)

Indeed, the same result can be achieved with much less code using Java 8.

I suggest the following:

Group all the items into a Map<String, List<Item>>, equivalent of the first original for loop:

Map<String, List<Item>> itemsGroupedByCode =
  items.stream().collect(Collectors.groupingBy(Item::getCode));

Collect all the messages citing duplicate entries, equivalent of the second original for loop, but without the prefix:

String duplicatesMessage =
  itemsGroupedByCode.entrySet().stream()
      .filter(entry -> entry.getValue().size() > 1)
      .map(entry -> {
        final String duplicateValues = entry.getValue().stream()
                                                       .map(Item::getDescription)
                                                       .collect(Collectors.joining(", ", "{", "}"));
        return String.format("'%1$s' used by %2$s", entry.getKey(), duplicateValues);
  }).collect(Collectors.joining(", "));

Return the result, empty if there were no duplicates or prefixed if there were some entries:

if (!duplicatesMessage.isEmpty()) {
  return "Some of the items are sharing the same code: " + duplicatesMessage;
}
return "";

I'd also suggest to change the return type of the method to Optional<String> and return Optional.empty() instead of the empty string. But this is up to you to decide if it fits the context of your app.


AJAX call in JavaScript I know there is a lot of libraries with this built in $.get() etc... but as for writing this in pure JavaScript how does this look?

var get_request;

ajaxRequest(function() {
    var activexmodes, i, _i, _len, _ref, _results;
    activexmodes = ['Msxm12.XMLHTTP', 'Microsoft.XMLHTTP'];
    if (window.ActiveXObject) {

        _ref = activexmodes.length;
        _results = [];

        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
            i = _ref[_i];
            try {
                _results.push(new ActiveXObject(activexmodes[i]));
            } catch (_error) {}
        }
        return _results;
    } else if (window.XMLHttpRequest) {
        return new XMLHttpRequest();
    } else {
        return false;
    }
});

get_request = new ajaxRequest();

There are a couple issues with this code:

You don't define a function in Javascript with ajaxRequest(function() { ... }); What you're doing there is calling function ajaxRequest and passing an anonymous function into it as the only parameter. It will throw a JS error as it is now, because ajaxRequest isn't defined.

To define an ajaxRequest function, you would do either function ajaxRequest() { ... } or var ajaxRequest = function() { ... };.
This code snippet:

activexmodes = ['Msxm12.XMLHTTP', 'Microsoft.XMLHTTP'];
_ref = activexmodes.length;

for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    i = _ref[_i];

will also throw a JS error because you're treating _ref like an Array when it's actually a Number. I'm guessing you meant to use activexmodes instead. _ref is completely unnecessary.
Why do you declare all your variables at the very top of the function? It's bad practice because declaring your variables when you first need them tells anyone who reads your code that "this is the first time I'm using this variable." If you declare them all at the top, anyone else who reads it has to search through to make sure it's not used or modified anywhere else. (In this case it's harmless, but in larger functions it can become and issue.)
To use the function, you should call it directly instead of using new:

var get_request = ajaxRequest();   // probably should be named getX(),
                                   // like getAJAXRequest()

I would be careful about returning false from the function. If that's a known return value and you're going to check for it everywhere you use it, then that's okay. But if you forget to support that rare case, the user will get some cryptic JS error somewhere down the line when you try to call get_request.open() or some other function.


Given set of cubes can we get a given word? Given some cubes, can cubes be arranged such that an input word can be formed from the top view of the cubes?

For example: assume an imaginary cube with only 3 surfaces where cube1: {a, b, c} and cube2 {m, n, o}, then word an can be formed but word ap cannot be formed.

Please look into the two following issues:

A couple of questions nested inside the codes regarding premature optimization.
Verifying complexity to be O(n!), where n is the number of alphabets in the word.

public final class CubeFind {
    private CubeFind() {}

    public static boolean checkWord(char[][] cubeMatrix, String word) {

        /*
         * Premature optimization: read that they were bad practices. they look good in my code, should i keep them ?
         *
         * 1. If not checked now, then NPE would result after hashMap is computed. on line 46
         * if (cubeMatrix == null) { throw new NullPointerException("The input cube matrix should not be null");
         *
         * 2. if (word == null {throw new NullPointerException("The input word should not be null"); }
         *
         * 3. if (cubeMatrix.length != word.length()) return false;
         */

        char[] chWords = word.toCharArray();
        final Map<Character, Integer> charFreq = new HashMap<Character, Integer>();

        for (char ch : chWords) {
            if (charFreq.containsKey(ch)) {
                charFreq.put(ch, charFreq.get(ch) + 1);
            } else {
                charFreq.put(ch,  1);
            }
        }

        return findWordExists(cubeMatrix, charFreq, 0);
    }

    private static boolean findWordExists (char[][] cubeMatrix, Map<Character, Integer> charFreq, int cubeNumber) {
        assert charFreq != null;

        if (cubeNumber == cubeMatrix.length) {
            for (Integer frequency : charFreq.values()) {
                if (frequency > 0) return false;
            }
            return true;
        }

        for (int i = 0; i <  cubeMatrix[cubeNumber].length; i++) {
            if (charFreq.containsKey(cubeMatrix[cubeNumber][i])) {
                int frequency = charFreq.get(cubeMatrix[cubeNumber][i]);
                // this check is needed to get a false result when input chars are less than number of cubes
                // eg: 'hel' should return false.
                if (frequency > 0) {
                    charFreq.put(cubeMatrix[cubeNumber][i], frequency - 1);
                    if (findWordExists(cubeMatrix, charFreq, cubeNumber + 1)) {
                        return true;
                    }
                    charFreq.put(cubeMatrix[cubeNumber][i], frequency);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        char[][] m = {{'e', 'a', 'l'} , {'x', 'h' , 'y'},  {'p' , 'q', 'l'}, {'l', 'h', 'e'}};
        System.out.println("Expected true,  Actual: " + CubeFind.checkWord(m, "hell"));
        System.out.println("Expected true,  Actual: " + CubeFind.checkWord(m, "help"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "helll"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hel"));
    }
}

Verify complexity to be O(n!), where n is the number of alphabets in the word.

Indeed.
    private CubeFind() {}

You don't need this to get a default constructor.

Premature optimization: read that they were bad practices. they look good in my code, should i keep them ?
If not checked now, then NPE would result after hashMap is computed. on line 46

if (cubeMatrix == null) { throw new NullPointerException("The input cube matrix should not be null");

if (word == null {throw new NullPointerException("The input word should not be null"); }

Please don't do that! You're not gaining anything, the first reason being that it's going to fail very quickly if you really get null or word. The second reason is that there's no reason to get null here, why would that happen? You're simply calling this function from main, it cannot be null. When not for useless optimizations, this practice is called defensive programming and is only useful in a few specific scenarios.
 if (cubeMatrix.length != word.length()) return false;

This one can also be seen as a way to eliminate cases you don't want to reason about later on. That is, you know after this line that you will have the correct number of cubes, and it simplifies the reasoning and the code. You should keep it.
if (cubeNumber == cubeMatrix.length) {

This one wasn't obvious at first, and could deserve a comment, eg. "If we chose a letter for all cubes, check that no letter is left", maybe.
charFreq.put(cubeMatrix[cubeNumber][i], frequency - 1);
if (findWordExists(cubeMatrix, charFreq, cubeNumber + 1)) {
    return true;
}
charFreq.put(cubeMatrix[cubeNumber][i], frequency);

Nice trick. Another way to do it is to give a copy of cubeMatrix. You would then avoid the second put, but it could be very costly here due to the number of copies you would have to do: don't do it.
I would define premature optimization as "a change made for performance reasons that brings no benefit or degrades readability, and has not been proved to actually improve performance".
Last, your tests are okay for this usage, but consider using an unit test library like JUnit to manage tests, this will help you later on.


F# program to generate a Map of substrings frequencies I wrote the following F# program that takes an input txt file and create a Map that contains all possible substrings of size N and their frequency in the file.

In other words if I call the program with a text file with the following content:

  James John Max Gary Jess Gilles Mary

With a length of 2, the probabilityTable contains a value with a key of "ar" with a value of 0.054054.

Here is the program:

module NameGenerator

open System
open System.Collections.Generic

// Open a file and read all lines into IEnumerable<string>
let readInputFile (filePath:string) =
    System.IO.File.ReadAllText(filePath)

// Parses a string and count the total number of occurrences of substrings of size length
let rec countOccurrences (input:string) (occurrenceTable:Map<string, float>) length =
    let adjLen = length - 1

    match input |> Seq.toList with
    | head :: tail when tail.Length >= adjLen ->
        let other = Seq.take adjLen tail |> Seq.toList
        let occurrence = (head :: other |> Array.ofList |> String)

        // add current occurrence to the occurrence table
        let updatedMap = match occurrenceTable.ContainsKey (occurrence) with
                         | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
                         | false -> occurrenceTable.Add(occurrence, 1.0)

        // call the function recursively with the rest of the string
        countOccurrences (tail |> Array.ofList |> String) updatedMap length
    | _ -> occurrenceTable

// Given a map that contains the a collection of string and their respective counts, return a
// frequency map that is obtained by count / total count
let buildFrenquencyTable (occurrenceTable:Map<string, float>) =
    // fold occurence dict, count total
    let total = Map.fold (fun acc key value -> acc + value) 0.0 occurrenceTable

    // map over previous map and replace values with count / total count
    Map.map (fun key value -> Math.Round(value / total, 6)) occurrenceTable

// Given an input file create a probability table for the different letters in the file
let buildProbabilityTable (filePath:string) length =
    let input = readInputFile filePath
    let initialDictionary = Map.empty

    countOccurrences input initialDictionary length
    |> buildFrenquencyTable

I would like a review on how I could do things better and use a more functional style.

Fortunately you're already following the functional idioms entirely. So that's a very good thing.

The only things I would comment on are a few minor details:

let occurrence = (head :: other |> Array.ofList |> String)

Those parenthesis are superfluous.

let updatedMap = match occurrenceTable.ContainsKey (occurrence) with
                 | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
                 | false -> occurrenceTable.Add(occurrence, 1.0)

In this case, you have a lot of whitespace to the left of the match conditions, usually in this case  I just break the match to a new line and then work from there.

let updatedMap =
    match occurrenceTable.ContainsKey (occurrence) with
    | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
    | false -> occurrenceTable.Add(occurrence, 1.0)

It's generally easier to read.

let total = Map.fold (fun acc key value -> acc + value) 0.0 occurrenceTable

I absolutely love to see fold used! I think it's far overlooked and definitely has many use cases.

In regards to this method:

let rec countOccurrences (input:string) (occurrenceTable:Map<string, float>) length =

You nailed tail-call recursion. I would be willing to bet that if you looked at the IL for this code you would see a beautiful tail. call in there. Excellent work!

Overall, beautiful work. I think you did a phenomenal job with this code. :)


Authentication for a Flask API I've written a couple of functions to check if a consumer of the API should be authenticated to use it or not.

Have I done anything blatantly wrong here?

Config

API_CONSUMERS = [{'name': 'localhost',
                  'host': '12.0.0.1:5000',
                  'api_key': 'Ahth2ea5Ohngoop5'},
                 {'name': 'localhost2',
                  'host': '127.0.0.1:5001',
                  'api_key': 'Ahth2ea5Ohngoop6'}]

Exceptions

class BaseException(Exception):

    def __init__(self, logger, *args, **kwargs):
        super(BaseException, self).__init__(*args, **kwargs)
        logger.info(self.message)

class UnknownHostException(BaseException):
    pass

class MissingHashException(BaseException):
    pass

class HashMismatchException(BaseException):
    pass

Authentication methods

import hashlib
from flask import request
from services.exceptions import (UnknownHostException, MissingHashException,
    HashMismatchException)

def is_authenticated(app):
    """
    Checks that the consumers host is valid, the request has a hash and the
    hash is the same when we excrypt the data with that hosts api key

    Arguments:
    app -- instance of the application
    """
    consumers = app.config.get('API_CONSUMERS')
    host = request.host

    try:
        api_key = next(d['api_key'] for d in consumers if d['host'] == host)
    except StopIteration:
        raise UnknownHostException(
            app.logger, 'Authentication failed: Unknown Host (' + host + ')')

    if not request.headers.get('hash'):
        raise MissingHashException(
            app.logger, 'Authentication failed: Missing Hash (' + host + ')')

    hash = calculate_hash(request.method, api_key)

    if hash != request.headers.get('hash'):
        raise HashMismatchException(
            app.logger, 'Authentication failed: Hash Mismatch (' + host + ')')

    return True

def calculate_hash(method, api_key):
    """
    Calculates the hash using either the url or the request content,
    plus the hosts api key

    Arguments:
    method  -- request method
    api_key -- api key for this host
    """
    if request.method == 'GET':
        data_to_hash = request.base_url + '?' + request.query_string
    elif request.method == 'POST':
        data_to_hash = request.data

    data_to_hash += api_key
    return hashlib.sha1(data_to_hash).hexdigest()

Exception itself actually inherits from a class called BaseException so:

class BaseException(Exception):

Seems backwards.


Pull From Oracle into CSV File I have written this code in C# to connect to an Oracle Database, omitting the tnsnames.ora file, then place results from a query into a CSV File.

Is there more efficient way to do this? (Such as reading in the data into a DataReader rather than a DataTable)

Please review and tell me what you would change.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Oracle.ManagedDataAccess.Client;
using System.Configuration;
using System.Data;
using FileHelpers;
using System.IO;

namespace oracle_test
{
class Program
{
    static void Main(string[] args)
    {
        OraTest ot = new OraTest();
        ot.Connect();
    }

    class OraTest
    {
        public void Connect()
        {
            var constr = new OracleConnectionStringBuilder()
            {
                DataSource = @"(DESCRIPTION =(ADDRESS_LIST =(ADDRESS = (PROTOCOL = TCP)(HOST = 10.100.100.10)(PORT = 1521)))(CONNECT_DATA =(SERVICE_NAME = ONE10)))",
                UserID = "100",
                Password = "100",
            }.ConnectionString;

            using (var con = new OracleConnection(constr))
            {
                string prfbalqry = "select * from ati where be = 0";

                OracleCommand cmd = new OracleCommand(prfbalqry, con);
                cmd.CommandType = System.Data.CommandType.Text;
                con.Open();

                DataTable pbResults = new DataTable();
                OracleDataAdapter oda = new OracleDataAdapter(cmd);
                oda.Fill(pbResults);

                StringBuilder sb = new StringBuilder();
                IEnumerable<string> columnNames = pbResults.Columns.Cast<DataColumn>().Select(column => column.ColumnName);
                sb.AppendLine(string.Join(",", columnNames));

                foreach (DataRow row in pbResults.Rows)
                {
                    IEnumerable<string> fields = row.ItemArray.Select(field => field.ToString());
                    sb.AppendLine(string.Join(",", fields));
                }

                File.WriteAllText(@"C:\Financial Reporting\Output Path\pbresults.csv", sb.ToString());
            }
        }
    }
}
}

OraTest is not a useful name. Call it OracleToCSVWriter or something like that.

Mind the naming of variables etc: oda is not very descriptive - adapter would maybe be better.

Hardcoded username/password is rarely a good idea.

Why do you convert to string in this line?:

IEnumerable<string> fields = row.ItemArray.Select(field => field.ToString());
sb.AppendLine(string.Join(",", fields));

I think the below would be sufficient:

sb.AppendLine(string.Join(",", row.ItemArray));

Even for such a small piece of code it is a good idea to split it up in meaningful parts (maybe: private string GetConnectionString() {...}, private DataTable LoadData(OracleConnection connection) {...}, WriteData(DataTable data) {...})

You should dispose OracleCommand, OracleDataAdapteras well as DataTablejust as you dispose OracleConnection.

When writing to file, I would write directly to a stream, instead of first collect all data in memory:

    using (StreamWriter writer = new StreamWriter("<Path>", false, Encoding.Unicode))
    {
      foreach (DataRow row in table.Rows)
      {
        writer.WriteLine(string.Join(", ", row.ItemArray));
      }
    }

That said You should be aware that when writing a CSV file, string and other data may contain commas (,)  and that could break the column layout, so you'll have to encapsulate strings in quotation marks, which will complicate the writing a little bit. A way to go could be something like:

        writer.WriteLine(string.Join(", ", row.ItemArray.Select(i => i is string? $"\"{i}\"" : i)));

or maybe:

writer.WriteLine(string.Join(", ", row.ItemArray.Select(i => $"\"{i}\"")));

(Not fully tested!)


Refactoring multiple boolean conditions? I have a Predicate which takes employee object.
Predicate<Employee> getPredicate() {
    return emp -> filter(emp);
}

Now the filter method is very complex, it calls four other methods which returns true/false if all the conditions are true, the predicate will return true.
private boolean filter(Employee employee) {
    String employeeJSONString = employeeToString(employee);
    return filterBasedOnConsistAge(employeeJSONString) &&
           filterBasedOnConsistGender(employeeJSONString) &&
           filterBasedOnConsistNationality(employeeJSONString) &&
           filterBasedOnConsistHandicap(employeeJSONString);
}

private String employeeToString(Employee employee) {
    // converts domainObject to a formatted string, it's a business requirement
}

There are five-line methods, that are linked using logical AND. But the problem here is, the chaining is looking clean. is there a way to improve this logic?

What especially jumps at me is, that you take your real data object (the Employee), convert it to a string representation and do your checks on the string.

Why? Can't you check your data object?

Apart from that, I don't see a problem with 5 and-conditions. This is clearer to read than some clever stream-through-predicates-and-reduce code. Clear. Simple. Leave it like that.

What I'd recommend is rethinking your naming:

getPredicate(): yes, it returns a predicate, we see that from the method signature. But what does this predicate test?
filter(): does some filtering, but according to which criteria?

(Sorry to pepijno, I typed this without seeing your answer... no offense meant ;-))


Printing the sums of numbers from 1 to 10 with only 1 loop The code below prints sum from 1 to 10:

  \$1\$
  \$1+2 =\$
  \$1+2+3 =\$
  \$1+2+3+4 =\$
  \$......\$
  \$1 + ... 10 = 55\$

public class Solution{

    public static void print_sums(){

        int sum = 0 ;
         for(int i = 1 ; i <= 10 ; i++){
             for(int j = 1 ; j <= i; j++ ){
                sum = sum + j ;
             }
             System.out.println( sum) ;
             sum = 0 ;
         }

    }

    public static void main(String[] args)
    {
        print_sums() ;

    }
}

I wonder out of "efficiency curiosity" - is it possible to do it in 1 loop?  Without 2 nested loops?

i.e. put both i and j in one loop and increment them from there.

I think it is impossible, because **the whole loop will run only 10 times - i = [1,10]

 for(int i = 1 , j = 1 ; j <= i && i <= 10 ; i++, j++)
             //for(int j = 1 ; j <= i; j++ ){
                sum = sum + j ;
             //}
             System.out.println( sum) ;
             sum = 0 ;

Yes, it is possible.

public static void printSums() {
    int sum = 0;
    for (int i = 1; i <= 10; i++) {
        sum += i;
        System.out.println(sum);
    }
}

The key is simply to calculate the sum of the first \$N\$ digits. It is easy if you already have the sum of the first \$N-1\$ digits : you simply add \$N\$.


Passing parameters by reference? Let me fix that for you I've implemented a code inspection that verifies whether a procedure has parameters that are implicitly passed by reference - in VBA a parameter is passed ByRef unless it's explicitly specified ByVal.

Here is the implementation in question:

[ComVisible(false)]
public class ImplicitByRefParameterInspection : IInspection
{
    public ImplicitByRefParameterInspection()
    {
        Severity = CodeInspectionSeverity.Warning;
    }

    public string Name { get { return "Parameter is passed ByRef implicitly"; } }
    public CodeInspectionType InspectionType { get { return CodeInspectionType.CodeQualityIssues; } }
    public CodeInspectionSeverity Severity { get; set; }

    public IEnumerable<CodeInspectionResultBase> GetInspectionResults(SyntaxTreeNode node)
    {
        var procedures = node.FindAllProcedures().Where(procedure => procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value)));
        var targets = procedures.Where(procedure => procedure.Parameters.Any(parameter => parameter.IsImplicitByRef)
                                                && !procedure.Instruction.Line.IsMultiline);

        return targets.SelectMany(procedure => procedure.Parameters.Where(parameter => parameter.IsImplicitByRef)
            .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity)));
    }
}

Would there be a better way to do this? Here is the ImplicitByRefParameterInspectionResult class (gosh that's a long name!):

[ComVisible(false)]
public class ImplicitByRefParameterInspectionResult : CodeInspectionResultBase
{
    public ImplicitByRefParameterInspectionResult(string inspection, Instruction instruction, CodeInspectionSeverity type)
        : base(inspection, instruction, type)
    {
    }

    public override IDictionary<string, Action<VBE>> GetQuickFixes()
    {
        return !Handled
            ? new Dictionary<string, Action<VBE>>
                {
                    {"Pass parameter by value", PassParameterByVal},
                    {"Pass parameter by reference explicitly", PassParameterByRef}
                }
            : new Dictionary<string, Action<VBE>>();
    }

    private void PassParameterByRef(VBE vbe)
    {
        if (!Instruction.Line.IsMultiline)
        {
            var newContent = string.Concat(ReservedKeywords.ByRef, " ", Instruction.Value);
            var oldContent = Instruction.Line.Content;

            var result = oldContent.Replace(Instruction.Value, newContent);

            var module = vbe.FindCodeModules(Instruction.Line.ProjectName, Instruction.Line.ComponentName).First();
            module.ReplaceLine(Instruction.Line.StartLineNumber, result);
            Handled = true;
        }
        else
        {
            // todo: implement for multiline
            throw new NotImplementedException("This method is not [yet] implemented for multiline instructions.");
        }
    }

    private void PassParameterByVal(VBE vbe)
    {
        if (!Instruction.Line.IsMultiline)
        {
            var newContent = string.Concat(ReservedKeywords.ByVal, " ", Instruction.Value);
            var oldContent = Instruction.Line.Content;

            var result = oldContent.Replace(Instruction.Value, newContent);

            var module = vbe.FindCodeModules(Instruction.Line.ProjectName, Instruction.Line.ComponentName).First();
            module.ReplaceLine(Instruction.Line.StartLineNumber, result);
            Handled = true;
        }
        else
        {
            // todo: implement for multiline
            throw new NotImplementedException("This method is not yet implemented for multiline instructions.");
        }
    }
}

Any comment is welcome.

Starting from this

var procedures = node.FindAllProcedures().Where(procedure => procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value)));
var targets = procedures.Where(procedure => procedure.Parameters.Any(parameter => parameter.IsImplicitByRef)
                                        && !procedure.Instruction.Line.IsMultiline);

return targets.SelectMany(procedure => procedure.Parameters.Where(parameter => parameter.IsImplicitByRef)
    .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity)));

Let's collapse it into one expression

return node.FindAllProcedures()
    .Where(procedure => procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value)))
    .Where(procedure => procedure.Parameters.Any(parameter => parameter.IsImplicitByRef)
                                        && !procedure.Instruction.Line.IsMultiline)
    .SelectMany(procedure => procedure.Parameters.Where(parameter => parameter.IsImplicitByRef)
    .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity)));

Move the last Select out of SelectMany

return node.FindAllProcedures()
    .Where(procedure => procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value)))
    .Where(procedure => procedure.Parameters.Any(parameter => parameter.IsImplicitByRef)
                                        && !procedure.Instruction.Line.IsMultiline)
    .SelectMany(procedure => procedure.Parameters)
    .Where(parameter => parameter.IsImplicitByRef)
    .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity));

Now it seems like procedure.Parameters.Any(parameter => parameter.IsImplicitByRef) is redundant, so let's remove that and join the successive Wheres

return node.FindAllProcedures()
    .Where(procedure => procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value))
                        && !procedure.Instruction.Line.IsMultiline)
    .SelectMany(procedure => procedure.Parameters)
    .Where(parameter => parameter.IsImplicitByRef)
    .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity));

It's not clear why procedure.Parameters.Any(parameter => !string.IsNullOrEmpty(parameter.Instruction.Value)) is necessary -- if it is, a comment is required, otherwise we can just write

return node.FindAllProcedures()
    .Where(procedure => !procedure.Instruction.Line.IsMultiline)
    .SelectMany(procedure => procedure.Parameters)
    .Where(parameter => parameter.IsImplicitByRef)
    .Select(parameter => new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity));

Which is looking more much manageable. Or if you prefer the alternative syntax

return from procedure in node.FindAllProcedures()
       where !procedure.Instruction.Line.IsMultiline
       from parameter in procedure.Parameters
       where parameter.IsImplicitByRef
       select new ImplicitByRefParameterInspectionResult(Name, parameter.Instruction, Severity);


Searching the Foursquare API with Python I'd like some feedback on the readability, style, and potential problems or issues.

foursquare.py

import time

from api_keys import CLIENT_ID
from api_keys import CLIENT_SECRET
from api_keys import CATEGORY_ID

from business import Business
from business import make_request

def search(lat, lng, distance):
    """
    Searches the Foursquare API (Max Limit = 50)

    :param lat: Latitude of the request
    :param long: Longitude of the request
    :param distance: Distance to search (meters)
    :returns: List of retrieved venues
    """

    url = 'https://api.foursquare.com/v2/venues/explore?ll=%s,%s&intent=browse&radius=%s&limit=50&categoryId=%s&client_id=%s&client_secret=%s&v=%s' % (lat, lng, distance, CATEGORY_ID, CLIENT_ID, CLIENT_SECRET, time.strftime("%Y%m%d"))
    venue_list = []

    try:
        data = make_request(url)

        for item in data['response']['groups'][0]['items']:
            venue = item['venue']
            venue_list.append(Business(venue['name'],
                                       venue['location']['address'],
                                       venue['rating'],
                                       venue['ratingSignals'],
                                       venue['stats']['checkinsCount']))
    except Exception, e:
        print e

    return venue_list

business.py

import urllib2
import json

class Business:
    def __init__(self, name, address, rating, rating_count, checkin_count):
        self.name = name
        self.address = address
        self.rating = rating
        self.rating_count = rating_count
        self.checkin_count = checkin_count

def make_request(url):
    """
    Makes a new HTTP request to the given URL

    :param url: The URL to request
    :returns: JSON response
    """

    req = urllib2.Request(url)
    response = urllib2.urlopen(req)
    data = json.loads(response.read())
    response.close()

    return data

Named tuples

Business is nothing short of a tuple where each attribute is named. Rather than going through the verbosity of writing everything out, you can just make it a namedtuple:

Business = namedtuple('Business', 'name address rating rating_count checkin_count')

Managing resources

For make_request, the preferred way to handle resources in Python is to use a context manager. For urlopen, we have contextlib.closing:

def make_request(url):
    with closing(urlopen(url)) as response:
        return json.loads(response.read())

Do you need to wrap it in Request? Not sure that gives you anything.

String formatting

Prefer the format() syntax to the % syntax. That is:

'Hello, {}'.format(name)

is better than:

'Hello, %s' % name


Split a data file into files for each time step I have written a simple code to extract different time steps from a big text file. It works for small text files, but not for bigger text files as input.

n=0
y=[]
with open ("DEPTH.dat", "r") as input:
    for x in input:
        x = x.strip()
        if x.startswith('SCALAR'):
            n += 1
        with open("TS_"+ str(n) + ".dat", "a") as subfile:
                subfile.write("{0}\n".format(x))

The input file is like the following:

SCALAR
ND   5
ST  0
TS        10.00
    0.0022
    0.0022
    0.0022
    0.0020
    0.4881
SCALAR
ND   5
ST  0
TS        100.00
    0.1
    0.2
    0.12
    0.32
    0.15
SCALAR
ND   5
ST  0
TS        200.00
    0.34
    0.25
    1.1
    1.0020
    1.4381

In this example file, the number of nodes ND=5 , so it works very well. But when I have 1,000,000 nodes, it does not work. It does not deliver any result even after 20 days. So I know I have to write the program as a function and return the result and not to upload the whole data into memory. I have no I idea  how to do that.

IO operations

Your code for each line of "DEPTH.dat" first open file in append mode, next write one line and finally close file. You may reduce open() and close() calls only to lines when 'SCALAR' line appears.

def split_less_io_operations(src_filename):
    idx = 1
    with open(src_filename, 'r') as inp:
        outfile = open("TS_before_first_SCALAR.dat", 'w')
        for line in inp:
            if line.startswith('SCALAR'):
                outfile.close()
                outfile = open("TS_{}.dat".format(idx), 'w')
                idx += 1
            outfile.write(line)
        outfile.close()

if __name__ == "__main__":
    split_less_io_operations('DEPTH.dat')


Project Euler #5 - Lowest common multiple of 1 through 20 This is my code.  All comments welcome.  Last time run it only took 335 milliseconds:

static bool CheckMultiples(int val)
{
    for (int i = 1; i <= 20; i++)
    {
        if (val % i != 0)
            return false;
    }

    return true;
}

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int Num = 20;
    while (!CheckMultiples(Num))
    {
        Num += 20;
    }

    s.Stop();

    Console.WriteLine("The smallest number divisible by all numbers 1-20 is {0}.", Num);
    Console.WriteLine("The time took is {0} milliseconds.", s.ElapsedMilliseconds);
}

There is a far more efficient approach to finding the least common multiple (\$\operatorname{lcm}\$) of a set of integers which, unlike your and rolfl's code, involves no trial-and-error. Recall that for any pair \$(a, b)\$ of natural numbers, we have
$$\operatorname{lcm}(a, b) = \frac{ab}{\operatorname{gcd}(a, b)}.$$
This reduces the implementation of \$\operatorname{lcm}\$ to the implementation of \$\operatorname{gcd}\$, which is easily done using the simple and efficient Euclidean algorithm. Then, calculating the least common multiple of \$\{1, 2, ..., 20\}\$ is as simple as \$\operatorname{reduce}(\operatorname{lcm}, \{1, 2, ..., 20\})\$.

You can find a simple Python 3 implementation of this idea in ideone here. Even in a slow interpreted language like Python, this is several orders of magnitude faster than your or rolfl's code, running in about .04 milliseconds.


'Buffered' function for Rx My application has a whole chain of Observables running through it, and recently I found that something was slowing down my (hot) source, but I couldn't work out where.

Obviously, with everything running in series by default, a good first step was to introduce some 'parallelism', so after having done battle with my own implementation, I discovered that ObserveOn did what I wanted: allow a source to 'carry on' while a subscriber did whatever.

But that didn't solve my problem of knowing where the slow bits were. Which lead me to trying to invent a Buffered function which does the buffering, but also tells me how long the buffer is.

I'm aware that this doesn't do all the fancy Rx business of giving you the choice of which scheduler and all that, but for my purposes currently Task is good enough (unless you tell me otherwise):

This is the tuple used to return data in:

public class WithBufferSize<T>
{
    public readonly T Value;
    public readonly int BufferSize;
    public WithBufferSize(T value, int bufferSize)
    {
        Value = value;
        BufferSize = bufferSize;
    }
}

Here is the function:

public static IObservable<WithBufferSize<T>> Buffered<T>(this IObservable<T> source)
{
    return Observable.Create<WithBufferSize<T>>(observer =>
    {
        var buffer = new BlockingCollection<T>();
        Exception exception = null;
        bool completed = false;
        var task = new Task(() =>
        {
            foreach(var t in buffer.GetConsumingEnumerable())
                observer.OnNext(new WithBufferSize<T>(t, buffer.Count));
            if(exception != null)
                observer.OnError(exception);
            else if(completed)
                observer.OnCompleted();
        }, TaskCreationOptions.LongRunning);
        task.Start();
        var subscription = source.Subscribe(t => buffer.Add(t),
        ex =>
        {
            exception = ex;
            buffer.CompleteAdding();
        },
        () =>
        {
            completed = true;
            buffer.CompleteAdding();
        });
        return new CompositeDisposable(
            subscription,
            Disposable.Create(() => buffer.CompleteAdding()));
    }).Publish().RefCount();
}

I originally used Materialise, but switched to using flags because it creates less objects.

Don't expose fields, even if they're readonly:

public readonly T Value;
public readonly int BufferSize;

Instead expose properties:

public T Value { get; private set; }
public int BufferSize { get; private set; }


Set and get in the same function I am attempting to write a function that returns the records that a user has selected on a grid. In this example, I grab all of them and return their IDs.

Grid.prototype.getSelectedRecords = function () {
    var self = this;

     self.selectedRecords = this.grid.selModel.getSelection().map(function (record) {
         return record.internalId;
     });

     return self.selectedRecords;
}

Here I am placing them in a object property AND returning that property. This function, in effect is working as a setter and a getter. Would it confuse other programmers that might be looking for a setter? I don't know if I want to write a setter/getter each time...

With how quirky JavaScript does object-oriented, is this bad?

First of all, I have no idea why you've got self in there. It's unnecessary (and indeed, you didn't even use it in the call to .grid.selModel...)

Secondly: I don't understand the point of setting a property in the first place. You're always returning the result of the grid.selModel... call, so the property isn't necessary. You could just have a local variable - or better yet, just return directly, with no properties or local variables. The method's just a decorator for another method's output.

Now, if the idea is that you can either use someGrid.getSelectedRecords() getter or someGrid.selectedRecords property, then you're going about things in a bad way.

If I see that I can use someGrid.selectedRecords directly, then no, it should not be overwritten if I call someGrid.getSelectedRecords(). That makes no sense. In fact, it'll cause something like this:

someGrid.getSelectedRecords() == someGrid.selectedRecords // true
someGrid.selectedRecords == someGrid.getSelectedRecords() // false

Wat?

So to directly answer your question: No, don't do what you're doing in that piece of code. But the reason why you shouldn't is because using both accessor methods and direct property access is a bad approach to begin with.

If you use getter and setter methods, your properties should be off-limits to external code. If you only use properties, you shouldn't add getter or setter methods, as they confuse the API greatly.

You could conceivably use Object.defineProperty() which'll let you, well, define a property but with explicit getter and setter functions (if the target runtime(s) support it). But frankly it's easier to just write getter and setter functions if you want to maintain a barrier between your object's instance data and the outside world.

But, again, in this particular case, your object doesn't seem to need any instance data at all as it just delegates to something else. This should work equally well, without getting properties mixed up in things:

Grid.prototype.getSelectedRecords = function () {
  return this.grid.selModel.getSelection().map(function (record) {
    return record.internalId;
  });
}

Returning the result of map and not storing has the added benefit of never returning a reference to instance data. The function will always return a brand new array.

Now, you might still want to memoize/cache those IDs, but in that case you'll be better served with "private" closure variables, rather than inherently "public" properties.

You could also go the opposite route and only use naked properties, and rely on users to use them correctly, or reap what they sow if they don't.
But that doesn't really apply here, since the method in question a shortcut for another object's method.

  I don't know if I want to write a setter/getter each time...

I can sympathize, but depending on what you're trying to accomplish you might have to.


Ruby Dynamic Struct - Pattern or AntiPattern? There is a pattern that keeps coming up in my ruby code and I'm somewhat ambivalent about it. It's somewhere between a Hash and a Struct. Basically
I used method_missing to return/set values in the Hash unless I want to
override a specific value with some logic or flatten out the complex underlying structure in the JSON. It's very flexible and quickly
allows code changes, but it also hides much of the structure of the object.

In effect, the structure is in the data ( JSON file ) and not in the code.
Is this an effective Pattern or just asking for trouble down the road?

class AttributeKeeper

    def initialize
      @attributes = Hash.new
    end

    def import
       // Special import methods usually from JSON
    end

    def export
       // Export to JSON with maybe some data verification along the way.
    end

    def special_value= (value )
        // Perform data check on special value
        @attributes[special_value] = value
    end

    def checked_value
        // Return value if passes checks.
    end

    def method_missing(meth, *args, &block)
      smeth = meth.to_s
      trim = smeth.chomp('=') #Handle setter methods.
      unless ( smeth == trim )
        @attributes[trim] = args[0]
      else
        @attributes[smeth]
      end
    end

    def responds_to?(meth)
      smeth = meth.to_s
      if( @attributes[smeth] or smeth[-1,1] == '=')
        true
      else
        super
      end
    end

end

I have the feeling that your patterns is very similar to the idea behind OpenStruct and similar libraries, such as Hashie::Mash.

So I would say, it's definitely not an anti-pattern in some cases. Such structures are very helpful when parsing and converting structured inputs, for example an API call.


Assigning projects in order of priority Let's assume we have the following situation:

Multiple project topics exist, each corresponding to a natural number n,
students can sign in and choose two projects and give them either priority_1 or priority_2,
The name and the time when they sign in is tracked as well.

With all of the information above assume you receive data in the from of a txt-file looking like this

Martin  16:46:32    8   19
Alice   15:22:56    8   12
Alex    17:23:11    19  1
John    19:02:11    11  13
Phillip 19:03:11    11  13
Diego   15:23:57    14  5
Jack    16:46:45    8   3

where the columns represent the name, time, priority 1 and priority 2 in this order. You can assume that all of them signed in on the same day and students which signed in first have a higher priority in comparison to the others.

I wanted to write a program that takes this txt-file as input and returns a txt-file with output

Name    Assigned Project
Alice   8
Diego   14
Martin  19
Jack    3
Alex    1
John    11
Phillip 13

The solution I came up with looks like this:

import numpy as np

dat = np.genfromtxt("data.txt", dtype="str")

class person:
    def __init__(self, name, time, prio1, prio2):
        self.name = name
        sp = time.split(":")
        t = sp[0]*3600 + sp[1]*60 + sp[2]
        self.time = t
        self.prio1 = prio1
        self.prio2 = prio2

names = dat[:, 0]
time = dat[:, 1]
prio1 = dat[:, 2]
prio2 = dat[:, 3]

people = []
for i,j,k,l in zip(names, time, prio1, prio2):
    people.append(person(i,j,k,l))

people_sorted_time = sorted(people, key=lambda x: x.time)

for k in range(len(people_sorted_time)):
    for j in range(k + 1, len(people_sorted_time)):
        if people_sorted_time[k].prio1 == people_sorted_time[j].prio1:
            people_sorted_time[j].prio1 = people_sorted_time[j].prio2

res = open("results","w")
res.write("Name"+"\t"+"Assigned Project"+"\n")
for k in range(len(people_sorted_time)):
    res.write(people_sorted_time[k].name + "\t"
        + people_sorted_time[k].prio1 + "\n")

The code seems to work fine, but I'm not sure if I actually was able to take care of all edge-cases. I'm also not sure if this is really a efficient way to solve the problem, I rarely code stuff like that (mostly computational physics stuff), and would appreciate any kind of suggestions on how one could improve the code in general.

EDIT: What I realized after some thinking is that it would probably be  quite hard do implement further priority variables (like prio 3, prio 4, etc.). If someone could suggest a better way of deciding how to assign the projects in terms of priority, I'd be glad to see it.

There are two issues I personally dislike very much.

Messing with date/time using homebrew algorithm and math

While looking easy to handle time/date are by far more complcated to handle than you ever can think of. Timezones, locals, leap years and so on. When doing time/date math and/or serialisation/deserialisation always(!) go for a library. For python this is datetime

When the code is lying to me when I'm reading it as natural language

With lying I mean your line

people_sorted_time[j].prio1 = people_sorted_time[j].prio2

This is not true. The person clearly stated a first priority project. When you change that value as an algorithmic side effect you immediatly break data integrity. Your person suddenly has both priorities on the same project. You even got yourself tricked. What happens, when a person got the first prio project taken away and later the second one as well?

Other issues

There is no need to have people_sorted_time, as you never refer to the read order again. Just do

people = sorted(people, key=lambda x: x.time)

Never loop over range(len(something), always try to loop over the elements directly. Your output loop rewrites (still lying about prio1) to

for p in people:
    res.write(p.name + "\t" + p.prio1 + "\n")

You use numpy only for reading a file, then convert back to standard python. This is a fail. Read with python directly.

with open("data.txt") as infile:
    lines = infile.readlines()
people = [Person(*line.split()) for line in lines]

You need time for comparison only. There is no need to mess with it, string comparison will do.

self.time = time

Do not modify the people data but maintain a set of available projects

prio1_projects = set(p.prio1 for p in people)
prio2_projects = set(p.prio2 for p in people)
projects_available = prio1_projects | prio2_projects

When assigning projects we do it like

people = sorted(people, key = lambda p: p.time)
assignments = []
for p in people:
    if p.prio1 in projects_available:
        proj = p.prio1
    elif p.prio2 in projects_available:
        proj = p.prio2
    else:
        proj =  None
    assignments.append(proj)
    if proj is not None:
        projects_available.remove(proj)

Note the new None case.

The output code

with open("results","w") as res:
    res.write("Name"+"\t"+"Assigned Project"+"\n")
    for p, a in zip(people, assignments):
        res.write(p.name + "\t" + str(a) + "\n")


Scan a webpage to find the start time and date for an event I am working on a simple web crawler that returns the start time and date for an event listed on a webpage. The webpage can be in two different formats and there are multiple other dates listed on the page. The part of the webpage I am scanning looks like this:

...

Time

        Starts: <time itemprop="startDate" datetime="2017-03-13T17:30:00ADT">Monday March 13, 2017 - 05:30 PM</time>

        Ends: <time itemprop="endDate" datetime="2017-03-13T19:00:00ADT">Monday March 13, 2017 - 07:00 PM</time>

Additional Dates/Times

        Starts: <time>Monday January 30, 2017 - 05:30 PM</time>

        Ends: <time>Monday January 30, 2017 - 07:00 PM</time>

Location

...

or like this:

...

Time

    <time itemprop="startDate" datetime="2017-03-17T13:30:00ADT">Friday March 17, 2017 - 01:30 PM</time>

Location

....

After using BeautifulSoup to find the links I am interested in I pass the link to these methods which find the text between 'Time' and 'Location'. Next it searches for a tag in that code block '">" which I know only appears before the date text and scans until the next closing tag, returning a date string.

MAX_CHARS = 140

def get_date(link):
    date_text = ""
    event_html = urllib2.urlopen(link['href']).read()
    start = find_date_location(event_html)
    # after the datetime closing tag the date begins until another tag opens
    for x in range(start, start + MAX_CHARS):
        if event_html[x] == '<':
            break
        date_text += event_html[x]

    return date_text

def find_date_location(html):
    date_starts = html.find('
Time
')
    date_ends = html.find('
Location
')
    for x in range(date_starts, date_ends):
        if html[x] + html[x+1] == '">':
            return x+2

    raise ValueError('Date not found in HTML within time range')

This would return "Monday March 13, 2017 - 05:30 PM" in the first case and "Friday March 17, 2017 - 01:30 PM" in the second case. My method seems really hacky. Any tips on how I could do this better?

Your current approach is very fragile and might easily break if the markup changes even slightly - imagine, for example, opening and closing h4 being on separate lines while still being a valid HTML element.

I would use a proper HTML parser like BeautifulSoup instead (you mentioned you've already tried it). In order to locate the start and end dates, we may use the itemprop attribute:

from bs4 import BeautifulSoup

def get_even_date_range(html):
    soup = BeautifulSoup(html, 'html.parser')

    start_date = soup.find("time", itemprop="startDate")
    end_date = soup.find("time", itemprop="endDate")

    return (start_date.get_text() if start_date else None,
            end_date.get_text() if end_date else None)

Here, the get_even_date_range() function would return a tuple with start and end dates as items. It would return None if a date is not found. For the first sample input HTML, it would return:

('Monday March 13, 2017 - 05:30 PM', 'Monday March 13, 2017 - 07:00 PM')

And, for the second:

('Friday March 17, 2017 - 01:30 PM', None)

You can then go further and convert the date strings to datetimes using the datetime.strptime() and the %A %B %d, %Y - %H:%M %p format:

from datetime import datetime
from bs4 import BeautifulSoup

DATE_FORMAT = "%A %B %d, %Y - %H:%M %p"

def get_date(date_element):
    return datetime.strptime(date_element.get_text(), DATE_FORMAT) if date_element else None

def get_even_date_range(html):
    soup = BeautifulSoup(html, 'html.parser')

    start_date = soup.find("time", itemprop="startDate")
    end_date = soup.find("time", itemprop="endDate")

    return get_date(start_date), get_date(end_date)

Note that I've also moved the repetitive date retrieval logic to a separate reusable get_date() function.


Parsing Windows Bitmap header information I am working a a C# program that will manipulate bitmap images. The first step is to read in the File Header and the Windows BITMAPINFOHEADER.

That will give me enough information to loop through pixels and do my manipulations.

Here is the class that reads the file header,

using System;
using System.IO;

namespace Bitmanipulate
{
    public class BMPFileHeader
    {
        char[] header_field = new char[2];
        private uint file_byte_size;
        private uint pixel_start;

        public BMPFileHeader(BinaryReader br)
        {
            br.BaseStream.Seek(0, SeekOrigin.Begin);
            header_field[0] = br.ReadChar();//1
            header_field[1] = br.ReadChar();//2
            file_byte_size = br.ReadUInt32();//6
            br.ReadUInt16();//8
            br.ReadUInt16();//10
            pixel_start = br.ReadUInt32();//14
        }

        public void show()
        {
            Console.WriteLine("Header Field");
            Console.WriteLine(header_field);
            Console.WriteLine("File size bytes");
            Console.WriteLine(file_byte_size);
            Console.WriteLine("Pixel Start");
            Console.WriteLine(pixel_start);
        }
    }
}

and here is the class reads the Windows BITMAPINFOHEADER

using System;
using System.IO;

namespace Bitmanipulate
{
    public class BMPHeaderReader
    {

        private uint header_size;
        private uint pixel_width;
        private uint pixel_height;
        private ushort pixel_depth;
        private uint row_size;
        private uint padding_bits;
        private uint padding_bytes;
        private uint width_bytes;
        private uint pixels;

        public BMPHeaderReader(BinaryReader br)
        {
            br.BaseStream.Seek(14, SeekOrigin.Begin);
            header_size = br.ReadUInt32();//18
            pixel_width = br.ReadUInt32();//22
            pixel_height = br.ReadUInt32();//26
            br.ReadUInt16();//28
            pixel_depth = br.ReadUInt16();//30
            row_size = (((pixel_depth * pixel_width) + 31) / 32) * 4;
            padding_bits = row_size * 8 - ((pixel_width * pixel_depth));
            padding_bytes = row_size - ((pixel_width * pixel_depth) / 8);
            width_bytes = (pixel_width * pixel_depth) / 8;
            pixels = pixel_height * pixel_width;
        }

        public void show()
        {
            Console.WriteLine("Header size");
            Console.WriteLine(header_size);
            Console.WriteLine("Pixel Width");
            Console.WriteLine(pixel_width);
            Console.WriteLine("Pixel Height");
            Console.WriteLine(pixel_height);
            Console.WriteLine("Pixel Depth");
            Console.WriteLine(pixel_depth);
            Console.WriteLine("Pixels");
            Console.WriteLine(pixels);
            Console.WriteLine("Row size");
            Console.WriteLine(row_size);
            Console.WriteLine("Padding bits");
            Console.WriteLine(padding_bits);
            Console.WriteLine("Padding bytes");
            Console.WriteLine(padding_bytes);

        }
    }
}

I have omitted the getters for clarity.

As this is basically my first ever C# program, is there anything that I am missing?

First of all, don't use underscores in fields names. Fields like header_size, pixel_width and so on should be renamed to headerSize, pixelWidth. You should use camelCase for private fields, parameters and local variables. Also don't shorten parameters. Use binaryReader instead of br.

All methods in C# should be PascalCased. It means you should change show to Show.

I'm personally not a fan of passing streams and readers in constructors to initialize an instance of some class. In my opinion constructor should be as simple as possible, without reading from streams and heavy calculations. Ideally it should take only parameters that will be stored to fields or properties.

In you case I would change this code:

public BMPFileHeader(BinaryReader br)
{
    br.BaseStream.Seek(0, SeekOrigin.Begin);
    header_field[0] = br.ReadChar();//1
    header_field[1] = br.ReadChar();//2
    file_byte_size = br.ReadUInt32();//6
    br.ReadUInt16();//8
    br.ReadUInt16();//10
    pixel_start = br.ReadUInt32();//14
}

to

private const int HeaderFieldSize = 2;

private char[] _headerField = new char[HeaderFieldSize];
private uint _fileByteSize;
private uint _pixelStart;

public BMPFileHeader(char[] headerField, uint fileByteSize, uint pixelStart)
{
    _headerField = headerField;
    _fileByteSize = fileByteSize;
    _pixelStart = pixelStart;
}

public static BMPFileHeader Read(BinaryReader binaryReader)
{
    binaryReader.BaseStream.Seek(0, SeekOrigin.Begin);

    var headerField = binaryReader.ReadChars(HeaderFieldSize);
    var fileByteSize = binaryReader.ReadUInt32(); // 6

    binaryReader.ReadUInt16(); // 8
    binaryReader.ReadUInt16(); // 10

    var pixelStart = binaryReader.ReadUInt32(); // 14

    return new BMPFileHeader(headerField, fileByteSize, pixelStart);
}

And the same approach I would apply in BMPHeaderReader.

Instead of this code:

Console.WriteLine("Header size");
Console.WriteLine(header_size);
Console.WriteLine("Pixel Width");
Console.WriteLine(pixel_width);
Console.WriteLine("Pixel Height");
Console.WriteLine(pixel_height);
Console.WriteLine("Pixel Depth");
Console.WriteLine(pixel_depth);
Console.WriteLine("Pixels");
Console.WriteLine(pixels);
Console.WriteLine("Row size");
Console.WriteLine(row_size);
Console.WriteLine("Padding bits");
Console.WriteLine(padding_bits);
Console.WriteLine("Padding bytes");
Console.WriteLine(padding_bytes);

you can write

Console.WriteLine(string.Join(Environment.NewLine,
                              new object[]
                              {
                                  "Header size",   headerSize,
                                  "Pixel Width",   pixelWidth,
                                  "Pixel Height",  pixelHeight,
                                  "Pixel Depth",   pixelDepth,
                                  "Pixels",        pixels,
                                  "Row size",      rowSize,
                                  "Padding bits",  paddingBits,
                                  "Padding bytes", paddingBytes
                              });


2D grid Hamiltonian path puzzle solver The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, s) and obstacles (denoted below by X's). The objective of the puzzle is to find a path starting at the starting point and going through each empty space exactly once (a Hamiltonian path). You can't, of course cross the obstacles. You can move horizontally and vertically. A typical puzzle would look like this:

......
.SX...
...X..
.....X
......
XX....
......

And its solution:

11 12 13 14 17 18
10 1  X  15 16 19
9  2  3  X  21 20
8  5  4  23 22 X
7  6  25 24 29 30
X  X  26 27 28 31
37 36 35 34 33 32

I wrote a solver in Python 3 (I later learned that this algorithm is actually a simple DFS). It solves the puzzle above in ~0.9 s, which is very good, but I was wondering if I can perhaps optimize it somehow.

import time

EMPTY_SPACE_SYMBOLS = ['.']
STARTING_POINT_SYMBOLS = ['S', 's']
OBSTACLE_SYMBOL = 'X'
PUZZLE_PATH = "grid.txt"
DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)]

start_time = time.time()

grid = open(PUZZLE_PATH).read().splitlines()
H = len(grid)
W = len(grid[0])
assert all(len(row) == W for row in grid), "Grid not rectangular"

def print_solution(coords):
    result_grid = [[OBSTACLE_SYMBOL for _ in range(W)] for _ in range(H)]
    for i, (r, c) in enumerate(coords, start=1):
        result_grid[r][c] = i
    str_grid = [[str(item).ljust(3) for item in row] for row in result_grid]
    print('\n'.join(' '.join(row) for row in str_grid))

def extend(path, legal_coords):
    res = []
    lx, ly = path[-1]
    for dx, dy in DIRS:
        new_coord = (lx + dx, ly + dy)
        if new_coord in legal_coords and new_coord not in path:
            res.append(path + [new_coord])
    return res

start_pos = None
legal = set()
for r, row in enumerate(grid):
    for c, item in enumerate(row):
        if item in STARTING_POINT_SYMBOLS:
            assert start_pos is None, "Multiple starting points"
            start_pos = (r, c)
        elif item in EMPTY_SPACE_SYMBOLS:
            legal.add((r, c))

assert start_pos is not None, "No starting point"

TARGET_PATH_LEN = len(legal) + 1
paths = [[start_pos]]
found = False
number_of_solutions = 0

while paths:
    cur_path = paths.pop()
    if len(cur_path) == TARGET_PATH_LEN:
        number_of_solutions += 1
        if not found:
            print_solution(cur_path)
            print("Solution found in {} s".format(time.time() - start_time))
        found = True
    paths += extend(cur_path, legal)

print('Total number of solutions found: {} (took: {} s)'.format(number_of_solutions, time.time() - start_time))

1. Review

Code is easier to test (and measure the performance) if it's organized into functions or classes. In this case you have persistent data (W, H, grid, legal, start_pos) that's shared between the various parts of the code, so a class would be the best way to go here.
It would be simpler to write:

EMPTY_SPACE_SYMBOLS = '.'
STARTING_POINT_SYMBOLS = 'Ss'

since Python can iterate over the characters in a string just as easily as over the items in a list.
Assertions should be reserved for detecting programming errors, and not used for reporting problems with the input. That's because assertions can be disabled via the -O option to the Python interpreter, or the PYTHONOPTIMIZE environment variable. For the errors in this code, you should raise exceptions.
It's more general to have a method format_solution that returns a string, rather than a function print_solution that prints it. That way the caller has the option of deciding what to do with it.
Instead of:

[OBSTACLE_SYMBOL for _ in range(self.w)]

write:

[OBSTACLE_SYMBOL] * self.w

Instead of building str_grid from result_grid and then formatting the former, just format result_grid directly:

'\n'.join(' '.join(str(item).ljust(3) for item in row)
          for row in result_grid)

The number "3" only works for small enough puzzles. To make the formatting work in the general case, it should be one more than the maximum number of digits in any number in the path, that is:

len(str(len(path) + 1)) + 1

extend is only called from one place in the code, so it would make sense to inline it at that point.
Coordinates are r and c in some places in the code, and x and y in other places. It would be better to be consistent.

2. Revised code

import time

EMPTY_SPACE_SYMBOLS = '.'
STARTING_POINT_SYMBOLS = 'Ss'
OBSTACLE_SYMBOL = 'X'
DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)]

class HamiltonSolver:
    """Solver for a Hamilton Path problem."""

    def __init__(self, grid):
        """Initialize the HamiltonSolver instance from a grid, which must be a
        list of strings, one for each row of the grid.

        """
        self.grid = grid
        self.h = h = len(grid)
        self.w = w = len(grid[0])
        if any(len(row) != w for row in grid):
            raise ValueError("Grid is not rectangular")
        self.start = None
        self.legal = set()
        for r, row in enumerate(grid):
            for c, item in enumerate(row):
                if item in STARTING_POINT_SYMBOLS:
                    if self.start is not None:
                        raise ValueError("Multiple starting points")
                    self.start = (r, c)
                elif item in EMPTY_SPACE_SYMBOLS:
                    self.legal.add((r, c))
        if self.start is None:
            raise ValueError("No starting point")

    def format_solution(self, path):
        """Format a path as a string."""
        grid = [[OBSTACLE_SYMBOL] * self.w for _ in range(self.h)]
        for i, (r, c) in enumerate(path, start=1):
            grid[r][c] = i
        w = len(str(len(path) + 1)) + 1
        return '\n'.join(''.join(str(item).ljust(w) for item in row)
                         for row in grid)

    def solve(self):
        """Generate solutions as lists of coordinates."""
        target_path_len = len(self.legal) + 1
        paths = [[self.start]]
        while paths:
            path = paths.pop()
            if len(path) == target_path_len:
                yield path
            r, c = path[-1]
            for dr, dc in DIRS:
                new_coord = r + dr, c + dc
                if new_coord in self.legal and new_coord not in path:
                    paths.append(path + [new_coord])

PUZZLE_GRID = '''
......
.SX...
...X..
.....X
......
XX....
......
'''.split()

def main():
    start_time = time.time()
    n_solutions = 0
    puzzle = HamiltonSolver(PUZZLE_GRID)
    for solution in puzzle.solve():
        if n_solutions == 0:
            print(puzzle.format_solution(solution))
            print("First solution found in {} s"
                  .format(time.time() - start_time))
        n_solutions += 1
    print("{} solution{} found in {} s"
          .format(n_solutions, '' if n_solutions == 1 else 's',
                  time.time() - start_time))

if __name__ == '__main__':
    main()

3. Speeding it up

Each time extend is called, the list of paths under consideration is extended by up to four new paths, each of which is a copy of the current path plus one new grid coordinate. As the search progresses, this results in many paths being created and stored (up to 20 paths in the example from the post).

But in a depth-first search it should be only be necessary to remember a single path at a time, together with the current position in the iteration over the four directions. (This is the "stack of iterators" pattern.)
The code checks to see if the new coordinate is available by calling new_coord in self.legal and new_coord not in path. But path is a list, and testing for membership in a list is not efficient (Python has to compare the new coordinate with every item in the list). For efficient membership testing you need a set.

In this case the code already has a set of legal coordinates. So we can remove a coordinate from this set when we add it to the path, and add it back to the set when we backtrack. This means we only need one membership test, and it also means that the path is complete when the set of legal coordinates is empty.
We can speed up the inner loop by caching method lookups like path.append in local variables.

The revised solve method looks like this:

def solve(self):
    """Generate solutions as lists of coordinates."""
    path = [self.start]
    dirs = [iter(DIRS)]

    # Cache attribute lookups in local variables
    path_append = path.append
    path_pop = path.pop
    legal = self.legal
    legal_add = legal.add
    legal_remove = legal.remove
    dirs_append = dirs.append
    dirs_pop = dirs.pop

    while path:
        r, c = path[-1]
        for dr, dc in dirs[-1]:
            new_coord = r + dr, c + dc
            if new_coord in legal:
                path_append(new_coord)
                legal_remove(new_coord)
                dirs_append(iter(DIRS))
                if not legal:
                    yield path
                break
        else:
            legal_add(path_pop())
            dirs_pop()

On the example from the post this is more than 2½ times as fast as the original code.

Update You asked in comments how this works. Well, the list path contains the current path reached in the search. The list dirs is the same length as path, and each element is an iterator over the list DIRS. Each iterator remembers where we got to in the list of directions at that point in the search, so that when we backtrack we can pop the dirs list and then continue iterating from where we left off.

The control flow is slightly tricky. When the path is extended it reaches the break statement, which breaks out of the for loop (bypassing the else) and so goes back to the top of the while loop, picking up the new coordinates that we just added to the path. But when no further progress can be made, the for loop runs out of directions and enters the else clause. This causes  path and dirs to be popped and then the while loop picks up from the previous point reached in the search.

I hope that's clear. If you're still not quite sure, step through the code in the Python debugger so that you can see exactly what it's doing.


Linked List: Smart Pointer Implementation Linked list using smart pointers, iterative implementation. It amazes me how a std::forward_list does not allow the list to be walked until the last pointer is null.

I would appreciate if you could pay special attention to usage of shared_ptr.

#include <iostream>
#include <string>
#include <memory>
#include <cmath>

const int SIZE=7;

struct Node {
    int val;
    std::shared_ptr<Node> next;
};
std::shared_ptr<Node> newNode(int v) { // Create and return new node
    std::shared_ptr<Node> n(new Node);
    n->val = v;
    n->next = NULL;
    return n;
}
void print(std::shared_ptr<Node> r) { // Print the list
    while (r != NULL) {
        std::cout << r->val << ' ';
        r = r->next;
    }
    std::cout << std::endl;
}
int main() {
    std::shared_ptr<Node> root(new Node), last;
    srand(time(NULL));
    root->val = rand();
    root->next = NULL;
    last = root;
    for (int i=1; i<SIZE; ++i) { // Build the list
        last->next = newNode(rand());
        last = last->next;
    }
    last->next = NULL;
    print(root);
    std::cout << std::endl;
    return 0;
}

I would appreciate if you could pay special attention to usage of shared_ptr.

This fills me with dread. It implies that you want every node to have shared ownership. My question would be, "shared with what? another list?".

shared_ptr contains code for thread-safe reference counting. For this reason, use of a shared_ptr in a single-threaded program brings with it an unnecessary overhead.

There may be some use cases for sharing nodes - for example in a directed graph structure. In this case, almost any other container for holding node pointers would be superior to a linked list.

Before I can continue the review, I'd have to ask what the intended use-case of the list is.

After comments, here's an implementation that uses unique_ptr. Comments inline.

You will see that I have dropped the last pointer as it's not required. If you want 2-way linkage then use a ptr_type for the forward pointer and an observer_type for the back-link.

#include <iostream>
#include <string>
#include <memory>
#include <cassert>

const int SIZE=7;

// create the concept of an observer-only deleter
struct observer_only {
    template<class Any>
    void operator()(Any*) const noexcept {
        // nop
    }
};

// abstract the pointer type so we can change it if we don't like it
template<class Node> using ptr_type = std::unique_ptr<Node>;

// create the concept of an observer-only pointer
template<class Node> using observer_type = std::unique_ptr<Node, observer_only>;

// a means of converting a raw pointer to an observer
template<class Node> auto observe(Node* ptr) {
    return observer_type<Node>(ptr);
}

// a means of creating an observer to an owning pointer
template<class Node> auto observe(ptr_type<Node> const& ptr) {
    return observe(ptr.get());
}

struct Node {
    Node(int i)
            : val(i)
    {}

    // member function to add nodes provides logical encapsulation
    observer_type<Node> insert_after(ptr_type<Node>&& ptr) {
        assert(ptr.get());
        assert(ptr->next.get() == nullptr);
        ptr->next = std::move(this->next);
        this->next = std::move(ptr);
        return observe(this);
    }

    int val;
    ptr_type<Node> next = nullptr;
};

// node generator
ptr_type<Node> newNode(int v) { // Create and return new node
    ptr_type<Node> n(new Node(v));
    return n;
}

// print an observer
void print(observer_type <Node> o) { // Print the list
    for ( ; o.get() != nullptr ; o = observe(o->next))
    {
        std::cout << o->val << ' ';
    }
    std::cout << std::endl;
}

// print a node
void print(ptr_type<Node> const& r) { // Print the list
    print(observe(r));
}

// test
int main() {
    srand(time(NULL));
    auto root = newNode(rand());
    auto observer = observe(root);
    for (int i=1; i<SIZE; ++i) { // Build the list
        observer = observer->insert_after(newNode(rand()));
    }
    print(root);
    std::cout << std::endl;
    return 0;
}

Explanation of architectural approach

As requested in comments.

The the old days of assembler or C I'd have implemented a singly linked list (the second-simplest of all data structures) as merely a node containing a value and a pointer (address) to the next node. Of course we'd have to remember to destroy the node when removing it. We'd also have to remember whether a pointer "owned" (controlled the lifetime of) a node, or was merely an observer.

In modern c++, there are at least 2 enhancements available. First of course, we have RAII and smart pointers, so the destruction timing is always correct. Second, we can use types to indicate roles.

In the above code, I have two pointer types. One is an "owner" pointer and one is an "observer". These are both specialisations of unique_ptr in my code, but I could have written my own. However, using unique_ptr, I have some built in advantages:

a unique_ptr cannot be copied, so I cannot cause myself problems by accidentally sharing ownership.
even though the owning and non-owning pointers have different deleters (the observer's deleter is a no-op), they have the same interfaces. This makes generic programming easy.

In c++17, there is a template called std::observer_ptr, which is designed to perform the same role as my observer_type.

Now I can use the owner_type to handle the forward node linkages. This gives me clean RAII and firm ownership of nodes. It also mean that I can implement a remove function which returns the removed node pointer. I can then re-insert that node pointer into another list, or discard it (let it go out of scope). Either way, because it's controlled by an auto-deleting unique_ptr, the code will be correct. No leaks.

All operations on the list that do not affect lifetimes are done through an observer (there is a free function to create an observer from an owner). This provides both a visual cue to a maintainer, plus a compiler guarantee, that I won't accidentally mutate lifetimes when I am supposed to be observing or merely mutating the value held in the node.

fully linked list

OK, but how would I implement a linked list this way (i.e. with back-links as well as forward-links)?

We'd pick an 'owning' direction. Lets say forwards. Nodes would contain an owner_type pointing to and owning the next node, and an observer_type pointing to the previous node.

The list 'begin' pointer is an owner_type, the list's 'end' is an observer_type.

The Node would look something like this:

struct Node
{
    int value;  // my value type

    owner_type<Node>    next;   // pointer to the next node
    observer_type<Node> prev;   // observer of the previous node.
};

Inserting an removing nodes is the same as if they were raw pointers, it's just that we need to assign the pointers using std::move, because they're not copyable.

This is good, because it shows graphically in the code what we are trying to achieve. It forces us to spell out our intentions. If the code is later modified, it will be more difficult to introduce a logic error, because logically incorrect code won't compile.


Golang unbuffered channel - Correct Usage Here is an example where I'm trying to understand the concepts of buffered channels> I have three functions and create a buffered channel of length 3. And also passed a waitgroup to nofiy when all the goroutines are done. And finally collecting the values through range.
Could you please help me in reviewing this code? And where I could improve?
package main

import (
    "fmt"
    "sync"
)

type f func(int, int, chan int, *sync.WaitGroup)

func add(x, y int, r chan int, wg *sync.WaitGroup) {
    fmt.Println("Started Adding function....")
    r <- (x + y)
    wg.Done()
}

func sub(x, y int, r chan int, wg *sync.WaitGroup) {
    fmt.Println("Started Difference function")
    r <- (x - y)
    wg.Done()
}

func prod(x, y int, r chan int, wg *sync.WaitGroup) {
    fmt.Println("Started Prod function")
    r <- (x * y)
    wg.Done()
}

func main() {
    var operations []f = []f{add, sub, prod}
    ch := make(chan int, len(operations))
    wg := sync.WaitGroup{}

    x, y := 10, 20

    wg.Add(len(operations))
    for _, i := range operations {
        go i(x, y, ch, &wg)
    }
    wg.Wait()
    close(ch)
    for val := range ch {
        fmt.Println(val)
    }

}

I've majorly written the review comments inline with the code. I could've made the code simple as @thwd suggested; but as you're learning and this is not an actual use case, I'm not changing the logic.
Also, to know about buffered channels better, do read this.
package main

import (
    "fmt"
    "sync"
)

// As goroutine could schedule in any order, it's better if the
// operation is stored as well, with the result.
type result struct {
    op string
    v  int
}

// It's better to use unidirectional channels if bi-directional
// is not needed. It can also distinguish how a channel should be used
// in different function/ methods (eg. producer, consumer)
type fn func(int, int, chan<- result, *sync.WaitGroup)

func add(x, y int, r chan<- result, wg *sync.WaitGroup) {
    fmt.Println("op: add")
    r <- result{"add", x + y}
    wg.Done()
}

func sub(x, y int, r chan<- result, wg *sync.WaitGroup) {
    fmt.Println("op: sub")
    r <- result{"sub", x - y}
    wg.Done()
}

func prod(x, y int, r chan<- result, wg *sync.WaitGroup) {
    fmt.Println("op: prod")
    r <- result{"prod", x * y}
    wg.Done()
}

func main() {
    // In case of multiple declaration, you can group
    // But it's totally dependent on the developer writing it.
    // But the ultimate goal is write clean code.
    var (
        fops = []fn{add, sub, prod}
        ch   = make(chan result, len(fops))
        wg   sync.WaitGroup
        x, y = 10, 20
    )

    wg.Add(len(fops))
    for _, f := range fops {
        go f(x, y, ch, &wg)
    }

    wg.Wait()
    close(ch)

    // Either use range, or you run a loop from [0, len(fops));
    // that would work as well!
    for v := range ch {
        fmt.Println(v)
    }
}