01 calorie counting

Day 1: Calorie Counting

01 fennel

the first one

this is my final^{[citation needed]}(update: not final, see below) solution using fennel, after solving the puzzles with lua first (see (even more) below).

(io.input "input")

(var calories [0])

(each [line (io.lines)]
  (if (= line "") (table.insert calories 0) 
    (let [i (length calories)]
      (tset calories i (+ (tonumber line) (. calories i))))))

; sort so that greater numbers go first
(table.sort calories (λ [a b] (> a b))) 

(print "part 1" (. calories 1))
(print "part 2" (let [c calories] (+ (. c 1) (. c 2) (. c 3))))

after watching aw's stream i realized the solution is inefficient in the sense that use a whole “array” to save the results, and that i use the table.sort function. instead, i could have calculated the maximum(s) on the fly, without needing to store anything else

i'm letting that pass for now because i'm here to learn about the affordances of the language(s), and i see knowing the standard library and becoming fluent with the use of tables as part of that.

update

same day update: i didn't let the previous notes pass, and i managed to solve everything “on the fly” by using a small table and the functions to insert or remove elements at arbitrary positions (table.insert or table.remove respectively), that default to acting at the end, like a stack.

(io.input "input")

(local n 3)

(var max [0 0 0]) ; greatest is position 1, then 2, last 3
(var calories-sum 0)

(each [line (io.lines)]
  (let [num (tonumber line)] 
    (if (not num) 
      (let [ s calories-sum
        ; count to how many "max" the new sum is greater than
        greater-than 
          (accumulate [sum 0 _ m (ipairs max)] 
            (+ sum (if (> s m) 1 0)))]
        (set calories-sum 0) ; restart accumulator
        (when (> greater-than 0) 
          ; insert new max and remove last element
          (table.insert max (- (+ n 1) greater-than) s) 
          (table.remove max))) 
      (set calories-sum (+ calories-sum num)))))

(print "part 1" (. max 1))
(print "part 2" (accumulate [sum 0 _ m (ipairs max)] (+ sum m)))

this took a while. it seems it is not necesarily faster, but it was fun to build. i especially liked arriving at the use of accumulate to figure out to how many maximums the new sum is.

i decided to use that strategy to avoid having to do 1) a “manual” comparison between the new sum and each of the maximum values, 2) a “manual” swapping around of the maximum values.

01 lua

i followed the drive to go fast when the puzzle was unveiled, so i used lua first. it seems i feel very comfortable in structured, imperative programming.

first version

this is a cleaned up version of what i used to obtain the results. i slightly modified it after doing the fennel version, especially in the use of the length operator # instead of an accumulator.

io.input("input")

calories = {0}
i = #calories
for line in io.lines() do
	if line ~= "" then
		calories[i] = calories[i] + tonumber(line)
	else
		table.insert(calories, 0)
		i = #calories
	end
end

--
maxa, maxb, maxc = 0, 0, 0
for i, c in ipairs(calories) do
	if c>maxa then
		maxc = maxb
		maxb = maxa
		maxa = c
	elseif c>maxb then
		maxc = maxb
		maxb = c
	elseif c>maxc then
		maxc = c
	end
end

part1 = maxa
part2 = maxa+maxb+maxc
print("part 1", part1)
print("part 2", part2)

the “inefficiency” is more evident here, as i use two loops to go through similar data twice. additionally, at this point i didn't remember there was a way of sorting the “array”, so i did a “manual” comparison.

second version

once i saw there was a table.sort function i used it instead. only the second part changed; the second for loop and what comes next was replaced with the following:

table.sort(calories, function(a,b) return (a>b) end)

part1 = calories[1]
part2 = calories[1]+calories[2]+calories[3]
print("part 1", part1)
print("part 2", part2)

lessons

some practical stuff i take with me:

• even though lua is “small”, it does have a handy table.sort function. it's worth keeping the standard library in mind (and in sight, first).
• regarding efficiency, it makes sense to think through the puzzle a little bit more before starting to write code. not because lua has tables i have to use them.
• update: it's fun to figure out if some aspects can be solved using either accumulate (note to self, similar to “fold”) or icollect (note to self, similar to “map”)

interestingly, i think that the fennel code looks way more nicer than the lua one. i'm starting to see the aesthetic appeal of lisps.

for the record^(?), i woke up in order to be ready at 6am, i did the first part in less than 5 minutes, and i was done with the second one in less than 15 minutes (total). let's see how that changes as i get more proficient and as the puzzles get more difficult. also, let's see what happens with my willingness to wake up that early to be “on time” for each new puzzle.

back to top

02 rock paper scissors

Day 2: Rock Paper Scissors

02 lua

for this puzzle i thought the simplest way to go would be to use a lookup table (i.e. hard-code the data), especially because of, you know, lua tables.

i'm glad i decided this instead of wrangling with conditionals and so on, even more when arriving at the second part.

io.input("input")

-- Rock, paper, scissors
own_scores = { X=1, Y=2, Z=3 } 
game_scores = { X = { A=3, B=0, C=6},
                Y = { A=6, B=3, C=0},
                Z = { A=0, B=6, C=3}}

		-- lose, draw, win
own_scores_2 = { X=0, Y=3, Z=6 }
game_moves = { 	X = { A=3, B=1, C=2}, -- lose
                Y = { A=1, B=2, C=3}, -- draw
                Z = { A=2, B=3, C=1}} -- win
score = 0
score_2 = 0
for line in io.lines() do
  other, you = string.match(line, "(%a+) (%a+)")
  score = own_scores[you] + game_scores[you][other] + score
  score_2 = own_scores_2[you] + game_moves[you][other] + score_2
end

print("part 1", score)
print("part 2", score_2)

not much to see here, i guess!

worth mentioning is that several times i saw the tables and wanted to “simplify” them. for example, own_scores_2 would correspond to the result of own_scores minus 1 and then times 3 (?). i decided to not do it; it doesn't make the code clearer and probably requires slightly more operations to work.

02 fennel

i doubted in doing the fennel version as it would be too straight of a transcription, but then i decided to go for it to compare the notation of tables there.

(io.input "input")

; rock, paper, scissors
(local own-scores-1 {:X 1 :Y 2 :Z 3})
(local game-scores {:X {:A 3 :B 0 :C 6}
                    :Y {:A 6 :B 3 :C 0}
                    :Z {:A 0 :B 6 :C 3}})

                     ; lose, draw, win
(local own-scores-2 {:X 0 :Y 3 :Z 6})
(local game-moves  {:X {:A 3 :B 1 :C 2}
                    :Y {:A 1 :B 2 :C 3}
                    :Z {:A 2 :B 3 :C 1}})

(var score-1 0)
(var score-2 0)

(each [line (io.lines)]
  (let [(other you) (string.match line "(%a+) (%a)") 
    move-score (. own-scores-1 you) 
    round-score (. (. game-scores you) other)
    own-score-2 (. own-scores-2 you)
    move-score-2 (. (. game-moves you) other)]
    (set score-1 (+ score-1 move-score round-score))
    (set score-2 (+ score-2 own-score-2 move-score-2))))

(print "part 1" score-1)
(print "part 2" score-2)

i feel that in this case the code gets more verbose; i tried to clean it up a little bit by using locals for the intermediate results from the tables.

lessons

i can see myself several years ago not wanting to use lookup tables. here i am now, and i'm glad about it.

also, lua tables are nice!

regarding time, i did wake up early to solve this, with a little bit of initial struggle. i had the first answer in around 14 minutes, and i was done in around 21 total. maybe i was “slow” writing the tables, but i would probably have been slower writing the conditions.

back to top

03 rock paper scissors

Day 3: Rucksack Reorganization

03 lua

this is the code i used to finish the puzzles and get the stars!

io.input("input")

function getPriority(c)
  if c>='a' and c<='z' then  
    return string.byte(c) - string.byte('a') + 1
  else
    return string.byte(c) - string.byte('A') + 27
  end
end

-- for part 1
local sum = 0
local linecount = 0
-- for part 2
local common = {}
local sumBadges = 0

for line in io.lines() do
  local h = {}
  local i = 0
  local repeated = nil
  for c in string.gmatch(line, "%a") do
    -- part 1
    if i<#line/2 then
      h[c] = (h[c] or 0) + 1
    elseif not repeated and h[c] then
      repeated = c
    end
    i = i + 1

    -- part 2
    if linecount==0 then
      common[c] = 1
    elseif common[c] and linecount==1 then
      common[c] = 2
    elseif common[c]==2 then -- 2
      common[c] = 3
      sumBadges = sumBadges + getPriority(c)
    end
  end
  -- part 1
  local priority = getPriority(repeated)
  sum = sum + priority

  -- part 2
  if linecount==2 then common = {} end
  linecount = (linecount + 1)%3
end

print("part 1", sum)
print("part 2", sumBadges)

the code got the work done but i feel there would be ways to make it even more compact. especially for the second part, i'm not super happy about how i managed to do it — but i knew being this explicit would help me in not having weird edge cases.

