bigboy #3
https://files.catbox.moe/klc5b5.7z
or https://0x0.st/KyL1.txt
83984
847316731798752

File: day03emu.webm (182 KB, 628x962)

182 KB WEBM

My input unexpectedly having Windows style line endings threw me off for a little while.

File: day03.png (680 KB, 1481x2770)

680 KB PNG

>>107417344
But of course it was very easy.
I even spent time rewriting my "ascii" number converter.

>>107417344
shit mate you still alive?

>>107417340
[CODE]
$ luajit 3.lua bigboy.txt
Part 1: 83984
0.172s
Part 2: 847316731798752
0.328s
[/CODE]

Interpreted language btw

File: 20251203_194941168.webm (1.33 MB, 853x480)

1.33 MB WEBM

>>107417353
My PS2slim is acting up. Pray for it. (I got it for $10)
>>107417356
Day 2 killed me but I survived.

File: solve.png (476 KB, 4684x3062)

476 KB PNG

idiomatic Rust solution

File: idiomatictrash.jpg (280 KB, 800x1137)

280 KB JPG

>>107417384
Idiotic Rust solution

what do you guys do for work?

>>107417404
I am unemployed

>>107417340
Zig greedy stack sol: P1 87ms, P2 116ms

>>107417404
codemonkey

>>107417404
your mom

>>107417421
nice contrast

>>107417432
Thanks

>>107417323
You faggots are so pathetic.
>spending your time coding for the fun of it and not applying it to something that might make you money or get a better job

File: carbon(1).png (145 KB, 1802x982)

145 KB PNG

So when is it getting harder ?

>>107417444
filtered

>>107417444
>jobbing is the meaning of life
kys

File: 1757909801280872.png (820 KB, 1396x7224)

820 KB PNG

idiomatic js

>>107417365
JIT? flush cache and try again

>>107417444
Why not both?

>>107417444
It is almost like the fun is the point.

>>107417404
I sell potatos

>>107417404
dick around in azure

File: asdfasdgasasdvasd.png (121 KB, 853x731)

121 KB PNG

Trying this in haskell was fun. Technically I could delete the first scan function because scanP2 is the general case, but i left it there for historical reasons

>>107417404
unemployed student

>>107417449
>>107417454
>>107417460
>>107417461
get a fucking job you useless retards

>>107417459
Flushing did not change the timing. But here are the results with jit off.

Part 1: 83984
6.008s
Part 2: 847316731798752
13.14s

>>107417496
Can't you just use `maximum` in lieu of your `findCharHighest`method ?

>>107417509
I do have a job but I also can have fun. Hope you could do that one day.

>>107417518
>Flushing did not change the timing
interesting
show code

>>107417404
swe code monkey. i spend all day sitting in shitty meetings, writing unit tests, writing useless tech documents, and staring at my phone while waiting for a build pipeline to run. i like AOC because it lets me write actually interesting code

>>107417509
Fuck off, Grinch, I want to have my Christmas fun.

>>107417509
filtered

>>107417404
unemployed atm, picked fruit this season.

>>107417509
>waaa you can't do things in your own time unless you're unemployed

>>107417529
you're right, I didn't even know there was that function

>>107417353
>AT&T syntax
yuck, invest in intel

My solution is O(n*(m*12)) so do I reduce that to O(n*m)?

>>107417761
It already is

>>107417391
Post the original

>>107417761
It is literally the same O, retard.

File: day3.png (806 KB, 1756x1696)

806 KB PNG

>>107417496
Here is my haskell solution. I am trying to learn Haskell for fun. I feel like in my ignorance I am doing a lot of things wrong, but it's been a while since last time I wrote anything.

>>107417841
what the FUCK is that font

>>107417847
Right Serif Mono. I usually use Isosevka, but I got bored of it and searched for something fancy.

https://pangrampangram.com/products/right-serif-mono

>>107417841
looks good
I'll learn a functional language one day

>>107417738
It's kinda a mess up of Intel and AT&T.
Destinations are first, immediates don't have a prefix, but registers have a prefix and instructions have a suffix.
I don't really care. Just use whatever the assembler I am using goes for.

File: trash.jpg (150 KB, 800x1137)

150 KB JPG

>>107417780

>>107417592
actually based and same. ai taking over has made it much worse. my brain is almost entirely off all day.

File: 1751954688234683.jpg (594 KB, 2048x1536)

594 KB JPG

>>107417897
Thanks. I'll trade you this one for it.

>>107417878
Thanks anon. It feels strange to write in functional style. First day was a real struggle for me because it was first time of me using Haskell. I was really close to put everything in a do block and write imperatively.

>>107417509
rather jobless than joyless

>>107417404
embedded swe

I managed to find the trick for part 2 making it trivial, but if one hadn't, how would you go about brute forcing it?

I'm guessing some way to run all permutations of selecting 12 from n and then storing the largest? how would you even do that though

>>107417323
>no edition edition

>>107417496
>>107417841
Nice !
Love seeing other anons using Haskell, the language is super rich and looking at others' solutions I alway learn a few ideas for the next days

>>107418123
depends what you mean by brute forcing it

>>107417404
"""data engineer""" (I suck with legacy bs and want to kms)

File: aoc2025day2haskell.png (200 KB, 760x763)

200 KB PNG

Day 2 in Haskell
embarrassing; couldn't even compute the bigboy.
For some reason my original naive solution was faster than what I thought would be a smarter purely-numeric solution...
Were there any smartanons posting suggestions? Could someone link me up?

>>107418123
what's the "trick", anon?

>>107418363
He pulled a rabbit out of his hat.

>>107418363
not anon but
>at each index, what is the index of the closest greater rightward digit?
it is trivial to construct such a table in O(n)
then, if there is a greater rightward digit, you simply check if enough digits follow it
if you need, say, 2 more digits, and the closest greater rightward digit is not the last, then you can safely omit whatever digit you're currently at
implementation here: >>107416288

