Duplicate argument

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

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

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

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

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

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

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

Стъпки:

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

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

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

Трябва да си създадете тип DragonFractal. При всяко извикване на метода му Next() string, той трябва да връща посока, в която да се нарисува следващата му линийка. Посоката трябва да бъде стринг "left", "right", "up" или "down" като първата стъпка винаги е "up".

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

dragon := new(DragonFractal)
dragon.Next() // 'up'
dragon.Next() // 'left'
dragon.Next() // 'down'
dragon.Next() // 'left'
dragon.Next() // 'down'
dragon.Next() // 'right'
dragon.Next() // 'down'
dragon.Next() // 'left'

Hint: Вероятно вече сте осъзнали, че на всяко извикване имате нужда от предишните стъпки. unexported стойност, в типа в DragonFractal би ви свършила перфектна работа.

Решения

Михаил Стойков
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Михаил Стойков
package main
type DragonFractal struct {
path []byte
step int
}
const (
up byte = iota
left
down
right
)
var directions [4]string = [4]string{"up", "left", "down", "right"}
func (d *DragonFractal) Next() (step string) {
switch d.step {
case 0:
d.path = make([]byte, 1)
d.path[d.step] = up
case len(d.path):
length := len(d.path)
newPath := make([]byte, length*2)
copy(newPath[:], d.path[:])
for index := 0; index < length; index++ {
newPath[length+index] = d.path[length-index-1] + 1
newPath[length+index] %= 4
}
d.path = newPath
}
step = directions[d.path[d.step]]
d.step++
return
}
PASS
ok  	_/tmp/d20131025-20908-jcahnh	0.011s
PASS
ok  	_/tmp/d20131025-20908-jcahnh	0.011s
PASS
ok  	_/tmp/d20131025-20908-jcahnh	0.011s
Ива Тотева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Ива Тотева
package main
const (
left = iota
down
right
up
)
func toString(direction int) string {
switch direction {
case left:
return "left"
case up:
return "up"
case right:
return "right"
case down:
return "down"
}
//A Debug.Assert() or an Error would be better.
return ""
}
func rotate90(direction int) int {
return (direction + 1) % 4
}
type DragonFractal struct {
previousDirections []int
currentIteration int
}
func (dragon *DragonFractal) calculateNextPowerOfTwoSteps() {
if dragon.currentIteration == 0 {
dragon.previousDirections = append(dragon.previousDirections, up)
} else {
for i := range dragon.previousDirections {
dragon.previousDirections = append(dragon.previousDirections, rotate90(dragon.previousDirections[dragon.currentIteration-i-1]))
}
}
}
func (dragon *DragonFractal) Next() string {
if dragon.currentIteration >= len(dragon.previousDirections) {
dragon.calculateNextPowerOfTwoSteps()
}
dragon.currentIteration++
return toString(dragon.previousDirections[dragon.currentIteration-1])
}
PASS
ok  	_/tmp/d20131025-20908-uhrqnb	0.011s
PASS
ok  	_/tmp/d20131025-20908-uhrqnb	0.011s
PASS
ok  	_/tmp/d20131025-20908-uhrqnb	0.011s
Александър Димитров
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Александър Димитров
package main
func rotate(direction string) string {
if direction == "up" {
return "left"
} else if direction == "down" {
return "right"
} else if direction == "left" {
return "down"
} else {
return "up"
}
}
type DragonFractal struct {
directions []string
currentIndex int
initialized bool
}
func (d *DragonFractal) initialize() {
d.directions = []string{"up"}
d.initialized = true
}
func (d *DragonFractal) Next() string {
if d.initialized {
if d.currentIndex == len(d.directions) {
rotatedDirections := []string{}
for index := len(d.directions) - 1; index >= 0; index-- {
rotatedDirections = append(rotatedDirections, rotate(d.directions[index]))
}
d.directions = append(d.directions, rotatedDirections...)
}
} else {
d.initialize()
}
d.currentIndex++
return d.directions[d.currentIndex-1]
}
PASS
ok  	_/tmp/d20131025-20908-6r5gwz	0.011s
PASS
ok  	_/tmp/d20131025-20908-6r5gwz	0.011s
PASS
ok  	_/tmp/d20131025-20908-6r5gwz	0.011s
Георги Терзиев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Георги Терзиев
package main
type DragonFractal struct {
current uint64
}
func (d *DragonFractal) Next() string {
d.current += 1
return transform(d.current)
}
func transform(u uint64) string {
powerOf2 := maxPowerOf2LessThanOrEqualTo(u)
switch {
case u == 1:
return "up"
case u == powerOf2:
return next(transform(1))
default:
return next(transform(2*powerOf2 - u + 1))
}
}
func maxPowerOf2LessThanOrEqualTo(u uint64) uint64 {
switch u {
case 1:
return 1
default:
var result uint64
result = 2
nextPower := result * 2
for nextPower <= u {
result = nextPower
nextPower = result * 2
}
return result
}
}
func next(s string) string {
switch {
case s == "up":
return "left"
case s == "left":
return "down"
case s == "down":
return "right"
case s == "right":
return "up"
}
return ""
}
PASS
ok  	_/tmp/d20131025-20908-1edsiu6	0.011s
PASS
ok  	_/tmp/d20131025-20908-1edsiu6	0.011s
PASS
ok  	_/tmp/d20131025-20908-1edsiu6	0.011s
Мартин Ангелов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Мартин Ангелов
package main
import (
"fmt"
)
type DragonFractal struct {
prevSteps, nextSteps []string
}
/* Returns the position of a string in a string slice
-1 if the string does not exist */
func getPos(stringSlice []string, needle string) int {
for p, v := range stringSlice {
if v == needle {
return p
}
}
return -1
}
func (d *DragonFractal) CalcNextSteps() {
transition := []string{
"up",
"left",
"down",
"right",
}
/*Last element of the new curve depends only on the first element
in first curve. The element before the last element in new curve,
depends only on the second element of the old curve and so on.
When rotating clockwise, up becomes left, left becomes down,
down becomes right and right becomes up.*/
for i := len(d.prevSteps) - 1; i >= 0; i-- {
pos := getPos(transition, d.prevSteps[i])
d.nextSteps = append(d.nextSteps, transition[(pos+1)%len(transition)])
}
}
func (d *DragonFractal) Next() string {
if d.prevSteps == nil {
d.prevSteps = make([]string, 1, 8)
d.prevSteps[0] = "up"
return d.prevSteps[0]
}
if len(d.nextSteps) == 0 {
d.CalcNextSteps()
}
curStep := d.nextSteps[0]
d.nextSteps = d.nextSteps[1:]
d.prevSteps = append(d.prevSteps, curStep)
return curStep
}
func main() {
dragon := new(DragonFractal)
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
fmt.Println(dragon.Next())
}
PASS
ok  	_/tmp/d20131025-20908-1umfk1g	0.011s
PASS
ok  	_/tmp/d20131025-20908-1umfk1g	0.011s
PASS
ok  	_/tmp/d20131025-20908-1umfk1g	0.011s
Георги Пеев
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Георги Пеев
package main
//linesOrientation -> 1-up, 2-right, 3-down, 4-left
type DragonFractal struct {
linesDirections []int
LastLineNumber int
}
func (df *DragonFractal) Next() string {
df.LastLineNumber++
if df.LastLineNumber > len(df.linesDirections) {
df.CalcNextPart()
}
direction := df.linesDirections[df.LastLineNumber - 1]
switch {
case direction == 1:
return "up"
case direction == 2:
return "right"
case direction == 3:
return "down"
case direction == 4:
return "left"
default:
return "oops"
}
}
func (df *DragonFractal) CalcNextPart() {
if len(df.linesDirections) == 0 {
df.linesDirections = make([]int, 1)
df.linesDirections[0] = 1
} else {
oldLen := len(df.linesDirections)
newLen := 2 * oldLen
newLinesDirections := make([]int, newLen)
copy(newLinesDirections, df.linesDirections)
for i := oldLen; i < newLen; i++ {
newDirection := df.linesDirections[newLen - 1 - i] - 1
if newDirection < 1 {
newDirection = 4
}
newLinesDirections[i] = newDirection
}
df.linesDirections = newLinesDirections
}
}
PASS
ok  	_/tmp/d20131025-20908-1tk2i0f	0.011s
PASS
ok  	_/tmp/d20131025-20908-1tk2i0f	0.011s
PASS
ok  	_/tmp/d20131025-20908-1tk2i0f	0.011s
Недялко Дяков
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Недялко Дяков
package main
const (
START int = iota
UP
LEFT
DOWN
RIGHT
)
type DragonFractal struct {
history []int
step int
iterationStep int
}
func (d *DragonFractal) Next() string {
if d.step == 0 {
d.history = make([]int, 1)
d.history = append(d.history, START)
d.step = 1
}
if d.step/2 <= d.iterationStep {
d.iterationStep = 0
}
direction := d.history[d.step-(d.iterationStep*2)] + 1
if direction == 5 {
direction = 1
}
d.step += 1
d.iterationStep += 1
d.history = append(d.history, direction)
return d.directionAsString(direction)
}
func (d *DragonFractal) directionAsString(direction int) string {
switch direction {
case UP:
return "up"
case LEFT:
return "left"
case DOWN:
return "down"
case RIGHT:
return "right"
}
return ""
}
PASS
ok  	_/tmp/d20131025-20908-xesfl4	0.011s
PASS
ok  	_/tmp/d20131025-20908-xesfl4	0.011s
PASS
ok  	_/tmp/d20131025-20908-xesfl4	0.011s
Александър Иванов
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Александър Иванов
package main
type DragonFractal struct {
previousSteps, allSteps []string
stepPosition int
}
func (df *DragonFractal) Next() string {
step := df.currentStep()
df.allSteps = append(df.allSteps, step)
df.stepPosition--
if df.stepPosition < 0 {
df.previousSteps = df.allSteps
df.stepPosition = len(df.allSteps) - 1
}
return step
}
func (df DragonFractal) currentStep() string {
if len(df.allSteps) == 0 {
return "up"
}
return turnStep(df.previousSteps[df.stepPosition])
}
func turnStep(step string) string {
switch step {
case "up":
return "left"
case "left":
return "down"
case "down":
return "right"
case "right":
return "up"
default:
panic("unknown step")
}
}
PASS
ok  	_/tmp/d20131025-20908-mmg0dr	0.015s
PASS
ok  	_/tmp/d20131025-20908-mmg0dr	0.012s
PASS
ok  	_/tmp/d20131025-20908-mmg0dr	0.047s
Габриел Ванков
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Габриел Ванков
package main
var current int = 0
type DragonFractal struct {
path []string
reversePath []string
}
func (df *DragonFractal) Next() (ret string) {
if len(df.path) == 0 {
df.path = append(df.path, "up")
current = 1
df.reversePath = append(df.reversePath, "down")
ret = "up"
return
}
if current >= len(df.reversePath) {
current = 0
df.reversePath = make([]string, 0)
for i := len(df.path) - 1; i >= 0; i-- {
switch {
case df.path[i] == "up":
df.reversePath = append(df.reversePath, "down")
case df.path[i] == "down":
df.reversePath = append(df.reversePath, "up")
case df.path[i] == "left":
df.reversePath = append(df.reversePath, "right")
case df.path[i] == "right":
df.reversePath = append(df.reversePath, "left")
}
}
}
switch {
case df.reversePath[current] == "up":
df.path = append(df.path, "right")
current++
ret = "right"
case df.reversePath[current] == "down":
df.path = append(df.path, "left")
current++
ret = "left"
case df.reversePath[current] == "right":
df.path = append(df.path, "down")
current++
ret = "down"
case df.reversePath[current] == "left":
df.path = append(df.path, "up")
current++
ret = "up"
}
return
}
PASS
ok  	_/tmp/d20131025-20908-9av0a	0.011s
PASS
ok  	_/tmp/d20131025-20908-9av0a	0.011s
PASS
ok  	_/tmp/d20131025-20908-9av0a	0.011s
Мария Терзиева
  • Коректно
  • 3 успешни тест(а)
  • 0 неуспешни тест(а)
