A well linked challenge
$begingroup$
An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write $abcbac$ and then I would draw the lines as:
Or I might write $abbcac$
Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the $b$s (or everything else)
If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.
Note that some strings can be drawn in multiple ways. For example $bbbb$ can be drawn in both of the following ways (and a third not included):
or
If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not strongly linked. (so $bbbb$ is not strongly linked)
Task
Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.
In addition your program must be a well linked string meaning
Every character appears an even number of times in your program.
It should output the truthy value when passed itself.
Answers will be scored as their lengths in bytes with fewer bytes being a better score.
Hint
A loop can be drawn around a contiguous substring iff there each character appears an even number of times in that substring.
Test Cases
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
code-golf decision-problem restricted-source
$endgroup$
add a comment |
$begingroup$
An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write $abcbac$ and then I would draw the lines as:
Or I might write $abbcac$
Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the $b$s (or everything else)
If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.
Note that some strings can be drawn in multiple ways. For example $bbbb$ can be drawn in both of the following ways (and a third not included):
or
If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not strongly linked. (so $bbbb$ is not strongly linked)
Task
Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.
In addition your program must be a well linked string meaning
Every character appears an even number of times in your program.
It should output the truthy value when passed itself.
Answers will be scored as their lengths in bytes with fewer bytes being a better score.
Hint
A loop can be drawn around a contiguous substring iff there each character appears an even number of times in that substring.
Test Cases
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
code-golf decision-problem restricted-source
$endgroup$
1
$begingroup$
Test case:abcbca -> False
.
$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
I think your hint contains a superfluousthere
.
$endgroup$
– Jonathan Frech
2 hours ago
add a comment |
$begingroup$
An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write $abcbac$ and then I would draw the lines as:
Or I might write $abbcac$
Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the $b$s (or everything else)
If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.
Note that some strings can be drawn in multiple ways. For example $bbbb$ can be drawn in both of the following ways (and a third not included):
or
If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not strongly linked. (so $bbbb$ is not strongly linked)
Task
Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.
In addition your program must be a well linked string meaning
Every character appears an even number of times in your program.
It should output the truthy value when passed itself.
Answers will be scored as their lengths in bytes with fewer bytes being a better score.
Hint
A loop can be drawn around a contiguous substring iff there each character appears an even number of times in that substring.
Test Cases
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
code-golf decision-problem restricted-source
$endgroup$
An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write $abcbac$ and then I would draw the lines as:
Or I might write $abbcac$
Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the $b$s (or everything else)
If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.
Note that some strings can be drawn in multiple ways. For example $bbbb$ can be drawn in both of the following ways (and a third not included):
or
If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not strongly linked. (so $bbbb$ is not strongly linked)
Task
Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.
In addition your program must be a well linked string meaning
Every character appears an even number of times in your program.
It should output the truthy value when passed itself.
Answers will be scored as their lengths in bytes with fewer bytes being a better score.
Hint
A loop can be drawn around a contiguous substring iff there each character appears an even number of times in that substring.
Test Cases
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
code-golf decision-problem restricted-source
code-golf decision-problem restricted-source
asked 3 hours ago
TRITICIMAGVSTRITICIMAGVS
34.2k10156367
34.2k10156367
1
$begingroup$
Test case:abcbca -> False
.
$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
I think your hint contains a superfluousthere
.
$endgroup$
– Jonathan Frech
2 hours ago
add a comment |
1
$begingroup$
Test case:abcbca -> False
.
$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
I think your hint contains a superfluousthere
.
$endgroup$
– Jonathan Frech
2 hours ago
1
1
$begingroup$
Test case:
abcbca -> False
.$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
Test case:
abcbca -> False
.$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
I think your hint contains a superfluous
there
.$endgroup$
– Jonathan Frech
2 hours ago
$begingroup$
I think your hint contains a superfluous
there
.$endgroup$
– Jonathan Frech
2 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
Try it online!
The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.
The next line first Ġ
roups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ
), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃ
it of each count and ask whether there Ẹ
xists a truthy (nonzero) value.
Therefore, this helper link returns whether a substring cannot be circled.
In the main link, we take all substrings of the input (Ẇ
), Ṗ
op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç
) on €
ach substring. The result is then whether Ạ
ll substrings cannot be circled.
$endgroup$
add a comment |
$begingroup$
Retina, 41 bytes
Lw`.+
N$^`
$.&
0A`
%O`.
(.)1
^.+(¶.+)+$
Try it online! Link includes test cases. Explanation:
Lw`.+
List all of the substrings. (This lists the odd ones as well, but we don't care.)
N$^`
$.&
0A`
Sort the substrings in reverse order of length so that we can remove the original string.
%O`.
Sort the characters in each substring.
(.)1
Remove duplicated characters, thus checking whether they appear an even number of times.
^.+(¶.+)+$
Check whether no substring could be circled.
$endgroup$
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179422%2fa-well-linked-challenge%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
Try it online!
The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.
The next line first Ġ
roups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ
), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃ
it of each count and ask whether there Ẹ
xists a truthy (nonzero) value.
Therefore, this helper link returns whether a substring cannot be circled.
In the main link, we take all substrings of the input (Ẇ
), Ṗ
op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç
) on €
ach substring. The result is then whether Ạ
ll substrings cannot be circled.
$endgroup$
add a comment |
$begingroup$
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
Try it online!
The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.
The next line first Ġ
roups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ
), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃ
it of each count and ask whether there Ẹ
xists a truthy (nonzero) value.
Therefore, this helper link returns whether a substring cannot be circled.
In the main link, we take all substrings of the input (Ẇ
), Ṗ
op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç
) on €
ach substring. The result is then whether Ạ
ll substrings cannot be circled.
$endgroup$
add a comment |
$begingroup$
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
Try it online!
The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.
The next line first Ġ
roups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ
), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃ
it of each count and ask whether there Ẹ
xists a truthy (nonzero) value.
Therefore, this helper link returns whether a substring cannot be circled.
In the main link, we take all substrings of the input (Ẇ
), Ṗ
op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç
) on €
ach substring. The result is then whether Ạ
ll substrings cannot be circled.
$endgroup$
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
Try it online!
The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.
The next line first Ġ
roups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ
), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃ
it of each count and ask whether there Ẹ
xists a truthy (nonzero) value.
Therefore, this helper link returns whether a substring cannot be circled.
In the main link, we take all substrings of the input (Ẇ
), Ṗ
op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç
) on €
ach substring. The result is then whether Ạ
ll substrings cannot be circled.
edited 2 hours ago
answered 2 hours ago
Doorknob♦Doorknob
54.4k17114347
54.4k17114347
add a comment |
add a comment |
$begingroup$
Retina, 41 bytes
Lw`.+
N$^`
$.&
0A`
%O`.
(.)1
^.+(¶.+)+$
Try it online! Link includes test cases. Explanation:
Lw`.+
List all of the substrings. (This lists the odd ones as well, but we don't care.)
N$^`
$.&
0A`
Sort the substrings in reverse order of length so that we can remove the original string.
%O`.
Sort the characters in each substring.
(.)1
Remove duplicated characters, thus checking whether they appear an even number of times.
^.+(¶.+)+$
Check whether no substring could be circled.
$endgroup$
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
add a comment |
$begingroup$
Retina, 41 bytes
Lw`.+
N$^`
$.&
0A`
%O`.
(.)1
^.+(¶.+)+$
Try it online! Link includes test cases. Explanation:
Lw`.+
List all of the substrings. (This lists the odd ones as well, but we don't care.)
N$^`
$.&
0A`
Sort the substrings in reverse order of length so that we can remove the original string.
%O`.
Sort the characters in each substring.
(.)1
Remove duplicated characters, thus checking whether they appear an even number of times.
^.+(¶.+)+$
Check whether no substring could be circled.
$endgroup$
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
add a comment |
$begingroup$
Retina, 41 bytes
Lw`.+
N$^`
$.&
0A`
%O`.
(.)1
^.+(¶.+)+$
Try it online! Link includes test cases. Explanation:
Lw`.+
List all of the substrings. (This lists the odd ones as well, but we don't care.)
N$^`
$.&
0A`
Sort the substrings in reverse order of length so that we can remove the original string.
%O`.
Sort the characters in each substring.
(.)1
Remove duplicated characters, thus checking whether they appear an even number of times.
^.+(¶.+)+$
Check whether no substring could be circled.
$endgroup$
Retina, 41 bytes
Lw`.+
N$^`
$.&
0A`
%O`.
(.)1
^.+(¶.+)+$
Try it online! Link includes test cases. Explanation:
Lw`.+
List all of the substrings. (This lists the odd ones as well, but we don't care.)
N$^`
$.&
0A`
Sort the substrings in reverse order of length so that we can remove the original string.
%O`.
Sort the characters in each substring.
(.)1
Remove duplicated characters, thus checking whether they appear an even number of times.
^.+(¶.+)+$
Check whether no substring could be circled.
answered 1 hour ago
NeilNeil
80.3k744178
80.3k744178
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
add a comment |
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
1
1
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
$begingroup$
This seems not to satisfy the restricted source requirements.
$endgroup$
– Ørjan Johansen
1 hour ago
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179422%2fa-well-linked-challenge%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Test case:
abcbca -> False
.$endgroup$
– Ørjan Johansen
2 hours ago
$begingroup$
I think your hint contains a superfluous
there
.$endgroup$
– Jonathan Frech
2 hours ago