title: Dependency Graph Visualization

text:
# Question
Title: Dependency Graph Visualization
The goal of this challenge is to write a **program** that visualizes a dependency graph in the form of a tree. While "dependency graph" in this context means nothing more than a directed graph, the visualization method described here works best for graphs describing some dependency relation (as an exercise, after you've read the challenge, try to reverse the direction of one of the sample graphs, and see if the result is as useful.)

The **input** to the program consists of one or more **target definitions**, which are lines of the form

```
Target DirectDependency1 DirectDependency2 ...

```

, defining a **target**, and its associated **direct dependencies**, if any. Targets and their dependencies are collectively called **objects**. If an object appears only as a dependency, and not as a target, it has no dependencies. The set of all objects that appear in the input is called **Γ**. (See the Input and Output section for more details about the input format.)

For any pair of objects, *A* and *B*, we say that:

* ***A* depends on *B*** (equivalently, ***B* is required by *A***), if *A* directly depends on *B*, or if *A* directly depends on *B'*, and *B'* depends on *B*, for some object *B'*;
* ***A* properly depends on *B*** (equivalently, ***B* is properly required by *A***), if *A* depends on *B*, and *B* does not depend on *A*.

We define a contrived object, **ʀooᴛ**, not in Γ, such that ʀooᴛ is not directly required by any object, and such that, for all objects *A*, ʀooᴛ directly depends on *A* if and only if *A* is in Γ, and *A* is not properly required by any object in Γ (in other words, ʀooᴛ directly depends on *A* if no other object depends on *A*, or if all objects that depend on *A* are also required by *A*.)

**Output Tree**

We construct a **tree**, whose root node is ʀooᴛ, and such that the children of each node are its direct dependencies. For example, given the input

```
Bread Dough Yeast
Dough Flour Water
Butter Milk

```

, the resulting tree is

, or, in ASCII form,

```
ʀooᴛ
+-Bread
| +-Dough
| | +-Flour
| | +-Water
| +-Yeast
+-Butter
  +-Milk

```

. The program's **output** is the above-defined tree, printed *without* the ʀooᴛ node. So, for example, the corresponding output for the above input is

```
Bread
+-Dough
| +-Flour
| +-Water
+-Yeast
Butter
+-Milk

```

. A detailed description of the layout of the output tree is given later.

**Node Order**

The child nodes of a given parent node, *P*, should be **sorted**, such that, for all child nodes *A* and *B* of *P*, *A* appears before *B* if and only if

* there exists a child node *C* of *P*, such that *A* is properly required by *C*, and *C* precedes, or equals to, *B*, according to the same order; **or**,
* *A* alphabetically precedes *B* (more preceisely, *A* precedes *B* using ASCII collation,) **and** there exists **no** child node *C* of *P*, such that *B* is properly required by *C*, and *C* precedes, or equals to, *A*, according to the same order.

(People looking for a mathematical challenge might want to show that this relation is well defined, and that it's, in fact, a strict total order. Don't forget that Γ is finite!)

For example, given the input

```
X D C B A
B D
C A

```

, the output should be

```
X
+-A
+-D
+-B
| +-D
+-C
  +-A

```

. `A` appears before `B`, and `B` appears before `C`, due to their alphabetical order; `D` appears before `B`, since it is properly required by it, and after `A`, since it alphabetically follows it; `B` and `C` do not appear before `D`, even though they precede it alphabetically, since there exists a node, namely, `B`, that properly requires `D`, and that equals to `B` (i.e., itself), and preceeds `C`, according to the same rules.

**Repetitions**

The same object, *A*, may appear more than once in the output, if, for example, it is required by more than one object. If *A* has no dependencies of its own, no special handling is required in this case. Otherwise, in order to minimize the verbosity of the output, and to avoid infinite recursion due to circular dependencies, the dependencies of *A* are listed only on its **first occurrence** for which none of the ancestors are siblings of another *A* node; any other occurrence of *A* should have no children, and should appear followed by a space and an ellipsis, as in *`A`*`...`.

For example, given the input

```
IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

```

, the output should be

```
WebRTC
+-TCP
| +-IP
|   +-Ethernet
+-UDP
  +-IP ...

```

. As another example, featuring both circular dependency and ancestry considerations,

```
Rock Scissors
Paper Rock
Scissors Paper

```

, should result in

```
Paper
+-Rock ...
Rock
+-Scissors ...
Scissors
+-Paper ...

```

. Note that, for example, the first occurrence of `Rock` does not list its dependencies, since its parent, `Paper`, is a sibling of another `Rock` node. The parent of the second `Rock` node, ʀooᴛ (which doesn't appear in the output), doesn't have `Rock` as a sibling, so the dependencies of `Rock` are listed on this node.

**Output Tree Layout**

I'm sure you got the hang of how the tree should be represented as ASCII art (and feel free to skip this section if you have,) but for the sake of completeness...

The child nodes of ʀooᴛ are printed on separate lines, without any indentation, in order. Each node is immediately followed by its children, if any, printed in the same fashion, recursively, indented by two characters to the right. For each node that has children, a vertical line, consisting of `|` (pipe) characters, extends down from the character directly below the first character of the node, until the row of its last child node, not including the last child node's children. If the indentation of a node is nonzero, it is preceded by `+-` (on the same indentation level as its parent), overwriting the vertical line described above.

## Input and Output

You may read the input through **STDIN**, or using an **equivalent method**. You may assume that there are **no empty lines**, and you may require that the last line ends, or doesn't end, in a newline character. You may assume that object names consists of **printable ASCII characters** (not including space). You may assume that objects in a target definition are **separated by a single space** character, and that there are **no leading or trailing spaces**. You may assume that each target is **defined at most once**, and that there are **no repetitions** in its dependency list.

You may write the output to **STDOUT**, or use an **equivalent method**. All output lines, except for the longest, may include trailing spaces. The last output line may, or may not, end in a newline character.

## Score

This is **code-golf**. The **shortest answer**, in bytes, wins.

## Test Cases

Your program should process each of the following test cases in a reasonable amount of time.

---

*Input*

```
Depender Dependee
Independent

```

*Output*

```
Depender
+-Dependee
Independent

```

---

*Input*

```
Earth Turtle
Turtle Turtle

```

*Output*

```
Earth
+-Turtle
  +-Turtle ...

```

---

*Input*

```
F A C B D I
A B
B A C
D E H
C
G F
J H G C E I
E D
H D
I G

```

*Output*

```
J
+-C
+-E
| +-D
|   +-E ...
|   +-H ...
+-H
| +-D ...
+-G
| +-F
|   +-C
|   +-A
|   | +-B ...
|   +-B
|   | +-C
|   | +-A ...
|   +-D ...
|   +-I ...
+-I
  +-G ...

```

---

**Civilization V Technology Tree**

*Input*

```
Pottery Agriculture
AnimalHusbandry Agriculture
Archery Agriculture
Mining Agriculture
Sailing Pottery
Calendar Pottery
Writing Pottery
Trapping AnimalHusbandry
TheWheel AnimalHusbandry
Masonry Mining
BronzeWorking Mining
Optics Sailing
Philosophy Writing
HorsebackRiding TheWheel
Mathematics TheWheel Archery
Construction Masonry
IronWorking BronzeWorking
Theology Calendar Philosophy
CivilService Philosophy Trapping
Currency Mathematics
Engineering Mathematics Construction
MetalCasting Construction IronWorking
Compass Optics
Education Theology CivilService
Chivalry CivilService HorsebackRiding Currency
Machinery Engineering
Physics Engineering MetalCasting
Steel MetalCasting
Astronomy Compass Education
Acoustics Education Chivalry
Banking Chivalry
PrintingPress Machinery Phyisics
Gunpowder Physics Steel
Navigation Astronomy
Economics Banking PrintingPress
Chemistry Gunpowder
Metallurgy Gunpowder
Archaeology Navigation
ScientificTheory Navigation Acoustics Economics
MilitaryScience Economics Chemistry
Fertilizer Chemistry
Rifling Metallurgy
Biology Archaeology ScientificTheory
SteamPower ScientificTheory MilitaryScience
Dynamite MilitaryScience Fertilizer Rifling
Electricity Biology SteamPower
ReplaceableParts SteamPower
Railroad SteamPower Dynamite
Refrigeration Electricity
Telegraph Electricity
Radio Electricity
Flight ReplaceableParts
Combustion ReplaceableParts Railroad
Penicillin Refrigeration
Plastics Refrigeration
Electronics Telegraph
MassMedia Radio
Radar Radio Flight Combustion
AtomicTheory Combustion
Ecology Penicillin Plastics
Computers Electronics MassMedia Radar
Rocketry Radar
Lasers Radar
NuclearFission AtomicTheory
Globalization Ecology Computers
Robotics Computers
Satellites Rocketry
Stealth Lasers
AdvancedBallistics Lasers NuclearFission
ParticlePhysics Robotics Satellites
NuclearFusion Satellites Stealth AdvancedBallistics
Nanotechnology ParticlePhysics
FutureTech Globalization Nanotechnology NuclearFusion
```

*Output*

```
FutureTech
+-Globalization
| +-Computers
| | +-Electronics
| | | +-Telegraph
| | |   +-Electricity
| | |     +-Biology
| | |     | +-Archaeology
| | |     | | +-Navigation
| | |     | |   +-Astronomy
| | |     | |     +-Compass
| | |     | |     | +-Optics
| | |     | |     |   +-Sailing
| | |     | |     |     +-Pottery
| | |     | |     |       +-Agriculture
| | |     | |     +-Education
| | |     | |       +-CivilService
| | |     | |       | +-Philosophy
| | |     | |       | | +-Writing
| | |     | |       | |   +-Pottery ...
| | |     | |       | +-Trapping
| | |     | |       |   +-AnimalHusbandry
| | |     | |       |     +-Agriculture
| | |     | |       +-Theology
| | |     | |         +-Calendar
| | |     | |         | +-Pottery ...
| | |     | |         +-Philosophy ...
| | |     | +-ScientificTheory
| | |     |   +-Acoustics
| | |     |   | +-Chivalry
| | |     |   | | +-CivilService ...
| | |     |   | | +-Currency
| | |     |   | | | +-Mathematics
| | |     |   | | |   +-Archery
| | |     |   | | |   | +-Agriculture
| | |     |   | | |   +-TheWheel
| | |     |   | | |     +-AnimalHusbandry ...
| | |     |   | | +-HorsebackRiding
| | |     |   | |   +-TheWheel ...
| | |     |   | +-Education ...
| | |     |   +-Economics
| | |     |   | +-Banking
| | |     |   | | +-Chivalry ...
| | |     |   | +-PrintingPress
| | |     |   |   +-Machinery
| | |     |   |   | +-Engineering
| | |     |   |   |   +-Construction
| | |     |   |   |   | +-Masonry
| | |     |   |   |   |   +-Mining
| | |     |   |   |   |     +-Agriculture
| | |     |   |   |   +-Mathematics ...
| | |     |   |   +-Phyisics
| | |     |   +-Navigation ...
| | |     +-SteamPower
| | |       +-MilitaryScience
| | |       | +-Chemistry
| | |       | | +-Gunpowder
| | |       | |   +-Physics
| | |       | |   | +-Engineering ...
| | |       | |   | +-MetalCasting
| | |       | |   |   +-Construction ...
| | |       | |   |   +-IronWorking
| | |       | |   |     +-BronzeWorking
| | |       | |   |       +-Mining ...
| | |       | |   +-Steel
| | |       | |     +-MetalCasting ...
| | |       | +-Economics ...
| | |       +-ScientificTheory ...
| | +-MassMedia
| | | +-Radio
| | |   +-Electricity ...
| | +-Radar
| |   +-Combustion
| |   | +-Railroad
| |   | | +-Dynamite
| |   | | | +-Fertilizer
| |   | | | | +-Chemistry ...
| |   | | | +-MilitaryScience ...
| |   | | | +-Rifling
| |   | | |   +-Metallurgy
| |   | | |     +-Gunpowder ...
| |   | | +-SteamPower ...
| |   | +-ReplaceableParts
| |   |   +-SteamPower ...
| |   +-Flight
| |   | +-ReplaceableParts ...
| |   +-Radio ...
| +-Ecology
|   +-Penicillin
|   | +-Refrigeration
|   |   +-Electricity ...
|   +-Plastics
|     +-Refrigeration ...
+-Nanotechnology
| +-ParticlePhysics
|   +-Robotics
|   | +-Computers ...
|   +-Satellites
|     +-Rocketry
|       +-Radar ...
+-NuclearFusion
  +-AdvancedBallistics
  | +-Lasers
  | | +-Radar ...
  | +-NuclearFission
  |   +-AtomicTheory
  |     +-Combustion ...
  +-Satellites ...
  +-Stealth
    +-Lasers ...
```

---

**Cygwin syslog-ng Package Dependency Graph**

*Input*

```
p11-kit-trust cygwin libtasn1_6
libtasn1_6 cygwin
libp11-kit0 cygwin libffi6 libintl8
libopenssl100 cygwin libgcc1 zlib0 ca-certificates
gsettings-desktop-schemas libglib2.0_0
p11-kit cygwin libp11-kit0 libtasn1_6
zlib0 libgcc1
libpcre1 cygwin
libfam0 gamin
shared-mime-info cygwin libglib2.0_0 libxml2
coreutils cygwin libattr1 libgcc1 libgmp10 libiconv2 libintl8 tzcode _update-info-dir
syslog-ng bash gawk libevtlog0 libgcc1 libglib2.0_0 libopenssl100 libpcre1 libwrap0 tzcode
libxml2 libiconv2 libreadline7 zlib0
cygwin base-cygwin
ca-certificates bash p11-kit p11-kit-trust cygwin
libintl8 cygwin libiconv2
libncursesw10 cygwin libgcc1 libstdc++6 terminfo
libstdc++6 libgcc1
bash coreutils cygwin libgcc1 libiconv2 libintl8 libncursesw10 libreadline7 _update-info-dir
libmpfr4 libgcc1 libgmp10
tzcode bash cygwin libgcc1
_update-info-dir cygwin
libreadline7 libncursesw10
gawk bash cygwin libgcc1 libgmp10 libintl8 libmpfr4 libreadline7
gamin libglib2.0_0
libglib2.0_0 libfam0 libffi6 libgcc1 libiconv2 libintl8 libpcre1 zlib0 gsettings-desktop-schemas shared-mime-info tzcode
```

*Output*

```
syslog-ng
+-libgcc1
+-bash
| +-cygwin
| | +-base-cygwin
| +-_update-info-dir
| | +-cygwin ...
| +-libgcc1
| +-libiconv2
| +-libintl8
| | +-cygwin ...
| | +-libiconv2
| +-libncursesw10
| | +-cygwin ...
| | +-libgcc1
| | +-libstdc++6
| | | +-libgcc1
| | +-terminfo
| +-libreadline7
| | +-libncursesw10 ...
| +-coreutils
|   +-cygwin ...
|   +-_update-info-dir ...
|   +-libattr1
|   +-libgcc1
|   +-libgmp10
|   +-libiconv2
|   +-libintl8 ...
|   +-tzcode ...
+-tzcode
| +-cygwin ...
| +-libgcc1
| +-bash ...
+-gawk
| +-cygwin ...
| +-libgcc1
| +-libgmp10
| +-libintl8 ...
| +-libreadline7 ...
| +-bash ...
| +-libmpfr4
|   +-libgcc1
|   +-libgmp10
+-libevtlog0
+-libpcre1
| +-cygwin ...
+-libglib2.0_0
| +-libffi6
| +-libgcc1
| +-libiconv2
| +-libintl8 ...
| +-libpcre1 ...
| +-tzcode ...
| +-zlib0
| | +-libgcc1
| +-gsettings-desktop-schemas
| | +-libglib2.0_0 ...
| +-libfam0
| | +-gamin
| |   +-libglib2.0_0 ...
| +-shared-mime-info
|   +-cygwin ...
|   +-libxml2
|   | +-libiconv2
|   | +-libreadline7 ...
|   | +-zlib0 ...
|   +-libglib2.0_0 ...
+-libopenssl100
| +-cygwin ...
| +-libgcc1
| +-ca-certificates
| | +-cygwin ...
| | +-bash ...
| | +-p11-kit
| | | +-cygwin ...
| | | +-libp11-kit0
| | | | +-cygwin ...
| | | | +-libffi6
| | | | +-libintl8 ...
| | | +-libtasn1_6
| | |   +-cygwin ...
| | +-p11-kit-trust
| |   +-cygwin ...
| |   +-libtasn1_6 ...
| +-zlib0 ...
+-libwrap0
```

---

**GNU grep `regex.c` Call Graph**

*Input*

```
check_dst_limits_calc_pos_1 check_dst_limits_calc_pos_1
re_string_destruct
match_ctx_add_sublast
build_charclass bitset_set
match_ctx_init
rpl_re_set_syntax
link_nfa_nodes re_node_set_init_1 re_node_set_init_2
re_node_set_init_union re_node_set_init_copy
register_state re_node_set_insert_last re_node_set_alloc
rpl_re_search re_search_stub
re_node_set_init_2
re_search_2_stub re_search_stub
merge_state_array re_acquire_state re_node_set_init_union
calc_eclosure calc_eclosure_iter
create_token_tree
create_tree create_token_tree
pop_fail_stack
re_compile_fastmap_iter
rpl_regcomp rpl_re_compile_fastmap re_compile_internal
check_arrival_expand_ecl find_subexp_node check_arrival_expand_ecl_sub re_node_set_merge re_node_set_alloc
clean_state_log_if_needed extend_buffers
lower_subexps lower_subexp
duplicate_node re_dfa_add_node
re_node_set_merge
build_equiv_class bitset_set
create_initial_state re_acquire_state_context re_node_set_merge re_node_set_init_copy re_node_set_contains
rpl_regfree free_dfa_content
check_halt_state_context check_halt_node_context re_string_context_at
check_dst_limits search_cur_bkref_entry check_dst_limits_calc_pos
re_node_set_insert re_node_set_init_1
transit_state_bkref transit_state_bkref check_subexp_matching_top get_subexp re_string_context_at re_node_set_init_union re_acquire_state_context
get_subexp_sub match_ctx_add_entry clean_state_log_if_needed check_arrival
free_tree free_token
parse_reg_exp free_tree parse_branch fetch_token postorder create_tree
re_string_skip_chars
match_ctx_clean
re_copy_regs
parse_expression parse_dup_op parse_sub_exp build_charclass_op parse_expression init_word_char create_tree free_tree create_token_tree fetch_token parse_bracket_exp postorder
init_dfa
re_acquire_state_context calc_state_hash re_node_set_compare create_cd_newstate
re_node_set_add_intersect
merge_state_with_log transit_state_bkref check_subexp_matching_top re_acquire_state_context re_string_context_at re_node_set_init_union
free_fail_stack_return
check_subexp_limits sub_epsilon_src_nodes re_node_set_contains
build_charclass_op create_tree bitset_not bitset_set build_charclass create_token_tree bitset_mask free_charset
re_node_set_alloc
check_arrival_add_next_nodes check_node_accept_bytes re_acquire_state re_node_set_merge check_node_accept re_node_set_insert
check_node_accept_bytes re_string_char_size_at re_string_wchar_at re_string_elem_size_at
re_string_allocate re_string_construct_common re_string_realloc_buffers
lower_subexp create_tree
parse_branch parse_expression create_tree postorder free_tree
rpl_regexec re_search_internal
free_state
expand_bkref_cache re_node_set_init_1 re_node_set_insert search_cur_bkref_entry re_node_set_merge re_node_set_init_copy check_arrival_expand_ecl re_node_set_contains re_acquire_state
peek_token re_string_peek_byte_case re_string_wchar_at peek_token
re_string_construct build_wcs_upper_buffer re_string_construct_common build_upper_buffer re_string_translate_buffer re_string_realloc_buffers build_wcs_buffer
re_string_realloc_buffers
calc_inveclosure re_node_set_insert_last
sub_epsilon_src_nodes re_node_set_add_intersect re_node_set_contains re_node_set_remove_at
sift_ctx_init
re_string_fetch_byte_case re_string_char_size_at
find_recover_state merge_state_with_log
sift_states_iter_mb check_node_accept_bytes re_node_set_contains
group_nodes_into_DFAstates bitset_set_all bitset_copy bitset_set re_node_set_init_1 re_node_set_insert re_node_set_init_copy bitset_merge bitset_clear bitset_contain bitset_empty
push_fail_stack re_node_set_init_copy
check_node_accept bitset_contain re_string_context_at
match_ctx_free match_ctx_clean
build_wcs_upper_buffer
rpl_regerror
sift_states_backward re_node_set_init_1 update_cur_sifted_state build_sifted_states
build_sifted_states re_node_set_insert sift_states_iter_mb check_dst_limits check_node_accept re_node_set_contains
transit_state_mb check_node_accept_bytes re_acquire_state_context re_string_context_at re_node_set_init_union clean_state_log_if_needed
optimize_utf8
build_collating_symbol bitset_set
re_search_stub rpl_re_compile_fastmap re_search_internal re_copy_regs
check_matching merge_state_with_log find_recover_state re_acquire_state_context transit_state check_subexp_matching_top transit_state_bkref extend_buffers check_halt_state_context re_string_context_at
extend_buffers build_wcs_upper_buffer re_string_translate_buffer re_string_realloc_buffers build_wcs_buffer build_upper_buffer
check_arrival re_node_set_init_1 re_string_context_at expand_bkref_cache re_node_set_merge re_node_set_init_copy re_node_set_contains check_arrival_expand_ecl check_arrival_add_next_nodes re_acquire_state_context
free_workarea_compile
match_ctx_add_entry
parse_bracket_symbol re_string_fetch_byte_case
free_charset
build_trtable re_node_set_merge re_node_set_alloc group_nodes_into_DFAstates re_acquire_state_context bitset_merge bitset_contain bitset_empty
re_node_set_init_copy
duplicate_node_closure duplicate_node_closure re_node_set_insert duplicate_node search_duplicated_node
parse_bracket_exp build_equiv_class bitset_not bitset_set parse_bracket_element build_range_exp free_charset peek_token_bracket bitset_mask build_charclass create_tree build_collating_symbol create_token_tree
parse_bracket_element peek_token_bracket re_string_wchar_at parse_bracket_symbol re_string_char_size_at
re_search_internal re_string_destruct re_string_allocate match_ctx_init match_ctx_free check_matching check_halt_state_context re_string_reconstruct match_ctx_clean set_regs prune_impossible_nodes
set_regs free_fail_stack_return update_regs pop_fail_stack proceed_next_node
prune_impossible_nodes sift_ctx_init check_halt_state_context sift_states_backward merge_state_array
check_arrival_expand_ecl_sub re_node_set_insert re_node_set_contains check_arrival_expand_ecl_sub
re_acquire_state re_node_set_compare create_ci_newstate calc_state_hash
build_wcs_buffer
rpl_re_compile_pattern re_compile_internal
free_dfa_content free_token free_state
get_subexp match_ctx_add_sublast get_subexp_sub clean_state_log_if_needed extend_buffers search_cur_bkref_entry find_subexp_node check_arrival
analyze calc_first optimize_subexps postorder lower_subexps calc_eclosure preorder link_nfa_nodes calc_inveclosure calc_next
re_node_set_init_1
duplicate_tree create_token_tree
calc_eclosure_iter duplicate_node_closure calc_eclosure_iter re_node_set_alloc re_node_set_insert re_node_set_merge
bitset_empty
free_token free_charset
bitset_copy
parse_dup_op fetch_token mark_opt_subexp fetch_number create_tree postorder duplicate_tree free_tree
rpl_re_compile_fastmap re_compile_fastmap_iter
re_dfa_add_node
re_node_set_insert_last
sift_states_bkref re_node_set_remove_at sift_states_backward search_cur_bkref_entry re_node_set_insert check_dst_limits merge_state_array re_node_set_init_copy re_node_set_contains
fetch_number fetch_token
match_ctx_add_subtop
fetch_token peek_token
bitset_set_all
re_string_reconstruct build_wcs_buffer re_string_translate_buffer re_string_skip_chars bitset_contain build_upper_buffer build_wcs_upper_buffer re_string_context_at
rpl_re_match_2 re_search_2_stub
create_cd_newstate re_node_set_init_copy re_node_set_remove_at free_state register_state
check_subexp_matching_top match_ctx_add_subtop
proceed_next_node check_node_accept re_node_set_contains push_fail_stack check_node_accept_bytes re_node_set_insert
rpl_re_match re_search_stub
build_range_exp bitset_set
add_epsilon_src_nodes re_node_set_add_intersect re_node_set_merge re_acquire_state re_node_set_alloc
update_regs
rpl_re_search_2 re_search_2_stub
transit_state re_string_context_at build_trtable transit_state_mb
check_dst_limits_calc_pos check_dst_limits_calc_pos_1
build_upper_buffer
calc_first re_dfa_add_node
re_compile_internal optimize_utf8 re_string_destruct init_dfa free_workarea_compile parse create_initial_state analyze free_dfa_content re_string_construct
parse_sub_exp postorder create_tree fetch_token free_tree parse_reg_exp
re_string_context_at bitset_contain
init_word_char
create_ci_newstate register_state free_state re_node_set_init_copy
update_cur_sifted_state check_subexp_limits re_acquire_state sift_states_bkref add_epsilon_src_nodes
parse fetch_token create_tree parse_reg_exp
rpl_re_set_syntax
rpl_re_set_registers
rpl_regerror
```

*Output* (Whoops! Too long for SE to handle.)

# Answer
> 6 votes
# Haskell, 512 bytes

```
import Data.List
r=reverse
n j|let(w,s)#p|let a?b=or[q!b<GT|(q,r)<-i,a==r,elem q(h p)>elem(a,q)i];a!b|a==b=EQ|a?b||(a<b)>b?a=LT;_!_=GT;l=nub.sortBy(!)$h p;m(v,s)q|h q==[]=(v,[q]:s)|elem q w=(v,[q++" ..."]:s)|(w,x:y)<-(v,[])#q=(w,(q:(u"| "=<<r y)++u"  "x):s)=foldl m(l++w,[])l;c(p,q)=z$p:q:h q;y=z=<<j;i=iterate(nub.sort.(c=<<))y!!length j;h""=[p|p<-id=<<j,and[elem(p,r)i|(r,q)<-i,p==q]];h p=[r|(q,r)<-y,p==q]=unlines=<<r(snd$mempty#"")
u s(x:y)=("+-"++x):map(s++)y
z(x:y)=(,)x<$>y
main=interact$n.map words.lines

```

Run online at Ideone

---
Tags: code-golf, ascii-art, graph-theory
---


title: Match strings with wildcards

text:
# Question
Title: Match strings with wildcards
Problem: given any input string that does not contain null bytes, determine whether or not the input string matches glob as defined below:

```
null   is disallowed in both string in glob
*      matches zero or more characters
**     is disallowed in glob
?      matches exactly 1 character
[ch]   matches a character class of the specified characters
       to include ] in a class, it must be the first character
[^ch]  matches a character class of all but specified characters
       to include ] in a class, it must be the first character after ^

The empty glob only matches the empty string.

```

The system glob() on the target platform implements glob where * doesn't match a /, so you can't use it. This has infested all shells. You could try converting to a regex; however this won't be as easy it it looks.

You must specify an encoding for your program. Your program must be valid in that encoding. All bytes including null are allowed in cp437. Your score is the number of characters in your encoding.

Bonus: If your program is expressed in a well-known encoding that uses 6 or fewer bits, your score is multiplied by the number of bits used in the encoding and divided by 7. Your program will be passed its arguments in ASCII in that case.

Your program will receive the string to match or not as the first argument and the glob pattern as the second argument. Your return code must be 0 on match and nonzero on nonmatch.

You may leave it undefined what happens if you get passed a disallowed glob.

Standard loopholes are disallowed; however the following are allowed:

```
 You may compress your program but it must work if executed directly.
 Binaries are allowed. Submit a disassembly with it so I can read it.
 Using two different chars which look the same is allowed.
 You may use trigraphs (but I can't see how it helps).

```

Examples:

```
"w*c*d" matches "wildcard" but doesn't match "wildcards"
"ww*w*d" matches "wwwdwd" but doesn't match "wwd"
"ww*[w-c]?*" matches "www-" and "wwcc" but doesn't match "wwc"
"[a-c]" matches "-" but doesn't match "b"
"^[*][^]]" matches "^*[" but doesn't match "^?[" or "^*]" or "**]"

```

# Answer
> 5 votes
## Common Lisp, ~~368~~ 340

Encoding is implementation-dependent, but UTF-8 is generally supported among implementations (see also the set of standard characters that must be supported).

```
(ql:quickload'cl-ppcre)(lambda(s g)(ppcre:scan(do(e(L(coerce g'list))c p)((not L)`(:sequence,@(reverse e):end-anchor))(push(case(setf c(pop L))(#\*'(:regex".*"))(#\? :everything)(#\[(prog1`(,(or(and(char=(car L)#\^)(pop L):inverted-char-class):char-class),@(subseq L 0(setf p(position #\] L :start 1))))(setf L(nthcdr(1+ p)L))))(t c))e))s))

```

### Pretty-printed

```
(lambda (s g)
  (cl-ppcre:scan
   (do (e
        (l (coerce g 'list))
        c
        p)
       ((not l) `(:sequence ,@(reverse e) :end-anchor))
     (push
      (case (setf c (pop l))
        (#\* '(regex".*")
        (#\? :everything)
        (#\[
         (prog1
             `(,(if (char= (car l) #\^)
                    (prog1 :inverted-char-class (pop l))
                    :char-class)
               ,@(subseq l 0 (setf p (position #\] l :start 1))))
           (setf l (nthcdr (1+ p) l))))
        (t c))
      e))
   s))

```

Converting to regex is not so hard when using non-string representations of regexes. `CL-PPCRE` is a regular expression library by Edi Weitz which accepts two ways of defining such expressions:

* the usual string-based syntax, or
* a more lispy approach using a DSL

Today I answered a question about alternative syntaxes for regular expressions, and this challenge is a good example of why a structured format can be useful instead of strings.

### Example

For the following glob, `"ww*[w-c]?*"`, the regular expression being built is described by this form:

```
(:sequence #\w
           #\w
           (:regex ".*")
           (:char-class #\w #\- #\c)
           :everything
           (:regex ".*"))

```

And we match `"www-"`. The `(:char-class ...)` list takes indiviudal charaters, which does not need escaping like it would if I wrote `"[w-c]"` as a string regex.

### Test suite

```
(loop for (glob match no-match) in
      '(("w*c*d"      ("wildcard")    ("wildcards"))
        ("ww*w*d"     ("wwwdwd")      ("wwd"))
        ("ww*[w-c]?*" ("www-" "wwcc") ("wwc"))
        ("[a-c]"      ("-")           ("b"))
        ("^[*][^]]"   ("^*[")         ("^?[" "^*]" "**]"))
        ("w*\\*s"     ("wild\\ness")  ()))

      for matchp = (lambda(s)(funcall *fun* s glob))

      always (every matchp match)
      never (some matchp no-match))

=> T

```

# Answer
> 3 votes
# MUMPS, ~~397~~ 387 bytes

Note that this code uses features of Caché ObjectScript (specifically, the `*` designator in a `$EXTRACT` call) and does not conform to the ANSI MUMPS standard.

```
f(g,s) f i=1:1:$L(g) d
    . s c=$E(g,i) i 'm s:"*?[]"'[c p=p_"1"""_c_"""" s:c="*" p=p_".E" s:c="?" p=p_"1E"
    . i c="]" s p=p_"1"_$E(b,1,*-1)_")" s m=0
    . s:c="[" a=$E(g,i+1)="^",m=a+1,b="(",i=i+a
    . i m s:$E(g,i+1)="]" d=1 s k=$F(g,"]",i+d)-2+d,r=$E(g,i+1,k),i=k
    . f j=1:1:$L(r) s:m=1 b=b_"1"""_$E(r,j)_""","
    . i m=2 f j=0:1:127 s:r'[$C(j) b=b_"1"""_$S(j=34:"""""",1:$C(j))_""","
    q s?@p

```

Haha, OP! I've foiled your plans! Sure, your glob syntax might be tricky to convert to a regex, but my language *has no regexes*! Instead, it has a crippled form of "pattern matching" (see docs, section 5.7) that happens to be pretty much exactly powerful enough to handle these globs.

Basically, what the code does is it converts OP-style globs into a string corresponding to the pattern match, and then evals that string, and tests the input string against the result of that eval. The one tricky point is that MUMPS pattern matches don't have a notion of an inverted character class (`[^abc]`), so we instead have to construct a character class consisting of all the ASCII characters except the ones specified in in the inverted character class.

Here are some correspondences between OP-style globs and MUMPS pattern matches:

```
OP              MUMPS
-----------------------------------------------------------
w*c*d           1"w".E1"c".E1"d"
ww*w*d          1"w"1"w".E1"w".E1"d"
ww*[w-c]?*      1"w"1"w".E1(1"w",1"-",1"c")1E.E
[a-c]           1(1"a",1"-",1"c")
^[*][^]]        [doesn't print well, because of the inverted character class thing]

```

There is probably room for additional golfing here. Here is an ungolfed version:

```
match(glob,string) ;
    ; the golfed version assumes a clean symbol table; here, I've explicitly cleaned it.
    new i,pattern,char,mode,buffer,range,advance,delta,j,k
    for i=1:1:$LENGTH(glob) do
    . set char=$EXTRACT(glob,i)
    . if ("*?[]"'[char),(mode=0) do
    . . set pattern=pattern_"1"""_char_"""" ; 1 of `char`
    . if (char="*"),(mode=0) do
    . . set pattern=pattern_".E" ; 0+ of any character
    . if (char="?"),(mode=0) do
    . . set pattern=pattern_"1E" ; 1 of any character
    . if (char="]") do
    . . set pattern=pattern_"1"_$EXTRACT(buffer,1,$LENGTH(buffer)-1)_")"
    . . set mode=0
    . if (char="[") do
    . . set advance=($EXTRACT(glob,i+1)="^") ; 0 or 1
    . . set mode=advance+1 ; 1 = in a char class; 2 = in an inverted char class
    . . set buffer="(" ; begin constructing an alternation
    . . set i=i+advance
    . if (mode'=0) do
    . . if ($EXTRACT(glob,i+1)="]") do
    . . . set delta=1
    . . . set k=$FIND(glob,"]",i+delta)-2+delta
    . . . set range=$EXTRACT(glob,i+1,k)
    . . . set i=k
    . for j=1:1:$LENGTH(range) do
    . . if (mode=1) do
    . . . set buffer=buffer_"1"""_$EXTRACT(range,j)_"""," ; add a character to the alternation
    . if (mode=2) do
    . . for j=0:1:127 do
    . . . if (range'[$CHAR(j)) do
    . . . . set buffer=buffer_"1"""_$SELECT(j=34:"""""",1:$CHAR(j))_""","
    quit string?@pattern ; eval `pattern` and test `string` against it, and return the outcome (0 or 1)

```

# Answer
> 2 votes
# Ceylon, ~~3514~~ ~~2586~~ ~~2360~~ ~~2248~~ ~~2228~~ ~~2196~~ ~~2059~~ ~~1882~~ ~~1620~~ ~~1147~~ ~~1130~~ ~~858~~ ~~830~~ ~~693~~ 658 bytes

```
import ceylon.language{B=Boolean,S=String,C=Character,o=false,r=process}shared void g(){B n(B(S)l,B(S)r)(S c)=>any{for(i in 0..c.size)l(c[0:i])&&r(c[i...])};B q(S c)=>c.size==1;B d({C*}s,B n)(S c){if(q(c),exists i=c[0]){return n!=i in s;}return o;}[B(S),S]h(S r){assert(exists s=r[0],exists e=r.firstOccurrence(']'));return[s=='^'then d(r[1..e],true)else d(r[...e],false),r[e+1...]];}B(S)p(S x){if(exists f=x[0]){value r=(f=='*'then[(S c)=>true,x.rest])else(f=='?'then[q,x.rest])else(f=='['then h(x.rest))else[d({f},o),x.rest];return n(r[0],p(r[1]));}else{return S.empty;}}assert(exists x=r.arguments[1],exists c=r.arguments[0]);r.exit(p(x)(c)then 0else 1);}

```

It seemed first that converting the glob to regular expressions is the easiest, but it also means escaping everything which is special in regular expressions but not in our globs ... I might try this in a different answer.

*Due to popular demand I removed most of the the how-I-got-there .. who is interested, can have a look into the history.*

So I build a new (limited) regexp-like matching engine, and a parser to convert our wildcard strings into such strings. (And some boiler plate for command line access and return code generation.)

Here is the same program formatted (i.e. with added whitespace) and with some documentation annotations:

```
import ceylon.language {
    B=Boolean,
    S=String,
    C=Character,
    o=false,
    r=process
}
"""A glob evaluation program.
   Takes two command line arguments, first is a candidate string,
   second one is a wildcard expression.

    Exits with code 0 if the expression is well-formed and
    matches the candidate, otherwise exits with 1.
   """
shared void g() {
    """A string predicate build from a left and a right predicate.
       It matches a string if that can be split in two substrings
       so the first one is matched by the left expression and
       the second one by the right expression.
       """
    B n(B(S) l, B(S) r)(S c) =>
            any {
        for (i in 0..c.size) l(c[0:i]) && r(c[i...])
    };

    """An expression which matches any string of length 1 (i.e. a single character).
       This corresponds to the question mark (`?`), therefore the name.
       """
    B q(S c) => c.size == 1;

    """A character class, i.e. an expression which matches any string of length 1,
       as long at it is (or is not) in a given list of characters.
       """
    B d(
        "The characters to be matched (or excluded)"
        {C*} s,
        "Is this negated? If true, matches only characters not in the list."
        B n)
            (
        "The candidate string."
        S c) {
        if (q(c), exists i = c[0]) {
            return n != i in s;
        }
        return o;
    }

    """Parses a started character class (i.e. the stuff after the `[`).

       Returns a tuple of the constructed matching function
       and the remaining string to be parsed for further expressions.
       """
    throws (`class AssertionError`, "if the expression is not well-formed, i.e. there is no `]` following.")
    [B(S), S] h(S r) {
        assert (exists s = r[0], exists e = r.firstOccurrence(']'));
        return [s == '^' then d(r[1..e], true) else d(r[...e], false), r[e + 1 ...]];
    }

    """Parses an glob expression from a string.
       Returns a string predicate.
       """
    B(S) p(
        "The string with the wildcard expression."
        S x) {
        if (exists f = x[0]) {
            value r = (f == '*' then [(S c) => true, x.rest])
                    else (f == '?' then [q, x.rest])
                    else (f == '[' then h(x.rest))
                    else [d({ f }, o), x.rest];
            return n(r[0], p(r[1]));
        } else {
            return S.empty;
        }
    }
    assert (exists x = r.arguments[1], exists c = r.arguments[0]);
    r.exit(p(x)(c) then 0 else 1);
}

```

I'm not sure if this is actually readable enough ... see the history of this answer for the original version with more readable names (and which was using interfaces and objects instead of just functions).

Some used tricks to make this shorter:

* import with alias – we use `String`, `Boolean` and `Character` quite often, so give them one-letter aliases. When we are already doing this, adding the renaming for `process` (used three times) and `false` (used twice) doesn't take much overhead. (This only helps for stuff used several times – the ceylon.language stuff is imported automatically, so we have some overhead here.)
* The `possibleMatchLengths` method was an optimization for speed – not needed when we are code-golfing. (I guess this can make matching quite slow in some extreme cases.)
* the Implementations of the `string` attribute was also removed, it was just there for debugging the initial versions.
* Instead of the implementations of the `Glob` interface in the first versions, we have just functions `Boolean(String)` (or `B(S)` in our short format), which saves quite some braces and `class`/`object`, and some functions returning such functions. Ceylon has a nice syntax for defining functions which return functions, used for the GlobList `g` and the CharacterClass `c` – simply a function with multiple argument lists.
* I unified the methods for `CharacterClass` and `NegatedCharacterClass`, passing a boolean parameter for `negated`. It is used as `negated != i in chars` (shorter `n!=i in s`) instead of having one function with `i in s` and one with `!i in s` (and both having the remaining conditions twice).
* The object/function emptyGlob was replaced by the static Reference `String.empty` (written `S.empty`, of course).
* Where a function consists of just one return statement, we can write it with the "fat arrow" notation and save the braces and the `return`.
* If such a function is used just once, sometimes we can put it directly where used, as an anonymous function definition. This is used for the `*` implementation.
* The function `q` (for the question mark) is in addition used in the definition of the character class function `d`, as `q(c)` is shorter than `c.size==1`.
* Instead of first defining a value with `value f = ...` or even with type `Character f = ...` and then doing an `if (exists f) {` or `assert(exists f);`, we can move the definition into the `if` or `assert`, saving some characters.
* If we want to pass an iterable constructed from a comprehension to a function (like the `any` function used in the definition of `g`), we can write `any{...}` instead of `any({...})` – this is the named argument syntax, which converts its last entry, if it's a comprehension, into an iterable, if the function accepts that.

# Answer
> 2 votes
## Python 3, 209 207 bytes

The general strategy is transforming the glob spec into a regex. That's accomplished by a function `r`, passed as the replacement parameter to `re.sub()`, (or `s()` in this case). If no match is found, a run-time error is thrown, causing a positive exit code.

```
import sys,re
_,t,g=sys.argv
s=re.sub
def r(m):a,b,c,d,e=m.groups();return a and s(r"(?=[-\\])",r"\\",a)or b and".*"or c and"."or d and"\\"+d or e
re.match(s(r"(\[\^?.+?\])|(\*)|(\?)|(\W)|(.)",r,g)+"$",t).re

```

The patterns produced for the example globs show how it works.

```
Glob            Regex pattern
w*c*d           w.*c.*d$
ww*w*d          ww.*w.*d$
ww*[w-c]?       ww.*[w\-c].$
[a-c]           [a\-c]$
^[*][^]]        \^[*][^]]$
a[\]b           a[\\]b

```

# Answer
> 2 votes
# CJam, 125

```
{AC+:A;}:F;0alqW+:X;{"*?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)
^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F"N/T=S/(C#=~}fCX,(\-!

```

CJam has no regular expressions (yet), so I just implemented the wildcard matching directly.
The encoding here is plain old ASCII (I might try some compression tricks later).

Try it online

**Explanation:**

The idea is to go through the pattern (glob) and keep a list of indices possibly reached so far in the input string. Initial list is `[0]`, `?` advances all indices by 1, `*` goes to all indices from the minimum reached so far to the end of the string, and character sets and other non-special characters just select the indices that match and advance them by 1. At the end, the string matches if the list of indices contains the string length.

Character sets are constructed on the fly and recorded as a string A and a boolean flag B (for positive/negative match), and used when reaching the closing `]`.

```
{…}:F;      define a function F
  AC+:A;    add variable C to variable A (A+=C)
0a          push [0] (initial array of indices, let's call it I)
             it will be kept and updated on the stack
l           read the first input line (containing the pattern)
q           read the rest of the input (the string to match)
W+          append the number -1 (as an array element, following the characters)
             this is a dummy guard value that avoids costly empty-string checks
:X;         save the array in X
{…}fC       for each character C in the pattern
  "…"       push that long string, containing code to handle various cases
  N/        split into (two) lines
  T=        get the T'th line; T is 1 when parsing a character set and 0 otherwise
             (T is initially 0 by default)
  S/        split by space into an array of strings
  (         take out the first item (containing special characters to check)
  C#        find the index of C in that string
  =         get the corresponding string from the array
             (when C is not found, # returns -1 which gets the last array item)
  ~         execute that string
X,(         get the length of X and decrement it
             (to get the length of the input string)
\-          calculate the set difference between it and I (the list of indices)
             the result is empty (false) iff I contained the string length
!           negate, to obtain the final 1/0 result

```

Now the long string with various pieces of code. Each line has a few characters to check and then a block for handling each one, and the default case.

First line: `*?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)`

```
*?[       special characters to look for
######### first block, corresponding to character *
_         duplicate I on the stack
{…}&      if I is not empty
  0=      get the first (smallest) index from I
  X,      get the length of X (1 longer than the input string)
  ,       make an array [0 1 2 … length(input string)]
  >       slice the array starting at the smallest index from I
######### second block, corresponding to character ?
:)        increment all items of I
######### third block, corresponding to character [
1:T       set T=1, causing the next characters to be processed with the 2nd line
:B;       also set B=1, the boolean flag signifying positive match
L:A;      initialize A (the array of characters) with an empty string/array
######### last block, corresponding to other regular characters
{…},      filter I's items, using the block as a boolean condition
  X=      get the character from X at the given index (it wraps around)
           if the input string was empty, this will be -1 (the dummy value)
  C=      compare to C (the current character in the pattern)
:)        increment the remaining indices

```

Second line (for character sets): `^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F`

```
^]        special characters to look for
######### first block, corresponding to character ^
A!B&      calculate not(A) & B, which is 1 (true) iff A is empty and B is 1
{…}       if true (first character and positive match, i.e. we're at "[^")
  0:B;    set B=0 (switch to negative match)
{…}       else
  F       call F, which just adds the character C to A
?         end if
######### second block, corresponding to character ]
A{…}      if A is not empty (it's a closing "]")
  0:T;    set T to 0, switching back to the first line
  {…},    filter I's items, using the block as a boolean condition
    X=    get the character from X at the given index
           if the input string was empty, this will be -1
    A-    calculate the set difference between it and A
    !     negate, obtaining 1 if the character was in A and 0 if it was not
    B=    compare to B (the positive/negative match indicator)
  :)      increment the remaining indices
{…}       else (A is empty, i.e. we're at "[]" or "[^]")
  F       call F to add the character to A
?         end if
######### last block, corresponding to other regular characters
F         call F

```

# Answer
> 2 votes
# Perl, 88 bytes

```
$_=pop;s/((\*)|\?)|(\[\^?\]?)(.*?)\]|\W/$1?".$2":$3?qr#$3\Q$4\E]#:"\\$&"/eg/pop=~/^$_\z/

```

The encoding is ASCII. This works by translating to regular expressions with regular expressions. It exits with a division by zero error (hence, nonzero status) on match failure.

Some ideas adapted from recursive’s Python solution.

---
Tags: code-golf, string
---


title: Python Golfing Suggestions

text:
# Question
Title: Python Golfing Suggestions
I have read: Tips for golfing in Python

I would like to golf this code further. Any more tips?

```
x,y,q,w=[int(i) for i in raw_input().split()]
while 1:
 a=int(input())
 s=d=""
 if q>x:
  s="W"
  q-=1
 elif q<x:
  s="E"
  q+=1
 if w>y:
  d="N"
  w-=1
 elif w<y:
  d="S"
  w+=1
 print d+s

```

The program: You move on a map which is 40 wide by 18 high. Thor is initially placed on a random spot on the map and must reach the light of power as quickly as possible. You need to have the shortest code possible.

During each turn, you must specify in which direction to move, from one of the following:

N (North) NE (North-East) E (East) SE (South-East) S (South) SW (South-West) W (West) NW (North-West)

YOU WIN WHEN THOR REACHES THE LIGHT OF POWER.

YOU LOSE: if Thor moves off the map. if Thor doesn't have enough energy left to reach the light of power.

EXAMPLE: THOR STARTS ON THE MAP ON THE SQUARE (3, 6). THE LIGHT OF POWER IS ON SQUARE (3, 8).

TURN 1 THOR MOVES SOUTHWARDS. NEW POSITION = (3, 7). THOR HAS ENOUGH ENERGY LEFT FOR 10 MOVES

TURN 2 THOR MOVES SOUTHWARDS. NEW POSITION = (3, 8). THOR HAS ENOUGH ENERGY LEFT FOR 9 MOVES

The program must first read the initialization data from standard input. Then, within an infinite loop, read the data from the standard input related to Thor's current state and provide to the standard output Thor's movement instructions.

INITIALIZATION INPUT: Line 1: 4 integers indicate the position of the light of power. 2 indicate Thor’s starting position.

INPUT FOR ONE GAME TURN: Line 1: The level of Thor’s remaining energy. This represents the number of moves he can still make.

OUTPUT FOR ONE GAME TURN: A single line providing the move to be made: N NE E SE S SW W or NW

Edit : it's a code golf on codingame.com

# Answer
> 4 votes
### N.B.: This may not be entirely correct as I don't know what your code is supposed to do

The first thing to do is remove unnecessary whitespace, especially that after the if statements:

```
x,y,q,w=[int(i) for i in raw_input().split()]
while 1:
 a=int(input())
 s=d=""
 if q>x:s="W";q-=1
 elif q<x:s="E";q+=1
 if w>y:d="N";w-=1
 elif w<y:d="S";w+=1
 print d+s

```

This golfs your code down by 4 bytes.

What would be ideal for this challenge is a switch case which, unfortunaley, does not exist in Python. Instead we can be clever with an array's index:

```
x,y,q,w=[int(i) for i in raw_input().split()]
while 1:
 a=int(input())
 s=d=""
 exec(['s="W";q-=1','s="E";q+=1'][q<x])
 exec(['d="N";w-=1','d="S";w+=1'][w<y])
 print d+s

```

Saving you *x* bytes.

Finally you can get rid of all whitespace now:

```
x,y,q,w=[int(i) for i in raw_input().split()]
while 1:a=int(input());s=d="";exec(['s="W";q-=1','s="E";q+=1'][q<x]);exec(['d="N";w-=1','d="S";w+=1'][w<y]);print d+s

```

---
Tags: code-golf, tips, python
---


title: Confidant Numbers

text:
# Question
Title: Confidant Numbers
# Confidant Numbers

Let `x` be an integer of an arbitrary base, such that `D` is an array of its digits. `x` is a Confidant Number if, for all `n` between `1` and the length of `D`:

```
D[n+1] = D[n] + D[n-1] + ... + D[1] + n

```

---

Take, for example, the number `349` in base 10. If we label the indices for this number, we have the following.

```
Index    Digit
-----    -----
1        3
2        4
3        9

```

Starting from the first digit, we have `1 + 3 = 4`, which yields the next digit. Then with the second digit we have `3 + 4 + 2 = 9`, which, again, yields the next digit. Thus, this number is a Confidant Number.

---

Given an integer with a base between 1 and 62, calculate all the Confidant Numbers for that base, and output a list of them, separated by newlines. You can assume that there is a finite amount of Confidant Numbers for a given base.

For digits greater than 9, use the alpha characters `A-Z`, and for digits greater than `Z` use the alpha characters `a-z`. You will not have to worry about digits beyond `z`.

They do not have to be output in any particular order.

---

Sample Input:

```
16

```

Sample Output:

```
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
12
23
34
45
56
67
78
89
9A
AB
BC
CD
DE
EF
125
237
349
45B
56D
67F
125B
237F

```

This is code golf, so the shortest code wins. Good luck!

(Thanks to Zach for helping out with the formatting and pointing out a few problems.)

# Answer
# Pyth, 38 bytes

```
0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ

```

Try it online: Demonstration

### Explanation:

```
0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ  implicit: Q = input base
0                                       print 0
                       m            SQ  map each d of [1, 2, ..., Q] to:
                        .u       Q]d      start with N=[d], apply v Q times
                          +N+lNsN           add (len(N) + sum(N)) to N
                                          gives all intermediate results
                      s                 join to one list of candidates
                 f<eTQ                  filter those, where every digit < Q
  ms@L+s`MT+rG1Gd                       convert numbers to letters 0-9A-Za-z
 j                                      print each on separate line

```
> 2 votes

# Answer
## Python 2, 104 bytes

```
n=input()
for i in range(n):
 s=''
 while i<n:s+=chr(48+i+(i>9)*7+i/36*6);print s;i+=n**0**i+i*(s>s[:1])

```

This uses the following observation: in a confidant number, the digit `i` is followed by `2*i+1`, except it's `i+1` instead for the second digit. By trying all possible first digits and adding more digits until they get too big, we can generate all confidant numbers.

We compute the character corresponding the number `i` as `chr(48+i+(i>9)*7+i/36*6)`, which shifts it into the number, uppercase letter, or uppercase letter range for the intervals `0-9, 10-35, 36-61`.

Then, we increase `i` via `i+=i+1` with two adjustments. To make this instead `i+=1` after the first digit, we add `i` conditional on `s` having more than `1` chars. Also, we need to avoid numbers starting with 0 from being printed, while at the same time allowing `0`. To do this, we do a hack that causes `i=0` to fail the condition `i<n` on the next loop by adding `n` to it. This is done by replacing `1` with `n**0**i`, which right-associates to `n**(0**i)`, which equals `n**(i==0)` or `n if i==0 else 1`.
> 9 votes

# Answer
# Python 3, ~~201~~ 200 bytes

```
n=int(input())
X=[[i]for i in range(1,n)]
for x in X:
 y=sum(x)+len(x)
 if y<n:X.append(x+[y])
X=[[0]]+X
print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X))

```

### Explanation

The key insight here is that given a sequence `x` (like, say, `[1,2,5]`), you can get the next term in the sequence with `sum(x)+len(x)`, which gives `11` in this case (`B`). Check to see if this is less than `n`, and if it is, add the extended sequence to the list of all such sequences (seeded by all single digits).

```
[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)]

```

This is how I map sequence items to characters. These are `''.join`ed together and then printed, separated by newlines.
> 4 votes

# Answer
## GS2, 44 bytes

```
26 c8 2f 08 4d 08 40 64 45 2e 30 42 67 40 24 d0
75 d3 20 e1 35 09 cb 20 23 78 22 09 34 30 e0 32
08 86 84 30 85 30 92 58 09 34 10

```

It produces the numbers in a different order, but the problem description doesn't specify, so I'm going for it! Here's the output for input of 16.

```
1
12
125
125B
2
23
237
237F
3
34
349
4
45
45B
5
56
56D
6
67
67F
7
78
8
89
9
9A
A
AB
B
BC
C
CD
D
DE
E
EF
F
0

```

Here are the mnemonic equivalents for the bytes:

```
read-num dec save-a
range1
{
    itemize
    {
        dup
        sum
        over length
        add

        swap right-cons

        dup last push-a le

            push-d eval
        block2 when
    }
    save-d eval
    init inits tail
} map

+ ' fold

{
    ascii-digits
    uppercase-alphabet catenate
    lowercase-alphabet catenate
    select
    show-line
} map

0

```
> 4 votes

# Answer
# CJam, ~~46~~ ~~42~~ 40 bytes

```
ri:R,{Q{+_A,s'[,_el^+f=oNo__,+:+_R<}g&}*

```

Try it online in the CJam interpreter.

### How it works

```
ri:R            e# Read an integer from STDIN and save it in R.
,               e# Push [0 ... R-1].
{               e# Fold; For each element but the first:
                e#   Push the element.
  Q             e#   Push an empty array (accumulator for base-R digits).
  {             e#   Do:
    +           e#     Concatenate the integer and the array on the stack.
    _           e#     Push a copy of the result.
    A,s'[,_el^+ e#     Push "0...0A...Za...z".
                e#     See: http://codegolf.stackexchange.com/a/54348
    f=          e#     Replace each base-R digit with the corresponding character.
    oNo         e#     Print the resulting string and a linefeed.
    _           e#     Push another copy of the accumulator.
    _,+         e#     Append its length to it.
    :+          e#     Add all digits (including the length).
    _R<         e#     Push a copy of the result and compare it with R.
  }g            e#   If the sum is less than R, it is a valid base-R digit,
                e#   the comparison pushes 1, and the loop is repeated.
  &             e#   Intersect the accumulator with an integer that is greater
                e#   or equal to R. This pushes an empty array.
}*              e#

```

At the end **0** and a few empty arrays are left on the stack, so the interpreter prints `0`.
> 3 votes

# Answer
# gawk, 111 bytes

```
{for(n=$0;n>c=++i;)for(j=0;n>$++j=c+=j;print"")for(c=k=0;k++<j;c+=$k)printf"%c",$k+($k>9?$k>35?61:55:48)}$0="0"

```

For every starting digit from `1` to `base-1` it calculates the next digits, and while these are lower than the base we still have a confidant number. Calculating the next digit while printing. Finally prints `0`.
> 1 votes

---
Tags: code-golf, number
---


title: Greater Average Submatrix

text:
# Question
Title: Greater Average Submatrix
## Objective

Write a program in any language that reads a matrix from `stdin` in which all columns are space delimited and all rows are newline delimited. The program must output a sub matrix so as that there is no other sub matrix with greater average, this sub matrix' average value, as well as the starting and ending coordinates. Each sub matrix must be at least 2x2. The initial matrix can be an m *x* n matrix where 2 \< m \< 256 and 2 \< n \< 512. For each element e, you know that -1000000 \< e \< 1000000

## Example Inputs

A)

```
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18

```

B)

```
1 1 1
1 1 1
1 1 1

```

## Example Output

A)

```
Sub Matrix:
11 12
17 18
Average of all values:
14.5
Starting Coordinates:
[4,0]
Ending Coordinates:
[5,1]

```

B)

```
Sub Matrix:
1 1
1 1
Average of all values:
1
Starting Coordinates:
[0,0]
Ending Coordinates:
[1,1]

```

## Rules

You may not use any matrix related library provided for your language but you may use lists, arrays, tables, dictionaries and all the operations that can be performed without including / importing anything in your language.

## Scoring

1. You get one point for every additional byte of code.
2. You get one point for every variable you use (even if it's a list).
3. You get one point for every function / method (including lambda / anonymous) you use.
4. The winner is the solution with the fewest points.

# Answer
> 1 votes
# MATLAB, 332 + 9 + 7 = 348

The code:

```
v=str2num(input(''));s=size(v);d=[];e={};for m=1:s(1)-1 for n=1:s(2)-1 for o=1:s(1)-m for p=1:s(2)-n q=v(o:m+o,p:n+p);e=[e {q}];d=[d;mean(q(:)) o p o+m p+n];end;end;end;end;[~,m]=max(d(:,1));disp('Sub Matrix:');disp(e{m});fprintf('Average of all values:\n%f\nStarting Coordinates:\n[%d,%d]\nEnding Coordinates:\n[%d,%d]\n',d(m,1:5))

```

And an explanation

```
%Functions used (7):
%    input str2num size mean max disp fprintf
%Variables used (9):
%    v s d e m n o p q

v=str2num(input('')); %Convert to matrix (new lines and spaces are correctly handled by str2num to form dimensions)
s=size(v); %Dimensions of n.
d=[];
e={};
for m=1:s(1)-1
    %Loop through all widths from 2 up to the width of the matrix (-1 to save doing that later)
    for n=1:s(2)-1
        %Loop through all heights from 2 up the the width of the matrix (-1 to save doing that later)
        for o=1:s(1)-m
            for p=1:s(2)-n
                %Extract the sub array
                q=v(o:m+o,p:n+p);
                %Store the sub array in a cell array so we don't have to extract it later.
                e=[e {q}];
                %Append to the list the details (mean and indicies) of this sub array.
                d=[d;mean(q(:)) o p o+m p+n];
            end
        end
    end
end
%Find the index of the sub array with the largest mean
[~,m]=max(d(:,1));
%And print the output
disp('Sub Matrix:');
disp(e{m});
fprintf('Average of all values:\n%f\nStarting Coordinates:\n[%d,%d]\nEnding Coordinates:\n[%d,%d]\n',d(m,1:5))

```

`input` asks for you to enter the matrix. Because MATLAB struggles with new lines, you need to type something like `['1 2 3 4' 10 '5 6 7 8']` Note that the 10 is the new line character. This basically just forms the array exactly as your string would be (the `'` and `[]` are not passed in to the code)

# Answer
> 0 votes
# Matlab, 386 = 366 + 12 + 8

I assumed that we have to make outputs exactly formatted like the output example.

Variables:

```
a,N,r,c,M,i,j,k,l,P,p,n

```

Functions:

```
input,char,str2num,numel,reshape,mean,disp,sprintf

```

Code (added newlines and indenteation for readability):

```
a=input('');
N=char(10);
r=sum(a==N);
a(a==N)=32;
a=str2num(a);
c=numel(a)/r;
a=reshape(a,r,c);
M=-inf;
for i=1:r-1;
    for j=1:c-1;
        for k=i+1:r;
            for l=j+1:c;
                P=a(i:k,j:l);
                p=mean(P(:));
                if p>M(1);
                    M=[p,i,j,k,l];
                    n=P;
                end;
            end;
        end;
    end;
end;
disp('Sub Matrix:');
disp(n);c='ing Coordinates:\n[%d,%d]\n';
disp(sprintf(['Average of all values\n%d\nStart',c,'End',c],M(1),M(2),M(3),M(4),M(5)))

```

---
Tags: code-challenge
---


title: The Attack of the Knights

text:
# Question
Title: The Attack of the Knights
## Objective

You have two knights on a standard chessboard labelled 1-8 and A-H, one knight is located at 1C and the other at 2G. You have to write a program in the language of your choosing that accepts a set of coordinates from `stdin`, like 2C, and then calculates which of the two knights you have to move in order to capture the enemy pawn at the provided coordinates with the least amount of moves assuming it is standing still. The program must also output which are these moves that the knight has to make.

## Example Usage

```
# echo 1C|./faster
Move Knight: 1C
Moves:

```

Also

```
# echo 3B|./faster
Move Knight: 1C
Moves: 1C -> 3B

```

One more

```
# echo 5A|./faster
Move Knight: 1C
Moves: 1C -> 3B
Moves: 3B -> 5A

```

Output shall be exactly as shown.

## Useful Resources

Knight's Tour

## Bonuses

You get -50 Bytes if your program is expandable and works with N knights.

# Answer
> 1 votes
# Mathematica ~~1183~~ 483 bytes (or 190) bytes

## Approach 1

240-50 (bonus) = 190 bytes

The knight's tour can be represented as a graph. So the issue becomes simply to find the shortest path from each knight to the pawn. Mathematica offers both `KnightTourGraph` and `FindShortestPath` as built-in functions.

```
w@p_:=Characters@p/.{r_,s_}:>(ToCharacterCode[s][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(v~Mod~8/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~h~k_:=Row[SortBy[(z/@FindShortestPath[8~KnightTourGraph~8,#,w@p])&/@w/@k,Length][[1]],"->"]

```

**Examples**

```
h["5A",{"1C","2G"}]

```

> 1C -\> 3B -\> 5A

```
h["8G",{"1C","2G"}]

```

> 2G -\> 3E -\> 5D -\> 7E -\> 8G

---

## Approach 2

(533-50 (bonus)= 483 bytes)

Here the knight's tour graph is constructed without using `KnightTourGraph`.

```
s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less][Quotient[v-1,8]+1,#2],v+#3,Nothing]&@@@{{1,2,-17,1,1},{8,2,-15,0,1},{2,1,-10,1,1},{7,1,-6,0,1},{2,8,6,1,0},{7,8,10,0,0},{1,7,15,1,0},{8,7,17,0,0}})
w@p_:=Characters[p]/.{r_,q_}:>(ToCharacterCode[q][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(Mod[v,8]/.{0 -> 8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~f~k_:=Row[SortBy[(z/@FindShortestPath[Graph[Range@64,Union@Flatten[s/@Range@64]],#,w@p])&/@w/@k,Length][[1]],"->"]

```

---

## Explanation

Below are two views of the chessboard. On the left, each chessboard position corresponds to vertex bearing an integer name. On the right, the positions have been labelled according to the convention suggested by the OP.

In both figures, White sits on the right, Black sits on the left.

Legal moves of a knight are paths along a knight tour graph.

The function, `s`, generates all 512 moves (as if each square allowed for 8 knight moves), eliminates inverses, and then weeds out the moves that would land off the board. There are 168 edges on the graph.

`edges` consists of a list of elements of the form, `UndirectedEdge[a,b]`. For instance, the edge, `UndirectedEdge[1,11]`corresponds to the idea that a knight at vertex 1, that is, at "A1" in standard notation, may jump to vertex 11, or "B3", and vice-versa.

`toVertex` takes a position (see right board) and returns a vertex (see left board). For instance `toVertex["3H"]` returns `59`.

`toChessPosition` does the opposing conversion, namely from a vertex to a chess position.

`vertexNames` is a list of replacements: `{1->"1A",2->"2A"...64->"8H"}`. This is only needed for the right chessboard figure shown above.

`numberedKnightsTour`is the graph displayed above on the left.

`chessKnightsTour`is the graph displayed above on the right.

The graphs are constructed using the above-defined vertices and edges.

`findShortestPath` receives the position of the pawn and a list of positions of the knights and finds the shortest path along the graph from a knight to the pawn.

```
    s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less]
edges=Union@Flatten[s/@Range@64];
toVertex[p_]:=Characters[p]/.{rank_,file_}:> (ToCharacterCode[file][[1]]-65)*8+ToExpression[rank]
toChessPosition[v_]:=ToString@(Mod[v,8]/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
vertexNames=Thread[Range@64->(toChessPosition[#]&/@Range[64])];
numberedKnightsTour=Graph[Range@64,edges,VertexLabels->"Name",GraphLayout->"SpringEmbedding"];
vertexNames=Thread[Range[64]->(toChessPosition[#]&/@Range[64])];
chessKnightsTour=Graph[Range@64,edges,ImageSize->Large,VertexLabels-> vertexNames,GraphLayout->"SpringEmbedding"];
GraphicsGrid[{{numberedKnightsTour,chessKnightsTour}},PlotLabel->"For each board below, \nWhite sits at Right, Black at Left\nNumbers refers to rank, letters refer to file",ImageSize->Large]
    findShortestPath[pawn_,knights_]:=Row[SortBy[(toChessPosition/@FindShortestPath[chessKnightsTour,#,toVertex@pawn])&/@toVertex/@knights,Length][[1]],"->"]

```

---

---
Tags: code-golf, chess
---


title: Tree traversing

text:
# Question
Title: Tree traversing
Have you heard about trees?

When performing DFS on a binary tree, you can traverse it in 3 possible orders.

* Root, left node, right node (Pre-order)
* Left node, Root, right node (In-order)
* Left node, right node, root (Post-order)

Check wikipedia to know more.

For this challenge, you have to provide a program that, given **the pre and in order traverses** of a tree returns the **original tree**.

Example 1:

**Inputs** Preorder:

```
[1 2 3 4 5 6 7]

```

In order:

```
[2 1 4 3 6 5 7]

```

Returns:

```
[1 [2 3 [4 5 [6 7]]]]

```

NOTES:

**Result notation**

```
[a [b c]]

```

Node `a` is the parent of nodes `b` and `c`. However in this one

```
[a [b [c]]]

```

Node `a` is the parent of node `b`, but it's `b` in this case the parent of `c`.

**More considerations**

* The tree might not be balanced.
* For every 2 traverses, the original tree is unique.
* Submissions can be programs and functions.
* The input format has to be a sequence of numbers representing the order in which the nodes are visited.
* The output format must be exactly as specified above.
* Shortest code in bytes wins.

Good luck

# Answer
> 1 votes
# Haskell, 114 bytes

```
[a]#_=show a
(a:b)#c|(d,_:e)<-span(/=a)c,(f,g)<-splitAt(length d)b=[a]#c++" ["++f#d++' ':g#e++"]"
a?b='[':a#b++"]"

```

Example run:

```
*Main> [1,2,3,4,5,6,7]?[2,1,4,3,6,5,7]
"[1 [2 3 [4 5 [6 7]]]]"

```

---
Tags: code-golf, binary-tree
---


title: A real sausage fest

text:
# Question
Title: A real sausage fest
Since the first weekend of October is drawing near, let's have our own Oktoberfest!

## Background

You and some other programmers have been hired by the local sausage guys in Munich, Germany. The sausage guys provide Oktoberfest with all the sausages the giant Volksfest needs. You manage to overhear your boss speaking to the other employees about why you and the others were hired without any previous sausage-related experience. You realize you were hired for your impeccable programming skills - and your boss apparently wants you to code a sausage analyzer.

This year around, the sausage guys have decided to increase the variety of sausages at Oktoberfest - but they have no idea of how much they've imported.

## Challenge

You need to help your boss figure out how much sausage of a certain kind they've actually imported. You will have to program a sausage analyzer which outputs the kind and number of every sausage the sausage guys have imported. Your boss has bought a special floppy drive for this occasion which, given a sausage, pipes it to `stdin`.

## Input

A number of sausages on `stdin`, each sausage separated by one space. Sausages are given on the following format:

**Prinskorv (P)**

```
 ¤
| |
| |
| |
 ¤

```

**Salchichón (S)**

```
 l
| |
| |
| |
| |
 l

```

**Landjäger (L)**

```
\ /
| |
| |
| |
| |
/ \

```

**Kabanos (K)**

```
.
|
|
|
|
|
.

```

**Cotechino Modena (C)**

```
 ___
|   |
|   |
|   |
|___|

```

**Rød pølse (R)**

```
 ^
| |
| |
| |
| |
 v

```

## Output

The occurrences of a given sausage along with an identifier of which kind of sausage it is, separated by a space. The identifier is the first letter in the name of the sausage. Order is not important.

Output shall be written to `stdout`, trailing newlines and spaces are allowed.

## Examples

**Input**

```
 ^   ^   ^   ^  .
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
 v   v   v   v  |
                .

```

**Output**

```
4R 1K

```

**Input**

```
\ /  ___   l   ¤   ¤
| | |   | | | | | | |
| | |   | | | | | | |
| | |   | | | | | | |
| | |___| | |  ¤   ¤
/ \        l

```

**Output**

```
1L 1C 1S 2P

```

**Input**

```
 l   ¤   l
| | | | | |
| | | | | |
| | | | | |
| |  ¤  | |
 l       l

```

**Output**

```
2S 1P

```

The programmer with the shortest program in bytes gets paid by the sausage guys (wins)!

# Sausage trivia

> **Prinskorv**
> *Prinskorv which directly translates to "prince-sausage" is a small Swedish sausage which is often sold in links. Usually fried in a frying pan and served with a generous helping of mustard.*
> **Salchichón**
> *Salchichón is a Spanish summer sausage often made with pork, although some recipes use other meats including ox, veal or horse. The meat and fat are chopped in thin bits, seasoned with salt, pepper, nutmeg, oregano, and garlic and then inserted in thick natural pork intestines.*
> **Landjäger**
> *Landjäger is a semi-dried sausage traditionally made in Southern Germany, Austria, Switzerland, and Alsace. It is popular as a snack food during activities such as hiking. It also has a history as soldier's food because it keeps without refrigeration and comes in single-meal portions.*
> **Kabanos**
> *Kabanos is a Polish long thin dry sausage made of pork or kosher turkey. They are smoky in flavour, and can be soft or very dry in texture depending on freshness. Kabanosy are often seasoned only with pepper. Unlike other meats, these sausages are typically eaten alone as an appetiser and, except when kosher, often served with cheese.*
> **Cotechino Modena**
> *Cotechino Modena or Cotechino di Modena is a fresh sausage made from pork, fatback, and pork rind, and comes from Modena, Italy, where it has PGI status. Cotechino is often served with lentils or cannellini beans with a sauce alongside mashed potatoes, especially around the New Year.*
> **Rød pølse**
> *Rød pølse (red sausage) is a type of brightly red, boiled pork sausage very common in Denmark. Since hot dog stands are ubiquitous in Denmark, some people regard røde pølser as one of the national dishes.*
> *All sausage information shamelessly copied from Wikipedia*

# Answer
> 8 votes
# Pyth, 30 bytes

```
jdm+hd@"SKLCRP"%Ced45rS-czd\/8

```

Try it online: Demonstration or Test Suite

### Explanation:

As all other participants I only look at the first line of the input. Let's say the first line of the input is `\ / ___ l ¤ ¤ ____`.

At first I split by spaces, which gives me the list

```
['\\', '/', '', '___', '', '', 'l', '', '', '¤', '', '', '¤', '', '___']

```

Now we want to get ride of `'/'`s and `''`s and sort the remaining thing.

```
['\\', '___', '___', 'l', '¤', '¤']

```

Now I can run-length-encode it.

```
[[1, '\\'], [2, '___'], [1, 'l'], [2, '¤']]

```

As it turns out, the order (ascii-value) of these chars or of the string `'___'` can be mapped nicely to the numbers `[0, 1, 2, 3, 4, 5]`.

```
char/string |  l   .   \    ___    ^   ¤
-------------------------------------------
value       | 108  46  92 6250335  94 164
value%45    |  18   1   2      15   4  29
(value%45)%6|   0   1   2       3   4   5

```

And this can be used to map them directly to the letters `SKLCRP`.

```
jdm+hd@"SKLCRP"%Ced45rS-czd\/8
                        czd     split the input string at spaces
                       -   \/   remove "/"s (and also ""s)
                      S         sort
                     r       8  run-length-encode
  m                             map each pair d of ^ to:
   +hd                            d[0] +
                Ced               convert d[1] to a number
               %   45             mod 45
      @"SKLCRP"                   take the ^th element in the string (mod 6)
jd                              join by spaces

```

# Answer
> 19 votes
# Pyth, ~~36~~ ~~34~~ ~~32~~ 30 bytes

```
XjdsMrShM-czd\\8"¤_l/^.KRLSCP

```

Saved yet *another* 2 bytes thanks to...guess who? :D

Ignores all the input except for the first line, removes all the `/`s and spaces, translates it to the target identifiers, sorts it, uses run-length encoding, and prints the result.

Live demo.

## 32-byte version

```
XjdsMrS-hMfTczd\\8"¤_l/^.KRLSCP

```

Live demo.

Saved another 2 bytes thanks to @Jakube!

## 34-byte version

```
jdsMrSX-hMfTczd\\"¤_l/^.KRLSCP")8

```

Live demo.

Saved 2 bytes thanks to @Jakube!

## 36-byte version

```
jdsMrSX-hMfTczd\/"¤_l\\^.""PCSLRK"8

```

Live demo.

# Answer
> 8 votes
# CJam, ~~38~~ ~~35~~ 33 bytes

```
l'_%'C*"l¤\^./""SPLRK "erS-$e`S*

```

Test it here.

## Explanation

The first line of each type of sausage is unique, and since the sausages are aligned at the top, it's sufficient to count the relevant characters in that first line. Two types require special treatment:

* **Landjäger (L)** have both `\` and `/`. We want to get rid of one of them, then we can count the other one like all the other characters.
* **Cotechino Modena (C)** have three underscores, so we need to divide the underscore count by 3. However, it's actually shorter to treat underscores individually by simply replacing runs of them in the input (which will always belong to only one sausage) with the target character `C` right away.

Now for the actual code:

```
l         e# Read one line from STDIN.
'_%       e# Split on runs of underscores.
'C*       e# Join back together by C's.
"l¤\^./"  e# Push a string with characters corresponding to each type, and a slash.
"SPLRK "  e# Push a string with the corresponding letters and a space.
er        e# Transliterate, turning each identifying character into the correct
          e# letter and all slashes into spaces.
S-        e# Remove spaces (which also gets rid of what used to be slashes).
$         e# Sort the string to group each letter.
e`        e# Run-length encode.
S*        e# Join by spaces.

```

# Answer
> 8 votes
# Javascript (ES6), 105

```
a=>[...'¤l/._^'].map((g,h)=>(f=(a.split(g).length-1)/'222261'[h],f?f+'PSLKCR'[h]:0)).filter(b=>b).join` `

```

It's pretty simple but here's an explanation anyway:

```
input=>
  // list of all unique characters of the sausages
  [...'¤l/._^'].map((sausage_char, index)=>(
    // find all occurrences of the character in the string
    occurrences = (input.split(sausage_char).length - 1)
      / '222261'[index], // divide by the number of that character in its sausage
      // when dividing and multiplying by numbers in strings, JS automatically casts them
    occurrences ? // is there anything for this sausage?
      occurrences + 'PSLKCR'[index] : // add the sausage's letter and count
      0 // return 0 so it can be filtered out
  ))
  // filter out the 0s
  .filter(b=>b)
  // return a space-separated string
  .join` `

```

# Answer
> 6 votes
# Mathematica 116

Some bytes could probably shaved off, but nothing to approach the golfing languages.

```
Row[Row/@Reverse/@Tally@ImportString[#,"Table"][[1]]/.{"¤"->"P","l"->"S","/"->"L","___"->"C","."->"K","^"->"R"}," "] &

```

`ImportString[#,"Table"][[1]]` returns a list of space-separated strings appearing in the top line of the input. The string may include any of the elements in the list, `{"¤","l","/","___",".","^"}`, including repeats. Each element is associated with a unique type of sausage.

`Tally` counts the number of times each such string appears.

`/.{"¤"->"P","l"->"S",...` replaces `¤` with `P`, `l` with `S` and so on.

`Reverse` places each tally before the item it is associated with.

The two `Row`s format the output.

# Answer
> 6 votes
# MATLAB, 113

Assuming that trailing spaces are allowed (yep they are), here is a MATLAB anonymous function:

```
@(a)arrayfun(@(p,m)fprintf([(m>32&&p)*'%d%c ' ''],p,m),histc(strtok(strrep(a,'___','_'),10),'./\^_l¤'),'K LRCSP')

```

And an explanation:

```
@(a) %Anonymous function, with an input a
    arrayfun(@(p,m) %Loop through the two input arrays (see later)
                   fprintf( %Print to console
                           [(m>32&&p)*'%d%c ' ''] %Essentially this means if p>0 and m>' ', print an integer followed by a char, then a space
                                                 ,p,m) %The values from the array input is what is getting printed
                                                      ,histc( %Make an array of how many times
                                                                       strtok(strrep(a,'___','_'),10), %Keep only the first line (as that is where the interesting bit is) and also replace ___ with _ for the 'C'
                                                             './\^_l¤'), %these inputs appear (which will be passed in turn as the 'p' variable to cellfun)
                                                                        'K LRCSP' %These are the characters to be printed with the count representing each sausage (it will be placed in the 'm' input of arrayfun)
             )

```

Appears to work correctly. Still has the trailing space, but now handles all sausages correctly.

# Answer
> 3 votes
## Perl, ~~84~~ 77 bytes

Someone could probably shave a bit off of this...

## 84 bytes

```
($s=<>)=~y|_^\.l\\¤|CRKSLP|d;$$_++for split//,$s;$C/=3;for(A..Z){print"$$_$_ "if$$_}

```

## 77 bytes

```
$$_++for split//,<>=~y|_^\.l\\¤|CRKSLP|dr;$C/=3;for(A..Z){print"$$_$_ "if$$_}

```

Breakdown:

Take first line of STDIN, transliterate values into letter codes, delete extra garbage. The `d` modifier shouldn't really be necessary, but I ran into weird unicode issues on the `¤` character without it.

Use symbolic reference to create and/or increment variable for each character found.

```
$$_++ for split //, <> =~ y|_^\.l\\¤|CRKSLP|dr;

```

Divide C variable by 3, due to triple-underscore

```
$C /= 3;

```

Loop through alphabet and print single-letter capital variables along with letter *if* they have a value greater than zero

```
for (A..Z) {
    print "$$_$_ " if $$_;
}

```

Test result: http://ideone.com/alpUlI

**Edit**: Chop 7 bytes by having transliterate pass anonymous return value directly into `split`.

# Answer
> 2 votes
## Perl, 172 bytes

Daresay more can be sliced off this sausage still, but here's a starter for ten.

```
$a=<>;$a=~s/¤/h/g;$a=~s/_+/_/g;$a=~s/(\/| |\n)//g;$a=~s/\\/x/g;$h{$_}++ for split(//,$a);foreach (sort keys %h){print $h{$_};$_=~tr/^.hlx_/RKPSLC/;print "$_ ";}print "\n"

```

Ungolfed version

```
$a=<>;              # get 1st line
$a=~s/¤/h/g;        # convert ¤ to h, avoid unicode hassles
$a=~s/_+/_/g;       # multiple consecutive _ to single _
$a=~s/(\/| |\n)//g; # strip / and spaces
$a=~s/\\/x/g;       # convert \\ to x to avoid regexp hassles

# build hash that counts occurences of character
$h{$_}++ for split(//,$a);

# print the answers
foreach (sort keys %h) {
 print $h{$_};
 $_=~tr/^.hlx_/RKPSLC/;
 print "$_ ";
}
print "\n";

```

Test results

```
$ perl meaty.pl <test1.txt
1K 4R
$ perl meaty.pl <test2.txt
1C 2P 1S 1L
$ perl meaty.pl <test3.txt
1P 2S
$

```

# Answer
> 2 votes
## Python 3, 120 bytes

I'm pretty sure you can shorten this, but there wasn't already a Python solution so here we go:

```
x=input()
a={z:x.count(y)for y,z in zip('¤l/.^_','PSLKRC')}
a['C']//=3
print(' '.join(str(a[x])+x for x in a if a[x]))

```

## Explanation

It's pretty simple, some might even say readable, but here's a short explanation anyway:

First one line of input is read, since each sausage can be determined from just the first line.

Now `a={z:x.count(y)for y,z in zip('¤l/.^_','PSLKRC')}` is a dictionary comprehension that maps the identifier of each type of sausage (`z`) to the count of each type of sausage (`x.count(y)`, where `y` is the sausage defining character).

We then divide the count of **Cotechino Modena (C)** sausages by 3 because of the triple underscore.

Finally we print out the result: `print(' '.join(str(a[x])+x for x in a if a[x]))`. This creates the output count of each sausage one at a time, but only if that sausage was seen at least once (`a[x]` is not zero =\> Truthy). Each count string is joined by a space and printed out.

---
Tags: code-golf
---


# Question
Title: Drop of Chaos (Constructing a Minimally Aperiodic Sequence)
The idea here is to produce an *almost* repeating pattern. That is, the sequence being constructed changes at the last moment to avoid a repetition of some subsequence. Subsequences of the type AA and ABA are to be avoided (where B is no longer than A).

## Examples:

I'll go ahead and start by listing all of the small examples to make my description clearer. Let's start with 0.

```
Valid:   0

Invalid: 00    (AA pattern)
Valid:   01

Invalid: 010   (ABA pattern)
Invalid: 011   (AA pattern)
Valid:   012

Valid:   0120
Invalid: 0121  (ABA pattern)
Invalid: 0122  (AA pattern)

Invalid: 01200 (AA pattern)
Invalid: 01201 (ABA pattern; 01-2-01)
Invalid: 01202 (ABA pattern)
Valid:   01203

```

Now, I strongly believe that a `4` is never needed, though I do not have a proof, because I have easily found sequences of hundreds of characters long that use only `0123`. (It's probably closely related to how only three characters are needed to have infinite strings that do not have any AA patterns. There's a Wikipedia page on this.)

## Input/Output

Input is a single, positive, non-zero integer `n`. You may assume that `n <= 1000`.

Output is an `n`-character sequence with no subsequences that match either prohibited pattern (AA or ABA).

### Sample inputs and outputs

```
>>> 1
0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

```

## Rules

* Only the characters `0123` are allowed.
* B is no longer than A. This is to avoid the situation where `012345` has to be followed by `6` because `0123451` has this: `1-2345-1`. In other words, the sequence would be trivial and uninteresting.
* `n` may be inputted through any method desired, **except** hard-coding.
* Output may be either a list or a string, depending on which is easier.
* **No brute force**; the run time should be on the order of minutes, at most an hour on a really slow machine, for `n=1000`. (This is intended to disqualify solutions that just loop through all `n`-length permutations of `{0,1,2,3}`, so that trick and similar tricks are disallowed.)
* Standard loopholes are disallowed, as usual.
* Scoring is in bytes. This is , so the shortest entry wins (probably - see bonus).
* **Bonus:** pick the lowest allowed digit at each step. If `1` and `3` are possible choices for the next digit in the sequence, pick `1`. Subtract **5** bytes from your score. However, take note of the note below.

## Note!

Dead-ends are possible. Your program or function must avoid these. Here's an example:

```
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130120
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130123
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310320
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310321301203102130

```

Each of these sequences cannot be extended any further (without using a `4`). But also note that there is a crucial difference between the first two and the second two. I'll replace the shared initial subsequence with an `X` to make this clearer.

```
Stump: X2130120
Stump: X2130123
Stump: X320
Stump: X321301203102130

```

The last two digits of `X` are `10`, so the only possible choices for the next digit are `2` and `3`. Choosing `2` leads to a situation where the sequence *must* terminate. **The greedy algorithm will *not* work here.** (Not without backtracking, anyway.)

# Answer
# Retina, 86 bytes - 5 = 81

```
$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

```

Where `<empty>` represents an empty trailing line. You can run the above code from a single file with the `-s` flag.

The input should be given in unary, e.g. `111111`. I haven't tested it for output on the order of thousands yet - two of the regexes might get a bit slow after a while - but it can easily handle a couple of hundred in a few seconds.

## Explanation

This is a simple backtracking solution.

1. Append a `0`.
2. While the current sequence is invalid, remove all trailing 3s and increment the last non-`3`.
3. Repeat until we have a valid sequence of the desired length.

This backtracking is implemented by a loop of regex substitutions which aborts once the string remains unchanged through one iteration.

```
$
_

```

This appends a `_` to the input, which is used to separate the unary input from the sequence we're building.

```
(r`^(?<-2>.)+_((.)+)\b$
$1!

```

This is the first substitution in the loop (indicated by the leading `(`). The regex matches if a) there is a word character (i.e. a digit) at the end the string (which means the string is valid - we'll see below that invalid sequences are marked with a trailing `#`) and b) there are at least as many characters in the sequence as in the input (this is checked using balancing groups). If that's the case, we remove the input and append a `!`. This `!` serves to make all regexes in the loop fail, such that it terminates.

```
\b$
0

```

If there is a word character at the end (i.e. the sequence is valid, and the loop wasn't terminated by the previous step), append a `0`.

```
3#
#

```

If (instead) the sequence had been marked invalid and ended in `3`, we remove that `3` (but leave the sequence as invalid, because there's no possible continuation for the current prefix... so the next character needs to be backtracked as well).

```
0#
1
1#
2
2#
3

```

If the sequence is marked invalid and any digit other than `3` is at the end, we increment the digit and remove the marker.

```
)r`\1(?<-2>.)*((.)+)$
$0#

```

The last substitution in the loop (as indicated by the `)`). It checks whether the string ends in `ABA` (where `B` is not longer than `A` but potentially empty). The relative lengths of `A` and `B` are again checked using balancing groups, and the repetition of `A` is checked with a simple backreference.

If this regex matches, we mark the sequence invalid by appending `#`.

```
!
<empty>

```

Once the loop terminates, all we need to do is remove the `!` and are then left with the desired output.
> 6 votes

# Answer
# Python 2, 175 - 5 = 170 bytes

```
n=input();s='';u=j=-1
while n>len(s):
 while u>2:u=int(s[0]);s=s[1:]
 u+=1;t=`u`+s;m=c=0
 while t[c:]*0**m:c+=1;i=t[c:].find(t[:c]);m=j<i<=c
 if c>=len(t):s=t;u=j
print s[::j]

```

This is the greedy algorithm with backtracking. I wish it were shorter. I hope it's correct (see below).

It builds the string one digit at a time. Given a string of `d` digits that it has found already, it tries to append a `0` as the `(d+1)`st digit. If that doesn't work, then it tries a `1`, then a `2`, then a `3`. If none of these works, then it goes back to the `d`th digit and increments it (if less than `3`) or removes it (if equal to `3`, in which case it increments the previous one, etc.).

The check for validity is the line with `.find` in it. In case anyone decides to read my code, I should say that this program is actually storing the string backwards, meaning that it's adding digits to the *front*. So the check involves looking for places where the *first* `c` digits appear again later on in the string (anyplace after the first `c` digits), and if there are any such places, whether the intervening length is at most `c`.

(Of course it reverses the string before printing.)

It could also easily be faster; I originally had it exiting various loops early for efficiency, but that cost precious bytes. It still does OK in the range of `n=1000`, though.

Anyway, the program does seem to exhibit a preference for the smaller digits, but it's not a very strong preference. For example, running it with `n=2000` gave me a string with `523` zeros, `502` ones, `497` twos and `478` threes, ending in `30210312013021`. So if anyone else is working on a greedy algorithm, maybe they can confirm this result. Or with `n=1000` I got `[263, 251, 248, 238]` for the counts by digit.

Finally, I would mention that these counts are sort of suggestive of symmetry, almost (though not exactly) as if we had started with a uniform distribution and then converted some of the `3`'s to `0`'s and a few of the `2`'s to `1`'s. But obviously that could just be coincidence. I have no idea!
> 2 votes

# Answer
# Haskell, 115 (120 bytes − 5 bonus)

```
x?_|or[t x==t(drop i x)|i<-[1..length x],t<-[take$div(i+1)2]]=[]
x?0=[x]
x?n=(?(n-1)).(:x)=<<"0123"
f=reverse.head.([]?)

```

Run online at Ideone

Example run:

```
*Main> f 40
"0120310213012310320130210312013210230120"

```
> 1 votes

---
Tags: code-golf, sequence, subsequence
---