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)