tag:blogger.com,1999:blog-296323752021-04-14T16:26:37.869-07:00vexorian's blogvexorian talks about stuff. Mostly programming or programming-adjacentUnknownnoreply@blogger.comBlogger36013tag:blogger.com,1999:blog-29632375.post-62328031427082478172021-04-14T16:19:00.006-07:002021-04-14T16:21:14.106-07:00Part 1: What I've learned from Kye<p>Recently I've felt a big urge to write about game design. So let me start with a story.</p><p>I was a Bolivian kid in the later 90s whose family just acquired a computer. Something my parents did really well was nurture my love for computers. So I would always convince them to buy me a new Magazine about computers. Back then we didn't even have cybercafes so computer magazines, were the way you'd acquire shareware software. The magazines would come with these CD-ROMs full of software selections you could try out. </p><p>What I loved the most, were the games. Which were pretty rare. Most of the times the CDs would come with mostly utilities like stuff like icon editors (I actually loved to make icons?). But every once in a while, they would come with shareware games. It's strange how, regardless of how many of those I must have tried over the years, there's only a handful that I actually remember.</p><p>One day I found a true jewel. Some guy from the UK made a charity ware game called "Kye", with some really random ideas. You were a green circle, which apparently is supposed to represent the author's dog. There were monsters for some reason. But mostly the soul of this game was puzzles involving blocks. You can play the original 2.0 version for free at <a href="https://archive.org/details/Kye_1020">archive.org</a><br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-y7tba64WEx0/YHdtfEs9oZI/AAAAAAAACHQ/wLCDrHufy4cXRGOpLzLEy--iNyZXePBRwCLcBGAsYHQ/s1099/Selecci%25C3%25B3n_999%2528444%2529.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="865" data-original-width="1099" src="https://1.bp.blogspot.com/-y7tba64WEx0/YHdtfEs9oZI/AAAAAAAACHQ/wLCDrHufy4cXRGOpLzLEy--iNyZXePBRwCLcBGAsYHQ/s320/Selecci%25C3%25B3n_999%2528444%2529.png" width="320" /></a></div>From what I remember, at first I wasn't even able to really beat level 3, but the good news is that there was a level editor. There must have been something about the weird visual style or the simplicity of the level editor that I've made countless of levels. None of them were any good, but in the process I did discover some interesting iterations between the objects. It was also very practical that levels were basically txt files. You could actually "see" the level when editing it with a text editor. I guess the fact that it had 'arcade' elements such a monsters was the main thing that made me want to make levels, it was all about obstacle courses back then.<br /><h3 style="text-align: left;">Kye's gameplay<br /></h3><p>If I were to make the simplest Kye level that explains what it is about, I would make this:</p><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://lh3.googleusercontent.com/-kv0EtEikNrk/YHdwLWMvF_I/AAAAAAAACHY/nJxShArNfrMgW2hQfdW0FVGZ2ky4K4C-ACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528445%2529.png" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="237" data-original-width="392" height="193" src="https://lh3.googleusercontent.com/-kv0EtEikNrk/YHdwLWMvF_I/AAAAAAAACHY/nJxShArNfrMgW2hQfdW0FVGZ2ky4K4C-ACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528445%2529.png" width="320" /></a></div>The goal of Kye is to get all the "diamonds" (those blue things). You get diamonds by moving the player character (green circle) to their cells. You move the player character using the cursor keys (You can also use the mouse if you are a horrible person). But what's interesting here is the yellow squares with a red arrow drawn on them. These arrow blocks will always attempt to move towards the direction indicated by the arrow, and will only stop when something is blocking them. In this case, the diamond in the middle is blocking them. But if you were to grab the two right-most diamonds, a thing would happen:<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://lh3.googleusercontent.com/-Dc1KKEdpb_w/YHdxC5pvigI/AAAAAAAACHg/f6zpyRMJXg4vtA2LU79DarRSbqUqL7RsACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528446%2529.png" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="240" data-original-width="411" height="187" src="https://lh3.googleusercontent.com/-Dc1KKEdpb_w/YHdxC5pvigI/AAAAAAAACHg/f6zpyRMJXg4vtA2LU79DarRSbqUqL7RsACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528446%2529.png" width="320" /></a></div>Now, Kye (the player) <i>can</i> push arrow blocks, but in this case it would only bring more problems:<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://lh3.googleusercontent.com/-rplUoO78Kv4/YHdxW7HhE-I/AAAAAAAACHo/BO1yD-0El2U7ti6aRnqaaPkOCECRuMQQACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528447%2529.png" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="253" data-original-width="409" height="198" src="https://lh3.googleusercontent.com/-rplUoO78Kv4/YHdxW7HhE-I/AAAAAAAACHo/BO1yD-0El2U7ti6aRnqaaPkOCECRuMQQACLcBGAsYHQ/Selecci%25C3%25B3n_999%2528447%2529.png" width="320" /></a></div>Kye is trapped. Kye should have started with the left-most diamond and this wouldn't have been a problem.<p></p><p></p><p>All of kye involves making this sort of choice. There are many elements in the game that just make this choice more interesting. Some blocks can make the arrow blocks rotate. Other blocks are just normal static blocks that you can use to stop arrow blocks or do other things. There are "black holes" that will just destroy anything that you push onto them or any arrow block that moves towards them. There are "Bouncers" that can push any block, including the arrow blocks. Rounded arrow blocks slide diagonally when they hit another rounded object. Clock blocks will constantly create arrow blocks. And the magnets can allow you to bypass some of these complications, or they can also stick to you in a way that traps you in a similar way.</p><p></p><p>But the Coolest thing about Kye, just happens to be the main thing you learn from the solution to level 3, the level that I initially had no idea whatsoever how to fix. And it is that Kye is a real time game. The arrows, the bouncers and the monsters won't wait for your moves, they have a life of their own.</p><p>This is what happens when you attempt to solve Level 3 without thinking: <br /></p><p></p><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen="" class="BLOG_video_class" height="266" src="https://www.youtube.com/embed/bvMGrYOF1fs" width="320" youtube-src-id="bvMGrYOF1fs"></iframe></div><br /><br />So you can't really get that top-left diamond because the arrows will block the path. What now?<p></p><p>The trick to solve this (and maybe if you really want to give this game a try, you should give it a try before reading this) is to plan ahead and make sure the bouncers are synchronized correctly. The bouncers will clean up the arrows by themselves.</p><p><br /> </p><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen="" class="BLOG_video_class" height="266" src="https://www.youtube.com/embed/LqDwS6cDJBk" width="320" youtube-src-id="LqDwS6cDJBk"></iframe></div><br /><p></p><p><br />And this, this is the power of Kye. There's 20x30 cells, which at first may seem like a huge amount of cells for this style of a puzzle game, but the reality is that the level designer will need plenty of room to be able to build of sorts of <i><b>machines, </b></i>combining the various elements. These machines are the real core of Kye's gameplay. That's why it is a real-time and not turn-based. </p><p> This is ultimately what I've learned from Kye. It's all about the machines. Different gameplay elements can make something bigger than the sum. But it all requires some thought about what the elements will be. If done correctly, levels can take a life of their own.<br /></p><div class="feedflare">
<a href="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?a=GNoy_5vRM58:G2zaJ6W5IRo:w2ZXrbNjBKQ"><img src="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?i=GNoy_5vRM58:G2zaJ6W5IRo:w2ZXrbNjBKQ" border="0"></img></a>
</div><img src="http://feeds.feedburner.com/~r/VexorianProgrammingContestBlog/~4/GNoy_5vRM58" height="1" width="1" alt=""/>Unknownnoreply@blogger.com0http://www.vexorian.com/2021/04/part-1-what-ive-learned-from-kye.htmltag:blogger.com,1999:blog-29632375.post-41812683117081559712021-03-20T13:05:00.002-07:002021-03-20T13:05:42.024-07:00Undusting the old blog. Some changes to come.<p>It's been a long couple of years. The last year was particularly long and I'd like to reopen this blog and site. There's some new things I want to share. The focus will no longer be programming contests. Although I do plan to participate in some of them in the short term, just because I participate in something it won't mean I will write explanations for that contest.</p><p>I want to have a voice for computer-related talk. So first, some recaps of what happened since the last post in.... 2018! </p><ul style="text-align: left;"><li>The real job meant that I am much less likely to be able to participate in a contest and I haven't really practiced much. In fact, my C++ skills are really dusty. My performance in programming contests has been abysmal. And that's one of the reasons I haven't been very open to talk about it. If I kept blogging like before my posts would go like "I opened 500-points problem I thought I had it but there was a bug, and I didn't have time to submit 250"</li><li>I kept improving <a href="https://twitter.com/CloudyConway">Cloudy Conway.</a> Or maybe I made it worse? Because its twitter account is far less popular now than it was back in 2016.</li><li>2019 Was the year I returned back to Super Mario Maker, due to the release of the Nintendo switch version. Since then I've been using it as a creative outlet and to practice my level design muscles. Recently I've released a <a href="https://www.youtube.com/watch?v=B-GneSWmDHE">Super World</a> containing 31 puzzle levels. Some of which are good. <br /></li><li>During the Pandemic, I decided to start a Plex server (Plex is a software for making a media server so you can organize your media library and also watch your media in any device that runs their app). One thing led to another and I ended up forking a project that was called "pseudoTV". The name of the fork is "<a href="https://github.com/vexorian/dizquetv">dizqueTV</a>" . It's a tool to creat e your own fake TV channels out of the videos (and audio files) in your plex library.</li><li>And now in 2021 I decided to quit Mario Maker and instead .... Uh Oh , that's a long story talk I'll leave for tomorrow.<br /></li></ul><p>Recently I've restarted my twitter account. The new official way to find me is <a href="https://twitter.com/vexorian_">@vexorian_</a> in twitter.com<br /></p><div class="feedflare">
<a href="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?a=3fGlu-VNfwY:8FHefdAeGww:w2ZXrbNjBKQ"><img src="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?i=3fGlu-VNfwY:8FHefdAeGww:w2ZXrbNjBKQ" border="0"></img></a>
</div><img src="http://feeds.feedburner.com/~r/VexorianProgrammingContestBlog/~4/3fGlu-VNfwY" height="1" width="1" alt=""/>Unknownnoreply@blogger.com0http://www.vexorian.com/2021/03/undusting-old-blog-some-changes-to-come.htmltag:blogger.com,1999:blog-29632375.post-29232527116073440672018-04-07T20:11:00.002-07:002019-01-09T09:23:34.318-08:00Google Code Jam 2018 Qualification Round<p>That was certainly an interesting codejam. One that was marked by the question "Do I even want to do this?".</p> <h2>The new system</h2> <p>Turns out Codejam is using a different system and rules than before. <a hre='https://twitter.com/fakevexorian/status/982395863535415299'>I don't really like it</a> Click that link if you want to see my live reaction after finding out at 7:00 PM last night. My plan for the weekend was to possibly spend the whole Friday night and Saturday working on the code jam and prepare a cool blog post about it with explanations and all for old time's sake. That didn't work out.</p> <p>I already said too much on those tweets, but what I just want to be clear about is: The Codejam Qualifaction was not just a contest. It was an event. It was always really great to see what happened. It always has the most massive number of participants ever. A big part of this is the idea that some coders might try some bizarre things. Solve the contest in ... Assembler? <a href='http://www.vexorian.com/2015/04/google-codejam-2015-qualification-round_45.html'>Or that year I used a programming language I designed myself</a>. Looking at the score board and filtering it so it only shows you people you know (this option is gone). <a href='http://www.vexorian.com/2012/04/to-solve-google-codejam-hall-of-mirrors_1616.html'>And sometimes there would be an epic problem that keeps you busy the whole day</a>.</p> <p>But the worst of all is the fact that (one of) the biggest programming competitions just got way less accessible than it was. Telling people that they can just use any programming language was great, but we lost that.</p> <h2>Do I even want to do this?</h2><p>So I am not even sure if I want to participate in the contest. I know how to solve problem A, but I can't even find a vital bit of info about the new rules: What is the CPU of the servers where our code runs? So this sounds suspiciously like one of those badly made ACM contests:/ do I even want to participate? I no longer have so much free time as before. I barely have time in the weekends to rest. So a Saturday is not something I can just spend in some contest if it doesn' sound at least a bit fun. And the prizes are as low as ever. I decide that at least for Friday I am not going to bother.</p> <h2>The last few hours - Problem B</h2><p>So okay, so I am a bit curious about how the codejam is going and I accidentally read problem B and figure out that it is an extremely easy problem.</p> <p>There is a badly made sorting algorithm. Taking an array `V`, it finds two indexes `i`, and `(i+2)` such that `V[i+2] > V[i]`. In that case, it takes the part of the array: `(V[i],V[i+1],V[i+2])` and reverses it `(V[i+2],V[i+1],V[i])`. It repeats this until it cant find any more such `i`, and `(i+2)` pairs. This algorithm can't always sort the array correctly, and given an input `V ` we are supposed to predict the part where the algorithm is going to fail. If it is going to fail, we have to find the first index that is not sorted correctly. For B large the number of elements can be up to 100000.</p> <p>The algorithm is `O(n^2)` so for the large version of the problem we can't just simulate it. The key of the problem is to notice that after reversing `(V[i],V[i+1],V[i+2])` into `(V[i+2],V[i+1],V[i])`, the position of `V[i+1]` is not going to change. So the operation is the same as swapping `V[i]` and `V[i+2]`, which are the elements we compared. This means that there are actually two independent <i>partitions</i> of the array. The elements with even indexes will never interact with the elements with odd indexes. So imagine the array `[6,5,4,3,2,1]` : It has two independent sub-arrays: `[6,..,4,..,2,..]` and `[5,..,3,..,1]` and in these sub problems, all you can do is swap consecutive elements. This means that the two sub arrays are being sorted with normal bubble sort. And eventually the bubble sorts will end running and we will get: `[2,..,4,..,6,..]` and `[1,..,3,..,5]` and when we put the two sub-arrays back into the big array we get: `[2,1,4,3,6,5]` and it is clearly not sorted. So to solve this problem, we just split the array into two sub-arrays, one with the even indexes and one with the odd indexes. Sort the two arrays and put them back together. If the result is sorted, then all is fine, else we return the first index where it breaks.</p> <pre class='cpp'><br />// get the sub array with parity (0 or 1)<br />vector<int> getv(const vector<int> &V, int parity) {<br /> vector<int> r;<br /> for (int i = parity; i < V.size(); i += 2) {<br /> r.push_back( V[i] );<br /> }<br /> return r;<br />}<br /><br />// mix two sub-arrays back into one large one:<br />vector<int> mix(const vector<int> &v1, const vector<int> &v2) {<br /> vector<int> V;<br /> for (int i = 0; i < v1.size() + v2.size(); i++) {<br /> V.push_back( (i%2 == 0)? v1[i/2] : v2[i/2] );<br /> }<br /> return V;<br />}<br /><br />string solve(const vector<int> &V) {<br /> // split<br /> vector<int> v1 = getv(V,0);<br /> vector<int> v2 = getv(V,1);<br /> // sort<br /> sort(v1.begin(), v1.end());<br /> sort(v2.begin(), v2.end());<br /> // merge again<br /> vector<int> v3 = mix(v1,v2);<br /> // check<br /> for (int i = 0; i+1 < V.size(); i++) {<br /> if (v3[i] > v3[i+1]) {<br /> return to_string(i);<br /> }<br /> }<br /> return "OK";<br />}<br /><br /></pre> <h2>Problem C is interactive</h2> <p>Okay ... so apparently I am participating in this. I am too bored to bother with A, so I open C. This is an interactive problem. You are given a 1000 x 1000 grid and want to paint at least `A` cells (in the easy version, `A` is 20 and in the hard version, 200). The objective is that the bounding box of all the painted cells should not contain any unpainted cell. And the catch is that when you pick a single cell to paint, the system is actually going to pick one of the 9 squares in the neighborhood of the cell you picked and paint that one. Even if the cell is already painted, if the system picks it, it will paint it again and waste a turn. You have only 1000 turns. Of course it picks any of the 9 squares in the neighborhood with 1/9 probability.</p> <p>So okay, this is an interesting thing that we wouldnapos;t have been able to have in the old system (or maybe we could, by making the system expose a public API that interacts with your program?). At least it is a bit interesting. The solution is to come up with a strategy and prove that the probability that it needs more than 1000 turns is very low. </p> <p>My solution works by making it into a linear problem. Instead of worry about 2D rectangles, you go in a straight line from bottom to top. Imagine we keep giving the system the order to paint at point `(x,y)`. Eventually, all 9 points around it will be painted. Once this happens, you can start returning `(x,y+3)` and paint another `3 x 3` square. And keep repeating. Until you/apos;ve painted enough squares. The result will always be a perfect rectangle.</p> <p>The only catch is to calculate that this will tend to require less than 1000 steps. Actually, due to the random nature of the problem, there is always a probability that for some reason it could pick the same point 1000 times, but that is a very improbable thing.</p> <p>So let's calculate the expected value for the number of turns we need before filling a complete 3 x 3 square. The number is between 25 and 26. To paint at least 20 squares, you would need 3 squares of `3 x 3` in total. That means that the expected number of turns you'll need is 228, which is pretty reasonable. Of course, the expected value is not the same as the probability it will work in less than 1000 steps. But a) It is easier to calculate and b) The expected value is designed to give us a good estimate. it's the average number of turns we will need, and because everything is so random, it would be a bit crazy to expect that the number of turns will get much larger than 228. Definitely not up until 1000...</p> <p>But that's not the solution I tried. Mine is a bit smarter, no need to wait for the whole 3x3 square, you only need to wait for the bottom row of 3 square cells. Once it is full, we can start trying a square higher. So basically, we start with `(x,y)`, once the row of 3 cells bellow `(x,y)` is full, we start trying with `(x,y+1)` and so and so. We only need to figure out a good ending condition for this. If filling the current `3x3` square surrounding the current `(x,y)` is enough to complete the requirement for `A`, then we can stop</p> <p>My calculations told me that the expected number of turns will be around 106 for `A=20` and more than 1200 for `A=200`. So it would pass the easy but not the hard problem. But in fact my calculations where over pessimistic and it passes the hard version of the problem as well.</p> <p>You may be wondering how the hell did I calculate all of this? Well, here is an example: Imagine that we will keep printing `(x,y)` until the bottom row of `(x-1,y-1)`, `(x,y-1)` and `(x+1,y-1)` are all painted. What is the expected number of steps we need to perform?</p> <p>There are 9 cells in total that can be painted by our `(x,y)` move but our objective is to paint 3 of them. The function `f(t)` will tell us the expected number of turns before we paint `t` specific cells (the other ones don't matter.</p> <ul><li>For `f(0)` : There are 0 cells that matter to us, so we don't need to paint anything, all is ready.</li><li>For `f(1)` : We need at least one turn. there are two possibilities: <ul><li>With probability `1/9`, we painted the correct cell and there are now zero more cells to paint. The expected number of steps will be `1 + f(0)`</li><li>With probability `8/9`, we painted a cell that doesn't matter so there is still one special cell. The expected number of steps will be `1 + f(1)`</li><li>The total is: `f(1) = (1/9)(1 + f(0)) + (8/9)(1 + f(1))`, note the recursion, but the recursion is not a problem, just consider `f(1)` as a variable, like `z`:</li><li>Solve the equation `z = (1/9)(1 + f(0)) + (8/9)(1 + z)`, the result of `z` will give us `f(1)`. </li></ul> <li>Then we can use that result to calculate `f(2)` (it's the same logic), and so and so. By filling the values of `f(t)`, I could find that it takes around 16 turns before we fill the bottom row and 25.something steps before filling the whole square. The reason this estimate is too pessimistic is that I don't consider that after filling the bottom row, there will be many squares in the `(x,y)` neighborhood that are painted, which increases the chance that future iterations of `y` are going to receive less work to do.</li> </ul> <p>Turns that the problem came with a tester tool to interact with your program locally. But I didn't notice until after solving the whole problem and testing manually multiple times :/</p> <h2>Problem D and A</h2><p>A is very easy but greedy and I am not feeling like explaining it right now. D was all about geometry, and I honestly was feeling a bit lazy. Do I really want to spend all that much time solving and specially debugging a geomtry problem? Not really. So I skipped it.</p> <p>Turns out Stack Overflow has a nice explanation: https://twitter.com/fakevexorian/status/982800480886775808 , but the question was posted during the contest.... So ... why bother even If I went through the problem of solving this, no one can tell if anyone solved the problem on their own or because they found the stack overflow thread? <h2>That's it</h2><div class="feedflare">
<a href="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?a=EEPw98y_Ft4:IBKNMreMokI:w2ZXrbNjBKQ"><img src="http://feeds.feedburner.com/~ff/VexorianProgrammingContestBlog?i=EEPw98y_Ft4:IBKNMreMokI:w2ZXrbNjBKQ" border="0"></img></a>
</div><img src="http://feeds.feedburner.com/~r/VexorianProgrammingContestBlog/~4/EEPw98y_Ft4" height="1" width="1" alt=""/>Unknownnoreply@blogger.com0http://www.vexorian.com/2018/04/google-code-jam-2018-qualification-round.html