CodeGolf: Frères

Question

Je viens juste de finir de participer au concours de programmation ACM ICPC 2009 aux finales latino-américaines. Ces questions concernaient le Brésil, la Bolivie, le Chili, etc.

Mon équipe et moi-même n'avons pu terminer que deux questions sur onze (pas mal, je pense, du premier coup).

En voici un que nous pourrions terminer. Je suis curieux de voir des variations du code. La question dans son intégralité: ps: Ces questions peuvent également être consultées sur le site Web officiel du CIPC accessible à tous.

Au pays d’ACM, régnait un grand roi obsédé par l’ordre. Le royaume avait une forme rectangulaire et le roi divisait le territoire en une grille de petits comtés rectangulaires. Avant de mourir, le roi a réparti les comtés parmi ses fils.

Le roi ignorait la rivalité entre ses fils: le premier héritier haïssait le deuxième mais pas les autres, le deuxième haïssait le troisième mais pas les autres, et ainsi de suite ... Enfin, le dernier héritier haïssait le premier héritier , mais pas les autres héritiers.

Dès la mort du roi, l'étrange rivaly des fils du roi déclencha une guerre généralisée dans le royaume. Les attaques ont eu lieu uniquement entre des paires de comtés adjacents (les comtés adjacents sont ceux qui partagent une frontière verticale ou horizontale). Un comté X a attaqué un comté Y adjacent chaque fois que X détestait Y. Le comté attaqué était toujours conquis. Toutes les attaques étaient menées simultanément et une série d’attaques simultanées était appelée une bataille . Après un certain nombre de batailles, les fils survivants ont fait une trêve et ne se sont plus jamais battus.

Par exemple, si le roi avait trois fils, nommés 0, 1 et 2 , la figure ci-dessous montre ce qui se passe dans la première bataille pour une répartition initiale des terres donnée:

SAISIR

L'entrée contient plusieurs scénarios de test. La première ligne d'un scénario de test contient quatre entiers, N, R, C et K .

1. N - Le nombre d'héritiers (2 < = N < = 100)
2. R et C - Les dimensions du terrain. (2 & Lt; = R, C & Lt; = 100)
3. K - Nombre de batailles qui vont avoir lieu. (1 & Lt; = K & Lt; = 100)

Les héritiers sont identifiés par des entiers séquentiels à partir de zéro. Chacune des lignes R suivantes contient des nombres C entiers HeirIdentificationNumber (en indiquant quel héritier est propriétaire de cette terre) séparés par des espaces simples. Ceci consiste à aménager le terrain initial.

Le dernier cas de test est une ligne séparée par quatre zéros séparés par des espaces simples. (Pour quitter le programme pour ainsi dire)

Sortie

Pour chaque test, votre programme doit imprimer R lignes avec C entiers, séparées par des espaces uniques dans le même format que l'entrée, représentant la répartition des terres après toutes les batailles.

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

Autre exemple:

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

Answer 1

Perl, 233 caractères

{$_=<>;($~,$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 carte est tenue dans un tableau à une dimension. C'est moins élégant que la solution à deux dimensions, mais c'est aussi plus court. Contient l'idiome @A=map{...}@A où tous les combats se déroulent à l'intérieur des accolades.

Answer 2

Python (420 caractères)

Je n'ai pas joué aux puzzles de golf de code depuis un moment, alors je suis sûr d'avoir raté quelques points:

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 caractères

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 caractères

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

Faites en sorte que le tableau soit assez grand pour mettre une bordure supplémentaire de " -2 " autour de l'extérieur - de cette façon, vous pouvez regarder à gauche / en haut / à droite / en bas sans vous soucier des exceptions en dehors des limites.

B () est la fonction de combat; il clone le tableau de tableaux et calcule la mise en page suivante. Pour chaque case, voyez si haut / bas / gauche / droite est le type qui vous déteste (ennemi 'e'), si c'est le cas, il vous emmène.

La boucle while principale lit uniquement les entrées, exécute k itérations de bataille et affiche la sortie conformément aux spécifications.

Entrée:

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

Sortie:

2220
2101
2220
0200
103
212

Answer 5

Python 2.6, 383 376 caractères

Ce code est inspiré de la réponse 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 caractères

Minimisé:

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

Le code ci-dessus est basé sur la version (dans l’espoir lisible) ci-dessous. La différence la plus significative avec réponse de sth est que ce code utilise Data.Array.IArray au lieu des listes imbriquées.

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 peu tard, mais néanmoins ... Données dans un tableau 1D. Avec un tableau 2D, la solution a environ 30 caractères de plus.

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