The Christmas Present Problem: It’s Hard – NP-Hard

Santa Clause (downloded from Google 07 Dec 2014, labelleed as free to reuse)

Santa Clause (downloded from Google 07 Dec 2014, labelleed as free to reuse)

As Christmas approaches, many of us are faced with the annual problem of who to buy presents for, how much to spend, what presents to buy and how to be fair to everybody.

Is this a tough problem to solve? Perhaps some science will help?

Let’s try and state the problem a little more precisely, and make it simple by assuming that we are buying presents for just one person. That does not detract from the more complex problem, especially if we establish that buying presents for one person is hard.

  • You have to buy presents for just one person; your daughter
  • You have a certain budget; an amount of money that you cannot excced
  • You have a list of gifts that your daughter would like (we are assuming that she has been good so Father Christmas is willing to leave these gifts)
  • To make life easier, you have given your daughter 100 points, and told her to assign a certain number of points to each item. The more points she assigns, the more likely she is to get that gift. For example, if she assigns all 100 points to just one gift (and zero points to the other gifts), then she is likely to get that gift. But if she assigns equal points to all gifts, then she is equally likely to get each item, but not all of them, as the total costs of the gifts bought cannot be more tha the overall budget.

Your task is to buy as many presents as possible which maximizes the number of points, whilst staying within your budget.

How difficult do you think it is to find a solution to this problem so that you daughter gets the best possible gifts such that there is not another selection of gifts that has a higher overall points value?

In fact, it is surprisingly difficult, especially as the number of available presents (and people you are buying for)  increases.

Pile of wrapped presents: http://christmasstockimages.com/free/objects/slides/many_christmas_gifts.htm (CC 3.0)

Pile of wrapped presents: http://christmasstockimages.com/free/objects/slides/many_christmas_gifts.htm (CC 3.0)

The problem is the so called Knapsack Problem, so named as you have knapsack which can carry a certain weight (your budget). Each item has a weight (cost of each item) but also a value (the number of points). You have to fill the knapsack, maximizing the value, but keeping the sum of all the weights less than the capacity of your knapsack.

Or, in terms of the Christmas Present Problem, you need to buy the best selection of presents to give the maximum number of points, while staying within your overall budget.

The Knapsack Problem is known to be an NP-Hard problem. These type of problems do not, as yet, have any efficient algorithm that can produce the optimal solution in reasonable time. At least for large sized problem instances. Hopefully, you can still give your daughter the best set of presents!

In fact, if you can find an efficient algorithm you could win one million dollars.

  

How to get ants to solve a chess problem

How to get ants to solve a chess problem

By Graham Kendall, University of Nottingham

Take a set of chess pieces and throw them all away except for one knight. Place the knight on any one of the 64 squares of a chess board.

Can you make 63 legal moves so that you visit every square on the chess board exactly once? As a reminder, a knight can move two squares in a straight line, followed by a ninety degree turn and a move of one further square. It might seem like a hard task, but this set of moves, called the knight’s tour, can be achieved in too many ways to count.

The knight's tour

If you are able to make the 63 moves and end up on a square from which you can move back to the original square with the 64th legal move, then this is known as a closed tour. Other tours are called open tours.

Mathematicians have pondered how many closed tours exist, and they have come up with an astonishing number: more than 26 trillion. There are so many more open tours that we do not know the exact number.

Both Philip Hingston and I were so captivated by the knight’s tour problem that we wanted to find a different way to solve it. We found that motivation in nature – specifically in ants.

Ants use a certain pattern, or algorithm, to forage for food. This algorithm can be used to tackle many types of problems including the Travelling Salesman Problem and Vehicle Routing Problems. Philip and Graham wondered if they could use the ant colony optimisation algorithm to solve the knight’s tour problem.