i won't do the fennel version for the moment, but it'd be interesting to try using “functional niceties” for that.

lessons

this was a nice opportunity to practice an apparently common lua idiom, the use of or to use the value of a variable or set one if it wasn't set. additionally, i got to use string.byte and string.gmatch; both seem handy and i had to look them up to make sure they existed and to make sure how they were used as an iterator (in the latter case).

it seems i like (and i'm used to) working at a somewhat “low” level, getting things done managing arrays, counters, and stuff like that. hopefully the fennel attempts will help me in trying another way of thinking.

this time i needed around 15 minutes for the first part, and i was done in 35 minutes total. i could have used more sleeping time, but yesterday afternoon and night was great.

i take with me the feeling of being alright with not having the most beautiful, concise code. i'm having fun!

back to top

04 camp cleanup

Day 4: Camp Cleanup

04 fennel

this is was my final solution using fennel, written after the lua version below.

(io.input "input")

(var sum1 0)
(var sum2 0)
(each [line (io.lines)]
  (let [(a b c d) (string.match line "(%d+)-(%d+),(%d+)-(%d+)")
        ri1 (tonumber a) rf1 (tonumber b) 
        ri2 (tonumber c) rf2 (tonumber d)]
      ; part 1
      (when (or (and (>= ri1 ri2) (<= rf1 rf2))
                (and (>= ri2 ri1) (<= rf2 rf1)))
        (set sum1 (+ sum1 1)))
      ; part 2
      (when (or (and (>= rf1 ri2) (<= ri1 ri2)) 
                (and (>= rf2 ri1) (<= ri2 ri1)))
        (set sum2 (+ sum2 1)))))

(print "part 1" sum1)
(print "part 2" sum2)

i'm still using the approach of iterating line by line and increasing the counters inside; i wonder how would it be to use the accumulate iterator in cases like this.

this is basically a transcription of the lua program below, but i like it more do to its compactness.

04 lua

this is the slightly cleaned up program i used to solve the puzzle and get the stars:

io.input("input")

local sum = 0
local sum2 = 0
for line in io.lines() do
  local ri1, rf1, ri2, rf2 = string.match(line, "(%d+)-(%d+),(%d+)-(%d+)")

  ri1=tonumber(ri1)
  rf1=tonumber(rf1)
  ri2=tonumber(ri2)
  rf2=tonumber(rf2)

  -- part 1
  if (ri1>=ri2 and rf1<=rf2) or (ri2>=ri1 and rf2<=rf1) then
    sum = sum + 1
  end
  -- part 2
  if (rf1>=ri2 and ri1<=ri2) or (rf2>=ri1 and ri2<=ri1)  then
    sum2 = sum2 + 1
  end
end

print("part 1", sum)
print("part 2", sum2)
	

note the use of the tonumber function, that “bit” me and made me have a couple of wrong answers. i erronously thought that by capturing a set of digits with the (%d+) pattern i was going to get a number. i guess i got spoiled by awk (?). in any case, i was able to figure that out with the typeof function.

actually, for a moment i used the following approach to get the numbers. i could have stayed with the table and not use local, named variables, but i preferred to use the named variables to not get lost in the comparisons.

local r = {}
for n in string.gmatch(line,"%d+") do
	table.insert(r, tonumber(n))
end
local ri1=r[1]
local rf1=r[2]
local ri2=r[3]
local rf2=r[4]
	

updates

conditionals

after watching aw's stream and looking at his code for day 4 in UF i realized my conditions were redundant in part two.

in fennel, it was enough with doing:

(when (and (>= rf1 ri2) (<= ri1 rf2)) 
  (set sum2 (+ sum2 1)))
	

and respectively, in lua:

if (rf1>=ri2 and ri1<=rf2) then
  sum2 = sum2 + 1
end	

mapping

@flavigula@sonomu.club illuminated me and allowed me to see how i could use both the threading macro -> and the table.pack function to convert all the arguments in the form of string, to numbers, and assing them directly to the named variables i had.

the following would be the actual final^{citation needed} version using fennel:

(io.input "input")

(var sum1 0)
(var sum2 0)
(each [line (io.lines)]
  (let [pattern "(%d+)-(%d+),(%d+)-(%d+)"
    [ri1 rf1 ri2 rf2] 
    (icollect [_ n 
              (-> line (string.match pattern) (table.pack) (ipairs))]
      (tonumber n))]
      (when (or (and (>= ri1 ri2) (<= rf1 rf2))
                (and (>= ri2 ri1) (<= rf2 rf1)))
        (set sum1 (+ sum1 1)))
      (when (and (>= rf1 ri2) (<= ri1 rf2)) 
        (set sum2 (+ sum2 1)))))

(print "part 1" sum1)
(print "part 2" sum2)

note (to self?) that the threading macro part is equivalent to:

;(-> ...) above equivalent to:
(ipairs (table.pack (string.match line pattern)))

lessons

in both of these cases, i was left wondering if i could use the return values of string.match and “pack” them in a table so that then i could map the tonumber function.

now i know that when parsing string to numbers, i should always use tonumber to make sure. interestingly, in previous days i had used it although i had noticed it didn't seem to make a difference. note that today the problem was apparent when reading numbers greater than or equal to 10 (i.e., with more than 1 digit), in the actual input.

for a moment i thought of starting today's solution with fennel directly, but then again i preferred to go with lua in order to solve it “fast”. probably, when puzzles get more complicated and i need more time to think through them, i'll start preferring using fennel.

today i finished part 1 in a little bit more than 18 minutes, and more than half of those were about figuring out the error that needed the tonumber function. i was done in a little bit more than 26 minutes total; for part 2 i was also making some mistakes with the comparisons, that i could identify since testing with the sample cases.

back to top

05 supply stacks

Day 5: Supply Stacks

05 lua

this is the code i used to solve today's puzzles and get the stars! this was some intense parsing.

for part 2 i originally had another file as i didn't want to mess up my answer for part 1, but for posting it here i joined them both together as the differences were minimal.

io.input("input")

stacks = {}
stacks2 = {}
instructions = {}
count = 0

-- parsing
for line in io.lines() do
  if string.find(line, "%[%a%]") then
    local nstacks =  #line//4 + 1  -- 1 5 9 13
    for i = 1,nstacks do
      if count == 0 then
        stacks[i] = {}
        stacks2[i] = {}
      end
      local index = 1 + (i-1)*4 -- 1, 5, 9
      local s = string.sub(line, index, index+3)
      local t = string.match(s, "%[(%a)%]")
      -- insert crate at the bottom:
      table.insert( stacks[i], 1, t )
      table.insert( stacks2[i], 1, t )
    end
  elseif string.find(line, "^move") then
    local pattern = "^move (%d+) from (%d+) to (%d+)$"
    local tt = table.pack(string.match(line, pattern))
    local t = {}
    for j, v in ipairs(tt) do t[j] = tonumber(v) end
    table.insert(instructions, t)
  end
  count = count + 1
end

-- moves
for _, t in ipairs(instructions) do
  q, src, dst = table.unpack(t)
  -- part 1
  for n = 1,q do
    local crate = table.remove( stacks[src] )
    table.insert( stacks[dst], crate )
  end

  -- part 2
  local crates = {}
  for n = 1,q do
    crates[q-n+1] = table.remove( stacks2[src] )
  end
  for n = 1,q do
    table.insert( stacks2[dst], crates[n] )
  end
end

-- result
local result = ""
for _, stack in ipairs(stacks) do
  result = result .. stack[#stack]
end
print("part 1", result)

result = ""
for _, stack in ipairs(stacks2) do
  result = result .. stack[#stack]
end
print("part 2", result)

later on i realized i could have done the moves part inside the main parsing loop as well, getting rid of the instructions table. it's such a “minor” change that i'm leaving it as is.

for parsing debugging purposes i wrote the following function that i left out above because it's not used to arrive at the answer:

function printStacks()
  for i,stack in ipairs(stacks) do
    local s = ""
    for _,j in ipairs(stack) do
      s = s .. j
    end
    print(i, s)
  end
end

lessons

i considered starting working on the puzzle using fennel, but now i found it a little bit overwhelming not because of wanting to go fast but because of the data handling i envisioned would happen (and yes, because i thought it would take me a lot of time).

i'm happy i was able to imagine how to solve this with lua, and also because i managed to keep calm. i liked how i was able to clean up my code and ideas on-the-fly. for example, first i was just storing the first kind of lines to parse them later when i “knew for sure” the amount of stacks, i.e. because of the numbering. then i realized i could know that amount from the beginning and therefore parse the crates in the first pass.

i also enjoyed using the table library functions to manage the “literal” stacks in part 1, and then using some array wrangling for the queues in part 2. the parsing was what took me the longest; once i had the data i found the moves to be easy.

for part 1 i was done in a little bit more than 57 minutes (!), and i was done with everything in 1:02 hours. let's see what comes in the next days... meanwhile, time to “start” the day!

back to top

06 tuning trouble

Day 6: Tuning Trouble

06 lua

this was my solution using lua:

io.input("input")
local s = io.read("a")

function endOfMarker( n ) -- n is the window size
  local i=1
  repeat
    local window = string.sub(s,i,i+n-1)
    local repeats = false
    local chars = {}
    for j=1,n do
      local c = string.sub(window,j,j)
      if chars[c] then 
        repeats = true
        break
      else chars[c] = true 
      end
    end
    i = i + 1
  until not repeats or i>#s
  return i+n-2
end

print("part 1", endOfMarker(4))
print("part 2", endOfMarker(14))

lessons

in the first part i felt a little bit slow; probably because i wanted to use the string.sub function in order to get used to its notation (first index, and last index of substring). at the end that approach was nice because i could easily extend it for part 2.

this was also the first time i use a repeat until loop. i observed in the opposite direction the confusion that some of my students tended to have when having more than one condition to signal the end of a (while) loop, i.e. should there be an and or an or.

this time i started but then i didn't feel like replicating the same behavior in fennel, as i feel there would be a more functional of solving this. looking forward to an example of this!

regarding times, for the first part i finished in a little bit more than 14 minutes, but then i was done at a little bit less than 17; and that included the re-writing of the code as a function that i could reuse for both parts. i'm still managing and enjoying waking up some minutes before the puzzle launch.

back to top

07 no space left on device

Day 7: No Space Left On Device

07 lua

today is one of those days when i saw the problem and thought “what am i doing here” at first. with a little bit more time i managed to start working on it.

in general i'm glad i'm using lua, but for this case i was especially glad that tables (and variables, for that matter) work the way they work; i.e. that i can point to the same table with different variables. i remember i had some problems last year with awk in situations like this, where it was not clear to me what it was doing.

the longest code so far!

io.input("input")

function createDir( dirname )
  return { name = dirname, children = {}, localsize = 0}
end

function insertDirIntoWD( dirname )
  -- if it already exists, return it
  for _, d in ipairs( wd.children ) do
    if d.name == dirname then return d end
  end 
--  print("inserting", dirname, "into", wd.name)
  -- create it otherwise
  local newdir = createDir(dirname)
  table.insert( wd.children, newdir )
  table.insert( dirs, newdir )
  return newdir
end

-- initialize
root = createDir("/") 
dirs = {root}
stack = {root}
wd = root -- working directory

local listing = false
for line in io.lines() do
  if listing then
    if string.find(line, "^%$") then
      listing = false
    else -- listing
      local pattern = "^(.+) (.+)$"
      local info, name = string.match( line, pattern )
      if info == "dir" then
        insertDirIntoWD( name )
      else -- file
        local size = tonumber(info)
        wd.localsize = wd.localsize + size
      end
    end
  end -- if listing

  if not listing then
    if string.find(line, "^%$ ls") then
      listing = true
    else -- change directory
      local dirname = string.match(line, "^%$ cd (.+)$")
      if dirname == "/" then
        wd = root
        stack = {root}
      elseif dirname == ".." then
        wd = table.remove( stack ) -- pop from stack
      else -- go to named dir
        table.insert( stack, wd ) -- push wd into stack
        wd = insertDirIntoWD( dirname )
      end -- if dirname
    end -- if $ ls
  end -- if not listing

end -- for line

function totalSize( dir )
  local sum = dir.localsize
  for i, d in ipairs( dir.children ) do
    sum = sum + totalSize( d )
  end
  return sum
end

-- part 1
local result1 = 0
-- part 2
local total = totalSize(dirs[1])
local unused = 70000000 - total
local needed = 30000000 - unused
local minGreaterThanNeeded = total

for i, d in ipairs(dirs) do
  local size = totalSize(d)
  -- part 1
  if size <= 100000 then
    result1 = result1 + size
  end
  -- part 2
  if size >= needed and size < minGreaterThanNeeded then
    minGreaterThanNeeded = size
  end
end

print("part 1", result1)
print("part 2", minGreaterThanNeeded)

lessons

at first i was afraid about the traversal of the directory tree, and also about its data struture. then i realized it wouldn't be as difficult because of, as i said above, the way tables and variables work in lua.

i was able to have a normal list of directories, where each of them was a table containing a corresponding children table that could include “pointers” to some of the directories in the main list. in other languages i guess i could have managed using the directory names, their paths, or some other way of identifying each of them. here i was able to use the same variable.

this advantage extended to the use of the stack for the traversal of the directories when following the input. first i was thinking in having a stack of directory names or some kind of id, so that i was able to look back and find them in the directory list. then i realized i could just use the same variables pointing to the directories.

in summary, any “directory” table (including name, local size, and children) was in the directory list/table, could be present in the children table/list of another one, could be present in the traversal stack for the instructions, and could be assigned to the wd (working directory) variable. all of them as references to the same table!

regarding recursion for the totalSize, at first i also thought it was going to be more difficult, but i mananged alright. probably there are better ways of doing it, especially because right now i'm being “naive” and i'm calculating the total sizes of directories more than once. i'll leave that problem for puzzles further along. (i didn't, see below)

today i needed a little bit less than 59 minutes for part 1, and i was done in a total of 66 minutes. interestingly, this is my third best ranked performance so far, after 01 (second) and 02 (first). it was intense! but as always, it's rewarding to see that i could implement this in a relatively short time.

update

i realized i could use the same, foretold directory tables to hold the value of their total size whenever it's calculated.

the changes are minimal and only happen in the totalSize function:

function totalSize( dir )
  if dir.totalsize then return dir.totalsize end
  local sum = dir.localsize
  for i, d in ipairs( dir.children ) do
    sum = sum + totalSize( d )
  end
  dir.totalsize = sum
  return sum
end

technically, and for clarity (?), i could have added a totalsize=nil in the createDir function. however, setting it to nil is the same as not setting it, so that's why i preferred to modify the totalSize function only.

back to top

08 treetop tree house

Day 8: Treetop Tree House

08 lua

this was intense! i went through several iterations. first i thought i'd use some recursive stuff like yesterday, only checking for the visibility of adjacent trees, but then i saw my approach wasn't alright: there could be a new, visible tree, next to a non-visible one.

part of me sees this code and wants to optimize it. however, i'm glad that with the approach i used at the end, integrating the solution for part 2 was almost straightforward.

here's the program!

io.input("input")

function addTree( r, c, height )
  local visible = nil
  if r==1 or c==1 or r==n or c==n then
    visible = true
  end
  local tree = { h = height, v = visible, s = 1 }
  trees[r][c] = tree
  return tree
end

trees = {}
n = 0
local row = 1
for line in io.lines() do
  n = #line
  local col = 1
  trees[row] = {}
  for height in string.gmatch(line, "%d") do
    local tree = addTree( row, col, height )
    if row>1 and col>1 then
      -- ABOVE
      local allLess = true
      local s = 0
      for r=row-1,1,-1 do
        s = s+1
        if trees[r][col].h >= tree.h then
          allLess = false
          break
        end
      end
      if allLess then tree.v = true end
      tree.s = s*tree.s

      -- LEFT
      allLess = true
      s = 0
      for c=col-1,1,-1 do
        s = s + 1
        if trees[row][c].h >= tree.h then
          allLess = false
          break
        end
      end
      if allLess then tree.v = true end
      tree.s = s*tree.s
    end
    col = col + 1
  end
  row = row + 1
end

-- second pass, other direction
for row = n-1, 2, -1 do
  for col = n-1, 2, -1 do
    local tree = trees[row][col]
    -- BELOW
    local allLess = true
    local s = 0
    for r=row+1,n do
      s = s + 1
      if trees[r][col].h >= tree.h then
        allLess = false
        break
      end
    end
    if allLess then tree.v = true end
    tree.s = tree.s*s

    -- RIGHT
    allLess = true
    s = 0
    for c=col+1,n do
      s = s + 1
      if trees[row][c].h >= tree.h then
        allLess = false
        break
      end
    end
    if allLess then tree.v = true end
    tree.s = tree.s*s

  end
end

local sum = 0
local maxscore = 0
for i, row in ipairs(trees) do
  for j, tree in ipairs(row) do
 -- part 1
    if tree.v then sum = sum + 1 end
 -- part 2
    if tree.s > maxscore and i>1 and i<n and j>1 and j<n then 
      maxscore = tree.s 
    end
  end
end

print("part 1", sum )
print("part 2", maxscore )

lessons

again, i see those loops and part of me wants to abstract them away. “a lot of repeated code”. it's alright!

i guess there could be more clever ways of going about this; i might think about them later today. maybe it's possible to store the maximum height in each direction, row and column? makes sense, but also i see some problems. at some point, once i had the answers, i thought it could be possible to not use the table for counting visible trees, and just counting them on-the-fly, but i saw that there were some trees being counted twice.

i guess what i did today was alright? at least i'm using the first pass through the data as a way to check for the conditions in two directions already.

today i needed a little bit more than 51 minutes for the first part, and i was done in a total of 61. my rank for the second part is way lower than for the first one; i guess that, by not “optimizing” (by not knowing strategies for it?) for the first part i left myself a nice structure for adding the second solution.

feeling a little bit sleepy; and it's cold and raining outside. i feel calm, and alright. i'm happy i'm using and learning lua.

back to top

09 rope bridge

Day 9: Rope Bridge

09 lua

this was fun!

the following is the code i used to solve part 2 of the puzzle, adapted back to give the answer of part 1 as well.

io.input("input")

function pos2index( pos )
  return pos.x*10000 + pos.y
end

function constrain( n, min, max )
  -- returns converted n, and if it was converted
  local min = min or -1
  local max = max or 1
  if n < min then return min, true
  elseif n > max then return max, true
  else return n, false
  end
end

local head = { x=1, y=1 }
local n = 9
local tail = {}
for i=1,n do tail[i] = { x=1, y=1 } end
local visitedP1 = { [pos2index(tail[1])] = true }
local resultP1 = 1
local visitedP2 = { [pos2index(tail[n])] = true }
local resultP2 = 1

for line in io.lines() do
  local dir, q = string.match(line, "^(%a) (%d+)$")
  q = tonumber(q)
  for step = 1,q do
    if dir == "R" then
      head.x = head.x + 1
    elseif dir == "L" then
      head.x = head.x - 1
    elseif dir == "U" then
      head.y = head.y + 1
    elseif dir == "D" then
      head.y = head.y - 1
    end

    -- loop through tails
    for i=1,n do
      local h = head
      if i>1 then h = tail[i-1] end
      local t = tail[i]
      local dif = { x=h.x-t.x, y=h.y-t.y }
      -- gx, gy indicate if the abs diff was greater than 1
      local dx, gx = constrain(dif.x) 
      local dy, gy = constrain(dif.y) 
      if dif.x == 0 and gy then -- vertical
        t.y = t.y + dy
      elseif dif.y == 0 and gx then -- horizontal
        t.x = t.x + dx
      elseif gx or gy then -- diagonal further away
        t.y = t.y + dy
        t.x = t.x + dx
      end
    end

    -- part 1
    local index = pos2index(tail[1])
    if not visitedP1[index] then
      visitedP1[index] = true
      resultP1 = resultP1 + 1
    end
    -- part 2
    local index = pos2index(tail[n])
    if not visitedP2[index] then
      visitedP2[index] = true
      resultP2 = resultP2 + 1
    end
  end
end
print("part 1", resultP1)
print("part 2", resultP2)

originally i wasn't accumulating the result during the main loop, and i was assigning the visited list without the conditional. in that version, i counted the final result using pairs, as follows:

local result = 0
for k, v in pairs(visitedP1) do
  result = result + 1
end
print("part 1", result)

lessons

this was my first time using a function with multiple results! it was nice because it allowed me to simplify my code a little bit; before adding that feature i was using some math.abs to figure out (again) if the absolute difference had been greater than 1.

also, i liked saving the visited list using a distinct index for each coordinate pair. at first i thought i would use strings as keys, but then i decided it would be worth trying using arithmetic. it was nice to know that in principle i would be able to use that system regardless of where the rope was going.

in part 1 i was not using an array for the tail, but i was doing mostly the same thing as what can be seen in the current code. when i saw that in part 2 i had to extrapolate with more tails, i knew it was going to be relatively easy with the system i had in place.

interestingly, this kind of shows in my personal stats: i was done with part 1 in almost 39 minutes (rank 5604), and i was done with everything in 48. my total ranking was the best so far, 3146; before it was 5024 for day 02. i don't want to focus too much on these numbers, but i like them because they might give me some insight on how “good” or not was my approach.

back to top

10 cathode-ray tube

Day 10: Cathode-Ray Tube

10 lua

this was some modulo fun! the following is the integrated and cleaned up version of the programs i used to solve the puzzles and get the stars

io.input("input")

-- for part 2
function pixel( cycle, spx )
  local cx = (cycle-1)%40
  local s = (cx == 0) and "\n" or ""
  local ch = (cx>=spx-1) and (cx<=spx+1) and "#" or "."
  return s .. ch
end

local cycle = 1
local x = 1
local strengths = 0 -- part 1
local screen = "" -- part 2

-- process
for line in io.lines() do
  local ins, num = string.match(line, "^(%a+) (-?%d+)$")
  -- part 1
  local period = (cycle-20)%40
  if period == 0 then
    strengths = strengths + cycle*x
  elseif num and period == 39 then
    strengths = strengths + (cycle+1)*x
  end  
  -- part 2
  screen = screen .. pixel(cycle, x)

  if num then -- addx
    screen = screen .. pixel(cycle+1, x)
    cycle = cycle + 1
    x = x + tonumber(num)
  end
  cycle = cycle + 1
end

print("part 1", strengths)
print("part 2",screen)

lessons

the first part was giving me some trouble as i wanted to make sure i covered the case of the relevant cycles being inside an addition instruction. maybe it wasn't needed (at least in my input), but the fact that it was in the example made me cautious about it. it was giving me trouble especially because i felt a little bit slow with my math and starting counts from 1; it's understandable as i was basically waking up!

the second part was super fun and interesting, i wonder how's the creative process behind all these puzzles. i remember last year being delighted about this kind of readable output.

regarding times (?), i finished the first part on 24 minutes and i was done with everything at a little bit more than 39 minutes. this is my second ranked part 2 overall. is it because i'm getting better or because less people are participating, who knows. interestingly, i felt that i took a long time for part 1, and that i was super fast with part 2; the times don't necessarily reflect that.

my result for part 2 surprised me; i thought i had to do more things, including comparing the test input with the given solution, but when i ran it and saw some letters (as i was running it with the given input), i tried them and they were right!

ten days already, wow! feeling good about this process, including giving myself time to write a little bit about each day.

back to top

11 monkey in the middle

Day 11: Monkey in the Middle

11 part 1 lua

ouch, this puzzle as a whole bit me hard. part 1 was seemingly straightforward, but then i couldn't extrapolate it (yet?) for the second part. i didn't expect i'd exceed the integer representation limits on day 11!

documenting my partial solution for the moment!

io.input("input")

local monkeys = {}
local lineIndex = 1
local monkey 
-- parsing 
for line in io.lines() do
  if line=="" then
    lineIndex = 1
    goto continue
  end

  if lineIndex == 1 then
    local newmonkey = { q = {}, targets ={}, count=0 }
    monkey = newmonkey
    table.insert(monkeys, newmonkey)
  elseif lineIndex == 2 then -- starting items
    local q = {}
    for item in string.gmatch(line, "%d+") do
      table.insert( q, tonumber(item) )
    end
    monkey.q = q
  elseif lineIndex == 3 then -- operation
    local sign, value = string.match(line, "([+*]) (.+)$")
    local num = tonumber(value)
    local f
    if sign == "*" then
      f = function (x) local v = num or x 
            return x*v
          end
    else
      f = function (x) local v = num or x 
            return x+v
          end
    end
    monkey.f = f
  elseif lineIndex == 4 then -- divisor
    monkey.divisor = tonumber(string.match(line, "%d+$"))
  elseif lineIndex == 5 then -- targets
    monkey.targets[true] = tonumber(string.match(line, "%d+$"))+1
  elseif lineIndex == 6 then -- targets
    monkey.targets[false] = tonumber(string.match(line, "%d+$"))+1  
  end

  lineIndex = lineIndex + 1
  ::continue::
end

for round = 1,20 do
  for i, monkey in ipairs(monkeys) do
    for _, item in ipairs(monkey.q) do
      local worry = monkey.f(item)//3
      local divisible = worry%monkey.divisor==0
      local target = monkey.targets[divisible]
      table.insert( monkeys[target].q, worry )
      monkey.count = monkey.count + 1
    end
    monkey.q = {} -- empty queue
  end

  -- for debugging
  --[[
  print("round", round)
  for i, monkey in ipairs(monkeys) do
    print("monkey", i-1, monkey.count)
    local oq =""
    for _, item in ipairs(monkey.q) do
      oq = oq .. tostring(item) .. ","
    end
    print(oq)
  end
  ]]
end

table.sort(monkeys, function(a,b) return a.count > b.count end)
print("part 1", monkeys[1].count*monkeys[2].count)

lessons (so far)

i enjoyed storing the operations that each monkey does as functions/closures! when i saw the problem i remember reading about it and then, looking back at the book, i liked the approach a lot.

additionally, using boolean values as keys in the targets table was very interesting; i didn't expect it to be possible but i liked it for this case.

i also find interesting that i used a label and a goto to emulate a “continue” present in other languages (skip to the next iteration of the loop).

i managed to use table.sort correctly at the first try, that was nice!

i'll take a break for now.

part 2

ok, i asked for some help and i was able to do it!

for a little bit of background, i tried and thought about several ways of simplifying the numbers while attempting to keep the same behavior.

i thought that if all the operations were multiplications that would have been easy, as one could represent the numbers as a series of factors, and that would be it: when multiplying for an already existing factor, i wouldn't add it to the series. for the case of squaring the numbering, i wouldn't add anything. all of this thinking that all the time the checks were divisions, and also noting that the divisors were always prime numbers. actually, i thought of making a list of all the divisors and work something out from there. however, the big problem here is that there were also additions, therefore this approach wouldn't work.

i tried to figure out if there would be a way of doing something similar but including the additions. maybe divide when there were multiplications, and keep everything as is when there were additions? i saw that wouldn't work.

i had given up, i asked for help, and there was the answer.

making a list of divisors was a nice first step, but actually what i needed was to find their least common multiple (i.e. multiplying them all as they were all primes) and use it as the “period” where meaningful results would happen, applying the modulo operation.

this would work for the addition as it would just wrap around keeping the property of (in)divisibility intact. additionally, 1) all the divisors are not only primes, but actually the first 8 primes, 2) the initial items were either multiples of these primes, or primes themselves. i find it funny that i don't have the algebraic (?) principles to think about modulo, so i had to made several tests to make sure this would work.

