Datorschack

Det är förmodligen möjligt att bygga ett datorchack utan mer kunskap än själva spelreglerna. Man måste veta hur pjäserna får förflytta sig, inklusive specialdragen (uppgradering, passant, rockad), att inte egna kungen får ställas i schack och kriterierna för vinst, förlust eller möjligtvis remi (och kriterierna för remi).

Som mänsklig spelare kan man troligtvis inte analysera alla tänkbara drag speciellt långt in i framtiden (åtminstone kan inte jag göra det) utan får istället jobba med strategier som t.ex. skulle kunna vara att identifiera spelplanskonfigurationer där vissa drag tenderar att vara mer eller mindre lönsamma.

En dator som spelar mot en människa borde kunna göra en grundlig analys av spelplanen för att veta vilket drag som öppnar för ett framtida segerdrag, och tittar man på logiken bakom en sådan implementation så är den inte speciellt avancerad. Men det håller inte.

Låt säga att varje given konfiguration av schackbrädet har 40 rimliga drag. Det innebär att 40 bräden i nästa generation måste analyseras för att se vilket drag som är lönsamt eller ej. Men det ligger också i sakens natur att ett drag som inte direkt ger något, kan vara antingen förödande eller väldigt lönsamt längre fram. Så varför inte kosta på sig att titta på varje drags nästa generation?

I snitt har varje nästa generation 40 rimliga drag, vilket innebär att vi måste analysera ytterligare 40*40 (1600) drag. Men det är förmodligen inte slut där. För att hitta ljuset i tunneln behöver man troligen titta på draget därefter, där varje alternativ i sin tur har 40 rimliga konsekvenser (40 * 1600) vilket ger oss 64 000 spelplaner att analysera. Om matchen sträcker sig över tre drag måste vi titta på (64 000 * 40) 2,5 miljoner drag. Och så håller det på.

Låt oss fortsätta att anta att varje given situation i snitt bjuder 40 rimliga drag, så ger det följande effekt:

1 drag kräver 1 600 analyser.
2 drag kräver 64 tusen analyser.
3 drag kräver 2,6 miljoner analyser.
4 drag kräver 102 miljoner analyser.
5 drag kräver 4 miljarder analyser.
6 drag kräver 164 miljarder analyser.
7 drag kräver 6 554 miljarder analyser.
8 drag kräver 262 144 miljarder analyser.
9 drag kräver 10 485 760 miljarder analyser.
10 drag kräver 419 430 400 miljarder analyser.

Men eftersom vi inte vet vad den mänskliga spelaren tänker göra, måste vi efter varje tänkt drag skapa en gren för varje rimligt motdrag. Så egentligen ser 10 generationer ut så här:

1 drag kräver 1 600 analyser samt ytterligare 64 000 analyser av möjliga motdrag.
2 drag kräver 2,6 miljoner analyser samt ytterligare 102 miljoner analyser av möjliga motdrag.
3 drag kräver 4 miljarder analyser samt ytterligare 164 miljarder analyser av möjliga motdrag.
4 drag kräver 6 553 miljarder analyser samt ytterligare 262 144 miljarder analyser av möjliga motdrag.
5 drag kräver 10 485 760 miljarder analyser samt ytterligare 419 430 400 miljarder analyser av möjliga motdrag.
6 drag kräver 16 777 216 biljoner analyser samt ytterligare 671 088 640 biljoner analyser av möjliga motdrag.
7 drag kräver 26 843 triljoner analyser samt ytterligare 1 073 741 triljoner analyser av möjliga motdrag.
8 drag kräver 42 949 672 triljoner analyser samt ytterligare 1 717 986 918 triljoner analyser av möjliga motdrag.
9 drag kräver 68 719 476 triljarder analyser samt ytterligare 2 748 779 kvadriljoner analyser av möjliga motdrag.
10 drag kräver 109 951 kvadriljarder analyser.

Och eftersom en analys tar några bytes att hålla i datorns arbetsminne, kan man konstatera att det fallerar av den anledningen. Processtiden även på en väldigt stark dator kommer vara ett annat problem.

Genom att lära sig strategier kan man identifiera vilka situationer man bör undvika och vilka situationer man bör premiera, och på så vis reducera antalet analyser som behöver göras. Vilka öppningar är bra? Kanske ungefär 5 över 2 generationer. Då har vi åtminstone i startsituationen reducerat från över hundra miljoner analyser till en handfull. Ju fler sådana strategier man har, desto fler nonsensanalyser skär man bort. Men frågan är hur långt man kan komma genom att slumpa vilka analyser som faktiskt ska göras? Kan ett enkelt C#-program vinna mot en seriös schackdator genom att slumpmässigt välja vilka grenar som ska analyseras på vilket djup?

Ni med näsduk i kavajfickan spottar på vårt kulturarv!

Idag uppmuntrade jag en konstnär att måla en upphittad C64 i en Facebook-grupp.

Jag skrev bl.a. att jag själv lackade min Amiga på 80-talet. Det hela eskalerade ganska fort.

Ok, fel av mig. Givetvis ska man vara rädd om gamla grejer, oavsett om det bara handlar om färgen på ett chassi. Hur som helst så frågade jag vad mer man behöver för att kunna laga den ifall den går sönder.

Och vips spottar man på “vårt gemensamma kulturarv”. Jag skulle kanske ha sagt att den C64 som ligger i en container ska stanna i en container. Eller skippa näsduken nästa gång.

Här tar jag betalt för att spotta på kulturarvet:

Några exponeringar från idag

Idag hälsade jag på hos mitt äldsta barn som, förutom katter och en hund, har en hel del inneboende reptiler. Här är mitt Instagram-inlägg från dagen:

Och här är alla andra exponeringar:

Produktionskostnad/vinst-förhållandet för misslyckade uppföljare

Det är ofta ett säkert kort inom filmindustrin att göra en uppföljare, eftersom man kan spela an på en framgång. Det blir ett slags varumärkesexploatering som inte alltid utnyttjar sin fulla potential. Ibland blir inte uppföljaren lika bra som sin föregångare, och här är tre exempel på hur budget förhåller sig till bruttointäkt i filmserier som inte lyckades följa upp sitt original. De filmer som inte når upp till 1,0 har alltså inte dragit in pengarna de kostade att producera, och här är tre exempel på “dåliga uppföljare”. Så här ser en flopp ut:

Highlander, inspelningsbudget och bruttointäkt (miljoner dollar):

Förhållande, inspelningsbudget och bruttointäkt:

Stålmannen, är en filmserie som varit igång sedan 1940-talet, men för de tidigaste filmerna är det inte riktigt känt vilka pengar som var inblandade, så här är inspelningsbudget och bruttointäkt (miljoner dollar) en bit in i serien, när Christopher Reeve klev in i serien:

Förhållande, inspelningsbudget och bruttointäkt:

Här ser vi exempel på där pengarna som står på spel varit så extremt framgångsrik i sitt ursprungsförfarande, så att jag var tvungen att introducera en decimal. Och trots att uppföljaren var en total flopp, så har den så pass stöd från sitt varumärke att siffrorna framöver varit svarta. Precis som i fallet med Stjärnornas krig, så har vi inte riktigt facit för filmserien än, för fler filmer är planerade i serien.

Alla helgons blodiga natt, inspelningsbudget och bruttointäkt (miljoner dollar):

Förhållande, inspelningsbudget och bruttointäkt:

Del 1.

Produktionskostnad/vinst-förhållandet för Star Wars, Elm Street och The Terminator

Vissa filmer får uppföljare och spin offs till synes utan ände. Inte sällan efter en framgångsrik start, verkar bolagen vara redo att skjuta till mer pengar för att krama mer ur det varumärke som utgör en framgångsrik film. Här är pengarna som satsats och spelats in från tre kända filmserier.

Star Wars, inspelningsbudget och bruttointäkt (miljoner dollar):

Förhållande, inspelningsbudget och bruttointäkt:

Gissningsvis kommer den näst sista filmen dra in lite mer pengar över åren, och för den sista filmen finns ingen uppgift om intäkter än. Förmodligen kommer den vara mer lönsam i förhållande till vad den kostat än de två tidigare filmerna.

Terror på Elm Street, inspelningsbudget och bruttointäkt (miljoner dollar):

Förhållande, inspelningsbudget och bruttointäkt:

I den sista filmen, som är en nyinspelning av den första, är det inte Robert Englund som spelar Freddy Krueger.

The Terminator, inspelningsbudget och bruttointäkt (miljoner dollar):

Förhållande, inspelningsbudget och bruttointäkt:

Så troligen är det ett bra förhållande mellan satsade och tjänade pengar som avgör hur många uppföljare en film får.

Del 2.

Metabollar

Jag tänkte visa en komplett implementation av 2-dimensionella metabollar i C#. Denna teknik skulle även kunna användas i 3D. Effekten ser ut så här:

Effekten beskrivs här, och denna implementation prioriterar prestanda för att fungera i realtid. I videon ovan används 20 positiva bollar (alltså bollar som tenderar att smeta ihop) och 10 negativa bollar (alltså bollar som tenderar att sluka andra bollar) och samtliga rör sig i sinusbanor på en yta av 320×200 pixlar. Renderingen bygger på Windows Forms och klassen Bitmap.

För att få rörelserna mjuka har jag satt formulärets egenskap DoubleBuffered till true. Dessutom har jag placerat en Timer på formuläret och satt dess Interval till 1 för att få så bra prestanda som möjligt utan att köra dedikerat, men om man ställer ännu högre krav på användarupplevelsen, skulle man välja ett annat bibliotek än Windows Forms. Dessa inställningar har jag ställt in i Visual Studio, så de syns inte i koden.

Här är formulärets kod:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Windows.Forms;

namespace Metaballs
{
    public partial class Form1 : Form
    {
        private IRenderer _renderer;
        private Bitmap _bitmap;
        private int[,] _pixels;
        private double _counter = 0.0;
        private readonly List<Ball> _balls = new List<Ball>();
        
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Shown(object sender, EventArgs e)
        {
            Refresh();
            _renderer = new MetaRenderer();
            _bitmap = new Bitmap(320, 200);
            _pixels = new int[320, 200];
            for (var i = 0; i < 30; i += 3)
            {
                _balls.Add(new Ball(MovementDescription.Randomize(), i, false));
                _balls.Add(new Ball(MovementDescription.Randomize(), i + 1, false));
                _balls.Add(new Ball(MovementDescription.Randomize(), i + 2, true));
            }
            timer1.Enabled = true;
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            //Clear array.
            for (var y = 0; y < 200; y++)
                for (var x = 0; x < 320; x++)
                    _pixels[x, y] = 0;

            foreach (var ball in _balls)
                _renderer.Apply(ball, _pixels);
            
            //Draw.
            _renderer.Draw(_pixels, _bitmap);
            foreach (var ball in _balls)
                ball.Tick(_counter);

            _counter += 1.0;
            Refresh();
        }

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            if (_bitmap == null)
                return;
            e.Graphics.InterpolationMode = InterpolationMode.NearestNeighbor;
            e.Graphics.DrawImage(_bitmap, 0, 0, 640, 400);
        }
    }
}

De resurser som används är _renderer som ansvarar för att bestämma hur bollarna påverkar varandra och hur det ska se ut, _bitmap som är ytan jag renderar till, _pixels som är min matris för beräkningar, _counter som används för sinusbanorna och _balls som är mina metabollar. Notera att jag, likt inställningarna jag nämnde tidigare, låtit Visual Studio mappa upp mina events, så dessa syns inte i koden. Men de kan läsas av från namngivningen av procedurerna.

Som synes av den sista kodraden zoomar jag resultatet med 50%. Om man vill se resultatet i naturlig storlek behöver man inte ange InterpolationMode (efter som ingen pixelinterpolering då sker) eller någon ny storlek (640, 400).

Jag har valt att peka ut renderingen med ett interface (IRenderer) eftersom det är mycket troligt att man vill ha olika renderingskod under tiden man designar sitt alster och när man är nöjd. T.ex. är det rimligt att man tydligt vill se sina bollar flytta sig över skärmen när man kalibrerar deras banor, men när det är färdigt vill man självklart se hur de påverkar varandra, eftersom det är det som är syftet (och det som visas i videon ovan). Här är IRenderer:

using System.Drawing;

namespace Metaballs
{
    public interface IRenderer
    {
        void Apply(Ball source, int[,] target);
        void Draw(int[,] source, Bitmap target);
    }
}

En debug-implementation kanske skulle låta Apply färgsätta de individuella bollarna olika och låta Draw visa det. Däremot är en produktionsimplementation av IRenderer hjärtat i programmet. Där skulle Apply addera eller subtrahera en boll på spelplanen, och Draw skulle visa en kontur baserat på det. En boll (Ball) representerar en position och en rörelse för en boll, och för att kunna hitta tröskelvärden när två bollar är nära varandra, består dessa av en cirkel med låga värden nära konturen och höga värden nära centrum. På så vis kan en godtycklig kontur skapas från summan som skapas när bollarna adderats till ytan (eller subtraherats, för de negativa bollarna). I min implementation är varje boll 98×98 pixlar stor, varför deras centrum ligger 49 pixlar i varje riktning från sin position, vilket framgår av Apply:

using System.Drawing;

namespace Metaballs
{
    public class MetaRenderer : IRenderer
    {
        private Color[] _colors;

        public MetaRenderer()
        {
            _colors = new Color[100];
            for (var i = 0; i < _colors.Length; i++)
                _colors[i] = Color.Black;
            var j = 60;
            for (var c = 0; c < 255; c += 30)
            {
                _colors[j] = Color.FromArgb(c, c, c);
                j++;
            }
            for (var c = 255; c >= 0; c -= 30)
            {
                _colors[j] = Color.FromArgb(c, c, c);
                j++;
            }
        }

        public void Apply(Ball source, int[,] target)
        {
            var ballX = (int)source.X - 49;
            var ballY = (int)source.Y - 49;
            for (var y = 0; y < 98; y++)
            {
                for (var x = 0; x < 98; x++)
                {
                    var xp = ballX + x;
                    if (xp < 0 || xp >= 320)
                        continue;
                    var yp = ballY + y;
                    if (yp < 0 || yp >= 200)
                        continue;
                    if (source.Negative)
                        target[xp, yp] -= DataDefinitions.Ball98[x, y];
                    else
                        target[xp, yp] += DataDefinitions.Ball98[x, y];
                }
            }
        }
        
        public void Draw(int[,] source, Bitmap target)
        {
            for (var y = 0; y < 200; y++)
            {
                for (var x = 0; x < 320; x++)
                {
                    target.SetPixel(x, y,
                        source[x, y] < _colors.Length
                        && source[x, y] >= 0
                            ? _colors[source[x, y]]
                            : Color.Black);
                }
            }
        }
    }
}

(Anti-aliasing-effekten uppnås av den toning som konfigureras i konstruktorn ovan.) Så här ser en boll ut:

using System;
   
   namespace Metaballs
   {
       public class Ball
       {
           private const double CenterX = 159.0;
           private const double CenterY = 99.0;
           private readonly MovementDescription _d;
           
           public double X { get; private set; }
           public double Y { get; private set; }
           public int Index { get; }
           public bool Negative { get; }
           
           public Ball(MovementDescription movementDescription, int index, bool negative)
           {
               _d = movementDescription;
               Index = index;
               Negative = negative;
               X = 159;
               Y = 99;
           }
   
           public void Tick(double counter)
           {
               X = CenterX + Math.Sin(counter / _d.SinFactor1) * _d.SinRadius1
                           + Math.Sin(counter / _d.SinFactor2) * _d.SinRadius2;
               Y = CenterY + Math.Cos(counter / _d.CosFactor1) * _d.CosRadius1
                           + Math.Cos(counter / _d.CosFactor2) * _d.CosRadius2;
           }
       }
   }

MovementDescription är en struktur som samlar data om hur sinusbanan ska se ut. Som man kunde ana från huvudprogrammet erbjuder strukturen en möjlighet att låta slumpen avgöra hastighet och radie.

using System;

namespace Metaballs
{
    public struct MovementDescription
    {
        private static Random Rnd;
        public double SinFactor1 { get; }
        public double SinFactor2 { get; }
        public double CosFactor1 { get; }
        public double CosFactor2 { get; }
        public double SinRadius1 { get; }
        public double SinRadius2 { get; }
        public double CosRadius1 { get; }
        public double CosRadius2 { get; }

        
        static MovementDescription()
        {
            Rnd = new Random();
        }
        
        public MovementDescription(
            double sinFactor1,
            double sinFactor2,
            double cosFactor1,
            double cosFactor2,
            double sinRadius1,
            double sinRadius2,
            double cosRadius1,
            double cosRadius2)
        {
            SinFactor1 = sinFactor1;
            SinFactor2 = sinFactor2;
            CosFactor1 = cosFactor1;
            CosFactor2 = cosFactor2;
            SinRadius1 = sinRadius1;
            SinRadius2 = sinRadius2;
            CosRadius1 = cosRadius1;
            CosRadius2 = cosRadius2;
        }