Here’s how that algorithm works: a computer program is used to simulate a population of ants. These ants are assigned the task to find a solution to a problem. As each ant goes about their task they lay a pheromone trail – a smelly substance that ants use to communicate with each other. In the simulated algorithm, the most successful ants (the ones that solve the problem better), lay more pheromone than those that perform poorly.


L. Shyamal

We repeat this procedure many times (perhaps millions of times). Through repetitions, the pheromone trails on good solutions increase and they decrease on the poorer solutions due to evaporation, which is also programmed in the simulation algorithm.

In the simulation to solve the knight’s tour problem, the ants could only make legal knight moves and were restricted to stay within the confines of the chess board. If an ant successfully completes a tour then we reinforce that tour by depositing more pheromone on that tour, when compared to a tour that was not a full tour.

Ants which attempt to find later tours are more likely to follow higher levels of pheromone. This means that they are more likely to make the same moves as previously successful ants.

There is a balance to be struck. If the ants follow the successful ants too rigidly, then the algorithm will quickly converge to a single tour. If we encourage the ants too much, not to follow the pheromone of previous ants, then than they will just act randomly. So it is a case of tuning the algorithm’s parameters to try and find a good balance.

Using this algorithm, we were able to find almost half a million tours. This was a significant improvement over previous work, which was based on a genetic algorithm. These algorithms emulate Charles Darwin’s principle of natural evolution – survival of the fittest. Fitter members (those that perform well on the problem at hand) of a simulated population survive and weaker members die off.

It is not easy to say why the ant algorithm performed so well, when compared to the genetic algorithm. Perhaps it was down to tuning the algorithmic parameters, or perhaps ants really do like to play chess!

The knight’s tour problem was being worked on as far back as 840 AD. Little did those problem-solvers know that ants, albeit simulated ones, would be tackling the same puzzle more than 1,000 years in the future.

The Conversation

Graham Kendall does not work for, consult to, own shares in or receive funding from any company or organisation that would benefit from this article, and has no relevant affiliations.

This article was originally published on The Conversation.
Read the original article.

  

My First Java Project

My first Java project

Java Programming. Downloaded from Googled, labelled as free to reuse, under Wikipedia Commons. URL: http://commons.wikimedia.org/wiki/File:Java_Programming_Cover.jpg

It’s been a while since I decided to use Java as my new programming language of choice. Since my last post I have been honing my Java skills, with my first java project.

I had a project I needed to do that is about analyzing academic papers, comparing them in various ways, sorting them, writing out reports etc.

My first instinct was to use PHP (which I learnt a few years ago – and I really like the language) but the only development environment I have is on a server. I could set up a development environment on my desktop, but it did not seem worth it for the times that I would use that environment in anger.

The other option was C++, but that went against what I was trying to do for this project, as you’ll understand if you read earlier posts in this project.

So, the obvious solution was to use Java.

As my first Java project, it seemed to have suitable complexity for a first time Java user, but allowing for the fact that I have a programming background. I suspect that the project would not be suitable for a complete newbie to programming.

