## Tuesday, November 17, 2015

### JSano19 trolls my levels

So I sent youtuber JSano19, who keeps solving one-screen puzzles my one-screen puzzles. Even though some of them are pretty bad or rely on some obscure Mario World "Features". But it has been fun, plus the videos have quite a bit of views.

First he played Pow It and Living Fire, and he found the intended solutions.

It was going all right until then he tried "Often Overlooked" and "A P-redicament". I talked about "Often Overlooked" in the Beach Koopa Saga post, and he did it mostly as expected, using the pipe to clone the koopas. However, there's a part where you are supposed to use the red shell to jump to the top (Either with a shell jump, or, much easier, by spin jumping on the shell to get height). But what he did was much more clever and... I am pretty sure it's a glitch.

This is so strange and ... changes everything. It's not really a big deal in this level as the spin jump was far simpler, but I wonder how this can affect some other puzzles out there.

This inspired me to make a whole new puzzle. It requires this trick and also some extra knowledge from the Beach Koopa Saga... : BA1E-0000-00EF-245D - Grow your Koopa.

Then he tried "A P-redicament", I never explained how to solve it, but the solution is definitely not to jump from the starting point to the exit -.-

So of course this means I had to update the level to remove that unintended solution. I don't want to exterminate ALL possible unintended solutions. The existence of some of them can improve a level rather than take away from it. And a puzzle with many different solution routes is nice. But when the solution removes the focus away from what I intend, and instead turns the level into a "do this precise jump" instead of a puzzle, I have to fix it.

Spoilers:
• Really all this level is about a small mechanic: Shells that Mario kicks or throws can collect coints for him.
• The contradiction is that you need to walk on some of the lower row of that bunch of blocks in the middle. So you need some of them to be solid. You also need to some how destroy the upper row. A P is not that help here, because you'd fall.
• Hints: All the coins are hints, I want to show the player that you can grab a coin while on the row above it, if it is just 1 grid square left/right and 1 grid square lower. All you need to do is move slightly left/right to be on top of the coin without falling and it gets it. The other 16 coins are there so hopefully playing with the red Koopa while figuring things out shows you that the shell can grab coins for you.
• Diversion: The koopa is initially needed to destroy those two blocks on top, but you need to keep it for later.
• Implementation: Carefully use the koopa to destroy the wall on the top, make sure to keep the shell somehow. Go towards the thomp, which will activate the P switch. Grab the top-left coin of the bunch of blocks/coins blocking the path. Wait for P switch to end and now put the shell in that new missing corner and kick the shell. This will get rid of the top row of blocks. For the rest, you need to go towards the Thomp (The shell needs to keep bouncing while on top of the blocks as you do this) and time it so that the shell will create the proper path for you.

## Saturday, November 14, 2015

### The Beach Koopa Saga.

These are four one-screen puzzles that shouldn't exist. But do. I think they make interesting puzzles, but the mechanics they rely on might be too obscure.

• Double Jump: 379C-0000-00A1-8BF7
• Often Overlooked: 2B4B-0000-00E9-D056
• Koopa Alchemy:  FA8A-0000-00EA-8A07
• Cloning and Color: D3DA-0000-00E7-F31B
I recommend attempting to solve them in order. This is the place to come to in case you are really curious about how to solve them. If you want to read more about one-screen puzzles (actually puzzle levels in general) I have a whole post about them and I am kinda explaining the levels in this post using that framework I explained there. The following paragraphs contain spoilers. If you needed to read spoilers for one puzzle, try to still solve the later puzzle(s) on your own. It might be fun/frustrating, I hope.

### Double Jump

This one is the easiest puzzle I could come up to that makes use of the mechanic I wanted to highlight here.

Contradiction: You need to stomp on the Koopa to climb to the top so you can then get to the right. But then you will find yourself unable to jump to the exit. So I guess you could instead take the Koopa's shell with you, but you can't take the shell with you because you need to jump.

It seems that experienced players fall into thinking that they need to use a shell jump glitch  to solve this level, but I intended something far simpler.

Mechanic: The mechanic tying all these puzzles together is that in Super Mario World, stomping on a koopa makes the Koopa leave their shell. It looks like those shell-less koopas are called "Beach Koopa".

Implementation: In this situation you need to take advantage of the poor beach Koopa. Stomp on the Koopa to make them leave the shell. But to make it so it's hard to do this accidentally, I made it so it is kind of unlikely the beach koopa will drop in the right location unless you do it intentionally. Wait for the Koopa to stand up and then grab the shell and stomp on the Koopa again so you can reach the top holding the Shell. The last jump might be tricky to some people. The easiest way is to drop the shell and spin jump on it. I guess you can also kick the shell and stomp on it at the right moment, but that's a life-threatening stunt.

### Often Overlooked

Hehe, I didn't notice that I took the screenshot with the comments on.

Contradiction: Like in the previous level, you can use the often overlooked Beach Koopa and the shell separately. First you use a similar trick to be able to grab the P switch (you need to kick the shell towards the yellow block below the P-switch). You will also need the trick to reach the top. Once you reach the right side you will find yourself on a strange situation. You need to press the P switches spawned by the pipe 3 times, but even if you are lucky and a Beach koopa is available to climb, you can only do it one time. What's up with that?

Hint / Diversion: The first p switch exists really as a distraction. Or maybe so that it's necessary to know that you can stomp on Beach Koopas before continuing. At the top there is a yellow block next to a coin. It's there to explain that to go through this you need to press the P switch and then wait until its music ends. Also this time it is easy and likely that a red Beach Koopa will fall towards the saws' area so that you hopefully can see that you can use this koopa to make the jump towards the yellow blocks.

Mechanic: This is where the saga turns obscure. The trick in this level is how SMW red koopas work when put inside pipes. Generally, the red koopa won't respawn unless they leave the screen or get killed. In SMW's case, what matters for the respawn condition is just the shell. As long as the shell leaves the screen, the red koopa respawns. Even if the Beach Koopa is still available. So by stomping on the red koopas and throwing the shell outside but leaving the beach koopa alive, you can make the tube create an indefinite number of beach koopas.

Implementation: Stomp on the red koopa in such a way that the Beach Koopa is thrown to the saws area. Clone the koopas and Do this 3 or 4 times. Having 3 koopas might be a bit risky because a mistake while using the P switches will force you to restart. Having 5 or more beach koopas is risky because it might be too crowded and they can still kill you.

Update: I fixed an unwanted alternate solution (cheese), it's possible to jump on a P switch in mid-air. So I had to change it so it is not possible (I hope) to move the pipe-create P-switches at all. Also added a reset door and some other minor changes.

### Koopa Alchemy

If you thought the last one required too much an obscure knowledge to work, that's because you didn't see this one yet. This level is terrible!

Also this level really had so much cheese possibilities, there's a reason it's in version 3 four right now. I really hope it doesn't have more ways to cheese it without using the intended mechanic, but I can't make guarantees. Maybe you can find more ways.

