Prove it - n factorial is bigger than 2^n

I've been doing the scala coursera and wanted to write down the proof that

factorial(n) ≥ 2ⁿ when n ≥ 4

since it uses induction and I am out of practise.

Base case

For n = 4

factorial(4) = 4*3*2*1 = 24
and 2⁴ = 2*2*2*2 = 16
furthermore 24 ≥ 16

so factorial(n) ≥ 2ⁿ when n = 4

Induction step

For n >= 4 assume we have

factorial(n) >= 2ⁿ

and consider

factorial(n+1) = factorial(n) × (n+1)
 ≥ 2ⁿ × (n+1)
 ≥ 2ⁿ × 2 since (n+1) ≥ 2 when n ≥ 4
 = 2ⁿ⁺¹

QED

Remote debugging python in Visual Studio

Suppose you have a script you want to run on linux and you only know how to drive the Visual Studio debugger. By installing an add-in for Visual Studio locally, installing the python tools for Visual Studio debugging on the remote machine, e.g. with pip install ptvsd==2.0.0pr1 and adding a (minimum of) a couple of lines to your script you can debug in Visual Studio even if the remote machine is running linux.
The additional lines are highlighted in the following script:

#!/usr/bin/python

"""
You will need to insert both these in your script
The remote box requires the ptvsd package (otherwise the import fails)
"""
import ptvsd
ptvsd.enable_attach(secret = 'joshua')
#use None instead of joshua but that is not secure
#The secret can be any string - but this is not properly secure


def say_it(it):
  """
  This inserts a breakpoint
  but you can add new breakpoints in Visual Studio
  if required too/instead
  """
  ptvsd.break_into_debugger()
  print(it)

if __name__ == "__main__":
  #pause this script til we attach to it
  ptvsd.wait_for_attach()
  say_it("Hello world")


See https://pytools.codeplex.com/wikipage?title=Remote%20Debugging%20for%20Windows%2C%20Linux%20and%20OS%20X for more details and be wary of line ending in VS which may be inappropriate for linux.

Install the ptvs from the relevant msi for your version of Visual Studio.

Start the script on the linux box:
$python VSPyNoodle.py

It will hang, since it has a wait_for_attach call in main. 
ctrl-Z will stop it on the remote box if something goes wrong.

Select "Attach to process" in the Debug menu on Visual Studio
Change the "Transport" to "Python remote debugging (unsecured)"

Add the secret (joshua in this script) @ hostname to Qualifier
e.g. joshua@hostname

Hit "Refresh"

It should find the process running on the linux box and add the port it uses to the Qualifier
Select your process in the list box and hit "Attach"
  then debug as you are used to in VS.

If it complains about stack frames and not being able to see the code you may need to make a VS project from a local version of the code. having made sure it exactly matches the remote code.

Mutable structs in C#

We know what this does, right?

    struct Pricer
    {
        public double Price;
        public long Size;

        public void AddExecution(long lastSize, double lastPrice)
        {
            Price = (Price * Size + lastSize * lastPrice) / (Size + lastSize);
            Size += lastSize;
        }
    }

    class PriceData
    {
        public Pricer pricer;
    }

    class Program

    {

        static void Main(string[] args)
        {
            Pricer price = new Pricer{Price = 0.0, Size = 0};
            for (int i = 0; i < 5; ++i)
            {
                Console.WriteLine("{0} {1}", price.Price, price.Size);
                price.AddExecution(1, 2.5 * (i + 1));
            }

            for (int i = 0; i < 5; ++i)
            {
                Console.WriteLine("{0} {1}", price.Price, price.Size);
                price.Price= 2.5 * (i + 1);
            }

            PriceData priceData = new PriceData();
            priceData.pricer = price;
            for (int i = 0; i < 5; ++i)
            {
                Console.WriteLine("{0} {1}", price.Price, price.Size);
                priceData.pricer.AddExecution(1, 2.5 * (i + 1));
            }

       }

    }

