Algoritmusok

TOTP számítása bash-ben

Fórumok

Sziasztok!

Alábbi PHP kódot sikeresen használom egy ideje:

function getOtp($key) {

    $alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
    /* Base32 decoder */
    // Remove spaces from the given public key and converting to an array
    $key = str_split(str_replace(" ","",$key));

    $n = 0;
    $j = 0;
    $binary_key = "";
    // Decode public key's each character to base32 and save into binary chunks
    foreach($key as $char) {
        $n = $n << 5;
        $n = $n + stripos($alphabet, $char);
        $j += 5;

        if($j >= 8) {
            $j -= 8;
            $binary_key .= chr(($n & (0xFF << $j)) >> $j);
        }
    }
    /* End of Base32 decoder */
    // current unix time 30sec period as binary
    $binary_timestamp = pack('N*', 0) . pack('N*', floor(microtime(true)/30));
    // generate keyed hash
    $hash = hash_hmac('sha1', $binary_timestamp, $binary_key, true);

    // generate otp from hash
    $offset = ord($hash[19]) & 0xf;
    $otp = (
        ((ord($hash[$offset+0]) & 0x7f) << 24 ) |
        ((ord($hash[$offset+1]) & 0xff) << 16 ) |
        ((ord($hash[$offset+2]) & 0xff) << 8 ) |
        (ord($hash[$offset+3]) & 0xff)
    ) % pow(10, 6);

   return $otp;
}

Szeretném ugyanazt a funktionalitást elérni bash-ben, de nem tartok még ott.

#!/bin/bash

T=$(echo $(date +%s) / 30 | bc)
export T
TB=$(perl -e "print pack(\"N*\", 0).pack(\"N*\", $T)")
echo $TB | od
K="TITOK123"
keyhex=$(printf '%s' "$TB" | openssl dgst -sha1 -hmac $K | cut -d' ' -f2 )
echo $keyhex
dec=$(echo "ibase=16; $(echo $keyhex | tr '[:lower:]' '[:upper:]')" | bc)
echo $dec
key=$(echo "$dec % 1000000" | bc)
echo "$key"

Erre a soora gyanakszom a leginkább:

TB=$(perl -e "print pack(\"N*\", 0).pack(\"N*\", $T)")

2 cella távolsága?

Fórumok

Van egy csomó egyforma cellám (szoba), ezeknek O oldaluk van, a szomszédjaikkal 1-1 oldalon kapcsolódnak = 1 közös faluk van.
Az egyszerűség kedvéért a szomszéd szobába mindig át lehet menni, vagyis az ajtók nincsenek egyik irányból sem zárva.

A feladat azt kitalálni, hogy 2 random szoba milyen messze van egymástól, a távolságot mérjük mondjuk "ajtó"-ban, Hány ajtón kell minimálisan átmenni, hogy A-ból B-be jussunk.

A legegyszerűbb ilyen, ha négyzet alakú szobák vannak, 4-4 ajtóval, szépen, mint a füzetben. Erre gyorsan ki lehet találni egy magik képletet, ami a poziciójuk alapján megmondja.
De mondjuk általános esetben? Mondjuk 6 oldalú szobák esetén. Netán szélsőséges esetben, pl. Ha Voronoj-celláim vannak? 

Vagy ha nem egyformák a szobák?

- Bonyolítja kicsit, hogy kell majd hozzá vmi model is, jellemzően SQL-ben szeretném az egészet aszalni.
- Jó lenne, ha majd lehetne írni egy egyszerű, tömör, zárt query-t, ami 2 cella-ID alapján megmondja a tutit. Szóval geometriai megoldások egyelőre visszafogottan érdekelnek.

Lehet ezt még bonyolítani, pl. ha "lyukak" is vannak (mint a keresztrejtvényben), vagy nem minden ajtó nyitható. De ezeket most hagyjuk. 

Az mondjuk már félig megoldás, ha a tisztelt közösség nevesíteni tudja a problémát, olvasni tudok.

TIA.

Fast FIR

Fórumok

Sziasztok!

Tud-e valaki veletlenul jo kis FIR algoritmust, ami akar meg gyors/hatekony is lehet? :) A win[] ablakfuggveny minden esetben lehet L + 1 = 2^N+1 elemszamu es szimmetrikus, ezt "er" kihasznalni. Azaz ahol L az mondjuk 32 ... 256 lenne a gyakorlatban mint ketto-hatvany, es win[n] = win[L-n] fennall. Nyilvan ha L az kisebb lenne mint az itteni ertekek (pl 4...8), akkor teljesen felesleges tultolni valami szofisztikalt eljarassal, ha pedig tul nagy, akkor mar ugyis inkabb konvolucionak hivnank mintsem FIR filteringnek. 

Egy naiv implementacio az kb ilyen most:

typedef struct
 {      int     fir_length;
        double  *fir_buffer;
        double  *fir_window;
        int     fir_index;
 } finite_impulse_response;

int fir_init(finite_impulse_response *fir,int len,double initial)
{
 int    i;
 fir->fir_length=len;
 fir->fir_buffer=(double *)malloc(sizeof(double)*len);
 for ( i=0; i<len; i++ )
  {     fir->fir_buffer[i]=initial;
  }
 fir->fir_window=(double *)malloc(sizeof(double)*(len+1));
 fir->fir_window= ...; /* computation of FIR window filter goes here */
 fir->fir_index=0;
 return(0);
}

double fir_apply(finite_impulse_response *fir,double in)
{
 double w;
 int    j,p;

 w=0.0;
 for ( j=0,p=fir->fir_index; j<fir->fir_length; j++ )
  {     w += fir->fir_buffer[p] * fir->fir_window[j];
        p=(p+1)%fir->fir_length;
  }
 w+=in*fir->fir_window[j];
 fir->fir_buffer[fir->fir_index]=in;
 fir->fir_index=(fir->fir_index+1)%fir->fir_length;

 return(w);
}

int fir_buffer(finite_impulse_response *fir,float *input,int ninput)
{
 int    i;
 for ( i=0; i<ninput ; i++ )
  {     input[i]=fir_apply(fir,input[i]);
  }
 return(0);
}

Lenyeg itt a legutolso fir_buffer() hivas, ami siman a fir_apply() hivason keresztul lekonvolvalja es a `fir` objektumban szepen tarolja az allapotgepet hogy kifele elrejtse az egesz hobelevancot. Szoval a feladat az a fir_apply() minel hatekonyabb, O(fir->fir_length) muveletigenynel jobban skalazo valtozata lenne. Nyilvan egy O(log(fir->fir_length)) lenne a legjobb :) Extrem hataresetekben, pl boxcar filterignel ugye O(1) muvelettel es O(length) memory footprinttel megoldhato, szoval csakcsak van valami a ketto kozott, kihasznalva hogy a length az ketto-hatvany es/vagy hogy a fir_window[] az szimmetrikus meg ilyesmi... 

thx, A.

Csoporton belüli homogenitás mérése mérőszámmal

Fórumok

Klaszterezés után az előálló klaszterek "minőségét" szeretném jellemezni mérőszámmal. A klaszterekben mondjuk betűk gyűlnek: AAA BBBBBCCE EEEEEF stb.

Ideális esetben a klaszterekben homogén lenne a tartalom, de az eset nem ideális, így alakulhat ki a fenti elrendezés.

Mivel többféle módszerrel történik ugyanazon adathalmaz klaszterezése, a létrejövő dendrogramokon pedig esetenként látszanak jobb elrendeződések (nagyobbak a homogén klaszterek, több homogén klaszter jön létre, mint más esetben), így valahogyan számszerűsíteni kéne ezeket a jobb elrendezéseket. Az nem elég, hogy "látszik". :-)

Ti hogyan oldanátok ezt meg?

2D packing algoritmust keresek

Fórumok

Sziasztok!

Adott a következő probléma, amire algoritmust keresek. (Hobbi projekt, nem munkához kell.)

Adott egy téglalap oldalméretekkel meghatározva, ezen a téglalapon kell elhelyezni n darab kisebb téglalapot, a következő szabályok szerint:

  • 2 <= n <= 50
  • Az elhelyezendő téglalapoknak egybevágóaknak kell lenni 
    • Közülük pontosan 1 téglalap a referencia, ennek az oldalarányát tartani kell
    • Az összess többi téglalap (n -1 darab) egyforma méretű kell legyen
    • A referencia téglalapnak ugyanakkorának (n=2 esetén) vagy nagyobbnak (n>2 esetén) kell lennie mint a többinek
  • Az elrendezésnek "mátrix jellegűnek" kell lennie, azaz pl
    • n = 2 esetén egy 1 x 2 es mátrixban lenne két egyforma téglalap
    • n = 3 esetén egy 2 x 3 as mátrixban a referencia téglalap lefoglalná az első két oszlopot teljesen, és a két kis téglalap lenne a 3. oszlop két sorában
    • n = 6 esetén egy 4 x 3 as mátrixban a referencia téglalap a bal felxő 2x2 cellát foglalná le, az 5 kis téglalap pedig a jobb oldali oszlopban, illetve a referencia téglalap alatt lennének
  • A téglalapok között kimaradt területet (értsd. üres cellák számát) kell minimalizálni
  • Eredményként a megoldásmátrix dimenziót kell kiadni, és hogy a referencia téglalap 1x1, 2x2, 3x3 stb cellát foglal e le az eredménymátrixból

