Matt Parker's "Share the Power" Puzzle

In response to Matt Parker's "Share the Power" puzzle video: https://www.youtube.com/watch?v=E5-pgBnGyzw

The problem is as follows: Sort integers 0 through 31 into two sets of 16 numbers so that each pile, when totalled, results in the same value. Not just for the base numbers, though. They also have to result in the same total if you power every number by 2, 3, and 4. (Watch the video, because Matt Parker's entertaining!)I like mathematics. So I watched this video, and decided I was going to solve it the best way possible: by making a program that randomly checks answers to the problem until it finds the correct solution. Because nothing I do makes sense.

Here is my program. It's made in GameMaker 7, because retro. Here's the entire code, found in one object:

Create event:

//Initialise a list holding values 0 through 31
global.Checklist=ds_list_create();
for(i=0; i<=31; i+=1) ds_list_add(global.Checklist,i);

//Initialise five "report" lists:
//0 = the string of numbers being tested on a given iteration;
//1-4 = the true or false status of the total of n to that power
for(i=0; i<=4; i+=1) {global.Testlist[i]=ds_list_create(); Found[i]=0;}
Iteration=0;

//Turns true if an answer is found
Ended=false;

Step event:

//Stop testing if we found the answer
if( Ended ) exit;

repeat( 200 ){Iteration+=1;

//Clears the top value of the reports when there's over 10 of them
if( ds_list_size(global.Testlist[1])>=10 ){for(j=0; j<=4; j+=1)

//Shuffle the values so we're trying a new one
ds_list_shuffle(global.Checklist);

//Report the actual values from group 1 that we're checking
var str; str="";for(i=0; i<=30; i+=2){str+=string(ds_list_find_value(global.Checklist,i));if( i<30 ) str+=", ";}ds_list_add(global.Testlist[0],str);

//Check the totals for each of n^1 to n^4
p[0]=true; p[1]=true; p[2]=true; p[3]=true; p[4]=true;

for(j=1; j<=4; j+=1) {var pile1; pile1=0; var pile2; pile2=0;for(i=0; i<=30; i+=2)if( pile1!=pile2 ) p[j]=false;

var str;str="FALSE";
if( p[j] ) {str="TRUE"; Found[j]+=1}ds_list_add(global.Testlist[j],str);}

//Terminate the checking next step if we've found the answer

if( p[1]==true && p[2]==true && p[3]==true && p[4]==true )

Draw event:

draw_set_font(font0);
draw_set_halign(fa_left);
draw_set_valign(fa_top);
draw_set_color(c_black);

//Draw the results
for(i=0; i<ds_list_size(global.Testlist[0]); i+=1){draw_text(20,10+(i*50),ds_list_find_value(global.Testlist[0],i));for(j=1; j<=4; j+=1)

draw_text(20+(120),10+(11*50) ,"Iteration")draw_text(20+(120),10+(11*50)+20,string(Iteration))

for(j=1; j<=4; j+=1)
{draw_text(20+((j-1)*120),10+(12*50) ,"n^"+string(j)+" Found")
draw_text(20+((j-1)*120),10+(12*50)+20,string(Found[j]))}

Untitled-25.fw.png

 And that's it! 200 times per step (should be 12,000 per second but it lags because it's compiled with an old GameMaker) it shuffles the numbers into two piles, checks each of n^1 through n^4, and if all four return true for a single set of numbers, bam! Winner!

Well, it would have been if I hadn't, impatiently waiting for my program to spit out the answer in mere minutes, I hadn't googled 32 factorial. If there is only one ordering of the numbers that results in a pass in all four categories and my program was doing one check per second, turns out I'd be sitting here for a few quadrillion millennia  waiting for my mythical answer.

So I altered the code a bit to up the count to 5,000 60 times per second (which is laggy, but y'know...), with it dropping that number if the FPS is too low (which it is).

And as I sit here writing this, the new program is on iteration 5,500,000. It has found a total of 83,000 combinations that work for n^1, but only 8 for n^4. And of course, none that work for all four.Optimisation time!

First, I made the code early-out if any of the tests fail. I then reversed the testing order, so n^4 goes first - since n^4 fails significantly more often, it means less redundant code is run.

And then I realised there was another nice optimisation I'd entirely ignored.If each of the two half-piles of numbers have to total the same, then the total of BOTH piles would be twice that. And since all of the numbers in both piles are set, I could work out this total! So I chucked Excel open and found that:

0^1 through 31^1 = 496;
0^2 through 31^2 = 10416;
0^3 through 31^3 = 246016;
0^4 through 31^4 = 6197520.

So for a valid solution, I only have to check one of the two piles for half of the above values (248, 5208, 123008, 3098760).

By now, the new program is checking over 100 iterations in the time it takes the original to check 1. I was figuring this might be my special way of solving a problem - turns out the profoundly lazy way is also the ridiculously lengthy way!

While it's running, I decide to rewatch the video just in case something lurches out at me. It's at this point I see this:In both of Matt's previous examples, for each eight numbers, the first, fourth, sixth and seventh go into pile one; the other four go into pile two.

Please don't let it be this easy.

I repeated the pattern... n^1 passed, n^2 passed... but n^3 and n^4 were slightly off.That was doing: unnuunnu (assuming in the screen caps above, the upper is "un" and the lower is "unnu"). uunnnnuu made n^3 pass as well, but n^4 still failed.

A real mathematician, at this point, would probably be laughing in my face. I should probably be working this out for real.

But then I found unnunuun.

And all the numbers aligned.

So Matt Parker, if you happen to be reading this,

Set 1: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30
Set 2: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31.

I didn't see the pattern you laid out in plain sight. And as a result, I made a piece of software. A piece of software that is both ridiculous and redundant. A piece of software that has gone through 47 million iterations checking random groups of numbers for a solution, and has yet to find a group that satisfies n^4 and n^3, let alone n^2 and n^1.Thank you.And damn you.

ADDENDUM!

I'm still looking at this trying to work out what's going on. I did notice one thing though:

unnunuun

The Us are in positions 0, 3, 5 and 6, and the Ns are in positions 1, 2, 4 and 7, in the final "pattern".

This is exactly the same as the alignment of numbers in the sets themselves. Which is pretty... FRACTAL

Maybe for 0-127 and n^1 to n^6, the answer is unnunuun, where every U is itself an unnunuun and every N is an nuununnu?

My brain hurts.

The Long Road Home Pt 3 & RekameMag Update

I'm typing this on an iPad, as a train takes me from Edinburgh to York. It's sixteen minutes late from Edinburgh - I have eight minutes between the original York arrival time and the York departure of the third of four trains which are to take me from Dundee to Redgrave, home. Bloody delays.

And yes, as much as being stranded in a city of bizarre accents for about an hour longer than I wanted is on my mind, I'm mainly thinking about how £10 for 24 hours of only-decent internet accent is shocking, and how using the iPad keyboard to type is like using a worn ball mouse to point and click. It fundamentally works, but it sucks.

But I'm happy! I'm going home, where parents, pets and friends reside, and morning wake ups and having to prepare my own meals don't. Where my bed is more comfortable (put a single, sharp spike on my Dundee flat's bed and it'd be an improvement) and my room is... well, more compact, so that doesn't count as a plus.

There's also events and places I'll get to go again. Car boot sales - got an original Game Boy and copy of Tetris for 50p at the last one I went to. Summer fetes, the nature reserve, Norwich... Er, ew.

It'll be a good couple of weeks though, definitely.

Other subject time! I'm slowly but surely working on a new issue of RekameMag (search it on GMC if you're interested, iPad's copy and pasting is diabolical). Got three articles and two reviews so far; Darrell "Dadio" Flood may be working on another article.

Anyways, to cut a long story short, I'm open to any and all decent Rekame-page-long articles and reviews to put into it. I figure having a variety of people doing content would be cooler than all just me jabbering on. Of course, I CAN do it all by myself, but yeah. Thought I'd quickly mention that since it may not be a huge amount of time until I throw it out.

If you are interested, comment here, email me or add me on MSN at nal(at)nalgames(dot)com, or add my Skype account, nal-games. As long as the quality is decent enough I'll slap it right in.

Last topic is naturally game making. I've not done anything for over two months, mainly because Innoquous 4 destroyed me. Though it's not done quite as well as I'd hoped, it's respectable enough, and those that played it did enjoy it. It second placed in one of the last Bytejacker Free Indie Rapid Fires, sandwiching itself between two excellent-looking games.

I'd rather like to enter the GMC Jam, but that comes entirely down to self-motivation and whether I'll have time, given it's over two of the first three days I'm home. If that doesn't happen, I'm sure I'll be able to conjure up some sort of quick inspiration burst at some point in the near future. I don't like game making droughts!

Anyway, that's all for the day. I'm either going to enjoy the countryside or watch a filthy comedy film now. Guess which one.

Ripoffs

If there's one thing that irks me about gaming, it's the sheer number of ripoffs of other games that exist. I'm not talking about games that are similar to one another (eg any FPS and Doom/Wolfenstein 3D), games that take popular (or even unpopular) games, change a few things then slap it out to the public and smile.

The source of inspiration for this is an iOS game I bought out of intrigue a month or two ago and have only just gotten round to playing, the uncatchily titled Pirates vs Ninjas vs Zombies vs Pandas. Yeah. It was 59p and I was interested to see what sort of odd game that title could hold. To my deep disappointment, it's basically Angry Birds. The premise is that for each level set (near-identical to the sets you get in Angry Birds) you're one of the four different titular groups, taking on another one. Essentially, each one has its own little traits (like the different birds in AB), and the enemy sits stationary (like the pigs) in a physics-affected castle (guess), waiting for you to be slingshotted/slungshot/whatever at them. Every mechanic is the same, down to the bonuses for unused "ammo" characters and for the number of blocks you break/damage.

The worst thing about the game is that for quite a while it was sitting very, very high in the iOS charts - above Angry Birds itself at one point. These guys were profiting quite heavily off someone else's concept. This sickens me - it's not quite as bad as just selling the game with ripped sprites, but it's damn close.

I don't get the mentality behind it at all. I struggle to imagine the concept meetings the PvNvZvP team members had.

"Let's think of a great new game!"
"We could rip off Angry Birds to get lots of money!"
"Well gee whizz, you're fantastic!"

I guess from that perspective it pretty much worked. But that brings me onto ripping off within free, independent development. There's no monetary gain to be had from this, so anyone that's a part of it is in it for two things - the fun, and positive reception.

Now, where along the line of thinking is it even remotely plausible that stealing somebody's ideas for your own use will garner positive reception? 95% of the time, the person you stole from will be well-known in the development community. Within ten plays someone will have recognised what you've done, and you'll start eating the backlash. From there you can either apologise and either credit the original developer or take the game down, or you can deny it's a ripoff, shoot your reputation in the foot (which you'll have done anyway, but this makes it oh so much worse) and never get it back, or at least not for a long time and a lot of making up for it. Both the fun and the positive reception die during any of those routes.

Note that this doesn't include fangames, where you are showing your appreciation for the original game (though this is still pretty unimaginative when you could show your appreciation by referring people, then put your skills to better use), and instances where you take the idea, turn it into something of your own accord, then credit the original developer (much better, as it shows initiative and appreciation in one).

It's a mentality I will never understand, and thankfully have never had in the past myself, though I've definitely been inspired by people before - see Ne Touchez Pas and FKR, inspired by Mark Essen's "Flywrench" and Cactus' "xWUNG" respectively, but I've always given credit where credit is due and have had a reason to create both (simplification of a complicated concept, and a different take on a similar concept respectively).

Nintendo 3DS still rocks, by the way. But the games are currently a bit shit - mine serves as a Pokémon Black upscaler at the moment! If you also own a 3DS and would like my Mii gurning on it, then scan my current YYG avatar with Mii Maker's QR Code scanner. (Apologies to readers in the future that are interested in this after the next YYG avatar change, whenever that inevitably happens!)

Dundonian Relocation

Any YoYo Games users reading this will have more than likely read the website's latest glog entry, on a job offering to work within Game Maker at the YYG Office in Dundee full time. I know for some of you, it's a very tempting offer - a full time wage to use Game Maker! I also know that for most of the tempted ones, the "big thing" that's holding you back is the need to relocate to Dundee, Scotland.

This is a blog entry to try and convey exactly what I went through, and still do, having done that relocation from a quiet village in eastern England to the city centre of a Scottish city. It will be a little similar to a previous glog entry, I Would Drive 500 Miles (Nearly), though that was written just six days after I arrived and five after I'd started work. I've now been here nearly seven months.

I won't lie, the relocation is hard. If you're close to your parents (I am) and your relatives, friends and pets (again, yes), it's a little difficult at first. But MSN, Skype, or even just your everyday telephone alleviates that quite significantly. There's also the travelling to Dundee with your belongings - by train works if you don't have to bring too much, though without the car space of my dad's Ford Mondeo I would've had to shed 90% of what I did end up bringing. If you're not within Great Britain you'll probably have to factor in a plane too. These aren't hugely expensive; a return train ticket this Christmas from Dundee to my home village (450 miles each way), bought two weeks in advance, cost me £100 (about $150 or €150, I'd guess. Don't quote me on that). This was without any special discounts, just the fact I bought in advance. Plenty of websites will let you gauge the fares of whichever method of transport you think you'd end up taking.

Dundee itself is a very nice city. It's far from a massive metropolis, but it has everything you need. There's about six different Tesco supermarkets, including a nice large one by the River Tay and a Tesco Metro (the store I use weekly) within the city centre, essentially a half-sized Tesco which has everything you need to live off, just a bit less of it. There are three malls in the city centre with everything from clothes shops to Argos (for those unfamiliar, it's like Amazon.com but a shop of it) to Starbucks. They vary in "quality", with the Overgate being predominantly full of well-known brands while The Forum (I think that's its name) seems to be more leaning towards independently owned shops. Both have a Gregg's bakery. For pubs, Japanese supermarkets and pretty much any mainstream chain you can think of that operates in Britain, Dundee is more than adequate.

On the entertainment side of things, I haven't done much research, but there's a large, swanky Odeon cinema and Dundee Megabowl, with its 36 or so bowling alleys, pool tables, arcade area and a little Wimpy's segment so you can stay in the place for several hours and let the fast food bit cover a meal. Both of those are a couple of miles away from the city centre, but it's only around £10 both ways for a taxi. If you're a fan of sightseeing, Dundee is great. There are a number of points of interest (it's the "City of Discovery", y'know!) including the permanently anchored RRS Discovery ship and the McManus Gallery, which includes some DMA Design-related tidbits from Russell and Mike (including a collection of Mike's old business cards!).

Weather is a common complaint, and is fairly understandable. Being up north, and part of the UK in the first place, it can be pretty cold. It doesn't rain a huge amount though - certainly no more than England. There was some very heavy and disruptive snowfall this year, which also caused one instance of the rare but cool thundersnow, and at least one day when every road was like a giant footpath. I've been told by Russell that it's the worst case of snow Dundee has seen in decades; it isn't regularly snow-coated here. But generally, if you own a coat (hypocritical of me, I know, given I don't!) and you didn't live in a permanent sauna before, you'll be fine.

Last part I should probably get to mentioning, and probably the most important too, is the job itself. The next thing I'm going to say, I have to reiterate is 100% my own words. I've not been told to say this, I'm not lying, and I'm not doing anyone any favours. I absolutely love the job. I'm getting paid a very liveable salary to do what I spent seven and a half years of my life prior to starting doing for nothing. When help is needed with something I have some very experienced and very friendly people all around willing to give it. It is just an amazing atmosphere. Casual, but not jokey. Productive, but not overly-serious and not strenuous.Yes, the distance from home is a bit of a kick in the balls. Yes, I miss my daft cats, and my little bedroom in the little quiet English village. But can I go back for a visit whenever I want? Yes. Is it a great city I'm in with plenty of convenience and friendly citizens? Yes.

And do I love my job? F**k yes.

Falsettoing like Matthew Bellamy

So yesterday I went to a friend's house for a few hours, after my weekly shop shift (which, pleasingly, I have a week off of next week, meaning I only have to do one more until I hit 19). We fit in some gaming. He played a couple of my creations - madnessMADNESSmadness and Confusion Readily Achieved Perspectively Through Unrealistic Relative Dimensions. That's beside the point though. As well as quick goes on Fallout 3 (my game, but he's borrowing it at the moment and loving it) and WipEout HD Fury (also my game, got it on disc and took it over) we had a go on Guitar Hero 5. He has the entire kit.

So, with him on the guitar, I had a choice between drums and singing (I'm awful with the guitar so I couldn't do bass). And, despite every inch of me thinking it'd be more humanly kind not to, but with encouragement from him as the drums are a pain in the arse to set up and require makeshift drum sticks... I sang. To mixed in-game results.

We started off with Michael Jackson's "Beat It". I annoyed Matt with a joke about how he's probably not beating it any more, then the song started. We BOTH blew it and lost about halfway through, though I was seeming to hit some of the screechy chorusy bits.

We did several other songs. My worst result came from Johnny Cash's "Ring of Fire" - I couldn't physically hit the lowest note sung in it, and if I went an octave higher I kept missing all the highest ones! A couple other songs basically proved to me that I'm a lot better when I know the lyrics off by heart. His fairly small TV makes lyrics difficult to read, especially as they're streaming across like lightning and split up into syllables. I was also generally worse at verses than I was at choruses, possibly also due to the unfamiliarity (pretty much everyone can do the chorus of Thin Lizzy's "Jailbreak", but all the verses are all over the place).

My best result? For Muse - Plug In Baby. For anyone that knows Muse, you'll know that the lead singer, Matthew Bellamy, frequently implements falsetto (really, really high) vocals into the band's songs. Plug In Baby features this. Thanks to my dumb voice, I hit the falsetto part NEARLY perfectly. I cocked it up with the final huge word, in which I began coughing uncontrollably. After the song I retained a headache for the remainder of the night, and my resulting sore throat continues to bug me right now, despite the medicine I took a few hours ago. I got 98% overall on Plug In Baby, by the way. I didn't drop below 60% in any song we played (we did about ten-fifteen), and only went below 70% in one - the first one.

But it was fun. I'm feeling the after-effects, and I'm sure Matt regrets ever letting me get my mits on that microphone. It was nothing short of fun though. I'm sure if I go over there again sometime we'll play it again.

I think my singing career is done for now, however.