Nagrodzony nagrodą Nobla Erwin Schrödinger, mający dość eksperymentowania z małymi zwierzętami domowymi , postanowił znaleźć najbliższy laser i zamiast tego zastrzelić go. Ponieważ ... nauka!

Opis

Będziesz mieć dwa punkty, które przechodzi przez laser i rozmiaru wiązki laserowej, i trzeba określić, gdzie wiązka laserowa musi pójść, mogła pójść, i nie mogła pójść.

Promień lasera może być poziomy, pionowy lub ukośny. W przypadku wiązki laserowej wielkości 1 wyglądają one odpowiednio tak:

       #  #
       #   #
#####  #    #
       #     #
       #      #

Ukośną wiązkę laserową można również odwrócić. Wiązki laserowe wielkości 2 wyglądają tak:

       ###  ##
#####  ###  ###
#####  ###   ###
#####  ###    ###
       ###     ##

Ogólnie, aby uzyskać wiązkę laserową o rozmiarze (n), wystarczy wziąć wiązkę laserową o rozmiarze (n-1) i dodać wiązkę laserową o rozmiarze (1) po obu stronach. Jako ostatni przykład, oto wszystkie możliwe wiązki laserowe o rozmiarze 3, pokazane na tej samej „płycie”:

###.....#####.....##
####....#####....###
#####...#####...####
.#####..#####..#####
..#####.#####.#####.
...###############..
....#############...
.....###########....
####################
####################
####################
####################
####################
.....###########....
....#############...
...###############..
..#####.#####.#####.
.#####..#####..#####
#####...#####...####
####....#####....###

Ta „plansza” zawsze będzie miała wymiary 20 x 20 (w znakach).

Wkład

Twój program otrzyma pięć liczb całkowitych jako dane wejściowe. Są to kolejno: ₁ , y ₁ , x ₂ , y ₂ oraz wielkość wiązki laserowej. Muszą być wykonane dokładnie w tej kolejności. Jeśli chcesz, możesz wziąć uporządkowane pary (x, y) jako tablicę, krotkę, listę lub inny wbudowany typ danych, który przechowuje dwie wartości.

Oba dwa punkty podane jako dane wejściowe będą znajdować się na planszy i na pewno będą się różnić (tzn. Dwa punkty nigdy nie będą takie same). Wielkość wiązki laserowej jest związana 1 ≤ size < 20. Zawsze będzie co najmniej jedna możliwa wiązka laserowa, która przechodzi przez oba punkty.

Wydajność

Twój program musi wypisać siatkę 20x20 następujących znaków:

• # jeśli każda możliwa wiązka laserowa, która przechodzi przez dwa punkty, również przechodzi przez ten punkt.
• . jeśli nie ma wiązki laserowej, która przechodzi przez dwa punkty i ten punkt.
• ? jeśli niektóre, ale nie wszystkie z możliwych wiązek laserowych przechodzą przez ten punkt.
• Xjeśli jest to jeden z dwóch oryginalnych punktów wejściowych (zastępuje to #).

Przypadki testowe

7, 7, 11, 3, 1

..............#.....
.............#......
............#.......
...........X........
..........#.........
.........#..........
........#...........
.......X............
......#.............
.....#..............
....#...............
...#................
..#.................
.#..................
#...................
....................
....................
....................
....................
....................

18, 18, 1, 1, 2

#??.................
?X??................
??#??...............
.??#??..............
..??#??.............
...??#??............
....??#??...........
.....??#??..........
......??#??.........
.......??#??........
........??#??.......
.........??#??......
..........??#??.....
...........??#??....
............??#??...
.............??#??..
..............??#??.
...............??#??
................??X?
.................??#

10, 10, 11, 10, 3

?????..????????..???
??????.????????.????
????????????????????
????????????????????
.???????????????????
..??????????????????
????????????????????
????????????????????
????????????????????
????????????????????
??????????XX????????
????????????????????
????????????????????
????????????????????
????????????????????
..??????????????????
.???????????????????
????????????????????
????????????????????
??????.????????.????

3, 3, 8, 10, 4

??????????..........
??????????..........
??????????..........
???X??????..........
???##?????..........
???###????..........
????###????.........
.????###????........
..????###????.......
..?????##?????......
..??????X??????.....
..??????????????....
..???????????????...
..????????????????..
..?????????????????.
..??????????????????
..??????????????????
..????????.?????????
..????????..????????
..????????...???????

Przypadki testowe zostały wygenerowane za pomocą następującego skryptu Ruby, umieszczonego wewnątrz fragmentu stosu w celu zaoszczędzenia przestrzeni pionowej.

/*

#!/usr/bin/ruby

$w = $h = 20

class Point
    attr_reader :x, :y
    def initialize x, y
        @x = x
        @y = y
    end
    def inspect
        "(#{@x}, #{@y})"
    end
    def == p
        @x == p.x && @y == p.y
    end
    alias eql? ==
    def hash
        @x * $h + @y
    end
    def valid?
        @x >= 0 && @y >= 0 && @x < $w && @y < $h
    end
end

module Angle
    HORIZONTAL = Point.new(1, 0)
    VERTICAL = Point.new(0, 1)
    DIAG1 = Point.new(1, 1)
    DIAG2 = Point.new(1, -1)
end

def line_points point, angle, size
    points = [point]

    while points[-1].valid?
        points.push Point.new(points[-1].x + angle.x, points[-1].y + angle.y)
    end
    points.pop
    while points[0].valid?
        points.unshift Point.new(points[0].x - angle.x, points[0].y - angle.y)
    end
    points.shift

    if size == 1
        points
    elsif size > 1
        a2 = case angle
            when Angle::HORIZONTAL then Angle::VERTICAL
            when Angle::VERTICAL then Angle::HORIZONTAL
            else Angle::VERTICAL  # HORIZONTAL also works
        end
        (size-1).times do |n|
            np1 = Point.new(point.x + a2.x*(n+1), point.y + a2.y*(n+1))
            np2 = Point.new(point.x - a2.x*(n+1), point.y - a2.y*(n+1))
            points.concat line_points np1, angle, 1 if np1.valid?
            points.concat line_points np2, angle, 1 if np2.valid?
        end
        points
    else
        throw 'something is very wrong'
    end
end

def generate_grid x1, y1, x2, y2, size
    p1 = Point.new(x1, y1)
    p2 = Point.new(x2, y2)
    lasers = []
    points = [Point.new((p1.x + p2.x) / 2, (p1.y + p2.y) / 2)]  # midpoint
    while points.length > 0
        point = points.pop
        new_lasers = Angle.constants
            .map{|angle| line_points point, Angle.const_get(angle), size }
            .select {|laser| laser.include?(p1) && laser.include?(p2) } -
            lasers
        if new_lasers.length > 0
            lasers.concat new_lasers
            points.push Point.new(point.x+1, point.y) if point.x+1 < $w
            points.push Point.new(point.x, point.y+1) if point.y+1 < $h
            points.push Point.new(point.x-1, point.y) if point.x-1 > 0
            points.push Point.new(point.x, point.y-1) if point.y-1 > 0
        end
    end
    grid = Array.new($h) { ?. * $w }
    lasers.each do |laser|
        laser.each do |point|
            grid[point.y][point.x] = ??
        end
    end
    lasers.reduce(:&).each do |point|
        grid[point.y][point.x] = ?#
    end
    grid[p1.y][p1.x] = 'X'
    grid[p2.y][p2.x] = 'X'
    grid
end

testcases = [
    [7, 7, 11, 3, 1],
    [18, 18, 1, 1, 2],
    [10, 10, 11, 10, 3],
    [3, 3, 8, 10, 4]
]

testcases.each do |test|
    puts test * ', '
    puts
    puts generate_grid(*test).map{|line| '    ' + line }
    puts
end

*/

Zasady

• Twój program musi być w stanie rozwiązać każdy z przypadków testowych w mniej niż 30 sekund (na rozsądnej maszynie). Jest to raczej kontrola rozsądku, ponieważ mój testowy program Ruby rozwiązał wszystkie przypadki testowe niemal natychmiast.

• To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie.

C, 291 280 277 265 bajtów

x,y,A,C,B,D,a,c,b,d,w,s,t;T(i){return abs(i)<2*w-1;}U(j,k){s+=T(j-k)*T(j)*T(k);t*=T(j-k)*j*k<1;}main(){for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w);y<20;y+=!x)s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);}

Można skompilować / uruchomić za pomocą:

gcc laser.c -o laser && echo "10 10 11 10 3" | ./laser

Poniżej ten sam kod z białymi spacjami i komentarzami wyjaśniającymi:

