6 ms·

Jq Internals: Backtracking (2017)

124 points by mshockwave 4y ago

brad0 4y ago
Does anyone know of a visual representation of backtracking? Either video or images, I'm not fussed.
- zwkrt 4y ago
  This blog post has a nice visualization of sudoku solving using backtracking. https://medium.com/analytics-vidhya/sudoku-backtracking-algorithm-and-visualization-75adec8e860c https://medium.com/analytics-vidhya/sudoku-backtracking-algo... Although the case they use is almost perversely simple. Imagine in a 'real' sudoku that each number might need to be backtracked multiple times, such that the algorithm is regularly going almost back to the start. Edit: here's a classic one trying to solve the 8 queens problem: https://commons.wikimedia.org/wiki/File:Eight-queens-animation.gif https://commons.wikimedia.org/wiki/File:Eight-queens-animati...
  - brad0 4y ago
    Thanks! I really liked this tree from the blog, it made it quite clear. https://miro.medium.com/max/786/1*Q-DyKa25eozOeMdN5YQONA.png https://miro.medium.com/max/786/1*Q-DyKa25eozOeMdN5YQONA.png
- lalwanivikas 4y ago
  Marty Stepp from Stanford had the best videos on this but they took it down from YouTube ¯\_(ツ)_/¯
- djbusby 4y ago
  There is a comic at the bottom of this post https://alopatindev.github.io/2018/01/14/how-to-take-notes-like-a-programmer/ https://alopatindev.github.io/2018/01/14/how-to-take-notes-l... Image: https://alopatindev.github.io/pictures/how-to-take-notes-like-a-programmer/programmer-interrupted.png https://alopatindev.github.io/pictures/how-to-take-notes-lik...
- dkjaudyeqooe 4y ago
  Don't have one to hand, but it's basically walking a tree depth first, where sibling nodes are the choice points.
- roncesvalles 4y ago
  Backtracking is a stone's throw from the mathematical concept of permutations so it might be better to look up visualizations of that and work from there. This one seems good: https://pebreo.github.io/combinations-visualization/ https://pebreo.github.io/combinations-visualization/ The number of permutations of n items is n!, because at every position you can place one item from all the items that haven't already been placed. Backtracking basically recursively produces all n! solutions (where every recursion depth is one position) similar to DFS brute force enumeration with the only difference that it also continuously evaluates partial solutions and short-circuits if it detects a partial solution that is guaranteed to make any complete solution containing it invalid. E.g. if you want to enumerate the permutations of 4 people standing in a row, there are 4!=24 ways to do it. However, if you add the condition that Alice can't stand next to Bob, you can short-circuit the enumeration early as soon as you detect that Alice and Bob have been placed together (such as Alice-Bob-?-?) You could also have more complex scenarios where every position has its own disjoint set of items to choose from. What you do with the enumeration is up to you. Maybe you just want to enumerate and display all possible permutations. Maybe you just want to produce the best or k best as determined by some fitness function.
mi_lk 4y ago
anyone knows why the last release is 4 years ago? the tool is so popular that this kind of release cadence seems weird https://github.com/stedolan/jq/releases/tag/jq-1.6 https://github.com/stedolan/jq/releases/tag/jq-1.6
- gavinsyancey 4y ago
  It works, and does what it is supposed to. Why does it need a new version?
  - AirStreamer27 4y ago
    To compete with the newer, blazingly fast tools
    - brad0 4y ago
      What are the competitors in the jq space?
      - llimllib 4y ago
        At least jaq[1] gojq[2], and jp[3] (this last of which is jmespath rather than the jq query language) [1]: https://github.com/01mf02/jaq https://github.com/01mf02/jaq [2]: https://github.com/itchyny/gojq https://github.com/itchyny/gojq [3]: https://github.com/jmespath/jp https://github.com/jmespath/jp
        mdaniel 4y ago
        I especially love gojq thanks to this change: $ echo '{"alpha":"beta"}' | jq -r '"hello $.alpha$"' jq: error: syntax error, unexpected INVALID_CHARACTER (Unix shell quoting issues?) at <top-level>, line 1: "hello $.alpha$" jq: 1 compile error $ echo '{"alpha":"beta"}' | gojq -r '"hello $.alpha$"' gojq: invalid query: "hello $.alpha$" "hello $.alpha$" ^ unexpected token "\\" because (a) muscle memory (b) sure, it's easy to spot that mistake in an 18 character expression, but for bigger ones, getouttahere
