This is the exercise in Spanish:

  Ejercicio 18

  Una isla es una agrupación de celdas (al menos una) con valor 1, cada una
  de las cuales es adyacente horizontal y/o verticalmente a una celda del
  mismo grupo.  Una isla está delimitada, horizontal y verticalmente, por
  celdas con valor 0 o por los límites (fronteras) del mapa.  Por ejemplo, en
  el mapa que se presenta en la Figura 3, de tamaño 5x10, hay 6 islas las
  cuales están compuestas de las siguientes celdas:

  * Isla 1: (1,1) (1,2) (1,3) (2,1) (2,2)
  * Isla 2: (3,4)
  * Isla 3: (4,5)
  * Isla 4: (5,1) (5,2) (5,3)
  * Isla 5: (1,6) (1,7) (1,8) (1,9) (1,10) (2,10) (2,7) (3,7) (4,7) (5,7) (5,8)
  * Isla 6: (5,10)

  Notar que (3,4) y (4,5) no forman una isla, sino que son dos islas distintas.

  (a) Escriba el pseudocódigo de un programa que, dado un mapa representado por
      una matriz de tamaño NxM de ceros y unos, donde 0 representa agua y 1
      tierra, imprima las islas encontradas en el mismo.
  (b) Implemente el programa de la parte anterior en C*.

  Nota: Se pide que el programa imprima las celdas de cada isla del mapa
  siguiendo el formato del ejemplo. El orden de impresión entre las islas no es
  relevante, ni tampoco el orden en que se imprimen las celdas de cada isla.

And here we provide a reference implementation:

echo $'1110011111\n1100001001\n0001001000\n0000101000\n1110001101' | \
  sed 'H;$!d;x;s/\n/%-x/g;s/.//;s/$/%/
    :a;s/\(xx*\)\([01]\)\([01]\+%\)/\1\2\1x\3/;ta
    :b;s/-\([x%y]\)/\1-/g;s/-\([01]\)/y\1-/;tb
    s/[-%]//g;s/[xy]*0//g;s/1//g;s/x*y*/|<&>/g
    :c;h;s/\(<x*y*\)>\(.*|.*\)\1y>/\1>\1y>\2/g
         s/\(<x*y*\)y>\(.*|.*\)\1>/\1y>\1>\2/g
         s/<\(x*y*>\)\(.*|.*\)<x\1/<\1<x\1\2/g
         s/<x\(x*y*>\)\(.*|.*\)<\1/<x\1<\1\2/g
         x;G;/^\(.*\)\n\1$/!{g;bc};x
    s/||*/-|:/g;:d;s/-|/|x-/g;s/-\([^|-]\)/\1-/g;td
    s/<\(x*\)/<\1,/g;s/y/x/g
    :e;s/\([<,|]\)x/\10x/g;s/0x/1/g;s/1x/2/g;s/2x/3/g;s/3x/4/g;s/4x/5/g
       s/5x/6/g;s/6x/7/g;s/7x/8/g;s/8x/9/g;s/9x/x0/g;te
    s/<\([^>]*\)>/ (\1)/g;s/-//g;s/|/\nIsla /g;s/.//'
Isla 1: (1,1) (2,1) (3,1) (2,2) (1,2)
Isla 2: (6,1) (7,1) (7,2) (7,3) (7,4) (7,5) (8,5) (8,1) (9,1) (10,1) (10,2)
Isla 3: (4,3)
Isla 4: (5,4)
Isla 5: (1,5) (2,5) (3,5)
Isla 6: (10,5)

Explanation:

first: Load all lines in memory in the format -x010101%-x11001100%...

a: Given two decimal digits, place between them the amount of x+1 that appeared
   before, eg: xx01 -> xx0xxx1

b: Now it's time to encode the 'y' coordinate in unary.  The dash is advanced
   like a cursor, adding a 'y' when crossing a number.  Since there's a single
   dash before the first line, two before the second, and so on, that'll be the
   number of 'y's before each number on each line.

next: This is where we remove [-%], the nodes with 0, the numbers and convert
   them into |<x*y*> format, ie: 101 -> |<xy>|<xxxy>.

c: This is the most interesting part of the program.  We use the '|' to separate
   each strongly connected component, with each <x*y*> node initially placed in
   a different component.

   Then we move the nodes from different blocks whose coordinate differ in only
   one x or one y into the same block.  Since all this transformation only
   moves the rightmost node to the component on the left, after a finite number
   of applications there will be no more possible moves, and we will have
   converged into the correct grouping.

   Homework 1 (easy): Prove it ends in finite time.
   Homework 2 (hard): Prove that anytime it ends it's because it's found the
                      correct (unique-except-by-order) solution.

next: Before each pipe we add a '-', using the same technique as in the 'y'
   coordinate, we end up with |x<node>...|xx<node>...|xxx<node>...

next: Time to begin the unary to decimal conversion, we separate the x* and y*
   with a comma in the middle, and convert the 'y's into 'x's to simplify.

e: The unary conversion is pretty straight forward:  We add any leading zeros
   on the |x <x ,x cases.  Then 0x is 1, 1x is 2, and so on. For the carry
   9x is converted to x0, eg: 19x -> 1x0 -> 20.  Any leading zeros are added as
   needed.

Finally there's the conversion to "Isla N: (y,x) (y,x)..." format.