Examples of cheese in previous versions:
• There used to be a giant goomba in a more open space instead of that wiggler. It was possible to kill it with a shell without losing the shell.
• Spin jumping on the Thomps. That's the reason the space is so tight now. Update: In fact, this was still possible, had to make a whole new version. I hope those munchers stop the cheese once and for all!
• Walking on top of the thomps. In the past, to make the implementation easier, there was a semi-solid platform in the thomp area. Bad idea.
• Grabbing the P switch. The wall between the start location and the P switch didn't exist, even though the P switch was lower, it was possible to grab it, somehow.
• Killing the thomps with a pow when they 'touch' the ground. The wings in thomps are intended so that you need to throw the pows directly at them to kill them, but when there's not a lot of space for the pows and they touch the ground (even though they are still flying) they can be killed remotely with the pow.

Contradiction: You need the Pows and the only way to acquire them is (I hope) by pressing the P switch. In order to do it you forcefully (I hope) lose the two shells, one is needed to kill the wiggler and there should be no way to do it without losing a shell. The other is needed to make the Bill blaster drop on the P-switch. So in order to take the Pows to the Thomps , you will need to stomp on the beach koopas. But unfortunately, one of the beach koopas is red, so they won't drop to the ground. And you need (I hope) to stomp on two beach koopas to be able to take the two pows with you.

The Mechanic: So what we need is two green beach koopas, but we only have a green one and a red one. Just change the red one's color! Stomp on the two koopas and make it so the red beach koopa enters the green shell. This turns the koopa's shoes green! Really.

Implementation: You need to be careful in stomping the koopas to change their color, it's too easy to kill something you don't want to kill.

### Cloning and Color

This one is really the combination of the two last ones. You'll need to combine both techniques to cross that spike area.

Contradiction: The only way (I hope) to cross above those spikes and reach the axe is by leaving the area with green beach koopas. But there's only one of them and in a completely wrong location.

Mechanic: Just clone some six or so red beach koopas and use the green shell to turn them green.

Implementation: Easier said than done, a bad stomp might make you lose the green shell, or kill all the green beach koopa you've been creating. But I was nice this time and added a door that allows you to reset the whole deal without losing a life. I should really try to use these doors more often in one-screen puzzles. An issue is that they might have unintended consequences. For example, a previous version of "Koopa Alchemy" had a reset door, but it was possible to exploit it to change the position of a pow block and then you can use the green koopa to get the other pow block.

-------------
I hope these were fun.

## Tuesday, November 03, 2015

### The Incredible Rotation Warp - Version 7, I mean 8

I just recently wrote a whole post about version 6 of this rotation idea. I was hoping not to need to update it in a while. But today I got an idea and an urge to implement it.

Id: A270-0000-00D5-F33D

Basically, you now start the game on the (previously-inexistent) "right" area. This right area becomes inaccessible once you use the first pipe. There are many advantages about this, in theory:

• This way I don't need that extra entry pipe in the rotation room. I noticed that people kept getting confused trying to enter it. With only 3 pipes in this area it is hopefully less confusing.
• Getting to see this (right) area shall help figuring out that the map rotates quicker.
• This also works as a good excuse to include some fire flower powerups in (left) and (down) areas.
• I also changed the name back to "The Incredible Rotation Warp".

I worry that some things like having 3 enemies in the rotation room again would make the level too complex. Let more updates come. Iterative Game Development is going to be the end of me.

Update: And.. an eight one. Just some small tweaks, making it easier to move the spring across. Removed some elements that made the camera scroll up in the final section after flying. Aesthetic tweaks too.

## Sunday, November 01, 2015

### A Spinning World

id: A270-0000-00D5-F33D

Update: Further updates in new post: Versions 7, 8

A month ago I had what I thought was a cool, original idea. There were already many levels based around flipping the screen vertically / horizontally. Really "all" you need to do is make a warp zone that's identical to the main zone but with everything flipped. The next logical step was think of rotation instead of just flipping.  With there being four different versions of the same world, each being equal to the previous one rotated 90 degrees right. How was I going to implement it? My idea was quite clear:

So I just needed two things, the room with that pipe that rotates everything and the room with the puzzle. In reality I would need to make 4 versions of each room. The first step was to see if the rotating room is possible at all. You see, let's name the rooms for each diection A (up), B (right), C (left) and D (down). I wanted the same pipe to take you from A to B, from B to C, from C to D and from D to A.

You can place pipes on top of other pipes, even warp pipes. This seems to be an intentional move by nintendo because with this it is easy to make a situation in which entering any of two (or more) pipes takes you to the same exit pipe. Thanks to a reddit thread I found out that it works in reverse as well: If you enter a pipe that has multiple entry points, it will always pick one of them. Priority depends on the order the pipes were placed in the map. Latter tubes have more priority. So I was just adding pipes trying to keep the correct priority going and correcting when it's wrong. After half an hour, it started to seem impossible. Because it is impossible.

We have four pipes: A-B, B-C, C-D and D-A, we want B-C to have a larger priority than A-B, C-D a larger priority than B-C, D-A larger than C-D and A-B larger than D-A. This is an impossible cycle. Sorry.

The only way to fix it was to remove the cycle somehow, but I didn't want to change the original idea of having a single tube to rotate it all. Then I had a an idea: There's a room in which the pipe would appear top. We can make it so high that you cannot jump through any normal means, and need a spring. So add a whole new pipe that can only be used in the (up) room and takes you to a room that it includes a spring. When you exit this spring room, you are actually taken to a different (but identical-looking) version of (up): (up').

So now there is an up area A, and another up area A', an spring area called E. We have pipes like A'-B, B-C, C-D, D-A, A-E, A'-E, and there's no cycle. There's a bit of a problem and it is that now there's a whole new room to complicate the original idea, and worse, you need to go through it every time you want to change the gravity direction once you are top.

Another issue is that this would make me run out of warp pipes quite quickly. Remember I need one from start to rotation room and 4 pipes between rotation room and puzzle room, on top of all those pipes mentioned above. The warp pipe limit is 10. I fixed this by making it so the puzzle room can't be accessed when the world direction is right.  Also the exit would have to be directly connected to the puzzle room.

But at least the rotation was working, I was truly excited and proceeded to think of the puzzle. It would have three version: Up, Down and Left. It makes sense that Left is the one that takes you to the exit.

Spoilers (Although this is an old version, the new version has a different puzzle area but the idea is roughly the same).

• The "left" area is connected to the exit but you need a Rakoon Suit to fly that large gap.
• This quite works well because if we rotate this, then the exit would be unreachable or be part of a deadly free fall.
• The four question blocks contain raccoon leaves, the only way to get them is jumping against them. This needs you to use a P to turn the coins into blocks and to be able to stand on them. This means that to get the raccoon leaf, you need the direction to be (up) and an active P switch.
• The only way (I thought) to activate the P switch is when the direction is (down), so you have to activate the switch and then go to the rotating room until you reach the (up) direction. Since this (unfortunately) requires the spring room and it would take too much time, this is the reason the spring room has a P switch that you can only active when you enter it while another P is active.
I was quite proud of this, so I published it. I tried to get some plays going, the first versions had too low success rates and many crosses in the rotating area, so I reduced the number of enemies. These are screenshots of the fourth edition, things like there being 4 question blocks instead of just one came from attempts to make the level more friendly.

I published it to /r/MarioMaker.  I tried to get streamers to play it. I passed it around a bit. I thought this idea was very original and that people would love it. The results, however, were ... underwhelming.

#### More Work

To be fair, 11 stars is not that bad. Most of my levels stay in one-digit star amounts. But as the time passed I found multiple people who implemented the rotation idea in more successful ways: Like /u/saintlantis and /u/GamingfulLuke . Their levels got like hundreds of stars. I can only dream of ever making such a good level. But what I take from all of this is that this old "Rotation Warp" idea needed more work. In Level design, it's not enough to have a nice idea and know how to implement it.

Where to start in updating this level? By coincidence I saw the same streamers (supertwou) play both my level and saintlantis'. The biggest impression I could get was that it was far easier to tell that their level is about rotation. It helps that the rotation does not only happen in a small room, it's clearer that all of the map rotates. I cannot really change the idea of the level too much (Or I would be making a whole new level instead of modifying it), I still need to keep a single room for rotation. But I can still improve the situation a bit.

This is the new rotation room. I hope the extra asymmetry can help.

I also further reduced the number of enemies, only two of them now. Let the difficulty come from noticing that the thing rotates.

I am willing to bet the spring room is one of the reasons the previous version was too confusing. We need the spring room to exist, but I reduced the number of times you need to go to it. I moved the spring room to the (right) room. This way the only reason to use the spring is to use the rotation pipe, as there is no puzzle area in the right room, you don't need the spring to get to any of the puzzle areas.

Another very subtle thing is that the arrows in the rotation room pointed to the opposite direction than their respective puzzle rooms. I fixed this :)

