No, this is not about Latin, sorry for those that arrived here with some wicked Google search about some dead language.
In a galaxy far, far away and long time ago, I attended a "scientific high school" (Liceo Scientifico), that happened in Milano, Italy.
When you attend that kind of school, you also have to study Latin... yeah, I know...
As you can easily imagine, me and most of my friends did not like the subject as we believed that it had nothing to do with science, which actually was our main interest.
Latin for us was good to come out of situations where you did not have a real answer, in the end it did not make any sense, but it sounded pretty damn cool.
Our teacher said it helped us to exercise our brain and would have provided us a good forma mentis, I honestly thought that if she had to use Latin to bullshit us, she was actually proving our point.
Still, we had no other choice than suck it up for five long years.
We also had to study religion and the teacher tried to convince us that exorcism is a true thing, but I was too busy playing fetch across the rainbow with my unicorn to pay attention to that.
The point is that in order to survive the immense boredom generated by those studies, we started playing puzzles during the lectures.
Our preferred one was this one :
The rules are quite simple : in a 10x10 square, starting top left, you move from cell to cell using the chess horse move and you record the progressive number of your move.
You cannot go outside the square and cannot enter twice in the same cell.
Winning condition is to fill in all the 100 numbers.
It is NOT easy, but eventually one of us solved the puzzle after about 2 or 3 years of Latin.
If you think this is a boring activity, you probably never studied Latin irregular verbs.
Unfortunately, the guy who solved the puzzle, failed Latin at the same time... but hey, it was TOTALLY worth it.Still, after a while -maybe 1 month- it became "not so interesting" to me and I thought it would have been more interesting to write an algorithm to solve it.
The first prototype was written in basic on a Sinclair QL, it never worked tho because I did not know the QL at all, and did not own one, I just did a few tests on the computer of a schoolmate brother.
I was 15 at that time and my (self taught) programming skills were still unfortunately limited to TI basic and some Z80 assembly.
Nonetheless that exercise helped me to formulate an algorithmic solution based on the following ideas (trying to remember it) :
1) "Moves" can be encoded in a way that, starting from a position X, the next position can be one of the 8 shown below
This means that we can create a function move(n) [with n between 1 and 8] that returns a 2 element array with dX and dY being the increments on the X and Y axis,
2) The new coordinates are calculated and an isValid(x,y) function returns true if the the move lands in a valid location.
Non valid locations are those outside the square (X<1 , X>10 , Y<1, Y>10) or those already occupied by previous steps
3) An array step[100] of integers will record at each step the move that brought me there and a second array cell[100][2] will store the X,Y coordinates of the positions
4) a stepCounter keeps track of current step
5) I verify if I am in a winning position (stepCounter == 100)
Logic :
When I start I immediately try the move(1), if isValid returns false, I try the move 2, until I reach the move 8.
In order to check if a cell is taken, I simply scan the cell[] array (there are some possible optimizations here, but the concept stands).
When I reach move 8 and still cannot place the move, I need to decrement stepCounter and try the next available move step[--stepCounter]
This is clearly a brute force algorithm, not particularly smart, but the beauty is that it can be easily generalized to solve different puzzles, I successfully used it to solve "find the exit of the maze" puzzles too.
Unfortunately the first working version of it came some time later (still before my friend did solve the puzzle manually tho :) ) running on a Ast Bravo 286 , which was my first MS-DOS PC running a 16 bit processor at an incredible speed of 10MHz.
A better version was coded in Turbo Pascal 3, later on improved with TP5.5 and finally refined with BP7 including some parts in assembly.
I also implemented part of it in Scheme Lisp, using a functional approach with recursive calls instead of the imperative style of the first versions, however I came out with the impression that these kind of problems should be solved with low level languages since code execution speed matters a lot.
By the time I had the BP7 version of the code, I had a second computer, a 486 DX 50MHz which proved to be way faster than my old 286, but the idea was : can I have both two computers work at the same time, on the SAME solution?
I did not have a network connecting the two PCs, just a serial cable, and fantasized on how to have them working in parallel exchanging information to balance dynamically the load.
I implemented instead a simpler approach : the BP7 version was able to save it's state to disk and eventually resume the execution.
If you think, saving the state is pretty easy : you just need the step[] array, anything else can be reconstructed.
This also meant that feeding a pre-filled step array to the program would make it take care of a PORTION of the executions.
I know it was not much, but it was a first step (my first step) into parallelism.
After all Latin was useful for me as I would have never faced this challenge without the boredom that "Rosa, Rosae, Rosae..." can generate, plus, as a bonus, now I can say basic profanities in the same language that the Pope speaks!
Recently I have been fiddling around parallel computing (for data mining and similar stuff), played a bit with map-reduce and some basic implementations in Python.
Map reduce is a great solution for some problems, provided you can pre- partition the data in a way that a master node sends packages of data to mapper (and finally reducer) client processes.
The issue I see is that you cannot (I believe) use it for a generic calculation where the step n depends on the steps [0..n-1], situation that can be easily represented by the puzzle I illustrated.
Now, I have two questions in my mind :
1) Do we have real problems to be solved that can be eventually attacked with an approach similar to a generalized version of my puzzle algorithm?
2) Which kind of balancing mechanism can be implemented to dynamically manage executions in parallel?
I have hard time figuring out point 1 (damn, I should have payed more attention to those Latin lectures, I am sure they would have been useful here!!), but I have some ideas for point 2.
The idea is :
what about experimenting with real hardware devices without an OS on them, extremely flexible in a way that we could eventually implement a low level communication protocol between them... and extremely cheap?
Are you thinking what I am thinking?
Cheap microcontrollers scaling up to ARM Sitara microprocessors (MSP430G2 up to BeagleBone Black with a Sitara @1GHz: 45$ )
For the actual balancing mechanism, I think it should be possible to work with a topology with no master and having peer clients exchanging directly information (maybe using SPI), I have some basic ideas, but I need to run some simulations first.
OK, this post is too long now, so I will follow up maybe next week in another post, meanwhile feel free to send your ideas, suggestions...
... and I will refrain from closing with a Latin quote.
[update : Example algorithm (in Java) here]
No comments:
Post a Comment