The details of what the project has to deliver is not that important but the lessons learnt are important, as these are things that I can use in later, larger, projects. These included:

  • Reading in a CSV (Comma Separated Variable) file. This is always a useful thing to be able to do. It’s one of those fall backs that is useful to have in your armoury as it makes accessing files such as spreadsheets and databases easy to do as they invariably have an option to save as a CSV file. Of course, it’s usually possible to access spreadsheets and databases directly (which is what I used to do under C++ using ODBC) but for this project I thought I would get to grips with CSV first. After some searching, I came across a package called CsvReader. It’s not the most basic package (which is a good thing), and it did have good reviews. I had some challenges installing it, but that was not to do with the package but the fact that this is the first time I have installed a Java package. Once I had sorted that out, it worked perfectly.
  • Writing out a latex/PDF file. One of the things I wanted to do was produce a half decent looking report. My initial thought was to write out a text file and then use Word to manually format it. This, for many reasons, is not a good idea; not least of all as it would be labour intensive every time I produced a new version of the report. I like to think that I had a flash of inspiration (but perhaps it is the obvious thing to do) and I decided to write out a latex file that I would convert to PDF via a suitable editor (my editor of choice at the moment is TexStudio, although I have used WinEdt in the past). This seems to work pretty well and I can now produce nice looking reports, without having to worry too much about the look of the final document as Latex will handle this as long as I have some idea of the structure as I develop the program. Of course, the beauty is that the report is complete, once the program has been run, without any need for any other processing/formatting. In a future blog I’ll provide a few more details as to how I did this as a) I think it’s interesting and b) I am sure that there are better ways of doing things and I’d like to get some ideas for developing the system further.
  • Writing files. An obvious thing I had to do when writing out latex files, was to learn out to write out files. As any Java programmer will know, this is very easy using the PrintWriter package.
  • Sorting arrays. I had a need to sort an array on one of the fields. In fact (see below), this involved sorting an array of class instantiations. This was probably the most difficult thing I did when developing my first Java project, and it took a while before it came together. But following a few examples from the web, and I had this working pretty quickly. It certainly seems easier than C++, which always seemed complicated and involved having to have friends of classes. I’m sure that there are easier ways in C++ but I never really got my head around it.
  • Classes and data. This is not really a Java thing and maybe I am totally wrong, but I quickly found that my data and member functions were making the class quite large, so I decided to have a class called (say) ‘Papers’ and another class called ‘PapersData’. The PapersData class simply holds all the data and the Papers class provides access to it, as well as providing all the other functionality. This leads to (at least in the way I do it) too many getters and setters, but it does separate the data/functions. But, the main reason I did this is because I wanted to hold different data types for my various objects and an ArrayList (or other array type objects) would not allow this. I am happy to be corrected but I was trying to recreate the struct (i.e. a class) type concept of C++. Anyhow, it seemed to work for what I wanted, but whether it would scale to larger projects is another matter.

The system I have ended up with, seems to work well. Whether it is scalable to larger projects remains to be seen, but it has certainly been a very good learning experience. I have doubts that if I was trying to learn C++, even with a good programmimg background, I would have progressed as fast as I have with Java.

No doubt, other people would pick up C++ faster than I would have done but, for me, Java is a lot easier to learn.

The other big bonus is the Eclipse IDE.  No doubt, I have only scratched the surface but the autocomplete (Ctrl/0) and the suggested error correction (Ctrl/1) are my new best friends!

So, as my first Java project, I think, has been a worth while exercise and I have learnt a great deal.

 

  

Videos on the basics of Java

Videos on the basics of Java

Whilst looking through youtube (see my previous posts – here and here – for why I am doing this), I have come across some very nice youtube videos on the basics of Java. A very nice series of videos by Jose Vidal starts from the the basics of Java:

Eclipse Java ‘Hello World’ Introduction Tutorial

)

… but moves quickly on to topics such as:

Javadoc

)

Constructors

)

Java Wrapper Classes

)

Java Immutable Classes

)

Java Packages

)

Java Arrays

)

Java Expanding Array

)

Java Selection Sort

)

Java Multidimensional Array

)

Java Inheritance Tutorial

)

Java Polymorphism

)

Java Reading a CSV file

)

Java Reading and Writing Binary Files

)

Java Serializable interface: Reading and writing Objects to a file

)

Java Arraylist

)

Java HashSet HashMap Demonstration

)

Java Generics Tutorial

)

Java Iterators

)

Java Building your own Iterator using Inner Classes

)

Eclipse Tips and Tricks for Beginners Tutorial

)

Java Set: HashSet TreeSet LinkedHashSet

)

Jose has many other videos in his collection and if you find the above useful you should check out his youtube channel.

 

Other useful videos

As I have said before, there are many (many, many) youtube videos out there that can help teach the basics of Java. They are too numerous to list, but here are just a few that I have either found helpful, or that I plan to watch later (and I might just keep adding to this list so that all the videos I found useful are kept in one place).

