CodeGolf: Fratelli

Question

Ho appena finito di partecipare al Conest di programmazione ACPC ICPC del 2009 nelle finali latinoamericane. Queste domande erano per Brasile, Bolivia, Cile, ecc.

Io e il mio team abbiamo potuto concludere solo due domande su undici (non male, penso per il primo tentativo).

Eccone uno che potremmo finire. Sono curioso di vedere eventuali variazioni al codice. La domanda per intero: ps: queste domande possono anche essere trovate sul sito web ufficiale ICPC alla portata di tutti.

---

Nella terra di ACM regnò un re verde che divenne ossessionato dall'ordine. Il regno aveva una forma rettangolare e il re divise il territorio in una griglia di piccole contee rettangolari. Prima di morire il re distribuiva le contee tra i suoi figli.

Il re non era a conoscenza delle rivalità tra i suoi figli: il primo erede odiava il secondo ma non il resto, il secondo odiava il terzo ma non il resto, e così via ... Infine, l'ultimo erede odiava il primo erede , ma non gli altri eredi.

Non appena il re morì, la strana rivalità tra i figli del re scatenò una guerra generalizzata nel regno. Gli attacchi hanno avuto luogo solo tra coppie di contee adiacenti (le contee adiacenti sono quelle che condividono un bordo verticale o orizzontale). Una contea X attaccava una contea adiacente Y ogni volta che X odiava Y. La contea attaccata veniva sempre conquistata. Tutti gli attacchi venivano eseguiti simultaneamente e una serie di attacchi simultanei veniva chiamata battaglia . Dopo un certo numero di battaglie, i figli sopravvissuti fecero una tregua e non combatterono mai più.

Ad esempio se il re avesse tre figli, chiamati 0, 1 e 2 , la figura sotto mostra cosa succede nella prima battaglia per una data distribuzione iniziale della terra:

---

INPUT

L'ingresso contiene diversi casi di test. La prima riga di un caso di test contiene quattro numeri interi, N, R, C e K .

1. N - Il numero di eredi (2 < = N < = 100)
2. R e C - Le dimensioni del terreno. (2 & Lt; = R, C & Lt; = 100)
3. K - Numero di battaglie che si svolgeranno. (1 & Lt; = K & Lt; = 100)

Gli eredi sono identificati da numeri interi sequenziali a partire da zero. Ciascuna delle successive linee R contiene C interi HeirIdentificationNumber (che dice ciò che l'erede possiede questa terra) separati da spazi singoli. Questo per strutturare la terra iniziale.

L'ultimo test case è una linea separata da quattro zero separati da spazi singoli. (Per uscire dal programma per così dire)

---

Output

Per ogni caso di test il tuo programma deve stampare R righe con numeri interi C ciascuno, separati da spazi singoli nello stesso formato dell'input, che rappresenta la distribuzione del terreno dopo tutte le battaglie.

---

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

Un altro esempio:

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

Answer 1

Perl, 233 caratteri

{$_=<>;($~,$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}}

La mappa è contenuta in un array monodimensionale. È meno elegante della soluzione bidimensionale, ma è anche più corta. Contiene il linguaggio @A=map{...}@A dove tutti i combattimenti continuano all'interno delle parentesi graffe.

Answer 2

Python (420 caratteri)

Non gioco ai puzzle di golf da un po 'di tempo, quindi sono sicuro di aver perso alcune cose:

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 personaggi

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 caratteri

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

Rendi l'array abbastanza grande da mettere un bordo extra di " -2 " all'esterno: in questo modo può apparire a sinistra / su / destra / giù senza preoccuparsi delle eccezioni fuori limite.

B () è la funzione di battaglia; clona l'array-of-array e calcola il layout successivo. Per ogni quadrato, vedi se su / giù / sinistra / destra è il ragazzo che ti odia (nemico 'e'), in tal caso, ti prende in consegna.

Il ciclo while principale legge solo l'input, esegue k iterazioni di battaglia e stampa l'output secondo le specifiche.

Input:

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

Output:

2220
2101
2220
0200
103
212

Answer 5

Python 2.6, 383 376 personaggi

Questo codice è ispirato alla la risposta di 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 personaggi

minimizzato:

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

Il codice sopra si basa sulla versione (si spera leggibile) di seguito. Forse la differenza più significativa con la risposta di sth è che questo codice utilizza Data.Array.IArray invece degli elenchi nidificati.

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 po 'in ritardo, ma comunque ... Dati in un array 1-D. Utilizzando un array 2-D, la soluzione è più lunga di circa 30 caratteri.

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++]}