Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
|
Jugo algebra
In the past weeks, I have been further thinking about the question why some
Jugo puzzles have so few states that can
be reached. The puzzle 111011001010000 can only reach 32 different states.
I realized that there is an interesting algebra with two binary operators
and two sets of unary functions with some interesting properties. It all
started with the realization that applying a solution vector to a problem
vector is a commutative operation, meaning that the two vectors are swapped
the operation still returns the same value. A binary vector of length l
with an exclusive-or operator is an Abelian group equivalent to the l fold product of the C2
cyclic group with
the zero vector as identity element. If the exclusive-or operator is represented
by the '+' sign and the domain of all binary vectors of length l is
represented by Al, then the following hold:
- Closure: For all a, b in Al the
result of a + b is also in Al.
- Associativity: For all a, b, c in
Al the equation
(a + b) + c = a + (b + c)
holds.
- Identity element: For the zero vector (denoted by '0') the equation
0 + a = a + 0 = a
for each value a in Al.
- Inverse element: For all a in Al the equation
a + a = 0 holds, meaning that a
is its own inverse element.
- Commutativity: For all a, b in Al the
equation a + b = b + a
holds.
A product operator for binary vectors can be defined with a rotation
operator and the exclusive-or operator. The rotation operator roti
moves the bits in the vector i positions to the right, where elements
are wrapped around. The product of binary vectors a and b is defined
by adding all roti(b) vectors for which the i-th value
in vector a is equal to 1. When the product operator is represented by
the '·' sign and when the one vector, the vector where only the first
value is equal to 1 and all remaining value equal to 0, is represented
by '1', the the following hold:
- Closure: For all a, b in Al the
result of a · b is also in Al.
- Associativity: For all a, b, c in
Al the equation
(a · b) · c = a · (b · c)
holds.
- Identity element: For the one vector the equation
1 · a = a · 1 = a
for each value a in Al.
- Commutativity: For all a, b in Al the
equation a · b = b · a
holds.
There is no inverse element for the product operator. The product operator
forms a commutative monoid.
The product operator is distributive over the exclusive-or operator, which
means that the following hold for all a, b, c in
Al:
- a · (b + c) = (a · b) + (a · c)
- (a + b) · c = (a · c) + (b · c)
This means that ( Al, +, - ) is
a ring.
With respect to roti unary operation, the following holds:
- roti · rotj = rot(i+j) modulo l
- For all a, b in Al:
roti(a) + roti(b) = roti(a + b)
- For all a, b in Al:
roti(a) · b = roti(a · b)
Besides the rotation operator (which is a permutation operator) there is
another permutation operator with some interesting properties. This
reorder operator is defined for all s where 1 < s < l
and s is not a divider of l. The reorders
operator moves the value at position i of the vector to position
i·s modulo l of the resulting
vector. For the rotation and reorder operators the following holds:
- reorderi · reorderj =reorderj · reorderi = reorderi · j modulo l.
- reorderi · rotj = rotk · reorderi
where k = i · j-1 modulo l
if j-1, the inverse of j, defined by j · j-1 modulo l = 1,
exists.
So far, I did not discover an equality involving the reorder operation and
the product operator. I wrote a C++ program
which checks the nontrivial equivalences.
Jugo 111101011001000
This evening, I discovered that the Jugo puzzle
111101011001000 can only reach 16 possible states. This means that this is
the easiest possible puzzle with 15 leaves to solve: either all leaves are
in the correct position or it can be solved with exactly one move. Any
other move will turn it into another state with the same leaves turned with
some rotation. I find that a rather remarkable property. The images here
on the right shows all the results when the zero rotated vector is
combined with one to fourteen positions rotated. As can be seen, each
row contains the same, albeit rotated, pattern. Here are some other
patterns with 64 or less solutions:
1 1 2
2 10 4
3 100 8
4 1100 8
5 11000 16
5 11110 16
6 101000 16
6 111000 16
6 111100 16
7 1110100 8
8 11110000 32
9 100100000 64
9 110110000 64
9 111111000 64
10 1111100000 64
10 1011101000 64
12 101111010000 32
14 11011110010000 32
15 111101011001000 16
My gut feelings tells me that there is a pattern of length 31 which
can only reach 32 different states and that all patterns with lengths
in between reach 32 or more states. If you search for the sequence
111101011001000 on the internet it will turn up some interesting
results. It appears that the sequence can be produced by a four
state shift register and exclusive-or operator. In this sequence
each digit is the exclusive-or of the third and fourth digit to
the right.
Pseudo-random image
This image is created with a pseudo-random generated created from
a 7 bit shift register with an exclusive-or operator. This pattern
is 127 bit long and contains all possible 7 bit numbers except for
zero. Each row in this image contains the same pattern, but shifted
a different number of positions. This is created by applying an exclusive-or
on the pattern and a pattern that is shifted 11 positions for each
next row. It is surprising how random this image looks, although in
it is not really random. It is too 'smooth' to be truely random.
Today, the final report by the Dutch Safety Board about the partial
collapse of the roof of the Grolsch Veste
on July 7 last year was present.
(Full reports in Dutch and
summary in English and German.) During the planning stage,
the design was not assessed in terms of feasibility and none of the
parties involved calculated the strength of the roof structure as it
would be while under construction. The main constractor decided to
change the planning and start completing the roof while its steel
construction was not yet completely finished. The main contracter
and the steel construction specialist both presumed that the other
had checked whether it was okay to do this.
God Emperor of Dune
I finished reading God-Keizer op Duin
(the Dutch translation of God Emperor of Dune) by Frank Herbert, which I started
reading on June 16, the day I bought the
book for € 7.95 from bookshop De Slegte. I read the book for the first time while
at the university. I remember that I read it in students library
Then I found it a rather boring book, one of the least interesting
of the whole serie. However, this time, I found it a rather interesting
book to read. Maybe it is because I am much older now.
Peter Struycken: catalogue
I received the catalogue Peter Struycken Neue Gemälde, Skulpturen und Zeichnungen
for the exhibition held from May 27 till July 10, 1977 in
Düsseldorf, Germany. I ordered this last Monday from
Book2 Antiquariaat.
Since last weekend, I have been working on a page about Peter Struycken, his
exhibitions, catalogues, books, and works. Tonight, I have added all the data
from the catalogue that I received today.
Symple in CodeCup 2013
It has been announced that the game Symple
will the subject of the CodeCup 2013.
For this contest one has to write a program that can play the game and
win from other programs. The maximum execution time per game is only 30
seconde, which does not seem much, given the large number of possible
moves in the middle game.
Flowers in magnolia
Our magnolia started to get some flowers again,
the second time this year, in the past days. They are all, about twenty,
I guess, on the new brances, which grow straight to the sky. Sadly, I have
to prune it soon, because it is showing too strong. Maybe simply cutting
the new branches is not enough anymore. That is the problem bit plants and
trees that grow older, you prune the branches, but the roots grow further
and further, making the branches and the leaves growing stronger and
stronger. Earlier this year, I pruned our willow, but now it is full with
branches and leaves again, which surprises me a little. Maybe it is because
I left some small branches.
Introduction to Sartre
At 11:54, I bought the book Sartre from the book series Kopstukken
Filosofie (leaders in philosophy) by Martin Suhr
(ISBN:9789056375010) for € 12.50 from bookshop Broekhuis.
Groninger Museum
Today, I went to the Groninger Museum to look at some material with respect to the art of
Peter Struycken. At 5:54, I left from home,
and I took the train of 6:27 to arrive at Groningen at 8:52. I walked around
the city and looked around bookshop Selexyz for a quarter of an hour, and
arrive just before 10 o'clock at the museum. I was the second person to buy
tickets. At home, I had made a list of books and materials that I would like
to see, but I left that at home. I spend the first half our recreating the
list in the Info Center. Then I went looking for the person responsible for
the library. Turned out that he had only one booklet at hand and that he
had to collect the others from the depot, which is situated at the top of
the building. I had to wait till about half past 12 before he came back.
I took the picture shown here, while waiting. I had not brought any book
with me into the library and I did not want to walk away. The next hours, I
spend making notes and taking lots of pictures, over one hundred, I guess.
At 14:48, I left the museum after having returned the materials and thanking
the clerk. I was a little disappointed about the amount of new information
that I have found, at least information that could be easily integrated
with the information that I already have collected.
This months interesting links
Home
| June 2012
| August 2012
| Random memories
Monday, July 2, 2012
Tuesday, July 3, 2012
Monday, July 23, 2012
Friday, July 27, 2012