Calendrier de l'avent 🎄 (mais sans chocolats)

[Ewi]

64 793 042 714 624 pour moi.

[viewww]

j’avais oublié qu’à chaque fois que je push mon code sur Github, Github me relance tous les tests.

Je viens de recevoir un mail comme quoi mon test de ce matin à timeout au bout de 6h

[anon10092024]

Et voila ! Star2 reussi !
J’ai essayé avec du denombrement, mais je n’arrivais pas à m’en sortir, et j’avais la flemme de me replonger dans le théorie des graphs, du coup j’ai utilisé l’astuce de @viewww (bien vu pour l’idée !) de mémoriser les valeurs des sous graph déjà calculé. Et effectivement, je passe d’un temps d’exécution inconnu (mais très grand :D) à 3ms …

jour 10 - etoile 1 & 2

from collections import defaultdict
from datetime import datetime

def computeNode(numberList, position, history):
    pathNumber = 0
    history.append(numberList[position])
    if (position == len(numberList) - 1):
        ## on a atteind+ la fin de la liste, on a trouvé un chemin valide
        print(f"Chemin trouvee numberList[{position}]={numberList[position]} - nodeNumber={pathNumber} - history={history}")
        return(1)

    ## sinon, on explore les possibilité à partir de cette position
    for i in range(1,4):
        if position + i < len(numberList):
            ## est-ce qu'on peut utiliser cet adapteur
            if 1 <= numberList[position + i] - numberList[position] <= 3:
                subHistory = history.copy()
                pathNumber += computeNode(numberList, position + i, subHistory)
    return(pathNumber)

def computeNodeFast(numberList, position):

    if position in alreadycomputed:
        return(alreadycomputed[position])

    pathNumber = 0
    if (position == len(numberList) - 1):
        ## on a atteind+ la fin de la liste, on a trouvé un chemin valide
        return(1)

    ## sinon, on explore les possibilité à partir de cette position
    for i in range(1,4):
        if position + i < len(numberList):
            ## est-ce qu'on peut utiliser cet adapteur
            if 1 <= numberList[position + i] - numberList[position] <= 3:
                pathNumber += computeNodeFast(numberList, position + i)
    alreadycomputed[position]=pathNumber
    return(pathNumber)

start_time = datetime.now()

numberList = [0]
f = open("Z:\donnees\developpement\Python\AdventOfCode\day10.txt", "r")
for line in f:
    numberList.append(int(line.rstrip("\n")))
f.close()

## Star 1
numberList.sort()
numberList.append(numberList[-1]+3)
delta = defaultdict(lambda: 0)
previousAdaptor = numberList[0]
for i in range(1,len(numberList)):
    delta[numberList[i]-previousAdaptor] += 1
    previousAdaptor = numberList[i]
print(delta)
print(f"star1 : {delta[1]*delta[3]}")

## Star 2 : creating graph
# history = []
# print(f"star2 : {computeNode(numberList,0, history)}")
alreadycomputed={}
print(f"star2 : {computeNodeFast(numberList,0)}")

end_time = datetime.now()
print('Duration: {}'.format(end_time - start_time))

Et le résultat :

star1 : 1890
star2 : 49607173328384
Duration: 0:00:00.003999

[Mistermick]

Comme beaucoup je me suis heurté à un mur avec un temps de traitement super long.
Encore une fois faire en fonctionnel c’était dur pour moi, j’aurais tellement voulu une variable globale pour stocker mes valeurs de sous graphes.
J’ai pensé trimbaler un accumulateur tout le long des exécutions, je pense que ça aurait marché mais ça m’a pris la tête.
Du coup j’ai juste passé le cache à la fonction sans lui donner la charge de le maintenir, le cache est géré en dehors de la fonction que j’ai appelé plein de fois avec des listes de plus en plus grandes, jusqu’à la liste de l’exercice.

C’est de plus en plus moche ce que je fais haha. ^^;

Jour 10

// change big string into array of number, then sort
let formatedDataTemp = data
.split('\n')
.map(d => parseInt(d, 10))
.sort((a,b) => a - b)