In no particular order.

Iterators Part 1 (Java)

)

I realise that many of the topics above are very basic for a seasoned programmer but I think that there is also some advanced material there as well (e.g. inheritance, polymorphism, iterators etc.), so hopefully it will be of interest to a wide variety of people.

I can certainly say (from my own persepctive) that to get your head around this in MFC/VS/C++ would certainly be a lot mor work (for me anyway).

The football prediction project

You can read more about this project by looking at the posts for this football prediction project.

  

Blackjack in Java

Whilst looking through youtube (see my previous posts – here and here – for why I am doing this), I came across a very nice resource that showed how to implement Blackjack in Java. I am sure the video’s presenter will be the first to admit that the project is far from complete (for example, there is no double down, no splitting etc.). But that is not the point of the exercise. It was to show how to develop a complete application rather than developing a complete Blackjack player in Java.

The video was very useful. It started from an empty project and added classes as they were needed (Card, Deck, Player) and showed how they all linked together.

To be honest, it did not teach me anything I did not know already about the language syntax (as it is very close to C++) but it was very good to see somebody build a complete application from scratch.

Blackjack in Java

If you want to watch the video, take a look at the video below.

Previous interest in blackjack

Blackjack in Java

Blackjack Table (Downloaded from Google, via Wikepedia Commons – labelled as free to reuse); URL: http://commons.wikimedia.org/wiki/File:Blackjack_board.JPG

I must admit to being a little biased towards this video, as I have published an academic paper on blackjack, which evolved a blackjack player so that it could play blackjack and win money. Of course, we could never use this in a casino (for many reasons!) but it was a fun project and it would be interesting to ressurect the project in Java – but that really is for another day. But I might go and see if I can find some open source classes for a deck of cards, then I could do my version of Blackjack in Java!

The football prediction project

You can read more about this project by looking at the posts for this football prediction project.

  

Learning Java, the first steps

In this post, I describe my first steps in learning Java. Not that I am a newbie to programming. I have been doing it for years, but mostly in C++, or various mainframe languages and editors. But I recently made the decisio to change to Java.

Learning Java

Learning Java

Java Programming. Downloaded from Googled, labelled as free to reuse, under Wikipedia Commons. URL: http://commons.wikimedia.org/wiki/File:Java_Programming_Cover.jpg

I thought it was about time to start learning Java. At the moment, I am based in Malaysia so I cannot simply reach to my bookshelves (in my office in Nottingham) and get one of the many Java books I have accumulated over the years. Of course, I could go to the University library (and may well do so) but at the moment, all I have is Google (other search engines are available!).

There are obviously lots of internet forums around, but these can be quite difficult to follow, can digress quite a lot and are often in the form of Q&As which might not be the best way to learn.

Youtube for Java

I often overlook Youtube, but as I found out in my previous post, there are some fantastic resources out there.

I was fortunate enough to come across a series of videos that introduce various topics. I was drawn to it as the first episode was called “Episode 1: Hello Java! Getting Started with Eclipse.”

I found this quite informative. I think you have to have some programming experience to keep up with it, and there is quite a lot of digressing – but I still found it a good watch.

In fact, I have watched the first 15 videos. Some are very useful, some not so. Tutorial 8 was not easy to follow (it’s about Networking). In my mind this was advanced stuff, but the presenter, I think, has a networking background so, I suspect, to him, it was pretty basic.

But overall, this series was worth watching, and I will watch some of the later episodes in the future.

Others are available

I was attracted to the videos above as it used Eclipse. But looking around Youtube, there are many (many, many) alternatives. Some are more advanced, some confusing, some too simple, some incorrect (or not well explained) – and that is from my limited knowledge.

Understandable?

I’m pleased to report that I understood most things. Of course, knowing C++ helps a lot, as the syntax is pretty similar. It’s also good that I don’t have to worry about whether I am using MFC (Microsoft Foundation Classes), whether, once I have console application, I could ever convert it to a Windows application, what to do when I get binding errors etc. As far as I can see, once you have your imports (for packages and calsses) sorted, then everything should be okay.

