mironimous's recent activity
-
Comment on <deleted topic> in ~comp
-
Comment on <deleted topic> in ~comp
mironimous Link ParentWhat I wanted to showcase are the places where C expressions - despite being clearly inspired by classical mathematical notation - deviates from it. Like you say, an experienced C programmer...What I wanted to showcase are the places where C expressions - despite being clearly inspired by classical mathematical notation - deviates from it. Like you say, an experienced C programmer normally would be able to see what the expression means (and in most cases except ioccc wouldn't write it), but a beginner might not, because they see that C expressions are mostly like conventional math notation and will assume and it will compile. Additionally, on a code review it might not get caught because it looks just right.
And I still sometimes get caught by bitwise operators having a lower precedence than comparison operators, plus it causes paren-pain when doing a lot of bitwise operations.
Also, I really just like this expression because it's confusing. -
Comment on <deleted topic> in ~comp
mironimous (edited )LinkAnother joy of C syntax are expressions: 1,010^2 == 10 Well, obviously one thousand and ten squared is not equal to ten, so this evaluates to 0? Wait, 1,010 is not the literal 1010, that's just a...Another joy of C syntax are expressions:
1,010^2 == 10Well, obviously one thousand and ten squared is not equal to ten, so this evaluates to 0?
Wait,1,010is not the literal 1010, that's just a comma expression, which means the part before the comma gets ignored (after being evaluated) and the second part is the value!
We can reduce this expression to010^2 == 10Well, 10 squared is 100 and not 10, so this is still 0.
Wait,010is an octal literal, since it begins with a zero, so the actual value is eight!
Ugh, so we have this8^2 == 10`Well, that still is 0, since 8 squared is 64 and not 10, right?
Wait,
^is not power, but xor, so we don't have 64, but8^2= 10.
This is the same as the rhs of the ==, so this should evaluate to 1.
So we are finally d-
Wait,==has a higher operator precedence than^, so we actually have to evaluate2 == 10first (which is 0) and then xor that with 8!
Ok, so after evaluating2 == 10, we have left8 ^ 0which is just 8.
While this example is a bit contrived, it is very short and I think this very beatifully showcases C's syntax.
-
Comment on Programming Challenge - Find path from city A to city B with least traffic controls inbetween. in ~comp
mironimous Link ParentHere I go: x z x Basically, sed has two buffers, the main pattern buffer and a hold buffer. The pattern buffer is cleared each new cycle, but the hold buffer not, so I exchange those, clear the...- Exemplary
Here I go:
x z xBasically, sed has two buffers, the main pattern buffer and a hold buffer.
The pattern buffer is cleared each new cycle, but the hold buffer not, so I exchange those, clear the buffer and exchange them again.:x s/$/%;%90123456789/ :y s/(.)%((%?.)*\1)|;.*/\3\2/ tyThis puts a % at the end and decrements any decimal number with a % after it - sed doesn't have any concept of numbers, so I have to do it manually.
For example, 5531% gets turned into 5530 and 30% would get turned into 3%9, which gets turned into 29.
Since the first line is the number of cities, we get the name of the last city./\n/bz s/^0*// N :z /\n0+$/!{ x N x bx }sed doesn't have any more control flow than "branch to label", "branch to label if previous substitution successful" and running a code of block if a pattern matches.
But I would like to reuse the decrement routine for the second line to repeat getting a line as long as it isn't zero.So we look if we have a newline in the buffer (
/\n/bzbranches to :z if we do see a newline) - if we don't, we know we are still on the first line, so we remove the zeros in front of the first number to normalize it (s/^0*//) and get a newline (N).
In any case, we have now a second number in our buffer, so we check if it is zero, and if not we get a new line into our hold buffer (x;N;x;) and decrement the second number (bx- branching to:x).s/(.*)\n.*/,\1;/ x s/^\n// s/(\n|$)/%&/g s/(^|\n)/:/gThis prepares everything for the actual algorithmic phase.
First, we don't need the second number anymore, so we remove it and format the first number so it is of the form,n;- it is needed later.Then we switch to the other buffer with the edges, which now becomes our main buffer.
We remove the newline at the very beginning, which we don't need, and put a % after every number of traffic controls.
Finally, we change every record to be of the form:id1 id2 weight, which removes the need for newlines that are annoying to handle.Our pattern space now looks like
:0 1 3%:0 2 2%:1 2 1%:1 3 4%:2 3 5%:a /[0-9]%/{ s/ %/ 0%/g s/^/0@1@2@3@4@5@6@7@8@9@#/ :b s/([0-9])@([^#]*#.*)(:[^:]*)\1%([^:]*)/\1@\3%\1\4\2/ tb s/.@|#//g ba }This is a sorting routine that sorts every record beginning with : that has a % behind a number.
Again, sed doesn't understand numbers, so we have to implement the sorting ourselves.
Comparison is pretty hard in sed, but pattern matching is easy, so we use radix sort.
Each loop, it moves each of the records with a n% (with n being a single digit) to the corresponing n@ at the beginning and moves the % one to the left and pad 0 as needed.
We are finished if there are no % signs with numbers in front of it left.In the context of the control flow, we have now sorted the edges in ascending order of traffic controls.
s/%0*([0-9])/\1/g /;/be s/^/:0 0:,0;/We remove the leftover % signs and remove the superfluous 0s in front of the numbers we just sorted (
s/%0*([0-9])/\1/g).
If we find a;, we jump to:e- we do not have a;in pattern space right now, but it is needed later, as we also use the sorting routine for finding the minimum of two numbers.
Finally, we put:0 0:,0;at the beginning.
The:0 0is the value for getting from 0 to 0 (first of the tuple) - 0 (second of the tuple).Next, we use prim's algorithm to use the minimum spanning tree for finding the minimum.
The,0;is a list of the vertices included in our spanning tree - right now, only 0.:d s/(,([0-9]*);.*:)(_?[0-9]* )?\2 ([^:]*)/\1_\2 \3\4/ td /\n/bf s/:_[0-9]* _[^:]*//gThis marks all edges that contain the number immediately in front of the semicolon (0 for the first run) with a
_in front of the id and - if it is the second id of the pair - swaps the ids.
If there's a newline, we branch to:f(we use it again later for finding the record with the last city).
If there is a edge with two marks, we all ready have both vertices in our tree so we delete it.s/(^[^;]*)(;[^_]*)(:_[0-9]* ([0-9]*)[^:]*)/\3\1,\4\2/ s/^:_([0-9]*) ([^:,]*)([^;]*)(:\1 [0-9]*)/:_\2%\4%\3/ ba :eThe first line searches for the first edge with a record that is marked - so the one with the lowest weight that already has a vertex in the spanning tree (this is how Prim's algorithm works)
It also moves the edge to the front and adds the unmarked vertex to the end of the vertex list so that edges containing it are marked next.The second line takes the edge of the form
:_n m wand turns it into:_m w%:n v%, where we get the v from the list of getting from 0 to n that we have at the front (remember the:0 0record).We then jump to
:ato sort those and continue at:e./^:_/s/^(:_[0-9]* )[^:]*(:[0-9]* ([0-9]*))/\1\3\2/ s/:_(.*;)/:\1/ s/%//g tcIf the marked record is at the front, we know that the edge going from n to m has a lower weight than getting from 0 to n, so going from 0 to m has the same weight as going from 0 to n, so we substitute in that case
:_m w%to:_m v%.
We then unmark it and remove the percents and, if any of the substitutions have been successful, we repeat everything from:c.s/_|,.*//g x G bd :f s/.*:_[^ ] ([0-9]*).*/\1/ tg s/.*// :gThis is the end to output the record containing the last city.
First, we remove everything after the first comma - so the vertices and leftover edges.
We then get the last city name from the hold buffer and search for it using the marking substitution (remember that we formatted it to,n;)
If it is not present, we output nothing, else we output the weight for it. -
Comment on Programming Challenge - Find path from city A to city B with least traffic controls inbetween. in ~comp
mironimous LinkOh, a graph problem. You know the perfect language for that? Right, sed. x z x :x s/$/%;%90123456789/ :y s/(.)%((%?.)*\1)|;.*/\3\2/ ty /\n/bz s/^0*// N :z /\n0+$/!{ x N x bx } s/(.*)\n.*/,\1;/ x...Oh, a graph problem.
You know the perfect language for that?
Right, sed.x z x :x s/$/%;%90123456789/ :y s/(.)%((%?.)*\1)|;.*/\3\2/ ty /\n/bz s/^0*// N :z /\n0+$/!{ x N x bx } s/(.*)\n.*/,\1;/ x s/^\n// s/(\n|$)/%&/g s/(^|\n)/:/g :a /[0-9]%/{ s/ %/ 0%/g s/^/0@1@2@3@4@5@6@7@8@9@#/ :b s/([0-9])@([^#]*#.*)(:[^:]*)\1%([^:]*)/\1@\3%\1\4\2/ tb s/.@|#//g ba } s/%0*([0-9])/\1/g /;/be s/^/:0 0:,0;/ :c :d s/(,([0-9]*);.*:)(_?[0-9]* )?\2 ([^:]*)/\1_\2 \3\4/ td /\n/bf s/:_[0-9]* _[^:]*//g s/(^[^;]*)(;[^_]*)(:_[0-9]* ([0-9]*)[^:]*)/\3\1,\4\2/ s/^:_([0-9]*) ([^:,]*)([^;]*)(:\1 [0-9]*)/:_\2%\4%\3/ ba :e /^:_/s/^(:_[0-9]* )[^:]*(:[0-9]* ([0-9]*))/\1\3\2/ s/:_(.*;)/:\1/ s/%//g tc s/_|,.*//g x G bd :f s/.*:_[^ ] ([0-9]*).*/\1/ tg s/.*// :gDoes not fullfill any of the boni.
If anyone has interest in an explanation I can give one (but tomorrow).
-
Comment on Cheapest way to put a hard drive on the internet. in ~comp
mironimous LinkI am regularily sleeping at two different locations, so I have one hdd setup for both locations using Raspberry Pis. You can use usb HDDs on a raspberry pi without problems if they have their own...I am regularily sleeping at two different locations, so I have one hdd setup for both locations using Raspberry Pis.
You can use usb HDDs on a raspberry pi without problems if they have their own power supplies.
One can normally also set their spin-down time or manually spin them down usinghdparm, the range of supported drives is quite wide and from my experience seems to support most usb drives.I also use
openvpnto connect the two locations andunisonto sync them at 4 am so that I can usually just backup really fast to the local drive and it gets synced to the respective other location, but this doesn't seem really useful in this case, since you probably only want to transfer the backups from your main site to your offsite andrsyncis enough for that.If you don't want to open ports at your friend's router but you're okay with opening ports at your own place, I would suggest running an openvpn client offsite to connect to your main site openvpn server.
Of course, any SoC with usb is okay, but of course it is preferable to have native ethernet and SATA connectors instead of relying on usb peripherals.
-
Comment on Programming Challenge - It's raining! in ~comp
mironimous (edited )LinkI made a function in python which takes a list of the capacities of the lakes, from left to right, and returns the number to fill (in linear time I think) #!/usr/bin/python3 def rain(lakes): # the...I made a function in python which takes a list of the capacities of the lakes, from left to right, and returns the number to fill (in linear time I think)
#!/usr/bin/python3 def rain(lakes): # the time it takes to fill the system of previous lakes filltime = 0 # the amount of overflow from the previous lakes in [filltime] spill = 0 for (i,capacity) in enumerate(lakes): # number of previous lakes including current one num = i + 1 # we have the spill from the previous lakes and for each second in filltime # one additional liter level = spill + filltime if level > capacity: # since we were already full, the filltime stays the same # but the spill is now the amount we are over the capacity spill = level - capacity else: # the spill is now zero, since we are still collecting in this lake spill = 0 # but the time to fill up is larger # at each second after [filltime], we get [num] liters of water # so the remaining time is just the remaining capacity divided by [num] filltime += (capacity - level)/num return filltimeThe way this works is by first calculating the time to fill the first (n-1) lakes and the amount of water that spilled over into the last lake in that time.
The previous lakes are all full after that time, so from that point on there are n liters of water flowing into the last lake each hour.- If it has already overflowed in that time, we can just add the number of hours to the overspill (since each hour, one liter is added) and substract the capacity of the current lake from it to get the new overspill
- If it has not overflowed, the remaining time to fill it is simply the remaining capacity in the lake divided by n
I have not really tested the code for errors, so it probably has some errors.
-
Comment on Programming Challenge: Merge an arbitrary number of arrays in sorted order. in ~comp
mironimous (edited )LinkHere is my sed solution: :a s/[^0-9,]//g s/(,|$)+/%,/g :b s/$/@0@1@2@3@4@5@6@7@8@9@/ :c s/^([0-9]*)([0-9])%([0-9]*,)(.*@\2[^@]*)@/\4\1%\2\3@/ tc s/@(.|$)//g /(^|,)[^%]/{s/(,|^)%/\10%/g; bb}...Here is my sed solution:
:a s/[^0-9,]//g s/(,|$)+/%,/g :b s/$/@0@1@2@3@4@5@6@7@8@9@/ :c s/^([0-9]*)([0-9])%([0-9]*,)(.*@\2[^@]*)@/\4\1%\2\3@/ tc s/@(.|$)//g /(^|,)[^%]/{s/(,|^)%/\10%/g; bb} s/%0*([^,])|,$/\1/g s/^,// N s/\n/,/ baInputs are comma separated lists of numbers, each newline the currently sorted list is outputted, so if you want the whole list, pipe it into
tail -n1.Internally it uses radix sort (
@0@1@2@3@4@5@6@7@8@9@are the marks for the buckets and it adds padding zeros in front of the numbers as needed and removes them at the end).Edit: Edited it so now it only outputs the list at EOF.
-
Comment on What are your unsolved programming problems? in ~comp
mironimous (edited )LinkSo I guess this is more a math problem than a programming problem, but it occured to me while programming and is about brute force and stuff, so I guess it's close enough. So you know maximum...So I guess this is more a math problem than a programming problem, but it occured to me while programming and is about brute force and stuff, so I guess it's close enough.
So you know maximum length sequences? Basically, you have a repeating sequence of 0s and 1s (I am just looking at the case F_2 which basically just means modulo 2, it trivially extends to other fields) where each subsequence of length n (except all 0s) appears exactly once in one period, which obviously means that the period length is 2^n-1. It turns out you can easily calculate such a sequence by finding a irreducible polynomial of degree n over F_2 (so it's necessary that the polynomial has no zero mod 2 anywhere) and use the coefficients for a recurrence relation (a_n = b_{n-1}a_{n-1} + ... + b_0 a_0 with b_k being the coefficient of x^k).
I've had the need of such a thing but over 2 dimensions, meaning you have a n*m tile where every x*y subrectangle appears exactly once. For example, here is a 4*4 tile where every 2*2 subrectangle appears exactly once (note that a subrectangle at the edge behaves like in pacman, extending to the other side):
+--+--+--+--+ | |##| | | +--+--+--+--+ |##|##|##| | +--+--+--+--+ | |##|##|##| +--+--+--+--+ | | |##| | +--+--+--+--+The problem is that the tile becomes very big very quickly (if you're doing a 4*4 subrectangle, you're already dealing with a 256*256 tile, which has 65536 bits and is basically impossible to brute force).
I've basically ruled out anything that linearly depends on only the x*y subrectangle (so recurrence relations and matrices) and now I'm trying to do something with the fact that every (x-k)*y subrectangle defines a k*y -> k*y permutation with no success so far.
Maybe someone knows just a word I have to google to find this out
-
Comment on Making C less dangerous in ~comp
mironimous Link ParentSurprising indeed. I've seen once tried to use an experimental llvm z80 backend (which threw errors on half of my code), but I didn't know there was an avr backend in the official llvm tree....Surprising indeed.
I've seen once tried to use an experimental llvm z80 backend (which threw errors on half of my code), but I didn't know there was an avr backend in the official llvm tree. That's probably because my only avr experience amounts to getting a loudspeaker to play some square tones on an arduino.
I will also look into the rust 8051 assemblers, I'm normally using the good old asem-51. -
Comment on Making C less dangerous in ~comp
mironimous Link ParentOne of the great points of C is that it is widely available on many architecture - if the ISA exists, there is a great chance someone wrote a C compiler for it, and that's partly why Linux is...One of the great points of C is that it is widely available on many architecture - if the ISA exists, there is a great chance someone wrote a C compiler for it, and that's partly why Linux is written in C (looking at the wikipedia page, it supports at least 30 architectures).
A further problem is that llvm, which is used by quite a lot of safer languages, is not really a good fit for 8-bit microcontrollers like 8051, 6502 or z80 and no one would be willing to write a rust compiler specifically for 8051.
Of course it is a good idea to use safer languages for systems that have hundreds of MBs, but there are at least 2 8051s inside my mouse alone and my e-piano runs on an SH-2a (and it has wlan functionality, so security is definitely an issue), so it doesn't seem like we will be able to stop using C soon. -
Comment on Programming Mini-Challenge: TicTacToeBot in ~comp
mironimous Link ParentIf you want to see the dark magic, you'll obviously have to turn on the light theme.If you want to see the dark magic, you'll obviously have to turn on the light theme.
-
Comment on Programming Mini-Challenge: TicTacToeBot in ~comp
mironimous (edited )LinkI guess I am a little late, but here is yet another C solution: #define a(x) int x=0;for(;*n[1];n[1]++)x=4*x|*n[1]==*#x;x*=0x41040404440015;x&=x*2&0xa80080080020820;...I guess I am a little late, but here is yet another C solution:
#define a(x) int x=0;for(;*n[1];n[1]++)x=4*x|*n[1]==*#x;x*=0x41040404440015;x&=x*2&0xa80080080020820; main(z,n)char**n;{a(O)a(X)return O?79:X?88:35;}This basically converts the field to a base 4 number and then does some magic with some constants, for O and then for X, and returns the solution as the return value of the program. The string is given as the first argument to the program.
Figuring out how these constants work is left as an exercise for the reader.
Edit: also, here is a naive implementation in gnu sed -r:
s/.*(O|X)..\1..\1.*|^(...)*(O|X)\3\3.*|(O|X)...\4...\4|..(O|X).\5.\5../\1\3\4\5/;s/..+/#/Edit 2: Because this challenge is fun, here is another solution using GNU APL:
↑'OX#'/⍨1,⍨'OX'{∨/(16<2⊥⌽5⍴x∧⊖⌽x),∧/(⍉x)⍪x←3 3⍴⍺=⍵}¨⊂⍞ -
Comment on Wendelstein 7-X stellarator achieves fusion product world record in ~science
mironimous Link ParentI don't think this will happen with the Wendelstein 7-X. The reactor itself is just too small to have a positive energy yield, there is not enough volume in comparison to the surface. Even if you...I don't think this will happen with the Wendelstein 7-X.
The reactor itself is just too small to have a positive energy yield, there is not enough volume in comparison to the surface.
Even if you ignore that, the existing design seems too complicated to just add a system to harvest energy and you can't really use the cooling systems since they have to be cold enough to maintain the superconductivity of the coils (or the water cooling of the lasers, where the heat comes mostly from your own electricity, so that doesn't work either).This is mostly a prototype to see if the stellarator design is feasible and effective and I think it's a very nice and innovative project if you view it from that angle.
I am not a physicist though, so I may have said some wrong things.
-
Comment on ~Random acts of Steam Sale in ~games
mironimous Link ParentSpaceChem seems nice; I have never actually played anything by Zachtronics, but he seems to make some very nice games. If you still have it, I'll take that.SpaceChem seems nice; I have never actually played anything by Zachtronics, but he seems to make some very nice games. If you still have it, I'll take that.
-
Comment on Programming Challenge: Given a triangle of numbers, find the path from the top to the bottom of the triangle with the largest sum. in ~comp
mironimous (edited )LinkHere's my GNU APL solution: {⍺+2⌈/⍵}/{⍵,⊂⎕}⍣⎕ ⍬ The part {⍵,⊂⎕}⍣⎕ ⍬ gets the input: We start with an empty value (⍬) The ⍣ in this case applies the function before it ({⍵,⊂⎕}) as often as the...Here's my GNU APL solution:
{⍺+2⌈/⍵}/{⍵,⊂⎕}⍣⎕ ⍬The part
{⍵,⊂⎕}⍣⎕ ⍬gets the input:- We start with an empty value (
⍬) - The ⍣ in this case applies the function before it (
{⍵,⊂⎕}) as often as the number behind it (⎕, which is a number inputted by the user and the first line) to the result of the previous iteration and starts with the empty value - The function
{⍵,⊂⎕}gets a new line from input, encloses it (so it is a single array element even if it is an array itself) and appends it to the existing array we are iterating on
The part
{⍺+2⌈/⍵}/computes the sum:- Now we have an array which contains the arrays of the triangle in ascending order, where we apply the reduce operator (
/), which evaluates by essentially putting the function before it ({⍺+2⌈/⍵}) between every element in the target array (the indiviual triangle rows) and applies them from right to left in usual apl fashion (from the longest triangle row to the smallest one) - The function
{⍺+2⌈/⍵}takes the maximum per two neighboring elements from the right array (2⌈/⍵, which is just the reduce operator per 2 elements with the maximum function⌈) and adds them element-wise to the array on the left
- We start with an empty value (
Speaking of
char str[6] = "Hello";, did you know thatchar str[5] = "Hello";is legal C according to the standard and will allocate the string "Hello" without zero-terminator? (I always find obscure language features fascinating and can't help but to bring them into my own projects to the dismay of others)