17
\$\begingroup\$

Originally from caird coinheringaahing's idea, I thought about how we could do it this year with such a short time before December, and I decided to gather some ideas from previous AoC events. (There's an explicit permission from Eric Wastl, the one who runs the AoC event.)

As I found 25 potentially good challenge ideas from previous AoC events (2015-2020), I'm running the Advent of Code Golf (AoCG) this year. On each day between Dec 1st and Dec 25th (inclusive), a new challenge will be posted at UTC midnight. It is a free-for-all and just-have-fun-by-participation event, no leaderboards and no prizes for solving them fast or solving them in the shortest code. But, if the event goes well, I will hand out a few bounties to the most active participants, based on various measures.

For the posting schedule: I expect myself to be unavailable on weekends, and I might have problems on other days too. I'll post the challenges when I can at around UTC midnight, but if a new challenge doesn't go live for an hour, or on weekends, anyone else is free to move that day's challenge to main instead. Please don't post it as Community Wiki though (it causes all answers to be CW too). You can take some extra rep as a bonus for helping me run the event :D

Event challenges


This post serves as the announcement of AoCG 2021, but it is also a public sandbox of challenges that will be used for the event. I will write up the 25 challenges for feedback here. If you have another idea (specifically related to previous AoC problems), feel free to post it; we will refine it together and line up the posting schedule accordingly, in case we have to throw away some existing ideas.

Note to those who are opposed to the AoCG being AoC-G instead of Ao-CG: I don't have any intention to make the event an AoC-G. I simply saw AoC as a good source of challenges to quickly draw ideas from (I'd totally agree with using sandbox gems if we had much more time than ~2 weeks before December), and the majority of challenges will be quite different from what you see on the AoC.

\$\endgroup\$
0

25 Answers 25

4
\$\begingroup\$

AoCG2021 Day 1: Automated delivery frenzy

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can we instead output the total number of santas? \$\endgroup\$
    – emanresu A
    Nov 19 at 8:52
  • 1
    \$\begingroup\$ It's worth mentioning that each instruction moves them exactly 1 square, since I was confused by that at first. \$\endgroup\$
    – Grain Ghost Mod
    Nov 19 at 13:56
  • \$\begingroup\$ I can has more test cases? \$\endgroup\$
    – alephalpha
    Nov 23 at 1:29
  • 1
    \$\begingroup\$ Problem changed to total number of santas. Added a mention of moving to "neighboring house". Test cases added. \$\endgroup\$
    – Bubbler
    Nov 23 at 2:16
4
\$\begingroup\$

AoCG2021 Day 4: Infinite Elves and infinite houses 2

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2015 Day 20, Part 1.


To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.

Each Elf is assigned a number, too, and delivers presents to houses based on that number. Instead of giving out presents at fixed intervals, Santa decides to give them out in longer and longer intervals because apparently he's short of supplies right now. Ignore the fact that the total number of presents delivered is the same after all :P

  • The first Elf (number 1) delivers presents to the houses numbered 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5, ... (1, 3, 6, 10, 15, ...)
  • The second Elf (number 2) delivers presents to the houses numbered 2, 2+3, 2+3+4, 2+3+4+5, 2+3+4+5+6, ... (2, 5, 9, 14, 20, ...)
  • Elf number 3 delivers presents to houses 3, 3+4, 3+4+5, ... (3, 7, 12, 18, 25, ...)
  • ...

There are infinitely many Elves, numbered starting with 1. Each Elf delivers exactly 1 present at each house.

So, the first nine houses on the street end up like this:

  • House 1 gets 1 present (by Elf 1).
  • House 2 gets 1 present (by Elf 2).
  • House 3 gets 2 presents (by Elves 1 and 3).
  • House 4 gets 1 present (by Elf 4).
  • House 5 gets 2 presents (by Elves 2 and 5).
  • House 6 gets 2 presents (by Elves 1 and 6).
  • House 7 gets 2 presents (by Elves 3 and 7).
  • House 8 gets 1 present (by Elf 8).
  • House 9 gets 3 presents (by Elves 2 (2+3+4), 4 (4+5), and 9).

So the lowest-numbered house that gets at least 3 presents is House 9.

Given a positive number n, what is the lowest house number that will get at least n presents?

Standard rules apply. The shortest code in bytes wins.

Test cases

n -> answer
1 -> 1
2 -> 3
3 -> 9
4 -> 15
5 -> 45
6 -> 45
7 -> 105
8 -> 105
9 -> 225
10 -> 315
12 -> 315
17 -> 1575
25 -> 10395
\$\endgroup\$
2
\$\begingroup\$

AoCG2021 Day 14: Adjusting dancing program's period

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 16. I'm using the wording from my puzzle based on the same AoC challenge instead of the original AoC one for clarity.


\$n\$ people numbered \$1, 2, \cdots, n\$ are standing in line in the order of their corresponding numbers. They "dance", or swap places, according to some predefined instructions. There are two kinds of instructions called Exchange and Partner:

  • Exchange(m,n): The two people standing at m-th and n-th positions swap places.
  • Partner(x,y): The two people numbered x and y swap places.

For example, if there are only five people 12345 and they are given instructions E(2,3) and P(3,5) in order, the following happens:

  • E(2,3): The 2nd and 3rd people swap places, so the line becomes 13245.
  • P(3,5): The people numbered 3 and 5 swap places, so the line becomes 15243.

Let's define a program as a fixed sequence of such instructions. You can put as many instructions as you want in a program.

Regardless of the length of your program, if the whole program is repeated a sufficient number of times, the line of people will eventually return to the initial state \$1,2,3,\cdots,n\$. Let's define the program's period as the smallest such number (i.e. the smallest positive integer \$m\$ where running the program \$m\$ times resets the line of people to the initial position). The states in the middle of a program are not considered.

For example, a program E(2,3); P(3,5); E(3,4) has the period of 6:

       E(2,3)   P(3,5)   E(3,4)
