python ohno.py

• Una misma ficha azul puede ver a las otras azules contiguas en su misma fila y columna, excluyendo ella misma
• Las fichas rojas rompen la contigüidad entre las azules
• Haz click en las fichas para cambiar sus colores. Las fichas "clavadas" del principio no se pueden cambiar
• Los numeros (A/B) describen cuantas fichas azules debe ver cada ficha azul (B) y cuantas ve relamente (A).
• Como mínimo, cualquier ficha azul debe ver otra ficha azul

        blues,reds,r =  set(),set(), Random()
        # An eye: there is no warrant to have unique solution for OhNO
        # ever one in case!
        # This is random... Hard to justify loop's termination (statistics)
        while (len(blues)<(pow(self.N,2) / 4)):
            blues.add((r.choice(range(self.N)),r.choice(range(self.N))))
       while (len(reds)<(pow(self.N,2) / 8)):
            reds.add((r.choice(range(self.N)),r.choice(range(self.N))))
            reds.difference_update(blues)
        #
        #blues=[(0,1), (0,2), (1,1)]  <===============   Commented
        #reds =[(0,0)]    <===============   Commented
 
 

• Una misma ficha azul puede ver a las otras azules contiguas en su misma fila y columna, excluyendo ella misma
• Las fichas rojas rompen la contigüidad entre las azules
• Haz click en las fichas para cambiar sus colores. Las fichas "clavadas" del principio no se pueden cambiar
• Los numeros (A/B) describen cuantas fichas azules debe ver cada ficha azul (B) y cuantas ve relamente (A).
• Como mínimo, cualquier ficha azul debe ver otra ficha azul

• Podemos emular una especie de semáforo distribuido con colas. Las operaciones P(s) y V(s) son las correspondeintes a rcv(q) y snd(q). Eso si, expresado en C, es un poco críptico, ya que tenemos que ver siempre el retorno de la llamada al sistema
• Al ser utilizado como señalización, el mensaje no precisa de datos. no se precisa comunicar ningún dato, el mismo acto de envío y recepción es suficiente. De ahí que el msg.txt sea de tamñao 0, no es necesario poner "LUZ VERDE" o "LUZ ROJA"...

/* 
  Syncrhonized red-green semaphores
 
  using queues
 
  a queue can act as a distributed semaphore
*/
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/msg.h>
 
#include <sys/stat.h>
#include <fcntl.h>
 
 
 
#include <stdlib.h>  // exit
#include <stdio.h>  // print
#include <unistd.h> // sleep
 
int msq1;
int msq2; // queue descriptors...
 
 
typedef struct msgbuf {
  long mtype;       /* message type, must be > 0 */
  char mtext[0];    /* message data */
} msg;
 
 
void one_process()
{
  struct msgbuf msg = {  1 };
  for( ; 1 ; )
    {
      if (msgrcv(msq1,(void *)&msg,sizeof(msg.mtext),0,0)==-1)
	{
	  perror("msgrcv");
	  exit(EXIT_FAILURE);
	}
      printf("one: \t\tRED\n");
      sleep(2);
      if (msgsnd(msq2,(void *)&msg,sizeof(msg.mtext),0))
	{
	  perror("msgsnd");
	  exit(1);
	}
      printf("one: \t\tGREEN\n");
    }
}
 
 
void two_process()
{
  struct msgbuf msg = { 1 };
  for( ; 1 ; )
    {
      if (msgrcv(msq2,(void *)&msg,sizeof(msg.mtext),0,0)==-1)
	{
	  perror("msgrcv");
	  exit(EXIT_FAILURE);
	}      printf("\t\t\t\ttwo: \t\tRED\n");
      sleep(2);
      if (msgsnd(msq1,(void *)&msg,sizeof(msg.mtext),0))
	{
	  perror("msgsnd");
	  exit(1);
	}
      printf("\t\t\t\ttwo: \t\tGREEN\n");
    }
}
 
 
int main(int argc, char **args)
{
  int pid;
  int msgkey =IPC_PRIVATE;
  struct msgbuf msg = { 1 };
 
  if ((msq1 = msgget(msgkey, IPC_CREAT | 0666 ))==-1)
    {
      perror("msgget");
      exit(EXIT_FAILURE);
    }
 
  if ((msq2 = msgget(msgkey, IPC_CREAT | 0666 ))==-1)
    {
      perror("msgget");
      exit(EXIT_FAILURE);
    }
 
  if (msgsnd(msq1,(void *)&msg,sizeof(msg.mtext),0))
    {
      perror("msgsnd");
      exit(1);
    }  
  pid = fork();
  switch (pid)
    {
    case 0 : // child
      one_process();
      break;
    default: // parent
      two_process();
    }
 
}
 

 gcc redgreen.que.c -o main && ./main
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED

/* 
  Syncrhonized red-green semaphores
 
  using semaphores...
 
  Safety Invariant:
     0 <= one_sem + two_sem <= 1
 
*/
 
#include <pthread.h>
#include <semaphore.h>
 
 
#include <stdlib.h>  // exit
#include <stdio.h>  // print
#include <unistd.h> // sleep
sem_t one_sem;
sem_t two_sem;
 
 
void* one_thread(void *arg)
{
  for( ; 1 ; )
    {
      if (sem_wait(&one_sem))
	{
	  perror("sem_wait");
	  exit(1);
	}
      printf("one: \t\tRED\n");
      sleep(2);
      if (sem_post(&two_sem))
	{
	  perror("sem_post");
	  exit(1);
	}
      printf("one: \t\tGREEN\n");
    }
}
 
 
void* two_thread(void *arg)
{
  for( ; 1 ; )
    {
      if (sem_wait(&two_sem))
	{
	  perror("sem_wait");
	  exit(1);
	}
      printf("\t\t\t\ttwo: \t\tRED\n");
      sleep(2);
      if (sem_post(&one_sem))
	{
	  perror("sem_post");
	  exit(1);
	}
      printf("\t\t\t\ttwo: \t\tGREEN\n");
    }
}
 
 
int main(int argc, char **args)
{
  pthread_t one,two;
 
  sem_init(&one_sem,0,1);
  sem_init(&two_sem,0,0);
  if (pthread_create(&one, NULL, one_thread, NULL))
    {
      perror("pthread_create");
      exit(1);
    }
  if (pthread_create(&two, NULL, two_thread, NULL))
    {
      perror("pthread_create");
      exit(1);
    }
 
  if (!pthread_join(one,NULL))
    {
      perror("pthread_join");
      exit(1);
    }
 
    if (!pthread_join(two,NULL))
    {
      perror("pthread_join");
      exit(1);
    }
 
}
 

gcc redgreen.c -lpthread -o main && ./main
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED
one: 		GREEN
				two: 		RED
				two: 		GREEN
one: 		RED

