A hétvégén régről félretett papírokat szortíroztam, hogy amit lehet kidobjak. Így került a kezembe egy három évvel ezelőtti bizonylat egy gyorsétteremből, ahol kártyával fizettem. Azt vettem észre, hogy a megszokottól eltérően nem csak az utolsó négy számjegy volt meghagyva a kártyaszámból, és a többi kicsillagozva, hanem mindössze 6 számjegy volt kicsillagozva a 16-ból. Mostanság a BKK jegy és bérletautomata is adott ilyen bizonylatot Ekkor kissé elgondolkoztam, hogy vajon hány kombináció lehetséges, és ez kellő biztonságot ad-e a vásárlónak, ha valaki illetéktelen jut a bizonylathoz?

Hogy őszinte legyek, mivel inkább vagyok programozó mint matematikus, ezért az információ gyűjtés után egyből kódolni kezdtem, anélkül, hogy jobban végig gondoltam volna a használt algoritmus tulajdonságait, amiből idejekorán levonhattam volna a végkövetkeztetést.

A bankkártyaszámokról

A bankkártya számok 8-19 számjegy hosszú számsorok, melyek eleje a kibocsájtó intézetet azonosítja, amit egy számlaszám követ, és egy előremutató hibajavító kódolást tartalmazó szám zár. Itthon általában 16 számjegyű VISA vagy MasterCard kártyaszámokkal találkozni.

A bankkártyaszámokban általában a Luhn algoritmust használják előremutató hibajavító kódként (Forward Error Correction), ami egy digit információvesztést (ismerve annak helyét) még helyre tud állítani. Itt kellett volna, hogy rájöjjek a válaszra, ám én itt azonnal kódolni kezdtem…

A megvalósításomhoz először teszt adatokra volt szükségem. Egy gyors kereséssel találtam minta kártyaszámokat, amikkel neki is állhattam a teszt kód megírásának:

using Xunit;

namespace CreditCardNumberGuesser.Tests {
    public class CreditCardNumberTest {
        [Theory]
        [InlineData("5555555555554444")]
        [InlineData("5105-1051-0510-5100")]
        public void CorrectNumersAreValid(string cardNumber) {
            CreditCardNumber cn = new CreditCardNumber(cardNumber);
            Assert.True(cn.IsValid());
        }

        [Theory]
        [InlineData("5555555555554443")]
        [InlineData("5105-1050-0510-5100")]
        public void IncorrectNumersAreInvalid(string cardNumber) {
            CreditCardNumber cn = new CreditCardNumber(cardNumber);
            Assert.False(cn.IsValid());
        }
    }
}

A kártyaszám osztály, benne a Luhn algoritmust szinte szavanként kódba ültető IsValid metódussal:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CreditCardNumberGuesser {
    static class CreditCardNumberHelper {
        public static int[] ToDigitArray(this string number) {
            var digits = from n in number
                         .Trim()
                         .Replace("-", "")
                         .Replace(" ", "")
                         select int.Parse(n.ToString());
            return digits.ToArray();
        }
    }

    class CreditCardNumber {
        private int[] digits;
        private Lazy<string> str;

        public CreditCardNumber(string number) : this(number.ToDigitArray()) { }

        public CreditCardNumber(int[] digits) {
            if (!digits.All(n => 0 <= n && n <= 9)) {
                throw new ArgumentOutOfRangeException("Each card digit must be between 0..9 inclusive!");
            }
            this.digits = digits;

            this.str = new Lazy<string>(() => {
                var sb = new StringBuilder(digits.Length + digits.Length / 4);
                for (int i = 0; i < digits.Length; i++) {
                    if (0 < i && i % 4 == 0) {
                        sb.Append("-");
                    }
                    sb.Append(digits[i]);
                }
                return sb.ToString();
            }
           );
        }

        public bool IsValid() {
            var sum = digits.Reverse().Skip(1)
                .Select((n, idx) => {
                    if (idx % 2 == 1) {
                        return n;
                    } else {
                        var dbl = n * 2;
                        if (dbl > 9) {
                            return dbl - 9;
                        } else {
                            return dbl;
                        }

                    }
                }).Sum();

            var checkDigit = (sum * 9).ToString().Last() - '0';

            return checkDigit == digits.Last();
        }

        public override string ToString() {
            return str.Value;
        }
    }
}

Amit itt érdemes megfigyelni, az a LINQ IEnumerable<T>.Select() azon overloadjának hívása, ahol nem csak az elemet, hanem az indexét is átadjuk a projekciós függvénynek. (Ha ez nem lenne, akkor vagy for ciklusra, vagy egy szekvenciával zip-pelt sorozat projekciójára lenne szükség, amik mind rosszabbul olvashatóak szerintem). Ez nekem a kód írásakor újdonság volt.

Ezután lássuk a program eredeti feladatát: valahogy meg kellene számolni, hogy hány érvényes kártyaszámot lehet találni a hiányzó helyeket kitöltve! Ehhez kell egy lista a lehetséges számokról. Ezt az alábbi osztállyal valósítottam meg:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CreditCardNumberGuesser {
    class CreditCardNumberSequenceGenerator : IEnumerable<CreditCardNumber> {
        private int[] pattern;
        string formatString;
        long maxguess;

        public CreditCardNumberSequenceGenerator(string pattern) {
            string normalized = pattern.Trim().Replace("-", "").Replace(" ", "");

            this.pattern = normalized.Select(n => {
                int num;
                if (int.TryParse(n.ToString(), out num)) {
                    return num;
                } else {
                    return -1;
                }
            }).ToArray();

            var missing = this.pattern.Count(n => n == -1);
            maxguess = 1;
            for (int i=0; i<missing; i++) {
                maxguess *= 10;
            }
            formatString = $"D{missing}";
        }

        private CreditCardNumber buildCard(long guess) {
            var guessNums = (from n in guess.ToString(formatString) select int.Parse(n.ToString())).ToArray();
            int j = 0;

            var nums = new int[pattern.Length];
            for(int i =0; i<pattern.Length; i++) {
                if(0 <= pattern[i]) {
                    nums[i] = (int)pattern[i];
                } else {
                    nums[i] = guessNums[j++];
                }
            }

            return new CreditCardNumber(nums);
        }

        public IEnumerator<CreditCardNumber> GetEnumerator() {
            long guess = 0;
            while(guess < maxguess) {
                long g = System.Threading.Interlocked.Increment(ref guess);
                yield return buildCard(g-1);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }
}

Ebben a kódban véleményem szerint egyszerűsége ellenére is van néhány említésre méltó pont.

A hiányzó helyiértékeket a -1 értékkel kódoltam a számjegy tömbben, mivel ez az kitöltött helyiérték értékkészletén kívül esik.

A hiányzó helyiértékekre adott “tipp” aktuális értékét egy long értékkel tárolom. Azért tehetem ezt, mert a kártyaszámok tipikusan 16 jegyűek, de ez a típus Int64.MaxValue = 2^63 -1 -ig tud értékeket ábrázolni, ami 18 hiányzó számjegyig használható (mivel egy 19 jegyű szám a 10-es számrendszerben). Azért ezt a megoldást választottam, mert nem akartam egy szám-tömbben BCD aritmetikát megvalósítani, tesztelni, amikor ez vajmi keveset adna hozzá a kísérletem értékéhez (BigInteger típussal is csinálhattam volna, az pedig nem jutott eszembe). Ráadásképp egy long növelése atomi művelet (tud lenni), az alternatívákkal ellentétben, így csak minimálisan kell a lockolással foglalkoznom, és nulla erőfeszítéssel párhuzamosítható a kód a maximális teljesítmény mellett. Ez a minimális foglalkozás kimerül az Interlocked.Increment -el való inkrementálásban, ami garantáltam atomi.

Kitérő az enumerátorok párhuzamos felhasználására

Egyébként arra jutottam, hogy a lockolással amúgy sem kellett volna foglalkoznom, mivel az IEnumerator<T> contractja eleve nem thread safe. Ez belátható, hisz az IEnumerable<T> így néz ki:

public interface IEnumerable<out T> : IEnumerable {
    IEnumerator<T> GetEnumerator();
}

Az iteráció állapotát tartalmazó IEnumerator<T> pedig:

public interface IEnumerator<out T> : IDisposable, IEnumerator {
    T Current { get; }
}

public interface IEnumerator {
    object Current { get; }
    bool MoveNext();
    void Reset();
}

Az enumerálás nem atomi, kít hívás váltogatásával zajlik: Egy MoveNext() majd egy Current, és így tovább. Mivel nem atomi, így az egész objektumot kell lockolni, hogy egy elem se maradjon ki, vagy szerepeljen kétszer. Ezért a PLINQ és a Parallel.ForEach, kénytelen maga megoldani a lockolást, cachelést az enumerátorból érték vételezésre. Azt viszont feltételezik, mert a párhuzamos feldolgozáshoz szükséges, hogy az enumerátortól visszakapott értékek függetlenek, azaz lehet rajtuk párhuzamosan dolgozni.

Vissza a bankkártyaszámokhoz

A tippelt érték számjegyekké alakítását egy 0-val balról paddelt formázott nyomtatással oldottam meg. Lehet fintorogni, de ez egy letesztelt, helyes algoritmus, amit készen szállít a BCL. Nem akartam tesztet és kódot írni egy ilyen a célom szempontjából mellékes dologra. A nullával paddeléshez a megfelelő format stringet a C# 6.0 String Interpolation funkciójával oldottam meg. Ez egy kényelmes funkció, legalábbis némi groovyzás után jó, hogy itt is tudom használni.

Rakjuk össze

Ezekből a komponensekből összeállítható végre a feladat megoldása:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CreditCardNumberGuesser {
    class Program {
        static void Main(string[] args) {
            var gen = new CreditCardNumberSequenceGenerator("5334 12** **** 1234");

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            var valids = gen.AsParallel().Where(ccn => ccn.IsValid()).OrderBy(ccn => ccn.ToString()).ToArray();
            sw.Stop();

            foreach( var ccn in valids) {
                Console.WriteLine(ccn);
            }

            Console.WriteLine();
            Console.WriteLine($"That is a total {valids.Length} valid credit card numbers");
            Console.WriteLine($"Took {sw.Elapsed} to calculate");

            Console.Write("Press any key to exit...");
            Console.ReadKey();
        }
    }
}

Eredmény

A program futása tanulságos: Ha X a hiányzó számjegyek száma, akkor 10^(X-1) érvényes kombináció adódik. Ez logikus is, hisz ha 1 számjegy hiányzik, azt a hibajavító kódból helyre lehet állítani. Ha 1-nél több hiányzik, akkor tetszőleges számot választva visszavezetjük az egyel kevesebb hiányzó számjegyes esetre, míg az utolsó esetben már adott, hogy mi az egyetlen lehetséges hiányzó elem. Ez programozás nélkül is leeshetett volna. 😞

A teljes kód (angol kommentekkel) letölthető lehetne, ha nem lennék lusta összecsomagolni. Ollózd ezt össze, ha használni akarod 😎.

És ha már bank és kártya: a Payday 2-ben sikerült hírhedtté válnom: Megvan a Joker kártyám! A sok bankrablás meghozta az eredményét! Igaz, azóta rá is untam a játékra, a fejlesztők antipatikus üzletpolitikája miatt: Újabb DLC-khez meg kellene újra vennem egy csomagban azokat, amiket már megvettem. Ez is tiszta bankrablás 😠!

A Mézga család Paulája mondta mindig, amikor egy a jövőből küldött csodára még nem volt elég érett az atom-ókori szocialista kispolgárság, hogy:

Bárcsak a Huffnágel Pistához mentem volna feleségül!

Ugyanezt mondja az a Linux felhasználó, aki nem tud újrafordítgatás nélkül videót lejátszani 2017-ben sem, míg mások Windows alatt futtatnak natívan linux programokat (és a videólejátszás a már 20 éve is működött). A Microsoft boszorkánykonyhájában ugyanis kifőztek valamit, amire talán még nem elég érett a mi korunk. Linux emuláció natív linux kód rendszerhívásainak feldolgozásával, a Windows Subsystem for Linux segítségével. Az közelgő őszi Windows 10 frissítéssel sokat javul állítólag, és én már korlátozottan használni is tudtam. No de mindez hogyan lehetséges?

Részletesen bemutatja nekünk Steve Huffnagel, egyenesen Redmondból! Valójában persze üzenet a múltból ez, hisz több mint egy éve várt már ez a geg a noteszomban!

A cikk itt érhető el.

Van egy növény, amit gyermekkorom óta ismerek, de a nevét nem ismerem. Megkérdeztem tanult barátomat!

- Van az a cucc ami olyan mint a búza, és a lányok hajába lehet dobálni. Nem tudod mi a neve?
- Toklász! Valaminek, aminek ekkora kulturális jelentősége van, ne lenne népi neve?

Azt is megtudtam, hogy a lányoknál csak a kutyák utálhatják jobban, ugyanis a kutyák mancsát, fülét, szemét is bántja a növény. Vigyázzatok a kutyákra, dobáljatok minden toklászt a lányok hajába!

Hosszú kihagyás után ismét jelenkezem, egy olvasónaplóval.

Harry Harrison tollából olvastam már a Bill a Galaxis hőse című szatírikus regényt. Kiváló olvasmánynak találtam, gondoltam szerencsét próbálok más írásaival is. Így esett az Édentől nyugatra című írására a választásom.

Az Édentől nyugatra témája egy fiatal ember élete egy olyan világban, melyet értelmes hüllők civilizációja ural. A domináns faj, a jilanék értemes dinoszauroszok, és civilizácójuk biotechnológián alapul, ellenben az általunk ismert fizikai technológiákon. Az egész bolygó meleg klímájú részét benépesítik, városállamokban élnek. Az “emberek” a kőkorszakban járnak még a történet idején, és törzsekben élve folytatják nomád halász-vadász életmódjukat. A hidegebb részeken élnek, mivel a domináns fajjal érintkezést kerülik. Egy kezdődő jégkorszak miatt azonban délebbre kényszerülnek, és elkezdődnek a konfliktusok a két értelmes faj között. A hüllők eleinte nem feltételezik, hogy értelmes lények az emberek, háziállatnak akarják betanítani a főhőst, egy fogságba esett fiút…

A történet így indul, és fokozódik, tekergődzik. Nem volt rossz a regény, de nem lett a kedvencem. Az Éden-trilógia két folytatás kötetét is elolvastam, nem csalódtam nagyot, de nem is lett top-listás. Végig fenntartotta az érdeklődésem, hogy mi lesz a vége, de csak egy ⁷⁄₁₀-et tudok adni neki.

Azt hiszem, hogy a szatírára nyitottabb vagyok mostanság. A Bill a galaxis hőse sokkal jobban tetszett Harrisontól.

Már korábban is beszámoltam múzeális /g/ tier Lenovo X200-as számítógépem driver nyűgjeiről. Mivel elkészült az új Visual Studio, és a csodás uninstaller csak hellyel-közzel működött, ezért kénytelen vagyok a számítógépet újratelepíteni. Ezen felül amúgy is teleszemeteltem már mindenféle vacakokkal, mint Epson nyomtató driver, PLC-k segédprogramjai, Eclipse. Soha ne tegyetek fel ilyen szemetet a számítógépetekre!

Szerencsére a Windows 8.1 óta nem kell aggódni, van erre egy PowerShell commandlet. Így tehát félretettem a PowerShell iránti ellenszenvem, és egy adminisztrátori konzolba begépeltem:

Export-WindowsDriver -Online -Destination P:\x200\drivers

És máris a pendriveomon landolt a notebook működő drivercsomagja! Meglátjuk, hogy ez a módszer valóban annyival intelligensebb-e a hagyományos mosópornál, és a szájam fékezett habzású lesz-e, amikor megpróbálom visszaállítani ebből a gép működő állapotát! :)