Happy Birthday Wikipedia

On January 15th 2001, Wikipedia launched.

It has its faults, it has its detractors and abuse. But it's also one of (if not the) most popular websites on the Interwebs.

It made official the decentralization of knowledge for the masses: you're a random expert on a bacteria in a specific kind of cheese? Chime in. No need for someone to write a book on the topic, publish it, and spread it around university libraries anymore!

Of course, it also re centralized knowledge in a way. It is the default encyclopedia, after all.

But I love seeing students going down the rabbit hole of tech I pointed to and learning things.

Even if the articles aren't the best about a topic, they contain enough to fan the flames of curiosity, and to me that's a win.

Algorithm Of The Day : Combinatory

So, I'd like to take x elements out of an array of n elements. I know from statistical analysis that there are a precise number of combinations:

$$\frac{n!}{x!.(n-x)!}$$

But what are they? There are a few classic algorithms to do that, but most of them are recursive and use an accumulator, not exactly Swift's forte, especially if you don't know the right keyword. Cue inout

So here's the rough idea: every time we select an item in the array, we have only n-1 items to pick from, and x-1 items to pick. So it's recursive in nature. But we have an array, which means that we can make every possible combinations using the first item in the array first, then start again by removing the first item, and we should never repeat the combinations.

Here's an example: let's take 3 elements out of an array of 4

John Paul Ringo George

----------------------

John Paul Ringo
John Paul       George
John      Ringo George
     Paul Ringo George

It definitely looks like loops: We do all of John's first, then when we're done we do Paul's, and then we're done because we don't have enough people to start with Ringo.

Another way of looking at it is "I've selected John, now start again with the rest of the list and pick 2", then "I've selected Paul, now start again with the rest of the list and pick 1", then "I've started with Ringo, now start again with the rest of the list and pick 1". When we're done with the lists starting with John, we remove him, start with Paul, and there's only one choice.

In swift, because of the extension mechanism, it's easy to generalize to every array, but we still need that recursion that needs both where we are and what's left to work. Then all we need to manage is the special edge cases:

  • there is no element in the array (because it's easy to deal with)
  • there is less elements in the array than we want (ditto)
  • there is exactly as many elements in the array as we want (well duh, there's only one possibility)

So here is the algorithm, with accumulators passed with inout (to modify them in the callee and the caller):

extension Array { // combinatory
    fileprivate func recArrangements(len: Int, start: Int, cur: inout [Element], result : inout [[Element]]) {
        if len == 0 {
            result.append([Element](cur))
        } else {
            var i = start
            while i <= (self.count-len) {
                cur[cur.count - len] = self[i]
                recArrangements(len: len-1, start: i+1, cur: &cur, result: &result)
                i += 1
            }
        }
    }
    
    func arrangements(of number: Int) -> [[Element]]? {
        if self.count == 0 { return nil }
        else if number > self.count { return nil }
        else if number == self.count { return [self] }
        var buffer = [Element](repeating: self[0], count: number)
        var result = [[Element]]()
        recArrangements(len: number, start: 0, cur: &buffer, result: &result)
        return result
    }
}

Proofs that it works:

> ["John", "Paul", "Ringo", "George"].arrangements(of: 3)
$R0: [[String]]? = 4 values {
  [0] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "Ringo"
  }
  [1] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "George"
  }
  [2] = 3 values {
    [0] = "John"
    [1] = "Ringo"
    [2] = "George"
  }
  [3] = 3 values {
    [0] = "Paul"
    [1] = "Ringo"
    [2] = "George"
  }
}
["Potassium",
"Calcium",
"Scandium",
"Titanium",
"Vanadium",
"Chromium",
"Manganese",
"Iron",
"Cobalt",
"Nickel",
"Copper",
"Zinc",
"Gallium",
"Germanium",
"Arsenic",
"Selenium",
"Bromine",
"Krypton"].arrangements(of: 3).count
$R1: Int? = 43758