        public static MovementDescription Randomize() =>
            new MovementDescription(
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100),
                Rnd.Next(10, 100)
            );
    }
}

Därmed är det enda som återstår själva bollen som ovan refereras till som Ball98, uppkallad efter sina sidors storlek. För att göra det enkelt, ritade jag boll genom att välja penselverktyget i Photoshop och skrev ett enkelt program som konverterade det hela till en int array i C#, enligt följande:

namespace Metaballs
{
    public class DataDefinitions
    {
        public static int[,] Ball98 = new int[98, 98]
{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 3, 3, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 4, 4, 4, 4, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 3, 4, 3, 4, 5, 5, 5, 6, 5, 5, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 5, 5, 4, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 3, 2, 2, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 6, 7, 8, 9, 9, 9, 9, 9, 10, 10, 9, 9, 10, 10, 10, 9, 9, 10, 9, 9, 8, 9, 8, 8, 8, 7, 7, 6, 6, 5, 4, 5, 4, 4, 3, 2, 3, 3, 3, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 9, 10, 10, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 11, 11, 11, 10, 10, 10, 9, 9, 8, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 9, 9, 10, 10, 11, 12, 12, 13, 13, 14, 14, 14, 15, 15, 14, 14, 15, 15, 14, 14, 13, 13, 13, 12, 11, 12, 11, 10, 9, 8, 8, 7, 6, 6, 5, 5, 4, 5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 8, 8, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 16, 16, 17, 17, 17, 17, 17, 17, 16, 16, 16, 15, 15, 14, 14, 14, 13, 11, 11, 10, 10, 9, 8, 8, 7, 7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 9, 11, 11, 12, 13, 14, 15, 16, 16, 17, 18, 19, 19, 20, 20, 20, 20, 21, 20, 20, 20, 20, 19, 19, 18, 18, 17, 16, 16, 15, 14, 13, 12, 12, 11, 9, 9, 8, 7, 6, 6, 5, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 8, 9, 10, 11, 13, 13, 14, 15, 16, 16, 17, 19, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 23, 23, 22, 21, 21, 21, 19, 19, 19, 18, 17, 14, 15, 14, 12, 11, 10, 9, 8, 7, 7, 5, 5, 5, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 7, 7, 7, 9, 11, 11, 12, 13, 15, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 27, 27, 27, 27, 26, 25, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 14, 13, 12, 11, 11, 9, 7, 8, 6, 6, 6, 5, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 7, 7, 9, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 23, 23, 25, 25, 26, 28, 28, 29, 31, 31, 31, 32, 32, 31, 31, 31, 31, 31, 30, 29, 28, 26, 25, 25, 23, 22, 21, 19, 18, 17, 15, 14, 13, 11, 11, 10, 8, 8, 7, 6, 6, 5, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 11, 12, 13, 15, 16, 18, 20, 20, 21, 23, 26, 26, 28, 29, 30, 32, 33, 33, 35, 35, 36, 36, 36, 36, 36, 36, 35, 35, 34, 33, 32, 30, 29, 28, 27, 25, 23, 21, 21, 20, 18, 16, 15, 13, 12, 11, 9, 8, 8, 6, 6, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 17, 18, 20, 22, 24, 25, 27, 29, 30, 32, 34, 35, 37, 37, 39, 40, 41, 42, 42, 42, 42, 42, 42, 41, 40, 38, 37, 36, 35, 33, 32, 30, 29, 27, 25, 23, 22, 20, 18, 17, 15, 14, 13, 11, 10, 9, 8, 7, 6, 5, 4, 4, 4, 3, 3, 2, 1, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 7, 8, 10, 10, 11, 12, 14, 16, 17, 19, 22, 24, 26, 27, 29, 31, 33, 35, 37, 39, 40, 42, 43, 44, 45, 46, 47, 48, 48, 48, 48, 47, 46, 46, 44, 44, 42, 40, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 20, 18, 16, 15, 13, 11, 10, 9, 8, 7, 5, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 7, 7, 8, 9, 11, 13, 14, 16, 18, 20, 22, 25, 27, 29, 30, 33, 35, 37, 40, 42, 43, 45, 47, 49, 50, 52, 53, 53, 54, 54, 54, 54, 53, 52, 52, 50, 49, 47, 45, 44, 41, 39, 38, 35, 33, 30, 29, 27, 25, 22, 20, 18, 16, 14, 13, 11, 9, 8, 7, 7, 5, 5, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 6, 7, 7, 9, 10, 11, 13, 15, 16, 18, 20, 23, 25, 27, 30, 32, 35, 38, 40, 43, 45, 47, 49, 51, 53, 55, 56, 58, 59, 60, 60, 60, 60, 60, 59, 59, 58, 56, 55, 53, 51, 50, 47, 45, 42, 40, 38, 35, 32, 30, 27, 24, 22, 20, 18, 16, 15, 13, 11, 10, 9, 7, 7, 6, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 9, 10, 11, 12, 15, 17, 19, 21, 23, 26, 29, 31, 34, 36, 39, 42, 45, 48, 50, 52, 56, 58, 60, 62, 63, 65, 66, 67, 68, 68, 68, 68, 67, 66, 66, 64, 62, 60, 58, 55, 53, 51, 48, 44, 42, 39, 36, 34, 30, 28, 26, 23, 21, 19, 16, 14, 12, 11, 10, 9, 7, 6, 5, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8, 10, 11, 12, 15, 16, 18, 21, 24, 26, 29, 32, 34, 37, 40, 43, 47, 49, 53, 56, 59, 62, 65, 67, 69, 71, 73, 74, 75, 76, 76, 76, 76, 75, 74, 73, 71, 69, 67, 65, 62, 59, 55, 53, 50, 47, 43, 40, 37, 34, 32, 29, 26, 24, 21, 18, 17, 14, 12, 11, 9, 7, 7, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 17, 18, 20, 23, 26, 29, 32, 34, 38, 42, 45, 48, 52, 55, 59, 62, 65, 68, 72, 74, 77, 79, 81, 82, 83, 84, 84, 85, 84, 83, 82, 81, 79, 76, 74, 72, 69, 65, 61, 59, 56, 52, 49, 45, 41, 38, 35, 32, 28, 26, 23, 20, 19, 16, 14, 13, 10, 9, 8, 6, 6, 5, 5, 3, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 21, 23, 26, 29, 32, 35, 39, 42, 46, 49, 53, 57, 61, 65, 68, 72, 76, 79, 82, 85, 87, 89, 91, 92, 93, 93, 93, 93, 91, 91, 89, 86, 84, 82, 79, 76, 72, 69, 65, 61, 57, 54, 49, 45, 41, 38, 35, 32, 29, 26, 23, 21, 18, 15, 14, 11, 10, 9, 8, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4, 5, 6, 7, 9, 9, 11, 12, 15, 17, 20, 23, 25, 28, 32, 35, 39, 42, 46, 50, 54, 59, 63, 67, 71, 75, 80, 84, 87, 90, 93, 96, 98, 99, 100, 102, 102, 103, 102, 100, 99, 98, 96, 93, 90, 87, 83, 79, 75, 71, 67, 63, 59, 54, 51, 46, 42, 38, 35, 32, 28, 25, 23, 20, 17, 15, 12, 11, 10, 8, 7, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 4, 4, 5, 6, 7, 8, 10, 11, 13, 14, 17, 19, 22, 25, 27, 30, 35, 39, 42, 46, 50, 56, 60, 65, 69, 73, 78, 83, 87, 92, 96, 99, 102, 106, 108, 110, 111, 113, 113, 113, 113, 111, 109, 107, 105, 102, 99, 95, 91, 87, 82, 78, 74, 70, 64, 60, 56, 50, 46, 42, 38, 34, 30, 27, 25, 22, 19, 17, 14, 13, 11, 10, 8, 7, 6, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0}, 
{0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 9, 11, 11, 13, 16, 18, 21, 24, 27, 30, 34, 37, 42, 46, 50, 55, 61, 65, 70, 75, 80, 85, 90, 95, 100, 104, 107, 111, 115, 117, 120, 121, 122, 122, 122, 122, 121, 119, 117, 114, 111, 107, 104, 99, 94, 90, 85, 80, 75, 70, 65, 61, 55, 50, 46, 42, 37, 33, 30, 27, 24, 21, 18, 16, 13, 12, 10, 8, 7, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0}, 
{0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 20, 23, 26, 29, 33, 37, 40, 45, 50, 54, 60, 65, 70, 76, 83, 88, 92, 98, 103, 108, 112, 117, 121, 125, 127, 130, 131, 132, 133, 133, 132, 131, 130, 127, 125, 121, 117, 112, 108, 103, 97, 92, 87, 81, 77, 72, 66, 59, 54, 50, 45, 42, 37, 33, 30, 26, 23, 20, 17, 14, 12, 11, 9, 8, 7, 5, 5, 4, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0}, 
{0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 9, 10, 12, 14, 16, 19, 22, 25, 28, 31, 34, 40, 45, 49, 54, 60, 65, 70, 76, 82, 88, 94, 100, 106, 112, 116, 121, 126, 130, 134, 137, 140, 141, 143, 144, 144, 143, 141, 140, 137, 134, 130, 125, 121, 117, 112, 106, 100, 95, 89, 82, 76, 71, 64, 59, 54, 49, 44, 40, 36, 32, 28, 25, 22, 19, 16, 14, 13, 11, 9, 8, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0}, 
{0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 5, 6, 8, 10, 11, 12, 15, 17, 20, 23, 27, 30, 33, 38, 42, 47, 52, 58, 64, 70, 76, 83, 88, 94, 101, 108, 114, 120, 125, 131, 135, 139, 144, 148, 150, 152, 154, 154, 154, 154, 152, 150, 147, 143, 139, 135, 131, 125, 120, 114, 108, 101, 94, 88, 81, 75, 70, 64, 58, 52, 47, 43, 38, 34, 30, 27, 23, 20, 17, 15, 13, 11, 9, 7, 7, 5, 4, 4, 3, 2, 2, 2, 2, 1, 1, 0, 0}, 
{0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 9, 10, 11, 13, 16, 18, 22, 25, 28, 33, 37, 41, 46, 51, 56, 62, 68, 74, 81, 89, 94, 101, 108, 115, 121, 127, 134, 139, 144, 150, 154, 158, 160, 162, 164, 164, 164, 164, 162, 160, 157, 154, 150, 144, 139, 134, 129, 121, 115, 108, 101, 95, 89, 81, 74, 68, 62, 56, 51, 46, 41, 37, 33, 29, 25, 21, 18, 16, 13, 11, 10, 8, 7, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0}, 
{0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 6, 6, 7, 9, 11, 13, 15, 18, 20, 24, 27, 30, 35, 38, 43, 49, 54, 60, 66, 72, 79, 86, 94, 101, 108, 115, 122, 129, 136, 143, 148, 153, 159, 163, 167, 171, 173, 175, 175, 175, 175, 173, 171, 167, 164, 160, 154, 148, 143, 136, 130, 122, 115, 108, 101, 94, 86, 79, 73, 66, 60, 55, 49, 44, 39, 34, 31, 27, 23, 20, 18, 15, 12, 11, 10, 8, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0}, 
{0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 6, 7, 8, 10, 12, 14, 16, 18, 21, 24, 27, 32, 37, 40, 46, 52, 58, 63, 70, 77, 84, 93, 99, 106, 114, 121, 129, 137, 144, 151, 158, 164, 169, 173, 177, 181, 183, 185, 186, 186, 186, 184, 181, 178, 174, 170, 164, 158, 151, 144, 137, 130, 121, 114, 106, 99, 92, 84, 77, 70, 63, 57, 52, 47, 41, 37, 32, 27, 24, 21, 18, 16, 13, 11, 10, 8, 6, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0}, 
{0, 0, 1, 1, 2, 2, 2, 4, 4, 4, 6, 7, 8, 10, 13, 14, 16, 19, 22, 26, 29, 33, 38, 43, 48, 54, 61, 67, 73, 80, 88, 96, 104, 112, 120, 128, 136, 144, 152, 159, 165, 173, 178, 183, 187, 191, 193, 195, 196, 196, 195, 193, 190, 187, 183, 178, 173, 167, 160, 152, 144, 136, 128, 120, 112, 104, 96, 88, 80, 74, 68, 61, 55, 49, 43, 38, 34, 30, 26, 22, 19, 17, 15, 12, 10, 8, 7, 6, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1}, 
{0, 1, 1, 1, 2, 2, 2, 4, 4, 5, 7, 7, 9, 11, 13, 15, 17, 21, 24, 28, 31, 35, 40, 46, 51, 57, 64, 71, 77, 84, 92, 101, 110, 118, 127, 135, 143, 152, 160, 167, 174, 181, 187, 192, 196, 200, 203, 205, 206, 206, 205, 203, 200, 197, 192, 187, 181, 174, 167, 159, 152, 143, 135, 126, 118, 109, 101, 94, 85, 77, 71, 64, 57, 51, 47, 40, 35, 32, 28, 24, 20, 18, 16, 13, 11, 9, 8, 7, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 2, 2, 2, 4, 4, 5, 7, 7, 9, 11, 13, 16, 18, 21, 25, 29, 33, 37, 42, 47, 53, 59, 67, 74, 80, 89, 96, 105, 114, 122, 132, 140, 149, 159, 166, 174, 181, 189, 195, 200, 205, 208, 211, 214, 215, 214, 214, 212, 209, 205, 200, 195, 189, 181, 174, 166, 159, 149, 140, 131, 123, 114, 105, 98, 89, 80, 73, 66, 59, 53, 47, 42, 37, 32, 29, 24, 21, 18, 15, 13, 11, 9, 8, 7, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 10, 12, 14, 16, 18, 22, 26, 28, 33, 38, 44, 49, 55, 62, 69, 76, 84, 93, 100, 109, 118, 127, 136, 146, 155, 164, 173, 181, 188, 195, 202, 208, 213, 217, 220, 222, 223, 223, 222, 220, 217, 213, 208, 202, 195, 188, 181, 173, 164, 155, 146, 136, 127, 118, 109, 100, 93, 84, 76, 69, 61, 56, 49, 43, 38, 33, 29, 25, 22, 18, 16, 14, 12, 10, 8, 7, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1}, 
{1, 1, 1, 2, 2, 2, 3, 4, 5, 5, 7, 8, 10, 12, 15, 16, 20, 23, 27, 31, 35, 40, 45, 51, 57, 64, 72, 80, 88, 95, 103, 113, 122, 132, 141, 152, 161, 169, 179, 187, 195, 202, 209, 215, 220, 224, 227, 229, 230, 230, 229, 226, 224, 220, 215, 209, 202, 195, 187, 178, 170, 161, 151, 141, 131, 122, 113, 104, 96, 87, 79, 72, 64, 57, 51, 46, 40, 35, 31, 27, 23, 20, 16, 14, 12, 10, 9, 8, 6, 5, 4, 3, 2, 2, 2, 1, 1, 0}, 
{1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 17, 21, 24, 28, 32, 36, 41, 46, 52, 59, 65, 73, 81, 89, 99, 107, 116, 127, 137, 147, 156, 165, 175, 183, 193, 201, 208, 214, 221, 227, 231, 234, 236, 237, 237, 236, 234, 231, 227, 221, 215, 208, 201, 193, 183, 175, 165, 155, 146, 136, 127, 117, 108, 99, 89, 81, 74, 66, 58, 52, 47, 41, 36, 31, 27, 24, 20, 18, 15, 12, 10, 9, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 2, 3, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 21, 24, 28, 32, 36, 42, 47, 54, 60, 67, 76, 84, 92, 101, 110, 120, 130, 140, 150, 159, 169, 178, 188, 198, 206, 213, 220, 226, 232, 236, 240, 242, 243, 243, 242, 240, 236, 232, 226, 220, 213, 206, 198, 188, 178, 168, 160, 149, 139, 130, 120, 111, 101, 91, 83, 76, 67, 60, 54, 47, 43, 38, 33, 29, 24, 21, 17, 15, 13, 11, 9, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1}, 
{0, 1, 1, 1, 2, 3, 3, 4, 5, 6, 8, 9, 11, 13, 15, 18, 21, 25, 29, 33, 37, 43, 48, 55, 62, 69, 77, 85, 93, 102, 112, 122, 131, 142, 153, 162, 172, 182, 193, 201, 209, 218, 225, 231, 236, 241, 244, 247, 247, 247, 247, 245, 241, 237, 231, 225, 218, 209, 200, 192, 183, 173, 162, 152, 142, 132, 122, 112, 102, 94, 85, 77, 69, 62, 54, 48, 43, 38, 33, 29, 25, 21, 19, 16, 13, 11, 9, 8, 6, 5, 4, 4, 3, 2, 2, 2, 1, 1}, 
{0, 1, 1, 1, 2, 3, 3, 4, 5, 6, 8, 9, 11, 13, 16, 19, 21, 25, 29, 33, 39, 44, 49, 55, 62, 70, 78, 86, 94, 103, 114, 124, 133, 143, 154, 164, 174, 185, 195, 204, 213, 221, 228, 234, 239, 244, 248, 250, 251, 251, 249, 248, 244, 240, 234, 228, 221, 213, 203, 195, 185, 175, 165, 154, 143, 133, 123, 113, 103, 95, 86, 78, 70, 63, 55, 49, 43, 38, 34, 29, 25, 21, 19, 16, 13, 11, 9, 8, 6, 5, 4, 4, 3, 2, 2, 2, 1, 1}, 
{1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 10, 12, 14, 16, 19, 21, 25, 29, 34, 38, 44, 50, 56, 62, 70, 78, 87, 96, 105, 115, 125, 136, 145, 156, 167, 177, 187, 197, 206, 214, 223, 230, 236, 243, 247, 249, 252, 253, 253, 252, 250, 246, 242, 236, 230, 223, 215, 206, 197, 187, 177, 167, 156, 145, 135, 125, 115, 105, 96, 87, 79, 71, 63, 56, 49, 44, 38, 34, 30, 26, 22, 19, 16, 13, 11, 10, 8, 6, 5, 5, 3, 3, 2, 2, 1, 1, 1}, 
{1, 1, 1, 2, 2, 3, 4, 5, 5, 6, 8, 10, 11, 13, 16, 18, 22, 26, 30, 34, 38, 44, 49, 56, 64, 71, 79, 87, 96, 105, 115, 125, 136, 146, 156, 166, 177, 187, 197, 207, 215, 224, 231, 237, 244, 248, 251, 253, 254, 255, 253, 251, 247, 243, 238, 230, 223, 216, 207, 198, 188, 177, 167, 156, 146, 136, 125, 115, 106, 96, 87, 79, 71, 63, 56, 50, 44, 38, 33, 29, 26, 22, 18, 16, 13, 11, 10, 8, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1}, 
{1, 1, 1, 2, 2, 3, 3, 5, 5, 6, 8, 10, 11, 13, 16, 18, 22, 26, 30, 34, 38, 44, 50, 56, 63, 71, 79, 87, 96, 106, 115, 125, 136, 146, 157, 167, 177, 187, 197, 207, 216, 224, 231, 237, 243, 247, 251, 253, 254, 254, 253, 250, 247, 243, 237, 231, 224, 216, 207, 198, 188, 178, 167, 156, 146, 136, 125, 115, 105, 96, 87, 79, 71, 64, 56, 49, 44, 38, 34, 29, 25, 22, 18, 16, 13, 11, 10, 8, 6, 5, 4, 3, 3, 3, 2, 1, 1, 1}, 
{1, 1, 1, 2, 2, 3, 3, 4, 5, 8, 8, 9, 11, 13, 16, 19, 22, 26, 29, 33, 38, 44, 50, 55, 62, 71, 79, 87, 96, 105, 114, 124, 135, 145, 156, 166, 177, 187, 197, 206, 215, 223, 230, 236, 242, 246, 250, 252, 253, 253, 253, 251, 247, 242, 236, 230, 223, 215, 206, 197, 187, 177, 167, 156, 145, 135, 125, 115, 105, 96, 87, 79, 71, 63, 56, 49, 44, 39, 34, 29, 26, 22, 18, 16, 14, 12, 9, 8, 6, 5, 5, 4, 3, 3, 2, 1, 1, 1}, 
{1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 11, 13, 16, 19, 21, 25, 29, 34, 38, 44, 49, 55, 62, 70, 78, 86, 95, 104, 113, 123, 133, 143, 154, 165, 175, 185, 194, 203, 213, 221, 228, 234, 239, 244, 246, 249, 251, 251, 250, 248, 244, 239, 234, 228, 221, 213, 203, 195, 185, 175, 165, 154, 143, 133, 123, 113, 103, 95, 86, 78, 70, 62, 55, 49, 43, 38, 33, 28, 25, 22, 18, 16, 13, 11, 9, 8, 6, 5, 4, 3, 3, 2, 2, 2, 1, 0}, 
{1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 11, 13, 16, 19, 21, 25, 29, 33, 37, 43, 49, 55, 61, 69, 77, 85, 94, 103, 112, 122, 132, 142, 152, 163, 173, 182, 192, 201, 209, 217, 224, 230, 237, 241, 244, 246, 247, 248, 246, 242, 241, 237, 231, 225, 217, 209, 201, 192, 182, 173, 162, 152, 142, 132, 122, 112, 102, 94, 85, 76, 68, 62, 54, 49, 43, 38, 33, 28, 25, 22, 18, 16, 13, 11, 9, 8, 6, 5, 5, 4, 3, 2, 2, 1, 1, 0}, 
{1, 1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 21, 25, 28, 32, 36, 42, 48, 53, 61, 68, 76, 84, 91, 100, 109, 119, 130, 140, 149, 159, 169, 179, 189, 198, 206, 214, 221, 227, 232, 236, 240, 242, 243, 243, 242, 240, 236, 232, 226, 220, 213, 206, 198, 188, 179, 170, 160, 149, 139, 130, 119, 109, 101, 92, 83, 74, 69, 61, 53, 47, 43, 38, 32, 28, 25, 20, 18, 15, 13, 11, 9, 8, 6, 5, 5, 3, 2, 2, 2, 1, 1, 0}, 
{1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 27, 31, 36, 41, 46, 52, 59, 65, 73, 81, 90, 98, 108, 117, 126, 136, 146, 155, 165, 174, 184, 193, 201, 209, 216, 221, 226, 231, 234, 236, 237, 237, 236, 234, 231, 226, 221, 215, 208, 201, 193, 184, 175, 166, 157, 146, 136, 127, 116, 107, 98, 90, 82, 73, 65, 59, 52, 46, 41, 35, 31, 27, 23, 20, 18, 15, 13, 11, 9, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1}, 
{1, 1, 2, 2, 2, 2, 3, 5, 5, 6, 7, 8, 10, 12, 15, 17, 19, 23, 27, 31, 35, 40, 45, 51, 58, 63, 71, 80, 88, 96, 105, 113, 122, 131, 142, 152, 160, 169, 179, 187, 195, 202, 209, 215, 220, 224, 227, 229, 230, 230, 229, 226, 224, 220, 215, 209, 202, 195, 187, 178, 170, 161, 151, 142, 131, 122, 113, 103, 95, 88, 80, 72, 64, 57, 52, 46, 40, 34, 30, 27, 23, 19, 17, 15, 13, 11, 9, 7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 10, 12, 15, 17, 19, 23, 26, 29, 33, 38, 44, 49, 55, 61, 69, 77, 85, 93, 100, 109, 118, 127, 137, 147, 155, 164, 172, 180, 188, 195, 202, 208, 213, 217, 220, 222, 223, 223, 222, 220, 217, 213, 208, 202, 195, 188, 181, 173, 163, 155, 146, 136, 127, 118, 109, 101, 93, 84, 75, 69, 62, 55, 49, 44, 38, 34, 29, 25, 22, 18, 16, 14, 12, 9, 8, 7, 5, 4, 4, 3, 3, 2, 1, 1, 1, 1}, 
{1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 11, 13, 15, 18, 21, 25, 28, 32, 37, 41, 47, 53, 59, 66, 74, 81, 88, 96, 105, 114, 123, 132, 141, 149, 158, 167, 174, 181, 188, 195, 200, 205, 209, 212, 214, 214, 215, 214, 211, 208, 205, 200, 194, 189, 182, 174, 166, 157, 149, 142, 131, 122, 114, 105, 97, 89, 81, 72, 66, 59, 53, 47, 42, 37, 32, 28, 24, 21, 18, 15, 13, 11, 9, 8, 7, 5, 4, 4, 3, 3, 2, 1, 1, 1, 0}, 
{1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 9, 11, 13, 15, 17, 20, 23, 27, 31, 35, 40, 46, 51, 57, 64, 70, 78, 85, 92, 100, 109, 118, 126, 135, 143, 151, 160, 167, 173, 180, 187, 192, 196, 199, 202, 205, 205, 206, 205, 203, 200, 196, 192, 187, 180, 174, 167, 159, 151, 143, 135, 126, 118, 110, 100, 92, 85, 78, 70, 64, 57, 52, 46, 40, 35, 31, 28, 24, 21, 17, 15, 13, 11, 9, 8, 6, 5, 4, 4, 2, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 8, 10, 13, 14, 16, 19, 23, 26, 28, 34, 39, 43, 48, 54, 60, 66, 74, 81, 88, 96, 104, 112, 120, 129, 136, 144, 152, 160, 166, 172, 178, 183, 187, 190, 193, 195, 196, 196, 195, 193, 191, 187, 183, 178, 172, 166, 160, 152, 144, 136, 128, 121, 113, 104, 96, 88, 81, 74, 66, 61, 55, 49, 43, 38, 33, 29, 26, 22, 19, 16, 15, 13, 10, 8, 7, 6, 4, 4, 4, 2, 2, 2, 2, 1, 1, 0}, 
{0, 1, 1, 1, 1, 2, 2, 3, 4, 4, 6, 7, 8, 10, 12, 14, 16, 18, 21, 24, 28, 31, 36, 41, 46, 51, 57, 64, 70, 77, 83, 92, 99, 106, 114, 122, 129, 137, 144, 151, 158, 163, 169, 174, 178, 181, 183, 185, 186, 186, 185, 183, 181, 178, 174, 169, 163, 157, 151, 144, 137, 129, 121, 114, 106, 99, 93, 84, 77, 70, 64, 58, 52, 46, 40, 37, 32, 27, 24, 21, 18, 15, 13, 12, 10, 8, 7, 6, 4, 4, 3, 2, 2, 2, 1, 1, 1, 0}, 
{0, 1, 1, 1, 1, 2, 3, 3, 4, 4, 5, 6, 8, 10, 11, 12, 15, 18, 20, 24, 27, 30, 35, 39, 44, 48, 54, 60, 66, 73, 79, 86, 94, 101, 108, 115, 122, 129, 136, 143, 148, 154, 159, 164, 168, 171, 173, 175, 175, 175, 175, 173, 171, 168, 164, 159, 155, 149, 143, 136, 129, 122, 116, 108, 101, 94, 86, 79, 73, 66, 60, 54, 49, 43, 39, 34, 29, 26, 23, 20, 18, 15, 13, 11, 10, 8, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0}, 
{0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 5, 6, 7, 9, 10, 11, 13, 16, 18, 22, 25, 28, 33, 36, 41, 46, 51, 56, 62, 68, 75, 80, 87, 94, 101, 108, 115, 121, 127, 134, 139, 145, 150, 154, 157, 160, 162, 164, 165, 165, 164, 163, 160, 157, 154, 150, 146, 140, 134, 127, 121, 115, 108, 102, 94, 88, 81, 74, 68, 62, 56, 51, 46, 41, 37, 32, 27, 24, 21, 18, 16, 14, 12, 10, 8, 6, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 0, 0}, 
{0, 1, 1, 1, 1, 1, 2, 3, 3, 3, 5, 6, 7, 7, 9, 11, 13, 15, 17, 20, 23, 26, 31, 34, 38, 42, 47, 52, 58, 63, 69, 76, 82, 88, 94, 101, 108, 113, 120, 126, 131, 135, 141, 144, 147, 150, 152, 154, 155, 155, 154, 153, 150, 147, 144, 140, 136, 130, 125, 120, 114, 108, 101, 95, 88, 81, 75, 70, 64, 58, 53, 48, 43, 38, 33, 30, 27, 23, 20, 17, 15, 13, 11, 9, 8, 6, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0}, 
{0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 21, 25, 29, 32, 36, 39, 43, 48, 54, 59, 64, 71, 77, 82, 88, 94, 100, 105, 111, 116, 121, 125, 131, 134, 137, 140, 141, 143, 144, 144, 143, 142, 140, 137, 134, 130, 126, 122, 116, 111, 105, 100, 94, 88, 82, 76, 71, 65, 60, 54, 49, 44, 41, 36, 31, 28, 25, 22, 19, 16, 14, 12, 10, 9, 8, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0}, 
{0, 1, 0, 0, 1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 17, 20, 23, 26, 29, 33, 37, 41, 44, 50, 55, 59, 65, 72, 76, 81, 87, 93, 98, 103, 108, 112, 116, 121, 125, 127, 130, 131, 133, 133, 133, 132, 131, 130, 127, 124, 121, 117, 113, 108, 103, 98, 93, 88, 82, 76, 71, 65, 59, 55, 50, 45, 41, 36, 33, 29, 26, 23, 20, 17, 15, 13, 11, 10, 8, 7, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 10, 12, 13, 16, 19, 21, 24, 27, 31, 34, 38, 41, 46, 50, 55, 61, 65, 70, 75, 81, 85, 90, 95, 99, 103, 107, 111, 115, 117, 119, 121, 122, 122, 122, 122, 120, 120, 116, 113, 111, 108, 104, 100, 95, 90, 86, 81, 75, 70, 65, 60, 55, 50, 46, 41, 37, 33, 30, 27, 24, 21, 19, 16, 13, 12, 10, 8, 7, 7, 5, 5, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 1, 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 17, 19, 22, 25, 28, 31, 34, 38, 42, 46, 51, 56, 60, 65, 70, 74, 78, 82, 87, 91, 95, 99, 102, 106, 108, 109, 111, 112, 113, 112, 112, 111, 110, 107, 104, 102, 99, 95, 91, 87, 82, 78, 73, 70, 65, 60, 55, 50, 46, 42, 38, 34, 31, 28, 25, 22, 19, 17, 15, 13, 11, 9, 7, 6, 6, 5, 4, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 4, 4, 6, 6, 7, 9, 10, 11, 13, 15, 17, 20, 23, 26, 29, 32, 35, 38, 42, 46, 50, 54, 59, 63, 67, 72, 76, 80, 83, 87, 90, 94, 95, 97, 99, 100, 102, 102, 102, 102, 101, 99, 98, 96, 93, 90, 87, 83, 80, 76, 72, 67, 63, 58, 55, 51, 46, 42, 39, 36, 32, 28, 25, 23, 20, 17, 15, 13, 11, 10, 8, 6, 6, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 8, 9, 10, 12, 14, 16, 18, 21, 23, 26, 29, 32, 35, 38, 42, 45, 49, 53, 57, 60, 65, 69, 72, 76, 79, 81, 85, 87, 89, 91, 92, 93, 93, 93, 93, 92, 91, 89, 87, 85, 81, 79, 76, 72, 69, 65, 61, 57, 53, 49, 45, 42, 39, 35, 31, 28, 26, 23, 21, 18, 15, 14, 12, 10, 9, 8, 6, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 5, 6, 6, 7, 8, 10, 12, 13, 14, 17, 18, 20, 23, 26, 28, 31, 35, 38, 41, 45, 48, 52, 55, 59, 62, 65, 68, 72, 74, 76, 79, 81, 82, 83, 84, 84, 85, 84, 83, 83, 81, 79, 77, 73, 71, 69, 65, 62, 59, 55, 52, 48, 45, 41, 38, 35, 32, 28, 25, 23, 21, 19, 16, 14, 13, 11, 9, 8, 7, 5, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 7, 7, 8, 10, 11, 12, 15, 16, 18, 21, 24, 26, 29, 32, 34, 37, 40, 43, 47, 50, 53, 56, 59, 62, 65, 67, 69, 71, 73, 74, 75, 76, 76, 77, 76, 75, 74, 73, 71, 69, 66, 64, 62, 59, 56, 53, 49, 47, 43, 40, 37, 34, 32, 29, 26, 24, 21, 19, 17, 14, 12, 11, 10, 8, 7, 5, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 9, 10, 11, 13, 15, 16, 19, 21, 23, 26, 29, 30, 33, 37, 39, 42, 44, 47, 51, 53, 55, 58, 60, 62, 63, 65, 66, 67, 68, 69, 69, 68, 67, 66, 65, 63, 61, 60, 58, 55, 53, 51, 47, 44, 42, 39, 36, 34, 30, 28, 26, 23, 21, 19, 16, 14, 12, 11, 10, 9, 7, 7, 6, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 8, 9, 10, 11, 14, 15, 16, 18, 20, 22, 24, 27, 30, 32, 34, 38, 40, 43, 46, 48, 49, 51, 53, 55, 56, 58, 59, 59, 61, 61, 61, 60, 59, 59, 58, 56, 55, 53, 51, 50, 47, 45, 43, 40, 38, 34, 32, 30, 27, 25, 23, 20, 19, 17, 15, 13, 11, 10, 9, 8, 7, 6, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 5, 6, 7, 8, 8, 9, 12, 13, 14, 16, 18, 20, 22, 24, 27, 29, 31, 33, 35, 37, 40, 42, 43, 45, 47, 49, 50, 51, 53, 54, 54, 53, 53, 54, 53, 52, 51, 50, 49, 47, 45, 44, 41, 39, 37, 35, 33, 31, 28, 26, 25, 22, 20, 18, 17, 15, 13, 11, 9, 8, 7, 7, 5, 5, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 6, 7, 7, 8, 10, 11, 12, 15, 16, 18, 20, 21, 23, 25, 27, 29, 31, 33, 35, 37, 38, 40, 42, 44, 44, 46, 46, 46, 47, 47, 47, 48, 47, 46, 46, 44, 43, 42, 40, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 20, 18, 16, 14, 14, 11, 10, 9, 7, 6, 6, 5, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 6, 6, 7, 8, 9, 10, 11, 13, 14, 15, 17, 18, 20, 22, 24, 25, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 41, 41, 42, 42, 42, 42, 42, 40, 39, 40, 38, 37, 35, 34, 33, 31, 29, 27, 25, 23, 22, 20, 19, 17, 15, 14, 12, 11, 10, 9, 8, 7, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 5, 7, 7, 8, 9, 11, 12, 13, 15, 16, 18, 20, 20, 21, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 35, 36, 36, 36, 36, 36, 36, 36, 35, 33, 32, 31, 31, 30, 28, 26, 25, 24, 22, 21, 20, 18, 17, 15, 13, 12, 11, 9, 8, 7, 7, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 5, 5, 6, 7, 9, 10, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 25, 26, 28, 28, 29, 30, 31, 31, 32, 31, 31, 31, 31, 31, 30, 29, 28, 28, 27, 26, 25, 23, 22, 21, 19, 18, 17, 15, 14, 13, 11, 10, 9, 9, 7, 7, 5, 5, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 10, 11, 12, 13, 15, 16, 16, 18, 19, 20, 22, 22, 23, 23, 25, 26, 26, 27, 27, 27, 27, 27, 27, 27, 26, 26, 25, 25, 24, 23, 22, 21, 20, 19, 18, 16, 15, 14, 13, 12, 11, 10, 9, 9, 8, 7, 6, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 1, 1, 2, 3, 3, 3, 3, 5, 5, 5, 6, 7, 8, 8, 9, 10, 11, 12, 14, 14, 16, 17, 18, 17, 20, 21, 21, 21, 22, 23, 23, 23, 23, 23, 24, 24, 23, 23, 22, 23, 21, 21, 20, 19, 19, 18, 17, 15, 14, 13, 12, 11, 10, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 11, 11, 12, 14, 14, 15, 16, 17, 17, 18, 19, 19, 20, 20, 20, 20, 20, 21, 21, 20, 20, 19, 19, 19, 18, 17, 16, 16, 15, 14, 14, 12, 12, 11, 9, 9, 8, 7, 6, 6, 5, 5, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 9, 9, 9, 10, 12, 12, 12, 13, 14, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 15, 14, 14, 14, 12, 12, 11, 10, 10, 9, 8, 7, 7, 6, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 10, 10, 10, 10, 11, 13, 13, 12, 14, 14, 14, 15, 15, 14, 14, 15, 15, 14, 13, 14, 13, 12, 12, 12, 12, 10, 10, 9, 8, 8, 7, 7, 6, 6, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11, 11, 11, 12, 12, 12, 13, 13, 12, 12, 13, 12, 12, 12, 12, 11, 11, 10, 10, 9, 9, 8, 8, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 9, 10, 11, 10, 10, 11, 10, 10, 10, 10, 9, 9, 9, 9, 8, 7, 7, 7, 6, 5, 4, 5, 5, 4, 3, 3, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 8, 8, 9, 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 5, 4, 3, 3, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 3, 4, 4, 5, 5, 5, 6, 6, 5, 5, 5, 6, 6, 5, 5, 6, 6, 5, 6, 5, 5, 4, 4, 5, 4, 3, 3, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 3, 4, 4, 4, 4, 5, 5, 5, 4, 4, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 3, 3, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
    }
}

Mycket nöje!

Funktioner är andra klassens medborgare i C#

I C# 8 är fortfarande funktioner ett slags “andra klassens medborgare” i jämförelse med variabler. Man kan alltså fortfarande göra mer med en variabel än en funktion i C# 8.

Varken variabler eller funktioner kan skapas i namnrymder, båda kan skapas i en klass och båda kan skapas i en funktion, vilket illustreras av detta exempel:

namespace ConsoleApp1
{
    public class MyClass
    {
        public int VariableInClass;