1. 12345 -> 13245 -> 15243 -> 15423
2. 15423 -> 14523 -> 14325 -> 14235
3. 14235 -> 12435 -> 12453 -> 12543
4. 12543 -> 15243 -> 13245 -> 13425
5. 13425 -> 14325 -> 14523 -> 14253
6. 14253 -> 12453 -> 12435 -> 12345

Now, you want to write a program for \$n\$ people so that it has the period of exactly \$m\$. Is it possible?

Input: The number of people \$n\$ and the target period \$m\$

Output: A value indicating whether it is possible to write such a program or not. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy:

n, m
1, 1
2, 2
3, 6
3, 3
8, 15
8, 120
16, 28
16, 5460

Falsy:

1, 2
2, 3
3, 4
6, 35
6, 60
8, 16
16, 17
\$\endgroup\$
2
\$\begingroup\$

AoCG2021 Day 16: Interpret Duet

Related to AoC2017 Day 18, Part 2. (Anyone want to add Duet to esolangs?)


Duet is an assembly-like language that involves two processes running the same program simultaneously. Each process of Duet operates with 26 registers named a to z, all initialized to zero, except for the register p which contains the process ID (0 or 1).

Individual instructions in Duet are as follows. X is a register, and Y and Z can be a register or a constant.

  • set X Y sets register X to the value of Y.
  • add X Y increases register X by the value of Y.
  • mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.
  • mod X Y sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
  • jgz Y Z jumps with an offset of the value of Z, but only if the value of Y is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)
  • snd Y sends the value of Y to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.
  • rcv X receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.

After each jgz instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program in either process terminates the entire program (i.e. both processes), as well as being stuck in a deadlock (both programs waiting at a rcv instruction).

Duet does not have any I/O facility. The only observable behavior of a program is that either it terminates, or it doesn't.

Both of these programs below should terminate by a deadlock:

snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d
set i 31
set a 1
mul p 17
jgz p p
mul a 2
add i -1
jgz i -2
add a -1
set i 127
set p 680
mul p 8505
mod p a
mul p 129749
add p 12345
mod p a
set b p
mod b 10000
snd b
add i -1
jgz i -9
jgz a 3
rcv b
jgz b -1
set f 0
set i 126
rcv a
rcv b
set p a
mul p -1
add p b
jgz p 4
snd a
set a b
jgz 1 3
snd b
set f 1
add i -1
jgz i -11
snd a
jgz f -16
jgz a -19

Write an interpreter for Duet, which takes a valid source code as input (list of lines is OK), and runs it until the program terminates. Your interpreter should terminate if and only if the input Duet program terminates.

Standard rules apply. The shortest code in bytes wins.

Some examples that halt because one process exits early:

  • Process 0 waits but Process 1 exits early by jumping over the end
mul p 10
jgz p p
rcv x
  • Process 1 loops indefinitely but Process 0 halts by jumping before the start
jgz p 0
jgz 1 -2
  • Process 0 loops indefinitely but Process 1 runs through the program and exits
add p 1
mod p 2
jgz p 0

Some examples that never halt:

  • Both processes run an infinite loop that passes some values around
set a 10
snd 1
snd 2
rcv x
rcv y
jgz a -4
  • Both processes run a tight loop
jgz 1 0
\$\endgroup\$
2
  • \$\begingroup\$ The 34th line in the second example is jgz 1 3. But X should be a register in jgz X Y. \$\endgroup\$
    – alephalpha
    Nov 28 at 12:45
  • 1
    \$\begingroup\$ @alephalpha Changed the description to allow constants in the first argument of jgz. \$\endgroup\$
    – Bubbler
    Nov 29 at 1:02
2
\$\begingroup\$

AoCG2021 Day 17: Langton's Hexa-Virus

The story continues from AoC2017 Day 22, Part 2.


The damn virus that was infecting a grid computing cluster now has jumped to a hexagonal computing cluster! In this cluster, the computers are connected in the honeycomb-like shape, and each computer has three neighbors.

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

Initially, the cluster is completely clean, and the virus is at x, facing east. At each tick, the virus moves in the following manner:

  • If the current computer is clean, infect it, turn left (60 degrees), and move forward once (move to the neighboring computer in that direction).
  • Otherwise (the current computer is infected), clean it, turn right, and move forward once.

Some initial iterations look like this (generated using this program; . is clean, * is infected, x is the virus at a clean computer, and X is the virus at an infected one):

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  x.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  x*  .. 
.  ..  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .x  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  x*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *X  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  .. 
.  ..  x.  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  .. 
.  ..  *x  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  x. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *x  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  X*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  *X  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  x.  .
 ..  *.  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  .x  .. 
.  ..  *.  .
 ..  *.  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

A better visualization can be seen here (pdf).

The number of infected computers at each iteration is A269757:

0, 1, 2, 3, 4, 5, 6, 5, 6, 7,
8, 9, 8, 7, 8, 9, 10, 11, 10, 9,
10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
18, 17, 16, 17, 18, 19, 20, 19, 18, 19,
20, 21, 22, 21, 20, 19, 18, 19, 20, 21,
22, 21, 20, 21, 22, 23, 24, 23, 22, 21,
20, 21, 22, 23, 24, 23, 22, 23, 24, 25, 26, ...

Your task is to output the sequence. Standard rules and I/O methods apply. (0-based and 1-based indexing allowed.) The shortest code in bytes wins.

\$\endgroup\$
2
\$\begingroup\$

AoCG2021 Day 25: Stitching maps together

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 20, Part 1. (This day is a dreaded one for many of you, I know :P)


As the train carries you to the destination, you've got some spare time. You open the travel booklet for the vacation spot, and its map is divided into nine pieces... in random order and orientation. Apparently you got a brain teaser version of the booklet or something.

The map pieces are represented as a square grid of zeros and ones, and they are rotated and/or flipped in a random orientation. The four edges of each map piece are the clues: if two pieces have a common edge pattern (one of the four sides), two pieces are stitched together on that edge.