File: code.png (218 KB, 1402x1128)

218 KB PNG

>>107418317
ive seen some people overcomplicating it with DP or recursion, i just assumed this simple way of doing it is best
dont care to bigboy it

>>107418426
doesn't sound like a trick
have you tried that with bigboy

>>107418440
oy this is day3
im not spoiling myself yet; still at work

File: 3a.png (94 KB, 988x534)

94 KB PNG

I feel like a rare animal this year

>>107418440
looks clean but i don't understand it
>overcomplicating with dp
i think dp is the most straightforward way to do this

>>107418461
no but it's O(n) for each row in both memory and time, and runs eric's input in 0.03s
i don't see why it wouldn't run the bigboy

>>107418478
oops sorry anon didnt notice you said day2

>>107418481
>i don't see why it wouldn't run the bigboy
I'm just curious about how long it'd take

>>107418481
theres no way that dp is more straightforward than what i posted

>>107418485
hehe is oke
good job on d3 =D

Are these getting easier or am I crazy? Only finnicky thing for this one was making sure I skip / take the right amount of elements to compare.

File: aoc2025-03.png (74 KB, 495x575)

74 KB PNG

This seems more complicated than necessary

>>107418491
i'm not at my desktop right now
here's the code if you want to try it

def solve(bat: list, need: int) -> int:
    n = len(bat)
    dp = [[-1] * 10 for _ in range(n)]
    for i in reversed(range(n - 1)):
        for j in range(10):
            ''' recurrence relation for closest greater rightward digit
                      
                       n - i - 2, if j < bat(i+1)
            dp(i,j) = 
                       dp(i+1,j), otherwise
                      
            '''
            dp[i][j] = n - i - 2 if j < bat[i + 1] else dp[i + 1][j]
    sol = 0
    for i in range(n):
        if dp[i][bat[i]] < need - 1 or need and i == n - 1:
            sol = sol*10 + bat[i]
            need -= 1
    return sol

p1 = p2 = 0
for bank in open(0).read().strip().split("\n"):
    bat = list(map(int, bank))
    p1 += solve(bat, 2)
    p2 += solve(bat, 12)
print(f"silver: {p1}, gold: {p2}")

>>107417897
>>107417902
Where do you get these? Do you have more?

>>107418493
if approaching the problem from "is there a bigger digit to the right? are there enough subsequent digits?", any other solution is either slower or computationally equivalent

let d = 12;
let ans: u64 = read_to_string("3.in")
    .unwrap()
    .trim()
    .lines()
    .map(|line| line.as_bytes())
    .map(|line|
        (0..d).fold((0, 0, line.len() - d), |(v, l, r), _| {
            let i = line[l..=r]
                .iter()
                .enumerate()
                .max_by_key(|&(i, v)| (v, Reverse(i)))
                .unwrap()
                .0
                + l;
            (10*v + (line[i] - b'0') as u64, i + 1, r + 1)
        }).0
    )
    .sum();
println!("{ans}");

File: aoc2025day3verbose.png (123 KB, 1085x507)

123 KB PNG

>>107418123
>I managed to find the trick for part 2
I'm not sure what trick you mean desu

Overengineered day 2, made a nice little "get next invalid id" function and refused to change tactics for the second star. Day 3 was a breeze.

>>107418564
ctrl-c'd after four minutes
amd ryzen 7 5800h

>>107418510
>Are these getting easier or am I crazy
This is on par with the first week previous years

>>107418510
i feel the same way, day 1 was the hardest by far

>>107418693
Sorry guys that was bloated

let d = 12;
let ans: u64 = read_to_string("3.in")
    .unwrap()
    .lines()
    .map(|line| {
        let bline = line.as_bytes();
        (0..d).fold((0, 0), |(v, l), step| {
            let r = bline.len() + step - d;
            let i = l + bline[l..=r].max_idx();
            (10*v + (bline[i] - b'0') as u64, i + 1)
        })
        .0
    })
    .sum();
println!("{ans}");

File: brain age.jpg (51 KB, 704x659)

51 KB JPG

Part 1

data = open("Day 03 input.txt", "r").read().strip().split("\n")
total = 0
for line in data:
    nums = [int(i) for i in line]
    num1 = max(nums[:-1])
    num2 = max(nums[nums.index(num1)+1:])
    total += num1*10 + num2

print total

Part 2

data = open("Day 03 input.txt", "r").read().strip().split("\n")
total = 0
for line in data:
    nums = [int(i) for i in line]
    num = 0
    for digit in range(12):
        if digit == 11: best = max(nums) #negative 0 lmao
        else: best = max(nums[:-(11-digit)])
        nums = nums[nums.index(best)+1:]
        num *= 10
        num += best
    total += num

print total

Wasn't up for the release. Unwashed python.
Wasted like 10 minutes chasing issues when I was just stupidly trying to slice with negative 0.

>>107418922
>.max_idx()

File: day 3.png (110 KB, 1440x1007)

110 KB PNG

First time that I solve a DP problem.
Does it have real world applications though?

>>107417444
t. https://www.youtube.com/watch?v=0cgJoo40tEg

>>107418939
>he didn't get invited to the insider Nightly program

I haven't even started for this year. Is it joeveer?

File: day 3_2.png (83 KB, 956x851)

83 KB PNG

>>107418956
upgrades

>>107418858
gut feeling is you're lying but i will check tomorrow
if it runs sub 10 seconds on my processor then i will rape you

>>107419042
It's early days, you can catch up in no time.
Catching up on the threads would take you longer than solving.

