jblog
toc

A278328

2017-03-11, post № 162

mathematics, programming, Python, #2016, #decimal reverse, #difference, #integer, #OEIS, #On-Line Encyclopedia of Integer Sequences, #palindrome, #reverse, #sequence, #square

The On-Line Encyclopedia of Integer Sequences (also known by its acronym, OEIS) is a database hosting hundreds of thousands of — as the name implies — integer sequences. Yet, despite the massive number of entries, I contributed a new integer sequence, A278328.

A278328 describes numbers whose absolute difference to their decimal reverse are square. An example would be 𝟣𝟤 or 𝟤𝟣 (both are the decimal reverse to each other), since \left|12-21\right|=9 and 9=3^2.

Not a whole lot is known about the sequence [1], partly due to its definition only resulting in the sequence when using the decimal system, though it is known that there are infinitely many numbers with said property. Since there are infinitely many palindromes (numbers whose reverse is the number itself), \left|n-n\right|=0 and 0=0^2.

Due to there — to my knowledge — not being a direct formula for those numbers, I wrote a Python script to generate them. On the sequence’s page, I posted a program which endlessly spews them out, though I later wrote a Python two-liner, which only calculates those members of the sequence in the range from 𝟢 to 𝟫𝟪 (shown below entered in a Python shell).

>>> import math
>>> filter(lambda n:math.sqrt(abs(n-int(str(n)[::-1])))%1 == 0, range(99))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 21, 22, 23, 26, 32, 33, 34, 37, 40, 43, 44, 45, 48, 51, 54, 55, 56, 59, 62, 65, 66, 67, 73, 76, 77, 78, 84, 87, 88, 89, 90, 95, 98]

Maze Solving

2017-02-27, post № 161

programming, Python PIL, #amazing, #labyrinth, #Minotaur, #solver

Mazes have been a subject of human interest for thousands of years. The Greeks used them to trap a bull-man hybrid, the French built them to show how they could impose order on nature, and even nowadays people enjoy wandering around corn mazes.
The algorithmic art of using computers to solve mazes — and even to find the shortest path through a maze —, however, has only emerged in the last couple of decades.

I was inspired by a recent Computerphile video in which Michael Pound talks about implementing different path finding algorithms for use in maze solving. And as he used Python — one of my favourite languages out there [1] —, I thought I could give it a try and came up with this maze solver.

maze-solving_normal_solved_enlarged.png

The mazes given to the solver (through a .png file) have to have a specific form. The maze needs to have a border all around (painted black) with two holes at the top and bottom, marking the maze’s start and exit (all path pixels are white).
Then the solver — using PIL — reads in the maze file, determines start and exit and starts at the maze’s start, labelling each maze path according to its shortest distance to the start. After it has found the exit, it stops looking at the maze and traces its origins back from the exit, marking the path it goes along as the maze’s optimal solution (highlighted in red).
The different hues of blue indicate the tile’s distance to the start, the white tiles are tiles the solver did not even look at.The different shadings also reveal information about the maze. Mazes with only one solution tend to have sharp changes as there are parts of the maze separated by only one wall, yet separated by a huge walk distance through the maze. The one maze with multiple solutions (see upper right image below) — in contrast — has only gradual changes in hue.

To solve a 𝟦 megapixel maze, the solver takes around 𝟥 seconds, for a 𝟣𝟨 megapixel maze around 𝟣𝟦 seconds and for a 𝟤𝟤𝟧 megapixel maze around 𝟩 minutes and 𝟤𝟤 seconds.
Performance was measured on an Intel Core i7 (𝟦.𝟢𝟢 GHz).

All mazes shown were downloaded from Michael Pound’s mazesolving GitHub repository, which were mostly generated using Daedalus.

The solver’s source code is listed below, though you can also download the .py file.

maze-solving-1_perfect2k_solved.png
maze-solving-2_braid2k_solved.png
maze-solving-3_perfect4k_solved.png
maze-solving-4_perfect10k_solved.png
maze-solving-5_perfect15k_solved.png
Source code: maze-solving.py

4096

2017-02-25, post № 160

games, Java, programming, #2016, #clone, #exponents, #jar, #powers of two

4096 is a Java-based clone of the well-known web and mobile game 2048, which itself clones 1024 and is similiar to THREES. The naming trend is quite obvious, though note that 2^{12} is a power of two where the exponent is divisible by three, further connecting to the aforementioned game.

In the game, you are faced with a 𝟦 ⨉ 𝟦 matrix, containing powers of two. By swiping in the four cardinal directions (e. g. pressing the arrow keys), you shove all the non-empty cells to that side. When two equal powers of two collide, they fuse together, adding. Once you shoved, an empty tile pseudo-randomly transforms to either a two-tile (𝟫𝟢%) or a four-tile (𝟣𝟢%).
Your objective at first is to reach the tile 4096, though the real goal is to achieve the highest score. Your score is the sum of all the collisions you managed to cause.

To play 4096, you can either download the .jar file or review and compile the game for yourself, using the source code listed below.

Controls

  • Up, down, left or right arrow key shoves the tiles,
  • ‘Escape’ restarts the game upon a loss,
  • ‘F11’ toggles fullscreen.
4096-1.png
4096-3.png
4096-4.png
Source code: Main.java
Jonathan Frech's blog; built 2021/04/16 21:21:49 CEST