If two pieces look like this:

Piece 1:
#..##
##...
#.#.#
.#.##
....#

Piece 2:
#.###
.....
.#...
##..#
.##..

The right edge of Piece 1 and the top edge of Piece 2 match; you can flip Piece 2 with respect to its main diagonal, and then join the two horizontally.

You can't decide the orientation of the whole map yet, but at least you can assemble the 3x3 map and tell which piece goes to the center. This is the objective of this challenge.

The edge patterns are all distinct; for any given pattern that appears in the input, there are either exactly two pieces (for interior edges) or one (for outer edges) with that pattern. Also, every interior edge pattern is asymmetric, so that you can uniquely join the edges together (modulo orientation as a whole).

Input: A list of nine square grids of zeros and ones, representing the nine map pieces; you can choose any other two distinct values (numbers, chars, or strings) for zeros and ones.

Output: The square grid that corresponds to the center piece (any orientation is fine), or its index (0- or 1-based) in the input.

Standard rules apply. The shortest code in bytes wins.

Test case

Uses #s and .s.

Input:
.###.#
#####.
..#..#
#..##.
.#.###
..####

#...#.
#..#..
.#.#..
.###..
#....#
...#.#

.##...
#..#..
..####
##...#
##.###
#.....

..#.##
#.....
#.##.#
###.##
#....#
#...##

#.#..#
##.#.#
#...#.
#.###.
..#.#.
.##..#

..##.#
#....#
....##
.#.###
.#...#
#.#.#.

....##
##.#.#
.#.###
.#....
.###.#
.#.###

.#....
..#.#.
##....
######
.#..#.
#..##.

..#...
....##
###..#
.#.#..
#####.
.#.##.

Answer: 2nd-to-last piece (8th with 1-indexing)
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Not this again... \$\endgroup\$
    – emanresu A
    yesterday
2
\$\begingroup\$

AoCG2021 Day 15: Leapfrog Santa

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2015 Day 3, Part 2.


Santa is delivering presents to an infinite two-dimensional grid of houses each 1 unit apart. The delivery begins delivering a present to the house at an arbitrary starting location, and then moving along a predetermined path delivering a new present at every step of the path. The path is a list of moves made of characters:

  • ^ north
  • v south
  • > east
  • < west

At each step Santa reads the instruction and starts heading in that direction until a house which hasn't had a present delivered yet is reached. At that point a present is delivered to that house and the next instruction starts.

Task

Given a string representing directions output the total length of the path that Santa will take.

This is so answers will be scored in bytes.

Test cases

v^v^v^v^: 36
^>v<^>v : 10 
>>>>>><<<<<<< : 19
>>>vvv<<< : 9
\$\endgroup\$
0
2
\$\begingroup\$

AoCG2021 Day 2: Naughty or nice?

\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 3: Say-Look-Say

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2015 Day 10.


The Elves are playing a variation of the game called look-and-say. In plain look-and-say, they take turns making sequences by reading aloud the previous sequence and using that reading as the next sequence. For example, 211 is read as "one two, two ones", which becomes 1221 (1 2, 2 1s).

But this time it's somewhat different. Given a sequence written on a piece of paper, an Elf reads the sequence, and for each chunk of digits, he writes the count on the left side and the digit on the right side. And the next Elf does the same on the entire sequence of digits!

For example, if the current sequence is 211333:

Original sequence    : 211333
Read 2 (one two)     : 1(211333)2
Read 1 (two ones)    : 21(211333)21
Read 3 (three threes): 321(211333)213

So the next sequence would be 321211333213.

If the Elves start with the single digit of 1, what will the sequence look like on the paper after n turns?

Input: The non-negative integer n. (Or a positive integer, if you choose to treat 1 as the 1st iteration.)

Output: The resulting list of digits. Can be in any acceptable format, such as a list of numbers or a single string. Be sure to handle multi-digit numbers that appear since iteration 7.

The sequence goes on like this:

1
111
31111
413111131
114111413111131413131
111111114111312114111413111131413131141413131413131
1111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131
11111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131
11111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411112111313111311121113131113111317113133180111111111111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111111211111111111112111111141113121113181113111317114121113131113111317113134111111111111111111111111111111111121111111111111211111114111312111318111311131711411111111111111211111114111312111318111111114111312114111413111131413131141413131413131141312141413131413131414131314131311214131213181413121414131314131314141313141313141312141413131413131414131314131311212141312131813131714121413121318141312141413131413131414131314131314131214141313141313141413131413131214131213181413121414131314131314141313141313141312141413131413131414131314131311212121413121318131317141213131313171313412121413121318131317141214131213181413121414131314131314141313141313141312141413131413131414131314131312141312131814131214141313141313141413131413131413121414131314131314141313141313121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
1
\$\begingroup\$

AoCG Day 5: Balancing sleigh with lots of trunks

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2015 Day 24, Part 2.


To recap: Santa gives you the list of gift packages' weights. The packages must be split into multiple groups so that each group has the same weight, so that the sleigh is balanced and Santa can defy physics to deliver the presents.

Also, one of the groups goes to the passenger compartment, and Santa wants to have the maximal legroom, so the number of packages in there must be minimal. If there are ties, choose the one with the minimal "quantum entanglement" - the product of all weights in that group - to minimize the risk of physics doing its job, so to speak.

If you were to divide [1, 2, 3, 4, 5, 7, 8, 9, 10, 11] into three groups of equal weight, the possible choices are (QE stands for Quantum Entanglement):

Group 1;             Group 2; Group 3
11 9       (QE= 99); 10 8 2;  7 5 4 3 1
10 9 1     (QE= 90); 11 7 2;  8 5 4 3
10 8 2     (QE=160); 11 9;    7 5 4 3 1
10 7 3     (QE=210); 11 9;    8 5 4 2 1
10 5 4 1   (QE=200); 11 9;    8 7 3 2
10 5 3 2   (QE=300); 11 9;    8 7 4 1
10 4 3 2 1 (QE=240); 11 9;    8 7 5
9 8 3      (QE=216); 11 7 2;  10 5 4 1
9 7 4      (QE=252); 11 8 1;  10 5 3 2
9 5 4 2    (QE=360); 11 8 1;  10 7 3
8 7 5      (QE=280); 11 9;    10 4 3 2 1
8 5 4 3    (QE=480); 11 9;    10 7 2 1
7 5 4 3 1  (QE=420); 11 9;    10 8 2

Since [11, 9] has the smallest number of packages, you should choose that one.

It turns out that Santa's sleigh is a pretty advanced model and has a bunch of trunks instead of one. Under the same conditions, determine which presents should go into the passenger compartment.

Input: The total number of groups n, and the list of packages' weights. n is at least 3, and it is guaranteed that the list of weights can be split into n groups of equal weight.

Output: The optimal list of packages to be placed in the passenger compartment. The individual packages may be output in any order. If there are multiple optimal solutions (same number of packages and same quantum entanglement), output any one of them.

Standard rules apply. The shortest code in bytes wins.

Test cases

Weights, Groups -> Answer
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 3 -> [11, 9]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 4 -> [11, 4]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 5 -> [11, 1]
[1, 1, 2, 2, 6, 6, 6, 6, 9], 3 -> [1, 6, 6] or [2, 2, 9]
[1, 2, 2, 3, 3, 3, 4, 6, 6, 9], 3 -> [4, 9]
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 6: Taxicab in a triangular city

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2016 Day 1, Part 1.


You're airdropped near Easter Bunny Headquarters in a city somewhere. "Near", unfortunately, is as close as you can get - the instructions on the Easter Bunny Recruiting Document the Elves intercepted start here, and nobody had time to work them out further.

The Document indicates that you should start at the given coordinates (where you just landed) and face North East. Then, follow the provided sequence: turn right 60 degrees, then walk forward the given number of blocks, ending at a new intersection.

"What, 60 degrees?" You think, and you look around. Then you realize the city is not quite like what you imagine; the streets in this city form a triangular grid.

Anyway, there's no time to follow such ridiculous instructions on foot, though, so you take a moment and work out the destination. Given that you can only walk on the street grid of the city, how far is the shortest path to the destination?

For example, if the instructions are [1, 1, 0, 2], it means to:

  • Turn right 60 degrees and move 1 block forward
  • Turn right 60 degrees and move 1 block forward
  • Turn right 60 degrees and stay in place
  • Turn right 60 degrees and move 2 blocks forward

In the end, you end up at just 1 block west of the start.

Input: A (possibly empty) list of non-negative integers. If you encounter a 0, it means to turn right 60 degrees but stay in place.

Output: A non-negative integer indicating how far away the destination is from the current position, measured in triangular taxicab distance.

Standard rules apply. The shortest code in bytes wins.

Test cases

[] -> 0
[1, 1, 1] -> 2
[1, 1, 0, 2] -> 1
[1, 2, 0, 0, 0, 2, 1] -> 4
[1, 2, 3, 4] -> 6
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 7: Bathroom security goes wild

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2016 Day 2, Part 2.


You finally figure out the bathroom code (on the weird diamond-shaped keypad) and open the bathroom door. And then you see another door behind it, with yet another keypad design:

You're given a list of UDLR strings. Each string corresponds to one button. You start at the previous button and move to the adjacent button for each instruction, and press whatever button you're on at the end of each string. U means to go up, D down, L left, and R right, respectively. If there's no adjacent button at the given direction, you simply don't move.

Additional clarifications for some diagonal edges: For example, if you're at button 0, both U (up) and R (right) correspond to moving to button 1. The full set of rules are:

0, U or R -> 1
1, L or D -> 0
2, D or R -> 3
3, L or U -> 2
5, U or R -> 4
4, L or D -> 5
7, D or R -> 6
6, L or U -> 7

If the instructions read as ["ULL", "RRDDD", "LURDL", "UUUUD"], the code is as follows:

Start at 0, U: 1, L: 0, L: 0 (nowhere to move) -> 0
Start at 0, R: 1, R: 2, D: 3, D: 4, D: 5 -> 5
Start at 5, L: 6, U: 7, R: 6, D: 6, L: 7 -> 7
Start at 7, U: 0, U: 1, U: 1, U: 1, D: 0 -> 0

So the code is [0, 5, 7, 0].

Standard rules apply. The shortest code in bytes wins.

Test cases

["ULL", "RRDDD", "LURDL", "UUUUD"] -> [0, 5, 7, 0]
["RRRR", "DLLUURR", "LDDRRUU"] -> [3, 2, 3]
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 8: Delivery Corrections

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2015 Day 3, Part 2.


Santa is delivering presents to an infinite two-dimensional grid of houses. The delivery begins delivering a present to the house at an arbitrary starting location, and then moving along a predetermined path delivering a new present at every step of the path. Moves are always exactly one house to the north ^, south v, east >, or west <.

However sometimes the notes giving the path have a few mistakes. Your job is to write a program that figures out how to correct these mistakes. We can't know exactly what mistakes were made but we do know that no house should ever receive more than 1 present. So we will just correct paths so that no house is visited more than once.

To correct a path we substitute a step with a different step. For example >^<v can be corrected to >^>v. Since we don't want to over-correct too much we will make the minimal number of corrections we can while reaching the desired result.

Task

Given a string representing directions output the minimal number of corrections required before it visits no house more than once.

This is so answers will be scored in bytes.

Test cases

>>v>>>vvv<<<^<v : 0
>>>>>><<<<<<< : 1
^^>>vv<< : 1
><> : 1
><>< : 2
^<v>^<v> : 2
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 9: Spiral memory stress test

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 3, Part 2.


You come across an experimental new kind of memory stored on an infinite two-dimensional grid.

Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, not including diagonals.