fn solve<const N: usize>(arr: &[Vec<u8>]) -> u64 {
    arr.iter()
        .map(|batteries| {
            let mut off = 0;
            let mut ret = [0u8; N];
            ret.iter_mut().enumerate().for_each(|(i, ret)| {
                (off, *ret) = batteries
                    .iter()
                    .enumerate()
                    .skip(off + 1)
                    .take(batteries.len() - off - (N - i))
                    .fold((off + 1, batteries[off]), |(off, b), (idx, batt)| {
                        match b.cmp(batt) {
                            Ordering::Less => (
                                idx + 1, // must offset idx by 1 for next loop itr
                                *batt,
                            ),
                            Ordering::Equal | Ordering::Greater => (off, b),
                        }
                    });
            });
            ret.into_iter().fold(0u64, |acc, n| acc * 10 + n as u64)
        })
        .sum()
}

shrimple as.

File: 1746718364146719.png (94 KB, 735x755)

94 KB PNG

>read on aoc subreddit how people are struggling with day 3 part 2 due to bruteforce taking too long
>they are using caching and hashmaps to "optimize" it
what is even going on? why would someone need to bruteforce this?
it never even occurred to me that I should try all possible combinations

>>107419153
there is so much wrong with this

Part one.

#include <stdio.h>
#define BATTERIES 100
#define BANKS 200

int main(){
    int joltage = 0, bank[BATTERIES+1] = {0};
    for(int i = 0, lIdx = 0, slIdx = 0; i < BANKS; i++, lIdx = 0, slIdx = 0, getchar()){
        for(int j = 0; j < BATTERIES; j++, bank[j] = getchar() - '0') if(bank[j] > bank[lIdx]) lIdx = j;
        for(int j = lIdx+1; j < BATTERIES+1; j++) if(bank[j] > bank[slIdx]) slIdx = j;
        joltage += 10*bank[lIdx] + bank[slIdx];
    }
    printf("%d\n", joltage);
}

>>107419203
why? it does part1 and 2 or arbitrary N and it's O(n*m) where m is the const N.

>>107418481
>i think dp is the most straightforward way to do this

Sliding window > monotonic stack > DP

They're all O(n) time but DP has easily the worst performance in practice. Maybe you have a very special mind and find sliding window more difficult to reason over, but to 99.9% of programmers it's simpler to read and maintain.

>>107418782
Are you seriously using a "typewriter ribbon running out of ink" font?
How much more pretentious can you get?

>>107419240
also sliding window is trivially O(1) space, stack is O(m), naive DP is O(n*m) and rolling DP can only achieve O(m) at best

n = input digits, m = output digits

>>107417674
You a thirdie? Is fruit picking legit? Can you survive the off-season on the money you made? I thought it pays like shit and is like borderline abuse.

>>107419220
wow

File: d03.png (404 KB, 1558x2582)

404 KB PNG

I am learning rust :)

>>107419336
oof

File: image.png (335 KB, 894x864)

335 KB PNG

Ahahahha, same!

Fri Sep 27 2024 02:57:22 GMT+0000
yep, the first ten digits of part two joltage form a nice timestamp.

>>107419181
>>107419355

>>107418317
My guess is that Integer math is just very slow, whereas list operations (I'm guessing that was your naive solution) are taking advantage of lazyness and end up faster.

My own day 2 was a few threads ago, but not super efficient either (did not try the bigboy)

>>107419304
If you lower your standards you can live pretty much anywhere at any time doing whatever the fuck you want

>>107419140
I'll wait until the weekend and do all at once.

>>107418782
please just stop using let* as an implicit progn. You shouldn't use variable names in any lisp for a value only used once. Also use a named call for recursion (and consider using loop instead since clojure doesn't perform tail call optimization)

(defn find-highest-joltage [need turned-on bank]
  (if (zero? need)
      (digits-›long turned-on)
      (let [highest (apply max (drop-last (dec need) bank))]
        (find-highest-joltage (dec need)
                  (conj turned-on highest)
                  (subvec bank (inc (indexOf bank highest)))))))

(defn solve [filename batteries-per-bank]
  (sum (mapv #(find-highest-joltage batteries-per-bank [] %)
         (slurp-digit-grid filename))))
[\code]

>>107419390
Sure, but one tends to look for the best qol/effort ratio

for a moment I though the second part will be trickier, as in 'The Elf offers you help, and together you are allowed to swap any four batteries'

>>107419181
no idea
my broot takes 0.8s on bigboy

>>107419181
Retards fell for the DP meme

>>107419402
>qol/effort ratio
<.0001 for most people on this part of the world

File: 1734070085986697.png (87 KB, 346x299)

87 KB PNG

>need to decorate the entirety of the north pole in less than 2 weeks
>have to do it alone of course
>try to get the decorations from the base
>have to waste days helping these retarded gnomes fixing their computers and elevators
I DO NOT HAVE TIME FOR YOUR SHIT
I DO NOT HAVE TIME TO COLLECT STARS FOR NO REASON
I have to get to the supply room to get the decorations FFS!!

>>107419304
white, US citizen. I'm just severely mentally ill.

>>107419358
>first ten digits of part two joltage
of your solution for part 2?
what's that date?

>window can only ever shrink
>if it hits size 1 the answer is just the next digits sequentially

>>107419494
anyone did this in C? I want to test it against mine

>>107417421
Now this is a good idiomatic Rust solution.

`
NUMBERS GO HERE
`.trim().split('\n').map(row => {
    row = row.split('').map(e => parseInt(e));
    let result = 0;
    for (let r = row.length-11, l = 0; r <= row.length; r++) {
        const max = Math.max(...row.slice(l, r));
        result = result * 10 + max;
        l = row.indexOf(max, l) + 1;
    }
    return result;
})
.reduce((a, e) => a + e)

>>107419220
Part two.

#include <stdio.h>
#define BATTERIES 100
#define BANKS 200
#define USE 12

int main(){
    long joltage = 0, bank[BATTERIES+1] = {0};
    for(int i = 0; i < BANKS; i++, getchar()){
        int idxT[USE+1] = {0};
        for(int j = 1; j < BATTERIES+1; j++) bank[j] = getchar() - '0';
        for(int j = 1; j < USE+1; j++){
            for(int k = idxT[j-1]+1; k < BATTERIES - (USE - j - 1); k++) if(bank[k] > bank[idxT[j]]) idxT[j] = k;
        }
        for(long j = USE, mp = 1; j > 0; j--, mp*=10) joltage += mp*bank[idxT[j]]; 
    }
    printf("%ld\n", joltage);
}

File: Screenshot_2025-12-03_17-40-43.png (92 KB, 801x701)

92 KB PNG

took me 12 minutes lol
it's way too easy, i feel tomorrow will brutally be extremely brutal

File: elves.jpg (27 KB, 550x281)

27 KB JPG

>>107419479

why do people talk about dp? it's a greedy problem lol. for each digit, if the digit is the highest in the valid range (and leftest), it's the one. no need to complicate it.

>>107419355
that site is so obnoxious

>>107416101
You can make it retroactively. That's what usually happens to seasonal events on /a/, nobody remembers on time.
>>107417404
Manufacturing.
>>107419181
I'm confused as well. I thought the obvious solution to silver was to be greedy from right to left with a cutoff for the first digit so as to not mis-identify 5719 as 99. With only a tiny bit of refactoring you do the same thing 12 times for gold instead of 2, you never ever need to check any "combinations" of digits at all because the greedy algorithm gives the correct result which is a result I learned all the way back in middle school. Given some digits you will always get the biggest number by arranging them from biggest to smallest. I don't even know how silver was recognized as a DP problem, there's no extra work to eliminate.

is it me or is this year a bit more difficult than the previous?

>>107419944
It's not, it's just that the early and easy problems have been removed.
I think DP was day 7 last year.

>>107419886
They say DP because they can't code. They basically have no idea what programming is or the purpose of a program is: to transform data. To them it is all about using a bunch of pre-made modules to build a pre-designed something with zero original thought, and that includes modules for "solutions" (i.e. import <solution>). They are people who can be replaced by AI and nobody would notice a difference, and considering how shitty AI coding is that says a lot.
They see this problem and think DP because they've been conditioned to think DP when they see a problem where you choose one item out of a sack at a time to create the largest or smallest of something. They don't know what they are doing, they just see
>Oh, create the highest joltage from these batteries
>Ok, so let me try every single one, and from each choice then choose the next one from the rest until I have 12, and to avoid doing the same calculations twice I will cache the result
It is pathetic. And they are your colleagues. They work with you, create code that makes everything worse, all the while judging whether or not you have enough unit test tests for your getters and setters that you are forced to create because your codebase is unfortunately OOP.

>>107419944
Only 12 problems. Completely expected that the difficulty curve will be sharper than the other years.

>>107419944
day 1 was tricky, and brutal for a day 1 desu, but 2 and 3 are ok. i think d3 2023 was hard too. 2024 i couldn't tell, i didn't play it.
fuck hello world problems anyway

>>107419989
>day 1 was tricky, and brutal for a day 1 desu
Does your language of choice not have a modulo operator?

>>107419944
The difficulty of the last puzzles are meant to be similar to previous year. So there are less days to up the difficulty.
>>107419886
I want to add that since the windows shrink you will get better than O(n^2) even if you use every single battery
>>107419578
The logic is similar to >>107419697

I still have no idea what the fuck is DP. Evey time somebody explains it, it is just fucking common sense and not some concrete trick you need to use to solve something.

>>107419991
NTA, but have you looked at the Day 1 of previous years? Day 1 tend to be
>Find the highest number in row and add them together
>Part 2: now multiply them
This Day 1 was more like a typical Day 2-3

>>107419944
it is brutal
I was hoping on day 1 - 12 difficulty to match that of previous years, instead of just a shorter difficulty curve

>>107419998
DP means you are using hashmap to avoid recalculating the same thing over and over again

>>107419998
DP is basically a marketing term for algos that make use of recurrence relations in the problem. The name was literally made just to confuse management and sound impressive.

>>107420015
that would be lame

>>107419886
because I didn't understand your post or >>107415695 until the next morning
my first impulse of sorting the digits and picking the top 2 really threw me.

>>107419998
Essentially everything in both computer science and computer programming with a fancy name falls into that category. Computer programmers have always been uniquely stupid and under-skilled relative to their actual economic output.

>>107420015
Hoped to finally complete a year? Well, too bad, no-coders don't deserve stars

>>107420030
This is called memoization.

File: 1758665748544992.jpg (48 KB, 827x792)

48 KB JPG

>>107420043
Just once
JUST ONCE I WANTED TO SAVE CHRISTMAS!

>>107420035
Are you honest to god telling me that you needed another person's post and a night of sleep to understand that 90 is larger than 89?

>>107420057
DP is the process of breaking a large problem into smaller sub-problems which are repeated and can be memoized

You fucking morons realize the inputs don't contain any 0s right?

>>107420078
so?

>>107419991
yeah but it's too easy to make mistakes dude. if you simulate each tick individually yeah sure (which i ended up doing, shamefully), but if you're going for a proper solution it's easy to screw up

>>107420078
This changes what exactly?

>>107420092
So the problem you're solving is different than the one you're being asked to solve. You are a bad person.

>>107420078
and?

File: img-2025-12-03-18-14-50.png (3 KB, 220x170)

3 KB PNG

>>107420104

>>107420060
Well, you failed. You are a disappointment. You will always be a disappointment. Every year Santa frowns when he sees your name because he knows that Christmas is doomed. Every year the elves try their best to keep the disgust they feel from showing on their faces when they talk about you. Every year children cry because Christmas is cancelled yet again because of your incompetence.

>>107420103
>>107420118
The DPtard spamming about how 90 is bigger than 89 has failed to realize that there is no 90. The correct solution is the greedy one.

>>107420062
what did you think those next words about "sorting" were about?
I needed a night of sleep to remember that it's not relevant that 98 is larger than 90

>>107420133
moron

>>107420030
>>107420077
wrong
>>107420031
right

>eu goes to sleep
>na shits up the thread
everytime

>>107420141
You will never write a performant program in your life because you slur fitting as overfitting.

>>107420164
the 9000 vs 8999 thing had nothing to do with dp brainlet

>>107420062
NTA but I think he's just meaning that he didn't get that particular "trick" (number propriety), not that the trick was revealed to him by an anon. But it's ok, when you're tired, you can tunnel vision. And also when you're playing for chronometer.

>>107420135
Even if the task was to create the largest number possible from the numbers no matter the order, WTF does DP have to do with it? All you need to do then is sort and take the two or twelve first digits.

>>107420152
>>eu goes to sleep
it's 6pm in europe, the only place you could be in that's going to sleep about now is india

>india goes to sleep
>thread goes to shit
wtf?

>>107420133
What are you, an idiot? I'm the one who said that 90 is bigger than 89 to show why DP is the stupidest fucking solution to this problem, and it absolutely doesn't matter if there are zeros in the input or not, because 91 is still larger than 89.
I used the example to illustrate why a greedy algo is the best, moron!

>>107420198
namaste spirit bro, just peace

>>107419998
watch an MIT lecture about it on youtube
I was searching for the one I saw but can't find the specific one

>>107419998
>>107420218
or just do these problems until J, they're very good, especially C and D.
https://atcoder.jp/contests/dp/tasks

>>107420198
India hasn't gone to sleep, they are mostly the only ones in this thread desperately trying to not be filtered because every other part of the world cleared it many, many hours ago

>>107420198
India are master coders and whites can't compete. Many such cases.

>>107420205
What are you talking about? Give an example where DP fails, yes, even with 0s.

>>107419240
It's easy to force a DP solution here if you have practiced enough problems. I understood the greedily finding the next element that is greatest among the leftover digits, and the monotonic stack one. Curious about the sliding window. Can you share it?

>>107420267
I will recommend these too. Pair it up with https://cp-algorithms.com/dynamic_programming/knapsack.html

>>107420409
It fails to be efficient

>>107419981
holy based
post of the year

>>107420101
>proper solution
shut the fuck up

>>107420409
>Curious about the sliding window. Can you share it?

See e.g. >>107418922

Left pointer starts at 0, right pointer 11 from the end
Find the max digit in this window, this is a digit of the solution
Left pointer is set 1 past the index of the chosen digit
Right index always advances by 1

Basically you find each digit in order, while ensuring you can't pick a digit so far in you don't have enough remaining to fill out your 12-digit solution.

>>107419981
>>107420530
agree, here's a (You)

File: buy my merch and donate b(...).png (41 KB, 800x800)

41 KB PNG

>Reconsider whether you really want to be on the hook for $150,000 per puzzle input copied and per copy distributed.

File: code.png (187 KB, 1598x1428)

187 KB PNG

Python

>>107420596
it's not a sliding window if you recalculate max(window) every time from scratch you retarded idiot it's just a window

File: b.jpg (36 KB, 746x704)

36 KB JPG

>a window that slides is not a sliding window

>>107420796
INDIAN

>>107420179
Define the solution as:

Let bank denote the string "818181911112111"
max_num(len, digits) = max. number achievable from the "len" length of prefix of bank with "digits" no. of digits

It can be written as:

max_num(_, 0) = 0
max_num(0, _) = -inf # With an empty prefix, we cannot create a no. of non-zero digits
max_num(len, digits) = max(
max_num(len-1, digits),
max_num(len-1, digits-1) * 10 + int(bank[len-1]),
)

Impl in Python:

from functools import cache
ans = 0
for bank in open(0).read().split():
    @cache
    def max_num(len: int, digits: int) -> int:
        if digits == 0: return 0
        if len == 0: return -1
        return max(
            max_num(len - 1, digits),
            max_num(len - 1, digits - 1) * 10 + int(bank[len - 1]),
        )
    ans += max_num(len(bank), 12)
print(ans)

This rewrites the solution for current query (len, digits) in terms of smaller sub-problems. This is the crux of the dynamic programming solutions. You can apply this for each row/bank. Now, the answer for a bank will be max_num(len(bank), 12).

This can be implemented either iteratively or recursively. It's really easy to implement if you just cache the results. You can reason about why the no. of different states will be len(bank) * 12. Because that's the no. of different combinations of arguments possible.

>>107420842
gpt on this thread is cringe
you have 149 other threads on this board
here it's human only sorry pal

>>107420796
this >>107417124 doesn't use a sliding window because the size of the window changes every time and the new max can't be trivially derived from the previous state
what an idiot

CAM ON ERIC
GIVE ME SOMETHING HARD

also is the theme this year decimal numbers or something? felt like I did a lot of % 10, * 10, / 10, */%10.pow(x)...

>>107420842
sir i am bramin i also do DP in python perfect for good looks wishnu has a good news for you

>>107420865
Calling my effort out as GPT is insulting :<

>>107420890
I used Python because it will be closer to the expression I gave above it. See my Zig solution in the previous thread for iterative.

>>107420842
I didn’t say that it was impossible or not a solution. I said that it was the dumbest solution. Read >>107419981

File: 2025-12-03_19-29-11.jpg (10 KB, 149x163)

10 KB JPG

>>107418614
>Where do you get these?
My computer.
>Do you have more?
Do you have any to trade?

>>107421026
>Do you have any to trade?
Sadly no, I am but a poor beggar...

File: 1484491572033.jpg (27 KB, 347x450)

27 KB JPG

>>107421088
I can spare this one.

>>107420596
Neat implementation, but this is the same sol I meant by "greedily finding the next element greatest among the leftover digits". This is still O(n*m) due to .max_idx(). Consider the worst case of 999..., Here, the left ptr will not shift by much, and you will end up scanning over almost the entire string (of length n) m times to find the max index. This is basically the same time complexity as the DP solution.

So, monotonic stack is still the big brain sol? Kind of disappointing.

>>107420455
And, which is more efficient? Which greedy algo?

>>107420963
It's just unnecessarily complex for this problem, not dumb.

>>107421112
Thanks anon, very sweet!

>>107420880
Seems like decimal manipulation is en vogue lots of new leecode problems are of that type and everybody is saying that's what the companies are asking in interviews

File: 1462064448990s.jpg (6 KB, 250x200)

6 KB JPG

Try the prime challenge if it was too easy for you!
>part 1 : Return the largest prime number per row and sum
>part 2 : The sum must be the largest prime number possible. The individual rows must still be prime, but they are not all required to be the largest prime.
Part 2 permits single digit primes by construction with leading 0s. Alternatively the the sum must be largest prime + 1.

>>107421165
>lots
max two
>everybody
one tranny on reddit

>>107421127
>And, which is more efficient? Which greedy algo?
Are you pretending to be retarded or are you actually retarded?

Day 3 done. Again, easy to figure out what to do, harder to implement properly, but so far I'm doing 1 hour per day, and I believe I have found a good balance between "I don't care as long as it works" and not making a giant mess.
I also want to add that I found part 1 to be more difficult than part 2.
>>107417404
Code monkey, but somehow lucked into an actually interesting job.
>>107417841
Nice font bro
>>107418922
How do you guys all manage to write such concise code? I always end up with a bunch of nested loops and variables all over the place.

>not a single person caught the logic bug in the puzzle
89 is not the largest number in

811111111111119

>>107418481
>no but it's O(n) for each row in both memory and time
The Ordo meme strikes again. Imagine believing that it is ok to do a bunch of useless shit as long as you don't make the "time complexity" worse

>>107421220
Are you implying there is only one greedy sol? Just share the one you are talking about, and why it is more efficient.

>>107420756
>>107420812
>>107420870
>t. filtered samefag retard

For the general case ("digits" of arbitrary size, large n and m) you'd maintain a sorted window of elements (max heap) and insert/remove as the window advances.

Obviously doing this is overkill when the window size is 12 and digits only have 9 values. But anyone who understands the basics of programming would see the sliding window solutions and not need to be spoonfed why it's a linear search in this instance, and the idea trivially generalises to O(n log m).

>>107421242
ok

>>107421242
Which number would be larger then?

>>107421265
98

>>107421265
90

>>107421194
>The sum must be the largest prime number possible. The individual rows must still be prime, but they are not all required to be the largest prime.
Anon, there's an even number of rows...

>>107421265
67

File: frame-001.png (146 KB, 498x354)

146 KB PNG

>>107421273

File: 1740570416940599.jpg (117 KB, 677x1000)

117 KB JPG

>>107421291

>>107421258
All of them that don't do obviously stupid shit, because none of the greedy solutions are stupid enough to check if e.g. 111111111111 is the highest number in 111111111111999999999999

>>107421265
1

>>107421308
wrong

>>107421278
Say your sum is 18312. The largest prime you could construct is the one below that, 18233. So you need to re-pick primes to sum up to that. In my case this is done by choosing 2 instead of 79 and 71 instead of 73.

>>107421165
>decimal manipulation
what does this mean
got an example?

File: beautify-picture.png (1.66 MB, 920x1653)

1.66 MB PNG

Day 3 in Python

On an unrelated note, does anyone happen to have access to a supercomputer?

File: the_matrix_reloaded_4k_34.0.jpg (225 KB, 1200x800)

225 KB JPG

>>107421310
based

>>107421273
You didn't read the puzzle then.

>>107421321
Ok, give me one greedy solution that is dumber than a DP solution but still doesn't do obviously moronic things

File: 1741280198069417.png (71 KB, 763x554)

71 KB PNG

Another load of clojure shit

>>107421330
math instead of temporary string conversions (which are performed by probably much faster math and could safely fill an array without allocating memory in any reasonable language)

>>107421349
no

>>107421337
you were trying to make a meme on purpose, right?

>>107421127
>So, monotonic stack is still the big brain sol? Kind of disappointing.

If you look at production sorting algorithms, they often finish by passing to insertsort, even though insertsort is O(n^2).

At this scale the big brain solution is the sliding window approach. You'd need much bigger inputs before monotonic stack overtakes.

>>107421356
>(->> (mapv (fn)) (mapv (fn)) (mapv (fn)))
how are you liking Clojure?

File: beautify-picture(1).png (569 KB, 759x693)

569 KB PNG

>>107421381
Well I solved the first part as picrel and I am too much of a retard to solve it properly

>>107421259
Seems impractical. Send your implementation after testing it.

>>107421308
>Emotionally charged arguments based on special cases.
Cool

>>107421405
>append int
>enumerate list str
atoi() for no reason award

>>107421380
Because you can't. Because it takes a special type of no-code brain to create a DP solution for this problem. The type of brain that usually belongs to a bicycle helmet wearing webdev turned UX who travels to work on a short bus.

>>107421399
It's frustrating and rewarding to find solutions because it makes you think differently from c-like languages in terms of how to get the thing to do what you want.
Also what would be a solution to the mapv (fn) thing?

>>107417404
unemployed with 3 years of experience

>>107421437
In being unemployed?

>>107421426
I think we've already established I am mentally challenged.

>>107421416
>Emotionally charged arguments based on special cases.
Are you pretending to be retarded or do you work in webdev?

File: carbon(148).png (535 KB, 1662x2830)

535 KB PNG

Love me vectors, simple as.

>>107421395
I was not talking about just the asymptotic complexity but anything more fun than these three. I guess the problem is too simple to have many different solutions (except obvious bad ones like (n C 12)).

>>107421405
well, if it works, it works!

>>107421482
>except obvious bad ones like (n C 12)
SIR! This is a glorious DP problem SIR! I have used a hashmap I am doing the DP sir! No nodes till be trimmed from the tree sir!

