Announcing Code Golf Advent Calendar 2022! (+ Event challenge sandbox)

Question

Following last year's event, we're doing Advent of Code Golf Code Golf Advent Calendar 2022¹! 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.

For this event to run successfully, we need 25 different challenges prepared before December. If you want to write a challenge for this event, please post it as an answer to this post. All 25 challenges are ready, and no more challenges are being accepted. This post will also act as a sandbox dedicated to the event.

Also unlike last year, the challenge writer will get to post the challenge they write. When you post a challenge, please attach the preferred date(s) you want to post it on. For reference, Dec 1st is Thursday, and Christmas is Sunday.

   December 2022    
Su Mo Tu We Th Fr Sa
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

You may also post "sandbox gems" (old abandoned sandbox posts) as event challenges, but please follow the process for ownership transfer:

• If a challenge proposal was not edited or commented on for a month, you can leave a comment that you would like take over the challenge, get it ready for main and post it.
• If the OP does not reply within two weeks, telling you that they still intend to post the challenge themselves, you are free to proceed with the challenge as you see fit.

You're free to discuss about this event in the dedicated chat room too.

Notice for challenge writers. When posting your challenge to main, please follow the rules below:

• The title should be in the form of CGAC2022 Day X: <challenge title>
• The body should start with a notice about this event:

  Part of [**Code Golf Advent Calendar 2022**](https://codegolf.meta.stackexchange.com/questions/25251/announcing-code-golf-advent-calendar-2022-event-challenge-sandbox) event. See the linked meta post for details.
  
  ---
  
  <challenge body>
  

¹ Following Eric Wastl's request to change the event's name to not contain "Advent of Code", we decided the new name in this meta post.

² Each individual challenge may be posted a few hours late if UTC midnight doesn't fit with the challenge writer's schedule.

---

Challenges posted

• CGAC2022 Day 1: Let's build a chocolate pyramid!
• CGAC2022 Day 2: Self-trapping Elf
• CGAC2022 Day 3: \$n\$-dimensional Chocolate Pyramid
• CGAC2022 Day 4: Can Santa fit down the chimney?
• CGAC2022 Day 5: Preparing an advent calendar
• CGAC2022 Day 6: Shuffles with specific "magic number"
• CGAC2022 Day 7: Fen The Wicked
• CGAC2022 Day 8: Fen The Wicked, Part 2
• CGAC2022 Day 9: Playing with bits
• CGAC2022 Day 10: Help Santa sort presents!
• CGAC2022 Day 11: Reduce, Reuse, Regift
• CGAC2022 Day 12: Santa's gift and the laser lock
• CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
• CGAC2022 Day 14: Chimney cleaning
• CGAC2022 Day 15: Chimney cleaning, Part 2
• CGAC2022 Day 16: Playing with bits, Part 2
• CGAC2022 Day 17: Present Heap
• CGAC2022 Day 18: Light all of the candles
• CGAC2022 Day 19: I Made It Out Of Clay
• CGAC2022 Day 20: Reconstruct Santa's Book
• CGAC2022 Day 21: Present stack headache
• CGAC2022 Day 22: Present stack headache, Part 2
• CGAC2022 Day 23: North Pole Railroads
• CGAC2022 Day 24: North Pole Railroads, Part 2

Answer 1

CGAC2022 Day 1: Let's build a chocolate pyramid!

Answer 2

Infinite Santa Queue Rename Sorry

(no preferred date)

Santa is a busy man. This Christmas, he's delivering infinitely many presents to infinitely many people. He has a list of the repeating 2D pattern of Naughty and Nice houses to deliver to, and tasks the elves with coming up with a repeating sequence of items (either Coal or Gifts) to deliver to them.

Your job is to verify, given Santa's naughty-and-nice-list, and the elves' gift-or-coal sequence, whether it is possible for Santa to deliver nonstop.

Specification

You are given Santa's grid as a square pattern of values representing either Naughty or Nice houses. For our examples, we will be using 0 for Naughty and 1 for Nice. You may assume there will always be at least one of each. Example:

1 1 0 1
1 1 0 0
0 0 0 1
0 0 1 1

This pattern tiles the infinite grid of houses:

    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
... 1 1 0 1 1 1 0 1 ...
... 1 1 0 0 1 1 0 0 ...
... 0 0 0 1 0 0 0 1 ...
... 0 0 1 1 0 0 1 1 ...
... 1 1 0 1 1 1 0 1 ...
... 1 1 0 0 1 1 0 0 ...
... 0 0 0 1 0 0 0 1 ...
... 0 0 1 1 0 0 1 1 ...
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .

Similarly, the elves give you a list of items, with values representing either Coal or Gifts. In the examples, we will be using 0s to represent Coal, and 1s to represent Gifts. You may assume there will always be at least one of each. Naughty houses should be delivered Coal, and Nice houses should be delivered Presents. Note that every house may not necessarily receive an item, but each house in Santa's path should be delivered the correct item.

Example:

1 0 1 1 0

This list of items repeats infinitely 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0....

(TODO: put a worked out example of the decision problem here)

decision-problem: Decide whether, with a given infinite list and on a given infinite grid, Santa can follow an orthogonal path on the infinite grid and deliver each item on the list to each house he passes in order.

code-golf: Shortest code in bytes wins!

Test cases

(todo!)

meta:

THIS is a work in progress sorry for quality issues im working on it ive been really busy lately but i wanna participate if possible at all haha !!! ^_^

Answer 3

CGAC2022 Day 2: Self-trapping Elf

Answer 4

Light all of the candles

• Preferred date: (Hanukkah) >= Dec 18

---

It's Hanukkah! Unfortunately, it appears some of the candles in your menorah have been blown out. You've got a lighter on hand, but it doesn't work quite right. Whenever you use your lighter at position k, the candles at positions k-1, k, and k+1 all toggle. Let's see an example. We'll represent our candles as a binary sequence with 1 being the "lit" state.

[1, 1, 1, 1, 0, 1, 1, 1, 1]  initial
[1, 1, 1, 0, 1, 0, 1, 1, 1]  light 4
[1, 1, 0, 1, 0, 0, 1, 1, 1]  light 3
[0, 0, 1, 1, 0, 0, 1, 1, 1]  light 1
[1, 1, 1, 1, 0, 0, 1, 1, 1]  light 0
[1, 1, 1, 1, 1, 1, 0, 1, 1]  light 5
[1, 1, 1, 1, 1, 1, 1, 0, 0]  light 7
[1, 1, 1, 1, 1, 1, 1, 1, 1]  light 8

The challenge

To cover our candelabra bases, we'll be working with any n>0 candles. Given the initial state of the candles as input, you must output a lighter usage sequence which will result in all of the candles being lit. Input and output can be taken in any reasonable form for a sequence. Output can be 0 or 1 indexed, but all numbers must fall within the range of the length (ie. no using the lighter at -1). You may assume that the input is always solvable, and you need only output one valid solution.

Test cases

These examples are zero indexed.

[1, 1, 1, 1, 0, 1, 1, 1, 1] -> [4, 3, 1, 0, 5, 7, 8]
[0, 1, 1, 1, 1, 1, 1, 1, 1] -> [1, 2, 4, 5, 7, 8]
[1, 0, 1, 1, 1, 1, 1, 1, 1] -> [2, 4, 5, 7, 8]
[0, 0, 0, 0, 0, 0, 0, 0, 0] -> [1, 4, 7]
[1, 1, 1, 1, 1, 1, 1, 1, 1] -> []
[1, 1, 1, 0, 1, 1, 1] -> [0, 1, 3, 5, 6]
[0, 1, 1, 1, 1, 1, 1] -> [0, 2, 3, 5, 6]
[1, 1, 1, 1, 1, 1, 1] -> []
[0] -> [0]
[1] -> []

Answer 5

When The Planets Align

(no preferred date) \ Assigned date: December 25th

---

As a Christmas gift, you were given a toy solar system. In this toy, all the orbits are circular and happen in the same plane. Each planet starts at a fixed location, has a fixed circumference orbit, and moves at a fixed speed. You want to figure out, given these variables, at what time all of the planets will align (relative to the star which they orbit).

The challenge

You are given three lists of non-negative integers, which are each \$n>1\$ items long:

• \$R_x\$, indicating the circumference of orbit for planet \$x\$ (will not be zero)
• \$P_x\$, indicating the start position of planet \$x\$ (positions are zero-indexed; you can assume \$P_x < R_x\$ for all \$x\$)
• \$S_x\$, indicating the number of units that planet \$x\$ moves along its orbit

(You may also take these as a collection of 3-tuples \$(R_x, P_x, S_x)\$ or a permutation thereof.)

Starting from \$t=0\$, after each time step, each planet moves \$S_x\$ units around their orbit (i.e. \$P_x \leftarrow (P_x + S_x) \mod P_x\$). Your goal is to find the smallest time \$t\$ where \$P_x\$ of all the planets are the same (i.e. \$t\$ such that \$(P_1 + t * S_1) \mod R_1 = (P_2 + t * S_2) \mod R_2 = \ldots = (P_n + t * S_n) \mod R_n\$). You may assume that such a time exists.

Test cases

\$R\$	\$P\$	\$S\$	\$t\$
\$[1,1]\$	\$[0,0]\$	\$[0,0]\$	\$0\$
\$[100,100]\$	\$[0,99]\$	\$[1,0]\$	\$99\$

(TODO: I haven't verified these test cases with code; I also should add a few more)

Answer 6

CGAC2022 Day 5: Preparing an advent calendar

Answer 7

Reconstruct Santa's Book

Date: Dec 20

Oh no, Santa spilled wine all over his great book. Now most of the letters are illegible. How will Santa now know who is groovy and who is unspeakable?

Challenge

There was once a sequence of words, like this:

groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable

However, most of the letters have gone missing and now it looks like this:

     v   oo   g      unsp        gr   y gro            b   uns

Then squashed together:

voogunspgrygrobuns

Your task is to recover the shortest sequence of words that could reduce to the given damaged string.

Note: The words will never have any overlapping characters. Since the book uses different words in different languages you need to handle different words.

Test Cases

Word A	Word B	Sentence	Result
a	b	ab	ab
ab	cd	abcd	ab cd
ab	cd	abc	ab cd
ab	cd	ac	ab cd
ab	cd	bd	ab cd
ab	cd	bda	ab cd ab
ab	cd	aa	ab ab
ooq	dr	ooqdr	ooq dr
ooq	dr	oooqdr	ooq ooq dr
groovy	unspeakable	voogunspgrygrobuns	groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable

Answer 8

CGAC2022 Day 4: Can Santa fit down the chimney?

Answer 9

CGAC2022 Day 6: Shuffles with specific "magic number"

Answer 10

CGAC2022 Day 10: Help Santa sort presents!

Answer 11

Reduce, Reuse, Regift

code-golf decision-problem origami

Traditionally presents are kept secret in boxes wrapped in paper. Since the ice caps are melting Santa Claus has begun to investigate some ways they might make the whole gift wrapping operation a little more eco-friendly. The first thing they've decided to do is to put all presents in perfectly cubic boxes. This makes things more efficient to process and cuts down on waste. The second thing they are doing is to reuse some of the scrap paper to wrap boxes as opposed to tossing it.

In this challenge you will help Santa make a machine which will identify which pieces of scrap can still be used to wrap gifts. Because of the industrial wrapper cutting machine used scraps will always be connected faces of a square tiling.

For example you might get the following scrap:

   #
####
 #

This scrap can fold around the cube perfectly with no overlap and no empty space. Some scraps might overlap, for example:

 #
#######
#

Can wrap around the cube perfectly, but since there are more than 6 squares there must be overlap. This is fine and this scrap can be used to wrap.

Some scraps can't wrap a cube without leaving some gaps. For example

######

This has 6 squares, but there's no way to fold them which covers all sides of a cube. So this should be sent to the recycling plant.

Some scraps can wrap the cube but require fancy folding techniques. For example:

####
####
####

This can be folded to wrap around a cube, but it requires folds that aren't along the edges of the squares. The wrapping machine just isn't that fancy, so this should be sent to the recycling plant.

Task

For this challenge, take a scrap as input in any reasonable method. Output one of two consistent distinct values. One value should only be output if the scrap can be used as gift wrapping, the other should only be output if the scrap should be sent to the recycling plant.

In order to be eco-friendly Santa is asking you to minimize the size of your source code as measured in bytes. (You've tried to explain that that's not how things work.) So this is code-golf.

Ideas for extensions

Would any of these extensions be fun or worthwhile for the advent event?

1. Take a scrap and cut out as many (non-overlapping) scraps as possible which can be used to wrap presents. Harder
2. Take a scrap and determine if it can wrap a cube with fancy folds. Harder
3. Scraps are made from the triangular tiling but need to wrap octahedral boxes. Harder, more complex input

You might at a glance extension 2 is easier. Just determine if the scrap contains some net right? However the following can be used to wrap a cube and contains no net of the cube:

#######

Answer 12

Momentum Sledding

(Idea from Math Games With Bad Drawings.)

You have a track, marked with a starting point and an ending point. # is snow and . is void.

S###########....
...........#....
######.....#....
######.....#....
######..........
################
################
..............##
..............##
E###############
################
################

You start with velocity \$(0,0)\$. Every frame you tweek your velocity by \$(h,v)\$, where \$h,v\in\{-1,0,1\}\$.

You will calculate the minimum ammount of frames it will take to go from the starting point to the ending point. You cannot travel to the void, but you can travel across void.

Walkthrough of Example

01#2##3#4#5#....
...........6....
######.....#....
######.....7....
######..........
###########8####
############9###
..............##
..............0#
6####5###4#####1
############3#2#
################

It took sisteen frames.

Scoring

code-golf still applies.

Test Cases

Input:

S.....#######E
.#...#........
..#.#.........
...#..........

Output:

7

Input:

S#.#..#...#..#.###E

Output:

7

Input:

S###########....
...........#....
######.....#....
######.....#....
######..........
################
################
..............##
..............##
E###############
################
################

Output:

16

Answer 13

CGAC Day 17: Present Heap

Answer 14

CGAC2022 Day 9: Playing with bits

Answer 15

CGAC2022 Day 21: Present stack headache

Answer 16

Sled Machine

(Idea from Cell Machine.)

You are given a board.

>v.....
.>#O...

And a number, say, 5.

You will simulate the board for that many iterations.

Moving Rules

• > (sleds) moves right, v moves down, < moves left, and ^ moves up. All sleds move at the same time.
• # (snowballs) generally do not move.
• O (rotater) rotate nearby sleds around it, from

>.
O.

to

..
Ov

• . is just empty.

Edge Cases (in order)

(By "X meet Y", I mean "X moves into a cell that contains Y")

• Sled meet sled(s). Then they crash together and form a snowball.
• Sled meet snowball. Then the sled will push the snowball in the same direction.
• Snowball meet snowball. Then they compress to make one snowball.
• Snowball meet sled. Then the sled gets crashed and the snowball is moved.
• Sled meet rotator. Then the sled replaces the rotater.
• Snowball meet rotator. Then the rotator gets pushed.
• Rotator meet sled. Then the rotator is broken into pieces, and makes a snowball.
• Rotator meet snowball. Then the rotator is crashed into the snowball.
• Rotator meet rotator. Then the moving rotator disappears.

Anything travelling off the grid is considered to never exist again.

Scoring

code-golf still applies.

Test Cases

TBD

Answer 17

CGAC2022 Day 3: \$n\$-dimensional Chocolate Pyramid

Answer 18

CGAC2022 Day 7: Fen The Wicked

Answer 19

CGAC2022 Day 8: Fen The Wicked, Part 2

Answer 20

CGAC2022 Day 12: Santa's gift and the laser lock

Answer 21

CGAC2022 Day 13: Santa's gift and the laser lock, Part 2

Answer 22

CGAC2022 Day 14: Chimney cleaning

Answer 23

CGAC2022 Day 19: I Made It Out Of Clay

Answer 24

CGAC2022 Day 22: Present stack headache, Part 2

Answer 25

North Pole Railroads, Part 2

• Preferred date: Dec 23

---

Santa and the Elves are secretly preparing for a new tourist train service, called "North Pole Railroads". The train will travel through various sightseeing spots near the North Pole.

As a part of this project, they want to know how many seats they will need. They already have the list of travels for each passenger (given as "from station X to station Y"), which is thanks to the same magic that lets Santa know which children are nice. Each station is numbered from 1, starting from the North Pole.

The Elves are arguing over how to determine the number of seats. Another option is to have just enough seats to allow all passengers to choose their seats. Note that they will have to consider all possible order of reservations. Two passengers with strictly overlapping travel cannot share a seat (e.g. one is (1, 3) and the other is (2, 4)), but a travel that ends at X is not overlapping with another that starts at X.

Task

Given the list of X, Y pairs that represent the travel of each passenger, output how many seats will be needed for North Pole Railroads.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

(1, 2), (2, 3), (1, 3), (3, 4) -> 3
1---2---3---4
 AAA     DDD
     BBB
 CCCCCCC
Explanation: if A takes seat 1 and B takes seat 2, C needs the third seat

(1, 2), (1, 3), (2, 3), (3, 4) -> 3
Explanation: the order in the input does not matter

(1, 3), (1, 3), (3, 6), (3, 6) -> 2

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 5
Explanation: B's travel overlaps with the other 4, so if ACDE gets to book first,
B will need the 5th seat

Answer 26

CGAC2022 Day 15: Chimney cleaning, Part 2

Answer 27

CGAC2022 Day 16: Playing with bits, Part 2

Answer 28

CGAC2022 Day 23: North Pole Railroads