Ha jól értelmezem, a probléma a 2D packing egy speciális alesete. Ezeket itt nézegettem, de szerintem minden ottani megoldás túl általános az én esetemre.

Use case: Fotózás, referencia fotóra szeretnék különféle effekteket (jelen esetben LUT-okat) applikálni, és szeretném egy képernyőn/képen nézegetni a variációkat.

Az algoritmust alighanem Rben vagy Pythonban fogom lekódolni, így ha valaki onnan tud libet vagy csomagot ajánlani, akkor extra megköszönöm.

(Nem kész szoftvert, hanem algoritmust keresek.)

Köszi előre is a tippeket,

 

Csaba

Disztichon alfa - Első magyar versgenerátor

Fórumok

Disztichon Alfa - Első magyar versgenerátor

"Az első magyar automatikus versgenerátor program, a Disztichon Alfa bármelyik Apple Macintosh számítógépen automatikusan magyar verseket, nevezetesen disztichonokat ír ki a számítógép képernyőjére. A generált versek 1) nyelvileg hibátlanok; 2) értelmesek, 3) tökéletesen kielégítik a disztichon formai ismérveit."

Könyv + melléklet elérhető innen:
https://mek.oszk.hu/11700/11744/

Disztichon Alfa 2.0
A Disztichon Alfa, Papp Tibor 1994-ben megjelent műve az első magyar digitális versgenerátor volt, amely eredeti technikai keretrendszere miatt néhány éven belül gyakorlatilag hozzáférhetetlenné vált. A közelmúltban elkészült az eredetivel megjelenésében azonos, de platformfüggetlen változat, amelyet az Irodalomtudományi Intézet honlapján, digitális szolgáltatásaink között fogunk közzétenni. A művet bemutató előadások a játékos hagyománykezelésről, a digitális megőrzés technikai paradoxonairól szólnak.

https://abtk.hu/esemenynaptar/esem%C3%A9ny%20r%C3%A9szletei/353/-/mtu-2…

Hangminta automatikus kiválasztása ~10 elemű tanulólistából

Fórumok

Sziasztok!

 

Volt valamikor egy Ericsson T28 nevű telefon. Ennek a nagy durranása az volt, hogy egy gomb lenyomásával képes volt élőszóban elmondott névjegyet felhívni.  Minden névjegyhez hozzá lehetett fűzni egy hangmintát, amivel ha nagyjából egyezett az élő szó, akkor tárcsázta. Röviden egy ilyet szeretnék csinálni, de minimum megérteni. Létező szolgáltatás volt ez, csak elment mindenki inkább a szövegértésre.

Általánosítva lennének hangmintáim, és egy sorszámot kellene visszaadni, hogy melyik hangzott el összességében mondjuk 10-20 szó felismerésére számítok. A végső cél hogy ez egy mikrovezérlős céleszközbe kerülhessen, szóval távlatok bizony vannak.

Namost. Általában nem vagyok analfabéta, de ez a terület maximálisan idegen számomra, és nem is tervezem hogy a szükségesnél jobban elmerüljek benne, csak amennyire ehhez az eszközhöz feltétlenül szükséges. Természetesen látom hogy nem lesz gyaloggalopp, és ingyen ebédre sem számítok.

Első gondolatom az lenne, hogy mint a hallásunk is, szűrés után (300Hz-3kHz) felbontanám frekvenciaösszetevőkre, és ebből valahogy gyártanék egy egyedi jellemzőt, mint egy ujjlenyomatot amit aztán eltárolva össze lehetne hasonlítani a mintával. Feltételezem hogy a frekvencia komponens időtartamát belekódolva megfelelő változatosságot lehet adni a mintáknak.

Ez csak az amit eddig agyaltam, de fogalmam sincs hogy egyáltalán az irány megfelelő-e.

Van valakinek bármilyen építő jellegű észrevétele, forrása, bármi? Lehetőleg minimális matekkal!

Gyors logaritmus fixpontos aritmetikával

Fórumok

Sziasztok!

Egész számoknak keresem a logaritmusát és mivel kernelben működne a program ezért nem használhatok lebegőpontos számokat. Van pl. egy 1 és 100e9 közötti tartomány, ezt szeretném logaritmussal leképezni egy kettő hatvány méretű területre. Teszem azt 10 bitem van, legnagyobb értékem az 1024, ez lenne a 100e9 és a hozzá közel eső számok. Az ehhez tartozó logaritmus a 1.025 alapú, mert ha x^1024 = 100e9 akkor x ~ 1.025. Mivel x bármilyen értéket felvehet 1 és 100e9 között én az ehhez legközelebbi logaritmus értéket keresem.

A jelenlegi megoldásom úgy néz ki, hogy előre kigenerálom az értékeket egy táblázatba, az első ezer számra ez így néz ki:
x : log_1.025(x)
1   : 0
2   : 28
3   : 44
4   : 56
....
912-934: 276
935-957: 277
958-981: 278
982-1000: 279

És ebben a táblázatban max 10 lépésben csinálok bináris keresést x-re és a kapott index lesz a logaritmus.

A kérdésem: lehetne-e ezt elegánsabban? Tudnátok-e mondani valami olyan módszert, amivel esetleg megspórolom a táblázatot meg a bináris keresést és képes lennék "egy lépésben" mondani x-hez egy log_1.025(x)-et? Szerencsére minden ismert fordítási időben x-et leszámítva, tehát megvan mi a legkisebb és legnagyobb x, megvan hogy hány bitre kell leképezni és milyen alapú logaritmussal.

Előre is köszönöm az ötleteket.

EOV to WGS84

Fórumok

Sziasztok,

 

Azzal a kihívással találkoztam, hogy EOVX és EOVY koordinátákat kellene átszámolnom GPS lon és lat formátumokra.

Találtam online átszámítókat, de maga a képlet nincs meg. Szeretnék írni egy kis programot, ami egy csv fájlt alakít át lokálisan.

Nézegettem pár szakdolgozatban, ami elérhető online, de sajnos nem találtam meg a képletet.

Köszi a segítséget előre is.

 

Itt tartok:

 

using System;


namespace GPS_transformer
{
    class Position
    {
        public DateTime timeStamp { get; private set; }
        public string address { get; private set; }
        public int eovx { get; private set; }
        public int eovy { get; private set; }

        public double longitude { get; private set; }

        public double latitude { get; private set; }

        public Position(DateTime timeStamp, string address, int eovx, int eovy)
        {
            this.timeStamp = timeStamp;
            this.address = address;
            this.eovx = eovx;
            this.eovy = eovy;
            this.EOV_to_GPS84();
        }

        private void EOV_to_GPS84()
        {
            //longitude = 47;
            //latitude = 19;
        }
    }
}

Üdv,

 

Zoli

algoritmust keresek - létezik-e - átlag számítás csak utolsó érték megtartásával

Fórumok

(Valószínűleg borzalmasan fogalmazok, terminológia szempontjából kövezzetek meg :) . )

Adott x db szám, és szeretnék egy átlagot (számtani közepet), anélkül, hogy tárolnom kellene az adatgyűjtés végéig az összes számot. Kevés matematikai tudásom alapján megoldhatónak tűnt, rosszul megfogalmazva: csak az átlagot tárolom, és az új adattal annak számolom ki az átlagát, és azt tárolom tovább. Így mindig csak egy számot kell tárolnom.

Próbáltam gyorsan egy egyszerű tesztet csinálni, lehet az jobban érthető egyeseknek, összehasonlítottam a két algoritmust, nem ugyan az az eredmény jön ki, de egymáshoz "nagyjából" közeli.

Kérdések: van-e ilyen algoritmus, és jó irányba próbálkoztam?

- - - - -

$nums = array();

for ($i = 0; $i < 100; $i++){
    $nums[] = rand(0,1000);
}

$sum = 0;
foreach ($nums as $num){
    $sum += $num;
}
$avg = $sum / count($nums);
unset($sum);
var_dump($avg);
unset($avg);

$first = 1;
foreach ($nums as $num){
    if ($first){
        $avg = $num;
        $first = 0;
    } else {
        $avg = ( $avg + $num ) / 2 ;
    }
}
var_dump($avg);