Handicap assistance, and then some.. Og hvordan boarder man et fly?

Jeg er i øjeblikket på vej til Buenos Aires (ja, i Argentina), for at præsentere et paper jeg arbejdede på sidste år. Det omhandler at vi har anvendt Barriere Certifikater på en kølecontainer (eller, hvertfald på en del af den), det skal nok blive godt! Jeg har ikke lavet præsentationen endnu, men givet at flyturen er på små 14 timer, tror jeg nok jeg får tid nok til det!

Det sjove er, at jeg skrev til rejseagenten at jeg var dårligt gående, og hun bestilte handicap hjælp! Selvom jeg efterhånden er træt af at skulle have hjælp til mange ting, syntes jeg faktisk det var ret sjovt at køre igennem Schipol lufthavn i Amsterdam, i en elbil, med Mohammed som chauffør! Det var faktisk enormt effektivt...

Nå, tilbage til det jeg ville snakke om - jeg så for tid siden et Mythbusters afsnit, hvor de afprøvede forskellige måder at boarde fly på - (den er tilgængelig her), og i den forbindelse syntes jeg faktisk det var interessant, at den hurtigste metode, er den folk mindst kan lide. Det relaterer sig (lidt) til et tidligere opslag jeg lavede omkring Pubcrawl Paradokset. Det er et planlægningsproblem, og det er et planlægningsproblem man kan løse! Det viser sig imidlertid, at der er lavet en del forskning på området, med at boarde fly! Og den konventionelle "bagfra og frem" er efter alle mål, den klart langsomste metode at bruge. Jeg fandt en spændende opsummering på The Atlantic.

Det viser sig, at den hurtigste metode, er at bare lade folk gå om bord tilfældigt, ét stort hvirvar. Men sjovt nok, så er det den metode folk hader. Og jeg kan godt forstå dem. Folk går ind i begge ender, uden at vide hvor de skal sidde, folk går forbi deres plads (underligt nok - det er vel efterhånden socialt accepteret at tælrækken går (n+1) for alle tal (pånær tallet 13, det findes ikke i fly - læg mærke til det, næste gang du flyver)). Og skal pludselig op og have fat i noget i deres håndbagage. Det er et helt håbløst koncept egentligt. Men så er det godt der findes andre metoder, som dog kræver at folk bruger de 2 hjerne celler, de sommetider har at flytte med. Det er der skrevet lidt om her. Alt i alt, et meget spændende område egentlig.

Hvis jeg får tid på flyveturen, tror jeg at jeg laver et simulerings script, til at teste de forskellige metoder. Jeg burde i øvrigt også få færdiggjort Pubcrawl simulatoren. Kombinatorik er vejen frem, og også et område jeg ikke mener får nok fokus.

Nå, jeg vil nyde en kold salat, god dag!
/Rasmus

Ping this site, ping that site - and try this combination..

At Lodam, we are putting a really big effort, in to being the best workplace in Denmark. This means that management, have signed us up for the "Great Place to Work" scheme, which sends out a questionnaire which then compares us the other businesses in Denmark (of the same size). They send the questionnaire by a link, that sends you to an online form, which you need to fill.

Furthermore, they encourage all the departments to answer, there are prizes involved.

And, as i don't like to loose, i would like to ensure that everybody in my department have answered the questionnaire, så we started to look at the URL strings they send out. They look something like this:


https://or.allegiancetech.de/cgi-bin/qwebcorporate.dll?idx=EUFMZ4&l=dansk&rk=6YAPJG


Notice the last 6 digits. That's the unique identifier. All left to do now, is to develop a small script that generates all possible permutations of keys, and then ping the web-page for every entry generated. It only contains capitalized letters and numbers, so the number of possible permutations is relatively small. Somewhere around 2.2 billion keys.

Last evening, i developed this script, which runs all the possible permutations (the 2.2 billion). Have fun - remove (or adjust) the iterMax parameter, to ensure that your computer does not go bonkers.

What i really want people to start thinking about, is cryptographic solutions that are better than this. Maybe, mix them with lower-case letters.

/Rasmus

Jeg har fundet en løsning-(ish)...

Jeg har fundet en løsning på problemet - eller hvertfald ud af hvad det hedder! Tak til Lars Jorge Díaz for at sende mig i den rigtige retning!

Det hedder Graeco-Latin Squares, og er egentlig ret brugt i statistik, for at finde ud af hvilke testpersoner man skal parre med hvilke. Og det kan angiveligt løses for alle problemer større end 2 hold, pånær for 6 hold - og det er så her jeg må finde ud af hvorfor. En umiddelbar indskydelse, er at tallet 6, er deleligt med både 1, 2, 3 og 6. Men jeg er ikke sikker. Modsat er 8 jo også deleligt med 1, 2, 4 og 8.

Det må jeg undersøge lidt nærmere når jeg får fri. I mellemtiden, her er en række links:

Så er der lidt løsning!
/Rasmus

Tallene bag "Pubcrawl Paradokset".

Jeg stoppede i går aftes med at udvikle på Brute-Force algoritmen, for lige at køre tallene igennem i hovedet - for at sikre mig, at jeg nu ikke sad og forsøgte at løse et eller andet hovedkulds åndssvagt problem, som man ved at tage 2 skridt tilbage, ikke kunne finde en løsning på.

Hvis man kigger helt nøgternt på det, så vil der med 3 steder være følgende gældende:

  • Der vil være 6 deltagende hold (husk n = 2m). Og ud fra disse, vil man have 6!/2 = 360 mulige kombinationer af holdene (ex. 1 vs 2, 1 vs 3, osv.).
  • Til hver tid, skal der bruges 3 kombinationer af hold. Hvilket peger på at der er mulige kombinationer nok.
  • Det må være noget med at de skal prøve alle tingene én gang, der får det til at være uløseligt.

Jeg læste en spændende artikel om scheduling og graf-teori, jeg tror muligvis det er vejen at gå.

Nå, tilbage til det rigtige arbejde!
/Rasmus

Et matematisk problem, lad os kalde det "Pubcrawl Paradokset"...

For lang tid siden, var jeg med til at planlægge en pubcrawl, og vi løb ind i et planlægningsproblem, jeg ikke har kunnet finde en løsning på endnu, og umiddelbart har ingen af dem jeg lige har spurgt, kunne give mig et hint af, i hvilken retning svaret måtte ligge. Så nu smider jeg det op på internettet, og håber at der sidder nogle kloge hoveder derude, der kan hjælpe lidt.

For en god ordens skyld, så skal det siges at jeg er ved at lave en brute-force løser, der tester alle mulige permutationer, men inden den bliver færdig for de rigtigt store tilfælde, kunne det være fedt hvis nogen havde en ordentlig grund til, hvorfor man ikke kan planlægge det. 

Jeg sætter i øvrigt en flaske vin på højkant. Måske 2. Og også et kram! Nå - her begynder vi:

  • Pubcrawlen involverer et antal aktiviteter, svarende til antallet af steder der skal besøges. Dette antal er m.
  • Pubcrawlen har n deltagende hold.
  • På hvert sted, skal to hold kæmpe imod hinanden, så n = 2m. Om man møder alle hold, er ikke vigtigt.
  • Hvert hold må kun prøve hver aktivitet én gang.
  • Holdene må ikke kæmpe mod hinanden mere end én gang.
  • Og slutteligt, grundet fysikkens love, kan man ikke være på 2 pubs på én gang.

Så langt jeg har fundet frem til, så kan problemet ikke løses hvis antallet af aktiviteter (m), er lige. Men for et ulige antal, kan man bare drible ned gennem et skema, og så passer pengene. Er der nogen der kan hjælpe? Gerne, eventuelt med noget litteratur på emnet, samt et navn på det matematiske aspekt af det. Jeg er sådan set ligeglad med om det kan løses eller ej, jeg vil bare gerne vide hvorfor. På billedet nedenfor har jeg vist et eksempel, med 3 steder, og 6 hold. Og den kan godt løses (med mindre jeg har overset noget).

pubcrawlParadox

 

Og skulle det resultere i at vi er nød til at opfinde noget matematik for at få det løst, jamen så gør vi det gerne! Jeg håber at måtte blive medforfatter på en eventuel publikation.

Jeg skal nok give lyd når jeg nærmer mig et resultat... Og ja, jeg løser også mine sudoku med kuglepen, jeg lever et hårdt liv!
/Rasmus