Essays/Advent Of Code 2016

From J Wiki
Jump to navigation Jump to search

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)