Mensajes

[Loretz]

Estupendo intento, Loretz, buena exhibición de recursos... No obstante creo que el punto flaco reside en la llamada que haces a lower_bound, lo que eleva la complejidad de tu algoritmo a O(Nlog(N)). Mejor que cuadrático O(N^2), al menos...

...
   for (auto i = v.begin(), j = v.end();
       i != j && it != j;
       ++i)
   {
       auto s = *i + k;
       it = std::lower_bound(it, j, s);

       if (it != j && *it == s) {
           ++n;
           ++it;
       }
   }
...

A ver que te parece   ésta, en O(N): Brevemente, para evitar llamadas a lower_bound, controlas con una variable extra m, que parte del vector recorrido YA sabes que no va a emparejar con el actual en curso V[n], por lo que no hace falta volver a recorrer...
Ah!, y lo mismo vale para vectores vacíos

Código (cpp) [Seleccionar] Expandir



/*        
P : strict(V)
fun k_paired(V[0..N) of int, int k) dev r
Q : r =#i,j : 0 <= i , j<N : V[j]-V[i]=k

I : Q[N/n] and 0 <= m <= n <= N and
    n<N -> \forall i : 0<=i < m : V[n]-V[i] > k   **

    ** m for efficiency reasons, discarding
       subtrahends V[i] far from V[n].
   

!B : n==N     B: n<N

 C(N,n,m)= 2N - (m+n) >= 0



Invariant snapshot:
-------------------

k = 20  , r = 0
0                 m                             n           N
+-----+-----+-----+-----+-...-+-----+-----+-----+-----+-...-+
|  1  |  3  |  5  |  40 |     |     | 49  | 50  | 60  |     |
+-----+-----+-----+-----+-...-+-----+-----+-----+-----+-...-+


*/



#include <iostream>

using namespace std;
int k_paired(const int V[], const int N, const int k)
{
 int n,m,r;
 for(n=m=r=0;n<N;)
   if (V[n]-V[m] <= k)
     r+=(V[n++]-V[m] == k);
   else m++;
 return r;

}

#define MAX 100000

int main(int argc, char **args)
{
 int N,k;
 int V[MAX];
 for(cin >> N ; N!=-1 ; cin>>N)
   {
     cin >> k;
     for(int n=0;n<N;n++)
cin >> V[n];
     cout << k_paired(V,N,k) << endl;
   }
 return 0;
}


A ver si pudieras medir tiempos con tus clases C++...

 

YreX-DwX, bravo!  Yo mismo no podría haberlo explicado mejor...

Ahora... alguien se anima a hacerlo en O(N)?
En O(N^2) no tiene mucho mérito...

Dado un vector de enteros V[0..N) , con todos sus componentes siguiendo un orden stricto creciente, (1,5,17,20) y un numero k >=0 , diseñar un algoritmo de complejidad lineal que resuelva el número de pares de componentes <i,j> , con 0<=i,j<N, tales que Vi-Vj=k.

En la siguientee lineas se da unos ejemplos como ilustracion

Código [Seleccionar] Expandir


5 3   (Numero de componentes del vector y k)
1 4 5 6 8  (Componentes del vector)
2  (Resultado)

4 2 (Numero de componentes del vector y k)
1 4 5 6 (Componentes del vector)
1  (Resultado)


3 0 (Numero de componentes del vector y k)
1 2 3 (Componentes del vector)
3 Resultado)



Yo dispongo de la solución. La pongo en dos días. Pero ahí esta el reto. Cuanto más simple mejor!

[cron]

Buenos días!
Estoy implementando un programa que se dedica a leer los datos de un fichero que se encuentra en una determinada carpeta. La cosa es que cada mes, se genera un nuevo fichero al que acceder, lo que me obliga a cambiar el código para acceder al ultimo fichero que se ha generado.

