Tuesday, January 31, 2017

How I Imagine Daily Life of Yugioh's Developer

1. Gemini Monster.

Game Designer: Hi dev, you still remember those normal monster?

Dev: yeah, sure

Game Designer: I'd like to add a few of them.

Dev: Ok, doesn't need lot of code.

Game Designer: Here's the tweak.. It is first treated as normal summon, and then when it is on the field you can normal summon it again to make it an effect monster. Off course, when it dies, it's a normal monster again.

Dev: Wat...

Conclusion: Yeah, let's make an effect monster with an effect that treated as normal monster and can be summoned twice.

2. XYZ Summon

Game Designer: We need new summon mechanic

Dev: OK.

Game Designer: let's call it XYZ summon so the XYZ monster, should first be in the extra deck.

Dev: Ok.

Game Designer: well, you can summon it similar to synchro and fusion, except when it is summoned, you put the materials below it.

Dev: That's a pain.

Game Designer: Oh and monster that become material doesn't treated as leaving the field by the way, just call it they are in limbo space.

Dev: ...

Game Designer: And when the material is sent to graveyard, they are not considered to be sent from field as well.

Dev: ...

3. Pendulum Summon.

Game Designer: Let's make a monster that could be treated as spell card as well!

Dev: Watever.

Monday, January 9, 2017

Facebook Hacker Cup Qualification Round - 2017

This is probably the first time I've ever solved all problems in Programming Competition. So, as to commemorate the event, I'm writing my solution about the problems.


Problem 1:
you can view it here.
question: given N percentage of a circle with radius 50 and center at (50, 50), determine whether point at (X, Y) is within that circle or not.

Answer:
This problem is quite obvious, in this problem we just need to figure out the degree and distance of (X, Y) from (50, 50).
The distance can be measured using basic trigonometry
r = sqrt(dx^2 + dy^2)
The degree can be measured with
arccos(dx / r)
Though we'll need a little tweak based on which quarter it's placed on.

tag: Mathematic, Trigonometry, Implementation

Problem 2:
can be viewed here.
problem is too long to be explained, checkout that link.