There also seem to be some nice features, such as ArrayLists, the Scanner class and the Collections object (which has sorting apparently – saves me having write a qsort and sort out friend functions etc.).

So ….

As far as learning Java, I think that I have found some excellent resources on Youtube and I would urge anybody learning Java to tap into this resource. Indeed, for many techical problems, Youtube seems a great resource.

Questions

Of course, I have questions. What is a call to super? What does implement do? How should I structure packages? How should I structure my classes and the GUI (it seems to me that it would be easy to write a console application and then plug on a GUI? – not something I’d want to try with Visual Studio).

But all these questions seem pretty easy to answer, with access to the right resource, but only time will tell.

The football prediction project

You can read more about this project by looking at the posts for this football prediction project.

  

Swing or SWT when using WindowBuilder

In my last post I was trying to decide whether to use Swing or SWT when using WindowBuilder. I am using the Eclipse IDE.

Learning to use Swing or SWT

The problem is, there does not seem to be any clear cut view as to which is best. This post on stackexchange is typical.

Researching the options

Most of the forums/tutorials I found on Google tended to jump in at the deep end, assuming that you know the basics and it was not very helpful in making this decision. Then I came across this youtube video.

The sound quality is not that good, but it takes you from how to install WindowBuilder, all the way to using Swing to create a window. I actually followed the tutorial in real time and managed to get the same results (a window with a text button in it), which I though was quite impressive.

The tutorial uses Swing, and I have since heard that Swing is better for Windows applications. Whether that is true or not, I don’t know, but as I have to make a decision, I have decided (for now anyway) to adopt Swing.

If I am honest, I don’t think it actually makes that much difference. The applications that I intend to write will be fairly simple from a GUI point of view, so I doubt that I would really push the limits of either Swing or SWT.

Decisions made

Swing or SWT for the Eclipse IDE?

Eclipse IDE (Dowsnloaded from Google, vis Creative Commons – 06 Mar 2014)

Whether, this is a good decision remains to be seen – but at least I am making some decisions. I have decided to use Eclipse, and now Swing.

I think that these represent two of the major decisions and even they are not reversible. I can always switch at a later date.

Probably of more importance now, is to actually write some Java code. Knowing C++ should make this relatively easy, but bolting everything together within a GUI might be the major challenge!

 

 

 

  

What Java GUI development tool shoud I use?

In my previous post, I outlined the reasons why I was switching to Java as the programming language of choice for a football prediction system that I am developing. In this post, I try to decide what Java GUI development tool I should use? Should I use Swing or SWT as my Java GUI builder?

Getting to grips with Java

Eclipse IDE (Dowsnloaded from Google, vis Creative Commons - 06 Mar 2014)

Eclipse IDE (Dowsnloaded from Google, vis Creative Commons – 06 Mar 2014)

I still need to get my head around Java. As I said before, I have done some Java programming but I’ll need to get a lot more skilled with the language. But, as one of the key reasons for switching to Java is to try and find an easier way (for me) to develop a graphical user interface, I thought that I ought to try and make that decision now.

WindowBuilder

Digging around, there are some tools that I could use. Eclipse WindowBuilder seems to get a decent write up, so I decided to use that. At the time of writing, I have installed this as part of my Eclipse installation. So far, so good.

Swing or SWT as the Java GUI helper?

Once I started digging a little deeper, I found that I had to make another decsion, whether to use Swing or SWT as my Java GUI builder. This does not seem so easy to answer. Searching for comparisons (this one is typical) tends to brings up pros and cons for each, with the conclusion that there is no right or wrong answer, in the same way that there is not clear cut answer whether you should use Eclipse, NetBeans or IntelliJ as your IDE.