So, the first few squares' values are chosen as follows:

  • Square 1 starts with the value 1.
  • Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
  • Square 3 is the same (diagonal neighbors don't count), so it also stores 1.
  • Square 4 has squares 1 and 3 as neighbors and stores the sum of their values, 2.
  • Square 5 has square 4 as its only neighbor, so it gets the value 2.

Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:

 12   12   10    8    7
 14    2    2    1    7
 17    3    1    1    6
 20    3    4    5    5
 20   23   27--->   ...

What is the first value written that is at least as large as the input (a positive integer)?

Standard rules apply. The shortest code in bytes wins.

Test cases

1 -> 1
2 -> 2
9 -> 10
18 -> 20
50 -> 55
100 -> 111
200 -> 214
500 -> 552
1000 -> 1070
1070 -> 1070
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 10: Memory reallocation routine

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 6.


A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.

In this area, there are n memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.

The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.

For example, if there are initially four banks with [0, 2, 7, 0] memory blocks:

  • The third bank is freed, and starting with the next (fourth) bank, the 7 blocks are cyclically spread out over the memory banks. After one cycle, the result looks like [2, 4, 1, 2]:

     0   2   0   0
                +1
    +1  +1  +1  +1
    +1  +1
    --------------
     2   4   1   2
    
  • In the next cycle, the second bank is freed and redistributed, resulting in [3, 1, 2, 3].

  • In the next cycle, the first bank is freed (when there are ties, the first bank is chosen), giving [0, 2, 3, 4].

  • Next cycles give [1, 3, 4, 1], then [2, 4, 1, 2], where the sequence forms a loop.

Your job is to simulate one cycle of memory reallocation.

Standard rules apply. The shortest code in bytes wins.

Test cases

[0, 2, 7, 0] -> [2, 4, 1, 2] -> [3, 1, 2, 3] -> [0, 2, 3, 4]
-> [1, 3, 4, 1] -> [2, 4, 1, 2]
[3, 1, 4, 1, 5, 9, 2] -> [5, 2, 5, 2, 6, 1, 4]
-> [6, 3, 6, 3, 0, 2, 5] -> [0, 4, 7, 4, 1, 3, 6]
-> [1, 5, 1, 5, 2, 4, 7] -> [2, 6, 2, 6, 3, 5, 1]
-> [3, 0, 3, 7, 4, 6, 2] -> [4, 1, 4, 1, 5, 7, 3]
-> [5, 2, 5, 2, 6, 1, 4]
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 11: Garbageful streams

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 9.


A large stream blocks your path. According to the locals, it's not safe to cross the stream at the moment because it's full of garbage. You look down at the stream; rather than water, you discover that it's a stream of characters.

You sit for a while and record part of the stream (the input). The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas: either another group or garbage. Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. The input represents a single group which itself may or may not contain smaller ones.

Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.

In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

You don't see any characters that deviate from these rules. Outside garbage, you only find well-formed groups, and garbage always terminates according to the rules above.

The following are some example streams with the number of groups they contain:

  • {}, 1 group.
  • {{{}}}, 3 groups.
  • {{},{}}, also 3 groups.
  • {{{},{},{{}}}}, 6 groups.
  • {<{},{},{{}}>}, 1 group (which itself contains garbage).
  • {<a>,<a>,<a>,<a>}, 1 group (containing four pieces of garbage).
  • {{<a>},{<a>},{<a>},{<a>}}, 5 groups.
  • {{<!>},{<!>},{<!>},{<a>}}, 2 groups (since all >s except the last one are cancelled, creating one large garbage).
  • {{<!!>,{<abc>},<!!!>>,{{<{!>}>},<yes<<<no>}},<>}, 5 groups.

Input: A self-contained, well-formed group as a string.

Output: The total number of groups it contains, including itself.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ The outmost group in the last example is not closed. The first { does not have a corresponding }. \$\endgroup\$
    – alephalpha
    Nov 26 at 2:10
  • 1
    \$\begingroup\$ @alephalpha Thanks, fixed. \$\endgroup\$
    – Bubbler
    Nov 26 at 6:46
  • \$\begingroup\$ What is the meaning of the {{!{ at the start of the last test-case? As far as I can tell, the rules should prohibit a ! from being inside a group without being inside garbage. \$\endgroup\$
    – pxeger
    yesterday
  • 1
    \$\begingroup\$ @pxeger Oh, I misread the AoC spec myself and thought ! can cancel anything anywhere. Fixed now. \$\endgroup\$
    – Bubbler
    yesterday
1
\$\begingroup\$

AoCG2021 Day 12: Oct's Fool

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2017 Day 11.


After having rescued a child process lost on a hexagonal infinite grid, you hear someone else screaming for help. You turn around, and unsurprisingly, there is another program looking for its own child process. "Help! He's gotten lost in an infinite octagonal grid!"

Well, it's not all octagonal, obviously. Instead, it's actually a 4-8-8 tiling:

An octagonal tile (X) has eight neighbors, indicated by eight directions (N, NE, E, SE, S, SW, W, NW). A square tile (Y) has only four neighbors in cardinal directions (N, E, S, W).

The program gives you the path taken by the child process. The initial tile is an octagon. You try following the directions one by one, and... something's wrong in the middle. "Look, he can't move diagonally from a square tile, you see?"

Given a sequence of movements, determine if it is valid on the 4-8-8 grid, assuming the initial position of an octagon.

Input: A list of strings entirely consisting of N, NE, E, SE, S, SW, W, NW. Or a single string containing these strings with a single delimiter (space, comma, newline, or any other char that is not one of NESW) in between. (If the input is ["N", "E", "NW", "NE", "E", "SE"] then you can take it as e.g. "N,E,NW,NE,E,SE")

Output: A value indicating whether it is valid or not. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy:

[]
["S"]
["SW"]
["N", "E", "NW", "NE"]
["NE", "SE", "SW", "NW", "N", "E", "S", "W"]

Falsy:

["N", "E", "NW", "NE", "E", "SE"]
["NE", "SE", "N", "E", "S", "SW", "NW", "W"]
["N", "NW"]
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 13: Defrag in action!

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2017 Day 14.


To recap: The disk is a rectangular grid with \$r\$ rows and \$c\$ columns. Each square in the disk is either free (0) or used (1). So far, you have identified the current status of the disk (a 0-1 matrix), and the number of regions in it (a region is a group of used squares that are all adjacent, not including diagonals).

But we didn't actually defrag the disk yet! Since we identified the regions of used squares, let's assume the shape of each region should be kept intact. It makes it hard to compact the used space, but we can at least move each chunk to the left. Let's do it.

More formally, the algorithm would look like this:

  • Identify the regions of used cells in the disk.
  • Loop until there is nothing to move:
    • Select a region that can be moved 1 unit to the left without overlapping with another region.
    • Move it 1 unit to the left. (The regions do not fuse into one even if they adjacent after such a move.)

Input: A rectangular array of zeroes and ones.

Output: A rectangular array of same size, which represents the result of the simple defrag operation.

For example, if the memory looks like this: (# is used, . is free)

##.#.#..
.#.#.#.#   
....#.#.   
#.#.##.#   
.##.#...   
##..#..#   
.#...#..   
##.#.##.

then it has 12 distinct regions

00.1.2..
.0.1.2.3   
....4.5.   
6.7.44.8   
.77.4...   
77..4..9   
.7...a..   
77.b.aa.

which should be defragged in this way:

0012....
.0123...   
...45...   
6.7448..   
.774....   
77.49...   
.7.a....   
77baa...

resulting in the disk state of

####....
.####...   
...##...   
#.####..   
.###....   
##.##...   
.#.#....   
#####...

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 18: Stripping strips

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2018 Day 3.


After a long period of chaos, the Elves have finally agreed on how to cut the fabric. Unfortunately, the next day they have come up with how to utilize the leftovers - make a super long present wrapping strip. Well, if it can shrink Santa, it might be able to shrink presents as well...

The description of the strip is a string of ODCF, which happens to be the first letters of "up down left right" in Elvish (totally not this Elvish). Divide the fabric into a grid of 1cm × 1cm square cells, select a starting cell somewhere in the middle, and then move around according to the description to claim the strip.

So if the string is OOCOFFFDD, you would get this strip, starting at X:

OFFF
CO.D
.O.D
.X..

... Except that the strip the Elves gave to you is self-intersecting, so it simply doesn't work (a 1cm² fabric part doesn't magically become 2cm² - well, it's physics, at least until Santa comes).

Given the string OOCOFFFDDCCCD, the ? is where the strip self-intersects:

OFFF
CO.D
C?CD
DX..

In order to avoid the ? cell becoming a problem, you can take its substring (a contiguous part of the given string) in two ways: OOCOFFFDDC (cutting away the last 3 chars) and COFFFDDCCCD (cutting away the first 2 chars) gives, respectively,

OFFF
CO.D
.OCD
.X..

OFFF
CX.D
CCCD
D...

Among the two and all the other options, the latter of the two above is the longest possible.

Given a nonempty string of ODCF, determine the length of its longest substring out of which you can make a valid (non-self-intersecting) strip. Assume the fabric leftover is large enough to cover any valid substring of the input.

Standard rules apply. The shortest code in bytes wins.

Test cases

C -> 1
ODD -> 2 (DD)
OOCOFFFDD -> 9 (whole input)
OOCOFFFDDCCCD -> 11 (whole input minus first 2)
OOOFFDCCCDFFFDCOOO -> 12 (minus first 3 and last 3)
\$\endgroup\$
1
\$\begingroup\$

AoCG2021 Day 21: Blinking through the forest

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 3.


In the way to vacation, you're traveling through a forest on an airplane. For some biological and geological reasons, the trees in this forest grow only at the exact integer coordinates on a grid, and the entire forest repeats itself infinitely to the right. For example, if the map (input) looks like this (# for trees and . for empty spaces):

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

the forest actually looks like this:

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

Starting at the top-left corner of this forest and moving at a rational slope (e.g. 3/2 represents two units to the right and 3 units down), how many trees will you encounter until you escape the forest through the bottom row?

Input: A rectangular grid representing the map, and a rational number (non-zero, non-infinity) representing the slope of your movement. You can use any two distinct values (numbers/chars) to represent trees and empty spaces respectively. You can take two positive integers for the slope instead of a rational number, and the two numbers are guaranteed to be coprime.

Output: The number of trees you will encounter during the flight.

Standard rules apply. The shortest code in bytes wins.

Test cases

Grid:
.##
#.#
##.
down/right -> trees
1/1 -> 0
99/1 -> 0
2/1 -> 1
2/3 -> 1
1/2 -> 2
1/3 -> 2
1/99 -> 2


Grid: (the one shown at the top)
down/right -> trees
1/1 -> 2
1/3 -> 7
1/5 -> 3
1/7 -> 4
2/1 -> 2
\$\endgroup\$
2
  • \$\begingroup\$ Can we take the rational number as [numerator, denominator]? Can we assume the rational will always be in reduced form? \$\endgroup\$
    – emanresu A
    2 days ago
  • \$\begingroup\$ @emanresuA Yes, as indicated in the last line of the Input. \$\endgroup\$
    – Bubbler
    2 days ago
1
\$\begingroup\$

AoCG2021 Day 22: Hyperbolic rescue

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2017 Day 11.


Crossing the bridge, you've barely reached the other side of the stream when you are overcome with a sense of deja-vu. "Haven't I done this already?" But before you can finish that thought, someone runs up to you, and cries "My child process has gotten lost in an infinite grid! Can you help me?"

Fortunately for them, you have plenty of experience with infinite grids, even hexagonal ones.

Unfortunately for you, this isn't your typical hex grid.

This is is an order-4 hexagonal tiling. In your typical hexagonal tiling three tiles meet at every vertex:

Regular hexagonal tiling

Image by wikipedia user watchduck

The order-4 hexagonal tiling has 4 tiles around every vertex. In terms of geometry this means it's embedded in hyperbolic space.

Order 4 hexagonal tiling

Image by Anton Sherwood

In order to traverse this hyperbolic space and rescue the child you receive a list of instructions. Each instruction consists a number from 0-6, with 0 move to the next tile straight ahead and each successive number meaning to take move to the next tile clockwise from the last. So as an example 3 would be the tile right behind you.

Given this path you want to figure out how far the child is from your current position.

So your task in this challenge is to take a path of instructions as input and output the number of steps in the shortest path to the same

Strategies

There are three ways to simplify paths we can use. The first is to remove backtracks. If you ever see a 3 that's just a step back to where you were the step before. So you can remove the 3 and that step. The one hitch is that when you get back you are facing the opposite direction so you need to flip the instruction after.

So if your sequence is:

..., y, 3, z, ...

It can be rewritten as:

..., y+3+z mod 6, ...

There's one special case if your sequence ends in a 3:

..., x, 3] = ...]

The second method you to take alternative paths around corners. For example in the regular square grid these two paths are the same length:

  B--D      B  D
  |     ==     | 
  A  C      A--C

Since both tilings are order 4 we can actually use a version of this rule.

..., x, 2, y ... = ..., x+1 mod 6, 4, y+1 mod 6, ...

And again there's an edge case when the 2 or 4 is the last step.

..., x, 2] = ..., x+1 mod 6, 4]

Note that these equivalences go both ways.

You can always find the shortest path by applying a combination of these two rules.

Worked examples

[0,0,0,0]

The second move can't be applied and the first one can only be applied backwards. This is the shortest possible path to the destination, so the answer is the number of steps 4.

[2,2,2,2]

We can apply the second rule right of the bat to get [2+1,4,2+1,2] = [3,4,3,2]. Now we can use the first rule with the 3 to get [3,3], and the first rule again gives us []. The answer here is 0 this is a loop.

[2,0,2,0,2,0,2,0]

Ok this is just the last one except we take an extra step forward after each turn. This should just make a bigger version of the same thing right? Nope, hyperbolic space is tricky. We can apply rule 2 a bunch but it never really goes anywhere. This is actually the shortest path to the destination. The answer is 8.

[2,1,2,1,2,1,2,1,2,1,2,1]

This one forms a big hexagon.

[2,1,2,1,2,1,2,1,2,1,2,1]
[2,1,2,1,2,1,2,1,2,2,4,2]
[2,1,2,1,2,1,2,1,3,4,5,2]
[2,1,2,1,2,1,2,2,5,2]
[2,1,2,1,2,1,3,4,0,2]
[2,1,2,1,2,2,0,2]
[2,1,2,1,3,4,1,2]
[2,1,2,2,1,2]
[2,1,3,4,2,2]
[2,2,2,2]
[2,3,4,3]
[2,3]
[]

It's a loop so the answer is 0.

[0,2,1,2]

This isn't a loop but it can be reduced.

[0,2,1,2]
[1,4,2,2]
[1,5,4,3]
[1,5]

There's nothing we can apply to [1,5] so the answer is 2.

Testcases

[0,0,0,0] -> 4
[2,2,2,2] -> 0
[2,0,2,0,2,0,2,0] -> 8
[4,0,4,0,4,0,4,0] -> 8
[2,1,2,1,2,1,2,1,2,1] -> 0
[4,5,4,5,4,5,4,5,4,5] -> 0
[0,2,1,2] -> 2
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your challenge ideas. I decided to discard the remaining three in my list and use all of yours instead. What is your opinion about the challenge order? Is it OK to shuffle the challenges around so that consecutive challenges look less repetitive? \$\endgroup\$
    – Bubbler
    yesterday
  • \$\begingroup\$ @Bubbler Sure. However I still had had one or two more ideas to write up as part 2s, I was thinking I would still have a little bit of time, so I'm not sure when exactly those might get posted. \$\endgroup\$
    – Grain Ghost Mod
    yesterday
  • \$\begingroup\$ If you can write up more challenges, please go ahead. I think it would be better if we can avoid three copies of day 1s for a more interesting one. You can do whatever you want for the leftover(s). \$\endgroup\$
    – Bubbler
    yesterday
1
\$\begingroup\$

AoCG2021 Day 24: Is the bus company cheating?

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 13, Part 2.


A shuttle bus service runs between the sea port (where you are) to the airport (where you need to go). Each bus has an ID number that also indicates how often the bus leaves for the airport - more precisely, the number of minutes between the departure of two consecutive buses of that ID. Every bus departed at the same time some time in the past at the timestamp of zero.

The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute.

The list of bus IDs looks like this:

7,13,x,x,59,x,31,19

where x means "don't care". So the objective here is to find the timestamp t where:

  • Bus 7 departs at t.
  • Bus 13 departs at t+1.
  • Bus 59 departs at t+4.
  • Bus 31 departs at t+6.
  • Bus 19 departs at t+7.

The earliest timestamp t for this list is 1068781.

However, you suspect that the company won't want to give out any gold coins, because sometimes the list looks like this:

7,7

which is obviously impossible - Bus 7 cannot depart at t and t+1 for any t.

Given the list of Bus IDs, determine if you can earn a gold coin or not.

Input: The list of bus IDs, possibly with some holes. A bus ID is always positive. A hole can be represented using any value that is not a positive integer (e.g. 0, -1, "x"). The list is guaranteed to be non-empty.

Output: A value representing the answer. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

The test cases use 0 for the holes in the list.

Truthy:

[7, 13, 0, 0, 59, 0, 31, 19]
[1, 2, 3, 4, 5]
[0]
[999]
[1, 3, 5, 7, 9, 11, 13, 15]

Falsy:

[7, 7]
[3, 1, 4, 1, 5, 9, 2]
[4, 0, 4]
\$\endgroup\$
0
\$\begingroup\$

AoCG2021 Day 19: To Hire or To Fire

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2018 Day 7, Part 2.


As soon as you and a few Elves successfully assemble the Sleigh kit, you spot another set of the same kit not so far away. But you noticed that the last Elf is slacking quite a lot but you had to work from start to end without having any free time at all.

In an attempt to fix this, you decide to take a specific number of Elves to maximize your free time.

This time, you and the Elves learned how to assemble it, so each job numbered n exactly takes n seconds to complete (instead of n + 60 seconds). And, to simplify things, the manual is given simply as a list of pairs of job numbers, each pair (x, y) meaning "job x should be completed before job y can begin". The smallest-numbered worker available (you being number 1 and the Elves being number 2, 3, ...) takes the next available job, smallest number first.

Given the example manual

[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)]