// add last value which is bigest number + 3
let formatedData = [...formatedDataTemp, formatedDataTemp[formatedDataTemp.length-1]+3]

// gives the number of arrangements of given list
let calculArrangements = ([a,b,...tail]) => {
    if (typeof a === 'undefined') return 1
    if (typeof b === 'undefined') return 1
    if (a+3 > b) return calculArrangements([a,...tail])+calculArrangements([b,...tail])
    if (a+3 === b) return calculArrangements([b,...tail])
    if (a+3 < b) return 0
}

// gives the number of arrangements of given list
// a cache is given so if the list or of any sublist is present in the cache, the cache is used instead of doing the calculation 
let calculArrangementsUseCache = (cache) => ([a,b,...tail]) => {
    let inCache = cache.filter(d => d.key === JSON.stringify([a,b,...tail]))
    if (inCache.length>0) return inCache[0].val
    
    if (typeof a === 'undefined') return 1
    if (typeof b === 'undefined') return 1
    if (a+3 > b) return calculArrangementsUseCache(cache)([a,...tail])+calculArrangementsUseCache(cache)([b,...tail])
    if (a+3 === b) return calculArrangementsUseCache(cache)([b,...tail])
    if (a+3 < b) return 0

}

// calculate the number of diff of 1,2 and 3 in the list
let result1 = formatedData
.reduce((acc,d) => {
    switch (d - acc.last){
        case 1: return {...acc, last:d, diff1:acc.diff1+1}
        case 2: return {...acc, last:d, diff2:acc.diff2+1}
        case 3: return {...acc, last:d, diff3:acc.diff3+1}
        default: return acc
    }
},{last:0, diff1:0, diff2:0, diff3:0})

// add the 0 to the list
// then make sublists, first sublist has one element : the biggest number, the second has the two biggests numbers and so on
// calculate each sublist from the smallest to the biggest which is the whole list of numbers
// each calculated sublist is stored into a cache and given to next calls
let result2 = [0,...formatedData]
.reduceRight(([head,...tail],d) => {
    if (typeof head === 'undefined') return [[d]]
    return [[d,...head],...[head,...tail]]
},[])
.reverse()
.reduce((acc,d,i) => 
    [...acc, {key:JSON.stringify(d), val:calculArrangementsUseCache(acc)(d)}],[])

console.log(result1.diff1 * result1.diff3)
console.log(result2[result2.length-1].val)

[zepostman]

Moi attendant que mon algo récursif pour le 10-2 se termine

Au final j’ai conservé mon algo mais au lieu de l’appeler une fois pour l’ensemble du tableau de valeur, je l’ai appelé sur des sous ensembles, et j’ai multiplié les résultats trouvés pour chaque. Pas très opti mais ça a marché.

[deneb]

Le jour 11 est relativement abordable pour les deux parties. J’ai hâte de voir le code de ceux qui affectionnent l’élégante programmation fonctionelle, parce que là mon code il pique les yeux

[Greytarkis]

je reviens sur le jour 10 pour partager ça (auteur anonyme) : https://pastebin.com/65t5G3Ge

Une petite animation de la solution.

