This program takes (from stdin) a value N followed by N lines representing a graph structure where each line consists of an integer id followed by an arbitrary number of integers representing the id’s of the bordering nodes.
The program then computes and outputs a list of the nodes (in the order they were entered) with a colour value ranging from 0..k such that each node has a unique colour to it’s bordering nodes.
This program expects 4 arguments to be passed in on the command line representing the location (as xy coords) of two circles. The program then computes the total area covered by the two circles including any possible overlap between them and prints the area to the console.
Despite the fact that this problem can be solved numerically in constant time using the equation:
D = sqrt( (x-u)^2 + (y-v)^2 )
A = (2 * PI) - (2 * ACos( D / 2 )) + (D / 2) * sqrt( 4 - D^2 )
I thought it would be more of a programming challenge to write a simple monte carlo simulation to solve for the area. The simulation can easily be modified to allow an arbitrary number of circles to be inputed at varying radii.
I decided to start taking part in some of the programming challenges over at /r/dailyprogrammer. The first of which was to read in an input file representing an edge/node graph structure of the form:
0 -> 1
1 -> 2
2 -> 4
3 -> 4
0 -> 3
And to output the Adjacency Matrix of the graph in the form:
0 1 0 1 0
0 0 1 0 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0
Below is the code of my submission. I decided to make the challenge a little more interesting using bit level operations to store the matrix in ~approx~ N*N bits rather than the usual minimum of N*N bytes.
Another opinion piece if you’ll grant me the time. Not that there’s anyone to read it but this site, much like blogging was in the olden days of the internet is really more of a hobby and for peace of mind than anything else.
This post was once again inspired by a comment on reddit asking why there were so few good resources for people who wanted to start their education into programming and software engineering by learning in C++.
In my honest opinion as a developer, a computer scientist, and as a teacher the reason there are no “good” resources for people looking to start with C++ is because C++ is just not something you should start with.
Programming is a relatively unimpressive skill to have on its own. The knowledge and ability to design software on the other hand is an incredibly powerful thing to be able to do. Having that ability gives unmeasurably high value to your ability to program, and it scales with how many paradigms, languages, and platforms you can take that to.
Programming is simply syntax wrapped around design. A house is a design built in brick, and likewise a piece of software is a design programmed in syntax.
Now tell me, is it of vital importance that you learn all the engineering principles, all the design aspects, all the architecture concepts, and all the safety mechanisms to build a house at the same time as you learn to lay diamond encrusted bricks in the most elaborate and complicated way possible? Of course it isn’t! It’s much more sensible (and safe) to learn to build a house with normal, simple, sensible bricks and then work on your skills and work your way up to laying diamond encrusted bricks in fancy patterns.
In exactly the same way, this is why someone who has never programmed before should not just dive into C++. Why make life harder for yourself when you just aren’t going to benefit from it? It’s much more sensible (In my opinion at least) to learn about language structures like loops and conditionals, and then learn about Imperative design patterns, and Object Oriented design patterns, and learn about inheritance, and interfaces, and type checking, object references, and data structures, and algorithms, ect, in an easy to pick up and safe to f#$k up language like python or java or C# who all have simplified and friendlier syntaxes (I’m not looking to start a war of which language is best/worse). Then if and when you have a use or a desire to use C++ you already know how to design the house. All you need is the bricks and mortar.
People become complacent and become afraid to branch out from their comfort zones
Another thing that really comes into play here, and this can be a really touchy subject for a lot of developers. You need to pick the language that’s right for the job. And as often is the case, there will be no perfect language. There will certainly be ones which are worse than the others, but there may be several who all excel towards one aspect of your goal but each fall short in some way making none of them quite right. In this case you need to pick the one you feel most comfortable with and roll with it.
A lot of the time I see people trashing languages, Java gets a terrible reputation and a similarly PHP developers have to hide their heads in shame as they pour their coffee at lunch. This (to me) is ridiculous. Each has it’s benefits, and each has it’s laundry list of shortcomings; just like every other language. Every language has it’s purpose, even BrainFuck and MOO had a place in the scientific community. Developers get really attached to their languages and tool chains and far too often they would rather reinvent the wheel bulkier, buggier, slower, and harder to use just to stay within their comfort zone so they don’t have to swap environments (or sometimes even as little as changing their IDE for five minutes…).
So here’s my point.
If a person is coming into a development situation fresh, and they have no prior knowledge of programming, and they have to (unavoidably have to) be developing in C++ for whatever reason, then that person is catastrophically unprepared for what they have walked into. Plain and simple. However, if that person just inherently thinks of C++ as the ultimate in coding and they want to do it in C++ just because then chances are 99.999999% of the time they can do it in a different language, a language that will be friendlier, be easier to learn in, will have libraries which are far easier to incorporate and run with, and will have a development environment which is often far easier to setup and target for their system. More importantly, is a person who is fresh to to all of this and knows very little on the subject really in a position to make an informed decision on what environment is “the best one, I must use that one!” ? By very definition they are not.
Oh yes, gather round for another classic Joss rant explanation of common development myths and theories.
Today’s story comes to us from another reddit post, this time asking about why there is (in general) a stigma towards sites like Code Academy who aim to make programming excessible and easy for the masses.
I think a big thing here that just needs to be stated is that Programming is not the same as Software Engineering.
Anyone can go online and learn a programming language, the syntax is relatively easy and sites like Code Academy do a pretty good job of teaching that most of the time. But they teach two things, “syntax” and the very very very basics of “program structuring.”
Developers give sites like Code Academy a bad rep because they actively (if not always intentionally) promote the idea that coding is the same as building a piece of software. They say…
Anyone can do <it>! <It's> easy! Come here today and learn <it>! <It> only takes an hour or two…
<It> being to write lines of code in a text editor and run it, but implied to mean you can start the next facebook.
Software Development is barely connected to coding. The code and the language are just how you write it down and give it to the computer. Yes, there is a lot of coding, sometimes millions of lines of it in a large system. But that pales in comparison to what those lines of code represent.
When you design software you build based on design patterns. Not every pattern is perfect for every situation which is why you need to know a lot of them so you can use the best one for each job. Similarly within those patterns you will be using data structures (arrays, hash tables, linked lists, databases, ect). Again, not one of them works perfectly for every use case. You need to know how they work and which is the best to use for each situation.
Anyone can learn to write int a = new int; or HashMap<String, Object> t = new HashMap<>(); in five minutes. It takes a lot longer to learn how they work and when to use them.
That is the difference between “programming” and “software engineering”, and that is why so much of the development community look down on sites like code academy. They paint a false image of the industry and the profession that many of us have devoted many years of our lives and education to.
Now. This is not to say we all know everything and what is best. This is a constantly evolving and changing field and we all are constantly learning and reworking the way we approach the problems presented to us.
I don’t mean to sound discouraging, if I have appeared that way thus far then please have my apologies. That was not my intention. My intent was show why the when the entire world has the ability and accessibility to learn to program and the attitude that they can master web developement and start the next instagram and that it will all be easy because computers are so good these days, that we will still be the same industry we had before they all learned and we will still be the “valued” workforce that we are.
Because you just can’t learn everything we’ve learned by doing tutorials online. Yes we too do online tutorials, watch lecture videos from conferences, go to seminars and master classes.. Yes we do those things too. But we have also been actually doing this work for years, learning from real-life projects, and directly from colleagues who had been doing this far longer than us. Many of us went to university and exclusively studied Computer Science, and algorithms, and software engineering, and project management and lots of other things we use every single day on the job.
In essence, Code Academy and everything it stands for only seeks to invalidate and deprecate everything that gives our experience and our industry value. Even if they did it under the best possible intentions.
A note about the growing trend towards GPGPU for the masses. This is my response to a Reddit post I saw about a new GPU language, I felt I should copy it here.
As someone who does a lot of development using the GPU a new language is the last thing I want. Programming for the GPU is complicated, it just is, and it should be because what you are running your program on is a very complicated piece of hardware. You have to treat it right and you have to structure your programs and algorithms in a specific way which is not common to other architectures.
All these attempts lately to make GPU programming easy and doable for everyone (the LISP and Haskell libraries come to mind) completely miss the mark. They work under the premise that if you make it easier, everyone can make everything GPU accelerated, and that that will be better. It won’t.
Half the problem with current libraries that make CPU concurrency easier is that people start parallelizing too early. They don’t fully and completely optimize something they already have, they don’t go in and profile it, they don’t notice long system calls and work in a bit of assembly which will reduce the latency. No. Instead they will just chuck some threads in there, because threads make things faster… It’s just not true.
This problem is even more volatile on the GPU. It’s a delicate balance and not every job is suited to the GPU just as not every job is suited to multi threading on the CPU. Giving people (the uninformed people at least) the power of the GPU for every conceivable task is just daft.
When you structure programs for the GPU you need to have full and complete control over everything it does and when it does it. Languages like OpenCL and CUDA may be complicated but your kernels do what they say they do. It’s exactly why writing good C is complicated because you are right on the hardware level with very low abstraction. OpenCL and CUDA don’t try to optimize what you wrote (past a few compile time optimizations which are to be expected) they translate your commands onto the hardware nearly directly. The downside of that is it means you need to fully and completely understand your algorithm and how the hardware will react to each stage of it, the benefit is incredible performance and massively parallel execution.
TL:DR GPU programming is hard for a reason and giving everyone an easy way to do it completely misses the point. It’s like trying to make everyones car into a supercar by handing out nitrous injectors.
So today I saw a post on /r/compsci where the poster was a new Comp Sci student 2 months into his course, having a hard time with programming and not sure how to keep going with his course so he can get a job as a Game Designer. I wrote quite a healthy response to him about how I feel people need to think about CS and I thought I’d mirror it here because it seems to have gone down very well on /r/compsci and because I haven’t posted anything in a few days.
Something that will become very apparent to you as you study CS is that it isn’t about C#, C++, or any one programming language. Yes you may have modules on certain languages but they are merely an ends to a means. That is to say, they don’t teach you C# so you learn how to program C# they teach it to you so you learn how to structure a hierarchical based Object Oriented (OO) program. Once you understand the theory of how to structure that kind of program you can learn the syntax of any like styled language and immediately run with it. Also bear in mind (rawr) that when they teach you C# they do not expect you to learn every function name in the standard library, they expect you to learn what things you can expect a language or standard library to come with. So that when you move to another like language and the standard library has all different function names you’re okay because you can just search what you need in the Language Documentation online.
Don’t use your degree to learn game development
Computer science is not about game development. However! A lot of the stuff you learn can be applied directly to game development. For instance, you shouldn’t learn “How to write a FPS game.”, you should learn…
3D Vector Mathematics and Trig
Object Oriented programming, and you’ll want to get pretty comfortable with a language so the code is neat and efficient
Graphics Programming (Probably using OpenGL)
If you have a module on “Game Theory” then by all means take it but bare in mind that Game Theory will be 99% breaking down and modelling very simple games like Coin Flip, Nim, Tower of Hanoi, ect in a very basic mathematical representation and will almost certainly include no programming unless they ask you to model any of those games as a Finite State Machine.
Use your degree to become exceedingly good at building programs
A good Computer Scientist does not know how to do one thing very well, with the mindset that “It’s okay, I’ll get a job doing that very specific thing.” (especially if that thing is Game Development) A good Computer Scientist understands Algorithm Design and Optimization, Data Storage Structures and Sorting, the benefits of Linear and Parallel execution and when to use each, the mathematics behind Formal Logic, Trig, Vectors, the (basic) Psychology of Human Computer Interaction (HCI) and how you can apply that to UI design, Database Design including Relational Algebra and Calculus to model them, …, the list goes on.
The game industry is Cut Throat and immensely competitive
You have likely heard this many times before but your dreams of working for a big game developer like DICE or 2K (just two random ones off the top of my head don’t downvote me because they aren’t your favorites) are probably not going to come to fruition.
Game Studios do not hire people based on their degree. I know, if you look at the recruitment page it says a BSc in CS and some experience working on other titles. This is just to push teenagers who think it would be a cool career to actually go to University and learn what they need to write that kind of software. Games after all, are software, and very complex pieces of software at that.
Truth be told if someone has a good enough programming portfolio and can show off a really impressive demo to a Game Studio they will not care which Uni (if any) you went to. They want good people (the best people) working for them. If you want one of three positions open at a Game Studio that 8000 people have applied for, you need to be the best.
But the best at what?
At a Game Company people do different jobs, they specialize, and then they get very good at what they do. A level designer probably doesn’t know much about how the core engine works, and he doesn’t have to. The Engine Designer probably can’t design a User Interface, and he doesn’t have to. And the UI designer… you get my point.
So pick a subfield of Game Development. If you hate programming and you don’t enjoy it, you are not going to be a professional programmer, or if you are you’re going to be miserable and you’ll write terrible code. There’s a lot to be said for the theory that good developers enjoy coding and writing software, and they do it in their spare time as a hobby despite the exact same thing being their 9-5. Anyway, you don’t like coding, so you aren’t going to be an Engine Programmer. If you like and enjoy Game Theory then maybe you should look into becoming a Level Designer. Designing a map in an FPS and designing a level in a Side Scrolling shoot’em up game use 90% the same skills and theory.
All of that said
You have only been at this for two months. It takes years to become a good and proficient Computer Scientist, it takes years to get to a point where you intuitively know how to layout and structure a piece of software, and even then you’ll make mistakes, and you’ll waste a lot of time redoing things in the “right” way only to have to redo them again.
If you are still worrying about C# and C++ don’t. They take time to learn but you’ll probably find it just clicks one day and you’ll realize that if this does that there a then this will do that and then that will happen, ect, and it will start to make sense.