Advent of Code 2021

APL programlama diliyle çözümlerimi aşaĝıda bulabilirsiniz.

Etkinligin ikinci yarisindaki sorularin kaydini gunluk bu sayfaya gecirmedigim icin eksiklikler var. Bir ara tekrar cozup buraya koymak isterim o cozumleri.

1. Gün

https://adventofcode.com/2021/day/1

q1 ←{ +/ (1↓⍵) > (¯1↓⍵) }
q1pt1 ←{
	q1 ⍎⍤1⊢↑ ⊃⎕NGET './q1.txt'1
}
q1pt2 ← {
	x ← ⍎⍤1⊢↑ ⊃⎕NGET './q1.txt'1
	q1 (2↓x) + (1↓¯1↓x) + (¯2↓x)
}
q1pt1_v2 ←{
	+/2</ ⍎⍤1⊢↑ ⊃⎕NGET './q1.txt'1
}
q1pt2_v2 ← {
	x ← ⍎⍤1⊢↑ ⊃⎕NGET './q1.txt'1
	+/2</3+/x
}

N op / diyerek çözümü basitleştirebileceĝimi sonradan öĝrendim.

2. Gün

https://adventofcode.com/2021/day/2

C ← 'forward' 'down' 'up'
M ← (1 0) (0 1) (0 ¯1)
d ← ⊃⎕NGET './q2.txt'1

q2←{
	×/↑↑+/{M[C⍳⍵[1]]×(⍎⍤1⊢↑⍵[2])}¨' '(≠⊆⊢)¨d
}

q2pt2←{
	f←{
		h ← ⍵[1]
		a ← ⍵[2]
		d ← ⍵[3]
		⍵ + ((⍺[1]) (⍺[2]) (a×⍺[1]))
	}
	⍝ (0 0 0) reduce'taki accumulator'un baslangic degeri
	x ← ⊖(↓↓0 0 0), {M[C⍳⍵[1]]×(⍎⍤1⊢↑⍵[2])}¨ ' '(≠⊆⊢)¨d_
	×/ (1 0 1)/ ↑f/ ↑¨x
}

reduce (/) saĝdan sola ilerliyor. Bu yüzden ⊖ yapıp ⍵ ile ⍺ 'yı deĝiştirmem gerekti.

3. Gün

https://adventofcode.com/2021/day/3

C ← 'forward' 'down' 'up'
M ← (1 0) (0 1) (0 ¯1)
d ← ⊃⎕NGET './q2.txt'1

q2←{
	×/↑↑+/{M[C⍳⍵[1]]×(⍎⍤1⊢↑⍵[2])}¨' '(≠⊆⊢)¨d
}

q2pt2←{
	f←{
		h ← ⍵[1]
		a ← ⍵[2]
		d ← ⍵[3]
		⍵ + ((⍺[1]) (⍺[2]) (a×⍺[1]))
	}
	x ← ⊖(↓↓0 0 0), {M[C⍳⍵[1]]×(⍎⍤1⊢↑⍵[2])}¨ ' '(≠⊆⊢)¨d_
	×/ (1 0 1)/ ↑{}/ ↑¨x
}

4. Gün

n ←{ ⍎⍤1⊢↑⍵ }

nonempty ←{ ↑,/0≠⍴¨⍵ }
playcards ←{ n↑↑(nonempty⊆⊢)' '∘(≠⊆⊢)¨1↓⍵ }

d ← ⊃⎕nget'q4-tmp.txt'1
P ← n','(≠⊆⊢)⊃d ⍝ Pouch
C ← playcards d ⍝ Cards
WT ← {⍵⍳1}¨ ↓⍉↑ ↑∨/¨{∨/5∊¨⍵}¨¨{(+/[1]⍵) (+/[2]⍵)}¨∨\C∘=¨P ⍝ Winning Turns
score ←{ P(⊢⌷⊣)WT(⊢⌷⊣)⍵ × +/ (↑,/,/⍵⌷C) ~ (1+⍵⌷WT)↑P }

q4pt1 ← score WT⍳⌊/WT
q4pt2 ← score WT⍳⌈/WT

∨\C∘=¨P diyerek tombala kartlarının her bir turdaki halini türetmek gayet hoştu. \ işlemini önümüzdeki problemlerde nerelerde deĝerlendirebileceĝimi merak ediyorum.

Bu sefer tacit (bileşik) programlamayı daha iyi anladım. Y(⊢⌷⊣)X demenin Y[X] için en iyi çözüm olduĝundan emin deĝilim ama en azından bu tür fonksiyonlar yazabiliyorum.

Bir de çok ↑ ve ↓ yaptıĝımı farkediyorum, ki bu da ¨ kullanmamı gerektiriyor. Kutulanmış deĝerleri işlemeyi daha iyi öĝrenmem gerek.

5. Gun

valid_pt1 ← {(∆x ∆y)←|-/¨⍵ ⋄         (∆x=0)∨(∆y=0)}
valid_pt2 ← {(∆x ∆y)←|-/¨⍵ ⋄ (∆x=∆y)∨(∆x=0)∨(∆y=0)}
applyvent ← {{(⍵⌷M)+←1}¨⍵} ⍝ impure function. modifies M
range ← {d←⍵-⍺ ⋄ s←d÷|d ⋄ ⍺+s×⍳+1+|d} ⍝ 5 range 3 gives 5 4 3

d ← ⊃⎕nget'q5.txt'1
V ← {n¨','∘(≠⊆⊢)¨(1 0 1)/' '(≠⊆⊢)⍵}¨d
D ← 1+⌈/∊V
M ← D D⍴0 ⋄ valid ← valid_pt1 ⋄ applyvent¨0⌷{↑(↑,.(⊂,))/↑range/¨⍵}¨(↑valid¨⊆⊢){↓⍉↑⍵}¨V
q5pt1 ← +/∊M≥2
M ← D D⍴0 ⋄ valid ← valid_pt2 ⋄ applyvent¨0⌷{↑(↑,.(⊂,))/↑range/¨⍵}¨(↑valid¨⊆⊢){↓⍉↑⍵}¨V
q5pt2 ← +/∊M≥2

Haritanin uzerinde gezinerek bu problemi cozmek keyifliydi. Zaten ben bu gibi etkilesimli-kodlama benim sevdigim ve tavsiye ettigim bir yontem. Veri uzerinde yaptigim islemleri adim adim insaa edebiliyor olmak ilk basta zor gorunen problemleri bile goz korkutucu olmaktan cikariyor.

Degisebilir (mutable) bir tablo kullanmak durumunda kaldim. Saf olarak da cozmeyi denemek isterim.

6. Gun

f ← {s←⍵⋄((1↓s),0)+s[0]×(0 0 0 0 0 0 1 0 1)}
genS ← {x←⍵ ⋄ {+/x=⍵}¨⍳8+1}

d ← ⊃⎕nget'q6.txt'1
N ← n','(≠⊆⊢)d

q6pt1 ← 20⍕ +/↑(⊢f)/(⍳80),↓genS N
q6pt2 ← 20⍕ +/↑(⊢f)/(⍳256),↓genS N

Problemi "array"ler uzerinden dusunmenin cozumu kolaylastirdigi bir ornekti bu benim icin.

Ilk buldugum cozum sorunun ikinci yarisinda hafizayi cok sisirince yeni bir cozum bulmam gerekti.

7. Gun

d ← ⊃⎕nget'q7.txt'1
N ← n','(≠⊆⊢)⊃d
K ← 1+⌈/∊N
q7pt1 ← ⌊/+/ |(⍉↑K⍴¨N)-(0⌷¨⍳K(≢N))
g ← {0.5×⍵×⍵+1}
q7pt2 ← ⌊/+/g|(⍉↑K⍴¨N)-(0⌷¨⍳K(≢N))

Tablo ile hos bir sekilde cozulebilen bir problem daha. APL’den bahsettigim bir yazi yazarsam ornek olarak bu problemi kullanacagim.

8. Gun

A ← 'abcdefg'
MK ← {(∊∘⍵)¨A}
MK_v2 ← A∊
Mb ← ↑MK ¨ ('abcfeg' 'cf' 'acdeg' 'acdfg' 'bcdf' 'abdfg' 'abdefg' 'acf' 'abcdefg' 'abcdfg')

l ← {{((~'|'∊⊢)¨⍵)⊆⍵}' '∘(≠⊆⊢)⍵}
loner ← {x←⍵ ⋄ {⍵/x}1={+/x=⍵}¨x}
len ← {∊(⍺=≢¨⍵)⊆⍵} ⍝ selects items with given length
decode ←{
     b←⍺∊⍵
     1(⊢⍳⊣)b∘(⊢≡⊣)¨↓Mb
 }

solve ← {
     x←⍵
     S_1←2 len x
     S_4←4 len x
     S_7←3 len x
     S_8←7 len x
     S_a←S_7~S_1
     S_g←⊃1 len{⍵~S_a,S_4}¨x
     S_e←⊃∊{⍵~S_g,S_a,S_4}¨x
     S_b←loner 1 len{⍵~S_7,S_e,S_g}¨x
     S_d←S_8~S_7,S_b,S_e,S_g
     S_c←loner 1 len{⍵~S_a,S_g,S_e,S_b,S_d}¨x
     S_f←⊃∊{⍵~S_a,S_c,S_g,S_e,S_b,S_d}¨x
     ∊(S_a S_b S_c S_d S_e S_f S_g)
 }

d ← ⊃⎕nget'q8.txt'1
q8pt2 ← +/{R←solve↑0⌷l ⍵ ⋄ ⊖{⍺+10×⍵}/⊖R∘decode¨↑1⌷l ⍵}¨d

Bu aslinda epey vaktimi aldi. S_g yi bulmak problemin dugumunu cozdu.

len ve loner gibi fonksiyonlarin "tacit" hallerini de yazabilmek isterim tabii bir gun :)

9. Gun

x←↑n¨¨⊃⎕NGET'q9.txt' 1
d←⍴x

q9_pt1 ← +/{o←4⌷⍵ ⋄ (o+1)×0=+/o>(0 1 0 1 0 1 0 1 0)/⍵}¨∊¨sx

connlabel←{{{⍵[1;0]=0:0 ⋄ ⌊/0~⍨,⍵}¨(⊂⊢)⌺3 1⊢{⍵[0;1]=0:0 ⋄ ⌊/0~⍨,⍵}¨(⊂⊢)⌺1 3⊢⍵}(⍣≡)1+∘⍸@⊢⍵}
m2←connlabel x<9
pt2←×/3↑(⊂∘⍒⌷⊢){+/∊m2=⍵}¨0~⍨∪∊m2

Komsu-renklendirme problemiydi bu seferki. Array uzerinden bir cozum bulmak icin ugrasir iken ⍣≡ 'i kesfettim. Sistem dengeye varana kadar (sonuc degisene kadar) ayni fonksiyonu tekrar tekrar cagirma imkani veriyor.

Ayrica ⌺ 'yi kullanmayi bilsem evvelden yaptigim 2-boyutlu filtre islemleri cok kolaylasirdi.

10. Gun

B        ← '>'   '}'  ']' ')' ' ' '(' '[' '{' '<'
Cost_b_1 ← 25137 1197 57  3   0   1   2   3   4
Cost_b_2 ← 25137 1197 57  3   0   0   0   0   0
Cost_b ← Cost_b_1

c←{Cost_b[B⍳⍵] }
cost←{
    x ← c⊃(⍵∊'>}])')/⍵
    x>0:0
    {⍺+⍵×5}/⊖0,⊖c¨⍵
}
f_i←{{(⍵,0)∨(0,⍵)}2=(1↓⍺[1]=⍵)+(¯1↓⍺[0]=⍵)}
f_rm←{∊(⊢⊆∘⍵)↑~∨/(⊢f_i∘⍵)¨'()' '{}' '[]' '<>'}
f_rms←{
    w_←f_rm ⍵
    (⍴w_)=(⍴⍵):w_
    f_rms w_
}
q10← {{⍵[0.5×(⍴⍵)-1]}{(⊂⍋⍵)⌷⍵}∊0(≠⊆⊢)cost¨f_rms¨d}
⍝ pt1
Cost_b ← Cost_b_1
q10 0
⍝ pt2
Cost_b ← Cost_b_2
q10 0

11. Gun

step←{
     x0←↑⍵[1]
     d←⍴x0
     flash←{
         ⍝⎕←DISPLAY ⍺ ⍵
         x←⍵
         F←⍺
         F_new←F-⍨x>9
         0=+/∊F_new:F x
         0=+/{(⍵⌷x)+←1}¨N_diag¨(,F_new)/(,⍳d):F x
         (F∨F_new)∇(x)
     }
     l r←↑¨(d⍴0)flash 1+x0
     (+/⍵[0],∊l)({9<⍵:0 ⋄ ⍵}¨r)
 }