        public void FunctionInClass()
        {
            int variableInFunction;
            
            void functionInFunction() { }
        }
    }
}

Eftersom det finns saker som du kan göra med variabler som du inte kan göra med funktioner, så är funktioner fortfarande att betrakta som ett slags andra klassens medborgare. Du kan inte lagra en funktion i en variabel, du kan inte skicka funktioner som argument och du kan inte använda type inference när du skapar funktioner.

var x = 10;

//Variabel som påverkar x
Action y = () => x++;
y();
Console.WriteLine(x);

//Funktion som påverkar x
void z() => x++;
z();
Console.WriteLine(x);

Att man inte kan lagra funktioner i variabler spelar inte någon jättestor roll. Som namnet antyder beskriver funktioner ofta något funktionellt, vilket i praktiken innebär att de innehåller programsatser. Programsatser kan även lagras i variabler, vilket innebär att funktionalitet kan lagras i en variabel och skickas som argument. Detta exempel visar hur instruktionen att summera två tal lagras i en variabel:

//Add the ability to add
//two integers in x.
Func<int, int, int> x =
    (int a, int b) => a + b;

//Execute the content
//of x, save the result in y.
var y = x(10, 20);

Detta exempel visar hur samma instruktion skickas som parameter till en funktion:

GiveMeFunctionality((a, b) => a + b);

C#-programmets startpunkt kan inte ersättas av en variabel, utan måste vara en riktig funktion kallad Main. I vissa fall kan man kringgå att en funktion inte kan användas som en variabel genom att skapa en variabel som anropar en funktion, och skicka den istället. T.ex. så här:

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            GiveMeFunctionality(
                Functionality);
        }

        static int Functionality
            (int a, int b) =>
            a + b;
        
        static void GiveMeFunctionality(
            Func<int, int, int> x)
        {
            Console.WriteLine(x(10, 20));
        }
    }
}