I changed the special effect that plays whenever you use the rotation pipe. I used to use the telephone effect, but it shows graphics in random places of the string. Instead the Car Horn effect shows a flower circle in the pipe.

I also made plenty of changes to the puzzle area:

I added an arrow right next to the pipe. This should help notice that direction is important. The actual puzzle area looks very different too. Spoiler: I don't want to spoil things too much but here are some details:
•  Having the additional P switch in the spring room was giving too much importance to that room, which should really be just an additional step in changing one of the directions. So now you need to activate the P (without taking it out of the puzzle area) rotate the map correctly and go back to the puzzle area before the P activation runs out.
• So there are only two ways to activate the P, you cannot activate the P in the (up) version because it can't be reached. You can activate the P in the (left) version, but you get stuck (a plant will rescue you, but the plant only activates AFTER the P runs out). So you need to activate the P in the (down) room.
• There are many reasons I changed the rows of coins into that device. The first is that coins were just confusing, people would think that they have to eat them and could fall down. Also, if you eat them, why would they come back when rotating the level? Keeping coins and blocks inside an isolated area helps against this confusion. It should be both clearer and more interesting to see how gravity direction affects the shell device. (I hope).
• There is also a bit of a safeguard in case you decide to leap of faith in the (down) version of the room. An extra chance to retract and go back to safety (that question mark spawns a vine).

Thanks for reading (I'd be really surprised if anyone actually found this interesting). I hope the new version works out!

## Thursday, October 29, 2015

### The Time Caverns

This has become one of my favorite among my Mario Maker levels. Mostly because it's very challenging but I hope not in an unfair way:

The id of the current version is BC99-0000-00C8-7E48. I posted the first version in /r/MarioMaker and it was decently received. But it was much harder than I intended, with only one person beating it after 24 attempts. I don't want to make levels super hard because those do badly in 100 Mario Challenge and I have very little chances for exposure.

What's interesting about this level besides of the tough enemy combinations is that it has a special system. There are 3 occasions in which at the end of an area there is a P switch, and depending of how long it took you to reach the P switch from the start of the area, the P switch will make a different vine appear that will take you to a distinct area. In this level, this feature is first used to give you a grade A or B and assign a special sub-area, depending on how well you did in the first area. Then in the second area if you took too long it will take you to a slightly longer version of the third area. And the third area is very special, at the end it will tell you a grade, either A+, B or F and end the level. Try getting an A+, it's "fun".

Two days ago, Nintendo announced that they will finally add checkpoints to the game. But the past attempts to add unofficial checkpoints to the game weren't fruitless. A common idea was to use P switches and Vines or Bob-bombs to maybe unlock certain areas depending on a password you input. This idea can be adapted to things other than passwords. In this occasion, the 'password' is replaced with 3 blocks attached to a track. It will take the blocks a while to reach the position below the Muncher and stop the Muncher from falling and blocking the Shell's path. The shell's path then determines which Vine to open.

I hope someone is reading this blog and enjoys the level.

## Friday, October 09, 2015

### One-screen puzzles

Shortly after Mario Maker's release date, Seth Bling of youtube fame published a level entitled "One-screen puzzle".

Levels featuring puzzles in a single screen were not a novelty, but what was and what made this level worthy of that name that implies it's THE One-screen level was that the solution was very interesting definitely not trivial and you could spend an hour trying to solve this level. It got quite a bunch of stars and a place in the elusive top 100. It made the genre rise in popularity and Seth made other 4 such puzzles since then.

As a fan of puzzle games I couldn't help but try my own take on these levels.

Pow It - (course id: 30CB-0000-0098-7220)

Living Fire (course id: 9334-0000-0090-111E)

Flight Day (course id: 82B6-0000-0093-FA1D)

So let's talk one-screen puzzles.

I may have spent a good amount of free time making levels for a puzzle game to be left unnamed for now. When I think of puzzles there are some things to find interesting. Light spoilers for Seth Bling's puzzle :
• The mechanic(s): A puzzle level in a game like Mario that has plenty of kinds of objects and combinations between them should center around a game mechanic (you call them gimmicks when you don't like them). A player that finishes the level should leave with a new learned trick. The better and more interesting/unique the mechanic the cooler the level will be.  If you want to you can try and make a single level about multiple mechanics. It can really up the difficulty and make it more challenging but this is risky as it makes the level more confusing. I prefer centering around a single thing, specially in one-screen ones where space is tight. In Seth Bling's level above I'd say the key thing is the way the P switch is actually more solid than the caparace. That's something I didn't keep present until solving it.
•  The contradiction: The mechanic acts like a key, lacking the key should lead to game states in which things don't make much sense. In a Portal level, you need to push two buttons under a time limit so tight that you almost need to be two places at once. In Seth Bling's puzzle, you need to use the spring both to jump and also to send objects in another path, and it appears that one usage negates the other.
• The diversion: The solution to the puzzle needs certain objects but just leaving them might make it too obvious that they are needed there and might make the solution seem trivial or worse, happen by total coincidence without the player realizing it. Giving some objects fake / initial roles and requiring the player to take them out of them can be a nice detail. In Seth Bling's puzzle, the red koopa's evident use is to help save Yoshi.
• The Hints: On the other hand, you don't want the player to feel clueless about things. If the mechanic is way original the player might need help getting there. This help is really one of the hardest parts of puzzle design. You want the player to feel clever. So the clues shouldn't be super explicit, but the player should also not feel lost for too long. In Mario Maker that means they'll skip the level in a flash.
• The Implementation: Just knowing what to do is one thing, doing it is another topic. Implementation and logic are often at odds. Too much logic and the puzzle is a pure brain teaser. While cool, it wouldn't fit too well in Mario. Too much implementation and the level is not that much of puzzle anymore. Difficulty is another thing. I dislike puzzles in which implementation is difficult because, to me, it adds frustration. You are the player and you KNOW how to solve this but the stupid puzzle just won't let you actually do it. This is the part I like least about Seth Bling's puzzle levels. After figuring it out I still needed 40 or so attempts before getting it right, at that point the level felt more like a Kaizo level than a puzzle.
If you want to try my puzzles on your own (pleeaaaase someone play my levels!) you should stop reading as I am about to spoil them big time.

### Pow It

Pow It is in my opinion the easiest of the bunch. The mechanic it centers around is very simple: The Pow block makes coins fall down, this includes blocks that turned into coins because of the P switch. Big deal huh? Well you see, the contradiction is that if you don't know this there are many ways in which you'll get trapped.

The main diversion exists as the Muncher next to the P switch. Your first reflex will be to use the Pow to kill it so you can grab the P switch.

But doing means you failed the puzzle, remember the intended solution is to use the Pow while the P is active. It's not all that bad though, because using the Pow this way makes the Hint happen; The 3 coins will fall, reminding you that Pow makes coins drop.

How can this be solved? It's my least favorite part of the puzzle. I mentioned how I don't like tricky implementation, but it turns out it might be needed to be able to correctly disguise the solution. In Seth Bling's level, it's hard to make the caparace stop so you can use it again. This makes thinking of using the caparace that way less trivial. In Pow It, it appears you need to kill the Muncher to get the P switch, but it isn't exactly so...

If you somehow gently drop the Pow above the Muncher you can walk on it then with some luck you can jump and fall on the P switch. This makes the Muncher drop in height a bit allowing you to take back the pow (be careful).

I think this part of the level may have creeped a bit over what I originally intended. Are players even supposed to know how to drop the pow without activating it? That you can use it to walk on top of harmful areas?

I may do something like update the level so the pow starts on a Muncher and you can walk on it at first. Better hints or it makes it too obvious?

### Living Fire

Living Fire is my favorite of the bunch because the solution is very unique. It begins with a hint: Fire balls can make bob-ombs explode. Right then it shows you a diversion, you need to rush to use a bob-omb to rescue the clown car. You certainly will need the clown car to reach the other side of the level.

That's when the troubles begin. You need to make the two other bob-ombs explode. But the fire can't be moved. There's a yoshi which can eat fire and then use it to throw 3 fireballs, but Yoshi is on a side of the level too far from the fire that falls from the pipe (contradiction).

The mechanic is actually funny: If you live the clown car right below the pipe, the fire ball will take control over the clown car. Did you notice they have eyes? Turns out these fireballs are alive!

Once possessed, the clown car will move towards Mario but is mostly harmless (unless you touch the fire "brain") you can jump to push the clown places. A good place is the bob-omb on the top. So that was the real use of the starman , you didn't only need it to go through the saws but also to kill the fireball and take back control of the clown car.

It's unfortunate that there are no hints that this is even possible. My big hope is that while trying to do things and jumping around it happens naturally that the fire ball possesses the clown by accident. Then they can turn that into a solution.

This doesn't solve how to explode the other bob-omb and what Yoshi's role is in all this, but I think that's enough spoilers.

### Flight Day

There's one key mechanic / puzzle to solve in this level and it is that conveyor belts allow Caped Mario / Tanoki Mario to gain momentum in a small space. To divert away from this, I put the giant spiny on top of the conveyor belt, making it seem like the belt is there just to keep the spiny in place. The koopa then needs to be used in two situations: One is free get the leaf from the question block. But we also need to kill the spiny. There are two ways to do this, both require you to really know how to throw shells.

That secures one pow. The rest of the level is about using the other traits of the cape and this extra pow to get the other pow. This one is really implementation-heavy, but I enjoyed the result so I'm sharing it.

Play my levels!

## Thursday, October 08, 2015

### Super Mario Maker - The Bad

Hello everyone,

Have you heard of Super Mario Maker? It's a wonderful game by Nintendo that allows you to "create and share" your own Super Mario Levels.

I first heard of it in June when I found the Nintendo World Championship Finals video in youtube and I have been getting hyped for it since. By August I was really excited, just a couple more days and we should go buy a wii U and get Super Mario Maker.

On September the 1st, a car hit me and I temporarily lost right arm mobility. I was sad because of all the things I was going to miss out, including SMM. Except, that by the 10-th I was still hyped and realized that it was actually possible to still play Mario using the gamepad attachment in the Wii controllers. So all was setup and I still acquired it. To say that this game has made me endure the long wait for my bones to heal would be an understatement. I really think the distraction and the lack of frustration from missing out has been a massive help to my mental health during all of this and also I have the perfect reason not to stop using my right hand fingers during this.

The Game itself is top notch. Even though I watched so many videos that few things were really a surprise to me. I was ready to start making "the levels of my dreams" and the interface was not going to be an obstacle. Everything about creating levels in this game flows incredibly well. The strange touch screen Wii U 'controller' works extremely well and this game makes it seem like a good idea. It's really impressive.

I made some levels, I submitted them. I was also very interested in playing levels from others, so I played them. There was just a small problem...

### ... Nobody plays my levels

I don't think I am exaggerating. To this date, My oldest level, "Use the Shells" has been played by 45 different people. It's my second-most played level. My most played level has 61 plays.

In the image, the number next to the foot icon represents the number of people who played it. The flag represents the number of times it has been passed (four!) and the number below it the total number of tries. Out of the 45 people who played, they in total played 290 times. This means on average each person invested 6.44 attempts to win my level. I've received 6 stars.

I created this level on Saturday 12-th, a day after the official release date. I was barely spamming objects on the course creator hoping to unlock new elements when it occurred me to make a semi-puzzle level using shells. There were some okay ideas in this but nothing outworldly, just situations in which you need to kick shells in order to break blocks. Tried to have a Mario flow in the level, making the complexity progressive and adding breaks in which you can get coins / gratuitously kill enemies outside of the puzzle setting.

This was not a good level. In fact, I corrected it and made a version with less frustrating aspects. I'm not complaining about the low success or star rate. But the low play count overall. Must mention that many other levels I made in which I spent more effort have even less people playing them. We are talking of a total of 45 people, since release weekend, in a game that sold millions of units. For comparison, the top starred level has more than 750000 next to the foot icon. What is going on?

### Top Starred Courses

What does a player who want to play other people's levels do? The first suspect is the list of the top starred levels. The number of stars needed to be in this list is around the hundreds, and that's assuming the player will bother to scroll down and reach the bottom of the list.

ars technica published an elaborate analysis of the levels you can find in this list. It's not really the type of levels that is concerning to me. I don't share the vocal dislike for autoplay levels. A far more worrying trend is that every author you can find in this list seems to have visibility as a youtuber, or is a big streamer in twitch or has been otherwise featured in a large channel. Don't get me wrong, most of the levels in this list are very nice levels (although a couple of youtubers are definitely overrated). The problem is that in order to reach this top list you need to be already famous.

One of the issues is that the list is stale. Even the option to consider only stars from last week doesn't seem to stop it. Once you play many of the levels in this list, you'll notice that it barely experiences any change. It would be nice to be able to downright hide any level older than a week. I would also love a "last day"  option and perhaps even a "last hour" once. It seems that there's only a "last week" option because Nintendo didn't expect the enormous volume of courses that was uploaded.

### Featured?

There's another section called featured. It's nowhere explained how this section works. Many players believe these levels were picked by Nintendo staffers. Watching this list closely doesn't seem to confirm this. For example, there's a [refresh] button that makes a completely new list to appear. If these were manual picks, you wouldn't expect them to go away as easily.

It's possible that this list shows levels that are found via heuristic to be getting stars in an unusual radio. Some of the levels that appear in this list can be quite good, but there can also be some less good ones. The inconsistency hints towards an automatic kind of curation being involved.

### The 100 Mario Challenge

For level makers that are not widely known and who aren't willing to put the work that is promoting their work. The 100 Mario Challenge is the only hope to have levels become known.

The 100 Mario Challenge let's you pick three difficulties: Easy, Normal and Expert. It then provides 100 lives to beat 16 levels (8 in easy mode). If the player is successful, they rescue princess Peach and unlock a weird mushroom costume - These costumes allow Mario to look like another character, there's a wide variety of costumes to unlock including characters from other Nintendo franchises and even Sonic, Megaman, Pacman and Some Pokemon are available. If you instead lose all 100 lives, you get a game over screen. During the game and when the course is beaten, you can leave comments and stars if you like the level. If you don't like a level or think it's too difficult, you can skip it at the cost of one life. The whole process of finding worthy levels without external aid is centered around this challenge.

The problem is that the challenge is motivation for players to beat 16 levels. But it doesn't matter which one. There's no reward for persistence, in fact, it's punished. Players who skip levels aggressively whenever there's too much risk in the level will lose lives at a smaller rate and have more chances to unlock the costumes. Nothing encourages the player to star / comment the levels they liked. In addition, there are levels out there that are made in bad faith: Levels that are unbearably difficult unless you are the author and know the secret shortcut to the end. These shortcuts can be very elaborate and obscure or rely on bugs in the game, making the levels effectively impossible for anyone who is not the author. After facing such things and also the frequent low quality levels, players of 100 Mario challenge would run out of patience and be more prone to skip.

If your level has failed to call the interest of the player and has made them lose a couple of lives already, it might be skipped. This will ensure the success rate stays low, 0% or close to 0%. In turn this will make the level be classified as Expert. In Expert mode, the problems are amplified. Not only are players less willing to spend lives in your level, there are also far less players playing in Expert mode. Once my levels reach this state, I can easily tell because the rate at which players play the level drops noticeably.

### Following Makers

The game also provides an option to follow your favorite makers. Unfortunately, a more suitable name for this feature would be 'bookmark'. You can have a list of makers you like and manually open their pages to see their levels. It would be far more useful if it generated a feed with the latest levels by people you follow (and perhaps also levels starred by them). In its current state this feature is useful only to save you the hassle of constantly typing your friends' level ids.

### Up and Coming

"Up and Coming" is the section that shows levels as they are uploaded. Few people seem to like the idea of trying these levels. This section is useful to see one of the root issues: One thing you can tell is that hitting the refresh button makes a bunch of newer levels appear. It seems like a couple of minutes sees the upload of a few tens of levels if not hundreds. There's just too many levels. We are talking far more than a single person can play in their whole life.

### "You may also like"

One last method the game provides for discovery consists of a list of courses you may like to try just after playing another one. The results seem to be also based on stars and similarity to the course you just played. The suggestions tend to always have an already large amount of stars.

Why not just enjoy making levels and sharing them with friends? Unfortunately, SMM is presented as a game and like even the most closed-minded definition  of a game, it has failure conditions. There's a limit on the number of levels that you can share, the only way to raise this limit is earning stars. If you wish to share levels with your friends you will need to keep the limit in mind.

Worse still, The Manual implies that levels that don't reach an undisclosed amount of stars will eventually be deleted.

I wish you could share levels in private , outside of the limits and without the level getting picked for 100 Mario challenge. Until then earning stars is really a mandatory part of the game if you are the kind of person to want to make a plenty of new things.

### Third Party Sites

In the realization that the game's methods for course discovery won't help you when your level has barely any plays and less than 10 (or 3) stars, you might try to advertise your level in third party sites. That's the moment you realize that everyone is having exactly the same problem.

Try any article in a major site discusing Mario Maker without asking for level ids. There will be people posting level ids in the comments. E.g these replies to the Kotaku article by Patricia Hernandez about how to find good levels:

The worst part of it is that it doesn't work. Very few people will actually try random level ids they find.

Try a twitter search for #SuperMarioMaker and #MarioMaker HTs. Ignoring the large accounts and the videos, you will find find plenty of ids, in tweets that seem to have no RTs or Favorites or interactions whatsoever.

Nintendo Life has a section where users can submit levels. There are currently over 7000 submissions, but the top rated level has ... 27 likes.

The /r/MarioMaker subreddit has a daily level exchange thread. You are encouraged to play 4 levels before posting your own level id. If people followed these rules, posting your level would be almost guarantee that 4 people will play it. In practice, you are lucky if one person plays it. I've had mixed luck with this but many times I play 4 levels (and the levels tend to be very good) and comment and give feedback but have my level ignored or played by a single person that gives no feedback.

You may try going to twitch and find the rare streamers who don't do 100 Mario Challenge or stream their own level making. A handful of streamers may accept requests to play specific ids. These streamers eventually find their queues collapsed of id requests and decide to stop accepting them.

There's an intrinsic problem in trying to use third party sites to promote your levels. Those sites are already full of other people trying exactly the same. Meanwhile, the players seem to prefer to stick to the (poor) tools the game provides. This might be the reason players find themselves complaining about the terrible quality of Mario Maker levels. Like this now infamous post in the Washington post: “Super Mario Maker” is an engine for circulating horrible new “Mario” levels

### To Sum Up

Nobody plays my Mario Maker levels and there are plenty of level creators finding themselves in the same situation. Meanwhile, players willing to play nice levels have to settle with a very poor curation system that mostly benefits people with large fames prior to the existence of the game. SMM is one of the first serious attempts from Nintendo to rely on player content and it shows. Something must be done about this.

Meanwhile, I'll keep spending hours developing and updating levels that will be played for a minute before skipped in Mario Challenge. I have way too much fun doing this and will dedicate this blog to talk about my attempts. I plan to include serious opinions like this post and also Level/Game Design talk. I have no control in regards to how many people play my levels, but I can put my best effort to make the few ones who do stay engaged and not frustrated.

I really, really want to talk about my levels. Welcome to this Mario Maker blog.

## Thursday, September 10, 2015

### One handed programming and other things you didn't expect to read about in this blog

Hello all,

It's really been a while since I updated this blog. I've been dealing with difficulties balancing the work demands of writing editorials in topcoder and etc.

Tomorrow we have a new SRM, 667. It's going to be a very special SRM for me although not for happy reasons. You see; last September 1st a car hit me and I got a shoulder fracture. It was described as a lucky outcome and it seems like conservative therapy that consists of immobilization and waiting for the bone to heal on its own is the best approach. As a result, tomorrow I will only use one hand, my left hand (I am right-handed) in tomorrow's SRM. Let's see what happens.

Of course my real concern is about how it will affect my performance writing the editorial. As of late and after finally dealing with the old delayed problems that stacked up since last year. I've been really trying to get the editorials back to their former quick publishing glory. It kinda worked with 666's editorial. But of course the issue at hand might slow me down. I am optimistic, however. I was able to solve and write the editorial for the TopCoder Open round 2D after the accident. I just needed longer breaks after each problem.

In happier news: I have recently started a Patreon . It's focusing on my computer art and twitter anti spam work. I wonder if I can expand it for explanations of algorithmic problems? Maybe.

## Saturday, May 30, 2015

### Out of codejam : The curse of the dp sense

That was it for me in the code jam. I really think the whole outcome centers around how badly I've dealt with problem D. The 11 extra points from D small would have made me advance and get a t-shirt. Honestly what I really don't like is that you needed to be in top 500 for round 2 for the distributed codejam, which is a completely different contest format. I don't see the point for this restriction.

The first demoralization of the day was learning that the codejam-commandline tool no longer works. Google finally deprecated the authentification used by this tool, which was not updated in a looooong while. I really wonder if anyone other than me actually used this tool...

Problem statements

# Problem A: pegs

The trick is to notice that peg man can pick any cell. So if there is any cell that takes you out of the board, pegman will pick that cell. Why is this important? Consider the arrows that point directly to the outside of the map. You NEED to change them. Because pegman can always start at that arrow and exit the map. So it is necessary that these arrows point elsewhere.

Once all arrows that point to the outside of the map point somewhere else. They will each point to another arrow. And this is sufficient. Because no arrow in the map points to the outside of the map. So it really doesn't matter if we point to an arrow, this other arrow will never take us to theo utside of the map.

So the solution (for both A-small and A-large) is to just take each arrow that points to the outside of the map. If you can pick any new direction to it that makes it point to another arrow, increase cost by 1. Else it is impossible.

# Problem B: pool

I read the first paragraphs and seemed a bit too mathy, I felt that it was likely the other small problems were more approachable so I decided to skip it to read the other problems.

# Problem C-small: sentences

There are at most 18 sentences with unknown language, we can try each of the 2^18 combinations of English/French assignments and just simulate it. Or so you'd think...

A small blunder: I didn't notice that the number of words was a bit large so just naively doing the simulation was a bad idea. Even with my trick to use 4 cores so that each core runs each case separately, my first solution still needed around 10 minutes to clear a A-small input.

You don't need to parse and compare the words every time, you only care about which words are common to the two languages, so for example just replace each word with an integer, you need at most 2180 integers (although a case with 2180 distinct words is trivially 0). An extra improvement is to use bitsets from STL or something similar. Basically, you represent each sentence by 2180 / 64.0 bit masks, if the i-th bit is 1 then the i-th word is included in the sentence. Doing union / intersection operations with bit operations so that you can do the stuff rather fast (2180 / 64.0) steps.

Here is the code for the sub-problem, once you assign English or French to each sentence:

int N;
vector<string> sentences;

int sub_problem(vector<bool> &eng)
{
bitset<2180> english_words, french_words, inter;
for (int i = 0; i < N; i++) {
if (eng[i]) {
} else {
}
}
inter = english_words & french_words;
return inter.count();
}


You'd need to initialize the bitsets before simulating all assignments:

   int word_ids = 0;
map<string, int> word_id;

for (int i = 0; i < N; i++) {
}
for (int i = 0; i < N; i++) {
istringstream st(sentences[i]);
string x;
while (st >> x) {
int j = 0;
if (word_id.count(x)) {
j = word_id[x];
} else {
j = word_ids++;
word_id[x] = j;
}
}
}


The rest is the usual bruteforce for the assignments.

When I got correct in this problem I felt confident. There was quite a lot of time for the match but I was 400-th -ish. I thought that just solving D-small would put me in top 500. I was right...

# Problem D-small

For some reason I instantly thought dynamic programming was the way. You can certainly fill the cells using dynamic programming. Remembering the previous row and some other stuff. Well, seems hard at first except when you notice:

• Numbers larger than 4 are clearly never usable. A cell can't have 5 neighbors.
• Turns out 4 is also never usable. You cannot have a 4 in the top or bottom rows. If you place a 4 elsewhere, all 4 cells adjacent to that cell must be 4 too. If you repeat this logic, you'll eventually need the top or bottom row to contain a 4, which would be wrong.
• So you only need numbers 1-3 for the cells.

There is more, much more. But I really wish these 3 facts where the ONLY ones I noticed, because then I would have been discouraged to think of the bad dynamic programming solution I thought of...

• If you place a 3 in a cell in the top row, then all cells in the row must be 3, which also means that the cells in the top-second row must be 3. (Same happens with the last two bottom rows). In fact, after this filling the rest is similar to filling the same problem but with R-2 rows. With the exception that you cannot place 3 in the third row anymore. So yeah this hints a dynamic programming solution.
• The only time you are allowed to place a 3 elsewhere is when all the cells in the row above the row are matched to cells above the row. So really, whenever a 3 appears, it means that you need to fill 2 consecutive rows with 3s and the rows surrounding them cannot have any 3.
• So usually you only need to decide between 1 and 2.

This led me to a dynamic programming solution and rushed to start to code. It was a mistake. For starters just dealing with bitmasks (and you needed three sets of bit masks in this solution) introduces so much debugging time to coding something. What's worse is that I completely underestimated the difficulty in dealing with the rotations. My initial strategy was to just code without caring about duplicate rotations and then just do something like dividing the result by C or something? I didn't really have enough hindsight for what to do there. Once I noticed how non-trivial the rotations were in this dynamic programming solution it was too late. I put some (wrong) patch work to make the rotations work. It passed examples, but not the small tests.

That was the blunder: A much finer strategy was to try and solve the problem using bruteforce. In hindsight it should have been obvious to me, so this hurts. Here's the logic you (me) need to remember in the future to know not to miss the chance of using bruteforce in the key-to-solve bruteforce problem in your next significant match:

• The requirements for the values of the cells are VERY restrictive. Just a single decision removes plenty of later decisions. It's very likely that 6 times 6 grids and smaller the results should be very small. There would be very few valid ways. A big hint is that the results in the examples are both very small : 1 and 2. And the examples are very weak, so it shows the problem setter didn't want to make things too noticeable...
• Even if after coding the brute force, it turns out that doing all the brute forces is too slow for 4 minutes. It's very unlikely it would be too slow for 20 minutes (again, the cases are quite small and the restrictions very restrictive). "But vexorian, why would I want to solve them in 20 minutes when there is a 4 minutes limit?" You ask. There are only 20, TWENTY different inputs for this problem (D-small), so you can just precalculate them all off-line and just submit the precalculated solutions after you donwload the input.
• Even in the remote case somehow there are way too many valid assignments for some of the cases. This might be very helpful to learn more about the problem. Being able to visualize the solutions for 4 times 4 might help you notice some patterns. I am fairly sure that when you learn the patterns, you can solve D-large.
• Fancy dynamic programming is way riskier than brute force. It's far more likely you'll have bugs in the mega complicated bit mask stuff than your brute force would be too slow to be of ANY use. It is at least far easier to deal with rotations if you use the brute force.

So yeah, you (me) really should have used brute force in this problem. It is very important to detect wrong assignments as quickly as possible so there are few invalid branchings. This is what my code would have looked like if I did the right choice. It passes the D-small input and is incredibly fast:

    int R, C;
vector<string> board;

set<vector<string>> seenBefore;

bool cellCheck(int x, int y)
{
// check if cell (x,y) matches requirements
int dx = 0, dy = 1;
bool unknown = false;
int c = 0;
int t = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx, ny = (y + dy + C) % C;
if (0 <= nx && nx < R) {
t++;
if (board[nx][ny] == '?') {
// an unknown cell, if there are still unknown cells then
// the number of adjacent equal cells doesn't HAVE to be equal
// but if it is larger it is still invalid.
unknown = true;
} else if (board[nx][ny] == board[x][y]) {
c++;
}
}
tie(dx,dy) = make_tuple(dy, -dx);
}
int m = board[x][y] - '0';
if ( (c == m) || ( (c < m) && unknown) ) {
return true;
} else {
return false;
}
}

bool check_rotation()
{
// rotate the board C-1 times , if any of those was found before, return false
vector<string> board2 = board;
for (int k = 1; k < C; k++) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
board2[i][j] = board[i][ (j + k) % C ];
}
}
if (seenBefore.count(board2)) {
return false;
}
}
// else add it to the seenBefore set
seenBefore.insert(board);
return true;
}

int count_valid = 0;
void backtrack(int x, int y)
{
if (x == R) {
if (cellCheck(R-1,C-1) && cellCheck(R-1,0)) {
// valid
if (check_rotation()) {
count_valid++;
}
}
} else if (y == C) {
// finished fillign the row
// don't forget to verify also the beginning of the row
if (cellCheck(x,C-1) && cellCheck(x,0)) {
backtrack(x + 1, 0);
}
} else {
for (char ch = '1'; ch <= '3'; ch++) {
board[x][y] = ch;
bool valid = true;
if (x > 0) {
valid = valid && cellCheck(x-1,y);
}
if (y > 0) {
valid = valid && cellCheck(x,y-1);
}
if (valid) {
backtrack(x,y+1);
}
board[x][y] = '?';
}
}
}

int solve()
{
board.resize(R);
for (string &x : board) {
x = string(C,'?');
}
seenBefore.clear();
count_valid = 0;
backtrack(0,0);
return count_valid;
}


## Saturday, May 16, 2015

### Cloudy Conway

I like twitter bots. Did you know that there's a sizable amount of twitter bots generating pictures algorithmically?

There's @fractweet , for example, keeps posting random mandelbrot pictures. Some of them can be pretty nice.

Another of my favorites is @greatartbot, it plays an art game by itself and posts the results. This generates a ton of colorful random pixel art.

