代码高尔夫：兄弟

Question

我刚刚参加完 2009 年 ACM ICPC 编程大赛拉丁美洲决赛。这些问题是针对巴西、玻利维亚、智利等国的。

我和我的团队只能完成十一个问题中的两个（我认为第一次尝试还不错）。

这是我们可以完成的一个。我很好奇看到代码的任何变化。问题全文：ps：这些问题也可以在每个人都可以访问的 ICPC 官方网站上找到。

---

在 ACM 的土地上统治着一位痴迷于秩序的伟大国王。王国呈矩形，国王将领土划分为由矩形小县组成的网格。国王临终前将郡县分给了他的儿子们。

国王不知道儿子之间的竞争：第一个继承人讨厌第二个继承人，但不讨厌其他继承人，第二个继承人讨厌第三个继承人，但不讨厌其他继承人，依此类推……最后，最后一个继承人讨厌第一个继承人，但不讨厌第一个继承人。其他继承人。

国王一死，国王的儿子们之间奇怪的竞争就在王国里引发了一场全面的战争。攻击仅发生在相邻县之间（相邻县是指共享一个垂直或水平边界的县）。每当 X 讨厌 Y 时，X 县就会攻击邻近的 Y 县。被攻击的县总是被征服。所有攻击同时进行，一组同时攻击被称为战斗。经过一定次数的战斗后，幸存的儿子们休战，再也没有战斗过。

例如，如果国王有三个儿子，分别名为 0、1 和 2，下图显示了给定初始土地分配情况下第一次战斗中发生的情况：

---

INPUT

输入包含多个测试用例。测试用例的第一行包含四个整数，N、R、C 和 K。

1. N - 继承人的数量（2 <= N <= 100）
2. R 和 C - 土地的面积。 (2 <= R,C <= 100)
3. K - 将要发生的战斗数量。 (1 <= K <= 100)

继承人由从零开始的连续整数标识。接下来的 R 行中的每一行都包含由单个空格分隔的 C 整数 HeirIdentificationNumber（表示哪个继承人拥有这块土地）。这是布局初始土地。

最后一个测试用例是由四个零分隔的行，每个零之间用单个空格分隔。 （可以这么说，退出程序）

---

输出

对于每个测试用例，您的程序必须打印 R 行，每行包含 C 整数，并以与输入相同的格式用单个空格分隔，代表土地分布战斗。

---

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

另一个例子：

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

Answer 1

Perl，233 字符

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

该映射保存在一维数组中。这不如二维解决方案优雅，但也更短。包含成语 @A=map{...}@A，其中所有战斗都在大括号内进行。

Answer 2

F#，675 个字符

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

使数组足够大，以便在外部放置一个额外的“-2”边框 - 这样可以向左/上/右/下查看，而不必担心越界异常。

B()为战斗函数；它克隆数组的数组并计算下一个布局。对于每个方块，看看上/下/左/右是否是讨厌你的人（敌人“e”），如果是，他就会接管你。

主 while 循环仅读取输入，运行 k 次战斗迭代，并按照规范打印输出。

输入：

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

输出：

2220
2101
2220
0200
103
212

Answer 3

Python（420 个字符）

我已经有一段时间没有玩过代码高尔夫谜题了，所以我确信我错过了一些东西：

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 4

Lua，291 个字符

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 5

Python 2.6，383 376 个字符

此代码的灵感来自于 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 个字符

最小化：

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

上面的代码基于以下（希望可读）版本。也许与某物的答案最显着的区别是此代码使用Data.Array.IArray 而不是嵌套列表。

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

有点晚了，但尽管如此......一维数组中的数据。使用二维数组，解决方案大约长 30 个字符。

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