Missing element from array (D&C) - code design/aesthetic improvement I am trying to implement in C/C++ a 'classical' Divide and Conquer algorithm which solves the following problem "Given an array of n-1 numbers (int) from 0 to n, find the missing number".

I am using the typical algorithm:
start from MSB
(1) find out how many bits of 1, 0 I should have (MSB bits)
(2) find out how many bits of 1, 0 I actually have (MSB bits)

split the array into 2 subarrays: one with MSBs of 0, the other with MSBs of 1.
By using (1) and (2) I figure out in which subarray my number should be and I recursively call the function for the next bit (MSB-1), until my subarray contains only 1 element.

I've written the code, and it works, but I have the feeling that it isn't really that aesthetic (the function has a lot of parameters), because I had some difficulties.

Let's say that we have v = {0,1,2,3,5,6,7}.
exp1 = 4 (expected number of "1" MSB bits).
I know how to calculate exp1, because I know that one number is missing from 0 to 7.
act1 = 3 (actual ...)
So, we will have something like this: 0 1 2 3 | 5 6 7.
Because act1 < exp1, we recursively call the function for the 5 6 7 part and for MSB-1.

exp1 = ? I will be unable to calculate this, because I will have no information upon the missing number. That is why I use the flagR and flagL flags. So that I know which part of the array I recursively called in order to compute exp1. But I really don't like the fact that I have been forced to use this 'trick'.

I have noticed myself that I should've forced an order in the partitioning process: the numbers that have 0 as MSB (current MSB) should be in the first part, the others in the second. I will rewrite the code.

The main() function isn't really that important for now, it serves for testing, currently.

Here is my spaghetti code:

#include <cstdio>
#include <cmath>

// get bit #j from int i
unsigned int get_bit(int i, int j)
{
  return i & (1<<j);
}

int find(int v[], int left, int right, int max_bit, int flagL, int flagR)
{
  if (left == right)
    if (flagR != 0)
      return v[left] + 1;
    if (flagL != 0)
      return v[left] - 1;
  else
  {
    int exp0 = 0; // expected bits of 0
    int act0 = 0; // actual bits of 0
    int act1 = 0; // actual bits of 1
    int exp1 = 0; // expected bits of 1

    for (int i=left+flagL;i<=right+flagR;i++)
      if (get_bit(i,max_bit) == 0)
        exp0++;
      else
        exp1++;

    for (int i=left;i<=right;i++)
      if (get_bit(v[i],max_bit) == 0)
        act0++;
      else
        act1++;

    // val_cur is the max_bit of the pivot (v[right])
    unsigned int val_cur = get_bit(v[right],max_bit);
    int i = 0;
    int k = 0;
    int man = 0;

    // divides the array into 2 subarrays
    // one subarray contains elements with max_bit = 0
    // the other contains elements with max_bit = 1
    for (k=1;k<right;k++)
    {
      if (get_bit(v[k],max_bit) == val_cur)
      {
        i++;
        man = v[i];
        v[i] = v[k];
        v[k] = man;
      }
    }
    i++;
    man = v[i];
    v[i] = v[k];
    v[k] = man;
    // i is the "border" between the subarrays

    // recursively call the function for the next bit (max_bit-1)
    // and with the correct partition
    if (get_bit(v[i],max_bit) == 1)
      if (act1 < exp1)
        return find(v,left,i,max_bit-1,0,1);
      else
        return find(v,i+1,right,max_bit-1,-1,0);
    else
      if (act0 < exp0)
        return find(v,left,i,max_bit-1,0,1);
      else
        return find(v,i+1,right,max_bit-1,-1,0);
  }
}

int main()
{
  int n = 7;
  int v[] = {7,0,4,1,3,6,2};

  // find the maximum number of bits
  int bits = 0;
  bits = floor(log(n*1.0)/log(2*1.0));

  // call the function
  printf("%d",find(v,0,6,bits,0,1));
  return 0;
}

I don't follow the definition:

"Given an array of n-1 numbers (int) from 0 to n, find the missing number".

So if n == 7, as in your example code, there should be 6 numbers (n-1) in the
array.  There are 8 numbers in the the range "0 to n" (0,1,2,3,4,5,6,7).
Perhaps the problem definition meant "0 to n-1" or "0 up to n, not including
n".

Your example code has seven numbers and n == 7:

int n = 7;
int v[] = {7,0,4,1,3,6,2};

I would expect n to be 8 for an array of 7 numbers where one of the 8 is
missing.

Anyway, your example works, printing '5', but if you replace, say the 2 with a 5
it now prints '3'.  Unless I messed up!

On the code, C ignores white space (unlike say Python).  Look at the
if-else chain at the beginning of find:

if (left == right)
  if (flagR != 0)
    return v[left] + 1;
  if (flagL != 0)
    return v[left] - 1;