i saw the test answers were right, so there it was!

the following shows how i was getting the divisors (although i didn't use them in the table) and the period, and then how i used it instead of the division over three. everything else stayed the same.

local divisors = {}
local period = 1
for _, monkey in ipairs(monkeys) do
  table.insert( divisors, monkey.divisor )
  period = period * monkey.divisor
end

for round = 1,10000 do
  print("round", round)
  for i, monkey in ipairs(monkeys) do
    for _, item in ipairs(monkey.q) do
      local worry = monkey.f(item)%period
      local divisible = worry%monkey.divisor==0
      local target = monkey.targets[divisible]
      table.insert( monkeys[target].q, worry )
      monkey.count = monkey.count + 1
    end
    monkey.q = {} -- empty queue
  end
end

more lessons

i take with me that it's okay to let the problem rest, and it's also okay to ask for help! i was almost there, but i probably wouldn't have arrived without the extra push.

back to top

12 hill climbing algorithm

Day 12: Hill Climbing Algorithm

12 lua

this took me a while! i'm not good yet with these path traversal algorithms, and arriving at today's solution felt nice. i especially liked how optimal (from my perspective) it ended up being.

io.input("input")

function loc(x, y)
  return { x = x, y = y }
end

local map = { v = {} }

-- parsing
local start, dest
local row = 1
local w, h 
for line in io.lines() do
  if row==1 then w = #line end
  local col = 1
  map[row] = {}
  map.v[row] = {}
  for h in string.gmatch(line,"%a") do
    local height = string.byte(h)
    if h=='S' then 
      height = string.byte('a')
      start = loc( col, row )
    elseif h=='E' then 
      height = string.byte('z')
      dest = loc( col, row ) 
    end
    map[row][col] = height
    map.v[row][col] = false -- visited
    col = col + 1
  end
  row = row + 1
end
map.cols = w
map.rows = row-1

function map:nextMoves( x, y )
  local map = self
  local cur = map[y][x]
  local leftDif = x>1 and not map.v[y][x-1] and cur-map[y][x-1]<=1
  local rightDif = x<map.cols and not map.v[y][x+1] and cur-map[y][x+1]<=1 
  local upDif = y>1 and not map.v[y-1][x] and cur-map[y-1][x]<=1
  local downDif = y<map.rows and not map.v[y+1][x] and cur-map[y+1][x]<=1
  local moves = {}
  if leftDif then table.insert( moves, loc( x-1, y) ) end
  if rightDif then table.insert( moves, loc( x+1, y) ) end
  if upDif then table.insert( moves, loc( x, y-1) ) end
  if downDif then table.insert( moves, loc( x, y+1) ) end
  return moves
end
 
local tocheck =  { loc(dest.x, dest.y) } 
map.v[dest.y][dest.x] = true -- visited

local count = 1
local count2 
repeat
  local checking = {}
  for _, p in ipairs(tocheck) do
    table.insert( checking, p )
  end

  tocheck = {}
  local found = false
  for _, p in ipairs(checking) do
    map.v[p.y][p.x] = true
    local t = map:nextMoves( p.x, p.y )

    for _, move in ipairs(t) do
      -- insert move only if not there already
      local contains = false
      for _, m in ipairs(tocheck) do
        if m.x==move.x and m.y==move.y then
          contains = true
          break
        end
      end

      if not contains then table.insert( tocheck, move ) end

      -- part 1
      if move.x == start.x and move.y == start.y then
        found = true
      end
      -- part2
      if not count2 and map[move.y][move.x]==string.byte('a') then
        count2 = count
      end
    end
  end

  if not found then count = count + 1 end
until found

print("part 1", count)
print("part 2", count2)

lessons

first of all, i want to acknowledge that (thankfully) i remembered a solution by @alderwick@merveilles.town from last year, where, as far as i remember, he started from the end and traversed the path backwards. i'm glad i followed that approach!

i had a little bit of trouble figuring out how to proceed: i felt there was going to be recursion and i'm always a little bit scared about it; or then i didn't know the data structure to use: at some point i felt i needed to create some kind of tree to store each possible path, and i was overwhelmed about how to check the visited points in a per-path basis... fortunately i managed to solve it in a relatively simple way!

i liked my approach. to arrive there, i had to iterate it manually to see how i could eventually generalize it and make it compact. for each point to check (starting from the end), i mark it as visited and i check what are the possible moves, and store them into a list of points to check in the next step. as we are looking for the shortest path, it makes sense to mark these points as visited since the first time they appear — i needed some time to realize and be sure about this, but now it seems obvious. now that i describe this, i feel something like it was the aforementioned approach by alderwick last year.

in my “first” attempt i was being very inefficient and it was apparent when testing with the real input: i had a table where i was storing all the previous moves (each entry of the table was an array of points) and i wasn't checking for duplicates when adding new ones. this approach almost froze my computer because of the amount of memory being used. that made me realize the duplicates issue, and also that i didn't have to store them; the visited (v) table was enough for the purposes of the problem. (i guess i thought i needed to store of all of them so that i could eventually traverse it back, or something like that)

it was nice to find and improve that aspect, and then see the program working fast to arrive to the answer. overall, this was fun!

as an extra, i tried the notation to make the function a part of the map. it wasn't crucial here, but it served as a little practice.

i find interesting that at the end the code ends up looking way less complicated than what i had envisioned when reading the puzzle. we are still around 100 lines of code! and regarding more stats, i finished part 1 in 99 minutes, and the second in almost 104 — part 2 was super easy after following the end-to-start approach!

feeling happy and motivated, ready to start the day!

back to top

13 distress signal

Day 13: Distress Signal

13 lua

today was fun! recursion arrived at last and i felt prepared for it. also, i enjoyed using the affordances of the language to parse the data as lists (tables) almost as is — i had to look it up in the book and i'm glad i'm able to get to learn more and more through this process.

io.input("input")

function compare(left, right)
  local t = { l = type(left), r = type(right) }
  if t.l == "number" and t.r == "number" then
    if left < right then return true
    elseif left > right then return false
    else return nil
    end
  elseif t.l ~= t.r then
    if t.l == "number" then
      return compare( {left}, right )
    else
      return compare( left, {right} )
    end
  elseif t.l and t.r then -- two lists
    local i = 1
    while i <= #left or i <= #right do
      local leftE = left[i]
      local rightE = right[i]
      if not rightE and leftE then
        return false
      elseif not leftE and rightE then
        return true
      end
      local isCorrect = compare(leftE, rightE)
      if isCorrect == nil then
        i = i+1
      else return isCorrect
      end
    end
    return nil
  end
end

local pair = {}
local index = 1
local count = 0
local packets = { }
for line in io.lines() do
  if line == "" then
    pair = {}
    index = index + 1
    goto continue
  end

  -- hehe, convert to lua table and ingest
  local t = line:gsub("%[","{"):gsub("%]","}")
  local s = "return " .. t
  local packet = load(s)()

  if not pair.l then
   pair.l = packet
  else
   pair.r = packet
   local correct = compare( pair.l, pair.r )
   if correct then count = count + index end
  end

  -- for part 2
  table.insert( packets, packet )

  ::continue::
end

print("part 1", count)

-- part 2
table.insert(packets, {{2}})
table.insert(packets, {{6}})
table.sort( packets, compare )
local d1, d2
for i, p in ipairs(packets) do
  local ip = p[1]
  if ip and type(ip)=="table" and #ip == 1 and #p == 1 then
    if ip[1] == 2 then d1 = i
    elseif ip[1] == 6 then d2 = i end
  end
end

print("part 2", d1*d2)

for part 2 i wrote a tableToString function to help me out with debugging. recursion again!

function tableToString(t)
  local s = "{"
  for i, v in ipairs(t) do
    if type(v)=="table" then
     s = s .. tableToString(v)
    else
     s = s .. tostring(v)
    end
    if i<#t then s = s .. "," end
  end
  s = s .. "}"
  return s
end

i needed to see the list of ordered because the input was tricky; or more precisely (?), because at first i was too lax with my conditions to identify the divider packets

lessons

important: if you modify the sample file to test some things for part 1, remember you did it for part 2, otherwise you won't be getting the expected result! haha lost some considerable time due to that.

three nice things from lua that i used today and enjoyed:

1. the load function that parses a string as code (note for the future: related functions are loadfile and dofile). i didn't feel in the mood of manually parsing the lists and this helped me with that. additionally, i hadn't used this tool before so i found it was worth applying the concept, as i had read about it at some point.
2. the table.sort function that uses an order function; i had used it before with simpler comparisons and today i was glad (and surprised!) i could just “plug in” the function i had written for part 1.
3. the type function; it's the first time i use it in my final program and it was crucial to differentiate between lists and numbers.

given that i'm still waking up early to solve these, i have the times i needed for each part. i'll keep sharing them: i finished part 1 in a little bit more than 47 minutes, and i was done in almost 76. after day 1, this is the best ranked part 1 — i guess my parsing approach did help a lot!

i remember last year there was a puzzle like this one but i'm not sure how i parsed and managed the lists in awk back then. it could be worth looking into that and remember; however today i'm glad i used the power of lua. the power of small?

i'm feeling very well equipped with lua. i feel that this year i'll able to finish all the puzzles. at least today i felt comfortable with recursion. let's see what comes next!

back to top

14 regolith reservoir

Day 14: Regolith Reservoir

14 lua

today was intense and fun!

io.input("input")

function string2point( s )
  local x, y = string.match( s, "(%d+),(%d+)" )
  return { x=tonumber(x), y=tonumber(y) }
end

function coord2string( x, y )
  return tostring(x) .. "," .. tostring(y)
end

map = {}
map.min = { x=1000, y=1000 }
map.max = { x=1, y=1 }

function map:updateRange( p )
  local map = self
  if p.x<map.min.x then map.min.x = p.x 
  elseif p.x>map.max.x then map.max.x = p.x 
  end
  if p.y<map.min.y then map.min.y = p.y 
  elseif p.y>map.max.y then map.max.y = p.y 
  end
end

function map:fillWithRock( s1, s2 )
  local map = self
  local p1 = string2point( s1 )
  local p2 = string2point( s2 )

  map:updateRange( p1 )
  map:updateRange( p2 )

  if p1.x == p2.x then 
    local x = p1.x
    local inc = (p1.y > p2.y) and -1 or 1
    for y = p1.y, p2.y, inc do
      local s = coord2string( x, y )
      map[s] = "#"
    end
  elseif p1.y == p2.y then
    local y = p1.y
    local inc = (p1.x > p2.x) and -1 or 1
    for x = p1.x, p2.x, inc do
      local s = coord2string( x, y )
      map[s] = "#"
    end
  end
end

function map:blocked( x, y )
  local map = self
  local s = coord2string( x, y )
  return map[s] or y==map.max.y+2
end

function map:printArea( x1, y1, x2, y2 )
  local map = self
  print( map.min.x, map.min.y, map.max.x, map.max.y)

  for row = y1, y2 do
    local rs = ""
    for col = x1, x2 do
      local cs = coord2string( col, row )
      local symbol = map[cs] or "."
      rs = rs .. symbol
    end
    print( row, rs )
  end
end

-- parse
for line in io.lines() do
  local s1, s2
  local i = 1
  for point in string.gmatch( line, "(%d+,%d+)" ) do
    s2 = point
    if s1 then
      map:fillWithRock( s1, s2 )
    end
    s1 = s2
    i = i + 1
  end
end

local result1, result2
local done = false
local i = 1
while not done do
  local unit = { x=500, y=0 }
  repeat
    local moving = true
    local nexty = unit.y+1

    -- part 1
    if nexty > map.max.y and not result1 then 
      result1 = i - 1
      --done=true
    end

    if not map:blocked( unit.x, nexty ) then
      unit.y = unit.y+1
    elseif not map:blocked( unit.x-1, nexty ) then
      unit.x = unit.x-1
      unit.y = unit.y+1
    elseif not map:blocked( unit.x+1, nexty) then
      unit.x = unit.x+1
      unit.y = unit.y+1
    else
      local s = coord2string( unit.x, unit.y )
      map[s] = "o"
      moving = false

      -- part 2
      if unit.y == 0 then
        result2 = i
        done = true
      end
    end
  until not moving or done
  i = i + 1
end

map:printArea( 490, 0, 503, 11 )

print("part 1", result1)
print("part 2", result2)

lessons

don't forget to convert tonumber! when i decided i was going to use strings as keys for the maps, i was having some problems because at some point i was looping using automatically converted strings to numbers (and therefore, those were floats), and the resulting keys were different than the ones i had used. some keys had a decimal point, and others didn't. i had to look up the issue in the book, and found the following, regarding lua 5.3 formatting floats and integeres in a different way. However, more often than not, this problem indicates a deeper flaw somewhere else, where an integer becomes a float with no good reason. i eventually realized it was because of the lack of the explicit tonumber call.

at first i thought of using a bidimensional list (a table?) for the map because using strings as keys didn't seem as elegant (?), but then it was giving me more problems than not (e.g. what should be it's original size? should i create new rows as they are needed?) so i decided to go with the “simple” way. i made my helper functions to convert back and forth from coordinate pairs to strings, and it worked alright! (except for the aforementioned problem!)

