Илия обнови решението на 31.12.2014 21:00 (преди над 3 години)
+package main
+
+import (
+ "container/list"
+ "crypto/rand"
+ "errors"
+ "fmt"
+ "regexp"
+ "strings"
+ "sync"
+ "time"
+ // "log"
+)
+
+const (
+ DOES_NOT_EXIST = iota
+ ENQUEUED
+ IN_PROGRESS
+ UNABLE_TO_PRODUCE
+ DONE
+)
+const (
+ DEV = true
+)
+
+func debug(things ...interface{}) {
+ if DEV {
+ // fmt.Print(log.Lshortfile)
+ // fmt.Print(": ")
+ for _, e := range things {
+ fmt.Print(e)
+ fmt.Print(" ")
+ }
+ fmt.Println()
+ }
+}
+
+//============================================================================
+// ORDER
+//============================================================================
+
+// Поръчката съдържа множество от думи. При създаване на нова поръчка за нея се генерира уникален идентификационен номер. За да твърдим, че е изпълнена успешно е нужно да получим като резултат регулярен израз, който match-ва всяка една от думите в множеството. Всеки произведен регулярен израз трябва да започва с ^ и да завършва с $. Разполагате с неограничено количество и от двата символа и няма нужда да ги пазите в склад. Статусът на поръчката трябва да се държи актуален, което означава, че фабриката трябва да се грижи да го променя когато е необходимо.
+type Order struct {
+ Id string
+ Status int // Състояние, което се обновява от фабриката
+ Words []string // Думи, за които трябва да бъде произведен регулярен израз
+ Result string // Произведеният регулярен израз
+ Channel chan *Order // Канал, по който да бъде върната поръчката, когато бъде приключена
+}
+
+// Създава нова поръчка с подадените думи и канал. Тази функция трябва да генерира уникално Id.
+func NewOrder(words []string, channel chan *Order) *Order {
+ bytes := make([]byte, 16)
+ rand.Read(bytes)
+ id := fmt.Sprintf("%S-%X", time.Now().String(), bytes)
+
+ return &Order{Id: id, Words: words, Channel: channel}
+}
+
+//============================================================================
+// ORDER QUEUE
+//============================================================================
+
+type OrderQueue struct {
+ queue *list.List
+}
+
+func NewOrderQueue() *OrderQueue {
+ return &OrderQueue{list.New()}
+}
+
+func (oq *OrderQueue) Push(order *Order) {
+ oq.queue.PushBack(order)
+}
+
+func (oq *OrderQueue) Shift() *Order {
+ return oq.queue.Remove(oq.queue.Front()).(*Order)
+}
+
+func (oq *OrderQueue) Len() int {
+ return oq.queue.Len()
+}
+
+//============================================================================
+// INFINITE ORDER CHANNEL
+//============================================================================
+
+type InfiniteOrderChan struct {
+ // orders []*Order
+ orders *OrderQueue
+ in chan *Order
+ out chan *Order
+}
+
+func NewInfiniteOrderChan() (ioc *InfiniteOrderChan) {
+ ioc = &InfiniteOrderChan{NewOrderQueue(), make(chan *Order, 10), make(chan *Order, 10)}
+ go func() {
+ for {
+ if ioc.orders.Len() == 0 {
+ order := <-ioc.in
+ ioc.orders.Push(order)
+ // ioc.orders = []*Order{order}
+ } else {
+ select {
+ case order := <-ioc.in:
+ // ioc.orders = append(ioc.orders, order)
+ ioc.orders.Push(order)
+ case ioc.out <- ioc.orders.Shift():
+ // case ioc.out <- ioc.orders[0]:
+ // ioc.orders = ioc.orders[1:] // Memory leak - can be fixed with containers/list
+ }
+ }
+ }
+ }()
+ return
+}
+
+func (ioc *InfiniteOrderChan) In() chan<- *Order {
+ return ioc.in
+}
+
+func (ioc *InfiniteOrderChan) Out() <-chan *Order {
+ return ioc.out
+}
+
+//============================================================================
+// WORKER
+//============================================================================
+
+// I think this struct should exist, but because the tests make us implement
+// lots of methods in factory it's easier to without it
+
+//============================================================================
+// FACTORY
+//============================================================================
+
+// Фабриката ще приема поръчки от клиентите, ще ги изпълнява и ще връща резултат щом приключи. При създаването се задава колко работници има, това е еквивалентно на броя поръчки, които могат да бъдат изпълнявани във всеки момент, тъй като един работник може да изпълнява само една поръчка в даден момент. Поръчка може да бъде изпълнена, ако фабриката разполага с необходимите материали, в противен случай се съобщава на клиента, че не може да бъде изпълнена. След изпълнението трябва материалите използвани за поръчката да бъдат изкарани от склада. Операциите за добавяне и премахване на материали трябва да бъдат "thread-safe".
+type Factory struct {
+ workerCount uint8
+ orders *InfiniteOrderChan
+ storage map[string]uint16
+ isProducing bool
+ vacation chan struct{}
+ *sync.Mutex
+}
+
+// Създава фабрика с подадения брой работници и започва да изпълнява поръчки.
+func NewFactory(workerCount uint8) (f *Factory) {
+ f = &Factory{
+ workerCount,
+ NewInfiniteOrderChan(),
+ map[string]uint16{},
+ false,
+ make(chan struct{}),
+ new(sync.Mutex),
+ }
+ return
+}
+
+func groupMaterials(words []string) map[string]uint16 {
+ result := make(map[string]uint16)
+ for _, w := range words {
+ result[w]++
+ }
+ return result
+}
+
+func toRegexString(materials []string) string {
+ return "^" + strings.Join(materials, "") + "$"
+}
+
+// Добавя поръчката в списъка на чакащите да бъдат изпълнени.
+func (f *Factory) Enqueue(order *Order) {
+ order.Status = ENQUEUED
+ f.orders.In() <- order
+ return
+}
+
+// Започва да изпълнява поръчки.
+func (f *Factory) StartProducing() {
+ f.isProducing = true
+ f.vacation = make(chan struct{})
+ for i := uint8(0); i < f.workerCount; i++ {
+ go func() {
+ for {
+ if f.isProducing { // maybe use chan bool instead?
+ select {
+ case order := <-f.orders.Out():
+ order.Status = IN_PROGRESS
+ materials, ok := f.generateRegexpMaterials(order.Words)
+ for ok {
+ if f.storageRemove(groupMaterials(materials)) {
+ order.Status = DONE
+ order.Result = toRegexString(materials)
+ break
+ } else {
+ materials, ok = f.generateRegexpMaterials(order.Words)
+ }
+ }
+ if order.Status != DONE {
+ order.Status = UNABLE_TO_PRODUCE
+ }
+ order.Channel <- order
+ case <-f.vacation:
+ return
+ default:
+ }
+ }
+ }
+ }()
+ }
+ return
+}
+
+// Прекратява производството като изпълнява само поръчките със статус IN_PROGRESS.
+func (f *Factory) StopProducing() {
+ f.isProducing = false
+ close(f.vacation)
+ return
+}
+
+// Приема map с материал: количество и добавя съответните материали и техните количества в склада.
+func (f *Factory) StorageAdd(materials map[string]uint16) {
+ f.Lock()
+ defer f.Unlock()
+
+ for k, v := range materials {
+ f.storage[k] += v
+ }
+ return
+}
+
+func (f *Factory) storageRemove(materials map[string]uint16) (ok bool) {
+ f.Lock()
+ defer f.Unlock()
+
+ for k, v := range materials {
+ if f.storage[k] < v {
+ return false
+ }
+ }
+ for k, v := range materials {
+ f.storage[k] -= v
+ }
+ return true
+}
+
+// Генерира регулярен израз (или връща грешка при недостатъчно материали), който match-ва всички думи в слайса words. Върнатият регулярен израз трябва да започва с ^ и да завършва с $.
+func (f *Factory) generateRegexp(words []string) (string, error) {
+ if res, ok := f.generateRegexpMaterials(words); ok {
+ return toRegexString(res), nil
+ }
+ return "", errors.New("Unable to create regex")
+}
+
+func (f *Factory) generateRegexpMaterials(words []string) ([]string, bool) {
+ materialsCount := 0
+ for _, v := range f.storage {
+ materialsCount += int(v)
+ }
+
+ materials := map[string]uint16{}
+ for k, v := range f.storage {
+ if v != 0 {
+ materials[k] = v
+ }
+ }
+
+ for i := 0; i < materialsCount; i++ {
+ if res, ok := generateOptions([]string{}, words, materials, i); ok {
+ return res, true
+ }
+
+ }
+ return nil, false
+}
+
+func matches(components, words []string) bool {
+ expr := "^" + strings.Join(components, "") + "$"
+ regex, err := regexp.Compile(expr)
+ if err != nil {
+ return false
+ }
+ for _, word := range words {
+ if !regex.MatchString(word) {
+ return false
+ }
+ }
+ return true
+}
+
+func generateOptions(doneSoFar, words []string, materialsLeft map[string]uint16, maxLength int) (result []string, ok bool) {
+ if len(doneSoFar) < maxLength {
+ for key, value := range materialsLeft {
+ if value > 0 {
+ materialsLeft[key]--
+ result, ok = generateOptions(append(doneSoFar, key), words, materialsLeft, maxLength-1)
+ materialsLeft[key]++
+ if ok {
+ return
+ }
+ }
+ }
+ return nil, false
+ }
+ if matches(doneSoFar, words) {
+ return doneSoFar, true
+ }
+ return nil, false
+}
+
+//============================================================================
+// CLIENT
+//============================================================================
+
+// Клиентите изпращат поръчки към фабриката и чакат да получат резултат. Те могат да проверяват какво се случва с поръчките им във всеки момент.
+
+type Client struct {
+ Name string
+ Orders map[string]*Order // Всички поръчки от този клиент, където ключът е Order.Id
+ Channel chan *Order // Канал, по който клиентът получава поръчка в момента, в който тя бъде приключена
+}
+
+// Създава нов клиент с подаденото име.
+func NewClient(name string) *Client {
+ // c := &Client{Name: name, Orders: map[string]*Order{}}
+ c := &Client{Name: name, Orders: make(map[string]*Order), Channel: make(chan *Order, 10)}
+ return c
+}
+
+// Създава нова поръчка с думи, изпраща я на подадената фабрика и връща id-то на поръчката.
+func (c *Client) Order(factory *Factory, words []string) string {
+ order := NewOrder(words, c.Channel)
+ c.Orders[order.Id] = order
+ factory.Enqueue(order)
+ return order.Id
+}
+
+// Проверява статуса на клиентска поръчка с подаденото id.
+func (c *Client) CheckStatus(id string) int {
+ if order, ok := c.Orders[id]; ok {
+ return order.Status
+ } else {
+ return DOES_NOT_EXIST
+ }
+}