• Productores consumidores se ejecutan indefinidamente. De otro modo, puedes llegar a bloqueos, (imagina 1 productor y 1000 consumidores, a 1 items cada uno... Es obvio que los consumidores se quedarán esperando indefinidamente
• El buffer, o es un escalar, o un buffer limitado. Nada se gana con los stacks... Interesa FIFO, no LIFO
• Nada se gana leyendo los manuales de la libreria <thread> o <condition variable> si no se conoce en que consisten los monitores

#include <cassert>
#include <iostream>
#include <vector> // as bounded buffer.
#include <thread>
#include <mutex>
#include <condition_variable>
#include <chrono>
#include <atomic>
#include <cassert>
 
#define MAX_THREADS 1000 
#define SIZE_BUFFER 5
#define TIMEOUT  200
 
using namespace std;
 
// Patemeters overwritten on input.
static int P = 5; // Producers
static int C = 10; // Consumers
static int P_DELAY=1000 ; // Prod-Delay
static int C_DELAY=500; 
 
 
// MONITOR VARIABLES
static mutex xmutex;                    // Our mutex, monitor methods in exclusion
static condition_variable if_full;             // to indicate that our stack is
					// not full  between the thread operations 
static condition_variable if_empty;            // to indicate that our stack is
					// not empty between the thread operations
 
static int front = 0;
static int rear = 0;
static vector<int>  buf(SIZE_BUFFER);
static int holes = SIZE_BUFFER;
static int items = 0;
// Monitor invariants:
// inv. items =  (front "-" rear) 
// inv. holes = SIZE_BUFFER - (front "-" rear)
// inv. 0 <= front < SIZE_BUFFER, 0 <= rear < SIZE_BUFFER
 
static atomic<int> m(0); // simulating a fresh message;
 
// MONITOR METHODS
void init()
{
  front=rear=items=0;
  holes = SIZE_BUFFER;
}
 
void deposit(const int id,const int msg)
{
	unique_lock<mutex> lock(xmutex);
 
	// await holes > 0
	if_full.wait(lock, [] { return holes > 0; }); 
	buf[rear] = msg; rear = ((rear+1) % SIZE_BUFFER);
	cout << "p[" << id << "]\tdeposit\t:\t" << msg << endl;
	holes--; items++;
	if_empty.notify_all();
}
 
//      Consume function, consumer_id will consume a product
int fetch(const int id)
{
	unique_lock<mutex> lock(xmutex);
	int mess;
	// await items > 0
	if_empty.wait(lock, [] { return items > 0; });
	mess = buf[front]; front = ((front+1) % SIZE_BUFFER);
	cout << "c[" << id << "]\t\t\t\t\tfetch\t:\t" << mess << endl;
	holes++;items--;
	if_full.notify_all();
	return mess;
}
 
 
// Real code for threads.
void producer(int id)
{
	for (; 1; )
	{
		deposit(id, ++m);
		this_thread::sleep_for(chrono::milliseconds(P_DELAY));
	}
	return;
}
 
void consumer(int id)
{
	int msg;
	for (; 1; )
	{
		msg = fetch(id);
		this_thread::sleep_for(chrono::milliseconds(C_DELAY));
	}
	return ;
}
 
 
void simulation()
{
	vector<thread> threads;
 
	init();
	// Create producers
	for (int p = 0; p < P; ++p)
	  threads.push_back(thread(producer, p));
 
	// Create consumers
	for (int c = 0; c < C; ++c)
	  threads.push_back(thread(consumer, c));
 
	// Wait for consumers and producers to finish
	for (auto& t : threads)
		t.join();
}
 
 
// IO staff.
int main(int argc, char *args[])
{
  cout << "C P P_DELAY C_DELAY " << endl;
  for( ; cin >> C >> P >> P_DELAY >> C_DELAY; )
    {
      assert((C<MAX_THREADS) && (P<MAX_THREADS) );
      assert((P_DELAY > 0) && (C_DELAY > 0) );
      simulation();
    }
  return 0;
}
 
 

g++ conc.cpp -o main -lpthread && ./main
C P P_DELAY C_DELAY 
5 5 500 500
p[1]	deposit	:	1
p[2]	deposit	:	2
p[0]	deposit	:	3
p[3]	deposit	:	4
c[0]					fetch	:	1
p[4]	deposit	:	5
c[1]					fetch	:	2
c[3]					fetch	:	3
c[2]					fetch	:	4
c[4]					fetch	:	5
p[1]	deposit	:	6
p[3]	deposit	:	7
p[0]	deposit	:	9
p[2]	deposit	:	8
c[0]					fetch	:	6
p[4]	deposit	:	10
c[1]					fetch	:	7
c[3]					fetch	:	9
c[2]					fetch	:	8
c[4]					fetch	:	10
p[1]	deposit	:	11
p[3]	deposit	:	12
p[0]	deposit	:	13
p[2]	deposit	:	14
c[0]					fetch	:	11
p[4]	deposit	:	15
c[1]					fetch	:	12
c[3]					fetch	:	13
c[2]					fetch	:	14
c[4]					fetch	:	15
p[1]	deposit	:	16
p[0]	deposit	:	18
p[3]	deposit	:	17
p[2]	deposit	:	19
c[0]					fetch	:	16
p[4]	deposit	:	20
c[1]					fetch	:	18
c[3]					fetch	:	17
c[2]					fetch	:	19
c[4]					fetch	:	20
p[0]	deposit	:	21
p[1]	deposit	:	22
p[3]	deposit	:	23
p[2]	deposit	:	24
p[4]	deposit	:	25
c[0]					fetch	:	21
c[1]					fetch	:	22
c[3]					fetch	:	23
c[2]					fetch	:	24
c[4]					fetch	:	25
p[0]	deposit	:	26
c[0]					fetch	:	26
p[3]	deposit	:	29
c[4]					fetch	:	29
p[4]	deposit	:	30
c[2]					fetch	:	30
p[1]	deposit	:	27
c[1]					fetch	:	27
p[2]	deposit	:	28
c[3]					fetch	:	28
p[0]	deposit	:	31
p[3]	deposit	:	32
c[4]					fetch	:	31
c[0]					fetch	:	32
p[4]	deposit	:	33
c[2]					fetch	:	33
p[1]	deposit	:	34
c[1]					fetch	:	34
p[2]	deposit	:	35
c[3]					fetch	:	35
p[4]	deposit	:	37
c[0]					fetch	:	37
p[3]	deposit	:	38
c[2]					fetch	:	38
p[2]	deposit	:	40
p[0]	deposit	:	36
p[1]	deposit	:	39
c[4]					fetch	:	40
c[1]					fetch	:	36
c[3]					fetch	:	39
p[4]	deposit	:	41
c[0]					fetch	:	41
p[3]	deposit	:	42
c[2]					fetch	:	42
p[2]	deposit	:	43
p[0]	deposit	:	44
p[1]	deposit	:	45
c[4]					fetch	:	43
c[1]					fetch	:	44
c[3]					fetch	:	45
...
C-c C-c

#include <stdio.h>

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h> // strlen
 
 
#define LINES_PER_FILE 1000
#define LINES_PER_PARAGRAPH 100
#define PARAGRAPH 100
#define LENGTH_LINE 250
 
/*
  Formal spec hard. Use line (not char) as main abstraction
 
  P : text[0..txtLns) of char[LENGTH_LINE];
  Q : \forall i,j : 0 <= i <= j <= N and paragraph(V,i,j,N) :
           let 
             M = emptyLines(V,0,i) 
           in
             isCopy(Pgrphs,M,i,j) and PgrphLns[M]=(j-i)
      txtPgrphs = min(1,N) + emptyLines(text,0,txtLns) 
 
  where 
 
     emptyLines(text,0,txtLns) = #i : 0 <=i <txtLns :empty(text[i])
     paragraph(V,i,j,N) = 
                  i = max k : 0 <= k <=j and (k > 0 -> empty(text[k-1]) : k
                  j = min k : i <= k <= N and (k < N -> empty(text[k]) : k
     isCopy(Pgrphs,M,n,m) = \forall i : 0 <= i < m-n : Pgrphs[M][i]=text[n+i]
 
*/
void  text2paragraphs(const char text[][LENGTH_LINE],
		      const int txtLns,
                      char pgrphs[PARAGRAPH][LINES_PER_PARAGRAPH][LENGTH_LINE],
		      int *txtPgrphs,
		      int pgrphLns[])
{
  int n;
  for(*txtPgrphs=(txtLns>0), n=pgrphLns[0]=0;  n<txtLns;n++)  
    if (strlen(text[n])>1)
      strncpy(pgrphs[*txtPgrphs-1][pgrphLns[(*txtPgrphs-1)]++],text[n],LENGTH_LINE);
    else
      (*txtPgrphs)++;
  return;
}
 
int main(int argc, char *args[])
{
  char text[LINES_PER_FILE][LENGTH_LINE];
  int txtLns,txtPgrphs;
  char paragraphs[PARAGRAPH][LINES_PER_PARAGRAPH][LENGTH_LINE];
  int pgrphLns[PARAGRAPH];
 
  char *line=NULL;
  ssize_t read;
  size_t len;
 
  // Input
  txtLns = 0 ;
  while ((read=getline(&line,&len,stdin))!=-1)
      strncpy(text[txtLns++],line,LENGTH_LINE);
  free(line);
 
  // Process
  text2paragraphs(text,txtLns,paragraphs,&txtPgrphs,pgrphLns);
 
  // Output
  printf("%d\n",txtPgrphs);
  for (int i=0; i< txtPgrphs ; i++)
    {
      printf("(%d,%d)\n",i,pgrphLns[i]);
      for (int j=0; j< pgrphLns[i] ; j++)
	printf("%d.%d\t%s",i,j,paragraphs[i][j]);
    }
}
 

bash-2.04$ cat poema.txt
A Dafne ya los brazos le crecian 
y en luengos ramos vueltos se mostraban; 
en verdes hojas vi que se tornaban 
los cabellos qu'el oro escurecian; 

de aspera corteza se cubrian 
los tiernos miembros que aun bullendo 'staban; 
los blancos pies en tierra se hincaban 
y en torcidas raices se volvian. 

Aquel que fue la causa de tal danio, 
a fuerza de llorar, crecer hacia 
este arbol, que con lagrimas regaba. 

Oh miserable estado, oh mal tamanio, 
que con llorarla crezca cada dia 
la causa y la razon por que lloraba!

bash-2.04$ ./main < poema.txt
4
(1,4)
1.1	A Dafne ya los brazos le crecian 
1.2	y en luengos ramos vueltos se mostraban; 
1.3	en verdes hojas vi que se tornaban 
1.4	los cabellos qu'el oro escurecian; 
(2,4)
2.1	de aspera corteza se cubrian 
2.2	los tiernos miembros que aun bullendo 'staban; 
2.3	los blancos pies en tierra se hincaban 
2.4	y en torcidas raices se volvian. 
(3,3)
3.1	Aquel que fue la causa de tal danio, 
3.2	a fuerza de llorar, crecer hacia 
3.3	este arbol, que con lagrimas regaba. 
(4,3)
4.1	Oh miserable estado, oh mal tamanio, 
4.2	que con llorarla crezca cada dia 
4.3	la causa y la razon por que lloraba!