today i spent almost 74 minutes in the first part, and i was done in a little bit more than 86. i did take a couple of breaks, especially after the successful parsing of the map, but i felt time flew! i didn't feel overwhelmed or blocked, and also i didn't find it tedious. it just was that it was a lot to do, everything with its own interesting set of challenges.

back to top

15

Day 15: Beacon Exclusion Zone

15 lua

this was intense! a lot of optimizations went happened, from naively using arrays (as can be seen still in part 1, but it was ”worse&rquo;) to using ranges and join operations in part 2. i tried further optimizing the latter, but i wasn't getting the right answer. so for the moment i'm leaving it as is:

io.input("input")
local targetRow = 2000000
local maxx, maxy = 4000000, 4000000

function abs(x)
  return (x>=0) and x or -x
end

function distance(x1, y1, x2, y2)
  return abs(x1-x2) + abs(y1-y2)
end

function inRange( x, y, row, targetD )
  local startD = abs(row-y)
  local dif = targetD - startD
  if dif<0 then return nil
  else return x-dif, x+dif
  end
end

local count = 0
local positions = {}
local beacons = {} -- beacons in row
local data = {}
for line in io.lines() do
  local nums = {}
  for match in string.gmatch(line, "(-?%d+)") do
    table.insert( nums, tonumber(match) )
  end
  local sx, sy, bx, by = table.unpack(nums)
  local d = distance(sx, sy, bx, by)

  local r1, r2 = inRange(sx, sy, targetRow, d)
 -- print(sx, sy, bx, by, d)
  if r1 then
    for c = r1,r2 do
      positions[c] = true
    end
  end
  if by == targetRow then
    beacons[bx] = true
  end

  -- for part 2
  table.insert(data, {sx, sy, bx, by, d})
