J'ai bien aimé la première partie du prechall.
Cela m'a rappelé l'époque où pour tricher dans les jeux. On allait modifier la mémoire ou le code.
La deuxième partie est en python. Et c est ce qui m a fait perdre beaucoup de temps.
C'est un classique des challenges de programmation mais je l'ai pris de travers…
Les catégories introduction sont en général à la portée de tous.
En général, les 1 étoiles me prennent en général 1 à 4h.
Au-dessus, les 2 étoiles, j arrive à en avoir quelques une
Les 3 étoiles, je ne suis pas sûr d en avoir eu une pendant le concours mais je suis toujours très intéressé de découvrir les write-up une fois le concours terminé.
Je suis du même avis.
On arrive sur ce genre de phase où il y a une restructuration de l'activité.
Mais ça ne va pas durer.
Il faudra probablement apprendre à revaloriser ses compétences ou revoir ses préférences techniques.
Mais dans l'ensemble l'IA va augmenter la taille des SI et leur complexité.
Résultat, on va passer moins de temps à coder et plus de temps en réunions de coordination.
Les véritables compétences à revaloriser. Ça va être :
- Les softskills: organisation, la motivation, la communication et le sens du service
- la modélisation système
- L'administration système.
Je trouve que ma condition de sortie est un peu moisie mais dans l'ensemble.
En gros, j'arrête le programme quand j'arrive à une contraction à 2 noeud avec 3 lien qui sont les 3 liens à couper.
C'était la solution attendu. Je n'ai pas cherché plus loin.
Le solve du z3 se charge de trouver la solution des systèmes d'équation.
Vu que je suis plus habitué à Java pour le parsing du input , j'ai écrit un petit programme qui me génère le code typescript attendu par le solver Z3.
La première version pouvait directement s'éxecuter dans la sandbox https://microsoft.github.io/z3guide/programming/Z3%20JavaScript%20Examples/
On peut aussi l'éxecuter en locale de cette manière:
Via package.json
J'ai enfin ma solution pour le jour 20.
1) J'ai exploré plusieurs solutions comme laisser mon PC calculé à l'aveugle pendant 1j de travail. Je chauffe en partie à l'électrique. Donc, cela ne me coutait pas de laisser mon PC cramer des Watt :).
2) J’ai tenté de simplifier les cycles des flip-flop sans grand succès. Car je pensais que les conjuctions serait beaucoup plus complexe avec leurs multiples false, true qu’elles crachent
3) Via récursivité de trouver une méthode pour factoriser les circuits. Je n’ai pas vu la solution suivante toute suite, car ma fonction recursive allé jusqu’au flip / flop. Mais au final,c’était trop complexe pour trouver une simplification évidente.
4) Finalement, j’ai tenté juste de regarder les cycles des trues sur les 4 conjonctions qui sont avant RX { "hz", "pv", "qh", "xm" }
Et là, c’était évident. J’avais des cycles réguliers pour ces 4 conjonctions. Il ne me reste plus qu’à trouver quand elles sont à true toutes les 4 en même temps. Ce qui revient à trouver le PPCM des 4 cycles.
J’ai demandé à chatgpt de me fournir le calcul d’un PPCM (çà se reconnait au style).
En prenant, le problème dans le bon sens, j’aurai pu le résoudre en 1h partie 1 et partie 2…. J’ai mis encore bien 5h cumulé.
publicclassAoc2023s20v3{publicrecordMessage(StringsourceName,booleanhight,Componentcomponent){}// Hard coded main conjunctionprotectedstaticfinalString[]CHECK_MAIN_RX_CONJUNCTION=newString[]{"hz","pv","qh","xm"};// Function to find the GCD (Greatest Common Divisor) of two numbersprivatestaticlongfindGCD(longa,longb){while(b!=0){longtemp=b;b=a%b;a=temp;}returna;}// Function to find the LCM (Lowest Common Multiple) of two numbersprivatestaticlongfindLCM(longa,longb){return(a*b)/findGCD(a,b);}// Function to find the LCM of an array of numberspublicstaticlongfindLCMOfArray(Long[]numbers){if(numbers.length==0){thrownewIllegalArgumentException("Array should not be empty");}longlcm=numbers[0];for(inti=1;i<numbers.length;i++){lcm=findLCM(lcm,numbers[i]);}returnlcm;}publicstaticabstractclassComponent{Stringname;String[]targetNames=newString[0];publicMap<String,Message>getMessageHight=newHashMap<>();publicMap<String,Message>getMessageLow=newHashMap<>();privateMessage[]sendTrue;privateMessage[]sendFalse;publicHashMap<Long,List<Boolean>>signalHistory=newLinkedHashMap<>();publicComponent(Stringname){this.name=name;}publicvoidregisterInput(Stringname){}publicvoidclear(){}publicvoidprocess(Circuitcircuit,Messagemessage){}publicfinalvoidsend(Circuitcircuit,booleansendSignalHight){Message[]toSend;if(sendSignalHight){if(sendTrue==null){sendTrue=Arrays.stream(targetNames).map(target->newMessage(this.name,sendSignalHight,circuit.elementsByName.get(target))).toArray(k->newMessage[k]);}toSend=sendTrue;}else{if(sendFalse==null){sendFalse=Arrays.stream(targetNames).map(target->newMessage(this.name,sendSignalHight,circuit.elementsByName.get(target))).toArray(k->newMessage[k]);}toSend=sendFalse;}if(thisinstanceofConjuction&&sendSignalHight)signalHistory.computeIfAbsent((long)circuit.circuitIndex,(k)->newArrayList<Boolean>()).add(sendSignalHight);ArrayDeque<Message>messages=circuit.messages;for(Messagetarget:toSend){messages.add(target);}}publicStringexpr(Circuitcircuit){returnthis.name;}}publicstaticclassFlipFlopextendsComponent{booleanstate;publicFlipFlop(Stringname){super(name);}@Overridepublicvoidclear(){state=false;}@Overridepublicvoidprocess(Circuitcircuit,Messagemessage){if(message.hight){// do nothingreturn;}this.state=!state;send(circuit,this.state);}@OverridepublicStringtoString(){return"FlipFlop [state="+state+", name="+name+", targetNames="+targetNames+"]";}publicStringexpr(Circuitcircuit){return"%"+this.name;}}publicstaticclassConjuctionextendsComponent{privatelongstate=0;privatelongallUp=0;privateMap<String,Long>inputMask=newHashMap<>();privateMap<String,Long>notInputMask=newHashMap<>();publicConjuction(Stringname){super(name);}@OverridepublicvoidregisterInput(Stringname){intnextId=inputMask.size();longmask=1L<<nextId;inputMask.put(name,mask);notInputMask.put(name,~mask);allUp=(1L<<(nextId+1))-1;}@Overridepublicvoidprocess(Circuitcircuit,Messagemessage){if(message.hight){longmask=inputMask.get(message.sourceName);state=state|mask;}else{longnotMask=notInputMask.get(message.sourceName);state=state¬Mask;}varnotAllTrue=state!=allUp;send(circuit,notAllTrue);}@OverridepublicStringtoString(){return"Conjuction [name="+name+", targetNames="+targetNames+"]";}publicStringexpr(Circuitcircuit){return"/*"+this.name+"*/("+this.inputMask.keySet().stream().map(n->circuit.elementsByName.get(n).expr(circuit)).collect(Collectors.joining(" & "))+") \n";}}publicstaticclassOutputextendsComponent{privatelongcountHight;privatelongcountSmall;publicOutput(Stringname){super(name);}@Overridepublicvoidclear(){this.countHight=0;this.countSmall=0;}@Overridepublicvoidprocess(Circuitcircuit,Messagemessage){if(message.hight)countHight++;elsecountSmall++;}@OverridepublicStringtoString(){return"Output [countHight="+countHight+", countSmall="+countSmall+", name="+name+", targetNames="+targetNames+"]";}}publicstaticclassCircuit{Map<String,Component>elementsByName=newHashMap<>();String[]broadcastList=newString[0];ArrayDeque<Message>messages=newArrayDeque<>();longcountHight;longcountLow;longcircuitIndex=0;voidparse(Scannerin){while(in.hasNext()){Stringrow=in.nextLine();String[]part=row.split("->");StringtypeName=part[0].trim();String[]targetNames=Arrays.stream(part[1].trim().split(",")).map(String::trim).toArray(k->newString[k]);if("broadcaster".equals(typeName)){broadcastList=targetNames;}elseif(typeName.startsWith("%")){FlipFlopflipFlop=newFlipFlop(typeName.substring(1));flipFlop.targetNames=targetNames;elementsByName.put(flipFlop.name,flipFlop);}elseif(typeName.startsWith("&")){Conjuctionc=newConjuction(typeName.substring(1));c.targetNames=targetNames;elementsByName.put(c.name,c);}}elementsByName.put("output",newOutput("output"));elementsByName.put("rx",newOutput("rx"));for(Componentsource:elementsByName.values()){for(Stringtarget:source.targetNames){Componentrx=elementsByName.get(target);if(rx!=null){rx.registerInput(source.name);}}}for(Stringtarget:broadcastList){elementsByName.get(target).registerInput("broadcast");}}publiclongexperienceToFindWhereRxIsUp(longcount){messages.clear();elementsByName.values().forEach(Component::clear);countHight=0;countLow=0;longs=System.currentTimeMillis();intx=0;while(true){circuitIndex=x;countLow++;for(Stringinitial:broadcastList){messages.add(newMessage("broadcast",false,elementsByName.get(initial)));}processMessages();if(x>count){System.out.println("seek "+x+" "+(System.currentTimeMillis()-s)+"ms");s=System.currentTimeMillis();returntryToFindLcmInMainConjuction();}x++;}}privatelongtryToFindLcmInMainConjuction(){List<Long>toComputeLcm=newArrayList<>();for(Stringname:CHECK_MAIN_RX_CONJUNCTION){Componentc=elementsByName.get(name);System.out.println(c.name+" => "+c.signalHistory.keySet());Longprevious=null;LongpreviousDiff=null;for(Longl:c.signalHistory.keySet()){if(previous!=null){longdiff=l-previous;System.out.print((l-previous)+",");if(previousDiff!=null){if(diff==previousDiff){toComputeLcm.add(diff);}else{System.out.println("Can't compute LCM");}}previousDiff=diff;}previous=l;}System.out.println();}returnfindLCMOfArray(toComputeLcm.toArray(newLong[toComputeLcm.size()]));}privatevoidprocessMessages(){while(!messages.isEmpty()){Messagemessage=messages.pollFirst();if(message.hight){countHight++;}else{countLow++;}message.component.process(this,message);}}}publicstaticvoidmain(String[]args){try(Scannerin=newScanner(Aoc2023s18v2.class.getResourceAsStream("res/t20.txt"))){Circuitcircuit=newCircuit();circuit.parse(in);longresult=circuit.experienceToFindWhereRxIsUp(20000);System.out.println(result);}}}
Pour la partie 1 , j'ai appliqué un bête parcours en profondeur.
Pour la partie 2, j'ai laissé tourner ma solution de partie 1 pour trouver la max de la partie 2.
Environ 1h de calcul.
J'aurai bien essayé de faire un truc plus intelligent mais je n'avais pas le temps.
Il faut quand même lancer ce code -Xss1g pour avoir une stack conséquence qui permet une récursivité aussi profonde.
packageaoc2023;importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassAoc2023s23{publicstaticPoint[]DIRECTIONS=newPoint[]{newPoint(1,0),newPoint(-1,0),newPoint(0,-1),newPoint(0,1)};publicrecordPoint(intx,inty){}publicstaticclassPath{boolean[][]walked;int[]pathX;int[]pathY;intstep=-1;publicPath(Worldworld){walked=newboolean[world.height][world.width];this.pathX=newint[world.width*world.height];this.pathY=newint[world.width*world.height];}publicvoidmove(intx,inty){walked[y][x]=true;step++;this.pathX[step]=x;this.pathY[step]=y;}publicvoidback(){if(step>=0){intx=getX();inty=getY();walked[y][x]=false;}step--;}privateintgetY(){returnthis.pathY[step];}privateintgetX(){returnthis.pathX[step];}}publicstaticclassWorld{List<String>rows;intwidth;intheight;intendx;intendy;intmaxPath=0;publicWorld(List<String>rows){this.rows=rows;this.height=rows.size();this.width=rows.get(0).length();this.endx=width-2;this.endy=height-1;}publicfinalcharcell(intx,inty){returnrows.get(y).charAt(x);}publicbooleancanWalkFrom(intsx,intsy,intdx,intdy){if(dx<0||dx>=width||dy<0||dy>=height){returnfalse;}chardest=cell(dx,dy);if(dest=='#'){returnfalse;}charstart=cell(sx,sy);returntrue;/* if (start == '.') { return true; } else if (start == '>') { return dx > sx; } else if (start == '<') { return dx < sx; } else if (start == '^') { return dy < sy; } else if (start == 'v') { return dy > sy; } throw new RuntimeException("Unsupported " + start); */}publicvoidexplore(Pathpath){intsx=path.getX();intsy=path.getY();if(sx==endx&&sy==endy){System.out.println("Size:"+path.step);if(path.step>maxPath){maxPath=path.step;}return;}for(inti=0;i<DIRECTIONS.length;i++){Pointp=DIRECTIONS[i];intdx=sx+p.x;intdy=sy+p.y;if(canWalkFrom(sx,sy,dx,dy)&&!path.walked[dy][dx]){path.move(dx,dy);explore(path);path.back();}}}}publicstaticvoidmain(String[]args){try(Scannerin=newScanner(Aoc2023s23.class.getResourceAsStream("res/t23.txt"))){List<String>rows=newArrayList<>();while(in.hasNext()){Stringrow=in.nextLine();rows.add(row);}Worldworld=newWorld(rows);Pathpath=newPath(world);path.move(1,0);world.explore(path);System.out.println("max="+world.maxPath);}}}
Posté par syj .
En réponse au message Advent of Code 2023, jour 21.
Évalué à 1.
Dernière modification le 23 décembre 2023 à 02:37.
J'ai implémenté la méthode avec séquence quadratique de Guillaume B.
Je suis un peu décu de ne pas avoir trouvé par moi-même
Mais je suis très heureux d'avoir découvert ce point des maths que je ne connaissais pas.
packageaoc2023;importjava.util.ArrayList;importjava.util.HashSet;importjava.util.List;importjava.util.Scanner;importjava.util.Set;publicclassAoc2023s21s3{publicstaticPoint[]DIRECTIONS=newPoint[]{newPoint(1,0),newPoint(-1,0),newPoint(0,-1),newPoint(0,1)};publicrecordPoint(intx,inty){}publicstaticclassState{Set<Point>current=newHashSet<>();;Set<Point>next=newHashSet<>();;char[][]map;intwidth;intheight;List<Long>quadraticsSeries=newArrayList<>();publicvoidpropagate(Pointp){for(Pointmove:DIRECTIONS){intdx=p.x+move.x;intdy=p.y+move.y;intrx=dx%width;if(rx<0){rx+=width;}intry=dy%height;if(ry<0){ry+=height;}Pointnp=newPoint(dx,dy);if(map[ry][rx]=='.'){next.add(np);}}}publiclongpropagate(Worldworld,intstep){map=world.map;width=world.width;height=world.height;// gridSize d'une taille arbitaire suffisant propage au moins une grille complète (à priori)intgridSize=width*2;// étape pour lesquels on va récupérer les valeurs de u(n) pour la séquence quadratique.intsame=(step-1)%gridSize;intend=same+gridSize*2+1;// Boucle de propagation (très inefficace) System.out.println("Propagation maximum à calculer :"+end);for(inti=0;i<end;i++){next.clear();current.forEach(p->propagate(p));// switchSet<Point>tmp=next;next=current;current=tmp;if(i>=0&&(i%(gridSize))==same){System.out.println("u("+current.size()+") = "+current.size());quadraticsSeries.add((long)current.size());}}longd1=quadraticsSeries.get(1)-quadraticsSeries.get(0);longd2=quadraticsSeries.get(2)-quadraticsSeries.get(1);//long d3 = quadraticsSeries.get(3) - quadraticsSeries.get(2);System.out.println("dp:"+(d2-d1));//System.out.println("dp:" + (d3-d2)); // si la séquence est quadratique d2-d1 == d3-d2 == d4-d3 ...longa=(d2-d1)/2;longc=quadraticsSeries.get(0);// a n^2 + b n + c = u(n) // b = (u(n) - a n^2 - c)/nintn=2;doubleb=(quadraticsSeries.get(n)-a*n*n-c)/n;System.out.println(quadraticsSeries);System.out.println(a+","+b+","+c);/* // Vérifie via la propagation jusqu'à u(3) que la formule u(n) = a*x^2 + bx+c est bien paramétré. n = 3; long control3 = (long)(a * n * n + n * b + c); System.out.println("Control3:" + control3); if(control3 != quadraticsSeries.get(3)) { throw new RuntimeException("Failed to compute u(n) = a*x^2 + bx+c "); }*/n=((step)/gridSize);return(long)(a*n*n+n*b+c);}publicbooleanmatch(intx,inty){returncurrent.contains(newPoint(x,y));}}publicstaticclassWorld{finalintwidth;finalintheight;char[][]map;Statestate=newState();publicWorld(List<String>rows){height=rows.size();width=rows.get(0).length();map=newchar[height][width];for(inty=0;y<height;y++){Stringrow=rows.get(y);for(intx=0;x<width;x++){if(row.charAt(x)=='S'){state.current.add(newPoint(x,y));map[y][x]='.';}else{map[y][x]=row.charAt(x);}}}}}publicstaticvoidmain(String[]args){try(Scannerin=newScanner(Aoc2023s21s3.class.getResourceAsStream("res/t21.txt"))){List<String>rows=newArrayList<>();while(in.hasNext()){rows.add(in.nextLine());}Worldworld=newWorld(rows);System.out.println(world.state.propagate(world,26501365));}}}
Je fatigue , il est temps que la saison se termine. J'ai encore perdu du temps sur des tests bête aux borne
Environ ~3h00 au total.
Encore obligé d'en arriver à écrire T.U. pour débuguer. Demain, je TDD, je vais probablement gagner du temps.
Pour la partie 1, j'ai utilisé un evaluator JEXL pour les expressions.
Pour la partie 2, je n'avais pas le choix. J'ai écris le "parseur" (En fait, c'est plutôt un split de l'expression) car il faut plus travailler sur des lots de pieces.
Mon objet Piece a maintenant une propriété Range que je vais split à chaque expression en 0, 1 ou 2.
Temps d'éxecution:123ms
packageaoc2023;importjava.math.BigInteger;importjava.util.ArrayList;importjava.util.Collection;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importjava.util.Random;importjava.util.Scanner;importjava.util.Stack;importorg.apache.commons.jexl3.JexlBuilder;importorg.apache.commons.jexl3.JexlContext;importorg.apache.commons.jexl3.JexlEngine;importorg.apache.commons.jexl3.JexlExpression;importorg.apache.commons.jexl3.MapContext;publicclassAoc2023s19v2{publicstaticRandomRANDOM=newRandom(0L);publicstaticJexlEnginejexl=newJexlBuilder().create();publicstaticrecordRange(intstart,intend){publiclongcount(){returnend-start;}publicRange[]split(intto){if(start>=to||to>=end){returnnull;}returnnewRange[]{newRange(start,to),newRange(to,end)};}publicRangerandom(){inti=start+RANDOM.nextInt((int)count());returnnewRange(i,i+1);}}publicstaticclassPiece{publicRangex;publicRangem;publicRangea;publicRanges;Piece(Rangex,Rangem,Rangea,Ranges){this.x=x;this.m=m;this.a=a;this.s=s;}publiclongprod(){returnx.count()*m.count()*a.count()*s.count();}@OverridepublicStringtoString(){return"Piece [x="+x+", m="+m+", a="+a+", s="+s+"]";}publicRangeget(Stringkey){returnswitch(key){case"x"->x;case"m"->m;case"a"->a;case"s"->s;default->thrownewRuntimeException();};}publicPiecesubstitute(Stringkey,Ranger){returnswitch(key){case"x"->newPiece(r,m,a,s);case"m"->newPiece(x,r,a,s);case"a"->newPiece(x,m,r,s);case"s"->newPiece(x,m,a,r);default->thrownewRuntimeException();};}}staticclassRule{Stringcondition;Stringdestination;StringattributTest;booleanattributeGreaterThan;intvalueTest;Rule(Stringcondition,Stringdestination){this.condition=condition;this.destination=destination;if(!this.condition.equals("true")){attributTest=""+this.condition.charAt(0);attributeGreaterThan=this.condition.charAt(1)=='>';valueTest=Integer.parseInt(this.condition.substring(2));}}publicbooleanmatch(Piecepiece){// Create a JEXL expression objectJexlExpressionjexlExpression=jexl.createExpression(condition);// Create a JexlContext and add the 'part' variable to itJexlContextcontext=newMapContext();context.set("x",piece.x.start);context.set("m",piece.m.start);context.set("s",piece.s.start);context.set("a",piece.a.start);// Evaluate the expressionbooleanresult=(boolean)jexlExpression.evaluate(context);//System.out.println("Evaluation result: " + result);returnresult;}publicStringtoString(){returncondition+","+destination;}publicbooleanprocess(Piecepiece,Workflowworkflow,Map<String,Workflow>workflows,List<Piece>accepts){if(condition.equals("true")){System.out.println("Default move to "+destination);getDestination(workflows,accepts).add(piece);returntrue;}Rangerange=piece.get(attributTest);System.out.println(this.condition);System.out.println(range);Rangesplit[]=range.split(attributeGreaterThan?valueTest+1:valueTest);if(split!=null){System.out.println("Splited to "+workflow.name+" & "+destination);System.out.println(split[0]+" <-> "+split[1]);if(attributeGreaterThan){getDestination(workflows,accepts).add(piece.substitute(attributTest,split[1]));workflow.pieces.add(piece.substitute(attributTest,split[0]));}else{getDestination(workflows,accepts).add(piece.substitute(attributTest,split[0]));workflow.pieces.add(piece.substitute(attributTest,split[1]));}returntrue;}else{if(attributeGreaterThan){if(range.start>valueTest){System.out.println("Greater move to ");getDestination(workflows,accepts).add(piece.substitute(attributTest,range));returntrue;}}else{if((range.end-1)<valueTest){System.out.println("Lower move to ");getDestination(workflows,accepts).add(piece.substitute(attributTest,range));returntrue;}}}returnfalse;}privateCollection<Piece>getDestination(Map<String,Workflow>workflows,List<Piece>accepts){if("A".equals(destination)){returnaccepts;}if("R".equals(destination)){returnnewArrayList();}returnworkflows.get(destination).pieces;}}staticclassWorkflow{Stringname;List<Rule>rules;Stack<Piece>pieces=newStack();Workflow(Stringname){this.name=name;this.rules=newArrayList<>();}voidaddRule(Rulerule){this.rules.add(rule);}publicStringtoString(){StringBuildersb=newStringBuilder();for(Rulerule:this.rules){sb.append(rule.toString());}returnsb.toString();}}staticMap<String,Workflow>parseInput(Scannerin){Map<String,Workflow>workflows=newHashMap<>();while(in.hasNext()){Stringline=in.nextLine();line=line.trim();if(line.isEmpty()){break;}Stringname=line.substring(0,line.indexOf('{')).trim();Workflowcurrent=newWorkflow(name);workflows.put(name,current);String[]parts=line.substring(line.indexOf('{')+1,line.length()-1).split(",");for(Stringpart:parts){String[]s=part.split(":");if(s.length==1){current.addRule(newRule("true",s[0]));}else{current.addRule(newRule(s[0],s[1]));}}}Rangerange=newRange(1,4001);Piecebase=newPiece(range,range,range,range);workflows.get("in").pieces.add(base);List<Piece>accepts=newArrayList<>();computeAccepts(workflows,accepts);BigIntegersum=BigInteger.ZERO;for(Piecepiece:accepts){// uncomment to checkIndividual(piece, workflows);sum=sum.add(BigInteger.valueOf(piece.prod()));}System.out.println(sum);returnworkflows;}privatestaticvoidcheckIndividual(PiecerangePiece,Map<String,Workflow>workflows){for(inti=0;i<1000;i++){StringcurrentName="in";Piecepiece=newPiece(rangePiece.x.random(),rangePiece.m.random(),rangePiece.a.random(),rangePiece.s.random());//System.out.println("Piece:" + piece); while(!currentName.equals("R")&&!currentName.equals("A")){//System.out.println("Current workflow:" + currentName);Workflowworkflow=workflows.get(currentName);for(Rulerule:workflow.rules){//System.out.println("Match:" + rule.condition);if(rule.match(piece)){currentName=rule.destination;//System.out.println("=>:" + rule.destination);break;}}}if(!currentName.equals("A")){System.err.println(rangePiece);thrownewRuntimeException(piece.toString());}}}privatestaticvoidcomputeAccepts(Map<String,Workflow>workflows,List<Piece>accepts){while(workflows.values().stream().filter(w->!w.pieces.isEmpty()).count()>0){Workflowworkflow=workflows.values().stream().filter(w->!w.pieces.isEmpty()).findFirst().orElse(null);System.out.println("Workflow:"+workflow.name);Piecepiece=workflow.pieces.pop();for(Rulerule:workflow.rules){if(rule.process(piece,workflow,workflows,accepts)){break;}}}}publicstaticvoidmain(String[]args){longs=System.currentTimeMillis();try(Scannerin=newScanner(Aoc2023s18v2.class.getResourceAsStream("res/t19.txt"))){parseInput(in);}System.out.println("Durée:"+(System.currentTimeMillis()-s)+"ms");}}
Pour la première partie, j'ai utilisé un bête algo de remplissage de forme par propagation.
Pour la deuxième partie, je connaissais l'algorithme du lacets(Shoelace) pour en avoir entendu parlé récemment.
Je me doutais qu'il fallait retirer le périmètre du polygone.
Par contre, je ne trouvais pas malgré toutes mes investigations ,c'est en lisant le CR de Guillaume que j'ai découvert le théorème de Pick et son usage.
Mauvais cocktail pour coder :)
- S'être couché à 3h
- Être fatigué, limite reste de gueule bois
- Regarder les conneries à la télé en même temps qu'on code.
Conséquences:
- çà donne un code très long à déboguer
- un problème pris de travers.
Mon code est tellement moche que je ne vais pas le partager :)
Honnêtement , je ne voyais pas comment appliquer un algo traditionnel de pathfinding avec les règles de déplacement.
Je suis donc partie sur une fonction récursive dans un premier temps. Mauvaise pioche entre les bogues, je suis arrivé après 3h à me dire que çà ne pouvait pas marcher.
Je change de stratégie. Je pars de l'arrivé et je remonte progressivement en mettant à jour les noeuds adjacents, j'y ai passé encore bien 3h au total sur la journée.
Ci-dessous ma soluce en Java pour la partie 2. Elle met 403ms une fois Java lancé (c'est comme un bon diesel Java). Et encore, j'ai une vilaine boucle qui compte jusqu'à avant le milliard.
J'optimise en utilisant des objets mutable & un bon vieux cache basé sur un Record.
packageaoc2023;importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassAoc2023s14v2{enumType{SPHERE,ROCK;}publicstaticclassPoint{intx;inty;Typetype;publicPoint(intx,inty,Typetype){this.x=x;this.y=y;this.type=type;}}publicstaticclassWorld{intwidth;intheight;Point[][]map;List<Point>spheres=newArrayList<>();publicWorld(List<String>rows){map=newPoint[rows.size()][rows.get(0).length()];for(inty=0;y<rows.size();y++){addRow(rows.get(y),y);}this.height=rows.size();}publicvoidaddRow(Stringrow,inty){this.width=row.length();for(intx=0;x<row.length();x++){Pointp=null;if(row.charAt(x)=='O'){p=newPoint(x,y,Type.SPHERE);spheres.add(p);}elseif(row.charAt(x)=='#'){p=newPoint(x,y,Type.ROCK);}map[y][x]=p;}}publicbooleanisFree(intx,inty){if(x<0||x>=width||y<0||y>=height){returnfalse;}returnthis.map[y][x]==null;}publicPointfind(intx,inty){if(x<0||x>=width||y<0||y>=height){returnnull;}returnthis.map[y][x];}publicvoidmove(intdx,intdy){booleanchange=false;do{change=false;for(Pointp:spheres){if(isFree(p.x+dx,p.y+dy)){map[p.y][p.x]=null;p.x+=dx;p.y+=dy;map[p.y][p.x]=p;change=true;}}}while(change);}publicintcomputeWeight(){intsum=0;for(Pointsphere:spheres){sum+=(height-sphere.y);}returnsum;}publicList<String>toRows(){List<String>rows=newArrayList<>();StringBuildersb=newStringBuilder();for(inty=0;y<height;y++){sb.setLength(0);for(intx=0;x<width;x++){Pointp=find(x,y);if(p==null){sb.append('.');}elseif(p.type==Type.ROCK){sb.append('#');}else{sb.append('O');}}rows.add(sb.toString());}returnrows;}}publicstaticvoidmain(String[]args){longstartMs=System.currentTimeMillis();try(Scannerin=newScanner(Aoc2023s14v2.class.getResourceAsStream("res/t14.txt"))){List<String>rows=newArrayList<>();while(in.hasNext()){rows.add(in.nextLine());}IntegerstartCycle=null;IntegercycleCount=null;Worldworld=null;finallongLOOPS=1_000_000_000L;for(longx=0;x<LOOPS;x++){CacheKeycurrent=newCacheKey(rows);if(keys[current.cacheIndex()]!=null&&keys[current.cacheIndex()].equals(current)){if(startCycle==null){startCycle=current.cacheIndex();cycleCount=0;}elseif(startCycle==current.cacheIndex()){System.out.println("Make cycle: "+cycleCount);// Could be more elegant :)while(x<(LOOPS-cycleCount)){x+=(cycleCount+1);}}else{cycleCount++;}world=cache_worlds[current.cacheIndex()];}else{world=computeWorld(rows);keys[current.cacheIndex()]=current;cache_worlds[current.cacheIndex()]=world;System.out.println("miss "+x);startCycle=null;cycleCount=null;}rows=world.toRows();}System.out.println(world.computeWeight());}System.out.println((System.currentTimeMillis()-startMs)+"ms");}privatestaticWorldcomputeWorld(List<String>rows){Worldworld;world=newWorld(rows);world.move(0,-1);world.move(-1,0);world.move(0,1);world.move(1,0);returnworld;}publicstaticrecordCacheKey(List<String>rows){publicintcacheIndex(){returnMath.abs(this.hashCode())%CACHE_SIZE;}}publicstaticfinalintCACHE_SIZE=1_000_000;publicstaticCacheKey[]keys=newCacheKey[CACHE_SIZE];publicstaticWorld[]cache_worlds=newWorld[CACHE_SIZE];}
Pour la deuxième partie, j'ai opté pour une solution où je remplace les tuiles de base par des tuiles de 3x3
Je remplie ensuite en faisant les cellules en bordure de la map.
Note: Ce code doit être utilisée --Xms2G pour avoir une stack plus grande que celle par défaut.
publicenumPipe{V('|',Arrays.asList(Direction.N,Direction.S),newint[][]{newint[]{0,1,0},newint[]{0,1,0},newint[]{0,1,0}}),// is a vertical pipe connecting north and south.H('-',Arrays.asList(Direction.E,Direction.W),newint[][]{newint[]{0,0,0},newint[]{1,1,1},newint[]{0,0,0}}),// is a horizontal pipe connecting east and west.L('L',Arrays.asList(Direction.N,Direction.E),newint[][]{newint[]{0,1,0},newint[]{0,1,1},newint[]{0,0,0}}),// , is a 90-degree bend connecting north and east.J('J',Arrays.asList(Direction.N,Direction.W),newint[][]{newint[]{0,1,0},newint[]{1,1,0},newint[]{0,0,0}}),// is a 90-degree bend connecting north and west._7('7',Arrays.asList(Direction.S,Direction.W),newint[][]{newint[]{0,0,0},newint[]{1,1,0},newint[]{0,1,0}}),// is a 90-degree bend connecting south and west.F('F',Arrays.asList(Direction.S,Direction.E),newint[][]{newint[]{0,0,0},newint[]{0,1,1},newint[]{0,1,0}}),// is a 90-degree bend connecting south and east.D('.',Collections.emptyList(),newint[][]{newint[]{0,0,0},newint[]{0,0,0},newint[]{0,0,0}}),// is ground; there is no pipe in this tile.S('S',Arrays.asList(Direction.N,Direction.S,Direction.E,Direction.W),newint[][]{newint[]{0,1,0},newint[]{1,1,1},newint[]{0,1,0}}),// is the starting position of the// animal; there is a pipe on this// tile, but your sketch doesn't// show what shape the pipe has.;charc;List<Direction>directions;int[][]matrix;Pipe(charc,List<Direction>directions,int[][]matrix){this.c=c;this.directions=directions;this.matrix=matrix;}booleanacceptFrom(Directiond){returndirections.contains(d);}}
Pour la partie 2, l'idée est assez simple. J'identifie les engrenages '*' par leurs coordonnées et je stocke sur chaque coordonnée la liste des nombres associés (numsById)
Alors pour moi, une bonne raclette:
- Bcp de fromages
- Des Tomates
- De l'oignon coupé finement.
- Un gouse d'ail cuite en même que les patates
- Un peu de patates (pas plus d'une pour moi)
- Un peu de jambon fumé et du bacon
Et sinon pour la problématique de l'appareil à Raclette , il y a ceux de GIFI qui se branche les un les autres. Donc tout le monde peut venir avec ses appareils à raclette.
Si, c'est comme dans l'article, c'est à dire:
- le navigateur récupère une black list du gouvernement , çà me va.
Par contre, si le système est du type. Quand on consulte un site, on vient demander au site du gouvernement si on a le droit d'y accéder, c'est plus ennuyeux.
Pour 3 raisons:
- le gouvernement connaitra ton historique de navigation
- ça risque de tuer les perf de navigation
- une ddos sur site , on ne navigue plus
Après, c'est le genre de feature qui pourra se désactiver. Vu qu'elle ne sera pas appliquable dans tous les pays.
Après pour l histoiriques de navigation, les antivirus, google, ils ont déjà cette historique avec l antiphishing d activés donc c est plutôt le risque 2 et 3 qui gène
[^] # Re: Pre challenge
Posté par syj . En réponse au journal France Cybersecurity Challenge (FCSC) 2024 va commencer. Évalué à 1 (+0/-0).
J'ai bien aimé la première partie du prechall.
Cela m'a rappelé l'époque où pour tricher dans les jeux. On allait modifier la mémoire ou le code.
La deuxième partie est en python. Et c est ce qui m a fait perdre beaucoup de temps.
C'est un classique des challenges de programmation mais je l'ai pris de travers…
[^] # Re: Même pour les quiches (comme moi)
Posté par syj . En réponse au journal France Cybersecurity Challenge (FCSC) 2024 va commencer. Évalué à 3 (+2/-0).
Les catégories introduction sont en général à la portée de tous.
En général, les 1 étoiles me prennent en général 1 à 4h.
Au-dessus, les 2 étoiles, j arrive à en avoir quelques une
Les 3 étoiles, je ne suis pas sûr d en avoir eu une pendant le concours mais je suis toujours très intéressé de découvrir les write-up une fois le concours terminé.
[^] # Re: son altesse sérénissime
Posté par syj . En réponse au journal Atlassian SaaS.... Évalué à 2 (+1/-0). Dernière modification le 13 février 2024 à 13:29.
Je confirme , je me suis trompé.
Je fais en général beaucoup fautes mais c'est encore pire que je suis énervé.
Trop tard pour changer.
# 20 M €
Posté par syj . En réponse au journal Combien pour un algorithme de détection de piscines sur les photos aériennes ?. Évalué à 6 (+5/-0). Dernière modification le 09 février 2024 à 08:56.
20 M€ c'est le coup du dev.
La maintenance annuelle, elle est à combien ?
[^] # Re: L'informatique c'est vaste
Posté par syj . En réponse au journal [Trolldi] La Big Tech vous souhaite une très belle réflexion existentielle. Évalué à 4.
Je suis du même avis.
On arrive sur ce genre de phase où il y a une restructuration de l'activité.
Mais ça ne va pas durer.
Il faudra probablement apprendre à revaloriser ses compétences ou revoir ses préférences techniques.
Mais dans l'ensemble l'IA va augmenter la taille des SI et leur complexité.
Résultat, on va passer moins de temps à coder et plus de temps en réunions de coordination.
Les véritables compétences à revaloriser. Ça va être :
- Les softskills: organisation, la motivation, la communication et le sens du service
- la modélisation système
- L'administration système.
# Algorithme de Karger
Posté par syj . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Pour le dernier jour, j'ai tenté plusieurs solutions naïve avant de chercher un algorithme qui pouvait répondre à mon problème.
Je suis tombé sur l'algorithme de Karger qui me semblait relativement simple à implémenter.
https://fr.wikipedia.org/wiki/Algorithme_de_Karger
Je trouve que ma condition de sortie est un peu moisie mais dans l'ensemble.
En gros, j'arrête le programme quand j'arrive à une contraction à 2 noeud avec 3 lien qui sont les 3 liens à couper.
C'était la solution attendu. Je n'ai pas cherché plus loin.
[^] # Re: J'ai aussi utilisé le Z3 theorem prover.
Posté par syj . En réponse au message Advent of Code 2023, jour 24. Évalué à 1. Dernière modification le 28 décembre 2023 à 23:31.
Je viens de voir que j'avais oublié de corriger le problème de séparation des bloques
il faut le lire. il manque un saut ligne est un commentaire.
(En espérant que c'est plus clair)
# J'ai aussi utilisé le Z3 theorem prover.
Posté par syj . En réponse au message Advent of Code 2023, jour 24. Évalué à 1. Dernière modification le 31 décembre 2023 à 11:07.
J'ai aussi utilisé le Z3 theorem prover.
En gros, je pose pour chaque axe & chaque grelon
rock.x + t1 * rock.vx = grelon.x + t1 * grelon.vx
rock.y + t1 * rock.vy = grelon.y + t1 * grelon.vy
rock.z + t1 * rock.vz = grelon.z + t1 * grelon.vz
Le solve du z3 se charge de trouver la solution des systèmes d'équation.
Vu que je suis plus habitué à Java pour le parsing du input , j'ai écrit un petit programme qui me génère le code typescript attendu par le solver Z3.
La première version pouvait directement s'éxecuter dans la sandbox https://microsoft.github.io/z3guide/programming/Z3%20JavaScript%20Examples/
On peut aussi l'éxecuter en locale de cette manière:
Via package.json
Code typescript
# Enfin...
Posté par syj . En réponse au message Advent of Code 2023, jour 20. Évalué à 1.
J'ai enfin ma solution pour le jour 20.
1) J'ai exploré plusieurs solutions comme laisser mon PC calculé à l'aveugle pendant 1j de travail. Je chauffe en partie à l'électrique. Donc, cela ne me coutait pas de laisser mon PC cramer des Watt :).
2) J’ai tenté de simplifier les cycles des flip-flop sans grand succès. Car je pensais que les conjuctions serait beaucoup plus complexe avec leurs multiples false, true qu’elles crachent
3) Via récursivité de trouver une méthode pour factoriser les circuits. Je n’ai pas vu la solution suivante toute suite, car ma fonction recursive allé jusqu’au flip / flop. Mais au final,c’était trop complexe pour trouver une simplification évidente.
4) Finalement, j’ai tenté juste de regarder les cycles des trues sur les 4 conjonctions qui sont avant RX { "hz", "pv", "qh", "xm" }
Et là, c’était évident. J’avais des cycles réguliers pour ces 4 conjonctions. Il ne me reste plus qu’à trouver quand elles sont à true toutes les 4 en même temps. Ce qui revient à trouver le PPCM des 4 cycles.
J’ai demandé à chatgpt de me fournir le calcul d’un PPCM (çà se reconnait au style).
En prenant, le problème dans le bon sens, j’aurai pu le résoudre en 1h partie 1 et partie 2…. J’ai mis encore bien 5h cumulé.
# Brut force pour la partie 2
Posté par syj . En réponse au message Advent of Code 2023, jour 23. Évalué à 1.
Pour la partie 1 , j'ai appliqué un bête parcours en profondeur.
Pour la partie 2, j'ai laissé tourner ma solution de partie 1 pour trouver la max de la partie 2.
Environ 1h de calcul.
J'aurai bien essayé de faire un truc plus intelligent mais je n'avais pas le temps.
Il faut quand même lancer ce code -Xss1g pour avoir une stack conséquence qui permet une récursivité aussi profonde.
# Méthode de Guillaume
Posté par syj . En réponse au message Advent of Code 2023, jour 21. Évalué à 1. Dernière modification le 23 décembre 2023 à 02:37.
J'ai implémenté la méthode avec séquence quadratique de Guillaume B.
Je suis un peu décu de ne pas avoir trouvé par moi-même
Mais je suis très heureux d'avoir découvert ce point des maths que je ne connaissais pas.
[^] # Re: Solution en Haskell.
Posté par syj . En réponse au message Advent of Code, jour 19. Évalué à 1.
600 microsecondes ?
Tu es sur que ce n'est pas des millisecondes ?
# Encore des problèmes de tests au borne
Posté par syj . En réponse au message Advent of Code, jour 19. Évalué à 1.
Je fatigue , il est temps que la saison se termine. J'ai encore perdu du temps sur des tests bête aux borne
Environ ~3h00 au total.
Encore obligé d'en arriver à écrire T.U. pour débuguer. Demain, je TDD, je vais probablement gagner du temps.
Pour la partie 1, j'ai utilisé un evaluator JEXL pour les expressions.
Pour la partie 2, je n'avais pas le choix. J'ai écris le "parseur" (En fait, c'est plutôt un split de l'expression) car il faut plus travailler sur des lots de pieces.
Mon objet Piece a maintenant une propriété Range que je vais split à chaque expression en 0, 1 ou 2.
Temps d'éxecution:123ms
# Bof , bof, je n'ai pas vraiment trouvé par moi-même.
Posté par syj . En réponse au message Advent of Code, jour 18. Évalué à 1.
Pour la première partie, j'ai utilisé un bête algo de remplissage de forme par propagation.
Pour la deuxième partie, je connaissais l'algorithme du lacets(Shoelace) pour en avoir entendu parlé récemment.
Je me doutais qu'il fallait retirer le périmètre du polygone.
Par contre, je ne trouvais pas malgré toutes mes investigations ,c'est en lisant le CR de Guillaume que j'ai découvert le théorème de Pick et son usage.
Mon implémtentation en Java.
# J'étais fatigué, j'ai fait un algo moisie, j'ai du corrigé des bug moisie
Posté par syj . En réponse au message Advent of Code, jour 17. Évalué à 1.
Mauvais cocktail pour coder :)
- S'être couché à 3h
- Être fatigué, limite reste de gueule bois
- Regarder les conneries à la télé en même temps qu'on code.
Conséquences:
- çà donne un code très long à déboguer
- un problème pris de travers.
Mon code est tellement moche que je ne vais pas le partager :)
Honnêtement , je ne voyais pas comment appliquer un algo traditionnel de pathfinding avec les règles de déplacement.
Je suis donc partie sur une fonction récursive dans un premier temps. Mauvaise pioche entre les bogues, je suis arrivé après 3h à me dire que çà ne pouvait pas marcher.
Je change de stratégie. Je pars de l'arrivé et je remonte progressivement en mettant à jour les noeuds adjacents, j'y ai passé encore bien 3h au total sur la journée.
3min pour donner la réponse de la partie 2.
# Solution en Java 403ms
Posté par syj . En réponse au message Advent of Code, jour 14. Évalué à 1.
Ci-dessous ma soluce en Java pour la partie 2. Elle met 403ms une fois Java lancé (c'est comme un bon diesel Java). Et encore, j'ai une vilaine boucle qui compte jusqu'à avant le milliard.
J'optimise en utilisant des objets mutable & un bon vieux cache basé sur un Record.
# J'en ai bavé.
Posté par syj . En réponse au message Advent of Code 2023, jour 12. Évalué à 1.
6h au total ! J'ai commencé par prendre le problème de travers.
J'ai fait substitution récursive des '?' ,c'était mon erreur.
C'est après que j'ai compris qu'il fallait distribuer les espaces restant entre les groupes.
çà permet d'exprimer le problème avec une fonction recursive pour lequel on peut mettre en place un cache des valeurs par rapport au reste à évaluer.
Environ 414ms sur ma machine (après avoir commenté les println)
# Ma solution
Posté par syj . En réponse au message Advent of Code 2023 : Jour 10. Évalué à 1.
Pour la deuxième partie, j'ai opté pour une solution où je remplace les tuiles de base par des tuiles de 3x3
Je remplie ensuite en faisant les cellules en bordure de la map.
Note: Ce code doit être utilisée --Xms2G pour avoir une stack plus grande que celle par défaut.
# Je me lance ma soluce en Java
Posté par syj . En réponse au message Advent of Code 2023 : Day 3. Évalué à 1.
Un peu long à coder, j'ai passé plus de temps sur la première partie que sur la deuxième partie.
Partie 1 :
Pour la partie 2, l'idée est assez simple. J'identifie les engrenages '*' par leurs coordonnées et je stocke sur chaque coordonnée la liste des nombres associés (numsById)
[^] # Re: Plusieurs leaderboards privés ?
Posté par syj . En réponse au journal Advent of code 2023. Évalué à 3.
Je confirme. On a un leadboard interne à ma boite. Plus celui-ci.
[^] # Re: J'y retourne !
Posté par syj . En réponse au journal Advent of code 2023. Évalué à 4.
J'aurai du te laisser faire la news :-p
# Personnellement, je préfère les tomates aux pattates
Posté par syj . En réponse au journal Il est temps que la communauté internationale fasse un choix. Évalué à 2.
Alors pour moi, une bonne raclette:
- Bcp de fromages
- Des Tomates
- De l'oignon coupé finement.
- Un gouse d'ail cuite en même que les patates
- Un peu de patates (pas plus d'une pour moi)
- Un peu de jambon fumé et du bacon
Et sinon pour la problématique de l'appareil à Raclette , il y a ceux de GIFI qui se branche les un les autres. Donc tout le monde peut venir avec ses appareils à raclette.
# J'adore
Posté par syj . En réponse au journal Grandbrothers. Évalué à 2.
J'adore :) Merci pour cette belle découverte.
# Ça dépend
Posté par syj . En réponse à la dépêche Pétition de Mozilla pour protéger Firefox. Évalué à 1.
Si, c'est comme dans l'article, c'est à dire:
- le navigateur récupère une black list du gouvernement , çà me va.
Par contre, si le système est du type. Quand on consulte un site, on vient demander au site du gouvernement si on a le droit d'y accéder, c'est plus ennuyeux.
Pour 3 raisons:
- le gouvernement connaitra ton historique de navigation
- ça risque de tuer les perf de navigation
- une ddos sur site , on ne navigue plus
Après, c'est le genre de feature qui pourra se désactiver. Vu qu'elle ne sera pas appliquable dans tous les pays.
Après pour l histoiriques de navigation, les antivirus, google, ils ont déjà cette historique avec l antiphishing d activés donc c est plutôt le risque 2 et 3 qui gène
# embrace - extend - extinguish
Posté par syj . En réponse au journal Wayland dans windows 10 et 11. Évalué à 2.
J'ai découvert moi aussi WSL 2 sur Windows. çà me permet de faire tourner un Linux & plein d'instance docker pour mes dev.
Je n'ai pas encore essayé de faire tourner des apps graphique mais je ne suis pas surpris que çà marche.
Ce qui me terrifie, c'est la stratégie historique de Microsoft: Embrace - Extend - Extinguish.
Avec, ils ont réussi à bouffer : OS/2 , Netscape, …