Project Euler / programming problems

General Chat
488

Tried to be fast today, but yebellz was faster :slight_smile:

image
image942×132 18.7 KB

python, day 4 
with open('4.txt') as data:
    lines = data.readlines()
total = 0
for s in lines:
    winning = set()
    value = 0
    for i in range(10, 39, 3):
        winning.add(int(s[i:i+2]))
    for i in range(42, len(s), 3):
        if int(s[i:i+2]) in winning:
            value = max(1, value*2)
    total += value
print(total)

counts = [1] * len(lines)
for k, s in enumerate(lines):
    winning = set()
    value = 0
    for i in range(10, 39, 3):
        winning.add(int(s[i:i+2]))
    for i in range(42, len(s), 3):
        if int(s[i:i+2]) in winning:
            value += 1
    for j in range(value):
        counts[k+j+1] += counts[k]
print(sum(counts))

Originally my variable k was also named i, which took me a couple minutes to debug… I’m more used to block scope variables, so I forgot how it works in python.

3 Likes
489

How do you view the timings?

My day 4 code 
import fileinput

def process(snip):
    snip = snip.strip().split(" ")
    return [int(i) for i in snip if i]

total = 0
for line in fileinput.input("4input"):
    line = line.strip()

    _, line = line.split(": ")
    winning, mine = line.split("|")
    winning = process(winning)
    mine = process(mine)
    matches = 0
    for num in mine:
        if num in winning:
            matches += 1
    if matches > 0:
        total += 2 ** (matches - 1)

print(total)

import fileinput
import numpy as np

def process(snip):
    snip = snip.strip().split(" ")
    return [int(i) for i in snip if i]

instances = np.ones(300)
for index, line in enumerate(fileinput.input("4input")):
    line = line.strip()

    _, line = line.split(": ")
    winning, mine = line.split("|")
    winning = process(winning)
    mine = process(mine)
    matches = 0
    for num in mine:
        if num in winning:
            matches += 1
    if matches > 0:
        instances[index+1: index+1+matches] += instances[index]

print(sum(instances[0:214]))
3 Likes
490
4 Likes
491

Easy day today, heard they are more difficult at the weekend, so that rings true.

Day 4 Part 2 
text = text.replaceAll('  ', ' ');
var inputArray = text.split('\n');
var total = 0;
var cardWins = [];

for (var n = 0; n < inputArray.length; n++){
    var row = inputArray[n].split(': ');
    var winHave = row[1].split(' | ');
    var win = winHave[0].split(' ');
    var have = winHave[1].split(' ');
    var points = 0;
    for (let i = 0; i < have.length; i++) {
        for (let j = 0; j < win.length; j++) {
            if (have[i] == win[j]) { points += 1; }
        }
    }
    cardWins[n] = points;
    console.log("card", n, "has" , points, "points");
}

var numCards = [];
numCards.length = cardWins.length;
numCards.fill(1);
for (let i = 0; i < numCards.length; i++) {
    for (let j = 0; j < cardWins[i]; j++) {
        numCards[i + 1 + j] += numCards[i];
    }
}

for (let j = 0; j < numCards.length; j++) {
    total += numCards[j];
}

console.log(total);
2 Likes
492

Looking at this thread inspired me to go back on work on Project Euler. I just solved problem 84 “Monopoly Odds”, which finishes the first 100 problems for me.

I was putting this one off, since it’s just a boring chore to code up all of the transition rules, and it’s conceptually easy and somewhat uninteresting to solve.

Code and Discussion

The problem is about finding the steady state distribution (or rather just identify the top 3 states) of a Markov chain. The vast bulk of the code is just coding up the rules to calculate the transition matrix. After doing that, the steady state distribution is trivial enough to find with a few lines of code to simulate a 1000 distributional transitions (it probably converges with far fewer than that). One could instead solve a system of equations, but just iterating is fast and precise enough to get the right answer, with less coding work.

import numpy as np
from scipy.linalg import circulant

sides = 4
denom = sides ** 2
prob_vector = np.zeros(40)
for i in range(1, sides + 1):
    for j in range(1, sides + 1):
        prob_vector[i + j] += 1
        if i == j: # Double outcome
            # Subtract odds of previous two rolls are doubles
            prob_vector[i + j] -= (1 / denom)
prob_vector /= denom

base_transitions = circulant(prob_vector)
# Likelihood of winding up in jail from rolling three doubles
base_transitions[10, :] += (1 / (sides ** 3))
# Go directly to jail
base_transitions[10, :] += base_transitions[30, :]
base_transitions[30, :] = 0

print(np.sum(base_transitions, 0)) # Sanity check

# Community Chest (2/16 cards): (02, 17, 33)
##  Advance to GO   (00)
base_transitions[0, :]  += (base_transitions[2, :] + base_transitions[17, :] + base_transitions[33, :]) / 16
##  Go to JAIL      (10)
base_transitions[10, :] += (base_transitions[2, :] + base_transitions[17, :] + base_transitions[33, :]) / 16
base_transitions[2, :]  *= (14 / 16)
base_transitions[17, :] *= (14 / 16)
base_transitions[33, :] *= (14 / 16)

print(np.sum(base_transitions, 0)) # Sanity check

# Chance (10/16 cards): (07, 22, 36)
##  Advance to GO   (00)
base_transitions[0, :]  += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to JAIL      (10)
base_transitions[10, :] += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to C1        (11)
base_transitions[11, :] += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to E3        (24)
base_transitions[24, :] += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to H2        (39)
base_transitions[39, :] += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to R1        (05)
base_transitions[5, :]  += (base_transitions[7, :] + base_transitions[22, :] + base_transitions[36, :]) / 16
##  Go to next R    (15, 25, 05)
##  Go to next R    (15, 25, 05)
base_transitions[15, :] += base_transitions[7, :] / 8
base_transitions[25, :] += base_transitions[22, :] / 8
base_transitions[5, :]  += base_transitions[36, :] / 8
##  Go to next U    (12, 28, 12)
base_transitions[12, :] += base_transitions[7, :]  / 16
base_transitions[28, :] += base_transitions[22, :] / 16
base_transitions[12, :] += base_transitions[36, :] / 16
##  Go back 3       (04, 19, 33)
base_transitions[4, :]  += base_transitions[7, :]  / 16
base_transitions[19, :] += base_transitions[22, :] / 16
base_transitions[33, :] += base_transitions[36, :] / 16

# Staying in place
base_transitions[7, :]  *= (6 / 16)
base_transitions[22, :] *= (6 / 16)
base_transitions[36, :] *= (6 / 16)

print(np.sum(base_transitions, 0)) # Sanity check

# Initialize with uniform likelihood over all but jail
initial = np.ones(40) / 39
initial[30] = 0

for i in range(1000): # More than enough to converge for finding top 3
    initial = base_transitions @ initial
print(initial)
print(initial[10], initial[24], initial[0]) # Top 3 for sides = 6

print(np.argsort(-initial)[:3])

I made the simplifying assumption that going to jail for speeding (rolling doubles 3 times in a row) does not reset the double counter, so that rolling doubles 4 times in a row means two trips to jail (after both the third and fourth roll). It is straightforward to modify the code to account for this, but it does not change the top 3.

Edit: checking the PE forum, I see that I also neglected to account for the possibility of going from Chance 3 to Community Chest 3, but clearly that has a small effect.

1 Like
493

Day 5 part 2 has me stumped, damn those hungry elves. Need to have a good think about how to do it compute efficiently at work tonight if I get a chance.

1 Like
494

Yeah, I’ll do that later too.

Seems like I’ve got to maintain the range structure especially on a board with 264k of RAM.

So processing one map might result in a single range getting split into as many as three new ranges (two remaining in the source and one in the destination), depending on how they intersect.

3 Likes
495

Finally got around to finishing day 5.

Not very proud of having to consider four different cases iteratively and mutating so many objects constantly but against all odds it worked on my first try. I ended up with the original 10 seed ranges planted across 152 different location ranges, which isn’t bad at all space-wise.

So many inequalities of all types 
    new_seeds = []
    for seed in seeds:
        # part overlaps beginning
        if seed[0] < source_start and seed[0] + seed[1] > source_start:
            new_seeds.append((seed[0], source_start - seed[0]))
            seed = (source_start, seed[0] + seed[1] - source_start)
        # part overlaps end 
        if seed[0] <= source_start + length and seed[0] + seed[1] > source_start + length:
            new_seeds.append((source_start + length, seed[0] + seed[1] - source_start - length))
            seed = (seed[0], source_start + length - seed[0] + 1)
        # complete overlap
        if seed[0] >= source_start and seed[0] + seed[1] <= source_start + length:
            dest.append((seed[0] + dest_start - source_start, seed[1]))
            seed = None
        # remaining part
        if seed != None:
            new_seeds.append(seed)

I’ll be interested to see how you all did it more elegantly.

By the way, I’ve been uploading my code to GitHub.

5 Likes
496

My code for day 5 is similar, and perhaps even less elegant.

Day 5, Part 2 
import fileinput
import numpy as np

lines = [line for line in fileinput.input("5input")]

seeds = lines[0]
_, seeds = seeds.split(': ')
seeds = [int(i) for i in seeds.split(" ")]
seeds = np.asarray(seeds).reshape(-1, 2)
print("seeds", seeds)

def get_maps(lines):
    maps = []
    map = []
    for line in lines:
        line = line.strip()
        if line == "":
            maps.append(map)
            map = []
        elif not line.endswith(":"):
            map.append([int(i) for i in line.split(" ")])
    maps.append(map)
    return maps

def find_overlap(seed, seed_size, dest, source, size):
    seed_end = seed + seed_size - 1
    source_end = source + size - 1

    if seed_end < source or source_end < seed:
        return [[seed, seed_size]], [] # Unmapped, Mapped

    if seed >= source:
        if seed_end <= source_end:
            return [], [[seed - source + dest, seed_size]]

        else: # seed_end > source_end:
            mapped_size = source + size - seed
            return [[source_end + 1, seed_size - mapped_size]], [[seed - source + dest, mapped_size]]

    else: # source > seed
        unmapped = [[seed, source - seed]]
        if seed_end <= source_end:
            return unmapped, [[dest, seed_size - source + seed]]

        else: # seed_end > source_end
            unmapped.append([source_end + 1, seed_end - source_end])
            return unmapped, [[dest, size]]

def apply_map(seeds, map):
    mapped = []
    unmapped = seeds
    for dest, source, size in map:
        next_unmapped = []
        for seed, seed_size in unmapped:
            new_unmapped, new_mapped = find_overlap(seed, seed_size, dest, source, size)
            mapped.extend(new_mapped)
            next_unmapped.extend(new_unmapped)
        unmapped = next_unmapped
    return mapped + unmapped

for map in get_maps(lines[2:]):
    seeds = apply_map(seeds, map)

print("Final", seeds)

smallest = 100000000000000000000
for seed, size_size in seeds:
    smallest = min(seed, smallest)
print(smallest)
Day 5, Part 1 
import fileinput

lines = [line for line in fileinput.input("5input")]

seeds = lines[0]
_, seeds = seeds.split(': ')
seeds = [int(i) for i in seeds.split(" ")]
print("seeds", seeds)

def get_maps(lines):
    maps = []
    map = []
    for line in lines:
        line = line.strip()
        if line == "":
            maps.append(map)
            map = []
        elif not line.endswith(":"):
            map.append([int(i) for i in line.split(" ")])
    maps.append(map)
    return maps

def apply_map(map, seed):
    for dest, source, size in map:
        if seed >= source and seed < source + size:
            return (seed - source) + dest
    return seed

maps = get_maps(lines[2:])

smallest = 1000000000000000000
for seed in seeds:
    for map in maps:
        seed = apply_map(map, seed)
    smallest = min(seed, smallest)
print(smallest)

I’ve already set up a local git repo for my solutions, but I haven’t pushed anything to GitHub yet. I’ll maybe do that a bit later.

3 Likes
497

I wrote some similarly inelegant code, splitting into four cases for the type of overlap, except mine did not work on the first attempt, and I’m too lazy to debug it :stuck_out_tongue:

2 Likes
498

But look at Yebellz’s code! Turns out there are FIVE cases. Or maybe six if you separate the or in the first one. Mine only worked because I used an if-if-if-if structure instead of if-elses, so multiple things could happen each iteration. I had tried to count all the actual cases in my head but since it was after 11pm already I just couldn’t handle it.

2 Likes
499

I honestly cannot even tell you right now how many cases there are or should be. It made sense when I was plugged in and writing that code, and it worked somehow, but I don’t really feel like thinking through all of that again, right now.

More elegant code, with better explanation, structuring and comments would make the algorithm more readily apparent from examining the code. My code fails to do that, since I just tried to work as quickly as possible.

Note that a lot of the if-else nesting is avoidable, since return statements automatically act like else. If I took more time, I would have refactored to try to make the code more readable, but I just left it as is, out of laziness.

What I mean is this sort of refactoring pattern:

Original

if alpha: # alpha is just a placeholder for some condition
    # Do something for condition alpha
    return stuff_for_alpha
else: # not alpha
    if beta:
        # Do something for not alpha and beta
        return stuff_for_beta
    else: # not beta
        # Do something for not beta
        return stuff_for_not_beta

Refactored

if alpha: # alpha is just a placeholder for some condition
    # Do something for condition alpha
    return stuff_for_alpha
if beta:
    # Do something for beta
    return stuff_for_beta
# Do something for not beta
return stuff_for_not_beta
500

I was thinking it would be nice to handle the cases by generating all possible ranges and then just filtering out the ones with negative/zero length. So you wouldn’t need any conditional code.

But I think that doesn’t quite cover everything.

Day 6 - first time not having to rewrite the main loop for part 2!

2 Likes
501

Okay, I changed my mind and did take a quick look.

In my code, the first case is just to cover the possibility of no overlap and skip the rest of the checks early. I think it might not be the most efficient way to handle it, and maybe your code is demonstrating a better way with applying the chain of if conditions, of which multiple can be active at the same time, but I haven’t analyzed it.

1 Like
502

I think that’s a really good idea. So, I guess something like this would work:

# These point to one after the actual end
seed_end   = seed_start   + seed_size
source_end = source_start + source_size

overlap_start = max(seed_start, source_start)
overlap_size  = min(seed_end, source_end) - overlap_start
if overlap_size > 0:
    mapped_start = overlap_start + destination_start - source_start
    mapped.append([mapped_start, overlap_size])

pre_size = min(seed_end, source_start) - seed_start
if pre_size > 0:
    unmapped.append([seed_start, pre_size])

post_start = max(seed_start, source_end)
post_size = seed_end - post_start
if post_size > 0:
    unmapped.append([post_start, post_size])

Edit: modified to add the actual mapping operation (shifting to destination)

3 Likes
503

First gold medal on our little leaderboard for me!

Clean way of getting the level of the hand for sorting 
def ranker(cards):
    nums = tuple(to_num(c) for c in cards)
    type = [ nums.count(i) for i in set(nums) ]
    type.sort(reverse = True)
    return (type, nums)

But then of course it got really ugly for part 2.

3 Likes
504

Day 8 part 2

When the puzzle input opened in my web browser it tried to translate LLLRLRRRLRLRLRR into Welsh. :rofl:

Spoiler

After burning my CPU for a good 10 minutes, thought there must be a better way.
Then it hit me, and found a LCM calculator.

2 Likes
505

Mine is offering to translate the puzzle input from Vietnamese.

I was going to say I don’t know what you mean, but after I finally thought about this puzzle for a minute I might have some idea. Gotta optimize my part 1 code a bit first since that already took a few minutes to run on the Pico.

2 Likes
506
Solution Discussion for Day 8 Part 2

I’m guessing that I might have done something similar to @April_in_Paris. First, I tried to iterate and check all simultaneously, and realized that it was not working after a few minutes. Then, considering that the answer to my first part had 5 digits and there were 6 parallel tracks, I figured that it was probably wildly infeasible to brute force this way. The eventual solution had 14 digits.

So, I handled each of the six tracks individually and found the number of steps for when they each first reached an end point. Then, I hastily made the flawed assumption that these numbers corresponded to the periodic cycle of each track reaching an end point. So, I added a line to calculate the LCM, got a result, and just then I realized that it might not be so simple. However, since I anyways had a number, I put it into the advent website, and it surprisingly accepted it as correct.

I was expecting it to be rejected, and having to do a more careful cycle analysis, since the cyclical nature of each track could in principle be more complicated.

Since it is a finite state machine (where state is both the current 3-letter node and the position in the LR instructions), each track must eventually get stuck in a repeating, cyclical pattern. However, this eventual cycle does not necessarily need to include the starting point (or some initial part of the track’s sequence), and this cycle might even visit multiple end points. Given these possible generalities, the simple approach suggested above seems unlikely to work.

TL;DR: I think I just got lucky that my flawed solution somehow worked. Or maybe the problem was specifically designed for that to be the case?

4 Likes
507
Day 8 part 2

From looking at some other solutions, it seems like the input was indeed designed to reward making several (a priori) incorrect assumptions?? Very strange choice.

When I first looked at part 2 this morning, I was about to do a simple LCM, then realized why that won’t work. I put the problem to the side during the day and figured I would implement it properly when I got home in the evening. Seeing now that the simpler solution just randomly works kind of takes the fun out of it :frowning_face:

1 Like