agumonkey 4y ago
Quite impressive sophistication level for such a 'small' utility. Very inspiring read :)
guelo 4y ago
For a tool I only use very occasionally I find jq's syntax to be too unique with too steep of a learning curve. Every time I reach for it I have to spend a bunch of time reading the manual trying to think like it does. I wish there was something for querying json that had more of a xpath or even a sql-like syntax, or GraphQL with the addition of wildcards.
- bachmeier 4y ago
  dsq works for me: https://github.com/multiprocessio/dsq https://github.com/multiprocessio/dsq
  - mdaniel 4y ago
    > dsq registers go-sqlite3-stdlib so you get access to numerous statistics, url, math, string, and regexp functions that aren't part of the SQLite base. (https://github.com/multiprocessio/dsq#standard-library https://github.com/multiprocessio/dsq#standard-library) Ah, I wondered if they rolled their own SQL parser, but no, I now see the sqlite.go in the repo and all is made clear
  - youngtaff 4y ago
    There’s some limitations in dsq which means it doesn’t query sub objects that have varying fields - they just remain as JSON strings
- pcthrowaway 4y ago
  The trick is to use it daily. The learning curve isn't worse than vim
  - tux2bsd 4y ago
    To use it daily you need a reason, or have the time & will to practice it.
    - pcthrowaway 4y ago
      Fair. I guess I think anyone using jq occasionally could probably be using it daily as well. Dealing with JSON data is pretty much standard for anyone developing or consuming a rest API
ducktective 4y ago
I wish jq had a spec.
- mdaniel 4y ago
  I hear you, but OTOH in this thread are two alternative implementations, one which seems especially focused on "bolt tightening" some of the edge cases: https://github.com/01mf02/jaq#assignments https://github.com/01mf02/jaq#assignments Isn't the adage to only build a framework after the 3rd or 4th implementation? That seems to apply to writing a RFC, also
pkrumins 4y ago
w jq

124 points by mshockwave 4y ago

brad0 4y ago

Does anyone know of a visual representation of backtracking? Either video or images, I'm not fussed.

zwkrt 4y ago
This blog post has a nice visualization of sudoku solving using backtracking. https://medium.com/analytics-vidhya/sudoku-backtracking-algorithm-and-visualization-75adec8e860c https://medium.com/analytics-vidhya/sudoku-backtracking-algo... Although the case they use is almost perversely simple. Imagine in a 'real' sudoku that each number might need to be backtracked multiple times, such that the algorithm is regularly going almost back to the start. Edit: here's a classic one trying to solve the 8 queens problem: https://commons.wikimedia.org/wiki/File:Eight-queens-animation.gif https://commons.wikimedia.org/wiki/File:Eight-queens-animati...
- brad0 4y ago
  Thanks! I really liked this tree from the blog, it made it quite clear. https://miro.medium.com/max/786/1*Q-DyKa25eozOeMdN5YQONA.png https://miro.medium.com/max/786/1*Q-DyKa25eozOeMdN5YQONA.png
lalwanivikas 4y ago
Marty Stepp from Stanford had the best videos on this but they took it down from YouTube ¯\_(ツ)_/¯
djbusby 4y ago
There is a comic at the bottom of this post https://alopatindev.github.io/2018/01/14/how-to-take-notes-like-a-programmer/ https://alopatindev.github.io/2018/01/14/how-to-take-notes-l... Image: https://alopatindev.github.io/pictures/how-to-take-notes-like-a-programmer/programmer-interrupted.png https://alopatindev.github.io/pictures/how-to-take-notes-lik...
dkjaudyeqooe 4y ago
Don't have one to hand, but it's basically walking a tree depth first, where sibling nodes are the choice points.
roncesvalles 4y ago
Backtracking is a stone's throw from the mathematical concept of permutations so it might be better to look up visualizations of that and work from there. This one seems good: https://pebreo.github.io/combinations-visualization/ https://pebreo.github.io/combinations-visualization/ The number of permutations of n items is n!, because at every position you can place one item from all the items that haven't already been placed. Backtracking basically recursively produces all n! solutions (where every recursion depth is one position) similar to DFS brute force enumeration with the only difference that it also continuously evaluates partial solutions and short-circuits if it detects a partial solution that is guaranteed to make any complete solution containing it invalid. E.g. if you want to enumerate the permutations of 4 people standing in a row, there are 4!=24 ways to do it. However, if you add the condition that Alice can't stand next to Bob, you can short-circuit the enumeration early as soon as you detect that Alice and Bob have been placed together (such as Alice-Bob-?-?) You could also have more complex scenarios where every position has its own disjoint set of items to choose from. What you do with the enumeration is up to you. Maybe you just want to enumerate and display all possible permutations. Maybe you just want to produce the best or k best as determined by some fitness function.