Mi pregunta es; existe alguna forma de que mi programa sea capaz de estar a la espera de encontrar un nuevo fichero dentro de la misma ruta con idea de que automáticamente, los datos que necesito sacar de dichos ficheros se actualicen sin necesidad de que cada mes tenga que cambiar el código.

Muchas gracias de antemano! Un saludo

A lo mejor no estás planteando el problema con la tecnología adecuada. Me explico: por qué programar un complejo programa C con llamadas complejas a API cuando todo esto se puede hacer con los comandos de la shell, ya que la pregunta original se refiere a Linux


A ver que te parece este pequeño scrpipt.

Código [Seleccionar] Expandir


#!/bin/sh
TARGET_DIR=$HOME  # Change to your choice, i.e. "/tmp/log"
LAST_MODIFIED=$(stat -c "%Y %n" $TARGET_DIR/* | sort | cut -d ' ' -f 2 | tail -1)
echo $LAST_MODIFIED


Esto detecta el ultimo fichero modificado en un directorio. Si lo quieres hacer periódicamente cada mes, lo mejor es integrarlo el servicio cron .  No puedo desbribir aquí como va, (dale a man cron)

Finalmente, llega tu programa original, el que tiene que procesar el fichero detectado. En lugar de hacer echo, invocas tu programa pasando el fichero por parámetro, sin cambiarlo.

Código [Seleccionar] Expandir


#!/bin/sh
TARGET_DIR=$HOME  # Change to your choice, i.e. "/tmp/log"
LAST_MODIFIED=$(stat -c "%Y %n" $TARGET_DIR/* | sort | cut -d ' ' -f 2 | tail -1)
myprogram $LAST_MODIFIED


Si puede valer....

Tendré que diseñar un algoritmo de inteligencia artificial de expliración de estados (vamos, un backtraking de to la vida, que es cualquier cosa menos inteligente, es pura fuerza bruta) y exponer una combinación que tenga solución.

No lo veo necesario. Ni siquiera un backtracking...

Hola! Tus comentarios fueron muy útiles...! En otro correo cuando pueda respondo cómo me ayudó.
Como tu dices, no era necesario.

Vayan aquí unas fotos del juego que YA es practicable.  https://github.com/rafaelm53539600/OhnO

Os lo descargáis con el botón verde, que dice "Download zip".
Después sólo que usar python 3, (no vale con python 2), y se invoca así.

Código [Seleccionar] Expandir

python ohno.py










Recuerdo las reglas:

• 
  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

Gracias NEBIRE, no veas lo que aprecio tu respuesta!
Veo que has comrpendido  a la perfección todo el sistema.

Me autorespondo...
Después de mirar el código, veo que la cuenta es de vecinas (contiguas) en la misma fila y columna, excluyéndose a sí misma de dicha cuenta. La aparición de una pieza roja, rompe la contigüidad.

Es así, y veo que tu redacción es mejor que la mía. Con tu permiso, lo cambiaré en el mensaje original.

Y el objetivo final es descubrir el color original de cada ficha en el mapa.

Bueno, esto no es exacto. El objetivo final es cumplir las restricciones de las fichas azules iniciales, llenado todo el tablero al 100% y esto no es siempre una solución única (más abajo te explico)

Personalmente creo que en la cuenta debiera contarse a sí misma y reflejarse así en el juego, es más fácil contar todas que saltarse una...

Yo también pensaba así, pero las reglas no dicen eso. Por eso puse la ayuda del par de números (A/B), (las que veo, las que debo ver). Esta claro que los maestros orientales del Japón valoraban la paciencia del conteo como forma de "concentración"    (Vamos, eso creo yo...)

...

He hecho una simple aproximación (en pseudocódigo). Pero me doy cuenta que al hacerlo de forma sencilla, para elegir las piezas de dar pistas, al azar, puede dar lugar a múltiples soluciones válidas (de momento he optado por dejar como piezas fijas, tantas como un valor al azar entre 1/4 y 1/3 del total de las piezas del tablero), originado precisamente a causa de aquellas piezas que no son 'tocadas' por ninguna de las fijas que ofrecen las pistas... pero bueno es una primera aproximación... ya lo miraré más en profundidad cuando pase a la implementación.

Mirando tu ejemplo 'solved', se alcanza a ver esto mismo que acabo de decir, por ejemplo la última fila... al no tener pistas, no se ve forzado, luego da igual si se ponen rojas o azules... Más aún las dos ultimas filas, salvo las dos rojas, no importa de qué color sea el resto, ofrece pués múltiples soluciones válidas.

TOTALMENTE de acuerdo, tienes razón.

En definitiva, lo que trato de decir es que el juego sería más interesante (y también más difícil) si no tuviera múltiples soluciones, o al menos restringirlo lo más posible.

Pero el juego no descarta que haya multiples soluciones... Naturalmente, si restringes como dices las fichas, no es que es sea más difícil, al contrario, es más fácil, porque las posiciones se pueden "deducir" ("forzar", en tus propios términos) y no especular.

El problema entonces, es que, jugando con las restricciones de las fichas azules, su posición y la aritmética, puedes llegar a restringirlo tanto QUE NO TENGA solución.

Fijate en el siguiente ejemplo, surgido con fichas al azar, cambiando el código en la línea 180.

Código (python) [Seleccionar] Expandir

       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



Ahora el problema es irresoluble! La casilla 1,2 requiere ver tres fichas. Una por arriba, (hecho) , pero por abajo no puede (LOCK) y por la izquierda tampoco (poruqe  a lo podr'a llegar a ver una!)

Y es ahí donde  quiero llegar... No puedo poner unos valores de entrada para que el esforzado humano, después de jugar 4 horas, se de cuenta de que no tiene solución.

Tendré que diseñar un algoritmo de inteligencia artificial de expliración de estados (vamos, un backtraking de to la vida, que es cualquier cosa menos inteligente, es pura fuerza bruta) y exponer una combinación que tenga solución.

Se me está ocurriendo luego poner un boton de "Me rindo!!!" en el que pulsando salga UNA  de las posibles soluciones....


Un abrazo!

Hola!
OhnO es un juego clásico de fichas sobre un tablero de origen japonés.  Sus reglas son:
EDITED: Credits NEBIRE

• 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

Es posible que haya miles de versiones por Internet.
Ofrezco la mía. Alguna valoración?
https://github.com/rafaelm53539600/OhnO

(Son 250 lineas, por eso no lo expongo en el Web)

 
Bravo!
Auténtica exhibición!

Lo prometido es deuda. Aqui tienes una implementación de sincronización con colas System V.

Comentarios

• 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"...

Código (c) [Seleccionar] Expandir

/*
  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();
    }

}


Código [Seleccionar] Expandir

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

Hola!
Estaba haciendo un ejercicio en el cual hay que sincronizar varios procesos y que estos procesos sigan sincronizandose (en este caso los procesos son unos semaforos que tienen que ir cambiando de color de forma logica osea cuando uno este en verde el otro no puede estar en verde y viceversa) hasta que se pulse ctrl-c.
El caso es que  mi idea era realizar esta sincronizacion con un buzon IPC [...]

Muchas gracias!

A ver, la forma "natural" de hacerlo es con semáforos, no con lo que tu llamas "buzones"... (Creo que con lo que te refieres a eso es a colas, pero bueno...) En cuanto pueda, hago una solución de ese modo

Aquí  hay una propuesta de simulación. Creo que deberías empezar por threads, en vez de , como creo, haces con IPC y fork(), al estar incompleto el código, no puedo interpretar....

Código (c) [Seleccionar] Expandir

/*
 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);
   }

}



Y la salida, (el efecto temporal no sale en esta página estática Web, claro. Deberias ver que se sincronizan al mismo tiempo. Correlo en tu terminal.)

Código [Seleccionar] Expandir

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