Pages

Sunday, September 6, 2015

Codeforces: Xenia and Hamming

Here is a coding puzzle I wanted to formalize due to clarity for myself. If you're into number theory this is your thing.

Problem statement: http://codeforces.com/contest/356/problem/B

Solution: First observation which is easy to make is that it is easier to calculate where the characters match instead of mismatch and that we do not need to compute n*x and m*y. This is true:

\( (n \cdot x)[dx + i \cdot |x|] = x[(dx + i \cdot |x|) \mod |x|] \)

Therefore, we want to count how many (dx, i) exist so that x[(dx + i*|x|) mod |x|] = y[(dx + i*|x|) mod |y|] holds. Since i*|x| mod |x| == 0, it is actually:

\( x[dx] = y[(dx + i \cdot |x|]) \mod |y| \)

Lets fix dx and see how i*|x| behaves within modulo |y|. This part requires some simple algebraic knowledge. i*|x| is trivially a repeating sequence within modulo |y|. But how does that repetition look like?

If i*|x| = t (mod |y|), then i*|x| - j*|y| = t, for some j. Using bezouts identity we know that t = gcd(|x|, |y|) * k, for some k.  This means that all sequences make jumps of length gcd(|x|, |y|). With this information and the frequency of all characters within the second string for each repeating sequence, an efficient algorithm can be developed.

Sunday, August 16, 2015

Targ.io -- a new HTML5 game!

Over the course of the last 2 months I have developed with a friend a new HTML5 game. It supports multiplayer and is meant to be very simple. You jump off of bricks and try to get as high as possible.

It really showcases the power of nodejs + socket.io. With enough optimizations, we were able to get a stable frame-rate even though all the computation is done on the server.

Interested to try it out? Go and play at: TARG.IO !


This preview should give a good insight about the idea behind:






Saturday, May 2, 2015

Exam season done and... The progress on EvyMap

Onwards with EvyMap (www.evymap.com)! Now that I have been done with my exams for a month, I have invested some time in EvyMap's progress. Throughout that time, I have thought a lot about the way EvyMap should function. This made me make a slight "change of course". The biggest change is the extension of the chat based system to a thread based one.  Therefore, people can create posts on a location and other people can then reply to it.

What that means for the user?
With this system, the usage of EvyMap should feel more natural. You enter a location, get some conversations offered, and you can join, if you want. 

How does this work geographically? 
Your post is going to be shared on the location of your choice. A person doesn't have to be necessary on the same location as your post is in order to see it. It is merely necessary for the other person to be close to your post.
A system has been integrated to adapt to the load on the map. Densely active areas will get the conversations that are more recent and close, while inactive areas will get those further away and less new. 

cool upcoming feature: Spreading of posts! Based on the activity your posts have, they will be able to spread geographically to more locations. 

What has been done further?
  • The design has been greatly adapted.
  • Small description added on the index page.
  • Main page displays well on smaller devices now (phones, etc.).
  • Self-adapting fetching of replies. Ajax calls are adapting their cycles based on activity.
  • Image uploading fixed for profile pictures: images of all proportions are now supported. 
  • The user-search bar is now using trigram matching: greatly improved search.
  • Some more XSS fixes.
  • Move from MySql to Postgresql
  • Code was greatly refactored and a new pipeline for producing Javascript has been made: Grunt is used together with Typescript. Minified Javascript is also produced on the production side -> performance up!
ToDo:
  • Fix more known XSS vulnerabilities.
  • Add bcrypt for password hashing in order to keep the passwords safe.
  • Adapt the post-fetching mechanism to the above load adaption algorithm.
  • Enable manual extension of the search area in time and space. 
  • Automatic user fetching while typing (currently, pressing enter is required).
  • Further adaptation of the reply fetching mechanism is needed.
  • Notifications on replies.
  • Access to made posts through the profile page.
  • Read-access without an account.
  • Delete/edit post/reply.
  • The cool upcoming feature :)

Monday, January 19, 2015

Updates on EvyMap

My first update on EvyMap's state (www.evymap.com)! First, a "thank you" goes to Martin Thoma for pointing out some needed attention over the security aspects. The same applies to some of my friends at my university, KIT. The updates:
  • Mechanisms for preventing XSS attacks implemented.
  • Mechanisms for preventing MySql attacks implemented.
  • Made the website work with utf-8.
  • User input goes through stricter validation.
  • The dynamic loading of all the images is made faster.
  • Birthday picker added within account settings.
  • Password resetting added.
  • Fixed scrolling within the message window.
  • Various pop-up messages have been integrated for keeping the user informed about the actions the server does.
  • Design within Firefox and Internet Explorer fixed.
The cream on top of all: A neat functionality that was recently added, illustrated with the following link:
After logging in, this will get you directly to New York and set you up for chatting.

Known issues:
  • Some random birthday gets assigned to the user upon registration.
Again, there is work to do, but we're progressing to some more "stable" version of this website! I'm always thankful for any advice or suggestion!

Thursday, January 1, 2015

Early version of EvyMap! Making "chat on a map" possible.

It has been a year since I've decided to play around with web-development. I started this journey by having a vision about a project: make people able to chat on a map. I thought that it would be interesting to have a sense of visual proximity with the person one talks to. I also used this as an opportunity to dive into new technologies.

How it works: you select a point on Google Maps and set your radius. That's it! 
You will receive all the messages that are being posted within that circle and the messaged you send will be received by the circles that have your point inside. True, asynchronous chat is possible -- this remains to the user to tweak in order to make it synchronous (setup of point/radius).

The link to the website: www.evymap.com.

Here is a preview of the main page:


There is still a long road ahead before this works stable. Top priority now: give users error messages for failing activities. This is an implicit warning: you may not get stuff like "wrong login information" :)
Also, works very bad on phones.

Thankful for any feedback!