Calendrier de l'avent 🎄 (mais sans chocolats)

[Xerto]

On repasse sur des choses un peu plus simples, qui devraient nous rappeler le début du mois de décembre.
Ma solution en Python sur GitHub, j’ai rien optimisé et tant que le buffer est petit (25) je ne pense pas que ça vaille vraiment le coup. On pourrait maintenir une liste des sommes existantes plutôt que de les recalculer à chaque fois dans mon cas, mais là le code prend 8ms, j’ai un peu la flemme d’écrire plus de code

[viewww]

hello je viens de lire la part1, ca n’a pas l’air trop méchant. A voir s’il y a un twist part2

[deneb]

Non, même pas. On verra si ça se corse demain !

[viewww]

Hop j’ai réussi. Il a fallu faire un tout petit peu d’optimisation (streams) pour s’arrêter dès qu’on trouve une solution convenable. Sinon calculer toutes les combinaisons peut prendre jusqu’à 5 secondes.

Part1 / Part2

[Donjohn]

J’ai fait part 1, mais bourrinement, je calcule les sum nécessaires et je cherche dans le tableau de resultat

Mais je pense que Day5 devrait nous aider à aller plus vite…

Day 9 part 1 PHP

    /**
     * @return int
     */
    public function day9part1(): int
    {
        $lines = $this->getFile('day9.txt');
        $max = count($lines)-25;

        for($i=25; $i<$max; $i++)
        {
            if (!$this->isSumOfPrevious($i, $lines)) {
                return $lines[$i];
            }
        }


        return 0;
    }


    /**
     * @param int $index
     * @param array $entries
     *
     * @return bool
     */
    private function isSumOfPrevious(int $index, array $entries): bool
    {
        $valueToFind = (int)$entries[$index];
        $values = array_splice($entries, $index-25, 25);
        sort($values);
        for($i=0; $i<25; $i++)
        {
            for($j=$i+1; $j<25; $j++)
            {
                if ((int)$values[$i]+(int)$values[$j] === $valueToFind) {
                    return true;
                }
            }
        }
        return false;
    }

[zepostman]

@anon10092024

J’ai bloqué un moment sur l’étoile 2 avant de comprendre que dict.copy() conserve le pointeur sur les inner list

Tain j’ai bloqué je sais pas combien de temps sur ce problème aussi.
Je voyais pas ce qui clochait dans mon algo et comme j’avais pensé à faire le copy() je me suis pas méfié.

[viewww]

@Donjohn

J’ai fait part 1, mais bourrinement, je calcule les sum nécessaires et je cherche dans le tableau de resultat

j’ai fait cette première version, puis j’ai utilisé l’API de stream d’Elixir (j’imagine que php à un équivalent ?) qui permet, en ne demandant à consommer qu’un seul élément du stream, d’arrêter de calculer les combinaisons dès qu’on a un résultat.

[Donjohn]

Je dis n’importe quoi, c’était ma première idée, mais c’était trop bourrin donc je m’arrête désormais au premier calcul trouvé.

[anon10092024]

hop, Jour 9 completé. Par contre c’est hyper rapide chez moi sans optimisation, je suis à 0.089s pour sortir les deux étoiles. La combinatoire n’est pas si forte je trouve.

@Donjohn : pourquoi tu calcules toutes les sommes necessaires ? Il suffit de tester les sommes deux à deux en commencant dans le range (preamble-25 : end) et de t’arreter à la premiere. C’est ce que j’ai fais et c’est super rapide.

Jour 9 (Python)

def testNumber(liste, testNumber):
    for i in range(len(liste)):
        for j in range(i+1, len(liste)):
            if liste[i]+liste[j] == currentNumber:
                return True, liste[i], liste[j]
    return False, -1, -1

def testSequenceFromIndex(liste, invalideNumber, index):
    currentSum = 0
    for i in range(index, len(liste)):
        currentSum += liste[i]
        if currentSum == invalidNumber:
            return True, i+1
        elif currentSum > invalidNumber:
            return False, -1
    return False, -1

numberList = []
preamble = 25
f = open("Z:\donnees\developpement\Python\AdventOfCode\day9.txt", "r")
numberRead = 1
for line in f:
    currentNumber = int(line.rstrip("\n"))

    ## preamble numbers : initializing the list of available numbers
    if numberRead <= preamble:
        numberList.append(currentNumber)
        #print("#{0}={1} - preamble not completed, adding it to availableNumbers".format(numberRead, currentNumber))
    else:
        ## validating number : is it the sum of two numbers in the premable last number of the list
        testResult, a, b = testNumber(numberList[-preamble:], currentNumber)
        if testResult:
            numberList.append(currentNumber)
            #print("#{0}={1} - number valide - is the sum of {2} and {3}".format(numberRead, currentNumber, a, b))
        else:
            invalidNumber = currentNumber
            print("Star 1 : {1} - #{0}={1} - number NOT valide".format(numberRead, invalidNumber, a, b))
            break
    numberRead += 1
