Кодовый гольф:Братья

StackOverflow https://stackoverflow.com/questions/1621480

  •  06-07-2019
  •  | 
  •  

Вопрос

Я только что закончил участвовать в латиноамериканском финале ACM ICPC Programming Conest 2009.Эти вопросы были адресованы Бразилии, Боливии, Чили и т.д.

Моя команда и я смогли ответить только на два вопроса из одиннадцати (думаю, неплохо для первой попытки).

Вот один, который мы могли бы закончить.Мне любопытно увидеть какие-либо изменения в коде.Вопрос в полном объеме: ps:Эти вопросы также можно найти на официальном веб-сайте ICPC, доступном для всех.

В стране АКМ правил великий король, который стал одержим порядком.Королевство имело прямоугольную форму, и король разделил территорию на сетку небольших прямоугольных графств.Перед смертью король распределил графства между своими сыновьями.

Король не подозревал о соперничестве между своими сыновьями:Первый наследник ненавидел второго, но не остальных, второй ненавидел третьего, но не остальных и так далее...Наконец, последний наследник ненавидел первого наследника, но не других наследников.

Как только король умер, странное соперничество между сыновьями короля вызвало всеобщую войну в королевстве.Атаки имели место только между парами соседних округов (соседние округа - это те, которые разделяют одну вертикальную или горизонтальную границу).Округ X атаковал соседний округ Y всякий раз , когда X ненавидел Y.Подвергшийся нападению округ всегда был завоеван.Все атаки, где проводились одновременно, и набор одновременных атак назывался битва.После определенного количества сражений оставшиеся в живых сыновья заключили перемирие и больше никогда не сражались.

Например, если у короля было три сына, названных 0, 1 и 2, на рисунке ниже показано , что происходит в первой битве за данное начальное распределение земель:

alt text

ВХОДНЫЕ ДАННЫЕ

Входные данные содержат несколько тестовых примеров.Первая строка тестового примера содержит четыре целых числа, 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
Это было полезно?

Решение

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 где вся борьба происходит внутри скоб.

Другие советы

Python (420 символов)

Я давно не играл с головоломками code golf, поэтому уверен, что пропустил несколько вещей:

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

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

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() - боевая функция;он клонирует массив массивов и вычисляет следующий макет.Для каждого квадрата посмотрите, находится ли вверх / вниз / влево / вправо парень, который вас ненавидит (враг "е"), если да, то он берет над вами верх.

Основной цикл while просто считывает входные данные, запускает k итераций battle и печатает выходные данные в соответствии со спецификацией.

Входные данные:

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

Python 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

Приведенный выше код основан на приведенной ниже версии (надеюсь, читаемой).Возможно, самое существенное различие с ответ sth заключается в том, что этот код использует 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

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++]}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top