Which fits $$\frac{18!}{8!.10!}=43758$$

Unfortunately, as with most recursive algorithms, its complexity is fairly horrendous... It is equivalent to 3 nested for loops (the way to write that code is left as an exercise), which means a whopping ... Then again, combinatory has a way of being exponential anyways. I wonder if there is a way to be more efficient.

[Dev Diaries] URL Shortener Style Things

UUIDs are fine, but who doesn't like a decent String instead? It's shorter and it doesn't scare the non-programmers as much!

UUIDs are 128 bits, and I want to use a 64 characters map: a to z, A-Z, and 0-9, plus - and + to round it up.

64 possibilities is equivalent to 6 bits of data, and UUIDs are made of 16 bytes (8 bits of data). What that gives me is a way to split 16 bytes into 22 sixytes (yes I invented that word. So what?)

| 8 8 8 _ | 8 8 8 _ | 8 8 8 _ | 8 8 8 _ | 8 8 8 _ | 8
| 6 6 6 6 | 6 6 6 6 | 6 6 6 6 | 6 6 6 6 | 6 6 6 6 | 6 6

Why? Because 3x8 = 6x4, same number of bits in both.

Now, we redistribute the bits around (Xs are the bits fron the bytes, Ys are the bits from the sixytes):

XXXXXX|XX XXXX|XXXX XX|XXXXXX
YYYYYY|YY YYYY|YYYY YY|YYYYYY

With some shifts and some binary or, we're down from a 36 hexadecimal character string with dashes to a 22 character with a very low probability of punctuation. Of course if you want to disambiguate the symbols like O and 0, you can change the character map, as long as your charmap stays 64 items long.

extension UUID {
    static let charmap = 
["a","b","c","d","e","f","g","h","i","j","k","l","m","n",
"o","p","q","r","s","t","u","v","w","x","y","z",
"A","B","C","D","E","F","G","H","I","J","K","L","M","N",
"O","P","Q","R","S","T","U","V","W","X","Y","Z",
"0","1","2","3","4","5","6","7","8","9","-","+"]
    static let charmapSet =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-+"

    var tinyWord : String {
        let from = self.uuid
        let bytes = [from.0, from.1, from.2,from.3,from.4,from.5,from.6,from.7,from.8,from.9,
                     from.10, from.11, from.12,from.13,from.14,from.15]
        
        // split in 6-bits ints
        var sbytes : [UInt8] = []
        for i in 0..<5 {
            let b1 = bytes[i*3]
            let b2 = bytes[i*3+1]
            let b3 = bytes[i*3+2]
            
            let sb1 = b1 >> 2
            let sb2 = (b1 & 0x03) << 4 | (b2 >> 4)
            let sb3 = (b2 & 0x0f) << 2 | (b3 >> 6)
            let sb4 = (b3 & 0x3f)
            sbytes += [sb1,sb2,sb3,sb4]
        }
        // all done but the last byte
        sbytes.append(bytes[15]>>2)
        sbytes.append(bytes[15]&0x03)
         
        var result = ""
        for i in sbytes {
            result += UUID.charmap[Int(i)]
        }
        
        return result
    }
}

The reverse procedure is a bit longer, because we have to stage the values in groups of 4 sexytes for 3 bytes, and do a couple of sanity checks.