x←↑n¨¨⊃⎕NGET'q11.txt'1
pt1←0⌷⊃step/⊖(⊂0 x),⍳100
pt2←1+{⍵⍳1}99<|2-/⊃¨{⊃step/⊖(⊂0 x),⍳⍵}¨⍳1000

"scan" (tarama) islemi tum elemanlarin uzerinden tekrar tekrar geciyor, ve bu yuzden de oldukca hantal. Bunun O(N!) olmayanini bulmak lazim.

12. Gun

A_lower←819⌶⎕A

d←⊃⎕NGET'q12.txt' 1
L←'-'∘(≠⊆⊢)¨d
C←∪↑,/L
C_once←{⍵/C}{⍵∊A_lower}¨⊃¨C
D←⊃↑⍴C
M←D D⍴0⍴D*2
{(⍵⌷M)←1}¨{⍵⍳1}¨¨{(,⍵)∘≡¨C}¨¨,¨¨L ⍝ marks M with 1s

iCity←{1(⊢⍳⊣)(,⍵)∘≡¨C}

f←{
  c←⍺
  Open←⍵
  next←Open∩{⍵/C}(iCity↑c)⌷(M∨⍉M)
  c≡'end':1
  0=(⍴next):0
  Open_←Open~C_once∩(↓,c)
  ∊{⍵ f Open_}¨next
}

pt1←+/ 'start'f(C~↓,'start')

f2←{
     fin←{⍵}
     c←↑⍺[0]
     path←⍺[1]
     Closed←⍵
     C_open←{⍵~↓'start'}{⍵/C}(Closed<(2-+/Closed>1))
     next←C_open ∩ {⍵/C}(iCity↑c)⌷(M∨⍉M)
     c≡'end':(fin 1)
     0=(⍴next):0
     +/∊{n←↓,⍵ ⋄ (⍵(∊path,'-',⍵)) f2 (Closed+(C∊n)×n∊C_once)}¨next
 }

pt2←('start' 'start') f2 ((⍴C)⍴0)

Bildigimiz postaci problemi…

13. Gun

p←{'.#'[⍵]}¨                                                      ⍝ plot for binary matrix

{a←⍺[0] ⋄ b←⍺[1]>⍳a⌷⍴⍵ ⋄ (b⌿[a]⍵)((0,¯1↓~b)⌿[a]⍵)}                ⍝ cuts ⍵ at ⍺ to 2
                                                                  ⍝   where ⍺[0] is axis
                                                                  ⍝   where ⍺[1] is position at axis
f←{
     pt1 pt2←⍺ cut ⍵
     pt2_←⍺{⍺[0]=0:⊖⍵ ⋄ ⌽⍵}pt2                                    ⍝ flip horizontally or vertically
     sBigger←∊⌈/⍴¨pt1 pt2_
     ⊃∨/{⊖⌽sBigger↑⌽⊖⍵}¨⊢pt1 pt2_                                 ⍝ pad (in top and left) to match the bigger of the two
 }
dat←⊃⎕NGET'proj/apl/q13.txt'1
P←⊖¨n¨,','(≠⊆⊢)¨↑','∘((∊¨)⊆⊢)dat                                  ⍝ points as (i j) tuples
d←∊1+⌈/P                                                          ⍝ dimensions
F←(('yx'∘⍳∊)@0)¨(n@1)¨'='(≠⊆⊢)¨↑2∘⌷¨' '(≠⊆⊢)¨1↓,↑','∘((~∊¨)⊆⊢)dat ⍝ folds (as t
M←(1@P)d⍴0                                                        ⍝ the initial matrix

pt1←q13pt1←+/∊(⊃F) f M
pt2←p↑f/⌽(⊂M),F

Internette gordugum APL kodlarindaki gibi yorumlar ekledim yandaki sutuna. Guzel olmamis mi? :)

14. Gun