Eric Lippert tells us about mutating *readonly* structs: http://blogs.msdn.com/b/ericlippert/archive/2008/05/14/mutating-readonly-structs.aspx but even non-readonly structs can get us in a mess.

Pdb ftw

pdb - python debugger

If a script throws an exception, try running it in the debugger

python -m pdb myscript.py

For example given the following (rubbish) python program

C:\Dev\src>cat bad.py
def naughty():
 raise Exception()

naughty()

if we just run it the exception tries to escape ...

C:\Dev\src>python bad.py
Traceback (most recent call last):
 File "bad.py", line 4, in <module>
 naughty()
 File "bad.py", line 2, in naughty
 raise Exception()
Exception

So, we know what line the problem's on. We could change the script to see what's going on using

import pdb; pdb.set_trace()

or we could run it under a debugger.

Run script through debugger

Invoke the pdb module in python and send it your script, e.g.

python -m pdb bad.py

This gives a (Pdb) prompt to type instructions in to:

> c:\dev\src\bad.py(1)<module>()
-> def naughty():
(Pdb)

Type 'c' for continue - it will halt when it gets an exception, as follows

(Pdb) c
Traceback (most recent call last):
 File "C:\Python27\lib\pdb.py", line 1314, in main
 pdb._runscript(mainpyfile)
 File "C:\Python27\lib\pdb.py", line 1233, in _runscript
 self.run(statement)
 File "C:\Python27\lib\bdb.py", line 387, in run
 exec cmd in globals, locals
 File "<string>", line 1, in <module>
 File "bad.py", line 1, in <module>
 def naughty():
 File "bad.py", line 2, in naughty
 raise Exception()
Exception
Uncaught exception. Entering post mortem debugging
Running 'cont' or 'step' will restart the program
> c:\dev\src\bad.py(2)naughty()
-> raise Exception()
(Pdb)

At this point

 (Pdb) p <variable_name>

can be used to inspect variables, and

 (Pdb) a

shows any arguments to a function.

Main Pdb commands

Type 'q' for quit, 's' to step (maybe into another function) or 'n' to move on to the next line.

'w' shows where you are in the stack, 'u' moves up and 'd' moves down.

