tag:blogger.com,1999:blog-34344880267629651852020-02-28T15:00:01.732-08:00Damir FerizovicAnonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3434488026762965185.post-29516124027632742462016-02-14T07:27:00.002-08:002017-09-20T10:33:08.541-07:00#4 GeoChatThis is like "modern" EvyMap, a project I worked on before. GeoChat is a very good example of how much better I have got in developing web stuff. This took me 1 month to create, compared to EvyMap 4-5 months. (for my defense: working on this stuff is just a small hobby of mine).<br /><br />GeoChat was made by taking additional care of the design. The page is fully functional on phones and is designed to be comfortable to use. Currently, the page is tied to one location, given by the user.<br />These are ideally the GPS coordinates, but manual location selection is also possible.<br /><br />An algorithm for automatic content selection was also added.<br /><div style="text-align: center;"><b><span style="font-size: large;"><br /></span></b></div><div style="text-align: center;"><a href="http://geochat.webdash.io/" target="_blank"><b><span style="font-size: large;">http://geochat.webdash.io/</span></b></a></div><br /><div class="separator" style="clear: both; text-align: center;"></div><br />Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-915101342130967802016-02-09T23:44:00.000-08:002017-09-20T10:33:41.338-07:00#3 Curv.ioThis one is a HTML5 remake of the popular game <b>curv</b>. I suppose that I don't need to elaborate much about the game mechanics. We implemented a matching system and a global scoreboard for the active players. Periodically, upgrades also spawn on the map, giving you various advantages over your opponents. The game is also working well on mobile platforms!<br /><br />Link:<br /><div style="text-align: center;"><a href="http://curvio.webdash.io/" target="_blank"><b><span style="font-size: large;">http://curvio.webdash.io/</span></b></a></div><br /><br />Screenshot:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-mkGInuKGN1A/VrrqMeXF6YI/AAAAAAAAB0E/5DdY1c_Im1I/s1600/curv.io.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="207" src="https://3.bp.blogspot.com/-mkGInuKGN1A/VrrqMeXF6YI/AAAAAAAAB0E/5DdY1c_Im1I/s400/curv.io.jpg" width="400" /></a></div><br />Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-87776873548658905852016-02-09T07:14:00.003-08:002017-09-20T10:37:04.884-07:00#2 AudioWarsThis one brought us the first place on a hackathon (theme: gamification). We developed a game that requires one to whistle a popular song in order to destroy asteroids heading to our planet. The best part? Local multiplayer works!<br /><br />The game does not have its own domain, but is still accessible here:<br /><br /><div style="text-align: center;"><a href="https://whistle.webdash.io/" target="_blank"><b><span style="font-size: large;">https://whistle.webdash.io/</span></b></a></div><br />Screenshot:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/--Lc6sb5-Yys/VroCJjSQ4cI/AAAAAAAABz0/sjD44HFck8c/s1600/audiowars.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="205" src="https://2.bp.blogspot.com/--Lc6sb5-Yys/VroCJjSQ4cI/AAAAAAAABz0/sjD44HFck8c/s400/audiowars.jpg" width="400" /></a></div><br />Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-17223681416088999792016-02-08T12:26:00.002-08:002017-09-20T10:37:55.092-07:00#1: noteverse.comThere are several web apps I developed together with a few friends on my university that I failed to share on my blog here. 5 of them, actually. Yeah, crazy... We somehow end up creating things and then we stop pushing the extra mile to see how to market things. At least we know what we need to work on now. :)<br /><br />The first app that I wanted to mention is:<br /><div style="text-align: center;"><a href="http://noteverse.com/" target="_blank"><span style="font-size: large;"><b>noteverse.com</b></span></a></div><br />I believe that this page is amazing for those that want to create some web content in 5 minutes. Currently, there are no "real" private sections, but channels do exist. Once an user occupied some area with his box, no other user is able to take away that place.<br /><br />The amount of boxes a user can create is limited by the amount of credit the user possesses. Visiting the page on a daily basis increases that amount.<br /><br />Here is a screenshot (zoomed out a bit):<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-LwtabGJH19E/Vrj5geV1haI/AAAAAAAABzk/zVtOyYtthQA/s1600/noteverse-preview.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="205" src="https://1.bp.blogspot.com/-LwtabGJH19E/Vrj5geV1haI/AAAAAAAABzk/zVtOyYtthQA/s400/noteverse-preview.jpg" width="400" /></a></div><span id="goog_543392716"></span><span id="goog_543392717"></span><br /><br />This is from the public channel. If you want to get to your own quiet place:<br /> <a href="http://noteverse.com/?channel=mychannel" target="_blank">noteverse.com?channel=mychannel</a><br /><br />In the next few days I will come to make a post about the app #2. It is pretty amazing if you're the type that likes to whistle around.Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-27122451451684767092015-09-06T18:31:00.000-07:002015-09-06T18:31:13.860-07:00Codeforces: Xenia and HammingHere is a coding puzzle I wanted to formalize due to clarity for myself. If you're into number theory this is your thing.<br /><b><br /></b><b>Problem statement: </b><a href="http://codeforces.com/contest/356/problem/B" target="_blank">http://codeforces.com/contest/356/problem/B</a><br /><br /><b>Solution: </b>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:<br /><br />\( (n \cdot x)[dx + i \cdot |x|] = x[(dx + i \cdot |x|) \mod |x|] \) <br /><complete><br /></complete><complete>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:</complete><br /><complete><br /></complete><complete>\( x[dx] = y[(dx + i \cdot |x|]) \mod |y| \)</complete><br /><complete><br /></complete>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?<br /><br />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.Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-47357840573729463532015-08-16T13:53:00.000-07:002017-09-20T10:38:46.590-07:00Targ.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.<br /><div><br /></div><div>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.</div><div><br /></div><div><span style="font-size: large;">Interested to try it out? Go and play at: </span><a href="http://targio.webdash.io/" style="font-size: x-large;" target="_blank"><b>TARG.IO</b></a><span style="font-size: large;"> </span><span style="font-size: large;">!</span></div><div><br /></div><div><br /></div><div>This preview should give a good insight about the idea behind:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-24641434322246404712015-05-02T06:33:00.000-07:002015-05-02T06:37:19.064-07:00Exam season done and... The progress on EvyMapOnwards with EvyMap (<a href="http://www.evymap.com/" target="_blank">www.evymap.com</a>)! 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.<br /><div><br /></div><div>What that means for the user?</div><div>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. </div><div><br /></div><div>How does this work geographically? </div><div>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.</div><div>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. </div><div><u><br /></u></div><div><u>A <b>cool</b> upcoming feature: Spreading of posts! Based on the activity your posts have, they will be able to spread geographically to more locations. </u></div><div><br /></div><div>What has been done further?</div><div><ul><li>The design has been greatly adapted.</li><li>Small description added on the index page.</li><li>Main page displays well on smaller devices now (phones, etc.).</li><li>Self-adapting fetching of replies. Ajax calls are adapting their cycles based on activity.</li><li>Image uploading fixed for profile pictures: images of all proportions are now supported. </li><li>The user-search bar is now using trigram matching: greatly improved search.</li><li>Some more XSS fixes.</li><li>Move from MySql to Postgresql</li><li>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!</li></ul><div>ToDo:</div></div><div><ul><li>Fix more known XSS vulnerabilities.</li><li>Add bcrypt for password hashing in order to keep the passwords safe.</li><li>Adapt the post-fetching mechanism to the above load adaption algorithm.</li><li>Enable manual extension of the search area in time and space. </li><li>Automatic user fetching while typing (currently, pressing enter is required).</li><li>Further adaptation of the reply fetching mechanism is needed.</li><li>Notifications on replies.</li><li>Access to made posts through the profile page.</li><li>Read-access without an account.</li><li>Delete/edit post/reply.</li><li>The cool upcoming feature :)</li></ul></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-29206029828821574462015-01-19T16:41:00.000-08:002015-01-19T16:47:05.549-08:00Updates on EvyMapMy first update on EvyMap's state (<a href="http://www.evymap.com/" target="_blank"><b>www.evymap.com</b></a>)! First, a "thank you" goes to <a href="http://martin-thoma.com/">Martin Thoma</a> for pointing out some needed attention over the security aspects. The same applies to some of my friends at my university, KIT. The updates:<br /><div><ul><li>Mechanisms for preventing XSS attacks implemented.</li><li>Mechanisms for preventing MySql attacks implemented.</li><li>Made the website work with utf-8.</li><li>User input goes through stricter validation.</li><li>The dynamic loading of all the images is made faster.</li><li>Birthday picker added within account settings.</li><li>Password resetting added.</li><li>Fixed scrolling within the message window.</li><li>Various pop-up messages have been integrated for keeping the user informed about the actions the server does.</li><li>Design within Firefox and Internet Explorer fixed.</li></ul><div>The cream on top of all: A neat functionality that was recently added, illustrated with the following link:</div><div><a href="http://www.evymap.com/?location=New%20York" target="_blank">http://www.evymap.com/?location=New%20York</a></div><div>After logging in, this will get you directly to New York and set you up for chatting.</div><div><br /></div><div>Known issues:</div></div><div><ul><li>Some random birthday gets assigned to the user upon registration.</li></ul><div>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!</div></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-20781544267620598252015-01-01T13:33:00.000-08:002015-01-01T13:33:01.627-08:00Early 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.<div><br /></div><div>How it works: you select a point on Google Maps and set your radius. That's it! </div><div>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).<br /><div><br /></div><div>The link to the website: <a href="http://www.evymap.com/">www.evymap.com</a>.</div><div><br /></div><div>Here is a preview of the main page:<br /><div><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-9N28FUWI0PE/VKW3oXdrf0I/AAAAAAAABwE/Uxd3qG4jJmE/s1600/evymap_preview.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-9N28FUWI0PE/VKW3oXdrf0I/AAAAAAAABwE/Uxd3qG4jJmE/s1600/evymap_preview.png" height="320" width="640" /></a></div><div><br /></div></div></div></div><div>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" :)</div><div>Also, works very bad on phones.</div><div><br /></div><div>Thankful for any feedback!</div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-26772711206210898452014-12-21T12:08:00.000-08:002014-12-21T12:08:21.462-08:00First android app I worked on!Together with a bro, Zach Lauzon, I made a cool app for Android devices called Flash Beat. It uses the strobe on your phone to produce light that goes well along the music. You can use it at a party, make a small disco at home, or impress your friends with beatbox skills like <a href="https://www.youtube.com/watch?v=jXSWrRf2GbI">this</a>. Also, you can make it flash on your friends' faces (you asshole).<br /><br />Without further ado, the app:<br /> <a href="https://play.google.com/store/apps/details?id=com.amtrix.flashbeat.free" style="text-align: start;"><img alt="Get it on Google Play" src="https://developer.android.com/images/brand/en_generic_rgb_wo_60.png" /></a><br /><br />Preview on a song:<br /><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/2TJTlhpFBx4?feature=player_embedded' frameborder='0' /></div><div class="separator" style="clear: both; text-align: center;"><br /></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-72824349789743841452014-12-21T09:32:00.000-08:002014-12-21T09:32:20.538-08:00Internship at GoogleInternship at Google is finished!<br /><br />Just 2 days ago I finished my first internship. Even though there were bumps on the road throughout it, I had fun participating in it. I met lots of friends, visited many places, got to eat a lot ( :) ), and also had a cool project.<br />The project I was working on was about making a regression test for a service handling social relationships between users and documents. I made sure that builds do not break certain relationships that should always exist.<br />My project was also dependent on other people there, which made me also more efficient at working with a team.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-GlviEYDV774/VJcD8gmKi6I/AAAAAAAABvs/F-8U1huBYq0/s1600/WP_20140915_17_45_38_Pro.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-GlviEYDV774/VJcD8gmKi6I/AAAAAAAABvs/F-8U1huBYq0/s1600/WP_20140915_17_45_38_Pro.jpg" height="356" width="640" /></a></div><span id="goog_827498966"></span><span id="goog_827498967"></span><br />Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com2tag:blogger.com,1999:blog-3434488026762965185.post-73998542888216363972014-06-08T12:42:00.000-07:002014-06-08T20:19:08.571-07:00Illustrating the size of the universe in terms of memory spaceAccidentally, I came over my friend's question "Are we alone in the universe?".<br />I started thinking. I knew the universe is big and I've read several times that the human mind can't even comprehend the size of it. As always, I thought that the solution lies in simplifying the problem and making things more abstract.<br /><br />Being a computer scientist, I went for representing it in terms of data :)<br />Most estimations of the data volume we produced lie below 5 Zettabytes. So, let's assume that we have a hard drive of that size.<br /><br />Furthermore, assuming every galaxy is of the same size as the Milky Way, we have approximately:<br /><span style="background-color: white;"><span style="color: #111111; font-family: Lustria, arial, sans-serif;"><span style="font-size: 15px; line-height: 22.0049991607666px;"><i>5.1 x 10^22 stars = <b>510 0000 0000 0000 0000 0000 stars</b></i></span></span></span><br /><i><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;">= </span><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;">170 billion galaxies x 300 billion stars</span></i><br /><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;"><i>= (number of galaxies in our universe) x (number of stars in our galaxy)</i></span><br /><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;"><br /></span><span style="color: #111111; font-family: Lustria, arial, sans-serif;"><span style="background-color: white; font-size: 15px; line-height: 22.0049991607666px;">Summed up, we have:</span></span><br /><span style="color: #111111; font-family: Lustria, arial, sans-serif;"><span style="background-color: white; font-size: 15px; line-height: 22.0049991607666px;">5 Zettabyte = 5</span></span><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;">×</span><span style="color: #111111; font-family: Lustria, arial, sans-serif;"><span style="background-color: white; font-size: 15px; line-height: 22.0049991607666px;">10^21 bytes = <b>4 x 10^22 bits</b> on our hard drive and </span></span><span style="background-color: white; color: #111111; font-family: Lustria, arial, sans-serif; font-size: 15px; line-height: 22.0049991607666px;"><b>5.1 x 10^22 stars</b></span><br /><br /><b><i>Imagine we want to make a picture with tiny dots on it, separated by a white space of 1 bit, making each dot represent a star. </i></b><b><i>With all the memory on Earth we couldn't store that image!</i></b><br /><br />Something funny to think about too: every word ever spoken can be stored in 0.001 Zettabytes. If all we did our whole life was naming stars, we would still have to name 1000 times as much as we did.<br /><br />With all that said, I believe that there is other intelligent life somewhere out there.<br /><br />References:<br /><a href="http://en.wikipedia.org/wiki/Exabyte">http://en.wikipedia.org/wiki/Exabyte</a><br /><a href="http://en.wikipedia.org/wiki/Zettabyte">http://en.wikipedia.org/wiki/Zettabyte</a><br /><a href="http://www.universetoday.com/102630/how-many-stars-are-there-in-the-universe/">http://www.universetoday.com/102630/how-many-stars-are-there-in-the-universe/</a><br /><br />Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com2tag:blogger.com,1999:blog-3434488026762965185.post-38923293047465821302014-03-23T11:49:00.002-07:002014-03-25T05:36:25.780-07:00Leaving my room in Tennesseeallee, KarlsruheIn 2 days I'll be leaving the room I used to live in for the last 2+ years. Many challenges have been won from this room out, but it's time to move on to the next chapter: bachelor's thesis at the CMU, Pittsburgh. Lastly, for the memories, an image of my workplace in this room:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-_X4KDh3njjw/Uy8sgk9EDJI/AAAAAAAAA0c/sQinmKQwK8A/s3200/IMG_0564.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-_X4KDh3njjw/Uy8sgk9EDJI/AAAAAAAAA0c/sQinmKQwK8A/s3200/IMG_0564.JPG" height="297" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><br /></div><span id="goog_1746247411"></span><span id="goog_1746247412"></span> So long!Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-78232601489197921222014-03-15T18:19:00.000-07:002014-03-15T18:27:57.667-07:00A small journey with XNA and C#There is something I've done a year ago, but never shared. Although it looks simple, it can produce some beautiful views. Here a preview:<br /><div><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/o9-3sS3J2UY?feature=player_embedded' frameborder='0' /></div><br /><b><i>To try it out: <a href="https://docs.google.com/uc?export=download&id=0Bw2zSjtvL2gYQ1NuSUszM2FzSVk">setup.zip</a> (source code: <a href="https://docs.google.com/uc?export=download&id=0Bw2zSjtvL2gYdnRPSVNKVmlRbDg">source.zip</a>).</i></b><br /><b><i><br /></i></b>As for the commands:<br />- C: creates one particle (holding down for more possible)<br />- A: makes a new spawn point for the particles<br />- D: creates a "pull gravity" at the cursor's position<br />- P: creates a "push gravity" at the cursor's position<br />- V: creates a pull-point over the given location<br />- B: creates a push-point over the given location<br />- 1: increases gravity pull range<br />- shift+1: decreases gravity pull range<br />- 2: increases gravity push range<br />- shift+2: decreases gravity push range<br />- +: make the dots larger<br />- -: make them smaller<br />- ESC: toggles the command prompt (up-arrow may be used for history access). Following commands are possible:<br /> - "SET COLOR x y z" where xxx,yyy,zzz are in [000,255] (leading zeroes are needed for 3 digits!)<br /> - "ADD x" adds x new dots at random positions<br /> - "REM x" removes x random dots<br /> - "CLEAR" clears the everything<br /> - "SAVE" saves the state and "LOAD" loads it<br /><br />Have fun!<br /><div></div></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-39100240395378228132014-03-15T17:31:00.000-07:002014-06-08T20:10:22.495-07:00Song extractor for the Osu! gameI've used to play a bit a game called Osu!. It's about catching the beats alongside a song. Here a preview of the best player in the world (combo is given in the bottom-left corner):<br /><div><br /><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/rRMJlEPZ4B8?feature=player_embedded' frameborder='0' /></div><div><br /></div></div><div>.... watching this is always like "WTF, HOW?!".</div><div><br /></div><div>To the reason I'm posting this. I've met some quite exciting songs while I've played the game and I wrote a program for extracting the songs out from the game. This is easy done by hand too, but it's quite tiresome.</div><div><br /><b><i>Here it is: <a href="https://docs.google.com/uc?export=download&id=0Bw2zSjtvL2gYV2RSSEw0VFFaejQ">osu_extractor_win7.zip</a> (<a href="http://pastie.org/8933948">readme</a> from the zip).</i></b></div><div><br /></div>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-91329596634039833462014-02-27T16:51:00.001-08:002014-03-13T10:28:11.606-07:00Primitive Roots modulo a prime number<h3>Finding primitive roots</h3>First off, it has to be noted that the constraint that the modulo value is a prime number is just for simplicity (hint: all values from 1 to <b>p-1</b> are coprime to <b>p</b> for a prime number <b>p</b>).</br>Now, what EVEN is a primitive root modulo p you may ask. This is just a number <b>g</b> which generates all numbers from <b>1</b> to <b>p-1</b> with \(g^{t} \: mod \: p\). That is, for every positive integer <b>x < p</b> there exists a <b>t</b>, so that \(g^{t} \equiv x \pmod{p}\).</br>Properties of primitive roots:</br><ul><li>for a given p there are <a href="https://en.wikipedia.org/wiki/Euler's_totient_function">phi</a> (phi(p))=phi(p-1) primitive roots</li><li>g is a primitive root \( \Leftrightarrow\) for every divisor d of \((p-1)=phi(p)\), \(g^{d} \not\equiv 1\pmod{p}\) holds \( \Leftrightarrow\) for every prime \(x\) from the prime factorization of \(p-1\), \(g^{(p-1)/x} \not\equiv 1\pmod{p}\) holds.</li><i>(comment: this is essentially there to check for repeating sequences in \(g^{t}\) for \(t \in {1,..,p-1} \pmod{p}\).</i></ul> Some research: I've ran <a href="http://pastie.org/8817954">this</a> code to look at the distribution of the primitive roots for primes between 100 and 1,000,000,000. By running the code we see this from the <a href="http://pastie.org/8818203">output</a>: <ul><li>the lower bound for the number of primitive roots is \(0.15 \cdot p\). Therefore, 15% of the numbers smaller than \(p\) are primitive roots for a given p (<b>in worst case!</b>). By selecting a random positive integer <b>< p</b> we have a 15% chance of selecting a primitive root!</li><li>given a random p, the chance of hitting a primitive root on random is even ~40%.</li></ul> </br>Therefore, in order to find a primitive root, we may simply pick up random numbers and check the above property which has to hold for primitive roots. Code which does that: <a href="http://pastie.org/8916329">link</a>. </br></br><h3>Now to the discrete logarithm (the index):</h3> for a given <b>x</b>, how to find a \(y=ind_{g}(x)\) with \(g^{y} \equiv x \pmod{p}\). The answer is: you can't. Many encryption algorithms are based on this fact. Though, they have some nice properties as normal logarithms:</br><ul><li>\(ind_{g}(ab) \equiv ind_{g}(a) + ind_{g}(b)\pmod{p-1} \)</li><li>\(ind_{g}(a^{k}) \equiv k \cdot ind_{g}(a)\pmod{p-1} \) </li></ul> That should bundle the core things about this topic. One is advised to check the references for a better understanding. </br></br>Useful links:</br>- <a href="https://en.wikipedia.org/wiki/Primitive_root_modulo_n">Wiki</a>- <a href="https://en.wikipedia.org/wiki/Discrete_logarithm">Wiki(discrete logratihm)</a>- <a href="https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number">Finding primitive roots</a>- <a href="https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCoQFjAA&url=http%3A%2F%2Fwww.ualberta.ca%2F~patnaik%2Fmath324%2Flecture%252013.pdf&ei=diATU7n5EKiP7AbCmYGwCw&usg=AFQjCNHbk-Tf6Ykv8CGzxHbPNbMda5-_eg&sig2=deF83qbF0aamB_I3OTxkgw&bvm=bv.62286460,d.ZGU">Index properties</a>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0tag:blogger.com,1999:blog-3434488026762965185.post-10597082891538119932014-02-23T06:22:00.000-08:002014-02-23T18:38:11.534-08:00Linear diophantine equations: simplification of sums for reachability (enabled javascipt for latex is needed)My first meaningful post shall be a mathy one. I wanted to understand the idea behind this, so I've decided to make a post explaining it :)</br>Assume we have a problem where we have to iterate over all \(x = \sum\limits_{i=1}^n c_{i} \cdot a_{i} \), where the \(c_{i}\) are freely selectable. In such problems a very easy simplification can be made: each such \(x\) can be represented in the form \(x = t \cdot q\), where \(t = gcd(a_{1},...,a_{n})\) and \(q \in \mathbb Z \). </br></br>To understand the above statement, we only need to think of the extended euclidean algorithm. Inside of it we find the integers \(x\) and \(y\) so that \(x \cdot a_{1} + y \cdot a_{2} = gcd(a_{1},a_{2}) \) holds. Additionally, we can easily imply that each number \(v\) written in the form \(v = c_{1} \cdot a_{1} + c_{2} \cdot a_{2} \) must be a multiple of \(g:=gcd(a_{1},a_{2})\) (as g divides \(a_{1}\)and \(a_{2}\) it must divide v for the equation to hold (!)).</br>We show now that the same holds for 3 variables. Let \(x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3} \) and \(g:=gcd(a_{1},a_{2},a_{3})\). We have to prove that \(x\) is a multiple of \(g\). Consider the first two variables and write: \(a_{1} \cdot c_{1} + a_{2} \cdot c_{2} = t_{1} \cdot gcd(a_{1},a_{2})\). This gives us \(x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3} = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3} \). Simply seen here: there are again two fixed numbers and two free! Smells like the extended euclidean again :) </br>We write: \(G := gcd( gcd(a_{1},a_{2}) , a_{3} ) = gcd(a_{1},a_{2},a_{3}) = g \) and get: \(x = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3} = t_{2} \cdot g \) - with this we're done! Inductively the statement follows for 4 and more variables. </br>Anonymoushttp://www.blogger.com/profile/01900618786163842653noreply@blogger.com0