non-greedy повторители

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

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

Решение на Log Parsing от Йосиф Цветков

Обратно към всички решения

Към профила на Йосиф Цветков

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 10 успешни тест(а)
  • 0 неуспешни тест(а)

Код

package main
func Map(data []string, mapper func(string) string) []string {
mapped := make([]string, len(data))
for index, value := range data {
mapped[index] = mapper(value)
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := make([]string, 0, len(data))
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
if len(data) != 0 {
reduced = data[0]
for index := 1; index <= len(data)-1; index++ {
reduced = combinator(reduced, data[index])
}
}
return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
}

Лог от изпълнението

PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.014s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.016s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.012s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s
PASS
ok  	_/tmp/d20141023-10368-1bcmc9o	0.011s

История (11 версии и 12 коментара)

Йосиф обнови решението на 15.10.2014 13:32 (преди над 3 години)

+package main
+
+func Map(data []string, mapper func(string) string) []string {
+ for index, value := range data {
+ data[index] = mapper(value)
+ }
+ return data
+}
+
+func Filter(data []string, predicate func(string) bool) []string {
+ filtered := []string{}
+ for _, value := range data {
+ if predicate(value) {
+ filtered = append(filtered, value)
+ }
+ }
+ return filtered
+}
+
+func Reduce(data []string, combinator func(string, string) string) string {
+ var final string
+ for _, value := range data {
+ final = combinator(final, value)
+ }
+ return final
+}
+
+func Any(data []string, predicate func(string) bool) bool {
+ for _, value := range data {
+ if predicate(value) {
+ return true
+ }
+ }
+ return false
+}
+
+func All(data []string, predicate func(string) bool) bool {
+ for _, value := range data {
+ if predicate(value) {
+ return false
+ }
+ }
+ return true
+}

Йосиф обнови решението на 15.10.2014 13:57 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
- for index, value := range data {
- data[index] = mapper(value)
+ mapped := []string{}
+ for _, value := range data {
+ mapped = append(mapped, mapper(value))
}
- return data
+ return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := []string{}
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) string {
var final string
for _, value := range data {
final = combinator(final, value)
}
return final
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return false
}
}
return true
}

Йосиф обнови решението на 15.10.2014 13:59 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
mapped := []string{}
for _, value := range data {
mapped = append(mapped, mapper(value))
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := []string{}
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) string {
- var final string
+ var reduced string
for _, value := range data {
- final = combinator(final, value)
+ reduced = combinator(reduced, value)
}
- return final
+ return reduced
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return false
}
}
return true
}

Йосиф обнови решението на 16.10.2014 02:41 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
mapped := []string{}
for _, value := range data {
mapped = append(mapped, mapper(value))
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := []string{}
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) string {
var reduced string
for _, value := range data {
reduced = combinator(reduced, value)
}
return reduced
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
- if predicate(value) {
+ if !predicate(value) {
return false
}
}
return true
}

Йосиф обнови решението на 17.10.2014 19:30 (преди над 3 години)