// Integers...
x,y,A,C,B,D,a,c,b,d,w,s,t;

// Is true if i is in range (of something)
T(i){return abs(i)<2*w-1;}

// Tests if lasers (horizontal, vertical, diagonal, etc) can/must exist at this point
// T(j-k) == 0 iff the laser of this direction can exist
// s += 1 iff this laser direction can pass through this point
// t *= 1 iff this laser direction must pass through this point
U(j,k){
    s+=T(j-k)*T(j)*T(k);
    t*=T(j-k)*j*k<1;
}

main(){ 
    // Read input; p0=(a,b), p1=(c,d)
    for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w); y<20; y+=!x)

        // A, B, C and D represent delta-x and delta-y for each points
        // e.g.: if we're processing (2,3), and p0=(4,5), A=4-2, B=5-3
        // s != 0 iff (x,y) can have some laser through it
        // t == 1 iff all lasers pass through (x,y)
        // (!A*!B+!C*!D) == 1 iff (x,y) is either p0 or p1  
        s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),
        putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);
}

C, 302 bajty

b[400],x,y,s,t,w,d,e,g,k;f(u,v){d=u*x+v*y;e=u*s+v*t;if(e<d)k=e,e=d,d=k;for(k=0;k<400&d+w>e;++k)g=k%20*u+k/20*v,b[k]|=g>e-w&g<d+w|(g<d|g>e)*2;}main(){scanf("%d%d%d%d%d",&x,&y,&s,&t,&w);w=2*w-1;f(1,0);f(0,1);f(1,1);f(1,-1);b[y*20+x]=4;b[t*20+s]=4;for(k=0;k<400;)putchar(".#.?X"[b[k]]),++k%20?0:puts("");}

Dane wejściowe są pobierane ze standardowego wejścia, odczytując 5 liczb w określonej kolejności.

Przed końcowym krokiem zmniejszenia rozmiaru:

#include <stdio.h>
#include <stdlib.h>

int b[400], x, y, s, t, w, d, e, g, k;

void f(int u, int v) {
  d = u * x + v * y;
  e = u * s + v * t;
  if (e < d) k = e, e = d, d = k;
  if (d + w > e) {
    for (k = 0; k < 400; ++k) {
      g = u * (k % 20) + v * (k / 20);
      if (g > e - w && g < d + w) b[k] |= 1;
      if (g < d || g > e) b[k] |= 2;
    }
  }
}

int main() {
  scanf("%d%d%d%d%d", &x, &y, &s, &t, &w);
  w = 2 * w - 1;
  f(1, 0); f(0, 1); f(1, 1); f(1, -1);
  b[y * 20 + x] = 4;
  b[t * 20 + s] = 4;
  for (k = 0; k < 400; ) {
     putchar(".#.?X"[b[k]]);
     ++k % 20 ? 0 : puts("");
  }
}

Kilka wyjaśnień kluczowych kroków:

• Tablica bprzechowuje stan / wynik. Bit 0 zostanie ustawiony dla wszystkich pikseli, które mogą być osiągnięte przez wiązkę. Bit 1 zostanie ustawiony dla wszystkich pikseli, które nie są objęte wszystkimi wiązkami.
• Funkcja fjest wywoływana dla wszystkich 4 kierunków (pionowy, poziomy, oba przekątne). Jego argumenty określają normalny wektor kierunku.
• W funkcji f:
  • Odległość obu punktów wejściowych względem kierunku jest obliczana ( di e) jako iloczyn iloczynu punktu z wprowadzonym wektorem normalnym.
  • Odległości są zamieniane, jeśli to konieczne, tak aby dzawsze było mniejsze lub równe e.
  • Jeśli różnica między di ejest większa niż szerokość wiązki, w tym kierunku nie są możliwe wiązki.
  • W przeciwnym razie zapętlić wszystkie piksele. Ustaw bit 0, jeśli piksel jest osiągalny przez dowolną wiązkę, a bit 1, jeśli nie jest objęty wszystkimi wiązkami.
• Zaznacz dwa punkty wejściowe wartością 4. Ponieważ wykorzystaliśmy bity 0 i 1 do śledzenia stanu, co daje wartości od 0 do 3, jest to najmniejsza nieużywana wartość.
• Zapętlaj piksele bi konwertuj wartości z zakresu od 0 do 4 na odpowiadające im znaki podczas ich drukowania.