end

local result1 = 0
local min, max = math.maxinteger, math.mininteger
for x,v in pairs(positions) do
  if not beacons[x] then
    result1 = result1 + 1
  end
end

print("part 1", result1)


-- part 2

function join( r1, r2 )
  local mini = (r1.i < r2.i ) and r1.i or r2.i
  local maxf = (r1.f > r2.f ) and r1.f or r2.f
  if r2.i <= r1.f+1 and r1.i<=r2.i or r1.i <= r2.f+1 and r2.i <= r1.i then
    return { i = mini, f = maxf }
  else
    return r1, r2
  end
end

local minx, miny = 0, 0
local beaconX, beaconY
for y = miny, maxy do 
  if y%500000==0 then print("#"..tostring(y)) end
  local ranges = {}
  local beacons = {} -- beacons in row
  for _, t in ipairs(data) do
    local sx, sy, bx, by, d = table.unpack(t)
    local ri, rf = inRange(sx, sy, y, d)
    if ri then
      ri = (ri > minx) and ri or minx 
      rf = (rf < maxx) and rf or maxx
      local range = { i=ri, f=rf }
      if #ranges == 0 then
        table.insert( ranges, range )
      else
        local i = 1
        repeat 
          local done
          local r1, r2 = join( ranges[i], range )
          if not r2 then
            ranges[i] = r1 -- joined range
            done = true
          else -- don't intersect, try again
            i = i + 1
            -- unless there are no more
            if i > #ranges then 
              ranges[i] = range
              done = true
            end
          end
        until done
      end

    end
  end

  if #ranges > 1 then
  -- clean up
    local i = 2
    repeat 
      local r1, r2 = join( ranges[i], ranges[i-1] )
      if not r2 then
        ranges[i-1] = r1 -- joined range
        table.remove( ranges, i )
      else -- don't intersect, try again
        i = i + 1
      end
    until i > #ranges
  end

  -- if there are still two ranges, here's the answer
  if #ranges > 1 then
    local r1, r2 = ranges[1], ranges[2]
    local minf = (r1.f>r2.f) and r2.f or r1.f
    beaconX = minf+1
    beaconY = y
  end
    
  if beaconX then break end