WARNING: midwits have been detected in this thread

>how do I know I'm speaking to a midwit

They obsess over O(n) in cases where it's irrelevant. They ignore branching, cache misses, heap overhead, and other factors a competent programmer would consider.

>I've found a midwit, how should I respond?

Call them a retard. Also call your representative and demand India be disconnected from the internet.

>>107421505
>reddit spacing

>No grid problems yet
wtf is Eric doing?!

Someone's insecure about their dogshit code.

>>107421505
100% truth. The Ordo meme is one of the stupidest things no-coders believe in.

>>107421330
>what does this mean
>got an example?
just look at the palindrome number problems on leetcode

>>107421505
Wasting time worrying about implementation details instead of algorithms is peak midwit.

>>107421570
Tell me you don't know how computers work without... actually, you just did

File: carbon.png (81 KB, 1902x552)

81 KB PNG

fun problem. not super happy with how verbose my part 2 is. Probably a lot cleaner in an imperative language.

O(no) i'm a computer and i'm being forced to run this man's shit code!

File: le pepe.jpg (95 KB, 798x798)

95 KB JPG

>>107417509
LMAO, imagine being a poorfag.

>>107415759
d sliding window: 624ms and 6MB MaxRSS
pypy 1:1 transliteration: 10.4s and 399MB
python: not going to wait a week on this garbage
zig sliding window: I'm not going to find out the new incompatible way to do basic IO for the FIFTEENTH TIME
>>107421505
>them
reddit gender

>>107421591
>use optimizing compiler
>turns your code into reasonably best case
I don't need to worry about that shit til I do.
I get into arguments with tardos like you when they suggest "Huge pages" without any metrics showing TLB misses or appreciable performance.
branching is not a big deal for any modern superscalar CPU used by literally any product that is general purpose.

literally fuck off.

File: ON_SAR.jpg (60 KB, 405x720)

60 KB JPG

Whats the Time Complexity on the DP solution? I see some people did greedy which is just O(n), but isn't DP also O(n) you're never iterating over each element more than once because of the memoization right?

File: scopium.jpg (128 KB, 903x500)

128 KB JPG

>>107421570
> Naive two loops O(n*n) still faster doing bigboys than stack O(n)

>>107421736
>naive two loops O(n*n)
huh? you only need one loop that you execute a fixed number of times.

>>107421698
No wonder modern webpages are slow as shit covered in suryp when tards like you are webdevs. The compiler can only do so much, and the more idiocy you throw in the code the more confused the compiler becomes. And the more your CPU has to fetch data from the RAM the more time and money you waste for all of us.
Literally stop coding. Do us all a favor and go work in McDonalds or something. But you'll most likely fuck that up as well.

>>107421762
>cache misses, muh branches, muh heap
>web
you have no power to influence those things. just understanding the data and how you handle it is 100000x more important than microarchitectural details, you deranged retard.

>>107421752
Ok, true, it wasn't O(n*n), but O(n*k). I can sleep now.

>>107421720
>He fell for the Ordo meme

>>107421752
I think he's correct. Naive you're looping through the set of nums twice. For every number you check if there's one after it that's bigger otherwise you add it to the result. When you hit 12 numbers you're done.

>>107421779
If you don't care about any of those things the only path for you is web. But you fuck that up too with your worthless code.
Literally stop coding. Do us all a favor.

>>107421505
>They obsess over O(n) in cases where it's irrelevant.
Midwit detected.
It's always irrelevant

>>107421696
>thinking of indians as individuals

>>107421799
what the FUCK is your problem you raging retard? show benchmarks for your day 3 if you're so great.

mine runs in: 728.6 µs ± 433.2 µs

>>107421827
My problem is that you are a no-coder who should apply for work in the closest McDonalds.

File: feels.png (203 KB, 600x600)

203 KB PNG

