Essays/Advent Of Code 2016
Problem 1 (Manhattan distance)
Input is a string of right and left turns and steps to take.
Part 1
The objective is to calculate the distance from the origin
Imperative Style
distance =: 3 : 0
+/ | y
)
calcProblem1 =: 3 : 0
steps =. ',' cut every ' ' cut y
facing=.''
xpos =. 0
ypos =. 0
for_step. steps do.
step =. 0{:: step
dir =. 0{ step
count =. ". }. step
if. facing-:'' do.
if. dir -: 'R' do. facing=.'E'
elseif. dir -: 'L' do. facing=. 'W' end.
else.
if. (facing-:'N') *. (dir-:'R') do. facing =. 'E'
elseif. (facing-:'N') *. (dir-:'L') do. facing =. 'W'
elseif. (facing-:'E') *. (dir-:'R') do. facing =. 'S'
elseif. (facing-:'E') *. (dir-:'L') do. facing =. 'N'
elseif. (facing-:'S') *. (dir-:'R') do. facing =. 'W'
elseif. (facing-:'S') *. (dir-:'L') do. facing =. 'E'
elseif. (facing-:'W') *. (dir-:'R') do. facing =. 'N'
elseif. (facing-:'W') *. (dir-:'L') do. facing =. 'S'
end.
end.
NB. smoutput (facing;count)
if. facing-:'N' do. ypos=.ypos+count
elseif. facing-:'E' do. xpos=.xpos+count
elseif. facing-:'S' do. ypos=.ypos-count
elseif. facing-:'W' do. xpos=.xpos-count
end.
NB. smoutput xpos;ypos
end.
distance xpos,ypos
)
calcProblem1 'R2, L3'
calcProblem1 'R2, R2, R2'
calcProblem1 'R5, L5, R5, R3'
-- contributed by Joe Bogner
Imperative Style (cleanup)
Clean up part 1 to make it more table driven vs conditional logic
compass =: _3[\ ('';'E';'W'),('N';'E';'W'),('E';'S';'N'),('S';'W';'E'),('W';'N';'S')
ops =: ('N';[`+),('S';[`-),('E';+`[),:('W';-`[)
calcProblem1a =: 3 : 0
steps =. ,. (0&{ ; ".@:}.) every ',' cut every ' ' cut y
facing=.(<'')
ypos=.0
xpos=.0
for_step. steps do.
'direction count' =. step
compassMatch=. ((0{"1 directions) i. facing) { compass
facing =. compassMatch {~ 1 + ('R';'L') i. (<direction)
op =. ((0{"1 ops) i. facing) { ops
xpos=.xpos op @. 1 count
ypos=.ypos op @. 2 count
end.
+/ | xpos,ypos
)
calcProblem1a 'R2, L3'
-- contributed by Joe Bogner
alternate solution
a =. wdclippaste '' NB. input from clipboard
O =: 4 2 $ _1 0 0 1 1 0 0 _1
f =: 4 : 0
a =. 4 | x ({.@] + _1 1 {~ 'R' = {.@[) {: y
y , a , (}. {: y) + x (".@}.@[ * O {~ ]) a
)
+&|/ }. {: > f each/ (,: 0 0 0) (, <)~ |. dltb each ',' cut a NB. part 1
plot <"1 |: }."1 > f each/ (,: 0 0 0) (, <)~ |. dltb each ',' cut a NB. part 2, find intersection in plot
-- contributed by Pascal Jasmin
alternate solution
NB. Create a boxed list containing each instruction in one box
inst =. <;._2 ',' ,~ (' ',CRLF) -.~ wd 'clippaste'
NB. Encode the direction of movement as (amount of north,amount of east)
NB. R changes sign of north component and then switches components
NB. L changes sign of east component and then switches components
NB. Create direction (in boxed list) for each move. Start by appending north (remove at the end)
dir =. ([: |. ] * 1 _1 |.~ 'L' = {.@[)&.:>/\.&.(,&(<1 0))&.|. inst
NB. Multiply each move by its direction. Add em up, then add component magnitudes
]totmove =. +/ | +/ dir (* ".@}.)&> inst
-- contributed by Henry Rich
alternate solution
tests=: 'R2, L3';'R2, R2, R2,';'R5, L5, R5, R3'
checks=: 5 2 12
Input=: freads '~temp/input.txt'
parseInput=: [: <;._1 ',' , ',RL0123456789'&(-.~ -.~ ])
Directions=: 1 0 , 0 1 , _1 0 ,: 0 _1 NB. NESW
getDirections=: Directions {~ 4 | 'L R' +/\@:<:@i. {.&>
getDistances=: 0 ". }.&>
getMoves=: (getDistances * getDirections)@parseInput
calcBlocks=: +/@:|
getBlocks=: calcBlocks@(+/)@getMoves
assert checks -: getBlocks&> tests
echo '1a is: ',": getBlocks Input
-- contributed by Ric Sherlock
Part 2
The objective is to find the first step that's been taken before
Imperative Style
Take the first problem and expand it to keep track of every step taken. Then key by each step to get the frequency and calc the distance on the first frequency > 1
calcProblem2 =: 3 : 0
steps =. ',' cut every ' ' cut y
facing=.''
xpos =. 0
ypos =. 0
eachstep =. ''
for_step. steps do.
step =. 0{:: step
dir =. 0{ step
count =. ". }. step
if. facing-:'' do.
if. dir -: 'R' do. facing=.'E'
elseif. dir -: 'L' do. facing=. 'W' end.
else.
if. (facing-:'N') *. (dir-:'R') do. facing =. 'E'
elseif. (facing-:'N') *. (dir-:'L') do. facing =. 'W'
elseif. (facing-:'E') *. (dir-:'R') do. facing =. 'S'
elseif. (facing-:'E') *. (dir-:'L') do. facing =. 'N'
elseif. (facing-:'S') *. (dir-:'R') do. facing =. 'W'
elseif. (facing-:'S') *. (dir-:'L') do. facing =. 'E'
elseif. (facing-:'W') *. (dir-:'R') do. facing =. 'N'
elseif. (facing-:'W') *. (dir-:'L') do. facing =. 'S'
end.
end.
NB. smoutput (facing;count)
if. facing-:'N' do.
eachstep =. eachstep,((xpos ,. ypos+i.@]) count)
ypos=.ypos+count
elseif. facing-:'E' do.
eachstep =. eachstep,((ypos ,.~ xpos+i.@]) count)
xpos=.xpos+count
elseif. facing-:'S' do.
eachstep =. eachstep,((xpos ,. ypos-i.@]) count)
ypos=.ypos-count
elseif. facing-:'W' do.
eachstep =. eachstep,((ypos ,.~ xpos-i.@]) count)
xpos=.xpos-count
end.
NB. smoutput xpos;ypos
NB. smoutput <"1 (eachstep)
end.
steps=. }. eachstep
distance 0 { (I. (1<]) #/.~ (<"1 steps)) { steps
)
calcProblem2 'R8, R4, R4, R8'
-- contributed by Joe Bogner
alternative solution
NB. Start from solution given above. Convert each move to a list of one-block moves;
NB. run together into a single table; find position of each block moved to
cumpos =. +/\ ; dir ((# ,:)~ ".@}.)&.> inst
NB. The first dup is the first location whose self-index is not its item position;
NB. fetch that position, convert to distance from origin
]firstrevisit =. +/ | cumpos {~ ({~ (i.&1@:~: i.@#)) i.~ cumpos
-- contributed by Henry Rich
alternative solution
Using definitions from above...
tests=: <'R8, R4, R4, R8'
chks=: 4
getCoords=: 0 0 , +/\@getMoves
getIntermediateCoords=: ;@:(|:&.>)@(2 <@({. + ([: (* * i.@|) -~/))\ ])
getFirstDuplicate=: {.@(#~ i.~ ~: i:~)
getBlockstoFirstIntersect=: calcBlocks@getFirstDuplicate@getIntermediateCoords@getCoords
assert chks -: getBlockstoFirstIntersect &> tests
echo '1b is: ',": getBlockstoFirstIntersect Input
Using Henry's idea to represent moves as multiple 1-block moves this becomes:
getMoves=: (getDistances # getDirections)@parseInput
getCoords=: 0 0 , +/\@getMoves
getFirstDuplicate=: {.@(#~ i.~ ~: i:~)
getBlockstoFirstIntersect=: calcBlocks@getFirstDuplicate@getCoords
getBlockstoFirstIntersect Input
-- contributed by Ric Sherlock
A concise approach
L=: + 0j1&*
R=: + 0j_1&*
parse1=: [: |.&.;: [: rplc&('R';'R ';'L';'L ') '0 ' , ]
eval1=: 3 :'+/|,+.". parse1 y'
NB. revisions for part 2
l=: 0j1&* @],~>:@i.@[|.@:([+{.@]) 0j1&* @]
r=: 0j_1&* @],~>:@i.@[|.@:([+{.@]) 0j_1&* @]
parse2=: [: |.&.;: [: rplc&('R';'r ';'L';'l ') '0 ' , ]
eval2 =: 3 : '+/|.+.(~.". parse2 y){~1 i:~ 1<(#/.~) ". parse2 y'
Here, we take advantage of complex numbers to represent our coordinates, and the rotations. By pushing the complexity into the numbers, we do not have to write much additional code (and most of the remainder is about converting from the the notation being used here).
Example use:
eval1 'R2, L3' 5 eval1 'R2, R2, R2' 2 eval1 'R5, L5, R5, R3' 12 eval2 'R8, R4, R4, R8' 4
Note that we'd need some significant additional work if we were to put this up as a publicly accessible web site (which exposes it to potentially hostile users).
Problem 2 (edge detection)
Input is multiple lines of containing the characters UDLR for up,down,left,right. These are movements from a starting point on a grid/layout.
Part 1
The objective is to calculate the ending position per line. Movements off the grid/layout are rejected.
Solution
Not the speediest on the full input. Uses complex numbers to map to the grid. Movement beyond the map are rejected with "moveNum". moveNum should probably be rewritten. Also, the approach of flattening the list and then reassembling seems heavy handed.
input =: 0 : 0
ULL
RRDDD
LURDL
UUUUD
)
translate =: ((_1j0 1j0 0j1 0j_1) {~ 'UDRL'&i.)
moveNum =: 4 : 'if. (+./ 0 <~ +. x+y) +. (+./ 2 >~ +. x+y) do. x else. x+y end.'
NB. http://www.jsoftware.com/pipermail/general/2007-November/031196.html
NB. http://www.jsoftware.com/pipermail/chat/2009-May/001817.html
NB. (- leftFold 2 3 5) -: _6 NB. 2-3-5
NB. (-/ 2 3 5) -: 4 NB. 5-3-2
leftFold =: 1 : 'u~/@|.y'
steps=: translate each (LF cut input)
structure=:; # each steps
moves=: moveNum leftFold \ 1j1, ; steps
moves =: ((i.@# = i.~) I. structure) <;.1 (}.moves)
digits=: {: every moves
convertInteger=: (1+i.9) {~ (, (i.3) j./ (i.3)) i. ]
smoutput convertInteger digits
-- contributed by Joe Bogner - created in ~ 40 minutes.
alternative solution
NB. Instructions, one box per button
inst =. <;._2 LF ,~^:(~: {:) (' ',CR) -.~ wd 'clippaste'
NB. the four directions
'U D L R' =: _2 ]\ _1 0 1 0 0 _1 0 1
NB. Convert letters to directions; append starting point; simulate each move, clamping at box borders
NB. Do everything /\.&.|. to get front-to-back order. Convert final position back to button number
>: 3 3 #. > ((0 >. 2 <. +)/@|.@,~&.>)/\.&.(,&(<1 1))&.|. "."0&.> inst
-- contributed by Henry Rich (talk) 20:20, 2 December 2016 (UTC)
Part 2
Similar as Part1, except the map is not a 3x3 matrix. The objective is to calculate the ending position per line. Movements off the grid/layout are rejected.
Solution
Changed the approach from above. Instead, build a map and then test moves on the map.
map=: 0 : 0
1
234
56789
ABC
D
)
padMap=: ([: |: (<''),.~ (<''),. ])^:2
mapB =: padMap <"0 > LF cut map NB. pad map so moves off the map can be tested
translate =: ((_1j0 1j0 0j1 0j_1) {~ 'UDRL'&i.)
solve2 =: 3 : 0
steps=: translate each (LF cut y)
structure=: ; # each steps
pos=: 3j1
moves=:''
move=: ((<@: +.) pos) { mapB
for_step. (; steps) do.
try=. ((<@: +.) pos + step) { mapB
if. (try~:(<'')) *. (try~:(<' '))do.
move=:try
pos=:pos+step
end.
moves=:moves,move
end.
; > {: each ((i.@# = i.~) I. structure) <;.1 moves
)
solve2 input
-- contributed by Joe Bogner - created in ~ 20 minutes.
table solution
advantage of making keypad a function parameter, and so same code used for any keypad.
T2 =: > cutLF 0 : 0
55655
11131
22362
31472
44483
627A5
738B6
849C7
99998
A6BAA
B7CDA
C8CCB
DBDDD
)
T =: > cutLF 0 : 0
11241
22351
33362
41574
52684
63695
74877
85987
96998
)
f =: 4 : 0
o =. '5'
for_i. y do. o =. o , > ((x {~ ({."1 x) i. ]) {~ 'URDL' >:@i. [) each/ ({: o) (, <)~ |. <"0 > i end.
}.o
)
T f cutLF a =. wdclippaste '' NB. part1
T2 f cutLF a =. wdclippaste '' NB. part2
-- contributed by Pascal Jasmin
alternative solution
NB. Instructions, one box per button
inst =. <;._2 LF ,~^:(~: {:) (' ',CR) -.~ wd 'clippaste'
NB. the four directions
'U D L R' =: _2 ]\ _1 0 1 0 0 _1 0 1
NB. Get positions of valid buttons, and the label text for them
'legal label' =: (($ #: ' '&(I.@:~: ,)) ; ' ' -.~ ,) ];._2 (0 : 0)
1
234
56789
ABC
D
)
NB. Convert letters to directions; append starting point; simulate each move, clamping at box borders
NB. Do everything /\.&.|. to get front-to-back order. Convert final position back to button label
label {~ legal i. > ((+^:(legal e.~ +))/@|.@,~&.>)/\.&.(,&(<3 0))&.|. "."0&.> inst
-- contributed by Henry Rich (talk) 20:33, 2 December 2016 (UTC)
Problem 3 (Valid Triangles)
Input is lines of text, each containing 3 numbers separated by spaces
Part 1
See which triplets represent valid triangles.
Solution
NB. Read in the input, one box per line
inst =. <;._2 LF ,~^:(~: {:) (CR) -.~ wd 'clippaste'
NB. See if each line is valid, count their number
+/ (+/ > 2 * >./)@(0&".)@> inst
-- contributed by Henry Rich (talk) 13:43, 3 December 2016 (UTC)
Alternate
input =: wdclippaste ''
mat =: ". every LF cut input
isTriangle =: ((0&{ + 1&{)>2&{) *. ((1&{ + 2&{)>0&{) *. ((0&{ + 2&{)>1&{)
smoutput p1=:+/ isTriangle"1 mat
-- contributed by Joe Bogner
Part 2
Reinterpret the input as 3-line groups, with each column representing a triangle.
Solution
NB. Read in the input, one box per line, as for part 1
inst =. <;._2 LF ,~^:(~: {:) (CR) -.~ wd 'clippaste'
NB. Transpose each 3-line section, then check each triangle and count them
+/ , (+/ > 2 * >./)"1@(_3&(|:\)) (0&".)@> inst
-- contributed by Henry Rich (talk) 13:43, 3 December 2016 (UTC)
short alternate
a =. wdclippaste '' +/ <`+/@\:~"1 ". > cutLF a NB. part 1 +/ <`+/@\:~"1 ,/ _3 |:\ ". > cutLF a NB. part 2
-- contributed by Pascal Jasmin (talk) 13:53, 3 December 2016 (UTC)
Alternate
input =: wdclippaste ''
mat =: ". every LF cut input
isTriangle =: ((0&{ + 1&{)>2&{) *. ((1&{ + 2&{)>0&{) *. ((0&{ + 2&{)>1&{)
'a b c' =: |: mat
smoutput p2=: +/ _3(isTriangle)\ (a,b,c)
NB. alternative isTriangle
test =: (+/@}: > {:)
isTriangle2 =: +/ @: ((test) *. ([: test 1&|.) *. ([: test 2&|.)) f.
-- contributed by Joe Bogner
Problem 4 (Security Through Obscurity)
Input is lines of text, encrypted room name, numeric sector id and checksum
Part 1
Sum sector ids of records where calculated checksum of encrypted room name matches checksum.
Solution
Input=: freads '~temp/aoc_04_input.txt'
parseRooms=: <@(}:);._2
getChkSum=: '[' takeafter ]
getSectorId=: _99 ". '[' taketo >:@i:&'-' }. ]
getName=: i:&'-' {. ]
calcChkSum=: (5 {. ~. \: #/.~)@:/:~@:(-.&'-')
echo +/@(getSectorId&> #~ getChkSum&.> = calcChkSum@getName&.>)@parseRooms Input
contributed by Ric Sherlock (talk)
with shorter parsing approach
a =. cutLF wdclippaste ''
f4 =: 3 : 0
'id chk' =. ".`}: apply each ('[' cut >@{:) y
tchk =. (5 {. (~. \: #/.~)@:/:~@:;@:}:) y
if. tchk -: chk do. id else. 0 end.
)
+/ f4@:('-'&cut) every a
Pascal Jasmin (talk) 16:08, 4 December 2016 (UTC)
Parsing with regular expressions
require 'regex'
NB. Read instructions, one box per line
inst =. <;._2 LF ,~^:(~: {:) (CR) -.~ wd 'clippaste'
NB. parse lines, converting each subexpression into a box: 3 boxes per row
parsed =. (<;.0~ [: ,."1 [: }. '([^0-9]*)-(.*)\[(.*)\]'&rxmatch)@> inst
NB. Discard invalid lines. Discard hyphens, sort characters into ascending order, then sort nub by frequency, take top 5
valid =. (#~ (2&{ -: [: ([: (5 {. ~. \: #/.~) [: /:~ -.&'-')&.> 0&{)"1) parsed
NB. Add up the valid sector numbers
+/ 0&".@> 1 {"1 valid
Henry Rich (talk) 17:34, 4 December 2016 (UTC)
Alternative Solution
lines =: LF cut input
checksum=: ([: }: _6&{.) each lines
sectorids =: ([: ". 3 {. _10&{.) every lines
alpha=: a. {~ (a. i. 'a') + i. 26
calc =: 5 {. (~. \: # /.~) @: /:~ @: (#~ alpha e.~ ])
top5 =: calc each ({.~ i.&'[') each lines
[ part1 =: +/ (checksum = top5) # sectorids
contributed by Joe Bogner (talk) 19:16, 9 January 2017 (UTC)
data =: (1!:1) inputpath
segment=: <;.2@:(LF&(-.~))
fragment=: <;._2@:('-'&(,~))&.>
order =: (/:~)@:;@:}:&.>
count =: <@:((\:)@:|@:(2&(-/\))@:(#@:> ,~ (> i. (~.@:>))))
checksum =: 3 : 0
chars=: ~.&.>@:order@:fragment@:segment y
orders=: (count"0)@:order@:fragment@:segment y
(5&{.)&.> (orders {&.> chars)
)
extractsumbool =: (}:@:(_6&{.)&.>@:segment = checksum)
extractroomID=: (_7&}.)&.>@:{:&>@:fragment@:segment
solve =: (0&".)&>@:(extractsumbool # extractroomID)
Graham Trogdon (talk) - 14:05 EST 03/21/17
Part 2
Decrypt room name and search for room containing North Pole objects
Solution
Alpha=: ($~ 999 * #) 'abcdefghijklmnopqrstuvwxyz'
decryptName=: (Alpha,' ') {~ (#Alpha) <. getSectorId + Alpha i. getName
idx=: I. ([: +./ 'north'&E.)&> decryptName&.> parseRooms Input
echo getSectorId idx {:: parseRooms Input
contributed by Ric Sherlock (talk)
With regular expressions
continuing from part 1
NB. The alphabet
alp =. 'abcdefghijklmnopqrstuvwxyz'
NB. Decoding verb: rotate the alphabet, append '-', do translation
dec =. ({~ ('-',alp)&i.)~ (' ' , |.&alp)
NB. Decode each string, and print along with sector number
0: smoutput@(] , (dec 0&".))&>/"1 (0 1) {"1 valid
contributed by Henry Rich (talk) 17:14, 5 December 2016 (UTC)
Alternative Solution
codes =: (_4&}. @: {.~ i.&'[') each lines
validIds =: (checksum = top5) # sectorids
validCodes=: (checksum = top5) # codes
decrypt =: ((alpha i. ]) { alpha |.~ [) each '-' cut ]
[ part2 =: I. (<'northpoleobjectstorage') = validIds ;@decrypt each validCodes
contributed by Joe Bogner (talk) 19:16, 9 January 2017 (UTC)
Problem 5 (Md5 hash)
Input is a secret code.
Part 1
Append numeric suffixes to the secret code until encountering 8 whose first 5 digits are 00000.
Solution
require '~addons/convert/misc/md5.ijs'
inst =: your secret code
(5 { [: md5 inst , ":)"0 >:^:('00000' -.@-: 5 {. [: md5 inst , ":)^:_@>:^:(>:i.8) _1
NB. Now take a walk. No, a 10-mile hike.
contributed by Henry Rich (talk) 17:14, 5 December 2016 (UTC)
console output interactive version
explicit inst(input code) f5 count, start_index
pD =: 1!:2&2 :(] [ 1!:2&2@:(,&<))
f5 =: 4 : 0
'c i' =.y
while. c > 0 do.
t =. 'md5' gethash x ,": i
if. '00000' -: 5 {. t do.
c =. <: c
pD t
end.
i =. >: i
end.
)
tacit same format
inst (] ({.@[ , >:@{:@[)`(<:@{.@[ , >:@{:@[ [ pD@])@.('00000' -: 5 {. ]) 'md5' gethash [ , ":@{:@])^:(0 < {.@])(^:_) 8 0
can get more outputs (part 2) by calling function with its return value.
Pascal Jasmin (talk) 17:55, 5 December 2016 (UTC)
alternative
Input=: 'abc' NB. your puzzle input
require '~addons/ide/qt/qt.ijs'
getmd5=: 'md5'&gethash_jqtide_ NB. much faster than convert/misc/md5
is5zeros=: '00000' -: 5&{.
getSaltedMD5=: getmd5@(, ":)
filterGood=: #~ is5zeros"1
getPassword5a=: 3 :0
8 getPassword5a y
:
salt=. y
pwd=. ''
iter=. 0
whilst. x > # pwd do.
res=. filterGood salt&getSaltedMD5"0 iter + i.1e6
if. #res do. pwd=. pwd , 5{"1 res end.
iter=. iter+1e6
end.
x {. pwd
)
echo 8 getPassword5a Input
--Ric Sherlock (talk) 22:27, 5 December 2016 (UTC)
Part 2
Get numeric values and positions for 8 digit password from MD5 hashes whose first 5 digits are 00000.
Solution
alternative
Reusing definitions from Part 1.
getpos=: _1 ".("0) 5 {"1 ] NB. numeric index of digit in password
getPassword5b=: 3 :0
8 getPassword5b y
:
salt=. y
pwd=. 10$' '
iter=. 0
whilst. ' ' e. pwd do.
res=. filterGood salt&getHashedMD5"0 iter + i.1e6
if. #res do.
res=. res #~ (getpos res) e. I. ' ' = pwd NB. only first pos
pwd=. (6{"1 res) (getpos res)} pwd
end.
iter=. iter+1e6
end.
x {. pwd
)
echo 8 getPassword5b Input
--Ric Sherlock (talk) 22:38, 5 December 2016 (UTC)
Problem 6 (Array counting)
Input is rectangular array of letters.
Part 1
Find most frequent letters in each column.
Solution
Input=: freads 'input.txt'
NB. transpose, count, find index of max count, retrieve from nub
echo (~. {~ [: (i. >./) #/.~)"1 |: ];._2 Input
--Ric Sherlock (talk) 05:25, 6 December 2016 (UTC)
Part 2
Find least frequent letters in each column.
Solution
echo (~. {~ [: (i. <./) #/.~)"1 |: ];._2 Input
--Ric Sherlock (talk) 05:25, 6 December 2016 (UTC)
Problem 7 (Internet Protocol Version 7)
Input is a list of strings
Part 1
Find ABBA sequences not in square brackets.
Solution
NB. Get input, one box per string
inst =. <;._2 CR -.~ wd 'clippaste'
NB. Find ABBA sequence
abba =. (-: |.) *. [: ~:/ 0 1&{
NB. Qualify with not-in-square brackets. Count nesting level of [].
abbaok =. 4&(abba\) (+./@[ *. [: -. [: +./ *.) 4 +./\ 0 ~: [: +/\ 1 _1 0 {~ '[]'&i.
NB. Count em
+/ abbaok@> inst
Henry Rich (talk) 10:26, 7 December 2016 (UTC)
alternate
first line of each function cuts on alternate '[]' . 2nd line does the test for each box, iodd/ieven retrieves select indexes. iodd are the hypertext (bracketed strings) .
a =. cutLF wdclippaste ''
ieven =: {~ 2&((] #~ 0 = |) i.@#)
iodd =: {~ 2&((] #~ |) i.@#)
f =: 3 : 0
a =. (' ' ,y) (<;._1)~ 1 , +/ '[]' ="0 1 y
b =. +./S:0@:(4 (2&}. ((~:/@:[) *. [ -: |.@]) 0 1&{)\leaf ]) a
(0 = +./ iodd b) *. 1 = +./ ieven b
)
f2 =: 3 : 0
a =. (' ' ,y) (<;._1)~ 1 , +/ '[]' ="0 1 y
t =. 1 0 1 {"1 ; (#~ ~:/@( 0 1&{"1) *. =/@( 0 2&{"1)) leaf 3 ]\ leaf ieven a
+./ t e. ; 3 ]\ leaf iodd a
)
+/ f every a NB. for part 1 +/ f2 every a part 2
tacit part 1 with utility verb
altcut =: ({.@] ,~ ])(<;._2)~ 1 ,~ +/@:(="0 1)
+/ ((0 = +./@:(iodd"1)) *. +./@:(ieven"1))@:(+/S:0@:(4 (2&}. ((~:/@:[) *. [ -: |.@]) 0 1&{)\leaf ])) every '[]' altcut leaf a
Pascal Jasmin (talk) 15:07, 7 December 2016 (UTC)
alternate
maskHypernet=: ~:/\@('[' e.~ ])
getHypernet=: (#~ maskHypernet)@(']['&charsub)
noHypernet=: (#~ -.@maskHypernet)@(']['&charsub)
is2Uniq=: 2 = #@~.
isStartRevEnd=: 2&{. -: |.@(2&}.)
hasABBA=: +./@(4 (is2Uniq *. isStartRevEnd)\ ])
supportsTLS=: hasABBA@noHypernet *. -.@hasABBA@getHypernet
Input=: <;._2 freads 'input.txt'
+/ supportsTLS&> Input
--Ric Sherlock (talk) 20:50, 7 December 2016 (UTC)
Part 2
Find ABA sequences not in square brackets with BAB in square brackets
Solution
NB. read input, one box per line
inst =. <;._2 CR -.~ wd 'clippaste'
NB. Find mask of positions of aba
aba =. 3&((0 1 -: {. = }.)\) &.> inst
NB. Find mask of places that start 3 characters in a row outside of []
outsb =. (3 *./\ 0 = [: +/\ 1 _1 0 {~ '[]'&i. )&.> inst
NB. Find mask of places that start 3 characters in a row inside of []
insb =. (3 *./\ 0 ~: [: +/\ 1 _1 0 {~ '[]'&i. )&.> inst
NB. For each outside sequence, create list of indexes of 1st 2 characters; for inside, the last 2
outinx =. (outsb (0 1 +/~ I.@:*.)&.> aba) ,. (insb (1 2 +/~ I.@:*.)&.> aba)
NB. Convert indexes to characters from the string
outinstg =. outinx {&.>"_1 inst
NB. See if input & output share a string
ssl =. +./@:e.&>/"1 outinstg
NB. Count em
+/ssl
Henry Rich (talk) 22:51, 7 December 2016 (UTC)
alternate
Using definitions from Part 1
isFirstLast=: {. = {:
noDelim=: '[' -.@e. ]
getABA=: (3&(]\) #~ (3 (noDelim *. is2Uniq *. isFirstLast)\ ]))
supportsSSL=: +./@(getABA@getHypernet e. 1 0 1&{"1@getABA@noHypernet)
echo +/ supportsSSL&> Input
--Ric Sherlock (talk) 10:48, 8 December 2016 (UTC)
Problem 8 (Two-factor authentication)
Input is a list of instructions for manipulating a matrix of "pixels".
Part 1
Count the number of pixels left in the On state.
Solution
initScreen=: $&'.'
parseInput=: (([: <"1 (,. |.)&.;:)&> 'rotate column';'rotate row') rplc~ 'x ' charsub -.&'=by'
rect=: ('#'"_)`([: < [: i.&.> |.@[)`]}~
row=: (-@{:@[ |. {.@[ { ])`({.@[)`]}
column=: ({.@[ {"1 -@{:@[ |. ])`([: < a: ; {.@[)`]}
rotate=:~
countOn=: +/@('#' = ,)
Input=: freads '~temp/aoc_08_input.txt'
Screen=: initScreen 6 50
0!:100 ;<@('Screen=: Screen '&,);.2 parseInput Input
countOn Screen
--Ric Sherlock (talk) 11:09, 8 December 2016 (UTC)
Part 2
What letters do the "pixels" display?
Solution
NB. to enhance the display <"2 }:"1"2 |:"2 ] _5]\ |: '. ' charsub Screen
--Ric Sherlock (talk) 11:09, 8 December 2016 (UTC)
Problem 9 (Explosives in Cyberspace)
Input is a message that contains strings of (mxn) representing repetitions
Part 1
Count the number of characters after applying the repetitions.
Solution
require 'regex'
NB. Get the string
inst =. (TAB,CRLF,' ') -.~ wd'clippaste'
NB. Get the matches, with a subfield for length and one for repetition count
flds =. '\(([^x]*)x([^)]*)\)' rxmatches inst
NB. Extract starting position & length of each () sequence
fldpos =. (<0 0) {"2 flds
fldlen =. ((<0 1) {"2 flds) + ([: 0&". inst ];.0~ ,.)"1 (1) {"2 flds
NB. At each position, create position of next field: that's field length+position for fields, or position+1 for text
actflds =. _2 }. (_1 ,~ (+ i.@#) fldlen fldpos} ($inst)$1) {~^:a: 0
NB. Get the field indexes that correspond to surviving fields
actx =. (fldpos i. actflds) -. #fldpos
NB. Calculate length of each surviving field as length * repetitions
actlen =. */"1 inst&(0&".;.0~ ,.)"1 (<actx;1 2) { flds
NB. Total the fields, and add 1 byte for each surviving text byte
]totlen =. (actflds -&# actx) + +/actlen
Henry Rich (talk) 13:00, 9 December 2016 (UTC)
expression builder approach
for part 2, recurse through (prerepeated) substring, but can multiply that result with the number of repeats.
p1 =: 4 : 0
o =. ''
while. (# y) > e =. ')' i.~ y do.
b =. '(' i:~ e {. y
i =. ". every 'x' cut y{~ b + >:i. <:e -b
o =. o , ',' , (": b) , ', ' , (": {: i) , (x {:: ' R '; ' RB ') , quote ({.i) {. (>:e )}. y
y =. ({.i) }. (>:e) }. y
end.
o , ',' , ": # y
)
R =: 2 : ' m * # n'
RB =: 2 : ' m * (1 +/@:".@:}.@:p1 n)'
echo +/ ". }. 0 p1 LF -.~ a NB. part1 echo +/ ". }. 1 p1 LF -.~ a NB. part2
Pascal Jasmin (talk) 20:51, 9 December 2016 (UTC)
Part 2
Repetitions are recursive.
Solution
Put the first version into a recursive verb.
require 'regex'
NB. Get the string
inst =. (TAB,CRLF,' ') -.~ wd'clippaste'
clen =: 3 : 0
flds =. '\(([^x]*)x([^)]*)\)' rxmatches y
if. 0=#flds do. #y return. end.
fldpos =. (<0 0) {"2 flds
fldlen =. ((<0 1) {"2 flds) + ([: 0&". y ];.0~ ,.)"1 (1) {"2 flds
actflds =. _2 }. (_1 ,~ (+ i.@#) fldlen fldpos} ($y)$1) {~^:a: 0
actx =. (fldpos i. actflds) -. #fldpos
'len rep' =. |: y&(0&".;.0~ ,.)"1 (<actx;1 2) { flds
NB. Fetch the text after the field
substrs =. y&(<;.0~ ,.)"1 (+/"1 (<actx;0) { flds) ,. len
NB. Recur on each field text
(actflds -&# actx) + +/ rep * clen@> substrs
)
clen inst
Henry Rich (talk) 22:46, 9 December 2016 (UTC)
Problem 10 (Balance Bots)
Input is a list of lines with bot transfer rules or initial value assignments
solution with global bot and output lists
a =. cutLF wdclippaste ''
amdt =: 2 : '(u (v{ ]))`(v"_@:])`]} ]' NB. amend utility.
maybenum =: [^:(__ e. ]) __&".
botrules =: maybenum leaf > 1 5 6 10 11&{ each (#~ ;@:(('bot' -: leaf {.) every)) cut each a
max =. >./ ; 0 2 4 {"1 botrules
bots =: (max+1) $ a:
outs =: 40 $ a:
add =: 4 : 'bots =: x ~.@:,leaf amdt y bots'
addo =: 4 : 'outs =: x ~.@:,leaf amdt y outs'
add/"1 ". every 1 _1 {"1 > (#~ ;@:(('value' -: leaf {.) every)) cut each a
appl =: 3 : 0
r =. botrules {~ y i.~ 0{::"1 botrules
i =. y /:~@:{:: bots
({. i ) addo`add@.('bot' -: 1 {:: r) 2{:: r
({: i ) addo`add@.('bot' -: 3 {:: r) 4{:: r
bots =: a: y} bots
)
I. (61 17 ; 17 61) e.~ (3 : 'bots' [ appl"0)@:I.@:(2 = # every)^:(0 = (61 17 ; 17 61) +./@:e.~ ])^:100 bots NB. part 1
(3 : 'bots' [ appl"0)@:I.@:(2 = # every)^:200 bots
*/ 3 {. ; outs NB. part 2
Pascal Jasmin (talk) 15:43, 10 December 2016 (UTC)
solution with global bot and displayed output lists
This solution preprocesses the input to convert 'output ' to '_' and instances of the word '0' to '999999'. For each line thereafter convert the line into a boxed numeric vector after removing non-digits and space. Outputs effectively become negative robots, and _0 is distinguished from 0 because zero is no longer. The length identifies action.
Num_j_=:(i.10)&+&.:(a.&i.)'0'
Alpha_j_=:;(i.26)&+&.:(a.&i.)&.>'Aa'
LF=:10{a.
Filter=:(#~`)(`:6)
rank=:#@:$
flat_literal=: ((0 <. 1 - rank) }. ([: ,/ ,.&LF)"2^:(0>.<:@:rank))@:":
echo=:0 0$1!:2&2@:flat_literal
show=:[echo
Replace=:2 :'(=&m)`(,:&n)}'
f=:3 : 0
robots=:0$a:
instructions=.y
action=.0$a:
require_bots&>instructions
whilst.(#instructions)*(((_1+#)-+/)mask,0) do.
mask=.i.0
for_boxed_instruction.instructions do.
instruction=.>boxed_instruction
if.-.obeyable instruction do.
mask=.mask,1
else.
command instruction
mask=.mask,0
end.
end.
action=.action,(-.mask)#instructions
instructions=.mask#instructions
end.
action
)
command=:3 :0
if.2=#y do.
'value bot'=.y
i=.({.&>robots)i.bot
robots=: i (value,~&.:>[:>{)`[`]}robots
else.
'bot low hi'=.y
i=.({.&>robots)i.bot
j=.({.&>robots)i.low
k=.({.&>robots)i.hi
values=.}.i{::robots
show y,values
robots=:i({.&.:>@:{)`[`]}robots
robots=:j((<./values),~&.:>{)`[`]}robots
robots=:k((>./values),~&.:>{)`[`]}robots
end.
)
require_bots=:3 :0
if.2=#y do.
'value bot'=.y
else.
'bot low hi'=.y
require_bot low
require_bot hi
end.
require_bot bot
)
obeyable=:3 :0
if.2=#y do.
'value bot'=.y
3>#(({.&>robots)i.bot){::robots
else.
'bot low hi'=.y
(3>#(({.&>robots)i.low){::robots)*.(3>#(({.&>robots)i.hi){::robots)*.(3=#(({.&>robots)i.bot){::robots)
end.
)
require_bot=:3 :0
if.y-.@:e.{.&>robots do.
robots=: robots,<y
end.
)
NB. part a
A=:1!:1<'data'
A=:1!:1<'/home/lambertdw/src/j/adventofcode/2016/36ba/data'
NB. convert word 'output ' to '_' making the outputs as negative robots.
NB. convert word '0 ' to '999999 ' changing output 0 and robot 0.
B=:([: ; [: (<'0 ')Replace(<'999999 ') [: (<'output ')Replace(<'_') [: <;.2 ' ' ,~ [: ; (<LF)Replace(<' ',LF)@:(;/))A
INSTRUCTIONS=: ([:<@:".;._1 LF,-.&Alpha_j_)B
f INSTRUCTIONS
NB. followed by search in emacs
NB. part b
{:*/>([: +./ _999999 _2 _1 e."0/ {.&>)Filter robots
--David Lambert (talk) 06:14, 8 January 2017 (UTC)
Problem 11 (Radioisotope Thermoelectric Generators)
Input is a manual encoding of inputs where number < 10 is a microchip, >:10 a generator, and they match based on 10&|(mod)
solution with optimized breadth first search
optimizations include, hashing such that floors with pairs, microchips, generators are interchangeable. Keeping a played moves list, and filtering allowed moves based on preexisting position, and doing a priority-first search (combo breadth and depth first). Priority first search needs a sorting step (by a scoring function). scoring weighted room count by floor number, with an added bonus for generators being on high floors.
The first control box hold elevator floor, moves made so far, and score for this state.
amdt =: 2 : '(u (v{ ]))`(v"_@:])`]} ]' NB. amend utility.
Y =: (&{::)(@:])
forfirst =: 2 : '(v }. ]) ,~^:(0 < #@[) [ u v take ]'
take =: (([ <. #@:]) {. ])
clean =: (((a:, a:) -.~ ,/)@:)(~.@:)
combT =: [: ; ([ ; [: i.@>: -~) ((1 {:: [) ,.&.> [: ,&.>/\. >:&.>@:])^:(0 {:: [) (<i.1 0) ,~ (<i.0 0) $~ -~
vmove =: 1 ; 0 2 ; 1 3 ; 2
boxvalid =: ((0 = ] #@:#~ >&9) +. ] *./@:e.~ 10 + ] #~ <&10)
validF =: #~ (*./@(boxvalid every@:}.)"1)
moves =: (0 Y @:(0 Y) {:: }.) {~ leaf 2 (<"0@:i.@] , (<"_1)@:combT :: (i.@0:) ) 0 Y @:(0 Y) #@{:: }.
score =: -@((0 ({. -~ {:)@:{:: ]) -~ >:@i.@# +/@:>:@:* (2 * +/@:(9&<) every) + (# every) )@:(2 {. leaf forfirst 1 ])
hash =: {.every @{. ,&": '`' joinstring ('gmp' {~ +./@(10&>) * #)every"0@:(10&| </. ]) each@:}.
play =: 4 : 0 NB. x one item, y list of possible moves.
i =. 0 Y 0 Y x
o =. i.0 0
for_a. >: i {:: vmove do.
o =. o , (<: a) [ amdt 0 each amdt 0"0 1 y /:~@:, leaf amdt a"0 1 (y -.~ leaf amdt (>:i)"0 _ ]) x
end.
NB.played =: played , ({.leaf @{., }.)"1 o =. (#~ played -.@ e.~ ({.leaf @{., }.)"1) (] /: 2 Y@(0 Y)"1) (score (,~ 2&{.) leaf forfirst 1 ])"1 (1 + amdt 1 each forfirst 1 ])"1 validF o NB. without hash
played =: played , hash"1 o =. (#~ played -.@ e.~ hash"1) (hash"1 {./. ]) (] /: 2 Y@(0 Y)"1) (score (,~ 2&{.) leaf forfirst 1 ])"1 (1 + amdt 1 each forfirst 1 ])"1 validF o
)
30{.a=: (]/:2 Y@(0 Y)"1)@:(((#~a:~:{."1)@:((]play moves)"1 clean))@:]forfirst(30*2 >:@>.@^.#@]))^:(10~:(#every)@:{:@:{.)^:33 ,:(score,~leaf forfirst 1])0 0;0 10;11 12 13 14;1 2 3 4;'' [ played =: i. 0 0
NB. solution of 33 moves for this input with just 2 more iterations.
30 {. (]/:2 Y@(0 Y)"1)@:(((#~a:~:{."1)@:((]play moves)"1 clean))@:]forfirst(30*2 >:@>.@^.#@]))^:(10~:(#every)@:{:@:{.)^:2 a
this gets close to solution in a few seconds. Can iterate further on a argument. A pure breadth first approach takes longer (than 8 minutes). But should eventually complete:
30 {.(]/:2 Y@(0 Y)"1) ((#~a:~:{."1)@:((]play moves)"1 clean))^:(10~:(#every)@:{:@:{.)^:33 ,:(score,~leaf forfirst 1])0 0;0 10;11 12 13 14;1 2 3 4;'' [ played =: i. 0 0
Pascal Jasmin (talk) 15:43, 10 December 2016 (UTC)
Problem 12 (Leonardo's Monorails)
Input is a list of assembler instructions
solution with transform into J statements
inp =. > cutLF wdclippaste ''
'a b c d p ' =: 0
inc =: 4 : 'p =: >: p [ (x) =: >: x~'
dec =: 4 : 'p =: >: p [ (x) =: <: x~'
cpy =: 4 : 'p =: >: p [ (y) =: ". x'
jnz =: 4 : 'if. (". x) = 0 do. p =: >: p else. p =: p + ". y end.'
cmd =: ;: inv("1) 1 0 2 {"1 (0&{ ,"1 quote leaf@:(1 2&{))("1) cut"1 inp
f =: 3 : 'while. p < # cmd do. p ".@{ cmd end.a'
f ''
Pascal Jasmin (talk) 15:43, 10 December 2016 (UTC)
solution by assembly and simulating the computer
Note=:3 :'0 0$(0 :0)' :[
assert=: 0 0 $ 13!:8^:((0 e. ])`(12"_))
LF=:10{a.
Num_j_=:(i.10)&+&.:(a.&i.)'0'
Alpha_j_=: ([: ,/ (i.26)&+"1 0&.:(a.&i.))'Aa'
smoutput=:0 0$1!:2&4
literate=: (([ }. (] ([: ,/ ,.&LF)"2)^:(-@:[))~ (0 <. -.@:(#@:$)))@:": NB. as a dyad x is x of ":
show=:[smoutput@:(LF,~literate)
Replace=:2 :'(e.&m)`(,:&n)}'
Filter=:(#~`)(`:6)
Note 'opcodes'
0 load
1 copy
2 increment
3 decrement
4 jump immediate
5 jump register
)
Note 'instruction format'
The program is a table of length 3 instruction vectors.
{. instruction is the opcode
1 2 { are the operands as appropriate. Numbers 0 through 3 represent registers a through d.
)
Note 'state'
y is the state consisting of a vector including the instruction pointer appended to the four registers.
)
TEST=:}:0 :0
cpy 41 a
inc a
inc a
dec a
jnz a 2
dec a
)
While=: 2 :'u^:(0-.@:-:v)^:_'
Until=: 2 :'u^:(0-:v)^:_'
REGISTERS=: 'abcdi'
INSTRUCTIONS=: _3 [\ 'cpyincdecjnz'
NB. assembly verbs
decode=: [: {. [: I. [: {."1 INSTRUCTIONS&(E."1/)
r=: REGISTERS e.~ 4&{
numbers=: _ -.~ _&".
Register=: (&{)(i.`)(REGISTERS"_`)(`:6)
lod=: 0,numbers,(_1 Register)
cpy=: 1 , 4 6 Register
lodcpy=: lod`cpy@.r
inc=: 2 , _1 Register
dec=: 3 , _1 Register
ji=: 4 , numbers
jnz=: 5 , 4 Register , numbers
jijnz=: ji`jnz@.r
assemble=: [: lodcpy`inc`dec`jijnz@.decode&> [: <;._2 ,&LF NB. assemble TEST
NB. evaluation verbs
ip=:_1&{
load=: (1{[)`(2{[)`]}
copy=: (({~1&{)~)`(2{[)`]}
increment=: (>:@:({~1&{)~)`(1{[)`]}
decrement=: (<:@:({~1&{)~)`(1{[)`]}
jump=: (ip@:]+(0~:1{[)*(<:@:(2{[)))`(_1:)`]}
jumpnz=: (ip@:]+(0~:]{~1{[)*(<:@:(2{[)))`(_1:)`]}
execute=:load`copy`increment`decrement`jump`jumpnz@.({.@:[)
step=: 0 0 0 0 1 + ({~ ip) execute ]
halt=: ((0>[) +. (>: #))~ ip
compute=: (step Until halt~ assemble)~&(5{.0)
DATA=: 1!:1<'/home/lambertdw/src/j/adventofcode/2016/36bc/data'
compute DATA
part b
compute=: (step Until halt~ assemble)~&0 0 1 0 0 10#.^:_1 compute DATA
--David Lambert (talk) 02:17, 5 February 2017 (UTC)
Problem 13 (Maze of Twisty Little Cubicles)
Input is a number that modifies maze settings.
floodfill solution
code =: 1353
pad =: 0&([ ,.~ [ ,. [ ,~ ,) :.unpad
0 {:: (>:@>@{. ; (3 3((4&{)`2:@.((0 = 4&{) *. 2 e. 1 3 5 7&{))@,;._3])@:pad@:>@{:)^:(2 ~: (<39 31) { >@{:) (^:_) 0 ; 2(<1 1)}(i.50)(2|+/)@#:@:(code +*:@[ +(3*[)+(2**) + ] + *:@])~"0 0"0 1 i.50 NB. part 1
+/ (=&2) , (3 3((4&{)`2:@.((0 = 4&{) *. 2 e. 1 3 5 7&{))@,;._3])@:pad(^:50) 2(<1 1)}(i.50)(2|+/)@#:@:(code +*:@[+(3*[)+(2**)+]+*:@])~"0 0"0 1 i.50 NB. part 2
Pascal Jasmin (talk) 15:43, 10 December 2016 (UTC)
Problem 14 (One-Time Pad)
Input is a salt.
pregenerated list of hashes
code =: 'cuanljph'
a =: code ('md5'gethash (, ":))"1 0 i.1000000 NB. part 1 20 seconds
a =: code ('md5'gethash^:2017 (, ":))"1 0 i.100000 NB. part2 40 minutes. could have done it in 10k chunks and repeated next line
62 { I. b =. 1001 (}. +./@:((+./@ E.)~"1 1)`0:@.('x' -: ]) (] 'x'"_`(5 # {~)@.(#@[ > ]) 1 i.~ 1 1 1 +./@E."1 ="0 1~)@{.)\ a
Pascal Jasmin (talk) 15:43, 10 December 2016 (UTC)
Problem 15 (Timing is Everything)
This solution does not directly use the input. An additional step to convert the instructions to appropriate verb would be required.
INPUT=:0 :0
Disc #1 has 13 positions; at time=0, it is at position 1.
Disc #2 has 19 positions; at time=0, it is at position 10.
Disc #3 has 3 positions; at time=0, it is at position 2.
Disc #4 has 7 positions; at time=0, it is at position 1.
Disc #5 has 5 positions; at time=0, it is at position 3.
Disc #6 has 17 positions; at time=0, it is at position 5.
Disc #7 has 11 positions; at time=0, it is at position 0.
)
NB. 0 = positions | +/ disc number , start , time
DayF=: 2 :'m|[:+/n&,'
NB. Part A
5{.(#~ ([: *./ 0 = 13 DayF 1 1 ,19 DayF 2 10, 3 DayF 3 2, 7 DayF 4 1, 5 DayF 5 3,17 DayF 6 5)&>)}.i.1e7
NB. Part B
5{.(#~ ([: *./ 0 = 13 DayF 1 1 ,19 DayF 2 10, 3 DayF 3 2, 7 DayF 4 1, 5 DayF 5 3,17 DayF 6 5,11 DayF 7 0)&>)}.i.1e7
--David Lambert (talk) 03:11, 9 January 2017 (UTC)
Problem 16 (Dragon Checksum)
Note=: 3 :'0 0$0 :0' :[
Note 'Instructions'
Call the data you have at this point "a".
Make a copy of "a"; call this copy "b".
Reverse the order of the characters in "b".
In "b", replace all instances of 0 with 1 and all 1s with 0.
The resulting data is "a", then a single 0, then "b".
)
While=: 2 :'u^:(0~:v)^:_'
step=: , (0 , -.@:|.)
checksum=: _2 =/\ ]
NB. Use: LENGTH day16 INPUT
day16=: 4 :''' '' -.~ ": checksum While (0 = 2 | #) x {. step While (x > #) ".&> ":y'
NB. example
20 day16 10000
01100
--David Lambert (talk) 04:15, 9 January 2017 (UTC)
Problem 17 (Two Steps Forward)
INPUT=:'rrrbmfta'
require'/usr/share/j/8.0.4/addons/convert/misc/md5.ijs' NB. a patched version of md5
Until=: 2 :'u^:(0-:v)^:_'
While=: 2 :'u^:(0-.@:-:v)^:_'
DIRECTION=: 'UDLR'
NB. ROOM{DOORS number the adjoining rooms.
DOORS=: _4 [\ _ 4 _ 1 _ 5 0 2 _ 6 1 3 _ 7 2 _ 0 8 _ 5 1 9 4 6 2 10 5 7 3 11 6 _ 4 12 _ 9 5 13 8 10 6 14 9 11 7 15 10 _ 8 _ _ 13 9 _ 12 14 10 _ 13 15 11 _ 14 _
paths=: ,:@:(;&0)
sort_by_shortest=: /: #L:0
sort_by_shortest=: /: #&>
open=: ((_ > DOORS) {~ (<0;1)&{::) *. ('bcdef' e.~ (#DIRECTION) {. md5)@:((<0;0)&{::)
choices=: DIRECTION #~ open
out=: 15 = (<0;1)&{::
new_rooms=: ((<0;0)&{::@:[ ,"1 0 (DIRECTION #~ ])) ;"1 0 (# (DOORS {~ (<0;1)&{::))~
([: ((}.@:[ , new_rooms) open) Until out paths)INPUT NB. answer a
NB. answer b
ouf=: (<'/tmp/a') 1!:3~ [: , LF ,.~ ": NB. append longer paths.
done=: [: , 15 = [: > _ _1&{.
([: (#~-.@:done)@:([([:ouf(#~done)))@:((}.@:[ , new_rooms) open)^:30e6 paths) INPUT
--David Lambert (talk) 06:42, 8 January 2017 (UTC)
Problem 18 (Like a Rogue)
change 400000 to 40 answers part a
INPUT=: '^.^^^.^..^....^^....^^^^.^^.^...^^.^.^^.^^.^^..^.^...^.^..^.^^.^..^.....^^^.^.^^^..^^...^^^...^...^.'
TRAPS=: _3[\'..^^..^^..^^'
stretch=: '.'&([ , ,~)
+/'.'=,('.^' {~ [: +./ TRAPS -:"1/ 3 [\ stretch)^:(<400000)INPUT
--David Lambert (talk) 06:24, 8 January 2017 (UTC)
Problem 19 (An Elephant Named Joseph)
part a
This problem indicates a hunt for the series in the online encyclopedia of integer sequences.
Until=: 2 :'u^:(0-:v)^:_'
start=: 1 ,. i.
finished=: ] 1 = #
i=: [:<.[:-:# NB. the middling index
gifts=: [:+/({~([:<0;~0,i))
steal=: ({~ (([:i.#)-.0,i)) , (gifts , (<0;1)&{)
whiteelephant=: [: steal Until finished start
day19a=: [: >:@:{:@:, whiteelephant
day19a&> >: i.20
1 1 3 1 2 3 5 7 9 1 2 3 4 5 6 7 8 9 11 13
Found as The Josephus problem the brief verb is
white_elephant=: 1&|.&.#:
--David Lambert (talk) 04:44, 9 January 2017 (UTC)
Problem 20 (Firewall Rules)
part a
A sieve of Eratosthenes approach in which we list all the integers, cross out those that don't belong, then count how many remain is a straightforward solution.
inclusive_range=: <. + i.@:(>. - >:@:<.) (i.>:4294967295)-.;<@:inclusive_range/"1 BLACKLIST
As written, this computation won't fit in my computer's memory. Instead I've inserted a verb into the descending sorted ranges concatenated to a starting minimum. Of this verb f, x therefore specifies a range and y the minimum bounded value. Duplicating y eliminates boxing. Converting from the input hyphens and linefeeds to spaces creates an ASCII representation of a numeric vector to prepare the BLACKLIST
LF=:10{a.
smoutput=:0 0$1!:2&4
literate=: (([ }. (] ([: ,/ ,.&LF)"2)^:(-@:[))~ (0 <. -.@:(#@:$)))@:": NB. as a dyad x is x of ":
show=:[smoutput@:(LF,~literate)
Replace=:2 :'(e.&m)`(,:&n)}'
g=:(>:_1+{.)*.(<:{:) NB. in range
f=:{:@:[^:(g~{:) NB. tail of range if in range (otherwise current solution)
h=:[: >: [: f/ (,{:@:{:)@:\:~
A=:1!:1<'/home/lambertdw/src/j/adventofcode/2016/36bk/data'
B=:_2[\".(LF,'-')Replace' 'A NB. The BLACKLIST
h B NB. solution
part b
I solved the second part using j, gawk, regular expressions, and inspection.
i=:(<{."1)~#[ NB. i removes the ranges less than current solution
j=:_:`(($: show@:h)@:i)@.(0<#@:([show@:{.@:/:~)@:[) NB. recursively evaluate h on remaining intervals
B j _1 NB. provide input to gawk 'c{print($1,c,$1-c)}{c=b;b=a;a=$1}'
--David Lambert (talk) 04:44, 15 January 2017 (UTC)
Problem 21 (Scrambled Letters and Hash)
part a
This two step approach assembles the instructions then executes them. The instructions are given a letter followed by one or two operands, in literal form. Thus data and instructions are stored together without boxing. There are 7 operations assigned op-codes of A through G. For example the verb b assembles a swap letter with letter instruction and the verb bb evaluates the instruction. Since each instruction is evaluated once in order, inserting evaluate into the reversed instruction list catenated to the data can execute the program. Arguments were extracted by viscously exploiting their being the only length one words.
Note=:3 :'0 0$(0 :0)' :[
assert=: 0 0 $ 13!:8^:((0 e. ])`(12"_))
LF=:10{a.
Num_j_=:(i.10)&+&.:(a.&i.)'0'
Alpha_j_=: ([: ,/ (i.26)&+"1 0&.:(a.&i.))'Aa'
smoutput=:0 0$1!:2&4
literate=: (([ }. (] ([: ,/ ,.&LF)"2)^:(-@:[))~ (0 <. -.@:(#@:$)))@:": NB. as a dyad x is x of ":
show=:[smoutput@:(LF,~literate)
Replace=:2 :'(e.&m)`(,:&n)}'
Filter=:(#~`)(`:6)
Note '--- Day 21: Scrambled Letters and Hash ---'
The computer system you're breaking into uses a weird scrambling
function to store its passwords. It shouldn't be much trouble to
create your own scrambled password so you can add it to the system;
you just have to implement the scrambler.
The scrambling function is a series of operations (the exact list is
provided in your puzzle input). Starting with the password to be
scrambled, apply each operation in succession to the string. The
individual operations behave as follows:
swap position X with position Y means that the letters at indexes X
and Y (counting from 0) should be swapped.
A {&a. {&a.
opcode=:(a.i.'a')+(<;._2'swap position;swap letter;rotate left;rotate right;rotate based;reverse;move;')&(E.&>
swap letter X with letter Y means that the letters X and Y should be
swapped (regardless of where they appear in the string).
BXY
rotate left/right X steps means that the whole string should be
rotated; for example, one right rotation would turn abcd into dabc.
C {&a. (left)
D {&a. (right)
rotate based on position of letter X means that the whole string
should be rotated to the right based on the index of letter X
(counting from 0) as determined before this instruction does any
rotations. Once the index is determined, rotate the string to the
right one time, plus a number of times equal to that index, plus one
additional time if the index was at least 4.
EX
reverse positions X through Y means that the span of letters at
indexes X through Y (including the letters at X and Y) should be
reversed in order.
F {&a. {&a.
move position X to position Y means that the letter which is at
index X should be removed from the string, then inserted such that
it ends up at index Y.
G {&a. {&a.
)
TEST=:}:0 :0
swap position 4 with position 0
swap letter d with letter b
reverse positions 0 through 4
rotate left 1 step
move position 1 to position 4
move position 3 to position 0
rotate based on position of letter b
rotate based on position of letter d
)
OPERATIONS=: <;._2'swap position;swap letter;rotate left;rotate right;rotate based;reverse;move;'
opcode=: [: I. [: ,/"%. _ _ 1 {. OPERATIONS E.&>~/~ ]
numbers=: a. {~ _ ". -.&Alpha_j_
letters=: [: ; [: (1=#&>)Filter ;:
a=: 'A' , numbers
b=: 'B' , letters
c=: 'C' , numbers
d=: 'D' , numbers
e=: 'E' , letters
f=: 'F' , numbers
g=: 'G' , numbers
parse=: (a@:[`(b@:[)`(c@:[)`(d@:[)`(e@:[)`(f@:[)`(g@:[)@.]&> ,@:opcode)@:(<;._2@:(,&LF))
evaluate=: aa`bb`cc`dd`ee`ff`gg@.('A' -&(a.&i.)~ {.@:[)
NA=: (&{)(i.`)(a."_`)(`:6) NB. get numeric arguments
aa=: ({~ 1 2 NA)~`(2 1 NA@:[)`]}
cc=: (|.~ ( 1 NA))~
dd=: (|.~ ([: - 1 NA))~
ff=: ((({.~ {.)~ , ({~ ({. + [: i. [: <: -/))~ , (}.~ >:@:{:)~)~ (1 2 NA))~
gg=: (((({:@:[ {. ] -. ({~ {.)~)) , ({~ {.)~ , (({:@:[ }. ] -. ({~ {.)~)))~ (1 2 NA))~
solve=: [: evaluate/ [: |. (Alpha_j_{~26+i.8) , parse
stest=: [: evaluate/ [: |. (Alpha_j_{~26+i.5) , parse NB. solve the test data
solve DATA=:1!:1<'/home/lambertdw/src/j/adventofcode/2016/36bl/data'
part b
Trying all !8 possible inputs is the simplest idea that could possibly work since we already have a working program. Rewrite solve to assemble the program just once, and to handle the initial state as well.
solve=: ([: evaluate/ [: |. 'abcdefgh' , parse) :(4 : 0)
program=. |. parse y
([: evaluate/ program&,)"1 x
)
permutations=: {~ (A.&i.~ !)@:#
A=:permutations'abcdefgh'
('fbgdceah' -:"1 solve&DATA)Filter A
--David Lambert (talk) 22:32, 3 February 2017 (UTC)
Problem 22 (Grid Computing)
part a
Changing '-' to ' ', then removing all non-digit and space characters leaves an ASCII encoded j integer vector.
LF=: 10{a.
Num_j_=: (i.10)&+&.(a.&i.)'0'
Replace=:2 :'(=&m)`(,:&n)}'
Filter=: (#~`)(`:6)
lex=: [: e.&(' ',Num_j_)Filter '-'Replace' '
parse=: _6 [\ _ ". lex
DATA=:1!:1<'/home/lambertdw/src/j/adventofcode/2016/36bm/data'
GRID=: parse DATA
used=: [: 0&<Filter _3&{"1
avai=: _2&{"1
perc=: _1&{"1
NB. part a
(([: +/ [: , used <:/ avai) - ([: +/ 50 = perc)) GRID
--David Lambert (talk) 05:56, 9 January 2017 (UTC)