كود جولف:الإخوة

Question

لقد انتهيت للتو من المشاركة في مسابقة البرمجة ACM ICPC لعام 2009 في نهائيات أمريكا اللاتينية.كانت هذه الأسئلة مخصصة للبرازيل وبوليفيا وتشيلي وغيرها.

لم نتمكن أنا وفريقي من إنهاء سوى سؤالين من أصل أحد عشر سؤالاً (ليس سيئًا على ما أعتقد في المحاولة الأولى).

هنا واحد يمكننا الانتهاء منه.أشعر بالفضول لرؤية أي اختلافات في الكود.السؤال كاملا: ملاحظة:يمكن أيضًا العثور على هذه الأسئلة على الموقع الرسمي للجنة الدولية للبراءات (ICPC) المتاح للجميع.

---

في أرض ACM حكم ملك عظيم أصبح مهووسًا بالنظام.كان للمملكة شكل مستطيل، وقام الملك بتقسيم المنطقة إلى شبكة من المقاطعات الصغيرة المستطيلة.قبل وفاته قام الملك بتوزيع المقاطعات على أبنائه.

ولم يكن الملك على علم بالخصومات بين أبنائه:الوريث الأول يكره الثاني وليس الباقي، والثاني يكره الثالث وليس الباقي، وهكذا... وأخيرًا، الوريث الأخير يكره الوريث الأول، وليس الورثة الآخرين.

بمجرد وفاة الملك، أدى التنافس الغريب بين أبناء الملك إلى إشعال حرب شاملة في المملكة.وقعت الهجمات فقط بين أزواج من المقاطعات المتجاورة (المقاطعات المتجاورة هي تلك التي تشترك في حدود رأسية أو أفقية واحدة).هاجمت مقاطعة X مقاطعة مجاورة Y عندما كرهت X Y.تم دائمًا احتلال المقاطعة المهاجمة.تم تنفيذ جميع الهجمات بشكل متزامن وتم استدعاء مجموعة من الهجمات المتزامنة معركة.بعد عدد معين من المعارك، عقد الأبناء الباقون على قيد الحياة هدنة ولم يتقاتلوا مرة أخرى أبدًا.

على سبيل المثال، إذا كان للملك ثلاثة أبناء، اسمه 0 و 1 و 2, يوضح الشكل أدناه ما يحدث في المعركة الأولى لتوزيع مبدئي معين للأراضي:

---

مدخل

يحتوي الإدخال على عدة حالات اختبار.يحتوي السطر الأول من حالة الاختبار على أربعة أعداد صحيحة، ن، ر، ج، ك.

1. ن - عدد الورثة (2 <= ن <= 100)
2. R و C - أبعاد الأرض.(2 <= ر، ج <= 100)
3. ك – عدد المعارك التي ستدور .(1 <= ك <= 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

بيرل، 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

بايثون (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 3

لوا، 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 4

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 الرئيسية تقرأ فقط المدخلات، وتدير عدة تكرارات للمعركة، وتطبع المخرجات وفقًا للمواصفات.

مدخل:

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 5

بايثون 2.6, 383 376 حرفا

هذا الكود مستوحى من إجابة ستيف لوش:

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())

---

هاسكل (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

أوك - 245

متأخرا بعض الشيء، ولكن على الرغم من ذلك...البيانات في مجموعة 1-D.باستخدام مصفوفة ثنائية الأبعاد، يصبح الحل أطول بحوالي 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++]}