savoy082

Everyone knows what mazes/labyrinths are! And plenty of us find it amusing to try and solve one! Take the image above as an example... Can you find a path from the top left opening to the bottom right opening? There exists at least one! I wrote a program in Python (making use of pygame and Pillow) to solve any maze given. I did this project several years ago, after learning about Dijkstra's algorithm . I read about the algorithm and decided to implement it, to get a feel for it. I realized that I could apply it to a maze in a picture, if I took each pixel of the image to be a vertex in the graph where I'd apply the method. I wanted to make my program fairly general, in terms of the mazes that could be given, and so I dwelled with a problem: how to tell if two adjacent pixels should be connected in the graph or not. I knew I only wanted to connect pixels that referred to the path, and not to the walls, so my idea was simple: I supposed that a picture of a maze would have mainly ...

This post's project was made by me and a colleague of mine, Inês Marques. We programmed a small puzzle game, based solely on colours and not on images, that we called HueHue (please mind that the idea for how the game works is not ours). The way the game works is pretty straightforward: you start with a bunch of coloured tiles all mixed up, like in the left image above, and then you want to organize them to create a degradee like the one in the right! The only thing you can take for granted is that the four corners are already correctly placed (and you can't move them, just to prevent accidents). The instructions are also quite simple: you use left and right clicks to swap tiles. Whenever you left-click a tile, you are telling the game that you will want to swap that tile. Whenever you right-click a tile, that tile gets swapped with the last tile you left-clicked! Simple, right? When you finish the puzzle and rearrange the degradee, the window caption changes and you can't ...

This post's problem is a follow-up from this earlier post in which I talk a little bit about the problem of the water buckets and describe how I wrote a program to solve it. If you spot any mistakes here (or there) please let me know! Problem statement : Given $n$ buckets of capacities $c_1, \cdots, c_n$, prove that if the target value $t$ is not a multiple of $d = \gcd{(c_1,\cdots,c_n)}$ then the problem is unsolvable. Show that if all quantities in all buckets are multiples of $d$, then after one single move, that still holds. Hint 1 Solution : We will show that, regardless of the sequence of moves, all values in all buckets are - at all times - multiples of $d$. Let $w_i$ denote the value of bucket $i$. It is easy to see that in the beginning we have that each bucket has $w_k = 0 = \sum_{i=1}^n 0\cdot c_i$ and thus our property holds for the initial configuration. Now consider that for each bucket $k, w_k = \sum_{i=1}^n a_{k,i}c_i$ (i.e., all values are multiples of $d$). Reme...

[ Link to code, you can try it in the end of the post] Suppose you have an infinite source of water and two buckets of capacities $5$L and $3$L. Through juggling around the water in the buckets, can you find a way to have one of the buckets hold exactly $1$L of water? A possible way of doing it would be: Fill the bucket of $3$L and then pour its water into the $5$L one; Fill the bucket of $3$L. At this point you have $3$L in each bucket; Pour the bucket of $3$L into the $5$L one. Since the bigger one already had $3$L in it, only $2$ will fit, meaning there will be a remaining litre in the $3$L bucket. I find this problem a very interesting one, and it is not hard to generalize it: given $N$ buckets of capacities $c_1, c_2, \cdots, c_N$, as well as a target value $T$ and an infinite source of water, is there a sequence of moves that puts exactly $T$ litres in one of the buckets? There are some cases for which one can immediately say that there is no such sequence. On one hand, if $T ...

[Code/código: regexPrinter ] A regular expression , without much rigor, is a very compact way of representing several different strings. One common use of regular expressions is to look for strings that have a certain structure in a bigger string (say a text). As an example, the regular expression abc(d|e) can be used to look for the strings "abcd" and "abce", where the character | denotes we have to make a choice. Thus cat|dog would match the strings "cat" and "dog". There are other special symbols that have meanings and purposes. One very interesting question that arises is: given a regular expression, what are the strings matched by it? To answer that question I wrote a small Python program, that I called regexPrinter , that prints all strings matched by a given regular expression! In order to manage that task, I chose a subset of the regex syntax that I wanted to be able to print and also decided that whenever a piece of a pattern was inf...

We shall prove that there exist $a, b \in \mathbb{R}\setminus\mathbb{Q}$ such that $a^b \in \mathbb{Q}$. I really love this proof because it is very simple and it is the shortest proof (of something meaningful...) I know! Proof : Let $a = b = \sqrt{2}$. If $a^b$ is rational, we are done. If it is not, consider $a = \sqrt{2}^\sqrt{2}, b = \sqrt{2}$. Now $a^b = \left(\sqrt{2}^\sqrt{2}\right)^\sqrt{2} = \sqrt{2}^{\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^2 = 2 \in \mathbb{Q}$, thus concluding the proof. Do you know any other twitter proofs ? Please let me know if you do! You can even e-mail me some and I can post them in the future. [Pt] Neste post vamos provar que existem números irracionais tais que, um levantado ao outro, dão um número racional. Eu gosto bastante desta prova porque é muito simples, e é a prova mais curta (de algo "decente" ) que eu conheço! Prova : Considere-se $a = \sqrt{2}$. Se $a^a$ for racional, então já provámos o desejado. Se não for, posso pensar em $\left(a...

    the scenery in which this proble m takes place Once again I bring you a problem alongside my proposed solution. If you find any mistakes or come up with a different solution, please let me know! Problem statement (and a lovely short story): The Shire is a lovely place where $N $ hobbits live in perfect harmony. Or at least they lived, until a hobbit decided to become an outside decorator and convinced some of its friends to paint their front doors with a very "fashionable" purple (all doors were yellow before that preposterous change). Overnight, the perfect balance and harmony in which the hobbits lived shattered, and hobbits whose doors were different colours couldn't stand one another. Worried, the great and wise Gandalf hurried to the Shire to try and settle this matter. This was what he decided to do: in alphabetical order, he would visit each hobbit. When visiting a hobbit $h $, he would change the colour of its door if and only if there were more hobbits mad...

This post contains a problem statement and my proposed solution. Please remember that I am only human and that I am (very) flawed. If you spot a mistake in my solution please  let me know. Problem statement : John and Mary have a bag full of integer numbers. In fact, the bag has $10^{10^{10}} $ numbers, each written on a plastic card, and the sum of all the $10^{10^{10}} $ integers in the bag is $0$. In turns, Mary and John are going to play with the bag, by doing the following: Picking two cards from the bag, let us say the cards have the numbers $a $ and $b $, and removing them from the bag; Inserting a new card in the bag with the number $a^3 + b^3$. Q: is there any initial number configuration and/or set of moves for which it is possible that, after $10^{10^{10}} - 1$ moves, the only card in the bag has the number $73$? The answer is "no". Can you show why? Hint 1 Look for an invariant of the game! That is, find a property of the game that does not change when Mary and...

This post's format will be a bit different from the usual. In this post, I will state a problem and then present my solution. More often than not (unfortunately) my solutions may have mistakes. If you find any, let me know! Problem statement : Let $[ABC] $ be an equilateral triangle of side length $1$. We now define a transformation of the triangle which moves one vertex and leaves the other two unchanged. To apply a transformation, start by picking the vertex you want to move. Assume it was $A $. Consider the line that goes through $A $ which is parallel to $[BC] $, and pick any point $A' $ in it. Your transformed triangle is $[A'BC] $. You can repeat this process as many times as you want. Q: Can the original triangle be transformed into an equilateral triangle of side length $2$? How/why? Try figuring this for yourself. The answer is "no". Can you show why? Hint 1 Look for an invariant of the transformation! That is, find a property of the triangle that does ...