f.close()

## Star 2 : looking for a set of addition with all previous numbers :
for i in range(len(numberList)):
    testResult, shift = testSequenceFromIndex(numberList, invalidNumber, i)
    if testResult:
        listResult = numberList[i:shift]
        print("Star 2 : {1} - sublist={0}".format(listResult, min(listResult) + max(listResult)))
        break

Et le résultat :

Star 1 : 105950735 - #565=105950735 - number NOT valide
Star 2 : 13826915 - sublist=[4117189, 4154061, 4424828, 4208390, 5060031, 4391939, 8942999, 5977809, 8491671, 5334788, 8808360, 5708469, 7418529, 5800654, 9709726, 6431377, 6969915]
[Finished in 0.089s]

[Donjohn]

@anon10092024 parceque j’ai dit de la merde et que je m’arrete evidemment au premier trouvé…

Sinon trouvé part2, je deplace une sorte de somme dans la liste. Je calcule une seule fois une somme et j’ajoute/enleve la fin ou le debut si c’est trop petit ou trop grand. C’est ultra rapide 0.0005ms alors que part1 me prend 0.013ms.

Day 9 part 2 PHP

        $value = $this->day9part1();
        $lines = $this->getFile('day9.txt');
        $start=0;
        $end=0;
        $removeStart=true;
        $pendingSum=0;

        while($pendingSum!==$value)
        {
            if ($pendingSum>$value)
            {
                if ($removeStart) {
                    $pendingSum-=(int)$lines[$start++];
                } else {
                    $pendingSum-=(int)$lines[--$end];
                }
                $removeStart=false;
            } else {
                $removeStart=true;
                $pendingSum+=(int)$lines[$end++];
            }

        }

        $lines = array_splice($lines, $start, ($end-$start));

        return min($lines)+max($lines);

[Ewi]

Pas le temps de faire autre chose que du bourrin :

Résumé

def check_number(data,n):
    for i in data:
        for j in data:
            if i!=j:
                if n == i+j:
                    return True
    return False

def day9_1(data):
    buffer = 25
    subData = data[0:buffer]

    for i in data[buffer:]:
        if not check_number(subData,i):
            return i
        subData.pop(0)
        subData.append(i)
    return None

def day9_2_process(data,n):
    for i in range(0,len(data)):
        sum = n
        for j in range(i,len(data)):
            sum-=data[j]
            if sum == 0:
                return i,j
            if sum < 0:
                break
    return None, None

def day9_2(data,n):
    i,j = day9_2_process(data,n)
    if i is not None:
        return max(data[i:j])+min(data[i:j])
    return -1

if __name__ == '__main__':
    fichier = open('input.txt', 'r')
    lignes = fichier.read().splitlines()
    data = [int(i) for i in lignes]
    res = day9_1(data)
    print(res)
    
    res = day9_2(data,res)
    print(res)

[anon10092024]

Tu peux optimiser vachement ton check number en calculant seulement i+j et pas j+i .

Au lieu de deux boucle for qui testent tout les chiffres, il suffit de faire la deuxieme boucle for sur le range (i+1, len(data)). Ca t’evite aussi de tester i == j.

La combinatoire passe de n² à n(n-1)/2

[Ewi]

Yep. Je fais pas semblant sur le bourrin ;).

[Mistermick]

J’ai galéré aujourd’hui avec ma programmation fonctionnelle, j’aurais rêvé de pouvoir utiliser une boucle T_T
C’est même pas très joli comme code et pas optimisé non plus, j’étais plus satisfait de ce que j’ai rendu les jours précédents.
Sinon je me suis aperçu que les dernières versions de nodeJS ne gèrent plus la tail call optimisation, donc si je fais trop d’appels récursifs ça plante, au moins ça m’évite d’être trop bourrin dans mon approche.

Jour 9

let formatedData = data
.split('\n')
.map(d => parseInt(d, 10))

// get all possible addition of two values from a list of values
let getAllSumsRec = (acc) => (first) => (second) => (list) => {
    if(first >= list.length) return acc 
    if(second >= list.length) return getAllSumsRec(acc) (first+1) (first+2) (list) 
    return getAllSumsRec([...acc, list[first] + list[second]]) (first) (second+1) (list)
}