package main
-func Map(data []string, mapper func(string) string) []string {
- mapped := []string{}
+func Map(data []string, mapper func(string) string) (mapped []string) {
for _, value := range data {
mapped = append(mapped, mapper(value))
}
- return mapped
+ return
}
-func Filter(data []string, predicate func(string) bool) []string {
- filtered := []string{}
+func Filter(data []string, predicate func(string) bool) (filtered []string) {
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
- return filtered
+ return
}
-func Reduce(data []string, combinator func(string, string) string) string {
- var reduced string
+func Reduce(data []string, combinator func(string, string) string) (reduced string) {
for _, value := range data {
reduced = combinator(reduced, value)
}
- return reduced
+ return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
}

Йосиф обнови решението на 17.10.2014 21:07 (преди над 3 години)

package main
-func Map(data []string, mapper func(string) string) (mapped []string) {
+func Map(data []string, mapper func(string) string) []string {
+ mapped := []string{}
for _, value := range data {
mapped = append(mapped, mapper(value))
}
- return
+ return mapped
}
-func Filter(data []string, predicate func(string) bool) (filtered []string) {
+func Filter(data []string, predicate func(string) bool) []string {
+ filtered := []string{}
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
- return
+ return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
for _, value := range data {
reduced = combinator(reduced, value)
}
return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
-}
+}

Йосиф обнови решението на 17.10.2014 21:17 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
mapped := []string{}
for _, value := range data {
mapped = append(mapped, mapper(value))
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := []string{}
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
+ if len(data) == 1 {
+ return combinator(data[0], "")
+ }
for _, value := range data {
reduced = combinator(reduced, value)
}
return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
}

Стига да си ги имплеметираш и там. Можете да ползвате цялата стандартна библиотека и каквото вие си напишете.

Относно решението ти:

  1. Хитър Reduce
  2. В Map и Filter се правят ненужно количество копирания на масиви.

Йосиф обнови решението на 18.10.2014 21:36 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
- mapped := []string{}
- for _, value := range data {
- mapped = append(mapped, mapper(value))
+ mapped := make([]string, len(data))
+ for index, value := range data {
+ mapped[index] = mapper(value)
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
- filtered := []string{}
+ filtered := make([]string, 0, cap(data))
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
- if len(data) == 1 {
+ switch len(data) {
+ case 0:
+ return
+ case 1:
return combinator(data[0], "")
+ default:
+ reduced = combinator(data[0], data[1])
+ for i := 2; i <= len(data)-1; i++ {
+ reduced = combinator(reduced, data[i])
+ }
+ return
}
- for _, value := range data {
- reduced = combinator(reduced, value)
- }
- return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
}

Сега вече не би трябвало да има memory leak/неграмотно ползване на ресурси.

Относно Reduce, беше готин(ако не друго, беше кратък) но е некоректен.

input := []string{"", "12"}
expected := "12aa"

strangeConcat := func(s1, s2 string) string {
    return s1 + s1 + s2 + "aa"
}
result := Reduce(input, strangeConcat)

В този случай result има стойност "аааа12аа" а не коректното "12аа" и затова съм пренаписал Reduce по толкова не-готин начин. Ще се помъча още (може някоя рекурсия да помогне) но едва ли ще измисля 3-редова реализация която да върви във всички случаи.

Йосиф обнови решението на 18.10.2014 22:21 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
mapped := make([]string, len(data))
for index, value := range data {
mapped[index] = mapper(value)
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := make([]string, 0, cap(data))
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
- switch len(data) {
- case 0:
- return
- case 1:
+ if len(data) == 1 {
return combinator(data[0], "")
- default:
+ } else if len(data) >= 2 {
reduced = combinator(data[0], data[1])
for i := 2; i <= len(data)-1; i++ {
reduced = combinator(reduced, data[i])
}
- return
}
+ return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
}

  • Защо смяташ че Reduce-а трябва да комбинира началния си аргумент ако няма други ?

  • Върни Filter-а да е с len(data) - в добрия случай няма никаква разлика в лошия случай заделяш повече памет отколкото може да ти потрябва.

Йосиф обнови решението на 20.10.2014 16:05 (преди над 3 години)

package main
func Map(data []string, mapper func(string) string) []string {
mapped := make([]string, len(data))
for index, value := range data {
mapped[index] = mapper(value)
}
return mapped
}
func Filter(data []string, predicate func(string) bool) []string {
filtered := make([]string, 0, cap(data))
for _, value := range data {
if predicate(value) {
filtered = append(filtered, value)
}
}
return filtered
}
func Reduce(data []string, combinator func(string, string) string) (reduced string) {
- if len(data) == 1 {
- return combinator(data[0], "")
- } else if len(data) >= 2 {
- reduced = combinator(data[0], data[1])
- for i := 2; i <= len(data)-1; i++ {
- reduced = combinator(reduced, data[i])
+ if len(data) != 0 {
+ reduced = data[0]
+ for index := 1; index <= len(data)-1; index++ {
+ reduced = combinator(reduced, data[index])
}
}
return
}
func Any(data []string, predicate func(string) bool) bool {
for _, value := range data {
if predicate(value) {
return true
}
}
return false
}
func All(data []string, predicate func(string) bool) bool {
for _, value := range data {
if !predicate(value) {
return false
}
}
return true
-}
+}

  • Защо смяташ че Reduce-а трябва да комбинира началния си аргумент ако няма други ?

    • Главно защото на Reduce се подава функция на два аргумента, като в тази функция всеки аргумент може да бъде модифициран, като например в:

    strangeConcat := func(s1, s2 string) string {
    return s1 + "ala" + s2 + "bala"
}

    и прецених че така е по-логично(поне за мен). Но след като го спомена и като прочетох "За начална стойност ползвайте първата стойност от масива." явно ще връщам първия(и единствен) елемент на слайса.

  • Върни Filter-а да е с len(data) - в добрия случай няма никаква разлика в лошия случай заделяш повече памет отколкото може да ти потрябва.

    • Грешно ли ще е ако оставя Filter както си е понеже ако заменя filtered := make([]string, 0, cap(data)) със filtered := make([]string, len(data)), то почват да ми се "чупят" тестове, по-специално TestFilterWithFalse и TestFilterWithTrue, тестове споделени с курса от Иван Боршуков? Доколкото разбирам, filtered := make([]string, len(data)) ми инициализира слайса със празни стрингове и това омазва всичко.

    Йосиф обнови решението на 20.10.2014 23:04 (преди над 3 години)

    package main
    func Map(data []string, mapper func(string) string) []string {
    mapped := make([]string, len(data))
    for index, value := range data {
    mapped[index] = mapper(value)
    }
    return mapped
    }
    func Filter(data []string, predicate func(string) bool) []string {
    - filtered := make([]string, 0, cap(data))
    + filtered := make([]string, 0, len(data))
    for _, value := range data {
    if predicate(value) {
    filtered = append(filtered, value)
    }
    }
    return filtered
    }
    func Reduce(data []string, combinator func(string, string) string) (reduced string) {
    if len(data) != 0 {
    reduced = data[0]
    for index := 1; index <= len(data)-1; index++ {
    reduced = combinator(reduced, data[index])
    }
    }
    return
    }
    func Any(data []string, predicate func(string) bool) bool {
    for _, value := range data {
    if predicate(value) {
    return true
    }
    }
    return false
    }
    func All(data []string, predicate func(string) bool) bool {
    for _, value := range data {
    if !predicate(value) {
    return false
    }
    }
    return true
    }