So, at the moment, I am still none the wiser whether to use Swing or SWT. Unless anybody has any insights (please feel free to leave a comment)  I think I might have to try both. Probably eaiser said than done, as I am no where near the stage where I can get a Window to display on the screen, let alone decide the best tool to do it!

I’ll try to report more later.

  

Time to switch to Java for a football prediction project

Time to switch to Java for a football prediction project

Programming Books (Clive Darra, Creative Commons)

I have decided that it was time to switch to Java for a football prediction project that I have been planning for some time.

I want to do the project justice so I thought I would start from the most basic decision. What programming language should I use?

The Problem with C++

For the past 20 years, I have been using C++ (before that I was using all sorts of mainframe languages). I can do what I need to do with C++, but I have never been entirely happy with it.

As a language, I quite like it, but it is all the stuff that goes with it that has always been frustrating. And most of that stuff is around Visual Studio (VS), MFC (Microsoft Foundation Classes) and Templates. Don’t get me wrong, this is not a Microsoft bashing exercise. I know of many people who use VS and are very happy with it, develop great applications and know how to use the tools that are available.

But I have never really got my head around it. I run into all sorts of problems with namespaces, linking errors, deciding whether to use MFC (Micosoft Foundation Classes), or not – and then regretting it, whether to use the classes available in VS so that I could port my code to another compiler should I wish to do so; and the list goes on.

The end result is that I have never really developed as a C++ programmer. I can do all the usual stuff (classes, inheritance, operator overloading, polymorphism) but I have never been able to get to grips with Windows (Graphical User Interface – GUI) programming and so have always stuck with a Command Line Interface (CLI).

To be honest, using a CLI has served me well and I have managed to churn out some nice programs. But for my football prediction project, I really want to develop some sort of GUI. The question I asked is, should I have another go at getting to grips with MFC, Windows programming and all that is need to get an application developed in VS to display a Window on the screen, or do I change to something else, in the hope that I will find it a little easier to understand?

So why Java?

After a lot of soul searching, and Googling, I decided that it was time to switch to Java. I have written a couple of programs in Java before, but nothing too much beyond “Hello World”.

But is like C (syntax wise), and like C++ (class wise), it is well supported, many of my academic colleagues use it, it is platform independent and, I hope, that GUI programming is a little easier than VS.

More questions that answers

Of course, making the decision to use Java just raises a whole load more questions. What IDE should I use (I have chosen Eclipse), how big is the learning curve, can I easily access Excel files, can I (should I) use MySQL, what Java tools are available to support developing a a GUI etc.

All these questions will have to wait. For now, I have to learn the basics of Java and get my head around the Eclipse IDE (Intergrated Development Environment).

Wish me luck.

 

  

Knight’s Tour

Knight's Tour

Knight’s Tour (screen shot from Numberphile video)

If you are interested in Chess, you may have come across Knight’s Tour problem before.

Your task is to take a knight and place it anywhere on the chess board. Then, by performing legal Knight’s moves. can you visit each square on the chess board? Moreoever, you are only allowed to visit each square once (so 64 moves)?

If you end up at the final square, and it would be possible to move to your starting square with a legal Knight’s move, this is know as a close tour. Mathematicians would also recognise this as a Hamiltonian Path.

If you end up on a square where it is not possible to get to your starting position (via a legal Knight’s move) this is know as an open tour.

When you first see this problem, you tend to think that it would be impossible to find any tour, whether open or closed.

You might be surprised to learn that there are 26,534,728,821,064 closed tours. Yes, that’s right, 26 TRILLION of these tours. So if you tried it and could not find one, then shame on you :-).

How many open tours do you think there are? At the time of writing, nobody knows!

The video below does the job of exaplaining Knight’s Tours much better than I can, and it also includes some extra information about semi-magical squares.

I have a particular interest in this video and I had some discussions with Brady Haran (the producer of this series) as I have published a couple of papers on this topic (see here and here) , where we used ants to find Knight’s tours.