A good thing about these twitter bots is they just work without your supervision and without you even remembering to run them. They keep making random pictures and posting them in twitter. When they have a following, there's even humans that can curate the resulting pictures for you.

I wanted to make some random art bot of my own. The big problem with these things is, if the method to generate them is too random and not interesting, the results will be a mess. If it is not random enough , the results might be very pretty but usually the same. You need some good balance.

Something that seems to generate hard-to-predict randomness that looks nice is Conway's game of life. So I wondered how to use its randomness for my silly at bot objective. Okay, most of the times you put a bunch of random live cells in a Conway simulation the eventual result looks like this:

But the interesting part is all the movement that results in this rather stable state. There's a good example in this page: http://knusper.net/knusperblog/2013/conway-s-game-of-life-in-python-numpy-matplotlib/

So I made a program, basically besides of the state of the cells, it also remembers the number of iterations that passed since each cell died. So we know the last iteration number in which each cell alive. Live cells have 0 in this value. So imagine that the total number of iterations was T. And the number of iterations a cell has been dead is X, if we divide X by T, we will get a number from 0 to 1. Now we will assign a different shade of gray to each cell. If the cell's value was 0, it would be black, if the value was 1, it would be white, but if the value was 0.5, it would be neutral gray...

It seems like a bunch of clouds. Apparently not very impressive. But to me this was perfect because it generates strange shapes and shades. We just need to add color. To add color, we turn this gray shade from 0.0 to 1.0 into a color spectrum. For example, let's make 0.0 Red, 0.5 Green and 1.0 Blue. This way 0.25 is Yellow and 0.75 is... a bluer green, I guess. This spectrum trick is what the Mandelbrot fractal from fractweet up there uses. Mandelbrot fractals are basically a fraud: All the beauty comes not from math but from picking colors for the values...

And this is really all of it. Just making different random choices for the number of colors in the spectrum and the initial live cells. Maybe also experiment with different sizes of Conway grids. Some additional parameters too. The result is a program that can generate fairly interesting pictures... A twitter bot that goes by the name @CloudConway.

So my first objective of making a twitter bot seems accomplished. But I think there's more to this whole method of generating interesting shapes from Conway's game of life. In the meantime, I plan to release source code for this bot when the code stops being embarrassing...

## Monday, April 27, 2015

### SRM 657

I guess I just solved the div1 easy. Tried the div1 medium, modulos, modulos , modulos. But I finished the div1 easy editorial, you can find it at http://apps.topcoder.com/wiki/display/tc/SRM+657. Or here, because really, why not:

The problem consists of 6 variables: E, EM, M, MH, H, they are the number of problems you can use in problem sets. Each problem set needs an Easy, A Medium and a Hard problem to be used. E,M and H problems MUST be used as easy, medium or hard, respectively. There are EM problems that can be either easy or medium and MH problems that can be either Medium or Hard. What is the maximum number of problem sets you can make without repeating any problem? Oh, and each variable is a integer as long as 10^18.

Two decisions are involved in this problem:

• Of the EM problems that can be easy or medium, how many will be assigned as medium? Let that number be a
• Of the MH problems that can be medium or hard, how many will be assigned as medium? Let that number be b

When a and b are known, we can calculate the number of problems of each difficulty we have available:

• E + ("EM" - a)  easy problems.
• M + a + b medium problems.
• H + ("MH" - b)  hard problems.

To have a problem set we need one of each kind of problems, so the maximum problem sets is min(E + "EM" - a, M + a + b, H + "MH" - b).

Imagine we wanted to see if it is possible to have x problems in total:

• If E + "EM" < x, no matter what value of a we pick, the number of easy problems would be too small.
• If E + "EM" >= x, then there are normally enough easy problems unless a becomes too large. We can find the maximum allowed value of a: M_a = x - E + "EM". Also a cannot be larger than "EM"
• Similarly, H + "MH" must be at least x and M_b = x - H - "MH" is the maximum allowed value for b.
• We just need M + a + b to be at least x, imagine we take the maximum allowed values: if M + M_a + M_b >= x then we can know x is a valid number of problem sets

Now note that if a value of x is allowed, then so will all smaller values and if a value of x is not allowed , no value larger than x will be allowed. So we can use Binary Search to find the maximum allowed value for x, this is the maximum possible number of problem sets.


long allowedX(long E, long EM, long M, long MH, long H, long x)
{
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);

}

long maxSets(long E, long EM, long M, long MH, long H)
{
// We have to maximize:
// min(E + EM - a, M + a + b, H + MH - b)
// where 0 <= a <= EM , 0 <= b <= MH
long lo = 0; // we know 0 is allowed
long hi = M + MH + 1; // we know this will never be allowed
while (lo + 1 < hi) {
long x = (lo + hi) / 2;
if (allowedX(E,EM,M,MH,H, x)) {
lo = x;
} else {
hi = x;
}
}
return lo;
}


That was the solution in the editorial, but I prefer my lambda solution:

long maxSets(long E, long EM, long M, long MH, long H)
{
// We have to maximize:
// min(E + EM - a, M + a + b, H + MH - b)
// where 0 <= a <= EM , 0 <= b <= MH
return BinarySearch<long>( 0LL, H + MH + 1,  [&](long x) {
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);
});
}


It uses this Binary Search library function because it is funny to use functions as arguments.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the maximum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
while (lo + 1 < hi) {
D ha = lo + (hi - lo) / 2;
if (P(ha)) {
lo = ha;
} else {
hi = ha;
}
}
return lo;
}



## Friday, April 17, 2015

### Codejam round 1A, problem B : Hair Cut

Okay, I participated in round 1A and utterly failed. A ton of factors got involved that made me waste time.

• I thought of the solution for problem A, but when I started to code it I figured out I didn't actually set up my codejam test environment. I had a ton of setup to do to make my (worthless) solution multithreading support to work AND for it to work in gcc 4.8.2 with c++11 support.
• I got really confused by problem A, apparently eating 1.5 (or any other fraction) mushrooms per second is valid... but I don't think that was really well explained... Also what's up with "constant ratio" when the ratio is definitely not constant? It becomes 0 at some times? Huh? And how about giving you an input example before describing what the input is?
• I tried to solve B, my first solution was too slow, then I tried to find cycles in the simulation and it worked but I kept failing the small solution. There was a small bug - After doing the cycle stuff I forgot to return 1-indexed results... Overall what happened in problem B is I completely missed there's a very simple (but with caveats) solution until the last 2 minutes of the match, it was too late.
• C small is just bruteforce and convex hull. Thanks to allowing colinear points (artificial difficulty at its finest :/) I actually had to do a ton of fixes to my convex hull algorithm which I haven't really used in years. My code was pretty awful and there were a couple of bugs in that old code that I had to fix.

Anyway, since B-small / B-large are the only problems I solved that are actually interesting. Here is an explanation for problem B large:

## The time

I think the most important thing is to notice the problem is much easier when we know the time t  at which customer N will be served. Imagine we knew this time in advance. Then we would only need a single loop to find all the barbers that finish serving a customer at time t. Each barber i is a cycle, every M_i the barber serves a new customer. So barbers with M_i such that: (t mod M_i = 0) will serve a new customer at time t.

You might be thinking that the solution is the barber that serves a new customer at time t and has the smallest index. This is not entirely true. Multiple customers may be served at time t, and N is not necessarily the first customer to be served at that time. How can we approach this?

Imagine a function b(t) that told you how many customers are served with starting time less than or equal than t. Then b(t-1) will be the amount of customers that were served right until time t. And b(t) - b(t-1) is the amount of customers that start getting served exactly at time t. Now N - b(t-1) - 1 customers will be served at time t before N. Which means that we are looking for the barber with the (N - b(t-1))-th smallest index among those barbers with (t % M_i = 0).

The last piece of the puzzle is how to find t. It all comes down to b(t), with this function we can do a binary search for the smallest t such that b(t) >= N, this is the time you want.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the minimum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
while (lo + 1 < hi) {
D ha = lo + (hi - lo) / 2;
if (P(ha)) {
hi = ha;
} else {
lo = ha;
}
}
return hi;
}

struct solver
{
int N, B;
vector<int> M;

int solve()
{

auto begunByTime = [&](long t) -> long {
if (t < 0) {
return 0;
}
long begun = 0;
for (int i = 0; i < B; i++) {
// how many times did it start?
begun += t / M[i] + 1;
}
return begun;
};

// Is the start time for at least N users <= t ?
auto enoughBegun = [&](long t) -> bool {
return (begunByTime(t) >= N);
};

long t = BinarySearch<long>(-1, 10000000000000LL, enoughBegun);
long old = begunByTime(t-1);
long rem = N - old;

//cout << "time = "<<t<<endl;
// find smallest index of a server that starts at time t:
for (int i = 0; i < B; i++) {
if (t % M[i] == 0) {
if (rem == 1) {
return i + 1;
} else {
rem--;
}
}
}
assert(false);
return -1;

}
void init() { }
cin >> B >> N;
//N = 1000000000;
//B = 1000;
M.resize(B);
for (int & x : M) {
cin >> x;
//x = 1 + rand() % 100000;
}

}

Edit: Fixed bugs, oh and also b(t) is just the sum of a bunch of divisions. For each barber, you can find the number of times the barber has started serving customers before or during t by just doing a division, because for every M_i seconds, the barber tries a new user.

## Saturday, April 11, 2015

### Google Codejam 2015 Qualification Round : Part 4: C small

Part 1: Problem D in Emily

Part 2: Problem A in unnamed language

Part 3: Problem B in Julia

## C small

Problem statement

Unlike the other Small problems I didn't really think of a solution of this right away. I had to take a day to do it.

The trick to the problem is that we can find in O(n) the product of the x first left-most numbers (for all x). And the same for the right-most numbers. So imagine if we had a substring [a,b]. If left[a-1] is equal to i and right[b+1] is k then all that we need to learn is if the substring is equal to j. If we can answer that question in O(n^2), we have the whole problem solved. And we totally can answer that question! We just need to start with an a, then b = a and calculate the product for b = a, then it is easy to calculate the product when b = a + 1, just multiply one more number. And so and so for b = a + 2, etc.

The only extra complication is doing the multiplication with i, j, k and the signs... Well, really there are 8 distinct numbers, and we can easily index them and make a table, multiplying this index with this other index yields this other index...

So I tried free pascal. I used to code in Pascal, and I hated it. Now I don't really remember much. So I guess it counts? I had to relearn Pascal a bit. But I reached a solution... which failed. And then it failed again and again... I really thought the problem was in that big hardcoded matrix, and spent hours trying to think of a mistake there. Turns out that free Pascal's Strings are limited to 255 characters (What the hell, free pascal?). You have to use AnsiString for limitless strings.

program C;

function solution(s : AnsiString): String;
const
CONST_I = 2;
CONST_J = 4;
CONST_K = 6;
var
i, j, n, left, curr : Integer;
right : Array[0..100000] of Integer;
t : Array[0..7,0..7] of Integer = (
(0,1,2,3,4,5,6,7),
(1,0,3,2,5,4,7,6),
(2,3,1,0,6,7,5,4),
(3,2,0,1,7,6,4,5),
(4,5,7,6,1,0,2,3),
(5,4,6,7,0,1,3,2),
(6,7,4,5,3,2,1,0),
(7,6,5,4,2,3,0,1)
);
inputInts: Array[0..99999] of Integer;

function ch2index(ch: Char): Integer;
begin
ch2index := CONST_K;
if ch = 'i' then ch2index := CONST_I;
if ch = 'j' then ch2index := CONST_J;
end;

begin

n := Length(s);
solution := 'NO';
for i:=1 to n do begin
inputInts[i - 1] := ch2index(s[i]);
end;
right[n] := 0;
for i := n - 1 downto 0 do begin
right[i] := t[inputInts[i]][right[i+1]];
end;
left := 0;
for i := 0 to n-1 do begin
curr := 0;
for j := i to n-1 do begin
curr := t[curr][inputInts[j]];
if (left = CONST_I) and (curr = CONST_J) and (right[j+1] = CONST_K) then begin
solution := 'YES';
end;
end;
left := t[left][inputInts[i]];
end;
end;

var
X, L : Integer;
w : AnsiString;
ww : AnsiString;
T : Integer;
i,j : Integer;
begin
for i := 1 to T do begin
end.