extension UUID {
    init?(tinyWord: String) {
        if tinyWord.count != 22 || !tinyWord.allSatisfy({ UUID.charmapSet.contains($0) }) { return nil }
        var current : UInt8 = 0
        var bytes : [UInt8] = []
        for (n,c) in tinyWord.enumerated() {
            guard let idx32 = UUID.charmap.firstIndex(of: String(c)) else { return nil }
            let idx = UInt8(idx32)
            if n >= 20 { // last byte
                if n == 20 {
                    current = idx << 2
                } else {
                    current |= idx
                    bytes.append(current)
                }
            } else if n % 4 == 0 { // first in cycle
                current = idx << 2
            } else if n % 4 == 1 { // combine
                current |= idx >> 4
                bytes.append(current)
                current = (idx & 0xf) << 4
            } else if n % 4 == 2 { // combine
                current |= (idx >> 2)
                bytes.append(current)
                current = (idx & 0x3) << 6
            } else {
                current |= idx
                bytes.append(current)
                current = 0
            }
        }
        
        // double check
        if bytes.count != 16 { return nil }
        
        self.init(uuid: (bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7], bytes[8], bytes[9],
                         bytes[10], bytes[11], bytes[12], bytes[13], bytes[14], bytes[15]))
    }
}

Let's test this!

let u = UUID()
let w = u.tinyWord
print(u.uuidString+" : \(u.uuidString.count)")
print(w+" : \(w.count)")
print(UUID(tinyWord: w)!)
30A5CB6E-778F-4218-A333-3BC8B5A40B65 : 36
mkxlBNEpqHIJmZViTAqlzb : 22
30A5CB6E-778F-4218-A333-3BC8B5A40B65

