Hey , so if you want to try some of my levels, the easiest way to find them is in my bookmark site profile page: vexorian's Mario Maker courses
Maybe you prefer something more organized. Here's a spreadsheet of all my courses, putting the ones with the best star rate at the top: The Spreadsheet
Saturday, May 14, 2016
Friday, May 13, 2016
New rules in Super Mario Maker and why I don't like them
Super Mario Maker is such a fun game! I've been playing and making levels since September. SMM will always have a warm place in my heart because it helped my morale while recovering from a car accident.
And one of the reason Super Mario Maker is so much fun is all the tricks and interactions between objects that you can find. Some of which have only been recently discovered. When you add a creative mind to these ideas, you can get some amazing levels.
Did you know that podoboos (The fire balls that normally bounce from lava) can pilot a Clown Car? And that this Fire-headed Clown Car can then be used to light up bombs?
Did you know that you can stand on a P-switch and use it to enter a door as long as you press UP quickly enough? Did you know that falling donut blocks can be jumped to and walked over, which is cool because thwomps can make them fall over?
Did you know that, by using tracks, you can make elements fall into the same track and thus share the same position. Which you can use to get fun results such as giant fireballs that shoot fire balls at Mario?
Did you know that, by using enemy stacking and podoboos you can place some objects with a half a grid square offset of where the game usually allows you to place them?
Those were various examples of cool interactions between the elements available in the game. Super Mario Maker is , after all, all about finding these interactions. The game encourages you to look for new things. It never tells you explicitly that dragging a super mushroom to an enemy can make it larger. Or that dragging a fire flower to a mushroom can make it a tiered powerup. You can attach canons to enemies, but the game never tells you this explicitly. It waits for you to find out on your own, through experimenting with the editor or by seeing it in someone else's level.
This is what the game is all about. Exploration. It wants you to try new things. New combinations. Behaviors that might not be obvious at first but the result of combining multiple elements in ways that maybe weren't explicitly intended by Nintendo. Goombas stacked on one another while on top of a treadmill and close to a horizontal spring look like they are dancing. Bullet bills can trigger P switches. Make fire sticks share the same position to make new shapes.
Then we have a problem. Because the inclusion of a bug in a course may have been the result of this very exploration. In fact, some of the things I mentioned might be bugs. This is 100% dependent on what Nintendo decide to call bugs and since the rule is ambiguous and punishes ALL usages of bugs and not just the ones that have the intention of ruining the players' experience.
It's not without precedent. In the past, there was once a trick that allowed you to place two objects in the same square in a way that the player sees one object but it in fact behaves like another one. This trick used a process similar the podoboo trick above, relying on placing objects on tracks and then removing the tracks in a careful way. Some of the most interesting Super Mario Maker levels I've played showcased this trick. We had clouds that became blocks, solid blocks that disappeared when a P-switch was pressed. Slippery blocks. This bug opened a plethora of possibilities and enabled some very fun levels to exist. Unfortunately, Nintendo not only fixed the glitch, but they deleted all levels that were detected to use it. Including levels that didn't seem to really use the trick - Maybe the trick was used accidentally and in a hidden area that's not visible during gameplay or maybe the algorithm to detect levels using the trick had false positives.
It's sad to think that the penalty for having bugs in your course has actually become worse. They will no longer just delete your level and make you unable to upload it again. In addition, they will wipe all your stars. All of them. Even those gained from 'legit' levels. The maker with most stars in Europe, Hyrulean, lost all the stars given to their account. Someone who used to hold over 500000 stars now has around 1000 stars. This is an extreme punishment for having a single glitch level out of 81 courses.
These rules need to be changed to specify that only harmful bugs will be subject to this punishment. There have been makers that intentionally make levels that crash the game and that's indeed behavior that needs some sort of measure. However, an ambiguous statement on anything that the dev team might think is a bug is a very harmful rule. It discourages the key elements of this game: Experimentation and Creativity. It also adds a level of discomfort to the craft of making levels, you don't know if Nintendo might suddenly decide that something in one of your levels is a bug and you might lose all the work you put into this game. Nintendo need to pursue making the game more enjoyable, not by limiting our creativity but by nourishing it.
And one of the reason Super Mario Maker is so much fun is all the tricks and interactions between objects that you can find. Some of which have only been recently discovered. When you add a creative mind to these ideas, you can get some amazing levels.
Did you know that podoboos (The fire balls that normally bounce from lava) can pilot a Clown Car? And that this Fire-headed Clown Car can then be used to light up bombs?
Did you know that you can stand on a P-switch and use it to enter a door as long as you press UP quickly enough? Did you know that falling donut blocks can be jumped to and walked over, which is cool because thwomps can make them fall over?
Did you know that, by using tracks, you can make elements fall into the same track and thus share the same position. Which you can use to get fun results such as giant fireballs that shoot fire balls at Mario?
Did you know that, by using enemy stacking and podoboos you can place some objects with a half a grid square offset of where the game usually allows you to place them?
This last one might seem irrelevant. Who cares about 0.5 square distance? Why would you need such specific precision when placing elements? And yet this week a certain, incredibly awesome level involving a Mecha became viral. I've seen people everywhere talking about this level. I wouldn't be surprised if Super Mario Maker experienced an activity spike because of this level. And the mech in this level wouldn't be possible without being able to position its elements correctly using this trick.
Those were various examples of cool interactions between the elements available in the game. Super Mario Maker is , after all, all about finding these interactions. The game encourages you to look for new things. It never tells you explicitly that dragging a super mushroom to an enemy can make it larger. Or that dragging a fire flower to a mushroom can make it a tiered powerup. You can attach canons to enemies, but the game never tells you this explicitly. It waits for you to find out on your own, through experimenting with the editor or by seeing it in someone else's level.
This is what the game is all about. Exploration. It wants you to try new things. New combinations. Behaviors that might not be obvious at first but the result of combining multiple elements in ways that maybe weren't explicitly intended by Nintendo. Goombas stacked on one another while on top of a treadmill and close to a horizontal spring look like they are dancing. Bullet bills can trigger P switches. Make fire sticks share the same position to make new shapes.
Just another day in Mario Maker
So when the news breaks that Nintendo announced new rules including:
The course included content that the Super Mario Maker team judged to be a bug in the game.
Then we have a problem. Because the inclusion of a bug in a course may have been the result of this very exploration. In fact, some of the things I mentioned might be bugs. This is 100% dependent on what Nintendo decide to call bugs and since the rule is ambiguous and punishes ALL usages of bugs and not just the ones that have the intention of ruining the players' experience.
It's not without precedent. In the past, there was once a trick that allowed you to place two objects in the same square in a way that the player sees one object but it in fact behaves like another one. This trick used a process similar the podoboo trick above, relying on placing objects on tracks and then removing the tracks in a careful way. Some of the most interesting Super Mario Maker levels I've played showcased this trick. We had clouds that became blocks, solid blocks that disappeared when a P-switch was pressed. Slippery blocks. This bug opened a plethora of possibilities and enabled some very fun levels to exist. Unfortunately, Nintendo not only fixed the glitch, but they deleted all levels that were detected to use it. Including levels that didn't seem to really use the trick - Maybe the trick was used accidentally and in a hidden area that's not visible during gameplay or maybe the algorithm to detect levels using the trick had false positives.
It's sad to think that the penalty for having bugs in your course has actually become worse. They will no longer just delete your level and make you unable to upload it again. In addition, they will wipe all your stars. All of them. Even those gained from 'legit' levels. The maker with most stars in Europe, Hyrulean, lost all the stars given to their account. Someone who used to hold over 500000 stars now has around 1000 stars. This is an extreme punishment for having a single glitch level out of 81 courses.
These rules need to be changed to specify that only harmful bugs will be subject to this punishment. There have been makers that intentionally make levels that crash the game and that's indeed behavior that needs some sort of measure. However, an ambiguous statement on anything that the dev team might think is a bug is a very harmful rule. It discourages the key elements of this game: Experimentation and Creativity. It also adds a level of discomfort to the craft of making levels, you don't know if Nintendo might suddenly decide that something in one of your levels is a bug and you might lose all the work you put into this game. Nintendo need to pursue making the game more enjoyable, not by limiting our creativity but by nourishing it.
Saturday, April 09, 2016
Google Code Jam 2016
I completely forgot about the qualification round. This morning I woke up and was planning to have a normal day when I accidentally noticed in my calendar applet that "Qualification Round" was on. What qualification round!? Oh no, the google one...
So I decide to register to the contest and it's 15 hours late. What are even the rules? Is it the same as usual? What's the cut-off? It turns out everything is mostly the same. I need 30 points and just the small inputs are enough to give you 37 points. So it should be easy to qualify.
Perhaps it's too similar to previous editions? I think 1000 t-shirts is pretty low, considering how much the attendance has grown since this number was established. Actually when I look at the past I think I would have never really put as much work on programming contest if, ages ago, when I was getting started, there weren't as many small rewards for simple things as they were. In the past, in codejam or topcoder open, qualifying to the elimination rounds was worth a t-shirt and there were extra little rewards for advancing in other rounds. In fact, the first codejam done using Google's own site had regional semifinals so if you were in the top 500 you'd already win a paid trip to a google office.
Back to the present. Qualifying, even 15 hours late should be pretty easy for adecrepitveteran contest participant such as I. But the real contest is to get a perfect 100/100. So what are my chances there? Looking at the score board it seemed like this qualification round had easier problems than previous editions, as a really considerable amount of competitors already had the perfect score. So I gave it a shot. Note that I am starting to write this before the end of the round, so I don't know if I scored properly.
Problem Statement
This is a straight-forward problem, you just need to simulate the steps until all digits are found. A pressing question is what's up with impossible cases? Well, I actually just coded right away and tested all 1000001 possible inputs from 0 to 1000000, with a maximum number of 1000 steps to find all digits. Even then, the simulation is very fast and the only case that doesn't reach all digits is `N = 0`, which will always be 0 no matter how far you go. So with that knowledge I just submitted an easy code:
const int MAX_ITERATIONS = 1000;
long solve(long x)
{
long y = x;
set<char> s;
for (int i = 0; i < MAX_ITERATIONS; i++) {
ostringstream st;
st << y;
for (char ch: st.str()) {
s.insert(ch);
}
if (s.size() == 10) {
return y;
}
y += x;
}
return -1;
// not pictured: I/O stuff including translating -1 to "impossible"
}
Problem Statement
Well, the small version can be solved using a Breadth-First Search. Just consider a string of +/- as a vertex in some graph and each possible step is an edge between its initial setup and its resulting setup. Then you want to find the shortest path between the input and +++++...+ . With `N <= 10`, there are at most `2^10 = 1024` vertices in the graph, so this is quite doable.
But I wanted to solve the hard version. Clueless as I often are, I just did the small version hoping that it would help me think of the hard solution. I concluded some greedy approach was needed because all permutations of cookies are reachable from any initial setup so cutting the search space wouldn't work (for me).
After coding the small version and being able to see some of the solutions it generates, I noticed a very obvious pattern:
+++-++---+--+
----++---+--+
++++++---+--+
---------+--+
++++++++++--+
------------+
+++++++++++++
Basically keep flipping the largest sequence of cookies at the top that have the same sign (+ or -) as the top-most cookie. You will eventually have a bunch of happy cookies. And this is the optimal solution. Because this is the optimal strategy in a different problem where a step consists only about changing the sign of a prefix of a string, and the other options in the real problem are not better.
int solve(string s)
{
int n = s.size();
int step_count = 0;
while (s != string(n, '+') ) {
int t = 1;
while ( (t < n) && (s[t] == s[t-1]) ) {
t++;
}
for (int i = 0; i < t; i++) {
if (s[i] == '+') {
s[i] = '-';
} else {
s[i] = '+';
}
}
step_count++;
}
return step_count;
}
/* _Used this to think of the real strategy which was pretty obvious in
hindsight ... */
int solve_slow(string s)
{
int n = s.size();
map<string, int> dist;
queue<string> Q;
dist[s] = 0;
Q.push(s);
map<string, string> parent;
while (! Q.empty()) {
string s = Q.front();
Q.pop();
for (int t = 1; t <= n; t++) {
string ss = s;
reverse(ss.begin(), ss.begin() + t);
for (int i = 1; i <= t; i++) {
char & ch = ss[i - 1];
ch = ( (ch == '+') ? '-' : '+' );
}
if ( dist.count(ss) == 0) {
dist[ss] = dist[s] + 1;
Q.push(ss);
parent[ss] = s;
}
}
}
string w = string(n, '+');
assert( dist.count(w) == 1 );
{
stack<string> S;
string x = w;
while (true) {
S.push(x);
if (parent.count(x) == 1) {
x = parent[x];
} else {
break;
}
}
while (! S.empty()) {
cout << S.top() << endl;
S.pop();
}
}
return dist[w];
}
Problem Statement
My initial hunch was that a huge majority of the possible binary strings are valid coins. Because really, primes tend to be hard to find and we want strings that aren't primes. Even though they can't be primes in many bases. But I still thought it would take a while to find 500 coins. So I decided to do something with threads. I find threads easier in python so I used python. When I finished coding it and tested, it turned out that the code was very fast, so the threads weren't needed :/, but it's still a cool looking solution:
N = 32
J = 500
NUM_THREADS = 4
EASY_PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
import random
import threading
import sys
mutex = threading.Lock()
seen_coins = dict()
def add_if_new(coin, divisors):
with mutex:
if coin not in seen_coins and len(seen_coins) < J:
seen_coins[coin] = divisors
sys.stderr.write( str(len(seen_coins)) + ' already!\n' )
sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
sys.stderr.flush()
def work_done():
with mutex:
if len(seen_coins) >= J:
return True
else:
return False
def random_coin():
x = [ random.randint(0,1) for i in range(N) ]
x[0] = 1
x[-1] = 1
return tuple(x)
def is_divisor(coin, b, d):
m = 0
p = 1
for x in reversed(coin):
if x == 1:
m = (m + p) % d
p = (p * b) % d
if m == 0:
return True
else:
return False
def get_divisors(coin):
divisors = []
for b in xrange(2,10 + 1):
for d in EASY_PRIMES:
if is_divisor(coin, b, d):
divisors.append(d)
break
else:
return None
return divisors
attempt_count = [0]
def worker():
while not work_done():
coin = random_coin()
divisors = get_divisors(coin)
if divisors != None:
add_if_new(coin, divisors)
with mutex:
attempt_count[0] = attempt_count[0] + 1
#sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
threads = [ threading.Thread(name='worker%d'%i, target=worker) for i in range(NUM_THREADS) ]
for t in threads:
t.start()
for t in threads:
t.join()
sys.stdout.write( 'Case #1:\n')
for x in seen_coins:
for y in x:
sys.stdout.write( str(y) )
for div in seen_coins[x]:
sys.stdout.write( ' ' + str(div) )
sys.stdout.write( '\n')
sys.stdout.flush()
I think one thing that improves the execution is I only test if the coin is a multiple of a small list of primes. Instead of looking for coins that are any composite number , I add the condition that they are a multiple of small primes. Most composite numbers are multiples of small prime numbers, so this shouldn't be an issue in theory, and in practice, it isn't.
Problem Statement
First the small problem is super trivial. Because `S = K`, so you can just test positions 1,2,3,...`S` and it will be enough. Because if there is any G in the initial string, then the final string will definitely have a G in that same position.
The larger solution is more complicated but not that much. Even though it took me a couple of hours to think of it .
If you want to be able to find any case that contains a G, then we should focus on the hardest cases, the ones that have only one G in the input: GLLL, LGLL, LLGL, LLLG. It turns out that if you include a G in position 1, it spreads to many positions in the later iterations. So imagine we had four positions: ABCD in the first string. We want to find which positions of the second string would be effected by positions A, B, C and D (E.g: If there is a G in position A, then the second position of the second string will contain a G. If there is a G in position B, then the second position of the second string will also contain a G, so position 2 of the second string can be classified as AB. If you repeat this you will find: A, AB, AC, AD, AB, B, BC, BD, AC, BC, C, CD, AD, BD, CD, D. Perhaps it will be easier if you read it as: AA, AB, AC, AD, AB, BB, BC, BD, AC, BC, CC, CD, AD, BD, CD, DD. In fact, with 3 steps we have: AAA, AAB, AAC, AAD, ... DDD. And so and so, it's the same as thinking of numbers in base K. So for C = 3, if we want positions that cover as many initial Gs as possible then we want the positions that have ABC and DAA (or DAB or ADC, anything containing a D). You can get the position index by converting from base k to base 10. This explanation is probably very bad. Sorry, I can't do better without drawings.
long translate(vector<int> digits, int K)
{
long res = 0;
long p = 1;
for (int i = 0; i < digits.size(); i++) {
res += p * digits[i];
p *= K;
}
/*for(auto x: digits) cout << " " << x;
cout << " -> "<<res<<endl;*/
assert(res >= 0);
return res;
}
list<long> solve(int K, int C, int S)
{
list<long> res;
int p = 0;
while (p < K) {
vector<int> digits;
for (int i = 0; i < C; i++) {
if (p < K) {
digits.push_back(p);
p++;
} else {
digits.push_back(0);
}
}
res.push_back( 1 + translate(digits, K) );
}
if (res.size() > S) {
//assert(false);
return {};
} else {
return res;
}
}
As I was typing, the round ended, let's check the final results...
All my large solutions were okay. But tons of people had them okay as well. I am barely in position 1246. That's pretty low, but I did start the round 15 hours late... (excuses)
So I decide to register to the contest and it's 15 hours late. What are even the rules? Is it the same as usual? What's the cut-off? It turns out everything is mostly the same. I need 30 points and just the small inputs are enough to give you 37 points. So it should be easy to qualify.
Perhaps it's too similar to previous editions? I think 1000 t-shirts is pretty low, considering how much the attendance has grown since this number was established. Actually when I look at the past I think I would have never really put as much work on programming contest if, ages ago, when I was getting started, there weren't as many small rewards for simple things as they were. In the past, in codejam or topcoder open, qualifying to the elimination rounds was worth a t-shirt and there were extra little rewards for advancing in other rounds. In fact, the first codejam done using Google's own site had regional semifinals so if you were in the top 500 you'd already win a paid trip to a google office.
Back to the present. Qualifying, even 15 hours late should be pretty easy for a
Problem A (Large)
Problem Statement
This is a straight-forward problem, you just need to simulate the steps until all digits are found. A pressing question is what's up with impossible cases? Well, I actually just coded right away and tested all 1000001 possible inputs from 0 to 1000000, with a maximum number of 1000 steps to find all digits. Even then, the simulation is very fast and the only case that doesn't reach all digits is `N = 0`, which will always be 0 no matter how far you go. So with that knowledge I just submitted an easy code:
const int MAX_ITERATIONS = 1000;
long solve(long x)
{
long y = x;
set<char> s;
for (int i = 0; i < MAX_ITERATIONS; i++) {
ostringstream st;
st << y;
for (char ch: st.str()) {
s.insert(ch);
}
if (s.size() == 10) {
return y;
}
y += x;
}
return -1;
// not pictured: I/O stuff including translating -1 to "impossible"
}
Problem B (Small and Large)
Problem Statement
Well, the small version can be solved using a Breadth-First Search. Just consider a string of +/- as a vertex in some graph and each possible step is an edge between its initial setup and its resulting setup. Then you want to find the shortest path between the input and +++++...+ . With `N <= 10`, there are at most `2^10 = 1024` vertices in the graph, so this is quite doable.
But I wanted to solve the hard version. Clueless as I often are, I just did the small version hoping that it would help me think of the hard solution. I concluded some greedy approach was needed because all permutations of cookies are reachable from any initial setup so cutting the search space wouldn't work (for me).
After coding the small version and being able to see some of the solutions it generates, I noticed a very obvious pattern:
+++-++---+--+
----++---+--+
++++++---+--+
---------+--+
++++++++++--+
------------+
+++++++++++++
Basically keep flipping the largest sequence of cookies at the top that have the same sign (+ or -) as the top-most cookie. You will eventually have a bunch of happy cookies. And this is the optimal solution. Because this is the optimal strategy in a different problem where a step consists only about changing the sign of a prefix of a string, and the other options in the real problem are not better.
int solve(string s)
{
int n = s.size();
int step_count = 0;
while (s != string(n, '+') ) {
int t = 1;
while ( (t < n) && (s[t] == s[t-1]) ) {
t++;
}
for (int i = 0; i < t; i++) {
if (s[i] == '+') {
s[i] = '-';
} else {
s[i] = '+';
}
}
step_count++;
}
return step_count;
}
/* _Used this to think of the real strategy which was pretty obvious in
hindsight ... */
int solve_slow(string s)
{
int n = s.size();
map<string, int> dist;
queue<string> Q;
dist[s] = 0;
Q.push(s);
map<string, string> parent;
while (! Q.empty()) {
string s = Q.front();
Q.pop();
for (int t = 1; t <= n; t++) {
string ss = s;
reverse(ss.begin(), ss.begin() + t);
for (int i = 1; i <= t; i++) {
char & ch = ss[i - 1];
ch = ( (ch == '+') ? '-' : '+' );
}
if ( dist.count(ss) == 0) {
dist[ss] = dist[s] + 1;
Q.push(ss);
parent[ss] = s;
}
}
}
string w = string(n, '+');
assert( dist.count(w) == 1 );
{
stack<string> S;
string x = w;
while (true) {
S.push(x);
if (parent.count(x) == 1) {
x = parent[x];
} else {
break;
}
}
while (! S.empty()) {
cout << S.top() << endl;
S.pop();
}
}
return dist[w];
}
Problem C (Small and Large)
Problem Statement
My initial hunch was that a huge majority of the possible binary strings are valid coins. Because really, primes tend to be hard to find and we want strings that aren't primes. Even though they can't be primes in many bases. But I still thought it would take a while to find 500 coins. So I decided to do something with threads. I find threads easier in python so I used python. When I finished coding it and tested, it turned out that the code was very fast, so the threads weren't needed :/, but it's still a cool looking solution:
N = 32
J = 500
NUM_THREADS = 4
EASY_PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
import random
import threading
import sys
mutex = threading.Lock()
seen_coins = dict()
def add_if_new(coin, divisors):
with mutex:
if coin not in seen_coins and len(seen_coins) < J:
seen_coins[coin] = divisors
sys.stderr.write( str(len(seen_coins)) + ' already!\n' )
sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
sys.stderr.flush()
def work_done():
with mutex:
if len(seen_coins) >= J:
return True
else:
return False
def random_coin():
x = [ random.randint(0,1) for i in range(N) ]
x[0] = 1
x[-1] = 1
return tuple(x)
def is_divisor(coin, b, d):
m = 0
p = 1
for x in reversed(coin):
if x == 1:
m = (m + p) % d
p = (p * b) % d
if m == 0:
return True
else:
return False
def get_divisors(coin):
divisors = []
for b in xrange(2,10 + 1):
for d in EASY_PRIMES:
if is_divisor(coin, b, d):
divisors.append(d)
break
else:
return None
return divisors
attempt_count = [0]
def worker():
while not work_done():
coin = random_coin()
divisors = get_divisors(coin)
if divisors != None:
add_if_new(coin, divisors)
with mutex:
attempt_count[0] = attempt_count[0] + 1
#sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
threads = [ threading.Thread(name='worker%d'%i, target=worker) for i in range(NUM_THREADS) ]
for t in threads:
t.start()
for t in threads:
t.join()
sys.stdout.write( 'Case #1:\n')
for x in seen_coins:
for y in x:
sys.stdout.write( str(y) )
for div in seen_coins[x]:
sys.stdout.write( ' ' + str(div) )
sys.stdout.write( '\n')
sys.stdout.flush()
I think one thing that improves the execution is I only test if the coin is a multiple of a small list of primes. Instead of looking for coins that are any composite number , I add the condition that they are a multiple of small primes. Most composite numbers are multiples of small prime numbers, so this shouldn't be an issue in theory, and in practice, it isn't.
Problem D (Small and Large)
Problem Statement
First the small problem is super trivial. Because `S = K`, so you can just test positions 1,2,3,...`S` and it will be enough. Because if there is any G in the initial string, then the final string will definitely have a G in that same position.
The larger solution is more complicated but not that much. Even though it took me a couple of hours to think of it .
If you want to be able to find any case that contains a G, then we should focus on the hardest cases, the ones that have only one G in the input: GLLL, LGLL, LLGL, LLLG. It turns out that if you include a G in position 1, it spreads to many positions in the later iterations. So imagine we had four positions: ABCD in the first string. We want to find which positions of the second string would be effected by positions A, B, C and D (E.g: If there is a G in position A, then the second position of the second string will contain a G. If there is a G in position B, then the second position of the second string will also contain a G, so position 2 of the second string can be classified as AB. If you repeat this you will find: A, AB, AC, AD, AB, B, BC, BD, AC, BC, C, CD, AD, BD, CD, D. Perhaps it will be easier if you read it as: AA, AB, AC, AD, AB, BB, BC, BD, AC, BC, CC, CD, AD, BD, CD, DD. In fact, with 3 steps we have: AAA, AAB, AAC, AAD, ... DDD. And so and so, it's the same as thinking of numbers in base K. So for C = 3, if we want positions that cover as many initial Gs as possible then we want the positions that have ABC and DAA (or DAB or ADC, anything containing a D). You can get the position index by converting from base k to base 10. This explanation is probably very bad. Sorry, I can't do better without drawings.
long translate(vector<int> digits, int K)
{
long res = 0;
long p = 1;
for (int i = 0; i < digits.size(); i++) {
res += p * digits[i];
p *= K;
}
/*for(auto x: digits) cout << " " << x;
cout << " -> "<<res<<endl;*/
assert(res >= 0);
return res;
}
list<long> solve(int K, int C, int S)
{
list<long> res;
int p = 0;
while (p < K) {
vector<int> digits;
for (int i = 0; i < C; i++) {
if (p < K) {
digits.push_back(p);
p++;
} else {
digits.push_back(0);
}
}
res.push_back( 1 + translate(digits, K) );
}
if (res.size() > S) {
//assert(false);
return {};
} else {
return res;
}
}
Final results
As I was typing, the round ended, let's check the final results...
All my large solutions were okay. But tons of people had them okay as well. I am barely in position 1246. That's pretty low, but I did start the round 15 hours late... (excuses)
Thursday, February 18, 2016
Opposite Forces [v4]
I should really post here more often. Here goes a level presentation:
This trick can only clone the object you are holding while entering the door. So it works at most once. So we only have access to 4 objects.
All that we need is to move all three objects currently at the bottom to the top. This is not as hard as it sounds. P-switches can be thrown upwards and Mario can take the Pow block with him.
Now all that we need to do is put a Pow block on top of a yellow block. Then press the P switch. The Pow falls on top of the conveyor belt. Be ready to drop the other P switch on the other conveyor belt.
If you time things correctly, the two objects will meet at the same time:
Now all is ready, you can get to the the center area, take that pow block and drop it below the door.
Now we just need to find a way to enter that door while a P switch is active. It's not that difficult really. If you return two steps back, just hold the Pow block and press the P switch next to the Pow block, since P-switch stops the Conveyor Belt, the other Pow will not fall, this allows you to drop the pow block on top:
Hope it was fun.
It's a tough one-screen puzzle. Currently rated super expert with 1% completion rate. The following explains how to solve this level. If you'd like to try it on your own you should avoid reading. You can also stop reading after each new step so you can try starting solving on your own at that point. There are other solutions that need extra dexterity, but this is the one I initially intended.
Going to that door
There's 3 sets of doors. The door on top of the lava bridge connects to the door at the top. The two P-doors (seen as outlined rectangles) are, of course, connected to each other. There is also the door at the center that takes to the final area. The objective of the level is to be able to enter this door AND also have an active P-switch so that the P-doors can be used and you can reach the Axe.
I recommend first simplifying the level. Forget about the P-doors. Our first objective is to learn how to reach the door at the center so that we can reach that area next to the Thwomp.
Pipe object cloning
If we plan to enter that door, it appears that we need a bunch of objects below it so that Mario can stand on them and enter the door. There seems to be a notorious lack of those objects. The distance from the ground to that door is 7 squares. And counting the P switch and Pow from the two pipes, we only have 3 objects available. Something is strange here.
The first mechanic we should learn is that we can "clone" objects that come out of pipes by using doors. Hold an object, and enter the top door:
This causes you to leave holding a P-switch, but the interesting thing is the Pipe spawns another P-switch.
This trick can only clone the object you are holding while entering the door. So it works at most once. So we only have access to 4 objects.
The door and the conveyor belt
There are two main conveyor belts and they work in opposite directions. The main mechanic in this puzzle is to take advantage of this so that you can use them to build a 'bridge' between them. Like this:
So you have two objects held above above the conveyor belts and we just need one more object on top of them to enter the door. The problem is that the conveyor belts are of different lengths and speeds so it is non-trivial to put objects on them so that they meet at exactly the same time. This is where the P switch enters. Note that if you use a P switch, there's still three other objects available, enough to build our entrance. The P-switch can stop conveyor belts from moving AND also turn the two yellow blocks into coins so that we can drop objects there so that they meet.
Now all that we need to do is put a Pow block on top of a yellow block. Then press the P switch. The Pow falls on top of the conveyor belt. Be ready to drop the other P switch on the other conveyor belt.
If you time things correctly, the two objects will meet at the same time:
Now all is ready, you can get to the the center area, take that pow block and drop it below the door.
The real Puzzle
Now we just need to find a way to enter that door while a P switch is active. It's not that difficult really. If you return two steps back, just hold the Pow block and press the P switch next to the Pow block, since P-switch stops the Conveyor Belt, the other Pow will not fall, this allows you to drop the pow block on top:
Hope it was fun.
Subscribe to:
Posts
(
Atom
)