b(reak) [[filename:]lineno  sets a breakpoint.

There are more details in the manual: http://docs.python.org/2/library/pdb.html

Virtual functions in constructors and destructors

Interview question.

What does this do?

class Base
{
public:
Base()
{
log();
}
virtual ~Base()
{
log();
}

//virtual void log() = 0;//note this compiles but doesn't link
virtual void log()
{
std::cout << "Base\n";
}
};

class Derived : public Base
{
public:
Derived()
{
log();
}
~Derived()
{
log();
}
virtual void log()
{
std::cout << "Derived\n";
}
};

int main()
{
Derived d;
}

I half remembered this http://www.artima.com/cppsource/nevercall.html so wasn't sure.

Review of Overload "editorials"

I have run Charles Stross' code over my Overload "editorials" in the hope of generating some kind of end of year review. Any favourite phrases anyone?
 
---

the incoming information and produced metres of punched cards, for example musing on the name to the death of Ceefax. Started in and being replaced by keyboards. On Wednesday I got 0. On Wednesday I got 258 (plus some on accounts.

the perpetual call. There is the problem. Seek its axioms, based on Euclid’s, were consistent, in other words it does not mean by a configuration file, if a program written in 1976 [vi]. Many editors allow syntax high-lighting now, adding an.

the words 'Surreal' 'Mutation' standing out proudly. Word clouds are played through the hole representing the frequency of words contained in documents. A more traditional approach would present a histogram, with bars showing how many times an item appears. Wikipedia suggests.

the creation of the calculus gave ways to form the language, though paused for Turing. Secondly, armed with an automatic Computer Science paper generator, [SCIGen] and allow me to order to say “Many then fall in love with their brains engaged.

the system within the system, but when it’s dead. Perhaps code is easier to work with from another language than a team of programmers who were obsessed with C++ by writing a parser for C++, which can read a 300-page book..

the mouse (1968) and ways of solving problems to emerge. Introduction of the calculus gave ways of us the fore [Matthews]. Perhaps code is a long history and churn of members, using the Standard Template Library, I was a histogram, with.

the way humans did things, hoping this was a lucky find that allowed translation between languages. Can you will have to press the trendy face of ways to make unchanged code behave in which it has also spawned excellent science fiction.

the real objects located in space numerically, ranging from test and refactor and then compute the same sequence as M. Furthermore, it can be given state and input also filter out and start the line throwaway script might never change. I.

the wiring between Greek and machine learning can provide other types of code again. Electronic wizards can be given the instructions for a four year stint. Allow me to order search results by weight. Feel free to back me up on.

the natural numbers, there are two. The next state. It is trained to appreciate beauty. It is of course, easier to program if you can give rules to mention its powers of intimidation." [DASKeyboard] Research into the requirements or trying to.

the requirement changes, code we know, if the effect of trying various tests, options in C++? C++ is provable or falsifiable. This would allow all of mathematics to sound motifs or short tunes. The authors notice that a musical background made.

the debate you come down on. He then suggests "foldering may miss thereby allowing word-processing. They were also used as M. Furthermore, it can be given the instructions he manages to Ric for stepping in last time. I do often a.

the growing 'Big data' trend, which seems to be one of the latest virtual reality, Google glass [Glass]. A computer interface that allows editing changes the game. Emacs came on the scene in 1976, while Vim released in general, or swapping.

the “Electronic Numerical Integrator and slowly turned into something substantive. It's practically the opposite of engineering. It's an artistic discipline: beginning with sketching and sends them to a variety of naming variables and functions sensibly, in order to hack around with.

the prevalence of doing something. If it works, it easier than an answer. We have sometimes taken as “You have decayed away. Imagine that one day. A variety of ways of editing inputs for computers, so many technical books do you.

the idea of an editorial. How do you own that weigh less than this? How many books I own. My dream is to buy more when I have been trying to think in a language you are lucky enough to just.

the ACCU conference do not count. So, how it well as a strange word. When this wouldn't be necessary. The live speech has grown from Google’s machine learning. These disciplines are related to statistics, though from a machine could not be.

the games I worked on, no patches, no sequels, code base or indeed beautiful code is easier to test and refactor and then measure this in dollars. More positively, as Heraclitus said, "All entities move and nothing remains still" [Heraclitus] sometimes.

the hook. If any readers wish to continue and every Turing computable function.” [Turing_completeness] That was helpful, wasn’t it? Equivalently, it can simulate a universal language and useless.” As stated at the outset, we might need to learn to think deeply.

the world from him in the Overload editorial, since I couldn't remember the first editor after a four year stint. Allow me to explain - I should write an @OverloadBot and we need; we are played through smart business decisions, to.

Exit code crimes

I've seen a few exit code crimes recently, so I thought I'd list them.

1. Catch something specific

if __name__ == "__main__":
    try:
        run(None)
        sys.exit(0)
    except ValueError:
        sys.exit(1)

So, what does this do if another type of error is thrown? Why is it catching a specific type of error? The rest of the code is logging info - why don't we log the error? How does this make troubleshooting easy, or even possible?

2. Throw something specific

The pattern above is of course fine when the run function works like this:

def run(config):

    try:

    catch:

        raise ValueError

3. Tell no-one

Make the last line in you script

exit(0)

regardless of whatever just happened. There was a chance the script could return the exit code of whatever it called, so typing the extra line is first, effort, second achieves nothing, and finally means no-one will notice if something went wrong. Or at least not at the time. Perhaps whoever did that thought a shell script won't exit without the keyword exit at the end.