Now I have a "password friendly" way to pass UUIDs around. Is it a waste of time (because I could just pass the UUIDs around, they aren't that much longer)? Who knows? It makes my shortened URLs a bit less intimidating 😁

[Dev Diaries] FrickinTodos

Everybody knows that when you start a new web framework or language, you have to start by a todo list, right?

My friend Steven and I have a problem: we attend a regular meeting (every other week) to synchronize with our colleagues on multiple topics, deal with emerging emergencies, etc etc. But we have so much on our plate in the intervening time that we forget some things, and we keep adding new stuff to the "to be dealt with later"

So we had an idea for a very simple way to do things:

  • We have a list of topics that need to be discussed
  • A topic has a discussion and comments attached (usually a very lively conversation)
  • Then a topic is set either as dealt with, or delayed till the next meeting
  • Every "open" topic has to end in either category
  • At the end of the meeting, when all the topics from the previous meeting, and the new ones, have either been marked as done or delayed, we generate a report, and prepare the next meeting to have all the delayed items ready for reuse.

The need to rebel

It so happens that IBM has announced that they were pulling off from Kitura. It's a shame, I like it (and use it) a lot, but hey, it's open source, so I'll keep my hopes up.

My server (on which this blog ran) died a little while ago, forcing me to reinstall everything (I've lost a couple of articles on this blog in the process), so I was very busy with "going tidy with my system", and the idea Steven and I had popped in the forefront as a way to occupy my developer brain while the gigabytes of data were transiting over the InterPipes.

So, I wanted to tie together a few technologies I know in an amateur kind of way into a production ready thing:

  • Swift DSLs
  • Kitura
  • HTTP Sessions
  • Redis
  • Docker
  • Ajax/jQuery

It's ugly (I'm no designer), but it's functional, and the workflow seems OK to me. A few caveats before I dive in:

  • There is no login/password. The data is stored in the session, meaning that if you change browser (or machine), you start new. You can't share it with someone else either. This solves one, and one only, problem: keeping track of the things that were deferred to next time, because that's the thing that we have trouble with.
  • This is for educational purposes, mostly my own. If you want to expand on it, feel free. If you want to use it, remember it solves just my problem.
  • The technological choices are motivated by my wanting to test my chops, not to make a tool that everyone will be using. I might turn it into something else later, but for now, it's just another Todo demo.

The DSLs

Back in June, I predicted to my Cocoaheads friends that the HTML DSL would be the first to appear, after SwiftUI (the video, in french, here).

Bingo: https://github.com/pointfreeco/swift-html.git

While the syntax isn't as clean as SwiftUI, it's also a labor of love by PointFree's developers Stephen Celis and Brandon Williams, for reasons not too dissimilar to my own.

let document: Node = .document(
  .html(
    .body(
      .h1("Welcome!"),
      .p("You’ve found our site!")
    )
  )
)

Type safety, enums, the whole nine yards. So yea, pretty cool.

That was to help with my somewhat sketchy HTML skills. At least the syntax problems and various pitfalls were avoided.

The session

Sessions in Kitura just require Codable objects to be stored. Good thing my Todo structure is Codable:

enum TodoStatus : String, Codable {
    case pending
    case done
    case delayed
    
    static var asXSource : String {
        return """
        [{value: 'pending', text: 'pending'},{value: 'done', text: 'done'},{value: 'delayed', text: 'delayed'}]
        """
    }
    
    var imageName : String {
        return "/"+self.rawValue+".png"
    }
}

struct Todo : Codable {
    var id: UUID = UUID()
    var title: String
    var comment: String?
    var status : TodoStatus
    
    var todoid : String { return "t"+self.id.uuidString.replacingOccurrences(of: "-", with: "") }
    var editid : String { return self.todoid+"_e" }
    var titleid : String { return self.todoid+"_t" }
    var commentid : String { return self.todoid+"_c" }
    var statusid : String { return self.todoid+"_s" }
    
    var imageName : String {
        return status.imageName
    }
    
    var asHtmlNode : Node {
        return Node.fragment([
            .h3(
                .span(attributes: [.id(self.editid)], .img(src: "/edit.png", alt: "Edit")),
                .span(attributes: [.id(self.titleid)], .text(self.title))
            ),
            .div(
                .div(attributes: [],
                     .img(attributes: [.id(self.statusid), .src(self.imageName), .alt(self.status.rawValue), .height(.px(24)), .width(.px(24))]),
                     .span(.raw("&nbsp;")),
                     .span(attributes:[.id(self.statusid + "t"), .class("status-text")], .text(self.status.rawValue))
                ),
                .div(attributes: [],
                     .span(attributes: [.id(self.commentid)], .text(self.comment ?? " "))
                )
            )
        ])
        
    }
}

Please note, it is also capable of outputting HTML for use in a javascript "accordion" fashion. The images were hardcoded here, but I guess a more elegant way can be found. The various ids are used for the javascript functions to find the relevant sections for editing.

Also, a list of Todos can be exported to markdown:

extension Array where Element == Todo {
    var toMarkdown : String {
        var result = ""
        for t in self {
            result += "#### "+t.title+"\n\n"
            result += (t.comment ?? "") + "\n\n"
            result += "Status: " + t.status.rawValue + "\n\n"
        }
        
        return result
    }
}

Now, storing in the session (I use KituraSessionRedis) is as simple as:

// let session = request.session
session?["todos"] = t
session?.save(callback: { (err) in
  if let err = err { print("Error saving session: \(err.localizedDescription)") }
})

Unfortunately, restoring Todos from a session won't work: Kitura has no idea how to do that, but it can restore a [[String:Codable]] back to me, which allows me to use the DictionaryCoding stuff I did a while ago.

func todosFromSession(_ s: SessionState?) -> [Todo] {
    if let t = s?["todos"] as? [Todo] { return t }
    else if let t = try? DictionaryCoding().decode([Todo].self, from: s?["todos"]) { return t }
    let t = [
        Todo(id: UUID(), title: "Test 1", comment: "Go!", status: .pending),
        Todo(id: UUID(), title: "Test nb 2", comment: nil, status: .done),
        Todo(id: UUID(), title: "Test • 3 🤷‍♂️", comment: "UTF-8 is hard, no?", status: .delayed),
    ]
    saveTodos(t, to: s)
    return t
}

The Javascript

Aaaaaaaaaaah weeeeeeeell. OK, my thoughts on JS are fairly well known. I don't like that language, for a lot of reasons I won't get into. But it's the only way to manipulate the DOM without reloading the page so...

  • jQuery (because I will do Ajax calls, and well... it works)
  • x-editable (yes I know it's old, but it works), jQueryUI edition
  • A touch of bootstrap, because I thought I'd have to layout stuff. Turns out I don't but it's still in.

X-editable uses a combination of fields in its POST routes for in-place editing, and it works pretty in a pretty straightforward manner:

router.post("/change") { request, response, next in
    if let b = request.body, let c = b.asURLEncoded {
        var notes = todosFromSession(request.session)
        switch c["name"] {
        case "title":
            if let pk = c["pk"], let pkid = UUID(uuidString: pk), let noteidx = notes.firstIndex(where: { $0.id == pkid } ) {
                var note = notes[noteidx]
                note.title = c["value"] ?? ""
                notes[noteidx] = note
            }
        case "comment":
            if let pk = c["pk"], let pkid = UUID(uuidString: pk), let noteidx = notes.firstIndex(where: { $0.id == pkid } ) {
                var note = notes[noteidx]
                note.comment = c["value"] ?? ""
                notes[noteidx] = note
            }
        case "status":
            if let pk = c["pk"], let pkid = UUID(uuidString: pk), let noteidx = notes.firstIndex(where: { $0.id == pkid } ) {
                var note = notes[noteidx]
                note.status = TodoStatus(rawValue: c["value"] ?? "") ?? .delayed
                notes[noteidx] = note
            }
        default:
            response.send(json: ["success": false])
            next()
            return
        }
        
        saveTodos(notes, to: request.session)
        response.send(json: ["success": true])
    } else {
        response.send(json: ["success": false])
    }
    next()
}

Note the value passing mechanisms in arrays: the whole struct has to be replaced (as opposed to a class) when editing them, hence the whole firstIndex business.

The whole HTML/JS stuff is pretty ugly to show, so I'll spare you the sight. I need 3 main functions on top of all the in-place edition:

  • clear (because sometimes we need to erase everything)
  • download (because we want the markdown version)
  • next (removes the tasks that are done, passes the ones that are delayed to pending)
router.post("/clear") { request, response, next in
    saveTodos([], to: request.session)
    response.send(json: ["success": true])
    next()
}
router.get("/download") { request, response, next in
    let notes = todosFromSession(request.session)
    
    let output = "### Notes (\(df.string(from: Date())))\n\n" + notes.toMarkdown
    
    if let d = output.data(using: .utf8) {
        response.headers.setType("application/octet-stream")
        response.headers.addAttachment(for: "CR.md")
        response.send(data: d)
    }
    
    next()
}
router.post("/next") { request, response, next in
    var todos = todosFromSession(request.session).filter { $0.status != .done }.map {
        return Todo(id: $0.id, title: $0.title, comment: $0.comment, status: .pending)
    }
    saveTodos(todos, to: request.session)
    response.send(json: ["success": true])
}

Docker

I wanted to make it easy to deploy, and test my Docker/docker-compose knowledge. It also allows me to make sure my code is 100% Linux-friendly.

I have done something that could be considered a sin. I have included redis inside the same container as my app. Why? because I wanted a single image, it's that simple. Plus others do it so I figured it wasn't such a big deal. I still feel I'm gonna get yelled at for that.

So, one image, based on the official Swift 5 image, plus redis, ready to go.

And docker-compose to start in in a friendly-ish way rather than build the image, create a new container for that image and expose the relevant ports.

That way everyone has a choice.

So, here it is: https://github.com/krugazor/FrickinTodos

3D Ray-Tracing

used to do 3D. A lot. I have a few leftovers from that era of my  life, and I am still knowledgeable enough to follow along the cool stuff  that's coming out of the race between GPU manufacturers (when they  aren't competing over who mines cryptocurrencies the best 🙄).

It's  always been super hard for me to explain how ray-tracing works, because  it's a very visual thing and it seemed like it required a good deal of  spatial awareness from the people I was trying to explain it to. But it  was probably because I suck at explaining how ray-tracing works without  showing it.

So, I was super happy to find a video that explains it all better than I always have. Enjoy, then download blender and have fun rendering stuff.