the visual order of the jobs is as follows:

  -->1--->2--
 /    \      \
3      -->4----->5
 \           /
  ---->6-----

If you take 0, 1, or 2 Elves with you (being 1, 2, 3 workers in total), the following will happen respectively:

1 worker:
you   | 333122444466666655555

2 workers:
you   | 333122444455555
elf 1 |    666666

3 workers:
you   | 333122   55555
elf 1 |    666666
elf 2 |     4444

So you get 3 seconds of rest when there are 3 workers, and no time to rest with fewer. Since there is no opportunity to do 4 jobs in parallel, the 3-worker case is the best for you. If multiple choices give the same amount of time to rest, choose the fewest number of workers.

Input: A description of the manual. Assume every job to be done appears in the manual, and the job numbers are consecutive from 1.

Output: The optimal total number of workers.

Standard rules apply. The shortest code in bytes wins.

Test cases

[(2, 1), (3, 2)] -> 1
[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)] -> 3
[(2, 3), (2, 5), (8, 6), (8, 4), (3, 7), (6, 7), (5, 1), (4, 1)] -> 3
+-2-+-3--+--7-+
|   +-5--|+   |
|        ||   |
+-8-+-6--+|   |
    +-4---+-1-+
1 worker:
2-3-5-8-4-1-6-7
2 worker:
22333555556666667777777
8888888844441
3 worker: (same as 4 worker; no way to parallelize [3, 4, 5, 6])
22333...44441.7777777
88888888666666
  55555
