A self-avoiding walk1 (SAW) consists of a series of steps on a rectangle grid, where the same point is visited once at the most. SAWs were introduced by chemist Paul Flory for modelling the behaviour of chain-like structures such as solvents and polymers. The three-dimensional interpretation of such structures doesn't allow that the same point is occupied more than once. It is extremely difficult to deduct the properties of SAWs in a mathematical manner. However, chemists and physicists have deducted various patterns of macromolecules, where the conjecture of their validity is based on numeric simulations. Moreover, it delivered Flory the Nobel prize in chemistry2 in 1974.

self-avoiding walk
self-avoiding walk

To be able to execute numeric simulations, we represent a polymer in a Cartesian surface as a sequence of monomers that are linked together based on the principle of a self-avoiding walk. We suppose that the first monomer is situated in the origin $$(0,0)$$ of that surface, and that the $$x$$ axis of the co-ordinate scale is pointed to the right, and the $$y$$ axis is pointing upwards. The next monomer in the sequence is always one unit above, under, left or right from the monomer before $$(x,y)$$, as illustrated in the picture below.

aangroeien van een polymeer
growth of a polymer

If we represent a position in the Cartesian surface as a tuple with two elements $$(x,y)$$, we can represent a polymer as a list of tuples, of which the first tuple represents the origin $$(0,0)$$.

Assignment

  1. Write a function grow that determines a position of the next monomer in a polymer for a monomer on a given position $$(x,y)$$ (where $$x, y \in \mathbb{Z}$$). This position must be chosen randomly from a number of possible positions above, under, left and right from the other monomer. Positions that are already taken by monomers of the polymer may not be chosen again. Two obligatory arguments must be given to the function. The first argument is a tuple with two elements that represent the position $$(x,y)$$ of the monomer before. The second argument is a check object that contains all positions (again, every position is represented as a tuple of two integers) that are already occupied by monomers of the polymer. As a result, the function must print one of the possible positions (again represented as a tuple of two elements) that lays around the position of the monomer before an has not yet been taken by other monomers of the polymer. If all four positions have already been taken, the function must return the value None as a result.

  2. Write a function polymer that prints a list of tuples with two elements as a result. This list represents a polymer, of which the tuples represent the positions  of the monomers within that polymer. The first element of the list is the tuple $$(0,0)$$ that represents the origin of the Cartesian surface. Use the function grow to add the position of the next monomer based on the previous positions. Keep repeating this procedure until all four positions around the last position are taken an the polymer can't be expanded anymore.

Example

>>> grow((0, 0), [(1, 0), (-1, 0), (0, -1)])
(0, 1)
>>> grow((0, 0), [(1, 0), (-1, 0), (0, 1)])
(0, -1)
>>> grow((0, 0), [(1, 0), (0, 1), (0, -1)])
(-1, 0)
>>> grow((0, 0), [(-1, 0), (0, 1), (0, -1)])
(1, 0)
>>> grow((0, 0), [(1, 0), (-1, 0), (0, 1), (0, -1)])

>>> polymer()
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1), (1, 1)]
>>> polymer()
[(0, 0), (1, 0), (2, 0), (2, -1), (3, -1), (4, -1), (4, 0), (4, 1), (3, 1), (3, 0)]