Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Драконов фрактал

Краен срок
07.05.2013 23:59

Срокът за предаване на решения е отминал

Както на всеки от нас се е случвало, да скучае на лекция, винаги опираме до момента, в който драскането по листа, който предварително е предназначен за смислени записки, е единственият ни вариант.

За ваше най-голямо щастие ние ще ви дадем най-ефективния начин за убиване на горепосоченото време, чертаейки драконов фрактал. Какво е драконов фрактал? Ако последвате няколкото стъпки по-долу, ще можете да си направите свой собствен драконов фрактал като този

Стъпки:

  1. Изберете си начална точка.
  2. Начертавате произволна отсечка нагоре: 0
  3. Приемате точката, до която сте стигнали за точка на въртене и завъртате целия обект на 90 градуса по часовниковата стрелка: 1
  4. Повтаряте стъпка 3 докато ви писне: 2

Ето и следващата итерация: 3

И идва време за условието на задача. Тъй като вече знаете как се прави драконов фрактал и вероятно може да си представите какво усилие се изисква за всяка следваща итерация, вие искате да си напише клас, който да ви помага да направите красивия драконов фрактал.

Трябва да напишете генератор с име dragon_fractal. При всяко извикване на next() върху генератора ние трябва да получаваме посока, в която да нарисуваме следващата линийка. Посоката трябва да бъде left, right, up или down като първата стъпка винаги връща up.

Ето как трябва да изглеждат първите няколко итерации.

>>> dragon = dragon_fractal()
>>> next(dragon)
'up'
>>> next(dragon)
'left'
>>> next(dragon)
'down'
>>> next(dragon)
'left'
>>> next(dragon)
'down'

Решения

