Right. This morning we’ll start doing some actual code about shunting. My rough plan, which I’m about to make up right now is:
I have no particular commitment to finishing these. My style is to do small things that lead in what I think is the direction of the solution I’m after. If sometimes they don’t turn out to be useful, I’m willing to drop the code and keep the learning. In particular, by the time I’ve done something on #2, it’s likely that I’ll see a different #3, or a #2.36 that should come before it.
And, of course, if #2 were to actually fail, I’d need a new idea. But I am sure that #2 will be fine. Let’s log into Aditi and start a script.
I scarf an old testing thing and paste it in as a starter. I think I’d like to save this script as a general starter:
-- inglenook 0.1
-- JR 2025-05-08 09:18 ff
function state_entry()
run_tests()
end
local test_correct
local test_wrong
function assert_equals(result, expected)
local correct = result == expected
if correct then
test_correct += 1
else
test_wrong += 1
print(`{result} == {expected} {correct}`)
end
end
function assert_nearly_equal(result, expected, delta)
correct = ll.Fabs(result-expected) <= delta
if correct then
test_correct += 1
else
test_wrong += 1
print(`{result} nearly_equal {expected} {correct}`)
end
end
function run_tests()
test_correct = 0
test_wrong = 0
assert_equals(2+2, 4)
assert_nearly_equal(2 + 2 + 0.01, 4, 0.1)
print(`Tests: correct {test_correct}, wrong {test_wrong}`)
end
function touch_start(total_number)
run_tests()
end
-- Simulate the state_entry event
state_entry()
That’ll do for now. Let’s see, what now? Let’s make a table that knows how to help us determine inversions and do swaps.
Pretty quickly, I have these tests passing:
local S = { data={4, 3, 1, 2}}
--
assert_equals(S:inversion_at(1, 2), true)
assert_equals(S:inversion_at(3, 4), false)
Our table S (for shunt) has an element data containing 4, 3, 1, 2. So there is an inversion between 1 and 2, since 4 is larger than 3, and there is no inversion at 3,4, since 1 is less than two. And, apparently the table S understands a function inversion_at that takes two indices and answers whether the values at those positions are inverted, that is, the first is larger than the second.
Here’s the code for inversion_at:
function S:inversion_at(i, j)
return self.data[i] > self.data[j]
end
I hope the return part is nearly clear: we answer whether the data value at i is greater than the value at j. For those who are new to functions in tables, we need to talk about the S: in the function definition, and the self in the code.
When we define a function whose name is prefixed by a table name, that function will be put into the named table, with a key equal to the function name. So function S:inversion_at puts a key “inversion_at” into S, and the value at that key is the function we define. Not the function result: the actual function.
When we define a function that way, the word self takes on a special meaning: it means the value of the table we provide when we call the function, also with a colon, as in S:inversion_at(1,2). When we make that call, self is S and so data is the value of data in S.
Now in this case, we could have just said S.data and it would all be good, but we’re working toward a class of Shunt objects that we can use over and over.
Anyway, we can check for inversions. Let’s do a swap function. Here’s my test:
S.data = {4, 3, 1, 2}
assert_equals(S:inversion_at(1, 2), true)
S:swap(1, 2)
assert_equals(S:inversion_at(1, 2), false)
assert_equals(S.data, {3, 4, 1, 2})
Seems simple enough. I’m setting up the data because I’m starting to modify the data in the S object and I want to start being careful that one test doesn’t break the setup for another. I think I can do swap like this:
function S:swap(i, j)
self.data[i], self.data[j] = self.data[j], self.data[i]
end
I expect my tests to run, but in fact I get this output:
[06:51] Inglenook 0.1: table: 0x000000001e435a94 == table: 0x000000001e435a6c false
[06:51] Inglenook 0.1: Tests: correct 4, wrong 1
My test for equality of the tables failed. Why? Because, as we can clearly see, Lua compares the objects by identity not content. Meh. There are some fancy ways to deal with that, and maybe we’ll dig into the ol’ trick bag later, but for now, I think I’ll just test the elements. I’m really sure everything is just fine but I feel it’s best to have at least one actual test for the final result.
Let’s do it with a function on S, just for practice. Change the test:
assert_equals(S:match({3, 4, 1, 2}), true)
And create match:
function S:match(values)
for i, d in self.data do
if d ~= values[i] then
return false
end
end
return true
end
My tests all pass.
Now let’s use our inversion checking and swapping ability to fix up a mixed-up shunt. A new test:
S.data = {5, 4, 3, 2, 1}
S:arrange()
assert_equals(S:match({1, 2, 3, 4, 5}), true)
Easy to say, perhaps not easy to implement, but I think I know how to do it. My plan is to iterate across the shunt looking for inversions. If we find one, we’ll swap it and start over. When we find none, we’ll return. Here goes:
function S:arrange()
local needs_arranging = true
while needs_arranging do
needs_arranging = false
for i = 1, #self.data - 1 do
if self:inversion_at(i, i+1) then
self:swap(i, i+1)
needs_arranging = true
end
end
end
end
My tests all pass! I am not completely surprised:I’ve been thinking about this a lot. But I want to see it work, so I’m going to add a print just for fun and a bit more reassurance.
function S:arrange()
local needs_arranging = true
while needs_arranging do
needs_arranging = false
for i = 1, #self.data - 1 do
if self:inversion_at(i, i+1) then
self:swap(i, i+1)
needs_arranging = true
self:print()
end
end
end
end
function S:print()
local out = ''
for i, v in self.data do
out = out .. `{v} `
end
print(out)
end
And I get this output:
[07:19] Inglenook 0.1: 4 5 3 2 1
[07:19] Inglenook 0.1: 4 3 5 2 1
[07:19] Inglenook 0.1: 4 3 2 5 1
[07:19] Inglenook 0.1: 4 3 2 1 5
[07:19] Inglenook 0.1: 3 4 2 1 5
[07:19] Inglenook 0.1: 3 2 4 1 5
[07:19] Inglenook 0.1: 3 2 1 4 5
[07:19] Inglenook 0.1: 2 3 1 4 5
[07:19] Inglenook 0.1: 2 1 3 4 5
[07:19] Inglenook 0.1: 1 2 3 4 5
[07:19] Inglenook 0.1: Tests: correct 6, wrong 0
Super! Interesting how it ripples the 5 up to where it belongs, then the 4, then 3, then 2. That’s some standard sort algorithm whose name I forget. Famously slow, I might add, but we’re not in a rush here are we?
I’ll comment out the call to print and save.
Now then, I think we have more than enough words here, so we should finish up. I think the main thing I’d like to address is the testing, which looks like this right now:
function run_tests()
test_correct = 0
test_wrong = 0
assert_equals(S:inversion_at(1, 2), true)
assert_equals(S:inversion_at(3, 4), false)
S.data = {4, 3, 1, 2}
assert_equals(S:inversion_at(1, 2), true)
S:swap(1, 2)
assert_equals(S:inversion_at(1, 2), false)
assert_equals(S:match({3, 4, 1, 2}), true)
S.data = {5, 4, 3, 2, 1}
S:arrange()
assert_equals(S:match({1, 2, 3, 4, 5}), true)
print(`Tests: correct {test_correct}, wrong {test_wrong}`)
end
Each of those blocks represents one conceptual test, the one for inversions, the one for swap, and the final one for arrange. I’d like to define each of those tests in a function of its own. One way would be just to do that and then call the function from inside run_tests, but you know I’d forget to add them and I’d assume everything was Just Fine when in fact it was Really Terrible. So let’s make a test table and add them to that. This will just take a bit of changing:
A table Tests:
Tests = {}
Into which we put our tests:
function Tests:test_inversions()
S.data = {4, 3, 1, 2}
assert_equals(S:inversion_at(1, 2), true)
assert_equals(S:inversion_at(3, 4), false)
end
function Tests:test_swap()
S.data = {4, 3, 1, 2}
assert_equals(S:inversion_at(1, 2), true)
S:swap(1, 2)
assert_equals(S:inversion_at(1, 2), false)
assert_equals(S:match({3, 4, 1, 2}), true)
end
function Tests:test_arrange()
S.data = {5, 4, 3, 2, 1}
S:arrange()
assert_equals(S:match({1, 2, 3, 4, 5}), true)
end
And we change run_tests to do this:
function run_tests(verbose)
test_correct = 0
test_wrong = 0
for k, v in pairs(Tests) do
if string.sub(k, 1, 5) == 'test_' then
if verbose then print(k) end
v(Tests)
end
end
print(`Tests: correct {test_correct}, wrong {test_wrong}`)
end
In run_tests we go through the table Tests and look for keys that start with “test_”. When we find one, we call the value at that key, namely the function associated with that key by our test function definitions.
Now every time we add a new test it will get picked up and run.
The order of test running, by the way, is unpredictable, as it depends on how Lua produces the keys in the do, and that’s random. Not random on every run, probably, but random as we add or remove or rename tests.
I’ve droned on too long here, let’s sum up.
We have a table S that understands how to check for inversions and swap elements, and uses those two notions to arrange the elements of the table in numeric order. And we have a tiny testing framework in Tests, a couple of assert methods, and a method run_tests to run them. We should quite likely at least put the run_tests function inside the Tests table. Maybe next time, we’re still evolving here.
What has all this accomplished? Well, for me, both those bits of progress are important and valuable. The improvements to testing will pay off, I’m sure, because I’ve never regretted testing and often regretted not testing, so making it easier to test things means that I’m more likely to do what works best for me: test everything.
And the S table? It’s giving me assurance that if we check inversions on our would-be train, and if we can devise a way to swap elements, which I am sure we can, then a loop looking for inversions to fix, and fixing them, will result in a train in the order we want. Will we use the S table in the real program, whatever that is? Quite possibly not. Will we use the way it behaves again? Almost certainly yes.
So here at the end of the session, I’m happy because I have better testing capability and more confidence in my basic idea of shunting so as to swap cars that are in the wrong order.
One more tiny note. You might wonder why I chose to say, for example, swap(i, j) instead of just swap(i) and imply the i+1 inside the function. That’s because I have an inkling that there might be times when we could easily swap two cars that are not adjacent, so I wanted my functions to handle the case. You should also note that I did not test that capability. Should I? I don’t know. I’m confident that the code works, but if someone wanted to test additional cases it would be fine with me. And who knows, I might lose a bit of confidence and if I do, I’ll add tests.
That’s how I do that. I hope you found it interesting. For me, it’s solid progress. Progress because it feels like moving toward swapping rail cars. Solid because everything is tested and shown to work. Good enough for now!
Safe paths until we meet again!
A bit of reading and I realize that this is better:
function run_tests(verbose)
-- ...
for k, v in pairs(Tests) do
if k:sub(1, 5) == 'test_' then
-- ...
end
end
end
Rather than this:
function run_tests(verbose)
-- ...
for k, v in pairs(Tests) do
if string.sub(k, 1, 5) == 'test_' then
-- ...
end
end
end
Since k is a string, the string methods work on it just fine.
Safe paths!