CódigoGolf:hermanos

Question

Acabo de terminar de participar en el Concurso de Programación ACM ICPC 2009 en las Finales Latinoamericanas.Estas preguntas eran para Brasil, Bolivia, Chile, etc.

Mi equipo y yo solo pudimos terminar dos preguntas de las once (creo que no está mal para el primer intento).

Aquí hay uno que podríamos terminar.Tengo curiosidad por ver alguna variación del código.La pregunta completa: PD:Estas preguntas también se pueden encontrar en el sitio web oficial del ICPC disponible para todos.

---

En la tierra de ACM gobernaba un gran rey que se obsesionaba con el orden.El reino tenía forma rectangular y el rey dividió el territorio en una cuadrícula de pequeños condados rectangulares.Antes de morir el rey repartió los condados entre sus hijos.

El rey desconocía las rivalidades entre sus hijos:El primer heredero odiaba al segundo pero no a los demás, el segundo odiaba al tercero pero no a los demás, y así sucesivamente... Finalmente, el último heredero odiaba al primer heredero, pero no a los demás herederos.

Tan pronto como murió el rey, la extraña rivalidad entre los hijos del rey desató una guerra generalizada en el reino.Los ataques sólo tuvieron lugar entre pares de condados adyacentes (los condados adyacentes son aquellos que comparten una frontera vertical u horizontal).Un condado X atacó a un condado adyacente Y cada vez que X odiaba a Y.El condado atacado siempre fue conquistado.Todos los ataques se llevaron a cabo simultáneamente y un conjunto de ataques simultáneos se denominó batalla.Después de un cierto número de batallas, los hijos supervivientes hicieron una tregua y nunca volvieron a luchar.

Por ejemplo, si el rey tuviera tres hijos, llamados 0, 1 y 2, la siguiente figura muestra lo que sucede en la primera batalla por una distribución inicial de tierra determinada:

---

APORTE

La entrada contiene varios casos de prueba.La primera línea de un caso de prueba contiene cuatro números enteros, N, R, C y K.

1. N - El número de herederos (2 <= N <= 100)
2. R y C - Las dimensiones del terreno.(2 <= R, C <= 100)
3. K - Número de batallas que se van a realizar.(1 <= K <= 100)

Los herederos se identifican mediante números enteros secuenciales que comienzan desde cero.Cada una de las siguientes líneas R contiene números enteros C HeirIdentificationNumber (que indica a qué heredero pertenece esta tierra) separados por espacios simples.Esto es para diseñar el terreno inicial.

El último caso de prueba es una línea separada por cuatro ceros separados por espacios simples.(Para salir del programa por así decirlo)

---

Producción

Para cada caso de prueba, su programa debe imprimir líneas R con números C enteros cada una, separadas por espacios simples en el mismo formato que la entrada, que representen la distribución de la tierra después de todas las batallas.

---

Sample Input:                          Sample Output:
3 4 4 3                                2 2 2 0
0 1 2 0                                2 1 0 1 
1 0 2 0                                2 2 2 0
0 1 2 0                                0 2 0 0 
0 1 2 2

Otro ejemplo:

Sample Input:                          Sample Output:
4 2 3 4                                1 0 3
1 0 3                                  2 1 2
2 1 2

Answer 1

Perl, 233 char

{$_=<>;($~,$R,$C,$K)=split;if($~){@A=map{$_=<>;split}1..$R;$x=0,
@A=map{$r=0;for$d(-$C,$C,1,-1){$r|=($y=$x+$d)>=0&$y<@A&1==($_-$A[$y])%$~
if($p=(1+$x)%$C)>1||1-$d-2*$p}$x++;($_-$r)%$~}@A
while$K--;print"@a\n"while@a=splice@A,0,$C;redo}}

El mapa se mantiene en una matriz unidimensional. Esto es menos elegante que la solución bidimensional, pero también es más corto. Contiene el modismo @A=map{...}@A donde toda la lucha continúa dentro de las llaves.

Answer 2

Python (420 caracteres)

No he jugado con rompecabezas de código en un tiempo, así que estoy seguro de que me perdí algunas cosas:

import sys
H,R,C,B=map(int,raw_input().split())
M=(1,0), (0,1),(-1, 0),(0,-1)
l=[map(int,r.split())for r in sys.stdin]
n=[r[:]for r in l[:]]
def D(r,c):
 x=l[r][c]
 a=[l[r+mr][c+mc]for mr,mc in M if 0<=r+mr<R and 0<=c+mc<C]
 if x==0and H-1in a:n[r][c]=H-1
 elif x-1in a:n[r][c]=x-1
 else:n[r][c]=x
G=range
for i in G(B):
 for r in G(R):
  for c in G(C):D(r,c)
 l=[r[:] for r in n[:]]
for r in l:print' '.join(map(str,r))

Answer 3

Lua, 291 caracteres

g=loadstring("return io.read('*n')")repeat n=g()r=g()c=g()k=g()l={}c=c+1 for
i=0,k do w={}for x=1,r*c do a=l[x]and(l[x]+n-1)%n w[x]=i==0 and x%c~=0 and
g()or(l[x-1]==a or l[x+1]==a or l[x+c]==a or l[x-c]==a)and a or
l[x]io.write(i~=k and""or x%c==0 and"\n"or w[x].." ")end l=w end until n==0

Answer 4

F #, 675 caracteres