fn←{
 turns←⍵
 dat←⊃⎕NGET'proj/apl/q14.txt' 1
 p0←2,/⊃dat                                                  ⍝ initial pairs
 Ma←{a b c←⍵ ⋄ (a b)(a c)(c b)}¨(∊(1 0 1)∘/)¨' '(≠⊆⊢)¨2↓dat  ⍝ all movez
 Mk←⊃¨Ma                                                     ⍝ keys of moves
 Punq←∪↑,/Ma,⊂p0                                             ⍝ all pairs, uniq
 M←↑(+/(¯1 1 1)∘×)¨(Punq∊⊂)¨¨Ma                              ⍝ ∆state of moves
 Ps←{↑(Mk∊⊂⍵)/M}¨Punq                                        ⍝ ∆state of pairs
 s0←⊃+/(Punq∊⊂)¨p0                                           ⍝ initial state
 sf←↑{⍵+∊+/Ps×⍵}/⌽(⊂s0),⍳turns                               ⍝ final state
 ⎕←⊢A←∪∊Punq                                                 ⍝ all letters available
 ⎕←⊢scr←⌈2÷⍨(+/sf∘×)¨(+/¨Punq∘=)¨A                           ⍝ scores
 (⌈/-⌊/)scr
}
pt1←fn 10
pt2←fn 40

pt2 yine pt1’in cozumuyle calisamadi. Hafiza cok sisti ve daha etkin bir cozum bulmak durumunda kaldim. Verileri degil verilerin sayilarini tutarak bunu da hallettim. Ama ⌈ kullanimindan oturu aldigim cevap istedigimden 1 fazla cikti. Ilk denememde dogru sonucu elde edemedim yani…

15. Gun

solv←{
  M←⍵
  d←⍴M
  O←(1@(⊂0 0))d⍴0
  V←d⍴0
  C←d⍴0
  g←⊂d-1
  H←+/¨|g-⍳d
  f←{
      ⍝ V  visited
      ⍝ O  open/available
      ⍝ H  heuristics (cost to 'g'oal)
      ⍝ C  costs (cost to start)

      o←⍸(O∧0=V)
      0=≢o:1                ⍝ no more open slots. finish
      x←o⌷⍨{⍵⍳⌊/⍵}C[o]+H[o] ⍝ take the least cost pos
      x≡g:1
      V[x]←1
      n←{(~0∘∊¨⍵≥0)/⍵}{(~0∘∊¨⍵<⊂d)/⍵}(0 ¯1)(¯1 0)(0 1)(1 0)+x      ⍝ neighbours
      c←C[x]
      C[n]←{⍵⌷O:(⍵⌷C)⌊c+⍵⌷M ⋄ c+⍵⌷M}¨n ⍝ update costs to neighbours
      O[n]←1                           ⍝ make available

      0
  }
  {f 0:C[g] ⋄ ∇ 0} 0
}
pt1←{
    M←↑n¨¨⊃⎕NGET'tmp.txt' 1
    solv M
}
pt2←{
    M←↑n¨¨⊃⎕NGET'tmp.txt' 1
    S←⊖⌽10 9↑⌽⊖↑{⍵⌽1+⍳9}¨∪,+/¨⍳5 5
    solv⍪/(⊃,/)¨↓{S∘(⌷⍨)¨⍵∘(,⍨)¨M}¨+/¨⍳5 5
}

16. Gun, 17

Bu noktadan sonraki sorular icin tuttugum notlarin kalitesi dustu. Bazi cozumleri kullandigim arayuz (Ride) cokunce kaybettigim de oldu.

18. Gun

mag←{
    ⍝⎕←↑⍵
    x←⍵
    n d←x
    2>≢n:⊃n
    i j←0 2+(⊢⍳⌈/)d
    l←1⌷⍴↑x
    a←↑i↑¨x
    c←↑j↓¨x
    m←+/3 2×⌷∘n¨(i(i+1))
    n←1-⍨i⌷d
    ∇↓(a,(2 1⍴m n),c)
}
itr←{
    s x←(9 4)<⌈/¨⍵
    x:∇ xpl ⍵
    s:∇ spl ⍵
    ⍝⎕←↑⍵
    ⍵
}
add←{0 1+↓⊃,/↑¨⍺ ⍵}
par←{
    x←⍵
    b←↑x∘=¨'[],'
    n←⍎¨(~∨⌿b)⊆x
    d←⊃¨(~∨⌿b)⊆(-⌿+\2↑b)
    n d
}

