1 | [
|
---|
2 | The 196-algorithm implemented in brainfuck by Mats Linander.
|
---|
3 |
|
---|
4 | This program reads a number in the form of a string of decimal digits
|
---|
5 | terminated by a unix style newline (0x10) and tries to determine if the
|
---|
6 | entered number is a lychrel number.
|
---|
7 |
|
---|
8 | A lychrel number is a number which never yields a palindrome when iteratively
|
---|
9 | added with its own reversal. The process of iteratively reversing and adding
|
---|
10 | until a palindromic number is obtained, is often called the 196-algorithm.
|
---|
11 | The smallest number believed to be a lychrel is 196. Hence the name of the
|
---|
12 | algorithm.
|
---|
13 |
|
---|
14 | This program will keep reversing and adding until a palindromic numbers is
|
---|
15 | obtained or it runs out of memory. Given x bytes of memory, an approximately
|
---|
16 | x/5 digits long number can be calculated.
|
---|
17 |
|
---|
18 | Rows starting with a percent sign ('%') show what the memory is supposed
|
---|
19 | to look like at that point of execution. The string ":::" means "...".
|
---|
20 |
|
---|
21 | ----------------------------------------------------------------------------
|
---|
22 | "THE BEER-WARE LICENSE" (Revision 42):
|
---|
23 | <matslina (at) kth (dot) se> wrote this file. As long as you retain this
|
---|
24 | notice you can do whatever you want with this stuff. If we meet some day,
|
---|
25 | and you think this stuff is worth it, you can buy me a beer in return.
|
---|
26 | Mats Linander 2004-06-15
|
---|
27 | ----------------------------------------------------------------------------
|
---|
28 |
|
---|
29 | ]
|
---|
30 |
|
---|
31 | // Request input; print the string "enter number: "
|
---|
32 | ++++++++++[->++++++++++>+++++++++++>+++<<<]
|
---|
33 | >+.>.++++++.<.>--.>++.<----.+++++++.-------
|
---|
34 | -.<---.+++.[-]>+++++.++[--<+>]<.[-]>>.[-]<<
|
---|
35 | <
|
---|
36 |
|
---|
37 | // Read a string of numbers and setup memory
|
---|
38 | // Let 'A' denote the first number read; 'B' the second; 'Y' the second last
|
---|
39 | // and 'Z' the last
|
---|
40 | // Note that the string may be of any length so it is possible that A=Y
|
---|
41 | // or Z=A and there can be any number of numbers between 'B' and 'Y'
|
---|
42 | +>>->
|
---|
43 | ,----------[-->++++++[-<------>]<[->+>+<<]<+>+>>>>>,----------]
|
---|
44 | <<<<<<[<<<<<]>-
|
---|
45 | % 1 0 0 0 A A 0 1 1 B B 0 1 1 ::: 0 1 1 Y Y 0 1 1 Z Z 0 0 0 :::
|
---|
46 |
|
---|
47 | // Main loop
|
---|
48 | // Loop while cell (0) is 1
|
---|
49 | <<<[
|
---|
50 |
|
---|
51 | // Move some numbers around
|
---|
52 | >>>>>>>[<< [->>[>>>>>]<+<<<<[<<<<<]>>>]>>[>>>>>]<<[-<<<[<<<<<]>>>+>>[>>>>>]<<]
|
---|
53 | >[-<+>]<<<<-<<<<<[<<<<<]>>>>>[-]>>>>>]
|
---|
54 | % 1 0 0 0 A Z 0 0 1 B Y 0 0 1 ::: 0 0 1 Y B 0 0 1 Z A 0 0 0 :::
|
---|
55 |
|
---|
56 | // Set some flags
|
---|
57 | <<<<[<<<<<]<<+>>>>>>>[<+>>>>>>]
|
---|
58 | % 1 1 0 0 A Z 0 1 1 B Y 0 1 1 ::: 0 1 1 Y B 0 1 1 Z A 0 0 0 :::
|
---|
59 |
|
---|
60 | // for all pairs (AZ and BY etc) if they are not equal (A!=Z or B!=Y etc) clear
|
---|
61 | // flag in cell (1)
|
---|
62 | <+[-<<
|
---|
63 | [->+>+<<]<[->+>-<<]>[-<+>]>>[-<<+>>]<[[-]<<<[<<<<<]<<[-]>>>>>>[>>>>>]<]
|
---|
64 | <<<<]
|
---|
65 | % 1 0/1 0 0 A Z 0 0 1 B Y 0 0 1 ::: 0 0 1 Y B 0 0 1 Z A 0 0 0 :::
|
---|
66 |
|
---|
67 | // The flag in cell (1) is set if and only if the number is palindromic
|
---|
68 | // If it is we clear the flag in cell (0) and the main loop will end
|
---|
69 | <[-<->]<
|
---|
70 | % 1/0 0 0 0 A Z 0 0 1 B Y 0 0 1 ::: 0 0 1 Y B 0 0 1 Z A 0 0 0 :::
|
---|
71 |
|
---|
72 | // If number is not palindromic we will do some addition
|
---|
73 | [
|
---|
74 |
|
---|
75 | // First output some information on where we are
|
---|
76 | // Print the string "AB:::YZ (plus) ZY:::BA = "
|
---|
77 | >>>>>>>>[<<++++++++[-<++++++>]<.>>>>>>>>]++++++++[-<+++++<++++<++++++>>>]<<<.>
|
---|
78 | .>+++.<.<.>>+++++[-<<->>]<[-]<<<[<<<.>++++++++[-<------>]<<<]++++++++++
|
---|
79 | [-<+++<++++++>>]<++.<+.[-]>.[-]
|
---|
80 |
|
---|
81 | // Go through all pairs (including the last one)
|
---|
82 | // Let 'G' and 'H' represent the pair of numbers we are currently working
|
---|
83 | // with in the loop below
|
---|
84 | >>>>>>[>>>>>]+[<<<<<]>>>>>[
|
---|
85 | % ::: G H 0 0 1 :::
|
---|
86 |
|
---|
87 | // Add them and check if the sum is larger than 9
|
---|
88 | <<<[-<+>]
|
---|
89 | >+<<[>>-<<[->+<]]>[-<+>]>[>>-<<-]<+++++++++
|
---|
90 | [>>+<<-<-[>>>-<<<[->>+<<]]>>[-<<+>>]>[->[-]<]<<]
|
---|
91 | % ::: G(plus)H(minus)9 0 0 0 1/0 :::
|
---|
92 |
|
---|
93 | // The rightmost cell in the list above is 1 iff the sum was larger than 9
|
---|
94 | // If it was we add 1 to the next pair of numbers
|
---|
95 | // If it was not we restore the sum
|
---|
96 | <->>>+>[-<->>+<]+<[-<<<++++++++++>>>]
|
---|
97 | % ::: G(plus)H 0 0 0 1 :::
|
---|
98 | // Do the next pair
|
---|
99 | >>>>>>]
|
---|
100 |
|
---|
101 | // After adding we prepare the sum for next iteration in the main loop
|
---|
102 | // and print the sum followed by newline
|
---|
103 | <<<<<[-]>[-<+>>+<]>[-<+>]<<<<<<<[<<<<<]>>>>>[>>>>>]<<<<<
|
---|
104 | [>[->+>+>+<<<]>>[-<<+>>]++++++++[->++++++<]>.[-]<<<<<<<<<]
|
---|
105 | >[->+>+>+<<<]>>[-<<+>>]++++++++[->++++++<]>.[-]
|
---|
106 | >[>>>>>]<<<<<[<+<<<<]<<<
|
---|
107 | +++++++++.---------
|
---|
108 | % 1 0 0 0 Z' Z' 0 1 1 Y' Y' 0 1 1 ::: 0 1 1 B' B' 0 1 1 A' A' 0 0 0 :::
|
---|
109 | // Where the A'B' ::: Y'Z' = AB ::: YZ (plus) ZY ::: BA
|
---|
110 |
|
---|
111 | // Go back to the main loop
|
---|
112 | >+<-]
|
---|
113 | >[-<+>]<
|
---|
114 |
|
---|
115 | ]
|
---|
116 |
|
---|
117 | // We've got a palindrome and have left the main loop
|
---|
118 | // Print "Palindrome: A'B':::Y'Z'"
|
---|
119 | % 1/0 0 0 0 A Z 0 0 1 B Y 0 0 1 ::: 0 0 1 Y B 0 0 1 Z A 0 0 0 :::
|
---|
120 | ++++++++++[->++++++++>+++++++++++>++++++<<<]>.
|
---|
121 | <++++[->++++<]>+.>--.---.+++++.<+++.>++++.---.
|
---|
122 | --.<+.>>--.++[--<<<+>>>]<<<++.>>>+[>>>++++++++
|
---|
123 | [-<++++++>]<.>>>]++++++++++.
|
---|