Men till skillnad från variabler kan funktioner vara rekursiva. En funktion kan alltid anropas från en annan funktion, och tack vara stödet för reflection i C# (som t.ex. C++ saknar) kan funktioner alltid anropas oberoende av var i koden de är deklarerade.

var x = 0;
void i()
{
    x++;
    while (x < 10) 
        i();
}

Motsvarigheten skulle kunna vara något i den här stilen, vilket kräver att variabeln i finns medan den fortfarande deklareras:

var x = 0;
var i = () => {
    x++;
    while (x < 10) 
        i();
};

Mitt första intryck av Windows Terminal

Sent om sidor lyckades jag installera rätt version av Windows 10 för att få ladda hem förhandsversionen av Windows Terminal, och efter att ha testat den så måste jag säga att jag å ena sidan inte har några stående ovationer att bjuda på, men måste samtidigt säga att det verkligen är hög tid att Windows fick en bra konsol-emulator.

För den som inte är varm i kläderna när det gäller grafiska användargränssnitt (GUI) av WIMP-typ så vill jag påpeka att dessa ofta behöver en konsol-emulator som erbjuder användaren att köra applikationer som inte har något passande grafiskt gränssnitt, utan en enkel kommandotolk, inte minst för att komma åt operativsystemets egna funktioner och tjänster. I Windows 10 handlar det om den gamla CMD, om den lite nyare PowerShell och sedermera även om Bash, men när helst textkommandon ska skrivas i en WIMP-miljö, behövs en konsol-emulator.

Det har funnits lite olika alternativ att välja på i Windows 10, men den enda som Microsoft har erhållit är cmd.exe, som är så pass eftersatt att möjligheten att klippa ut, kopiera och klistra in text är att betrakta som relativt ny funktionalitet. Men det är cmd.exe som använts för den som vill köra CMD, PowerShell eller Bash.

Windows Terminal verkar som sagt inte vara någon revolution (än) men är definitivt ett behövligt tillskott till Windows 10. Fönstret bjuder på ett plus-tecken där man kan öppna en ny flik med någon installerad kommandotolk (vilket endast är CMD och PowerShell om man inte lagt till någon tredjepartstolk).

Ett irritationsmoment i den här förhandsversionen är att du inte kan flytta själva fönstret genom att dra i fönstertiteln utanför PowerShell-fliken, före plus-symbolen. Det är endast området mellan plus-symbolen och minimeringsknappen som kan användas för att positionera fönstret. Det måste väl ändå vara en bugg?

Om man väljer att ändra inställningarna för Windows Terminal startar den editor du valt att använda för JSON, vilket i mitt fall (tydligen) är Visual Studio. Fördelen med att inställningarna är lagrade i INI-filer, XML-filer eller JSON-filer är att det är enkelt att redigera och förvalta dem, men nackdelen är att man får konsultera Bing (eller motsvarande) för att få reda på vad som går att göra. Men eftersom Windows Terminal installeras med stöd för CMD och PowerShell och eftersom jag titt som tätt använder Developer Command Prompt for Visual Studio (DCPVS), så tänker jag att jag vill lägga till den under plus-tecknet.

Inställningsfilen (som av någon anledning heter profiles.json) innehåller ett objekt per flik, så genom att klippa och klistra, och justera så borde man enkelt kunna lägga till DCPVS.

Trodde jag. Men på den punkten får jag inget gensvar. Min nya post visas, men kommandot jag vill exekvera, körs inte.

Det kan såklart handla om skit bakom spakarna, men om så är fallet, så behöver åtminstone jag mer tydlighet. Så för att köra DCPVS måste jag fortfarande snällt köra VsDevCmd.bat manuellt, min konfiguration till trots.

Detta projekt behövs, och jag kör som sagt en förhandsversion av Windows Terminal, men hittills är jag inte jätteimponerad.

Skapa binära filer snabbt och enkelt

Ibland behöver man skapa binära filer, t.ex. för att testa en egenutvecklad file header. För att göra detta kan man starta HxD och peta in de bytes man vill ha i filen. Men om man vill trycka in tal större än 255 eller textsträngar så är det en del att hålla i huvudet. Programmet MkBin bygger en binärfil efter instruktioner i en textfil.

Programmet tar två argument. Först -source som anger textfilen som beskriver binärfilen och -target som anger den binära filen som ska skrivas.

Tal som anges i textfilen antas vara bytes (8-bitarstal mellan 0 och 255), men det går att skriva in kontrollord framför för att ändra datatyp, vilket exemplet i bilden ovan visar.

Om man vill laborera med vilka texter som ger vilket binära resultat, kan man starta programmet med växeln -prompt istället för -source och -target, bara genom att skriva:

MkBin.exe -prompt

Då kan man skriva text och få direkt feedback på vad som skulle hamna i en textfil. Kontrollord som byte, short, int och long, eller 8-bit, 16-bit, 32-bit eller 64-bit anger formatet på efterföljande tal och uttryck som anges inom citat antas vara strängar med UTF-8-kodning. Exempel:

MkBin finns att hämta här.

Sprdef 1.7

Version 1.7 of the Commodore 64 sprite editor for Windows, Sprdef, allows the user to scroll and flip a sprite and fixes a bug with thumbnail updates.

Sprdef version 1.7

Features:

  • Undo/redo buffer
  • Single color/multi color sprite edit
  • CBM prg Studio integration
  • BASIC import/export
  • Keyboard first editing or mouse first editing

Download: http://winsoft.se/files/SetupSprdef.exe

Sprdef requires .NET Framework 4.8 or later.

Skärmbyte på arkadspelet

Jag äger en nytillverkad klassisk argadmaskin som spelar Jamma-kassetter, där skärmen tyvärr gav upp. Som synes klarar arkadspelet antingen vertikala eller horisontella spel med digital styrning. Jag använder den för vertikala spel.

Det var enkelt att skruva loss den gamla skärmen och sätta den nya panelen på plats, men jag upptäckte naturligtvis lite för sent att jag satte den nya panelen 1,5 millimeter för långt till höger.

Framför skärmen sitter två glasskivor med ett motivtryckt papper emellan, för att dölja skärmens kant.

Här är glasskivorna på plats och listen som håller fast dem är fastskruvade. Här såg jag mitt lilla misstag, men beslutade mig för att skruva ihop den ändå, och justera panelens position i sidled vid ett senare tillfälle.

Så här ser spelkassetterna ut. Idag finns även nytillverkade spelkassetter med flera spel på, men typiskt innehåller kassetterna spel från Pac Man- och Galaga-eran. Så här ser den ut med Ms. Pac Man laddad:

Så nu är det bara att stoppa in en femma och köra igång!

Följ mig på Instagram för fler äventyr:

Visa det här inlägget på Instagram

Skärmbyte på arkadspelet!

Ett inlägg delat av Anders Hesselbom (@andershbom)

Sprdef 1.5

Sprdef är en sprite-editor för Windows 10 som används vid spelutveckling för Commodore 64 med Windows som utvecklingsmiljö. Version 1.5 integrerar med CBM prg Studio, har undo/redo-buffer, fungerar i både single- och multicolor-läge och kan importera/exportera BASIC-data. Ladda hem programmet här.

Skärmbild av Sprdef 1.5.

Pathfinding i terräng

A* (A-star) är en snabb pathfinder-algoritm som kan användas i t.ex. strategispel för att hitta vägar genom labyrinter eller terräng. Christoph Husse publicerade 2010 en briljant implementation i C# som tillåter egna kriterier, definierade i en solver, för kostnaden att flytta sig från en nod till en annan. I följande exempel har jag använt Christophs kod, men jag har skalat bort hans solver och istället hårdkodat in en viktad terräng. Kartan i exemplet är liten, endast 50×25 celler, och kostnaden för att gå på en cell sträcker sig från 0 till 99. De celler som har värdet 100 betraktas som ett oöverstigligt hinder. Bilden visar en körning, där startpositionen är längst ner till vänster.

Det hela utspelar sig i ett vanligt Windows Forms-fönster som har en karta (typen Map) och en stig (typen Path). Både Map och Path presenteras nedan. (De första fyra kodblocken visar alltså innehållet i fönstret, och de resterande kodblocken visar klasserna som används i projektet.)

private Map Map { get; set; }
private Path Path { get; set; }

I fönstrets Load-event skapar jag kartan, kartans terräng och använder sedan klassen som implementerar A* för att hitta den bästa vägen från start (längst ner till vänster) till mål (längst upp till höger). Funktionen FindPath ger null om det inte finns någon väg mellan punkterna.

private void Form1_Load(object sender, EventArgs e)
{
    Map = new Map(50, 25);
    CreateTerrain(Map);
    var aStar = new AStar(Map);
    Path = aStar.FindPath(
        new Point(0, Map.Height - 1),
        new Point(Map.Width - 1, 0))
        ?? new Path();
    Invalidate();
}

Funktionen för att generera terrängen, CreateTerrain, skapar ett godtyckligt bergslandskap.

private void CreateTerrain(Map map)
{
    var rnd = new Random();
    var walkcosts = new int[map.Width + 2, map.Height + 2];
    for (var y = 0; y < map.Height + 2; y++)
        for (var x = 0; x < map.Width + 2; x++)
            if (rnd.Next(0, 3) == 1)
                walkcosts[x, y] = rnd.Next(-10, 300);
    int GetAverage(int[,] a, int x, int y) =>
        (a[x - 1, y - 1] + a[x, y - 1] + a[x + 1, y - 1]
         + a[x - 1, y] + a[x, y] + a[x + 1, y]
         + a[x - 1, y + 1] + a[x, y + 1] + a[x + 1, y + 1]) / 9;
    for (var y = 0; y < map.Height; y++)
    {
        for (var x = 0; x < map.Width; x++)
        {
            var avg = GetAverage(walkcosts, x + 1, y + 1);
            if (avg < 0)
                avg = 0;
            else if (avg > 100)
                avg = 100;
            map.SetWalkCost(x, y, (byte)avg);
        }
    }
}

I fönstrets Paint-event ritas det hela ut på skärmen.

private void Form1_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(Color.Black);
    var m = new MapRenderer(Map, Path, 24);
    m.Draw(e.Graphics, 0, 0);
}

Klassen MapRenderer som ansvarar för ritandet ser ut så här:

using System.Drawing;
using System.Drawing.Drawing2D;

namespace PathFinderAStar
{
    public class MapRenderer
    {
        public Map Map { get; }
        public Path Path { get; }
        public int CellSize { get; }

        public MapRenderer(Map map, Path path, int cellSize)
        {
            Map = map;
            Path = path;
            CellSize = cellSize;
        }

        public void Draw(Graphics g, int offsetX, int offsetY)
        {
            var xpos = offsetX;
            var ypos = offsetY;
            using (var font = new Font(FontFamily.GenericSansSerif, 8))
            {
                for (var y = 0; y < Map.Height; y++)
                {
                    for (var x = 0; x < Map.Width; x++)
                    {
                        g.SmoothingMode = SmoothingMode.None;
                        g.DrawRectangle(
                            Pens.Gray,
                            xpos,
                            ypos,
                            CellSize,
                            CellSize);
                        using (var b = new SolidBrush(
                            Color.FromArgb(Map.GetWalkCost(x, y) * 2,
                            0,
                            0)))
                            g.FillRectangle(
                                b,
                                xpos + 2,
                                ypos + 2,
                                CellSize - 3,
                                CellSize - 3);
                        var pathCell = Path.GetCellAt(x, y);
                        g.SmoothingMode = SmoothingMode.HighQuality;
                        if (pathCell != null)
                            g.FillEllipse(
                                Brushes.CadetBlue,
                                xpos + 5,
                                ypos + 5,
                                CellSize - 9,
                                CellSize - 9);
                        g.DrawString(
                            Map.GetWalkCost(x, y).ToString(),
                            font,
                            Brushes.White,
                            xpos + 1,
                            ypos + 1);
                        xpos += CellSize;
                    }
                    xpos = offsetX;
                    ypos += CellSize;
                }
            }
        }
    }
}