(et pourquoi personne utilise le caching en python ? vous faites tous des histos custom D: @lru_cache https://docs.python.org/3/library/functools.html )

*** DAY 11 ***

N’oubliez pas que vous calculez pour l’état précédent afin de savoir si un siège devient libre.

[viewww]

Bonjour

[Xerto]

Part 1 faite, par contre ma part 2 dure une éternité sur l’exemple… J’ai dû loupé un truc (on est vendredi, ça doit être ça)

Part 1

def wait_for_still_1(puzzle):
    change = True
    neigh_diffs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    while change:
        change = False
        new_puzzle = [r.copy() for r in puzzle]
        for r in range(0, len(puzzle)):
            row = puzzle[r]
            for i in range(0, len(row)):
                if row[i] == ".":
                    continue
                neighs = [puzzle[r+d[0]][i+d[1]] for d in neigh_diffs
                          if 0 <= r+d[0] < len(puzzle)
                          and 0 <= i+d[1] < len(row)]
                if row[i] == "L" and neighs.count("#") == 0:
                    new_puzzle[r][i] = "#"
                    change = True
                elif row[i] == "#" and neighs.count("#") > 3:
                    new_puzzle[r][i] = "L"
                    change = True
        puzzle = [r.copy() for r in new_puzzle]
    print(f"Occupied seats: {''.join([''.join(r) for r in puzzle]).count('#')}")

[viewww]

Je viens de finir la part1, c’est assez verbeux mais j’aime bien quand le code est expressif

Voici mon code : part1

[Xerto]

Bon je m’en suis sorti, j’avais mal nommé mes variables. Je fais un peu de refactor et je pousse ça sur GitHub. Par contre je suis lent (2.8s).

[viewww]

j’ai pas commencé la part2, mais déjà la part1 prend chez moi presque une seconde …

[Xerto]

Et donc solution factorisé sur GitHub en Python.

[Ewi]

j’ai pas encore regardé en détail mais on dirait un jeu de la vie++ ?

[viewww]

oui c’est une sorte d’automate cellulaire

[canard]

De mon côté j’ai atteint hier avec la deuxième partie du problème le niveau où ça me prends beaucoup trop de temps pour arriver à une solution. Je pense que je vais m’arrêter là

[Ewi]

Version barbar:

Résumé

import copy 

def printData(data,swap):
    for i in range(0, len(data) ):
        for j in range(0, len(data[i]) ):
            print(data[i][j][swap],end="")
        print()


def countAdjacent(data,x,y,swap):
    seat=0
    for i in range(x-1, x+2):
        for j in range(y-1, y+2):
            if i!=x or y !=j:
                if data[i][j][swap]=='#':
                    seat+=1
    return seat

def countInView(data,x,y,swap):
    seat=0
    for i in range(x-1, x+2):
        for j in range(y-1, y+2):
            if i != x or y != j:
                diffi=i
                diffj=j
                while 1 <= diffi < len(data)-1 and 1 <= diffj < len(data[x])-1 and data[diffi][diffj][swap] == '.':
                    diffi+=i-x
                    diffj+=j-y
                if data[diffi][diffj][swap]=='#':
                    seat+=1
    return seat

def day10_1(data,gen,countfunction,maxAdjacent):
    swap=0
    for k in range(0,gen):
        modif=False
        nbSeat=0
        for i in range(1,len(data)-1):
            for j in range(1,len(data[i])-1):
                adjacent = countfunction(data,i,j,swap)
                if data[i][j][swap]=='L':
                    if adjacent==0:
                        data[i][j][(swap+1)%2]='#'
                        modif=True
                    else:
                        data[i][j][(swap + 1) % 2]=data[i][j][swap]
                elif data[i][j][swap] == '#':
                    nbSeat+=1
                    if adjacent >=maxAdjacent:
                        data[i][j][(swap + 1) % 2] = 'L'
                        modif=True
                    else:
                        data[i][j][(swap + 1) % 2] = data[i][j][swap]
                else:
                    data[i][j][(swap + 1) % 2] = data[i][j][swap]

        if not modif:
            return nbSeat
        swap = (swap+1)%2

# main
if __name__ == '__main__':
    fichier = open('input.txt', 'r')
    linesDeMonFichier = fichier.read().splitlines()
    data = [ [['.','.']]+[[char,''] for char in i]+[['.','.']] for i in linesDeMonFichier]
    data = [[['.','.'] for char in data[0]]] + data + [[['.','.'] for char in data[0]]]

    data2=copy.deepcopy(data)
    r = day10_1(data, 100, countAdjacent, 4)
    print(r)
    r = day10_1(data2,100,countInView,5)
    print(r)

[viewww]

J’ai terminé à mon tour, pas de finesse algorithmique, mais j’ai fait en sorte de faire du code modulaire pour réutiliser un maximum de code de la part1 pour la part2

Mon code : part1 / part2

[viewww]

Mais comment vous vous y retrouvez dans cette cascade de boucles et de tableaux ?

[Ewi]

Si tu veux, je peux tout mettre en liste compréhension

et t’as aussi des trucs étrange :