Problem Idea Logic Gates Simulation
Back to General discussions forum
Input to program could be number of inputs, number of outputs, number of logic gates, and a circuit built up of logic gates... where the circuit does not have a loop, then finally test inputs to that circuit
Sample Input for one circuit test case might look like...
4 1 3
0 AND 1
2 AND 3
4 AND 5
0 0 0 0
0 0 0 1
0 0 1 0
...
1 1 1 1
Expected output for this circuit would be: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
4 -> Number of inputs, 1 -> Number of outputs, 3 -> number of logic gates. Logic gates in input would be referred by a numerical id. If there are I inputs to the circuit, then the id's 0 to I-1 would be reserved for the inputs. The next lines specify what inputs logic gate I takes in and what type of gate it is, then logic gate I+1, then logic gate I+2, etc.
That sounds cool! I remember thinking of something like this perhaps since years when I only studied programming, with Pascal.
There is one obstacle I see we need to think about, but on that later...
Even no need in limitation circuit does not have a loop. Loops are all right if we have clock input. Moreover this
allows creating rather whimsical schematics - flip-flops, counters, adders, you know...
Thus the task is something like "implement logic interpreter". It can be extended, by the way, as the outputs of some expressions could be not the immediate outputs, but internal values, used in next level expressions:
0 AND 1 => Y1
2 AND 3 => Y2
4 AND 5 => T1
Y1 OR T1 => Y3
here Y... means the value of output while T... the internal value.
And "opposite" task we can have - to propose circuit for given set of inputs/outputs. E.g. like converting 4-bit input to seven-segment code. Though probably there could be found some ready generators...
Moreover to make things more fancy we can switch to some kind of ternary logic - need to research a bit about possible implementations :)
As about the difficulty I mentioned - it's just about generating some interesting examples for input - e.g. without trivial and redundand parts etc. Though possibly this can be achieved by randomly generating several examples and checking which is the "most beautiful" according to outputs.
I'll try to think about this - but if you have some ideas (or even would like to participate) - please share!
Ooh, your formulation of the problem is certainly more elegant. Better syntax on the input and the clock input is a good idea as well. If we're using Y for output, T for internal, I think we could also use I for input.
For generating interesting examples for inputs to the circuit generation problem... no idea :P
For the "opposite" task of proposing circuits some ideas could be
A circuit which fetches or updates addressable memory
Apply some encryption algorithm which uses simple operations (e.g. bitwise operations, maybe addition)
Simulate a DFA
Evaluate a SPECIFIC n degree polynomial (say, 1 <= n <= 8) for some integer x (say, 0 <= x <= 30) ... this is something I've thought of before and I've got a nice solution for it which doesn't require multiplication.
Decode assembly instructions and send output signals that would be suitable for something like sending further instruction to the ALU or Registers or such
Page Tables
A circuit which takes in some pattern and sends out that pattern in a repeated fashion over time
- e.g. the pattern could be 11001010, so at some starting time t it sends 1, then at t+1 it sends 1, at t+2 it sends 0, t+3 -> 0, t+4 -> 1, t+5 -> 0, t+6 -> 1, t+7-> 0, and then it loops.
A circuit which tracks a 2D position and receives signals telling it to go N,W,S or E and reports its position
Floating point number implementation that uses a small amount of bits for the exponent and mantissa.
From this video: https://youtu.be/5TFDG-y-EHs?t=510 I've heard that it's seemingly legal within the floating point specification to have a floating point number with 3 bits (1 for the sign, 1 for the exponent, 1 for the mantissa).
Though maybe we want more than that so we have a few more numbers than -inf, -1, -0, 0, 1, inf, and NAN :P
Not that we have to strictly abide by any spec, and can just define our own nonstandard floating point numbers.
I'm also imagining a "challenge problem" (one of those ones where there best solution is not necessarily obvious and you get more points for more optimal solution)... input is some complex circuit, output is supposed to be a simpler or faster version of the same circuit. Maybe some obvious inefficiencies can be baked in so there are some guaranteed improvements you can make, or you could start from a simpler circuit, and make it more complex by replacing some subsets of the logic gates to have the same truth table, but using more logic gates.
Fun fact btw, there is at least two simple algorithms to turn any truth table into a circuit (key terms: Conjunctive Normal Form, Disjunctive Normal Form). But of course the size of a truth table scales exponentially with the number of inputs, and the circuit produced is very likely not optimal... mainly just guarantees that a circuit is always possible given you fully know all possible inputs combinations and the corresponding outputs.
Vadim, Hi!
At last I'm returning to this thread - and with somewhat positive news - the first task (combining your initial idea and one of your latest hints) - was just published :) Thank you!
Your further considerations got me puzzled at some points (the moment I feel lack of proper education in this part) but overall brought me to some follow-up thought:
We can have some logic circuit description language interpreter (oh that chain of genitive cases!) and problems which require to build various circuits in it. I feel it should be simpler than AHDL / VHDL so people can understand it in few minutes, but strong enough to allow easily build firstly various flip-flops, then shift registers, counters, summators etc. E.g. it could be a set of problems similar to "turing-machine" or "assembly" paths.
Though not sure how much people would like it. For me it seems fun, but it is due to my second main hobby is electronics. For others it could be quite dull (as also some other ideas I consider funny, ha-ha).
Need to think better on how such interpreter may look like, though :)
And probably we need some in-browser visualizer for this (and for TM too)...
Floating point number implementation that uses a small amount of bits for the exponent and mantissa
Yeah, as confessed, some things you share make jaw-dropping effect on me :) Always thought it is something exorbitantly complicated!
Good morning Rodion, many thanks for the new problem.
There is a small correction necessary in the given example, it uses a, b, d, e instead of a, b, c, d.
Mathias, Hi! Happy Sunday!
Wow, thanks - I was alarmed first thinking there is some bug in generator - but it happened I'm just lost one
rule (for e) while copying. Now should be better!
As usually I'm somewhat impressed by your speed. Just went and checked - notification was sent at 6:40 UTC and your
solution came in a hour (less)... Given it is weekend and one perhaps won't rush immediately to computer... I really
wonder whether you train at competitive programming intentionally :)
Pure coincidence. I had some work to do (before family gets up), but this looked much more fun and I couldn't resist. And given the discussion above, we kind of knew already what to expect.
Btw: notification was sent - are email notifications supposed to work? I am definitely signed up (just checked: You're already subscribed to this newsletter.) but have never received any email. Is that working for anybody?
are email notifications supposed to work
supposed, correct word... I remember Quandray told it works for him, but when added my own email - I don't remember
receiving anything (but thought it's my mail provider fault). Thanks for reporting on this, shall investigate further...
You most probably checked spam/trash folders and no need to ask about this, right :) Just to confirm - I'll write to this "tinyletter" support then.
BTW if anyone aware of some other way to easily create similar "subscription" flow - please advice. Probably google groups would work (?) though only for gmail users, right?
I noticed the comments about e-mail notifications. I signed up for these some time ago but have never had a single notification. However, this is hardly a problem as I make a point of checking the site at least once a week. So I will always be able to spot new problems and other information.
I found this latest problem very interesting. Thanks Vadim and Rodion. It is always nice to come across new ideas and FDNF is certainly (for me at least) one of those. At first glance the problem looked very complicated but on reading through the really clear and detailed problem description I was surprised at how simple it actually was. The most likely point of confusion would probably have been the implication rule, but this was fully described in the problem description so there was no need to look anything up. For anyone reading this there is a clear moral here. Don't be tempted to write off a problem before reading thoroughly through the description (possibly several times) and giving it some careful thought. Things are often a lot simpler than they seem at first glance!
The problems on this site have introduced me to a wide variety of fascinating new ideas. Almost all of them have been a great deal of fun and I look forward to many more in the future. I think the only significant exception (for me personally) has been SQL. I have never used SQL in the past and will never need to use it in future (except for the inevitable problems coming up on this site). The SQL problems on the site seemed to be very easy (and probably are for those of you who are frequent users of SQL). I could solve each of them very easily in a language like Python and assumed that moving to SQL would be like trying another new language. As I rarely use any advanced features of a language and avoid libraries (prefering to solve things for myself) I tend to use just the main inbuilt features of a language and these are very similar in most languages. After checking for the language syntax requirements the rest is easy. Unfortunately I didn't have this experience with SQL. Solving the problems turned into an online hunt for functions and structures which I was certain would be present in the language. I was soon beset with problems stemming from the different versions of SQL that are around. In some cases I gave up trying to implement what seemed to be the obvious algorithm and started changing the algorithm in various ways in an attempt to find something that would be accepted. I am quite ashamed of some of the algorithms that I ended up with but it was so frustrating trying to find code that would actually work. I am sure that the SQL specialists out there will have breezed through these problems in several minutes each and will be quite amused at my feeble attempts. I am sure that SQL must be easy to use when you know what you are doing and that many of you will be hoping to see more of these SQL problems. Everyone has their areas of expertise and I accept that SQL is definitely not one of mine. I will "look forward" to future SQL problems as a special kind of challenge!
I am pleased to hear you guys found the problem interesting :D
Rodion wrote everything about the problem himself, I only suggested ideas about it (all laid out in this thread), and wasn't expecting the CNF/DNF fun-fact to become the key component of the problem.
Regarding SQL... your experience with it certainly echoes my own, I struggled a fair bit with the SQL problems and my experience with other languages for the most part did not carry over to help me with SQL. That being said... my understanding is that there is actually a lot of theory behind database stuff, a colleague of mine took a course on Databases and said that some of the theoretical stuff is like, relation algebra and calculus, boyy codd normal form, the 5 operations you build upon being unions, intersections, cartesian products, projection, and difference I think... all with proper mathematical rigor behind it. I think that there's got to be some insights to draw from SQL, so personally I haven't given up on it.
Friends, thanks a lot for all response!
To Vadim - you see, problems come in different way - sometimes an idea, or heap of ideas give quite a kick-start and
implementing the rest seems comparatively easy. Though not rarely it happens that it's difficult to realize immediately
what to do with the pure idea :) I'm quite thankful for all the various ways of help with problems!
To Clive - about SQL I feel roughly the same (and by Vadim's comment it seems common feeling). Despite I worked in
number of projects using it - and this site uses big deal of it to store data - I always feel uneasy when need to
add or modify some query (besides simplest). These problems mainly appeared here because I'm asked something about
SQL at every job interview, e.g. roughly every year. But I don't think we shall add more of them, as powers of SQL
come with significant amounts of data, indices on table columns etc - something not easily fit for exercises on the site.
Let those few be introductory material for people targeting career in IT :)
I could solve each of them very easily in a language like Python
This made me think it would be suitable to add some small explanatory article like "why sql" and link to first of problems :)
Though really there exist tendency even in industrial projects to replace complicated database queries with some in-language loops / filtering etc (though generally it is bad idea). So you (and we all) are not alone in this adverse feeling towards SQL!
Seems like I have to provide a counterview then: I have written thousands and thousands of lines of code in SQL (particularly in the Oracle version of SQL and its procedural extension PL/SQL) and really like it. It is powerful and performant if you work a lot with data.
And there are crazy people out there who use SQL to solve “normal” programming puzzles, just google “advent of code with sql” :).
Oh, that's great - so we have DBA among us :) Then I guess if ever here'll come another SQL-related task, it should be from you :)
and its procedural extension PL/SQL
Some people consider this one of most controversial approach nowadays - on one hand it allows to write imperative logic closer to database and thus potentially much faster - on the other it generaly isn't easily scalable, makes db engine change close to impossible... and requires people to become SQL-programmers, which many prefer to avoid :)
Very good arguments against the use of PL/SQL, and I agree with all of them. But I am no database admin, far from it. I don't generally write production-level code. Demonstrators and proof-of-concepts are my main focus, and for that speed and convenience are often important. Horses for courses. Plus I actually like SQL somehow. :)