end

local result2 = beaconX*4000000 + beaconY
print("part 2", result2)

lessons

this was a nice problem for seeing how a “naive” initial approach wouldn't work for other conditions.

at some point i wanted to implement an iterator, but i decided to try it first with a list and a normal for loop. i'm glad i didn't implement it because that approach was one of the things that changed a lot; however i'm still curious about learning about using those.

in part 1 i spent almost 50 minutes at it was the second best ranked part 1, so far. i was done in 2 hours and 50 minutes; wow! 2 hours in the second part!

i'm still curious about part 2; i'm not super happy about how the ”check and add a new range“ part looks, but whenever i tried to change it to something like the clean up below, i wasn't getting the answer. it might be worth looking whenever i have more available time (!)

feeling happy and motivated to keep going!

back to top

16 proboscidea volcanium

Day 16: Proboscidea Volcanium

not finished yet

back to top

17 pyroclastic flow

Day 17: Pyroclastic Flow

17 lua

wow, this was intense! glad i could finish

this is my somewhat cleaned up code! because of what i did to solve part 2, now one has to change the value of the target variable to choose with part to solve.

io.input("input")
--
--local target = 2022 -- part 1
local target = 1000000000000 -- part 2

local shapes = {
  { w = 4, h = 1, map = { {1, 1, 1, 1} } },
  { w = 3, h = 3, map = { {0, 1, 0}, {1, 1, 1}, {0, 1, 0} } },
  { w = 3, h = 3, map = { {1, 1, 1}, {0, 0, 1}, {0, 0, 1} } },
  { w = 1, h = 4, map = { {1}, {1}, {1}, {1} } },
  { w = 2, h = 2, map = { {1, 1}, {1, 1} } },
}


