Android A-go-go

Been a while since I last posted, but the tinkering continues. As we're now offering Computing as a GCSE, we get to teach cool stuff like mobile app development.

The first thing we did today was a simple "virtual pet" app, which is basically the tutorial for creating Android apps using MIT App Inventor. If you fancy doing some beginners' apps, that's not a bad place to start. We also started on a Whack-A-Mole type game, which introduces graphical sprites and timers. It's a simple game, but quite fun to make. I'm not sure how advanced you can get with App Inventor, but some of the demos on the site look very interesting.

We also had the first meeting of what looks destined to be named "Code Club", where kids get together  at lunchtime each week and make cool things. First they're trying to decide what to make (web-based app or mobile "thing"), then I'll try to help them make it a reality. I can't wait, even if it means I have to learn Java.

How much have the Olympics cost you?

Quick one today. A bit of maths and some tinkering around with Flash movieclips have produced this:



It is designed to run from the start of the Olympic opening ceremony until the end of the games, and works out how much it has cost the individual taxpayer so far. Grumpy? Undoubtedly. Accurate? Probably not.

Creating Harmony

Last week I did some work on a new project, which came about from a conversation in the staff room. At school, we have a system where pupils stay with the same group of peers for three years. In years 7,8 and 9, the form doesn't change (although the form tutor does).

When they reach year 10, we muddle the forms up and re-assign pupils. Not sure why, we just do. Maybe it's because we change from five forms to six, so we need to redistribute the pupils. However, because we're nice, we don't just assign people to form randomly. We allow them to influence the procedure. Having said that, it might be fun to do it by drawing coloured balls from a big sack. Or maybe we could let a magic hat decide.

Anyway, pupils get to choose up to four people who they would like to be placed with. They also get to choose one person who they would rather NOT be placed with. The challenge is to place 100+ pupils into 6 forms, keeping the most people happy and making sure everyone has at least one preferred classmate.
It takes a teacher about 4 hours to do this job. It's a bit like filling in a sudoku. Just when you have one thing right, you realise that you have created a new problem. Sounds like a job for a computer!

I decided to see if a computer could do it more quickly. As with all computing tasks, the first part is to think about some general rules. I decided on the following:

We would measure how successful an arrangement is by giving it a score. If a person is in the same class as their chosen pupils, the arrangement scores one point per match. If they are in the same class as someone they have chosen to avoid, the arrangement loses two points. Using this scoring system, we can measure any given arrangement and compare it to see if it is better than a different arrangement. We can also grade it against the "perfect" score, which is where every person has everyone they requested. At this stage, I had no idea how easy it would be to find this perfect score, or if it is even possible.

I then started thinking about how to go about testing different arrangements. Computers are fast, so it might be possible to do a "brute force" method and test every possible combination. However, the numbers get very big very quickly. The first person has a choice of 6 forms, so does the next, and the next, leading to a possible 6^100 combinations. This is not feasible to compute in a reasonable time.
So a completely dumb loop through every combination would take too long. I needed a smarter method of testing candidate arrangements. I decided on the following algorithm:

1. Take a random pupil.
2. Look at each form and test to see how "harmonious" it would be with the new pupil (scored as previously described). If there's an obvious best choice, put them in there so long as it is not full (each form has a maximum number of pupils).
3. If there is more than one best choice, or the best choice is full, choose again based on class size. Put them in the smallest form.
4. Take another random pupil and repeat until all the pupils have been assigned.
5. Once all pupils have a form, assess the "harmony score" of the whole year group.
6. If it's better than any arrangement we have seen so far, keep a record of the form arrangements.
7. Wipe all the forms and repeat until we have either found a perfect arrangement or we give up

After I programmed it, I set it loose on the real data from last year's options. I entered all the names and the options for the actual Year 9 group and started off running the program for 1,000 attempts. On each attempt, it picked pupils at random, so there was an equally good chance of hitting a workable combination at any time. It didn't find a perfect arrangement, though. It couldn't even find an arrangement where everyone had at least one preferred classmate. I tried it again for 10,000 loops with no luck. I even set it going for 100,000 loops, and it couldn't find a perfect outcome. It was close, though. In just a few minutes, the program had managed to find a solution where all but three pupils were happy, and many of them were very happy indeed because they had all their preferred classmates. I worked out that a human could look at the solution and do some manual shuffling so that the last 3 people were happy. At the least, it would shave a significant amount of time off the 4 hours the job had previously taken.

Then I ran the program again, and it found a great solution almost straight away. And the next time, it did it again! Because it's picking randomly, it could find a solution quickly, or it could take a while. I'm sure there's a more efficient way of doing the job, but for the moment it looks like the program can definitely make a contribution here. It just needs tidying up and a decent interface so that pupils can enter their preference directly. I've even thought of a name: Harmoniza.

WGHS Rooms App Early stage

Some progress on my little app for booking rooms at school. It has a login screen and currently returns a list of upcoming room bookings...

...which is just a specially formatted web page.

Oh, and it has an icon.

Yeah, it's not going to be out-selling Angry Birds, but the important thing is to learn how it's done!

Fixing the logins and playing with app development

Well, it seems that I made a bit of a mistake when I set up the login cookie system on my Rooms Booking site. Whenever you switched computers and tried to log in, it was creating a strange limbo state where you were logged in, but couldn't do anything. Confusing. Anyway, I think it's fixed now. If you move computers, you will have to log in again. Solved.

I have also been working on an Android app to access the database. I'm not sure if anyone would use it, but really it's just an exercise for me to learn how to create a data-linked app. Screen-shots will appear as they happen.

Playing with logins

This weekend I have been experimenting with Google's login methods, so you can log my web sites using your existing Google username and password. I have it working, but I'm not sure whether it's worth implementing right now. At the moment you don't actually have the option to create an account for the Music Database or Room Booking database. I have to create them for you. It might be nice to have an account creation option, and using Google login (or Facebook Login, which seems to work the same) would be a quick way of doing it.

I have also tinkered with the fishing game, adding a second type of fish (clownfish), but I seem to have caused more problems than I solved. I think my code needs to be optimised, because it started slowing down when I started animating the new fish. Still need to learn more about sprites and the best way to animate them.

Shop's open

The fishing game will have a shop where you can upgrade your gear (better boat, better harpoon, better gun etc). So today I did a quick animation which appears at the end of each level. To test it, I have put it at the start of the game. Also, in this version you'll see the harpoon which doesn't return as soon as it grabs a fish. This harpoon will let you get several fish in one shot!

Updated source code (wave12.py)