Георги Ангелов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Георги Ангелов
RIGHT = 0
UP = 1
LEFT = 2
DOWN = 3
def rotate(direction, by_direction):
return (direction + by_direction) % 4
def direction_to_string(direction):
if direction == UP:
return 'up'
elif direction == RIGHT:
return 'right'
elif direction == DOWN:
return 'down'
elif direction == LEFT:
return 'left'
else:
raise Exception("Unknown direction {}".format(direction))
# Вариант без списък, с wikipedia
def dragon_fractal():
direction = RIGHT
step = 0
while True:
is_left = (((step & -step) << 1) & step) != 0
direction = rotate(DOWN if is_left else UP, direction)
step += 1
yield direction_to_string(direction)
# Вариант без wikipedia, със списък
# def dragon_fractal():
# fragment_size = 1
# lines = [UP]
#
# yield direction_to_string(lines[0])
#
# while True:
# for line_index in range(fragment_size - 1, -1, -1):
# step_direction = lines[line_index]
#
# new_direction = rotate(step_direction, UP)
# lines.append(new_direction)
#
# yield direction_to_string(new_direction)
#
# fragment_size = len(lines) 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Виктория Христова
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Виктория Христова
import math
OPPOSITES = {'up': 'left',
'left': 'down',
'down': 'right',
'right': 'up'}
def dragon_fractal():
direction = 'up'
iteration = 0
count = 0
steps = []
while True:
current_direction = direction
steps.append(direction)
count += 1
iteration = int(math.log(count, 2)) + 1
direction = OPPOSITES[steps[2 ** iteration - 1 - count]]
yield current_direction 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Александър Димитров
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Александър Димитров
def rotate90(direction):
if direction == 'up':
return 'left'
elif direction == 'down':
return 'right'
elif direction == 'left':
return 'down'
else:
return 'up'
def dragon_fractal():
points = ['up']
size = 1
while True:
for pointIndex in range(size//2, size):
yield points[pointIndex]
for pointIndex in range(size - 1, -1, -1):
points.append(rotate90(points[pointIndex]))
size *= 2 
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Христина Христова
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Христина Христова
DIRECTIONS = {0: 'right', 90: 'up', 180: 'left', 270: 'down'}
def dragon_fractal():
fractal_elements = [90]
while True:
for element in reversed(fractal_elements):
yield DIRECTIONS[fractal_elements[-1]]
fractal_elements.append((element + 90) % 360)
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Филарета Йорданова
  • Некоректно
  • 1 успешни тест(а)
  • 2 неуспешни тест(а)
Филарета Йорданова
def update_directions(directions):
for direction in reversed(directions):
if direction == "up":
directions.append("left")
elif direction == "left":
directions.append("down")
elif direction == "down":
directions.append("right")
elif direction == "right":
directions.append("up")
def dragon_fractal():
i = 0
directions = ["up"]
while True:
yield directions[i]
update_directions(directions)
i += 1 
EE.
======================================================================
ERROR: test_128th_result (test.DragonFractal)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "lib/language/python/runner.py", line 57, in thread
    raise TimeoutError
TimeoutError

======================================================================
ERROR: test_first_fifty_step (test.DragonFractal)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "lib/language/python/runner.py", line 57, in thread
    raise TimeoutError
TimeoutError

----------------------------------------------------------------------
Ran 3 tests in 4.063s

FAILED (errors=2)
Йордан Джамбазов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Йордан Джамбазов
def dragon_fractal():
step = 0
direction = 0
directions = ['right', 'up', 'left', 'down']
while True:
turn_right = step & (step - 1 ^ step) + 1
step += 1
direction = (direction + (-1 if turn_right else 1)) % 4
yield directions[direction]
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Мария Митева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Мария Митева
DIRECTIONS = ["up", "left", "down", "right"]
def dragon_fractal():
all_list = []
cur_list = []
direction = 0
while True:
yield DIRECTIONS[direction]
all_list.append(direction)
if len(cur_list) == 0:
cur_list = all_list[:]
direction = (cur_list[-1] + 1) % 4
del cur_list[-1] 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Георги Шопов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Георги Шопов
DIRECTIONS = ['left', 'up', 'right', 'down']
def calculate_direction(direction, rotation_number):
new_direction = (DIRECTIONS.index(direction) + rotation_number) % 4
return DIRECTIONS[new_direction]
def reverse(direction):
return calculate_direction(direction, 2)
def rotate_clockwise(direction):
return calculate_direction(direction, 1)
def dragon_fractal():
yield 'up'
distance = ['up']
while True:
added_distance = []
for direction in distance[::-1]:
next_direction = rotate_clockwise(reverse(direction))
yield next_direction
added_distance.append(next_direction)
distance += added_distance 
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Орлин Христов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Орлин Христов
from itertools import count, chain
DIRECTIONS = ('right', 'up', 'left', 'down')
class Rotator:
def __init__(self, states, rotations_prototype, start_index=0):
self._cursor = start_index
self._states = [state.lower() for state in states]
self._rotations = chain((0,), rotations_prototype())
def __next__(self):
self._cursor += next(self._rotations)
return self._item()
def __iter__(self):
return self
def _item(self, displacement=0):
return self._states[(self._cursor + displacement) % len(self._states)]
def __str__(self):
return '... {} <- {} -> {} ...'.format(self._item(-1),
self._item().upper(),
self._item(+1))
def dragon_rotations(base_rotation=+1):
rotations = [base_rotation, ]
for steps_taken in count():
while not steps_taken < len(rotations):
rotations.append(base_rotation)
rotations.extend([-rotation for rotation in rotations[-2::-1]])
yield rotations[steps_taken]
def dragon_fractal(start='up'):
return Rotator(DIRECTIONS, dragon_rotations, DIRECTIONS.index(start))
...
----------------------------------------------------------------------
Ran 3 tests in 0.004s

OK
Радослав Рачев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Радослав Рачев
DIRECTIONS_AFTER_ROTATION = {
'up': 'left', 'left': 'down', 'down': 'right', 'right': 'up'}
def dragon_fractal():
directions = []
current_directions = ['up']
while True:
for direction in current_directions:
yield direction
directions += current_directions
current_directions = [DIRECTIONS_AFTER_ROTATION[
direction] for direction in reversed(directions)] 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Деян Спиров
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Деян Спиров
DIRECTIONS = ['up', 'right', 'down', 'left']
class dragon_fractal:
def __init__(self):
self._fractal = ['up']
self._step_number = 0
def __iter__(self):
return self
def __next__(self):
self._step_number += 1
if self._step_number >= len(self._fractal):
self.grow()
return self._fractal[self._step_number - 1]
def grow(self):
self._fractal = self._fractal + self._rotated_reversed()
def _rotated_reversed(self):
"""Return a copy of the directions array,
rotated clockwise and then reversed"""
rotated = list(map(lambda direction:
DIRECTIONS[(DIRECTIONS.index(direction) - 1) % 4],
self._fractal))
rotated.reverse()
return rotated 
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Мария Терзиева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Мария Терзиева
def rotate(direction):
DIRECTIONS = {'up': 'left',
'left': 'down',
'down': 'right',
'right': 'up'}
for key, value in DIRECTIONS.items():
if key == direction:
return value
def rotate_list(my_list):
return [rotate(element) for element in my_list]
def dragon_fractal():
directions = ['up']
iteration = 0
while True:
if iteration == len(directions) - 1:
reversed_directions = list(reversed(directions))
directions += rotate_list(reversed_directions)
yield directions[iteration]
iteration += 1 
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Милан Миланов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Милан Миланов
def dragon_fractal():
fractal = ['up']
current_fractal_line_number = 0
flip = {'up': 'down', 'down': 'up', 'left': 'right', 'right': 'left'}
while True:
yield fractal[current_fractal_line_number]
current_fractal_line_number += 1
if current_fractal_line_number >= len(fractal):
limit = len(fractal) // 2 + 1
flipped_fractal_part = [flip[line] for line in fractal[:limit]]
fractal += ['left'] + flipped_fractal_part + fractal[limit:] 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Данаил Димитров
  • Некоректно
  • 0 успешни тест(а)
  • 3 неуспешни тест(а)
Данаил Димитров
def dragon_fractal():
fractal_body = ["up"]
WAYS_ROTATE = {"up": "left", "down": "right", "left": "down", "right": "up"}
fractal_lenght = 1
while True:
for part_to_rotate in reversed(fractal_body[:fractal_lenght]):
fractal_body.append(WAYS_ROTATE[part_to_rotate])
yield fractal_body[-1]
fractal_lenght *= 2 
FFF
======================================================================
FAIL: test_128th_result (test.DragonFractal)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "lib/language/python/runner.py", line 60, in thread
    raise it.exc_info[1]
  File "lib/language/python/runner.py", line 48, in run
    self.result = func(*args, **kwargs)
  File "/tmp/d20130513-14014-16wwwr9/test.py", line 37, in test_128th_result
    self.assertEqual(result[-1], 'left')
AssertionError: 'down' != 'left'
- down
+ left


======================================================================
FAIL: test_first_fifty_step (test.DragonFractal)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "lib/language/python/runner.py", line 60, in thread
    raise it.exc_info[1]
  File "lib/language/python/runner.py", line 48, in run
    self.result = func(*args, **kwargs)
  File "/tmp/d20130513-14014-16wwwr9/test.py", line 31, in test_first_fifty_step
    self.assertEqual(result, expected)
AssertionError: Lists differ: ['left', 'down', 'left', 'down... != ['up', 'left', 'down', 'left',...

First differing element 0:
left
up

+ ['up',
- ['left',
? ^

+  'left',
? ^

   'down',
   'left',
   'down',
   'right',
   'down',
   'left',
   'down',
   'right',
   'up',
   'right',
   'down',
   'right',
   'down',
   'left',
   'down',
   'right',
   'up',
   'right',
   'up',
   'left',
   'up',
   'right',
   'down',
   'right',
   'up',
   'right',
   'down',
   'right',
   'down',
   'left',
   'down',
   'right',
   'up',
   'right',
   'up',
   'left',
   'up',
   'right',
   'up',
   'left',
   'down',
   'left',
   'up',
   'left',
   'up',
   'right',
   'down',
-  'right',
?         ^

+  'right']
?         ^

-  'up']

======================================================================
FAIL: test_first_ten_steps (test.DragonFractal)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "lib/language/python/runner.py", line 60, in thread
    raise it.exc_info[1]
  File "lib/language/python/runner.py", line 48, in run
    self.result = func(*args, **kwargs)
  File "/tmp/d20130513-14014-16wwwr9/test.py", line 18, in test_first_ten_steps
    self.assertEqual(result, expected)
AssertionError: Lists differ: ['left', 'down', 'left', 'down... != ['up', 'left', 'down', 'left',...

First differing element 0:
left
up

+ ['up',
- ['left',
? ^

+  'left',
? ^

   'down',
   'left',
   'down',
   'right',
   'down',
   'left',
   'down',
-  'right',
?         ^

+  'right']
?         ^

-  'up']

----------------------------------------------------------------------
Ran 3 tests in 0.011s

FAILED (failures=3)
Станислав Гатев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Станислав Гатев
DIRECTIONS_CLOCKWISE_ROTATIONS = {
'up': 'left', 'left': 'down', 'down': 'right', 'right': 'up'}
def rotate_dir_clockwise(direction):
return DIRECTIONS_CLOCKWISE_ROTATIONS[direction]
def dragon_fractal():
directions = ['up']
current_dir_index = 0
while True:
yield directions[current_dir_index]
current_dir_index += 1
if current_dir_index == len(directions):
directions += list(map(rotate_dir_clockwise, directions[::-1])) 
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Мартин Костов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Мартин Костов
class dragon_fractal:
def __init__(self):
self.new_directions = []
self.directions = ['up']
self.rotate = {'up':'left',
'down':'right',
'right':'up',
'left':'down'}
def __iter__(self):
return self.directions
def __next__(self):
if not self.new_directions:
self.new_directions = self.directions[:]
self.directions.append(self.rotate[self.new_directions[-1]])
self.new_directions.pop()
return self.directions[-2]
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Нели Хатева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Нели Хатева
from collections import deque as deque
from itertools import count as count
UP = 'up'
DOWN = 'down'
LEFT = 'left'
RIGHT = 'right'
ROTATED = {UP: LEFT, DOWN: RIGHT, LEFT: DOWN, RIGHT: UP}
def dragon_fractal():
grapfic = deque()
yield UP
grapfic.append(UP)
while True:
for j in count(0):
for i in range(2**j - 1, -1, -1):
line = grapfic[i]
yield ROTATED[line]
grapfic.append(ROTATED[line]) 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Илия Ячев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Илия Ячев
class DragonFractalIterator():
def __init__(self):
self.current = ['up']
self.index = -1
self.rotate = {'up': 'left',
'left': 'down',
'down': 'right',
'right': 'up'}
def __iter__(self):
return self
def __next__(self):
self.index += 1
if self.index == len(self.current):
self.current += [self.rotate[x] for x in self.current[::-1]]
return self.current[self.index]
def dragon_fractal():
return DragonFractalIterator()
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Радослав Платиканов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Радослав Платиканов
UP = 'up'
DOWN = 'down'
LEFT = 'left'
RIGHT = 'right'
DIRECTIONS = (UP, RIGHT, DOWN, LEFT)
def dragon_fractal():
dir = 0
n = 1
while True:
yield DIRECTIONS[dir]
turn_right = (((n & -n) << 1) & n) != 0
if turn_right:
dir = (dir + 1) % 4
else:
dir = (dir + 3) % 4
n += 1
def dragon_fractal_old():
steps = [0]
pointer = 0
while True:
yield DIRECTIONS[steps[-1]]
if pointer < 0:
pointer = len(steps) - 1
steps.append((steps[pointer] + 3) % 4)
pointer = pointer - 1 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Николай Русев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Николай Русев
MOVES = ('up', 'right', 'down', 'left')
def dragon_fractal():
iteration = 0
move = 0
while True:
yield MOVES[move]
iteration += 1
turnClockwise = ((iteration & -iteration) << 1) & iteration is not 0
if turnClockwise:
move += 1
else:
move -= 1
move %= 4 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Николай Хубанов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Николай Хубанов
def dragon_fractal():
"""
For more information about the used algorithm:
http://en.wikipedia.org/wiki/Dragon_curve
"""
DIRECTIONS = ('up', 'left', 'down', 'right')
turn, direction = 0, 0
while True:
yield DIRECTIONS[direction % 4]
turn += 1
direction += 1 if (((turn & (-turn)) << 1) & turn) == 0 else -1 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Красимира Божанова
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Красимира Божанова
def dragon_fractal():
swap_direction = {'up': 'down', 'down': 'up',
'left': 'right', 'right': 'left'}
path = ['up']
counter = 0
while True:
yield path[counter]
counter += 1
if counter >= len(path):
path.append('left')
previous_length = len(path) - 1
length_to_swap = previous_length//2 + 1
for index in range(0, length_to_swap):
path.append(swap_direction[path[index]])
path.extend(path[length_to_swap:previous_length]) 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Иван Капукаранов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Иван Капукаранов
def dragon_fractal():
transformations = {'up': 'left', 'left': 'down',
'down': 'right', 'right': 'up'}
state = ['up']
direction = 'up'
while True:
moves = []
for index in range(1, len(state)+1):
yield direction
direction = transformations[state[-index]]
moves.append(direction)
for item in moves:
state.append(item) 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Христо Мохамед
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Христо Мохамед
def state_machine(state, place):
if(place >= len(state)):
temp = ' '
for character in state:
if character == 'R':
temp += 'L'
elif character == 'L':
temp += 'R'
temp += 'R'
temp = temp[::-1]
state = state + temp
if ' ' in temp:
state = state.replace(' ', '')
return state
def position_machine(state, place, position):
if state[place] == 'R':
if position == 'up':
return("left")
if position == 'left':
return("down")
if position == 'down':
return("right")
if position == "right":
return("up")
elif state[place] == 'L':
if position == 'up':
return("right")
if position == 'down':
return("left")
if position == 'left':
return("up")
if position == 'right':
return("down")
return position
def dragon_fractal():
position = "up"
state = 'R'
place = 0
while True:
yield position
state = state_machine(state, place)
position = position_machine(state, place, position)
place += 1
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Калоян Калудов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Калоян Калудов
def dragon_fractal():
def rotated(dir):
if dir == 'up':
dir = 'left'
elif dir == 'left':
dir = 'down'
elif dir == 'down':
dir = 'right'
elif dir == 'right':
dir = 'up'
return dir
yield 'up'
iterations = ['up']
while True:
new_iterations = iterations
for i in reversed(iterations):
yield rotated(i)
new_iterations.append(rotated(i))
iterations = new_iterations 
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK
Беатрис Бонева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Беатрис Бонева
def dragon_fractal():
n = 0
ways = ['right', 'up', 'left', 'down']
way = 0
while True:
first_bit = n & -n
left_or_right = n & (first_bit << 1)
way = (way + (-1 if left_or_right else 1)) % 4
n += 1
yield ways[way]
...
----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK