Numeración de crucigramas

9

Produzca un programa para numerar correctamente una cuadrícula de crucigramas.

Entrada

La entrada será el nombre de un archivo que representa la cuadrícula de crucigramas. El nombre de archivo de entrada se puede pasar como argumento, en la entrada estándar o por otros medios convencionales que no sean la codificación fija.

Formato de archivo de cuadrícula: un archivo de texto. La primera línea consta de dos constantes enteras separadas por espacios en blanco My N. Siguiendo esa línea hay M líneas cada una compuesta de Ncaracteres (más una nueva línea) seleccionados entre [#A-Z ]. Estos caracteres se interpretan de tal manera que '#' indican un cuadrado bloqueado, ' 'un cuadrado abierto en el rompecabezas sin contenido conocido y cualquier letra un cuadrado abierto que contenga esa letra.

Salida

La salida será un archivo de numeración, y puede enviarse a la salida estándar, a un archivo cuyo nombre se deriva del nombre de archivo de entrada, a un archivo especificado por el usuario oa algún otro destino convencional.

Formato de archivo de numeración Un archivo de texto. Las líneas que comienzan con '#' se ignoran y pueden usarse para comentarios. Todas las demás líneas contienen una pestaña separada triplete i, m, ndonde irepresenta un número que va a imprimirse en la parrilla, y my nrepresentan la fila y columna de la plaza donde debe ser impreso. El número de filas y columnas comienza en 1.

Esquema de numeración

Una cuadrícula numerada correctamente tiene las siguientes propiedades:

  1. La numeración comienza en 1.
  2. Ninguna columna o tramo de cuadrados abiertos está sin numerar. (Puede suponer que no existirá una respuesta de carácter único en el problema).
  3. Los números se encontrarán en orden de conteo escaneando de la fila superior a la inferior tomando cada fila de izquierda a derecha. (Entonces, cada tramo horizontal está numerado en su cuadrado más a la izquierda, y cada columna está numerada en su cuadrado más alto).

Prueba de entrada y salida esperada

Entrada:

5   5
#  ##
#    
  #  
    #
##  #

Salida (descuidando las líneas de comentarios):

1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

Aparte

Este es el primero de los que esperamos sean varios desafíos relacionados con crucigramas. Planeo usar un conjunto consistente de formatos de archivo en todo momento y construir un conjunto respetable de utilidades relacionadas con crucigramas en el proceso. Por ejemplo, un rompecabezas posterior requerirá imprimir una versión ASCII del crucigrama basado en la entrada y salida de este rompecabezas.

dmckee --- gatito ex moderador
fuente
Los tramos de un solo carácter no están numerados, ¿verdad?
Keith Randall
@Kieth: Prefiero la regla donde no hay tales tramos, pero no la he especificado aquí porque validar la cuadrícula está planificada como otro problema. Supongo que lo que usas es cuestión de gustos.
dmckee --- ex-gatito moderador
¿el archivo de entrada estará en txt?
www0z0k
@ www0z0k: Sí. El geek de Unix en mí siempre se predetermina al texto.
dmckee --- ex-gatito moderador
1
@ www0z0k: los saltos de línea son lo que sea nativo en su plataforma. Eso es ASCII decimal 20 en el mío y representado como '\n'en c en todas las plataformas. Se supone que el archivo de entrada se produjo en el mismo sistema que lo procesará, por lo que este problema debería ser transparente. Una nota general sobre code-golf: si está trabajando en un idioma extraño o en una plataforma extraña, simplemente tome nota de cualquier cosa que pueda sorprender al lector. La gente tendrá en cuenta eso al juzgar su presentación.
dmckee --- ex-gatito moderador

Respuestas:

4

Ruby - 210 139 caracteres

o=0
(n=(/#/=~d=$<.read.gsub("
",S='#'))+1).upto(d.size-1){|i|d[i]!=S&&(i<n*2||d[i-1]==S||d[i-n]==S)&&print("%d\t%d\t%d
"%[o+=1,i/n,i%n+1])}

Probado con rubí 1.9.

Arnaud Le Blanc
fuente
Yo sigo la mayor parte de eso. No estoy seguro de lo que hace s.shift.split.map, pero eso debe estar formando la matriz a partir de la entrada.
dmckee --- ex-gatito moderador
Por cierto, ¿cómo debo invocarlo en una línea de comandos de Unix? Intenté darle un shebang apropiado para mi sistema, pero se queja ./temp.ruby:4: wrong argument type Symbol (expected Proc) (TypeError).
dmckee --- ex gatito moderador
s.shift toma la primera línea, la división devuelve ["m", "n"], el mapa devuelve [m, n]. Estoy corriendo con ruby1.9 como esto: ruby1.9 test.rb.
Arnaud Le Blanc
3

PHP - 175 caracteres

<?for($i=$n=strpos($d=strtr(`cat $argv[1]`,"\n",$_="#"),$_)+$o=1;isset($d[$i]);++$i)$d[$i]!=$_&($i<$n*2|$d[$i-1]==$_|$d[$i-$n]==$_)&&printf("%d\t%d\t%d\n",$o++,$i/$n,$i%$n+1);
Arnaud Le Blanc
fuente
Me preguntaba cuándo alguien lo haría en una matriz 1d.
dmckee --- ex-gatito moderador
3

Pitón, 194 177 176 172 caracteres

f=open(raw_input())
V,H=map(int,next(f).split())
p=W=H+2
h='#'
t=W*h+h
n=1
for c in h.join(f):
 t=t[1:]+c;p+=1
 if'# 'in(t[-2:],t[::W]):print"%d\t%d\t%d"%(n,p/W,p%W);n+=1
Keith Randall
fuente
h.join(f)Creo que deberías poder usarlo
gnibbler
y en next(f)lugar de f.readline()si eres> = 2.6 másf.next()
gnibbler
Mi python nunca fue muy buena, pero parece que estás usando '#' adicionales para manejar los casos extremos, ¿no? Sin embargo, obtengo resultados extraños en los datos de prueba, incluidos los números adicionales.
dmckee --- ex-gatito moderador
@dmckee, sí, estoy usando #s adicionales para marcar el borde. ¿Puedes publicar un caso de prueba donde creas que falla?
Keith Randall
@Kieth: Para el caso de prueba anterior, obtengo 12 líneas de salida (y las primeras 10 no coinciden). Usando python2.6 o 2.7 en mi Mac. Ejecutarlo con echo test_input_file_name | python golf.py, ¿está mal?
dmckee --- ex-gatito moderador
2

C ++ 270 264 260 256 253 char

#include<string>
#include<iostream>
#define X cin.getline(&l[1],C+2)
using namespace std;int main(){int r=0,c,R,C,a=0;cin>>R>>C;string l(C+2,35),o(l);X;for(;++r<=R;o=l)for(X,c=0;++c<=C;)if(l[c]!=35&&(l[c-1]==35||o[c]==35))printf("%d %d %d\n",++a,r,c);}

Usar:

g++ cross.cpp -o cross
cat puzzle |  cross

Bien formateado:

#include<string>
#include<iostream>
// using this #define saved 1 char
#define X cin.getline(&l[1],C+2)

using namespace std;

int main()
{
    int r=0,c,R,C,a=0;
    cin>>R>>C;
    string l(C+2,35),o(l);
    X;

    for(;++r<=R;o=l)
        for(X,c=0;++c<=C;)
            if(l[c]!=35&&(l[c-1]==35||o[c]==35))
                printf("%d %d %d\n",++a,r,c);
}

Intenté leer todo el crucigrama de una vez y usando un solo bucle.
Pero el costo de compensar el carácter '\ n superó cualquier ganancia:

#include <iostream>
#include <string>
#define M cin.getline(&l[C+1],R*C
using namespace std;

int main()
{
    int R,C,a=0,x=0;
    cin>>R>>C;
    string l(++R*++C,35);
    M);M,0);

    for(;++x<R*C;)
        if ((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))
            printf("%d %d %d\n",++a,x/C,x%C);
}

Comprimido: 260 caracteres

#include<iostream>
#include<string>
#define M cin.getline(&l[C+1],R*C
using namespace std;int main(){int R,C,a=0,x=0;cin>>R>>C;string l(++R*++C,35);M);M,0);for(;++x<R*C;)if((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))printf("%d %d %d\n",++a,x/C,x%C);}
Martin York
fuente
Me llevó algunos intentos invocarlo correctamente. Resbaloso.
dmckee --- ex-gatito moderador
2

C, 184 189 caracteres

char*f,g[999],*r=g;i,j,n;main(w){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(r,99,f);++j)
for(i=0;i++<w;++r)
*r==35||j&&i>1&&r[-w]-35&&r[-1]-35||printf("%d\t%d\t%d\n",++n,j+1,i);}

No hay mucho que decir aquí; La lógica es bastante básica. El programa toma el nombre del archivo en la entrada estándar en tiempo de ejecución. (Es tan molesto que el programa tiene que trabajar con un nombre de archivo, y no puede simplemente leer el contenido del archivo directamente de la entrada estándar. ¡Pero el que paga el flautista llama la melodía!)

El fscanf()patrón extraño es mi intento de escanear la primera línea completa, incluida la nueva línea pero sin incluir los espacios en blanco iniciales en la siguiente línea. Hay una razón por la que nadie usa scanf().

caja de pan
fuente
Creo que invierte el número de filas y columnas. Si entiendo correctamente, el primer número es el número de filas, pero lo trata como el número de columnas.
Ugoren
Por lo que puedo decir, la salida de mi programa coincide con el ejemplo dado en la descripción y la salida de la implementación de referencia. ¿Me puede dar un ejemplo específico de a qué se refiere?
breadbox
Cualquier ejemplo donde los números de filas y columnas no son iguales.
Ugoren
Está bien, pero seamos específicos por favor. Cuando se proporciona la cuadrícula de ejemplo proporcionada en la descripción, mi programa genera (1,2) para el número 1. ¿Está diciendo que mi programa debería generar (2,1)?
breadbox
Estoy hablando de entrada, no de salida. Cuando la primera línea es 5 5, tomas los primeros 5 como el ancho, cuando deberías haber tomado la segunda (lo cual no importa, por supuesto, en este ejemplo).
Ugoren
1

Implementación de referencia:

c99 sin golf y más de 2000 caracteres, incluidas varias ranuras de depuración todavía allí.

#include <stdio.h>
#include <string.h>

void printgrid(int m, int n, char grid[m][n]){
  fprintf(stderr,"===\n");
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
      switch (grid[i][j]) {
      case '\t': fputc('t',stderr); break;
      case '\0': fputc('0',stderr); break;
      case '\n': fputc('n',stderr); break;
      default: fputc(grid[i][j],stderr); break;
      }
    }
    fputc('\n',stderr);
  }
  fprintf(stderr,"===\n");
}

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the output
         filename */
    if (!(outf = fopen(argv[2],"w"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Number a crossword grid.\n\t%s <grid file> [<output file>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

/*    printgrid(m,n,grid); */
  readgrid(inf,m,n,grid);
/*    printgrid(m,n,grid);  */

  /* loop through the grid  produce numbering output */
  fprintf(outf,"# Numbering for '%s'\n",infname);
  int num=1;
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
/*       fprintf(stderr,"\t\t\t (%d,%d): '%c' ['%c','%c']\n",i,j, */
/*        grid[i][j],grid[i-1][j],grid[i][j-1]); */
      if ( grid[i][j] != '#' &&
       ( (i == 0) || (j == 0) ||
         (grid[i-1][j] == '#') ||
         (grid[i][j-1] == '#') )
         ){
    fprintf(outf,"%d\t%d\t%d\n",num++,i+1,j+1);
      }
    }
  }
  fclose(outf);
  return 0;
}
dmckee --- gatito ex moderador
fuente
1

PerlTeX : 1143 caracteres (pero aún no lo he jugado)

\documentclass{article}

\usepackage{perltex}
\usepackage{tikz}

\perlnewcommand{\readfile}[1]{
  open my $fh, '<', shift;
  ($rm,$cm) = split /\s+/, scalar <$fh>;
  @m = map { chomp; [ map { /\s/ ? 1 : 0 } split // ] } <$fh>;
  return "";
}

\perldo{
  $n=1;
  sub num {
    my ($r,$c) = @_;
    if ($r == 0) {
      return $n++;
    }
    if ($c == 0) {
      return $n++;
    }
    unless ($m[$r][$c-1] and $m[$r-1][$c]) {
      return $n++;
    }
    return;
  }
}

\perlnewcommand{\makegrid}[0]{
  my $scale = 1;
  my $return;
  my ($x,$y) = (0,$r*$scale);
  my ($ri,$ci) = (0,0);
  for my $r (@m) {
    for my $open (@$r) {
      my $f = $open ? '' : '[fill]';
      my $xx = $x + $scale;
      my $yy = $y + $scale;
      $return .= "\\draw $f ($x,$y) rectangle ($xx,$yy);\n";

      my $num = $open ? num($ri,$ci) : 0;
      if ( $num ) {
        $return .= "\\node [below right] at ($x, $yy) {$num};";
      }

      $x += $scale;
      $ci++;
    }
    $ci = 0;
    $x = 0;
    $ri++;
    $y -= $scale;
  }
  return $return;
}

\begin{document}
\readfile{grid.txt}

\begin{tikzpicture}
  \makegrid
\end{tikzpicture}

\end{document}

Necesita un archivo llamado grid.txtcon la especificación, luego compilar con

perltex --nosafe --latex=pdflatex grid.tex
Joel Berger
fuente
1

Scala 252:

object c extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val b=(0 to z(0)).map{r=>readLine}
var c=0
(0 to z(0)).map{y=>(0 to z(1)).map{x=>if(b(y)(x)==' '&&((x==0||b(y)(x-1)==35)||(y==0||b(y-1)(x)==35))){c+=1
println(c+"\t"+(y+1)+"\t"+(x+1))}}
}}

compilación e invocación:

scalac cg-318-crossword.scala && cat cg-318-crossword | scala c
usuario desconocido
fuente
0

SHELL SCRIPT

#!/bin/sh
crossWordFile=$1

totLines=`head -1 $crossWordFile | cut -d" " -f1`
totChars=`head -1 $crossWordFile | awk -F' ' '{printf $2}'`

NEXT_NUM=1
for ((ROW=2; ROW<=(${totLines}+1); ROW++))
do
   LINE=`sed -n ${ROW}p $crossWordFile`
   for ((COUNT=0; COUNT<${totChars}; COUNT++))
   do
      lineNumber=`expr $ROW - 1`
      columnNumber=`expr $COUNT + 1`
      TOKEN=${LINE:$COUNT:1}
      if [ "${TOKEN}" != "#" ]; then
      if [ ${lineNumber} -eq 1 ] || [ ${columnNumber} -eq 1 ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
      elif [ "${TOKEN}" != "#" ] ; then
          upGrid=`sed -n ${lineNumber}p $crossWordFile | cut -c"${columnNumber}"`
          leftGrid=`sed -n ${ROW}p $crossWordFile | cut -c${COUNT}`
          if [ "${leftGrid}" = "#" ] || [ "${upGrid}" = "#" ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
          fi
      fi
      fi
   done
done

muestra de E / S:

./numberCrossWord.sh crosswordGrid.txt

1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3
Aman ZeeK Verma
fuente
Es posible que no haya entendido completamente los requisitos, ya que solo traté de entender de las E / S proporcionadas, perdone si la solución es solo una solución para un caso particular dado :)
Aman ZeeK Verma
Mi /bin/shqueja sobre la línea 11. ¿Podría decir qué shell está utilizando (incluido el número de versión)?
dmckee --- ex-gatito moderador
La línea 8 parece ser similar a la línea 11 ... ¿no? $ bash --version GNU bash, versión 3.1.17 (1) -release (x86_64-suse-linux)
Aman ZeeK Verma
intente modificar #! bin / sh a # /! / bin / bash, ¡debería funcionar ahora!
Aman ZeeK Verma
0

ANSI C 694 caracteres

Esta es una versión en C que busca recorridos horizontales o verticales de dos espacios que están unidos contra el borde o contra un carácter '#'.

El archivo de entrada se toma de stdin y debe ser:

<rows count> <cols count><newline>
<cols characters><newline> x rows
...

Cualquier consejo para compactar esto será recibido con gratitud.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define H '#'

char *p,*g;
int m=0,d=0,r=0,c=0,R=0,C=0;
void n() {
    while(!isdigit(d=getchar()));
    m=d-'0';
    while(isdigit(d=getchar()))
        m=m*10+d-'0';
}

int t() {
    return (((c<1||*(p-1)==H)&&c<C-1&&*p!=H&&p[1]!=H)||
            ((r<1||*(p-C-1)==H)&&r<R-1&&*p!=H&&p[C+1]!=H));
}

int main (int argc, const char * argv[]) 
{
    n();R=m;m=0;n();C=m;
    p=g=malloc(R*C+R+1);
    while((d=getchar())!=EOF) {
        *p++=d;
    }
    int *a,*b;
    b=a=malloc(sizeof(int)*R*C+R+1);
    p=g;m=0;
    while(*p) {
        if(t()) {
            *a++=++m;
            *a++=r+1;
            *a++=c+1;
        }
        if(++c/C) r++,p++;
        c-=c/C*c;
        p++;
    }
    while(*b) {
        printf("%d\t%d\t%d\n",*b,b[1],b[2]);
        b+=3;
    }
}

Salida para el ejemplo proporcionado

1   1   2
2   1   3
3   2   2
4   2   4
5   2   5
6   3   1
7   3   4
8   4   1
9   4   3
10  5   3
Jonathan Watmough
fuente
Este código maneja correctamente # _ # espacios vacíos verticales y horizontales de un solo espacio, que aunque pueden no ocurrir como un solo espacio no conectado, parecen estar permitidos, por ejemplo, como la última letra de, por ejemplo, una palabra horizontal.
Jonathan Watmough