mi_lk 4y ago

anyone knows why the last release is 4 years ago? the tool is so popular that this kind of release cadence seems weird https://github.com/stedolan/jq/releases/tag/jq-1.6 https://github.com/stedolan/jq/releases/tag/jq-1.6

gavinsyancey 4y ago
It works, and does what it is supposed to. Why does it need a new version?
- AirStreamer27 4y ago
  To compete with the newer, blazingly fast tools
  - brad0 4y ago
    What are the competitors in the jq space?
    - llimllib 4y ago
      At least jaq[1] gojq[2], and jp[3] (this last of which is jmespath rather than the jq query language) [1]: https://github.com/01mf02/jaq https://github.com/01mf02/jaq [2]: https://github.com/itchyny/gojq https://github.com/itchyny/gojq [3]: https://github.com/jmespath/jp https://github.com/jmespath/jp
      - mdaniel 4y ago
        I especially love gojq thanks to this change: $ echo '{"alpha":"beta"}' | jq -r '"hello $.alpha$"' jq: error: syntax error, unexpected INVALID_CHARACTER (Unix shell quoting issues?) at <top-level>, line 1: "hello $.alpha$" jq: 1 compile error $ echo '{"alpha":"beta"}' | gojq -r '"hello $.alpha$"' gojq: invalid query: "hello $.alpha$" "hello $.alpha$" ^ unexpected token "\\" because (a) muscle memory (b) sure, it's easy to spot that mistake in an 18 character expression, but for bigger ones, getouttahere

agumonkey 4y ago

Quite impressive sophistication level for such a 'small' utility. Very inspiring read :)

guelo 4y ago

For a tool I only use very occasionally I find jq's syntax to be too unique with too steep of a learning curve. Every time I reach for it I have to spend a bunch of time reading the manual trying to think like it does. I wish there was something for querying json that had more of a xpath or even a sql-like syntax, or GraphQL with the addition of wildcards.

bachmeier 4y ago
dsq works for me: https://github.com/multiprocessio/dsq https://github.com/multiprocessio/dsq
- mdaniel 4y ago
  > dsq registers go-sqlite3-stdlib so you get access to numerous statistics, url, math, string, and regexp functions that aren't part of the SQLite base. (https://github.com/multiprocessio/dsq#standard-library https://github.com/multiprocessio/dsq#standard-library) Ah, I wondered if they rolled their own SQL parser, but no, I now see the sqlite.go in the repo and all is made clear
- youngtaff 4y ago
  There’s some limitations in dsq which means it doesn’t query sub objects that have varying fields - they just remain as JSON strings
pcthrowaway 4y ago
The trick is to use it daily. The learning curve isn't worse than vim
- tux2bsd 4y ago
  To use it daily you need a reason, or have the time & will to practice it.
  - pcthrowaway 4y ago
    Fair. I guess I think anyone using jq occasionally could probably be using it daily as well. Dealing with JSON data is pretty much standard for anyone developing or consuming a rest API

ducktective 4y ago

I wish jq had a spec.

mdaniel 4y ago
I hear you, but OTOH in this thread are two alternative implementations, one which seems especially focused on "bolt tightening" some of the edge cases: https://github.com/01mf02/jaq#assignments https://github.com/01mf02/jaq#assignments Isn't the adage to only build a framework after the 3rd or 4th implementation? That seems to apply to writing a RFC, also

pkrumins 4y ago

w jq