else
{
  int exp0 = 0; // expected bits of 0

According to the indentation of statements, you intended the if (flagR != 0)
and if (flagL != 0) to be dependent upon left == right, as in:

if (left == right) {
    if (flagR != 0) {
        return v[left] + 1;
    }
    if (flagL != 0) {
        return v[left] - 1;
    }
}
else {
    int exp0 = 0; // expected bits of 0

But what the compiler will see is

if (left == right) {
    if (flagR != 0) {
        return v[left] + 1;
    }
}
if (flagL != 0) {
    return v[left] - 1;
}
else {
    int exp0 = 0; // expected bits of 0

If you get the editor to re-indent the code for you (or use UNIX indent
command), you will see that your indenting is wrong.  The lesson is always to
use braces to say explicitly what you mean.

The same goes for your other expressions:

for (int i=left+flagL;i<=right+flagR;i++)
  if (get_bit(i,max_bit) == 0)
    exp0++;
  else
    exp1++;

should be more like this:

for (int i = left + flagL; i <= right + flagR; i++) {
    if (get_bit(i, max_bit) == 0) {
        exp0++;
    } else {
        exp1++;
    }
}

In this case, there is no misunderstanding by the compiler but you should add the braces nevertheless - consider what happens if you don't add explicit braces with:

for (int i=left+flagL;i<=right+flagR;i++)
  if (get_bit(i,max_bit) == 0)
    exp0++;
  else
    exp1++;
    something_else();


New features for Processing game/desk accessory I have written a simple desk accessory in Proccessing called Trip, you can see it below. It is working, but it is very simple, and needs more features.

import processing.pdf.*;

PImage tardis;
int flash = 0;

void setup() {
  size(256, 256);
  frame.setResizable(true);
  tardis = loadImage("TARDIS1.jpg");
  beginRecord(PDF, "trip.pdf");
  background(random(100), random(100), random(100));
  randomSeed(299792458);
}
void draw() {
  stroke(random(100), random(100), random(100));
  line(random(width), random(height), mouseX, mouseY);
  if (flash == 1) {
    background(random(100), random(100), random(100));
  }
}
void keyPressed() {
  if (key == 's') {
    endRecord();
    exit();
  }
  else if (key == 'q') {
    exit();
  }
  else if (key == 'b') {
    background(random(100), random(100), random(100));
  }
  else if (key == 't') {
    image(tardis ,0 ,0, width, height);
  }
  else if (key == 'f') {
    if (flash == 0) {
      flash = 1;
    }
    else if (flash == 1) {
      flash = 0;
    }
  }
}

I would appreciate any new ideas for features, particularly Easter egg-style secret features.

How about something where if you change the background to a particular color, something cool happens?

Like if it turns full black,(0,0,0), it causes an image to pop up on screen.


Assign value based on 100s of switch statement In the following code I have potentially hundreds of possible cases. (This is just a small subset.) Is there some way to more effectively set state.dimensionQty based on the string held in state.dimensionType? For example, some kind of function or loop, that would make switch less imperative?

Simply put, state.dimensions contains all possible dimension measurement, and the user has specified a dimensionType that they would like to save.

Example is Vue.js code within Vuex, but the general case is relevant too.

switch (state.dimensionType) {
    case 'quantity':
      state.dimensionQty = state.dimensions.quantity
      break
    case 'in':
      state.dimensionQty = state.dimensions.in
      break
    case 'm':
      state.dimensionQty = state.dimensions.m
      break
    case 'cm':
      state.dimensionQty = state.dimensions.cm
      break
    case 'ft':
      state.dimensionQty = state.dimensions.ft
      break
    case 'yd':
      state.dimensionQty = state.dimensions.yd
      break
    default:
      throw new Error(
        'No dimension type specified.'
      )
  }

If state.dimensionType is always an exact key match for a value in state.dimensions, and assuming that the default means the key doesn't exist, then you can do a lookup, for example:

if (!state.dimensions.hasOwnProperty(state.dimensionType)) {
  throw new Error('No dimension type specified');
}

state.dimensionQty = state.dimensions[state.dimensionType];


Getting and setting a static variable [Bindable]
public class ProductsCache
{
    private static var _products:ArrayCollection;

    public function get products():ArrayCollection{
        return _products;
    }
    public function set products(value:ArrayCollection):void{
        _products = value;
    }
}

By the name of the class you see my intentions with this bit of code. I intend to set a "cache" of registries that I intend to use across modules and update accordingly. The get method is used for dropdown lists, the set method after a successful insert statement.

This works good for my needs. But I still need your feedback.

EDIT: I don't know what voting means here. Is this good code for its purpose? or do I really need to learn factories and dependency injections?

I was previously using a singleton for this, but I wasn't comfortable with that, I want to keep the singleton excusively for credential and config data. And use this for the rest of the app functionality.

Using a static variable will have the same effect as using a singleton!
Imagine if you had two instances of ProductsCache:
var a: ProductsCache = new ProductsCache();
var b: ProductsCache = new ProductsCache();
a.products = someArrayCollection;
b.products = anotherArrayCollection;

Now, because it's using a static variable, a.products will be anotherArrayCollection.
"Do I really need to learn factories and dependency injections?"
Yes, please, learn Dependency injection! You won't regret it! I don't think for this particular case you need a Factory pattern, but it never hurts to learn that too.
Dependency Injection is not that hard actually, the golden rule is: Whenever an object needs your ProductsCache, give them a reference to your ProductsCache. Don't use something like ProductsCache.instance.products. Tell objects about the ProductsCache you want them to use, don't let them ask a singleton about it. Very easy rule to remember: Tell, don't ask.


Better way to write a string slicer Here is some code to insert a new line escape sequence after a certain number of characters (for fixed width displays)

    private string spliceNoteText(string text)
    {
        StringBuilder sb = new StringBuilder();

        int maxWidth = 70;
        int blockOfText;

        for (int i = 0; i <= text.Length; i += maxWidth)
        {
            if (i >= text.Length)
                continue;

            int charsRemaining = text.Length - i;

            if (charsRemaining <= maxWidth)
                blockOfText = charsRemaining;
            else
                blockOfText = maxWidth;

            sb.Append(text.Substring(i, blockOfText));
            sb.Append("\n");

        }
        return sb.ToString();
    }

It's is ugly and boring, can it be made prettier or more elegant?

You could already create the StringBuilder with the text you want to 'splice', rather than building it up again. Then you can just determine how many newline characters you want to add (and you should use Environment.NewLine instead of specifying it explicitly), and insert them in the right place.

    private string SpliceNoteText(string text, int maxWidth)
    {
        StringBuilder sb = new StringBuilder(text);

        for (int i = 0; i < (sb.Length / maxWidth); i++)
        {
            int insertPosition = i * maxWidth;
            sb.Insert(insertPosition, Environment.NewLine);
        }

        return sb.ToString();
    }


Moving method from derived class to base I've some classes (Derived1, Derived2, etc.) derived from class Base. All of derived classes have a following methods (reduced sample):

void Derived1::handleTimer(const StatusType &st) {
  if (!st.isOk()) {
    m_timer->WakeUpPeriod(10); // wait for 10 seconds;
    m_timer->SetHandler(boost::bind(Derived1::handleTimer, this, _1));
    return;
  }

  try {
    ... // there is some specific for Derived's code
    m_timer->WakeUpPeriod(10 * 60); // wait for 10 minutes;
    m_timer->SetHandler(boost::bind(Derived1::handleTimer, this, _1));
  }
  catch(...) {
    m_timer->WakeUpPeriod(10); // wait for 10 second;
    m_timer->SetHandler(boost::bind(Derived1::handleTimer, this, _1));
  }
}

void Derived1::start() {
  m_timer->WakeUpPeriod(1); // wait for 1 second;
  m_timer->SetHandler(boost::bind(Derived1::handleTimer, this, _1));
}

I'd like to move these methods to Base. However, my trying looks pretty ugly. Is there more appropriate way?
There is my current solution.

class Base {
public:
  typedef boost::function <void (const StatusType&)> HandlerType;
  Base(HandlerType handler) : m_hadler(handler) {}
  void start() {
    m_timer->WakeUpPeriod(1); // wait for 1 second;
    m_timer->SetHandler(m_handler);
  }
protected:
  virtual void doSomeSpecific() = 0;

  void handleTimer(const StatusType &st) {
    if (!st.isOk()) {
      m_timer->WakeUpPeriod(10); // wait for 10 seconds;
      m_timer->SetHandler(m_handler);
      return;
    }

    try {
      doSomeSpecific();
      m_timer->WakeUpPeriod(10 * 60); // wait for 10 minutes;
      m_timer->SetHandler(m_handler);
    }
    catch(...) {
      m_timer->WakeUpPeriod(10); // wait for 10 second;
      m_timer->SetHandler(m_handler);
    }
  }

private:
  HandlerType m_handler;

  ... // other data and function members
};

Now Derived classes

void Derived1::doSomeSpecific() { ... }

Derived1::Derived1() : Base(boost::bind(Derived1::handleTimer, this, _1) {}

void Derived1::handleTimer(const StatusType &st) { Base::handleTimer(st); }

The use of doSomeSpecific inside of handleTimer is remarkably similar to the Template Pattern.

If there is no base implementation of doSomeSpecific you might consider making it private (still virtual so it can be overridden). Unless of course you really want further derived classes to be able to call the doSomeSpecific implementations of their parent classes.

Also, you can consider making handleTimer non-virtual if all derived classes must have the same behavior.

By making doSomeSpecific private, and handleTimer non-virtual, the only point of customization becomes doSomeSpecific, and it becomes an all or nothing point of customization. This can simplify your implementations of your derived classes, because you can trust that they only customize one specific part of your base class.


Transforming XML to HTML with XSLT I'm still learning from designing with types non strings by Scott Wlaschin.
For my project I transform some XML to HTML with xslt.
Because every filename can have side effects, they are stored in string option types.
If I do the transformation I get an ugly pyramid of Option.map and five times more lines of code compared to the simple version.
Is there a shorter way to write that code?

open System.Xml.Xsl

type HtmlPage = HtmlPage of string
type XmlFile  = XmlFile of  string
type XslFile  = XslFile of  string

type HtmlTransformer =
    {
        HtmlPage :  HtmlPage    option
        XmlFile :   XmlFile     option
        XslFile :   XslFile     option
    }

let toHtmlNoOption (xmlFn:string) (xsltFn:string) (htmlFn:string) =
    try
        let xslt = new XslCompiledTransform()
        xslt.Load xsltFn
        xslt.Transform (xmlFn,htmlFn)
    with _-> ()

let toHtml (sc:HtmlTransformer) =
    try
        let xslt = new XslCompiledTransform()
        let xfn =
            sc.XslFile
            |> Option.map (fun (XslFile xf)  -> xf)
        let xmlFn =
            sc.XmlFile
            |> Option.map (fun (XmlFile xf)  -> xf)
        let htmlFn =
            sc.HtmlPage
            |> Option.map (fun (HtmlPage lp)  -> lp)
        xfn
        |> Option.map xslt.Load
        |> Option.map
            (fun () ->
                htmlFn
                |> Option.map
                    (fun hFn ->
                        xmlFn
                        |> Option.map
                            (fun xFn -> xslt.Transform(xFn,hFn)))
            )
    with
        _ -> None

Because every filename can have side effects, they are stored in string option types.

I don't understand what you mean by that, but it's not particularly important for the rest of the question.

Your concern about the structure of the code is valid. Fortunately, you have several options. Let's start gently.

Map3

Option.map is useful if you have a single option value, and you want to transform it into another option value if the input value is a Some case. If you have two option values, you'll need a hypothetical Option.map2 function, and in this case, where you have three option values, you'll need a hypothetical Option.map3 function. These functions are not yet available in the Option module, but are being considered for inclusion in the future.

You can easily write the required function yourself, though:

// ('a -> 'b -> 'c -> 'd) -> 'a option -> 'b option -> 'c option -> 'd option
let optionMap3 f x y z =
    match x, y, z with
    | Some x', Some y', Some z' -> f x' y' z' |> Some
    | _ -> None

This completely generic function would enable you to write an option-based function adapter over your nice toHtmlNoOption function:

let toHtml' (sc : HtmlTransformer) =
    let xfn = sc.XslFile |> Option.map (fun (XslFile xf)  -> xf)
    let xmlFn = sc.XmlFile |> Option.map (fun (XmlFile xf)  -> xf)
    let htmlFn = sc.HtmlPage|> Option.map (fun (HtmlPage lp) -> lp)

    (xfn, xmlFn, htmlFn) |||> optionMap3 toHtmlNoOption

The return expression uses the exotic |||> pipe operator to compose the three option values into toHtmlNoOption, which will only be invoked if all three values are Some cases.

Computation expression

You can do better, though, using a computation expression. There's no built-in computation expression for option types, but you can easily add a minimal one that addresses this particular purpose:

type OptionBuilder () =
    member this.Bind(v, f) = Option.bind f v
    member this.Return v = Some v

let option = OptionBuilder ()

This enables you to rewrite the function like this:

let toHtml'' (sc : HtmlTransformer) = option {
    let! XslFile xfn = sc.XslFile
    let! XmlFile xmlFn = sc.XmlFile
    let! HtmlPage htmlFn = sc.HtmlPage

    return toHtmlNoOption xfn xmlFn htmlFn }

Notice how the use of let!-bound values enable you to use pattern matching to destructure the string values out of the single-union cases. Within this option expression, xfn, xmlFn, and htmlFn all have the type string.

Because this expression is evaluated within an option computation expression, it'll short-circuit and return None as soon as any of the let!-bound values turn out to be None. Only if they are all Some cases does it evaluate all the way to the end, where it calls into the toHtmlNoOption function and returns the return value of that function call.


Handle IDisposable objects When I work a lot with objects, that implements IDisposable I am using this pattern, like shown here with a SqlConnection and a SqlCommand.

    private string _connectionString = "";

    public IEnumerable<User> GetUsers()
    {
        List<User> users = new List<User>();
        string sql = "SELECT * FROM [user]";
        InvokeSql(sql, (connection, command) =>
        {
            IDataReader reader = command.ExecuteReader();
            while (reader.Read())
            {
                User user = new User();
                users.Add(user);

                user.Name = reader["name"] as string;
            }
        });
        return users;
    }

    private void InvokeSql(string sql, Action<SqlConnection, SqlCommand> action)
    {
        if (string.IsNullOrWhiteSpace(sql))
        {
            throw new ArgumentNullException("sql");
        }

        if (action == null)
        {
            throw new ArgumentNullException("action");
        }

        using (SqlConnection connection = new SqlConnection(_connectionString))
        using (SqlCommand command = new SqlCommand(sql, connection))
        {
            connection.Open();
            action(connection, command);
        }
    }

So I can reuse the InvokeSql and do not have to bother about the disposing.
But is it really a good idea, to use an Action in a using Statement?

So I can reuse the InvokeSql and do not have to bother about the disposing.

Sure. Except InvokeSql is private, so reuse is rather limited to that class. And if that class has a GetUsers method, I dare expect only User-related stuff in that class... which InvokeSql isn't.

In all likelihood, your model is going to involve more than just User entities; I'd make a base class to encapsulate the CRUD and this InvokeSql method; then a derived type can be responsible for User entities, and another derived type can be responsible for another entity type - something like a "repository".

ExecuteReader returns a SqlDataReader instance, which also implements IDisposable: you're missing a using block here:

IDataReader reader = command.ExecuteReader();
while (reader.Read())

using (SqlDataReader reader = command.ExecuteReader())
{
    while (reader.Read())
    ...


Creating a grid in HTML from a database search I have a little piece of code that is a little bit unoptimized and need some help with optimization in this case.

The procedure is to search in a database using "Conditions/Condicao" and create a grid using tables in HTML with content.  In debug, the following part is taking a long time to complete with 300 results or more.

for (x = 0; x < Campos.Length; x++)
{
    string concat = "";
    for (i = 0; i < 2; i++)
    {
        if (concat != "")
        {
            concat += "," + oDrc[y].ItemArray[1].ToString().Trim().Replace("'", "");
        }
        else
        {
            concat += oDrc[y].ItemArray[0].ToString().Trim().Replace("'", "");
        }
    }
    if (!pkunica)
    {
        concat = "";
        for (i = 0; i < Pks.Length; i++)
        {
            if (concat != "")
            {
                concat += "," + oDrc[y].ItemArray[i].ToString().Trim().Replace("'", "");
            }
            else
            {
                concat += oDrc[y].ItemArray[i].ToString().Trim().Replace("'", "");
            }
        }
    }

I've uploaded the full code to Pastebin.  And about some words, they're in PT-BR.

Use string.Empty instead of "" to indicate an empty string. It conveys your intent without ambiguity (i.e.: nobody will think you forgot to enter something in the string).

When concatenating in a loop, use a StringBuilder.

Use meaningful names. I don't know what concat and oDrc actually mean. Nor pkunica, but that might be a language-issue (I'd encourage you to stick to English-only).


A simple SDL script that creates a window Is there possibly a way to take out the nested if statements without losing the error reports? I am just learning SDL and would like to further simplify my code so that it is readable by me when I look at in a few days.

#include <SDL.h>
#include <iostream>

int main(int argc, char *argv[]) {
    SDL_Window *window = nullptr; //the window
    SDL_Surface *windowSurface = nullptr; //will store current window surface
    SDL_Surface *imageSurface = nullptr; //will store image to be applied to the window

    //inits video
    if (SDL_Init(SDL_INIT_VIDEO) < 0)
        std::cout << "Video Init Error: " << SDL_GetError() << std::endl;
//if error
    else { //creates window
        window = SDL_CreateWindow("Slime Runner Prelim Tests",
SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, 640, 480, SDL_WINDOW_SHOWN);
        if (window == NULL)
            std::cout << "Window creation error: " << SDL_GetError() <<
std::endl; //if error
        else { // if all is good with window creation.
            //WINDOW HAS BEEN CREATED

            windowSurface = SDL_GetWindowSurface(window);

            imageSurface = SDL_LoadBMP("Images/Background.bmp");
        if (imageSurface == NULL)
                std::cout << "Image load error: " << SDL_GetError() <<
std::endl;
            else {
                SDL_BlitSurface(imageSurface, NULL, windowSurface, NULL);
                SDL_UpdateWindowSurface(window);
            }
        }//end of window creation if
    }//end of SDL_INIT_VIDEOs
    SDL_Delay(4000);
    SDL_FreeSurface(imageSurface);
    imageSurface = nullptr;
    SDL_DestroyWindow(window);
    window = nullptr;
    SDL_Quit();

    return 0;
}

Is there possibly a way to take out the nested if statements without losing the error reports?

Use RAII to encapsulate your resources into objects that enforce the create/destroy pairing. You can write your own RAII wrapper objects or (better) use a resource factory that creates std::unique_ptr/std::shared_ptr's. A concrete factory for arbitrary SDL resources:

namespace sdl2 {
template <typename Creator, typename Destroyer, typename... Arguments>
auto make_resource(Creator c, Destroyer d, Arguments &&... args) {
  auto r = c(std::forward<Arguments>(args)...);
  if (!r) {
    throw std::system_error(errno, std::generic_category(), SDL_GetError());
  }
  return std::unique_ptr<std::decay_t<decltype(*r)>, decltype(d)>(r, d);
}
} // namespace sdl2

This factory attempts to create the resource, checks to ensure it was created, and returns a unique_ptr that destroys the resource correctly when the pointer goes out of scope.  Specific helpers to provide higher levels of abstraction for resources like SDL_Window, SDL_Texture, SDL_Renderer, etc, can be created like so:

namespace sdl2 {
using WindowPtr = std::unique_ptr<SDL_Window, decltype(&SDL_DestroyWindow)>;

WindowPtr make_window(const char *title, int x, int y, int w, int h,
                      std::uint32_t flags) {
  return make_resource(SDL_CreateWindow, SDL_DestroyWindow, title, x, y, w, h,
                       flags);
}
} // namespace sdl2

You can write your own abstractions over SDL's C API to utilize some of the modern C++ constructs and ideally end with something like this:

int main() try {
  auto window = sdl2::make_window("Slime Runner Prelim Tests",
                                  SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED,
                                  640, 480,
                                  SDL_WINDOW_SHOWN);
  auto screen = sdl2::get_surface(window);
  auto image = sdl2::load_bitmap("Images/Background.tmp");
  sdl2::blit_surface(image, nullptr, screen, nullptr);
  sdl2::update_surface(window);
  sdl2::delay(4s);
} catch (...) {
  std::cout << "Error: " << error.what() << '\n';
}

Note: You don't have to use exceptions, but RAII does provide you with the flexibility to choose whichever error handling system you want (exceptions, checked errors, etc) while simplifying the cleanup process.

int main(int argc, char *argv[])

If you are not using argc and argv, omit them.

int main()

std::endl

Be aware of what std::endl actually does.  If you simply want to print a newline character, prefer '\n' since it's both shorter and correct.

SDL_BlitSurface(imageSurface, NULL, windowSurface, NULL);

Use nullptr instead of NULL.


Summed absolute difference of two array Question (SAD Queries on CodeChef)

  The Summed Absolute Difference (SAD) of two arrays. Given arrays
  (1-indexed) \$P\$ and \$Q\$ of lengths \$p\$ and \$q\$.

  Given a collection of \$n\$ arrays \$A_1, \ldots, A_n\$, report \$SAD(A_i, A_j)\$ for
  several queries \$(i, j)\$.

  The first line of input contains a single positive integer \$n\$.

  Each of the next \$n\$ lines starts with a positive integer \$s_i\$, the size
  of \$A_i\$,

  followed by \$s_i\$ space-separated integers \$A_{i,1}, \ldots, A_{i,s_i}\$ which denotes
  the array \$A_i\$. The next line of input consists of a single positive
  integer \$M\$.

  Each of the next \$M\$ lines consists of 2 positive integers \$a\$ and \$b\$ which lie
  between \$1\$ and \$n\$ (inclusive), specifying the indices of the arrays for
  which the SAD value must be reported.

Example

  Input:

4
4 0 3 1 -2
2 0 4
2 2 4
4 4 -3 -4 4

3
3 4
4 2
1 4

  Output:

30
30
60

Explanation

  Query 1: The arrays in question are A3 = [2, 4] and A4 = [4, -3, -4,
  4].

  $$SAD(A3, A4)$$
  $$= |2 - 4| + | 2 - (-3) | + |2 - (-4) | + | 2 - 4 |$$
  $$+ | 4 - 4 | + | 4 - (-3) | + | 4 - (-4) | + | 4 - 4 |$$
                         $$= 2 + 5 + 6 + 2 + 0 + 7 + 8 + 0$$
                         $$= 30$$

Constraints

\$1 \leq n, M \leq 10^5\$

\$1 \leq s_1 + ... + s_n \leq 10^5\$

\$-10^9 \leq A_{i,j} \leq 10^9\$

\$1 \leq i, j \leq n\$ in each of the queries

My approach

#include <iostream>
#include<cmath>

using namespace std;

int main()
{

    long long  int n,x,a,b,sum=0,s=1;
    cin>>n;
    long long int *size=new long long int[n];
    long long int **arr=new long long int*[n];
    for(int i=1;i<=n;i++)
    {
        arr[i]=new long long int[n];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>size[s];

        for(int j=0;j<size[s];j++)
        {
            cin>>arr[i][j];
        }
        s++;
    }
    long long int m;
    cin>>m;
    while(m--)
    {
        cin>>a>>b;
        for(int i=1;i<=size[a];i++)
        {
            for(int j=0;j<size[b];j++)
                sum=sum+fabs(arr[a][i]-arr[b][j]);
        }
        cout<<sum;
        cout<<endl;
        sum=0;
    }
    return 0;
}

How can i reduce the time complexity and space complexity of this program.

I have taken a 1D dynamic array to store the size of arrays and a 2D dynamic array to store the index and the array value for that index

@vnp has already given an excellent review of your algorithmic problems. I'm not going to duplicate their work. I'm just going to review the code itself.

using namespace std;

Avoid doing the above. It may save you a few keystrokes in a small program like this one, but can turn into a major maintenance headache for a codebase that you need to support. See this question.

long long  int n,x,a,b,sum=0,s=1;

Never declare multiple variables on a single line. It's very easy to screw up the syntax and get some surprising bugs. Declaring each variable on its own line does not make the code slower.
Don't declare variables until they're needed. You need n right away, but you don't use a or b until over 50 lines later.
Give variables descriptive names. In a problem like this, you can get away with using names like n, a, and b because they're the names in the problem. But what is x? I don't even see it being used at all? Is it vestigial from an earlier attempt at the problem?

On to the next lines....

long long int *size=new long long int[n];
long long int **arr=new long long int*[n];

Don't use naked new. Either use smart pointers or - in this case - containers. What you want here is std::vector. There is absolutely zero speed penalty for using a vector rather than allocating an array yourself with new.

You don't free any of the memory you allocate. I don't know if that's tolerated in these coding competitions, but it is undefined behaviour in general. Here's a hot tip: If you are in a coding competition where it's okay to leak memory, and you want to save every cycle so you don't want to pay for freeing any memory, you can still use standard containers. All you need to do is define an allocator that doesn't delete. Which is just:

template <typename T>
struct leaking_allocator
{
    using value_type = T;
    auto allocate(std::size_t n) { return new T[n]; }
    auto deallocate(T*, std::size_t) noexcept { }
};

If you'd used a vector, you wouldn't need both size and arr. You would just need auto A = std::vector<std::vector<long long int>{};. You would read n then do A.resize(n);. Then for each array you would read s and do A[i].resize(s);, and read the next s values into A[i][0] to A[i][s - 1]. The size of any array would be A[i].size().

And, of course, your program wouldn't leak (unless you deliberately made it do so by using a leaking allocator).

for(int i=1;i<=n;i++)
{
    arr[i]=new long long int[n];
}

You have an out-of-bounds error here. You're lucky the program doesn't crash. I know the problem talks about 1-based arrays, but C++ arrays are 0-based. You need to do that conversion, either in your head or in the code.

So either:

for(int i = 0; i < n; ++i)
    arr[i] = new long long int[n];

or:

for(int i = 1; i <= n; ++i)
    arr[i - 1] = new long long int[n];

(Note: As Pete Kirkham points out, the above is still wrong. The allocation line should be moved to the next loop, after cin>>size[s];. And instead of allocating n elements, it should be allocating size[s]. The vector versions don't have this bug.)

In the next loop:

for(int i=1;i<=n;i++)
{
    cin>>size[s];

    for(int j=0;j<size[s];j++)
    {
        cin>>arr[i][j];
    }
    s++;
}

You have the same out-of-bounds error. But you also have a needless extra loop variable. Both i and s are doing the same thing here. And you never use s again after this loop. You could simplify this to:

for (int i = 0; i < n; ++i)
{
    cin >> size[i];

    for(int j = 0; j < size[i]; ++j)
        cin >> arr[i][j];
}

But of course, if you used vectors, both of the above loops could simplify to:

auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here

auto n = 0;
std::cin >> n;
A.resize(n);

for (auto i = 0; i < A.size(); ++i)
{
    auto s = 0;
    std::cin >> s;
    A[i].resize(s);

    for (auto j = 0; j < A[i].size(); ++j)
        std::cin >> A[i][j];
}

or even better and safer, using range-based loops:

auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here

auto n = 0;
std::cin >> n;
A.resize(n);

for (auto&& arr : A) // for each array in A
{
    auto s = 0;
    std::cin >> s;
    arr.resize(s);

    for (auto&& item : arr) // for each item in A[i]
        std::cin >> item;
}

On to the calculation loop....

while(m--)
{
    cin>>a>>b;
    for(int i=1;i<=size[a];i++)
    {
        for(int j=0;j<size[b];j++)
            sum=sum+fabs(arr[a][i]-arr[b][j]);
    }
    cout<<sum;
    cout<<endl;
    sum=0;
}

Once again, that first inner loop has an out-of-bounds error.

@vnp has already pointed out that you should be using std::abs(), not std::fabs(). But here are some more tips to increase speed and readability:

sum=sum+fabs(arr[a][i]-arr[b][j]);

can be simplified to:

sum += std::abs(arr[a][i] - arr[b][j]);

Because you've declared sum outside of the loop, you have to clear it on each iteration. That's a little brittle. It would be safer and more sensible to declare sum just before calculating the sum.

Also:

cout<<endl;

Never use endl. Especially in performance code. If you want a newline, just write a newline.

So the loop above becomes:

while (m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (int i = 0; i < size[a]; ++i)
    {
        for (int j = 0; j < size[b]; ++j)
            sum += std::abs(arr[a][i] - arr[b][j]);
    }

    std::cout << sum << '\n';
}

And if you use vectors, the code is basically identical:

while(m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (int i = 0; i < A[a].size(); ++i)
    {
        for (int j = 0; j < A[b].size(); ++j)
            sum += std::abs(A[a][i] - A[b][j]);
    }

    std::cout << sum << '\n';
}

or with range loops:

while(m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (auto item_a : A[a]) // for each item_a in A[a]
                             // (don't need && because they're just
                             // long long int, and we're just
                             // reading them)
    {
        for (auto item_b : A[b]) // for each item_b in A[b]
            sum += std::abs(item_a - item_b);
    }

    std::cout << sum << '\n';
}

And finally:

return 0;

There's no need for this. main() returns zero automatically.

Summary

You have two critical problems in your code:

You leak every array you allocate. If this is deliberate, at least document it with a comment. This problem would go away if you used smart pointers and containers. (But if you really want to leak, you can still use smart pointers and containers. You'd just need to use leaking deleters and allocators.)
Many of your loops access out-of-bounds memory. The problem talks about 1-based arrays, but arrays in C++ are 0-based. You need to do that conversion.

You have one problem that will really hurt your efficiency:

Don't use endl.

And you have a few minor problems that are mostly stylistic:

Don't declare variables until right before they're needed.
Don't declare multiple variables all on one line.
Don't use manual memory management - don't use naked new/delete. Use containers and smart pointers. They are zero-cost abstractions.
Space out your code. It's hard to spot errors when each line is just a jumble of symbols.

Some of the above will give you small speed boosts, but as @vnp noted, the real thing that's killing your time is that you didn't think the problem through, and just tried to brute-force it.

However, you have some serious bugs that you should worry about fixing first, before worrying about speed.


Encoding text to keypresses on old phone keyboard (0-9*#) I am going through "Haskell Programming from first principles" for the first time and I would like to get some pointers on what can be improved in my code, which is the following:

module DaPhone ( stringToKeyTaps
           , fingerTaps
           , mostPopularLetter
           , mostPopularWord
           , coolestLtr
           , coolestWord
           , daPhoneTaps
           , daPhoneTaps
           , testKeyBoard
           , testConvo) where

import Data.Char
import Data.List
import Data.Maybe

type KeyLabel = Char
type Digit = Char

data Key = Key KeyLabel [Digit] deriving (Eq, Show)
label (Key l _) = l
digits (Key _ ds) = ds

isDigitOf :: Digit -> Key -> Bool
c `isDigitOf` key = c `elem` (digits key)

type KeyboardLayout = [Key]

getKeyFor :: KeyboardLayout -> Digit -> Key
getKeyFor kmap c = fromJust $ find (c `isDigitOf`) kmap

type Taps = Int
type KeyTaps = [(KeyLabel, Taps)]

stringToKeyTaps :: KeyboardLayout -> String -> KeyTaps
stringToKeyTaps _ [] = []
stringToKeyTaps kmap (c:cs)i
    | c `elem` ['A'..'Z'] =
    charToKeyTap kmap '^' : stringToKeyTaps kmap ((toLower c):cs)
    | c `elem` charSet = charToKeyTap kmap c : stringToKeyTaps kmap cs
    | otherwise = stringToKeyTaps kmap cs
    where charSet = foldr ((++) . (digits)) [] kmap

charToKeyTap kmap c =
        (label $ theKey, (fromJust $ elemIndex c $ digits $ theKey) + 1)
                        where theKey = getKeyFor kmap c

fingerTaps :: KeyTaps -> Taps
fingerTaps = foldr ((+) . snd) 0

mostPopularLetter :: String -> Char
mostPopularLetter = mostPopularElement

mostPopularWord :: String -> String
mostPopularWord = mostPopularElement . words

coolestLtr :: [String] -> Char
coolestLtr = mostPopularLetter . filter (/=' ') . concat

coolestWord :: [String] -> String
coolestWord = mostPopularWord . intercalate " "

mostPopularElement :: (Ord a, Eq a) => [a] -> a
mostPopularElement = head . head .
        sortBy (\x y -> (length y) `compare` (length x)) . group . sort

-- provided variables
testKeyBoard :: KeyboardLayout
testKeyBoard = [ Key '1' "1"
               , Key '2' "abc2"
               , Key '3' "def3"
               , Key '4' "ghi4"
               , Key '5' "jkl5"
               , Key '6' "mno6"
               , Key '7' "pqrs7"
               , Key '8' "tuv8"
               , Key '9' "wxyz9"
               , Key '0' " 0"
               , Key '*' "^"
               , Key '#' ".,"
               ]

testConvo :: [String]
testConvo = [ "Wanna play 20 questions"
            , "Ya"
            , "U 1st haha"
            , "Lol ok. Have u ever tasted alcohol lol"
            , "Lol ya"
            , "Lol ur cool haha. Ur turn"
            ]

--partially applied converter for provided exercise
daPhoneTaps = stringToKeyTaps testKeyBoard

I would love to get a code review by someone better acquainted to functional programming and Haskell.

Library combinators and list comprehension syntax allow much collapsing of your code, and many of your type aliases and oneliners do not deserve a name, except perhaps for those at the bottom because you export them.

type KeyboardLayout = [(Char, [Char])]

stringToKeyTaps :: KeyboardLayout -> String -> [(Char, Int)]
stringToKeyTaps kmap cs =
  [ (label, index + 1)
  | c <- cs
  , c' <- ['^' | isUpper c] ++ [toLower c]
  , Just (label, index) <- asum $ (map . traverse) (elemIndex c') kmap
  ]

fingerTaps :: [(Char, Int)] -> Int
fingerTaps = sum . map snd

mostPopularElement :: (Ord a, Eq a) => [a] -> a
mostPopularElement = head . head . sortOn length . group . sort


Splitting TSV file into multiple files based on content of column I'm having to process an Amazon orders report (TSV flat file from the MWS Report API) and am needing to split the report based on sales channels (I could request them separately but need to keep API request counts as low as possible) whilst editing the contents of one of the columns (mapping a virtual SKU to its real counterpart). I'm using the CsvHelper library to handle the reading and writing, and would like to handle the file a line at a time to avoid loading the entire file into memory at once, which means as far as I know I can't use the using block on the StreamWriter and CsvWriter instances, so I made a wrapper class that implements IDisposable and calls Dispose on both writers as part of its Dispose method. I store a Dictionary of these classes using sales channel as the key, then once the file has been completed I loop through the dictionary calling Dispose on each element.

Wrapper Class:

internal class AmazonCsvWriter : IDisposable
{
    private bool _disposed;
    private readonly StreamWriter _streamWriter;
    private readonly CsvWriter _csv;

    public AmazonCsvWriter(string folder)
    {
        if (!Directory.Exists(folder))
        {
            Directory.CreateDirectory(folder);
        }

        _streamWriter = new StreamWriter(Path.Combine(folder, $"{DateTime.Now:yyyyMMddHHmmss}.txt"), false, Encoding.GetEncoding("Windows-1252"));
        _csv = new CsvWriter(_streamWriter);
        _csv.Configuration.Delimiter = "\t";
        _csv.Configuration.RegisterClassMap(new AmazonOrderRowMap());
        _csv.WriteHeader<AmazonOrderRow>();
        _csv.NextRecord();
    }

    public void WriteRecord(AmazonOrderRow record)
    {
        _csv.WriteRecord(record);
        _csv.NextRecord();
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual  void Dispose(bool disposing)
    {
        if (_disposed)
        {
            return;
        }

        if (disposing)
        {
            _csv.Dispose();
            _streamWriter.Dispose();
        }

        _disposed = true;
    }
}

Used in this function:

    public void ProcessFbaOrders(string reportFile)
    {
        try
        {
            using (var sr = new StreamReader(reportFile, Encoding.GetEncoding("Windows-1252")))
            using (var csv = new CsvReader(sr))
            {
                csv.Configuration.Delimiter = "\t";
                csv.Configuration.RegisterClassMap(new AmazonOrderRowMap());
                IEnumerable<AmazonOrderRow> records = csv.GetRecords<AmazonOrderRow>();
                foreach (AmazonOrderRow record in records)
                {
                    if (!_csvWriters.ContainsKey(record.SalesChannel))
                    {
                        _csvWriters.Add(record.SalesChannel,
                            new AmazonCsvWriter(Path.Combine(_platform.OutputFolder, record.SalesChannel)));
                    }

                    record.Sku = GetRealSku(record.Sku);

                    _csvWriters[record.SalesChannel].WriteRecord(record);
                }

            }
        }
        finally
        {
            foreach (KeyValuePair<string, AmazonCsvWriter> kvp in _csvWriters)
            {
                kvp.Value.Dispose();
            }
        }

        File.Delete(reportFile);
    }

_csvWriters is defined as:

    private readonly Dictionary<string, AmazonCsvWriter> _csvWriters;

Is this safely closing the Stream/CsvWriters or is there a better method for handling this?

First I would like to say that your code looks clean and well structured. You are doing most things well like using the proper casing for naming your things, using using's and stacking them as well, using readonly where you should.

Improvements could be made by using better names for your variables like e.g _csv and csv. A reader of your code who is switching between the AmazonCsvWriter class and the ProcessFbaOrders() method will get confused because in the AmazonCsvWriter class the _csv variable holds an instance of a CsvWriter and in the mentioned method the csv variable holds an instance of a CsvReader.

You are using a Dictionary<string, AmazonCsvWriter> to write the the unordered records to their desired destination based on the SalesChannel of the record.

Although your code accomplish its goal you could do better by using Enumerable.GroupBy() like so

IEnumerable<IGrouping<string, AmazonOrderRow>> query =
        records.GroupBy(record => record.SalesChannel, record=> record);

and then you can iterate over it like so

foreach (IGrouping<string, AmazonOrderRow> recordGroup in query)
{
    string csvOutputPath = Path.Combine(_platform.OutputFolder, recordGroup.Key);
    Directory.CreateDirectory(csvOutputPath);

    using (var streamWriter = new StreamWriter(Path.Combine(csvOutputPath, $"{DateTime.Now:yyyyMMddHHmmss}.txt"), false, Encoding.GetEncoding("Windows-1252")))
    using (var csvWriter= new CsvWriter(streamWriter))
    {
        csvWriter.Configuration.Delimiter = "\t";
        csvWriter.Configuration.RegisterClassMap(new AmazonOrderRowMap());
        csvWriter.WriteHeader<AmazonOrderRow>();
        csvWriter.NextRecord();
        foreach(var record in recordGroup)
        {
            record.Sku = GetRealSku(record.Sku);
            csvWriter.WriteRecord(record);
            csvWriter.NextRecord();
        }
    }
}

As a side note, you don't need to check if a directory exists before you call Directory.CreateDirectory() because the CreateDirectory() method checks the same and if the directory exists it simply returns.


Best way to avoid users to cancel my routine halfway through while managing other errors I'm struggling to find the best way to prevent users from cancelling a routine halfway through (by pressing ESC, break, etc) without making sure the sheet is being locked again. On top of that, I also want to manage potential other errors that this routine could generate. My code is :

Private Sub Worksheet_Activate()

Application.OnKey "{ESC}", ""
Application.EnableCancelKey = xlErrorHandler
Application.ScreenUpdating = False
ActiveWindow.DisplayHeadings = False
On Error GoTo errHandler

On Error Resume Next
ActiveSheet.Unprotect "XXXXX"
ActiveSheet.ShowAllData
ActiveSheet.Range("estimate_table").AutoFilter Field:=59, Criteria1:=">0"
ActiveSheet.Protect "XXXXX"

Application.ScreenUpdating = True
Application.OnKey "{ESC}"
Application.EnableCancelKey = xlInterupt

exitHandler:
    ActiveSheet.Protect "XXXXX"
    Application.OnKey "{ESC}"
    Application.EnableCancelKey = xlInterupt
    Application.ScreenUpdating = True
    Exit Sub
errHandler:
    If Err.Number = 18 Then
    Resume exitHandler
    Else
    MsgBox "An error has occured. The list can't be updated."
    Resume exitHandler
    End If

End Sub

What I'm trying to achieve is run an autofilter on a table in a locked sheet every time the sheet is activated. I want users to be able to stop the routine if necessary (maybe it's taking forever) but I want to be sure that no matter what, the sheet is back to being locked.

Also, I noticed that sometime, if user stops the routine once and goes back and forth between sheets, the routine won't work anymore and will generate an error that is never reset or cleared (i.e. the message "An error has occured..blablabla" is displayed every time the user activates the sheet). So I want to be sure that the routine doesn't get blocked / bugged even if an error has occurred before (hence my On Error Resume Next).

Overall I'm not sure I'm doing it correctly here (not familiar with VBA and error handling in general). With the code above, It doesn't seem like I'm able to stop the routine at all (but least the sheet seems locked all the time, which is nice)

I think I've managed to improve (or clean at least) the code mentioned above:

Private Sub Worksheet_Activate()

Application.EnableCancelKey = xlErrorHandler
On Error GoTo errHandler
Application.ScreenUpdating = False
ActiveWindow.DisplayHeadings = False

ActiveSheet.Unprotect "XXXXX"
ActiveSheet.ShowAllData
ActiveSheet.Range("estimate_table").AutoFilter Field:=59, Criteria1:=">0"
ActiveSheet.Protect "XXXXX"

Application.ScreenUpdating = True
Application.EnableCancelKey = xlInterupt

Exit Sub

exitHandler:
    ActiveSheet.Protect "XXXXX"
    Application.EnableCancelKey = xlInterupt
    Application.ScreenUpdating = True
    Exit Sub
errHandler:
    If Err.Number = 18 Then
    Resume exitHandler
    Else
    Resume Next
    End If

End Sub

What I still don't understand is why it seems like I still can't stop the routine by pressing ESC (90% of the time, the process goes through and once in a while the process is indeed stopped)..


Finding a cryptoarithmetic solution This code is intended to find all possible solutions to a cryptoarithmetic problem.  The description of the problem I was trying to solve is here:

  In cryptoarithmetic problems, we are given a problem wherein the
  digits are replaced with characters representing digits. A solution to
  such a problem is a set of digits that, when substituted in the
  problem, gives a true numerical interpretation.

  Example:

IS
IT
___
OK

  has a solution

{ I = 1; K = 1; O = 3; S = 5; T = 6}

  For each of the below cryptoarithmetic problems, write a program that finds all
  the solutions in the shortest possible time.

IS     I
IT    AM
__    __
OK    OK

I was only able to solve it using brute force, though I believe there are more efficient methods.  I am also hoping to receive feedback on my formatting, naming, and really anything you think could use improvement.

(defun place-value-to-integer (the-list &OPTIONAL place-value)
  (let ((place-value (if place-value place-value 1)))
    (if (= (length the-list) 1) (* place-value (first the-list))
      (+ (* place-value (first (last the-list))) (place-value-to-integer (butlast the-list) (* 10 place-value))))))

(defun fill-from-formula (formula guess)
  (loop for digit in formula collect (gethash digit guess)))

(defun check-answer (augend-formula addend-formula sum-formula guess)
  (let ((augend (fill-from-formula augend-formula guess))
    (addend (fill-from-formula addend-formula guess))
    (sum (fill-from-formula sum-formula guess)))
        (= (place-value-to-integer sum) (+ (place-value-to-integer augend) (place-value-to-integer addend)))))

(defun brute-force-guess(augend-formula addend-formula sum-formula unique-values &OPTIONAL callback guess)
  (let ((guess (if (null guess) (make-hash-table) guess)))
    (loop for digit in '(0 1 2 3 4 5 6 7 8 9) do
      (setf (gethash (car unique-values) guess) digit)
      (if (= (length unique-values) 1)
        (if (check-answer augend-formula addend-formula sum-formula guess) (print-result augend-formula addend-formula sum-formula guess) nil)
        (brute-force-guess augend-formula addend-formula sum-formula (cdr unique-values) callback guess)))))

(defun print-result (augend-formula addend-formula sum-formula guess)
  (format t "One answer is ~a + ~a = ~a ~%"
      (fill-from-formula augend-formula guess)
      (fill-from-formula addend-formula guess)
      (fill-from-formula sum-formula guess)))

(defun find-unique-values (the-list)
  (let ((unique-items ()))
    (loop for sublist in the-list do
      (loop for item in sublist do
          (unless (member item unique-items) (setf unique-items (append (list item) unique-items))))) unique-items))

(let ((problemA (list (list 'I 'S) (list 'I 'T) (list 'O 'K)))
      (problemB (list (list 'I) (list 'A 'M) (list 'O 'K))))
    (brute-force-guess (first problemA) (second problemA) (third problemA) (find-unique-values problemA) #'print-result)
    (brute-force-guess (first problemB) (second problemB) (third problemB) (find-unique-values problemB) #'print-result))

Some preliminary notes for now (I'll add later):

Whenever you need to write (if n n 2) or (if (not n) 2 n), you can instead write (or n 2). or will take any number of arguments and return either nil or the first argument that evaluates to non-nil.

When working with optional arguments, you can set defaults for them.

(defun place-value-to-integer (the-list &OPTIONAL place-value)
  (let ((place-value (if place-value place-value 1)))
  ...

can be written as

(defun place-value-to-integer (the-list &OPTIONAL (place-value 1))
  ...

I don't have time to get into the rest right now, but you're using loop to setf a series of hash values, which tells me you could probably simplify it by using a more functional approach (it might be one of the exceptions, but it doesn't feel like one at first glance).

EDIT:

(if a b nil) is equivalent to (when a b) (and it's good style to use the second over the first).

EDIT2: Ok, wow, hey. That's two hours of my life I won't get back. I wrote up and edited down a pretty ridiculously long piece on my process (if you care, it's here). Here's how I would tackle a brute-force approach to this problem.

EDIT3: Simplified slightly.

(defpackage :cry-fun (:use :cl :cl-ppcre))
(in-package :cry-fun)

(defun digits->number! (&rest digits)
  (apply #'+ (loop for d in (nreverse digits) for i from 0
                   collect (* d (expt 10 i)))))

(defun number->digits (num &optional (pad-to 5))
  (let ((temp num)
        (digits nil))
     (loop do (multiple-value-call
                   (lambda (rest d) (setf temp rest digits (cons d digits)))
                (floor temp 10))
           until (= pad-to (length digits)))
     digits))

(defun string->terms (problem-string)
  (reverse
   (mapcar (lambda (s) (mapcar (lambda (i) (intern (format nil "~a" i)))
                   (coerce s 'list)))
           (split " " (string-downcase problem-string)))))

(defmacro solve-for (problem-string)
  (let* ((arg-count (length (remove-duplicates (regex-replace-all " " problem-string ""))))
         (nines (apply #'digits->number! (make-list arg-count :initial-element 9))))
    `(loop for i from 0 to ,nines
           when (apply (solution-fn ,problem-string) (number->digits i ,arg-count))
           collect it)))

(defmacro solution-fn (problem-string)
  (let* ((terms (string->terms problem-string))
         (args (remove-duplicates (apply #'append terms))))
    `(lambda ,args
       (when (= (+ ,@(loop for term in (cdr terms) collect `(digits->number! ,@term)))
                (digits->number! ,@(car terms)))
             (list ,@(mapcan (lambda (i) (list (symbol-name i) i)) args))))))

EDIT (by jaresty): adding comments to show example intermediate values for "solution-fn"

(defmacro solution-fn (problem-string)
  (let* ((terms (string->terms problem-string))
     ;example: (terms ((o k) (i t) (i s)))
         (args (remove-duplicates (apply #'append terms))))
         ;example: (args (o k t i s))
    `(lambda ,args
       (when (= (+ ,@(loop for term in (cdr terms) collect `(digits->number! ,@term)))
                (digits->number! ,@(car terms)))
        ;example: (when (= (+ (i t) (i s)) (o k)
             (list ,@(mapcan (lambda (i) (list (symbol-name i) i)) args))))))
        ;example: (list "o" o "k" k "t" t "i" i "s" s)


Directory of Snapshots I have snapshots (photos) that I load off my camera's memory card, and store in a folder. Sometimes I have videos, and occasionally plain audio too (the camera can record just sound).

Additionally, my wife, and kids have their point-and-shoots too.

I have a workflow where I dump the photos on to a designated folder on a linux samba share, and then run this script which identifies the photos, auto-rotates the portrait picturs, and renames them according to the date and time the picture was taken (rather than a sequential number from the camera).

This way, assuming the various cameras have the correct clock-time set, the different cameras all have photos that are named similar things (and can be sorted alphabetically to get them in chronological order too.

Notes:

the jhead program the script calls will rename/rotate the photos, and the name will become something like: Img20140217-164850.20.jpg
the jhead also identifies that some pictures may have 'raw' partners, for example, my Nikon camera takes a picture called DSC1234.JPG and simultaneously the picture DSC1234.NEF (the raw photo). The command jhead -aNEF -ft -autorot -n DSC*.JPG will identify the JPG photo, strip the .JPG extensions, and, because there is also the -aNEF argument, will rename the matching NEF file to the same base-name (Img*) as the JPG.... in other words, for the files DSC1234.JPG and DSC1234.JPG, the jhead program will produce, for example, both Img20140217-164850.20.jpg and Img20140217-164850.20.NEF
the script deals with both Canon, and Nikon raw files (RW2 and NEF respectively)

The script is relatively simple, but has a fair amount of repetition. Any suggestions for how to improve it?

#!/usr/bin/tcsh -f

#cd /valuable/picxfer

# Do the .jpg first because the jhead program will write .jpg even for .JPG input.
echo 'Checking DSC*.jpg'
if ( `tcsh -f -c "ls -1 DSC*.jpg >& /dev/null" && echo yes` == "yes" ) then
  jhead -anef -ft -autorot -n DSC*.jpg
else
  echo no Nikon jpg files
endif

echo 'Checking DSC*.JPG'
if ( `tcsh -f -c "ls -1 DSC*.JPG >& /dev/null" && echo yes` == "yes" ) then
  jhead -aNEF -ft -autorot -n DSC*.JPG
else
  echo no Nikon JPG files
endif

echo 'Checking *.jpg'
if ( `tcsh -f -c "ls -1 p*.jpg >& /dev/null" && echo yes` == "yes" ) then
  jhead -arw2 -ft -autorot -n p*.jpg
else
  echo no Canon jpg files
endif

echo 'Checking *.JPG'
if ( `tcsh -f -c "ls -1 P*.JPG >& /dev/null" && echo yes` == "yes" ) then
  jhead -aRW2 -ft -autorot -n P*.JPG
else
  echo no Canon JPG files
endif

echo Setting permissions
chmod ugo=r Img*

Your if conditions can be simplified. Instead of this:

if ( `tcsh -f -c "ls -1 DSC*.jpg >& /dev/null" && echo yes` == "yes" ) then

You could write like this:

if ( `ls DSC*.jpg >& /dev/null && echo x` != "" ) then

That is:

you don't need to spawn a tcsh sub-shell
you don't need the -1 for ls to list files in a single column because you redirect that to /dev/null anyway
the `...` part will only output anything if there were files, so you don't need yes == yes, it's enough to check for emptiness

If you don't mind using Bash instead of Tcsh, then the ifs can be even more simple:

if ls DSC*.jpg &> /dev/null; then

A lot less useless fluff.

With Bash you could simplify the repetitive blocks with a function, for example:

check_files() {
    glob=$1
    flags=$2
    nomsg=$3
    echo Checking "$glob"
    if ls $glob &>/dev/null; then
        jhead -a$flags -ft -autorot -n $glob
    else
        echo $nomsg
    fi
    echo
}

check_files 'DSC*.jpg' nef 'no Nikon jpg files'
check_files 'DSC*.JPG' NEF 'no Nikon JPG files'
check_files 'p*.jpg' rw2 'no Canon jpg files'
check_files 'P*.JPG' RW2 'no Canon JPG files'


Program to count the number of lines of code I need to get this program reviewed. It is counting the lines of code in all files in the
given directory.

I'm new to python and need some advice on pretty much everything.

#!/usr/bin/python
import os
import sys

def CountFile(f):
    counter = 0
    f = open(f, "r")
    for line in f.read().split('\n'):
        counter = counter + 1
    f.close()
    return counter

def CountDir(dirname):
    counter = 0
    for f in os.listdir(dirname):
        fa = os.path.join(dirname, f)
        if os.path.isdir(fa):
            dcount = CountDir(fa)
            counter = counter + dcount
        else:
            fcount = CountFile(fa)
            counter = counter + fcount
    return counter

print CountDir(sys.argv[1])

First a small nitpick: in python the prevailing naming convention for function names is all lowercase, with words separated by underscores. So CountFile should be count_file, or even better would be something like count_lines, since count_file doesn't really explain what the function does.

Now in CountFile, you read the file using f.read() then split on newlines. This isn't really necessary -- for one thing because file objects have a method called readlines which returns a list of the lines, but more importantly because file objects are iterable, and iterating over them is equivalent to iterating over the lines. So for line in f.read().split('\n'): is equivalent to for line in f:, but the latter is better because when you call read() you actually read the entire contents of the file into memory, whereas for line in f: reads the lines one at a time. It's also the idiomatic way to go about reading a file line by line.

If you're not concerned about memory, however, then because flat is better than nested you can do away with the explicit for loop and just call len on your list of lines. The entire function could be return len(open(f, 'r').readlines()) (but this isn't really advisable in the general case because of the memory thing). You could also use a generator expression and write return sum(1 for line in f).

Now notice that in CountFile, you write f = open(f, "r") to open a file, then later you write f.close() -- this kind of pattern is what context managers and the with statement were introduced for. The context manager protocol is already conveniently implemented for file objects, so you could write:

counter = 0
with open(f, 'r') as f:
   for line in f:
       counter += 1

And you wouldn't need to explicitly close the file. This may not seem like such a big deal in this case, and it isn't really, but with statements are a convenient way to ensure you that you only use resources (like files, or database connections, or anything like that) just as long as you need to. (Also, allocating and later freeing a resource might be a lot more involved than just calling open and close on it, and you might have to worry about what happens if something goes wrong while you're using the resource (using try... finally)... Hiding that behind a with statement makes for much more readable code because you can focus on what you're trying to accomplish instead of details like that.)

Your CountDir function looks mostly okay. You might look into using os.walk instead of os.listdir so you won't need to check for directories -- it would look something like

for root, _, files in os.walk(dirname):
    for f in files:
        count += CountFile(os.path.join(root, f))

(The _ doesn't have any special meaning, it just by convention means that we won't be using that variable.) Another advantage of os.walk is that by default it doesn't follow symlinks, whereas listdir doesn't care, so if you don't explicitly check for symlinks you might end up counting things twice.

If you stick with os.listdir, you could still make your code a bit cleaner by using a conditional expression, which would look like:

counter += CountDir(fa) if os.path.isdir(fa) else CountFile(fa)


C++11 recursive atomic spinlock Could you please review my spinlock implementation?

class spinlock {
private:
    static const std::thread::id lock_is_free;
    std::atomic<std::thread::id> lock_owner;
    int lock_count;

public:
    spinlock() : lock_owner(lock_is_free), lock_count(0) {
    }

    void lock() {
        static thread_local std::thread::id this_thread_local = std::this_thread::get_id();
        auto this_thread = this_thread_local;

        for (auto id = lock_is_free; ; id = lock_is_free) {
            if (lock_owner.compare_exchange_strong(id, this_thread, std::memory_order_acquire, std::memory_order_relaxed)) { ++lock_count; break; }
            id = this_thread;
            if (lock_owner.compare_exchange_strong(id, this_thread, std::memory_order_acquire, std::memory_order_relaxed)) { ++lock_count; break; }
        }
    }

    void unlock() {
        assert(lock_owner.load(std::memory_order_relaxed) == std::this_thread::get_id());
        if (lock_count > 0 && --lock_count == 0) {
            lock_owner.store(lock_is_free, std::memory_order_release);
        }
    }
};

const std::thread::id spinlock::lock_is_free;

Use of TLS

I'm not completely sold on your use of TLS. This looks like a premature optimization to me, that said if you have measured and it improves your performance then keep it.

Static member

I think it would be better style to not have this static member but this is highly subjective.

Readability

Your code here:

    for (auto id = lock_is_free; ; id = lock_is_free) {
        if (lock_owner.compare_exchange_strong(id, this_thread, std::memory_order_acquire, std::memory_order_relaxed)) { ++lock_count; break; }
        id = this_thread;
        if (lock_owner.compare_exchange_strong(id, this_thread, std::memory_order_acquire, std::memory_order_relaxed)) { ++lock_count; break; }
    }

is very difficult to read for me. In fact I'm struggling to understand what the intended behaviour is. To me it looks like what you really wanted was:

// If we're being locked recursively, this will always compare false
// (insert your desired memory_order here) because no one can fiddle
// with `lock_owner` while we have the lock. If we're not entering
// recursively then this will always compare true because the thread
// doing the checking can only be in one place at one time.
if(lock_owner.load() != this_thread){
    // Okay so it's not a recursive call.
    do{
        auto id = lock_is_free;
    }while(!lock_owner.compare_exchange_weak(id, this_thread,
                                             std::memory_order_acquire,
                                             std::memory_order_relaxed));
}
// Okay in any event, recursive or not we have the lock now.
lock_count++;
return;

Note: I change compare_exchange_strong to compare_exchange_weak this is recommended when you call compare_exchange in a loop as per std::atomic::compare_exchange (cppreference.com).

I would much prefer this implementation of unlock()

void unlock(){
    assert(lock_owner.load() == std::this_thread::get_id());
    assert(lock_count != 0);

    --lock_count;
    if(lock_count == 0){
        lock_owner.store(lock_is_free, std::memory_order_release);
    }
}

Following the style of std::mutex::unlock() stating that calling unlock when the calling thread doesn't own the lock is undefined behaviour we can simply satisfy ourselves with the two asserts to aid during debug-time.


Automatic Visual Studio Nuget consolidatation I'm hoping to automate the 'Manage Nuget Packages for Solution' Consolidate User Interface using Powershell in the 'Package Manager Console'.

The following script should take ONE of the packages in the consolidation list and 'fix it'.

#do just one
get-package | Group-Object Id | foreach { [pscustomobject]@{ packagename=$_.Name; VG=$_.Group ;versions=($_.Group |select -expandproperty versions |select -ExpandProperty Version); versionMAX=($_.Group |select -expandproperty versions |select -ExpandProperty Version |sort -property versions -descending |select -last 1)  } } | foreach { [pscustomobject]@{ packagename=$_.packagename; VG=$_.VG; versions=$_.versions; versionCount= $_.versions.Count; versionMAX=$_.versionMAX }} | where versionCount -gt 1 | foreach { [pscustomobject]@{ packagename=$_.packagename; VG=$_.VG; versions=$_.versions; versionMAX=$_.versionMAX; dversions=($_.versions | select -Unique) }} | foreach { [pscustomobject]@{ packagename=$_.packagename; VG=$_.VG; versionMAX=$_.versionMAX; PN=$_.VG.ProjectName; versions=$_.versions; dversionCount=$_.dversions.Count }} | where dversionCount -gt 1 | select -first 1 | foreach { foreach($v in $_.VG) { update-package -Id $v.Id -Version $_.versionMAX -projectname $v.ProjectName } }

You can use Select-Object instead of casting to pscustomobjects. For instance this:

foreach { [pscustomobject]@{ packagename=$_.packagename; VG=$_.VG; versions=$_.versions; versionCount= $_.versions.Count; versionMAX=$_.versionMAX }}

becomes this, which is somewhat shorter and less noisy:

select packagename VG versions @{Name="versionCount"; Exp={$_.versions.Count}} versionMAX

Notice the calculated property for versionCount.

Regarding the single line of code, I think you could have multiple statements separated by semicolons. You would work on the code as multiple lines in your text editor, and then join them together before pasting into VS.

Write-Output hello; Write-Output world


I feel as if my quicksort can be made more efficient, but what? I just learned the quicksort algorithm and tried to implement it, but it feels dirty:

#include <iostream>

void quicksort(int list[], int low, int high)
{
    if(low >= high)
        return;
    else
    {
        int pivot = low, i = low, j = high;

        while(i < j)
        {
            while(list[i] <= list[pivot] && i < high)
            {
                i++;
            }

            while(list[j] > list[pivot] && j > low)
            {
                j--;
            }

            if(i > j)
                break;

            int temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }

        int temp = list[pivot];
        list[pivot] = list[j];
        list[j] = temp;

        quicksort(list, low, j-1);
        quicksort(list, j+1, high);

    }
}

int main()
{
    int arr[10] = { 12, 2, 24, 32, 5, 1203, 7, 123, 2354, 2 };
    quicksort(arr, 0, 9);

    for(int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
}

The break condition in the while loop feels really cheap; as if I did something wrong and needed to put it there...

What can I improve?

I don't like seeing arrays passed as parameters.

void quicksort(int list[], int low, int high)
//                  ^^^^^

Inside the function all similarity to an array has disappeared. It has decayed into a pointer. By using the array like syntax you might catch people out that want to treat it as an array (which is a real maintenance issue).

If this code is C then just pass as a pointer.
If this code is C++ then pass as a reference to an array, or use a container type and pass by reference (I prefer the container option as you can template it).

In quick pre-condition checks at the head of a function like this.
There is no need for the else part.

if(low >= high)
    return;
else

It looks neater and saves you a level of indentation.

One variable per line.
Also give the variables more meaningful names.

    int pivot = low, i = low, j = high;

Also I would say that pivot is really the value you are pivoting around. Not the location of the value you are pivoting around.

    int pivot = list[<location Of Pivot Value>]; // See below for more.

Pretty sure there is a bug here i < high is not correct.

        while(list[i] <= list[pivot] && i < high)

Same thing here. Pretty sure there is a bug here j > low is not correct.

        while(list[j] > list[pivot] && j > low)

Yep. You are correct the break is ugly here.

        if(i < j)
        {    std::swap(list[i], list[j]);
        }

You are only doing this (below) to prevent your self choosing the same pivot point each time. So you should choose a different technique to choose the pivot point. Why not the element in the middle of the list?

    int temp = list[pivot];
    list[pivot] = list[j];
    list[j] = temp;

You pass the location of the first and last element in the array.

    quicksort(list, low, j-1);
    quicksort(list, j+1, high);

It is more C++ like to use first and one past the point you consider end. It also makes the code look neater try it and see.


Print the largest odd number entered I wrote this code to solve a problem from a John Vuttag book:

  Ask the user to input 10 integers, and then print the largest odd number that was entered.  If no odd number was entered, it should print a message to that effect.

Can my code be optimized or made more concise?  Any tips or errors found?

{
    a = int (raw_input("enter num: "))
    b = int (raw_input("enter num: "))
    c = int (raw_input("enter num: "))
    d = int (raw_input("enter num: "))
    e = int (raw_input("enter num: "))
    f = int (raw_input("enter num: "))
    g = int (raw_input("enter num: "))
    h = int (raw_input("enter num: "))
    i = int (raw_input("enter num: "))
    j = int (raw_input("enter num: "))

    num_List = {a,b,c,d,e,f,g,h,i,j }
    mylist=[]

    ## Use for loop to search for odd numbers

    for i in num_List:

                 if i&1 :
                     mylist.insert(0,i)
                     pass

                 elif i&1 is not True:
                     continue
    if not mylist:
        print 'no odd integers were entered'
    else:
        print max (mylist)

}

This is a solution that doesn't use lists, and only goes through the input once.

maxOdd = None

for _ in range(10):
    num = int (raw_input("enter num: "))
    if num & 1:
        if maxOdd is None or maxOdd < num:
            maxOdd = num

if maxOdd:
    print "The max odd number is", maxOdd
else:
    print "There were no odd numbers entered"


Implementation of iterator pattern for any array of elements I have implemented Iterator pattern:

The interface Container.java:

public interface Container<T> {

    Iterator<T> getIterator();
}

Interface Iterator.java:

public interface Iterator<T>{

    boolean hasNext();

    T next();
}

Class ResourceContainer.java:

public class ResourceContainer<T extends Serializable> implements Container<T>{

    private T names [];

    public ResourceContainer(T [] names){
        this.names = names;
    }

    @Override
    public Iterator<T> getIterator() {
        return new ResourceIterator<T>(this.names);
    }

}

Class ResourceIterator.java:

public class ResourceIterator<T extends Serializable> implements Iterator<T>{

    private T [] names;
    private int index;

    public ResourceIterator(T [] names){
        this.names = names;
    }

    @Override
    public boolean hasNext() {
        boolean flag = false;

        if(this.index < this.names.length){
            flag = true;
        }

        return flag;
    }

    @Override
    public T next() {
        return this.names[index++];
    }

}

An EmployeeVO class:

import java.io.Serializable;

public class EmployeeVO implements Serializable{

    private String name;
    private Integer id;
    private String departmentName;

    public EmployeeVO(Integer id, String name, String departmentName){
        this.name = name;
        this.id = id;
        this.departmentName = departmentName;
    }

    @Override
    public String toString(){
        StringBuffer strb = new StringBuffer();

        strb.append(" Id \"").append(this.id).append("\"")
            .append(" Name \"").append(this.name).append("\"")
            .append(" Department \"").append(this.departmentName).append("\"");

        return strb.toString();
    }
}

Main class:

public class MainClass {

    public static void main(String [] args){

        Integer [] nums = new Integer[]{12,23,100,1};

        Container<Integer> container01 = new ResourceContainer<Integer>(nums);
        Iterator<Integer> itr01 = container01.getIterator();

        while(itr01.hasNext()){
            System.out.println(itr01.next());
        }

        String [] names = new String[]{ "Alan", "Jim", "Nicholas" };

        Container<String> container02 = new ResourceContainer<String>(names);
        Iterator<String> itr02 = container02.getIterator();

        while(itr02.hasNext()){
            System.out.println(itr02.next());
        }

        EmployeeVO [] employees = new EmployeeVO[] {
        new EmployeeVO(23, "Alan Turing", "Computer Science"),
        new EmployeeVO(45, "Jim Klaus", "Mechanical Engineering"),
        new EmployeeVO(76, "Nicholas Johanson", "Electrical Engineering")
        };

        Container<EmployeeVO> container03 = new ResourceContainer<EmployeeVO>(employees);
        Iterator<EmployeeVO> itr03 = container03.getIterator();

        while(itr03.hasNext()){
            System.out.println(itr03.next());
        }
    }
}

The output of when I run MainClass from the command line:

12
23
100
1
Alan
Jim
Nicholas
Id "23" Name "Alan Turing" Department "Computer Science"
Id "45" Name "Jim Klaus" Department "Mechanical Engineering"
Id "76" Name "Nicholas Johanson" Department "Electrical Engineering"

By following the code, please review and let me know whether I implemented the iterator pattern properly. Is the usage of generics proper? Can the implementation be further improved?

I have two points for improvement:

Right now next() method increments the index. What happens if someone calls next() without calling hasNext() method?

Take care of ArrayIndexOutOfBoundsException or increment the index carefully.

You could implement remove() method (Optional)


Conway's Game of Life in Python Here's my Python implementation of Conway's Game of Life:

class Game(object):

    def __init__(self, state, infinite_board = True):

        self.state = state
        self.width = state.width
        self.height = state.height
        self.infinite_board = infinite_board

    def step(self, count = 1):

        for generation in range(count):

            new_board = [[False] * self.width for row in range(self.height)]

            for y, row in enumerate(self.state.board):
                for x, cell in enumerate(row):
                    neighbours = self.neighbours(x, y)
                    previous_state = self.state.board[y][x]
                    should_live = neighbours == 3 or (neighbours == 2 and previous_state == True)
                    new_board[y][x] = should_live

            self.state.board = new_board

    def neighbours(self, x, y):

        count = 0

        for hor in [-1, 0, 1]:
            for ver in [-1, 0, 1]:
                if not hor == ver == 0 and (self.infinite_board == True or (0 <= x + hor < self.width and 0 <= y + ver < self.height)):
                    count += self.state.board[(y + ver) % self.height][(x + hor) % self.width]

        return count

    def display(self):
        return self.state.display()

class State(object):

    def __init__(self, positions, x, y, width, height):

        active_cells = []

        for y, row in enumerate(positions.splitlines()):
            for x, cell in enumerate(row.strip()):
                if cell == 'o':
                    active_cells.append((x,y))

        board = [[False] * width for row in range(height)]

        for cell in active_cells:
            board[cell[1] + y][cell[0] + x] = True

        self.board = board
        self.width = width
        self.height = height

    def display(self):

        output = ''

        for y, row in enumerate(self.board):
            for x, cell in enumerate(row):
                if self.board[y][x]:
                    output += ' o'
                else:
                    output += ' .'
            output += '\n'

        return output

glider = """ oo.
             o.o
             o.. """

my_game = Game(State(glider, x = 2, y = 3, width = 10, height = 10))
print my_game.display()
my_game.step(27)
print my_game.display()

Output:

 . . . . . . . . . .
 . . . . . . . . . .
 . . o o . . . . . .
 . . o . o . . . . .
 . . o . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .

 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . o . . .
 . . . . . o o . . .
 . . . . . o . o . .
 . . . . . . . . . .
 . . . . . . . . . .

I have several concerns:

It feels a bit unnatural to write self.state.board[y][x], instead of [x][y]. However, I thought it would make sense to let the board be an array of rows rather than columns.
I'm not sure how to divide the tasks between the two classes. For instance, I could have implemented the neighbours() function in the State class, rather than in the Game class.
I know it's good practice to write a lot of comments,  but I found most of this code self-explanatory (though that could be because I've just written it).
I used several nested for-loops, but maybe I could replace some with list comprehensions.
I could have left out the display() function of the Game class and just write print my_game.state.display() on the last line. Does this simplify things, or does it only make it more complicated?

This is excellent code for a Python novice.

To address your questions:

Rather than x and y, try naming your variables row and col.  Then it wouldn't feel unnatural to write self.state.board[row][col].
In my opinion, the .neighbour() function would be better in the State class, since you're counting neighbours of a cell within that state.
Your code is easy to understand, partly because the rules of the game are well known.  However, you should still write docstrings for your functions.  It's not obvious, for example, what to pass for the state parameter to the Game constructor unless you read the code.  (Should I pass a 2D array of booleans?)
You could use list comprehensions, but the current code is not bad either.
I would rename both of your display(self) functions to __str__(self).  In Game, that function would become

def __str__(self):
    return str(self.state)

Then you can just print my_game.


Masking user input passwords I have a method that accepts user input. Additionally, it masks passwords then the input is a password. It also bypasses the prompt of if an env variable supplies the needed input.

Apparently, my code needs refactoring, but how?

def self.gets(args)
  array = []
  args.each do |arg|
    print "#{arg.to_s.capitalize}: "
    if ENV['AWESOMEAPP_'+arg.to_s.upcase]
      array.push ENV['AWESOMEAPP_'+arg.to_s.upcase]
    else
      if arg.to_s=~/password/
        array.push STDIN.noecho(&:gets).chomp
      else
        array.push STDIN.gets.chomp
      end
    end
    print "\n"
  end
  array
end

After reading @user1777136 s answer, I came up with this

module Awesome
  # Has methods that are similar to but extended versions
  # of core ruby methods
  module Extensions
    # Get multipe inputs from user
    # Masks passwords if detected
    # Bypasses prompt when ENV variables present
    def self.mgets(names)
      names.map do |name|
        sgets(name)
      end
    end

    # single gets
    def self.sgets(name)
      print "#{name.to_s.capitalize}: "
      return env_sgets(name) if ENV['AWESOME_' + name.to_s.upcase]
      return secure_sgets if name.match?(/password/)
      STDIN.gets.chomp
    end

    # get from env variable
    def self.env_sgets(name)
      ENV['AWESOME_' + name.to_s.upcase]
    end

    # secure gets from stdin
    def self.secure_sgets
      STDIN.noecho(&:gets).chomp
    end
  end
end


Generating all unlabeled trees with up to n nodes I want to visualize all unlabeled trees with \$n\$ or fewer nodes, not just count them.

First idea/attempt: Take a list of all \$n-1\$ node trees, then append a new leaf to every tree in every way to get a new list of \$n\$ node trees. Clearly, this new list will contain a lot of isomorphic duplicates. To fix this, we start adding the \$n\$ trees to a new list, and doing so only if they are not isomorphic to any of the trees in the new list. Since graph isomorphism problem is not known to be solvable in polynomial time, this makes the entire process even more horrible performance wise, because this process will do a lot of such checks.

My question is if this can be done more efficiently, or in a better way?

The python code implementing this idea/attempt using networkX and pyplot:

""" trees of order N or less will be generated """
N = 9

import networkx as nx

""" return copy of graph with newNode node appended to toNode node """
def leaf_copy(graph, newNode, toNode):
    g = nx.Graph.copy(graph)
    g.add_node(newNode)
    g.add_edge(newNode,toNode)
    return g

from networkx.algorithms import isomorphism

""" get all n+1 node cases out of all n node cases in prevTreeList """
def genNextTreeList(prevTreeList):
    """ one node case """
    if prevTreeList == None or prevTreeList == []:
        g = nx.Graph()
        g.add_node(1)
        return [g]

    """ new loads of n+1 graphs by all possible list appendations """
    """ this will include loads of isomprhic duplicates... """
    nextTreeList = []
    for g in prevTreeList:
        v = len(g.nodes())+1
        for node in g.nodes():
            nextTreeList.append(leaf_copy(g,v,node))

    """ remove isomorphic duplicates """
    """ it will check every graph to be added with all added graphs for isomorphism... """
    nextTreeListClean = []
    for g in nextTreeList:
        isomorphic = False
        for clean_g in nextTreeListClean:
            i = isomorphism.GraphMatcher(g,clean_g)
            if i.is_isomorphic():
                isomorphic = True
                break
        if not isomorphic:
            nextTreeListClean.append(g)
    return nextTreeListClean

import matplotlib.pyplot as plt

if __name__ == "__main__":

    print(0, "\t", 1)

    G = []
    figure = 0
    for n in range(N):
        G = genNextTreeList(G)

        """ print the number of examples to check if the code is working properly """
        print(n+1, "\t", len(G))

        """ draw and save the plots """
        for g in G:
            figure += 1
            fig = plt.figure(figure)
            plt.title(str(n+1)+'.'+str(G.index(g)+1))
            nx.draw(g, with_labels=False)
            plt.figure(figure).savefig('plot'+str(figure)+'.png',bbox_inches='tight',dpi=100)
            plt.close(fig)

1. Review

In Python, a docstring goes after the function or class introduction. So instead of:

""" return copy of graph with newNode node appended to toNode node """
def leaf_copy(graph, newNode, toNode):

write something like:

def leaf_copy(graph, newNode, toNode):
    """Return a copy of graph with newNode appended to toNode."""

There are several advantages of doing it this way. Docstrings are available via the help function in the interactive interpreter:

>>> help(leaf_copy)
Help on function leaf_copy in module __main__:

leaf_copy(graph, newNode, toNode)
    Return a copy of graph with newNode appended to toNode.

Also, some integrated development environments (for example, PyCharm) can read and interpret docstrings to provide context-sensitive help or to generate reference documentation. And the built-in doctest module can automatically run examples in docstrings.
The trivial graph with one node and no edges is generated like this:

g = nx.Graph()
g.add_node(1)

but networkx has the function trivial_graph which does something similar.
The specification of genNextTreeList is:

""" get all n+1 node cases out of all n node cases in prevTreeList """

but this only the case if prevTreeList is the result of iterating genNextTreeList starting with an empty list. A more accurate specification would be something like this:

def genNextTreeList(prevTreeList):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in prevTreeList,
    except that if prevTreeList is None or the empty list, in which
    case a list containing the trivial graph is returned.

    """

It says in the Zen of Python,

  Special cases aren't special enough to break the rules.

so I would drop the special case. It is easy enough for the caller to pass the list containing the trivial graph, if that's what's wanted.

Also, it should be clear now that genNextTreeList does not only operate on trees. So a better name and specification would be something like this:

def augmented_graphs(graphs):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in the argument.

    """

Instead of having a flag isomorphic to determine whether the new graph has been found to be a duplicate, use Python's for ... else: ... statement, or the any or all functions.
There's no need to use networkx.algorithms.isomorphism.GraphMatcher: you could just call networkx.algorithms.isomorphism.is_isomorphic directly.
genNextTreeList has a two-step construction of the result: first, construct a list nextTreeList of augmented graphs, and second, eliminate duplicates. These could be combined into a single step by testing each new graph for isomorphism as soon as you construct it, like this:

from networkx.algorithms.isomorphism import is_isomorphic

def augmented_graphs(graphs):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in the argument.

    """
    result = []
    for old_graph in graphs:
        new_node = max(old_graph.nodes()) + 1
        for node in old_graph.nodes():
            new_graph = leaf_copy(old_graph, new_node, node)
            if not any(is_isomorphic(new_graph, g) for g in result):
                result.append(new_graph)
    return result

The top-level code does two things: it generates the free trees with up to N nodes, and it plots them. This would be better split into two functions each of which does a single thing, for example:

from networkx.generators.classic import trivial_graph

def free_trees(n):
    """Return list of free trees with up to n vertices."""
    result = trees = [trivial_graph()]
    for i in range(n - 1):
        trees = augmented_graphs(trees)
        result.extend(trees)
    return result

2. Alternative approach

A look at the NetworkX manual finds networkx.generators.nonisomorphic_trees.nonisomorphic_trees which implements the algorithm of

Robert Alan Wrights, Bruce Richmond, Andrew Odlyzko and Brendan D. Mckay (1986). “Constant time generation of free trees”. SIAM J. Comput. 15:2, pp. 540–548.

This generates the 19,320 free trees on 16 nodes (see A000055) in just over a second:

>>> from networkx.generators.nonisomorphic_trees import nonisomorphic_trees
>>> from timeit import timeit
>>> timeit(lambda:list(nonisomorphic_trees(16)), number=1)
1.0307372510433197

Here are 100 of these trees:


Are these good examples of functions that do one thing only or am I getting a little carried away? I'm reading Robert C. Martin's "Clean Code" and for the past few days I've been fiddling with its function writing guidelines. At first I thought the idea of functions being two/three lines long to be ludicrous, but I'm slowly getting the hang of it. The problem is, I'm pretty sure I'm overdoing it now.

These are the first lines of the module I decided to refactor using the advice from the book.

Public Sub ExportAvailabilityData()
  Dim aplicativo As Excel.Application
  Set aplicativo = CreateObject("Excel.Application")
  aplicativo.Visible = True

  Dim pastaDeTrabalho As Excel.Workbook
  Set pastaDeTrabalho = aplicativo.Workbooks.Add

  Do Until pastaDeTrabalho.Sheets.Count = DaysInMonth(Month(Date)) + 1
    pastaDeTrabalho.Sheets.Add
  Loop

  Dim day As Integer
  For day = 1 To DaysInMonth(Month(Date))
    pastaDeTrabalho.Sheets(day).Name = Format(day, "00") & "." & Format(Month(Date), "00")
  Next day

  pastaDeTrabalho.Sheets(DaysInMonth(Month(Date)) + 1).Name = "Summary " & UCase(MonthName(Month(Date)))
End Sub

Private Function DaysInMonth(ByVal month As Integer) As Integer
  DaysInMonth = Day(DateSerial(Year(Date), month + 1, 1) - 1)
End Function

And this is how it looks like today.

Public Sub ExportAvailabilityData()
  Dim aplicativo As Excel.Application
  Set aplicativo = CreateObject("Excel.Application")
  aplicativo.Visible = True

  Dim pastaDeTrabalho As Excel.Workbook
  Set pastaDeTrabalho = aplicativo.Workbooks.Add

  CreateSheets pastaDeTrabalho
  NameSheets pastaDeTrabalho
End Sub

Private Sub CreateSheets(ByRef pastaDeTrabalho As Excel.Workbook)
  CreateDailySheets pastaDeTrabalho, Month(Date)
  CreateSummarySheet pastaDeTrabalho
End Sub

Private Sub CreateDailySheets(ByRef pastaDeTrabalho As Excel.Workbook, ByVal month As Integer)
  Do Until pastaDeTrabalho.Sheets.Count = DaysInMonth(month)
    pastaDeTrabalho.Sheets.Add
  Loop
End Sub

Private Sub CreateSummarySheet(ByRef pastaDeTrabalho As Excel.Workbook)
  pastaDeTrabalho.Sheets.Add
End Sub

Private Function DaysInMonth(ByVal month As Integer) As Integer
  DaysInMonth = Day(DateSerial(Year(Date), month + 1, 1) - 1)
End Function

Private Sub NameSheets(ByRef pastaDeTrabalho As Excel.Workbook)
  NameDailySheets pastaDeTrabalho, Month(Date)
  NameSummarySheet pastaDeTrabalho, Month(Date)
End Sub

Private Sub NameDailySheets(ByRef pastaDeTrabalho As Excel.Workbook, ByVal month As Integer)
  Dim day As Integer
  For day = 1 To DaysInMonth(month)
    pastaDeTrabalho.Sheets(day).Name = AssembleDailySheetName(day, month)
  Next day
End Sub

Private Sub NameSummarySheet(ByRef pastaDeTrabalho As Excel.Workbook, ByVal month As Integer)
  Dim index As Integer
  index = GetSummarySheetIndex(month)
  pastaDeTrabalho.Sheets(index).Name = AssembleSummarySheetName(month)
End Sub

Private Function GetSummarySheetIndex(ByVal month As Integer) As Integer
  GetSummarySheetIndex = DaysInMonth(month) + 1
End Function

Private Function AssembleDailySheetName(ByVal day As Integer, ByVal month As Integer) As String
  AssembleDailySheetName = Format(day, "00") & "." & Format(month, "00")
End Function

Private Function AssembleSummarySheetName(ByVal month As Integer) As String
  AssembleSummarySheetName = "Summary " & UCase(MonthName(month))
End Function

When I considered replacing the "." constant inside AssembleDailySheetName() with a call to yet another function (GetDateSeparator() or something similar), I decided to stop and get some feedback.

I think you have definitely taken it in the right direction. Excellent work!

I don't see any compelling reason to break AssembleDailySheetName() down any further.

My only complaint is that I don't really like the separation of adding and naming the sheets. I see both steps as being part of creating a sheet. I think it would be nice to set the name of the sheet immediately after adding it (in the same function). That will likely eliminate some code as well. I suspect Sheets.Add may return the new sheet. If that's the case, there would be no need to look up the sheet by index to name it.