mag⊃⊢y←(itr add⍨)/⌽par¨⊃⎕NGET'proj/apl/q18.txt' 1

19. Gun

'pmat' 'det'⎕CY'dfns'
RA←{⍵/⍨1=det¨⍵},(↓pmat 3)∘.{⍵@(⍺,¨⍳3)⊢3 3⍴0},1-2×⍳2 2 2
dat←getdata ⍬
D←≢dat
snsA←(∘.⊣)⍨dat

⍝ find matching sensors
matches←(∘.{cmn←⊃∩/∊¨⍺ ⍵ ⋄ 12=+⌿⍺∊cmn})⍨{(∘.far)⍨↓⍵}¨dat
snsM←↑¨(⍴snsA)⍴↑(,matches),.{⊂⍺/↓⍵}(,snsA)

fnd←(,⍨⍴dat)⍴⊃(,snsM),.(⊂relpos)(,⍉snsM)
⍝ found matches. fnd[i;j] ≡ r x y z,
⍝   `r` is ∆rot of "j" wrt "i"
⍝   `x y z` is ∆pos of "j" wrt "i"
fndr←⊃¨fnd    ⍝ found rotations
fndp←(1∘↓)¨fnd ⍝ found positions
I←⍸25>fndr    ⍝ indexes of matches in "fnd"

⍝{(⍵⌷xp)←⊂0 0 0 ⋄ (⍵⌷xr)←0}¨{(=/¨⍵)/⍵},⍳D D

open←(≢∪∊I)⍴0
imap←(⊃¨I){⊂(1∘⌷¨⍵)}⌸I
myi←(≢imap)⍴10+≢imap
0{myi[⍺]<⍵:⍵ ⋄ myi[⍺]←⍵ ⋄ ⍵>30:⍵ ⋄ ∇/(⊃imap[⍺]),⍵+1}0
Icand←⊃,/(((⊃¨I){⊂⍵}⌸I)@myi)27⍴9999
Idup←{i j←⍵ ⋄ open[i]←1 ⋄ open[j]}¨Icand
I_←(~Idup)/Icand
0≡≢∊~/∊¨I I_ ⍝ ensure nothing missing

P R←fill I_ ⍝ absolute positions and rotations
part1←≢∪⊃⍪/{↑(⊃P[⍵])∘+¨R[⍵]∘roti¨↓⊃dat[⍵]}¨⍳D
part2←{⌈/∊P(∘.{+/⍺-⍵})P}

20. Gun

m x0←readdata ⍬

pad←{k←⍺ ⋄ r c←(2 0)+⍴⍵ ⋄ (r⍴k){⍺,⍵,⍺}(c⍴k){⍺⍪⍵⍪⍺}⍵}

⊢part1←+/∊({s←⊃⍵ ⋄ a←⊃1⌷⍵ ⋄ (m⌷⍨2⊥9⍴s),⊂({m⌷⍨2⊥∊{(s 0 1)[⍵]}¨⍵}⌺3 3)1+s pad a}⍣2)(0,(⊂x0))
⊢part2←+/∊({s←⊃⍵ ⋄ a←⊃1⌷⍵ ⋄ (m⌷⍨2⊥9⍴s),⊂({m⌷⍨2⊥∊{(s 0 1)[⍵]}¨⍵}⌺3 3)1+s pad a}⍣50)(0,(⊂x0))

21. Gun

part1←{
   ⍝ both 'pad' and '⌺' uses 0 as fill-character
   ⍝  so I used 1 2 in place of 0 1 in the img matrix
    n←0
    scr←0 0
    pos←1-⍨4 1
    {i nr←⍵ ⋄ ⌈/scr≥1000:⍵ ⋄ nr_ ∆x←r nr ⋄ pos[i]←10|∆x+i⌷pos ⋄ scr[i]+←1+pos[i] ⋄ ∇(2|i+1)nr_}(0 0)
    (⌊/scr)×n×3
}
part2←{
    initpos←4 8
    N←21+10+1
    I←⍳N N
    IW←⍸¨⊂[1 2]21<(0 1)∘.⌷I ⍝ win indexes
    p←↓(initpos-1)(∘.=)⍳10 ⋄ s←(1@(⊂0 0))N N⍴0 ⋄ wins←0 0 ⋄ f 0
    (⊂p)(⊂s)
}

22. Gun

todo

23. Gun