\$\endgroup\$
0
\$\begingroup\$

AoC2021 Day 20: Wonky license check

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2018 Day 8.


The license file for an imaginary software system is defined as follows:

  • The entire file is a sequence of non-negative integers.
  • The entire file defines a tree of nodes.
  • Each node in the tree has the following fields in the order:
    • Header, a single number indicating the number of child nodes.
    • Zero or more child nodes, as specified in the header.
    • Zero or more metadata entries (each being a single integer), as specified in the footer.
    • Footer, a single number indicating the number of metadata entries.

Hmm, does it really work? It should, because it is your job to validate the given license file!

An example of a valid license file:

2 0 10 11 12 3 1 0 99 1 2 1 1 1 2 3
A----------------------------------
  B----------- C-----------
                 D-----

A has two children (B, C) and three metadata entries. B has no children and three metadata entries. C has one child and one metadata entry, and so on. It is well-formed, so it is valid.

How about this?

2 1 0 0 1 1 0 0 1 1 0

The root node has 2 children and 0 metadata. Then we need to divide 1 0 0 1 1 0 0 1 1 into two nodes. But:

  • 1 0 0 is not a valid node: it has 1 child and 0 metadata, but single 0 is not a valid node.
  • 1 0 0 1 is not valid either: it has 1 child and 1 metadata, but again we are left with single 0.
  • 1 0 0 1 1 is valid (1 child, 1 metadata, 0 0 being the child), but the rest 0 0 1 1 is not a valid node.
  • 1 0 0 1 1 0 is not a valid node because 0 0 1 1 isn't.
  • The first child cannot be longer than that because the second must have 1 metadata.