Klassen Map beskriver en 2-dimensionell karta, på vilken vi ska hitta en stig.

using System;
using System.Diagnostics;
using System.Drawing;

namespace PathFinderAStar
{
    public class Map
    {
        private readonly MapCell[,] _terrain;
        public int Width { get; }
        public int Height { get; }

        public Map(int width, int height)
        {
            if (width < 2 || width > 2000)
                throw new ArgumentOutOfRangeException(nameof(width));
            if (height < 2 || height > 2000)
                throw new ArgumentOutOfRangeException(nameof(height));
            Width = width;
            Height = height;
            _terrain = new MapCell[width, height];
        }

        public byte GetWalkCost(int x, int y)
        {
            if (x < 0 || x >= Width)
                throw new ArgumentOutOfRangeException(nameof(x));
            if (y < 0 || y >= Height)
                throw new ArgumentOutOfRangeException(nameof(y));
            var cell = _terrain[x, y];
            if (cell == null)
                return 0;
            Debug.Assert(cell.X == x);
            Debug.Assert(cell.Y == y);
            return cell.WalkCost;
        }

        public void SetWalkCost(int x, int y, byte walkCost)
        {
            if (x < 0 || x >= Width)
                throw new ArgumentOutOfRangeException(nameof(x));
            if (y < 0 || y >= Height)
                throw new ArgumentOutOfRangeException(nameof(y));
            if (walkCost > 100)
                throw new ArgumentOutOfRangeException(nameof(walkCost));
            var cell = _terrain[x, y];
            if (cell == null)
            {
                cell = new MapCell(x, y, walkCost);
                _terrain[x, y] = cell;
                return;
            }
            Debug.Assert(cell.X == x);
            Debug.Assert(cell.Y == y);
            cell.WalkCost = walkCost;
        }

        public void Clear()
        {
            for (var y = 0; y < Height; y++)
                for (var x = 0; x < Width; x++)
                    _terrain[x, y] = null;
        }

        public MapCell GetCell(int x, int y) =>
            GetCell(new Point(x, y));

        public MapCell GetCell(Point p)
        {
            if (p.X < 0 || p.X >= Width || p.Y < 0 || p.Y >= Height)
                return null;
            var c = _terrain[p.X, p.Y];
            return c;
        }

        public double GetDistance(MapCell start, MapCell goal)
        {
            var actualDistance = Math.Sqrt((start.X - goal.X)
                * (start.X - goal.X)
                + (start.Y - goal.Y)
                * (start.Y - goal.Y));
            return actualDistance + (double)goal.WalkCost / 10;
        }

        public void Add(MapCell cell)
        {
            if (cell == null)
                throw new ArgumentNullException(nameof(cell));
            if (cell.X < 0 || cell.X >= Width)
                throw new ArgumentOutOfRangeException(nameof(cell.X));
            if (cell.Y < 0 || cell.Y >= Height)
                throw new ArgumentOutOfRangeException(nameof(cell.Y));
            if (_terrain[cell.X, cell.Y] != null)
                throw new SystemException();
            _terrain[cell.X, cell.Y] = cell;
        }

        public void Remove(MapCell cell)
        {
            if (cell == null)
                throw new ArgumentNullException(nameof(cell));
            if (_terrain[cell.X, cell.Y] == null)
                throw new SystemException();
            if (_terrain[cell.X, cell.Y] != cell)
                throw new SystemException();
            _terrain[cell.X, cell.Y] = null;
        }

        public bool Contains(MapCell cell) =>
            _terrain[cell.X, cell.Y] != null;

        public void SetWithHistory(int x, int y, MapCell cell) =>
            _terrain[x, y] = cell;

        public bool IsEmpty
        {
            get
            {
                for (var y = 0; y < Height; y++)
                    for (var x = 0; x < Width; x++)
                        if (_terrain[x, y] != null)
                            return false;
                return true;
            }
        }

        public int CompareCells(MapCell c1, MapCell c2)
        {
            if (c1 == null)
                throw new ArgumentNullException(nameof(c1));
            if (c2 == null)
                throw new ArgumentNullException(nameof(c2));
            if (c1.F < c2.F)
                return -1;
            if (c1.F > c2.F)
                return 1;
            return 0;
        }

    }
}

Stigen beskrivs av klassen Path:

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

namespace PathFinderAStar
{
    public class Path : List<MapCell>
    {
        public Path()
        {
        }

        public Path(int count)
        {
            for (var i = 0; i < count; i++)
                Add(null);
        }

        public MapCell GetCellAt(int x, int y) =>
            this.FirstOrDefault(c => c.X == x && c.Y == y);
    }
}

Både kartan (Map) och stigen (Path) består av referenser till celler som beskriver hur terrängen ser ut på en specifik plats. Typen heter MapCell (G, H, F och Index används av A*.):

namespace PathFinderAStar
{
    public class MapCell
    {
        private byte _walkCost;
        public int X { get; }
        public int Y { get; }
        public double G { get; set; }
        public double H { get; set; }
        public double F { get; set; }
        public int Index { get; set; }

        public byte WalkCost
        {
            get => _walkCost;
            set => _walkCost = value > 100 ? (byte)100 : value;
        }

        public bool IsWall =>
            WalkCost >= 100;

        public MapCell(int x, int y, byte walkCost)
        {
            X = x;
            Y = y;
            WalkCost = walkCost;
        }
    }
}

Sen har vi själva A*-algoritmen, såsom den implementerats av Christoph Husse, med mina förenklingar. Den konsumeras direkt i formulärets Load-event och ligger i klassen AStar.

using System.Drawing;

namespace PathFinderAStar
{
    public class AStar
    {
        private Map Map { get; }
        private Map ClosedSet { get; }
        private Map OpenSet { get; }
        private Map CameFrom { get; }
        private Map RuntimeGrid { get; }
        private PriorityQueue OrderedOpenSet { get; }

        public AStar(Map map)
        {
            Map = map;
            ClosedSet = new Map(Map.Width, Map.Height);
            OpenSet = new Map(Map.Width, Map.Height);
            CameFrom = new Map(Map.Width, Map.Height);
            RuntimeGrid = new Map(Map.Width, Map.Height);
            OrderedOpenSet = new PriorityQueue(Map);
        }

        public Path FindPath(Point start, Point goal)
        {
            var startCell = Map.GetCell(start);
            var goalCell = Map.GetCell(goal);
            if (startCell == goalCell)
                return new Path { startCell };
            ClosedSet.Clear();
            OpenSet.Clear();
            CameFrom.Clear();
            RuntimeGrid.Clear();
            OrderedOpenSet.Clear();
            startCell.G = 0.0;
            startCell.H = Map.GetDistance(startCell, goalCell);
            startCell.F = startCell.H;
            OpenSet.Add(startCell);
            OrderedOpenSet.Push(startCell);
            RuntimeGrid.Add(startCell);
            var neighbours = new Path(8);
            while (!OpenSet.IsEmpty)
            {
                var next = OrderedOpenSet.Pop();
                if (next == goalCell)
                {
                    var result = ReconstructPath(
                        CameFrom,
                        CameFrom.GetCell(goalCell.X, goalCell.Y));
                    result.Add(goalCell);
                    return result;
                }
                OpenSet.Remove(next);
                ClosedSet.Add(next);
                StoreNeighbours(next, neighbours);
                foreach (var currentNeighbour in neighbours)
                {
                    if (currentNeighbour == null
                        || currentNeighbour.IsWall
                        || ClosedSet.Contains(currentNeighbour))
                        continue;
                    var tentativeG = RuntimeGrid.GetCell(next.X, next.Y).G
                        + Map.GetDistance(next, currentNeighbour);
                    if (!TentativeIsBetter(currentNeighbour,
                        tentativeG, out var added))
                        continue;
                    CameFrom.SetWithHistory(
                        currentNeighbour.X,
                        currentNeighbour.Y,
                       next);
                    if (!RuntimeGrid.Contains(currentNeighbour))
                        RuntimeGrid.Add(currentNeighbour);
                    currentNeighbour.G = tentativeG;
                    currentNeighbour.H = Map.GetDistance(
                        currentNeighbour,
                        goalCell);
                    currentNeighbour.F = currentNeighbour.G
                        + currentNeighbour.H;
                    if (added)
                        OrderedOpenSet.Push(currentNeighbour);
                    else
                        OrderedOpenSet.Update(currentNeighbour);
                }

            }
            return null;
        }

        private bool TentativeIsBetter(
            MapCell currentNeighbour,
            double tentativeG,
            out bool added)
        {
            if (!OpenSet.Contains(currentNeighbour))
            {
                OpenSet.Add(currentNeighbour);
                added = true;
                return true;
            }
            added = false;
            return tentativeG < RuntimeGrid.GetCell(
                currentNeighbour.X,
                currentNeighbour.Y).G;
        }

        private void StoreNeighbours(MapCell c, Path neighbours)
        {
            neighbours[0] = Map.GetCell(c.X - 1, c.Y - 1);
            neighbours[1] = Map.GetCell(c.X, c.Y - 1);
            neighbours[2] = Map.GetCell(c.X + 1, c.Y - 1);
            neighbours[3] = Map.GetCell(c.X - 1, c.Y);
            neighbours[4] = Map.GetCell(c.X + 1, c.Y);
            neighbours[5] = Map.GetCell(c.X - 1, c.Y + 1);
            neighbours[6] = Map.GetCell(c.X, c.Y + 1);
            neighbours[7] = Map.GetCell(c.X + 1, c.Y + 1);
        }

        private Path ReconstructPath(Map cameFrom, MapCell currentCell)
        {
            void ReconstructPathRecursive(
                Map recursiveCameFrom,
                MapCell recursiveCurrentCell,
                Path result)
            {
                var item = recursiveCameFrom.GetCell(
                    recursiveCurrentCell.X,
                    recursiveCurrentCell.Y);
                if (item != null)
                    ReconstructPathRecursive(
                        recursiveCameFrom,
                        item,
                        result);
                result.Add(recursiveCurrentCell);

            }
            var path = new Path();
            ReconstructPathRecursive(cameFrom, currentCell, path);
            return path;
        }
    }
}

Och slutligen, typen PriorityQueue som algoritmen använder för att hålla reda på vilka celler som undersöks, ser ut så här:

using System.Collections.Generic;

namespace PathFinderAStar
{
    public class PriorityQueue
    {
        private List<MapCell> InnerList { get; } = new List<MapCell>();
        private Map Map { get; }

        public PriorityQueue(Map map)
        {
            Map = map;
        }

        public void Clear() =>
            InnerList.Clear();

        public int Push(MapCell c)
        {
            var index1 = InnerList.Count;
            c.Index = index1;
            InnerList.Add(c);
            do
            {
                if (index1 <= 0)
                    break;
                var index2 = (index1 - 1) / 2;
                if (Compare(index1, index2) < 0)
                {
                    SwitchElements(index1, index2);
                    index1 = index2;
                    continue;
                }
                break;

            } while (true);
            return index1;
        }

        public MapCell Pop()
        {
            var result = InnerList[0];
            InnerList[0] = InnerList[InnerList.Count - 1];
            InnerList[0].Index = 0;
            InnerList.RemoveAt(InnerList.Count - 1);
            result.Index = -1;
            var p = 0;
            do
            {
                var pn = p;
                var p1 = 2 * p + 1;
                var p2 = 2 * p + 2;
                if (InnerList.Count > p1 && Compare(p, p1) > 0)
                    p = p1;
                if (InnerList.Count > p2 && Compare(p, p2) > 0)
                    p = p2;
                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);
            return result;
        }

        public void Update(MapCell cell)
        {
            var count = InnerList.Count;
            while (cell.Index - 1 > 0
                && Compare(cell.Index - 1, cell.Index) > 0)
                SwitchElements(cell.Index - 1, cell.Index);
            while (cell.Index + 1 < count
                && Compare(cell.Index + 1, cell.Index) < 0)
                SwitchElements(cell.Index + 1, cell.Index);
        }

        private int Compare(int i1, int i2) =>
            Map.CompareCells(InnerList[i1], InnerList[i2]);

        private void SwitchElements(int i1, int i2)
        {
            var c1 = InnerList[i1];
            InnerList[i1] = InnerList[i2];
            InnerList[i2] = c1;
            InnerList[i1].Index = i1;
            InnerList[i2].Index = i2;
        }
    }
}

Med denna kod på plats har man en enkel funktion (FindPath) att anropa för att hitta en stig mellan två punkter (om sådan finns). Och om man vill anpassa kriterierna för hur en stig väljs, t.ex. hur terrängen ska viktas mot avståndet, görs det i funktionen GetDistance i klassen Map.

Hold-and-modify compression

A photograph usually requires 24 bits (3 bytes) per pixel. One strategy for reducing memory is to reduce the number of bits used to describe the color of each pixel, but that also reduces the number of possible colors that the format can display. A high-resolution image on the Amiga 500 typically consist of a table of 16 colors, which often is a bit too few colors for most photographic images. This is a 24-bit oroginal:

And this is the 4-bit 16-color version, that could be displayed on an Amiga:

In the 16-bit version, each pixel is a 3-byte color description, but in the 4-bit version, each pixel is a reference to a color in a 16-records long table of color. The decrease of memory consumption causes a rather obvious loss in image quality.

Hold-and-modify (HAM) allows for displaying more colors than the 16 colors stored in the table. The Amiga implementation of HAM uses a 16-color palette, and the byte array that make out the image data uses two control bits and four data bits. The control bits decide if the next four bits of the byte describes a color set (an index reference), a red modify, a green modify, or a blue modify. The last two bits per byte are not used.

So, a while a regular 16-color image uses 4 bits per pixel (a reference to a color in the table), a HAM image uses 6 bits per pixel, and if the first two is a color set, then the next four are still just a reference, like all pixels are in a regular 16-color image. But the other control bits indicate that the next four bits carries information on how the pixel color is different from the pixel to the left. It could be that it contains more red or less green, and so on, allowing up to 4096 colors to be displayed.

This method works very well on photographic images, but sharp edges may cause bleeding colors, because any pixel that is not a reference to a color table depends on its neighbor to the left. But the method works well for displaying full color images using only 6 bits per pixel instead of 3 bytes.
The artifact can be observed in this classic HAM animation by Ken Offer (1987):

Character compression per image depth

An image is a two-dimensional array of colored pixels, in this case 200 rows pf 320 pixels (320×200), today typically a 2-dimensional pixel array. Color indexing is the concept of replacing the 24-bit pixels with an 8-bit pointer to a color palette, thus reducing the memory required to represent the image. Character compression is the concept of replacing the pixel matrix with a matrix of references to a palette of 8×8 cells. Fewer bits per pixel results in poorer quality, but higher probability of finding similar 8×8 cells, and therefore a smaller image. More bits per pixel results in higher quality, but less probability of finding similar 8×8 cells, and therefore a larger image. The technique does not work well on photographic images. I use these original images:

1-bit (2 colors)

2-bit (4 colors)

3-bit (8 colors)

4-bit (16 colors)

5-bit (32 colors)

8-bit (256 colors)

In total, a 320×200 (64000) pixels image (8000 bytes) consist of 40×25 (1000) characters. On a blank image, only one of them are unique and needs to be stored. If the image contains just one set pixel, then the image contains two unique characters. One blank and one containing the pixel. Using character compression, the one pixel image requires 2000 bytes for the character index (1000 entries of 2 bytes each), 8 bytes for the empty character and 8 bytes for the character with a pixel. 2016 bytes in total, instead of the 8000 bytes that is required to store a 1-bit 320×200 pixel image.

The first (1-bit) image in this example contains 716 of 1000 unique characters and the 2000-byte index, meaning that the compressed images requires 716×8 + 2000 bytes (7728 bytes). Here is one example of matchig characters:

And here are all the matches highlighted:

By reducing the size of the character, you increase the likelihood to find duplicated character, but you increase the size of the character registry.

The probability of finding duplicate characters decrease when more colors are added (the 8-bit version of the image does not contain any duplicated characters) so a strategy for achieving better compression would be to allow a certain degree of mismatch. If two characters are similar to a certain degree, they can be treated as same. If the threshold for treating two characters as similar is too high, no compression will be achieved. If the threshold is too low, the image will look a bit off.

Uncompressed, the 8-bit image consumes one byte per pixel (not counting the color table of 256 colors). The pixel data requires 64000 (320×200) bytes and the color table requires 768 (256×3) bytes. If we use character compression to reduce the number of unique 8×8 pixel cells from 1000 to 500, the table (1000 entries, 2000 bytes) and 500 unique characters (32000 bytes) and the color palette (768 bytes), we would have reduced the memory required from 64768 bytes to 34768 bytes. However, the uncompressed image might be slightly distorted.

If I only look at average color of the character, these 429 cells are similar enough to be interchanged with another character:

Here is the compressed version of the image. The original 8-bit image consists of a color palette (768 bytes) and a pixel array of 64000 bytes. The compressed version consists of the same color palette, a 2000 byte character index and 571 characters, each requiring 64 bytes (36544 bytes).

Of course, the compression level should be slightly lowered for a perfect result, but there are lots of other measures that can be taken. Similarity can be defined in a more sophisticated way than a close average brightness and hue. For photographic images: The threshold for equality could be higher when the detail level is high (in this case, in the center of the image) and lower when the detail level is low. But for pixeled images, top-down-left-right-scanning is good enough. As a conclusion, this is the same image with a slightly lower compression level, still with room for the previous mentioned possible improvements:

A slightly lower compression level increases the output quality significantly, but I am convinced that a more intelligent compression engine will do an even better job.

Mjukvaran SQLite skrivs av oresonliga idioter

SQLite är en mjukvara för datalagring, skriven i C, som fungerar på i princip vilken enhet som helst, från t.ex. Windows Phone till Linux. Mjukvaran är Public Domain, så företaget som utvecklar den försörjer sig istället på att sälja t.ex. support, tilläggsfunktioner eller drift.

Den utvecklare som ska bidra till den officiella produkten måste leva upp till en uppförandekod på 72 punkter som finns publicerad som en del av dokumentationen på deras hemsida (läst 2018-10-23). T.ex. får man inte mörda (punkt 3), vänsterprassla (punkt 4) eller vara stolt (punkt 34), samtidigt som man måste respektera äldre (punkt 68), älska sina fiender (punkt 31) och älska att fasta (punkt 13).

Jag kan ibland vara naiv och utgå ifrån att mina kompanjoner inte är mördare, och kan därför rentav tycka att det är lite nedlåtande att behöva be någon jag ska jobba med att skriva under på det. Och ska jag vara helt ärlig så har jag över huvudet taget svårt att vara kollega med den sortens människa som antas behöva ha en uppförandekod för att inte mörda. Men om jag kan se bortom det, så vill jag naturligtvis hellre jobba med en humanist än mördare. Så vad har fastan med saken att göra?

Det är nog ingen idé att försöka förstå, för det visar sig att SQLite utvecklas av vidskepliga idioter. T.ex. finns det ingen som bidrar till produkten som inte älskar en 2000 år gammal krigsgud från Mellanöstern (punkt 1) eller som inte ger denna övernaturliga entitet äran för sina egna insatser (punkt 42). Som mjukvaruutvecklare i behov av datalagring bör du fundera på om den som behöver denna uppförandekod, och vidare, den som lever efter denna uppförandekod, är någon som du vill ha att göra med? Över huvudet taget, på något tänkbart vis? I så fall har du problem.

IMDb Scraper

IMDb Scraper is a simple library for extracting a movie title and year from a IMDb ID.

Installation (.NET Framework 4.6):

Install-Package ImdbScraper

Example:

var repository = new Repository();
var result = repository.GetMovie(87332);
Console.WriteLine(result.ToString());

 

“Mannen på gatan”

Jag ogillar verkligen att SVT använder “mannen på gatan”, men när de väl slänger kameran i ansiktet och frågar, så svarar man. Så den som tittar här, 9:30 minuter in, får veta av mig vilka nyhetskällor som är pålitliga.

Eftersom frågan kom på tal, så måste jag tillstå att jag gillar SVT och jag gillar Sveriges Radio P1. Jag vet om att de är min politiska motståndare, men jag uppskattar deras ambition att leverera objektiv och oberoende samhällsinformation.

Feel-bad movie: Excision

Excision is an excellent and very beautifully made movie about a seriously misunderstood girl. Pauline (AnnaLynne McCord) is living in the shadow of her sister Grace (Ariel Winter). The film portraits her breaking away from the high expectations put upon her, with a worst possible ending.

Beautiful performances from Malcolm McDowell, Traci Lords and Ray Wise!

Harter-Heighways drakkurva

Harter-Heighways drakkurva är en enkel och vacker linjär fraktal med många intressanta attribut. Dels är dess kontur självrepetitiv och kan pusslas ihop med lika dana konturer på många olika sätt, och linjen som kurvan består av korsar aldrig sig själv, oavsett hur lång drakkurva man väljer att rita. En drakkurva kan beskrivas som en serie av höger- och vänstersvängar. Första iterationen består av en sväng, normalt höger. Alla iterationer efter den första innehåller lika många instruktioner som den föregående, multiplicerat med två och plus 1. Alltså 1, 3, 7, 15, 31, och så vidare. Den första generationen består alltså av en högersväng (H):

H

För att skapa nästa iteration utgår man från den föregående och lägger till svängarna från den, baklänges, samtidigt som man byter ut högersvängar till vänstersvängar (V). Man avgränsar föregående iteration från den nya iterationen med en högersväng, alltså:

HHV

Tecken 1 (H) är första iterationen, nästa tecken 2 (H) är avgränsaren mellan den gamla och nya generationen, och den sista vänstersvängen (V) är vårt H från första iterationen, ersatt med ett V. Vidare, HHV baklänges blir VHH och byter man ut alla H mot V och alla V mot H så får man HVV. Då är generation tre alltså HHV, H som avgränsare och sist HVV.

HHVHHVV

Och så vidare! Nästa generation kompletteras med föregående generation baklänges, med höger ändrat till vänster och vänster ändrat till höger. Och ett H i mitten:

HHVHHVVHHHVVHVV

Ett papper kan vikas som en drakkurva, men inte i särskilt många generationer. I C# skulle man kunna använda en sådan här struktur för att beskriva ett enda steg i drakkurvan.

public struct DragonStep
{
    public DragonStep(bool isRightTurn)
            : this(isRightTurn, false) { }
    public DragonStep(bool isRightTurn,
        bool isIterationSeparator)
    {
        IsRightTurn = isRightTurn;
        IsIterationSeparator = isIterationSeparator;
    }
    public bool IsRightTurn { get; set; }
    public bool IsIterationSeparator { get; set; }
}

Egentligen behövs bara en boolesk egenskap för att hålla reda på om steget representerar en höger- eller vänstersväng, men jag vill hålla reda på var en generation börjar och slutar för att kunna rendera den med olika färger.

Här är listklassen som anropas för att bygga kurvan. Funktionen GetDragonSequence skapar en sekvens av höger och vänster-svängar i form av en lista av strukturen vi nyss såg. När man fått listan, handlar det bara om att välja en startposition och en startriktning, och sedan svänga åt höger eller vänster enligt vad som står i listan.

public class DragonCurveGenerator
{
    public static List<DragonStep> GetDragonSequence(int generations)
    {
        var ret = new List<DragonStep>();
        if (generations <= 0)
            return ret;
        if (generations > 0)
            ret.Add(new DragonStep(true));
        if (generations <= 1)
            return ret;
        for (var i = 1; i < generations; i++)
        {
            var lastGenerationFinalIndex = ret.Count - 1;
            ret.Add(new DragonStep(truetrue));
            for (var x = lastGenerationFinalIndex; x >= 0 ; x--)
                ret.Add(new DragonStep(!ret[x].IsRightTurn));
        }
        return ret;
    }
}

Jag definierar upp de möjliga riktningarna med en enumeration, för enkelhetens skull:

public enum Direction { Up, Right, Down, Left }

Sen är det bara en fråga om att rita kurvan, alltså följa sekvensen av svängar. Här får varje sväng representeras av en pixel. Notera att jag utnyttjar avgränsaren mellan iterationer för färgsättning.

public class DragonCurveRenderer
{
    public static void Draw(List<DragonStep> steps,
        Graphics g, Point startPosition, Direction startDirection,
        Brush color1, Brush color2, int first)
    {
        if (steps == null || steps.Count <= 0)
            return;
        var direction = startDirection;
        var x = startPosition.X;
        var y = startPosition.Y;
        var color = color1;
        var index = 0;
        foreach (var step in steps)
        {
            if (step.IsIterationSeparator)
            {
                color = color == color1 ? color2 : color1;
                index++;
            }
            if (index >= first)
                g.FillRectangle(color, x, y, 1, 1);
            ApplyDirection(direction, ref x, ref y);
            if (step.IsRightTurn)
            {
                if ((int) direction < 3)
                    direction++;
                else
                    direction = Direction.Up;
            }
            else
            {
                if (direction > 0)
                    direction--;
                else
                    direction = Direction.Left;
            }
        }
    }
    private static void ApplyDirection(Direction direction,
        ref int x, ref int y)
    {
        switch (direction)
        {
            case Direction.Up:
                y--;
                break;
            case Direction.Right:
                x++;
                break;
            case Direction.Down:
                y++;
                break;
            case Direction.Left:
                x--;
                break;
            default:
                throw new ArgumentOutOfRangeException();
        }
    }
}

Bilden föreställer en drakkurva på 18 generationer där generation 6 (med index 5) är den förste som ritas ut. Alltså totalt 13 fält, varannan är vit, varannan är svart. Så här kan användningen se ut (Windows Forms):

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace DragonCurve
{
    public partial class Form1 : Form
    {
        private List<DragonStep> DragonSteps { get; set; }
        public Form1()
        {
            InitializeComponent();
        }
        private void Form1_Load(object sender, EventArgs e)
        {
            DragonSteps = DragonCurveGenerator.GetDragonSequence(18);
        }
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            var startPoint = new Point(550, 450);
            DragonCurveRenderer.Draw(DragonSteps, e.Graphics,
                startPoint, Direction.Up, Brushes.White, Brushes.Black, 5);
        }
    }
}

E.T. for Atari 2600

The Atari 2600 was a home gaming console from 1977. The 2600 was a rather primitive machine compared to the later Commodore 64 (1982), but it supported hardware sprites and color graphics, which the Sinclair ZX didn’t. But the introduction price was rather high. $199 back then corresponds to more than $800 today.

Many games were released for the 2600, but one of the most talked about, E.T., was a huge commercial failure. You play as the alien E.T. on Earth, and the objective of the game is to help E.T. get home. Every move you make costs energy, but you can pick up pieces of candy to gain energy.

First, you need to pick up three parts that make up a special phone that can be used to contact the home planet. You can swap 9 pieces of candy for a part, if you like. The parts are found in pits that you fall into, and can levitate out of. To levitate, press fire so that E.T.’s neck is stretched, and when the neck is stretched, you simply levitate higher by pushing the joystick forward.

E.T. has three lives. E.T.’s friend Elliot can bring him back to life when he dies. There is a special object that persuades Elliot to give E.T. a fourth life if it is carried. The game contains two protagonists, a scientist and an FBI agent, who can capture E.T. or steal phone parts from him. If you manage to find all three phone parts, you need to locate a place where the phone works. And after finding this place, you have to locate the place where the spaceship lands, and stay there and await the ship. If you succeed, you progress to the next level where the objective is the same, but the conditions are harder.

The game looks quite good for its time, but it is it is rather buggy and unpredictable. You can fall into a pit without any warning, and it is sometimes rather hard to get out of a pit without falling in again. The best thing about this game, is that you can chat with a friend while playing – the game does not require full attention. This video shows how to complete the first level:

Grisen i säcken

26 år har passerat sedan Galenskaparna och Aftershave hade premiär med sin revy Grisen i säcken, och jag har precis sett om den versionen jag bandade på VHS i mitten av 90-talet. Revyn består av tre akter, där akt två och tre håller det format som vi är vana att se från gruppen – ett slags sofistikerat studentspex. Men det är första akten som gör denna revy speciell, och därför lämnar jag övrigt okommenterat. Den första akten är en sammanhängande musikal som gruppen själva beskriver som en dansbandsopera, viket flörtar med den för tiden populära genren rock opera, som representerades av t.ex. Pete Townshend, Savatage, Dave Clark och Styx.

Den utspelar sig 1991, vilket var året revyn hade premiär. 1991 var ett turbulent år i politiken. Ekonomin hade kraschat och stödet Socialdemokraterna var lågt. De förlorade makten till Moderaterna under Carl Bildt. Kristdemokraterna kom in i riksdagen, tillsammans med missnöjespartiet Ny Demokrati som styrdes av Ian Wachtmeister och Bert Karlsson. Det är Ny Demokratis uppgång och fall som utgör handlingen för akten – eller möjligtvis partiet Ny Deodorant som existerar i ett parallellt universum, under ledning av Rune och sedermera greven Douglas. Att Rune motsvarar Bert och Douglas motsvarar Ian är helt uppenbart för den som sett Grisen i säcken, men jag nämner det ifall du inte sett den och ändå vill förstå vad jag pratar om.

Budskapet i första akten är fortfarande aktuellt, och många händelser går att applicera på Sverigedemokraterna, men förutsättningarna är helt annorlunda. Bert och Ian (och så även Rune och Douglas) var företagsamma och mer eller mindre framgångsrika entreprenörer, medan Sverigedemokrater är frustrerade gräsrötter, helt utan tidigare erkännande i samhället de verkar i. Ny Demokrati (och även Ny Deodorant) havererade redan under första mandatperioden.

Rimligen kan inte Galenskaparna och Aftershave ha känt till hur historien om Ny Demokrati skulle sluta, när de lät sitt fiktiva parti Ny Deodorant haverera – Rune och Douglas blev tillslut programledare i tv. I valet 1994 fick Ny Demokrati 1,4 procent av väljarstödet och både Bert och Ian hoppade av. Ian fick en talkshow på TV3, “I grevens tid”, medan det gullades med Bert i Melodifestivalen – inget förlåter rasistisk politik som exploaterandet av unga artister.

När jag såg Grisen i säcken för första gången var jag V-väljare, och jag applåderade den politiska träffsäkerheten. Idag tillhör jag den politiska mitten, men tycker ändå att detta verk har åldrats väl. Jag behöver inte hålla med om allt för att förstå Claes Erikssons briljanta manus och gruppens utmärkta framförande. Men med det sagt, så delar jag förmodligen Erikssons syn på Ny Demokrati. Och kanske även på Sverigedemokraterna, men det vet jag egentligen inte.

Fem inlägg om C# på Nethouse-bloggen

Jag har skrivit fem inlägg om C# på Nethouse blogg som jag tänkte be att få dela med mig av.

Kortare kod med mönstermatchning i C# 7

Förenklad hantering av funktioner som producerar multipla värden i C#

Skalning i MonoGame

Late binding i C#

Lazy evaluated string interpolation

Uppdatering 2017-09-22:

Kort kod och syftningsfel

Uppdatering 2018-01-26:

Microsoft Cognitive Services: Computer Vision

Spaning: Framtiden för handdatorn

Min första mobiltelefon var någon gammal Ericsson som både lät mig ringa (för hutlös minuttaxa) och skicka SMS. Min första handdator* var en svartvit Sony CLIÉ med Palm OS. Den virtuella upplösningen var 320 x 320 punkter, men den fysiska upplösningen var på 640 x 640 punkter, vilket innebar att den kunde återge vektorgrafik och text betydligt bättre än bitmapsbilder. Dessutom kunde den visa 16 gråskalor. Man kunde surfa på Internet genom att koppla den till sin PC:s USB-bort och ladda hem de sidor man ville läsa senare under dagen.

Idag har dessa två enheter fusionerats till en enda enhet, som i princip är en handdator med en ringfunktion**. Många har försökt, men det var Apple som lyckades göra denna nya produkt till en kommersiell succé i slutet på 00-talet. När man idag säger “mobil” eller “telefon” så menar man en handdator som har ringfunktion (som numera knappt används). Vill man förtydliga, kan man säga “smart telefon”, men idag är det nästan som att säga “platt-tv”.

Det var inte förrän Apple gav sig in i leken som handdatorn med ringfunktion blev var mans ägo, och det var inte heller förrän Apple gav sig in i leken med produkten iPad som “surfplattan” blev en kommersiellt framgångsrik produkt. Skillnaden mellan en smart telefon och en surfplatta är att surfplattan saknar ringfunktion, och är därmed alltså en handdator.

När Microsoft på allvar ger sig in i matchen med en surfplatta uppstod förvirringen på allvar. Microsofts Surface Pro saknar tangentbord, precis som iPad, och den har touchscreen precis som iPad. Men eftersom den levereras med bättre anslutningsmöjligheter till andra enheter och med ett bredare utbud av mjukvara antas den istället vara “en dator”, vilket omkullkastar allt jag hittills sagt.

För rent tekniskt, är inte en surfplatta en telefon utan ringfunktion, utan en dator. Precis på samma sätt som en smartphone faktiskt är en dator med ringfunktion. Och eftersom dessa enheter är datorer, så är det hårdvaran och operativsystemet som påverkar deras användbarhet. En iPad har ett operativsystem (IOS) som utvecklats för informationskonsumenter, som sakta rör sig mot att även kunna tillgodose producenter. En Surface Pro har ett operativsystem som utvecklats för informationsproducenter, som sakta för sig mot att även tillgodose konsumenter. Men det är fortfarande datorer!

Nu när intresset för att ringa telefonsamtal har minskat, och Nokia släppt en traditionell mobiltelefon som kostar några hundralappar, ser jag två potentiella konsekvenser. För det första tror jag att intresset för telefoni minskar bland både producenter och konsumenter av dyra handdatorer. För det andra tror jag att den som vill kunna ringa, i framtiden kommer att köpa en telefon (i ordets traditionella bemärkelse), typ en Nokia 3310.

Apples enorma framgång med iPhone kommer göra att det annalkande paradigmskiftet dröjer, men när det väl kommer, tror jag att det innebär att den lilla handdatorn tappar sin ringfunktion, men erhåller egenskaper som gör att den ersätter PC:n. När man kör Visual Studio, Cubase, SQL Server, med mera, i sin “telefon man inte kan ringa med”, så är det “telefonen” man dockar in till skärm och tangentbord på jobbet. Men det är inte den man kommer att ringa med. Om man vill ringa, så köper man en Nokia 3310.

*) En handdator är en mycket portabel dator – så pass portabel att den kan bäras i en hand när den är i drift. En handdator har tryckkänslig skärm (touchscreen) och möjlighet till batteridrift.

**) Inte ens respektabla Cambridge Dictionary innehåller en definition av ett telefonsamtal (alltså nyttjandet av en ringfunktion), utan nöjer sig med att säga att ett telefonsamtal är vad som sker när man “använder en telefon”.

Mac vs. PC

MacWorld presenterar “11 klockrena argument” för att Mac är bättre än PC. Rent tekniskt är en Mac en PC från Apple, men det som menas här är att en Mac är bättre än en annan PC, som t.ex. en Microsoft Surface, en HP Elitebook eller en Chromebook. För detta levereras 11 “klockrena” argument (som alla utom det 4:e är korrekta), vars styrka och kvalité jag tänker nosa lite på, genom att jämföra dem med Microsoft.

1. Mac OS främjar hälsan

När OS X var nytt, var det extremt buggigt, men nu är det hyfsat stabilt. Det är viktigt för användarens mentala hälsa. Dessutom har inte mycket förändrats, vilket inte ställer frustrerande krav på användaren. Windows 8 såg inte alls ut som Windows 7, vilket var frustrerande. Detta stämmer! Däremot kan man inte säga att en modern Macbook är mindre kraschbenägen än t.ex. en modern Surface – idag hittar du Windows t.ex. i atomubåtar och i kärnkraftverk.

2. Ekosystem i världsklass

En Mac och en Iphone samspelar bra, men det råder inga som helst tvivel om att både Google och Microsoft har kommit längre än Apple i arbetet med att fusionera sina plattformar, men Apple är fortfarande världsklass med en hedrande tredje plats.

3. Färre val gör dig lyckligare

Få modeller ger få val, vilket ger mindre beslutsångest. Man skriver att Apple har sju datorer i produktion – fyra bärbara och tre stationära. Microsoft har sin Surface Pro i lite olika utföranden, en Surface Book och en Surface Studio, och det är väldigt tydligt vilken produkt som vänder sig till vilken användare. Om färre val gör dig lyckligare, blir man då ännu lyckligare av ännu färre val? Då vinner Microsoft över Apple, men här jämför man sig med Lenovo, HP eller Dell, som alla har ett större produktutbud.

4. Du slipper virus

Det du inte vet, mår du inte dåligt av – när säkerhet verkligen är ett krav, hittar man nästan alltid Windows eller Linux.

5. Du får grymma program på köpet

När man jämför mjukvaruutbudet på Windows Phone med IOS så vinner Apple. Jämför man Windows 10 med Mac OS så vinner Windows 10. Utbudet av kvalitativ mjukvara som antingen ingår i Windows-licensen eller finns som open source för Windows, är oslagbart. Men om färre val gör dig lyckligare, så är det Windows Phone och Mac OS som tar hem priset.

6. Du får vad du betalar för

“Vill du ha en dator som baseras på den senaste tekniken och har en elegant design är Apples datorer ett utmärkt val. Men visst, om det viktiga är en billig dator som klarar surfande och Facebook finns det bättre alternativ.” En Mac är inte speciellt prisvärd eller up to date, och ofta blir de tiotusentalskroners Facebook-maskiner.

7. Det bara fungerar 

Allt fungerar out of the box, men det kan vara svårt att byta ut komponenter på egen hand. Detta är inte unikt för Apple. Jag kan t.ex. inte byta batteri på min Surface Pro, men självklart levereras en märkesdator fullt installerad, utan bloatware. Det gäller naturligtvis även Microsoft.

8. Skärmarna är fantastiska

Det råder inga tvivel om att Microsoft är stråt vassare här, men skärmarna är bra! De har dessutom touch, stöd för penna och Surface Dial.

9. Fri telefonsupport

Du kan inte ringa Microsoft hur som helst när du vill ha support, du får nöja dig med att ta det i text om det ska vara gratis. Här vinner Apple, något som du förmodligen betalar för när du köper adaptrar till överpris – there is no such thing as a free lunch.

10. Touch Bar är en innovation

Det är verkligen mer innovativt att dra och rita direkt på skärmen, men visst, detta är en innovation. Inte alla modeller har någon touch bar, dock.

11. Du kommer att bli nöjd

Om du köper en produkt som är dyr, så kommer du intala dig att du är nöjd, av psykologiska skäl. Så du kommer troligen bli nöjd, av helt fel orsak.

Min slutsats är att vi inte har att göra med “11 klockrena argument”, men väl “10 argument”.

Två nya SID-låtar

Jag har slängt ihop två nya SID-låtar som kan avnjutas på din Commodore 64.

Den ena (the_roger_boogie.sid) är ett resultat från ett demo-jam på jobbet tillsammans med Klas Dahlén, Roger Johansson och Erik Sandberg. Den är egenkomponerad och använder en samtida playerrutin (SID 8580). Förhandsgranskning finns på YouTube.

Den andra, som är en cover på låten I Touch Myself av Divinyls, slände jag ihop igår kväll. Den körs på en rutin som är anpassad till den gamla brödburken (SID 6582).

Ladda gärna hem filerna här!

Entity Framework 6

Entity Framework 6 (EF6) är mycket enkelt att komma igång med. För att få tillgång till aktuell version, använd Nuget-paketet EntityFramework. Den här bloggposten visar det minsta man behöver veta för att komma igång med EF6 i sitt program.

Install-Package EntityFramework

Dessutom behöver du ha en tom databas att jobba mot. I detta exempel antar jag att databasen heter EfTest. Anslutningssträngen lagras i konfigurationsfilen. I mitt fall är det en vanlig Console Application.

  <connectionStrings>
    <add name="EfTest" providerName="System.Data.SqlClient" connectionString="Data Source=XXX;Initial Catalog=EfTest;Integrated Security=True" />
  </connectionStrings>

Nästa steg är att skapa DbContext-objektet. Denna ärver från System.Data.Entity.DbContext. Basklassen behöver veta vilken anslutningssträng som ska användas. Antingen skickar man in själva anslutningssträngen, eller så hänvisar man till ett namn. De tabeller som ska användas beskrivs av klasser och väljs in som argument till den generiska DbSet (också i System.Data.Entity). Här har jag helt enkelt skapat två klasser som heter Tabell1 och Tabell2.

    public class TestContext : DbContext
    {
        public TestContext() : base("name=EfTest")
        {
        }
        public DbSet<Tabell1> Tabell1 { get; set; }
        public DbSet<Tabell2> Tabell2 { get; set; }
    }

Låt oss titta på klassen Tabell1. Den innehåller en primärnyckel (int) och en sträng som heter Value. Attributet Key på fältet (System.ComponentModel.DataAnnotations) anger att motsvarande kolumn i databasen är en primärnyckel. Attributet DatabaseGenerated (System.ComponentModel.DataAnnotations.Schema) använder jag här för att säga att kolumnen ska vara en räknare, och alltså inte något som jag ska tillhandahålla data till vid tillägg. Det innebär alltså att nya poster skapas genom att Value får ett värde, inte Tabell1Id.

    using (var db = new TestContext())
    {
        db.Tabell1.Add(new Tabell1 {Value = "Hej"});
        db.SaveChanges();
    }

När tabellen läses av, kan man konstatera att nyckelkolumnen i detta fall ska ha fått sitt värde ändå.

    using (var db = new TestContext())
    {
        foreach (var tabell1 in db.Tabell1)
        {
            Console.WriteLine($"{tabell1.Tabell1Id} - {tabell1.Value}");
        }
    }

Det är när programmet körs första gången som databasen byggs upp automatiskt. Om en befintlig tabell förändras, t.ex. genom att klassen Tabell1 får en till property (vilket motsvarar en till kolumn) kommer programmet inte längre att fungera. Då måste en strategi för uppgradering tillhandahållas. T.ex. kan man säga att databasschemat helt enkelt ska genereras om vid förändring. Det innebär att man förlorar allt data, så med denna strategi vill man förmodligen komplettera med kod som lägger in lite testdata.

Database.SetInitializer(new DropCreateDatabaseIfModelChanges<TestContext>());

För att tillhandahålla testdata, skriv en egen initializer, baserad på den som du vill använda, och tillhandahåll testdata i funktionen Seed.

    public class DropCreateInitializer : DropCreateDatabaseIfModelChanges<TestContext>
    {
        protected override void Seed(TestContext context)
        {
            context.Tabell1.Add(new Tabell1 { Value = "Hej" });
            context.Tabell1.Add(new Tabell1 { Value = "Oj" });
        }
    }

Sen är det bara att använda sin egna initializer.

Database.SetInitializer(new DropCreateInitializer());

Fullskärm med exakt virtuell bildupplösning

Om du vill bygga ett spel med Monogame som 1) körs i fullsärmsläge och 2) har en låg virtuell upplösning, typ 320 x 200 pixlar, så finns en enkel lösning. Istället för att rendera spelet på din backbuffer, så renderar du till en render target som är just 320 x 200 pixlar stor. För att åstadkomma detta, skapa en ny property i ditt spel, av typen RenderTarget2D.

private RenderTarget2D renderTarget { get; set; }

I konstruktorn, givet att vi befinner oss i release-kompileringen, skapar man en backbuffer som är lika stor som skärmen.

            graphics = new GraphicsDeviceManager(this);
#if DEBUG
            ScreenWidth = 640;
            ScreenHeight = 400;
            graphics.PreferredBackBufferWidth = ScreenWidth;
            graphics.PreferredBackBufferHeight = ScreenHeight;
            graphics.IsFullScreen = false;
#else
            ScreenWidth = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Width;
            ScreenHeight = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Height;
            graphics.PreferredBackBufferWidth = ScreenWidth;
            graphics.PreferredBackBufferHeight = ScreenHeight;
            graphics.IsFullScreen = true;
#endif
            Content.RootDirectory = "Content";

Funktionen Initialize är en lämplig plats att skapa RenderTarget2D-objektet. Det är storleken på den som styr den virtuella upplösningen.

renderTarget = new RenderTarget2D(GraphicsDevice, 320, 200);

Slutligen renderas spelet mot RenderTarget2D-objektet. Funktionen Draw skulle kunna se ut så här:

protected override void Draw(GameTime gameTime)
{
    graphics.GraphicsDevice.SetRenderTarget(renderTarget);
    graphics.GraphicsDevice.Clear(Color.Black);

    //Rita spelet här!
    spriteBatch.Begin();
    spriteBatch.Draw(hej, new Vector2(0, 0), Color.White);
    spriteBatch.Draw(hej, new Vector2(310, 190), Color.White);
    spriteBatch.End();

    graphics.GraphicsDevice.SetRenderTarget(null);
    spriteBatch.Begin(samplerState: SamplerState.PointClamp);
    spriteBatch.Draw(renderTarget, new Rectangle(0, 0, ScreenWidth, ScreenHeight), new Rectangle(0, 0, 320, 200), Color.White);
    spriteBatch.End();
    base.Draw(gameTime);
}

Notera det sista anropet på spriteBatch.Draw, den tredje sista raden. Den skalar upp spelet till den riktiga back bufferten. Om man vill ha rektangulära pixlar, ska det hanteras där. Denna exempelkod tar inte hänsyn till olika bildförhållanden.

Så här ser hela koden ut:

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;

namespace Game1
{
    public class Game1 : Game
    {
        private RenderTarget2D renderTarget { get; set; }
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;
        private int ScreenWidth { get; }
        private int ScreenHeight { get; }
        private Texture2D hej;

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
#if DEBUG
            ScreenWidth = 640;
            ScreenHeight = 400;
            graphics.PreferredBackBufferWidth = ScreenWidth;
            graphics.PreferredBackBufferHeight = ScreenHeight;
            graphics.IsFullScreen = false;
#else
            ScreenWidth = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Width;
            ScreenHeight = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Height;
            graphics.PreferredBackBufferWidth = ScreenWidth;
            graphics.PreferredBackBufferHeight = ScreenHeight;
            graphics.IsFullScreen = true;
#endif
            Content.RootDirectory = "Content";
        }
        protected override void Initialize()
        {
            renderTarget = new RenderTarget2D(GraphicsDevice, 320, 200);
            base.Initialize();
        }
        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
            hej = Content.Load<Texture2D>("hej");
        }
        protected override void Update(GameTime gameTime)
        {
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.Escape))
                Exit();
            base.Update(gameTime);
        }
        protected override void Draw(GameTime gameTime)
        {
            graphics.GraphicsDevice.SetRenderTarget(renderTarget);
            graphics.GraphicsDevice.Clear(Color.Black);

            //Rita spelet här!
            spriteBatch.Begin();
            spriteBatch.Draw(hej, new Vector2(0, 0), Color.White);
            spriteBatch.Draw(hej, new Vector2(310, 190), Color.White);
            spriteBatch.End();

            graphics.GraphicsDevice.SetRenderTarget(null);
            spriteBatch.Begin(samplerState: SamplerState.PointClamp);
            spriteBatch.Draw(renderTarget, new Rectangle(0, 0, ScreenWidth, ScreenHeight), new Rectangle(0, 0, 320, 200), Color.White);
            spriteBatch.End();
            base.Draw(gameTime);
        }
    }
}

Jag utvecklar detta på min arbetsgivares blogg.

Skala upp Monogame

När man bygger retrospel med en upplösning på omkring 320 x 200 pixlar, vill man gärna skala upp spelet så att sprites och andra objekt inte blir så små på en modern skärm. För den som programmerar Monogame finns flera lösningar. Jag tycker att den enklaste metoden är att använda ett transform matrix. När jag debuggar mitt spel, tycker jag att en uppskalning på 3 x 3 är rätt lämplig, vilket innebär att ett fönster på 960 x 600 pixlar är lämpligt. Detta är spelets konstruktor, spelet har kompletterats med en medlemsvariabel vid namn transformMatrix av typen Matrix.

graphics.PreferredBackBufferWidth = 960;
graphics.PreferredBackBufferHeight = 600;
graphics.IsFullScreen = false;
transformMatrix = Matrix.CreateScale(960 / 320, 600 / 200, 1.0f);

I skarpt läge låter jag skärmupplösningen styra skalningen, eftersom jag vill att spelet ska köras i fullskärm.

var width = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Width;
var height = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Height;
graphics.PreferredBackBufferWidth = width;
graphics.PreferredBackBufferHeight = height;
graphics.IsFullScreen = true;
transformMatrix = Matrix.CreateScale(width / 320, height / 200, 1.0f);

För att effekten ska slå igenom, ska Matrix-objektet skickas med till SpriteBatch-objektets Begin-metod. För att undvika oönskad kantutjämning använder jag en sampler state som heter PointClamp.

spriteBatch.Begin(transformMatrix: transformMatrix, samplerState: SamplerState.PointClamp);

Ett exempelspel skulle kunna se ut så här:

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;

namespace Game1
{
    public class Game1 : Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;
        Matrix transformMatrix;
        Texture2D testtexture { get; set; }
        private int x = 0;
        private int y = 0;
        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
#if DEBUG
            graphics.PreferredBackBufferWidth = 960;
            graphics.PreferredBackBufferHeight = 600;
            graphics.IsFullScreen = false;
            transformMatrix = Matrix.CreateScale(960 / 320, 600 / 200, 1.0f);
#else
            var width = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Width;
            var height = GraphicsAdapter.DefaultAdapter.CurrentDisplayMode.Height;
            graphics.PreferredBackBufferWidth = width;
            graphics.PreferredBackBufferHeight = height;
            graphics.IsFullScreen = true;
            transformMatrix = Matrix.CreateScale(width / 320, height / 200, 1.0f);
#endif
            Content.RootDirectory = "Content";
        }
        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
            testtexture = Content.Load<Texture2D>("my_folder");
        }
        protected override void Update(GameTime gameTime)
        {
            var state = Keyboard.GetState();
            if (state.IsKeyDown(Keys.Escape))
                Exit();
            if (state.IsKeyDown(Keys.Left))
                x--;
            else if (state.IsKeyDown(Keys.Right))
                x++;
            if (state.IsKeyDown(Keys.Up))
                y--;
            else if (state.IsKeyDown(Keys.Down))
                y++;
            base.Update(gameTime);
        }
        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);
            spriteBatch.Begin(transformMatrix: transformMatrix, samplerState: SamplerState.PointClamp);
            spriteBatch.Draw(testtexture, new Vector2(x, y), Color.White);
            spriteBatch.End();
            base.Draw(gameTime);
        }
    }
}

Ett problem som man bör känna till, är att om bildförhållandet mellan den virtuella upplösningen och den fysiska upplösningen inte är samma, så kommer fler pixlar än önskat att synas. När man kör i fönster, så kan man styra detta så att bildförhållandet är detsamma. 960 x 600 har samma bildförhållande som 320 x 200. Men i fullskärmsläge bör man ha detta i åtanke.

Jag utvecklar detta på min arbetsgivares blogg.

Labyrint (recursive backtracking)

Jag har börjat arbeta med ett datorspel i kategorin roguelike. Varje spel ska vara unikt, så kartan genereras när en användare spelar spelet. Vid uppstart skapar jag en labyrint som sen används som kontur för rummen som genereras efter behov. De rum som spelaren inte besöker behöver man trots allt inte hålla i RAM, men jag vill ha konturen färdig för att kunna ha lite kontroll över kartans kvalité.

 
Totalt okunnig om labyrintalgoritmer läste jag igenom Wikipedias artikel om recursive backtracking som i korthet går ut på följande:
1. Utgå från den cell som ska vara startpunkten, C.
 
2. Om C inte är vald sedan tidigare, plocka bort en slumpvis utvald vägg på C. Följ den nyskapade öppningen och låt den vara C.
 
3. Om nya C har varit C tidigare, stega bakåt till första cell som fortfarande har fyra väggar, gör den till C, upprepa steg 2.
 
4. Om C nu är samma som var C vid punkt 1 så är labyrinten klar.
 
Så i princip startar mitt (blivande) datorspel med en hel hög av celler (precis hur många jag vill) som håller information om in- och utgångar (konturen), men det är först när cellen används som fyller jag på med s.k. tiles, alltså de byggstenar som bestämmer kartans detaljer. Låt oss titta på själva labyrinten, och lämna resten därhän.
För detta exempel valde jag språket C#. Trots att språket är lite pratigt, är det ganska flexibelt och användbart.

Först av allt behövs en entitet – en cell – som kan ha väggar i fyra riktningar: Norr, öst, söder och väst. Jag anger att jag både vill kunna läsa (get) och skriva (set) dessa egenskaper under programmets gång. Initialt måste cellen ha alla sina fyra möjliga väggar.

public class Cell
{
    public bool WallNorth { get; set; } = true;
    public bool WallEast { get; set; } = true;
    public bool WallSouth { get; set; } = true;
    public bool WallWest { get; set; } = true;
}

Vidare måste cellen kunna svara på var i labyrinten den befinner sig. Det behövs för att cellens grannar ska kunna hittas. En cell som inte kan svara på det, får inte skapas över huvudet taget.

    public int X { get; }
    public int Y { get; }
    public Cell(int x, int y)
    {
        X = x;
        Y = y;
    }

Eftersom cellen enligt algoritmens regler måste kunna svara på hur många väggar den har, måste vi beskriva hur vi kan veta det.

    public int WallsCount
    {
        get
        {
            var c = WallNorth ? 1 : 0;
            c += WallEast ? 1 : 0;
            c += WallSouth ? 1 : 0;
            c += WallWest ? 1 : 0;
            return c;
        }
    }

Och slutligen måste cellen kunna berätta om sin position i ett lämpligt format.

    public Point Position => new Point(X, Y);

Därefter behövs en representation av själva labyrinten som kan hålla en matris av celler. Denna gång väljer jag att skapa en liten labyrint med 100 celler (10 x 10). Bredden och höjden måste kunna läsas (get) under programmets gång. Koden skapar inte cellerna, endast platshållaren för dem.

public class Labyrinth
{
    public static int Width { get; } = 10;
    public static int Height { get; } = 10;
    public Cell[,] Cell = new Cell[Width, Height];
}

Sen ska vi beskriva algoritmen i labyrintens konstruktor (=funktion med ansvar för initiering). Vi börjar med att berätta att vi vill kunna skapa slumptal, och att platshållaren för våra celler verkligen ska innehålla celler.

        var rnd = new Random();
        for (var y = 0; y < Height; y++)
            for (var x = 0; x < Width; x++)
                Cells[x, y] = new Cell(x, y);

Därefter måste vi definiera konceptet med grannar för konstruktorn. Grannar är angränsande celler.

        Func<int, int, List<Point>> getNeighbours = (x, y) =>
        {
            var ret = new List<Point>();
            if (y > 0 && Cells[x, y - 1].WallsCount >= 4)
                ret.Add(Cells[x, y - 1].Position);
            if (x < Width - 1 && Cells[x + 1, y].WallsCount >= 4)
                ret.Add(Cells[x + 1, y].Position);
            if (y < Height - 1 && Cells[x, y + 1].WallsCount >= 4)
                ret.Add(Cells[x, y + 1].Position);
            if (x > 0 && Cells[x - 1, y].WallsCount >= 4)
                ret.Add(Cells[x - 1, y].Position);
            return ret;
        };

Sen måste vi beskriva hur man slår in en vägg. Det är inte så enkelt som att sätta en cells vägg-egenskap (t.ex. WallNorth) till false, eftersom grannen åt det hållet också måste få sin motsvarande vägg (t.ex. WallSouth) satt till false.

        Action<Cell, Point> knockWall = (cell1, cell2) =>
        {
            if (cell2.Y < cell1.Y)
            {
                cell1.WallNorth = false;
                Cells[cell2.X, cell2.Y].WallSouth = false;
                return;
            }
            if (cell2.X > cell1.X)
            {
                cell1.WallEast = false;
                Cells[cell2.X, cell2.Y].WallWest = false;
                return;
            }
            if (cell2.Y > cell1.Y)
            {
                cell1.WallSouth = false;
                Cells[cell2.X, cell2.Y].WallNorth = false;
                return;
            }
            if (cell2.X < cell1.X)
            {
                cell1.WallWest = false;
                Cells[cell2.X, cell2.Y].WallEast = false;
                return;
            }
        };

Nu har konstruktorn tillgång till resurserna, och den vet vad en granne är och hur man slår in en vägg. Dags att sätta igång! Vi behöver hålla koll på vilka celler vi besökt…

            var queue = new Queue<Cell>();

…och så behöver vi en slumpvis utvald cell att börja i.

            var c = Cells[rnd.Next(Width), rnd.Next(Height)];
            queue.Enqueue(c);

Därefter, slå ut en vägg och följ efter. Om det inte går, backa till start och prova igen.

            while (queue.Count > 0)
            {
                var neighbours = getNeighbours(c.X, c.Y);
                if (neighbours.Count > 0)
                {
                    var neighbour = neighbours[rnd.Next(neighbours.Count)];
                    knockWall(c, neighbour);
                    queue.Enqueue(c);
                    c = Cells[neighbour.X, neighbour.Y];
                }
                else
                {
                    c = queue.Dequeue();
                }
            }

 
För att representera detta på skärmen, behöver jag bara bekymra mig om två av väggarna, höger och under. Högra grannens vänstervägg och undre grannens övre vägg har samma status (tack vare knockWall).
    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        const int size = 20;
        for (var y = 0; y < Labyrinth.Height; y++)
            for (var x = 0; x < Labyrinth.Width; x++)
            {
                if (Labyrinth.Cells[x, y].WallEast)
                    e.Graphics.DrawLine(Pens.Black, x * size + (size - 1), y * size, x * size + (size - 1), y * size + (size - 1));
                if (Labyrinth.Cells[x, y].WallSouth)
                    e.Graphics.DrawLine(Pens.Black, x * size, y * size + (size - 1), x * size + (size - 1), y * size + (size - 1));
            }
    }
 
Hela källkoden ser ut så här:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        private Labyrinth Labyrinth { get; } = new Labyrinth();
        public Form1()
        {
            InitializeComponent();
        }

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        const int size = 20;
        for (var y = 0; y < Labyrinth.Height; y++)
            for (var x = 0; x < Labyrinth.Width; x++)
            {
                if (Labyrinth.Cells[x, y].WallEast)
                    e.Graphics.DrawLine(Pens.Black, x * size + (size - 1), y * size, x * size + (size - 1), y * size + (size - 1));
                if (Labyrinth.Cells[x, y].WallSouth)
                    e.Graphics.DrawLine(Pens.Black, x * size, y * size + (size - 1), x * size + (size - 1), y * size + (size - 1));
            }
    }
    }
    public class Cell
    {
        public bool WallNorth { get; set; } = true;
        public bool WallEast { get; set; } = true;
        public bool WallSouth { get; set; } = true;
        public bool WallWest { get; set; } = true;
        public int X { get; }
        public int Y { get; }
        public Cell(int x, int y)
        {
            X = x;
            Y = y;
        }
        public int WallsCount
        {
            get
            {
                var c = WallNorth ? 1 : 0;
                c += WallEast ? 1 : 0;
                c += WallSouth ? 1 : 0;
                c += WallWest ? 1 : 0;
                return c;
            }
        }
        public Point Position => new Point(X, Y);
    }
    public class Labyrinth
    {
        public static int Width { get; } = 10;
        public static int Height { get; } = 10;
        public Cell[,] Cells = new Cell[Width, Height];
        public Labyrinth()
        {
            var rnd = new Random();
            for (var y = 0; y < Height; y++)
                for (var x = 0; x < Width; x++)
                    Cells[x, y] = new Cell(x, y);
            Func<int, int, List<Point>> getNeighbours = (x, y) =>
            {
                var ret = new List<Point>();
                if (y > 0 && Cells[x, y - 1].WallsCount >= 4)
                    ret.Add(Cells[x, y - 1].Position);
                if (x < Width - 1 && Cells[x + 1, y].WallsCount >= 4)
                    ret.Add(Cells[x + 1, y].Position);
                if (y < Height - 1 && Cells[x, y + 1].WallsCount >= 4)
                    ret.Add(Cells[x, y + 1].Position);
                if (x > 0 && Cells[x - 1, y].WallsCount >= 4)
                    ret.Add(Cells[x - 1, y].Position);
                return ret;
            };
            Action<Cell, Point> knockWall = (cell1, cell2) =>
            {
                if (cell2.Y < cell1.Y)
                {
                    cell1.WallNorth = false;
                    Cells[cell2.X, cell2.Y].WallSouth = false;
                    return;
                }
                if (cell2.X > cell1.X)
                {
                    cell1.WallEast = false;
                    Cells[cell2.X, cell2.Y].WallWest = false;
                    return;
                }
                if (cell2.Y > cell1.Y)
                {
                    cell1.WallSouth = false;
                    Cells[cell2.X, cell2.Y].WallNorth = false;
                    return;
                }
                if (cell2.X < cell1.X)
                {
                    cell1.WallWest = false;
                    Cells[cell2.X, cell2.Y].WallEast = false;
                    return;
                }
            };
            var queue = new Queue<Cell>();
            var c = Cells[rnd.Next(Width), rnd.Next(Height)];
            queue.Enqueue(c);
            while (queue.Count > 0)
            {
                var neighbours = getNeighbours(c.X, c.Y);
                if (neighbours.Count > 0)
                {
                    var neighbour = neighbours[rnd.Next(neighbours.Count)];
                    knockWall(c, neighbour);
                    queue.Enqueue(c);
                    c = Cells[neighbour.X, neighbour.Y];
                }
                else
                {
                    c = queue.Dequeue();
                }
            }
        }
    }
}
Och detta är resultatet:
 

Ghostbusters (2016)

Paul Feig lämnade nästan garantier på att rebooten av Ghostbusters skulle vara dålig. En kass trailer, en hip hop-remix av soundtracket, rasstereotyper, könsstereotyper och en provokativ damage control. Under resans gång lyckades Reddit publicera filmens synopsis och regissör Paul Feig lät hälsa att den så kallade “nördkulturen” innehåller några av planetens minst sympatiska människor.

Det sista vill jag kommentera, eftersom nördkulturen är något som ligger mig varmt om hjärtat. Jag är inte någon nörd, ens i ordets nya, positiva bemärkelse. Visst har jag fastnat lite i gamla Commodore-maskiner och Linda och Valentin-böckerna, men det jag gillar med nördkulturen är de riktiga nördarna. Och jag känner tillräckligt många för att kunna säga att man får leta på andra platser om man verkligen vill hitta några av planetens minst sympatiska människor.

Tvärt emot det intryck som trailern gav, så fungerade faktiskt många skämt. Det havererade lite när karaktären Kevin anställdes mot Abbys vilja, för att både Erin och Jillian hade mindre professionella motiv att vilja anställa honom. Den situationen hade kanske varit ännu värre om spökligan vore män som anställde en kvinna.

Trots att filmen hade högre budget än originalet, var specialeffekterna märkbart sämre. Personkemin mellan spökjägarna fungerade sisådär, men var och en var de jättebra. Regin var undermålig, vilket är det absolut bästa man kan förvänta sig av Feig.

En av de viktigaste orsakerna till att den nya Ghostbusters-filmen inte behöll samma spökliga som vi såg på bio 1984, är naturligtvis Harold Ramis bortgång. Men vi fick faktiskt se resten av gänget, Bill Murray, Ernie Hudson och Dan Aykroyd, skymta förbi. Förmodligen under tvång, med tanke på filmens rykte. Jag klickade på 6 av 10 på IMDb, och bidrog därmed till att (i skrivande stund) höja filmens snitt.

Uppdatering 2017-08-10: Mr. Plinkett’s Ghostbusters (2016) Review

Min första Cordova-app

Denna bloggpost är ett resultat av mitt första försök att skapa en plattformsoberoende app med Visual Studio 2015 och Cordova, som pratar med ett Web API.

När man väljer att skapa en Cordova-app i Visual Studio, får man med lite kod som man kanske inte vill ha med när man testar lite själv. Jag valde att rensa innehållet i den div vars klass heter “app”, helt tömma CSS-filen från innehåll, och rensa upp allt utom “pause” och “resume” från index.js.

Därefter installerade jag jQuery och jQuery Mobile. Här finns det två saker att tänka på. För det första passar inte nödvändigtvis den senaste jQuery Mobile ihop med den senaste jQuery. Efter en googling kunde jag konstatera att version 1.4.5 av jQuery Mobile fungerar med version 2.1.4 av jQuery, så dessa installerade jag.

Install-Package jquery -version 2.1.4
Install-Package jquery.mobile -version 1.4.5

Det andra att ha i åtanke är att script-filerna installeras i mapparna Scripts respektive Content. Men i en Cordova-app ska dessa ligga under www/scripts respektive www/css, så man måste manuellt flytta dem dit, genom att dra och släppa i Solution Explorer. Sen är det bara att inkludera i head-sektionen på index.html.

<script type="text/javascript" src="scripts/jquery-2.1.4.min.js"></script>
<script type="text/javascript" src="scripts/jquery.mobile-1.4.5.min.js"></script>

Inuti min div (“app”) placerar jag två bilder, “firstScreen” och “secondScreen”, där jag låter den första innehålla ett enkelt formulär och den andra vara dold.

<div id="firstScreen">
    <form target="http://localhost:64924/api/Values" method="get">
        <input type="text" id="p1" name="p1" />
        <br />
        <input type="text" id="p2" name="p2" />
        <br />
        <input type="button" onclick="submitForm();" />
    </form>
</div>
<div id="secondScreen" style="display: none;">
    Hello!
</div>

Koden för att skicka innehållet i formuläret till servern, antar att jag har ett enkelt Web API igång. Om det gick bra, presenterar jag svaret på den nya sidan och visar den. Om det inte gick bra, skriver jag fail i en textbox.

function submitForm() {
    var x = { p1: $("#p1").val(), p2: $("#p2").val() };

    $.post('http://localhost:64924/api/Values/', x, { headers: { 'Accept': 'application/json', 'Content-Type': 'application/json' } })
    .success(function(data, status) {
        $("#firstScreen").hide();
        $("#secondScreen").text(data);
        $("#secondScreen").show();
    })
    .error(function(data, status) {
        $("#p1").val("Fail!");
    });
}

Cordova-appen pekar ut en ASP.NET Web API-applikation, som är väldigt lik exempelapplikationen som man får om man väljer att skapa en sådan i Visual Studio 2015. Jag pekar på den exempelcontroller som följde med, Values. Eftersom jag gör en http-post förväntar jag mig att metoden Post ska svara. Argumentet som jag tar emot, har två properties vars namn stämmer överens med datat i formuläret: p1 och p2. Funktionen gör just inget annat än att skicka tillbaka strängen “From server!” till Cordova-appen.

public string Post([FromBody]Testmeddelande value)
{
    return "From server!";
}

Därmed har jag en enkel plattformsoberoende app som kan samla in och skicka data, samt ta emot och presentera svaret.