let getAllSums = getAllSumsRec([])(0)(1)

// get the first and second index from a list for which continuous sum gives the tested val
// if no match, return false
let getContiguousSumRec = (first) => (list) => (testedVal) => {
    // exit when all elements are tested
    if(first >= list.length) return false 
    
    // test sums starting from "first" index
    // return an object : {found:true, sum:1234, index:123}
    // the index is relative to first index, add first+1 to get absolute index
    let sum = list
    .slice(first+1)
    .reduce((acc,d,i) => {
        if (acc.found) return acc
        if (acc.sum + d === testedVal) return {found:true, sum:acc.val+d, index:i}
        return {...acc, sum:acc.sum+d}
    },{found:false, sum:list[first]})

    // if found, return the first and second index (translated to absolute position)
    if (sum.found) return {first:first, second:first+sum.index+1}
    return getContiguousSumRec(first+1)(list)(testedVal)
}

let getContiguousSum = getContiguousSumRec(0)

// test all indexes starting from 26 where the addition of two among any of the 25 previous numbers is the number at tested position
// return the first failed index
let result1 = 
    formatedData
    .reduce((acc,d,i,data) => {
        if (acc > 0) return acc
        if (data.slice(i-25,i).length > 0 && !getAllSums(data.slice(i-25,i)).includes(d)){
            return i
        } else {
            return 0
        }
    } ,0)

console.log(formatedData[result1])

// get the first and second index position for which 
// when we sum the elements inside the list from first to second index 
// it gives the failed number
let indexes = getContiguousSum(formatedData.slice(0,result1))(formatedData[result1])

// get the min and max value from the list between first and second index included
let result2 = formatedData
.slice(indexes.first, indexes.second+1)
.reduce((acc,d,i) => {
    if (i === 0) return {min:d, max:d}
    if (d > acc.max) return {...acc, max:d}
    if (d < acc.min) return {...acc, min:d}
    return acc
},{})

console.log(result2.min + result2.max)

[viewww]

J’ai fait mon geek, j’ai créé une petite tache mix (un script Elixir) pour me créer les fichiers du jour et télécharger le puzzle input depuis adventofcode.com

le code ici

[deneb]

Le Day 10 part 1 est assez trivial, mais le part 2 est intéressant !

Un moyen d’avancer pour ceux qui auraient du mal à démarrer:

Le lien StackExchange qui va bien

https://math.stackexchange.com/questions/284700/maximum-number-of-path-for-acyclic-graph-with-start-and-end-node

[viewww]

Tu es bien matinal

part1 est ptet pas bien compliqué mais il faut relire l’énoncé 10x quand même !

[deneb]

@viewww

Tu es bien matinal

Pas vraiment, disons que chez moi il est 13h quand les challenges arrivent, ça aide à être bien réveillé

[viewww]

haha alors c’est moi qui suis matinal
bon j’ai réussi part1 et part2 fais mal à la tête,j’'y reviendrai plus tard !

[deneb]

Allez zou, mon code pour la Part 2.

Soyez indulgents, c’est du Kotlin et j’en ai écrit ma première ligne il y a 2 jours quand j’ai commencé cet Advent of Code.

Day 10 Part 2

fun main() {

    val valuesFromFile = File("c:\\Temp\\input10.txt").readLines().map { it.toInt() }.sorted()
    // Adding initial 0 for outlet and last max adapter + 3 value for built-in device adapter
    val jolts: List<Int> = listOf(0) + valuesFromFile + (valuesFromFile.last() + 3)
    val nodes = jolts.map { JoltNode(it) }

    // Building Edges
    nodes.forEachIndexed { i, joltNode ->
        for (j in 1..3) {
            val nextIndex = i + j
            if (nextIndex < nodes.size) {
                val nextJoltNode = nodes[nextIndex]
                if (nextJoltNode.value - joltNode.value <= 3) {
                    joltNode.addChild(nextJoltNode)
                }
            }
        }
    }

    // Summing weights along backtracking path, last node starts with weight 1
    nodes.last().weight = 1L

    for (i in nodes.size - 2 downTo 0) {
        val joltNode = nodes[i]
        joltNode.children.forEach {
            joltNode.weight += it.weight
        }
    }

    println(nodes.first().weight)
}

class JoltNode(_value: Int) {
    var value = _value
    var weight: Long = 0
    val children = mutableListOf<JoltNode>()
    fun addChild(child: JoltNode) {
        children.add(child)
    }
}