Therefore, the second example is not a valid license file.

Given a license file as an array of non-negative integers, determine if it is valid. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy:

[0, 0]
[1, 0, 0, 0]
[0, 99, 99, 99, 3]
[2, 0, 10, 11, 12, 3, 1, 0, 99, 1, 2, 1, 1, 1, 2, 3]

Falsy:

[]
[0]
[0, 1]
[1, 1]
[1, 0, 2, 3, 2]
[3, 0, 1, 0, 0, 1, 0, 0, 1, 2, 3, 2]
[2, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]
\$\endgroup\$
0
\$\begingroup\$

AoCG2021 Day 23: Finding the best seat

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 11, Part 2.


You enter the waiting area for a ferry, and you see a bunch of people sitting at a bunch of seats. The seats form a grid like this (. is a floor, L is an empty seat and # is an occupied seat):

LL.#L
#.L.L
L.L.L
L.L#.
.#L#L

Now, since you value privacy a lot, you try to pick a seat that has the minimum number of people visible from it. A seat is visible from another seat if there is no other seat (empty or occupied; floor doesn't count) exactly on the straight line between the two.

For example (rows and columns are numbered from the top left, starting at 1):

  • R1C1 sees R2C1 (directly below it) and the two occupied seats on R5 (because the slope does not allow any other seat in between) but does not see R1C4 (blocked by R1C2) or R4C4 (blocked by R3C3).
  • R1C2 does not see R5C4 (due to R3C3 at slope 2/1) but sees the other four.
  • R3C1 and R4C3 see all five occupied seats.
  • R4C1 sees only two.

Therefore, R4C1 is the best choice for you, and the anti-privacy (the number of occupied seats you can see) of that seat is 2.

Given a grid like this, calculate the minimum anti-privacy over all empty seats.

Input: A rectangular grid with three distinct values (you can choose which values to use) for floor, empty seat, and occupied seat, respectively. It is guaranteed that the input contains at least one empty seat.

Output: The answer to the problem.

Test cases

L -> 0

LL# -> 0

####
####
####
###L -> 9

.#L.
L..L
#L#L
LL.# -> 3


LL.#L
#.L.L
L.L.L
L.L#.
.#L#L -> 2
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .