The string data type.
Strings are a type of data structure which is a sequence of symbols
(letters, digits, punctuation marks, special characters, ...).
The following function computes the reverse of a string and the
function ispalindrome checks whether the reverse is the same as
the original string.
function reverse(x)
{ var y = "";
for (k in x) { y = x[k]+y; }
return(y); }
function isapalindrome(x)
{ if (x == reverse(x))
{ return(1); }
else
{ return(0); } }
Palindromes are quite famous, as people like symmetries.
In Germany, for example, the name "OTTO" is known for being a palindrome
as well as for being the name of some emperors in the middle ages.
In English, when the
Panama Canal
was build from 1881 until 1914,
the sentence "A man, a plan, a canal - Panama" became famous,
also due to being a palindrome. To see this, one would, however, have
to remove spaces and punctuation marks and make all letters into the
same case. The next program removes these spaces.
The following program is one of the ways to extract the letters
from a string and to convert the upper case letters into lower case
letters. The command to do this is called a "switch" or "case" command,
the wording "switch(x[k])" tells the browser that it should find the
matching case for the value of "x[k]" (which is the letter at position k)
and then follow the instructions after the wording "case ..." until the
wording "break" is found. So in the case that k is 5 and x[k] is "d",
the commands between the case for the letter "d" and "break" are done
where the case for "D" is ignored and then the lower case letter "d"
is appended to the variable y. Here is the program.
function letters(x)
{ var y = ""; var k;
for (k in x)
{ switch(x[k])
{ case "a": case "A": y = y+"a"; break;
case "b": case "B": y = y+"b"; break;
case "c": case "C": y = y+"c"; break;
case "d": case "D": y = y+"d"; break;
case "e": case "E": y = y+"e"; break;
case "f": case "F": y = y+"f"; break;
case "g": case "G": y = y+"g"; break;
case "h": case "H": y = y+"h"; break;
case "i": case "I": y = y+"i"; break;
case "j": case "J": y = y+"j"; break;
case "k": case "K": y = y+"k"; break;
case "l": case "L": y = y+"l"; break;
case "m": case "M": y = y+"m"; break;
case "n": case "N": y = y+"n"; break;
case "o": case "O": y = y+"o"; break;
case "p": case "P": y = y+"p"; break;
case "q": case "Q": y = y+"q"; break;
case "r": case "R": y = y+"r"; break;
case "s": case "S": y = y+"s"; break;
case "t": case "T": y = y+"t"; break;
case "u": case "U": y = y+"u"; break;
case "v": case "V": y = y+"v"; break;
case "w": case "W": y = y+"w"; break;
case "x": case "X": y = y+"x"; break;
case "y": case "Y": y = y+"y"; break;
case "z": case "Z": y = y+"z"; break;
default: break; } }
return(y); }
All these programs can be tested with the following
button.
The Boolean data type.
The Boolean data types are named after
George Boole
who investigated this data type. Boolean data types are in the basic
case just a variable which can be take either the value 0 or the value 1;
in the more complicated case, it consists of several such digits which all
can either take the value 0 or the value 1. One such digit is called "a bit",
eight of them are called "a byte". Here a table of the basic operations
"not", "and", "or" and "exclusive or".
x
y
not x
x and y
x or y
x eor y
x
y
~x / !x
x & y / x && y
x | y / x || y
x ^ y
0
0
1
0
0
0
0
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
0
0101
1100
1010
0100
1101
1001
The second row describes how to do the operations on variables representing
a series of bits or just on one bit; there are different commands for the
two cases in Javascript. So if x represents 0101 and y represents 1100, then
~x, x | y, x & y and x ^ y are done bitwise and give the results in the
last row.
One can express all functions from {0,1}n to {0,1} using and,
or and not on the inputs. Here some examples.
x eor y is the same as (x or y) and (not(x) or not(y)).
maj(x,y,z) is 1 iff at least two of the inputs are one. So
maj(x,y,z) = (x and y) or (x and z) or (y and z).
the function which checks whether vwxy is a binary number being
a multiple of 3 is the following:
(not(v) and not(w) and not(x) and not(y)) or
(not(v) and not(w) and x and y) or
(not(v) and w and x and not(y)) or
(v and not(w) and not(x) and y) or
(v and w and not(x) and not(y)) or
(v and w and x and y).
Internally, all the memory and the logic of the computer circuit is
organised in Boolean logic. So numbers are stored in binary notation
with 10 for two, 11 for three, 100 for four, 101 for five, 110 for six,
111 for seven, 1000 for eight, 1001 for nine, 1010 for ten and so on.
The central processing unit of a computer calculates only with numbers
up to a given size where leading zeroes are added in for having all numbers
of the same length. Then addition of numbers and multiplication and other
such operations are organised by Boolean functions which are hardwired
into the central processing unit.
Sample Application of Boolean Operations.
In most cases, Boolean functions are only auxiliary and used to implement
the normal operations on numbers like addition, multiplication, subtraction
and so on. However there are some few applications where the Boolean
functions between (binary) numbers are directly utilised.
One of these applications is the game
Nim. In this game, two players
alternately reduce one number in a list of numbers by at least one
until all numbers are zero.
The player who does the last move and reaches 0,0,...,0 wins.
For example two players, Anke and Boris, play.
Start Position: 1,128,150,182
Anke moves to: 1,128,55,182
Boris moves to: 1,32,55,55
Anke moves to: 1,1,55,55
Boris moves to: 1,1,1,55
Anke moves to: 1,1,1,1
Boris moves to: 0,1,1,1
Anke moves to: 0,0,1,1
Boris moves to: 0,0,0,1
Anke wins by moving to: 0,0,0,0
It is difficult to see how to do the winning strategy of Anke with decimal
numbers. However, if one converts the numbers into binary, one can see that
whenever Anke has moved, the bitwise exclusive or of all numbers is 0,
that is, x[1] ^ x[2] ^ x[3] ^ x[4] is 0. Boris has now no good move and
will break this symmetry; however, when it is broken, Anke can find a move
to restore it. When drawn at random, the starting position is unlikely
to have the symmetry, therefore Anke can very likely move with the first
move into a winning position. Here a computer program which computes
the winning move.
function findmove(x)
{ var k; z = 0;
var y = new Array();
y = x.split(",");
for (k in y)
{ z = z ^ y[k]; }
if (z > 0)
{ for (k in y)
{ if ((z > 0) && ((z ^ y[k]) < y[k]))
{ y[k] = y[k] ^ z; z = -1 } } }
if (z == -1)
{ return("Recommended move for "+x+" is "+y); }
else
{ return("No good move for "+x+"; anything is fine"); } }
In this script, the program uses that the input x is a text consisting
of a comma-separated list of inputs (as the user might give it).
Thus the first two commands transform this list into an array of numbers.
In the first for-loop the program checks whether there is a good move, that
is, whether the game is not in a winning position for the opponent.
This is done by computing the xor of all numbers in the array y.
If a positive value is found then the program searches in the second
for-loop which of the array elements can be reduced in order to obtain
a symmetric situation where the xor is 0; note that here the new value
must be smaller than the old one. Once this is found, the z is set to -1
in order to denote that the adjustment of y has been done.
Afterwards the function returns the recommendation for the new move.
If there is no winning move, the differences between possible moves
is only psychological for the case that at certain moves the opponent
has more difficulties to figure out its winning move; however, if the
opponent has enough computational abilitiies, the player will eventually
lose the game, whatever move it makes.