local f = io.read("a")

local jets = {}
for j in string.gmatch(f,"[<>]") do
  table.insert( jets, j)
end

function emptiness()
  return {0, 0, 0, 0, 0, 0, 0}
end

local tunnel = {}

function tunnel:print()
  for i = #self, 1, -1 do
    local s = ""
    local row = self[i]
    for _, c in ipairs(row) do
      s = s .. (c == 1 and "@" or ( c==2 and "#" or "."))
    end
    print(s)
  end
end

function tunnel:drawShape( shape, shX, shY, color)
  local tunnel = self
  local color = color or 1
  for ly = 1, shape.h  do
    local y = ly + shY - 1
    tunnel[y] = tunnel[y] or emptiness()
    for lx = 1, shape.w do
      local x = lx + shX - 1
      tunnel[y][x] = shape.map[ly][lx]==1 and color or tunnel[y][x]
    end
  end
end

function tunnel:clearShape( shape, shX, shY )
  self:drawShape( shape, shX, shY, 0 )
end

function equals( t1, t2 )
  for i = 1, #t1 do
    if t1[i] ~= t2[i] then return false end
  end
  return true
end

local shI = 1
local jeI = 1
local erasedRows = 0
local iFound, iPeriod

local i = 1
while i <= target do
  local shape = shapes[shI]
  local x = 3 -- left
  local y = #tunnel + 4 -- bottom
  for i = 1, 3 do
    table.insert( tunnel, emptiness() )
  end

  repeat -- moving loop
    tunnel:drawShape( shape, x, y )

    -- jet
    local jet = jets[jeI]   
    local inc = jet=="<" and -1 or 1
    local canMove = false
    if (inc == -1 and x > 1 ) or ( inc == 1 and x + shape.w - 1 < 7) then
      canMove = true
      for lx = 1, shape.w do
        local shX = lx + x - 1
        for ly = 1, shape.h do
          local shY = ly + y - 1
          if tunnel[shY][shX+inc] == 2 and shape.map[ly][lx]==1 then
            canMove = false
          end
        end
      end
    end

    if canMove then
      tunnel:clearShape( shape, x, y )
      x = x + inc
      tunnel:drawShape( shape, x, y )
    end

    jeI = (jeI == #jets) and 1 or (jeI + 1)

    -- down
    canMove = (y > 1)
    if canMove then
      for lx = 1, shape.w do
        local shX = lx + x - 1
        for ly = 1, shape.h do
          local shY = ly + y - 1
          if tunnel[shY-1][shX] == 2 and shape.map[ly][lx]==1 then
            canMove = false
            break
          end
        end
        if not canMove then break end 
      end
    end

    if canMove then
      tunnel:clearShape( shape, x, y )
      y = y - 1
      tunnel:drawShape( shape, x, y )
    end
  until not canMove 
  
  -- stopped shape
  tunnel:drawShape( shape, x, y, 2)

  -- clean tunnel
  repeat
    local emptyRow = true
    local ind = #tunnel
    for _, c in ipairs( tunnel[ind] ) do
      if c > 0 then
        emptyRow = false
        break
      end
    end
    if emptyRow then
      table.remove( tunnel )
    end
  until not emptyRow or #tunnel == 0

  -- check for repetition
  local period
  for size = 10, #tunnel/2 do
    local equal = true
    for j = 1, size do
      local tail = tunnel[ #tunnel - j + 1 ]
      local tail2 = tunnel[ #tunnel - size - j + 1 ]
      if not equals(tail, tail2) then
        equal = false
        break
      end
    end
    if equal then 
      period = size

      for i = 1,period do
        table.remove(tunnel)
      end
      erasedRows = erasedRows + period

      if not iFound then 
        iFound = i 
      elseif not iPeriod then
        iPeriod = i - iFound
        -- jump ahead!
        local remaining = target - i
        local advance = remaining // iPeriod
        local outOfIPeriod = remaining % iPeriod
        erasedRows = erasedRows + advance*period
        i = target - outOfIPeriod
      end
     -- print(i, iFound, period, iPeriod, #tunnel )

      break
    end
  end

  shI = (shI == #shapes) and 1 or (shI + 1)

  i = i + 1
end

print("result ", #tunnel + erasedRows)

lessons

i'm guessing the input was constructed in such a way that there would be repetition in the final sequence; i don't feel i have the mathematical tools to figure that out. i'm still not sure why it happens and why the period is less than the size of the input (oh, now that i write it, i guess there is repetition in the input as well?)

i'm happy i could figure out the math to arrive at the solution once the period was found, especially because it wasn't straightforwad because the amount of shapes doesn't correspond to the amount of growth.

for the first part i needed 2 hours, and i as done in 3:34 hours. funnily enough, this is my best ranked puzzle by far, with a ranking of 2161.

time to go back to day 16?

back to top

18 boiling boulders

Day 18: Boiling Boulders

18 part 1, lua

i took a little bit longer than expected because i was mixing some processes, but i had fun arriving at this solution!

io.input("input")

function s2p( s )
  local nx, ny, nz = string.match(s, "(%d+),(%d+),(%d+)")
  return tonumber(nx), tonumber(ny), tonumber(nz)
end

function p2s( x, y, z )
  return string.format("%d,%d,%d", x, y, z )
end

local cubes = {} 
local potneigh = {}
local ncubes = 0
for line in io.lines() do
  local s = line
  local x, y, z = s2p(s)
  ncubes = ncubes + 1
  cubes[ s ] = true

  local dirs = {}
  table.insert( dirs, p2s( x, y, z+1) )
  table.insert( dirs, p2s( x, y, z-1) )
  table.insert( dirs, p2s( x, y+1, z) )
  table.insert( dirs, p2s( x, y-1, z) )
  table.insert( dirs, p2s( x+1, y, z) )
  table.insert( dirs, p2s( x-1, y, z) )

  for _, d in ipairs(dirs) do
    potneigh[d] = (potneigh[d] or 0) + 1
  end
end

local neigh = 0
for d, sum in pairs(potneigh) do
  if cubes[d] then
    neigh = neigh + sum
  end
end

local result1 = ncubes*6 - neigh1
print("part 1", result1)

for part 2 my initial approach of counting the empty cubes that are neighbors to 6 cubes was wrong. there are probably larger volumes of empty pockets, and for the moment i'm not sure how to find and count them.

lessons

i'm getting used to the “lua-isms” for conditionals in the same line; however sometimes it might be worth to first use a more verbose if to make sure i'm not leaving anything behind.

back to top

20

Day 20

20 lua

thank you @alderwick@merveilles.town for your help and hints for solving this puzzle!

io.input("input")

local key = 1 -- part 1
local key = 811589153 -- part 2

local mixed = {}
local i = 0
for line in io.lines() do
  local num = tonumber(line)*key
  table.insert( mixed, { num = num, pos=i} )
  i = i + 1
end

local n = #mixed

function wrap(x)
  return x%n
end

local pos0 = {}
local it = 1
local nit = 10
local sums = {}

for it = 1,nit do
  for i, d in ipairs(mixed) do
    if d.num == 0 then goto nextnum end

    local ppos = d.num+d.pos
    local inc = 0
    if ppos >= n or ppos <0 then
      inc = ppos//(n-1)
    end
    local newpos = wrap( ppos + inc )

    for j, t in ipairs(mixed) do
      if j==i then goto continue end

      if newpos < d.pos and t.pos>=newpos and t.pos<d.pos then
        t.pos = t.pos + 1
      elseif newpos > d.pos and t.pos<=newpos and t.pos>d.pos then
        t.pos = t.pos - 1
      end

      ::continue::
    end
    
    d.pos = newpos

    ::nextnum::
  end

  -- find position of 0
  for i, d in ipairs(mixed) do
    if d.num == 0 then pos0[it] = d.pos break end
  end
  print(it, "pos0", pos0[it])

  sums[it] = 0
end

for j = 1, nit do
  for i, d in ipairs(mixed) do
    if d.pos == wrap(pos0[j] + 1000) 
      or d.pos == wrap(pos0[j]+2000) 
      or d.pos == wrap(pos0[j]+3000) then
      sums[j] = sums[j] + d.num
    end
  end
end
print("part 1", sums[1])
print("part 2", sums[10])

back to top

21 monkey math

Day 21: Monkey Math

21 lua

back on track! (?)

io.input("input")

local m = {}
for line in io.lines() do
  local pattern = "^(%a+): (.+)$"
  local name, arg = string.match(line, pattern)
  local num = tonumber(arg)
  if num then
    m[name] = function() return num end
  else
    local pattern = "(%a+) ([%+%-%*%/]) (%a+)"
    local a, op, b = string.match(arg, pattern)
    if op == "+" then
      m[name] = function() return m[a]()+m[b]() end
      -- for part 2
      if name == "root" then 
        m["root2"] = function() return m[a]()-m[b]() end
      end
    elseif op == "-" then
      m[name] = function() return m[a]()-m[b]() end
    elseif op == "*" then
      m[name] = function() return m[a]()*m[b]() end
    elseif op == "/" then
      m[name] = function() return m[a]()/m[b]() end
    end
  end
end

local result1 = m["root"]()
print( string.format("part 1: %d", result1) )

-- part 2
local at = 0 
local inc = 10000000000
repeat
  repeat
    m["humn"] = function() return at end
    dif = m["root2"]()
    at = at + inc
  until dif <= 0
  if dif==0 then break end
  at = at - 10*inc
  inc = inc/10
until inc < 1

local result2 = at - inc
print( string.format("part 2: %d", result2))

lessons

i liked i could apply what i learned from the previous monkey math puzzle, plus what i learned from some other tests i did at the moment to make sure i could define a function calling functions that are not defined yet (i could! if that wasn't the case i had a planned workaround). this made the first part surprisingly straightforward!

for the second part i found the result iterating “manually”. once i had it right i modified my code so that the program would replicate the process i was following and would find the answer by itself. interestingly, this is the first time i don't make sure i can find the answer with the example input; actually the program as is doesn't work for it (?)

it feels strange to somewhat brute-force it, but that search seemed more attainable to me than solving it in a more “elegant” way. to review later, symbolic math handling!

this is my best ranked puzzle by far; i finished the first part in a little bit more than 14 minutes and i was done (with the manually-obtained answer) in 42, ranked in 1091 (!).

back to top

23 unstable diffusion

Day 23: Unstable Diffusion

23 lua

this was fun!

io.input("input")

function p2s( x, y )
  return string.format("%d,%d", x, y)
end

function s2p( s )
  local x, y = string.match(s,"(-?%d+),(-?%d+)")
  x = tonumber(x)
  y = tonumber(y)
  return x, y
end

function neighbors(x, y)
  local n = {}
  n.NW = p2s( x-1, y-1)
  n.N = p2s( x, y-1)
  n.NE = p2s( x+1, y-1)
  n.E = p2s( x+1, y )
  n.SE = p2s(x+1, y+1)
  n.S = p2s(x, y+1)
  n.SW = p2s(x-1, y+1)
  n.W = p2s(x-1, y)
  return n
end

local max = {y=0, x=0}
local min = {y=10000, x=10000}
function updateMaxMin( j, i )
  if j>max.x then max.x = j
  elseif j<min.x then min.x = j end
  if i>max.y then max.y = i 
  elseif i<min.y then min.y = i end
end

local nelves = 0
local elves = {}

-- parse map
local i = 1
for line in io.lines() do
  local j = 1
  for c in string.gmatch(line, "%g") do
    if c=="#" then
      elves[ p2s(j,i) ] = true
      updateMaxMin(j, i)
      nelves = nelves + 1
    end
    j = j + 1
  end
  i = i + 1
end


local dirs = {"N", "S", "W", "E"}
local offdirs = 0
local round = 1
local result1
repeat
  -- first half
  local attempts = {} 
  for s, e in pairs(elves) do
    local x, y = s2p(s)

    local alone = true
    local n = neighbors(x,y)
    for k, ns in pairs(n) do
      if elves[ns] then alone = false break end
    end
    if alone then goto continue end

    for i=0,3 do
      local idirs = (i+offdirs)%4 + 1
      local dir = dirs[idirs]
      if dir=="N" and not (elves[n.NW] or elves[n.N] or elves[n.NE]) then
        --print("propose north")
        if attempts[n.N] == nil then
          attempts[n.N] = s
        elseif attempts[n.N] then -- attempt
          attempts[n.N] = false
        end
        break
      elseif dir=="S" and not (elves[n.SW] or elves[n.S] or elves[n.SE]) then
       --print("propose south")
        if attempts[n.S] == nil then
          attempts[n.S] = s
        elseif attempts[n.S] then -- attempt
          attempts[n.S] = false
        end
        break
      elseif dir=="W" and not (elves[n.SW] or elves[n.W] or elves[n.NW]) then
        --print("propose west")
        if attempts[n.W] == nil then
          attempts[n.W] = s
        elseif attempts[n.W] then -- attempt
          attempts[n.W] = false
        end
        break
      elseif dir=="E" and not (elves[n.SE] or elves[n.E] or elves[n.NE]) then
       -- print("propose east")
        if attempts[n.E] == nil then
          attempts[n.E] = s
        elseif attempts[n.E] then -- attempt
          attempts[n.E] = false
        end
        break
      end
    end

    ::continue::
  end

  --second half
  local count = 0
  for k, s in pairs(attempts) do
    if s then 
      elves[s] = nil
      elves[k] = true
      local nx, ny = s2p(k)
      updateMaxMin(nx, ny)
      count = count + 1
    end
  end

  --[[
  print("moved:",count)
  print(min.x, min.y, max.x, max.y)
  --]]

  offdirs = (offdirs==3) and 0 or (offdirs+1)

  if round%100==0 then
    print("round", round)
  end

  if round == 10 then
    result1 = (max.y-min.y+1)*(max.x-min.x+1)-nelves
  end

  if count > 0 then
    round = round + 1
  end
until count == 0

print("part 1", result1)
print("part 2", round)

-- print map:
for y=min.y,max.y do
  local m = ""
  for x=min.x,max.x do
    local s = p2s(x,y)
    m = m .. (elves[s] and "#" or ".")
  end
--  print(m)
end

lessons

for converting the positions to keys i was using some arithmetic, but that failed me when the horizontal coordinates were negative. i went back to the approach of using strings as keys, but i guess there would be other ways of solving it; the back-and-forth from strings to numbers is probably not very efficient.

probably there's a way to simplify the way i check and create the attempted moves. in any case i enjoyed the approach: set the attempted cell to false when someone else had attempted it already.

for this puzzle i spent 102 minutes in part 1, and i was done in 110 (! interesting number from the puzzle)

let's see what comes next in the final days!

back to top

25 full of hot air

Day 25: Full of Hot Air

23 part 1, lua

this was fun!

io.input("input")

function s2d( s )
  local b = #s - 1
  local num = 0
  for i = 1, #s do
    local sub = string.sub( s, i, i )
    local d = tonumber(sub)
    if not d then
      if sub=="-" then d=-1 
      elseif sub=="=" then d=-2 end
    end
    num = num + d*(5^b)
    b = b - 1
  end
  return num
end

function d2s( num )
  local s = ""
  repeat
    local mod = num % 5
    local rest = num // 5
    local dif = mod - 5
    local digit
    if dif >= -2 then
      rest = rest + 1
      if dif == -2 then digit = "="
      elseif dif == -1 then digit = "-" end
    else
      digit = string.format("%d", mod)
    end
    s = digit .. s
    num = rest
  until num == 0
  return s
end

local sum = 0
for line in io.lines() do
  sum = sum + s2d(line)
end

local result1 = d2s(sum)
print("part1:", result1)

i couldn't continue with part 2 because it required me to have all the previous puzzles done, oh well!

lessons

i'm glad i woke up for this one! nice and easy way to end this enjoyable and fun process.

i really like lua now!

back to top