let R()=System.Console.ReadLine().Split([|' '|])|>Array.map int
let B(a:int[][]) r c g=
 let n=Array.init r (fun i->Array.copy a.[i])
 for i in 1..r-2 do for j in 1..c-2 do
  let e=a.[i].[j]-1
  let e=if -1=e then g else e
  if a.[i-1].[j]=e||a.[i+1].[j]=e||a.[i].[j-1]=e||a.[i].[j+1]=e then
   n.[i].[j]<-e
 n
let mutable n,r,c,k=0,0,0,0
while(n,r,c,k)<>(0,2,2,0)do
 let i=R()
 n<-i.[0]
 r<-i.[1]+2
 c<-i.[2]+2
 k<-i.[3]
 let mutable a=Array.init r (fun i->
 if i=0||i=r-1 then Array.create c -2 else[|yield -2;yield!R();yield -2|])
 for j in 1..k do a<-B a r c (n-1)
 for i in 1..r-2 do
  for j in 1..c-2 do
   printf "%d" a.[i].[j]
  printfn ""

Haga que la matriz sea lo suficientemente grande como para poner un borde adicional de " -2 " alrededor del exterior: de esta manera puede mirar hacia la izquierda / arriba / derecha / abajo sin preocuparse por las excepciones fuera de los límites.

B () es la función de batalla; clona la matriz de matrices y calcula el siguiente diseño. Para cada casilla, mira si arriba / abajo / izquierda / derecha es el tipo que te odia (enemigo 'e'), si es así, te toma el control.

El ciclo while principal solo lee la entrada, ejecuta k iteraciones de la batalla e imprime la salida según la especificación.

Entrada:

3 4 4 3
0 1 2 0
1 0 2 0
0 1 2 0
0 1 2 2
4 2 3 4
1 0 3
2 1 2
0 0 0 0

Salida:

2220
2101
2220
0200
103
212

Answer 5

Python 2.6, 383 376 caracteres

Este código está inspirado en Respuesta de Steve Losh :

import sys
A=range
l=lambda:map(int,raw_input().split())
def x(N,R,C,K):
 if not N:return
 m=[l()for _ in A(R)];n=[r[:]for r in m]
 def u(r,c):z=m[r][c];n[r][c]=(z-((z-1)%N in[m[r+s][c+d]for s,d in(-1,0),(1,0),(0,-1),(0,1)if 0<=r+s<R and 0<=c+d<C]))%N
 for i in A(K):[u(r,c)for r in A(R)for c in A(C)];m=[r[:]for r in n]
 for r in m:print' '.join(map(str,r))
 x(*l())
x(*l())

---

Haskell (GHC 6.8.2), 570 446 415 413 388 caracteres

Minimizado:

import Monad
import Array
import List
f=map
d=getLine>>=return.f read.words
h m k=k//(f(\(a@(i,j),e)->(a,maybe e id(find(==mod(e-1)m)$f(k!)$filter(inRange$bounds k)[(i-1,j),(i+1,j),(i,j-1),(i,j+1)])))$assocs k)
main=do[n,r,c,k]<-d;when(n>0)$do g<-mapM(const d)[1..r];mapM_(\i->putStrLn$unwords$take c$drop(i*c)$f show$elems$(iterate(h n)$listArray((1,1),(r,c))$concat g)!!k)[0..r-1];main

El código anterior se basa en la versión (ojala) legible a continuación. Quizás la diferencia más significativa con respuesta de sth es que este código usa Data.Array.IArray en lugar de listas anidadas.

import Control.Monad
import Data.Array.IArray
import Data.List

type Index = (Int, Int)
type Heir = Int
type Kingdom = Array Index Heir

-- Given the dimensions of a kingdom and a county, return its neighbors.
neighbors :: (Index, Index) -> Index -> [Index]
neighbors dim (i, j) =
  filter (inRange dim) [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]

-- Given the first non-Heir and a Kingdom, calculate the next iteration.
iter :: Heir -> Kingdom -> Kingdom
iter m k = k // (
  map (\(i, e) -> (i, maybe e id (find (== mod (e - 1) m) $
                                    map (k !) $ neighbors (bounds k) i))) $
  assocs k)

-- Read a line integers from stdin.
readLine :: IO [Int]
readLine = getLine >>= return . map read . words

-- Print the given kingdom, assuming the specified number of rows and columns.
printKingdom :: Int -> Int -> Kingdom -> IO ()
printKingdom r c k =
  mapM_ (\i -> putStrLn $ unwords $ take c $ drop (i * c) $ map show $ elems k)
        [0..r-1]

main :: IO ()
main = do
  [n, r, c, k] <- readLine     -- read number of heirs, rows, columns and iters
  when (n > 0) $ do                -- observe that 0 heirs implies [0, 0, 0, 0]
    g <- sequence $ replicate r readLine   -- read initial state of the kingdom
    printKingdom r c $                      -- print kingdom after k iterations
      (iterate (iter n) $ listArray ((1, 1), (r, c)) $ concat g) !! k
    main                                               -- handle next test case

Answer 6

AWK - 245

Un poco tarde, pero no obstante ... Datos en una matriz 1-D. Usando una matriz 2-D, la solución es aproximadamente 30 caracteres más larga.

NR<2{N=$1;R=$2;C=$3;K=$4;M=0}NR>1{for(i=0;i++<NF;)X[M++]=$i}END{for(k=0;k++<K;){
for(i=0;i<M;){Y[i++]=X[i-(i%C>0)]-(b=(N-1+X[i])%N)&&X[i+((i+1)%C>0)]-b&&X[i-C]-b
&&[i+C]-b?X[i]:b}for(i in Y)X[i]=Y[i]}for(i=0;i<M;)printf"%s%d",i%C?" ":"\n",
X[i++]}