Answer:
This is a problem where, if you feel confused, just try to implement it.
The solution here is just to order the items in the descending order (or ascending if you're using stack).
1. Pick the most heavy item (last in the ascending ordered stack), we will call it X
2. Based on that item, also pick n - 1 item starting from the lightest where n = Math.ceil(50 / B)
3. keep doing it, until all (X * n) < 50.

for example if our items:
[50, 30, 30, 10, 6, 5, 4, 3, 2, 1, 1, 1]
our pick will be:

  • 50
  • 30 and 1
  • 30 and 1
  • 10 and 1, 2, 3, 4
  • 5 and 6 is left, we can ignore them and just assume that he has delivered it in the previous delivery.


tag: Greedy

Problem 3:
details can be viewed here
tl;dr: given N dice with M side, figure out the probability that the sums of all dice is greater than X.

Answer:
Ok, this one, is harder (Actually, I literally figured out the answer right after I wake up the next day lol).

The thought process:

Ok, I start with: ... I know this is probably binomial distribution, normal distribution, pascal triangle or something... but I couldn't figure out how I can use it to solve this problem?

Pascal Triangle for 2 sided coin.
After a few times of thinking..., well doesn't hurt to get some insight, let's write some simulation... probably something like this?

Random Dice Generator.
For non-rubyist, that code basically create 100.000 simulation throwing <dice>-sided dice <n>-times. and get the sum of those dices.
Value distribution for throwing 3-sided-dice two times.
Ok, that looks exactly like 1, 2, 3, 2, 1
Value distribution for throwing 3-sided-dice three times.
Now this one is harder, it looks like 1, 3, 6, 7, 6, 3, 1, but I'm not really sure.

What if instead of throwing random simulation, we look exactly at the actual possible values?
Simulation2
Calculating the frequency of each value from that code get us exactly: [1,2,3,2,1].
Neat, the first one is correct, what about the 2nd one?

Let's just change our function a bit.
Fuck reusability, reliability, readability, and speed lol.
Calculating the frequency of each values gave us: [1, 3, 6, 7, 6, 3, 1].
Whoa, neat!

Now how can we generalize these values? By creating the Generalized Pascal Triangle
I don't really know how I get it, this is the point where it just struck your head or something.

Pascal Triangle for 4-sided-dice

Pascal Triangle for 6-sided-dice


How do we generate these triangles?
For 2 sided coin, everyone probably knows that:
pt2[x] = pt2.parent[x - 1] + pt2.parent[x]

or, if you're more mathematic wired, we can represent it like this as well:
pt2[x] = pt2[x - 1, y - 1] + pt2[x, y - 1]
So, how about 4 sided dice?
It's not much different.
pt4[x] = pt4[x - 3, y -1] + pt4[x - 2,  y - 1] + pt4[x - 1, y - 1] + pt4[x, y - 1]
Notice the formula?
yeah, it is:
ptN[x] = sum(ptN[x - N + i, y] for i in xrange(1, N - 1)) 
legends: ptN[x, y] = Pascal Triangle for N sided-dice at (x, y)
can we optimize this calculation? yeah, we can, but it's not necessary, (be warned, I don't actually implemented this, so I can't guarantee the formula, it might have an off-by-one-error)
ptAN[x, y] = ptAN[x - N + i, y] + ptN[x, y]
legends: ptAN[x, y] = Pascal Triangle Accumulative Value.
it's probably also more useful to store its accumulative value instead of its actual value, so my array would look like this:
Pascal Triangle (Accumulative) for 4 sided dice.
This way, if I were to figure out the probability of X >= X' when you throw 4 sided dice with value (0, 1, 2, 3) 2 times.
I just need to calculate:
P(X >= X') = ptA4[X', 2] / ptA4[0, 2]
Notice that I said the value of our dice is (0, 1, 2, 3) while the value of dice in the problem is (1, 2, 3, 4), so we should also tweak our implementation a little. The good part is it is trivial, but the bad part  it's also where the bugs may arise from.

As for closing remarks:
I personally consider these problems a good one actually, or not, it's just that I like these kind of question because it fit my strong point.

Finally, have this gem from 2011.


Monday, January 2, 2017

Ruby, Metaprogramming, and LinearEquation Solver


Metaprogramming
Metaprogramming is a programming technique in which computer programs have the ability to treat programs as their data. It means that a program could be designed to read, generate, analyse or transform other programs, and even modify itself while running. ~ Wikipedia.
In Ruby, there's an enormous amount of function, that would help you writing a program, that could dynamically modify itself.

Most common example is:
  • define_method(methodname, &block)

    define_method is a method that take two argument, a symbol or string as the methodname, and the block process of what it should do.

    for example, if I have a class, that refer to a user table in mysql with field name, email, and password, i can define 3 new method dynamically, namely find_by_name, find_by_email, and find_by_password with the following code: (not accurate, but you get the point)


  • method_missing?(methodname)

    method missing is a method that just accept a string or symbol argument, this is a method that allows you to handle any arbitrary method when it is called.
    Suppose your User have a field name, email, and password, and then there's user info where we put his address, facebook_id, phone_number, and so on. Now you might want to write your program so that a User object may receive any method in UserInfo, well, it'll probably be written like:

Alright, so we've seen how we can write a program that could modify itself mid-runtime, or defining what is not defined. Since we've seen how we write a program that "write" itself, it's also possible for our program to read its own source-code.

Meet the "source-code".

In the next example, We'll look how we implement a linear-equation solver using metaprogramming, (not really useful since then, our equation is hardcoded, but why not?).

Look at the following example of how we define our equation:

Guess what, there's no variable x, y, or z in program, we also didn't create new behavior for Fixnum instance by defining .x, .y, or .z method, and of course we doesn't use method_missing? as well.
Would it then throw error? well, no, not until it's evaluated.

If the codes will be an error when it's evaluated, then just don't evaluate it ~ Ramadoka:2017 


 Which is exactly what I'll do.

Let's take a look at what it does

what magic did we found there?

you might guessed it correctly, it's the @eq.source 

that magic, allows us to read the source-code of our function, and since ruby is dynamic-typed interpreted language, it doesn't know whether an object would respond to a method or not, until it is evaluated, so yeah, there won't be a compile time error, as long as our-code passed the lexical analysis.

Now, that we have done it, we basically just said:

"ruby, kindly, don't parse my code, let me handle that part myself."

Which is pretty meta for my taste...

That marks the end of our topic about metaprogramming, but if you're curious about how the code of LinearEquation works, please feel free to continue along.

Linear Equation Solver

The first step is defining the requirement (can be adjusted later), how do we want to say 3x + 2y + z = 10
since apparently 3x + 2y + z = 10 doesn't pass the lexical analysis (or in other words, ruby know it's not a valid program even without running it).

In this example I'm defining my requirement would be:
3.x => 3x
- x => - x
+ 2 = 10 => not valid (too lazy to reduce to minimum state)
+ z = 10 => + z = 10
+ -x => apparently work as intended
- -x => not working correctly.

If the code doesn't match the requirement, you can either
a) change the code so it meet the requirement
b) change the requirement so it match the code

So Yeah, since this is just a proof of concept, I'm picking the 2nd option.

How do we handle the parsing?

Regex, Regex is always the answer, as anonymous programmer said:

A programmer has a problem, and then he said, I know, I'll use regex.
Now he has 2 problem.

Ok, as you've seen regex is not the silver bullet to handle parsing, we probably need a full-blown parser, but implementing a parser might take 10x time longer than it is, so let's live with the bug now.

as buggy as it is, this regex handles the filtering of a parameter for our basic necessity:
/[+-]* *(?:\d+\.){0,1}[a-zA-Z]+/
by using string.scan using this regex, a 3.x + y + 2.z
will become ["3.x", "+ y", "+2.z"]

and then, there's two other regex to parse our parameters, it can be either:
/(?<multiplier>\d+)\.(?<name>\w+)/
if it start with the multiplier (e.g: 2.x)

or, it can also be:
/(?<multiplier>)(?<name>[a-z]+)/)
if it doesn't have multiplier (e.g: y)

once we have parsed 3.x - 2.y + z = 10 into
[3x, -2y, 1z] and [10]

We will use Matrix Multiplication to solve the equation:

as it turns out, our equation can be rewritten as Matrix Multiplication as: 

Aaaand, that's it, I'm out of material. Thanks for reading this scientific nonsense.

For the full version of the LinearEquation Implementation you can see it here.

Does this post lacking madokaism?, No Longer!
lahirnya juru selamat