📜 ⬆️ ⬇️

Normal Markov algorithm for dividing numbers

Good day. I would like to share with you a very interesting variant of abnormal programming - the compilation of normal Markov algorithms. This programming option can serve as a great mental break from familiar languages ​​and programming environments.
The students, whom I have the opportunity to teach, shout a shout that it is difficult, but only to the first with their own hands made working algorithm, then it flows into very interesting algorithmic tasks.
Actually, to the topic of this post: our task is to write a normal Markov algorithm for dividing two integers with an accuracy of 4 decimal places (for the assignment of numbers we use the unary calculus system). For example, input: | / ||||, output: 0.25.
In this case, we have only one operation — replacing one substring in the source string with another. Who cares what it is and how it works - welcome under the cat.


Normal Markov Algorithm

By a normal Markov algorithm, we mean some sort of ordered set of products (replacements of substrings). Products can be as ordinary (run as many times as possible) and final (performed only once and after them the algorithm ends). Products run from the first. If the first can not be done - do the second and so on. If, after any product, you can again perform some of the previous ones, we execute it. The operation of the algorithm is terminated when there is no next product to execute and all previous ones cannot be completed or after the execution of any final product.
Actually solving the problem

List of replacements:
%* *%
%| %*
*| **
|* t
t* *t
t% %t
%t %v|
t |
%v ?d
?d d?
|d d|
? %
*d h
h* oh
h% h
h « »
* « »
d |_
/| -k
k| kk
k |+
+| |+
- ey
|e e|
y %
eo 0o
e « »
|_ .a
a. .a
.. .
.aaaaaaaaaa a,.
,a a,
.aaaaaaaaa 9
.aaaaaaaa 8
.aaaaaaa 7
.aaaaaa 6
.aaaaa 5
.aaaa 4
.aaa 3
.aa 2
.a 1
. 0
, « »
a .a
o p||||||||||
|p p|
pp p
% u
u+ u
u _
|+ |)+
) (>
>+ +>
+ {
{ |
>>>>> =
|= =
(= =
( /
p= =<
<0 0<
<1 1<
<2 2<
<3 3<
<4 4<
<5 5<
<6 6<
<7 7<
<8 8<
<9 9<
<<<<< $
0$ $0
1$ $1
2$ $2
3$ $3
4$ $4
5$ $5
6$ $6
7$ $7
8$ $8
9$ $9
=$ .FIN
0= =0
1= =1
2= =2
3= =3
4= =4
5= =5
6= =6
7= =7
8= =8
9= =9
_> « »
0> >0
1> >1
2> >2
3> >3
4> >4
5> >5
6> >6
7> >7
8> >8
9> >9
p> « »
p .FIN
_ .FIN

FIN after substring with which we replace means that such products are final.

Write an emulator that allows you to emulate the work of such an algorithm will not be any difficulty in any of the programming languages.
')
As a result, to log in | / |||| by string conversions we get 0.25. Who does not believe - check. (We write the entry on a piece of paper, for example, the same | / |||| and perform the above substitutions until the algorithm finishes its work (see the completion condition see above))
PS Here is such an elegant and unusual version of programming and removal of the brain.

PPS Dear programmers, I propose a contest from the “Are you weak?” Series (it will allow you to strain the brain and take a break from the usual programming). The task is simple - to compile a Markov algorithm for multiplying two ordinary fractions.
Example: Input: (1/2) * (2/5)
The result should be 1/5
If it is interesting to anyone - dare.

Source: https://habr.com/ru/post/110004/


All Articles