💳Kártya jóslás

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 minimláisan 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 ntipatikus üzletpolitikája miatt: Újabb DLC-khez meg kellene újra vennem egy csomagban azokat, amiket már megvettem. Ez is tiszta bankrablás 😠!