This is the exercise in Spanish:

  Ejercicio 18

  Una isla es una agrupación de celdas (al menos una) con valor 1, cada una
  de las cuales es adyacente horizontal y/o verticalmente a una celda del
  mismo grupo.  Una isla está delimitada, horizontal y verticalmente, por
  celdas con valor 0 o por los límites (fronteras) del mapa.  Por ejemplo, en
  el mapa que se presenta en la Figura 3, de tamaño 5x10, hay 6 islas las
  cuales están compuestas de las siguientes celdas:

  * Isla 1: (1,1) (1,2) (1,3) (2,1) (2,2)
  * Isla 2: (3,4)
  * Isla 3: (4,5)
  * Isla 4: (5,1) (5,2) (5,3)
  * Isla 5: (1,6) (1,7) (1,8) (1,9) (1,10) (2,10) (2,7) (3,7) (4,7) (5,7) (5,8)
  * Isla 6: (5,10)

  Notar que (3,4) y (4,5) no forman una isla, sino que son dos islas distintas.

  (a) Escriba el pseudocódigo de un programa que, dado un mapa representado por
      una matriz de tamaño NxM de ceros y unos, donde 0 representa agua y 1
      tierra, imprima las islas encontradas en el mismo.
  (b) Implemente el programa de la parte anterior en C*.

  Nota: Se pide que el programa imprima las celdas de cada isla del mapa
  siguiendo el formato del ejemplo. El orden de impresión entre las islas no es
  relevante, ni tampoco el orden en que se imprimen las celdas de cada isla.

And here we provide a reference implementation:

echo $'1110011111\n1100001001\n0001001000\n0000101000\n1110001101' | \
  sed 'H;$!d;x;s/\n/%-x/g;s/.//;s/$/%/
    :a;s/\(xx*\)\([01]\)\([01]\+%\)/\1\2\1x\3/;ta
    :b;s/-\([x%y]\)/\1-/g;s/-\([01]\)/y\1-/;tb
    s/[-%]//g;s/[xy]*0//g;s/1//g;s/x*y*/|<&>/g
    :c;h;s/\(<x*y*\)>\(.*|.*\)\1y>/\1>\1y>\2/g
         s/\(<x*y*\)y>\(.*|.*\)\1>/\1y>\1>\2/g
         s/<\(x*y*>\)\(.*|.*\)<x\1/<\1<x\1\2/g
         s/<x\(x*y*>\)\(.*|.*\)<\1/<x\1<\1\2/g
         x;G;/^\(.*\)\n\1$/!{g;bc};x
    s/||*/-|:/g;:d;s/-|/|x-/g;s/-\([^|-]\)/\1-/g;td
    s/<\(x*\)/<\1,/g;s/y/x/g
    :e;s/\([<,|]\)x/\10x/g;s/0x/1/g;s/1x/2/g;s/2x/3/g;s/3x/4/g;s/4x/5/g
       s/5x/6/g;s/6x/7/g;s/7x/8/g;s/8x/9/g;s/9x/x0/g;te
    s/<\([^>]*\)>/ (\1)/g;s/-//g;s/|/\nIsla /g;s/.//'
Isla 1: (1,1) (2,1) (3,1) (2,2) (1,2)
Isla 2: (6,1) (7,1) (7,2) (7,3) (7,4) (7,5) (8,5) (8,1) (9,1) (10,1) (10,2)
Isla 3: (4,3)
Isla 4: (5,4)
Isla 5: (1,5) (2,5) (3,5)
Isla 6: (10,5)

Explanation:

first: Load all lines in memory in the format -x010101%-x11001100%...

a: Given two decimal digits, place between them the amount of x+1 that appeared
   before, eg: xx01 -> xx0xxx1

b: Now it's time to encode the 'y' coordinate in unary.  The dash is advanced
   like a cursor, adding a 'y' when crossing a number.  Since there's a single
   dash before the first line, two before the second, and so on, that'll be the
   number of 'y's before each number on each line.

next: This is where we remove [-%], the nodes with 0, the numbers and convert
   them into |<x*y*> format, ie: 101 -> |<xy>|<xxxy>.

c: This is the most interesting part of the program.  We use the '|' to separate
   each strongly connected component, with each <x*y*> node initially placed in
   a different component.

   Then we move the nodes from different blocks whose coordinate differ in only
   one x or one y into the same block.  Since all this transformation only
   moves the rightmost node to the component on the left, after a finite number
   of applications there will be no more possible moves, and we will have
   converged into the correct grouping.

   Homework 1 (easy): Prove it ends in finite time.
   Homework 2 (hard): Prove that anytime it ends it's because it's found the
                      correct (unique-except-by-order) solution.

next: Before each pipe we add a '-', using the same technique as in the 'y'
   coordinate, we end up with |x<node>...|xx<node>...|xxx<node>...

next: Time to begin the unary to decimal conversion, we separate the x* and y*
   with a comma in the middle, and convert the 'y's into 'x's to simplify.

e: The unary conversion is pretty straight forward:  We add any leading zeros
   on the |x <x ,x cases.  Then 0x is 1, 1x is 2, and so on. For the carry
   9x is converted to x0, eg: 19x -> 1x0 -> 20.  Any leading zeros are added as
   needed.

Finally there's the conversion to "Isla N: (y,x) (y,x)..." format.
[cancel] password:  [private]