Мария Терзиева
package main
type DragonFractal struct {
directions []string
iteration int
}
func (fractal *DragonFractal) Next() string {
directionPairs := map[string]string{
"up": "left",
"left": "down",
"down": "right",
"right": "up",
}
if fractal.iteration == 0 {
fractal.directions = append(fractal.directions, "up")
}
next := fractal.directions[fractal.iteration]
if fractal.iteration == len(fractal.directions)-1 {
for index := fractal.iteration; index > -1; index-- {
current := fractal.directions[index]
fractal.directions = append(fractal.directions, directionPairs[current])
}
}
fractal.iteration++
return next
}
PASS
ok  	_/tmp/d20131025-20908-14d4s22	0.011s
PASS
ok  	_/tmp/d20131025-20908-14d4s22	0.011s
PASS
ok  	_/tmp/d20131025-20908-14d4s22	0.011s
Димитър Дишев
  • Некоректно
  • 0 успешни тест(а)
  • 3 неуспешни тест(а)
Димитър Дишев
package main
import "fmt"
type DragonFractal struct {
allSteps []string
timesCalledMethodNext int
}
func reverse(input []string) []string {
for i, j := 0, len(input)-1; i < j; i, j = i+1, j-1 {
input[i], input[j] = input[j], input[i]
}
return input
}
func (d *DragonFractal) push(item string) {
for i := range d.allSteps {
if d.allSteps[i] == "" {
d.allSteps[i] = item
break
}
}
}
func (d *DragonFractal) countElements() int {
count := 0
for i := range d.allSteps {
if d.allSteps[i] != "" {
count++
}
}
return count
}
func (d *DragonFractal) generateSteps() {
var nextRotation []string
if len(d.allSteps) == 0 {
d.allSteps = make([]string, 1)
d.allSteps[0] = "up"
} else {
nextRotation = append(nextRotation, d.allSteps...)
if d.countElements() > len(d.allSteps)/2 {
t := make([]string, len(d.allSteps)*2)
copy(t, d.allSteps)
d.allSteps = t
}
for i := range nextRotation {
switch nextRotation[i] {
case "up":
nextRotation[i] = "left"
case "left":
nextRotation[i] = "down"
case "right":
nextRotation[i] = "up"
case "down":
nextRotation[i] = "right"
}
}
nextRotation = reverse(nextRotation)
for i := range nextRotation {
d.push(nextRotation[i])
}
}
}
func (d *DragonFractal) Next() {
d.timesCalledMethodNext++
if d.timesCalledMethodNext > len(d.allSteps)/2 {
d.generateSteps()
}
fmt.Println(d.allSteps[d.timesCalledMethodNext-1])
}
# _/tmp/d20131025-20908-ra67o2
./solution_test.go:10: dragon.Next() used as value
./solution_test.go:19: dragon.Next() used as value
./solution_test.go:23: dragon.Next() used as value
./solution_test.go:27: dragon.Next() used as value
./solution_test.go:31: dragon.Next() used as value
./solution_test.go:40: dragon.Next() used as value
FAIL	_/tmp/d20131025-20908-ra67o2 [build failed]
# _/tmp/d20131025-20908-ra67o2
./solution_test.go:10: dragon.Next() used as value
./solution_test.go:19: dragon.Next() used as value
./solution_test.go:23: dragon.Next() used as value
./solution_test.go:27: dragon.Next() used as value
./solution_test.go:31: dragon.Next() used as value
./solution_test.go:40: dragon.Next() used as value
FAIL	_/tmp/d20131025-20908-ra67o2 [build failed]
# _/tmp/d20131025-20908-ra67o2
./solution_test.go:10: dragon.Next() used as value
./solution_test.go:19: dragon.Next() used as value
./solution_test.go:23: dragon.Next() used as value
./solution_test.go:27: dragon.Next() used as value
./solution_test.go:31: dragon.Next() used as value
./solution_test.go:40: dragon.Next() used as value
FAIL	_/tmp/d20131025-20908-ra67o2 [build failed]