>>107421505
>They obsess over O(n) in cases where it's irrelevant. They ignore branching, cache misses, heap overhead, and other factors a competent programmer would consider.
kekked. literally "O(n) isn't important you know what's important branching, overhead, cache..." that's literally SPACE COMPLEXITY. some people haven't read their sicp and it shows. :(

>>107421842
>no benchmarks
your opinion has been thoroughly destroyed. good day retard. maybe learn what flame graphs are next instead of wasting your time with uarch details.

>>107421855
>branching, overhead, cache..." that's literally SPACE COMPLEXITY
Omega dimwit

>>107421861
I didn't want to humiliate you further, but sure.
450 µs, and this is my unwashed code I haven't bothered to optimize the slightest.

>>107420179
>Even if the task was to create the largest number possible from the numbers no matter the order
that would have been way easier
just sort the characters in the string and get the first 12 characters

>>107421907
Exactly. But tards still want to do DP for some reason.

>>107421883
...am I wrong? ...your argument is people shouldn't bother with complexity because what matters is space complexity....

>>107421026
>>107418614
>planking
:|
>planking, japan
:O

>>107421900
holy shit you're such a fucking dumb nigger lmao.

all the time in my code is dominated by less than comparisons in a hot loop. your times aren't even better than mine.

>>107421921
Yes, you're completely wrong but it's not surprising because you mentioned SICP

Time and space complexity have nothing to do with the reality of how hardware works

>>107421855
That's not what space complexity means at all you fucking retard.

Do you use vectors where an array would do? Do you create new vectors instead of reusing the same allocation? Does your code have unnecessary if statements, especially unpredictable ones? Do you access memory in a cache-friendly way?

Space complexity is a measure of how much memory your program requires. You can refactor code to be stack-only, or minimise random-like branches, without affecting space requirements at all.

I wonder if there's a way to make this problem actually require DP instead of being doable with a greedy algorithm. Maybe doing something similar to 2020 day 10 where you're forced to use batteries within a certain joltage distance of each other? Would probably require different inputs that admit a solution

>>107421931
Well, my average time is about the same time as your deviation from your mean. In my code that I haven't done shit to optimize. If you think that code that runs 30% faster is "nothing" with a much smaller S.D., then go ahead. Prove it. Prove that it isn't a big deal.
And when you've proven it, maybe I'll actually take a look at how my solution could be optimized to run just a little bit faster so you'll blown completely the fuck out again.
>b-but it is just a difference of micro seconds
For this input, yes. For larger input? No.

File: jackie-chan-meme-template.jpg (63 KB, 1500x1005)

63 KB JPG

>>107421952
>time and space complexity have nothing to do with reality

>>107421981
yup that's exactly it. the house robber problem (where you have to skip the next house after you pick one) is essentially that and can only be solved with dp.
https://leetcode.com/problems/house-robber/description/

>>107421921
he's a retard who once found a O(n^2) algorithm to be faster than an O(n) algorithm when increasing the number of elements from 10 to 11, and was so surprised by this fact he has to bring this up every thread
just ignore him

Can anyone tell me wtf DP is supposed to mean? I can't find it, I never learnt algortihms.

>>107422059
double penetration

>>107422047
idgi... I mean, I think everyone ITT understands why B-Trees are generally favored over binary trees in general, but most of the cases where big Os generally decouple from how CPUs work is pretty far and few between.

>>107422059
double penetration of your CPU if you fuck up.

>>107422059
dynamic programming, fancy word for divide and conquer with the usual difference being overlapping subproblems. usually associated with stuff like memoization, god awful recursive code no one likes and what not.

i used a monotonic descending stack, this was definitely the intended solution.

>>107422122
I use 3 nested loops.

>>107422144
>3 nested loops
honestly, how?

>>107422112
>god awful recursive code no one likes and what not
really? I find array recursive dp much easier than array dp. bottom up is a lot easier to visualize and reason about than top down.

>>107422152
see >>107417384

File: 1444451230930s.jpg (6 KB, 250x250)

6 KB JPG

oh right and me calling the guy out as a kike faggot yesterday is somehow worse than this autism fight
you subhuman niggers

File: 82374172_664107694357764_(...).jpg (85 KB, 1080x607)

85 KB JPG

What tactics are you using for day3p2? Nothing nice comes to mind immediately.

>>107422021
I can't help your lack of reading comprehension

>>107422158
this was not written by human hands. that's not a compliment btw

>>107417384
m8 you got rekt by >>107418922
both shorter and more readable

>>107422059
Dick Penis hehe

File: solve.png (474 KB, 5008x2542)

474 KB PNG

>>107422197
this was typed by idiomatic hands

>>107422158
oh, I see. Ya, I guess I have three loops too.

>>107422182
see 6 posts above

File: 1755588638839968.png (561 KB, 1200x687)

561 KB PNG

>>107422182

why do you guys use rust?

File: bench.png (536 KB, 1954x1354)

536 KB PNG

Benchmarked DP vs. greedy vs. monotonic stack just to settle this stupid debate. Let me know if you can improve these implementations. Results were as expected. Code: https://pastebin.com/wW7YQEYT and results in the image.

>>107422059
Dragon Punch, don't whiff it

>>107422237
Does having AI rewrite other languages into rust count as using rust?

>>107422182
There's no real trick to it. You just gotta pick 12 numbers. The set order means you your options are pretty limited in terms of you're only able to choose a bigger number while they're 12 more left to choose from. Once you've chosen your biggest first number its just doing it again from there but this time with 11. Hope that helps.

>>107422216
tf does map_or_else(identity, Option::unwrap) do?

>>107422237
see >>107416080
Rust is blazingly fast

>>107422257
it returns the err value unchanged and unwraps the ok value

>>107422238
Yep. Like I said, DP is the dumbest solution

>>107422249
>Does having AI rewrite other languages into rust count as using rust?
Real Rust can only officially be written by cute fem boys with painted nails in programmer socks. You can literally feel the estrogen while reading it. I guarentee you tripple loop guy doesn't have cute boy feet.

>>107422182
loop over the input twelve times, updating begin/end limits on each iteration

>>107422280
>it returns the err value unchanged and unwraps the ok value
ok... I understand, you early exit on 9. makes sense. thanks.

File: day3.png (45 KB, 689x951)

45 KB PNG

Ziggers in!

>>107422238
>@embedFile
that's one way to not have to update your Zig every single year.

>>107422182
A number with higher first digit is always bigger than number with lower first digit. So just find first what highest and leftest digit you can use first and work from this.

>>107422182
This >>107422256 . It's how you would do it irl. unironically how has no one tried to find the sol of p2 manually. it will be better than the brute with all combinations. should take about 4hrs

>>107421416
>Seems impractical. Send your implementation after testing it.

What part is impractical? Standard lazy max heap:

>max heap of (value, -index)
>store index of last_popped element
>begin by pushing first m elements
>for each step of the window:
>pop heap
>discard as stale until popped value has greater index than last_popped
>update last_popped
>record digit of solution
>push next element
>repeat until you have m digits
>can special case if window size ever reduces to 1

You're essentially drifting towards the monotonic stack approach, only with a heap. Sliding window only wins for AoC-size inputs where small m means you can replace the heap with a stack and treat the linear search as constant.

>>107422216
Hold the fuck on you're copying >>107418922, you just replaced his fold with a scan

File: day03.png (102 KB, 900x858)

102 KB PNG

actually idiomatic rust.
takes 60ms for
>>107417340

>>107422373
dumb retard, see >>107415347

>>107422386
>best.reverse();
gj, your best is now your worst.

>>107422386
retarded collect

>>107422404
twice reversed, once best

>>107422332
what does sol mean?

>>107422386
AI coded

>>107422356
Seems very similar to the stack sol, except you are incurring an unnecessary log(m) factor. Stack sol is amortized O(n), best till now. See >>107422238

>>107421720
>but isn't DP also O(n) you're never iterating over each element more than once because of the memoization
kekkkkkkkk